Tesseract  3.02
 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 
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 
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 
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 
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 }