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
seam.cpp
Go to the documentation of this file.
1 /* -*-C-*-
2 ********************************************************************************
3 *
4 * File: seam.c (Formerly seam.c)
5 * Description:
6 * Author: Mark Seaman, OCR Technology
7 * Created: Fri Oct 16 14:37:00 1987
8 * Modified: Fri May 17 16:30:13 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 "seam.h"
29 #include "blobs.h"
30 #include "callcpp.h"
31 #include "structures.h"
32
33 #ifdef __UNIX__
34 #include <assert.h>
35 #endif
36
37 /*----------------------------------------------------------------------
38 V a r i a b l e s
39 ----------------------------------------------------------------------*/
40 #define NUM_STARTING_SEAMS 20
41 makestructure(newseam, free_seam, SEAM);
42
43 /*----------------------------------------------------------------------
44 Public Function Code
45 ----------------------------------------------------------------------*/
53 bool point_in_split(SPLIT *split, EDGEPT *point1, EDGEPT *point2) {
54 return ((split) ? ((exact_point (split->point1, point1) ||
55 exact_point (split->point1, point2) ||
56 exact_point (split->point2, point1) ||
57 exact_point (split->point2, point2)) ? TRUE : FALSE)
58 : FALSE);
59 }
60
61
69 bool point_in_seam(SEAM *seam, SPLIT *split) {
70 return (point_in_split(seam->split1, split->point1, split->point2) ||
71 point_in_split(seam->split2, split->point1, split->point2) ||
72 point_in_split(seam->split3, split->point1, split->point2));
73 }
74
81 bool point_used_by_split(SPLIT *split, EDGEPT *point) {
82 if (split == NULL) return false;
83 return point == split->point1 || point == split->point2;
84 }
85
92 bool point_used_by_seam(SEAM *seam, EDGEPT *point) {
93 if (seam == NULL) return false;
94 return point_used_by_split(seam->split1, point) ||
95 point_used_by_split(seam->split2, point) ||
96 point_used_by_split(seam->split3, point);
97 }
98
104 SEAMS add_seam(SEAMS seam_list, SEAM *seam) {
105 return (array_push (seam_list, seam));
106 }
107
108
116 void combine_seams(SEAM *dest_seam, SEAM *source_seam) {
117 dest_seam->priority += source_seam->priority;
118 dest_seam->location += source_seam->location;
119 dest_seam->location /= 2;
120
121 if (source_seam->split1) {
122 if (!dest_seam->split1)
123 dest_seam->split1 = source_seam->split1;
124 else if (!dest_seam->split2)
125 dest_seam->split2 = source_seam->split1;
126 else if (!dest_seam->split3)
127 dest_seam->split3 = source_seam->split1;
128 else
129 cprintf("combine_seam: Seam is too crowded, can't be combined !\n");
130 }
131 if (source_seam->split2) {
132 if (!dest_seam->split2)
133 dest_seam->split2 = source_seam->split2;
134 else if (!dest_seam->split3)
135 dest_seam->split3 = source_seam->split2;
136 else
137 cprintf("combine_seam: Seam is too crowded, can't be combined !\n");
138 }
139 if (source_seam->split3) {
140 if (!dest_seam->split3)
141 dest_seam->split3 = source_seam->split3;
142 else
143 cprintf("combine_seam: Seam is too crowded, can't be combined !\n");
144 }
145 free_seam(source_seam);
146 }
147
148
154 void delete_seam(void *arg) { //SEAM *seam)
155 SEAM *seam = (SEAM *) arg;
156
157 if (seam) {
158 if (seam->split1)
159 delete_split(seam->split1);
160 if (seam->split2)
161 delete_split(seam->split2);
162 if (seam->split3)
163 delete_split(seam->split3);
164 free_seam(seam);
165 }
166 }
167
175 SEAMS start_seam_list(TBLOB *blobs) {
176 TBLOB *blob;
177 SEAMS seam_list;
178 TPOINT location;
179 /* Seam slot per char */
180 seam_list = new_seam_list ();
181
182 for (blob = blobs; blob->next != NULL; blob = blob->next) {
183 TBOX bbox = blob->bounding_box();
184 TBOX nbox = blob->next->bounding_box();
185 location.x = (bbox.right() + nbox.left()) / 2;
186 location.y = (bbox.bottom() + bbox.top() + nbox.bottom() + nbox.top()) / 4;
187 seam_list = add_seam(seam_list,
188 new_seam(0.0, location, NULL, NULL, NULL));
189 }
190
191 return seam_list;
192 }
193
200 void free_seam_list(SEAMS seam_list) {
201 int x;
202
203 array_loop(seam_list, x) delete_seam(array_value (seam_list, x));
204 array_free(seam_list);
205 }
206
207
213 bool test_insert_seam(SEAMS seam_list,
214 int index,
215 TBLOB *left_blob,
216 TBLOB *first_blob) {
217 SEAM *test_seam;
218 TBLOB *blob;
219 int test_index;
220 int list_length;
221
222 list_length = array_count (seam_list);
223 for (test_index=0, blob=first_blob->next;
224 test_index < index;
225 test_index++, blob=blob->next) {
226 test_seam = (SEAM *) array_value(seam_list, test_index);
227 if (test_index + test_seam->widthp < index &&
228 test_seam->widthp + test_index == index - 1 &&
229 account_splits_right(test_seam, blob) < 0)
230 return false;
231 }
232 for (test_index=index, blob=left_blob->next;
233 test_index < list_length;
234 test_index++, blob=blob->next) {
235 test_seam = (SEAM *) array_value(seam_list, test_index);
236 if (test_index - test_seam->widthn >= index &&
237 test_index - test_seam->widthn == index &&
238 account_splits_left(test_seam, first_blob, blob) < 0)
239 return false;
240 }
241 return true;
242 }
243
250 SEAMS insert_seam(SEAMS seam_list,
251 int index,
252 SEAM *seam,
253 TBLOB *left_blob,
254 TBLOB *first_blob) {
255 SEAM *test_seam;
256 TBLOB *blob;
257 int test_index;
258 int list_length;
259
260 list_length = array_count(seam_list);
261 for (test_index=0, blob=first_blob->next;
262 test_index < index;
263 test_index++, blob=blob->next) {
264 test_seam = (SEAM *) array_value(seam_list, test_index);
265 if (test_index + test_seam->widthp >= index) {
266 test_seam->widthp++; /*got in the way */
267 } else if (test_seam->widthp + test_index == index - 1) {
268 test_seam->widthp = account_splits_right(test_seam, blob);
269 if (test_seam->widthp < 0) {
270 cprintf("Failed to find any right blob for a split!\n");
271 print_seam("New dud seam", seam);
272 print_seam("Failed seam", test_seam);
273 }
274 }
275 }
276 for (test_index=index, blob=left_blob->next;
277 test_index < list_length;
278 test_index++, blob=blob->next) {
279 test_seam = (SEAM *) array_value(seam_list, test_index);
280 if (test_index - test_seam->widthn < index) {
281 test_seam->widthn++; /*got in the way */
282 } else if (test_index - test_seam->widthn == index) {
283 test_seam->widthn = account_splits_left(test_seam, first_blob, blob);
284 if (test_seam->widthn < 0) {
285 cprintf("Failed to find any left blob for a split!\n");
286 print_seam("New dud seam", seam);
287 print_seam("Failed seam", test_seam);
288 }
289 }
290 }
291 return (array_insert (seam_list, index, seam));
292 }
293
294
301 int account_splits_right(SEAM *seam, TBLOB *blob) {
302 inT8 found_em[3];
303 inT8 width;
304
305 found_em[0] = seam->split1 == NULL;
306 found_em[1] = seam->split2 == NULL;
307 found_em[2] = seam->split3 == NULL;
308 if (found_em[0] && found_em[1] && found_em[2])
309 return 0;
310 width = 0;
311 do {
312 if (!found_em[0])
313 found_em[0] = find_split_in_blob(seam->split1, blob);
314 if (!found_em[1])
315 found_em[1] = find_split_in_blob(seam->split2, blob);
316 if (!found_em[2])
317 found_em[2] = find_split_in_blob(seam->split3, blob);
318 if (found_em[0] && found_em[1] && found_em[2]) {
319 return width;
320 }
321 width++;
322 blob = blob->next;
323 } while (blob != NULL);
324 return -1;
325 }
326
327
334 int account_splits_left(SEAM *seam, TBLOB *blob, TBLOB *end_blob) {
335 inT32 depth = 0;
336 inT8 width = 0;
337 inT8 found_em[3];
338 account_splits_left_helper(seam, blob, end_blob, &depth, &width, found_em);
339 return width;
340 }
341
342 void account_splits_left_helper(SEAM *seam, TBLOB *blob, TBLOB *end_blob,
343 inT32 *depth, inT8 *width, inT8* found_em) {
344 if (blob != end_blob) {
345 (*depth)++;
346 account_splits_left_helper(seam, blob->next, end_blob,
347 depth, width, found_em);
348 (*depth)--;
349 } else {
350 found_em[0] = seam->split1 == NULL;
351 found_em[1] = seam->split2 == NULL;
352 found_em[2] = seam->split3 == NULL;
353 *width = 0;
354 }
355 if (!found_em[0])
356 found_em[0] = find_split_in_blob(seam->split1, blob);
357 if (!found_em[1])
358 found_em[1] = find_split_in_blob(seam->split2, blob);
359 if (!found_em[2])
360 found_em[2] = find_split_in_blob(seam->split3, blob);
361 if (!found_em[0] || !found_em[1] || !found_em[2]) {
362 (*width)++;
363 if (*depth == 0) {
364 *width = -1;
365 }
366 }
367 }
368
369
375 bool find_split_in_blob(SPLIT *split, TBLOB *blob) {
376 TESSLINE *outline;
377
378 for (outline = blob->outlines; outline != NULL; outline = outline->next)
379 if (outline->Contains(split->point1->pos))
380 break;
381 if (outline == NULL)
382 return FALSE;
383 for (outline = blob->outlines; outline != NULL; outline = outline->next)
384 if (outline->Contains(split->point2->pos))
385 return TRUE;
386 return FALSE;
387 }
388
389
396 SEAM *join_two_seams(SEAM *seam1, SEAM *seam2) {
397 SEAM *result = NULL;
398 SEAM *temp;
399
400 assert(seam1 &&seam2);
401
402 if (((seam1->split3 == NULL && seam2->split2 == NULL) ||
403 (seam1->split2 == NULL && seam2->split3 == NULL) ||
404 seam1->split1 == NULL || seam2->split1 == NULL) &&
405 (!shared_split_points(seam1, seam2))) {
406 clone_seam(result, seam1);
407 clone_seam(temp, seam2);
408 combine_seams(result, temp);
409 }
410 return (result);
411 }
412
413
421 SEAM *new_seam(PRIORITY priority,
422 const TPOINT& location,
423 SPLIT *split1,
424 SPLIT *split2,
425 SPLIT *split3) {
426 SEAM *seam;
427
428 seam = newseam ();
429
430 seam->priority = priority;
431 seam->location = location;
432 seam->widthp = 0;
433 seam->widthn = 0;
434 seam->split1 = split1;
435 seam->split2 = split2;
436 seam->split3 = split3;
437
438 return (seam);
439 }
440
441
447 SEAMS new_seam_list() {
448 return (array_new (NUM_STARTING_SEAMS));
449 }
450
451
458 void print_seam(const char *label, SEAM *seam) {
459 if (seam) {
460 cprintf(label);
461 cprintf(" %6.2f @ (%d,%d), p=%d, n=%d ",
462 seam->priority, seam->location.x, seam->location.y,
463 seam->widthp, seam->widthn);
464 print_split(seam->split1);
465
466 if (seam->split2) {
467 cprintf(", ");
468 print_split (seam->split2);
469 if (seam->split3) {
470 cprintf(", ");
471 print_split (seam->split3);
472 }
473 }
474 cprintf ("\n");
475 }
476 }
477
478
485 void print_seams(const char *label, SEAMS seams) {
486 int x;
487 char number[CHARS_PER_LINE];
488
489 if (seams) {
490 cprintf("%s\n", label);
491 array_loop(seams, x) {
492 sprintf(number, "%2d: ", x);
493 print_seam(number, (SEAM *) array_value(seams, x));
494 }
495 cprintf("\n");
496 }
497 }
498
499
507 int shared_split_points(SEAM *seam1, SEAM *seam2) {
508 if (seam1 == NULL || seam2 == NULL)
509 return (FALSE);
510
511 if (seam2->split1 == NULL)
512 return (FALSE);
513 if (point_in_seam(seam1, seam2->split1))
514 return (TRUE);
515
516 if (seam2->split2 == NULL)
517 return (FALSE);
518 if (point_in_seam(seam1, seam2->split2))
519 return (TRUE);
520
521 if (seam2->split3 == NULL)
522 return (FALSE);
523 if (point_in_seam(seam1, seam2->split3))
524 return (TRUE);
525
526 return (FALSE);
527 }
528
529 /**********************************************************************
530 * break_pieces
531 *
532 * Break up the blobs in this chain so that they are all independent.
533 * This operation should undo the affect of join_pieces.
534 **********************************************************************/
535 void break_pieces(TBLOB *blobs, SEAMS seams, inT16 start, inT16 end) {
536 TESSLINE *outline = blobs->outlines;
537 TBLOB *next_blob;
538 inT16 x;
539
540 for (x = start; x < end; x++)
541 reveal_seam ((SEAM *) array_value (seams, x));
542
543 next_blob = blobs->next;
544
545 while (outline && next_blob) {
546 if (outline->next == next_blob->outlines) {
547 outline->next = NULL;
548 outline = next_blob->outlines;
549 next_blob = next_blob->next;
550 }
551 else {
552 outline = outline->next;
553 }
554 }
555 }
556
557
558 /**********************************************************************
559 * join_pieces
560 *
561 * Join a group of base level pieces into a single blob that can then
562 * be classified.
563 **********************************************************************/
564 void join_pieces(TBLOB *piece_blobs, SEAMS seams, inT16 start, inT16 end) {
565 TBLOB *next_blob;
566 TBLOB *blob;
567 inT16 x;
568 TESSLINE *outline;
569 SEAM *seam;
570
571 for (x = 0, blob = piece_blobs; x < start; x++)
572 blob = blob->next;
573 next_blob = blob->next;
574 outline = blob->outlines;
575 if (!outline)
576 return;
577
578 while (x < end) {
579 seam = (SEAM *) array_value (seams, x);
580 if (x - seam->widthn >= start && x + seam->widthp < end)
581 hide_seam(seam);
582 while (outline->next)
583 outline = outline->next;
584 outline->next = next_blob->outlines;
585 next_blob = next_blob->next;
586
587 x++;
588 }
589 }
590
591
592 /**********************************************************************
593 * hide_seam
594 *
595 * Change the edge points that are referenced by this seam to make
596 * them hidden edges.
597 **********************************************************************/
598 void hide_seam(SEAM *seam) {
599 if (seam == NULL || seam->split1 == NULL)
600 return;
601 hide_edge_pair (seam->split1->point1, seam->split1->point2);
602
603 if (seam->split2 == NULL)
604 return;
605 hide_edge_pair (seam->split2->point1, seam->split2->point2);
606
607 if (seam->split3 == NULL)
608 return;
609 hide_edge_pair (seam->split3->point1, seam->split3->point2);
610 }
611
612
613 /**********************************************************************
614 * hide_edge_pair
615 *
616 * Change the edge points that are referenced by this seam to make
617 * them hidden edges.
618 **********************************************************************/
619 void hide_edge_pair(EDGEPT *pt1, EDGEPT *pt2) {
620 EDGEPT *edgept;
621
622 edgept = pt1;
623 do {
624 edgept->Hide();
625 edgept = edgept->next;
626 }
627 while (!exact_point (edgept, pt2) && edgept != pt1);
628 if (edgept == pt1) {
629 /* cprintf("Hid entire outline at (%d,%d)!!\n",
630 edgept->pos.x,edgept->pos.y); */
631 }
632 edgept = pt2;
633 do {
634 edgept->Hide();
635 edgept = edgept->next;
636 }
637 while (!exact_point (edgept, pt1) && edgept != pt2);
638 if (edgept == pt2) {
639 /* cprintf("Hid entire outline at (%d,%d)!!\n",
640 edgept->pos.x,edgept->pos.y); */
641 }
642 }
643
644
645 /**********************************************************************
646 * reveal_seam
647 *
648 * Change the edge points that are referenced by this seam to make
649 * them hidden edges.
650 **********************************************************************/
651 void reveal_seam(SEAM *seam) {
652 if (seam == NULL || seam->split1 == NULL)
653 return;
654 reveal_edge_pair (seam->split1->point1, seam->split1->point2);
655
656 if (seam->split2 == NULL)
657 return;
658 reveal_edge_pair (seam->split2->point1, seam->split2->point2);
659
660 if (seam->split3 == NULL)
661 return;
662 reveal_edge_pair (seam->split3->point1, seam->split3->point2);
663 }
664
665
666 /**********************************************************************
667 * reveal_edge_pair
668 *
669 * Change the edge points that are referenced by this seam to make
670 * them hidden edges.
671 **********************************************************************/
672 void reveal_edge_pair(EDGEPT *pt1, EDGEPT *pt2) {
673 EDGEPT *edgept;
674
675 edgept = pt1;
676 do {
677 edgept->Reveal();
678 edgept = edgept->next;
679 }
680 while (!exact_point (edgept, pt2) && edgept != pt1);
681 if (edgept == pt1) {
682 /* cprintf("Hid entire outline at (%d,%d)!!\n",
683 edgept->pos.x,edgept->pos.y); */
684 }
685 edgept = pt2;
686 do {
687 edgept->Reveal();
688 edgept = edgept->next;
689 }
690 while (!exact_point (edgept, pt1) && edgept != pt2);
691 if (edgept == pt2) {
692 /* cprintf("Hid entire outline at (%d,%d)!!\n",
693 edgept->pos.x,edgept->pos.y); */
694 }
695 }