Tesseract  3.02
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
tabfind.cpp
Go to the documentation of this file.
1 
2 // File: TabFind.cpp
3 // Description: Subclass of BBGrid to find vertically aligned blobs.
4 // Author: Ray Smith
5 // Created: Fri Mar 21 15:03:01 PST 2008
6 //
7 // (C) Copyright 2008, Google Inc.
8 // Licensed under the Apache License, Version 2.0 (the "License");
9 // you may not use this file except in compliance with the License.
10 // You may obtain a copy of the License at
11 // http://www.apache.org/licenses/LICENSE-2.0
12 // Unless required by applicable law or agreed to in writing, software
13 // distributed under the License is distributed on an "AS IS" BASIS,
14 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 // See the License for the specific language governing permissions and
16 // limitations under the License.
17 //
19 
20 #include "tabfind.h"
21 #include "alignedblob.h"
22 #include "blobbox.h"
23 #include "colpartitiongrid.h"
24 #include "detlinefit.h"
25 #include "linefind.h"
26 #include "ndminx.h"
27 
28 // Include automatically generated configuration file if running autoconf.
29 #ifdef HAVE_CONFIG_H
30 #include "config_auto.h"
31 #endif
32 
33 namespace tesseract {
34 
35 // Multiple of box size to search for initial gaps.
36 const int kTabRadiusFactor = 5;
37 // Min and Max multiple of height to search vertically when extrapolating.
38 const int kMinVerticalSearch = 3;
39 const int kMaxVerticalSearch = 12;
40 const int kMaxRaggedSearch = 25;
41 // Minimum number of lines in a column width to make it interesting.
42 const int kMinLinesInColumn = 10;
43 // Minimum width of a column to be interesting.
44 const int kMinColumnWidth = 200;
45 // Minimum fraction of total column lines for a column to be interesting.
46 const double kMinFractionalLinesInColumn = 0.125;
47 // Fraction of height used as alignment tolerance for aligned tabs.
48 const double kAlignedFraction = 0.03125;
49 // Minimum gutter width in absolute inch (multiplied by resolution)
50 const double kMinGutterWidthAbsolute = 0.02;
51 // Maximum gutter width (in absolute inch) that we care about
52 const double kMaxGutterWidthAbsolute = 2.00;
53 // Multiplier of gridsize for min gutter width of TT_MAYBE_RAGGED blobs.
54 const int kRaggedGutterMultiple = 5;
55 // Min aspect ratio of tall objects to be considered a separator line.
56 // (These will be ignored in searching the gutter for obstructions.)
57 const double kLineFragmentAspectRatio = 10.0;
58 // Multiplier of new y positions in running average for skew estimation.
59 const double kSmoothFactor = 0.25;
60 // Min coverage for a good baseline between vectors
61 const double kMinBaselineCoverage = 0.5;
62 // Minimum overlap fraction when scanning text lines for column widths.
63 const double kCharVerticalOverlapFraction = 0.375;
64 // Maximum horizontal gap allowed when scanning for column widths
65 const double kMaxHorizontalGap = 3.0;
66 // Maximum upper quartile error allowed on a baseline fit as a fraction
67 // of height.
68 const double kMaxBaselineError = 0.4375;
69 // Min number of points to accept after evaluation.
70 const int kMinEvaluatedTabs = 3;
71 // Minimum aspect ratio of a textline to make a good textline blob with a
72 // single blob.
73 const int kMaxTextLineBlobRatio = 5;
74 // Minimum aspect ratio of a textline to make a good textline blob with
75 // multiple blobs. Target ratio varies according to number of blobs.
76 const int kMinTextLineBlobRatio = 3;
77 // Fraction of box area covered by image to make a blob image.
78 const double kMinImageArea = 0.5;
79 // Upto 30 degrees is allowed for rotations of diacritic blobs.
80 // Keep this value slightly larger than kCosSmallAngle in blobbox.cpp
81 // so that the assert there never fails.
82 const double kCosMaxSkewAngle = 0.866025;
83 
84 BOOL_VAR(textord_tabfind_show_initialtabs, false, "Show tab candidates");
85 BOOL_VAR(textord_tabfind_show_finaltabs, false, "Show tab vectors");
87  "Fraction of height used as a minimum gap for aligned blobs.");
88 
89 TabFind::TabFind(int gridsize, const ICOORD& bleft, const ICOORD& tright,
90  TabVector_LIST* vlines, int vertical_x, int vertical_y,
91  int resolution)
92  : AlignedBlob(gridsize, bleft, tright),
93  resolution_(resolution),
94  image_origin_(0, tright.y() - 1) {
95  width_cb_ = NULL;
96  v_it_.set_to_list(&vectors_);
97  v_it_.add_list_after(vlines);
98  SetVerticalSkewAndParellelize(vertical_x, vertical_y);
100 }
101 
103  if (width_cb_ != NULL)
104  delete width_cb_;
105 }
106 
108 
109 // Insert a list of blobs into the given grid (not necessarily this).
110 // If take_ownership is true, then the blobs are removed from the source list.
111 // See InsertBlob for the other arguments.
112 // It would seem to make more sense to swap this and grid, but this way
113 // around allows grid to not be derived from TabFind, eg a ColPartitionGrid,
114 // while the grid that provides the tab stops(this) has to be derived from
115 // TabFind.
116 void TabFind::InsertBlobsToGrid(bool h_spread, bool v_spread,
117  BLOBNBOX_LIST* blobs,
118  BBGrid<BLOBNBOX, BLOBNBOX_CLIST,
119  BLOBNBOX_C_IT>* grid) {
120  BLOBNBOX_IT blob_it(blobs);
121  int b_count = 0;
122  int reject_count = 0;
123  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
124  BLOBNBOX* blob = blob_it.data();
125 // if (InsertBlob(true, true, blob, grid)) {
126  if (InsertBlob(h_spread, v_spread, blob, grid)) {
127  ++b_count;
128  } else {
129  ++reject_count;
130  }
131  }
132  if (textord_debug_tabfind) {
133  tprintf("Inserted %d blobs into grid, %d rejected.\n",
134  b_count, reject_count);
135  }
136 }
137 
138 // Insert a single blob into the given grid (not necessarily this).
139 // If h_spread, then all cells covered horizontally by the box are
140 // used, otherwise, just the bottom-left. Similarly for v_spread.
141 // A side effect is that the left and right rule edges of the blob are
142 // set according to the tab vectors in this (not grid).
143 bool TabFind::InsertBlob(bool h_spread, bool v_spread, BLOBNBOX* blob,
144  BBGrid<BLOBNBOX, BLOBNBOX_CLIST,
145  BLOBNBOX_C_IT>* grid) {
146  TBOX box = blob->bounding_box();
147  blob->set_left_rule(LeftEdgeForBox(box, false, false));
148  blob->set_right_rule(RightEdgeForBox(box, false, false));
149  blob->set_left_crossing_rule(LeftEdgeForBox(box, true, false));
150  blob->set_right_crossing_rule(RightEdgeForBox(box, true, false));
151  if (blob->joined_to_prev())
152  return false;
153  grid->InsertBBox(h_spread, v_spread, blob);
154  return true;
155 }
156 
157 // Calls SetBlobRuleEdges for all the blobs in the given block.
159  SetBlobRuleEdges(&block->blobs);
160  SetBlobRuleEdges(&block->small_blobs);
161  SetBlobRuleEdges(&block->noise_blobs);
162  SetBlobRuleEdges(&block->large_blobs);
163 }
164 
165 // Sets the left and right rule and crossing_rules for the blobs in the given
166 // list by fiding the next outermost tabvectors for each blob.
167 void TabFind::SetBlobRuleEdges(BLOBNBOX_LIST* blobs) {
168  BLOBNBOX_IT blob_it(blobs);
169  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
170  BLOBNBOX* blob = blob_it.data();
171  TBOX box = blob->bounding_box();
172  blob->set_left_rule(LeftEdgeForBox(box, false, false));
173  blob->set_right_rule(RightEdgeForBox(box, false, false));
174  blob->set_left_crossing_rule(LeftEdgeForBox(box, true, false));
175  blob->set_right_crossing_rule(RightEdgeForBox(box, true, false));
176  }
177 }
178 
179 // Returns the gutter width of the given TabVector between the given y limits.
180 // Also returns x-shift to be added to the vector to clear any intersecting
181 // blobs. The shift is deducted from the returned gutter.
182 // If ignore_unmergeables is true, then blobs of UnMergeableType are
183 // ignored as if they don't exist. (Used for text on image.)
184 // max_gutter_width is used as the maximum width worth searching for in case
185 // there is nothing near the TabVector.
186 int TabFind::GutterWidth(int bottom_y, int top_y, const TabVector& v,
187  bool ignore_unmergeables, int max_gutter_width,
188  int* required_shift) {
189  bool right_to_left = v.IsLeftTab();
190  int bottom_x = v.XAtY(bottom_y);
191  int top_x = v.XAtY(top_y);
192  int start_x = right_to_left ? MAX(top_x, bottom_x) : MIN(top_x, bottom_x);
193  BlobGridSearch sidesearch(this);
194  sidesearch.StartSideSearch(start_x, bottom_y, top_y);
195  int min_gap = max_gutter_width;
196  *required_shift = 0;
197  BLOBNBOX* blob = NULL;
198  while ((blob = sidesearch.NextSideSearch(right_to_left)) != NULL) {
199  const TBOX& box = blob->bounding_box();
200  if (box.bottom() >= top_y || box.top() <= bottom_y)
201  continue; // Doesn't overlap enough.
202  if (box.height() >= gridsize() * 2 &&
203  box.height() > box.width() * kLineFragmentAspectRatio) {
204  // Skip likely separator line residue.
205  continue;
206  }
207  if (ignore_unmergeables && BLOBNBOX::UnMergeableType(blob->region_type()))
208  continue; // Skip non-text if required.
209  int mid_y = (box.bottom() + box.top()) / 2;
210  // We use the x at the mid-y so that the required_shift guarantees
211  // to clear all the blobs on the tab-stop. If we use the min/max
212  // of x at top/bottom of the blob, then exactness would be required,
213  // which is not a good thing.
214  int tab_x = v.XAtY(mid_y);
215  int gap;
216  if (right_to_left) {
217  gap = tab_x - box.right();
218  if (gap < 0 && box.left() - tab_x < *required_shift)
219  *required_shift = box.left() - tab_x;
220  } else {
221  gap = box.left() - tab_x;
222  if (gap < 0 && box.right() - tab_x > *required_shift)
223  *required_shift = box.right() - tab_x;
224  }
225  if (gap > 0 && gap < min_gap)
226  min_gap = gap;
227  }
228  // Result may be negative, in which case, this is a really bad tabstop.
229  return min_gap - abs(*required_shift);
230 }
231 
232 // Find the gutter width and distance to inner neighbour for the given blob.
233 void TabFind::GutterWidthAndNeighbourGap(int tab_x, int mean_height,
234  int max_gutter, bool left,
235  BLOBNBOX* bbox, int* gutter_width,
236  int* neighbour_gap ) {
237  const TBOX& box = bbox->bounding_box();
238  // The gutter and internal sides of the box.
239  int gutter_x = left ? box.left() : box.right();
240  int internal_x = left ? box.right() : box.left();
241  // On ragged edges, the gutter side of the box is away from the tabstop.
242  int tab_gap = left ? gutter_x - tab_x : tab_x - gutter_x;
243  *gutter_width = max_gutter;
244  // If the box is away from the tabstop, we need to increase
245  // the allowed gutter width.
246  if (tab_gap > 0)
247  *gutter_width += tab_gap;
248  bool debug = WithinTestRegion(2, box.left(), box.bottom());
249  if (debug)
250  tprintf("Looking in gutter\n");
251  // Find the nearest blob on the outside of the column.
252  BLOBNBOX* gutter_bbox = AdjacentBlob(bbox, left,
253  bbox->flow() == BTFT_TEXT_ON_IMAGE, 0.0,
254  *gutter_width, box.top(), box.bottom());
255  if (gutter_bbox != NULL) {
256  TBOX gutter_box = gutter_bbox->bounding_box();
257  *gutter_width = left ? tab_x - gutter_box.right()
258  : gutter_box.left() - tab_x;
259  }
260  if (*gutter_width >= max_gutter) {
261  // If there is no box because a tab was in the way, get the tab coord.
262  TBOX gutter_box(box);
263  if (left) {
264  gutter_box.set_left(tab_x - max_gutter - 1);
265  gutter_box.set_right(tab_x - max_gutter);
266  int tab_gutter = RightEdgeForBox(gutter_box, true, false);
267  if (tab_gutter < tab_x - 1)
268  *gutter_width = tab_x - tab_gutter;
269  } else {
270  gutter_box.set_left(tab_x + max_gutter);
271  gutter_box.set_right(tab_x + max_gutter + 1);
272  int tab_gutter = LeftEdgeForBox(gutter_box, true, false);
273  if (tab_gutter > tab_x + 1)
274  *gutter_width = tab_gutter - tab_x;
275  }
276  }
277  if (*gutter_width > max_gutter)
278  *gutter_width = max_gutter;
279  // Now look for a neighbour on the inside.
280  if (debug)
281  tprintf("Looking for neighbour\n");
282  BLOBNBOX* neighbour = AdjacentBlob(bbox, !left,
283  bbox->flow() == BTFT_TEXT_ON_IMAGE, 0.0,
284  *gutter_width, box.top(), box.bottom());
285  int neighbour_edge = left ? RightEdgeForBox(box, true, false)
286  : LeftEdgeForBox(box, true, false);
287  if (neighbour != NULL) {
288  TBOX n_box = neighbour->bounding_box();
289  if (debug) {
290  tprintf("Found neighbour:");
291  n_box.print();
292  }
293  if (left && n_box.left() < neighbour_edge)
294  neighbour_edge = n_box.left();
295  else if (!left && n_box.right() > neighbour_edge)
296  neighbour_edge = n_box.right();
297  }
298  *neighbour_gap = left ? neighbour_edge - internal_x
299  : internal_x - neighbour_edge;
300 }
301 
302 // Return the x-coord that corresponds to the right edge for the given
303 // box. If there is a rule line to the right that vertically overlaps it,
304 // then return the x-coord of the rule line, otherwise return the right
305 // edge of the page. For details see RightTabForBox below.
306 int TabFind::RightEdgeForBox(const TBOX& box, bool crossing, bool extended) {
307  TabVector* v = RightTabForBox(box, crossing, extended);
308  return v == NULL ? tright_.x() : v->XAtY((box.top() + box.bottom()) / 2);
309 }
310 // As RightEdgeForBox, but finds the left Edge instead.
311 int TabFind::LeftEdgeForBox(const TBOX& box, bool crossing, bool extended) {
312  TabVector* v = LeftTabForBox(box, crossing, extended);
313  return v == NULL ? bleft_.x() : v->XAtY((box.top() + box.bottom()) / 2);
314 }
315 
316 // This comment documents how this function works.
317 // For its purpose and arguments, see the comment in tabfind.h.
318 // TabVectors are stored sorted by perpendicular distance of middle from
319 // the global mean vertical vector. Since the individual vectors can have
320 // differing directions, their XAtY for a given y is not necessarily in the
321 // right order. Therefore the search has to be run with a margin.
322 // The middle of a vector that passes through (x,y) cannot be higher than
323 // halfway from y to the top, or lower than halfway from y to the bottom
324 // of the coordinate range; therefore, the search margin is the range of
325 // sort keys between these halfway points. Any vector with a sort key greater
326 // than the upper margin must be to the right of x at y, and likewise any
327 // vector with a sort key less than the lower margin must pass to the left
328 // of x at y.
329 TabVector* TabFind::RightTabForBox(const TBOX& box, bool crossing,
330  bool extended) {
331  if (v_it_.empty())
332  return NULL;
333  int top_y = box.top();
334  int bottom_y = box.bottom();
335  int mid_y = (top_y + bottom_y) / 2;
336  int right = crossing ? (box.left() + box.right()) / 2 : box.right();
337  int min_key, max_key;
338  SetupTabSearch(right, mid_y, &min_key, &max_key);
339  // Position the iterator at the first TabVector with sort_key >= min_key.
340  while (!v_it_.at_first() && v_it_.data()->sort_key() >= min_key)
341  v_it_.backward();
342  while (!v_it_.at_last() && v_it_.data()->sort_key() < min_key)
343  v_it_.forward();
344  // Find the leftmost tab vector that overlaps and has XAtY(mid_y) >= right.
345  TabVector* best_v = NULL;
346  int best_x = -1;
347  int key_limit = -1;
348  do {
349  TabVector* v = v_it_.data();
350  int x = v->XAtY(mid_y);
351  if (x >= right &&
352  (v->VOverlap(top_y, bottom_y) > 0 ||
353  (extended && v->ExtendedOverlap(top_y, bottom_y) > 0))) {
354  if (best_v == NULL || x < best_x) {
355  best_v = v;
356  best_x = x;
357  // We can guarantee that no better vector can be found if the
358  // sort key exceeds that of the best by max_key - min_key.
359  key_limit = v->sort_key() + max_key - min_key;
360  }
361  }
362  // Break when the search is done to avoid wrapping the iterator and
363  // thereby potentially slowing the next search.
364  if (v_it_.at_last() ||
365  (best_v != NULL && v->sort_key() > key_limit))
366  break; // Prevent restarting list for next call.
367  v_it_.forward();
368  } while (!v_it_.at_first());
369  return best_v;
370 }
371 
372 // As RightTabForBox, but finds the left TabVector instead.
373 TabVector* TabFind::LeftTabForBox(const TBOX& box, bool crossing,
374  bool extended) {
375  if (v_it_.empty())
376  return NULL;
377  int top_y = box.top();
378  int bottom_y = box.bottom();
379  int mid_y = (top_y + bottom_y) / 2;
380  int left = crossing ? (box.left() + box.right()) / 2 : box.left();
381  int min_key, max_key;
382  SetupTabSearch(left, mid_y, &min_key, &max_key);
383  // Position the iterator at the last TabVector with sort_key <= max_key.
384  while (!v_it_.at_last() && v_it_.data()->sort_key() <= max_key)
385  v_it_.forward();
386  while (!v_it_.at_first() && v_it_.data()->sort_key() > max_key) {
387  v_it_.backward();
388  }
389  // Find the rightmost tab vector that overlaps and has XAtY(mid_y) <= left.
390  TabVector* best_v = NULL;
391  int best_x = -1;
392  int key_limit = -1;
393  do {
394  TabVector* v = v_it_.data();
395  int x = v->XAtY(mid_y);
396  if (x <= left &&
397  (v->VOverlap(top_y, bottom_y) > 0 ||
398  (extended && v->ExtendedOverlap(top_y, bottom_y) > 0))) {
399  if (best_v == NULL || x > best_x) {
400  best_v = v;
401  best_x = x;
402  // We can guarantee that no better vector can be found if the
403  // sort key is less than that of the best by max_key - min_key.
404  key_limit = v->sort_key() - (max_key - min_key);
405  }
406  }
407  // Break when the search is done to avoid wrapping the iterator and
408  // thereby potentially slowing the next search.
409  if (v_it_.at_first() ||
410  (best_v != NULL && v->sort_key() < key_limit))
411  break; // Prevent restarting list for next call.
412  v_it_.backward();
413  } while (!v_it_.at_last());
414  return best_v;
415 }
416 
417 // Return true if the given width is close to one of the common
418 // widths in column_widths_.
419 bool TabFind::CommonWidth(int width) {
420  width /= kColumnWidthFactor;
421  ICOORDELT_IT it(&column_widths_);
422  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
423  ICOORDELT* w = it.data();
424  if (NearlyEqual<int>(width, w->x(), 1))
425  return true;
426  }
427  return false;
428 }
429 
430 // Return true if the sizes are more than a
431 // factor of 2 different.
432 bool TabFind::DifferentSizes(int size1, int size2) {
433  return size1 > size2 * 2 || size2 > size1 * 2;
434 }
435 
436 // Return true if the sizes are more than a
437 // factor of 5 different.
438 bool TabFind::VeryDifferentSizes(int size1, int size2) {
439  return size1 > size2 * 5 || size2 > size1 * 5;
440 }
441 
443 
444 // Top-level function to find TabVectors in an input page block.
445 // Returns false if the detected skew angle is impossible.
446 // Applies the detected skew angle to deskew the tabs, blobs and part_grid.
447 bool TabFind::FindTabVectors(TabVector_LIST* hlines,
448  BLOBNBOX_LIST* image_blobs, TO_BLOCK* block,
449  int min_gutter_width,
450  ColPartitionGrid* part_grid,
451  FCOORD* deskew, FCOORD* reskew) {
452  ScrollView* tab_win = FindInitialTabVectors(image_blobs, min_gutter_width,
453  block);
454  ComputeColumnWidths(tab_win, part_grid);
456  SortVectors();
457  CleanupTabs();
458  if (!Deskew(hlines, image_blobs, block, deskew, reskew))
459  return false; // Skew angle is too large.
460  part_grid->Deskew(*deskew);
461  ApplyTabConstraints();
462  #ifndef GRAPHICS_DISABLED
464  tab_win = MakeWindow(640, 50, "FinalTabs");
465  if (textord_debug_images) {
466  tab_win->Image(AlignedBlob::textord_debug_pix().string(),
467  image_origin_.x(), image_origin_.y());
468  } else {
469  DisplayBoxes(tab_win);
470  DisplayTabs("FinalTabs", tab_win);
471  }
472  tab_win = DisplayTabVectors(tab_win);
473  }
474  #endif // GRAPHICS_DISABLED
475  return true;
476 }
477 
478 // Top-level function to not find TabVectors in an input page block,
479 // but setup for single column mode.
480 void TabFind::DontFindTabVectors(BLOBNBOX_LIST* image_blobs, TO_BLOCK* block,
481  FCOORD* deskew, FCOORD* reskew) {
482  InsertBlobsToGrid(false, false, image_blobs, this);
483  InsertBlobsToGrid(true, false, &block->blobs, this);
484  deskew->set_x(1.0f);
485  deskew->set_y(0.0f);
486  reskew->set_x(1.0f);
487  reskew->set_y(0.0f);
488 }
489 
490 // Cleans up the lists of blobs in the block ready for use by TabFind.
491 // Large blobs that look like text are moved to the main blobs list.
492 // Main blobs that are superseded by the image blobs are deleted.
494  BLOBNBOX_IT large_it = &block->large_blobs;
495  BLOBNBOX_IT blob_it = &block->blobs;
496  int b_count = 0;
497  for (large_it.mark_cycle_pt(); !large_it.cycled_list(); large_it.forward()) {
498  BLOBNBOX* large_blob = large_it.data();
499  if (large_blob->owner() != NULL) {
500  blob_it.add_to_end(large_it.extract());
501  ++b_count;
502  }
503  }
504  if (textord_debug_tabfind) {
505  tprintf("Moved %d large blobs to normal list\n",
506  b_count);
507  #ifndef GRAPHICS_DISABLED
508  ScrollView* rej_win = MakeWindow(500, 300, "Image blobs");
509  block->plot_graded_blobs(rej_win);
510  block->plot_noise_blobs(rej_win);
511  rej_win->Update();
512  #endif // GRAPHICS_DISABLED
513  }
514  block->DeleteUnownedNoise();
515 }
516 
517 // Helper function to setup search limits for *TabForBox.
518 void TabFind::SetupTabSearch(int x, int y, int* min_key, int* max_key) {
519  int key1 = TabVector::SortKey(vertical_skew_, x, (y + tright_.y()) / 2);
520  int key2 = TabVector::SortKey(vertical_skew_, x, (y + bleft_.y()) / 2);
521  *min_key = MIN(key1, key2);
522  *max_key = MAX(key1, key2);
523 }
524 
526 #ifndef GRAPHICS_DISABLED
527  // For every vector, display it.
528  TabVector_IT it(&vectors_);
529  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
530  TabVector* vector = it.data();
531  vector->Display(tab_win);
532  }
533  tab_win->Update();
534 #endif
535  return tab_win;
536 }
537 
538 // PRIVATE CODE.
539 //
540 // First part of FindTabVectors, which may be used twice if the text
541 // is mostly of vertical alignment.
542 ScrollView* TabFind::FindInitialTabVectors(BLOBNBOX_LIST* image_blobs,
543  int min_gutter_width,
544  TO_BLOCK* block) {
546  ScrollView* line_win = MakeWindow(0, 0, "VerticalLines");
547  line_win = DisplayTabVectors(line_win);
548  }
549  // Prepare the grid.
550  if (image_blobs != NULL)
551  InsertBlobsToGrid(true, false, image_blobs, this);
552  InsertBlobsToGrid(true, false, &block->blobs, this);
553  ScrollView* initial_win = FindTabBoxes(min_gutter_width);
554  FindAllTabVectors(min_gutter_width);
555 
557  SortVectors();
558  EvaluateTabs();
559  if (textord_tabfind_show_initialtabs && initial_win != NULL)
560  initial_win = DisplayTabVectors(initial_win);
561  MarkVerticalText();
562  return initial_win;
563 }
564 
565 // Helper displays all the boxes in the given vector on the given window.
566 static void DisplayBoxVector(const GenericVector<BLOBNBOX*> boxes,
567  ScrollView* win) {
568  #ifndef GRAPHICS_DISABLED
569  for (int i = 0; i < boxes.size(); ++i) {
570  TBOX box = boxes[i]->bounding_box();
571  int left_x = box.left();
572  int right_x = box.right();
573  int top_y = box.top();
574  int bottom_y = box.bottom();
575  ScrollView::Color box_color = boxes[i]->BoxColor();
576  win->Pen(box_color);
577  win->Rectangle(left_x, bottom_y, right_x, top_y);
578  }
579  win->Update();
580  #endif // GRAPHICS_DISABLED
581 }
582 
583 // For each box in the grid, decide whether it is a candidate tab-stop,
584 // and if so add it to the left/right tab boxes.
585 ScrollView* TabFind::FindTabBoxes(int min_gutter_width) {
586  left_tab_boxes_.clear();
587  right_tab_boxes_.clear();
588  // For every bbox in the grid, determine whether it uses a tab on an edge.
589  GridSearch<BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT> gsearch(this);
590  gsearch.StartFullSearch();
591  BLOBNBOX* bbox;
592  while ((bbox = gsearch.NextFullSearch()) != NULL) {
593  if (TestBoxForTabs(bbox, min_gutter_width)) {
594  // If it is any kind of tab, insert it into the vectors.
595  if (bbox->left_tab_type() != TT_NONE)
596  left_tab_boxes_.push_back(bbox);
597  if (bbox->right_tab_type() != TT_NONE)
598  right_tab_boxes_.push_back(bbox);
599  }
600  }
601  // Sort left tabs by left and right by right to see the outermost one first
602  // on a ragged tab.
603  left_tab_boxes_.sort(SortByBoxLeft<BLOBNBOX>);
604  right_tab_boxes_.sort(SortRightToLeft<BLOBNBOX>);
605  ScrollView* tab_win = NULL;
606  #ifndef GRAPHICS_DISABLED
608  tab_win = MakeWindow(0, 100, "InitialTabs");
609  tab_win->Pen(ScrollView::BLUE);
610  tab_win->Brush(ScrollView::NONE);
611  // Display the left and right tab boxes.
612  DisplayBoxVector(left_tab_boxes_, tab_win);
613  DisplayBoxVector(right_tab_boxes_, tab_win);
614  tab_win = DisplayTabs("Tabs", tab_win);
615  }
616  #endif // GRAPHICS_DISABLED
617  return tab_win;
618 }
619 
620 bool TabFind::TestBoxForTabs(BLOBNBOX* bbox, int min_gutter_width) {
621  GridSearch<BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT> radsearch(this);
622  TBOX box = bbox->bounding_box();
623  // If there are separator lines, get the column edges.
624  int left_column_edge = bbox->left_rule();
625  int right_column_edge = bbox->right_rule();
626  // The edges of the bounding box of the blob being processed.
627  int left_x = box.left();
628  int right_x = box.right();
629  int top_y = box.top();
630  int bottom_y = box.bottom();
631  int height = box.height();
632  bool debug = WithinTestRegion(3, left_x, top_y);
633  if (debug) {
634  tprintf("Column edges for blob at (%d,%d)->(%d,%d) are [%d, %d]\n",
635  left_x, top_y, right_x, bottom_y,
636  left_column_edge, right_column_edge);
637  }
638  // Compute a search radius based on a multiple of the height.
639  int radius = (height * kTabRadiusFactor + gridsize_ - 1) / gridsize_;
640  radsearch.StartRadSearch((left_x + right_x)/2, (top_y + bottom_y)/2, radius);
641  // In Vertical Page mode, once we have an estimate of the vertical line
642  // spacing, the minimum amount of gutter space before a possible tab is
643  // increased under the assumption that column partition is always larger
644  // than line spacing.
645  int min_spacing =
646  static_cast<int>(height * textord_tabfind_aligned_gap_fraction);
647  if (min_gutter_width > min_spacing)
648  min_spacing = min_gutter_width;
649  int min_ragged_gutter = kRaggedGutterMultiple * gridsize();
650  if (min_gutter_width > min_ragged_gutter)
651  min_ragged_gutter = min_gutter_width;
652  int target_right = left_x - min_spacing;
653  int target_left = right_x + min_spacing;
654  // We will be evaluating whether the left edge could be a left tab, and
655  // whether the right edge could be a right tab.
656  // A box can be a tab if its bool is_(left/right)_tab remains true, meaning
657  // that no blobs have been found in the gutter during the radial search.
658  // A box can also be a tab if there are objects in the gutter only above
659  // or only below, and there are aligned objects on the opposite side, but
660  // not too many unaligned objects. The maybe_(left/right)_tab_up counts
661  // aligned objects above and negatively counts unaligned objects above,
662  // and is set to -MAX_INT32 if a gutter object is found above.
663  // The other 3 maybe ints work similarly for the other sides.
664  // These conditions are very strict, to minimize false positives, and really
665  // only aligned tabs and outermost ragged tab blobs will qualify, so we
666  // also have maybe_ragged_left/right with less stringent rules.
667  // A blob that is maybe_ragged_left/right will be further qualified later,
668  // using the min_ragged_gutter.
669  bool is_left_tab = true;
670  bool is_right_tab = true;
671  bool maybe_ragged_left = true;
672  bool maybe_ragged_right = true;
673  int maybe_left_tab_up = 0;
674  int maybe_right_tab_up = 0;
675  int maybe_left_tab_down = 0;
676  int maybe_right_tab_down = 0;
677  if (bbox->leader_on_left()) {
678  is_left_tab = false;
679  maybe_ragged_left = false;
680  maybe_left_tab_up = -MAX_INT32;
681  maybe_left_tab_down = -MAX_INT32;
682  }
683  if (bbox->leader_on_right()) {
684  is_right_tab = false;
685  maybe_ragged_right = false;
686  maybe_right_tab_up = -MAX_INT32;
687  maybe_right_tab_down = -MAX_INT32;
688  }
689  int alignment_tolerance = static_cast<int>(resolution_ * kAlignedFraction);
690  BLOBNBOX* neighbour = NULL;
691  while ((neighbour = radsearch.NextRadSearch()) != NULL) {
692  if (neighbour == bbox)
693  continue;
694  TBOX nbox = neighbour->bounding_box();
695  int n_left = nbox.left();
696  int n_right = nbox.right();
697  if (debug)
698  tprintf("Neighbour at (%d,%d)->(%d,%d)\n",
699  n_left, nbox.bottom(), n_right, nbox.top());
700  // If the neighbouring blob is the wrong side of a separator line, then it
701  // "doesn't exist" as far as we are concerned.
702  if (n_right > right_column_edge || n_left < left_column_edge ||
703  left_x < neighbour->left_rule() || right_x > neighbour->right_rule())
704  continue; // Separator line in the way.
705  int n_mid_x = (n_left + n_right) / 2;
706  int n_mid_y = (nbox.top() + nbox.bottom()) / 2;
707  if (n_mid_x <= left_x && n_right >= target_right) {
708  if (debug)
709  tprintf("Not a left tab\n");
710  is_left_tab = false;
711  if (n_mid_y < top_y)
712  maybe_left_tab_down = -MAX_INT32;
713  if (n_mid_y > bottom_y)
714  maybe_left_tab_up = -MAX_INT32;
715  } else if (NearlyEqual(left_x, n_left, alignment_tolerance)) {
716  if (debug)
717  tprintf("Maybe a left tab\n");
718  if (n_mid_y > top_y && maybe_left_tab_up > -MAX_INT32)
719  ++maybe_left_tab_up;
720  if (n_mid_y < bottom_y && maybe_left_tab_down > -MAX_INT32)
721  ++maybe_left_tab_down;
722  } else if (n_left < left_x && n_right >= left_x) {
723  // Overlaps but not aligned so negative points on a maybe.
724  if (debug)
725  tprintf("Maybe Not a left tab\n");
726  if (n_mid_y > top_y && maybe_left_tab_up > -MAX_INT32)
727  --maybe_left_tab_up;
728  if (n_mid_y < bottom_y && maybe_left_tab_down > -MAX_INT32)
729  --maybe_left_tab_down;
730  }
731  if (n_left < left_x && nbox.y_overlap(box) && n_right >= target_right) {
732  maybe_ragged_left = false;
733  if (debug)
734  tprintf("Not a ragged left\n");
735  }
736  if (n_mid_x >= right_x && n_left <= target_left) {
737  if (debug)
738  tprintf("Not a right tab\n");
739  is_right_tab = false;
740  if (n_mid_y < top_y)
741  maybe_right_tab_down = -MAX_INT32;
742  if (n_mid_y > bottom_y)
743  maybe_right_tab_up = -MAX_INT32;
744  } else if (NearlyEqual(right_x, n_right, alignment_tolerance)) {
745  if (debug)
746  tprintf("Maybe a right tab\n");
747  if (n_mid_y > top_y && maybe_right_tab_up > -MAX_INT32)
748  ++maybe_right_tab_up;
749  if (n_mid_y < bottom_y && maybe_right_tab_down > -MAX_INT32)
750  ++maybe_right_tab_down;
751  } else if (n_right > right_x && n_left <= right_x) {
752  // Overlaps but not aligned so negative points on a maybe.
753  if (debug)
754  tprintf("Maybe Not a right tab\n");
755  if (n_mid_y > top_y && maybe_right_tab_up > -MAX_INT32)
756  --maybe_right_tab_up;
757  if (n_mid_y < bottom_y && maybe_right_tab_down > -MAX_INT32)
758  --maybe_right_tab_down;
759  }
760  if (n_right > right_x && nbox.y_overlap(box) && n_left <= target_left) {
761  maybe_ragged_right = false;
762  if (debug)
763  tprintf("Not a ragged right\n");
764  }
765  if (maybe_left_tab_down == -MAX_INT32 && maybe_left_tab_up == -MAX_INT32 &&
766  maybe_right_tab_down == -MAX_INT32 && maybe_right_tab_up == -MAX_INT32)
767  break;
768  }
769  if (is_left_tab || maybe_left_tab_up > 1 || maybe_left_tab_down > 1) {
771  } else if (maybe_ragged_left && ConfirmRaggedLeft(bbox, min_ragged_gutter)) {
773  } else {
774  bbox->set_left_tab_type(TT_NONE);
775  }
776  if (is_right_tab || maybe_right_tab_up > 1 || maybe_right_tab_down > 1) {
778  } else if (maybe_ragged_right &&
779  ConfirmRaggedRight(bbox, min_ragged_gutter)) {
781  } else {
783  }
784  if (debug) {
785  tprintf("Left result = %s, Right result=%s\n",
786  bbox->left_tab_type() == TT_MAYBE_ALIGNED ? "Aligned" :
787  (bbox->left_tab_type() == TT_MAYBE_RAGGED ? "Ragged" : "None"),
788  bbox->right_tab_type() == TT_MAYBE_ALIGNED ? "Aligned" :
789  (bbox->right_tab_type() == TT_MAYBE_RAGGED ? "Ragged" : "None"));
790  }
791  return bbox->left_tab_type() != TT_NONE || bbox->right_tab_type() != TT_NONE;
792 }
793 
794 // Returns true if there is nothing in the rectangle of width min_gutter to
795 // the left of bbox.
796 bool TabFind::ConfirmRaggedLeft(BLOBNBOX* bbox, int min_gutter) {
797  TBOX search_box(bbox->bounding_box());
798  search_box.set_right(search_box.left());
799  search_box.set_left(search_box.left() - min_gutter);
800  return NothingYOverlapsInBox(search_box, bbox->bounding_box());
801 }
802 
803 // Returns true if there is nothing in the rectangle of width min_gutter to
804 // the right of bbox.
805 bool TabFind::ConfirmRaggedRight(BLOBNBOX* bbox, int min_gutter) {
806  TBOX search_box(bbox->bounding_box());
807  search_box.set_left(search_box.right());
808  search_box.set_right(search_box.right() + min_gutter);
809  return NothingYOverlapsInBox(search_box, bbox->bounding_box());
810 }
811 
812 // Returns true if there is nothing in the given search_box that vertically
813 // overlaps target_box other than target_box itself.
814 bool TabFind::NothingYOverlapsInBox(const TBOX& search_box,
815  const TBOX& target_box) {
816  BlobGridSearch rsearch(this);
817  rsearch.StartRectSearch(search_box);
818  BLOBNBOX* blob;
819  while ((blob = rsearch.NextRectSearch()) != NULL) {
820  const TBOX& box = blob->bounding_box();
821  if (box.y_overlap(target_box) && !(box == target_box))
822  return false;
823  }
824  return true;
825 }
826 
827 void TabFind::FindAllTabVectors(int min_gutter_width) {
828  // A list of vectors that will be created in estimating the skew.
829  TabVector_LIST dummy_vectors;
830  // An estimate of the vertical direction, revised as more lines are added.
831  int vertical_x = 0;
832  int vertical_y = 1;
833  // Find an estimate of the vertical direction by finding some tab vectors.
834  // Slowly up the search size until we get some vectors.
835  for (int search_size = kMinVerticalSearch; search_size < kMaxVerticalSearch;
836  search_size += kMinVerticalSearch) {
837  int vector_count = FindTabVectors(search_size, TA_LEFT_ALIGNED,
838  min_gutter_width,
839  &dummy_vectors,
840  &vertical_x, &vertical_y);
841  vector_count += FindTabVectors(search_size, TA_RIGHT_ALIGNED,
842  min_gutter_width,
843  &dummy_vectors,
844  &vertical_x, &vertical_y);
845  if (vector_count > 0)
846  break;
847  }
848  // Get rid of the test vectors and reset the types of the tabs.
849  dummy_vectors.clear();
850  for (int i = 0; i < left_tab_boxes_.size(); ++i) {
851  BLOBNBOX* bbox = left_tab_boxes_[i];
852  if (bbox->left_tab_type() == TT_CONFIRMED)
854  }
855  for (int i = 0; i < right_tab_boxes_.size(); ++i) {
856  BLOBNBOX* bbox = right_tab_boxes_[i];
857  if (bbox->right_tab_type() == TT_CONFIRMED)
859  }
860  if (textord_debug_tabfind) {
861  tprintf("Beginning real tab search with vertical = %d,%d...\n",
862  vertical_x, vertical_y);
863  }
864  // Now do the real thing ,but keep the vectors in the dummy_vectors list
865  // until they are all done, so we don't get the tab vectors confused with
866  // the rule line vectors.
867  FindTabVectors(kMaxVerticalSearch, TA_LEFT_ALIGNED, min_gutter_width,
868  &dummy_vectors, &vertical_x, &vertical_y);
869  FindTabVectors(kMaxVerticalSearch, TA_RIGHT_ALIGNED, min_gutter_width,
870  &dummy_vectors, &vertical_x, &vertical_y);
872  &dummy_vectors, &vertical_x, &vertical_y);
874  &dummy_vectors, &vertical_x, &vertical_y);
875  // Now add the vectors to the vectors_ list.
876  TabVector_IT v_it(&vectors_);
877  v_it.add_list_after(&dummy_vectors);
878  // Now use the summed (mean) vertical vector as the direction for everything.
879  SetVerticalSkewAndParellelize(vertical_x, vertical_y);
880 }
881 
882 // Helper for FindAllTabVectors finds the vectors of a particular type.
883 int TabFind::FindTabVectors(int search_size_multiple, TabAlignment alignment,
884  int min_gutter_width, TabVector_LIST* vectors,
885  int* vertical_x, int* vertical_y) {
886  TabVector_IT vector_it(vectors);
887  int vector_count = 0;
888  // Search the right or left tab boxes, looking for tab vectors.
889  bool right = alignment == TA_RIGHT_ALIGNED || alignment == TA_RIGHT_RAGGED;
890  const GenericVector<BLOBNBOX*>& boxes = right ? right_tab_boxes_
891  : left_tab_boxes_;
892  for (int i = 0; i < boxes.size(); ++i) {
893  BLOBNBOX* bbox = boxes[i];
894  if ((!right && bbox->left_tab_type() == TT_MAYBE_ALIGNED) ||
895  (right && bbox->right_tab_type() == TT_MAYBE_ALIGNED)) {
896  TabVector* vector = FindTabVector(search_size_multiple, min_gutter_width,
897  alignment,
898  bbox, vertical_x, vertical_y);
899  if (vector != NULL) {
900  ++vector_count;
901  vector_it.add_to_end(vector);
902  }
903  }
904  }
905  return vector_count;
906 }
907 
908 // Finds a vector corresponding to a tabstop running through the
909 // given box of the given alignment type.
910 // search_size_multiple is a multiple of height used to control
911 // the size of the search.
912 // vertical_x and y are updated with an estimate of the real
913 // vertical direction. (skew finding.)
914 // Returns NULL if no decent tabstop can be found.
915 TabVector* TabFind::FindTabVector(int search_size_multiple,
916  int min_gutter_width,
917  TabAlignment alignment,
918  BLOBNBOX* bbox,
919  int* vertical_x, int* vertical_y) {
920  int height = MAX(bbox->bounding_box().height(), gridsize());
921  AlignedBlobParams align_params(*vertical_x, *vertical_y,
922  height,
923  search_size_multiple, min_gutter_width,
924  resolution_, alignment);
925  // FindVerticalAlignment is in the parent (AlignedBlob) class.
926  return FindVerticalAlignment(align_params, bbox, vertical_x, vertical_y);
927 }
928 
929 // Set the vertical_skew_ member from the given vector and refit
930 // all vectors parallel to the skew vector.
931 void TabFind::SetVerticalSkewAndParellelize(int vertical_x, int vertical_y) {
932  // Fit the vertical vector into an ICOORD, which is 16 bit.
933  vertical_skew_.set_with_shrink(vertical_x, vertical_y);
935  tprintf("Vertical skew vector=(%d,%d)\n",
937  v_it_.set_to_list(&vectors_);
938  for (v_it_.mark_cycle_pt(); !v_it_.cycled_list(); v_it_.forward()) {
939  TabVector* v = v_it_.data();
940  v->Fit(vertical_skew_, true);
941  }
942  // Now sort the vectors as their direction has potentially changed.
943  SortVectors();
944 }
945 
946 // Sort all the current vectors using the given vertical direction vector.
947 void TabFind::SortVectors() {
948  vectors_.sort(TabVector::SortVectorsByKey);
949  v_it_.set_to_list(&vectors_);
950 }
951 
952 // Evaluate all the current tab vectors.
953 void TabFind::EvaluateTabs() {
954  TabVector_IT rule_it(&vectors_);
955  for (rule_it.mark_cycle_pt(); !rule_it.cycled_list(); rule_it.forward()) {
956  TabVector* tab = rule_it.data();
957  if (!tab->IsSeparator()) {
958  tab->Evaluate(vertical_skew_, this);
959  if (tab->BoxCount() < kMinEvaluatedTabs) {
960  if (textord_debug_tabfind > 2)
961  tab->Print("Too few boxes");
962  delete rule_it.extract();
963  v_it_.set_to_list(&vectors_);
964  } else if (WithinTestRegion(3, tab->startpt().x(), tab->startpt().y())) {
965  tab->Print("Evaluated tab");
966  }
967  }
968  }
969 }
970 
971 // Trace textlines from one side to the other of each tab vector, saving
972 // the most frequent column widths found in a list so that a given width
973 // can be tested for being a common width with a simple callback function.
974 void TabFind::ComputeColumnWidths(ScrollView* tab_win,
975  ColPartitionGrid* part_grid) {
976  #ifndef GRAPHICS_DISABLED
977  if (tab_win != NULL)
978  tab_win->Pen(ScrollView::WHITE);
979  #endif // GRAPHICS_DISABLED
980  // Accumulate column sections into a STATS
981  int col_widths_size = (tright_.x() - bleft_.x()) / kColumnWidthFactor;
982  STATS col_widths(0, col_widths_size + 1);
983  ApplyPartitionsToColumnWidths(part_grid, &col_widths);
984  #ifndef GRAPHICS_DISABLED
985  if (tab_win != NULL) {
986  tab_win->Update();
987  }
988  #endif // GRAPHICS_DISABLED
989  if (textord_debug_tabfind > 1)
990  col_widths.print();
991  // Now make a list of column widths.
992  MakeColumnWidths(col_widths_size, &col_widths);
993 }
994 
995 // Find column width and pair-up tab vectors with existing ColPartitions.
996 void TabFind::ApplyPartitionsToColumnWidths(ColPartitionGrid* part_grid,
997  STATS* col_widths) {
998  // For every ColPartition in the part_grid, add partners to the tabvectors
999  // and accumulate the column widths.
1000  ColPartitionGridSearch gsearch(part_grid);
1001  gsearch.StartFullSearch();
1002  ColPartition* part;
1003  while ((part = gsearch.NextFullSearch()) != NULL) {
1004  BLOBNBOX_C_IT blob_it(part->boxes());
1005  if (blob_it.empty())
1006  continue;
1007  BLOBNBOX* left_blob = blob_it.data();
1008  blob_it.move_to_last();
1009  BLOBNBOX* right_blob = blob_it.data();
1010  TabVector* left_vector = LeftTabForBox(left_blob->bounding_box(),
1011  true, false);
1012  if (left_vector == NULL || left_vector->IsRightTab())
1013  continue;
1014  TabVector* right_vector = RightTabForBox(right_blob->bounding_box(),
1015  true, false);
1016  if (right_vector == NULL || right_vector->IsLeftTab())
1017  continue;
1018 
1019  AddPartnerVector(left_blob, right_blob, left_vector, right_vector);
1020  int line_left = left_vector->XAtY(left_blob->bounding_box().bottom());
1021  int line_right = right_vector->XAtY(right_blob->bounding_box().bottom());
1022  // Add to STATS of measurements if the width is significant.
1023  int width = line_right - line_left;
1024  if (width >= kMinColumnWidth)
1025  col_widths->add(width / kColumnWidthFactor, 1);
1026  }
1027 }
1028 
1029 // Helper makes the list of common column widths in column_widths_ from the
1030 // input col_widths. Destroys the content of col_widths by repeatedly
1031 // finding the mode and erasing the peak.
1032 void TabFind::MakeColumnWidths(int col_widths_size, STATS* col_widths) {
1033  ICOORDELT_IT w_it(&column_widths_);
1034  int total_col_count = col_widths->get_total();
1035  while (col_widths->get_total() > 0) {
1036  int width = col_widths->mode();
1037  int col_count = col_widths->pile_count(width);
1038  col_widths->add(width, -col_count);
1039  // Get the entire peak.
1040  for (int left = width - 1; left > 0 &&
1041  col_widths->pile_count(left) > 0;
1042  --left) {
1043  int new_count = col_widths->pile_count(left);
1044  col_count += new_count;
1045  col_widths->add(left, -new_count);
1046  }
1047  for (int right = width + 1; right < col_widths_size &&
1048  col_widths->pile_count(right) > 0;
1049  ++right) {
1050  int new_count = col_widths->pile_count(right);
1051  col_count += new_count;
1052  col_widths->add(right, -new_count);
1053  }
1054  if (col_count > kMinLinesInColumn &&
1055  col_count > kMinFractionalLinesInColumn * total_col_count) {
1056  ICOORDELT* w = new ICOORDELT(width, col_count);
1057  w_it.add_after_then_move(w);
1059  tprintf("Column of width %d has %d = %.2f%% lines\n",
1060  width * kColumnWidthFactor, col_count,
1061  100.0 * col_count / total_col_count);
1062  }
1063  }
1064 }
1065 
1066 // Mark blobs as being in a vertical text line where that is the case.
1067 // Returns true if the majority of the image is vertical text lines.
1068 void TabFind::MarkVerticalText() {
1070  tprintf("Checking for vertical lines\n");
1071  BlobGridSearch gsearch(this);
1072  gsearch.StartFullSearch();
1073  BLOBNBOX* blob = NULL;
1074  while ((blob = gsearch.NextFullSearch()) != NULL) {
1075  if (blob->region_type() < BRT_UNKNOWN)
1076  continue;
1077  if (blob->UniquelyVertical()) {
1079  }
1080  }
1081 }
1082 
1083 int TabFind::FindMedianGutterWidth(TabVector_LIST *lines) {
1084  TabVector_IT it(lines);
1085  int prev_right = -1;
1086  int max_gap = static_cast<int>(kMaxGutterWidthAbsolute * resolution_);
1087  STATS gaps(0, max_gap);
1088  STATS heights(0, max_gap);
1089  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1090  TabVector* v = it.data();
1091  TabVector* partner = v->GetSinglePartner();
1092  if (!v->IsLeftTab() || v->IsSeparator() || !partner) continue;
1093  heights.add(partner->startpt().x() - v->startpt().x(), 1);
1094  if (prev_right > 0 && v->startpt().x() > prev_right) {
1095  gaps.add(v->startpt().x() - prev_right, 1);
1096  }
1097  prev_right = partner->startpt().x();
1098  }
1100  tprintf("TabGutter total %d median_gap %.2f median_hgt %.2f\n",
1101  gaps.get_total(), gaps.median(), heights.median());
1102  if (gaps.get_total() < kMinLinesInColumn) return 0;
1103  return static_cast<int>(gaps.median());
1104 }
1105 
1106 // Find the next adjacent (looking to the left or right) blob on this text
1107 // line, with the constraint that it must vertically significantly overlap
1108 // the [top_y, bottom_y] range.
1109 // If ignore_images is true, then blobs with aligned_text() < 0 are treated
1110 // as if they do not exist.
1111 BLOBNBOX* TabFind::AdjacentBlob(const BLOBNBOX* bbox,
1112  bool look_left, bool ignore_images,
1113  double min_overlap_fraction,
1114  int gap_limit, int top_y, int bottom_y) {
1115  GridSearch<BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT> sidesearch(this);
1116  const TBOX& box = bbox->bounding_box();
1117  int left = box.left();
1118  int right = box.right();
1119  int mid_x = (left + right) / 2;
1120  sidesearch.StartSideSearch(mid_x, bottom_y, top_y);
1121  int best_gap = 0;
1122  bool debug = WithinTestRegion(3, left, bottom_y);
1123  BLOBNBOX* result = NULL;
1124  BLOBNBOX* neighbour = NULL;
1125  while ((neighbour = sidesearch.NextSideSearch(look_left)) != NULL) {
1126  if (debug) {
1127  tprintf("Adjacent blob: considering box:");
1128  neighbour->bounding_box().print();
1129  }
1130  if (neighbour == bbox ||
1131  (ignore_images && neighbour->region_type() < BRT_UNKNOWN))
1132  continue;
1133  const TBOX& nbox = neighbour->bounding_box();
1134  int n_top_y = nbox.top();
1135  int n_bottom_y = nbox.bottom();
1136  int v_overlap = MIN(n_top_y, top_y) - MAX(n_bottom_y, bottom_y);
1137  int height = top_y - bottom_y;
1138  int n_height = n_top_y - n_bottom_y;
1139  if (v_overlap > min_overlap_fraction * MIN(height, n_height) &&
1140  (min_overlap_fraction == 0.0 || !DifferentSizes(height, n_height))) {
1141  int n_left = nbox.left();
1142  int n_right = nbox.right();
1143  int h_gap = MAX(n_left, left) - MIN(n_right, right);
1144  int n_mid_x = (n_left + n_right) / 2;
1145  if (look_left == (n_mid_x < mid_x) && n_mid_x != mid_x) {
1146  if (h_gap > gap_limit) {
1147  // Hit a big gap before next tab so don't return anything.
1148  if (debug)
1149  tprintf("Giving up due to big gap = %d vs %d\n",
1150  h_gap, gap_limit);
1151  return result;
1152  }
1153  if (h_gap > 0 && (look_left ? neighbour->right_tab_type()
1154  : neighbour->left_tab_type()) >= TT_CONFIRMED) {
1155  // Hit a tab facing the wrong way. Stop in case we are crossing
1156  // the column boundary.
1157  if (debug)
1158  tprintf("Collision with like tab of type %d at %d,%d\n",
1159  look_left ? neighbour->right_tab_type()
1160  : neighbour->left_tab_type(),
1161  n_left, nbox.bottom());
1162  return result;
1163  }
1164  // This is a good fit to the line. Continue with this
1165  // neighbour as the bbox if the best gap.
1166  if (result == NULL || h_gap < best_gap) {
1167  if (debug)
1168  tprintf("Good result\n");
1169  result = neighbour;
1170  best_gap = h_gap;
1171  } else {
1172  // The new one is worse, so we probably already have the best result.
1173  return result;
1174  }
1175  } else if (debug) {
1176  tprintf("Wrong way\n");
1177  }
1178  } else if (debug) {
1179  tprintf("Insufficient overlap\n");
1180  }
1181  }
1182  if (WithinTestRegion(3, left, box.top()))
1183  tprintf("Giving up due to end of search\n");
1184  return result; // Hit the edge and found nothing.
1185 }
1186 
1187 // Add a bi-directional partner relationship between the left
1188 // and the right. If one (or both) of the vectors is a separator,
1189 // extend a nearby extendable vector or create a new one of the
1190 // correct type, using the given left or right blob as a guide.
1191 void TabFind::AddPartnerVector(BLOBNBOX* left_blob, BLOBNBOX* right_blob,
1192  TabVector* left, TabVector* right) {
1193  const TBOX& left_box = left_blob->bounding_box();
1194  const TBOX& right_box = right_blob->bounding_box();
1195  if (left->IsSeparator()) {
1196  // Try to find a nearby left edge to extend.
1197  TabVector* v = LeftTabForBox(left_box, true, true);
1198  if (v != NULL && v != left && v->IsLeftTab() &&
1199  v->XAtY(left_box.top()) > left->XAtY(left_box.top())) {
1200  left = v; // Found a good replacement.
1201  left->ExtendToBox(left_blob);
1202  } else {
1203  // Fake a vector.
1204  left = new TabVector(*left, TA_LEFT_RAGGED, vertical_skew_, left_blob);
1205  vectors_.add_sorted(TabVector::SortVectorsByKey, left);
1206  v_it_.move_to_first();
1207  }
1208  }
1209  if (right->IsSeparator()) {
1210  // Try to find a nearby left edge to extend.
1211  if (WithinTestRegion(3, right_box.right(), right_box.bottom())) {
1212  tprintf("Box edge (%d,%d-%d)",
1213  right_box.right(), right_box.bottom(), right_box.top());
1214  right->Print(" looking for improvement for");
1215  }
1216  TabVector* v = RightTabForBox(right_box, true, true);
1217  if (v != NULL && v != right && v->IsRightTab() &&
1218  v->XAtY(right_box.top()) < right->XAtY(right_box.top())) {
1219  right = v; // Found a good replacement.
1220  right->ExtendToBox(right_blob);
1221  if (WithinTestRegion(3, right_box.right(), right_box.bottom())) {
1222  right->Print("Extended vector");
1223  }
1224  } else {
1225  // Fake a vector.
1226  right = new TabVector(*right, TA_RIGHT_RAGGED, vertical_skew_,
1227  right_blob);
1228  vectors_.add_sorted(TabVector::SortVectorsByKey, right);
1229  v_it_.move_to_first();
1230  if (WithinTestRegion(3, right_box.right(), right_box.bottom())) {
1231  right->Print("Created new vector");
1232  }
1233  }
1234  }
1235  left->AddPartner(right);
1236  right->AddPartner(left);
1237 }
1238 
1239 // Remove separators and unused tabs from the main vectors_ list
1240 // to the dead_vectors_ list.
1241 void TabFind::CleanupTabs() {
1242  // TODO(rays) Before getting rid of separators and unused vectors, it
1243  // would be useful to try moving ragged vectors outwards to see if this
1244  // allows useful extension. Could be combined with checking ends of partners.
1245  TabVector_IT it(&vectors_);
1246  TabVector_IT dead_it(&dead_vectors_);
1247  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1248  TabVector* v = it.data();
1249  if (v->IsSeparator() || v->Partnerless()) {
1250  dead_it.add_after_then_move(it.extract());
1251  v_it_.set_to_list(&vectors_);
1252  } else {
1253  v->FitAndEvaluateIfNeeded(vertical_skew_, this);
1254  }
1255  }
1256 }
1257 
1258 // Apply the given rotation to the given list of blobs.
1259 void TabFind::RotateBlobList(const FCOORD& rotation, BLOBNBOX_LIST* blobs) {
1260  BLOBNBOX_IT it(blobs);
1261  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1262  it.data()->rotate_box(rotation);
1263  }
1264 }
1265 
1266 // Recreate the grid with deskewed BLOBNBOXes.
1267 // Returns false if the detected skew angle is impossible.
1268 bool TabFind::Deskew(TabVector_LIST* hlines, BLOBNBOX_LIST* image_blobs,
1269  TO_BLOCK* block, FCOORD* deskew, FCOORD* reskew) {
1270  ComputeDeskewVectors(deskew, reskew);
1271  if (deskew->x() < kCosMaxSkewAngle)
1272  return false;
1273  RotateBlobList(*deskew, image_blobs);
1274  RotateBlobList(*deskew, &block->blobs);
1275  RotateBlobList(*deskew, &block->small_blobs);
1276  RotateBlobList(*deskew, &block->noise_blobs);
1277  if (textord_debug_images) {
1278  // Rotate the debug pix and arrange for it to be drawn at the correct
1279  // pixel offset.
1280  Pix* pix_grey = pixRead(AlignedBlob::textord_debug_pix().string());
1281  int width = pixGetWidth(pix_grey);
1282  int height = pixGetHeight(pix_grey);
1283  float angle = atan2(deskew->y(), deskew->x());
1284  // Positive angle is clockwise to pixRotate.
1285  Pix* pix_rot = pixRotate(pix_grey, -angle, L_ROTATE_AREA_MAP,
1286  L_BRING_IN_WHITE, width, height);
1287  // The image must be translated by the rotation of its center, since it
1288  // has just been rotated about its center.
1289  ICOORD center_offset(width / 2, height / 2);
1290  ICOORD new_center_offset(center_offset);
1291  new_center_offset.rotate(*deskew);
1292  image_origin_ += new_center_offset - center_offset;
1293  // The image grew as it was rotated, so offset the (top/left) origin
1294  // by half the change in size. y is opposite to x because it is drawn
1295  // at ist top/left, not bottom/left.
1296  ICOORD corner_offset((width - pixGetWidth(pix_rot)) / 2,
1297  (pixGetHeight(pix_rot) - height) / 2);
1298  image_origin_ += corner_offset;
1299  pixWrite(AlignedBlob::textord_debug_pix().string(), pix_rot, IFF_PNG);
1300  pixDestroy(&pix_grey);
1301  pixDestroy(&pix_rot);
1302  }
1303 
1304  // Rotate the horizontal vectors. The vertical vectors don't need
1305  // rotating as they can just be refitted.
1306  TabVector_IT h_it(hlines);
1307  for (h_it.mark_cycle_pt(); !h_it.cycled_list(); h_it.forward()) {
1308  TabVector* h = h_it.data();
1309  h->Rotate(*deskew);
1310  }
1311  TabVector_IT d_it(&dead_vectors_);
1312  for (d_it.mark_cycle_pt(); !d_it.cycled_list(); d_it.forward()) {
1313  TabVector* d = d_it.data();
1314  d->Rotate(*deskew);
1315  }
1316  SetVerticalSkewAndParellelize(0, 1);
1317  // Rebuild the grid to the new size.
1318  TBOX grid_box(bleft_, tright_);
1319  grid_box.rotate_large(*deskew);
1320  Init(gridsize(), grid_box.botleft(), grid_box.topright());
1321  InsertBlobsToGrid(false, false, image_blobs, this);
1322  InsertBlobsToGrid(true, false, &block->blobs, this);
1323  return true;
1324 }
1325 
1326 // Flip the vertical and horizontal lines and rotate the grid ready
1327 // for working on the rotated image.
1328 // This also makes parameter adjustments for FindInitialTabVectors().
1329 void TabFind::ResetForVerticalText(const FCOORD& rotate, const FCOORD& rerotate,
1330  TabVector_LIST* horizontal_lines,
1331  int* min_gutter_width) {
1332  // Rotate the horizontal and vertical vectors and swap them over.
1333  // Only the separators are kept and rotated; other tabs are used
1334  // to estimate the gutter width then thrown away.
1335  TabVector_LIST ex_verticals;
1336  TabVector_IT ex_v_it(&ex_verticals);
1337  TabVector_LIST vlines;
1338  TabVector_IT v_it(&vlines);
1339  while (!v_it_.empty()) {
1340  TabVector* v = v_it_.extract();
1341  if (v->IsSeparator()) {
1342  v->Rotate(rotate);
1343  ex_v_it.add_after_then_move(v);
1344  } else {
1345  v_it.add_after_then_move(v);
1346  }
1347  v_it_.forward();
1348  }
1349 
1350  // Adjust the min gutter width for better tabbox selection
1351  // in 2nd call to FindInitialTabVectors().
1352  int median_gutter = FindMedianGutterWidth(&vlines);
1353  if (median_gutter > *min_gutter_width)
1354  *min_gutter_width = median_gutter;
1355 
1356  TabVector_IT h_it(horizontal_lines);
1357  for (h_it.mark_cycle_pt(); !h_it.cycled_list(); h_it.forward()) {
1358  TabVector* h = h_it.data();
1359  h->Rotate(rotate);
1360  }
1361  v_it_.add_list_after(horizontal_lines);
1362  v_it_.move_to_first();
1363  h_it.set_to_list(horizontal_lines);
1364  h_it.add_list_after(&ex_verticals);
1365 
1366  // Rebuild the grid to the new size.
1367  TBOX grid_box(bleft(), tright());
1368  grid_box.rotate_large(rotate);
1369  Init(gridsize(), grid_box.botleft(), grid_box.topright());
1370 }
1371 
1372 // Clear the grid and get rid of the tab vectors, but not separators,
1373 // ready to start again.
1375  v_it_.move_to_first();
1376  for (v_it_.mark_cycle_pt(); !v_it_.cycled_list(); v_it_.forward()) {
1377  if (!v_it_.data()->IsSeparator())
1378  delete v_it_.extract();
1379  }
1380  Clear();
1381 }
1382 
1383 // Reflect the separator tab vectors and the grids in the y-axis.
1384 // Can only be called after Reset!
1386  TabVector_LIST temp_list;
1387  TabVector_IT temp_it(&temp_list);
1388  v_it_.move_to_first();
1389  // The TabVector list only contains vertical lines, but they need to be
1390  // reflected and the list needs to be reversed, so they are still in
1391  // sort_key order.
1392  while (!v_it_.empty()) {
1393  TabVector* v = v_it_.extract();
1394  v_it_.forward();
1395  v->ReflectInYAxis();
1396  temp_it.add_before_then_move(v);
1397  }
1398  v_it_.add_list_after(&temp_list);
1399  v_it_.move_to_first();
1400  // Reset this grid with reflected bounding boxes.
1401  TBOX grid_box(bleft(), tright());
1402  int tmp = grid_box.left();
1403  grid_box.set_left(-grid_box.right());
1404  grid_box.set_right(-tmp);
1405  Init(gridsize(), grid_box.botleft(), grid_box.topright());
1406 }
1407 
1408 // Compute the rotation required to deskew, and its inverse rotation.
1409 void TabFind::ComputeDeskewVectors(FCOORD* deskew, FCOORD* reskew) {
1410  double length = vertical_skew_ % vertical_skew_;
1411  length = sqrt(length);
1412  deskew->set_x(static_cast<float>(vertical_skew_.y() / length));
1413  deskew->set_y(static_cast<float>(vertical_skew_.x() / length));
1414  reskew->set_x(deskew->x());
1415  reskew->set_y(-deskew->y());
1416 }
1417 
1418 // Compute and apply constraints to the end positions of TabVectors so
1419 // that where possible partners end at the same y coordinate.
1420 void TabFind::ApplyTabConstraints() {
1421  TabVector_IT it(&vectors_);
1422  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1423  TabVector* v = it.data();
1424  v->SetupConstraints();
1425  }
1426  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1427  TabVector* v = it.data();
1428  // With the first and last partner, we want a common bottom and top,
1429  // respectively, and for each change of partner, we want a common
1430  // top of first with bottom of next.
1431  v->SetupPartnerConstraints();
1432  }
1433  // TODO(rays) The back-to-back pairs should really be done like the
1434  // front-to-front pairs, but there is no convenient way of producing the
1435  // list of partners like there is with the front-to-front.
1436  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1437  TabVector* v = it.data();
1438  if (!v->IsRightTab())
1439  continue;
1440  // For each back-to-back pair of vectors, try for common top and bottom.
1441  TabVector_IT partner_it(it);
1442  for (partner_it.forward(); !partner_it.at_first(); partner_it.forward()) {
1443  TabVector* partner = partner_it.data();
1444  if (!partner->IsLeftTab() || !v->VOverlap(*partner))
1445  continue;
1446  v->SetupPartnerConstraints(partner);
1447  }
1448  }
1449  // Now actually apply the constraints to get common start/end points.
1450  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1451  TabVector* v = it.data();
1452  if (!v->IsSeparator())
1453  v->ApplyConstraints();
1454  }
1455  // TODO(rays) Where constraint application fails, it would be good to try
1456  // checking the ends to see if they really should be moved.
1457 }
1458 
1459 } // namespace tesseract.