00001
00020 #include "mfcpch.h"
00021 #ifdef __UNIX__
00022 #include <assert.h>
00023 #endif
00024 #include <math.h>
00025 #include "memry.h"
00026 #include "makerow.h"
00027 #include "pitsync1.h"
00028 #include "topitch.h"
00029 #include "pithsync.h"
00030 #include "tprintf.h"
00031 #ifdef TEXT_VERBOSE
00032 #include "../cutil/callcpp.h"
00033 #endif
00034
00036 #define PROJECTION_MARGIN 10
00037
00038 #define EXTERN
00039
00043 void FPCUTPT::setup(
00044 FPCUTPT *cutpts,
00045 INT16 array_origin,
00046 STATS *projection,
00047 INT16 zero_count,
00048 INT16 pitch,
00049 INT16 x,
00050 INT16 offset
00051 ) {
00052
00053 INT16 half_pitch = pitch / 2 - 1;
00054 UINT32 lead_flag;
00055 INT32 ind;
00056
00057 if (half_pitch > 31)
00058 half_pitch = 31;
00059 else if (half_pitch < 0)
00060 half_pitch = 0;
00061 lead_flag = 1 << half_pitch;
00062
00063 pred = NULL;
00064 mean_sum = 0;
00065 sq_sum = offset * offset;
00066 cost = sq_sum;
00067 faked = FALSE;
00068 terminal = FALSE;
00069 fake_count = 0;
00070 xpos = x;
00071 region_index = 0;
00072 mid_cuts = 0;
00073 if (x == array_origin) {
00074 back_balance = 0;
00075 fwd_balance = 0;
00076 for (ind = 0; ind <= half_pitch; ind++) {
00077 fwd_balance >>= 1;
00078 if (projection->pile_count (ind) > zero_count)
00079 fwd_balance |= lead_flag;
00080 }
00081 }
00082 else {
00083 back_balance = cutpts[x - 1 - array_origin].back_balance << 1;
00084 back_balance &= lead_flag + lead_flag - 1;
00085 if (projection->pile_count (x) > zero_count)
00086 back_balance |= 1;
00087 fwd_balance = cutpts[x - 1 - array_origin].fwd_balance >> 1;
00088 if (projection->pile_count (x + half_pitch) > zero_count)
00089 fwd_balance |= lead_flag;
00090 }
00091 }
00092
00093
00097 void FPCUTPT::assign(
00098 FPCUTPT *cutpts,
00099 INT16 array_origin,
00100 INT16 x,
00101 BOOL8 faking,
00102 BOOL8 mid_cut,
00103 INT16 offset,
00104 STATS *projection,
00105 float projection_scale,
00106 INT16 zero_count,
00107 INT16 pitch,
00108 INT16 pitch_error
00109 ) {
00110 int index;
00111 int balance_index;
00112 INT16 balance_count;
00113 INT16 r_index;
00114 FPCUTPT *segpt;
00115 INT32 dist;
00116 double sq_dist;
00117 double mean;
00118 double total;
00119 double factor;
00120
00121 INT16 half_pitch = pitch / 2 - 1;
00122 UINT32 lead_flag;
00123
00124 if (half_pitch > 31)
00125 half_pitch = 31;
00126 else if (half_pitch < 0)
00127 half_pitch = 0;
00128 lead_flag = 1 << half_pitch;
00129
00130 back_balance = cutpts[x - 1 - array_origin].back_balance << 1;
00131 back_balance &= lead_flag + lead_flag - 1;
00132 if (projection->pile_count (x) > zero_count)
00133 back_balance |= 1;
00134 fwd_balance = cutpts[x - 1 - array_origin].fwd_balance >> 1;
00135 if (projection->pile_count (x + half_pitch) > zero_count)
00136 fwd_balance |= lead_flag;
00137
00138 xpos = x;
00139 cost = MAX_FLOAT32;
00140 pred = NULL;
00141 faked = faking;
00142 terminal = FALSE;
00143 region_index = 0;
00144 fake_count = MAX_INT16;
00145 for (index = x - pitch - pitch_error; index <= x - pitch + pitch_error;
00146 index++) {
00147 if (index >= array_origin) {
00148 segpt = &cutpts[index - array_origin];
00149 dist = x - segpt->xpos;
00150 if (!segpt->terminal && segpt->fake_count < MAX_INT16) {
00151 balance_count = 0;
00152 if (textord_balance_factor > 0) {
00153 if (textord_fast_pitch_test) {
00154 lead_flag = back_balance ^ segpt->fwd_balance;
00155 balance_count = 0;
00156 while (lead_flag != 0) {
00157 balance_count++;
00158 lead_flag &= lead_flag - 1;
00159 }
00160 }
00161 else {
00162 for (balance_index = 0;
00163 index + balance_index < x - balance_index;
00164 balance_index++)
00165 balance_count +=
00166 (projection->pile_count (index + balance_index) <=
00167 zero_count) ^ (projection->pile_count (x -
00168 balance_index)
00169 <= zero_count);
00170 }
00171 balance_count =
00172 (INT16) (balance_count * textord_balance_factor /
00173 projection_scale);
00174 }
00175 r_index = segpt->region_index + 1;
00176 total = segpt->mean_sum + dist;
00177 balance_count += offset;
00178 sq_dist =
00179 dist * dist + segpt->sq_sum + balance_count * balance_count;
00180 mean = total / r_index;
00181 factor = mean - pitch;
00182 factor *= factor;
00183 factor += sq_dist / (r_index) - mean * mean;
00184 if (factor < cost && segpt->fake_count + faked <= fake_count) {
00185 cost = factor;
00186 pred = segpt;
00187 mean_sum = total;
00188 sq_sum = sq_dist;
00189 fake_count = segpt->fake_count + faked;
00190 mid_cuts = segpt->mid_cuts + mid_cut;
00191 region_index = r_index;
00192 }
00193 }
00194 }
00195 }
00196 }
00197
00198
00202 void FPCUTPT::assign_cheap(
00203 FPCUTPT *cutpts,
00204 INT16 array_origin,
00205 INT16 x,
00206 BOOL8 faking,
00207 BOOL8 mid_cut,
00208 INT16 offset,
00209 STATS *projection,
00210 float projection_scale,
00211 INT16 zero_count,
00212 INT16 pitch,
00213 INT16 pitch_error
00214 ) {
00215 int index;
00216 INT16 balance_count;
00217 INT16 r_index;
00218 FPCUTPT *segpt;
00219 INT32 dist;
00220 double sq_dist;
00221 double mean;
00222 double total;
00223 double factor;
00224
00225 INT16 half_pitch = pitch / 2 - 1;
00226 UINT32 lead_flag;
00227
00228 if (half_pitch > 31)
00229 half_pitch = 31;
00230 else if (half_pitch < 0)
00231 half_pitch = 0;
00232 lead_flag = 1 << half_pitch;
00233
00234 back_balance = cutpts[x - 1 - array_origin].back_balance << 1;
00235 back_balance &= lead_flag + lead_flag - 1;
00236 if (projection->pile_count (x) > zero_count)
00237 back_balance |= 1;
00238 fwd_balance = cutpts[x - 1 - array_origin].fwd_balance >> 1;
00239 if (projection->pile_count (x + half_pitch) > zero_count)
00240 fwd_balance |= lead_flag;
00241
00242 xpos = x;
00243 cost = MAX_FLOAT32;
00244 pred = NULL;
00245 faked = faking;
00246 terminal = FALSE;
00247 region_index = 0;
00248 fake_count = MAX_INT16;
00249 index = x - pitch;
00250 if (index >= array_origin) {
00251 segpt = &cutpts[index - array_origin];
00252 dist = x - segpt->xpos;
00253 if (!segpt->terminal && segpt->fake_count < MAX_INT16) {
00254 balance_count = 0;
00255 if (textord_balance_factor > 0) {
00256 lead_flag = back_balance ^ segpt->fwd_balance;
00257 balance_count = 0;
00258 while (lead_flag != 0) {
00259 balance_count++;
00260 lead_flag &= lead_flag - 1;
00261 }
00262 balance_count = (INT16) (balance_count * textord_balance_factor
00263 / projection_scale);
00264 }
00265 r_index = segpt->region_index + 1;
00266 total = segpt->mean_sum + dist;
00267 balance_count += offset;
00268 sq_dist =
00269 dist * dist + segpt->sq_sum + balance_count * balance_count;
00270 mean = total / r_index;
00271 factor = mean - pitch;
00272 factor *= factor;
00273 factor += sq_dist / (r_index) - mean * mean;
00274 cost = factor;
00275 pred = segpt;
00276 mean_sum = total;
00277 sq_sum = sq_dist;
00278 fake_count = segpt->fake_count + faked;
00279 mid_cuts = segpt->mid_cuts + mid_cut;
00280 region_index = r_index;
00281 }
00282 }
00283 }
00284
00285
00307 double check_pitch_sync2(
00308 BLOBNBOX_IT *blob_it,
00309 INT16 blob_count,
00310 INT16 pitch,
00311 INT16 pitch_error,
00312 STATS *projection,
00313 INT16 projection_left,
00314 INT16 projection_right,
00315 float projection_scale,
00316 INT16 &occupation_count,
00317 FPSEGPT_LIST *seg_list,
00318 INT16 start,
00319 INT16 end
00320 ) {
00321 BOOL8 faking;
00322 BOOL8 mid_cut;
00323 INT16 x;
00324 INT16 blob_index;
00325 INT16 left_edge;
00326 INT16 right_edge;
00327 INT16 array_origin;
00328 INT16 offset;
00329 INT16 zero_count;
00330 INT16 best_left_x = 0;
00331 INT16 best_right_x = 0;
00332 BOX this_box;
00333 BOX next_box;
00334 FPSEGPT *segpt;
00335 FPCUTPT *cutpts;
00336 double best_cost;
00337 double mean_sum;
00338 FPCUTPT *best_end;
00339 INT16 best_fake;
00340 INT16 best_count;
00341 BLOBNBOX_IT this_it;
00342 FPSEGPT_IT seg_it = seg_list;
00343
00344 #ifdef TEXT_VERBOSE
00345
00346 cprintf("t");
00347 #endif
00348
00349
00350
00351
00352 zero_count = 0;
00353 if (pitch < 3)
00354 pitch = 3;
00355 if ((pitch - 3) / 2 < pitch_error)
00356 pitch_error = (pitch - 3) / 2;
00357 this_it = *blob_it;
00358 this_box = box_next (&this_it);
00359
00360
00361
00362
00363
00364
00365
00366
00367 for (left_edge = projection_left; projection->pile_count (left_edge) == 0
00368 && left_edge < projection_right; left_edge++);
00369 for (right_edge = projection_right; projection->pile_count (right_edge) == 0
00370 && right_edge > left_edge; right_edge--);
00371 ASSERT_HOST (right_edge >= left_edge);
00372 if (pitsync_linear_version >= 4)
00373 return check_pitch_sync3 (projection_left, projection_right, zero_count,
00374 pitch, pitch_error, projection,
00375 projection_scale, occupation_count, seg_list,
00376 start, end);
00377 array_origin = left_edge - pitch;
00378 cutpts = (FPCUTPT *) alloc_mem ((right_edge - left_edge + pitch * 2 + 1)
00379 * sizeof (FPCUTPT));
00380 for (x = array_origin; x < left_edge; x++)
00381
00382 cutpts[x - array_origin].setup (cutpts, array_origin, projection,
00383 zero_count, pitch, x, 0);
00384 for (offset = 0; offset <= pitch_error; offset++, x++)
00385
00386 cutpts[x - array_origin].setup (cutpts, array_origin, projection,
00387 zero_count, pitch, x, offset);
00388
00389 this_it = *blob_it;
00390 best_cost = MAX_FLOAT32;
00391 best_end = NULL;
00392 this_box = box_next (&this_it);
00393 next_box = box_next (&this_it);
00394 blob_index = 1;
00395 while (x < right_edge - pitch_error) {
00396 if (x > this_box.right () + pitch_error && blob_index < blob_count) {
00397 this_box = next_box;
00398 next_box = box_next (&this_it);
00399 blob_index++;
00400 }
00401 faking = FALSE;
00402 mid_cut = FALSE;
00403 if (x <= this_box.left ())
00404 offset = 0;
00405 else if (x <= this_box.left () + pitch_error)
00406 offset = x - this_box.left ();
00407 else if (x >= this_box.right ())
00408 offset = 0;
00409 else if (x >= next_box.left () && blob_index < blob_count) {
00410 offset = x - next_box.left ();
00411 if (this_box.right () - x < offset)
00412 offset = this_box.right () - x;
00413 }
00414 else if (x >= this_box.right () - pitch_error)
00415 offset = this_box.right () - x;
00416 else if (x - this_box.left () > pitch * pitsync_joined_edge
00417 && this_box.right () - x > pitch * pitsync_joined_edge) {
00418 mid_cut = TRUE;
00419 offset = 0;
00420 }
00421 else {
00422 faking = TRUE;
00423 offset = projection->pile_count (x);
00424 }
00425 cutpts[x - array_origin].assign (cutpts, array_origin, x,
00426 faking, mid_cut, offset, projection,
00427 projection_scale, zero_count, pitch,
00428 pitch_error);
00429 x++;
00430 }
00431
00432 best_fake = MAX_INT16;
00433 best_cost = MAX_INT32;
00434 best_count = MAX_INT16;
00435 while (x < right_edge + pitch) {
00436 offset = x < right_edge ? right_edge - x : 0;
00437 cutpts[x - array_origin].assign (cutpts, array_origin, x,
00438 FALSE, FALSE, offset, projection,
00439 projection_scale, zero_count, pitch,
00440 pitch_error);
00441 cutpts[x - array_origin].terminal = TRUE;
00442 if (cutpts[x - array_origin].index () +
00443 cutpts[x - array_origin].fake_count <= best_count + best_fake) {
00444 if (cutpts[x - array_origin].fake_count < best_fake
00445 || cutpts[x - array_origin].fake_count == best_fake
00446 && cutpts[x - array_origin].cost_function () < best_cost) {
00447 best_fake = cutpts[x - array_origin].fake_count;
00448 best_cost = cutpts[x - array_origin].cost_function ();
00449 best_left_x = x;
00450 best_right_x = x;
00451 best_count = cutpts[x - array_origin].index ();
00452 }
00453 else if (cutpts[x - array_origin].fake_count == best_fake
00454 && x == best_right_x + 1
00455 && cutpts[x - array_origin].cost_function () == best_cost) {
00456
00457 best_right_x = x;
00458 }
00459 }
00460 x++;
00461 }
00462 ASSERT_HOST (best_fake < MAX_INT16);
00463
00464 best_end = &cutpts[(best_left_x + best_right_x) / 2 - array_origin];
00465 if (this_box.right () == textord_test_x
00466 && this_box.top () == textord_test_y) {
00467 for (x = left_edge - pitch; x < right_edge + pitch; x++) {
00468 tprintf ("x=%d, C=%g, s=%g, sq=%g, prev=%d\n",
00469 x, cutpts[x - array_origin].cost_function (),
00470 cutpts[x - array_origin].sum (),
00471 cutpts[x - array_origin].squares (),
00472 cutpts[x - array_origin].previous ()->position ());
00473 }
00474 }
00475 occupation_count = -1;
00476 do {
00477 for (x = best_end->position () - pitch + pitch_error;
00478 x < best_end->position () - pitch_error
00479 && projection->pile_count (x) == 0; x++);
00480 if (x < best_end->position () - pitch_error)
00481 occupation_count++;
00482
00483 segpt = new FPSEGPT (best_end);
00484 seg_it.add_before_then_move (segpt);
00485 best_end = best_end->previous ();
00486 }
00487 while (best_end != NULL);
00488 seg_it.move_to_last ();
00489 mean_sum = seg_it.data ()->sum ();
00490 mean_sum = mean_sum * mean_sum / best_count;
00491 if (seg_it.data ()->squares () - mean_sum < 0)
00492 tprintf ("Impossible sqsum=%g, mean=%g, total=%d\n",
00493 seg_it.data ()->squares (), seg_it.data ()->sum (), best_count);
00494 free_mem(cutpts);
00495
00496
00497
00498 return seg_it.data ()->squares () - mean_sum;
00499 }
00500
00501
00510 double check_pitch_sync3(
00511 INT16 projection_left,
00512 INT16 projection_right,
00513 INT16 zero_count,
00514 INT16 pitch,
00515 INT16 pitch_error,
00516 STATS *projection,
00517 float projection_scale,
00518 INT16 &occupation_count,
00519 FPSEGPT_LIST *seg_list,
00520 INT16 start,
00521 INT16 end
00522 ) {
00523 BOOL8 faking;
00524 BOOL8 mid_cut;
00525 INT16 left_edge;
00526 INT16 right_edge;
00527 INT16 x;
00528 INT16 array_origin;
00529 INT16 offset;
00530 INT16 projection_offset;
00531 INT16 prev_zero;
00532 INT16 next_zero;
00533 INT16 zero_offset;
00534 INT16 best_left_x = 0;
00535 INT16 best_right_x = 0;
00536 FPSEGPT *segpt;
00537 FPCUTPT *cutpts;
00538 BOOL8 *mins;
00539 int minindex;
00540 int test_index;
00541 double best_cost;
00542 double mean_sum;
00543 FPCUTPT *best_end;
00544 INT16 best_fake;
00545 INT16 best_count;
00546 FPSEGPT_IT seg_it = seg_list;
00547
00548 end = (end - start) % pitch;
00549 if (pitch < 3)
00550 pitch = 3;
00551 if ((pitch - 3) / 2 < pitch_error)
00552 pitch_error = (pitch - 3) / 2;
00553
00554 zero_offset = (INT16) (pitch * pitsync_joined_edge);
00555 for (left_edge = projection_left; projection->pile_count (left_edge) == 0
00556 && left_edge < projection_right; left_edge++);
00557 for (right_edge = projection_right; projection->pile_count (right_edge) == 0
00558 && right_edge > left_edge; right_edge--);
00559 array_origin = left_edge - pitch;
00560 cutpts = (FPCUTPT *) alloc_mem ((right_edge - left_edge + pitch * 2 + 1)
00561 * sizeof (FPCUTPT));
00562 mins = (BOOL8 *) alloc_mem ((pitch_error * 2 + 1) * sizeof (BOOL8));
00563 for (x = array_origin; x < left_edge; x++)
00564
00565 cutpts[x - array_origin].setup (cutpts, array_origin, projection,
00566 zero_count, pitch, x, 0);
00567 prev_zero = left_edge - 1;
00568 for (offset = 0; offset <= pitch_error; offset++, x++)
00569
00570 cutpts[x - array_origin].setup (cutpts, array_origin, projection,
00571 zero_count, pitch, x, offset);
00572
00573 best_cost = MAX_FLOAT32;
00574 best_end = NULL;
00575 for (offset = -pitch_error, minindex = 0; offset < pitch_error;
00576 offset++, minindex++)
00577 mins[minindex] = projection->local_min (x + offset);
00578 next_zero = x + zero_offset + 1;
00579 for (offset = next_zero - 1; offset >= x; offset--) {
00580 if (projection->pile_count (offset) <= zero_count) {
00581 next_zero = offset;
00582 break;
00583 }
00584 }
00585 while (x < right_edge - pitch_error) {
00586 mins[minindex] = projection->local_min (x + pitch_error);
00587 minindex++;
00588 if (minindex > pitch_error * 2)
00589 minindex = 0;
00590 faking = FALSE;
00591 mid_cut = FALSE;
00592 offset = 0;
00593 if (projection->pile_count (x) <= zero_count) {
00594 prev_zero = x;
00595 }
00596 else {
00597 for (offset = 1; offset <= pitch_error; offset++)
00598 if (projection->pile_count (x + offset) <= zero_count
00599 || projection->pile_count (x - offset) <= zero_count)
00600 break;
00601 }
00602 if (offset > pitch_error) {
00603 if (x - prev_zero > zero_offset && next_zero - x > zero_offset) {
00604 for (offset = 0; offset <= pitch_error; offset++) {
00605 test_index = minindex + pitch_error + offset;
00606 if (test_index > pitch_error * 2)
00607 test_index -= pitch_error * 2 + 1;
00608 if (mins[test_index])
00609 break;
00610 test_index = minindex + pitch_error - offset;
00611 if (test_index > pitch_error * 2)
00612 test_index -= pitch_error * 2 + 1;
00613 if (mins[test_index])
00614 break;
00615 }
00616 }
00617 if (offset > pitch_error) {
00618 offset = projection->pile_count (x);
00619 faking = TRUE;
00620 }
00621 else {
00622 projection_offset =
00623 (INT16) (projection->pile_count (x) / projection_scale);
00624 if (projection_offset > offset)
00625 offset = projection_offset;
00626 mid_cut = TRUE;
00627 }
00628 }
00629 if (start == 0 && end == 0
00630 || !textord_fast_pitch_test
00631 || (x - projection_left - start) % pitch <= end)
00632 cutpts[x - array_origin].assign (cutpts, array_origin, x,
00633 faking, mid_cut, offset, projection,
00634 projection_scale, zero_count, pitch,
00635 pitch_error);
00636 else
00637 cutpts[x - array_origin].assign_cheap (cutpts, array_origin, x,
00638 faking, mid_cut, offset,
00639 projection, projection_scale,
00640 zero_count, pitch,
00641 pitch_error);
00642 x++;
00643 if (next_zero < x || next_zero == x + zero_offset)
00644 next_zero = x + zero_offset + 1;
00645 if (projection->pile_count (x + zero_offset) <= zero_count)
00646 next_zero = x + zero_offset;
00647 }
00648
00649 best_fake = MAX_INT16;
00650 best_cost = MAX_INT32;
00651 best_count = MAX_INT16;
00652 while (x < right_edge + pitch) {
00653 offset = x < right_edge ? right_edge - x : 0;
00654 cutpts[x - array_origin].assign (cutpts, array_origin, x,
00655 FALSE, FALSE, offset, projection,
00656 projection_scale, zero_count, pitch,
00657 pitch_error);
00658 cutpts[x - array_origin].terminal = TRUE;
00659 if (cutpts[x - array_origin].index () +
00660 cutpts[x - array_origin].fake_count <= best_count + best_fake) {
00661 if (cutpts[x - array_origin].fake_count < best_fake
00662 || cutpts[x - array_origin].fake_count == best_fake
00663 && cutpts[x - array_origin].cost_function () < best_cost) {
00664 best_fake = cutpts[x - array_origin].fake_count;
00665 best_cost = cutpts[x - array_origin].cost_function ();
00666 best_left_x = x;
00667 best_right_x = x;
00668 best_count = cutpts[x - array_origin].index ();
00669 }
00670 else if (cutpts[x - array_origin].fake_count == best_fake
00671 && x == best_right_x + 1
00672 && cutpts[x - array_origin].cost_function () == best_cost) {
00673
00674 best_right_x = x;
00675 }
00676 }
00677 x++;
00678 }
00679 ASSERT_HOST (best_fake < MAX_INT16);
00680
00681 best_end = &cutpts[(best_left_x + best_right_x) / 2 - array_origin];
00682
00683
00684
00685
00686
00687
00688
00689
00690 occupation_count = -1;
00691 do {
00692 for (x = best_end->position () - pitch + pitch_error;
00693 x < best_end->position () - pitch_error
00694 && projection->pile_count (x) == 0; x++);
00695 if (x < best_end->position () - pitch_error)
00696 occupation_count++;
00697
00698 segpt = new FPSEGPT (best_end);
00699 seg_it.add_before_then_move (segpt);
00700 best_end = best_end->previous ();
00701 }
00702 while (best_end != NULL);
00703 seg_it.move_to_last ();
00704 mean_sum = seg_it.data ()->sum ();
00705 mean_sum = mean_sum * mean_sum / best_count;
00706 if (seg_it.data ()->squares () - mean_sum < 0)
00707 tprintf ("Impossible sqsum=%g, mean=%g, total=%d\n",
00708 seg_it.data ()->squares (), seg_it.data ()->sum (), best_count);
00709 free_mem(mins);
00710 free_mem(cutpts);
00711 return seg_it.data ()->squares () - mean_sum;
00712 }