tesseract  v4.0.0-17-g361f3264
Open Source OCR Engine
tabfind.h
1 // File: tabfind.h
3 // Description: Subclass of BBGrid to find tabstops.
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 #ifndef TESSERACT_TEXTORD_TABFIND_H_
21 #define TESSERACT_TEXTORD_TABFIND_H_
22 
23 #include "alignedblob.h"
24 #include "tesscallback.h"
25 #include "tabvector.h"
26 #include "linefind.h"
27 
28 class BLOBNBOX;
29 class BLOBNBOX_LIST;
30 class TO_BLOCK;
31 class ScrollView;
32 struct Pix;
33 
34 namespace tesseract {
35 
37 
38 struct AlignedBlobParams;
39 class ColPartitionGrid;
40 
42 const int kColumnWidthFactor = 20;
43 
53 class TabFind : public AlignedBlob {
54  public:
55  TabFind(int gridsize, const ICOORD& bleft, const ICOORD& tright,
56  TabVector_LIST* vlines, int vertical_x, int vertical_y,
57  int resolution);
58  virtual ~TabFind();
59 
68  void InsertBlobsToGrid(bool h_spread, bool v_spread,
69  BLOBNBOX_LIST* blobs,
71 
79  bool InsertBlob(bool h_spread, bool v_spread, BLOBNBOX* blob,
81  // Calls SetBlobRuleEdges for all the blobs in the given block.
82  void SetBlockRuleEdges(TO_BLOCK* block);
83  // Sets the left and right rule and crossing_rules for the blobs in the given
84  // list by finding the next outermost tabvectors for each blob.
85  void SetBlobRuleEdges(BLOBNBOX_LIST* blobs);
86 
87  // Returns the gutter width of the given TabVector between the given y limits.
88  // Also returns x-shift to be added to the vector to clear any intersecting
89  // blobs. The shift is deducted from the returned gutter.
90  // If ignore_unmergeables is true, then blobs of UnMergeableType are
91  // ignored as if they don't exist. (Used for text on image.)
92  // max_gutter_width is used as the maximum width worth searching for in case
93  // there is nothing near the TabVector.
94  int GutterWidth(int bottom_y, int top_y, const TabVector& v,
95  bool ignore_unmergeables, int max_gutter_width,
96  int* required_shift);
100  void GutterWidthAndNeighbourGap(int tab_x, int mean_height,
101  int max_gutter, bool left,
102  BLOBNBOX* bbox, int* gutter_width,
103  int* neighbour_gap);
104 
111  int RightEdgeForBox(const TBOX& box, bool crossing, bool extended);
115  int LeftEdgeForBox(const TBOX& box, bool crossing, bool extended);
116 
133  TabVector* RightTabForBox(const TBOX& box, bool crossing, bool extended);
137  TabVector* LeftTabForBox(const TBOX& box, bool crossing, bool extended);
138 
143  bool CommonWidth(int width);
148  static bool DifferentSizes(int size1, int size2);
153  static bool VeryDifferentSizes(int size1, int size2);
154 
159  return width_cb_;
160  }
161 
165  const ICOORD& image_origin() const {
166  return image_origin_;
167  }
168 
169  protected:
173  TabVector_LIST* vectors() {
174  return &vectors_;
175  }
176  TabVector_LIST* dead_vectors() {
177  return &dead_vectors_;
178  }
179 
187  bool FindTabVectors(TabVector_LIST* hlines,
188  BLOBNBOX_LIST* image_blobs, TO_BLOCK* block,
189  int min_gutter_width, double tabfind_aligned_gap_fraction,
190  ColPartitionGrid* part_grid,
191  FCOORD* deskew, FCOORD* reskew);
192 
193  // Top-level function to not find TabVectors in an input page block,
194  // but setup for single column mode.
195  void DontFindTabVectors(BLOBNBOX_LIST* image_blobs,
196  TO_BLOCK* block, FCOORD* deskew, FCOORD* reskew);
197 
198  // Cleans up the lists of blobs in the block ready for use by TabFind.
199  // Large blobs that look like text are moved to the main blobs list.
200  // Main blobs that are superseded by the image blobs are deleted.
201  void TidyBlobs(TO_BLOCK* block);
202 
203  // Helper function to setup search limits for *TabForBox.
204  void SetupTabSearch(int x, int y, int* min_key, int* max_key);
205 
210 
211  // First part of FindTabVectors, which may be used twice if the text
212  // is mostly of vertical alignment. If find_vertical_text flag is
213  // true, this finds vertical textlines in possibly rotated blob space.
214  // In other words, when the page has mostly vertical lines and is rotated,
215  // setting this to true will find horizontal lines on the page.
216  // tabfind_aligned_gap_fraction should be the value of parameter
217  // textord_tabfind_aligned_gap_fraction
218  ScrollView* FindInitialTabVectors(BLOBNBOX_LIST* image_blobs,
219  int min_gutter_width,
220  double tabfind_aligned_gap_fraction,
221  TO_BLOCK* block);
222 
223  // Apply the given rotation to the given list of blobs.
224  static void RotateBlobList(const FCOORD& rotation, BLOBNBOX_LIST* blobs);
225 
226  // Flip the vertical and horizontal lines and rotate the grid ready
227  // for working on the rotated image.
228  // The min_gutter_width will be adjusted to the median gutter width between
229  // vertical tabs to set a better threshold for tabboxes in the 2nd pass.
230  void ResetForVerticalText(const FCOORD& rotate, const FCOORD& rerotate,
231  TabVector_LIST* horizontal_lines,
232  int* min_gutter_width);
233 
234  // Clear the grid and get rid of the tab vectors, but not separators,
235  // ready to start again.
236  void Reset();
237 
238  // Reflect the separator tab vectors and the grids in the y-axis.
239  // Can only be called after Reset!
240  void ReflectInYAxis();
241 
242  private:
243  // For each box in the grid, decide whether it is a candidate tab-stop,
244  // and if so add it to the left and right tab boxes.
245  // tabfind_aligned_gap_fraction should be the value of parameter
246  // textord_tabfind_aligned_gap_fraction
247  ScrollView* FindTabBoxes(int min_gutter_width,
248  double tabfind_aligned_gap_fraction);
249 
250  // Return true if this box looks like a candidate tab stop, and set
251  // the appropriate tab type(s) to TT_UNCONFIRMED.
252  // tabfind_aligned_gap_fraction should be the value of parameter
253  // textord_tabfind_aligned_gap_fraction
254  bool TestBoxForTabs(BLOBNBOX* bbox, int min_gutter_width,
255  double tabfind_aligned_gap_fraction);
256 
257  // Returns true if there is nothing in the rectangle of width min_gutter to
258  // the left of bbox.
259  bool ConfirmRaggedLeft(BLOBNBOX* bbox, int min_gutter);
260  // Returns true if there is nothing in the rectangle of width min_gutter to
261  // the right of bbox.
262  bool ConfirmRaggedRight(BLOBNBOX* bbox, int min_gutter);
263  // Returns true if there is nothing in the given search_box that vertically
264  // overlaps target_box other than target_box itself.
265  bool NothingYOverlapsInBox(const TBOX& search_box, const TBOX& target_box);
266 
267  // Fills the list of TabVector with the tabstops found in the grid,
268  // and estimates the logical vertical direction.
269  void FindAllTabVectors(int min_gutter_width);
270  // Helper for FindAllTabVectors finds the vectors of a particular type.
271  int FindTabVectors(int search_size_multiple,
272  TabAlignment alignment,
273  int min_gutter_width,
274  TabVector_LIST* vectors,
275  int* vertical_x, int* vertical_y);
276  // Finds a vector corresponding to a tabstop running through the
277  // given box of the given alignment type.
278  // search_size_multiple is a multiple of height used to control
279  // the size of the search.
280  // vertical_x and y are updated with an estimate of the real
281  // vertical direction. (skew finding.)
282  // Returns nullptr if no decent tabstop can be found.
283  TabVector* FindTabVector(int search_size_multiple, int min_gutter_width,
284  TabAlignment alignment,
285  BLOBNBOX* bbox,
286  int* vertical_x, int* vertical_y);
287 
288  // Set the vertical_skew_ member from the given vector and refit
289  // all vectors parallel to the skew vector.
290  void SetVerticalSkewAndParallelize(int vertical_x, int vertical_y);
291 
292  // Sort all the current vectors using the vertical_skew_ vector.
293  void SortVectors();
294 
295  // Evaluate all the current tab vectors.
296  void EvaluateTabs();
297 
298  // Trace textlines from one side to the other of each tab vector, saving
299  // the most frequent column widths found in a list so that a given width
300  // can be tested for being a common width with a simple callback function.
301  void ComputeColumnWidths(ScrollView* tab_win,
302  ColPartitionGrid* part_grid);
303 
304  // Finds column width and:
305  // if col_widths is not null (pass1):
306  // pair-up tab vectors with existing ColPartitions and accumulate widths.
307  // else (pass2):
308  // find the largest real partition width for each recorded column width,
309  // to be used as the minimum acceptable width.
311  STATS* col_widths);
312 
313  // Helper makes the list of common column widths in column_widths_ from the
314  // input col_widths. Destroys the content of col_widths by repeatedly
315  // finding the mode and erasing the peak.
316  void MakeColumnWidths(int col_widths_size, STATS* col_widths);
317 
318  // Mark blobs as being in a vertical text line where that is the case.
319  void MarkVerticalText();
320 
321  // Returns the median gutter width between pairs of matching tab vectors
322  // assuming they are sorted left-to-right. If there are too few data
323  // points (< kMinLinesInColumn), then 0 is returned.
324  int FindMedianGutterWidth(TabVector_LIST* tab_vectors);
325 
326  // Find the next adjacent (to left or right) blob on this text line,
327  // with the constraint that it must vertically significantly overlap
328  // the [top_y, bottom_y] range.
329  // If ignore_images is true, then blobs with aligned_text() < 0 are treated
330  // as if they do not exist.
331  BLOBNBOX* AdjacentBlob(const BLOBNBOX* bbox,
332  bool look_left, bool ignore_images,
333  double min_overlap_fraction,
334  int gap_limit, int top_y, int bottom_y);
335 
336  // Add a bi-directional partner relationship between the left
337  // and the right. If one (or both) of the vectors is a separator,
338  // extend a nearby extendable vector or create a new one of the
339  // correct type, using the given left or right blob as a guide.
340  void AddPartnerVector(BLOBNBOX* left_blob, BLOBNBOX* right_blob,
341  TabVector* left, TabVector* right);
342 
347  void CleanupTabs();
348 
354  bool Deskew(TabVector_LIST* hlines, BLOBNBOX_LIST* image_blobs,
355  TO_BLOCK* block, FCOORD* deskew, FCOORD* reskew);
356 
357  // Compute the rotation required to deskew, and its inverse rotation.
358  void ComputeDeskewVectors(FCOORD* deskew, FCOORD* reskew);
359 
364  void ApplyTabConstraints();
365 
366  protected:
367  ICOORD vertical_skew_; //< Estimate of true vertical in this image.
368  int resolution_; //< Of source image in pixels per inch.
369  private:
370  ICOORD image_origin_; //< Top-left of image in deskewed coords
371  TabVector_LIST vectors_; //< List of rule line and tabstops.
372  TabVector_IT v_it_; //< Iterator for searching vectors_.
373  TabVector_LIST dead_vectors_; //< Separators and unpartnered tab vectors.
374  // List of commonly occurring width ranges with x=min and y=max.
375  ICOORDELT_LIST column_widths_; //< List of commonly occurring width ranges.
378  // Sets of bounding boxes that are candidate tab stops.
381 };
382 
383 } // namespace tesseract.
384 
385 #endif // TESSERACT_TEXTORD_TABFIND_H_
Definition: colpartitiongrid.h:33
ScrollView * FindTabBoxes(int min_gutter_width, double tabfind_aligned_gap_fraction)
Definition: tabfind.cpp:560
TabFind(int gridsize, const ICOORD &bleft, const ICOORD &tright, TabVector_LIST *vlines, int vertical_x, int vertical_y, int resolution)
Definition: tabfind.cpp:66
void SetVerticalSkewAndParallelize(int vertical_x, int vertical_y)
Definition: tabfind.cpp:908
ICOORD image_origin_
Definition: tabfind.h:370
bool Deskew(TabVector_LIST *hlines, BLOBNBOX_LIST *image_blobs, TO_BLOCK *block, FCOORD *deskew, FCOORD *reskew)
Definition: tabfind.cpp:1266
int GutterWidth(int bottom_y, int top_y, const TabVector &v, bool ignore_unmergeables, int max_gutter_width, int *required_shift)
Definition: tabfind.cpp:162
bool ConfirmRaggedRight(BLOBNBOX *bbox, int min_gutter)
Definition: tabfind.cpp:782
void SetupTabSearch(int x, int y, int *min_key, int *max_key)
Definition: tabfind.cpp:491
void ComputeColumnWidths(ScrollView *tab_win, ColPartitionGrid *part_grid)
Definition: tabfind.cpp:951
void AddPartnerVector(BLOBNBOX *left_blob, BLOBNBOX *right_blob, TabVector *left, TabVector *right)
Definition: tabfind.cpp:1189
Definition: alignedblob.h:81
TabAlignment
Definition: tabvector.h:45
void DontFindTabVectors(BLOBNBOX_LIST *image_blobs, TO_BLOCK *block, FCOORD *deskew, FCOORD *reskew)
Definition: tabfind.cpp:453
TabVector_LIST dead_vectors_
Definition: tabfind.h:373
ScrollView * FindInitialTabVectors(BLOBNBOX_LIST *image_blobs, int min_gutter_width, double tabfind_aligned_gap_fraction, TO_BLOCK *block)
Definition: tabfind.cpp:515
Definition: tabvector.h:112
GenericVector< BLOBNBOX * > left_tab_boxes_
Definition: tabfind.h:379
Definition: rect.h:34
void GutterWidthAndNeighbourGap(int tab_x, int mean_height, int max_gutter, bool left, BLOBNBOX *bbox, int *gutter_width, int *neighbour_gap)
Definition: tabfind.cpp:209
int FindMedianGutterWidth(TabVector_LIST *tab_vectors)
Definition: tabfind.cpp:1081
void SortVectors()
Definition: tabfind.cpp:924
int LeftEdgeForBox(const TBOX &box, bool crossing, bool extended)
Definition: tabfind.cpp:287
WidthCallback * width_cb_
Definition: tabfind.h:377
bool FindTabVectors(TabVector_LIST *hlines, BLOBNBOX_LIST *image_blobs, TO_BLOCK *block, int min_gutter_width, double tabfind_aligned_gap_fraction, ColPartitionGrid *part_grid, FCOORD *deskew, FCOORD *reskew)
Definition: tabfind.cpp:423
bool InsertBlob(bool h_spread, bool v_spread, BLOBNBOX *blob, BBGrid< BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT > *grid)
Definition: tabfind.cpp:119
void Reset()
Definition: tabfind.cpp:1346
Definition: baseapi.cpp:94
ICOORD vertical_skew_
Definition: tabfind.h:367
TabVector_IT v_it_
Definition: tabfind.h:372
void CleanupTabs()
Definition: tabfind.cpp:1239
static bool DifferentSizes(int size1, int size2)
Definition: tabfind.cpp:408
bool CommonWidth(int width)
Definition: tabfind.cpp:395
static void RotateBlobList(const FCOORD &rotation, BLOBNBOX_LIST *blobs)
Definition: tabfind.cpp:1257
bool TestBoxForTabs(BLOBNBOX *bbox, int min_gutter_width, double tabfind_aligned_gap_fraction)
Definition: tabfind.cpp:596
void ResetForVerticalText(const FCOORD &rotate, const FCOORD &rerotate, TabVector_LIST *horizontal_lines, int *min_gutter_width)
Definition: tabfind.cpp:1301
void FindAllTabVectors(int min_gutter_width)
Definition: tabfind.cpp:804
Definition: blobbox.h:144
Definition: scrollview.h:102
bool ConfirmRaggedLeft(BLOBNBOX *bbox, int min_gutter)
Definition: tabfind.cpp:773
const ICOORD & bleft() const
Definition: bbgrid.h:73
int gridsize() const
Definition: bbgrid.h:64
TabVector * RightTabForBox(const TBOX &box, bool crossing, bool extended)
Definition: tabfind.cpp:305
int resolution_
Definition: tabfind.h:368
virtual ~TabFind()
Definition: tabfind.cpp:79
Definition: baseapi.h:37
Definition: tesscallback.h:1673
void TidyBlobs(TO_BLOCK *block)
Definition: tabfind.cpp:466
void ApplyTabConstraints()
Definition: tabfind.cpp:1392
const ICOORD & image_origin() const
Definition: tabfind.h:165
WidthCallback * WidthCB()
Definition: tabfind.h:158
TabVector * LeftTabForBox(const TBOX &box, bool crossing, bool extended)
Definition: tabfind.cpp:349
TabVector * FindTabVector(int search_size_multiple, int min_gutter_width, TabAlignment alignment, BLOBNBOX *bbox, int *vertical_x, int *vertical_y)
Definition: tabfind.cpp:892
ICOORDELT_LIST column_widths_
Definition: tabfind.h:375
void ReflectInYAxis()
Definition: tabfind.cpp:1357
Definition: statistc.h:33
integer coordinate
Definition: points.h:32
ScrollView * DisplayTabVectors(ScrollView *tab_win)
Definition: tabfind.cpp:498
Definition: tabfind.h:53
void EvaluateTabs()
Definition: tabfind.cpp:930
Definition: alignedblob.h:42
void ComputeDeskewVectors(FCOORD *deskew, FCOORD *reskew)
Definition: tabfind.cpp:1381
void MarkVerticalText()
Definition: tabfind.cpp:1066
TabVector_LIST * dead_vectors()
Definition: tabfind.h:176
void MakeColumnWidths(int col_widths_size, STATS *col_widths)
Definition: tabfind.cpp:1030
void SetBlockRuleEdges(TO_BLOCK *block)
Definition: tabfind.cpp:134
int RightEdgeForBox(const TBOX &box, bool crossing, bool extended)
Definition: tabfind.cpp:282
Definition: blobbox.h:705
TabVector_LIST * vectors()
Definition: tabfind.h:173
static bool VeryDifferentSizes(int size1, int size2)
Definition: tabfind.cpp:414
bool NothingYOverlapsInBox(const TBOX &search_box, const TBOX &target_box)
Definition: tabfind.cpp:791
TabVector_LIST vectors_
Definition: tabfind.h:371
const ICOORD & tright() const
Definition: bbgrid.h:76
void InsertBlobsToGrid(bool h_spread, bool v_spread, BLOBNBOX_LIST *blobs, BBGrid< BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT > *grid)
Definition: tabfind.cpp:92
GenericVector< BLOBNBOX * > right_tab_boxes_
Definition: tabfind.h:380
Definition: points.h:189
void ApplyPartitionsToColumnWidths(ColPartitionGrid *part_grid, STATS *col_widths)
Definition: tabfind.cpp:980
BLOBNBOX * AdjacentBlob(const BLOBNBOX *bbox, bool look_left, bool ignore_images, double min_overlap_fraction, int gap_limit, int top_y, int bottom_y)
Definition: tabfind.cpp:1109
const int kColumnWidthFactor
Definition: tabfind.h:42
void SetBlobRuleEdges(BLOBNBOX_LIST *blobs)
Definition: tabfind.cpp:143