tabfind.h

Go to the documentation of this file.

 
// File:        tabfind.h
// Description: Subclass of BBGrid to find tabstops.
// Author:      Ray Smith
//
// (C) Copyright 2008, Google Inc.
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
// http://www.apache.org/licenses/LICENSE-2.0
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
 
#ifndef TESSERACT_TEXTORD_TABFIND_H_
#define TESSERACT_TEXTORD_TABFIND_H_
 
#include <functional> // for std::function
#include "alignedblob.h"
#include "linefind.h"
#include "tabvector.h"
 
class BLOBNBOX;
class BLOBNBOX_LIST;
class TO_BLOCK;
class ScrollView;
struct Pix;
 
namespace tesseract {
 
using WidthCallback = std::function<bool(int)>;
 
struct AlignedBlobParams;
class ColPartitionGrid;
 
const int kColumnWidthFactor = 20;
 
class TESS_API TabFind : public AlignedBlob {
public:
  TabFind(int gridsize, const ICOORD &bleft, const ICOORD &tright, TabVector_LIST *vlines,
          int vertical_x, int vertical_y, int resolution);
  ~TabFind() override;
 
  void InsertBlobsToGrid(bool h_spread, bool v_spread, BLOBNBOX_LIST *blobs,
                         BBGrid<BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT> *grid);
 
  bool InsertBlob(bool h_spread, bool v_spread, BLOBNBOX *blob,
                  BBGrid<BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT> *grid);
  // Calls SetBlobRuleEdges for all the blobs in the given block.
  void SetBlockRuleEdges(TO_BLOCK *block);
  // Sets the left and right rule and crossing_rules for the blobs in the given
  // list by finding the next outermost tabvectors for each blob.
  void SetBlobRuleEdges(BLOBNBOX_LIST *blobs);
 
  // Returns the gutter width of the given TabVector between the given y limits.
  // Also returns x-shift to be added to the vector to clear any intersecting
  // blobs. The shift is deducted from the returned gutter.
  // If ignore_unmergeables is true, then blobs of UnMergeableType are
  // ignored as if they don't exist. (Used for text on image.)
  // max_gutter_width is used as the maximum width worth searching for in case
  // there is nothing near the TabVector.
  int GutterWidth(int bottom_y, int top_y, const TabVector &v, bool ignore_unmergeables,
                  int max_gutter_width, int *required_shift);
  void GutterWidthAndNeighbourGap(int tab_x, int mean_height, int max_gutter, bool left,
                                  BLOBNBOX *bbox, int *gutter_width, int *neighbour_gap);
 
  int RightEdgeForBox(const TBOX &box, bool crossing, bool extended);
  int LeftEdgeForBox(const TBOX &box, bool crossing, bool extended);
 
  TabVector *RightTabForBox(const TBOX &box, bool crossing, bool extended);
  TabVector *LeftTabForBox(const TBOX &box, bool crossing, bool extended);
 
  bool CommonWidth(int width);
  static bool DifferentSizes(int size1, int size2);
  static bool VeryDifferentSizes(int size1, int size2);
 
  WidthCallback WidthCB() {
    return width_cb_;
  }
 
  const ICOORD &image_origin() const {
    return image_origin_;
  }
 
protected:
  TabVector_LIST *vectors() {
    return &vectors_;
  }
  TabVector_LIST *dead_vectors() {
    return &dead_vectors_;
  }
 
  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);
 
  // Top-level function to not find TabVectors in an input page block,
  // but setup for single column mode.
  void DontFindTabVectors(BLOBNBOX_LIST *image_blobs, TO_BLOCK *block, FCOORD *deskew,
                          FCOORD *reskew);
 
  // Cleans up the lists of blobs in the block ready for use by TabFind.
  // Large blobs that look like text are moved to the main blobs list.
  // Main blobs that are superseded by the image blobs are deleted.
  void TidyBlobs(TO_BLOCK *block);
 
  // Helper function to setup search limits for *TabForBox.
  void SetupTabSearch(int x, int y, int *min_key, int *max_key);
 
  ScrollView *DisplayTabVectors(ScrollView *tab_win);
 
  // First part of FindTabVectors, which may be used twice if the text
  // is mostly of vertical alignment.  If find_vertical_text flag is
  // true, this finds vertical textlines in possibly rotated blob space.
  // In other words, when the page has mostly vertical lines and is rotated,
  // setting this to true will find horizontal lines on the page.
  // tabfind_aligned_gap_fraction should be the value of parameter
  // textord_tabfind_aligned_gap_fraction
  ScrollView *FindInitialTabVectors(BLOBNBOX_LIST *image_blobs, int min_gutter_width,
                                    double tabfind_aligned_gap_fraction, TO_BLOCK *block);
 
  // Apply the given rotation to the given list of blobs.
  static void RotateBlobList(const FCOORD &rotation, BLOBNBOX_LIST *blobs);
 
  // Flip the vertical and horizontal lines and rotate the grid ready
  // for working on the rotated image.
  // The min_gutter_width will be adjusted to the median gutter width between
  // vertical tabs to set a better threshold for tabboxes in the 2nd pass.
  void ResetForVerticalText(const FCOORD &rotate, const FCOORD &rerotate,
                            TabVector_LIST *horizontal_lines, int *min_gutter_width);
 
  // Clear the grid and get rid of the tab vectors, but not separators,
  // ready to start again.
  void Reset();
 
  // Reflect the separator tab vectors and the grids in the y-axis.
  // Can only be called after Reset!
  void ReflectInYAxis();
 
private:
  // For each box in the grid, decide whether it is a candidate tab-stop,
  // and if so add it to the left and right tab boxes.
  // tabfind_aligned_gap_fraction should be the value of parameter
  // textord_tabfind_aligned_gap_fraction
  ScrollView *FindTabBoxes(int min_gutter_width, double tabfind_aligned_gap_fraction);
 
  // Return true if this box looks like a candidate tab stop, and set
  // the appropriate tab type(s) to TT_UNCONFIRMED.
  // tabfind_aligned_gap_fraction should be the value of parameter
  // textord_tabfind_aligned_gap_fraction
  bool TestBoxForTabs(BLOBNBOX *bbox, int min_gutter_width, double tabfind_aligned_gap_fraction);
 
  // Returns true if there is nothing in the rectangle of width min_gutter to
  // the left of bbox.
  bool ConfirmRaggedLeft(BLOBNBOX *bbox, int min_gutter);
  // Returns true if there is nothing in the rectangle of width min_gutter to
  // the right of bbox.
  bool ConfirmRaggedRight(BLOBNBOX *bbox, int min_gutter);
  // Returns true if there is nothing in the given search_box that vertically
  // overlaps target_box other than target_box itself.
  bool NothingYOverlapsInBox(const TBOX &search_box, const TBOX &target_box);
 
  // Fills the list of TabVector with the tabstops found in the grid,
  // and estimates the logical vertical direction.
  void FindAllTabVectors(int min_gutter_width);
  // Helper for FindAllTabVectors finds the vectors of a particular type.
  int FindTabVectors(int search_size_multiple, TabAlignment alignment, int min_gutter_width,
                     TabVector_LIST *vectors, int *vertical_x, int *vertical_y);
  // Finds a vector corresponding to a tabstop running through the
  // given box of the given alignment type.
  // search_size_multiple is a multiple of height used to control
  // the size of the search.
  // vertical_x and y are updated with an estimate of the real
  // vertical direction. (skew finding.)
  // Returns nullptr if no decent tabstop can be found.
  TabVector *FindTabVector(int search_size_multiple, int min_gutter_width, TabAlignment alignment,
                           BLOBNBOX *bbox, int *vertical_x, int *vertical_y);
 
  // Set the vertical_skew_ member from the given vector and refit
  // all vectors parallel to the skew vector.
  void SetVerticalSkewAndParallelize(int vertical_x, int vertical_y);
 
  // Sort all the current vectors using the vertical_skew_ vector.
  void SortVectors();
 
  // Evaluate all the current tab vectors.
  void EvaluateTabs();
 
  // Trace textlines from one side to the other of each tab vector, saving
  // the most frequent column widths found in a list so that a given width
  // can be tested for being a common width with a simple callback function.
  void ComputeColumnWidths(ScrollView *tab_win, ColPartitionGrid *part_grid);
 
  // Finds column width and:
  //   if col_widths is not null (pass1):
  //     pair-up tab vectors with existing ColPartitions and accumulate widths.
  //   else (pass2):
  //     find the largest real partition width for each recorded column width,
  //     to be used as the minimum acceptable width.
  void ApplyPartitionsToColumnWidths(ColPartitionGrid *part_grid, STATS *col_widths);
 
  // Helper makes the list of common column widths in column_widths_ from the
  // input col_widths. Destroys the content of col_widths by repeatedly
  // finding the mode and erasing the peak.
  void MakeColumnWidths(int col_widths_size, STATS *col_widths);
 
  // Mark blobs as being in a vertical text line where that is the case.
  void MarkVerticalText();
 
  // Returns the median gutter width between pairs of matching tab vectors
  // assuming they are sorted left-to-right.  If there are too few data
  // points (< kMinLinesInColumn), then 0 is returned.
  int FindMedianGutterWidth(TabVector_LIST *tab_vectors);
 
  // Find the next adjacent (to left or right) blob on this text line,
  // with the constraint that it must vertically significantly overlap
  // the [top_y, bottom_y] range.
  // If ignore_images is true, then blobs with aligned_text() < 0 are treated
  // as if they do not exist.
  BLOBNBOX *AdjacentBlob(const BLOBNBOX *bbox, bool look_left, bool ignore_images,
                         double min_overlap_fraction, int gap_limit, int top_y, int bottom_y);
 
  // Add a bi-directional partner relationship between the left
  // and the right. If one (or both) of the vectors is a separator,
  // extend a nearby extendable vector or create a new one of the
  // correct type, using the given left or right blob as a guide.
  void AddPartnerVector(BLOBNBOX *left_blob, BLOBNBOX *right_blob, TabVector *left,
                        TabVector *right);
 
  void CleanupTabs();
 
  bool Deskew(TabVector_LIST *hlines, BLOBNBOX_LIST *image_blobs, TO_BLOCK *block, FCOORD *deskew,
              FCOORD *reskew);
 
  // Compute the rotation required to deskew, and its inverse rotation.
  void ComputeDeskewVectors(FCOORD *deskew, FCOORD *reskew);
 
  void ApplyTabConstraints();
 
protected:
  ICOORD vertical_skew_; 
  int resolution_;       
private:
  ICOORD image_origin_;         
  TabVector_LIST vectors_;      
  TabVector_IT v_it_;           
  TabVector_LIST dead_vectors_; 
  // List of commonly occurring width ranges with x=min and y=max.
  ICOORDELT_LIST column_widths_; 
  WidthCallback width_cb_;
  // Sets of bounding boxes that are candidate tab stops.
  std::vector<BLOBNBOX *> left_tab_boxes_;
  std::vector<BLOBNBOX *> right_tab_boxes_;
};
 
} // namespace tesseract.
 
#endif // TESSERACT_TEXTORD_TABFIND_H_