tesseract  v4.0.0-17-g361f3264
Open Source OCR Engine
colpartitiongrid.h
1 // File: colpartitiongrid.h
3 // Description: Class collecting code that acts on a BBGrid of ColPartitions.
4 // Author: Ray Smith
5 // Created: Mon Oct 05 08:42:01 PDT 2009
6 //
7 // (C) Copyright 2009, 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_COLPARTITIONGRID_H_
21 #define TESSERACT_TEXTORD_COLPARTITIONGRID_H_
22 
23 #include "bbgrid.h"
24 #include "colpartition.h"
25 #include "colpartitionset.h"
26 
27 namespace tesseract {
28 
29 class TabFind;
30 
31 // ColPartitionGrid is a BBGrid of ColPartition.
32 // It collects functions that work on the grid.
33 class ColPartitionGrid : public BBGrid<ColPartition,
34  ColPartition_CLIST,
35  ColPartition_C_IT> {
36  public:
37  ColPartitionGrid() = default;
38  ColPartitionGrid(int gridsize, const ICOORD& bleft, const ICOORD& tright);
39 
40  virtual ~ColPartitionGrid() = default;
41 
42  // Handles a click event in a display window.
43  void HandleClick(int x, int y);
44 
45  // Merges ColPartitions in the grid that look like they belong in the same
46  // textline.
47  // For all partitions in the grid, calls the box_cb permanent callback
48  // to compute the search box, searches the box, and if a candidate is found,
49  // calls the confirm_cb to check any more rules. If the confirm_cb returns
50  // true, then the partitions are merged.
51  // Both callbacks are deleted before returning.
53  TessResultCallback2<bool, const ColPartition*,
54  const ColPartition*>* confirm_cb);
55 
56  // For the given partition, calls the box_cb permanent callback
57  // to compute the search box, searches the box, and if a candidate is found,
58  // calls the confirm_cb to check any more rules. If the confirm_cb returns
59  // true, then the partitions are merged.
60  // Returns true if the partition is consumed by one or more merges.
62  TessResultCallback2<bool, const ColPartition*,
63  const ColPartition*>* confirm_cb,
64  ColPartition* part);
65 
66  // Computes and returns the total overlap of all partitions in the grid.
67  // If overlap_grid is non-null, it is filled with a grid that holds empty
68  // partitions representing the union of all overlapped partitions.
69  int ComputeTotalOverlap(ColPartitionGrid** overlap_grid);
70 
71  // Finds all the ColPartitions in the grid that overlap with the given
72  // box and returns them SortByBoxLeft(ed) and uniqued in the given list.
73  // Any partition equal to not_this (may be nullptr) is excluded.
74  void FindOverlappingPartitions(const TBOX& box, const ColPartition* not_this,
75  ColPartition_CLIST* parts);
76 
77  // Finds and returns the best candidate ColPartition to merge with part,
78  // selected from the candidates list, based on the minimum increase in
79  // pairwise overlap among all the partitions overlapped by the combined box.
80  // If overlap_increase is not nullptr then it returns the increase in overlap
81  // that would result from the merge.
82  // See colpartitiongrid.cpp for a diagram.
84  const ColPartition* part, ColPartition_CLIST* candidates, bool debug,
85  TessResultCallback2<bool, const ColPartition*,
86  const ColPartition*>* confirm_cb,
87  int* overlap_increase);
88 
89  // Split partitions where it reduces overlap between their bounding boxes.
90  // ColPartitions are after all supposed to be a partitioning of the blobs
91  // AND of the space on the page!
92  // Blobs that cause overlaps get removed, put in individual partitions
93  // and added to the big_parts list. They are most likely characters on
94  // 2 textlines that touch, or something big like a dropcap.
95  void SplitOverlappingPartitions(ColPartition_LIST* big_parts);
96 
97  // Filters partitions of source_type by looking at local neighbours.
98  // Where a majority of neighbours have a text type, the partitions are
99  // changed to text, where the neighbours have image type, they are changed
100  // to image, and partitions that have no definite neighbourhood type are
101  // left unchanged.
102  // im_box and rerotation are used to map blob coordinates onto the
103  // nontext_map, which is used to prevent the spread of text neighbourhoods
104  // into images.
105  // Returns true if anything was changed.
106  bool GridSmoothNeighbours(BlobTextFlowType source_type, Pix* nontext_map,
107  const TBOX& im_box, const FCOORD& rerotation);
108 
109  // Reflects the grid and its colpartitions in the y-axis, assuming that
110  // all blob boxes have already been done.
111  void ReflectInYAxis();
112 
113  // Rotates the grid and its colpartitions by the given angle, assuming that
114  // all blob boxes have already been done.
115  void Deskew(const FCOORD& deskew);
116 
117  // Transforms the grid of partitions to the output blocks, putting each
118  // partition into a separate block. We don't really care about the order,
119  // as we just want to get as much text as possible without trying to organize
120  // it into proper blocks or columns.
121  void ExtractPartitionsAsBlocks(BLOCK_LIST* blocks, TO_BLOCK_LIST* to_blocks);
122 
123  // Sets the left and right tabs of the partitions in the grid.
124  void SetTabStops(TabFind* tabgrid);
125 
126  // Makes the ColPartSets and puts them in the PartSetVector ready
127  // for finding column bounds. Returns false if no partitions were found.
128  // Each ColPartition in the grid is placed in a single ColPartSet based
129  // on the bottom-left of its bounding box.
130  bool MakeColPartSets(PartSetVector* part_sets);
131 
132  // Makes a single ColPartitionSet consisting of a single ColPartition that
133  // represents the total horizontal extent of the significant content on the
134  // page. Used for the single column setting in place of automatic detection.
135  // Returns nullptr if the page is empty of significant content.
137 
138  // Mark the BLOBNBOXes in each partition as being owned by that partition.
139  void ClaimBoxes();
140 
141  // Retypes all the blobs referenced by the partitions in the grid.
142  // Image blobs are sliced on the grid boundaries to give the tab finder
143  // a better handle on the edges of the images, and the actual blobs are
144  // returned in the im_blobs list, as they are not owned by the block.
145  void ReTypeBlobs(BLOBNBOX_LIST* im_blobs);
146 
147  // The boxes within the partitions have changed (by deskew) so recompute
148  // the bounds of all the partitions and reinsert them into the grid.
149  void RecomputeBounds(int gridsize, const ICOORD& bleft,
150  const ICOORD& tright, const ICOORD& vertical);
151 
152  // Improves the margins of the ColPartitions in the grid by calling
153  // FindPartitionMargins on each.
154  void GridFindMargins(ColPartitionSet** best_columns);
155 
156  // Improves the margins of the ColPartitions in the list by calling
157  // FindPartitionMargins on each.
158  void ListFindMargins(ColPartitionSet** best_columns,
159  ColPartition_LIST* parts);
160 
161  // Deletes all the partitions in the grid after disowning all the blobs.
162  void DeleteParts();
163 
164  // Deletes all the partitions in the grid that are of type BRT_UNKNOWN and
165  // all the blobs in them.
166  void DeleteUnknownParts(TO_BLOCK* block);
167 
168  // Deletes all the partitions in the grid that are NOT of flow type
169  // BTFT_LEADER.
170  void DeleteNonLeaderParts();
171 
172  // Finds and marks text partitions that represent figure captions.
173  void FindFigureCaptions();
174 
177  // For every ColPartition in the grid, finds its upper and lower neighbours.
178  void FindPartitionPartners();
179  // Finds the best partner in the given direction for the given partition.
180  // Stores the result with AddPartner.
181  void FindPartitionPartners(bool upper, ColPartition* part);
182  // Finds the best partner in the given direction for the given partition.
183  // Stores the result with AddPartner.
184  void FindVPartitionPartners(bool to_the_left, ColPartition* part);
185  // For every ColPartition with multiple partners in the grid, reduces the
186  // number of partners to 0 or 1. If get_desperate is true, goes to more
187  // desperate merge methods to merge flowing text before breaking partnerships.
188  void RefinePartitionPartners(bool get_desperate);
189 
190  private:
191  // Finds and returns a list of candidate ColPartitions to merge with part.
192  // The candidates must overlap search_box, and when merged must not
193  // overlap any other partitions that are not overlapped by each individually.
194  void FindMergeCandidates(const ColPartition* part, const TBOX& search_box,
195  bool debug, ColPartition_CLIST* candidates);
196 
197  // Smoothes the region type/flow type of the given part by looking at local
198  // neighbours and the given image mask. Searches a padded rectangle with the
199  // padding truncated on one size of the part's box in turn for each side,
200  // using the result (if any) that has the least distance to all neighbours
201  // that contribute to the decision. This biases in favor of rectangular
202  // regions without completely enforcing them.
203  // If a good decision cannot be reached, the part is left unchanged.
204  // im_box and rerotation are used to map blob coordinates onto the
205  // nontext_map, which is used to prevent the spread of text neighbourhoods
206  // into images.
207  // Returns true if the partition was changed.
208  bool SmoothRegionType(Pix* nontext_map,
209  const TBOX& im_box,
210  const FCOORD& rerotation,
211  bool debug,
212  ColPartition* part);
213  // Executes the search for SmoothRegionType in a single direction.
214  // Creates a bounding box that is padded in all directions except direction,
215  // and searches it for other partitions. Finds the nearest collection of
216  // partitions that makes a decisive result (if any) and returns the type
217  // and the distance of the collection. If there are any pixels in the
218  // nontext_map, then the decision is biased towards image.
219  BlobRegionType SmoothInOneDirection(BlobNeighbourDir direction,
220  Pix* nontext_map,
221  const TBOX& im_box,
222  const FCOORD& rerotation,
223  bool debug,
224  const ColPartition& part,
225  int* best_distance);
226  // Counts the partitions in the given search_box by appending the gap
227  // distance (scaled by dist_scaling) of the part from the base_part to the
228  // vector of the appropriate type for the partition. Prior to return, the
229  // vectors in the dists array are sorted in increasing order.
230  // dists must be an array of GenericVectors of size NPT_COUNT.
231  void AccumulatePartDistances(const ColPartition& base_part,
232  const ICOORD& dist_scaling,
233  const TBOX& search_box,
234  Pix* nontext_map,
235  const TBOX& im_box,
236  const FCOORD& rerotation,
237  bool debug,
238  GenericVector<int>* dists);
239 
240  // Improves the margins of the ColPartition by searching for
241  // neighbours that vertically overlap significantly.
242  void FindPartitionMargins(ColPartitionSet* columns, ColPartition* part);
243 
244  // Starting at x, and going in the specified direction, up to x_limit, finds
245  // the margin for the given y range by searching sideways,
246  // and ignoring not_this.
247  int FindMargin(int x, bool right_to_left, int x_limit,
248  int y_bottom, int y_top, const ColPartition* not_this);
249 };
250 
251 } // namespace tesseract.
252 
253 #endif // TESSERACT_TEXTORD_COLPARTITIONGRID_H_
void GridFindMargins(ColPartitionSet **best_columns)
Definition: colpartitiongrid.cpp:967
Definition: colpartitiongrid.h:33
void FindVPartitionPartners(bool to_the_left, ColPartition *part)
Definition: colpartitiongrid.cpp:1248
ColPartitionSet * MakeSingleColumnSet(WidthCallback *cb)
Definition: colpartitiongrid.cpp:822
Definition: colpartitionset.h:40
void Deskew(const FCOORD &deskew)
Definition: colpartitiongrid.cpp:736
void AccumulatePartDistances(const ColPartition &base_part, const ICOORD &dist_scaling, const TBOX &search_box, Pix *nontext_map, const TBOX &im_box, const FCOORD &rerotation, bool debug, GenericVector< int > *dists)
Definition: colpartitiongrid.cpp:1608
bool MakeColPartSets(PartSetVector *part_sets)
Definition: colpartitiongrid.cpp:784
Definition: rect.h:34
void FindFigureCaptions()
Definition: colpartitiongrid.cpp:1061
void HandleClick(int x, int y)
Definition: colpartitiongrid.cpp:76
void RecomputeBounds(int gridsize, const ICOORD &bleft, const ICOORD &tright, const ICOORD &vertical)
Definition: colpartitiongrid.cpp:938
Definition: baseapi.cpp:94
void FindPartitionMargins(ColPartitionSet *columns, ColPartition *part)
Definition: colpartitiongrid.cpp:1684
bool SmoothRegionType(Pix *nontext_map, const TBOX &im_box, const FCOORD &rerotation, bool debug, ColPartition *part)
Definition: colpartitiongrid.cpp:1401
void ReflectInYAxis()
Definition: colpartitiongrid.cpp:647
void DeleteParts()
Definition: colpartitiongrid.cpp:1009
Definition: bbgrid.h:159
int ComputeTotalOverlap(ColPartitionGrid **overlap_grid)
Definition: colpartitiongrid.cpp:319
bool MergePart(TessResultCallback2< bool, ColPartition *, TBOX *> *box_cb, TessResultCallback2< bool, const ColPartition *, const ColPartition *> *confirm_cb, ColPartition *part)
Definition: colpartitiongrid.cpp:123
void SplitOverlappingPartitions(ColPartition_LIST *big_parts)
Definition: colpartitiongrid.cpp:515
const ICOORD & bleft() const
Definition: bbgrid.h:73
int gridsize() const
Definition: bbgrid.h:64
void Merges(TessResultCallback2< bool, ColPartition *, TBOX *> *box_cb, TessResultCallback2< bool, const ColPartition *, const ColPartition *> *confirm_cb)
Definition: colpartitiongrid.cpp:102
void DeleteUnknownParts(TO_BLOCK *block)
Definition: colpartitiongrid.cpp:1024
void ReTypeBlobs(BLOBNBOX_LIST *im_blobs)
Definition: colpartitiongrid.cpp:877
void SetTabStops(TabFind *tabgrid)
Definition: colpartitiongrid.cpp:760
void ExtractPartitionsAsBlocks(BLOCK_LIST *blocks, TO_BLOCK_LIST *to_blocks)
Definition: colpartitiongrid.cpp:675
Definition: baseapi.h:37
virtual ~ColPartitionGrid()=default
Definition: tesscallback.h:1673
void DeleteNonLeaderParts()
Definition: colpartitiongrid.cpp:1043
integer coordinate
Definition: points.h:32
bool GridSmoothNeighbours(BlobTextFlowType source_type, Pix *nontext_map, const TBOX &im_box, const FCOORD &rerotation)
Definition: colpartitiongrid.cpp:625
void ClaimBoxes()
Definition: colpartitiongrid.cpp:864
Definition: tabfind.h:53
BlobRegionType SmoothInOneDirection(BlobNeighbourDir direction, Pix *nontext_map, const TBOX &im_box, const FCOORD &rerotation, bool debug, const ColPartition &part, int *best_distance)
Definition: colpartitiongrid.cpp:1525
void ListFindMargins(ColPartitionSet **best_columns, ColPartition_LIST *parts)
Definition: colpartitiongrid.cpp:991
void RefinePartitionPartners(bool get_desperate)
Definition: colpartitiongrid.cpp:1294
Definition: blobbox.h:705
Definition: blamer.h:43
void FindMergeCandidates(const ColPartition *part, const TBOX &search_box, bool debug, ColPartition_CLIST *candidates)
Definition: colpartitiongrid.cpp:1317
ColPartition * BestMergeCandidate(const ColPartition *part, ColPartition_CLIST *candidates, bool debug, TessResultCallback2< bool, const ColPartition *, const ColPartition *> *confirm_cb, int *overlap_increase)
Definition: colpartitiongrid.cpp:406
const ICOORD & tright() const
Definition: bbgrid.h:76
void FindPartitionPartners()
Definition: colpartitiongrid.cpp:1186
int FindMargin(int x, bool right_to_left, int x_limit, int y_bottom, int y_top, const ColPartition *not_this)
Definition: colpartitiongrid.cpp:1715
Definition: colpartition.h:68
Definition: points.h:189
void FindOverlappingPartitions(const TBOX &box, const ColPartition *not_this, ColPartition_CLIST *parts)
Definition: colpartitiongrid.cpp:353