21 #pragma warning(disable:4244) // Conversion warnings 25 #include "config_auto.h" 31 #include "allheaders.h" 148 "Debug table marking steps in detail");
150 "Show page stats used in table finding");
152 "Enables the table recognizer for table layout and filtering.");
165 global_median_xheight_(0),
166 global_median_blob_width_(0),
167 global_median_ledding_(0),
168 left_to_right_language_(true) {
186 const ICOORD& top_right) {
225 BLOBNBOX_CLIST* part_boxes = part->
boxes();
226 BLOBNBOX_C_IT pit(part_boxes);
227 for (pit.mark_cycle_pt(); !pit.cycled_list(); pit.forward()) {
234 if (leader_part == NULL) {
238 leader_part->
AddBox(pblob);
240 clean_part->
AddBox(pblob);
247 if (leader_part != NULL) {
270 #ifndef GRAPHICS_DISABLED 279 table_win =
MakeWindow(100, 300,
"Fragmented Text");
282 #endif // GRAPHICS_DISABLED 289 ColSegment_LIST column_blocks;
303 ColSegment_LIST table_columns;
309 ColSegment_LIST table_regions;
312 #ifndef GRAPHICS_DISABLED 318 #endif // GRAPHICS_DISABLED 334 #ifndef GRAPHICS_DISABLED 341 #endif // GRAPHICS_DISABLED 348 #ifndef GRAPHICS_DISABLED 355 #endif // GRAPHICS_DISABLED 363 #ifndef GRAPHICS_DISABLED 370 #endif // GRAPHICS_DISABLED 443 if (part->
boxes()->empty()) {
453 bool found_split =
true;
454 while (found_split) {
456 BLOBNBOX_C_IT box_it(right_part->
boxes());
464 for (box_it.mark_cycle_pt(); !box_it.cycled_list(); box_it.forward()) {
465 const TBOX& box = box_it.data()->bounding_box();
467 box.
left() - previous_right > kThreshold) {
470 int mid_x = (box.
left() + previous_right) / 2;
472 right_part = left_part->
SplitAt(mid_x);
480 previous_right =
MAX(previous_right, box.
right());
513 return box.
height() > kHeightRequired &&
514 box.
width() > kWidthRequired &&
515 box.
area() > kAreaRequired;
528 ColSegment_LIST* column_blocks) {
531 if (columns != NULL) {
532 ColSegment_LIST new_blocks;
543 ColSegment_LIST* column_blocks) {
544 ColSegment_IT src_it(new_blocks);
545 ColSegment_IT dest_it(column_blocks);
547 for (src_it.mark_cycle_pt(); !src_it.cycled_list(); src_it.forward()) {
550 bool match_found =
false;
552 for (dest_it.mark_cycle_pt(); !dest_it.cycled_list(); dest_it.forward()) {
560 delete src_it.extract();
566 dest_it.add_after_then_move(src_it.extract());
575 return (abs(b1.
left() - b2.
left()) < x_margin) &&
599 int y = part->
MidY();
623 if (right < box.
left()) {
636 if (left > box.
right()) {
688 if (neighbor == part)
694 if (neighbor_box.
top() < part_box.
bottom() &&
695 gap < min_space_below) {
696 min_space_below = gap;
697 below_neighbor = neighbor;
699 else if (part_box.
top() < neighbor_box.
bottom() &&
700 gap < min_space_above) {
701 min_space_above = gap;
702 above_neighbor = neighbor;
714 STATS xheight_stats(0, kMaxVerticalSpacing + 1);
715 STATS width_stats(0, kMaxBlobWidth + 1);
716 STATS ledding_stats(0, kMaxVerticalSpacing + 1);
735 BLOBNBOX_C_IT it(part->
boxes());
736 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
737 xheight_stats.
add(it.data()->bounding_box().height(), 1);
738 width_stats.
add(it.data()->bounding_box().width(), 1);
749 #ifndef GRAPHICS_DISABLED 751 const char* kWindowName =
"X-height (R), X-width (G), and ledding (B)";
757 #endif // GRAPHICS_DISABLED 865 BLOBNBOX_CLIST* part_boxes = part->
boxes();
866 BLOBNBOX_C_IT it(part_boxes);
876 int previous_x1 = -1;
878 int largest_partition_gap_found = -1;
882 const double max_gap = kMaxGapInTextPartition * part->
median_size();
883 const double min_gap = kMinMaxGapInTextPartition * part->
median_size();
885 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
889 if (previous_x1 != -1) {
890 int gap = current_x0 - previous_x1;
901 if (-gap < part->median_size() * kMaxBlobOverlapFactor) {
902 previous_x1 =
MAX(previous_x1, current_x1);
916 if (gap > largest_partition_gap_found)
917 largest_partition_gap_found = gap;
919 previous_x1 = current_x1;
933 if (largest_partition_gap_found == -1)
939 return largest_partition_gap_found < min_gap;
959 const int top = box.
top() + search_size;
960 const int bottom = box.
bottom() - search_size;
964 int x = right_to_left ? box.
right() : box.
left();
967 while ((leader = hsearch.
NextSideSearch(right_to_left)) != NULL) {
1026 int current_spacing = 0;
1027 int upper_spacing = 0;
1033 current_spacing = mid - left;
1034 upper_spacing = upper_mid - left;
1040 current_spacing = right - mid;
1041 upper_spacing = right - upper_mid;
1043 if (current_spacing * kParagraphEndingPreviousLineRatio > upper_spacing)
1049 kStrokeWidthConstantTolerance)) {
1057 kMaxParagraphEndingLeftSpaceMultiple * part->
median_size())
1065 kMinParagraphEndingTextToWhitespaceRatio * upper_part->
space_to_right())
1092 if (top > max_top) {
1096 if (bottom < min_bottom) {
1097 min_bottom = bottom;
1122 if (!upper_part || !lower_part)
1148 ColSegment_IT it(column_blocks);
1149 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1152 int num_table_cells = 0;
1153 int num_text_cells = 0;
1168 if (!num_table_cells && !num_text_cells) {
1169 delete it.extract();
1182 ColSegment_IT it(segments);
1183 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1210 bool neighbor_found =
false;
1211 bool modified =
false;
1221 neighbor_found =
false;
1227 if (neighbor == seg)
1249 neighbor_found =
true;
1256 }
while (neighbor_found);
1278 ColSegment_IT it(table_columns);
1298 bool found_neighbours =
false;
1314 found_neighbours =
true;
1316 if (found_neighbours) {
1317 it.add_after_then_move(col);
1328 ColSegment_LIST* table_regions) {
1329 ColSegment_IT cit(table_columns);
1330 ColSegment_IT rit(table_regions);
1339 bool* table_region =
new bool[page_height];
1343 for (
int i = 0; i < page_height; i++) {
1344 table_region[i] =
false;
1348 cit.move_to_first();
1349 for (cit.mark_cycle_pt(); !cit.cycled_list(); cit.forward()) {
1350 TBOX col_box = cit.data()->bounding_box();
1354 for (
int i = intersection_box.
bottom(); i < intersection_box.
top(); i++) {
1355 table_region[i -
bleft().
y()] =
true;
1359 TBOX current_table_box;
1364 for (
int i = 1; i < page_height; i++) {
1366 if (!table_region[i - 1] && table_region[i]) {
1371 if (table_region[i - 1] && !table_region[i]) {
1373 if (!current_table_box.
null_box()) {
1376 rit.add_after_then_move(seg);
1381 delete[] table_region;
1397 bool neighbor_found =
false;
1398 bool modified =
false;
1402 TBOX search_region(box);
1405 neighbor_found =
false;
1411 if (neighbor == seg)
1429 neighbor_found =
true;
1436 }
while (neighbor_found);
1492 ColSegment_CLIST adjusted_tables;
1493 ColSegment_C_IT it(&adjusted_tables);
1499 TBOX grown_box = table_box;
1507 it.add_after_then_move(col);
1518 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1533 TBOX search_box = table_box;
1547 const TBOX& search_range,
1551 for (
int i = 0; i < 2; ++i) {
1575 const TBOX& search_range,
1590 if (result_box->
contains(part_box))
1605 const TBOX& table_box) {
1623 int num_extra_partitions = 0;
1624 int extra_space_to_right = 0;
1625 int extra_space_to_left = 0;
1628 for (
int i = 0; i < 2; ++i) {
1645 num_extra_partitions++;
1649 extra_space_to_right++;
1650 extra_space_to_left++;
1653 int space_threshold = kSideSpaceMargin * part.
median_size();
1655 extra_space_to_right++;
1657 extra_space_to_left++;
1662 return (extra_space_to_right > num_extra_partitions / 2) ||
1663 (extra_space_to_left > num_extra_partitions / 2);
1677 const int max_distance = kMaxColumnHeaderDistance *
1679 int table_top = table_box->
top();
1682 if (box.
bottom() - table_top > max_distance)
1688 previous_neighbor = NULL;
1693 if (previous_neighbor == NULL) {
1694 previous_neighbor = neighbor;
1711 int* table_xprojection =
new int[page_width];
1720 for (
int i = 0; i < page_width; i++) {
1721 table_xprojection[i] = 0;
1738 BLOBNBOX_CLIST* part_boxes = part->
boxes();
1739 BLOBNBOX_C_IT pit(part_boxes);
1746 int next_position_to_write = 0;
1748 for (pit.mark_cycle_pt(); !pit.cycled_list(); pit.forward()) {
1755 xstart =
MAX(xstart, next_position_to_write);
1756 for (
int i = xstart; i < xend; i++)
1757 table_xprojection[i -
bleft().
x()]++;
1758 next_position_to_write = xend;
1767 delete[] table_xprojection;
1775 for (
int i = 0; i < length; i++) {
1776 if (xprojection[i] > peak_value) {
1777 peak_value = xprojection[i];
1783 if (peak_value < kMinRowsInTable)
1785 double projection_threshold = kSmallTableProjectionThreshold * peak_value;
1786 if (peak_value >= kLargeTableRowCount)
1787 projection_threshold = kLargeTableProjectionThreshold * peak_value;
1789 for (
int i = 0; i < length; i++) {
1790 xprojection[i] = (xprojection[i] >= projection_threshold) ? 1 : 0;
1793 int largest_gap = 0;
1795 for (
int i = 1; i < length; i++) {
1797 if (xprojection[i - 1] && !xprojection[i]) {
1801 if (run_start != -1 && !xprojection[i - 1] && xprojection[i]) {
1802 int gap = i - run_start;
1803 if (gap > largest_gap)
1824 table_win =
MakeWindow(0, 0,
"Table Structure");
1839 ColSegment_CLIST good_tables;
1840 ColSegment_C_IT good_it(&good_tables);
1855 if (table_structure != NULL) {
1860 delete table_structure;
1861 good_it.add_after_then_move(found_table);
1870 for (good_it.mark_cycle_pt(); !good_it.cycled_list(); good_it.forward())
1876 ColSegment_LIST *segments,
1878 #ifndef GRAPHICS_DISABLED 1881 ColSegment_IT it(segments);
1882 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1885 int left_x = box.
left();
1886 int right_x = box.
right();
1887 int top_y = box.
top();
1888 int bottom_y = box.
bottom();
1889 win->
Rectangle(left_x, bottom_y, right_x, top_y);
1897 #ifndef GRAPHICS_DISABLED 1905 int left_x = box.
left();
1906 int right_x = box.
right();
1907 int top_y = box.
top();
1908 int bottom_y = box.
bottom();
1911 win->
Rectangle(left_x, bottom_y, right_x, top_y);
1924 #ifndef GRAPHICS_DISABLED 1932 color = default_color;
1934 color = table_color;
1937 int left_x = box.
left();
1938 int right_x = box.
right();
1939 int top_y = box.
top();
1940 int bottom_y = box.
bottom();
1943 win->
Rectangle(left_x, bottom_y, right_x, top_y);
1958 #ifndef GRAPHICS_DISABLED 1966 int left_x = box.
left();
1967 int right_x = box.
right();
1968 int top_y = box.
top();
1969 int bottom_y = box.
bottom();
1974 int mid_x = (left_x + right_x) / 2;
1975 int mid_y = (top_y + bottom_y) / 2;
1976 int other_x = (upper_box.
left() + upper_box.
right()) / 2;
1977 int other_y = (upper_box.
top() + upper_box.
bottom()) / 2;
1980 win->
Line(mid_x, mid_y, other_x, other_y);
1985 int mid_x = (left_x + right_x) / 2;
1986 int mid_y = (top_y + bottom_y) / 2;
1987 int other_x = (lower_box.
left() + lower_box.
right()) / 2;
1988 int other_y = (lower_box.
top() + lower_box.
bottom()) / 2;
1991 win->
Line(mid_x, mid_y, other_x, other_y);
2039 if (table_partition) {
2040 table_partition->
Absorb(part, width_cb);
2042 table_partition = part;
2047 if (table_partition) {
2059 grid->
InsertBBox(
true,
true, table_partition);
2068 num_table_cells_(0),
2083 return kBoxColors[type_];
2094 if (num_table_cells_ > kTableColumnThreshold * num_text_cells_)
2096 else if (num_text_cells_ > num_table_cells_)
ColPartition * ColumnContaining(int x, int y)
const double kTableColumnThreshold
const int kSideSpaceMargin
void Line(int x1, int y1, int x2, int y2)
const double kMaxGapInTextPartition
void GetTableRegions(ColSegment_LIST *table_columns, ColSegment_LIST *table_regions)
const int kMaxColumnHeaderDistance
void IncludeLeftOutColumnHeaders(TBOX *table_box)
bool MatchingStrokeWidth(const ColPartition &other, double fractional_tolerance, double constant_tolerance) const
TBOX intersection(const TBOX &box) const
void set_space_below(int space)
ColPartition * CopyButDontOwnBlobs()
ColPartition * nearest_neighbor_below() const
bool overlap(const TBOX &box) const
void MoveColSegmentsToGrid(ColSegment_LIST *segments, ColSegmentGrid *col_seg_grid)
bool AllowTextPartition(const ColPartition &part) const
void DisplayBoxes(ScrollView *window)
const double kAllowBlobWidth
void set_nearest_neighbor_below(ColPartition *part)
bool VSignificantCoreOverlap(const ColPartition &other) const
void set_global_median_blob_width(int width)
bool GapInXProjection(int *xprojection, int length)
ColSegmentGrid table_grid_
void DisplayColPartitionConnections(ScrollView *win, ColPartitionGrid *grid, ScrollView::Color default_color)
const double kMinParagraphEndingTextToWhitespaceRatio
const double kMaxBlobOverlapFactor
void SetGlobalSpacings(ColPartitionGrid *grid)
const ICOORD & bleft() const
void LocateTables(ColPartitionGrid *grid, ColPartitionSet **columns, WidthCallback *width_cb, const FCOORD &reskew)
void plot(ScrollView *window, float xorigin, float yorigin, float xscale, float yscale, ScrollView::Color colour) const
void Init(int gridsize, const ICOORD &bleft, const ICOORD &tright)
TBOX bounding_union(const TBOX &box) const
ScrollView * MakeWindow(int x, int y, const char *window_name)
void GetColumnBlocks(ColPartitionSet **columns, ColSegment_LIST *col_segments)
const ICOORD & bleft() const
const double kLargeTableProjectionThreshold
inT16 x() const
access function
StructuredTable * RecognizeTable(const TBOX &guess_box)
bool HLineBelongsToTable(const ColPartition &part, const TBOX &table_box)
void set_flow(BlobTextFlowType f)
void set_line_grid(ColPartitionGrid *lines)
int direction(EDGEPT *point)
const double kAllowBlobHeight
void InitializePartitions(ColPartitionSet **all_columns)
const double kMaxXProjectionGapFactor
bool HasLeaderAdjacent(const ColPartition &part)
bool left_to_right_language_
#define BOOL_VAR(name, val, comment)
const int kRulingVerticalMargin
ColPartitionGrid leader_and_ruling_grid_
void FilterParagraphEndings()
const double kSmallTableProjectionThreshold
bool major_x_overlap(const TBOX &box) const
bool IsHorizontalLine() const
const int kAdjacentLeaderSearchPadding
int space_to_right() const
void AddBox(BLOBNBOX *box)
const int kMinBoxesInTextPartition
int RightAtY(int y) const
const double kAllowTextArea
BlobRegionType region_type() const
const int kMinRowsInTable
void InsertTextPartition(ColPartition *part)
void RepositionIterator()
bool major_y_overlap(const TBOX &box) const
void GroupColumnBlocks(ColSegment_LIST *current_segments, ColSegment_LIST *col_segments)
void InsertRulingPartition(ColPartition *part)
void set_space_above(int space)
ColPartition * nearest_neighbor_above() const
void SetUniqueMode(bool mode)
void MarkTablePartitions()
void StartVerticalSearch(int xmin, int xmax, int y)
void SetPartitionType(int resolution, ColPartitionSet *columns)
bool textord_tablefind_show_stats
const double kAllowBlobArea
ColPartition * SplitAt(int split_x)
void DisplayColPartitions(ScrollView *win, ColPartitionGrid *grid, ScrollView::Color text_color, ScrollView::Color table_color)
const double kSplitPartitionSize
int global_median_blob_width_
bool AllowBlob(const BLOBNBOX &blob) const
void set_min_height(int height)
ColPartition * ShallowCopy() const
void GetColumnBoxes(int y_bottom, int y_top, ColSegment_LIST *segments)
void set_max_text_height(int height)
void Display(ScrollView *window, ScrollView::Color color)
void Rectangle(int x1, int y1, int x2, int y2)
const double kAllowTextHeight
void InsertBBox(bool h_spread, bool v_spread, BBC *bbox)
const int kMaxVerticalSpacing
const int kMaxBoxesInDataPartition
const TBOX & bounding_box() const
const double kStrokeWidthConstantTolerance
inT16 y() const
access_function
bool BelongToOneTable(const TBOX &box1, const TBOX &box2)
const ICOORD & tright() const
double overlap_fraction(const TBOX &box) const
void MarkPartitionsUsingLocalInformation()
void DeleteObject(T *object)
int global_median_ledding_
void InsertCleanPartitions(ColPartitionGrid *grid, TO_BLOCK *block)
void GetTableColumns(ColSegment_LIST *table_columns)
void StartSideSearch(int x, int ymin, int ymax)
ScrollView::Color BoxColor() const
void GrowTableToIncludePartials(const TBOX &table_box, const TBOX &search_range, TBOX *result_box)
const double kMinOverlapWithTable
const TBOX & bounding_box() const
bool contains(const FCOORD pt) const
void set_space_to_right(int space)
PolyBlockType type() const
void MakeTableBlocks(ColPartitionGrid *grid, ColPartitionSet **columns, WidthCallback *width_cb)
void RefinePartitionPartners(bool get_desperate)
int global_median_xheight_
void InsertBox(const TBOX &other)
const double kParagraphEndingPreviousLineRatio
void add(inT32 value, inT32 count)
void FilterHeaderAndFooter()
BBC * NextVerticalSearch(bool top_to_bottom)
ScrollView * MakeWindow(int x, int y, const char *window_name)
void set_text_grid(ColPartitionGrid *text)
void DeleteSingleColumnTables()
void set_space_to_left(int space)
void SplitAndInsertFragmentedTextPartition(ColPartition *part)
void set_num_text_cells(int n)
void GridMergeTableRegions()
bool ConsecutiveBoxes(const TBOX &b1, const TBOX &b2)
void GridMergeColumnBlocks()
void FindPartitionPartners()
const double kMaxTableCellXheight
BBC * NextSideSearch(bool right_to_left)
const double kAllowTextWidth
void Init(int grid_size, const ICOORD &bottom_left, const ICOORD &top_right)
const double kStrokeWidthFractionalTolerance
bool IsInSameColumnAs(const ColPartition &part) const
ColPartition * SingletonPartner(bool upper)
const int kLargeTableRowCount
bool textord_tablefind_show_mark
void set_global_median_ledding(int ledding)
void DisplayColSegments(ScrollView *win, ColSegment_LIST *cols, ScrollView::Color color)
static void SetPartitionSpacings(ColPartitionGrid *grid, ColPartitionSet **all_columns)
void AdjustTableBoundaries()
void set_num_table_cells(int n)
void Absorb(ColPartition *other, WidthCallback *cb)
int space_to_left() const
ColPartitionGrid clean_part_grid_
bool MatchingSizes(const ColPartition &other) const
int median_bottom() const
const TBOX & bounding_box() const
void GrowTableBox(const TBOX &table_box, TBOX *result_box)
void set_global_median_xheight(int xheight)
void StartRectSearch(const TBOX &rect)
void SetColumnsType(ColSegment_LIST *col_segments)
void set_bounding_box(const TBOX &other)
void set_left_to_right_language(bool order)
const double kMinMaxGapInTextPartition
void DisplayColSegmentGrid(ScrollView *win, ColSegmentGrid *grid, ScrollView::Color color)
void InsertLeaderPartition(ColPartition *part)
void SmoothTablePartitionRuns()
const double kMaxParagraphEndingLeftSpaceMultiple
void set_inside_table_column(bool val)
void InsertFragmentedTextPartition(ColPartition *part)
void SetVerticalSpacing(ColPartition *part)
const ICOORD & tright() const
void set_nearest_neighbor_above(ColPartition *part)
const TBOX & bounding_box() const
void InsertImagePartition(ColPartition *part)
#define CLISTIZE(CLASSNAME)
bool textord_tablefind_recognize_tables
ColSegmentGrid col_seg_grid_
BlobTextFlowType flow() const
ColPartitionGrid fragmented_text_grid_
void GrowTableToIncludeLines(const TBOX &table_box, const TBOX &search_range, TBOX *result_box)
BlobTextFlowType flow() const
BlobRegionType blob_type() const
bool inside_table_column()
bool HasWideOrNoInterWordGap(ColPartition *part) const
void GridCoords(int x, int y, int *grid_x, int *grid_y) const
void ClearGridData(void(*free_method)(BBC *))
void set_blob_type(BlobRegionType t)