wordrec/findseam.cpp File Reference

#include "findseam.h"
#include "gradechop.h"
#include "olutil.h"
#include "plotedges.h"
#include "outlines.h"
#include "freelist.h"
#include "seam.h"

Go to the source code of this file.

Defines

Functions


Define Documentation

#define add_seam_to_queue ( seams,
seam,
priority   ) 

Value:

if (seam)\
{\
      if (HeapFull(seams))\
         junk_worst_seam(seams,seam,priority);\
      else\
         HeapPush (seams, priority, (char*) seam);\
   }
Add this seam value to the seam queue.

If the heap is already full then nothing is done.

Definition at line 54 of file findseam.cpp.

Referenced by choose_best_seam(), and combine_seam().

#define BAD_PRIORITY   9999.0

Definition at line 44 of file findseam.cpp.

Referenced by choose_best_seam(), and pick_good_seam().

#define best_seam_priority ( seam_queue   ) 

Value:

(HeapEmpty (seam_queue) ?              \
   NO_FULL_PRIORITY       :              \
   ((SEAM*) seam_queue_element(seam_queue, 0))->priority)
Return the best priority value on the queue.

Definition at line 66 of file findseam.cpp.

Referenced by choose_best_seam().

#define create_seam_pile ( seam_pile   )     (seam_pile = array_new (MAX_OLD_SEAMS))

Create a new seam pile with no elements in it.

Definition at line 80 of file findseam.cpp.

Referenced by pick_good_seam().

#define create_seam_queue ( seam_queue   )     (seam_queue = MakeHeap (MAX_NUM_SEAMS))

Create a new seam queue with no elements in it.

Definition at line 74 of file findseam.cpp.

Referenced by pick_good_seam().

#define delete_seam_queue ( seam_queue   ) 

Value:

(FreeHeapData (seam_queue, delete_seam), \
   seam_queue = NULL)                      \
Delete a seam queue along with all the seam structures associated with it.

Definition at line 86 of file findseam.cpp.

Referenced by pick_good_seam().

#define GOOD_PARTIAL_PRIORITY   good_split

Evalute right away

Definition at line 43 of file findseam.cpp.

Referenced by choose_best_seam().

#define MAX_NUM_SEAMS   150

How many total seams to keep

Definition at line 37 of file findseam.cpp.

Referenced by choose_best_seam().

#define MAX_OLD_SEAMS   150

How many old seams to keep

Definition at line 39 of file findseam.cpp.

#define NO_FULL_PRIORITY   -1

Special marker for pri.

Definition at line 41 of file findseam.cpp.

#define pop_next_seam ( seams,
seam,
priority   )     (HeapPop (seams,&priority,&seam) == OK) \

Remove the next seam from the queue.

Put the seam and priority values in the requested variables. If there was nothing to pop then return FALSE, else return TRUE.

Definition at line 97 of file findseam.cpp.

Referenced by choose_best_seam().

#define seam_queue_element ( seam_queue,
index   ) 

Value:

((index < SizeOfHeap (seam_queue)) ?        \
   HeapDataFor (seam_queue, index)   :        \
   NULL)                                      \
Return the element from the seam queue at the requested index.

Definition at line 104 of file findseam.cpp.

#define SPLIT_CLOSENESS   20

Difference in x value

Definition at line 35 of file findseam.cpp.

Referenced by combine_seam().


Function Documentation

void choose_best_seam ( SEAM_QUEUE  seam_queue,
SEAM_PILE seam_pile,
SPLIT split,
PRIORITY  priority,
SEAM **  seam_result,
TBLOB blob 
)

Choose the best seam that can be created by assembling a collection of splits.

Parameters:
seam_queue All possible seams, with assoc. partial priority values
seam_pile cache of seams, to be evaluated eventually
split New split to be evaluated
priority Priority of new split?
seam_result Modified
blob Blob in question
Note:
Global: chop_debug
Returns:
none
A queue of all the possible seams is maintained. Each new split received is placed in that queue with its partial priority value. These values in the seam queue are evaluated and combined until a good enough seam is found. If no further good seams are being found then this function returns to the caller, who will send more splits. If this function is called with a split of NULL, then no further splits can be supplied by the caller.

fmg (guessing): Each blob seems to have a list of outlines, each outline is composed of many seams, each seam references/is made up of many splits - if only temprarily.

seam_queue is created (via macro) during processing, as is seam_pile. When these are evaluated sufficiently, they are no longer needed?

Definition at line 164 of file findseam.cpp.

References add_seam_to_queue, array_count, array_push(), BAD_PRIORITY, best_seam_priority, CHAR_SAMPLE::blob(), blob_bounding_box(), chop_debug, clone_seam, combine_seam(), constrained_split(), delete_seam(), GOOD_PARTIAL_PRIORITY, good_split, MAX_NUM_SEAMS, new_seam(), NULL, ok_split, split_record::point1, pop_next_seam, edgeptstruct::pos, print_seam(), seam_priority(), seam_record::split1, and TPOINT::x.

Referenced by pick_good_seam(), try_point_pairs(), and try_vertical_splits().

00169                                    {
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 }

void combine_seam ( SEAM_QUEUE  seam_queue,
SEAM_PILE  seam_pile,
SEAM seam 
)

Find other seams to combine with this one.

The new seams that result from this union should be added to the seam queue. Return TRUE if any additional seams were added to the queue.

tessedit_fix_sideways_chops ||

Definition at line 246 of file findseam.cpp.

References add_seam_to_queue, array_loop, array_value, chop_debug, join_two_seams(), seam_record::location, NULL, ok_split, split_record::point1, split_record::point2, edgeptstruct::pos, print_seam(), seam_record::priority, seam_record::split1, seam_record::split2, SPLIT_CLOSENESS, and TPOINT::y.

Referenced by choose_best_seam().

00246                                                                           { 
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 }

INT16 constrained_split ( SPLIT split,
TBLOB blob 
)

Constrain this split to obey certain rules.

Definition at line 318 of file findseam.cpp.

References CHAR_SAMPLE::blob(), crosses_outline(), FALSE, is_little_chunk(), olinestruct::loop, olinestruct::next, split_record::point1, split_record::point2, split_bounds_overlap, and TRUE.

Referenced by choose_best_seam().

00318                                                    {
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 }

void delete_seam_pile ( SEAM_PILE  seam_pile  ) 

Delete the seams that are held in the seam pile & destroy the splits that are referenced by these seams.

Definition at line 338 of file findseam.cpp.

References array_free, array_loop, array_value, and delete_seam().

Referenced by pick_good_seam().

00338                                            {
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 }

void junk_worst_seam ( SEAM_QUEUE  seams,
SEAM new_seam,
float  new_priority 
)

Delete the worst seam from the queue because it is full.

Definition at line 117 of file findseam.cpp.

References delete_seam(), HeapPopWorst(), HeapPush(), and new_seam().

00117                                                                            { 
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 }

SEAM* pick_good_seam ( TBLOB blob  ) 

Find and return a good seam that will split this blob into two pieces.

Work from the outlines provided.

Definition at line 354 of file findseam.cpp.

References BAD_PRIORITY, CHAR_SAMPLE::blob(), choose_best_seam(), chop_debug, create_seam_pile, create_seam_queue, delete_seam(), delete_seam_pile(), delete_seam_queue, display_splits, draw_blob_edges(), edge_window_wait, FALSE, FreeHeap, good_split, HeapPop(), MakeHeap(), mark_split(), MAX_NUM_POINTS, olinestruct::next, NULL, OK, ok_split, prioritize_points(), seam_record::priority, seam_record::split1, seam_record::split2, seam_record::split3, TRUE, try_point_pairs(), try_vertical_splits(), and update_edge_window.

Referenced by attempt_blob_chop().

00354                                   {
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 }

PRIORITY seam_priority ( SEAM seam,
INT16  xmin,
INT16  xmax 
)

Assign a full priority value to the seam.

Definition at line 432 of file findseam.cpp.

References full_split_priority(), NULL, split_record::point1, split_record::point2, seam_record::priority, seam_record::split1, seam_record::split2, seam_record::split3, split_outline(), and unsplit_outlines().

Referenced by choose_best_seam().

00432                                                            {
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 }

void try_point_pairs ( EDGEPT points[MAX_NUM_POINTS],
INT16  num_points,
SEAM_QUEUE  seam_queue,
SEAM_PILE seam_pile,
SEAM **  seam,
TBLOB blob 
)

Try all the splits that are produced by pairing critical points together.

See if any of them are suitable for use. Use a seam queue and seam pile that have already been initialized and used.

Definition at line 472 of file findseam.cpp.

References CHAR_SAMPLE::blob(), choose_best_seam(), good_split, is_exterior_point, new_split(), ELIST_LINK::next, partial_split_priority, seam_record::priority, split_length, weighted_edgept_dist, and x_y_weight.

Referenced by pick_good_seam().

00475                                                    {
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 }

void try_vertical_splits ( EDGEPT points[MAX_NUM_POINTS],
INT16  num_points,
SEAM_QUEUE  seam_queue,
SEAM_PILE seam_pile,
SEAM **  seam,
TBLOB blob 
)

Try all the splits that are produced by vertical projection to see if any of them are suitable for use.

Use a seam queue and seam pile that have already been initialized and used.

Definition at line 514 of file findseam.cpp.

References CHAR_SAMPLE::blob(), choose_best_seam(), good_split, olinestruct::loop, new_split(), olinestruct::next, edgeptstruct::next, NULL, partial_split_priority, split_length, vertical_projection_point(), weighted_edgept_dist, and x_y_weight.

Referenced by pick_good_seam().

00517                                                    {
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:28 2007 for Tesseract by  doxygen 1.5.1