Tesseract 3.02

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
findseam.cpp
Go to the documentation of this file.
1 /* -*-C-*-
2 ********************************************************************************
3 *
4 * File: findseam.c (Formerly findseam.c)
5 * Description:
6 * Author: Mark Seaman, OCR Technology
7 * Created: Fri Oct 16 14:37:00 1987
8 * Modified: Tue Jul 30 15:44:59 1991 (Mark Seaman) marks@hpgrlt
9 * Language: C
10 * Package: N/A
11 * Status: Reusable Software Component
12 *
13 * (c) Copyright 1987, Hewlett-Packard Company.
14 ** Licensed under the Apache License, Version 2.0 (the "License");
15 ** you may not use this file except in compliance with the License.
16 ** You may obtain a copy of the License at
17 ** http://www.apache.org/licenses/LICENSE-2.0
18 ** Unless required by applicable law or agreed to in writing, software
19 ** distributed under the License is distributed on an "AS IS" BASIS,
20 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
21 ** See the License for the specific language governing permissions and
22 ** limitations under the License.
23 *
24 *********************************************************************************/
25 /*----------------------------------------------------------------------
26 I n c l u d e s
27 ----------------------------------------------------------------------*/
28 #include "findseam.h"
29 #include "gradechop.h"
30 #include "olutil.h"
31 #include "plotedges.h"
32 #include "outlines.h"
33 #include "freelist.h"
34 #include "seam.h"
35 #include "wordrec.h"
36
37 // Include automatically generated configuration file if running autoconf.
38 #ifdef HAVE_CONFIG_H
39 #include "config_auto.h"
40 #endif
41
42 /*----------------------------------------------------------------------
43 T y p e s
44 ----------------------------------------------------------------------*/
45 #define SPLIT_CLOSENESS 20/* Difference in x value */
46 /* How many to keep */
47 #define MAX_NUM_SEAMS 150
48 /* How many to keep */
49 #define MAX_OLD_SEAMS 150
50 #define NO_FULL_PRIORITY -1/* Special marker for pri. */
51 /* Evalute right away */
52 #define BAD_PRIORITY 9999.0
53
54 /*----------------------------------------------------------------------
55 M a c r o s
56 ----------------------------------------------------------------------*/
57 /**********************************************************************
58 * add_seam_to_queue
59 *
60 * Add this seam value to the seam queue. If the heap is already full
61 * then nothing is done.
62 **********************************************************************/
63
64 #define add_seam_to_queue(seams,seam,priority) \
65 if (seam)\
66 {\
67 if (HeapFull(seams))\
68 junk_worst_seam(seams,seam,priority);\
69 else\
70 HeapPush (seams, priority, (char*) seam);\
71 }
72
73 /**********************************************************************
74 * best_seam_priority
75 *
76 * Return the best priority value on the queue.
77 **********************************************************************/
78
79 #define best_seam_priority(seam_queue) \
80 (HeapEmpty (seam_queue) ? \
81 NO_FULL_PRIORITY : \
82 ((SEAM*) seam_queue_element(seam_queue, 0))->priority)
83
84 /**********************************************************************
85 * create_seam_queue
86 *
87 * Create a new seam queue with no elements in it.
88 **********************************************************************/
89
90 #define create_seam_queue(seam_queue) \
91 (seam_queue = MakeHeap (MAX_NUM_SEAMS))
92
93 /**********************************************************************
94 * create_seam_pile
95 *
96 * Create a new seam pile with no elements in it.
97 **********************************************************************/
98
99 #define create_seam_pile(seam_pile) \
100 (seam_pile = array_new (MAX_OLD_SEAMS))
101
102 /**********************************************************************
103 * delete_seam_queue
104 *
105 * Delete a seam queue along with all the seam structures associated
106 * with it.
107 **********************************************************************/
108
109 #define delete_seam_queue(seam_queue) \
110 (FreeHeapData (seam_queue, delete_seam), \
111 seam_queue = NULL) \
112
113
114 /**********************************************************************
115 * pop_next_seam
116 *
117 * Remove the next seam from the queue. Put the seam and priority
118 * values in the requested variables. If there was nothing to pop
119 * then return FALSE, else return TRUE.
120 **********************************************************************/
121
122 #define pop_next_seam(seams,seam,priority) \
123 (HeapPop (seams,&priority,&seam) == TESS_HEAP_OK) \
124
125
126 /**********************************************************************
127 * seam_queue_element
128 *
129 * Return the element from the seam queue at the requested index.
130 **********************************************************************/
131
132 #define seam_queue_element(seam_queue,index) \
133 ((index < SizeOfHeap (seam_queue)) ? \
134 HeapDataFor (seam_queue, index) : \
135 NULL) \
136
137
138 /*----------------------------------------------------------------------
139 F u n c t i o n s
140 ----------------------------------------------------------------------*/
141 namespace tesseract {
142
143 /**********************************************************************
144 * junk_worst_seam
145 *
146 * Delete the worst seam from the queue because it is full.
147 **********************************************************************/
148 void Wordrec::junk_worst_seam(SEAM_QUEUE seams, SEAM *new_seam,
149 float new_priority) {
150 SEAM *seam;
151 float priority;
152
153 HeapPopWorst(seams, &priority, &seam);
154 if (priority > new_priority) {
155 delete_seam(seam); /*get rid of it */
156 HeapPush (seams, new_priority, (char *) new_seam);
157 }
158 else {
159 delete_seam(new_seam);
160 HeapPush (seams, priority, (char *) seam);
161 }
162 }
163
164
165 /**********************************************************************
166 * choose_best_seam
167 *
168 * Choose the best seam that can be created by assembling this a
169 * collection of splits. A queue of all the possible seams is
170 * maintained. Each new split received is placed in that queue with
171 * its partial priority value. These values in the seam queue are
172 * evaluated and combined until a good enough seam is found. If no
173 * further good seams are being found then this function returns to the
174 * caller, who will send more splits. If this function is called with
175 * a split of NULL, then no further splits can be supplied by the
176 * caller.
177 **********************************************************************/
178 void Wordrec::choose_best_seam(SEAM_QUEUE seam_queue,
179 SEAM_PILE *seam_pile,
180 SPLIT *split,
181 PRIORITY priority,
182 SEAM **seam_result,
183 TBLOB *blob) {
184 SEAM *seam;
185 char str[80];
186 float my_priority;
187 /* Add seam of split */
188 my_priority = priority;
189 if (split != NULL) {
190 TPOINT split_point = split->point1->pos;
191 split_point += split->point2->pos;
192 split_point /= 2;
193 seam = new_seam(my_priority, split_point, split, NULL, NULL);
194 if (chop_debug > 1)
195 print_seam ("Partial priority ", seam);
196 add_seam_to_queue (seam_queue, seam, (float) my_priority);
197
198 if (my_priority > chop_good_split)
199 return;
200 }
201
202 TBOX bbox = blob->bounding_box();
203 /* Queue loop */
204 while (pop_next_seam (seam_queue, seam, my_priority)) {
205 /* Set full priority */
206 my_priority = seam_priority (seam, bbox.left(), bbox.right());
207 if (chop_debug) {
208 sprintf (str, "Full my_priority %0.0f, ", my_priority);
209 print_seam(str, seam);
210 }
211
212 if ((*seam_result == NULL || /* Replace answer */
213 (*seam_result)->priority > my_priority) && my_priority < chop_ok_split) {
214 /* No crossing */
215 if (constrained_split (seam->split1, blob)) {
216 delete_seam(*seam_result);
217 clone_seam(*seam_result, seam);
218 (*seam_result)->priority = my_priority;
219 }
220 else {
221 delete_seam(seam);
222 seam = NULL;
223 my_priority = BAD_PRIORITY;
224 }
225 }
226
227 if (my_priority < chop_good_split) {
228 if (seam)
229 delete_seam(seam);
230 return; /* Made good answer */
231 }
232
233 if (seam) {
234 /* Combine with others */
235 if (array_count (*seam_pile) < MAX_NUM_SEAMS
236 /*|| tessedit_truncate_chopper==0 */ ) {
237 combine_seam(seam_queue, *seam_pile, seam);
238 *seam_pile = array_push (*seam_pile, seam);
239 }
240 else
241 delete_seam(seam);
242 }
243
244 my_priority = best_seam_priority (seam_queue);
245 if ((my_priority > chop_ok_split) ||
246 (my_priority > chop_good_split && split))
247 return;
248 }
249 }
250
251
252 /**********************************************************************
253 * combine_seam
254 *
255 * Find other seams to combine with this one. The new seams that result
256 * from this union should be added to the seam queue. The return value
257 * tells whether or not any additional seams were added to the queue.
258 **********************************************************************/
259 void Wordrec::combine_seam(SEAM_QUEUE seam_queue, SEAM_PILE seam_pile,
260 SEAM *seam) {
261 register inT16 x;
262 register inT16 dist;
263 inT16 bottom1, top1;
264 inT16 bottom2, top2;
265
266 SEAM *new_one;
267 SEAM *this_one;
268
269 bottom1 = seam->split1->point1->pos.y;
270 if (seam->split1->point2->pos.y >= bottom1)
271 top1 = seam->split1->point2->pos.y;
272 else {
273 top1 = bottom1;
274 bottom1 = seam->split1->point2->pos.y;
275 }
276 if (seam->split2 != NULL) {
277 bottom2 = seam->split2->point1->pos.y;
278 if (seam->split2->point2->pos.y >= bottom2)
279 top2 = seam->split2->point2->pos.y;
280 else {
281 top2 = bottom2;
282 bottom2 = seam->split2->point2->pos.y;
283 }
284 }
285 else {
286 bottom2 = bottom1;
287 top2 = top1;
288 }
289 array_loop(seam_pile, x) {
290 this_one = (SEAM *) array_value (seam_pile, x);
291 dist = seam->location.x - this_one->location.x;
292 if (-SPLIT_CLOSENESS < dist &&
293 dist < SPLIT_CLOSENESS &&
294 seam->priority + this_one->priority < chop_ok_split) {
295 inT16 split1_point1_y = this_one->split1->point1->pos.y;
296 inT16 split1_point2_y = this_one->split1->point2->pos.y;
297 inT16 split2_point1_y = 0;
298 inT16 split2_point2_y = 0;
299 if (this_one->split2) {
300 split2_point1_y = this_one->split2->point1->pos.y;
301 split2_point2_y = this_one->split2->point2->pos.y;
302 }
303 if (
305 (
306 /* this_one->split1 always exists */
307 (
308 ((split1_point1_y >= top1 && split1_point2_y >= top1) ||
309 (split1_point1_y <= bottom1 && split1_point2_y <= bottom1))
310 &&
311 ((split1_point1_y >= top2 && split1_point2_y >= top2) ||
312 (split1_point1_y <= bottom2 && split1_point2_y <= bottom2))
313 )
314 )
315 &&
316 (
317 this_one->split2 == NULL ||
318 (
319 ((split2_point1_y >= top1 && split2_point2_y >= top1) ||
320 (split2_point1_y <= bottom1 && split2_point2_y <= bottom1))
321 &&
322 ((split2_point1_y >= top2 && split2_point2_y >= top2) ||
323 (split2_point1_y <= bottom2 && split2_point2_y <= bottom2))
324 )
325 )
326 ) {
327 new_one = join_two_seams (seam, this_one);
328 if (chop_debug > 1)
329 print_seam ("Combo priority ", new_one);
330 add_seam_to_queue (seam_queue, new_one, new_one->priority);
331 }
332 }
333 }
334 }
335
336
337 /**********************************************************************
338 * constrained_split
339 *
340 * Constrain this split to obey certain rules. It must not cross any
341 * inner outline. It must not cut off a small chunk of the outline.
342 **********************************************************************/
343 inT16 Wordrec::constrained_split(SPLIT *split, TBLOB *blob) {
344 TESSLINE *outline;
345
346 if (is_little_chunk (split->point1, split->point2))
347 return (FALSE);
348
349 for (outline = blob->outlines; outline; outline = outline->next) {
350 if (split_bounds_overlap (split, outline) &&
351 crosses_outline (split->point1, split->point2, outline->loop)) {
352 return (FALSE);
353 }
354 }
355 return (TRUE);
356 }
357
358
359 /**********************************************************************
360 * delete_seam_pile
361 *
362 * Delete the seams that are held in the seam pile. Destroy the splits
363 * that are referenced by these seams.
364 **********************************************************************/
365 void Wordrec::delete_seam_pile(SEAM_PILE seam_pile) {
366 inT16 x;
367
368 array_loop(seam_pile, x) {
369 delete_seam ((SEAM *) array_value (seam_pile, x));
370 }
371 array_free(seam_pile);
372 }
373
374 /**********************************************************************
375 * pick_good_seam
376 *
377 * Find and return a good seam that will split this blob into two pieces.
378 * Work from the outlines provided.
379 **********************************************************************/
380 SEAM *Wordrec::pick_good_seam(TBLOB *blob) {
381 SEAM_QUEUE seam_queue;
382 SEAM_PILE seam_pile;
383 POINT_GROUP point_heap;
384 PRIORITY priority;
385 EDGEPT *edge;
386 EDGEPT *points[MAX_NUM_POINTS];
387 EDGEPT_CLIST new_points;
388 SEAM *seam = NULL;
389 TESSLINE *outline;
390 inT16 num_points = 0;
391
392 #ifndef GRAPHICS_DISABLED
393 if (chop_debug > 2)
394 wordrec_display_splits.set_value(true);
395
396 draw_blob_edges(blob);
397 #endif
398
399 point_heap = MakeHeap (MAX_NUM_POINTS);
400 for (outline = blob->outlines; outline; outline = outline->next)
401 prioritize_points(outline, point_heap);
402
403 while (HeapPop (point_heap, &priority, &edge) == TESS_HEAP_OK) {
404 if (num_points < MAX_NUM_POINTS)
405 points[num_points++] = (EDGEPT *) edge;
406 }
407 FreeHeap(point_heap);
408
409 /* Initialize queue & pile */
410 create_seam_pile(seam_pile);
411 create_seam_queue(seam_queue);
412
413 try_point_pairs(points, num_points, seam_queue, &seam_pile, &seam, blob);
414 try_vertical_splits(points, num_points, &new_points,
415 seam_queue, &seam_pile, &seam, blob);
416
417 if (seam == NULL) {
418 choose_best_seam(seam_queue, &seam_pile, NULL, BAD_PRIORITY, &seam, blob);
419 }
420 else if (seam->priority > chop_good_split) {
421 choose_best_seam (seam_queue, &seam_pile, NULL, seam->priority,
422 &seam, blob);
423 }
424
425 EDGEPT_C_IT it(&new_points);
426 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
427 EDGEPT *inserted_point = it.data();
428 if (!point_used_by_seam(seam, inserted_point)) {
429 for (outline = blob->outlines; outline; outline = outline->next) {
430 if (outline->loop == inserted_point) {
431 outline->loop = outline->loop->next;
432 }
433 }
434 remove_edgept(inserted_point);
435 }
436 }
437
438 delete_seam_queue(seam_queue);
439 delete_seam_pile(seam_pile);
440
441 if (seam) {
442 if (seam->priority > chop_ok_split) {
443 delete_seam(seam);
444 seam = NULL;
445 }
446 #ifndef GRAPHICS_DISABLED
447 else if (wordrec_display_splits) {
448 if (seam->split1)
449 mark_split (seam->split1);
450 if (seam->split2)
451 mark_split (seam->split2);
452 if (seam->split3)
453 mark_split (seam->split3);
454 if (chop_debug > 2) {
455 update_edge_window();
456 edge_window_wait();
457 }
458 }
459 #endif
460 }
461
462 if (chop_debug)
463 wordrec_display_splits.set_value(false);
464
465 return (seam);
466 }
467
468
469 /**********************************************************************
470 * seam_priority
471 *
472 * Assign a full priority value to the seam.
473 **********************************************************************/
474 PRIORITY Wordrec::seam_priority(SEAM *seam, inT16 xmin, inT16 xmax) {
475 PRIORITY priority;
476
477 if (seam->split1 == NULL)
478 priority = 0;
479
480 else if (seam->split2 == NULL) {
481 priority = (seam->priority +
482 full_split_priority (seam->split1, xmin, xmax));
483 }
484
485 else if (seam->split3 == NULL) {
486 split_outline (seam->split2->point1, seam->split2->point2);
487 priority = (seam->priority +
488 full_split_priority (seam->split1, xmin, xmax));
489 unsplit_outlines (seam->split2->point1, seam->split2->point2);
490 }
491
492 else {
493 split_outline (seam->split2->point1, seam->split2->point2);
494 split_outline (seam->split3->point1, seam->split3->point2);
495 priority = (seam->priority +
496 full_split_priority (seam->split1, xmin, xmax));
497 unsplit_outlines (seam->split3->point1, seam->split3->point2);
498 unsplit_outlines (seam->split2->point1, seam->split2->point2);
499 }
500
501 return (priority);
502 }
503
504
505 /**********************************************************************
506 * try_point_pairs
507 *
508 * Try all the splits that are produced by pairing critical points
509 * together. See if any of them are suitable for use. Use a seam
510 * queue and seam pile that have already been initialized and used.
511 **********************************************************************/
512 void Wordrec::try_point_pairs (EDGEPT * points[MAX_NUM_POINTS],
513 inT16 num_points,
514 SEAM_QUEUE seam_queue,
515 SEAM_PILE * seam_pile,
516 SEAM ** seam,
517 TBLOB * blob) {
518 inT16 x;
519 inT16 y;
520 SPLIT *split;
521 PRIORITY priority;
522
523 for (x = 0; x < num_points; x++) {
524 for (y = x + 1; y < num_points; y++) {
525
526 if (points[y] &&
527 weighted_edgept_dist(points[x], points[y],
528 chop_x_y_weight) < chop_split_length &&
529 points[x] != points[y]->next &&
530 points[y] != points[x]->next &&
531 !is_exterior_point(points[x], points[y]) &&
532 !is_exterior_point(points[y], points[x])) {
533 split = new_split (points[x], points[y]);
534 priority = partial_split_priority (split);
535
536 choose_best_seam(seam_queue, seam_pile, split, priority, seam, blob);
537 }
538 }
539 }
540
541 }
542
543
544 /**********************************************************************
545 * try_vertical_splits
546 *
547 * Try all the splits that are produced by vertical projection to see
548 * if any of them are suitable for use. Use a seam queue and seam pile
549 * that have already been initialized and used.
550 * Return in new_points a collection of points that were inserted into
551 * the blob while examining vertical splits and which may safely be
552 * removed once a seam is chosen if they are not part of the seam.
553 **********************************************************************/
554 void Wordrec::try_vertical_splits(EDGEPT * points[MAX_NUM_POINTS],
555 inT16 num_points,
556 EDGEPT_CLIST *new_points,
557 SEAM_QUEUE seam_queue,
558 SEAM_PILE * seam_pile,
559 SEAM ** seam,
560 TBLOB * blob) {
561 EDGEPT *vertical_point = NULL;
562 SPLIT *split;
563 inT16 x;
564 PRIORITY priority;
565 TESSLINE *outline;
566
567 for (x = 0; x < num_points; x++) {
568 vertical_point = NULL;
569 for (outline = blob->outlines; outline; outline = outline->next) {
570 vertical_projection_point(points[x], outline->loop,
571 &vertical_point, new_points);
572 }
573
574 if (vertical_point &&
575 points[x] != vertical_point->next &&
576 vertical_point != points[x]->next &&
577 weighted_edgept_dist(points[x], vertical_point,
578 chop_x_y_weight) < chop_split_length) {
579
580 split = new_split (points[x], vertical_point);
581 priority = partial_split_priority (split);
582
583 choose_best_seam(seam_queue, seam_pile, split, priority, seam, blob);
584 }
585 }
586 }
587
588 }