Tesseract  3.02
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
alignedblob.cpp
Go to the documentation of this file.
1 
2 // File: alignedblob.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 "alignedblob.h"
21 #include "ndminx.h"
22 
23 // Include automatically generated configuration file if running autoconf.
24 #ifdef HAVE_CONFIG_H
25 #include "config_auto.h"
26 #endif
27 
28 INT_VAR(textord_debug_tabfind, 0, "Debug tab finding");
29 INT_VAR(textord_debug_bugs, 0, "Turn on output related to bugs in tab finding");
30 INT_VAR(textord_testregion_left, -1, "Left edge of debug reporting rectangle");
31 INT_VAR(textord_testregion_top, -1, "Top edge of debug reporting rectangle");
32 INT_VAR(textord_testregion_right, MAX_INT32, "Right edge of debug rectangle");
33 INT_VAR(textord_testregion_bottom, MAX_INT32, "Bottom edge of debug rectangle");
34 BOOL_VAR(textord_debug_images, false, "Use greyed image background for debug");
35 BOOL_VAR(textord_debug_printable, false, "Make debug windows printable");
36 
37 namespace tesseract {
38 
39 // Fraction of resolution used as alignment tolerance for aligned tabs.
40 const double kAlignedFraction = 0.03125;
41 // Fraction of resolution used as alignment tolerance for ragged tabs.
42 const double kRaggedFraction = 2.5;
43 // Fraction of height used as a minimum gutter gap for aligned blobs.
44 const double kAlignedGapFraction = 0.75;
45 // Fraction of height used as a minimum gutter gap for ragged tabs.
46 const double kRaggedGapFraction = 1.0;
47 // Constant number of pixels used as alignment tolerance for line finding.
48 const int kVLineAlignment = 3;
49 // Constant number of pixels used as gutter gap tolerance for line finding.
50 const int kVLineGutter = 1;
51 // Constant number of pixels used as the search size for line finding.
52 const int kVLineSearchSize = 150;
53 // Min number of points to accept for a ragged tab stop.
54 const int kMinRaggedTabs = 5;
55 // Min number of points to accept for an aligned tab stop.
56 const int kMinAlignedTabs = 4;
57 // Constant number of pixels minimum height of a vertical line.
58 const int kVLineMinLength = 500;
59 // Minimum gradient for a vertical tab vector. Used to prune away junk
60 // tab vectors with what would be a ridiculously large skew angle.
61 // Value corresponds to tan(90 - max allowed skew angle)
62 const double kMinTabGradient = 4.0;
63 // Tolerance to skew on top of current estimate of skew. Divide x or y length
64 // by kMaxSkewFactor to get the y or x skew distance.
65 // If the angle is small, the angle in degrees is roughly 60/kMaxSkewFactor.
66 const int kMaxSkewFactor = 15;
67 
68 // Constant part of textord_debug_pix_.
69 const char* kTextordDebugPix = "psdebug_pix";
70 
71 // Name of image file to use if textord_debug_images is true.
72 STRING AlignedBlob::textord_debug_pix_ = kTextordDebugPix;
73 // Index to image file to use if textord_debug_images is true.
74 int AlignedBlob::debug_pix_index_ = 0;
75 
76 // Increment the serial number counter and set the string to use
77 // for a filename if textord_debug_images is true.
79  ++debug_pix_index_;
80  textord_debug_pix_ = kTextordDebugPix;
81  char numbuf[32];
82  snprintf(numbuf, sizeof(numbuf), "%d", debug_pix_index_);
83  textord_debug_pix_ += numbuf;
84  textord_debug_pix_ += ".pix";
85 }
86 
87 // Constructor to set the parameters for finding aligned and ragged tabs.
88 // Vertical_x and vertical_y are the current estimates of the true vertical
89 // direction (up) in the image. Height is the height of the starter blob.
90 // v_gap_multiple is the multiple of height that will be used as a limit
91 // on vertical gap before giving up and calling the line ended.
92 // resolution is the original image resolution, and align0 indicates the
93 // type of tab stop to be found.
94 AlignedBlobParams::AlignedBlobParams(int vertical_x, int vertical_y,
95  int height, int v_gap_multiple,
96  int min_gutter_width,
97  int resolution, TabAlignment align0)
98  : right_tab(align0 == TA_RIGHT_RAGGED || align0 == TA_RIGHT_ALIGNED),
99  ragged(align0 == TA_LEFT_RAGGED || align0 == TA_RIGHT_RAGGED),
100  alignment(align0),
101  confirmed_type(TT_CONFIRMED),
102  min_length(0) {
103  // Set the tolerances according to the type of line sought.
104  // For tab search, these are based on the image resolution for most, or
105  // the height of the starting blob for the maximum vertical gap.
106  max_v_gap = height * v_gap_multiple;
107  if (ragged) {
108  // In the case of a ragged edge, we are much more generous with the
109  // inside alignment fraction, but also require a much bigger gutter.
111  if (alignment == TA_RIGHT_RAGGED) {
112  l_align_tolerance = static_cast<int>(resolution * kRaggedFraction + 0.5);
113  r_align_tolerance = static_cast<int>(resolution * kAlignedFraction + 0.5);
114  } else {
115  l_align_tolerance = static_cast<int>(resolution * kAlignedFraction + 0.5);
116  r_align_tolerance = static_cast<int>(resolution * kRaggedFraction + 0.5);
117  }
119  } else {
121  l_align_tolerance = static_cast<int>(resolution * kAlignedFraction + 0.5);
122  r_align_tolerance = static_cast<int>(resolution * kAlignedFraction + 0.5);
124  }
125  min_gutter = static_cast<int>(height * gutter_fraction + 0.5);
126  if (min_gutter < min_gutter_width)
127  min_gutter = min_gutter_width;
128  // Fit the vertical vector into an ICOORD, which is 16 bit.
129  set_vertical(vertical_x, vertical_y);
130 }
131 
132 // Constructor to set the parameters for finding vertical lines.
133 // Vertical_x and vertical_y are the current estimates of the true vertical
134 // direction (up) in the image. Width is the width of the starter blob.
135 AlignedBlobParams::AlignedBlobParams(int vertical_x, int vertical_y,
136  int width)
137  : gutter_fraction(0.0),
138  right_tab(false),
139  ragged(false),
140  alignment(TA_SEPARATOR),
141  confirmed_type(TT_VLINE),
142  max_v_gap(kVLineSearchSize),
143  min_gutter(kVLineGutter),
144  min_points(1),
145  min_length(kVLineMinLength) {
146  // Compute threshold for left and right alignment.
149 
150  // Fit the vertical vector into an ICOORD, which is 16 bit.
151  set_vertical(vertical_x, vertical_y);
152 }
153 
154 // Fit the vertical vector into an ICOORD, which is 16 bit.
155 void AlignedBlobParams::set_vertical(int vertical_x, int vertical_y) {
156  int factor = 1;
157  if (vertical_y > MAX_INT16)
158  factor = vertical_y / MAX_INT16 + 1;
159  vertical.set_x(vertical_x / factor);
160  vertical.set_y(vertical_y / factor);
161 }
162 
163 
165  const ICOORD& bleft, const ICOORD& tright)
166  : BlobGrid(gridsize, bleft, tright) {
167 }
168 
170 }
171 
172 // Return true if the given coordinates are within the test rectangle
173 // and the debug level is at least the given detail level.
174 bool AlignedBlob::WithinTestRegion(int detail_level, int x, int y) {
175  if (textord_debug_tabfind < detail_level)
176  return false;
178  y <= textord_testregion_top && y >= textord_testregion_bottom;
179 }
180 
181 // Display the tab codes of the BLOBNBOXes in this grid.
182 ScrollView* AlignedBlob::DisplayTabs(const char* window_name,
183  ScrollView* tab_win) {
184 #ifndef GRAPHICS_DISABLED
185  if (tab_win == NULL)
186  tab_win = MakeWindow(0, 50, window_name);
187  // For every tab in the grid, display it.
189  gsearch.StartFullSearch();
190  BLOBNBOX* bbox;
191  while ((bbox = gsearch.NextFullSearch()) != NULL) {
192  TBOX box = bbox->bounding_box();
193  int left_x = box.left();
194  int right_x = box.right();
195  int top_y = box.top();
196  int bottom_y = box.bottom();
197  TabType tabtype = bbox->left_tab_type();
198  if (tabtype != TT_NONE) {
199  if (tabtype == TT_MAYBE_ALIGNED)
200  tab_win->Pen(ScrollView::BLUE);
201  else if (tabtype == TT_MAYBE_RAGGED)
202  tab_win->Pen(ScrollView::YELLOW);
203  else if (tabtype == TT_CONFIRMED)
204  tab_win->Pen(ScrollView::GREEN);
205  else
206  tab_win->Pen(ScrollView::GREY);
207  tab_win->Line(left_x, top_y, left_x, bottom_y);
208  }
209  tabtype = bbox->right_tab_type();
210  if (tabtype != TT_NONE) {
211  if (tabtype == TT_MAYBE_ALIGNED)
212  tab_win->Pen(ScrollView::MAGENTA);
213  else if (tabtype == TT_MAYBE_RAGGED)
214  tab_win->Pen(ScrollView::ORANGE);
215  else if (tabtype == TT_CONFIRMED)
216  tab_win->Pen(ScrollView::RED);
217  else
218  tab_win->Pen(ScrollView::GREY);
219  tab_win->Line(right_x, top_y, right_x, bottom_y);
220  }
221  }
222  tab_win->Update();
223 #endif
224  return tab_win;
225 }
226 
227 // Helper returns true if the total number of line_crossings of all the blobs
228 // in the list is at least 2.
229 static bool AtLeast2LineCrossings(BLOBNBOX_CLIST* blobs) {
230  BLOBNBOX_C_IT it(blobs);
231  int total_crossings = 0;
232  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
233  total_crossings += it.data()->line_crossings();
234  }
235  return total_crossings >= 2;
236 }
237 
238 // Finds a vector corresponding to a set of vertically aligned blob edges
239 // running through the given box. The type of vector returned and the
240 // search parameters are determined by the AlignedBlobParams.
241 // vertical_x and y are updated with an estimate of the real
242 // vertical direction. (skew finding.)
243 // Returns NULL if no decent vector can be found.
245  BLOBNBOX* bbox,
246  int* vertical_x,
247  int* vertical_y) {
248  int ext_start_y, ext_end_y;
249  BLOBNBOX_CLIST good_points;
250  // Search up and then down from the starting bbox.
251  TBOX box = bbox->bounding_box();
252  bool debug = WithinTestRegion(2, box.left(), box.bottom());
253  int pt_count = AlignTabs(align_params, false, bbox, &good_points, &ext_end_y);
254  pt_count += AlignTabs(align_params, true, bbox, &good_points, &ext_start_y);
255  BLOBNBOX_C_IT it(&good_points);
256  it.move_to_last();
257  box = it.data()->bounding_box();
258  int end_y = box.top();
259  int end_x = align_params.right_tab ? box.right() : box.left();
260  it.move_to_first();
261  box = it.data()->bounding_box();
262  int start_x = align_params.right_tab ? box.right() : box.left();
263  int start_y = box.bottom();
264  // Acceptable tab vectors must have a mininum number of points,
265  // have a minimum acceptable length, and have a minimum gradient.
266  // The gradient corresponds to the skew angle.
267  // Ragged tabs don't need to satisfy the gradient condition, as they
268  // will always end up parallel to the vertical direction.
269  bool at_least_2_crossings = AtLeast2LineCrossings(&good_points);
270  if ((pt_count >= align_params.min_points &&
271  end_y - start_y >= align_params.min_length &&
272  (align_params.ragged ||
273  end_y - start_y >= abs(end_x - start_x) * kMinTabGradient)) ||
274  at_least_2_crossings) {
275  int confirmed_points = 0;
276  // Count existing confirmed points to see if vector is acceptable.
277  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
278  bbox = it.data();
279  if (align_params.right_tab) {
280  if (bbox->right_tab_type() == align_params.confirmed_type)
281  ++confirmed_points;
282  } else {
283  if (bbox->left_tab_type() == align_params.confirmed_type)
284  ++confirmed_points;
285  }
286  }
287  // Ragged vectors are not allowed to use too many already used points.
288  if (!align_params.ragged ||
289  confirmed_points + confirmed_points < pt_count) {
290  const TBOX& box = bbox->bounding_box();
291  if (debug) {
292  tprintf("Confirming tab vector of %d pts starting at %d,%d\n",
293  pt_count, box.left(), box.bottom());
294  }
295  // Flag all the aligned neighbours as confirmed .
296  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
297  bbox = it.data();
298  if (align_params.right_tab) {
299  bbox->set_right_tab_type(align_params.confirmed_type);
300  } else {
301  bbox->set_left_tab_type(align_params.confirmed_type);
302  }
303  if (debug) {
304  bbox->bounding_box().print();
305  }
306  }
307  // Now make the vector and return it.
308  TabVector* result = TabVector::FitVector(align_params.alignment,
309  align_params.vertical,
310  ext_start_y, ext_end_y,
311  &good_points,
312  vertical_x, vertical_y);
313  result->set_intersects_other_lines(at_least_2_crossings);
314  if (debug) {
315  tprintf("Box was %d, %d\n", box.left(), box.bottom());
316  result->Print("After fitting");
317  }
318  return result;
319  } else if (debug) {
320  tprintf("Ragged tab used too many used points: %d out of %d\n",
321  confirmed_points, pt_count);
322  }
323  } else if (debug) {
324  tprintf("Tab vector failed basic tests: pt count %d vs min %d, "
325  "length %d vs min %d, min grad %g\n",
326  pt_count, align_params.min_points, end_y - start_y,
327  align_params.min_length, abs(end_x - start_x) * kMinTabGradient);
328  }
329  return NULL;
330 }
331 
332 // Find a set of blobs that are aligned in the given vertical
333 // direction with the given blob. Returns a list of aligned
334 // blobs and the number in the list.
335 // For other parameters see FindAlignedBlob below.
336 int AlignedBlob::AlignTabs(const AlignedBlobParams& params,
337  bool top_to_bottom, BLOBNBOX* bbox,
338  BLOBNBOX_CLIST* good_points, int* end_y) {
339  int ptcount = 0;
340  BLOBNBOX_C_IT it(good_points);
341 
342  TBOX box = bbox->bounding_box();
343  bool debug = WithinTestRegion(2, box.left(), box.bottom());
344  if (debug) {
345  tprintf("Starting alignment run at blob:");
346  box.print();
347  }
348  int x_start = params.right_tab ? box.right() : box.left();
349  while (bbox != NULL) {
350  // Add the blob to the list if the appropriate side is a tab candidate,
351  // or if we are working on a ragged tab.
352  TabType type = params.right_tab ? bbox->right_tab_type()
353  : bbox->left_tab_type();
354  if (((type != TT_NONE && type != TT_MAYBE_RAGGED) || params.ragged) &&
355  (it.empty() || it.data() != bbox)) {
356  if (top_to_bottom)
357  it.add_before_then_move(bbox);
358  else
359  it.add_after_then_move(bbox);
360  ++ptcount;
361  }
362  // Find the next blob that is aligned with the current one.
363  // FindAlignedBlob guarantees that forward progress will be made in the
364  // top_to_bottom direction, and therefore eventually it will return NULL,
365  // making this while (bbox != NULL) loop safe.
366  bbox = FindAlignedBlob(params, top_to_bottom, bbox, x_start, end_y);
367  if (bbox != NULL) {
368  box = bbox->bounding_box();
369  if (!params.ragged)
370  x_start = params.right_tab ? box.right() : box.left();
371  }
372  }
373  if (debug) {
374  tprintf("Alignment run ended with %d pts at blob:", ptcount);
375  box.print();
376  }
377  return ptcount;
378 }
379 
380 // Search vertically for a blob that is aligned with the input bbox.
381 // The search parameters are determined by AlignedBlobParams.
382 // top_to_bottom tells whether to search down or up.
383 // The return value is NULL if nothing was found in the search box
384 // or if a blob was found in the gutter. On a NULL return, end_y
385 // is set to the edge of the search box or the leading edge of the
386 // gutter blob if one was found.
387 BLOBNBOX* AlignedBlob::FindAlignedBlob(const AlignedBlobParams& p,
388  bool top_to_bottom, BLOBNBOX* bbox,
389  int x_start, int* end_y) {
390  TBOX box = bbox->bounding_box();
391  // If there are separator lines, get the column edges.
392  int left_column_edge = bbox->left_rule();
393  int right_column_edge = bbox->right_rule();
394  // start_y is used to guarantee that forward progress is made and the
395  // search does not go into an infinite loop. New blobs must extend the
396  // line beyond start_y.
397  int start_y = top_to_bottom ? box.bottom() : box.top();
398  if (WithinTestRegion(2, x_start, start_y)) {
399  tprintf("Column edges for blob at (%d,%d)->(%d,%d) are [%d, %d]\n",
400  box.left(), box.top(), box.right(), box.bottom(),
401  left_column_edge, right_column_edge);
402  }
403  // Compute skew tolerance.
404  int skew_tolerance = p.max_v_gap / kMaxSkewFactor;
405  // Calculate xmin and xmax of the search box so that it contains
406  // all possibly relevant boxes upto p.max_v_gap above or below accoording
407  // to top_to_bottom.
408  // Start with a notion of vertical with the current estimate.
409  int x2 = (p.max_v_gap * p.vertical.x() + p.vertical.y()/2) / p.vertical.y();
410  if (top_to_bottom) {
411  x2 = x_start - x2;
412  *end_y = start_y - p.max_v_gap;
413  } else {
414  x2 = x_start + x2;
415  *end_y = start_y + p.max_v_gap;
416  }
417  // Expand the box by an additional skew tolerance
418  int xmin = MIN(x_start, x2) - skew_tolerance;
419  int xmax = MAX(x_start, x2) + skew_tolerance;
420  // Now add direction-specific tolerances.
421  if (p.right_tab) {
422  xmax += p.min_gutter;
423  xmin -= p.l_align_tolerance;
424  } else {
425  xmax += p.r_align_tolerance;
426  xmin -= p.min_gutter;
427  }
428  // Setup a vertical search for an aligned blob.
429  GridSearch<BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT> vsearch(this);
430  if (WithinTestRegion(2, x_start, start_y))
431  tprintf("Starting %s %s search at %d-%d,%d, search_size=%d, gutter=%d\n",
432  p.ragged ? "Ragged" : "Aligned", p.right_tab ? "Right" : "Left",
433  xmin, xmax, start_y, p.max_v_gap, p.min_gutter);
434  vsearch.StartVerticalSearch(xmin, xmax, start_y);
435  // result stores the best real return value.
436  BLOBNBOX* result = NULL;
437  // The backup_result is not a tab candidate and can be used if no
438  // real tab candidate result is found.
439  BLOBNBOX* backup_result = NULL;
440  // neighbour is the blob that is currently being investigated.
441  BLOBNBOX* neighbour = NULL;
442  while ((neighbour = vsearch.NextVerticalSearch(top_to_bottom)) != NULL) {
443  if (neighbour == bbox)
444  continue;
445  TBOX nbox = neighbour->bounding_box();
446  int n_y = (nbox.top() + nbox.bottom()) / 2;
447  if ((!top_to_bottom && n_y > start_y + p.max_v_gap) ||
448  (top_to_bottom && n_y < start_y - p.max_v_gap)) {
449  if (WithinTestRegion(2, x_start, start_y))
450  tprintf("Neighbour too far at (%d,%d)->(%d,%d)\n",
451  nbox.left(), nbox.bottom(), nbox.right(), nbox.top());
452  break; // Gone far enough.
453  }
454  // It is CRITICAL to ensure that forward progress is made, (strictly
455  // in/decreasing n_y) or the caller could loop infinitely, while
456  // waiting for a sequence of blobs in a line to end.
457  // NextVerticalSearch alone does not guarantee this, as there may be
458  // more than one blob in a grid cell. See comment in AlignTabs.
459  if ((n_y < start_y) != top_to_bottom || nbox.y_overlap(box))
460  continue; // Only look in the required direction.
461  if (result != NULL && result->bounding_box().y_gap(nbox) > gridsize())
462  return result; // This result is clear.
463  if (backup_result != NULL && p.ragged && result == NULL &&
464  backup_result->bounding_box().y_gap(nbox) > gridsize())
465  return backup_result; // This result is clear.
466 
467  // If the neighbouring blob is the wrong side of a separator line, then it
468  // "doesn't exist" as far as we are concerned.
469  int x_at_n_y = x_start + (n_y - start_y) * p.vertical.x() / p.vertical.y();
470  if (x_at_n_y < neighbour->left_crossing_rule() ||
471  x_at_n_y > neighbour->right_crossing_rule())
472  continue; // Separator line in the way.
473  int n_left = nbox.left();
474  int n_right = nbox.right();
475  int n_x = p.right_tab ? n_right : n_left;
476  if (WithinTestRegion(2, x_start, start_y))
477  tprintf("neighbour at (%d,%d)->(%d,%d), n_x=%d, n_y=%d, xatn=%d\n",
478  nbox.left(), nbox.bottom(), nbox.right(), nbox.top(),
479  n_x, n_y, x_at_n_y);
480  if (p.right_tab &&
481  n_left < x_at_n_y + p.min_gutter &&
482  n_right > x_at_n_y + p.r_align_tolerance &&
483  (p.ragged || n_left < x_at_n_y + p.gutter_fraction * nbox.height())) {
484  // In the gutter so end of line.
485  if (bbox->right_tab_type() >= TT_MAYBE_ALIGNED)
487  *end_y = top_to_bottom ? nbox.top() : nbox.bottom();
488  if (WithinTestRegion(2, x_start, start_y))
489  tprintf("gutter\n");
490  return NULL;
491  }
492  if (!p.right_tab &&
493  n_left < x_at_n_y - p.l_align_tolerance &&
494  n_right > x_at_n_y - p.min_gutter &&
495  (p.ragged || n_right > x_at_n_y - p.gutter_fraction * nbox.height())) {
496  // In the gutter so end of line.
497  if (bbox->left_tab_type() >= TT_MAYBE_ALIGNED)
499  *end_y = top_to_bottom ? nbox.top() : nbox.bottom();
500  if (WithinTestRegion(2, x_start, start_y))
501  tprintf("gutter\n");
502  return NULL;
503  }
504  if ((p.right_tab && neighbour->leader_on_right()) ||
505  (!p.right_tab && neighbour->leader_on_left()))
506  continue; // Neigbours of leaders are not allowed to be used.
507  if (n_x <= x_at_n_y + p.r_align_tolerance &&
508  n_x >= x_at_n_y - p.l_align_tolerance) {
509  // Aligned so keep it. If it is a marked tab save it as result,
510  // otherwise keep it as backup_result to return in case of later failure.
511  if (WithinTestRegion(2, x_start, start_y))
512  tprintf("aligned, seeking%d, l=%d, r=%d\n",
513  p.right_tab, neighbour->left_tab_type(),
514  neighbour->right_tab_type());
515  TabType n_type = p.right_tab ? neighbour->right_tab_type()
516  : neighbour->left_tab_type();
517  if (n_type != TT_NONE && (p.ragged || n_type != TT_MAYBE_RAGGED)) {
518  if (result == NULL) {
519  result = neighbour;
520  } else {
521  // Keep the closest neighbour by Euclidean distance.
522  // This prevents it from picking a tab blob in another column.
523  const TBOX& old_box = result->bounding_box();
524  int x_diff = p.right_tab ? old_box.right() : old_box.left();
525  x_diff -= x_at_n_y;
526  int y_diff = (old_box.top() + old_box.bottom()) / 2 - start_y;
527  int old_dist = x_diff * x_diff + y_diff * y_diff;
528  x_diff = n_x - x_at_n_y;
529  y_diff = n_y - start_y;
530  int new_dist = x_diff * x_diff + y_diff * y_diff;
531  if (new_dist < old_dist)
532  result = neighbour;
533  }
534  } else if (backup_result == NULL) {
535  if (WithinTestRegion(2, x_start, start_y))
536  tprintf("Backup\n");
537  backup_result = neighbour;
538  } else {
539  TBOX backup_box = backup_result->bounding_box();
540  if ((p.right_tab && backup_box.right() < nbox.right()) ||
541  (!p.right_tab && backup_box.left() > nbox.left())) {
542  if (WithinTestRegion(2, x_start, start_y))
543  tprintf("Better backup\n");
544  backup_result = neighbour;
545  }
546  }
547  }
548  }
549  return result != NULL ? result : backup_result;
550 }
551 
552 } // namespace tesseract.
553