tesseract  5.0.0-alpha-619-ge9db
tabfind.h
Go to the documentation of this file.
1 // File: tabfind.h
3 // Description: Subclass of BBGrid to find tabstops.
4 // Author: Ray Smith
5 //
6 // (C) Copyright 2008, Google Inc.
7 // Licensed under the Apache License, Version 2.0 (the "License");
8 // you may not use this file except in compliance with the License.
9 // You may obtain a copy of the License at
10 // http://www.apache.org/licenses/LICENSE-2.0
11 // Unless required by applicable law or agreed to in writing, software
12 // distributed under the License is distributed on an "AS IS" BASIS,
13 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 // See the License for the specific language governing permissions and
15 // limitations under the License.
16 //
18 
19 #ifndef TESSERACT_TEXTORD_TABFIND_H_
20 #define TESSERACT_TEXTORD_TABFIND_H_
21 
22 #include <functional> // for std::function
23 #include "alignedblob.h"
24 #include "tabvector.h"
25 #include "linefind.h"
26 
27 class BLOBNBOX;
28 class BLOBNBOX_LIST;
29 class TO_BLOCK;
30 class ScrollView;
31 struct Pix;
32 
33 namespace tesseract {
34 
35 using WidthCallback = std::function<bool(int)>;
36 
37 struct AlignedBlobParams;
38 class ColPartitionGrid;
39 
41 const int kColumnWidthFactor = 20;
42 
52 class TabFind : public AlignedBlob {
53  public:
54  TabFind(int gridsize, const ICOORD& bleft, const ICOORD& tright,
55  TabVector_LIST* vlines, int vertical_x, int vertical_y,
56  int resolution);
57  ~TabFind() override;
58 
67  void InsertBlobsToGrid(bool h_spread, bool v_spread,
68  BLOBNBOX_LIST* blobs,
70 
78  bool InsertBlob(bool h_spread, bool v_spread, BLOBNBOX* blob,
80  // Calls SetBlobRuleEdges for all the blobs in the given block.
81  void SetBlockRuleEdges(TO_BLOCK* block);
82  // Sets the left and right rule and crossing_rules for the blobs in the given
83  // list by finding the next outermost tabvectors for each blob.
84  void SetBlobRuleEdges(BLOBNBOX_LIST* blobs);
85 
86  // Returns the gutter width of the given TabVector between the given y limits.
87  // Also returns x-shift to be added to the vector to clear any intersecting
88  // blobs. The shift is deducted from the returned gutter.
89  // If ignore_unmergeables is true, then blobs of UnMergeableType are
90  // ignored as if they don't exist. (Used for text on image.)
91  // max_gutter_width is used as the maximum width worth searching for in case
92  // there is nothing near the TabVector.
93  int GutterWidth(int bottom_y, int top_y, const TabVector& v,
94  bool ignore_unmergeables, int max_gutter_width,
95  int* required_shift);
99  void GutterWidthAndNeighbourGap(int tab_x, int mean_height,
100  int max_gutter, bool left,
101  BLOBNBOX* bbox, int* gutter_width,
102  int* neighbour_gap);
103 
110  int RightEdgeForBox(const TBOX& box, bool crossing, bool extended);
114  int LeftEdgeForBox(const TBOX& box, bool crossing, bool extended);
115 
132  TabVector* RightTabForBox(const TBOX& box, bool crossing, bool extended);
136  TabVector* LeftTabForBox(const TBOX& box, bool crossing, bool extended);
137 
142  bool CommonWidth(int width);
147  static bool DifferentSizes(int size1, int size2);
152  static bool VeryDifferentSizes(int size1, int size2);
153 
158  return width_cb_;
159  }
160 
164  const ICOORD& image_origin() const {
165  return image_origin_;
166  }
167 
168  protected:
172  TabVector_LIST* vectors() {
173  return &vectors_;
174  }
175  TabVector_LIST* dead_vectors() {
176  return &dead_vectors_;
177  }
178 
186  bool FindTabVectors(TabVector_LIST* hlines,
187  BLOBNBOX_LIST* image_blobs, TO_BLOCK* block,
188  int min_gutter_width, double tabfind_aligned_gap_fraction,
189  ColPartitionGrid* part_grid,
190  FCOORD* deskew, FCOORD* reskew);
191 
192  // Top-level function to not find TabVectors in an input page block,
193  // but setup for single column mode.
194  void DontFindTabVectors(BLOBNBOX_LIST* image_blobs,
195  TO_BLOCK* block, FCOORD* deskew, FCOORD* reskew);
196 
197  // Cleans up the lists of blobs in the block ready for use by TabFind.
198  // Large blobs that look like text are moved to the main blobs list.
199  // Main blobs that are superseded by the image blobs are deleted.
200  void TidyBlobs(TO_BLOCK* block);
201 
202  // Helper function to setup search limits for *TabForBox.
203  void SetupTabSearch(int x, int y, int* min_key, int* max_key);
204 
209 
210  // First part of FindTabVectors, which may be used twice if the text
211  // is mostly of vertical alignment. If find_vertical_text flag is
212  // true, this finds vertical textlines in possibly rotated blob space.
213  // In other words, when the page has mostly vertical lines and is rotated,
214  // setting this to true will find horizontal lines on the page.
215  // tabfind_aligned_gap_fraction should be the value of parameter
216  // textord_tabfind_aligned_gap_fraction
217  ScrollView* FindInitialTabVectors(BLOBNBOX_LIST* image_blobs,
218  int min_gutter_width,
219  double tabfind_aligned_gap_fraction,
220  TO_BLOCK* block);
221 
222  // Apply the given rotation to the given list of blobs.
223  static void RotateBlobList(const FCOORD& rotation, BLOBNBOX_LIST* blobs);
224 
225  // Flip the vertical and horizontal lines and rotate the grid ready
226  // for working on the rotated image.
227  // The min_gutter_width will be adjusted to the median gutter width between
228  // vertical tabs to set a better threshold for tabboxes in the 2nd pass.
229  void ResetForVerticalText(const FCOORD& rotate, const FCOORD& rerotate,
230  TabVector_LIST* horizontal_lines,
231  int* min_gutter_width);
232 
233  // Clear the grid and get rid of the tab vectors, but not separators,
234  // ready to start again.
235  void Reset();
236 
237  // Reflect the separator tab vectors and the grids in the y-axis.
238  // Can only be called after Reset!
239  void ReflectInYAxis();
240 
241  private:
242  // For each box in the grid, decide whether it is a candidate tab-stop,
243  // and if so add it to the left and right tab boxes.
244  // tabfind_aligned_gap_fraction should be the value of parameter
245  // textord_tabfind_aligned_gap_fraction
246  ScrollView* FindTabBoxes(int min_gutter_width,
247  double tabfind_aligned_gap_fraction);
248 
249  // Return true if this box looks like a candidate tab stop, and set
250  // the appropriate tab type(s) to TT_UNCONFIRMED.
251  // tabfind_aligned_gap_fraction should be the value of parameter
252  // textord_tabfind_aligned_gap_fraction
253  bool TestBoxForTabs(BLOBNBOX* bbox, int min_gutter_width,
254  double tabfind_aligned_gap_fraction);
255 
256  // Returns true if there is nothing in the rectangle of width min_gutter to
257  // the left of bbox.
258  bool ConfirmRaggedLeft(BLOBNBOX* bbox, int min_gutter);
259  // Returns true if there is nothing in the rectangle of width min_gutter to
260  // the right of bbox.
261  bool ConfirmRaggedRight(BLOBNBOX* bbox, int min_gutter);
262  // Returns true if there is nothing in the given search_box that vertically
263  // overlaps target_box other than target_box itself.
264  bool NothingYOverlapsInBox(const TBOX& search_box, const TBOX& target_box);
265 
266  // Fills the list of TabVector with the tabstops found in the grid,
267  // and estimates the logical vertical direction.
268  void FindAllTabVectors(int min_gutter_width);
269  // Helper for FindAllTabVectors finds the vectors of a particular type.
270  int FindTabVectors(int search_size_multiple,
271  TabAlignment alignment,
272  int min_gutter_width,
273  TabVector_LIST* vectors,
274  int* vertical_x, int* vertical_y);
275  // Finds a vector corresponding to a tabstop running through the
276  // given box of the given alignment type.
277  // search_size_multiple is a multiple of height used to control
278  // the size of the search.
279  // vertical_x and y are updated with an estimate of the real
280  // vertical direction. (skew finding.)
281  // Returns nullptr if no decent tabstop can be found.
282  TabVector* FindTabVector(int search_size_multiple, int min_gutter_width,
283  TabAlignment alignment,
284  BLOBNBOX* bbox,
285  int* vertical_x, int* vertical_y);
286 
287  // Set the vertical_skew_ member from the given vector and refit
288  // all vectors parallel to the skew vector.
289  void SetVerticalSkewAndParallelize(int vertical_x, int vertical_y);
290 
291  // Sort all the current vectors using the vertical_skew_ vector.
292  void SortVectors();
293 
294  // Evaluate all the current tab vectors.
295  void EvaluateTabs();
296 
297  // Trace textlines from one side to the other of each tab vector, saving
298  // the most frequent column widths found in a list so that a given width
299  // can be tested for being a common width with a simple callback function.
300  void ComputeColumnWidths(ScrollView* tab_win,
301  ColPartitionGrid* part_grid);
302 
303  // Finds column width and:
304  // if col_widths is not null (pass1):
305  // pair-up tab vectors with existing ColPartitions and accumulate widths.
306  // else (pass2):
307  // find the largest real partition width for each recorded column width,
308  // to be used as the minimum acceptable width.
309  void ApplyPartitionsToColumnWidths(ColPartitionGrid* part_grid,
310  STATS* col_widths);
311 
312  // Helper makes the list of common column widths in column_widths_ from the
313  // input col_widths. Destroys the content of col_widths by repeatedly
314  // finding the mode and erasing the peak.
315  void MakeColumnWidths(int col_widths_size, STATS* col_widths);
316 
317  // Mark blobs as being in a vertical text line where that is the case.
318  void MarkVerticalText();
319 
320  // Returns the median gutter width between pairs of matching tab vectors
321  // assuming they are sorted left-to-right. If there are too few data
322  // points (< kMinLinesInColumn), then 0 is returned.
323  int FindMedianGutterWidth(TabVector_LIST* tab_vectors);
324 
325  // Find the next adjacent (to left or right) blob on this text line,
326  // with the constraint that it must vertically significantly overlap
327  // the [top_y, bottom_y] range.
328  // If ignore_images is true, then blobs with aligned_text() < 0 are treated
329  // as if they do not exist.
330  BLOBNBOX* AdjacentBlob(const BLOBNBOX* bbox,
331  bool look_left, bool ignore_images,
332  double min_overlap_fraction,
333  int gap_limit, int top_y, int bottom_y);
334 
335  // Add a bi-directional partner relationship between the left
336  // and the right. If one (or both) of the vectors is a separator,
337  // extend a nearby extendable vector or create a new one of the
338  // correct type, using the given left or right blob as a guide.
339  void AddPartnerVector(BLOBNBOX* left_blob, BLOBNBOX* right_blob,
340  TabVector* left, TabVector* right);
341 
346  void CleanupTabs();
347 
353  bool Deskew(TabVector_LIST* hlines, BLOBNBOX_LIST* image_blobs,
354  TO_BLOCK* block, FCOORD* deskew, FCOORD* reskew);
355 
356  // Compute the rotation required to deskew, and its inverse rotation.
357  void ComputeDeskewVectors(FCOORD* deskew, FCOORD* reskew);
358 
363  void ApplyTabConstraints();
364 
365  protected:
368  private:
369  ICOORD image_origin_;
370  TabVector_LIST vectors_;
371  TabVector_IT v_it_;
372  TabVector_LIST dead_vectors_;
373  // List of commonly occurring width ranges with x=min and y=max.
374  ICOORDELT_LIST column_widths_;
375 
376  WidthCallback width_cb_;
377  // Sets of bounding boxes that are candidate tab stops.
378  GenericVector<BLOBNBOX*> left_tab_boxes_;
379  GenericVector<BLOBNBOX*> right_tab_boxes_;
380 };
381 
382 } // namespace tesseract.
383 
384 #endif // TESSERACT_TEXTORD_TABFIND_H_
ScrollView
Definition: scrollview.h:97
tesseract::TabVector
Definition: tabvector.h:111
tesseract::TabFind::Reset
void Reset()
Definition: tabfind.cpp:1345
tesseract::TabFind::FindTabVectors
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:422
tesseract::TabFind::SetBlobRuleEdges
void SetBlobRuleEdges(BLOBNBOX_LIST *blobs)
Definition: tabfind.cpp:142
linefind.h
tesseract::kColumnWidthFactor
const int kColumnWidthFactor
Definition: tabfind.h:41
ICOORD
integer coordinate
Definition: points.h:30
tesseract::WidthCallback
std::function< bool(int)> WidthCallback
Definition: tabfind.h:35
TO_BLOCK
Definition: blobbox.h:691
tesseract::TabFind::SetupTabSearch
void SetupTabSearch(int x, int y, int *min_key, int *max_key)
Definition: tabfind.cpp:490
tesseract::TabFind::GutterWidthAndNeighbourGap
void GutterWidthAndNeighbourGap(int tab_x, int mean_height, int max_gutter, bool left, BLOBNBOX *bbox, int *gutter_width, int *neighbour_gap)
Definition: tabfind.cpp:208
FCOORD
Definition: points.h:187
tesseract::TabFind::InsertBlobsToGrid
void InsertBlobsToGrid(bool h_spread, bool v_spread, BLOBNBOX_LIST *blobs, BBGrid< BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT > *grid)
Definition: tabfind.cpp:91
BLOBNBOX
Definition: blobbox.h:142
tesseract::GridBase::tright
const ICOORD & tright() const
Definition: bbgrid.h:75
tesseract::TabFind::GutterWidth
int GutterWidth(int bottom_y, int top_y, const TabVector &v, bool ignore_unmergeables, int max_gutter_width, int *required_shift)
Definition: tabfind.cpp:161
tesseract::TabFind::FindInitialTabVectors
ScrollView * FindInitialTabVectors(BLOBNBOX_LIST *image_blobs, int min_gutter_width, double tabfind_aligned_gap_fraction, TO_BLOCK *block)
Definition: tabfind.cpp:514
tesseract::TabFind::ReflectInYAxis
void ReflectInYAxis()
Definition: tabfind.cpp:1356
tesseract::TabFind::RightEdgeForBox
int RightEdgeForBox(const TBOX &box, bool crossing, bool extended)
Definition: tabfind.cpp:281
tesseract::TabFind::CommonWidth
bool CommonWidth(int width)
Definition: tabfind.cpp:394
tesseract::TabFind::resolution_
int resolution_
Of source image in pixels per inch.
Definition: tabfind.h:367
tesseract::TabFind::LeftEdgeForBox
int LeftEdgeForBox(const TBOX &box, bool crossing, bool extended)
Definition: tabfind.cpp:286
tesseract::TabFind::vectors
TabVector_LIST * vectors()
Definition: tabfind.h:172
tesseract::AlignedBlob
Definition: alignedblob.h:81
tesseract::TabFind::DontFindTabVectors
void DontFindTabVectors(BLOBNBOX_LIST *image_blobs, TO_BLOCK *block, FCOORD *deskew, FCOORD *reskew)
Definition: tabfind.cpp:452
tesseract::TabFind::DifferentSizes
static bool DifferentSizes(int size1, int size2)
Definition: tabfind.cpp:407
tesseract::BBGrid< BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT >
tesseract
Definition: baseapi.h:65
tesseract::TabFind::VeryDifferentSizes
static bool VeryDifferentSizes(int size1, int size2)
Definition: tabfind.cpp:413
STATS
Definition: statistc.h:30
tesseract::TabFind::vertical_skew_
ICOORD vertical_skew_
Estimate of true vertical in this image.
Definition: tabfind.h:366
tesseract::TabFind::RightTabForBox
TabVector * RightTabForBox(const TBOX &box, bool crossing, bool extended)
Definition: tabfind.cpp:304
tesseract::TabFind::TabFind
TabFind(int gridsize, const ICOORD &bleft, const ICOORD &tright, TabVector_LIST *vlines, int vertical_x, int vertical_y, int resolution)
Definition: tabfind.cpp:65
GenericVector< BLOBNBOX * >
tesseract::AlignedBlobParams
Definition: alignedblob.h:42
tesseract::TabFind::SetBlockRuleEdges
void SetBlockRuleEdges(TO_BLOCK *block)
Definition: tabfind.cpp:133
tesseract::GridBase::gridsize
int gridsize() const
Definition: bbgrid.h:63
tesseract::TabFind::~TabFind
~TabFind() override
Definition: tabfind.cpp:79
tesseract::TabFind::LeftTabForBox
TabVector * LeftTabForBox(const TBOX &box, bool crossing, bool extended)
Definition: tabfind.cpp:348
tesseract::TabFind::DisplayTabVectors
ScrollView * DisplayTabVectors(ScrollView *tab_win)
Definition: tabfind.cpp:497
alignedblob.h
tesseract::TabFind::WidthCB
WidthCallback WidthCB()
Definition: tabfind.h:157
tesseract::TabFind::ResetForVerticalText
void ResetForVerticalText(const FCOORD &rotate, const FCOORD &rerotate, TabVector_LIST *horizontal_lines, int *min_gutter_width)
Definition: tabfind.cpp:1300
tesseract::TabFind
Definition: tabfind.h:52
tesseract::ColPartitionGrid
Definition: colpartitiongrid.h:32
tesseract::TabFind::InsertBlob
bool InsertBlob(bool h_spread, bool v_spread, BLOBNBOX *blob, BBGrid< BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT > *grid)
Definition: tabfind.cpp:118
tesseract::TabFind::dead_vectors
TabVector_LIST * dead_vectors()
Definition: tabfind.h:175
tesseract::TabFind::image_origin
const ICOORD & image_origin() const
Definition: tabfind.h:164
tesseract::TabAlignment
TabAlignment
Definition: tabvector.h:44
tesseract::TabFind::TidyBlobs
void TidyBlobs(TO_BLOCK *block)
Definition: tabfind.cpp:465
tabvector.h
tesseract::GridBase::bleft
const ICOORD & bleft() const
Definition: bbgrid.h:72
TBOX
Definition: rect.h:33
tesseract::TabFind::RotateBlobList
static void RotateBlobList(const FCOORD &rotation, BLOBNBOX_LIST *blobs)
Definition: tabfind.cpp:1256