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