#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.
#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);\ }
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 |
#define best_seam_priority | ( | seam_queue | ) |
Value:
(HeapEmpty (seam_queue) ? \ NO_FULL_PRIORITY : \ ((SEAM*) seam_queue_element(seam_queue, 0))->priority)
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) \
Definition at line 86 of file findseam.cpp.
Referenced by pick_good_seam().
#define GOOD_PARTIAL_PRIORITY good_split |
#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) \
Definition at line 104 of file findseam.cpp.
#define SPLIT_CLOSENESS 20 |
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.
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 |
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 }
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 }
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 }
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 }