44 int16_t half_pitch = pitch / 2 - 1;
50 else if (half_pitch < 0)
52 lead_flag = 1 << half_pitch;
56 sq_sum = offset * offset;
64 if (x == array_origin) {
67 for (ind = 0; ind <= half_pitch; ind++) {
70 fwd_balance |= lead_flag;
74 back_balance = cutpts[x - 1 - array_origin].back_balance << 1;
75 back_balance &= lead_flag + lead_flag - 1;
78 fwd_balance = cutpts[x - 1 - array_origin].fwd_balance >> 1;
79 if (projection->
pile_count (x + half_pitch) > zero_count)
80 fwd_balance |= lead_flag;
99 float projection_scale,
106 int16_t balance_count;
115 int16_t half_pitch = pitch / 2 - 1;
120 else if (half_pitch < 0)
122 lead_flag = 1 << half_pitch;
124 back_balance = cutpts[x - 1 - array_origin].back_balance << 1;
125 back_balance &= lead_flag + lead_flag - 1;
128 fwd_balance = cutpts[x - 1 - array_origin].fwd_balance >> 1;
129 if (projection->
pile_count (x + half_pitch) > zero_count)
130 fwd_balance |= lead_flag;
139 for (
index = x - pitch - pitch_error;
index <= x - pitch + pitch_error;
141 if (
index >= array_origin) {
142 segpt = &cutpts[
index - array_origin];
143 dist = x - segpt->xpos;
148 lead_flag = back_balance ^ segpt->fwd_balance;
150 while (lead_flag != 0) {
152 lead_flag &= lead_flag - 1;
156 for (balance_index = 0;
157 index + balance_index < x - balance_index;
169 r_index = segpt->region_index + 1;
170 total = segpt->mean_sum + dist;
171 balance_count += offset;
173 dist * dist + segpt->sq_sum + balance_count * balance_count;
174 mean = total / r_index;
175 factor = mean - pitch;
177 factor += sq_dist / (r_index) - mean * mean;
184 mid_cuts = segpt->mid_cuts + mid_cut;
185 region_index = r_index;
201 int16_t array_origin,
207 float projection_scale,
213 int16_t balance_count;
222 int16_t half_pitch = pitch / 2 - 1;
227 else if (half_pitch < 0)
229 lead_flag = 1 << half_pitch;
231 back_balance = cutpts[x - 1 - array_origin].back_balance << 1;
232 back_balance &= lead_flag + lead_flag - 1;
235 fwd_balance = cutpts[x - 1 - array_origin].fwd_balance >> 1;
236 if (projection->
pile_count (x + half_pitch) > zero_count)
237 fwd_balance |= lead_flag;
247 if (
index >= array_origin) {
248 segpt = &cutpts[
index - array_origin];
249 dist = x - segpt->xpos;
253 lead_flag = back_balance ^ segpt->fwd_balance;
255 while (lead_flag != 0) {
257 lead_flag &= lead_flag - 1;
262 r_index = segpt->region_index + 1;
263 total = segpt->mean_sum + dist;
264 balance_count += offset;
266 dist * dist + segpt->sq_sum + balance_count * balance_count;
267 mean = total / r_index;
268 factor = mean - pitch;
270 factor += sq_dist / (r_index) - mean * mean;
276 mid_cuts = segpt->mid_cuts + mid_cut;
277 region_index = r_index;
292 BLOBNBOX_IT *blob_it,
297 int16_t projection_left,
298 int16_t projection_right,
299 float projection_scale,
300 int16_t &occupation_count,
301 FPSEGPT_LIST *seg_list,
311 int16_t array_origin;
314 int16_t best_left_x = 0;
315 int16_t best_right_x = 0;
325 FPSEGPT_IT seg_it = seg_list;
334 if ((pitch - 3) / 2 < pitch_error)
335 pitch_error = (pitch - 3) / 2;
346 for (left_edge = projection_left; projection->
pile_count (left_edge) == 0
347 && left_edge < projection_right; left_edge++);
348 for (right_edge = projection_right; projection->
pile_count (right_edge) == 0
349 && right_edge > left_edge; right_edge--);
351 if (pitsync_linear_version >= 4)
353 pitch, pitch_error, projection,
354 projection_scale, occupation_count, seg_list,
356 array_origin = left_edge - pitch;
358 std::vector<FPCUTPT> cutpts(right_edge - left_edge + pitch * 2 + 1);
359 for (x = array_origin; x < left_edge; x++)
361 cutpts[x - array_origin].setup(&cutpts[0], array_origin, projection,
362 zero_count, pitch, x, 0);
363 for (offset = 0; offset <= pitch_error; offset++, x++)
365 cutpts[x - array_origin].setup(&cutpts[0], array_origin, projection,
366 zero_count, pitch, x, offset);
374 while (x < right_edge - pitch_error) {
375 if (x > this_box.
right () + pitch_error && blob_index < blob_count) {
382 if (x <= this_box.
left ())
384 else if (x <= this_box.
left () + pitch_error)
385 offset = x - this_box.
left ();
386 else if (x >= this_box.
right ())
388 else if (x >= next_box.
left () && blob_index < blob_count) {
389 offset = x - next_box.
left ();
390 if (this_box.
right () - x < offset)
391 offset = this_box.
right () - x;
393 else if (x >= this_box.
right () - pitch_error)
394 offset = this_box.
right () - x;
404 cutpts[x - array_origin].assign (&cutpts[0], array_origin, x,
405 faking, mid_cut, offset, projection,
406 projection_scale, zero_count, pitch,
411 best_fake = INT16_MAX;
412 best_cost = INT32_MAX;
413 best_count = INT16_MAX;
414 while (x < right_edge + pitch) {
415 offset = x < right_edge ? right_edge - x : 0;
416 cutpts[x - array_origin].assign (&cutpts[0], array_origin, x,
417 false,
false, offset, projection,
418 projection_scale, zero_count, pitch,
420 cutpts[x - array_origin].terminal =
true;
421 if (cutpts[x - array_origin].index () +
422 cutpts[x - array_origin].fake_count <= best_count + best_fake) {
423 if (cutpts[x - array_origin].fake_count < best_fake
424 || (cutpts[x - array_origin].fake_count == best_fake
425 && cutpts[x - array_origin].cost_function () < best_cost)) {
426 best_fake = cutpts[x - array_origin].fake_count;
427 best_cost = cutpts[x - array_origin].cost_function ();
430 best_count = cutpts[x - array_origin].index ();
432 else if (cutpts[x - array_origin].fake_count == best_fake
433 && x == best_right_x + 1
434 && cutpts[x - array_origin].cost_function () == best_cost) {
443 best_end = &cutpts[(best_left_x + best_right_x) / 2 - array_origin];
446 for (x = left_edge - pitch; x < right_edge + pitch; x++) {
447 tprintf (
"x=%d, C=%g, s=%g, sq=%g, prev=%d\n",
448 x, cutpts[x - array_origin].cost_function (),
449 cutpts[x - array_origin].sum (),
450 cutpts[x - array_origin].squares (),
451 cutpts[x - array_origin].previous ()->position ());
454 occupation_count = -1;
456 for (x = best_end->
position () - pitch + pitch_error;
457 x < best_end->
position () - pitch_error
459 if (x < best_end->position () - pitch_error)
462 segpt =
new FPSEGPT (best_end);
463 seg_it.add_before_then_move (segpt);
466 while (best_end !=
nullptr);
467 seg_it.move_to_last ();
468 mean_sum = seg_it.data ()->
sum ();
469 mean_sum = mean_sum * mean_sum / best_count;
470 if (seg_it.data ()->squares () - mean_sum < 0)
471 tprintf (
"Impossible sqsum=%g, mean=%g, total=%d\n",
472 seg_it.data ()->squares (), seg_it.data ()->sum (), best_count);
476 return seg_it.data ()->squares () - mean_sum;
489 int16_t projection_left,
490 int16_t projection_right,
495 float projection_scale,
496 int16_t &occupation_count,
497 FPSEGPT_LIST *seg_list,
506 int16_t array_origin;
508 int16_t projection_offset;
512 int16_t best_left_x = 0;
513 int16_t best_right_x = 0;
522 FPSEGPT_IT seg_it = seg_list;
524 end = (end - start) % pitch;
527 if ((pitch - 3) / 2 < pitch_error)
528 pitch_error = (pitch - 3) / 2;
531 for (left_edge = projection_left; projection->
pile_count (left_edge) == 0
532 && left_edge < projection_right; left_edge++);
533 for (right_edge = projection_right; projection->
pile_count (right_edge) == 0
534 && right_edge > left_edge; right_edge--);
535 array_origin = left_edge - pitch;
537 std::vector<FPCUTPT> cutpts(right_edge - left_edge + pitch * 2 + 1);
539 std::vector<bool> mins(pitch_error * 2 + 1);
540 for (x = array_origin; x < left_edge; x++)
542 cutpts[x - array_origin].setup(&cutpts[0], array_origin, projection,
543 zero_count, pitch, x, 0);
544 prev_zero = left_edge - 1;
545 for (offset = 0; offset <= pitch_error; offset++, x++)
547 cutpts[x - array_origin].setup(&cutpts[0], array_origin, projection,
548 zero_count, pitch, x, offset);
552 for (offset = -pitch_error, minindex = 0; offset < pitch_error;
553 offset++, minindex++)
554 mins[minindex] = projection->
local_min (x + offset);
555 next_zero = x + zero_offset + 1;
556 for (offset = next_zero - 1; offset >= x; offset--) {
557 if (projection->
pile_count (offset) <= zero_count) {
562 while (x < right_edge - pitch_error) {
563 mins[minindex] = projection->
local_min (x + pitch_error);
565 if (minindex > pitch_error * 2)
570 if (projection->
pile_count (x) <= zero_count) {
574 for (offset = 1; offset <= pitch_error; offset++)
575 if (projection->
pile_count (x + offset) <= zero_count
576 || projection->
pile_count (x - offset) <= zero_count)
579 if (offset > pitch_error) {
580 if (x - prev_zero > zero_offset && next_zero - x > zero_offset) {
581 for (offset = 0; offset <= pitch_error; offset++) {
582 test_index = minindex + pitch_error + offset;
583 if (test_index > pitch_error * 2)
584 test_index -= pitch_error * 2 + 1;
585 if (mins[test_index])
587 test_index = minindex + pitch_error - offset;
588 if (test_index > pitch_error * 2)
589 test_index -= pitch_error * 2 + 1;
590 if (mins[test_index])
594 if (offset > pitch_error) {
600 static_cast<int16_t>(projection->
pile_count (x) / projection_scale);
601 if (projection_offset > offset)
602 offset = projection_offset;
606 if ((start == 0 && end == 0)
608 || (x - projection_left - start) % pitch <= end)
609 cutpts[x - array_origin].assign(&cutpts[0], array_origin, x,
610 faking, mid_cut, offset, projection,
611 projection_scale, zero_count, pitch,
614 cutpts[x - array_origin].assign_cheap(&cutpts[0], array_origin, x,
615 faking, mid_cut, offset,
616 projection, projection_scale,
620 if (next_zero < x || next_zero == x + zero_offset)
621 next_zero = x + zero_offset + 1;
622 if (projection->
pile_count (x + zero_offset) <= zero_count)
623 next_zero = x + zero_offset;
626 best_fake = INT16_MAX;
627 best_cost = INT32_MAX;
628 best_count = INT16_MAX;
629 while (x < right_edge + pitch) {
630 offset = x < right_edge ? right_edge - x : 0;
631 cutpts[x - array_origin].assign(&cutpts[0], array_origin, x,
632 false,
false, offset, projection,
633 projection_scale, zero_count, pitch,
635 cutpts[x - array_origin].terminal =
true;
636 if (cutpts[x - array_origin].index () +
637 cutpts[x - array_origin].fake_count <= best_count + best_fake) {
638 if (cutpts[x - array_origin].fake_count < best_fake
639 || (cutpts[x - array_origin].fake_count == best_fake
640 && cutpts[x - array_origin].cost_function () < best_cost)) {
641 best_fake = cutpts[x - array_origin].fake_count;
642 best_cost = cutpts[x - array_origin].cost_function ();
645 best_count = cutpts[x - array_origin].index ();
647 else if (cutpts[x - array_origin].fake_count == best_fake
648 && x == best_right_x + 1
649 && cutpts[x - array_origin].cost_function () == best_cost) {
658 best_end = &cutpts[(best_left_x + best_right_x) / 2 - array_origin];
667 occupation_count = -1;
669 for (x = best_end->
position () - pitch + pitch_error;
670 x < best_end->
position () - pitch_error
672 if (x < best_end->position () - pitch_error)
675 segpt =
new FPSEGPT (best_end);
676 seg_it.add_before_then_move (segpt);
679 while (best_end !=
nullptr);
680 seg_it.move_to_last ();
681 mean_sum = seg_it.data ()->
sum ();
682 mean_sum = mean_sum * mean_sum / best_count;
683 if (seg_it.data ()->squares () - mean_sum < 0)
684 tprintf (
"Impossible sqsum=%g, mean=%g, total=%d\n",
685 seg_it.data ()->squares (), seg_it.data ()->sum (), best_count);
686 return seg_it.data ()->squares () - mean_sum;