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
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");
86 double_VAR(textord_tabfind_aligned_gap_fraction, 0.75,
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);
99 width_cb_ = NewPermanentTessCallback(this, &TabFind::CommonWidth);
100 }
101
102 TabFind::~TabFind() {
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.
158 void TabFind::SetBlockRuleEdges(TO_BLOCK* 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);
455 TabVector::MergeSimilarTabVectors(vertical_skew_, &vectors_, this);
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
463 if (textord_tabfind_show_finaltabs) {
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.
493 void TabFind::TidyBlobs(TO_BLOCK* block) {
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
525 ScrollView* TabFind::DisplayTabVectors(ScrollView* tab_win) {
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) {
545 if (textord_tabfind_show_initialtabs) {
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
556 TabVector::MergeSimilarTabVectors(vertical_skew_, &vectors_, this);
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
607 if (textord_tabfind_show_initialtabs) {
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) {
770 bbox->set_left_tab_type(TT_MAYBE_ALIGNED);
771 } else if (maybe_ragged_left && ConfirmRaggedLeft(bbox, min_ragged_gutter)) {
772 bbox->set_left_tab_type(TT_MAYBE_RAGGED);
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) {
777 bbox->set_right_tab_type(TT_MAYBE_ALIGNED);
778 } else if (maybe_ragged_right &&
779 ConfirmRaggedRight(bbox, min_ragged_gutter)) {
780 bbox->set_right_tab_type(TT_MAYBE_RAGGED);
781 } else {
782 bbox->set_right_tab_type(TT_NONE);
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)
853 bbox->set_left_tab_type(TT_MAYBE_ALIGNED);
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)
858 bbox->set_right_tab_type(TT_MAYBE_ALIGNED);
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);
871 FindTabVectors(kMaxRaggedSearch, TA_LEFT_RAGGED, min_gutter_width,
872 &dummy_vectors, &vertical_x, &vertical_y);
873 FindTabVectors(kMaxRaggedSearch, TA_RIGHT_RAGGED, min_gutter_width,
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);
934 if (textord_debug_tabfind)
935 tprintf("Vertical skew vector=(%d,%d)\n",
936 vertical_skew_.x(), vertical_skew_.y());
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);
1058 if (textord_debug_tabfind)
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() {
1069 if (textord_debug_tabfind)
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()) {
1078 blob->set_region_type(BRT_VERT_TEXT);
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 }
1099 if (textord_debug_tabfind)
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.
1374 void TabFind::Reset() {
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!
1385 void TabFind::ReflectInYAxis() {
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.