Tesseract  3.02
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
blobs.cpp
Go to the documentation of this file.
1 /* -*-C-*-
2  ********************************************************************************
3  *
4  * File: blobs.c (Formerly blobs.c)
5  * Description: Blob definition
6  * Author: Mark Seaman, OCR Technology
7  * Created: Fri Oct 27 15:39:52 1989
8  * Modified: Thu Mar 28 15:33:26 1991 (Mark Seaman) marks@hpgrlt
9  * Language: C
10  * Package: N/A
11  * Status: Experimental (Do Not Distribute)
12  *
13  * (c) Copyright 1989, 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 /*----------------------------------------------------------------------
27  I n c l u d e s
28 ----------------------------------------------------------------------*/
29 // Include automatically generated configuration file if running autoconf.
30 #ifdef HAVE_CONFIG_H
31 #include "config_auto.h"
32 #endif
33 
34 #include "mfcpch.h"
35 #include "blobs.h"
36 #include "ccstruct.h"
37 #include "clst.h"
38 #include "cutil.h"
39 #include "emalloc.h"
40 #include "helpers.h"
41 #include "ndminx.h"
42 #include "normalis.h"
43 #include "ocrblock.h"
44 #include "ocrrow.h"
45 #include "points.h"
46 #include "polyaprx.h"
47 #include "structures.h"
48 #include "werd.h"
49 
51 
52 // A Vector representing the "vertical" direction when measuring the
53 // divisiblity of blobs into multiple blobs just by separating outlines.
54 // See divisible_blob below for the use.
56 // A vector representing the "vertical" direction for italic text for use
57 // when separating outlines. Using it actually deteriorates final accuracy,
58 // so it is only used for ApplyBoxes chopping to get a better segmentation.
60 
61 /*----------------------------------------------------------------------
62  F u n c t i o n s
63 ----------------------------------------------------------------------*/
64 
66 
67 // Consume the circular list of EDGEPTs to make a TESSLINE.
69  TESSLINE* result = new TESSLINE;
70  result->loop = outline;
71  result->SetupFromPos();
72  return result;
73 }
74 
75 // Copies the data and the outline, but leaves next untouched.
76 void TESSLINE::CopyFrom(const TESSLINE& src) {
77  Clear();
78  topleft = src.topleft;
79  botright = src.botright;
80  start = src.start;
81  is_hole = src.is_hole;
82  if (src.loop != NULL) {
83  EDGEPT* prevpt = NULL;
84  EDGEPT* newpt = NULL;
85  EDGEPT* srcpt = src.loop;
86  do {
87  newpt = new EDGEPT(*srcpt);
88  if (prevpt == NULL) {
89  loop = newpt;
90  } else {
91  newpt->prev = prevpt;
92  prevpt->next = newpt;
93  }
94  prevpt = newpt;
95  srcpt = srcpt->next;
96  } while (srcpt != src.loop);
97  loop->prev = newpt;
98  newpt->next = loop;
99  }
100 }
101 
102 // Deletes owned data.
104  if (loop == NULL)
105  return;
106 
107  EDGEPT* this_edge = loop;
108  do {
109  EDGEPT* next_edge = this_edge->next;
110  delete this_edge;
111  this_edge = next_edge;
112  } while (this_edge != loop);
113  loop = NULL;
114 }
115 
116 // Normalize in-place using the DENORM.
117 void TESSLINE::Normalize(const DENORM& denorm) {
118  EDGEPT* pt = loop;
119  do {
120  denorm.LocalNormTransform(pt->pos, &pt->pos);
121  pt = pt->next;
122  } while (pt != loop);
123  SetupFromPos();
124 }
125 
126 // Rotates by the given rotation in place.
127 void TESSLINE::Rotate(const FCOORD rot) {
128  EDGEPT* pt = loop;
129  do {
130  int tmp = static_cast<int>(floor(pt->pos.x * rot.x() -
131  pt->pos.y * rot.y() + 0.5));
132  pt->pos.y = static_cast<int>(floor(pt->pos.y * rot.x() +
133  pt->pos.x * rot.y() + 0.5));
134  pt->pos.x = tmp;
135  pt = pt->next;
136  } while (pt != loop);
137  SetupFromPos();
138 }
139 
140 // Moves by the given vec in place.
141 void TESSLINE::Move(const ICOORD vec) {
142  EDGEPT* pt = loop;
143  do {
144  pt->pos.x += vec.x();
145  pt->pos.y += vec.y();
146  pt = pt->next;
147  } while (pt != loop);
148  SetupFromPos();
149 }
150 
151 // Scales by the given factor in place.
152 void TESSLINE::Scale(float factor) {
153  EDGEPT* pt = loop;
154  do {
155  pt->pos.x = static_cast<int>(floor(pt->pos.x * factor + 0.5));
156  pt->pos.y = static_cast<int>(floor(pt->pos.y * factor + 0.5));
157  pt = pt->next;
158  } while (pt != loop);
159  SetupFromPos();
160 }
161 
162 // Sets up the start and vec members of the loop from the pos members.
164  EDGEPT* pt = loop;
165  do {
166  pt->vec.x = pt->next->pos.x - pt->pos.x;
167  pt->vec.y = pt->next->pos.y - pt->pos.y;
168  pt = pt->next;
169  } while (pt != loop);
170  start = pt->pos;
172 }
173 
174 // Recomputes the bounding box from the points in the loop.
176  int minx = MAX_INT32;
177  int miny = MAX_INT32;
178  int maxx = -MAX_INT32;
179  int maxy = -MAX_INT32;
180 
181  // Find boundaries.
182  start = loop->pos;
183  EDGEPT* this_edge = loop;
184  do {
185  if (!this_edge->IsHidden() || !this_edge->prev->IsHidden()) {
186  if (this_edge->pos.x < minx)
187  minx = this_edge->pos.x;
188  if (this_edge->pos.y < miny)
189  miny = this_edge->pos.y;
190  if (this_edge->pos.x > maxx)
191  maxx = this_edge->pos.x;
192  if (this_edge->pos.y > maxy)
193  maxy = this_edge->pos.y;
194  }
195  this_edge = this_edge->next;
196  } while (this_edge != loop);
197  // Reset bounds.
198  topleft.x = minx;
199  topleft.y = maxy;
200  botright.x = maxx;
201  botright.y = miny;
202 }
203 
204 // Computes the min and max cross product of the outline points with the
205 // given vec and returns the results in min_xp and max_xp. Geometrically
206 // this is the left and right edge of the outline perpendicular to the
207 // given direction, but to get the distance units correct, you would
208 // have to divide by the modulus of vec.
210  int* min_xp, int* max_xp) const {
211  *min_xp = MAX_INT32;
212  *max_xp = MIN_INT32;
213  EDGEPT* this_edge = loop;
214  do {
215  if (!this_edge->IsHidden() || !this_edge->prev->IsHidden()) {
216  int product = CROSS(this_edge->pos, vec);
217  UpdateRange(product, min_xp, max_xp);
218  }
219  this_edge = this_edge->next;
220  } while (this_edge != loop);
221 }
222 
224  return TBOX(topleft.x, botright.y, botright.x, topleft.y);
225 }
226 
227 #ifndef GRAPHICS_DISABLED
229  ScrollView::Color child_color) {
230  if (is_hole)
231  window->Pen(child_color);
232  else
233  window->Pen(color);
234  window->SetCursor(start.x, start.y);
235  EDGEPT* pt = loop;
236  do {
237  bool prev_hidden = pt->IsHidden();
238  pt = pt->next;
239  if (prev_hidden)
240  window->SetCursor(pt->pos.x, pt->pos.y);
241  else
242  window->DrawTo(pt->pos.x, pt->pos.y);
243  } while (pt != loop);
244 }
245 #endif // GRAPHICS_DISABLED
246 
247 // Iterate the given list of outlines, converting to TESSLINE by polygonal
248 // approximation and recursively any children, returning the current tail
249 // of the resulting list of TESSLINEs.
250 static TESSLINE** ApproximateOutlineList(C_OUTLINE_LIST* outlines,
251  bool children,
252  TESSLINE** tail) {
253  C_OUTLINE_IT ol_it(outlines);
254  for (ol_it.mark_cycle_pt(); !ol_it.cycled_list(); ol_it.forward()) {
255  C_OUTLINE* outline = ol_it.data();
256  TESSLINE* tessline = ApproximateOutline(outline);
257  tessline->is_hole = children;
258  *tail = tessline;
259  tail = &tessline->next;
260  if (!outline->child()->empty()) {
261  tail = ApproximateOutlineList(outline->child(), true, tail);
262  }
263  }
264  return tail;
265 }
266 
267 // Factory to build a TBLOB from a C_BLOB with polygonal
268 // approximation along the way.
270  C_OUTLINE_IT ol_it = src->out_list();
271  TBLOB* tblob = new TBLOB;
272  ApproximateOutlineList(src->out_list(), false, &tblob->outlines);
273  return tblob;
274 }
275 
276 // Normalizes the blob for classification only if needed.
277 // (Normally this means a non-zero classify rotation.)
278 // If no Normalization is needed, then NULL is returned, and the denorm is
279 // unchanged. Otherwise a new TBLOB is returned and the denorm points to
280 // a new DENORM. In this case, both the TBLOB and DENORM must be deleted.
282  TBLOB* rotated_blob = NULL;
283  // If necessary, copy the blob and rotate it. The rotation is always
284  // +/- 90 degrees, as 180 was already taken care of.
285  if ((*denorm)->block() != NULL &&
286  (*denorm)->block()->classify_rotation().y() != 0.0) {
287  TBOX box = bounding_box();
288  int x_middle = (box.left() + box.right()) / 2;
289  int y_middle = (box.top() + box.bottom()) / 2;
290  rotated_blob = new TBLOB(*this);
291  const FCOORD& rotation = (*denorm)->block()->classify_rotation();
292  DENORM* norm = new DENORM;
293  // Move the rotated blob back to the same y-position so that we
294  // can still distinguish similar glyphs with differeny y-position.
295  float target_y = kBlnBaselineOffset +
296  (rotation.y() > 0 ? x_middle - box.left() : box.right() - x_middle);
297  norm->SetupNormalization(NULL, NULL, &rotation, *denorm, NULL, 0,
298  x_middle, y_middle, 1.0f, 1.0f, 0.0f, target_y);
299  // x_middle, y_middle, 1.0f, 1.0f, 0.0f, y_middle);
300  rotated_blob->Normalize(*norm);
301  *denorm = norm;
302  }
303  return rotated_blob;
304 }
305 
306 // Copies the data and the outline, but leaves next untouched.
307 void TBLOB::CopyFrom(const TBLOB& src) {
308  Clear();
309  TESSLINE* prev_outline = NULL;
310  for (TESSLINE* srcline = src.outlines; srcline != NULL;
311  srcline = srcline->next) {
312  TESSLINE* new_outline = new TESSLINE(*srcline);
313  if (outlines == NULL)
314  outlines = new_outline;
315  else
316  prev_outline->next = new_outline;
317  prev_outline = new_outline;
318  }
319 }
320 
321 // Deletes owned data.
322 void TBLOB::Clear() {
323  for (TESSLINE* next_outline = NULL; outlines != NULL;
324  outlines = next_outline) {
325  next_outline = outlines->next;
326  delete outlines;
327  }
328 }
329 // Normalize in-place using the DENORM.
330 void TBLOB::Normalize(const DENORM& denorm) {
331  // TODO(rays) outline->Normalize is more accurate, but breaks tests due
332  // the changes it makes. Reinstate this code with a retraining.
333 #if 1
334  for (TESSLINE* outline = outlines; outline != NULL; outline = outline->next) {
335  outline->Normalize(denorm);
336  }
337 #else
338  denorm.LocalNormBlob(this);
339 #endif
340 }
341 
342 // Rotates by the given rotation in place.
343 void TBLOB::Rotate(const FCOORD rotation) {
344  for (TESSLINE* outline = outlines; outline != NULL; outline = outline->next) {
345  outline->Rotate(rotation);
346  }
347 }
348 
349 // Moves by the given vec in place.
350 void TBLOB::Move(const ICOORD vec) {
351  for (TESSLINE* outline = outlines; outline != NULL; outline = outline->next) {
352  outline->Move(vec);
353  }
354 }
355 
356 // Scales by the given factor in place.
357 void TBLOB::Scale(float factor) {
358  for (TESSLINE* outline = outlines; outline != NULL; outline = outline->next) {
359  outline->Scale(factor);
360  }
361 }
362 
363 // Recomputes the bounding boxes of the outlines.
365  for (TESSLINE* outline = outlines; outline != NULL; outline = outline->next) {
366  outline->ComputeBoundingBox();
367  }
368 }
369 
370 // Returns the number of outlines.
371 int TBLOB::NumOutlines() const {
372  int result = 0;
373  for (TESSLINE* outline = outlines; outline != NULL; outline = outline->next)
374  ++result;
375  return result;
376 }
377 
378 /**********************************************************************
379  * TBLOB::bounding_box()
380  *
381  * Compute the bounding_box of a compound blob, defined to be the
382  * bounding box of the union of all top-level outlines in the blob.
383  **********************************************************************/
385  if (outlines == NULL)
386  return TBOX(0, 0, 0, 0);
387  TESSLINE *outline = outlines;
388  TBOX box = outline->bounding_box();
389  for (outline = outline->next; outline != NULL; outline = outline->next) {
390  box += outline->bounding_box();
391  }
392  return box;
393 }
394 
395 #ifndef GRAPHICS_DISABLED
397  ScrollView::Color child_color) {
398  for (TESSLINE* outline = outlines; outline != NULL; outline = outline->next)
399  outline->plot(window, color, child_color);
400 }
401 #endif // GRAPHICS_DISABLED
402 
403 // Factory to build a TWERD from a (C_BLOB) WERD, with polygonal
404 // approximation along the way.
406  TWERD* tessword = new TWERD;
407  tessword->latin_script = src->flag(W_SCRIPT_IS_LATIN);
408  C_BLOB_IT b_it(src->cblob_list());
409  TBLOB *tail = NULL;
410  for (b_it.mark_cycle_pt(); !b_it.cycled_list(); b_it.forward()) {
411  C_BLOB* blob = b_it.data();
412  TBLOB* tblob = TBLOB::PolygonalCopy(blob);
413  if (tail == NULL) {
414  tessword->blobs = tblob;
415  } else {
416  tail->next = tblob;
417  }
418  tail = tblob;
419  }
420  return tessword;
421 }
422 
423 // Normalize in-place and record the normalization in the DENORM.
424 void TWERD::SetupBLNormalize(const BLOCK* block, const ROW* row,
425  float x_height, bool numeric_mode,
426  DENORM* denorm) const {
427  int num_segments = 0;
428  DENORM_SEG* segs = NULL;
429  if (numeric_mode) {
430  segs = new DENORM_SEG[NumBlobs()];
431  for (TBLOB* blob = blobs; blob != NULL; blob = blob->next) {
432  TBOX blob_box = blob->bounding_box();
433  float factor = kBlnXHeight / x_height;
434  factor = ClipToRange(kBlnXHeight * 4.0f / (3 * blob_box.height()),
435  factor, factor * 1.5f);
436  segs[num_segments].xstart = blob_box.left();
437  segs[num_segments].ycoord = blob_box.bottom();
438  segs[num_segments++].scale_factor = factor;
439  }
440  }
441  denorm->SetupBLNormalize(block, row, x_height, bounding_box(),
442  num_segments, segs);
443  delete [] segs;
444 }
445 
446 // Normalize in-place using the DENORM.
447 void TWERD::Normalize(const DENORM& denorm) {
448  for (TBLOB* blob = blobs; blob != NULL; blob = blob->next) {
449  blob->Normalize(denorm);
450  }
451 }
452 
453 // Copies the data and the blobs, but leaves next untouched.
454 void TWERD::CopyFrom(const TWERD& src) {
455  Clear();
457  TBLOB* prev_blob = NULL;
458  for (TBLOB* srcblob = src.blobs; srcblob != NULL; srcblob = srcblob->next) {
459  TBLOB* new_blob = new TBLOB(*srcblob);
460  if (blobs == NULL)
461  blobs = new_blob;
462  else
463  prev_blob->next = new_blob;
464  prev_blob = new_blob;
465  }
466 }
467 
468 // Deletes owned data.
469 void TWERD::Clear() {
470  for (TBLOB* next_blob = NULL; blobs != NULL; blobs = next_blob) {
471  next_blob = blobs->next;
472  delete blobs;
473  }
474 }
475 
476 // Recomputes the bounding boxes of the blobs.
478  for (TBLOB* blob = blobs; blob != NULL; blob = blob->next) {
479  blob->ComputeBoundingBoxes();
480  }
481 }
482 
484  TBOX result;
485  for (TBLOB* blob = blobs; blob != NULL; blob = blob->next) {
486  TBOX box = blob->bounding_box();
487  result += box;
488  }
489  return result;
490 }
491 
492 // Merges the blobs from start to end, not including end, and deletes
493 // the blobs between start and end.
494 void TWERD::MergeBlobs(int start, int end) {
495  TBLOB* blob = blobs;
496  for (int i = 0; i < start && blob != NULL; ++i)
497  blob = blob->next;
498  if (blob == NULL || blob->next == NULL)
499  return;
500  TBLOB* next_blob = blob->next;
501  TESSLINE* outline = blob->outlines;
502  for (int i = start + 1; i < end && next_blob != NULL; ++i) {
503  // Take the outlines from the next blob.
504  if (outline == NULL) {
505  blob->outlines = next_blob->outlines;
506  outline = blob->outlines;
507  } else {
508  while (outline->next != NULL)
509  outline = outline->next;
510  outline->next = next_blob->outlines;
511  next_blob->outlines = NULL;
512  }
513  // Delete the next blob and move on.
514  TBLOB* dead_blob = next_blob;
515  next_blob = next_blob->next;
516  blob->next = next_blob;
517  delete dead_blob;
518  }
519 }
520 
521 #ifndef GRAPHICS_DISABLED
522 void TWERD::plot(ScrollView* window) {
524  for (TBLOB* blob = blobs; blob != NULL; blob = blob->next) {
525  blob->plot(window, color, ScrollView::BROWN);
526  color = WERD::NextColor(color);
527  }
528 }
529 #endif // GRAPHICS_DISABLED
530 
531 /**********************************************************************
532  * blob_origin
533  *
534  * Compute the origin of a compound blob, define to be the centre
535  * of the bounding box.
536  **********************************************************************/
537 void blob_origin(TBLOB *blob, /*blob to compute on */
538  TPOINT *origin) { /*return value */
539  TBOX bbox = blob->bounding_box();
540  *origin = (bbox.topleft() + bbox.botright()) / 2;
541 }
542 
543 /**********************************************************************
544  * blobs_widths
545  *
546  * Compute the widths of a list of blobs. Return an array of the widths
547  * and gaps.
548  **********************************************************************/
549 WIDTH_RECORD *blobs_widths(TBLOB *blobs) { /*blob to compute on */
550  WIDTH_RECORD *width_record;
551  TPOINT topleft; /*bounding box */
552  TPOINT botright;
553  int i = 0;
554  int blob_end;
555  int num_blobs = count_blobs (blobs);
556 
557  /* Get memory */
558  width_record = (WIDTH_RECORD *) memalloc (sizeof (int) * num_blobs * 2);
559  width_record->num_chars = num_blobs;
560 
561  TBOX bbox = blobs->bounding_box();
562  width_record->widths[i++] = bbox.width();
563  /* First width */
564  blob_end = bbox.right();
565 
566  for (TBLOB* blob = blobs->next; blob != NULL; blob = blob->next) {
567  TBOX curbox = blob->bounding_box();
568  width_record->widths[i++] = curbox.left() - blob_end;
569  width_record->widths[i++] = curbox.width();
570  blob_end = curbox.right();
571  }
572  return width_record;
573 }
574 
575 
576 /**********************************************************************
577  * count_blobs
578  *
579  * Return a count of the number of blobs attached to this one.
580  **********************************************************************/
581 int count_blobs(TBLOB *blobs) {
582  int x = 0;
583 
584  for (TBLOB* b = blobs; b != NULL; b = b->next)
585  x++;
586  return x;
587 }
588 
589 /**********************************************************************
590  * divisible_blob
591  *
592  * Returns true if the blob contains multiple outlines than can be
593  * separated using divide_blobs. Sets the location to be used in the
594  * call to divide_blobs.
595  **********************************************************************/
596 bool divisible_blob(TBLOB *blob, bool italic_blob, TPOINT* location) {
597  if (blob->outlines == NULL || blob->outlines->next == NULL)
598  return false; // Need at least 2 outlines for it to be possible.
599  int max_gap = 0;
600  TPOINT vertical = italic_blob ? kDivisibleVerticalItalic
602  for (TESSLINE* outline1 = blob->outlines; outline1 != NULL;
603  outline1 = outline1->next) {
604  if (outline1->is_hole)
605  continue; // Holes do not count as separable.
606  TPOINT mid_pt1(
607  static_cast<inT16>((outline1->topleft.x + outline1->botright.x) / 2),
608  static_cast<inT16>((outline1->topleft.y + outline1->botright.y) / 2));
609  int mid_prod1 = CROSS(mid_pt1, vertical);
610  int min_prod1, max_prod1;
611  outline1->MinMaxCrossProduct(vertical, &min_prod1, &max_prod1);
612  for (TESSLINE* outline2 = outline1->next; outline2 != NULL;
613  outline2 = outline2->next) {
614  if (outline2->is_hole)
615  continue; // Holes do not count as separable.
616  TPOINT mid_pt2(
617  static_cast<inT16>((outline2->topleft.x + outline2->botright.x) / 2),
618  static_cast<inT16>((outline2->topleft.y + outline2->botright.y) / 2));
619  int mid_prod2 = CROSS(mid_pt2, vertical);
620  int min_prod2, max_prod2;
621  outline2->MinMaxCrossProduct(vertical, &min_prod2, &max_prod2);
622  int mid_gap = abs(mid_prod2 - mid_prod1);
623  int overlap = MIN(max_prod1, max_prod2) - MAX(min_prod1, min_prod2);
624  if (mid_gap - overlap / 4 > max_gap) {
625  max_gap = mid_gap - overlap / 4;
626  *location = mid_pt1;
627  *location += mid_pt2;
628  *location /= 2;
629  }
630  }
631  }
632  // Use the y component of the vertical vector as an approximation to its
633  // length.
634  return max_gap > vertical.y;
635 }
636 
637 /**********************************************************************
638  * divide_blobs
639  *
640  * Create two blobs by grouping the outlines in the appropriate blob.
641  * The outlines that are beyond the location point are moved to the
642  * other blob. The ones whose x location is less than that point are
643  * retained in the original blob.
644  **********************************************************************/
645 void divide_blobs(TBLOB *blob, TBLOB *other_blob, bool italic_blob,
646  const TPOINT& location) {
647  TPOINT vertical = italic_blob ? kDivisibleVerticalItalic
649  TESSLINE *outline1 = NULL;
650  TESSLINE *outline2 = NULL;
651 
652  TESSLINE *outline = blob->outlines;
653  blob->outlines = NULL;
654  int location_prod = CROSS(location, vertical);
655 
656  while (outline != NULL) {
657  TPOINT mid_pt(
658  static_cast<inT16>((outline->topleft.x + outline->botright.x) / 2),
659  static_cast<inT16>((outline->topleft.y + outline->botright.y) / 2));
660  int mid_prod = CROSS(mid_pt, vertical);
661  if (mid_prod < location_prod) {
662  // Outline is in left blob.
663  if (outline1)
664  outline1->next = outline;
665  else
666  blob->outlines = outline;
667  outline1 = outline;
668  } else {
669  // Outline is in right blob.
670  if (outline2)
671  outline2->next = outline;
672  else
673  other_blob->outlines = outline;
674  outline2 = outline;
675  }
676  outline = outline->next;
677  }
678 
679  if (outline1)
680  outline1->next = NULL;
681  if (outline2)
682  outline2->next = NULL;
683 }