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 // 18 /////////////////////////////////////////////////////////////////////// 19 20 #ifndef TESSERACT_TEXTORD_TABFIND_H__ 21 #define TESSERACT_TEXTORD_TABFIND_H__ 22 23 #include "alignedblob.h" 24 #include "callback.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 36 typedef ResultCallback1<bool, int> WidthCallback; 37 38 struct AlignedBlobParams; 39 40 // Pixel resolution of column width estimates. 41 const int kColumnWidthFactor = 20; 42 43 // The TabFind class contains code to find tab-stops and maintain the 44 // vectors_ list of tab vectors. 45 // Also provides an interface to find neighbouring blobs 46 // in the grid of BLOBNBOXes that is used by multiple subclasses. 47 // Searching is a complex operation because of the need to enforce 48 // rule/separator lines, and tabstop boundaries, (when available), so 49 // as the holder of the list of TabVectors this class provides the functions. 50 class TabFind : public AlignedBlob { 51 public: 52 TabFind(int gridsize, const ICOORD& bleft, const ICOORD& tright, 53 TabVector_LIST* vlines, int vertical_x, int vertical_y); 54 virtual ~TabFind(); 55 56 // Insert a list of blobs into the given grid (not necessarily this). 57 // If take_ownership is true, then the blobs are removed from the source list. 58 // See InsertBlob for the other arguments. 59 void InsertBlobList(bool h_spread, bool v_spread, bool large, 60 BLOBNBOX_LIST* blobs, bool take_ownership, 61 BBGrid<BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT>* grid); 62 63 // Insert a single blob into the given grid (not necessarily this). 64 // If h_spread, then all cells covered horizontally by the box are 65 // used, otherwise, just the bottom-left. Similarly for v_spread. 66 // If large, then insert only if the bounding box doesn't intersect 67 // anything else already in the grid. Returns true if the blob was inserted. 68 // A side effect is that the left and right rule edges of the blob are 69 // set according to the tab vectors in this (not grid). 70 bool InsertBlob(bool h_spread, bool v_spread, bool large, BLOBNBOX* blob, 71 BBGrid<BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT>* grid); 72 73 // Find the gutter width and distance to inner neighbour for the given blob. 74 void GutterWidthAndNeighbourGap(int tab_x, int mean_height, 75 int max_gutter, bool left, 76 BLOBNBOX* bbox, int* gutter_width, 77 int* neighbour_gap); 78 79 // Find the next adjacent (to left or right) blob on this text line, 80 // with the constraint that it must vertically significantly overlap 81 // the input box. 82 BLOBNBOX* AdjacentBlob(const BLOBNBOX* bbox, 83 bool right_to_left, int gap_limit); 84 85 // Compute and return, but do not set the type as being BRT_TEXT or 86 // BRT_UNKNOWN according to how well it forms a text line. 87 BlobRegionType ComputeBlobType(BLOBNBOX* blob); 88 89 // Return the x-coord that corresponds to the right edge for the given 90 // box. If there is a rule line to the right that vertically overlaps it, 91 // then return the x-coord of the rule line, otherwise return the right 92 // edge of the page. For details see RightTabForBox below. 93 int RightEdgeForBox(const TBOX& box, bool crossing, bool extended); 94 // As RightEdgeForBox, but finds the left Edge instead. 95 int LeftEdgeForBox(const TBOX& box, bool crossing, bool extended); 96 97 // Compute the rotation required to deskew, and its inverse rotation. 98 void ComputeDeskewVectors(FCOORD* deskew, FCOORD* reskew); 99 100 // Return true if the given width is close to one of the common 101 // widths in column_widths_. 102 bool CommonWidth(int width); 103 // Return true if the sizes are more than a 104 // factor of 2 different. 105 static bool DifferentSizes(int size1, int size2); 106 107 // Return a callback for testing CommonWidth. WidthCB()108 WidthCallback* WidthCB() { 109 return width_cb_; 110 } 111 112 // Return the coords at which to draw the image backdrop. image_origin()113 const ICOORD& image_origin() const { 114 return image_origin_; 115 } 116 117 protected: 118 // Accessors get_vectors()119 TabVector_LIST* get_vectors() { 120 return &vectors_; 121 } 122 123 // Top-level function to find TabVectors in an input page block. 124 void FindTabVectors(int resolution, TabVector_LIST* hlines, 125 BLOBNBOX_LIST* image_blobs, TO_BLOCK* block, 126 FCOORD* reskew, FCOORD* rerotate); 127 128 // Top-level function to not find TabVectors in an input page block, 129 // but setup for single column mode. 130 void DontFindTabVectors(int resolution, BLOBNBOX_LIST* image_blobs, 131 TO_BLOCK* block, FCOORD* reskew); 132 133 // Return the TabVector that corresponds to the right edge for the given 134 // box. If there is a TabVector to the right that vertically overlaps it, 135 // then return it, otherwise return NULL. Note that Right and Left refer 136 // to the position of the TabVector, not its type, ie RightTabForBox 137 // returns the nearest TabVector to the right of the box, regardless of 138 // its type. 139 // If a TabVector crosses right through the box (as opposed to grazing one 140 // edge or missing entirely), then crossing false will ignore such a line. 141 // Crossing true will return the line for BOTH left and right edges. 142 // If extended is true, then TabVectors are considered to extend to their 143 // extended_start/end_y, otherwise, just the startpt_ and endpt_. 144 // These functions make use of an internal iterator to the vectors_ list 145 // for speed when used repeatedly on neighbouring boxes. The caveat is 146 // that the iterator must be updated whenever the list is modified. 147 TabVector* RightTabForBox(const TBOX& box, bool crossing, bool extended); 148 // As RightTabForBox, but finds the left TabVector instead. 149 TabVector* LeftTabForBox(const TBOX& box, bool crossing, bool extended); 150 // Helper function to setup search limits for *TabForBox. 151 void SetupTabSearch(int x, int y, int* min_key, int* max_key); 152 153 // Display the tab vectors found in this grid. 154 ScrollView* DisplayTabVectors(ScrollView* tab_win); 155 156 private: 157 // First part of FindTabVectors, which may be used twice if the text 158 // is mostly of vertical alignment. 159 void FindInitialTabVectors(BLOBNBOX_LIST* image_blobs, TO_BLOCK* block); 160 161 // For each box in the grid, decide whether it is a candidate tab-stop, 162 // and if so add it to the tab_grid_. 163 ScrollView* FindTabBoxes(); 164 165 // Return true if this box looks like a candidate tab stop, and set 166 // the appropriate tab type(s) to TT_UNCONFIRMED. 167 bool TestBoxForTabs(BLOBNBOX* bbox); 168 169 // Fills the list of TabVector with the tabstops found in the grid, 170 // and estimates the logical vertical direction. 171 void FindAllTabVectors(); 172 // Helper for FindAllTabVectors finds the vectors of a particular type. 173 int FindTabVectors(int search_size_multiple, 174 TabAlignment alignment, 175 TabVector_LIST* vectors, 176 int* vertical_x, int* vertical_y); 177 // Finds a vector corresponding to a tabstop running through the 178 // given box of the given alignment type. 179 // search_size_multiple is a multiple of height used to control 180 // the size of the search. 181 // vertical_x and y are updated with an estimate of the real 182 // vertical direction. (skew finding.) 183 // Returns NULL if no decent tabstop can be found. 184 TabVector* FindTabVector(int search_size_multiple, 185 TabAlignment alignment, 186 BLOBNBOX* bbox, 187 int* vertical_x, int* vertical_y); 188 189 // Set the vertical_skew_ member from the given vector and refit 190 // all vectors parallel to the skew vector. 191 void SetVerticalSkewAndParellelize(int vertical_x, int vertical_y); 192 193 // Sort all the current vectors using the vertical_skew_ vector. 194 void SortVectors(); 195 196 // Evaluate all the current tab vectors. 197 void EvaluateTabs(); 198 199 // Trace textlines from one side to the other of each tab vector, saving 200 // the most frequent column widths found in a list so that a given width 201 // can be tested for being a common width with a simple callback function. 202 void ComputeColumnWidths(ScrollView* tab_win); 203 204 // Set the region_type_ member for all the blobs in the grid. 205 void ComputeBlobGoodness(); 206 207 // Set the region_type_ member of the blob, if not already known. 208 void SetBlobRegionType(BLOBNBOX* blob); 209 210 // Mark blobs as being in a vertical text line where that is the case. 211 void MarkVerticalText(); 212 213 // Returns true if the majority of the image is vertical text lines. 214 bool TextMostlyVertical(); 215 216 // If this box looks like it is on a textline in the given direction, 217 // return the width of the textline-like group of blobs, and the number 218 // of blobs found. 219 // For more detail see FindTextlineSegment below. 220 int FindTextlineWidth(bool right_to_left, BLOBNBOX* bbox, int* blob_count); 221 222 // Search from the given tabstop bbox to the next opposite 223 // tabstop bbox on the same text line, which may be itself. 224 // Returns true if the search is successful, and sets 225 // start_pt, end_pt to the fitted baseline, width to the measured 226 // width of the text line (column width estimate.) 227 bool TraceTextline(BLOBNBOX* bbox, ICOORD* start_pt, ICOORD* end_pt, 228 int* left_edge, int* right_edge); 229 230 // Search from the given bbox in the given direction until the next tab 231 // vector is found or a significant horizontal gap is found. 232 // Returns the width of the line if the search is successful, (defined 233 // as good coverage of the width and a good fitting baseline) and sets 234 // start_pt, end_pt to the fitted baseline, left_blob, right_blob to 235 // the ends of the line. Returns zero otherwise. 236 // Sets blob_count to the number of blobs found on the line. 237 // On input, either both left_vector and right_vector should be NULL, 238 // indicating a basic search, or both left_vector and right_vector should 239 // be not NULL and one of *left_vector and *right_vector should be not NULL, 240 // in which case the search is strictly between tab vectors and will return 241 // zero if a gap is found before the opposite tab vector is reached, or a 242 // conflicting tab vector is found. 243 // If ignore_images is true, then blobs with aligned_text() < 0 are treated 244 // as if they do not exist. 245 int FindTextlineSegment(bool right_to_lefts, bool ignore_images, 246 BLOBNBOX* bbox, int* blob_count, 247 ICOORD* start_pt, ICOORD* end_pt, 248 TabVector** left_vector, TabVector** right_vector, 249 BLOBNBOX** left_blob, BLOBNBOX** right_blob); 250 251 // Find the next adjacent (to left or right) blob on this text line, 252 // with the constraint that it must vertically significantly overlap 253 // the [top_y, bottom_y] range. 254 // If ignore_images is true, then blobs with aligned_text() < 0 are treated 255 // as if they do not exist. 256 BLOBNBOX* AdjacentBlob(const BLOBNBOX* bbox, 257 bool right_to_left, bool ignore_images, 258 int gap_limit, int top_y, int bottom_y); 259 260 // Add a bi-directional partner relationship between the left 261 // and the right. If one (or both) of the vectors is a separator, 262 // extend a nearby extendable vector or create a new one of the 263 // correct type, using the given left or right blob as a guide. 264 void AddPartnerVector(BLOBNBOX* left_blob, BLOBNBOX* right_blob, 265 TabVector* left, TabVector* right); 266 267 // Remove separators and unused tabs from the main vectors_ list 268 // to the dead_vectors_ list. 269 void CleanupTabs(); 270 271 // Deskew the tab vectors and blobs, computing the rotation and resetting 272 // the storked vertical_skew_. The deskew inverse is returned in reskew. 273 void Deskew(TabVector_LIST* hlines, BLOBNBOX_LIST* image_blobs, 274 TO_BLOCK* block, FCOORD* reskew); 275 276 // Restart everything and rotate the input blobs ready for vertical text. 277 void ResetForVerticalText(TabVector_LIST* hlines, BLOBNBOX_LIST* image_blobs, 278 TO_BLOCK* block, FCOORD* rerotate); 279 280 // Compute and apply constraints to the end positions of TabVectors so 281 // that where possible partners end at the same y coordinate. 282 void ApplyTabConstraints(); 283 284 protected: 285 ICOORD vertical_skew_; // Estimate of true vertical in this image. 286 int resolution_; // Of source image in pixels per inch. 287 private: 288 ICOORD image_origin_; // Top-left of image in deskewed coords 289 TabVector_LIST vectors_; // List of rule line and tabstops. 290 TabVector_IT v_it_; // Iterator for searching vectors_. 291 TabVector_LIST dead_vectors_; // Separators and unpartnered tab vectors. 292 ICOORDELT_LIST column_widths_; // List of commonly occurring widths. 293 // Callback to test an int for being a common width. 294 WidthCallback* width_cb_; 295 // Instance of the base class that contains only candidate tab stops. 296 BBGrid<BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT>* tab_grid_; 297 }; 298 299 } // namespace tesseract. 300 301 #endif // TESSERACT_TEXTORD_TABFIND_H__ 302 303