Tesseract  3.02
 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  **********************************************************************/
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  **********************************************************************/
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  **********************************************************************/
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  **********************************************************************/
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  **********************************************************************/
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) {
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  **********************************************************************/
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  **********************************************************************/
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],
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  **********************************************************************/
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,
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 }