Tesseract 3.02

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

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.
78 void AlignedBlob::IncrementDebugPix() {
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.
110 gutter_fraction = kRaggedGapFraction;
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 }
118 min_points = kMinRaggedTabs;
119 } else {
120 gutter_fraction = kAlignedGapFraction;
121 l_align_tolerance = static_cast<int>(resolution * kAlignedFraction + 0.5);
122 r_align_tolerance = static_cast<int>(resolution * kAlignedFraction + 0.5);
123 min_points = kMinAlignedTabs;
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.
147 l_align_tolerance = MAX(kVLineAlignment, width);
148 r_align_tolerance = MAX(kVLineAlignment, width);
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
164 AlignedBlob::AlignedBlob(int gridsize,
165 const ICOORD& bleft, const ICOORD& tright)
166 : BlobGrid(gridsize, bleft, tright) {
167 }
168
169 AlignedBlob::~AlignedBlob() {
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;
177 return x >= textord_testregion_left && x <= textord_testregion_right &&
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.
188 GridSearch<BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT> gsearch(this);
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.
244 TabVector* AlignedBlob::FindVerticalAlignment(AlignedBlobParams align_params,
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)
486 bbox->set_right_tab_type(TT_DELETED);
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)
498 bbox->set_left_tab_type(TT_DELETED);
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