00001
00020 #include "mfcpch.h"
00021 #include "blobbox.h"
00022
00023 #define PROJECTION_MARGIN 10 //arbitrary
00024 #define EXTERN
00025
00028 EXTERN double_VAR (textord_error_weight, 3,
00029 "Weighting for error in believability");
00030 EXTERN BOOL_VAR (pitsync_projection_fix, TRUE,
00031 "Fix bug in projection profile");
00034 ELISTIZE (BLOBNBOX) ELIST2IZE (TO_ROW) ELISTIZE (TO_BLOCK)
00038 void BLOBNBOX::merge(
00039 BLOBNBOX *nextblob
00040 ) {
00041 box += nextblob->box;
00042 nextblob->joined = TRUE;
00043 }
00044
00045
00052 void BLOBNBOX::chop(
00053 BLOBNBOX_IT *start_it,
00054 BLOBNBOX_IT *end_it,
00055 FCOORD rotation,
00056 float xheight
00057 ) {
00058 INT16 blobcount;
00059 BLOBNBOX *newblob;
00060 BLOBNBOX *blob;
00061 INT16 blobindex;
00062 INT16 leftx;
00063 float blobwidth;
00064 float rightx;
00065 float ymin, ymax;
00066 float test_ymin, test_ymax;
00067 ICOORD bl, tr;
00068 BLOBNBOX_IT blob_it;
00069
00070
00071 blobcount = (INT16) floor (box.width () / xheight);
00072 if (blobcount > 1 && (blob_ptr != NULL || cblob_ptr != NULL)) {
00073
00074 blobwidth = (float) (box.width () + 1) / blobcount;
00075 for (blobindex = blobcount - 1, rightx = box.right ();
00076 blobindex >= 0; blobindex--, rightx -= blobwidth) {
00077 ymin = (float) MAX_INT32;
00078 ymax = (float) -MAX_INT32;
00079 blob_it = *start_it;
00080 do {
00081 blob = blob_it.data ();
00082 if (blob->blob_ptr != NULL)
00083 find_blob_limits (blob->blob_ptr, rightx - blobwidth, rightx,
00084 rotation, test_ymin, test_ymax);
00085 else
00086 find_cblob_vlimits (blob->cblob_ptr, rightx - blobwidth,
00087 rightx,
00088 test_ymin, test_ymax);
00089 blob_it.forward ();
00090 if (test_ymin < ymin)
00091 ymin = test_ymin;
00092 if (test_ymax > ymax)
00093 ymax = test_ymax;
00094 }
00095 while (blob != end_it->data ());
00096 if (ymin < ymax) {
00097 leftx = (INT16) floor (rightx - blobwidth);
00098 if (leftx < box.left ())
00099 leftx = box.left ();
00100 bl = ICOORD (leftx, (INT16) floor (ymin));
00101 tr = ICOORD ((INT16) ceil (rightx), (INT16) ceil (ymax));
00102 if (blobindex == 0)
00103 box = BOX (bl, tr);
00104 else {
00105 newblob = new BLOBNBOX;
00106
00107 newblob->box = BOX (bl, tr);
00108
00109 end_it->add_after_stay_put (newblob);
00110 }
00111 }
00112 }
00113 }
00114 }
00115
00116
00121 void find_blob_limits(
00122 PBLOB *blob,
00123 float leftx,
00124 float rightx,
00125 FCOORD rotation,
00126 float &ymin,
00127 float &ymax) {
00128 float testy;
00129 FCOORD pos;
00130 FCOORD vec;
00131 POLYPT *polypt;
00132
00133 OUTLINE_IT out_it = blob->out_list ();
00134 POLYPT_IT poly_it;
00135
00136 ymin = (float) MAX_INT32;
00137 ymax = (float) -MAX_INT32;
00138 for (out_it.mark_cycle_pt (); !out_it.cycled_list (); out_it.forward ()) {
00139
00140 poly_it.set_to_list (out_it.data ()->polypts ());
00141 for (poly_it.mark_cycle_pt (); !poly_it.cycled_list ();
00142 poly_it.forward ()) {
00143 polypt = poly_it.data ();
00144 pos = polypt->pos;
00145 pos.rotate (rotation);
00146 vec = polypt->vec;
00147 vec.rotate (rotation);
00148 if (pos.x () < leftx && pos.x () + vec.x () > leftx
00149 || pos.x () > leftx && pos.x () + vec.x () < leftx) {
00150 testy = pos.y () + vec.y () * (leftx - pos.x ()) / vec.x ();
00151
00152 if (testy < ymin)
00153 ymin = testy;
00154 if (testy > ymax)
00155 ymax = testy;
00156 }
00157 if (pos.x () >= leftx && pos.x () <= rightx) {
00158 if (pos.y () > ymax)
00159 ymax = pos.y ();
00160 if (pos.y () < ymin)
00161 ymin = pos.y ();
00162 }
00163 if (pos.x () > rightx && pos.x () + vec.x () < rightx
00164 || pos.x () < rightx && pos.x () + vec.x () > rightx) {
00165 testy = pos.y () + vec.y () * (rightx - pos.x ()) / vec.x ();
00166
00167 if (testy < ymin)
00168 ymin = testy;
00169 if (testy > ymax)
00170 ymax = testy;
00171 }
00172 }
00173 }
00174 }
00175
00176
00181 void find_cblob_limits(
00182 C_BLOB *blob,
00183 float leftx,
00184 float rightx,
00185 FCOORD rotation,
00186 float &ymin,
00187 float &ymax) {
00188 INT16 stepindex;
00189 ICOORD pos;
00190 ICOORD vec;
00191 C_OUTLINE *outline;
00192
00193 C_OUTLINE_IT out_it = blob->out_list ();
00194
00195 ymin = (float) MAX_INT32;
00196 ymax = (float) -MAX_INT32;
00197 for (out_it.mark_cycle_pt (); !out_it.cycled_list (); out_it.forward ()) {
00198 outline = out_it.data ();
00199 pos = outline->start_pos ();
00200 pos.rotate (rotation);
00201 for (stepindex = 0; stepindex < outline->pathlength (); stepindex++) {
00202
00203 if (pos.x () >= leftx && pos.x () <= rightx) {
00204 if (pos.y () > ymax)
00205 ymax = pos.y ();
00206 if (pos.y () < ymin)
00207 ymin = pos.y ();
00208 }
00209 vec = outline->step (stepindex);
00210 vec.rotate (rotation);
00211 pos += vec;
00212 }
00213 }
00214 }
00215
00216
00221 void find_cblob_vlimits(
00222 C_BLOB *blob,
00223 float leftx,
00224 float rightx,
00225 float &ymin,
00226 float &ymax) {
00227 INT16 stepindex;
00228 ICOORD pos;
00229 ICOORD vec;
00230 C_OUTLINE *outline;
00231
00232 C_OUTLINE_IT out_it = blob->out_list ();
00233
00234 ymin = (float) MAX_INT32;
00235 ymax = (float) -MAX_INT32;
00236 for (out_it.mark_cycle_pt (); !out_it.cycled_list (); out_it.forward ()) {
00237 outline = out_it.data ();
00238 pos = outline->start_pos ();
00239 for (stepindex = 0; stepindex < outline->pathlength (); stepindex++) {
00240
00241 if (pos.x () >= leftx && pos.x () <= rightx) {
00242 if (pos.y () > ymax)
00243 ymax = pos.y ();
00244 if (pos.y () < ymin)
00245 ymin = pos.y ();
00246 }
00247 vec = outline->step (stepindex);
00248 pos += vec;
00249 }
00250 }
00251 }
00252
00253
00258 void find_cblob_hlimits(
00259 C_BLOB *blob,
00260 float bottomy,
00261 float topy,
00262 float &xmin,
00263 float &xmax) {
00264 INT16 stepindex;
00265 ICOORD pos;
00266 ICOORD vec;
00267 C_OUTLINE *outline;
00268
00269 C_OUTLINE_IT out_it = blob->out_list ();
00270
00271 xmin = (float) MAX_INT32;
00272 xmax = (float) -MAX_INT32;
00273 for (out_it.mark_cycle_pt (); !out_it.cycled_list (); out_it.forward ()) {
00274 outline = out_it.data ();
00275 pos = outline->start_pos ();
00276 for (stepindex = 0; stepindex < outline->pathlength (); stepindex++) {
00277
00278 if (pos.y () >= bottomy && pos.y () <= topy) {
00279 if (pos.x () > xmax)
00280 xmax = pos.x ();
00281 if (pos.x () < xmin)
00282 xmin = pos.x ();
00283 }
00284 vec = outline->step (stepindex);
00285 pos += vec;
00286 }
00287 }
00288 }
00289
00290
00294 PBLOB *rotate_blob(
00295 PBLOB *blob,
00296 FCOORD rotation
00297 ) {
00298 PBLOB *copy;
00299 POLYPT *polypt;
00300 OUTLINE_IT out_it;
00301 POLYPT_IT poly_it;
00302
00303 copy = new PBLOB;
00304 *copy = *blob;
00305 out_it.set_to_list (copy->out_list ());
00306 for (out_it.mark_cycle_pt (); !out_it.cycled_list (); out_it.forward ()) {
00307
00308 poly_it.set_to_list (out_it.data ()->polypts ());
00309 for (poly_it.mark_cycle_pt (); !poly_it.cycled_list ();
00310 poly_it.forward ()) {
00311 polypt = poly_it.data ();
00312
00313 polypt->pos.rotate (rotation);
00314 polypt->vec.rotate (rotation);
00315 }
00316 out_it.data ()->compute_bb ();
00317 }
00318 return copy;
00319 }
00320
00321
00325 PBLOB *rotate_cblob(
00326 C_BLOB *blob,
00327 float xheight,
00328 FCOORD rotation
00329 ) {
00330 PBLOB *copy;
00331 POLYPT *polypt;
00332 OUTLINE_IT out_it;
00333 POLYPT_IT poly_it;
00334
00335 copy = new PBLOB (blob, xheight);
00336 out_it.set_to_list (copy->out_list ());
00337 for (out_it.mark_cycle_pt (); !out_it.cycled_list (); out_it.forward ()) {
00338
00339 poly_it.set_to_list (out_it.data ()->polypts ());
00340 for (poly_it.mark_cycle_pt (); !poly_it.cycled_list ();
00341 poly_it.forward ()) {
00342 polypt = poly_it.data ();
00343
00344 polypt->pos.rotate (rotation);
00345 polypt->vec.rotate (rotation);
00346 }
00347 out_it.data ()->compute_bb ();
00348 }
00349 return copy;
00350 }
00351
00352
00356 C_BLOB *crotate_cblob(
00357 C_BLOB *blob,
00358 FCOORD rotation
00359 ) {
00360 C_OUTLINE_LIST out_list;
00361
00362 C_OUTLINE_IT in_it = blob->out_list ();
00363
00364 C_OUTLINE_IT out_it = &out_list;
00365
00366 for (in_it.mark_cycle_pt (); !in_it.cycled_list (); in_it.forward ()) {
00367 out_it.add_after_then_move (new C_OUTLINE (in_it.data (), rotation));
00368 }
00369 return new C_BLOB (&out_list);
00370 }
00371
00372
00379 BOX box_next(
00380 BLOBNBOX_IT *it
00381 ) {
00382 BLOBNBOX *blob;
00383 BOX result;
00384
00385 blob = it->data ();
00386 result = blob->bounding_box ();
00387 do {
00388 it->forward ();
00389 blob = it->data ();
00390 if (blob->blob () == NULL && blob->cblob () == NULL)
00391
00392 result += blob->bounding_box ();
00393 }
00394
00395 while (blob->blob () == NULL && blob->cblob () == NULL || blob->joined_to_prev ());
00396 return result;
00397 }
00398
00399
00407 BOX box_next_pre_chopped(
00408 BLOBNBOX_IT *it
00409 ) {
00410 BLOBNBOX *blob;
00411 BOX result;
00412
00413 blob = it->data ();
00414 result = blob->bounding_box ();
00415 do {
00416 it->forward ();
00417 blob = it->data ();
00418 }
00419
00420 while (blob->joined_to_prev ());
00421 return result;
00422 }
00423
00424
00428 TO_ROW::TO_ROW (
00429 BLOBNBOX * blob,
00430 float top,
00431 float bottom,
00432 float row_size
00433 ):y_min (bottom), y_max (top), initial_y_min (bottom) {
00434 float diff;
00435 BLOBNBOX_IT it = &blobs;
00436
00437 it.add_to_end (blob);
00438 diff = top - bottom - row_size;
00439 if (diff > 0) {
00440 y_max -= diff / 2;
00441 y_min += diff / 2;
00442 }
00443
00444 else if ((top - bottom) * 3 < row_size) {
00445 diff = row_size / 3 + bottom - top;
00446 y_max += diff / 2;
00447 y_min -= diff / 2;
00448 }
00449 }
00450
00451
00455 void TO_ROW::add_blob(
00456 BLOBNBOX *blob,
00457 float top,
00458 float bottom,
00459 float row_size
00460 ) {
00461 float allowed;
00462 float available;
00463 BLOBNBOX_IT it = &blobs;
00464
00465 it.add_to_end (blob);
00466 allowed = row_size + y_min - y_max;
00467 if (allowed > 0) {
00468 available = top > y_max ? top - y_max : 0;
00469 if (bottom < y_min)
00470
00471 available += y_min - bottom;
00472 if (available > 0) {
00473 available += available;
00474 if (available < allowed)
00475 available = allowed;
00476 if (bottom < y_min)
00477 y_min -= (y_min - bottom) * allowed / available;
00478 if (top > y_max)
00479 y_max += (top - y_max) * allowed / available;
00480 }
00481 }
00482 }
00483
00484
00488 void TO_ROW::insert_blob(
00489 BLOBNBOX *blob
00490 ) {
00491 BLOBNBOX_IT it = &blobs;
00492
00493 if (it.empty ())
00494 it.add_before_then_move (blob);
00495 else {
00496 it.mark_cycle_pt ();
00497 while (!it.cycled_list ()
00498 && it.data ()->bounding_box ().left () <=
00499 blob->bounding_box ().left ())
00500 it.forward ();
00501 if (it.cycled_list ())
00502 it.add_to_end (blob);
00503 else
00504 it.add_before_stay_put (blob);
00505 }
00506 }
00507
00508
00512 void TO_ROW::compute_vertical_projection() {
00513 BOX row_box;
00514 BLOBNBOX *blob;
00515 BOX blob_box;
00516 BLOBNBOX_IT blob_it = blob_list ();
00517
00518 if (blob_it.empty ())
00519 return;
00520 row_box = blob_it.data ()->bounding_box ();
00521 for (blob_it.mark_cycle_pt (); !blob_it.cycled_list (); blob_it.forward ())
00522 row_box += blob_it.data ()->bounding_box ();
00523
00524 projection.set_range (row_box.left () - PROJECTION_MARGIN,
00525 row_box.right () + PROJECTION_MARGIN);
00526 projection_left = row_box.left () - PROJECTION_MARGIN;
00527 projection_right = row_box.right () + PROJECTION_MARGIN;
00528 for (blob_it.mark_cycle_pt (); !blob_it.cycled_list (); blob_it.forward ()) {
00529 blob = blob_it.data ();
00530 if (blob->blob () != NULL)
00531 vertical_blob_projection (blob->blob (), &projection);
00532 else if (blob->cblob () != NULL)
00533 vertical_cblob_projection (blob->cblob (), &projection);
00534 }
00535 }
00536
00537
00544 void vertical_blob_projection(
00545 PBLOB *blob,
00546 STATS *stats
00547 ) {
00548
00549 OUTLINE_IT out_it = blob->out_list ();
00550
00551 for (out_it.mark_cycle_pt (); !out_it.cycled_list (); out_it.forward ()) {
00552 vertical_outline_projection (out_it.data (), stats);
00553 }
00554 }
00555
00556
00563 void vertical_outline_projection(
00564 OUTLINE *outline,
00565 STATS *stats
00566 ) {
00567 POLYPT *polypt;
00568 INT32 xcoord;
00569 float end_x;
00570 POLYPT_IT poly_it = outline->polypts ();
00571 OUTLINE_IT out_it = outline->child ();
00572 float ymean;
00573 float width;
00574
00575 for (poly_it.mark_cycle_pt (); !poly_it.cycled_list (); poly_it.forward ()) {
00576 polypt = poly_it.data ();
00577 end_x = polypt->pos.x () + polypt->vec.x ();
00578 if (polypt->vec.x () > 0) {
00579 for (xcoord = (INT32) floor (polypt->pos.x ());
00580 xcoord < end_x; xcoord++) {
00581 if (polypt->pos.x () < xcoord) {
00582 width = (float) xcoord;
00583 ymean =
00584 polypt->vec.y () * (xcoord -
00585 polypt->pos.x ()) / polypt->vec.x () +
00586 polypt->pos.y ();
00587 }
00588 else {
00589 width = polypt->pos.x ();
00590 ymean = polypt->pos.y ();
00591 }
00592 if (end_x > xcoord + 1) {
00593 width -= xcoord + 1;
00594 ymean +=
00595 polypt->vec.y () * (xcoord + 1 -
00596 polypt->pos.x ()) / polypt->vec.x () +
00597 polypt->pos.y ();
00598 }
00599 else {
00600 width -= end_x;
00601 ymean += polypt->pos.y () + polypt->vec.y ();
00602 }
00603 ymean = ymean * width / 2;
00604 stats->add (xcoord, (INT32) floor (ymean + 0.5));
00605 }
00606 }
00607 else if (polypt->vec.x () < 0) {
00608 for (xcoord = (INT32) floor (end_x);
00609 xcoord < polypt->pos.x (); xcoord++) {
00610 if (polypt->pos.x () > xcoord + 1) {
00611 width = xcoord + 1.0f;
00612 ymean =
00613 polypt->vec.y () * (xcoord + 1 -
00614 polypt->pos.x ()) / polypt->vec.x () +
00615 polypt->pos.y ();
00616 }
00617 else {
00618 width = polypt->pos.x ();
00619 ymean = polypt->pos.y ();
00620 }
00621 if (end_x < xcoord) {
00622 width -= xcoord;
00623 ymean +=
00624 polypt->vec.y () * (xcoord -
00625 polypt->pos.x ()) / polypt->vec.x () +
00626 polypt->pos.y ();
00627 }
00628 else {
00629 width -= end_x;
00630 ymean += polypt->pos.y () + polypt->vec.y ();
00631 }
00632 ymean = ymean * width / 2;
00633 stats->add (xcoord, (INT32) floor (ymean + 0.5));
00634 }
00635 }
00636 }
00637
00638 for (out_it.mark_cycle_pt (); !out_it.cycled_list (); out_it.forward ()) {
00639 vertical_outline_projection (out_it.data (), stats);
00640 }
00641 }
00642
00643
00650 void vertical_cblob_projection(
00651 C_BLOB *blob,
00652 STATS *stats
00653 ) {
00654
00655 C_OUTLINE_IT out_it = blob->out_list ();
00656
00657 for (out_it.mark_cycle_pt (); !out_it.cycled_list (); out_it.forward ()) {
00658 vertical_coutline_projection (out_it.data (), stats);
00659 }
00660 }
00661
00662
00669 void vertical_coutline_projection(
00670 C_OUTLINE *outline,
00671 STATS *stats
00672 ) {
00673 ICOORD pos;
00674 ICOORD step;
00675 INT32 length;
00676 INT16 stepindex;
00677 C_OUTLINE_IT out_it = outline->child ();
00678
00679 pos = outline->start_pos ();
00680 length = outline->pathlength ();
00681 for (stepindex = 0; stepindex < length; stepindex++) {
00682 step = outline->step (stepindex);
00683 if (step.x () > 0) {
00684 if (pitsync_projection_fix)
00685 stats->add (pos.x (), -pos.y ());
00686 else
00687 stats->add (pos.x (), pos.y ());
00688 }
00689 else if (step.x () < 0) {
00690 if (pitsync_projection_fix)
00691 stats->add (pos.x () - 1, pos.y ());
00692 else
00693 stats->add (pos.x () - 1, -pos.y ());
00694 }
00695 pos += step;
00696 }
00697
00698 for (out_it.mark_cycle_pt (); !out_it.cycled_list (); out_it.forward ()) {
00699 vertical_coutline_projection (out_it.data (), stats);
00700 }
00701 }
00702
00703
00709 TO_BLOCK::TO_BLOCK(
00710 BLOCK *src_block
00711 ) {
00712 block = src_block;
00713 }
00714
00715 static void clear_blobnboxes(BLOBNBOX_LIST* boxes) {
00716 BLOBNBOX_IT it = boxes;
00717
00718
00719 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
00720 BLOBNBOX* box = it.data();
00721 if (box->blob() != NULL)
00722 delete box->blob();
00723 if (box->cblob() != NULL)
00724 delete box->cblob();
00725 }
00726 }
00727
00728 TO_BLOCK::~TO_BLOCK() {
00729
00730 clear_blobnboxes(&blobs);
00731 clear_blobnboxes(&underlines);
00732 clear_blobnboxes(&noise_blobs);
00733 clear_blobnboxes(&small_blobs);
00734 clear_blobnboxes(&large_blobs);
00735 }
00736