///////////////////////////////////////////////////////////////////////
// File: tablefind.cpp
// Description: Helper classes to find tables from ColPartitions.
// Author: Faisal Shafait (faisal.shafait@dfki.de)
// Created: Tue Jan 06 11:13:01 PST 2009
//
// (C) Copyright 2009, Google Inc.
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
// http://www.apache.org/licenses/LICENSE-2.0
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
///////////////////////////////////////////////////////////////////////
#include "colfind.h"
#include <math.h>
#ifdef HAVE_CONFIG_H
#include "config_auto.h"
#endif
#ifdef HAVE_LIBLEPT
#include "allheaders.h"
#endif
namespace tesseract {
// Maximum vertical spacing between neighbor partitions
const int kMaxVerticalSpacing = 500;
// Minimum number of components in a text partition. A partition having fewer
// components than that is more likely a data partition and is a candidate
// table cell.
const int kMinBoxesInTextPartition = 10;
// Maximum number of components that a data partition can have
const int kMaxBoxesInDataPartition = 20;
// Maximum allowed gap in a text partitions as a multiple of its median size.
const double kMaxGapInTextPartition = 4.0;
// Minimum value that the maximum gap in a text partition should have as a
// factor of its median size.
const double kMinMaxGapInTextPartition = 0.5;
// Maximum x-height a table partition can have as a multiple of global
// median x-height
const double kMaxTableCellXheight = 2.0;
// Maximum line spacing between a table column header and column contents
// for merging the two
const int kMaxColumnHeaderDistance = 100;
// Minimum ratio of num_table_partitions to num_text_partitions in a column
// block to be called it a table column
const double kTableColumnThreshold = 3.0;
// Search for horizontal ruling lines within the vertical margin as a
// multiple of grid size
const int kRulingVerticalMargin = 3;
// Minimum overlap that a colpartition must have with a table region
// to become part of that table
const double kMinOverlapWithTable = 0.6;
// Maximum side space (distance from column boundary) that a typical
// text-line in flowing text should have as a multiple of its x-height
// (Median size).
const int kSideSpaceMargin = 10;
// Fraction of the peak of x-projection of a table region to set the
// threshold for the x-projection histogram
const double kProjectionThreshold = 0.35;
// Minmimum number of rows in a table
const int kMinRowsInTable = 3;
BOOL_VAR(textord_dump_table_images, false, "Paint table detection output");
BOOL_VAR(textord_show_tables, false, "Show table regions");
ELISTIZE(ColSegment)
CLISTIZE(ColSegment)
// Copy cleaned partitions from part_grid_ to clean_part_grid_ and
// insert dot-like noise into period_grid_
void ColumnFinder::GetCleanPartitions(TO_BLOCK* block) {
double min_dim = block->line_size/3.0;
// Initialize clean partitions list and grid
clean_part_grid_.Init(gridsize(), bleft(), tright());
period_grid_.Init(gridsize(), bleft(), tright());
// Iterate the ColPartitions in the grid.
GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT>
gsearch(&part_grid_);
gsearch.StartFullSearch();
ColPartition* part;
while ((part = gsearch.NextFullSearch()) != NULL) {
ColPartition* clean_part = part->ShallowCopy();
// Insert all non-text partitions to clean_parts
if (!part->IsTextType()) {
clean_part_grid_.InsertBBox(true, true, clean_part);
continue;
}
// Insert text colpartitions after removing noisy components from them
BLOBNBOX_CLIST* part_boxes = part->boxes();
BLOBNBOX_C_IT pit(part_boxes);
for (pit.mark_cycle_pt(); !pit.cycled_list(); pit.forward()) {
BLOBNBOX *pblob = pit.data();
if (!pblob->noise_flag()) {
clean_part->AddBox(pblob);
} else {
TBOX blob_box = pblob->bounding_box();
if (blob_box.height() < min_dim && blob_box.width() < 2*min_dim) {
period_grid_.InsertBBox(false, false, pblob);
}
}
}
if (!clean_part->IsEmpty())
clean_part_grid_.InsertBBox(true, true, clean_part);
}
// TODO(rays) This is the previous period blob code. Neither is completely
// satisfactory, as a more disciplined approach to noise removal would be
// better, so revisit this choice and decide what to keep when the earlier
// stages do a better job of noise removal.
#if 0
BLOBNBOX_IT sit(&block->small_blobs);
BLOBNBOX_IT nit(&block->noise_blobs);
BLOBNBOX_IT it(&period_blobs_);
// Insert dot sized boxes from small_blobs into period_blobs_
for (sit.mark_cycle_pt(); !sit.cycled_list(); sit.forward()) {
BLOBNBOX * blob = sit.data();
TBOX blob_box = blob->bounding_box();
if (blob_box.height() < min_dim && blob_box.width() < 2*min_dim) {
it.add_after_then_move(sit.extract());
}
}
// Insert dot sized boxes from noise_blobs into period_blobs_
for (nit.mark_cycle_pt(); !nit.cycled_list(); nit.forward()) {
BLOBNBOX * blob = nit.data();
TBOX blob_box = blob->bounding_box();
if (blob_box.height() < min_dim && blob_box.width() < 2*min_dim) {
it.add_after_then_move(nit.extract());
}
}
InsertBlobList(false, false, false, &period_blobs_, false, &period_grid_);
#endif
}
// High level function to perform table detection
void ColumnFinder::LocateTables() {
// Make single-column blocks from good_columns_ partitions. col_segments are
// moved to a grid later which takes the ownership
ColSegment_LIST column_blocks;
GetColumnBlocks(&column_blocks);
SetPartitionSpacings();
// Mark ColPartitions as being candidate table partition depending on
// the inter-word spacing
GridMarkTablePartitions();
FilterFalseAlarms();
SmoothTablePartitionRuns();
// Set the ratio of candidate table partitions in each column
SetColumnsType(&column_blocks);
// Move column segments to col_seg_grid_
MoveColSegmentsToGrid(&column_blocks, &col_seg_grid_);
// Detect split in column layout that might have occured due to the
// presence of a table. In such a case, merge the corresponding columns.
GridMergeColumnBlocks();
// Group horizontally overlapping table partitions into table columns.
// table_columns created here get deleted at the end of this method.
ColSegment_LIST table_columns;
GetTableColumns(&table_columns);
// Within each column, mark the range table regions occupy based on the
// table columns detected. table_regions are moved to a grid later which
// takes the ownership
ColSegment_LIST table_regions;
GetTableRegions(&table_columns, &table_regions);
// Merge table regions across columns for tables spanning multiple
// columns
MoveColSegmentsToGrid(&table_regions, &table_grid_);
GridMergeTableRegions();
// Adjust table boundaries by including nearby horizontal lines and left
// out column headers
AdjustTableBoundaries();
GridMergeTableRegions();
// Remove false alarms consiting of a single column
DeleteSingleColumnTables();
if (textord_show_tables) {
ScrollView* table_win = MakeWindow(1500, 300, "Detected Tables");
DisplayColPartitions(table_win, ScrollView::BLUE);
DisplayColSegments(&table_columns, table_win, ScrollView::GREEN);
table_grid_.DisplayBoxes(table_win);
}
if (textord_dump_table_images)
WriteToPix();
// Merge all colpartitions in table regions to make them a single
// colpartition and revert types of isolated table cells not
// assigned to any table to their original types.
MakeTableBlocks();
}
// Make single-column blocks from good_columns_ partitions.
void ColumnFinder::GetColumnBlocks(ColSegment_LIST* column_blocks) {
for (int i = 0; i < gridheight_; ++i) {
ColPartitionSet* columns = best_columns_[i];
if (columns != NULL) {
ColSegment_LIST new_blocks;
// Get boxes from the current vertical position on the grid
columns->GetColumnBoxes(i*gridsize_, (i + 1) * gridsize_, &new_blocks);
// Merge the new_blocks boxes into column_blocks if they are well-aligned
GroupColumnBlocks(&new_blocks, column_blocks);
}
}
}
// Merge column segments into the current list if they are well aligned.
void ColumnFinder::GroupColumnBlocks(ColSegment_LIST* new_blocks,
ColSegment_LIST* column_blocks) {
ColSegment_IT src_it(new_blocks);
ColSegment_IT dest_it(column_blocks);
// iterate through the source list
for (src_it.mark_cycle_pt(); !src_it.cycled_list(); src_it.forward()) {
ColSegment* src_seg = src_it.data();
TBOX src_box = src_seg->bounding_box();
bool match_found = false;
// iterate through the destination list to find a matching column block
for (dest_it.mark_cycle_pt(); !dest_it.cycled_list(); dest_it.forward()) {
ColSegment* dest_seg = dest_it.data();
TBOX dest_box = dest_seg->bounding_box();
if (ConsecutiveBoxes(src_box, dest_box)) {
// If matching block is found, insert the current block into it
// and delete the soure block
dest_seg->InsertBox(src_box);
match_found = true;
delete src_it.extract();
break;
}
}
// If no match is found, just append the source block to column_blocks
if (!match_found) {
dest_it.add_after_then_move(src_it.extract());
}
}
}
// are the two boxes immediate neighbors along the vertical direction
bool ColumnFinder::ConsecutiveBoxes(const TBOX &b1, const TBOX &b2) {
int x_margin = 20;
int y_margin = 5;
return (abs(b1.left() - b2.left()) < x_margin) &&
(abs(b1.right() - b2.right()) < x_margin) &&
(abs(b1.top()-b2.bottom()) < y_margin ||
abs(b2.top()-b1.bottom()) < y_margin);
}
// Set left, right and top, bottom spacings of each colpartition.
void ColumnFinder::SetPartitionSpacings() {
// Iterate the ColPartitions in the grid.
GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT>
gsearch(&clean_part_grid_);
gsearch.StartFullSearch();
ColPartition* part;
while ((part = gsearch.NextFullSearch()) != NULL) {
ColPartitionSet* columns = best_columns_[gsearch.GridY()];
TBOX box = part->bounding_box();
int y = part->MidY();
ColPartition* left_column = columns->ColumnContaining(box.left(), y);
ColPartition* right_column = columns->ColumnContaining(box.right(), y);
// set distance from left column as space to the left
if (left_column) {
int left_space = MAX(0, box.left() - left_column->LeftAtY(y));
part->set_space_to_left(left_space);
}
// set distance from right column as space to the right
if (right_column) {
int right_space = MAX(0, right_column->RightAtY(y) - box.right());
part->set_space_to_right(right_space);
}
SetVerticalSpacing(part);
}
SetGlobalSpacings();
}
// Set spacing and closest neighbors above and below a given colpartition.
void ColumnFinder::SetVerticalSpacing(ColPartition* part) {
TBOX box = part->bounding_box();
int top_range = MIN(box.top() + kMaxVerticalSpacing, tright().y());
int bottom_range = MAX(box.bottom() - kMaxVerticalSpacing, bleft().y());
box.set_top(top_range);
box.set_bottom(bottom_range);
TBOX part_box = part->bounding_box();
// Start a rect search
GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT>
rectsearch(&clean_part_grid_);
rectsearch.StartRectSearch(box);
ColPartition* neighbor;
int min_space_above = kMaxVerticalSpacing;
int min_space_below = kMaxVerticalSpacing;
ColPartition* above_neighbor = NULL;
ColPartition* below_neighbor = NULL;
while ((neighbor = rectsearch.NextRectSearch()) != NULL) {
if (neighbor == part)
continue;
TBOX neighbor_box = neighbor->bounding_box();
if (neighbor_box.major_x_overlap(part_box)) {
int gap = abs(part->median_bottom() - neighbor->median_bottom());
// If neighbor is below current partition
if (neighbor_box.top() < part_box.bottom() &&
gap < min_space_below) {
min_space_below = gap;
below_neighbor = neighbor;
} // If neighbor is above current partition
else if (part_box.top() < neighbor_box.bottom() &&
gap < min_space_above) {
min_space_above = gap;
above_neighbor = neighbor;
}
}
}
part->set_space_above(min_space_above);
part->set_space_below(min_space_below);
part->set_nearest_neighbor_above(above_neighbor);
part->set_nearest_neighbor_below(below_neighbor);
}
// Set global spacing and x-height estimates
void ColumnFinder::SetGlobalSpacings() {
STATS xheight_stats(0, kMaxVerticalSpacing + 1);
STATS ledding_stats(0, kMaxVerticalSpacing + 1);
// Iterate the ColPartitions in the grid.
GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT>
gsearch(&clean_part_grid_);
gsearch.StartFullSearch();
ColPartition* part;
while ((part = gsearch.NextFullSearch()) != NULL) {
if (part->IsTextType()) {
xheight_stats.add(part->median_size(), 1);
ledding_stats.add(part->space_above(), 1);
ledding_stats.add(part->space_below(), 1);
}
}
// Set estimates based on median of statistics obtained
global_median_xheight_ = static_cast<int>(xheight_stats.median() + 0.5);
global_median_ledding_ = static_cast<int>(ledding_stats.median() + 0.5);
if (textord_show_tables) {
ScrollView* stats_win = MakeWindow(500, 10,
"X-height and ledding histograms");
xheight_stats.plot(stats_win, 10, 200, 2, 15, ScrollView::GREEN);
ledding_stats.plot(stats_win, 10, 200, 2, 15, ScrollView::RED);
}
}
// Three types of partitions are maked as table partitions:
// 1- Partitions that have at lease one large gap between words
// 2- Partitions that consist of only one word (no significant gap
// between components)
// 3- Partitions that vertically overlap with other partitions within the
// same column.
void ColumnFinder::GridMarkTablePartitions() {
// Iterate the ColPartitions in the grid.
GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT>
gsearch(&clean_part_grid_);
gsearch.StartFullSearch();
ColPartition* part;
while ((part = gsearch.NextFullSearch()) != NULL) {
if (!part->IsTextType()) // Only consider text partitions
continue;
// Only consider partitions in dominant font size or smaller
if (part->median_size() > kMaxTableCellXheight * global_median_xheight_)
continue;
// Mark partitions with a large gap, or no significant gap as
// table partitions.
// Comments: It produces several false alarms at:
// - last line of a paragraph
// - single word section headings
// - page headers and footers
// - numbered equations
// - line drawing regions
// TODO(faisal): detect and fix above-mentioned cases
if (HasWideOrNoInterWordGap(part)) {
part->set_table_type();
}
}
}
// Check if the partition has at lease one large gap between words or no
// significant gap at all
bool ColumnFinder::HasWideOrNoInterWordGap(ColPartition* part) {
BLOBNBOX_CLIST* part_boxes = part->boxes();
BLOBNBOX_C_IT pit(part_boxes);
if (part->bounding_box().width() <
kMinBoxesInTextPartition * part->median_size() &&
pit.length() < kMinBoxesInTextPartition)
return true;
// Make a copy of the components in the current partition and insert periods
// into it to compute gaps while taking periods into account.
BLOBNBOX_CLIST boxes;
BLOBNBOX_C_IT it(&boxes);
for (pit.mark_cycle_pt(); !pit.cycled_list(); pit.forward()) {
BLOBNBOX *pblob = pit.data();
it.add_after_then_move(pblob);
}
// Start rectangular search to find periods in this partition
GridSearch<BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT> rectsearch(&period_grid_);
TBOX part_box = part->bounding_box();
rectsearch.StartRectSearch(part_box);
BLOBNBOX* period;
while ((period = rectsearch.NextRectSearch()) != NULL) {
// Insert a period only if it lies in a gap between two consecutive boxes
if (LiesInGap(period, &boxes))
boxes.add_sorted(SortByBoxLeft<BLOBNBOX>, true, period);
}
int current_x0;
int current_x1;
int previous_x1 = -1;
int max_partition_gap = -1;
double max_gap = kMaxGapInTextPartition * part->median_size();
double min_gap = kMinMaxGapInTextPartition * part->median_size();
for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
BLOBNBOX *blob = it.data();
current_x0 = blob->bounding_box().left();
current_x1 = blob->bounding_box().right();
if (previous_x1 != -1) {
int gap = current_x0 - previous_x1;
// If a large enough gap is found, mark it as a table cell (return true)
if (gap > max_gap)
return true;
if (gap > max_partition_gap)
max_partition_gap = gap;
}
previous_x1 = current_x1;
}
// Since no large gap was found, return false if the partition is too
// long to be a data cell
if (part->bounding_box().width() >
kMaxBoxesInDataPartition * part->median_size() ||
pit.length() > kMaxBoxesInDataPartition)
return false;
// return true if the maximum gap found is smaller than the minimum allowed
// max_gap in a text partition
return (max_partition_gap < min_gap);
}
// Check if the period lies in a gap between consecutive boxes
bool ColumnFinder::LiesInGap(BLOBNBOX* period, BLOBNBOX_CLIST* boxes) {
BLOBNBOX_C_IT it(boxes);
TBOX period_box = period->bounding_box();
int num_boxes = it.length();
// skip the first element since it has no gap to its left.
it.forward();
for (int i = 1; i < num_boxes; i++) {
TBOX box = it.data()->bounding_box();
TBOX previous_blob = it.data_relative(-1)->bounding_box();
TBOX gap_box = TBOX(previous_blob.botright(), box.topleft());
if (gap_box.major_overlap(period_box)) {
return true;
}
it.forward();
}
return false;
}
// Filter individual text partitions marked as table partitions
// consisting of paragraph endings, small section headings, and
// headers and footers.
void ColumnFinder::FilterFalseAlarms() {
// Detect last line of paragraph
// Iterate the ColPartitions in the grid.
GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT>
gsearch(&clean_part_grid_);
gsearch.StartFullSearch();
ColPartition* part;
while ((part = gsearch.NextFullSearch()) != NULL) {
if (part->type() != PT_TABLE)
continue; // Consider only table partitions
// Paragraph ending should have flowing text above it.
ColPartition* upper_part = part->nearest_neighbor_above();
if (!upper_part)
continue;
if (upper_part->type() != PT_FLOWING_TEXT)
continue;
if (upper_part->bounding_box().width() <
2 * part->bounding_box().width())
continue;
// Paragraph ending should be left-aligned to text line above it.
if (abs(part->bounding_box().left() - upper_part->bounding_box().left())
> global_median_xheight_)
continue;
// Ledding above the line should be less than ledding below
if (part->space_above() < part->space_below() &&
part->space_above() <= 2 * global_median_ledding_)
part->clear_table_type();
}
// Consider top-most text colpartition as header and bottom most as footer
ColPartition* header = NULL;
ColPartition* footer = NULL;
int max_top = -MAX_INT32;
int min_bottom = MAX_INT32;
gsearch.StartFullSearch();
while ((part = gsearch.NextFullSearch()) != NULL) {
if (!part->IsTextType())
continue; // Consider only text partitions
int top = part->bounding_box().top();
int bottom = part->bounding_box().bottom();
if (top > max_top) {
max_top = top;
header = part;
}
if (bottom < min_bottom) {
min_bottom = bottom;
footer = part;
}
}
if (header)
header->clear_table_type();
if (footer)
footer->clear_table_type();
}
// Mark all ColPartitions as table cells that have a table cell above
// and below them
// TODO(faisal): This is too aggressive at the moment. The method needs to
// consider spacing and alignment as well. Detection of false alarm table cells
// should also be done as part of it.
void ColumnFinder::SmoothTablePartitionRuns() {
// Iterate the ColPartitions in the grid.
GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT>
gsearch(&clean_part_grid_);
gsearch.StartFullSearch();
ColPartition* part;
while ((part = gsearch.NextFullSearch()) != NULL) {
if (part->type() >= PT_TABLE)
continue; // Consider only text partitions
ColPartition* upper_part = part->nearest_neighbor_above();
ColPartition* lower_part = part->nearest_neighbor_below();
if (!upper_part || !lower_part)
continue;
if (upper_part->type() == PT_TABLE && lower_part->type() == PT_TABLE)
part->set_table_type();
}
}
// Set the type of a column segment based on the ratio of table to text cells
void ColumnFinder::SetColumnsType(ColSegment_LIST* column_blocks) {
ColSegment_IT it(column_blocks);
for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
ColSegment* seg = it.data();
TBOX box = seg->bounding_box();
int num_table_cells = 0;
int num_text_cells = 0;
GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT>
rsearch(&clean_part_grid_);
rsearch.StartRectSearch(box);
ColPartition* part;
while ((part = rsearch.NextRectSearch()) != NULL) {
if (!rsearch.ReturnedSeedElement())
continue; // Consider each partition only once
if (part->type() == PT_TABLE) {
num_table_cells++;
} else if (part->type() == PT_FLOWING_TEXT) {
num_text_cells++;
}
}
// If a column block has no text or table partition in it, it is not needed
// for table detection.
if (!num_table_cells && !num_text_cells) {
delete it.extract();
} else {
seg->set_num_table_cells(num_table_cells);
seg->set_num_text_cells(num_text_cells);
// set column type based on the ratio of table to text cells
seg->set_type();
}
}
}
// Move column blocks to grid
void ColumnFinder::MoveColSegmentsToGrid(ColSegment_LIST *segments,
ColSegmentGrid *col_seg_grid) {
col_seg_grid->Init(gridsize(), bleft(), tright());
ColSegment_IT it(segments);
for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
ColSegment* seg = it.extract();
col_seg_grid->InsertBBox(true, true, seg);
}
}
// Merge column blocks if a split is detected due to the presence of a
// table. A text block is considered split if it has multiple
// neighboring blocks above/below it, and at least one of the
// neighboring blocks is of table type (has a high density of table
// partitions). In this case neighboring blocks in the direction
// (above/below) of the table block are merged with the text block.
// Comment: This method does not handle split due to a full page table
// since table columns in this case do not have a text column on which
// split decision can be based.
void ColumnFinder::GridMergeColumnBlocks() {
int margin = gridsize_;
// Iterate the Column Blocks in the grid.
GridSearch<ColSegment, ColSegment_CLIST, ColSegment_C_IT>
gsearch(&col_seg_grid_);
gsearch.StartFullSearch();
ColSegment* seg;
while ((seg = gsearch.NextFullSearch()) != NULL) {
if (seg->type() != COL_TEXT)
continue; // only consider text blocks for split detection
bool neighbor_found = false;
bool modified = false; // Modified at least once
// keep expanding current box as long as neighboring table columns
// are found above or below it.
do {
TBOX box = seg->bounding_box();
// slightly expand the search region vertically
int top_range = MIN(box.top() + margin, tright().y());
int bottom_range = MAX(box.bottom() - margin, bleft().y());
box.set_top(top_range);
box.set_bottom(bottom_range);
neighbor_found = false;
GridSearch<ColSegment, ColSegment_CLIST, ColSegment_C_IT>
rectsearch(&col_seg_grid_);
rectsearch.StartRectSearch(box);
ColSegment* neighbor;
while ((neighbor = rectsearch.NextRectSearch()) != NULL) {
if (neighbor == seg)
continue;
TBOX neighbor_box = neighbor->bounding_box();
// If the neighbor box significantly overlaps with the current
// box (due to the expansion of the current box in the
// previous iteration of this loop), remove the neighbor box
// and expand the current box to include it.
if (neighbor_box.overlap_fraction(box) >= 0.9) {
seg->InsertBox(neighbor_box);
modified = true;
rectsearch.RemoveBBox();
gsearch.RepositionIterator();
delete neighbor;
continue;
}
// Only expand if the neighbor box is of table type
if (neighbor->type() != COL_TABLE)
continue;
// Insert the neighbor box into the current column block
if (neighbor_box.major_x_overlap(box) &&
!box.contains(neighbor_box)) {
seg->InsertBox(neighbor_box);
neighbor_found = true;
modified = true;
rectsearch.RemoveBBox();
gsearch.RepositionIterator();
delete neighbor;
}
}
} while (neighbor_found);
if (modified) {
// Because the box has changed, it has to be removed first.
gsearch.RemoveBBox();
col_seg_grid_.InsertBBox(true, true, seg);
gsearch.RepositionIterator();
}
}
}
// Group horizontally overlapping table partitions into table columns.
// TODO(faisal): This is too aggressive at the moment. The method should
// consider more attributes to group table partitions together. Some common
// errors are:
// 1- page number is merged with a table column above it even
// if there is a large vertical gap between them.
// 2- column headers go on to catch one of the columns arbitrarily
// 3- an isolated noise blob near page top or bottom merges with the table
// column below/above it
// 4- cells from two vertically adjacent tables merge together to make a
// single column resulting in merging of the two tables
void ColumnFinder::GetTableColumns(ColSegment_LIST *table_columns) {
ColSegment_IT it(table_columns);
// Iterate the ColPartitions in the grid.
GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT>
gsearch(&clean_part_grid_);
gsearch.StartFullSearch();
ColPartition* part;
while ((part = gsearch.NextFullSearch()) != NULL) {
if (part->inside_table_column() || part->type() != PT_TABLE)
continue; // prevent a partition to be assigned to multiple columns
TBOX box = part->bounding_box();
ColSegment* col = new ColSegment();
col->InsertBox(box);
part->set_inside_table_column(true);
// Start a search below the current cell to find bottom neighbours
GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT>
vsearch(&clean_part_grid_);
vsearch.StartVerticalSearch(box.left(), box.right(), box.bottom());
ColPartition* neighbor;
bool found_neighbours = false;
while ((neighbor = vsearch.NextVerticalSearch(true)) != NULL) {
// only consider neighbors not assigned to any column yet
if (neighbor->inside_table_column())
continue;
// presence of a non-table neighbor marks the end of current
// table column
if (neighbor->type() != PT_TABLE) {
// Horizontal lines should not break the flow
if (neighbor->IsLineType())
continue;
else
break;
}
TBOX neighbor_box = neighbor->bounding_box();
col->InsertBox(neighbor_box);
neighbor->set_inside_table_column(true);
found_neighbours = true;
}
if (found_neighbours) {
it.add_after_then_move(col);
} else {
part->set_inside_table_column(false);
delete col;
}
}
}
// Mark regions in a column that are x-bounded by the column boundaries and
// y-bounded by the table columns' projection on the y-axis as table regions
void ColumnFinder::GetTableRegions(ColSegment_LIST* table_columns,
ColSegment_LIST* table_regions) {
ColSegment_IT cit(table_columns);
ColSegment_IT rit(table_regions);
// Iterate through column blocks
GridSearch<ColSegment, ColSegment_CLIST, ColSegment_C_IT>
gsearch(&col_seg_grid_);
gsearch.StartFullSearch();
ColSegment* part;
int page_height = tright().y() - bleft().y();
ASSERT_HOST(page_height > 0);
// create a bool array to hold projection on y-axis
bool* table_region = new bool[page_height];
while ((part = gsearch.NextFullSearch()) != NULL) {
TBOX part_box = part->bounding_box();
// reset the projection array
for (int i = 0; i < page_height; i++) {
table_region[i] = false;
}
// iterate through all table columns to find regions in the current
// page column block
cit.move_to_first();
for (cit.mark_cycle_pt(); !cit.cycled_list(); cit.forward()) {
TBOX col_box = cit.data()->bounding_box();
// find intersection region of table column and page column
TBOX intersection_box = col_box.intersection(part_box);
// project table column on the y-axis
for (int i = intersection_box.bottom(); i < intersection_box.top(); i++) {
table_region[i - bleft().y()] = true;
}
}
// set x-limits of table regions to page column width
TBOX current_table_box;
current_table_box.set_left(part_box.left());
current_table_box.set_right(part_box.right());
// go through the y-axis projection to find runs of table
// regions. Each run makes one table region.
for (int i = 1; i < page_height; i++) {
// detect start of a table region
if (!table_region[i - 1] && table_region[i]) {
current_table_box.set_bottom(i + bleft().y());
}
// detect end of a table region
if (table_region[i - 1] && !table_region[i]) {
current_table_box.set_top(i + bleft().y());
if (!current_table_box.null_box()) {
ColSegment* seg = new ColSegment();
seg->InsertBox(current_table_box);
rit.add_after_then_move(seg);
}
}
}
}
delete[] table_region;
}
// Merge table regions corresponding to tables spanning multiple columns if
// there is a colpartition (horizontal ruling line or normal text) that
// touches both regions.
// TODO(faisal): A rare error occurs if there are two horizontally adjacent
// tables with aligned ruling lines. In this case, line finder returns a
// single line and hence the tables get merged together
void ColumnFinder::GridMergeTableRegions() {
// Iterate the table regions in the grid.
GridSearch<ColSegment, ColSegment_CLIST, ColSegment_C_IT>
gsearch(&table_grid_);
gsearch.StartFullSearch();
ColSegment* seg;
while ((seg = gsearch.NextFullSearch()) != NULL) {
bool neighbor_found = false;
bool modified = false; // Modified at least once
do {
// Start a rectangle search x-bounded by the image and y by the table
TBOX box = seg->bounding_box();
TBOX search_region(box);
search_region.set_left(bleft().x());
search_region.set_right(tright().x());
neighbor_found = false;
GridSearch<ColSegment, ColSegment_CLIST, ColSegment_C_IT>
rectsearch(&table_grid_);
rectsearch.StartRectSearch(search_region);
ColSegment* neighbor;
while ((neighbor = rectsearch.NextRectSearch()) != NULL) {
if (neighbor == seg)
continue;
TBOX neighbor_box = neighbor->bounding_box();
// Check if a neighbor box has a large overlap with the table
// region. This may happen as a result of merging two table
// regions in the previous iteration.
if (neighbor_box.overlap_fraction(box) >= 0.9) {
seg->InsertBox(neighbor_box);
rectsearch.RemoveBBox();
gsearch.RepositionIterator();
delete neighbor;
modified = true;
continue;
}
// Check if two table regions belong together based on a common
// horizontal ruling line
if (BelongToOneTable(box, neighbor_box)) {
seg->InsertBox(neighbor_box);
neighbor_found = true;
modified = true;
}
}
} while (neighbor_found);
if (modified) {
// Because the box has changed, it has to be removed first.
gsearch.RemoveBBox();
table_grid_.InsertBBox(true, true, seg);
gsearch.RepositionIterator();
}
}
}
// Decide if two table regions belong to one table based on a common
// horizontal ruling line or another colpartition
bool ColumnFinder::BelongToOneTable(const TBOX &box1, const TBOX &box2) {
// Check for ColPartitions spanning both table regions
TBOX bbox = box1.bounding_union(box2);
// Start a rect search on bbox
GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT>
rectsearch(&clean_part_grid_);
rectsearch.StartRectSearch(bbox);
ColPartition* part;
while ((part = rectsearch.NextRectSearch()) != NULL) {
TBOX part_box = part->bounding_box();
// return true if a colpartition spanning both table regions is found
if (part_box.overlap(box1) && part_box.overlap(box2))
return true;
}
return false;
}
// Adjust table boundaries by:
// - building a tight bounding box around all ColPartitions contained in it.
// - expanding table boundaries to include all colpartitions that overlap the
// table by more than half of their area
// - expanding table boundaries to include nearby horizontal rule lines
// - expanding table vertically to include left out column headers
// TODO(faisal): Expansion of table boundaries is quite aggressive. It usually
// makes following errors:
// 1- horizontal lines consisting of underlines are included in the table if
// they are close enough
// 2- horizontal lines originating from noise tend to get merged with a table
// near the top of the page
// 3- the criteria for including horizontal lines is very generous. Many times
// horizontal lines separating headers and footers get merged with a
// single-column table in a multi-column page thereby including text
// from the neighboring column inside the table
// 4- the criteria for including left out column headers also tends to
// occasionally include text-lines above the tables, typically from
// table caption
void ColumnFinder::AdjustTableBoundaries() {
// Iterate the table regions in the grid
ColSegment_CLIST adjusted_tables;
ColSegment_C_IT it(&adjusted_tables);
GridSearch<ColSegment, ColSegment_CLIST, ColSegment_C_IT>
gsearch(&table_grid_);
gsearch.StartFullSearch();
ColSegment* table;
// search for horizontal ruling lines within the vertical margin
int vertical_margin = kRulingVerticalMargin * gridsize_;
while ((table = gsearch.NextFullSearch()) != NULL) {
TBOX table_box = table->bounding_box();
TBOX search_box = table_box;
int top = MIN(search_box.top() + vertical_margin, tright().y());
int bottom = MAX(search_box.bottom() - vertical_margin, bleft().y());
search_box.set_top(top);
search_box.set_bottom(bottom);
TBOX box;
// Start a rect search on table_box
GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT>
rectsearch(&clean_part_grid_);
rectsearch.StartRectSearch(search_box);
ColPartition* part;
while ((part = rectsearch.NextRectSearch()) != NULL) {
// Do not consider image partitions
if (part->IsImageType())
continue;
TBOX part_box = part->bounding_box();
// Include partition in the table if more than half of it
// is covered by the table
if (part_box.overlap_fraction(table_box) > kMinOverlapWithTable) {
box = box.bounding_union(part_box);
continue;
}
// Include a partially overlapping horizontal line only if the
// extra ColPartitions that will be included due to expansion
// have large side spacing w.r.t. columns containing them.
if (HLineBelongsToTable(part, table_box)) {
box = box.bounding_union(part_box);
}
}
IncludeLeftOutColumnHeaders(box);
// To prevent a table from expanding again, do not insert the
// modified box back to the grid. Instead move it to a list and
// and remove it from the grid. The list is moved later back to the grid.
if (!box.null_box()) {
ColSegment* col = new ColSegment();
col->InsertBox(box);
it.add_after_then_move(col);
}
gsearch.RemoveBBox();
delete table;
}
// clear table grid to move final tables in it
table_grid_.Clear();
it.move_to_first();
// move back final tables to table_grid_
for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
ColSegment* seg = it.extract();
table_grid_.InsertBBox(true, true, seg);
}
}
// Checks whether the horizontal line belong to the table by looking at the
// side spacing of extra ColParitions that will be included in the table
// due to expansion
bool ColumnFinder::HLineBelongsToTable(ColPartition* part,
const TBOX& table_box) {
TBOX part_box = part->bounding_box();
if (!part->IsLineType() || !part_box.major_x_overlap(table_box))
return false;
// Do not consider top-most horizontal line since it usually
// originates from noise
if (!part->nearest_neighbor_above())
return false;
TBOX bbox = part_box.bounding_union(table_box);
// Start a rect search on bbox
GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT>
rectsearch(&clean_part_grid_);
rectsearch.StartRectSearch(bbox);
ColPartition* extra_part;
int num_extra_partitions = 0;
int extra_space_to_right = 0;
int extra_space_to_left = 0;
while ((extra_part = rectsearch.NextRectSearch()) != NULL) {
if (!rectsearch.ReturnedSeedElement())
continue;
TBOX extra_part_box = extra_part->bounding_box();
if (extra_part_box.overlap_fraction(table_box) > 0.6)
continue; // ColPartition already in table
if (extra_part->IsImageType()) // Non-text ColPartitions do not contribute
continue;
num_extra_partitions++;
// presense of a table cell is a strong hint, so just increment the scores
// without looking at the spacing.
if (extra_part->type() == PT_TABLE || extra_part->IsLineType()) {
extra_space_to_right++;
extra_space_to_left++;
continue;
}
int space_threshold = kSideSpaceMargin * part->median_size();
if (extra_part->space_to_right() > space_threshold)
extra_space_to_right++;
if (extra_part->space_to_left() > space_threshold)
extra_space_to_left++;
}
// tprintf("%d %d %d\n",
// num_extra_partitions,extra_space_to_right,extra_space_to_left);
return (extra_space_to_right > num_extra_partitions / 2) ||
(extra_space_to_left > num_extra_partitions / 2);
}
// Look for isolated column headers above the given table box and
// include them in the table
void ColumnFinder::IncludeLeftOutColumnHeaders(TBOX& table_box) {
// Start a search above the current table to look for column headers
GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT>
vsearch(&clean_part_grid_);
vsearch.StartVerticalSearch(table_box.left(), table_box.right(),
table_box.top());
ColPartition* neighbor;
ColPartition* previous_neighbor = NULL;
while ((neighbor = vsearch.NextVerticalSearch(false)) != NULL) {
int table_top = table_box.top();
TBOX box = neighbor->bounding_box();
// Do not continue if the next box is way above
// TODO(faisal): make the threshold some factor of line spacing
if (box.bottom() - table_top > kMaxColumnHeaderDistance)
break;
// Unconditionally include partitions of type TABLE or LINE
// TODO(faisal): add some reasonable conditions here
if (neighbor->type() == PT_TABLE || neighbor->IsLineType()) {
table_box.set_top(box.top());
previous_neighbor = NULL;
continue;
}
// If there are two text partitions, one above the other, without a table
// cell on their left or right side, consider them a barrier and quit
if (previous_neighbor == NULL) {
previous_neighbor = neighbor;
} else {
TBOX previous_box = previous_neighbor->bounding_box();
if (!box.major_y_overlap(previous_box))
break;
}
}
}
// Remove false alarms consiting of a single column based on their
// projection on the x-axis. Projection of a real table on the x-axis
// should have at least one zero-valley larger than the global median
// x-height of the page.
void ColumnFinder::DeleteSingleColumnTables() {
int page_width = tright().x() - bleft().x();
ASSERT_HOST(page_width > 0);
// create an integer array to hold projection on x-axis
int* table_xprojection = new int[page_width];
// Iterate through all tables in the table grid
GridSearch<ColSegment, ColSegment_CLIST, ColSegment_C_IT>
table_search(&table_grid_);
table_search.StartFullSearch();
ColSegment* table;
while ((table = table_search.NextFullSearch()) != NULL) {
TBOX table_box = table->bounding_box();
// reset the projection array
for (int i = 0; i < page_width; i++) {
table_xprojection[i] = 0;
}
// Start a rect search on table_box
GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT>
rectsearch(&clean_part_grid_);
rectsearch.StartRectSearch(table_box);
ColPartition* part;
while ((part = rectsearch.NextRectSearch()) != NULL) {
if (!rectsearch.ReturnedSeedElement())
continue; // Consider each partition only once
if (!part->IsTextType())
continue; // Do not consider non-text partitions
TBOX part_box = part->bounding_box();
// Do not consider partitions partially covered by the table
if (part_box.overlap_fraction(table_box) < kMinOverlapWithTable)
continue;
BLOBNBOX_CLIST* part_boxes = part->boxes();
BLOBNBOX_C_IT pit(part_boxes);
for (pit.mark_cycle_pt(); !pit.cycled_list(); pit.forward()) {
BLOBNBOX *pblob = pit.data();
// ignore blob height for the purpose of projection since we
// are only interested in finding valleys
int xstart = pblob->bounding_box().left();
int xend = pblob->bounding_box().right();
for (int i = xstart; i < xend; i++)
table_xprojection[i - bleft().x()]++;
}
}
// Find largest valley between two reasonable peaks in the table
if (!GapInXProjection(table_xprojection, page_width)) {
table_search.RemoveBBox();
delete table;
}
}
delete[] table_xprojection;
}
// Return true if at least one gap larger than the global x-height
// exists in the horizontal projection
bool ColumnFinder::GapInXProjection(int* xprojection, int length) {
// Find peak value of the histogram
int peak_value = 0;
for (int i = 0; i < length; i++) {
if (xprojection[i] > peak_value) {
peak_value = xprojection[i];
}
}
// Peak value represents the maximum number of horizontally
// overlapping colpartitions, so this can be considered as the
// number of rows in the table
if (peak_value < kMinRowsInTable)
return false;
double projection_threshold = kProjectionThreshold * peak_value;
// Threshold the histogram
for (int i = 0; i < length; i++) {
xprojection[i] = (xprojection[i] > projection_threshold) ? 1 : 0;
}
// Find the largest run of zeros between two ones
int largest_gap = 0;
int run_start = -1;
for (int i = 1; i < length; i++) {
// detect start of a run of zeros
if (xprojection[i - 1] && !xprojection[i]) {
run_start = i;
}
// detect end of a run of zeros and update the value of largest gap
if (run_start != -1 && !xprojection[i - 1] && xprojection[i]) {
int gap = i - run_start;
if (gap > largest_gap)
largest_gap = gap;
run_start = -1;
}
}
return (largest_gap > global_median_xheight_);
}
// Displays the column segments in some window.
void ColumnFinder::DisplayColSegments(ColSegment_LIST *segments,
ScrollView* win,
ScrollView::Color color) {
#ifndef GRAPHICS_DISABLED
win->Pen(color);
win->Brush(ScrollView::NONE);
ColSegment_IT it(segments);
for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
ColSegment *col = it.data();
TBOX box = col->bounding_box();
int left_x = box.left();
int right_x = box.right();
int top_y = box.top();
int bottom_y = box.bottom();
win->Rectangle(left_x, bottom_y, right_x, top_y);
}
win->Update();
#endif
}
// Displays the colpartitions using a new coloring on an existing window.
// Note: This method is only for debug purpose during development and
// would not be part of checked in code
void ColumnFinder::DisplayColPartitions(ScrollView* win,
ScrollView::Color default_color) {
#ifndef GRAPHICS_DISABLED
// Iterate the ColPartitions in the grid.
GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT>
gsearch(&clean_part_grid_);
gsearch.StartFullSearch();
ColPartition* part;
win->Brush(ScrollView::NONE);
ScrollView::Color color;
while ((part = gsearch.NextFullSearch()) != NULL) {
color = default_color;
TBOX box = part->bounding_box();
// ColPartition* upper_part = part->nearest_neighbor_above();
// ColPartition* lower_part = part->nearest_neighbor_below();
// if (!upper_part && !lower_part)
// color = ScrollView::ORANGE;
// else if (upper_part && !lower_part)
// color = ScrollView::CYAN;
// else if (!upper_part && lower_part)
// color = ScrollView::MAGENTA;
if (part->type() == PT_TABLE)
color = ScrollView::YELLOW;
int left_x = box.left();
int right_x = box.right();
int top_y = box.top();
int bottom_y = box.bottom();
win->Pen(color);
win->Rectangle(left_x, bottom_y, right_x, top_y);
}
win->Update();
#endif
}
// Write debug image and text file.
// Note: This method is only for debug purpose during development and
// would not be part of checked in code
void ColumnFinder::WriteToPix() {
#ifdef HAVE_LIBLEPT
// Input file must be named test1.tif
PIX* pix = pixRead("test1.tif");
if (!pix) {
tprintf("Input file test1.tif not found.\n");
return;
}
int img_height = pixGetHeight(pix);
int img_width = pixGetWidth(pix);
// Maximum number of text or table partitions
int num_boxes = 10;
BOXA* text_box_array = boxaCreate(num_boxes);
BOXA* table_box_array = boxaCreate(num_boxes);
GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT>
gsearch(&clean_part_grid_);
gsearch.StartFullSearch();
ColPartition* part;
// load colpartitions into text_box_array and table_box_array
while ((part = gsearch.NextFullSearch()) != NULL) {
TBOX box = part->bounding_box();
box.rotate_large(reskew_);
BOX* lept_box = boxCreate(box.left(), img_height - box.top(),
box.right() - box.left(),
box.top() - box.bottom());
if (part->type() == PT_TABLE)
boxaAddBox(table_box_array, lept_box, L_INSERT);
else
boxaAddBox(text_box_array, lept_box, L_INSERT);
}
// draw colpartitions on the output image
PIX* out = pixDrawBoxa(pix, text_box_array, 3, 0xff000000);
out = pixDrawBoxa(out, table_box_array, 3, 0x0000ff00);
BOXA* table_array = boxaCreate(num_boxes);
// text file containing detected table bounding boxes
FILE* fptr = fopen("tess-table.txt", "w");
GridSearch<ColSegment, ColSegment_CLIST, ColSegment_C_IT>
table_search(&table_grid_);
table_search.StartFullSearch();
ColSegment* table;
// load table boxes to table_array and write them to text file as well
while ((table = table_search.NextFullSearch()) != NULL) {
TBOX box = table->bounding_box();
box.rotate_large(reskew_);
// Since deskewing introduces negative coordinates, reskewing
// might not completely recover from that since both steps enlarge
// the actual box. Hence a box that undergoes deskewing/reskewing
// may go out of image boundaries. Crop a table box if needed to
// contain it inside the image dimensions.
box = box.intersection(TBOX(0, 0, img_width - 1, img_height - 1));
BOX* lept_box = boxCreate(box.left(), img_height - box.top(),
box.right() - box.left(),
box.top() - box.bottom());
boxaAddBox(table_array, lept_box, L_INSERT);
fprintf(fptr, "%d %d %d %d TABLE\n", box.left(),
img_height - box.top(), box.right(), img_height - box.bottom());
}
fclose(fptr);
// paint table boxes on the debug image
out = pixDrawBoxa(out, table_array, 5, 0x7fff0000);
pixWrite("out.png", out, IFF_PNG);
// memory cleanup
boxaDestroy(&text_box_array);
boxaDestroy(&table_box_array);
boxaDestroy(&table_array);
pixDestroy(&pix);
pixDestroy(&out);
#endif
}
// Merge all colpartitions in table regions to make them a single
// colpartition and revert types of isolated table cells not
// assigned to any table to their original types.
void ColumnFinder::MakeTableBlocks() {
// Since we have table blocks already, remove table tags from all
// colpartitions
GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT>
gsearch(&part_grid_);
gsearch.StartFullSearch();
ColPartition* part;
while ((part = gsearch.NextFullSearch()) != NULL) {
if (part->type() == PT_TABLE) {
part->clear_table_type();
}
}
// Now make a single colpartition out of each table block and remove
// all colpartitions contained within a table
GridSearch<ColSegment, ColSegment_CLIST, ColSegment_C_IT>
table_search(&table_grid_);
table_search.StartFullSearch();
ColSegment* table;
while ((table = table_search.NextFullSearch()) != NULL) {
TBOX table_box = table->bounding_box();
// Start a rect search on table_box
GridSearch<ColPartition, ColPartition_CLIST, ColPartition_C_IT>
rectsearch(&part_grid_);
rectsearch.StartRectSearch(table_box);
ColPartition* part;
ColPartition* table_partition = NULL;
while ((part = rectsearch.NextRectSearch()) != NULL) {
// Do not consider image partitions
if (!part->IsTextType())
continue;
TBOX part_box = part->bounding_box();
// Include partition in the table if more than half of it
// is covered by the table
if (part_box.overlap_fraction(table_box) > kMinOverlapWithTable) {
rectsearch.RemoveBBox();
if (table_partition) {
table_partition->Absorb(part, WidthCB());
} else {
table_partition = part;
}
}
}
// Insert table colpartition back to part_grid_
if (table_partition) {
table_partition->SetPartitionType(best_columns_[table_search.GridY()]);
table_partition->set_table_type();
part_grid_.InsertBBox(true, true, table_partition);
}
}
}
// Provides a color for BBGrid to draw the rectangle.
ScrollView::Color ColSegment::BoxColor() const {
const ScrollView::Color kBoxColors[PT_COUNT] = {
ScrollView::YELLOW,
ScrollView::BLUE,
ScrollView::YELLOW,
ScrollView::MAGENTA,
};
return kBoxColors[type_];
}
// Insert a box into this column segment
void ColSegment::InsertBox(const TBOX& other) {
bounding_box_ = bounding_box_.bounding_union(other);
}
// Set column segment type based on the ratio of text and table partitions
// in it.
void ColSegment::set_type() {
if (num_table_cells_ > kTableColumnThreshold * num_text_cells_)
type_ = COL_TABLE;
else if (num_text_cells_ > num_table_cells_)
type_ = COL_TEXT;
else
type_ = COL_MIXED;
}
} // namespace tesseract.