tesseract 4.1.1
Loading...
Searching...
No Matches
tablefind.h
Go to the documentation of this file.
1
2// File: tablefind.h
3// Description: Helper classes to find tables from ColPartitions.
4// Author: Faisal Shafait (faisal.shafait@dfki.de)
5// Created: Tue Jan 06 11:13:01 PST 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_TABLEFIND_H_
21#define TESSERACT_TEXTORD_TABLEFIND_H_
22
23#include "colpartitiongrid.h"
24#include "elst.h"
25#include "rect.h"
26
27namespace tesseract {
28
29// Possible types for a column segment.
36};
37
38class ColPartitionSet;
39
40// ColSegment holds rectangular blocks that represent segmentation of a page
41// into regions containing single column text/table.
42class ColSegment;
43ELISTIZEH(ColSegment)
44CLISTIZEH(ColSegment)
45
46class ColSegment : public ELIST_LINK {
47 public:
48 ColSegment();
49 ~ColSegment() = default;
50
51 // Simple accessors and mutators
52 const TBOX& bounding_box() const {
53 return bounding_box_;
54 }
55
56 void set_top(int y) {
57 bounding_box_.set_top(y);
58 }
59
60 void set_bottom(int y) {
61 bounding_box_.set_bottom(y);
62 }
63
64 void set_left(int x) {
65 bounding_box_.set_left(x);
66 }
67
68 void set_right(int x) {
69 bounding_box_.set_right(x);
70 }
71
72 void set_bounding_box(const TBOX& other) {
73 bounding_box_ = other;
74 }
75
76 int get_num_table_cells() const {
77 return num_table_cells_;
78 }
79
80 // set the number of table colpartitions covered by the bounding_box_
81 void set_num_table_cells(int n) {
82 num_table_cells_ = n;
83 }
84
85 int get_num_text_cells() const {
86 return num_text_cells_;
87 }
88
89 // set the number of text colpartitions covered by the bounding_box_
90 void set_num_text_cells(int n) {
91 num_text_cells_ = n;
92 }
93
94 ColSegType type() const {
95 return type_;
96 }
97
98 // set the type of the block based on the ratio of table to text
99 // colpartitions covered by it.
100 void set_type();
101
102 // Provides a color for BBGrid to draw the rectangle.
103 ScrollView::Color BoxColor() const;
104
105 // Insert a rectangle into bounding_box_
106 void InsertBox(const TBOX& other);
107
108 private:
109 TBOX bounding_box_; // bounding box
110 int num_table_cells_;
111 int num_text_cells_;
112 ColSegType type_;
113};
114
115// Typedef BBGrid of ColSegments
117 ColSegment_CLIST,
118 ColSegment_C_IT>;
120 ColSegment_CLIST,
121 ColSegment_C_IT>;
122
123// TableFinder is a utility class to find a set of tables given a set of
124// ColPartitions and Columns. The TableFinder will mark candidate ColPartitions
125// based on research in "Table Detection in Heterogeneous Documents".
126// Usage flow is as follows:
127// TableFinder finder;
128// finder.InsertCleanPartitions(/* grid info */)
129// finder.LocateTables(/* ColPartitions and Columns */);
130// finder.Update TODO(nbeato)
132 public:
133 // Constructor is simple initializations
134 TableFinder();
135 ~TableFinder();
136
137 // Set the resolution of the connected components in ppi.
138 void set_resolution(int resolution) {
139 resolution_ = resolution;
140 }
141 // Change the reading order. Initially it is left to right.
142 void set_left_to_right_language(bool order);
143
144 // Initialize
145 void Init(int grid_size, const ICOORD& bottom_left, const ICOORD& top_right);
146
147 // Copy cleaned partitions from ColumnFinder's part_grid_ to this
148 // clean_part_grid_ and insert dot-like noise into period_grid_.
149 // It resizes the grids in this object to the dimensions of grid.
151
152 // High level function to perform table detection
153 // Finds tables and updates the grid object with new partitions for the
154 // tables. The columns and width callbacks are used to merge tables.
155 // The reskew argument is only used to write the tables to the out.png
156 // if that feature is enabled.
158 ColPartitionSet** columns,
159 WidthCallback* width_cb,
160 const FCOORD& reskew);
161
162 protected:
163 // Access for the grid dimensions.
164 // The results will not be correct until InsertCleanPartitions
165 // has been called. The values are taken from the grid passed as an argument
166 // to that function.
167 int gridsize() const;
168 int gridwidth() const;
169 int gridheight() const;
170 const ICOORD& bleft() const;
171 const ICOORD& tright() const;
172
173 // Makes a window for debugging, see BBGrid
174 ScrollView* MakeWindow(int x, int y, const char* window_name);
175
178 // Inserts text into the table finder.
185 bool AllowTextPartition(const ColPartition& part) const;
186 bool AllowBlob(const BLOBNBOX& blob) const;
187
191
192 // Utility function to move segments to col_seg_grid
193 // Note: Move includes ownership,
194 // so segments will be be owned by col_seg_grid
195 void MoveColSegmentsToGrid(ColSegment_LIST* segments,
196 ColSegmentGrid* col_seg_grid);
197
201
202 // Initialize the grid and partitions
203 void InitializePartitions(ColPartitionSet** all_columns);
204
205 // Set left, right and top, bottom spacings of each colpartition.
206 // Left/right spacings are w.r.t the column boundaries
207 // Top/bottom spacings are w.r.t. previous and next colpartitions
208 static void SetPartitionSpacings(ColPartitionGrid* grid,
209 ColPartitionSet** all_columns);
210
211 // Set spacing and closest neighbors above and below a given colpartition.
213
214 // Set global spacing estimates. This function is dependent on the
215 // partition spacings. So make sure SetPartitionSpacings is called
216 // on the same grid before this.
218 // Access to the global median xheight. The xheight is the height
219 // of a lowercase 'x' character on the page. This can be viewed as the
220 // average height of a lowercase letter in a textline. As a result
221 // it is used to make assumptions about spacing between words and
222 // table cells.
223 void set_global_median_xheight(int xheight);
224 // Access to the global median blob width. The width is useful
225 // when deciding if a partition is noise.
226 void set_global_median_blob_width(int width);
227 // Access to the global median ledding. The ledding is the distance between
228 // two adjacent text lines. This value can be used to get a rough estimate
229 // for the amount of space between two lines of text. As a result, it
230 // is used to calculate appropriate spacing between adjacent rows of text.
231 void set_global_median_ledding(int ledding);
232
233 // Updates the nearest neighbors for each ColPartition in clean_part_grid_.
234 // The neighbors are most likely SingletonPartner calls after the neighbors
235 // are assigned. This is hear until it is decided to remove the
236 // nearest_neighbor code in ColPartition
237 void FindNeighbors();
238
243
244 // High level function to mark partitions as table rows/cells.
245 // When this function is done, the column partitions in clean_part_grid_
246 // should mostly be marked as tables.
247 void MarkTablePartitions();
248 // Marks partitions given a local view of a single partition
251 // Check if the partition has at least one large gap between words or no
252 // significant gap at all
253 // TODO(nbeato): Make const, prevented because blobnbox array access
254 bool HasWideOrNoInterWordGap(ColPartition* part) const;
255 // Checks if a partition is adjacent to leaders on the page
256 bool HasLeaderAdjacent(const ColPartition& part);
257 // Filter individual text partitions marked as table partitions
258 // consisting of paragraph endings, small section headings, and
259 // headers and footers.
260 void FilterFalseAlarms();
263 // Mark all ColPartitions as table cells that have a table cell above
264 // and below them
266
279
280 // Get Column segments from best_columns_
281 void GetColumnBlocks(ColPartitionSet** columns,
282 ColSegment_LIST *col_segments);
283
284 // Group Column segments into consecutive single column regions.
285 void GroupColumnBlocks(ColSegment_LIST *current_segments,
286 ColSegment_LIST *col_segments);
287
288 // Check if two boxes are consecutive within the same column
289 bool ConsecutiveBoxes(const TBOX &b1, const TBOX &b2);
290
291 // Set the ratio of candidate table partitions in each column
292 void SetColumnsType(ColSegment_LIST* col_segments);
293
294 // Merge Column Blocks that were split due to the presence of a table
296
302
303 // Merge partititons cells into table columns
304 // Differs from paper by just looking at marked table partitions
305 // instead of similarity metric.
306 // Modified section 4.1 of paper.
307 void GetTableColumns(ColSegment_LIST *table_columns);
308
309 // Finds regions within a column that potentially contain a table.
310 // Ie, the table columns from GetTableColumns are turned into boxes
311 // that span the entire page column (using ColumnBlocks found in
312 // earlier functions) in the x direction and the min/max extent of
313 // overlapping table columns in the y direction.
314 // Section 4.2 of paper.
315 void GetTableRegions(ColSegment_LIST *table_columns,
316 ColSegment_LIST *table_regions);
317
318
321
322 // Merge table regions corresponding to tables spanning multiple columns
324 bool BelongToOneTable(const TBOX &box1, const TBOX &box2);
325
326 // Adjust table boundaries by building a tight bounding box around all
327 // ColPartitions contained in it.
329
330 // Grows a table to include partitions that are partially covered
331 // by the table. This includes lines and text. It does not include
332 // noise or images.
333 // On entry, result_box is the minimum size of the result. The results of the
334 // function will union the actual result with result_box.
335 void GrowTableBox(const TBOX& table_box, TBOX* result_box);
336 // Grow a table by increasing the size of the box to include
337 // partitions with significant overlap with the table.
338 void GrowTableToIncludePartials(const TBOX& table_box,
339 const TBOX& search_range,
340 TBOX* result_box);
341 // Grow a table by expanding to the extents of significantly
342 // overlapping lines.
343 void GrowTableToIncludeLines(const TBOX& table_box, const TBOX& search_range,
344 TBOX* result_box);
345 // Checks whether the horizontal line belong to the table by looking at the
346 // side spacing of extra ColParitions that will be included in the table
347 // due to expansion
348 bool HLineBelongsToTable(const ColPartition& part, const TBOX& table_box);
349
350 // Look for isolated column headers above the given table box and
351 // include them in the table
352 void IncludeLeftOutColumnHeaders(TBOX* table_box);
353
354 // Remove false alarms consiting of a single column
356
357 // Return true if at least one gap larger than the global x-height
358 // exists in the horizontal projection
359 bool GapInXProjection(int* xprojection, int length);
360
363 // This function will run the table recognizer and try to find better
364 // bounding boxes. The structures of the tables never leave this function
365 // right now. It just tries to prune and merge tables based on info it
366 // has available.
367 void RecognizeTables();
368
372
373 // Displays Colpartitions marked as table row. Overlays them on top of
374 // part_grid_.
375 void DisplayColSegments(ScrollView* win, ColSegment_LIST *cols,
376 ScrollView::Color color);
377
378 // Displays the colpartitions using a new coloring on an existing window.
379 // Note: This method is only for debug purpose during development and
380 // would not be part of checked in code
382 ScrollView::Color text_color,
383 ScrollView::Color table_color);
385 ScrollView::Color default_color);
387 ColPartitionGrid* grid,
388 ScrollView::Color default_color);
390 ScrollView::Color color);
391
392 // Merge all colpartitions in table regions to make them a single
393 // colpartition and revert types of isolated table cells not
394 // assigned to any table to their original types.
396 ColPartitionSet** columns,
397 WidthCallback* width_cb);
398
400 // Useful objects used during table find process.
402 // Resolution of the connected components in ppi.
404 // Estimate of median x-height over the page
406 // Estimate of the median blob width on the page
408 // Estimate of median leading on the page
410 // Grid to hold cleaned colpartitions after removing all
411 // colpartitions that consist of only noise blobs, and removing
412 // noise blobs from remaining colpartitions.
414 // Grid contains the leaders and ruling lines.
416 // Grid contains the broken down column partitions. It can be thought
417 // of as a "word" grid. However, it usually doesn't break apart text lines.
418 // It does break apart table data (most of the time).
420 // Grid of page column blocks
422 // Grid of detected tables
424 // The reading order of text. Defaults to true, for languages such as English.
426};
427
428} // namespace tesseract.
429
430#endif // TESSERACT_TEXTORD_TABLEFIND_H_
#define CLISTIZEH(CLASSNAME)
Definition: clst.h:879
#define ELISTIZEH(CLASSNAME)
Definition: elst.h:918
@ COL_TEXT
Definition: tablefind.h:32
@ COL_MIXED
Definition: tablefind.h:34
@ COL_TABLE
Definition: tablefind.h:33
@ COL_UNKNOWN
Definition: tablefind.h:31
@ COL_COUNT
Definition: tablefind.h:35
integer coordinate
Definition: points.h:32
Definition: points.h:189
Definition: rect.h:34
void set_bounding_box(const TBOX &other)
Definition: tablefind.h:72
int get_num_table_cells() const
Definition: tablefind.h:76
void set_num_table_cells(int n)
Definition: tablefind.h:81
void set_num_text_cells(int n)
Definition: tablefind.h:90
ColSegType type() const
Definition: tablefind.h:94
void set_top(int y)
Definition: tablefind.h:56
void set_right(int x)
Definition: tablefind.h:68
int get_num_text_cells() const
Definition: tablefind.h:85
const TBOX & bounding_box() const
Definition: tablefind.h:52
void set_left(int x)
Definition: tablefind.h:64
void set_bottom(int y)
Definition: tablefind.h:60
void DisplayColSegments(ScrollView *win, ColSegment_LIST *cols, ScrollView::Color color)
Definition: tablefind.cpp:1871
bool BelongToOneTable(const TBOX &box1, const TBOX &box2)
Definition: tablefind.cpp:1444
void GrowTableBox(const TBOX &table_box, TBOX *result_box)
Definition: tablefind.cpp:1520
void MakeTableBlocks(ColPartitionGrid *grid, ColPartitionSet **columns, WidthCallback *width_cb)
Definition: tablefind.cpp:1997
ScrollView * MakeWindow(int x, int y, const char *window_name)
Definition: tablefind.cpp:518
void InsertFragmentedTextPartition(ColPartition *part)
Definition: tablefind.cpp:402
void IncludeLeftOutColumnHeaders(TBOX *table_box)
Definition: tablefind.cpp:1664
void Init(int grid_size, const ICOORD &bottom_left, const ICOORD &top_right)
Definition: tablefind.cpp:181
const ICOORD & bleft() const
Definition: tablefind.cpp:387
void GrowTableToIncludeLines(const TBOX &table_box, const TBOX &search_range, TBOX *result_box)
Definition: tablefind.cpp:1570
void GetTableColumns(ColSegment_LIST *table_columns)
Definition: tablefind.cpp:1273
void LocateTables(ColPartitionGrid *grid, ColPartitionSet **columns, WidthCallback *width_cb, const FCOORD &reskew)
Definition: tablefind.cpp:259
const ICOORD & tright() const
Definition: tablefind.cpp:390
void SplitAndInsertFragmentedTextPartition(ColPartition *part)
Definition: tablefind.cpp:436
void GroupColumnBlocks(ColSegment_LIST *current_segments, ColSegment_LIST *col_segments)
Definition: tablefind.cpp:538
bool ConsecutiveBoxes(const TBOX &b1, const TBOX &b2)
Definition: tablefind.cpp:568
void SetGlobalSpacings(ColPartitionGrid *grid)
Definition: tablefind.cpp:709
void GetTableRegions(ColSegment_LIST *table_columns, ColSegment_LIST *table_regions)
Definition: tablefind.cpp:1323
bool HasWideOrNoInterWordGap(ColPartition *part) const
Definition: tablefind.cpp:857
void InitializePartitions(ColPartitionSet **all_columns)
Definition: tablefind.cpp:579
bool HasLeaderAdjacent(const ColPartition &part)
Definition: tablefind.cpp:946
void set_resolution(int resolution)
Definition: tablefind.h:138
bool HLineBelongsToTable(const ColPartition &part, const TBOX &table_box)
Definition: tablefind.cpp:1600
void GetColumnBlocks(ColPartitionSet **columns, ColSegment_LIST *col_segments)
Definition: tablefind.cpp:523
void set_global_median_blob_width(int width)
Definition: tablefind.cpp:759
void DisplayColSegmentGrid(ScrollView *win, ColSegmentGrid *grid, ScrollView::Color color)
Definition: tablefind.cpp:1891
ColPartitionGrid leader_and_ruling_grid_
Definition: tablefind.h:415
void MoveColSegmentsToGrid(ColSegment_LIST *segments, ColSegmentGrid *col_seg_grid)
Definition: tablefind.cpp:1176
void InsertLeaderPartition(ColPartition *part)
Definition: tablefind.cpp:410
bool GapInXProjection(int *xprojection, int length)
Definition: tablefind.cpp:1768
void set_global_median_xheight(int xheight)
Definition: tablefind.cpp:756
ColSegmentGrid col_seg_grid_
Definition: tablefind.h:421
int gridheight() const
Definition: tablefind.cpp:384
void InsertCleanPartitions(ColPartitionGrid *grid, TO_BLOCK *block)
Definition: tablefind.cpp:193
static void SetPartitionSpacings(ColPartitionGrid *grid, ColPartitionSet **all_columns)
Definition: tablefind.cpp:586
void set_global_median_ledding(int ledding)
Definition: tablefind.cpp:762
void InsertRulingPartition(ColPartition *part)
Definition: tablefind.cpp:418
void set_left_to_right_language(bool order)
Definition: tablefind.cpp:177
bool AllowBlob(const BLOBNBOX &blob) const
Definition: tablefind.cpp:502
ColSegmentGrid table_grid_
Definition: tablefind.h:423
void SetColumnsType(ColSegment_LIST *col_segments)
Definition: tablefind.cpp:1143
void GrowTableToIncludePartials(const TBOX &table_box, const TBOX &search_range, TBOX *result_box)
Definition: tablefind.cpp:1542
ColPartitionGrid fragmented_text_grid_
Definition: tablefind.h:419
void InsertTextPartition(ColPartition *part)
Definition: tablefind.cpp:394
void SetVerticalSpacing(ColPartition *part)
Definition: tablefind.cpp:666
void DisplayColPartitionConnections(ScrollView *win, ColPartitionGrid *grid, ScrollView::Color default_color)
Definition: tablefind.cpp:1950
void DisplayColPartitions(ScrollView *win, ColPartitionGrid *grid, ScrollView::Color text_color, ScrollView::Color table_color)
Definition: tablefind.cpp:1916
void MarkPartitionsUsingLocalInformation()
Definition: tablefind.cpp:827
ColPartitionGrid clean_part_grid_
Definition: tablefind.h:413
void InsertImagePartition(ColPartition *part)
Definition: tablefind.cpp:421
bool AllowTextPartition(const ColPartition &part) const
Definition: tablefind.cpp:489