wordrec/findseam.cpp

Go to the documentation of this file.
00001 
00020 /*----------------------------------------------------------------------
00021               I n c l u d e s
00022 ----------------------------------------------------------------------*/
00023 #include "findseam.h"
00024 #include "gradechop.h"
00025 #include "olutil.h"
00026 #include "plotedges.h"
00027 #include "outlines.h"
00028 #include "freelist.h"
00029 #include "seam.h"
00030 
00031 /*----------------------------------------------------------------------
00032               T y p e s
00033 ----------------------------------------------------------------------*/
00035 #define SPLIT_CLOSENESS        20
00036 
00037 #define MAX_NUM_SEAMS          150
00038 
00039 #define MAX_OLD_SEAMS          150
00040 
00041 #define NO_FULL_PRIORITY       -1
00042 
00043 #define GOOD_PARTIAL_PRIORITY  good_split
00044 #define BAD_PRIORITY           9999.0
00045 
00046 /*----------------------------------------------------------------------
00047               M a c r o s
00048 ----------------------------------------------------------------------*/
00054 #define add_seam_to_queue(seams,seam,priority)  \
00055 if (seam)\
00056 {\
00057       if (HeapFull(seams))\
00058          junk_worst_seam(seams,seam,priority);\
00059       else\
00060          HeapPush (seams, priority, (char*) seam);\
00061    }
00062 
00066 #define best_seam_priority(seam_queue)   \
00067 (HeapEmpty (seam_queue) ?              \
00068    NO_FULL_PRIORITY       :              \
00069    ((SEAM*) seam_queue_element(seam_queue, 0))->priority)
00070 
00074 #define create_seam_queue(seam_queue)     \
00075 (seam_queue = MakeHeap (MAX_NUM_SEAMS))
00076 
00080 #define create_seam_pile(seam_pile)     \
00081 (seam_pile = array_new (MAX_OLD_SEAMS))
00082 
00086 #define delete_seam_queue(seam_queue)      \
00087 (FreeHeapData (seam_queue, delete_seam), \
00088    seam_queue = NULL)                      \
00089 
00090 
00097 #define pop_next_seam(seams,seam,priority)  \
00098 (HeapPop (seams,&priority,&seam) == OK)   \
00099 
00100 
00104 #define seam_queue_element(seam_queue,index)  \
00105 ((index < SizeOfHeap (seam_queue)) ?        \
00106    HeapDataFor (seam_queue, index)   :        \
00107    NULL)                                      \
00108 
00109 
00110 /*----------------------------------------------------------------------
00111               F u n c t i o n s
00112 ----------------------------------------------------------------------*/
00113 /* ================== */
00117 void junk_worst_seam(SEAM_QUEUE seams, SEAM *new_seam, float new_priority) { 
00118   SEAM *seam;
00119   float priority;
00120 
00121   HeapPopWorst(seams, &priority, &seam);
00122   if (priority > new_priority) {
00123     delete_seam(seam);  /*get rid of it */
00124     HeapPush (seams, new_priority, (char *) new_seam);
00125   }
00126   else {
00127     delete_seam(new_seam);
00128     HeapPush (seams, priority, (char *) seam);
00129   }
00130 }
00131 
00132 
00133 /* ================== */
00164 void choose_best_seam(SEAM_QUEUE seam_queue,
00165                       SEAM_PILE *seam_pile,
00166                       SPLIT *split,
00167                       PRIORITY priority,
00168                       SEAM **seam_result,
00169                       TBLOB *blob) {
00170   SEAM *seam;
00171   TPOINT topleft;
00172   TPOINT botright;
00173   char str[80];
00174   float my_priority;
00175   /* Add seam of split */
00176   my_priority = priority;
00177   if (split != NULL) {
00178     seam = new_seam (my_priority,
00179       (split->point1->pos.x + split->point1->pos.x) / 2,
00180       split, NULL, NULL);
00181     if (chop_debug > 1)
00182       print_seam ("Partial priority    ", seam);
00183     add_seam_to_queue (seam_queue, seam, (float) my_priority);
00184 
00185     if (my_priority > GOOD_PARTIAL_PRIORITY)
00186       return;
00187   }
00188 
00189   blob_bounding_box(blob, &topleft, &botright);
00190   /* Queue loop */
00191   while (pop_next_seam (seam_queue, seam, my_priority)) {
00192     /* Set full priority */
00193     my_priority = seam_priority (seam, topleft.x, botright.x);
00194     if (chop_debug) {
00195       sprintf (str, "Full my_priority %0.0f,  ", my_priority);
00196       print_seam(str, seam);
00197     }
00198 
00199     if ((*seam_result == NULL || /* Replace answer */
00200     (*seam_result)->priority > my_priority) && my_priority < ok_split) {
00201       /* No crossing */
00202       if (constrained_split (seam->split1, blob)) {
00203         delete_seam(*seam_result);
00204         clone_seam(*seam_result, seam);
00205         (*seam_result)->priority = my_priority;
00206       }
00207       else {
00208         delete_seam(seam);
00209         seam = NULL;
00210         my_priority = BAD_PRIORITY;
00211       }
00212     }
00213 
00214     if (my_priority < good_split) {
00215       if (seam)
00216         delete_seam(seam);
00217       return;                    /* Made good answer */
00218     }
00219 
00220     if (seam) {
00221                                  /* Combine with others */
00222       if (array_count (*seam_pile) < MAX_NUM_SEAMS
00223       /*|| tessedit_truncate_chopper==0 */ ) {
00224         combine_seam(seam_queue, *seam_pile, seam);
00225         *seam_pile = array_push (*seam_pile, seam);
00226       }
00227       else
00228         delete_seam(seam);
00229     }
00230 
00231     my_priority = best_seam_priority (seam_queue);
00232     if ((my_priority > ok_split) ||
00233       (my_priority > GOOD_PARTIAL_PRIORITY && split))
00234       return;
00235   }
00236 }
00237 
00238 
00239 /* ================== */
00246 void combine_seam(SEAM_QUEUE seam_queue, SEAM_PILE seam_pile, SEAM *seam) { 
00247   register INT16 x;
00248   register INT16 dist;
00249   INT16 bottom1, top1;
00250   INT16 bottom2, top2;
00251 
00252   SEAM *new_one;
00253   SEAM *this_one;
00254 
00255   bottom1 = seam->split1->point1->pos.y;
00256   if (seam->split1->point2->pos.y >= bottom1)
00257     top1 = seam->split1->point2->pos.y;
00258   else {
00259     top1 = bottom1;
00260     bottom1 = seam->split1->point2->pos.y;
00261   }
00262   if (seam->split2 != NULL) {
00263     bottom2 = seam->split2->point1->pos.y;
00264     if (seam->split2->point2->pos.y >= bottom2)
00265       top2 = seam->split2->point2->pos.y;
00266     else {
00267       top2 = bottom2;
00268       bottom2 = seam->split2->point2->pos.y;
00269     }
00270   }
00271   else {
00272     bottom2 = bottom1;
00273     top2 = top1;
00274   }
00275   array_loop(seam_pile, x) {
00276     this_one = (SEAM *) array_value (seam_pile, x);
00277     dist = seam->location - this_one->location;
00278     if (-SPLIT_CLOSENESS < dist &&
00279       dist < SPLIT_CLOSENESS &&
00280     seam->priority + this_one->priority < ok_split) {
00281       if (
00284         (this_one->split1->point1->pos.y >= top1
00285         && this_one->split1->point2->pos.y >= top1
00286         || this_one->split1->point1->pos.y <= bottom1
00287         && this_one->split1->point2->pos.y <= bottom1)
00288         && (this_one->split1->point1->pos.y >= top2
00289         && this_one->split1->point2->pos.y >= top2
00290         || this_one->split1->point1->pos.y <= bottom2
00291         && this_one->split1->point2->pos.y <= bottom2)
00292         && (this_one->split2 == NULL
00293         || (this_one->split2->point1->pos.y >= top1
00294         && this_one->split2->point2->pos.y >= top1
00295         || this_one->split2->point1->pos.y <= bottom1
00296         && this_one->split2->point2->pos.y <= bottom1)
00297         && (this_one->split2->point1->pos.y >= top2
00298         && this_one->split2->point2->pos.y >= top2
00299         || this_one->split2->point1->pos.y <= bottom2
00300       && this_one->split2->point2->pos.y <= bottom2))) {
00301         new_one = join_two_seams (seam, this_one);
00302         if (chop_debug > 1)
00303           print_seam ("Combo priority       ", new_one);
00304         add_seam_to_queue (seam_queue, new_one, new_one->priority);
00305       }
00306     }
00307   }
00308 }
00309 
00310 
00311 /* ================== */
00318 INT16 constrained_split(SPLIT *split, TBLOB *blob) {
00319   TESSLINE *outline;
00320 
00321   if (is_little_chunk (split->point1, split->point2))
00322     return (FALSE);
00323 
00324   for (outline = blob->outlines; outline; outline = outline->next) {
00325     if (split_bounds_overlap (split, outline) &&
00326     crosses_outline (split->point1, split->point2, outline->loop)) {
00327       return (FALSE);
00328     }
00329   }
00330   return (TRUE);
00331 }
00332 
00333 /* ================== */
00338 void delete_seam_pile(SEAM_PILE seam_pile) {
00339   INT16 x;
00340 
00341   array_loop(seam_pile, x) {
00342     delete_seam ((SEAM *) array_value (seam_pile, x));
00343   }
00344   array_free(seam_pile);
00345 }
00346 
00347 
00348 /* ================== */
00354 SEAM *pick_good_seam(TBLOB *blob) {
00355   SEAM_QUEUE seam_queue;
00356   SEAM_PILE seam_pile;
00357   POINT_GROUP point_heap;
00358   PRIORITY priority;
00359   EDGEPT *edge;
00360   EDGEPT *points[MAX_NUM_POINTS];
00361   SEAM *seam = NULL;
00362   TESSLINE *outline;
00363   INT16 num_points = 0;
00364 
00365 #ifndef GRAPHICS_DISABLED
00366   if (chop_debug)
00367     display_splits = TRUE;
00368 
00369   draw_blob_edges(blob);
00370 #endif
00371 
00372   point_heap = MakeHeap (MAX_NUM_POINTS);
00373   for (outline = blob->outlines; outline; outline = outline->next)
00374     prioritize_points(outline, point_heap);
00375 
00376   while (HeapPop (point_heap, &priority, &edge) == OK) {
00377     if (num_points < MAX_NUM_POINTS)
00378       points[num_points++] = (EDGEPT *) edge;
00379   }
00380   FreeHeap(point_heap);
00381 
00382   /* Initialize queue & pile */
00383   create_seam_pile(seam_pile);
00384   create_seam_queue(seam_queue);
00385 
00386   try_point_pairs(points, num_points, seam_queue, &seam_pile, &seam, blob);
00387 
00388   try_vertical_splits(points, num_points, seam_queue, &seam_pile, &seam, blob);
00389 
00390   if (seam == NULL) {
00391     choose_best_seam(seam_queue, &seam_pile, NULL, BAD_PRIORITY, &seam, blob);
00392   }
00393   else if (seam->priority > good_split) {
00394     choose_best_seam (seam_queue, &seam_pile, NULL, seam->priority,
00395       &seam, blob);
00396   }
00397   delete_seam_queue(seam_queue);
00398   delete_seam_pile(seam_pile);
00399 
00400   if (seam) {
00401     if (seam->priority > ok_split) {
00402       delete_seam(seam);
00403       seam = NULL;
00404     }
00405 #ifndef GRAPHICS_DISABLED
00406     else if (display_splits) {
00407       if (seam->split1)
00408         mark_split (seam->split1);
00409       if (seam->split2)
00410         mark_split (seam->split2);
00411       if (seam->split3)
00412         mark_split (seam->split3);
00413       if (chop_debug > 1) {
00414         update_edge_window();
00415         edge_window_wait();
00416       }
00417     }
00418 #endif
00419   }
00420 
00421   if (chop_debug)
00422     display_splits = FALSE;
00423 
00424   return (seam);
00425 }
00426 
00427 
00428 /* ================== */
00432 PRIORITY seam_priority(SEAM *seam, INT16 xmin, INT16 xmax) {
00433   PRIORITY priority;
00434 
00435   if (seam->split1 == NULL)
00436     priority = 0;
00437 
00438   else if (seam->split2 == NULL) {
00439     priority = (seam->priority +
00440       full_split_priority (seam->split1, xmin, xmax));
00441   }
00442 
00443   else if (seam->split3 == NULL) {
00444     split_outline (seam->split2->point1, seam->split2->point2);
00445     priority = (seam->priority +
00446       full_split_priority (seam->split1, xmin, xmax));
00447     unsplit_outlines (seam->split2->point1, seam->split2->point2);
00448   }
00449 
00450   else {
00451     split_outline (seam->split2->point1, seam->split2->point2);
00452     split_outline (seam->split3->point1, seam->split3->point2);
00453     priority = (seam->priority +
00454       full_split_priority (seam->split1, xmin, xmax));
00455     unsplit_outlines (seam->split3->point1, seam->split3->point2);
00456     unsplit_outlines (seam->split2->point1, seam->split2->point2);
00457   }
00458 
00459   return (priority);
00460 }
00461 
00462 
00463 /* ================== */
00471 void
00472 try_point_pairs (EDGEPT * points[MAX_NUM_POINTS],
00473 INT16 num_points,
00474 SEAM_QUEUE seam_queue,
00475 SEAM_PILE * seam_pile, SEAM ** seam, TBLOB * blob) {
00476   INT16 x;
00477   INT16 y;
00478   SPLIT *split;
00479   PRIORITY priority;
00480 
00481   for (x = 0; x < num_points; x++) {
00482     for (y = x + 1; y < num_points; y++) {
00483 
00484       if (points[y] &&
00485         weighted_edgept_dist (points[x], points[y],
00486         x_y_weight) < split_length &&
00487         points[x] != points[y]->next &&
00488         points[y] != points[x]->next &&
00489         !is_exterior_point (points[x], points[y]) &&
00490       !is_exterior_point (points[y], points[x])) {
00491 
00492         split = new_split (points[x], points[y]);
00493         priority = partial_split_priority (split);
00494 
00495         choose_best_seam(seam_queue, seam_pile, split, priority, seam, blob);
00496 
00497         if (*seam && (*seam)->priority < good_split)
00498           return;
00499       }
00500     }
00501   }
00502 
00503 }
00504 
00505 
00506 /* ================== */
00513 void
00514 try_vertical_splits (EDGEPT * points[MAX_NUM_POINTS],
00515 INT16 num_points,
00516 SEAM_QUEUE seam_queue,
00517 SEAM_PILE * seam_pile, SEAM ** seam, TBLOB * blob) {
00518   EDGEPT *vertical_point = NULL;
00519   SPLIT *split;
00520   INT16 x;
00521   PRIORITY priority;
00522   TESSLINE *outline;
00523 
00524   for (x = 0; x < num_points; x++) {
00525 
00526     if (*seam != NULL && (*seam)->priority < good_split)
00527       return;
00528 
00529     vertical_point = NULL;
00530     for (outline = blob->outlines; outline; outline = outline->next) {
00531       vertical_projection_point (points[x],
00532         outline->loop, &vertical_point);
00533     }
00534 
00535     if (vertical_point &&
00536       points[x] != vertical_point->next &&
00537       vertical_point != points[x]->next &&
00538       weighted_edgept_dist (points[x], vertical_point,
00539     x_y_weight) < split_length) {
00540 
00541       split = new_split (points[x], vertical_point);
00542       priority = partial_split_priority (split);
00543 
00544       choose_best_seam(seam_queue, seam_pile, split, priority, seam, blob);
00545     }
00546   }
00547 }

Generated on Wed Feb 28 19:49:13 2007 for Tesseract by  doxygen 1.5.1