Tesseract  3.02
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
tabfind.h
Go to the documentation of this file.
1 
2 // 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 
29  "Force using vertical text page mode");
31  "find horizontal lines such as headers in vertical page mode");
33  "Fraction of textlines deemed vertical to use vertical page mode");
35  "Fraction of height used as a minimum gap for aligned blobs.");
36 
37 class BLOBNBOX;
38 class BLOBNBOX_LIST;
39 class TO_BLOCK;
40 class ScrollView;
41 struct Pix;
42 
43 namespace tesseract {
44 
46 
47 struct AlignedBlobParams;
48 class ColPartitionGrid;
49 
51 const int kColumnWidthFactor = 20;
52 
62 class TabFind : public AlignedBlob {
63  public:
64  TabFind(int gridsize, const ICOORD& bleft, const ICOORD& tright,
65  TabVector_LIST* vlines, int vertical_x, int vertical_y,
66  int resolution);
67  virtual ~TabFind();
68 
77  void InsertBlobsToGrid(bool h_spread, bool v_spread,
78  BLOBNBOX_LIST* blobs,
80 
88  bool InsertBlob(bool h_spread, bool v_spread, BLOBNBOX* blob,
90  // Calls SetBlobRuleEdges for all the blobs in the given block.
91  void SetBlockRuleEdges(TO_BLOCK* block);
92  // Sets the left and right rule and crossing_rules for the blobs in the given
93  // list by finding the next outermost tabvectors for each blob.
94  void SetBlobRuleEdges(BLOBNBOX_LIST* blobs);
95 
96  // Returns the gutter width of the given TabVector between the given y limits.
97  // Also returns x-shift to be added to the vector to clear any intersecting
98  // blobs. The shift is deducted from the returned gutter.
99  // If ignore_unmergeables is true, then blobs of UnMergeableType are
100  // ignored as if they don't exist. (Used for text on image.)
101  // max_gutter_width is used as the maximum width worth searching for in case
102  // there is nothing near the TabVector.
103  int GutterWidth(int bottom_y, int top_y, const TabVector& v,
104  bool ignore_unmergeables, int max_gutter_width,
105  int* required_shift);
109  void GutterWidthAndNeighbourGap(int tab_x, int mean_height,
110  int max_gutter, bool left,
111  BLOBNBOX* bbox, int* gutter_width,
112  int* neighbour_gap);
113 
120  int RightEdgeForBox(const TBOX& box, bool crossing, bool extended);
124  int LeftEdgeForBox(const TBOX& box, bool crossing, bool extended);
125 
142  TabVector* RightTabForBox(const TBOX& box, bool crossing, bool extended);
146  TabVector* LeftTabForBox(const TBOX& box, bool crossing, bool extended);
147 
152  bool CommonWidth(int width);
157  static bool DifferentSizes(int size1, int size2);
162  static bool VeryDifferentSizes(int size1, int size2);
163 
168  return width_cb_;
169  }
170 
174  const ICOORD& image_origin() const {
175  return image_origin_;
176  }
177 
178  protected:
182  TabVector_LIST* vectors() {
183  return &vectors_;
184  }
185  TabVector_LIST* dead_vectors() {
186  return &dead_vectors_;
187  }
188 
194  bool FindTabVectors(TabVector_LIST* hlines,
195  BLOBNBOX_LIST* image_blobs, TO_BLOCK* block,
196  int min_gutter_width,
197  ColPartitionGrid* part_grid,
198  FCOORD* deskew, FCOORD* reskew);
199 
200  // Top-level function to not find TabVectors in an input page block,
201  // but setup for single column mode.
202  void DontFindTabVectors(BLOBNBOX_LIST* image_blobs,
203  TO_BLOCK* block, FCOORD* deskew, FCOORD* reskew);
204 
205  // Cleans up the lists of blobs in the block ready for use by TabFind.
206  // Large blobs that look like text are moved to the main blobs list.
207  // Main blobs that are superseded by the image blobs are deleted.
208  void TidyBlobs(TO_BLOCK* block);
209 
210  // Helper function to setup search limits for *TabForBox.
211  void SetupTabSearch(int x, int y, int* min_key, int* max_key);
212 
217 
218  // First part of FindTabVectors, which may be used twice if the text
219  // is mostly of vertical alignment. If find_vertical_text flag is
220  // true, this finds vertical textlines in possibly rotated blob space.
221  // In other words, when the page has mostly vertical lines and is rotated,
222  // setting this to true will find horizontal lines on the page.
223  ScrollView* FindInitialTabVectors(BLOBNBOX_LIST* image_blobs,
224  int min_gutter_width, TO_BLOCK* block);
225 
226  // Apply the given rotation to the given list of blobs.
227  static void RotateBlobList(const FCOORD& rotation, BLOBNBOX_LIST* blobs);
228 
229  // Flip the vertical and horizontal lines and rotate the grid ready
230  // for working on the rotated image.
231  // The min_gutter_width will be adjusted to the median gutter width between
232  // vertical tabs to set a better threshold for tabboxes in the 2nd pass.
233  void ResetForVerticalText(const FCOORD& rotate, const FCOORD& rerotate,
234  TabVector_LIST* horizontal_lines,
235  int* min_gutter_width);
236 
237  // Clear the grid and get rid of the tab vectors, but not separators,
238  // ready to start again.
239  void Reset();
240 
241  // Reflect the separator tab vectors and the grids in the y-axis.
242  // Can only be called after Reset!
243  void ReflectInYAxis();
244 
245  private:
246  // For each box in the grid, decide whether it is a candidate tab-stop,
247  // and if so add it to the left and right tab boxes.
248  ScrollView* FindTabBoxes(int min_gutter_width);
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  bool TestBoxForTabs(BLOBNBOX* bbox, int min_gutter_width);
253 
254  // Returns true if there is nothing in the rectangle of width min_gutter to
255  // the left of bbox.
256  bool ConfirmRaggedLeft(BLOBNBOX* bbox, int min_gutter);
257  // Returns true if there is nothing in the rectangle of width min_gutter to
258  // the right of bbox.
259  bool ConfirmRaggedRight(BLOBNBOX* bbox, int min_gutter);
260  // Returns true if there is nothing in the given search_box that vertically
261  // overlaps target_box other than target_box itself.
262  bool NothingYOverlapsInBox(const TBOX& search_box, const TBOX& target_box);
263 
264  // Fills the list of TabVector with the tabstops found in the grid,
265  // and estimates the logical vertical direction.
266  void FindAllTabVectors(int min_gutter_width);
267  // Helper for FindAllTabVectors finds the vectors of a particular type.
268  int FindTabVectors(int search_size_multiple,
269  TabAlignment alignment,
270  int min_gutter_width,
271  TabVector_LIST* vectors,
272  int* vertical_x, int* vertical_y);
273  // Finds a vector corresponding to a tabstop running through the
274  // given box of the given alignment type.
275  // search_size_multiple is a multiple of height used to control
276  // the size of the search.
277  // vertical_x and y are updated with an estimate of the real
278  // vertical direction. (skew finding.)
279  // Returns NULL if no decent tabstop can be found.
280  TabVector* FindTabVector(int search_size_multiple, int min_gutter_width,
281  TabAlignment alignment,
282  BLOBNBOX* bbox,
283  int* vertical_x, int* vertical_y);
284 
285  // Set the vertical_skew_ member from the given vector and refit
286  // all vectors parallel to the skew vector.
287  void SetVerticalSkewAndParellelize(int vertical_x, int vertical_y);
288 
289  // Sort all the current vectors using the vertical_skew_ vector.
290  void SortVectors();
291 
292  // Evaluate all the current tab vectors.
293  void EvaluateTabs();
294 
295  // Trace textlines from one side to the other of each tab vector, saving
296  // the most frequent column widths found in a list so that a given width
297  // can be tested for being a common width with a simple callback function.
298  void ComputeColumnWidths(ScrollView* tab_win,
299  ColPartitionGrid* part_grid);
300 
301  // Find column width and pair-up tab vectors with existing ColPartitions.
302  void ApplyPartitionsToColumnWidths(ColPartitionGrid* part_grid,
303  STATS* col_widths);
304 
305  // Helper makes the list of common column widths in column_widths_ from the
306  // input col_widths. Destroys the content of col_widths by repeatedly
307  // finding the mode and erasing the peak.
308  void MakeColumnWidths(int col_widths_size, STATS* col_widths);
309 
310  // Mark blobs as being in a vertical text line where that is the case.
311  void MarkVerticalText();
312 
313  // Returns the median gutter width between pairs of matching tab vectors
314  // assuming they are sorted left-to-right. If there are too few data
315  // points (< kMinLinesInColumn), then 0 is returned.
316  int FindMedianGutterWidth(TabVector_LIST* tab_vectors);
317 
318  // Find the next adjacent (to left or right) blob on this text line,
319  // with the constraint that it must vertically significantly overlap
320  // the [top_y, bottom_y] range.
321  // If ignore_images is true, then blobs with aligned_text() < 0 are treated
322  // as if they do not exist.
323  BLOBNBOX* AdjacentBlob(const BLOBNBOX* bbox,
324  bool look_left, bool ignore_images,
325  double min_overlap_fraction,
326  int gap_limit, int top_y, int bottom_y);
327 
328  // Add a bi-directional partner relationship between the left
329  // and the right. If one (or both) of the vectors is a separator,
330  // extend a nearby extendable vector or create a new one of the
331  // correct type, using the given left or right blob as a guide.
332  void AddPartnerVector(BLOBNBOX* left_blob, BLOBNBOX* right_blob,
333  TabVector* left, TabVector* right);
334 
339  void CleanupTabs();
340 
346  bool Deskew(TabVector_LIST* hlines, BLOBNBOX_LIST* image_blobs,
347  TO_BLOCK* block, FCOORD* deskew, FCOORD* reskew);
348 
349  // Compute the rotation required to deskew, and its inverse rotation.
350  void ComputeDeskewVectors(FCOORD* deskew, FCOORD* reskew);
351 
356  void ApplyTabConstraints();
357 
358  protected:
359  ICOORD vertical_skew_; //< Estimate of true vertical in this image.
360  int resolution_; //< Of source image in pixels per inch.
361  private:
362  ICOORD image_origin_; //< Top-left of image in deskewed coords
363  TabVector_LIST vectors_; //< List of rule line and tabstops.
364  TabVector_IT v_it_; //< Iterator for searching vectors_.
365  TabVector_LIST dead_vectors_; //< Separators and unpartnered tab vectors.
366  ICOORDELT_LIST column_widths_; //< List of commonly occurring widths.
368  WidthCallback* width_cb_;
369  // Sets of bounding boxes that are candidate tab stops.
370  GenericVector<BLOBNBOX*> left_tab_boxes_;
371  GenericVector<BLOBNBOX*> right_tab_boxes_;
372 };
373 
374 } // namespace tesseract.
375 
376 #endif // TESSERACT_TEXTORD_TABFIND_H__