///////////////////////////////////////////////////////////////////////
// File: colpartition.cpp
// Description: Class to hold partitions of the page that correspond
// roughly to text lines.
// Author: Ray Smith
// Created: Thu Aug 14 10:54:01 PDT 2008
//
// (C) Copyright 2008, 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 "colpartition.h"
#include "colpartitionset.h"
#include "workingpartset.h"
namespace tesseract {
ELIST2IZE(ColPartition)
CLISTIZE(ColPartition)
//////////////// ColPartition Implementation ////////////////
// If multiple partners survive the partner depth test beyond this level,
// then arbitrarily pick one.
const int kMaxPartnerDepth = 4;
// Maximum change in spacing (in inches) to ignore.
const double kMaxSpacingDrift = 1.0 / 72; // 1/72 is one point.
// Maximum fraction of line height used as an additional allowance
// for top spacing.
const double kMaxTopSpacingFraction = 0.25;
// Maximum ratio of sizes for lines to be considered the same size.
const double kMaxSizeRatio = 1.5;
// blob_type is the blob_region_type_ of the blobs in this partition.
// Vertical is the direction of logical vertical on the possibly skewed image.
ColPartition::ColPartition(BlobRegionType blob_type, const ICOORD& vertical)
: left_margin_(MIN_INT32), right_margin_(MAX_INT32),
median_bottom_(MAX_INT32), median_top_(MIN_INT32), median_size_(0),
blob_type_(blob_type),
good_width_(false), good_column_(false),
left_key_tab_(false), right_key_tab_(false),
left_key_(0), right_key_(0), type_(PT_UNKNOWN), vertical_(vertical),
working_set_(NULL), block_owned_(false),
first_column_(-1), last_column_(-1), column_set_(NULL),
side_step_(0), top_spacing_(0), bottom_spacing_(0),
type_before_table_(PT_UNKNOWN), inside_table_column_(false),
nearest_neighbor_above_(NULL), nearest_neighbor_below_(NULL),
space_above_(0), space_below_(0), space_to_left_(0), space_to_right_(0) {
}
// Constructs a fake ColPartition with a single fake BLOBNBOX, all made
// from a single TBOX.
// WARNING: Despite being on C_LISTs, the BLOBNBOX owns the C_BLOB and
// the ColPartition owns the BLOBNBOX!!!
// Call DeleteBoxes before deleting the ColPartition.
ColPartition* ColPartition::FakePartition(const TBOX& box) {
ColPartition* part = new ColPartition(BRT_UNKNOWN, ICOORD(0, 1));
part->AddBox(new BLOBNBOX(C_BLOB::FakeBlob(box)));
part->set_left_margin(box.left());
part->set_right_margin(box.right());
part->ComputeLimits();
return part;
}
ColPartition::~ColPartition() {
// Remove this as a partner of all partners, as we don't want them
// referring to a deleted object.
ColPartition_C_IT it(&upper_partners_);
for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
it.data()->RemovePartner(false, this);
}
it.set_to_list(&lower_partners_);
for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
it.data()->RemovePartner(true, this);
}
}
// Constructs a fake ColPartition with no BLOBNBOXes.
// Used for making horizontal line ColPartitions and types it accordingly.
ColPartition::ColPartition(const ICOORD& vertical,
int left, int bottom, int right, int top)
: left_margin_(MIN_INT32), right_margin_(MAX_INT32),
bounding_box_(left, bottom, right, top),
median_bottom_(bottom), median_top_(top), median_size_(top - bottom),
blob_type_(BRT_HLINE),
good_width_(false), good_column_(false),
left_key_tab_(false), right_key_tab_(false),
type_(PT_UNKNOWN), vertical_(vertical),
working_set_(NULL), block_owned_(false),
first_column_(-1), last_column_(-1), column_set_(NULL),
side_step_(0), top_spacing_(0), bottom_spacing_(0),
type_before_table_(PT_UNKNOWN), inside_table_column_(false),
nearest_neighbor_above_(NULL), nearest_neighbor_below_(NULL),
space_above_(0), space_below_(0), space_to_left_(0), space_to_right_(0) {
left_key_ = BoxLeftKey();
right_key_ = BoxRightKey();
}
// Adds the given box to the partition, updating the partition bounds.
// The list of boxes in the partition is updated, ensuring that no box is
// recorded twice, and the boxes are kept in increasing left position.
void ColPartition::AddBox(BLOBNBOX* bbox) {
boxes_.add_sorted(SortByBoxLeft<BLOBNBOX>, true, bbox);
TBOX box = bbox->bounding_box();
// Update the partition limits.
bounding_box_ += box;
if (!left_key_tab_)
left_key_ = BoxLeftKey();
if (!right_key_tab_)
right_key_ = BoxRightKey();
if (TabFind::WithinTestRegion(2, box.left(), box.bottom()))
tprintf("Added box (%d,%d)->(%d,%d) left_blob_x_=%d, right_blob_x_ = %d\n",
box.left(), box.bottom(), box.right(), box.top(),
bounding_box_.left(), bounding_box_.right());
}
// Claims the boxes in the boxes_list by marking them with a this owner
// pointer. If a box is already owned, then run Unique on it.
void ColPartition::ClaimBoxes(WidthCallback* cb) {
bool completed = true;
do {
completed = true;
BLOBNBOX_C_IT bb_it(&boxes_);
for (bb_it.mark_cycle_pt(); !bb_it.cycled_list(); bb_it.forward()) {
BLOBNBOX* bblob = bb_it.data();
ColPartition* other = bblob->owner();
if (other == NULL) {
// Normal case: ownership is available.
bblob->set_owner(this);
} else if (other != this) {
// bblob already has an owner, so resolve the dispute with Unique.
// Null everything owned by this upto, but not including bblob, as
// they will all be up for grabs in Unique.
for (bb_it.move_to_first(); bb_it.data() != bblob; bb_it.forward()) {
ASSERT_HOST(bb_it.data()->owner() == this);
bb_it.data()->set_owner(NULL);
}
// Null the owners of all other's blobs. They should all be
// still owned by other.
BLOBNBOX_C_IT other_it(&other->boxes_);
for (other_it.mark_cycle_pt(); !other_it.cycled_list();
other_it.forward()) {
ASSERT_HOST(other_it.data()->owner() == other);
other_it.data()->set_owner(NULL);
}
Unique(other, cb);
// Now we need to run ClaimBoxes on other, as it may have obtained
// a box from this (beyond bbox) that is owned by a third party.
other->ClaimBoxes(cb);
// Scan our own list for bblob. If bblob is still in it and owned by
// other, there is trouble. Otherwise we can just restart to finish
// the blob list.
bb_it.set_to_list(&boxes_);
for (bb_it.mark_cycle_pt();
!bb_it.cycled_list() && bb_it.data() != bblob;
bb_it.forward());
ASSERT_HOST(bb_it.cycled_list() || bblob->owner() == NULL);
completed = false;
break;
}
}
} while (!completed);
}
// Delete the boxes that this partition owns.
void ColPartition::DeleteBoxes() {
// Although the boxes_ list is a C_LIST, in some cases it owns the
// BLOBNBOXes, as the ColPartition takes ownership from the grid,
// and the BLOBNBOXes own the underlying C_BLOBs.
for (BLOBNBOX_C_IT bb_it(&boxes_); !bb_it.empty(); bb_it.forward()) {
BLOBNBOX* bblob = bb_it.extract();
delete bblob->cblob();
delete bblob;
}
}
// Returns true if this is a legal partition - meaning that the conditions
// left_margin <= bounding_box left
// left_key <= bounding box left key
// bounding box left <= bounding box right
// and likewise for right margin and key
// are all met.
bool ColPartition::IsLegal() {
if (bounding_box_.left() > bounding_box_.right()) {
if (textord_debug_bugs) {
tprintf("Bounding box invalid\n");
Print();
}
return false; // Bounding box invalid.
}
if (left_margin_ > bounding_box_.left() ||
right_margin_ < bounding_box_.right()) {
if (textord_debug_bugs) {
tprintf("Margins invalid\n");
Print();
}
return false; // Margins invalid.
}
if (left_key_ > BoxLeftKey() || right_key_ < BoxRightKey()) {
if (textord_debug_bugs) {
tprintf("Key inside box: %d v %d or %d v %d\n",
left_key_, BoxLeftKey(), right_key_, BoxRightKey());
Print();
}
return false; // Keys inside the box.
}
return true;
}
// Returns true if the left and right edges are approximately equal.
bool ColPartition::MatchingColumns(const ColPartition& other) const {
int y = (MidY() + other.MidY()) / 2;
if (!NearlyEqual(other.LeftAtY(y) / kColumnWidthFactor,
LeftAtY(y) / kColumnWidthFactor, 1))
return false;
if (!NearlyEqual(other.RightAtY(y) / kColumnWidthFactor,
RightAtY(y) / kColumnWidthFactor, 1))
return false;
return true;
}
// Sets the sort key using either the tab vector, or the bounding box if
// the tab vector is NULL. If the tab_vector lies inside the bounding_box,
// use the edge of the box as a key any way.
void ColPartition::SetLeftTab(const TabVector* tab_vector) {
if (tab_vector != NULL) {
left_key_ = tab_vector->sort_key();
left_key_tab_ = left_key_ <= BoxLeftKey();
} else {
left_key_tab_ = false;
}
if (!left_key_tab_)
left_key_ = BoxLeftKey();
}
// As SetLeftTab, but with the right.
void ColPartition::SetRightTab(const TabVector* tab_vector) {
if (tab_vector != NULL) {
right_key_ = tab_vector->sort_key();
right_key_tab_ = right_key_ >= BoxRightKey();
} else {
right_key_tab_ = false;
}
if (!right_key_tab_)
right_key_ = BoxRightKey();
}
// Copies the left/right tab from the src partition, but if take_box is
// true, copies the box instead and uses that as a key.
void ColPartition::CopyLeftTab(const ColPartition& src, bool take_box) {
left_key_tab_ = take_box ? false : src.left_key_tab_;
if (left_key_tab_) {
left_key_ = src.left_key_;
} else {
bounding_box_.set_left(XAtY(src.BoxLeftKey(), MidY()));
left_key_ = BoxLeftKey();
}
if (left_margin_ > bounding_box_.left())
left_margin_ = src.left_margin_;
}
// As CopyLeftTab, but with the right.
void ColPartition::CopyRightTab(const ColPartition& src, bool take_box) {
right_key_tab_ = take_box ? false : src.right_key_tab_;
if (right_key_tab_) {
right_key_ = src.right_key_;
} else {
bounding_box_.set_right(XAtY(src.BoxRightKey(), MidY()));
right_key_ = BoxRightKey();
}
if (right_margin_ < bounding_box_.right())
right_margin_ = src.right_margin_;
}
// Add a partner above if upper, otherwise below.
// Add them uniquely and keep the list sorted by box left.
// Partnerships are added symmetrically to partner and this.
void ColPartition::AddPartner(bool upper, ColPartition* partner) {
if (upper) {
partner->lower_partners_.add_sorted(SortByBoxLeft<ColPartition>,
true, this);
upper_partners_.add_sorted(SortByBoxLeft<ColPartition>, true, partner);
} else {
partner->upper_partners_.add_sorted(SortByBoxLeft<ColPartition>,
true, this);
lower_partners_.add_sorted(SortByBoxLeft<ColPartition>, true, partner);
}
}
// Removes the partner from this, but does not remove this from partner.
// This asymmetric removal is so as not to mess up the iterator that is
// working on partner's partner list.
void ColPartition::RemovePartner(bool upper, ColPartition* partner) {
ColPartition_C_IT it(upper ? &upper_partners_ : &lower_partners_);
for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
if (it.data() == partner) {
it.extract();
break;
}
}
}
// Returns the partner if the given partner is a singleton, otherwise NULL.
ColPartition* ColPartition::SingletonPartner(bool upper) {
ColPartition_CLIST* partners = upper ? &upper_partners_ : &lower_partners_;
if (!partners->singleton())
return NULL;
ColPartition_C_IT it(partners);
return it.data();
}
// Merge with the other partition and delete it.
void ColPartition::Absorb(ColPartition* other, WidthCallback* cb) {
if (TabFind::WithinTestRegion(2, bounding_box_.left(),
bounding_box_.bottom()) ||
TabFind::WithinTestRegion(2, other->bounding_box_.left(),
other->bounding_box_.bottom())) {
tprintf("Merging:");
Print();
other->Print();
}
// Merge the two sorted lists.
BLOBNBOX_C_IT it(&boxes_);
BLOBNBOX_C_IT it2(&other->boxes_);
for (; !it2.empty(); it2.forward()) {
BLOBNBOX* bbox2 = it2.extract();
ColPartition* prev_owner = bbox2->owner();
ASSERT_HOST(prev_owner == other || prev_owner == NULL);
if (prev_owner == other)
bbox2->set_owner(this);
bbox2->set_region_type(blob_type_);
TBOX box2 = bbox2->bounding_box();
int left2 = box2.left();
while (!it.at_last() && it.data()->bounding_box().left() <= left2) {
if (it.data() == bbox2)
break;
it.forward();
}
if (!it.empty() && it.data() == bbox2)
continue;
if (it.empty() || (it.at_last() &&
it.data()->bounding_box().left() <= left2)) {
it.add_after_then_move(bbox2);
} else {
it.add_before_then_move(bbox2);
}
}
left_margin_ = MIN(left_margin_, other->left_margin_);
right_margin_ = MAX(right_margin_, other->right_margin_);
if (other->left_key_ < left_key_) {
left_key_ = other->left_key_;
left_key_tab_ = other->left_key_tab_;
}
if (other->right_key_ > right_key_) {
right_key_ = other->right_key_;
right_key_tab_ = other->right_key_tab_;
}
delete other;
ComputeLimits();
if (cb != NULL) {
SetColumnGoodness(cb);
}
}
// Shares out any common boxes amongst the partitions, ensuring that no
// box stays in both. Returns true if anything was done.
bool ColPartition::Unique(ColPartition* other, WidthCallback* cb) {
bool debug = TabFind::WithinTestRegion(2, bounding_box_.left(),
bounding_box_.bottom()) ||
TabFind::WithinTestRegion(2, other->bounding_box_.left(),
other->bounding_box_.bottom());
if (debug) {
tprintf("Running Unique:");
Print();
other->Print();
}
BLOBNBOX_C_IT it(&boxes_);
BLOBNBOX_C_IT it2(&other->boxes_);
it.mark_cycle_pt();
it2.mark_cycle_pt();
bool any_moved = false;
while (!it.cycled_list() && !it2.cycled_list()) {
BLOBNBOX* bbox = it.data();
BLOBNBOX* bbox2 = it2.data();
TBOX box = bbox->bounding_box();
TBOX box2 = bbox2->bounding_box();
if (box.left() < box2.left()) {
it.forward();
} else if (box.left() > box2.left()) {
it2.forward();
} else if (bbox == bbox2) {
// Separate out most frequent case for efficiency.
if (debug) {
tprintf("Keeping box (%d,%d)->(%d,%d) only in %s\n",
box.left(), box.bottom(), box.right(), box.top(),
ThisPartitionBetter(bbox, *other) ? "This" : "Other");
}
if (ThisPartitionBetter(bbox, *other))
it2.extract();
else
it.extract();
it.forward();
it2.forward();
any_moved = true;
} else {
// Lefts are equal, but boxes may be in any order.
BLOBNBOX_C_IT search_it(it2);
for (search_it.forward(); !search_it.at_first() &&
search_it.data() != bbox &&
search_it.data()->bounding_box().left() == box.left();
search_it.forward());
if (search_it.data() == bbox) {
// Found a match.
if (ThisPartitionBetter(bbox, *other)) {
search_it.extract();
// We just (potentially) invalidated it2, so reposition at bbox2.
it2.move_to_first();
for (it2.mark_cycle_pt(); it2.data() != bbox2; it2.forward());
} else {
it.extract();
}
it.forward();
any_moved = true;
} else {
// No match to bbox in list2. Just move first it forward.
it.forward();
}
}
}
// Now check to see if there are any in either list that would be better
// off in the other.
if (!it.empty()) {
it.move_to_first();
for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
BLOBNBOX* bbox = it.data();
if (!ThisPartitionBetter(bbox, *other)) {
other->AddBox(it.extract());
TBOX box = bbox->bounding_box();
if (debug) {
tprintf("Moved box (%d,%d)->(%d,%d) from this to other:\n",
box.left(), box.bottom(), box.right(), box.top());
}
any_moved = true;
}
}
}
if (!it2.empty()) {
it2.move_to_first();
for (it2.mark_cycle_pt(); !it2.cycled_list(); it2.forward()) {
BLOBNBOX* bbox2 = it2.data();
if (ThisPartitionBetter(bbox2, *other)) {
AddBox(it2.extract());
TBOX box = bbox2->bounding_box();
if (debug) {
tprintf("Moved box (%d,%d)->(%d,%d) from other to this:\n",
box.left(), box.bottom(), box.right(), box.top());
}
any_moved = true;
}
}
}
if (any_moved) {
if (debug)
tprintf("Unique did something!\n");
ComputeLimits();
other->ComputeLimits();
if (cb != NULL) {
SetColumnGoodness(cb);
other->SetColumnGoodness(cb);
}
}
return any_moved;
}
// Split this partition at the given x coordinate, returning the right
// half and keeping the left half in this.
ColPartition* ColPartition::SplitAt(int split_x) {
if (split_x <= bounding_box_.left() || split_x >= bounding_box_.right())
return NULL; // There will be no change.
ColPartition* split_part = ShallowCopy();
BLOBNBOX_C_IT it(&boxes_);
for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
BLOBNBOX* bbox = it.data();
ColPartition* prev_owner = bbox->owner();
ASSERT_HOST(prev_owner == this || prev_owner == NULL);
const TBOX& box = bbox->bounding_box();
if (box.left() >= split_x) {
split_part->AddBox(it.extract());
if (prev_owner != NULL)
bbox->set_owner(split_part);
}
}
ASSERT_HOST(!it.empty());
if (split_part->IsEmpty()) {
// Split part ended up with nothing. Possible if split_x passes
// through the last blob.
delete split_part;
return NULL;
}
right_key_tab_ = false;
split_part->left_key_tab_ = false;
right_margin_ = split_x;
split_part->left_margin_ = split_x;
ComputeLimits();
split_part->ComputeLimits();
return split_part;
}
// Recalculates all the coordinate limits of the partition.
void ColPartition::ComputeLimits() {
bounding_box_ = TBOX(); // Clear it
BLOBNBOX_C_IT it(&boxes_);
BLOBNBOX* bbox = NULL;
if (it.empty()) {
bounding_box_.set_left(left_margin_);
bounding_box_.set_right(right_margin_);
bounding_box_.set_bottom(0);
bounding_box_.set_top(0);
} else {
for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
bbox = it.data();
bounding_box_ += bbox->bounding_box();
}
}
if (!left_key_tab_)
left_key_ = BoxLeftKey();
if (left_key_ > BoxLeftKey() && textord_debug_bugs) {
// TODO(rays) investigate the causes of these error messages, to find
// out if they are genuinely harmful, or just indicative of junk input.
tprintf("Computed left-illegal partition\n");
Print();
}
if (!right_key_tab_)
right_key_ = BoxRightKey();
if (right_key_ < BoxRightKey() && textord_debug_bugs) {
tprintf("Computed right-illegal partition\n");
Print();
}
if (it.empty())
return;
STATS top_stats(bounding_box_.bottom(), bounding_box_.top() + 1);
STATS bottom_stats(bounding_box_.bottom(), bounding_box_.top() + 1);
STATS size_stats(0, bounding_box_.height() + 1);
for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
bbox = it.data();
TBOX box = bbox->bounding_box();
top_stats.add(box.top(), 1);
bottom_stats.add(box.bottom(), 1);
size_stats.add(box.height(), 1);
}
median_top_ = static_cast<int>(top_stats.median() + 0.5);
median_bottom_ = static_cast<int>(bottom_stats.median() + 0.5);
median_size_ = static_cast<int>(size_stats.median() + 0.5);
if (right_margin_ < bounding_box_.right() && textord_debug_bugs) {
tprintf("Made partition with bad right coords");
Print();
}
if (left_margin_ > bounding_box_.left() && textord_debug_bugs) {
tprintf("Made partition with bad left coords");
Print();
}
if (TabFind::WithinTestRegion(2, bounding_box_.left(),
bounding_box_.bottom())) {
tprintf("Recomputed box for partition %p\n", this);
Print();
}
}
// Computes and sets the type_ and first_colum_, last_column_ and column_set_.
void ColPartition::SetPartitionType(ColPartitionSet* columns) {
int first_spanned_col = -1;
int last_spanned_col = -1;
type_ = columns->SpanningType(blob_type_,
bounding_box_.left(), bounding_box_.right(),
MidY(), left_margin_, right_margin_,
&first_column_, &last_column_,
&first_spanned_col, &last_spanned_col);
column_set_ = columns;
if (first_column_ != last_column_ &&
(type_ == PT_PULLOUT_TEXT || type_ == PT_PULLOUT_IMAGE ||
type_ == PT_PULLOUT_LINE)) {
// Unequal columns may indicate that the pullout spans one of the columns
// it lies in, so force it to be allocated to just that column.
if (first_spanned_col >= 0) {
first_column_ = first_spanned_col;
last_column_ = first_spanned_col;
} else {
if ((first_column_ & 1) == 0)
last_column_ = first_column_;
else if ((last_column_ & 1) == 0)
first_column_ = last_column_;
else
first_column_ = last_column_ = (first_column_ + last_column_) / 2;
}
}
}
// Returns the first and last column touched by this partition.
void ColPartition::ColumnRange(ColPartitionSet* columns,
int* first_col, int* last_col) {
int first_spanned_col = -1;
int last_spanned_col = -1;
type_ = columns->SpanningType(blob_type_,
bounding_box_.left(), bounding_box_.right(),
MidY(), left_margin_, right_margin_,
first_col, last_col,
&first_spanned_col, &last_spanned_col);
}
// Sets the internal flags good_width_ and good_column_.
void ColPartition::SetColumnGoodness(WidthCallback* cb) {
int y = MidY();
int width = RightAtY(y) - LeftAtY(y);
good_width_ = cb->Run(width);
good_column_ = blob_type_ == BRT_TEXT && left_key_tab_ && right_key_tab_;
}
// Adds this ColPartition to a matching WorkingPartSet if one can be found,
// otherwise starts a new one in the appropriate column, ending the previous.
void ColPartition::AddToWorkingSet(const ICOORD& bleft, const ICOORD& tright,
int resolution,
ColPartition_LIST* used_parts,
WorkingPartSet_LIST* working_sets) {
if (block_owned_)
return; // Done it already.
block_owned_ = true;
WorkingPartSet_IT it(working_sets);
// If there is an upper partner use its working_set_ directly.
ColPartition* partner = SingletonPartner(true);
if (partner != NULL && partner->working_set_ != NULL) {
working_set_ = partner->working_set_;
working_set_->AddPartition(this);
return;
}
if (partner != NULL && textord_debug_bugs) {
tprintf("Partition with partner has no working set!:");
Print();
partner->Print();
}
// Search for the column that the left edge fits in.
WorkingPartSet* work_set = NULL;
it.move_to_first();
int col_index = 0;
for (it.mark_cycle_pt(); !it.cycled_list() &&
col_index != first_column_;
it.forward(), ++col_index);
if (textord_debug_tabfind >= 2) {
tprintf("Match is %s for:", (col_index & 1) ? "Real" : "Between");
Print();
}
if (it.cycled_list() && textord_debug_bugs) {
tprintf("Target column=%d, only had %d\n", first_column_, col_index);
}
ASSERT_HOST(!it.cycled_list());
work_set = it.data();
// If last_column_ != first_column, then we need to scoop up all blocks
// between here and the last_column_ and put back in work_set.
if (!it.cycled_list() && last_column_ != first_column_) {
// Find the column that the right edge falls in.
BLOCK_LIST completed_blocks;
TO_BLOCK_LIST to_blocks;
for (; !it.cycled_list() && col_index <= last_column_;
it.forward(), ++col_index) {
WorkingPartSet* end_set = it.data();
end_set->ExtractCompletedBlocks(bleft, tright, resolution, used_parts,
&completed_blocks, &to_blocks);
}
work_set->InsertCompletedBlocks(&completed_blocks, &to_blocks);
}
working_set_ = work_set;
work_set->AddPartition(this);
}
// From the given block_parts list, builds one or more BLOCKs and
// corresponding TO_BLOCKs, such that the line spacing is uniform in each.
// Created blocks are appended to the end of completed_blocks and to_blocks.
// The used partitions are put onto used_parts, as they may still be referred
// to in the partition grid. bleft, tright and resolution are the bounds
// and resolution of the original image.
void ColPartition::LineSpacingBlocks(const ICOORD& bleft, const ICOORD& tright,
int resolution,
ColPartition_LIST* block_parts,
ColPartition_LIST* used_parts,
BLOCK_LIST* completed_blocks,
TO_BLOCK_LIST* to_blocks) {
int page_height = tright.y() - bleft.y();
// Compute the initial spacing stats.
ColPartition_IT it(block_parts);
int part_count = 0;
for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
ColPartition* part = it.data();
ASSERT_HOST(!part->boxes()->empty());
STATS side_steps(0, part->bounding_box().height());
BLOBNBOX_C_IT blob_it(part->boxes());
int prev_bottom = blob_it.data()->bounding_box().bottom();
for (blob_it.forward(); !blob_it.at_first(); blob_it.forward()) {
BLOBNBOX* blob = blob_it.data();
int bottom = blob->bounding_box().bottom();
int step = bottom - prev_bottom;
if (step < 0)
step = -step;
side_steps.add(step, 1);
prev_bottom = bottom;
}
part->set_side_step(static_cast<int>(side_steps.median() + 0.5));
if (!it.at_last()) {
ColPartition* next_part = it.data_relative(1);
part->set_bottom_spacing(part->median_bottom() -
next_part->median_bottom());
part->set_top_spacing(part->median_top() - next_part->median_top());
} else {
part->set_bottom_spacing(page_height);
part->set_top_spacing(page_height);
}
if (textord_debug_tabfind) {
part->Print();
tprintf("side step = %.2f, top spacing = %d, bottom spacing=%d\n",
side_steps.median(), part->top_spacing(), part->bottom_spacing());
}
++part_count;
}
if (part_count == 0)
return;
SmoothSpacings(resolution, page_height, block_parts);
// Move the partitions into individual block lists and make the blocks.
BLOCK_IT block_it(completed_blocks);
TO_BLOCK_IT to_block_it(to_blocks);
ColPartition_LIST spacing_parts;
ColPartition_IT sp_block_it(&spacing_parts);
for (it.mark_cycle_pt(); !it.empty();) {
ColPartition* part = it.extract();
sp_block_it.add_to_end(part);
it.forward();
if (it.empty() || !part->SpacingsEqual(*it.data(), resolution)) {
// There is a spacing boundary. Check to see if it.data() belongs
// better in the current block or the next one.
if (!it.empty()) {
ColPartition* next_part = it.data();
// If there is a size match one-way, then the middle line goes with
// its matched size, otherwise it goes with the smallest spacing.
ColPartition* third_part = it.at_last() ? NULL : it.data_relative(1);
if (textord_debug_tabfind)
tprintf("Spacings unequal: upper:%d/%d, lower:%d/%d,"
" sizes %d %d %d\n",
part->top_spacing(), part->bottom_spacing(),
next_part->top_spacing(), next_part->bottom_spacing(),
part->median_size(), next_part->median_size(),
third_part != NULL ? third_part->median_size() : 0);
// If spacing_diff ends up positive, then next_part goes in the
// current block.
int spacing_diff = next_part->bottom_spacing() - part->bottom_spacing();
if (part->SizesSimilar(*next_part) &&
(third_part == NULL || !next_part->SizesSimilar(*third_part))) {
// Sizes overrule.
spacing_diff = 1;
} else if (!part->SizesSimilar(*next_part) && third_part != NULL &&
next_part->SizesSimilar(*third_part)) {
// Sizes overrule.
spacing_diff = -1;
}
if (spacing_diff > 0) {
sp_block_it.add_to_end(it.extract());
it.forward();
}
}
TO_BLOCK* to_block = MakeBlock(bleft, tright, &spacing_parts, used_parts);
if (to_block != NULL) {
to_block_it.add_to_end(to_block);
block_it.add_to_end(to_block->block);
}
sp_block_it.set_to_list(&spacing_parts);
}
}
}
// Helper function to clip the input pos to the given bleft, tright bounds.
static void ClipCoord(const ICOORD& bleft, const ICOORD& tright, ICOORD* pos) {
if (pos->x() < bleft.x())
pos->set_x(bleft.x());
if (pos->x() > tright.x())
pos->set_x(tright.x());
if (pos->y() < bleft.y())
pos->set_y(bleft.y());
if (pos->y() > tright.y())
pos->set_y(tright.y());
}
// Constructs a block from the given list of partitions.
// Arguments are as LineSpacingBlocks above.
TO_BLOCK* ColPartition::MakeBlock(const ICOORD& bleft, const ICOORD& tright,
ColPartition_LIST* block_parts,
ColPartition_LIST* used_parts) {
if (block_parts->empty())
return NULL; // Nothing to do.
ColPartition_IT it(block_parts);
ColPartition* part = it.data();
int line_spacing = part->bottom_spacing();
if (line_spacing < part->median_size())
line_spacing = part->bounding_box().height();
PolyBlockType type = it.data()->type();
bool text_type = it.data()->IsTextType();
ICOORDELT_LIST vertices;
ICOORDELT_IT vert_it(&vertices);
ICOORD start, end;
int min_x = MAX_INT32;
int max_x = MIN_INT32;
int min_y = MAX_INT32;
int max_y = MIN_INT32;
int iteration = 0;
do {
if (iteration == 0)
ColPartition::LeftEdgeRun(&it, &start, &end);
else
ColPartition::RightEdgeRun(&it, &start, &end);
ClipCoord(bleft, tright, &start);
ClipCoord(bleft, tright, &end);
vert_it.add_after_then_move(new ICOORDELT(start));
vert_it.add_after_then_move(new ICOORDELT(end));
min_x = MIN(min_x, start.x());
min_x = MIN(min_x, end.x());
max_x = MAX(max_x, start.x());
max_x = MAX(max_x, end.x());
min_y = MIN(min_y, start.y());
min_y = MIN(min_y, end.y());
max_y = MAX(max_y, start.y());
max_y = MAX(max_y, end.y());
if ((iteration == 0 && it.at_first()) ||
(iteration == 1 && it.at_last())) {
++iteration;
it.move_to_last();
}
} while (iteration < 2);
if (textord_debug_tabfind)
tprintf("Making block at (%d,%d)->(%d,%d)\n",
min_x, min_y, max_x, max_y);
BLOCK* block = new BLOCK("", true, 0, 0, min_x, min_y, max_x, max_y);
block->set_poly_block(new POLY_BLOCK(&vertices, type));
// Make a matching TO_BLOCK and put all the BLOBNBOXes from the parts in it.
// Move all the parts to a done list as they are no longer needed, except
// that have have to continue to exist until the part grid is deleted.
// Compute the median blob size as we go, as the block needs to know.
STATS heights(0, max_y + 1 - min_y);
TO_BLOCK* to_block = new TO_BLOCK(block);
BLOBNBOX_IT blob_it(&to_block->blobs);
ColPartition_IT used_it(used_parts);
for (it.move_to_first(); !it.empty(); it.forward()) {
ColPartition* part = it.extract();
if (text_type) {
// Only transfer blobs from text regions to the output blocks.
// The rest stay behind and get deleted with the ColPartitions.
for (BLOBNBOX_C_IT bb_it(part->boxes()); !bb_it.empty();
bb_it.forward()) {
BLOBNBOX* bblob = bb_it.extract();
ASSERT_HOST(bblob->owner() == part);
ASSERT_HOST(bblob->region_type() >= BRT_UNKNOWN);
C_OUTLINE_IT ol_it(bblob->cblob()->out_list());
ASSERT_HOST(ol_it.data()->pathlength() > 0);
heights.add(bblob->bounding_box().height(), 1);
blob_it.add_after_then_move(bblob);
}
}
used_it.add_to_end(part);
}
if (text_type && blob_it.empty()) {
delete block;
delete to_block;
return NULL;
}
to_block->line_size = heights.median();
int block_height = block->bounding_box().height();
if (block_height < line_spacing)
line_spacing = block_height;
to_block->line_spacing = line_spacing;
to_block->max_blob_size = block_height + 1;
if (type == PT_VERTICAL_TEXT) {
// This block will get rotated 90 deg clockwise so record the inverse.
FCOORD rotation(0.0f, 1.0f);
block->set_re_rotation(rotation);
}
return to_block;
}
// Returns a copy of everything except the list of boxes. The resulting
// ColPartition is only suitable for keeping in a column candidate list.
ColPartition* ColPartition::ShallowCopy() const {
ColPartition* part = new ColPartition(blob_type_, vertical_);
part->left_margin_ = left_margin_;
part->right_margin_ = right_margin_;
part->bounding_box_ = bounding_box_;
part->median_bottom_ = median_bottom_;
part->median_top_ = median_top_;
part->median_size_ = median_size_;
part->good_width_ = good_width_;
part->good_column_ = good_column_;
part->left_key_tab_ = left_key_tab_;
part->right_key_tab_ = right_key_tab_;
part->type_ = type_;
part->left_key_ = left_key_;
part->right_key_ = right_key_;
return part;
}
// Provides a color for BBGrid to draw the rectangle.
// Must be kept in sync with PolyBlockType.
ScrollView::Color ColPartition::BoxColor() const {
return POLY_BLOCK::ColorForPolyBlockType(type_);
}
// Keep in sync with BlobRegionType.
static char kBlobTypes[BRT_COUNT + 1] = "NHRIUVT";
// Prints debug information on this.
void ColPartition::Print() {
int y = MidY();
tprintf("ColPart:%c(M%d-%c%d-B%d,%d/%d)->(%dB-%d%c-%dM,%d/%d)"
" w-ok=%d, v-ok=%d, type=%d%c, fc=%d, lc=%d, boxes=%d"
" ts=%d bs=%d ls=%d rs=%d\n",
boxes_.empty() ? 'E' : ' ',
left_margin_, left_key_tab_ ? 'T' : 'B', LeftAtY(y),
bounding_box_.left(), median_bottom_, bounding_box_.bottom(),
bounding_box_.right(), RightAtY(y), right_key_tab_ ? 'T' : 'B',
right_margin_, median_top_, bounding_box_.top(),
good_width_, good_column_, type_,
kBlobTypes[blob_type_],
first_column_, last_column_, boxes_.length(),
space_above_, space_below_, space_to_left_, space_to_right_);
}
// Sets the types of all partitions in the run to be the max of the types.
void ColPartition::SmoothPartnerRun(int working_set_count) {
STATS left_stats(0, working_set_count);
STATS right_stats(0, working_set_count);
PolyBlockType max_type = type_;
ColPartition* partner;
for (partner = SingletonPartner(false); partner != NULL;
partner = partner->SingletonPartner(false)) {
if (partner->type_ > max_type)
max_type = partner->type_;
if (column_set_ == partner->column_set_) {
left_stats.add(partner->first_column_, 1);
right_stats.add(partner->last_column_, 1);
}
}
type_ = max_type;
first_column_ = left_stats.mode();
last_column_ = right_stats.mode();
if (last_column_ < first_column_)
last_column_ = first_column_;
for (partner = SingletonPartner(false); partner != NULL;
partner = partner->SingletonPartner(false)) {
partner->type_ = max_type;
if (column_set_ == partner->column_set_) {
partner->first_column_ = first_column_;
partner->last_column_ = last_column_;
}
}
}
// Cleans up the partners of the given type so that there is at most
// one partner. This makes block creation simpler.
void ColPartition::RefinePartners(PolyBlockType type) {
if (type_ == type) {
RefinePartnersInternal(true);
RefinePartnersInternal(false);
} else if (type == PT_COUNT) {
// This is the final pass. Make sure only the correctly typed
// partners surivive, however many there are.
RefinePartnersByType(true, &upper_partners_);
RefinePartnersByType(false, &lower_partners_);
}
}
////////////////// PRIVATE CODE /////////////////////////////
// Cleans up the partners above if upper is true, else below.
void ColPartition::RefinePartnersInternal(bool upper) {
ColPartition_CLIST* partners = upper ? &upper_partners_ : &lower_partners_;
if (!partners->empty() && !partners->singleton()) {
RefinePartnersByType(upper, partners);
if (!partners->empty() && !partners->singleton()) {
// Check for transitive partnerships and break the cycle.
RefinePartnerShortcuts(upper, partners);
if (!partners->empty() && !partners->singleton()) {
// Types didn't fix it. Flowing text keeps the one with the longest
// sequence of singleton matching partners. All others max overlap.
if (type_ == PT_FLOWING_TEXT)
RefineFlowingTextPartners(upper, partners);
else
RefinePartnersByOverlap(upper, partners);
}
}
}
}
// Restricts the partners to only desirable types. For text and BRT_HLINE this
// means the same type_ , and for image types it means any image type.
void ColPartition::RefinePartnersByType(bool upper,
ColPartition_CLIST* partners) {
if (TabFind::WithinTestRegion(2, bounding_box_.left(),
bounding_box_.bottom())) {
tprintf("Refining %s partners by type for:\n", upper ? "Upper" : "Lower");
Print();
}
ColPartition_C_IT it(partners);
// Purify text by type.
if (blob_type_ > BRT_UNKNOWN || blob_type_ == BRT_HLINE) {
// Keep only partners matching type_.
// Exception: PT_VERTICAL_TEXT is allowed to stay with the other
// text types if it is the only partner.
for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
ColPartition* partner = it.data();
if (partner->type_ != type_ &&
(!partners->singleton() ||
(type_ != PT_VERTICAL_TEXT && partner->type_ != PT_VERTICAL_TEXT) ||
!IsTextType() || !partner->IsTextType())) {
partner->RemovePartner(!upper, this);
it.extract();
} else if (TabFind::WithinTestRegion(2, bounding_box_.left(),
bounding_box_.bottom())) {
tprintf("Keeping partner:");
partner->Print();
}
}
} else {
// Keep only images with images, but not being fussy about type.
for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
ColPartition* partner = it.data();
if (partner->blob_type_ > BRT_UNKNOWN ||
partner->blob_type_ == BRT_HLINE) {
partner->RemovePartner(!upper, this);
it.extract();
} else if (TabFind::WithinTestRegion(2, bounding_box_.left(),
bounding_box_.bottom())) {
tprintf("Keeping partner:");
partner->Print();
}
}
}
}
// Remove transitive partnerships: this<->a, and a<->b and this<->b.
// Gets rid of this<->b, leaving a clean chain.
// Also if we have this<->a and a<->this, then gets rid of this<->a, as
// this has multiple partners.
void ColPartition::RefinePartnerShortcuts(bool upper,
ColPartition_CLIST* partners) {
bool done_any = false;
do {
done_any = false;
ColPartition_C_IT it(partners);
for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
ColPartition* a = it.data();
// Check for a match between all of a's partners (it1/b1) and all
// of this's partners (it2/b2).
ColPartition_C_IT it1(upper ? &a->upper_partners_ : &a->lower_partners_);
for (it1.mark_cycle_pt(); !it1.cycled_list(); it1.forward()) {
ColPartition* b1 = it1.data();
if (b1 == this) {
done_any = true;
it.extract();
a->RemovePartner(!upper, this);
break;
}
ColPartition_C_IT it2(partners);
for (it2.mark_cycle_pt(); !it2.cycled_list(); it2.forward()) {
ColPartition* b2 = it2.data();
if (b1 == b2) {
// Jackpot! b2 should not be a partner of this.
it2.extract();
b2->RemovePartner(!upper, this);
done_any = true;
// That potentially invalidated all the iterators, so break out
// and start again.
break;
}
}
if (done_any)
break;
}
if (done_any)
break;
}
} while (done_any && !partners->empty() && !partners->singleton());
}
// Keeps the partner with the longest sequence of singleton matching partners.
// Converts all others to pullout.
void ColPartition::RefineFlowingTextPartners(bool upper,
ColPartition_CLIST* partners) {
ColPartition_C_IT it(partners);
ColPartition* best_partner = it.data();
// Nasty iterative algorithm.
int depth = 1;
int survivors = 0;
do {
survivors = 0;
for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
ColPartition* partner = it.data();
// See if it survives a chase to depth levels.
for (int i = 0; i < depth && partner != NULL; ++i) {
partner = partner->SingletonPartner(upper);
if (partner != NULL && partner->type_ != PT_FLOWING_TEXT)
partner = NULL;
}
if (partner != NULL) {
++survivors;
best_partner = it.data();
}
}
++depth;
} while (survivors > 1 && depth <= kMaxPartnerDepth);
// Keep only the best partner.
for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
ColPartition* partner = it.data();
if (partner != best_partner) {
partner->RemovePartner(!upper, this);
it.extract();
// Change the types of partner to be PT_PULLOUT_TEXT.
while (partner != NULL && partner->type_ == PT_FLOWING_TEXT) {
partner->type_ = PT_PULLOUT_TEXT;
partner = partner->SingletonPartner(upper);
}
}
}
}
// Keep the partner with the biggest overlap.
void ColPartition::RefinePartnersByOverlap(bool upper,
ColPartition_CLIST* partners) {
ColPartition_C_IT it(partners);
ColPartition* best_partner = it.data();
// Find the partner with the best overlap.
int best_overlap = 0;
for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
ColPartition* partner = it.data();
int overlap = MIN(bounding_box_.right(), partner->bounding_box_.right())
- MAX(bounding_box_.left(), partner->bounding_box_.left());
if (overlap > best_overlap) {
best_overlap = overlap;
best_partner = partner;
}
}
// Keep only the best partner.
for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
ColPartition* partner = it.data();
if (partner != best_partner) {
partner->RemovePartner(!upper, this);
it.extract();
}
}
}
// Return true if bbox belongs better in this than other.
bool ColPartition::ThisPartitionBetter(BLOBNBOX* bbox,
const ColPartition& other) {
TBOX box = bbox->bounding_box();
// Margins take priority.
int left = box.left();
int right = box.right();
if (left < left_margin_ || right > right_margin_)
return false;
if (left < other.left_margin_ || right > other.right_margin_)
return true;
int top = box.top();
int bottom = box.bottom();
int this_overlap = MIN(top, median_top_) - MAX(bottom, median_bottom_);
int other_overlap = MIN(top, other.median_top_) -
MAX(bottom, other.median_bottom_);
int this_miss = median_top_ - median_bottom_ - this_overlap;
int other_miss = other.median_top_ - other.median_bottom_ - other_overlap;
if (TabFind::WithinTestRegion(3, box.left(), box.bottom())) {
tprintf("Unique on (%d,%d)->(%d,%d) overlap %d/%d, miss %d/%d, mt=%d/%d\n",
box.left(), box.bottom(), box.right(), box.top(),
this_overlap, other_overlap, this_miss, other_miss,
median_top_, other.median_top_);
}
if (this_miss < other_miss)
return true;
if (this_miss > other_miss)
return false;
if (this_overlap > other_overlap)
return true;
if (this_overlap < other_overlap)
return false;
return median_top_ >= other.median_top_;
}
// Returns the median line-spacing between the current position and the end
// of the list.
// The iterator is passed by value so the iteration does not modify the
// caller's iterator.
static int MedianSpacing(int page_height, ColPartition_IT it) {
STATS stats(0, page_height);
while (!it.cycled_list()) {
ColPartition* part = it.data();
it.forward();
stats.add(part->bottom_spacing(), 1);
stats.add(part->top_spacing(), 1);
}
return static_cast<int>(stats.median() + 0.5);
}
// Smoothes the spacings in the list into groups of equal linespacing.
// resolution is the resolution of the original image, used as a basis
// for thresholds in change of spacing. page_height is in pixels.
void ColPartition::SmoothSpacings(int resolution, int page_height,
ColPartition_LIST* parts) {
// The task would be trivial if we didn't have to allow for blips -
// occasional offsets in spacing caused by anomolous text, such as all
// caps, groups of descenders, joined words, Arabic etc.
// The neighbourhood stores a consecutive group of partitions so that
// blips can be detected correctly, yet conservatively enough to not
// mistake genuine spacing changes for blips. See example below.
ColPartition* neighbourhood[PN_COUNT];
ColPartition_IT it(parts);
it.mark_cycle_pt();
// Although we know nothing about the spacings is this list, the median is
// used as an approximation to allow blips.
// If parts of this block aren't spaced to the median, then we can't
// accept blips in those parts, but we'll recalculate it each time we
// split the block, so the median becomes more likely to match all the text.
int median_space = MedianSpacing(page_height, it);
ColPartition_IT start_it(it);
ColPartition_IT end_it(it);
for (int i = 0; i < PN_COUNT; ++i) {
if (i < PN_UPPER || it.cycled_list()) {
neighbourhood[i] = NULL;
} else {
if (i == PN_LOWER)
end_it = it;
neighbourhood[i] = it.data();
it.forward();
}
}
while (neighbourhood[PN_UPPER] != NULL) {
// Test for end of a group. Normally SpacingsEqual is true within a group,
// but in the case of a blip, it will be false. Here is an example:
// Line enum Spacing below (spacing between tops of lines)
// 1 ABOVE2 20
// 2 ABOVE1 20
// 3 UPPER 15
// 4 LOWER 25
// 5 BELOW1 20
// 6 BELOW2 20
// Line 4 is all in caps (regular caps), so the spacing between line 3
// and line 4 (looking at the tops) is smaller than normal, and the
// spacing between line 4 and line 5 is larger than normal, but the
// two of them add to twice the normal spacing.
// The following if has to accept unequal spacings 3 times to pass the
// blip (20/15, 15/25 and 25/20)
// When the blip is in the middle, OKSpacingBlip tests that one of
// ABOVE1 and BELOW1 matches the median.
// The first time, everything is shifted down 1, so we present
// OKSpacingBlip with neighbourhood+1 and check that PN_UPPER is median.
// The last time, everything is shifted up 1, so we present OKSpacingBlip
// with neighbourhood-1 and check that PN_LOWER matches the median.
if (neighbourhood[PN_LOWER] == NULL ||
(!neighbourhood[PN_UPPER]->SpacingsEqual(*neighbourhood[PN_LOWER],
resolution) &&
!OKSpacingBlip(resolution, median_space, neighbourhood) &&
(!OKSpacingBlip(resolution, median_space, neighbourhood - 1) ||
!neighbourhood[PN_LOWER]->SpacingEqual(median_space, resolution)) &&
(!OKSpacingBlip(resolution, median_space, neighbourhood + 1) ||
!neighbourhood[PN_UPPER]->SpacingEqual(median_space, resolution)))) {
// The group has ended. PN_UPPER is the last member.
// Compute the mean spacing over the group.
ColPartition_IT sum_it(start_it);
ColPartition* last_part = neighbourhood[PN_UPPER];
double total_bottom = 0.0;
double total_top = 0.0;
int total_count = 0;
ColPartition* upper = sum_it.data();
// We do not process last_part, as its spacing is different.
while (upper != last_part) {
total_bottom += upper->bottom_spacing();
total_top += upper->top_spacing();
++total_count;
sum_it.forward();
upper = sum_it.data();
}
if (total_count > 0) {
// There were at least 2 lines, so set them all to the mean.
int top_spacing = static_cast<int>(total_top / total_count + 0.5);
int bottom_spacing = static_cast<int>(total_bottom / total_count + 0.5);
if (textord_debug_tabfind) {
tprintf("Spacing run ended. Cause:");
if (neighbourhood[PN_LOWER] == NULL) {
tprintf("No more lines\n");
} else {
tprintf("Spacing change. Spacings:\n");
for (int i = 0; i < PN_COUNT; ++i) {
if (neighbourhood[i] == NULL) {
tprintf("NULL\n");
} else {
tprintf("Top = %d, bottom = %d\n",
neighbourhood[i]->top_spacing(),
neighbourhood[i]->bottom_spacing());
}
}
}
tprintf("Mean spacing = %d/%d\n", top_spacing, bottom_spacing);
}
sum_it = start_it;
upper = sum_it.data();
while (upper != last_part) {
upper->set_top_spacing(top_spacing);
upper->set_bottom_spacing(bottom_spacing);
if (textord_debug_tabfind) {
tprintf("Setting mean on:");
upper->Print();
}
sum_it.forward();
upper = sum_it.data();
}
}
// PN_LOWER starts the next group and end_it is the next start_it.
start_it = end_it;
// Recalculate the median spacing to maximize the chances of detecting
// spacing blips.
median_space = MedianSpacing(page_height, end_it);
}
// Shuffle pointers.
for (int j = 1; j < PN_COUNT; ++j) {
neighbourhood[j - 1] = neighbourhood[j];
}
if (it.cycled_list()) {
neighbourhood[PN_COUNT - 1] = NULL;
} else {
neighbourhood[PN_COUNT - 1] = it.data();
it.forward();
}
end_it.forward();
}
}
// Returns true if the parts array of pointers to partitions matches the
// condition for a spacing blip. See SmoothSpacings for what this means
// and how it is used.
bool ColPartition::OKSpacingBlip(int resolution, int median_spacing,
ColPartition** parts) {
if (parts[PN_UPPER] == NULL || parts[PN_LOWER] == NULL)
return false;
// The blip is OK if upper and lower sum to an OK value and at least
// one of above1 and below1 is equal to the median.
return parts[PN_UPPER]->SummedSpacingOK(*parts[PN_LOWER],
median_spacing, resolution) &&
((parts[PN_ABOVE1] != NULL &&
parts[PN_ABOVE1]->SpacingEqual(median_spacing, resolution)) ||
(parts[PN_BELOW1] != NULL &&
parts[PN_BELOW1]->SpacingEqual(median_spacing, resolution)));
}
// Returns true if both the top and bottom spacings of this match the given
// spacing to within suitable margins dictated by the image resolution.
bool ColPartition::SpacingEqual(int spacing, int resolution) const {
int bottom_error = BottomSpacingMargin(resolution);
int top_error = TopSpacingMargin(resolution);
return NearlyEqual(bottom_spacing_, spacing, bottom_error) &&
NearlyEqual(top_spacing_, spacing, top_error);
}
// Returns true if both the top and bottom spacings of this and other
// match to within suitable margins dictated by the image resolution.
bool ColPartition::SpacingsEqual(const ColPartition& other,
int resolution) const {
int bottom_error = MAX(BottomSpacingMargin(resolution),
other.BottomSpacingMargin(resolution));
int top_error = MAX(TopSpacingMargin(resolution),
other.TopSpacingMargin(resolution));
return NearlyEqual(bottom_spacing_, other.bottom_spacing_, bottom_error) &&
(NearlyEqual(top_spacing_, other.top_spacing_, top_error) ||
NearlyEqual(top_spacing_ + other.top_spacing_, bottom_spacing_ * 2,
bottom_error));
}
// Returns true if the sum spacing of this and other match the given
// spacing (or twice the given spacing) to within a suitable margin dictated
// by the image resolution.
bool ColPartition::SummedSpacingOK(const ColPartition& other,
int spacing, int resolution) const {
int bottom_error = MAX(BottomSpacingMargin(resolution),
other.BottomSpacingMargin(resolution));
int top_error = MAX(TopSpacingMargin(resolution),
other.TopSpacingMargin(resolution));
int bottom_total = bottom_spacing_ + other.bottom_spacing_;
int top_total = top_spacing_ + other.top_spacing_;
return (NearlyEqual(spacing, bottom_total, bottom_error) &&
NearlyEqual(spacing, top_total, top_error)) ||
(NearlyEqual(spacing * 2, bottom_total, bottom_error) &&
NearlyEqual(spacing * 2, top_total, top_error));
}
// Returns a suitable spacing margin that can be applied to bottoms of
// text lines, based on the resolution and the stored side_step_.
int ColPartition::BottomSpacingMargin(int resolution) const {
return static_cast<int>(kMaxSpacingDrift * resolution + 0.5) + side_step_;
}
// Returns a suitable spacing margin that can be applied to tops of
// text lines, based on the resolution and the stored side_step_.
int ColPartition::TopSpacingMargin(int resolution) const {
return static_cast<int>(kMaxTopSpacingFraction * median_size_ + 0.5) +
BottomSpacingMargin(resolution);
}
// Returns true if the median text sizes of this and other agree to within
// a reasonable multiplicative factor.
bool ColPartition::SizesSimilar(const ColPartition& other) const {
return median_size_ <= other.median_size_ * kMaxSizeRatio &&
other.median_size_ <= median_size_ * kMaxSizeRatio;
}
// Computes and returns in start, end a line segment formed from a
// forwards-iterated group of left edges of partitions that satisfy the
// condition that the rightmost left margin is to the left of the
// leftmost left bounding box edge.
// TODO(rays) Not good enough. Needs improving to tightly wrap text in both
// directions, and to loosely wrap images.
void ColPartition::LeftEdgeRun(ColPartition_IT* part_it,
ICOORD* start, ICOORD* end) {
ColPartition* part = part_it->data();
int start_y = part->bounding_box_.top();
if (!part_it->at_first() &&
part_it->data_relative(-1)->bounding_box_.bottom() > start_y)
start_y = (start_y + part_it->data_relative(-1)->bounding_box_.bottom())/2;
int end_y = part->bounding_box_.bottom();
int min_right = MAX_INT32;
int max_left = MIN_INT32;
do {
part = part_it->data();
int top = part->bounding_box_.top();
int bottom = part->bounding_box_.bottom();
int tl_key = part->SortKey(part->left_margin_, top);
int tr_key = part->SortKey(part->bounding_box_.left(), top);
int bl_key = part->SortKey(part->left_margin_, bottom);
int br_key = part->SortKey(part->bounding_box_.left(), bottom);
int left_key = MAX(tl_key, bl_key);
int right_key = MIN(tr_key, br_key);
if (left_key <= min_right && right_key >= max_left) {
// This part is good - let's keep it.
min_right = MIN(min_right, right_key);
max_left = MAX(max_left, left_key);
end_y = bottom;
part_it->forward();
if (!part_it->at_first() && part_it->data()->bounding_box_.top() < end_y)
end_y = (end_y + part_it->data()->bounding_box_.top()) / 2;
} else {
if (textord_debug_tabfind)
tprintf("Sum key %d/%d, new %d/%d\n",
max_left, min_right, left_key, right_key);
break;
}
} while (!part_it->at_first());
start->set_y(start_y);
start->set_x(part->XAtY(min_right, start_y));
end->set_y(end_y);
end->set_x(part->XAtY(min_right, end_y));
if (textord_debug_tabfind && !part_it->at_first())
tprintf("Left run from y=%d to %d terminated with sum %d-%d, new %d-%d\n",
start_y, end_y, part->XAtY(max_left, end_y),
end->x(), part->left_margin_, part->bounding_box_.left());
}
// Computes and returns in start, end a line segment formed from a
// backwards-iterated group of right edges of partitions that satisfy the
// condition that the leftmost right margin is to the right of the
// rightmost right bounding box edge.
// TODO(rays) Not good enough. Needs improving to tightly wrap text in both
// directions, and to loosely wrap images.
void ColPartition::RightEdgeRun(ColPartition_IT* part_it,
ICOORD* start, ICOORD* end) {
ColPartition* part = part_it->data();
int start_y = part->bounding_box_.bottom();
if (!part_it->at_first() &&
part_it->data_relative(1)->bounding_box_.top() < start_y)
start_y = (start_y + part_it->data_relative(1)->bounding_box_.top()) / 2;
int end_y = part->bounding_box_.top();
int min_right = MAX_INT32;
int max_left = MIN_INT32;
do {
part = part_it->data();
int top = part->bounding_box_.top();
int bottom = part->bounding_box_.bottom();
int tl_key = part->SortKey(part->bounding_box_.right(), top);
int tr_key = part->SortKey(part->right_margin_, top);
int bl_key = part->SortKey(part->bounding_box_.right(), bottom);
int br_key = part->SortKey(part->right_margin_, bottom);
int left_key = MAX(tl_key, bl_key);
int right_key = MIN(tr_key, br_key);
if (left_key <= min_right && right_key >= max_left) {
// This part is good - let's keep it.
min_right = MIN(min_right, right_key);
max_left = MAX(max_left, left_key);
end_y = top;
part_it->backward();
if (!part_it->at_last() &&
part_it->data()->bounding_box_.bottom() > end_y)
end_y = (end_y + part_it->data()->bounding_box_.bottom()) / 2;
} else {
if (textord_debug_tabfind)
tprintf("Sum cross %d/%d, new %d/%d\n",
max_left, min_right, left_key, right_key);
break;
}
} while (!part_it->at_last());
start->set_y(start_y);
start->set_x(part->XAtY(max_left, start_y));
end->set_y(end_y);
end->set_x(part->XAtY(max_left, end_y));
if (textord_debug_tabfind && !part_it->at_last())
tprintf("Right run from y=%d to %d terminated with sum %d-%d, new %d-%d\n",
start_y, end_y, end->x(), part->XAtY(min_right, end_y),
part->bounding_box_.right(), part->right_margin_);
}
} // namespace tesseract.