Tesseract 3.02

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
colpartition.cpp
Go to the documentation of this file.
1
2 // File: colpartition.cpp
3 // Description: Class to hold partitions of the page that correspond
4 // roughly to text lines.
5 // Author: Ray Smith
6 // Created: Thu Aug 14 10:54:01 PDT 2008
7 //
8 // (C) Copyright 2008, Google Inc.
9 // Licensed under the Apache License, Version 2.0 (the "License");
10 // you may not use this file except in compliance with the License.
11 // You may obtain a copy of the License at
12 // http://www.apache.org/licenses/LICENSE-2.0
13 // Unless required by applicable law or agreed to in writing, software
14 // distributed under the License is distributed on an "AS IS" BASIS,
15 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 // See the License for the specific language governing permissions and
17 // limitations under the License.
18 //
20
21 #include "colpartition.h"
22 #include "colpartitiongrid.h"
23 #include "colpartitionset.h"
24 #include "detlinefit.h"
25 #include "dppoint.h"
26 #include "imagefind.h"
27 #include "workingpartset.h"
28
29 #ifdef _MSC_VER
30 #pragma warning(disable:4244) // Conversion warnings
31 #endif
32
33 namespace tesseract {
34
35 ELIST2IZE(ColPartition)
36 CLISTIZE(ColPartition)
37
39
40 // If multiple partners survive the partner depth test beyond this level,
41 // then arbitrarily pick one.
42 const int kMaxPartnerDepth = 4;
43 // Maximum change in spacing (in inches) to ignore.
44 const double kMaxSpacingDrift = 1.0 / 72; // 1/72 is one point.
45 // Maximum fraction of line height used as an additional allowance
46 // for top spacing.
47 const double kMaxTopSpacingFraction = 0.25;
48 // What multiple of the largest line height should be used as an upper bound
49 // for whether lines are in the same text block?
50 const double kMaxSameBlockLineSpacing = 3;
51 // Maximum ratio of sizes for lines to be considered the same size.
52 const double kMaxSizeRatio = 1.5;
53 // Fraction of max of leader width and gap for max IQR of gaps.
54 const double kMaxLeaderGapFractionOfMax = 0.25;
55 // Fraction of min of leader width and gap for max IQR of gaps.
56 const double kMaxLeaderGapFractionOfMin = 0.5;
57 // Minimum number of blobs to be considered a leader.
58 const int kMinLeaderCount = 5;
59 // Cost of a cut through a leader.
60 const int kLeaderCutCost = 8;
61 // Minimum score for a STRONG_CHAIN textline.
62 const int kMinStrongTextValue = 6;
63 // Minimum score for a CHAIN textline.
64 const int kMinChainTextValue = 3;
65 // Minimum number of blobs for strong horizontal text lines.
66 const int kHorzStrongTextlineCount = 8;
67 // Minimum height (in image pixels) for strong horizontal text lines.
68 const int kHorzStrongTextlineHeight = 10;
69 // Minimum aspect ratio for strong horizontal text lines.
70 const int kHorzStrongTextlineAspect = 5;
71 // Maximum upper quartile error allowed on a baseline fit as a fraction
72 // of height.
73 const double kMaxBaselineError = 0.4375;
74 // Min coverage for a good baseline between vectors
75 const double kMinBaselineCoverage = 0.5;
76 // Max RMS color noise to compare colors.
77 const int kMaxRMSColorNoise = 128;
78 // Maximum distance to allow a partition color to be to use that partition
79 // in smoothing neighbouring types. This is a squared distance.
80 const int kMaxColorDistance = 900;
81
82 // blob_type is the blob_region_type_ of the blobs in this partition.
83 // Vertical is the direction of logical vertical on the possibly skewed image.
84 ColPartition::ColPartition(BlobRegionType blob_type, const ICOORD& vertical)
85 : left_margin_(-MAX_INT32), right_margin_(MAX_INT32),
86 median_bottom_(MAX_INT32), median_top_(-MAX_INT32), median_size_(0),
87 median_left_(MAX_INT32), median_right_(-MAX_INT32), median_width_(0),
88 blob_type_(blob_type), flow_(BTFT_NONE), good_blob_score_(0),
89 good_width_(false), good_column_(false),
90 left_key_tab_(false), right_key_tab_(false),
91 left_key_(0), right_key_(0), type_(PT_UNKNOWN), vertical_(vertical),
92 working_set_(NULL), last_add_was_vertical_(false), block_owned_(false),
93 desperately_merged_(false),
94 first_column_(-1), last_column_(-1), column_set_(NULL),
95 side_step_(0), top_spacing_(0), bottom_spacing_(0),
96 type_before_table_(PT_UNKNOWN), inside_table_column_(false),
97 nearest_neighbor_above_(NULL), nearest_neighbor_below_(NULL),
98 space_above_(0), space_below_(0), space_to_left_(0), space_to_right_(0),
99 owns_blobs_(true) {
100 memset(special_blobs_densities_, 0, sizeof(special_blobs_densities_));
101 }
102
103 // Constructs a fake ColPartition with a single fake BLOBNBOX, all made
104 // from a single TBOX.
105 // WARNING: Despite being on C_LISTs, the BLOBNBOX owns the C_BLOB and
106 // the ColPartition owns the BLOBNBOX!!!
107 // Call DeleteBoxes before deleting the ColPartition.
108 ColPartition* ColPartition::FakePartition(const TBOX& box,
109 PolyBlockType block_type,
110 BlobRegionType blob_type,
111 BlobTextFlowType flow) {
112 ColPartition* part = new ColPartition(blob_type, ICOORD(0, 1));
113 part->set_type(block_type);
114 part->set_flow(flow);
115 part->AddBox(new BLOBNBOX(C_BLOB::FakeBlob(box)));
116 part->set_left_margin(box.left());
117 part->set_right_margin(box.right());
118 part->SetBlobTypes();
119 part->ComputeLimits();
120 part->ClaimBoxes();
121 return part;
122 }
123
124 // Constructs and returns a ColPartition with the given real BLOBNBOX,
125 // and sets it up to be a "big" partition (single-blob partition bigger
126 // than the surrounding text that may be a dropcap, two or more vertically
127 // touching characters, or some graphic element.
128 // If the given list is not NULL, the partition is also added to the list.
129 ColPartition* ColPartition::MakeBigPartition(BLOBNBOX* box,
130 ColPartition_LIST* big_part_list) {
131 box->set_owner(NULL);
132 ColPartition* single = new ColPartition(BRT_UNKNOWN, ICOORD(0, 1));
133 single->set_flow(BTFT_NONE);
134 single->AddBox(box);
135 single->ComputeLimits();
136 single->ClaimBoxes();
137 single->SetBlobTypes();
138 single->set_block_owned(true);
139 if (big_part_list != NULL) {
140 ColPartition_IT part_it(big_part_list);
141 part_it.add_to_end(single);
142 }
143 return single;
144 }
145
146 ColPartition::~ColPartition() {
147 // Remove this as a partner of all partners, as we don't want them
148 // referring to a deleted object.
149 ColPartition_C_IT it(&upper_partners_);
150 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
151 it.data()->RemovePartner(false, this);
152 }
153 it.set_to_list(&lower_partners_);
154 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
155 it.data()->RemovePartner(true, this);
156 }
157 }
158
159 // Constructs a fake ColPartition with no BLOBNBOXes to represent a
160 // horizontal or vertical line, given a type and a bounding box.
161 ColPartition* ColPartition::MakeLinePartition(BlobRegionType blob_type,
162 const ICOORD& vertical,
163 int left, int bottom,
164 int right, int top) {
165 ColPartition* part = new ColPartition(blob_type, vertical);
166 part->bounding_box_ = TBOX(left, bottom, right, top);
167 part->median_bottom_ = bottom;
168 part->median_top_ = top;
169 part->median_size_ = top - bottom;
170 part->median_width_ = right - left;
171 part->left_key_ = part->BoxLeftKey();
172 part->right_key_ = part->BoxRightKey();
173 return part;
174 }
175
176
177 // Adds the given box to the partition, updating the partition bounds.
178 // The list of boxes in the partition is updated, ensuring that no box is
179 // recorded twice, and the boxes are kept in increasing left position.
180 void ColPartition::AddBox(BLOBNBOX* bbox) {
181 TBOX box = bbox->bounding_box();
182 // Update the partition limits.
183 if (boxes_.length() == 0) {
184 bounding_box_ = box;
185 } else {
186 bounding_box_ += box;
187 }
188
189 if (IsVerticalType()) {
190 if (!last_add_was_vertical_) {
191 boxes_.sort(SortByBoxBottom<BLOBNBOX>);
192 last_add_was_vertical_ = true;
193 }
194 boxes_.add_sorted(SortByBoxBottom<BLOBNBOX>, true, bbox);
195 } else {
196 if (last_add_was_vertical_) {
197 boxes_.sort(SortByBoxLeft<BLOBNBOX>);
198 last_add_was_vertical_ = false;
199 }
200 boxes_.add_sorted(SortByBoxLeft<BLOBNBOX>, true, bbox);
201 }
202 if (!left_key_tab_)
203 left_key_ = BoxLeftKey();
204 if (!right_key_tab_)
205 right_key_ = BoxRightKey();
206 if (TabFind::WithinTestRegion(2, box.left(), box.bottom()))
207 tprintf("Added box (%d,%d)->(%d,%d) left_blob_x_=%d, right_blob_x_ = %d\n",
208 box.left(), box.bottom(), box.right(), box.top(),
209 bounding_box_.left(), bounding_box_.right());
210 }
211
212 // Removes the given box from the partition, updating the bounds.
213 void ColPartition::RemoveBox(BLOBNBOX* box) {
214 BLOBNBOX_C_IT bb_it(&boxes_);
215 for (bb_it.mark_cycle_pt(); !bb_it.cycled_list(); bb_it.forward()) {
216 if (box == bb_it.data()) {
217 bb_it.extract();
218 ComputeLimits();
219 return;
220 }
221 }
222 }
223
224 // Returns the tallest box in the partition, as measured perpendicular to the
225 // presumed flow of text.
226 BLOBNBOX* ColPartition::BiggestBox() {
227 BLOBNBOX* biggest = NULL;
228 BLOBNBOX_C_IT bb_it(&boxes_);
229 for (bb_it.mark_cycle_pt(); !bb_it.cycled_list(); bb_it.forward()) {
230 BLOBNBOX* bbox = bb_it.data();
231 if (IsVerticalType()) {
232 if (biggest == NULL ||
233 bbox->bounding_box().width() > biggest->bounding_box().width())
234 biggest = bbox;
235 } else {
236 if (biggest == NULL ||
237 bbox->bounding_box().height() > biggest->bounding_box().height())
238 biggest = bbox;
239 }
240 }
241 return biggest;
242 }
243
244 // Returns the bounding box excluding the given box.
245 TBOX ColPartition::BoundsWithoutBox(BLOBNBOX* box) {
246 TBOX result;
247 BLOBNBOX_C_IT bb_it(&boxes_);
248 for (bb_it.mark_cycle_pt(); !bb_it.cycled_list(); bb_it.forward()) {
249 if (box != bb_it.data()) {
250 result += bb_it.data()->bounding_box();
251 }
252 }
253 return result;
254 }
255
256 // Claims the boxes in the boxes_list by marking them with a this owner
257 // pointer. If a box is already owned, then it must be owned by this.
258 void ColPartition::ClaimBoxes() {
259 BLOBNBOX_C_IT bb_it(&boxes_);
260 for (bb_it.mark_cycle_pt(); !bb_it.cycled_list(); bb_it.forward()) {
261 BLOBNBOX* bblob = bb_it.data();
262 ColPartition* other = bblob->owner();
263 if (other == NULL) {
264 // Normal case: ownership is available.
265 bblob->set_owner(this);
266 } else {
267 ASSERT_HOST(other == this);
268 }
269 }
270 }
271
272 // NULL the owner of the blobs in this partition, so they can be deleted
273 // independently of the ColPartition.
274 void ColPartition::DisownBoxes() {
275 BLOBNBOX_C_IT bb_it(&boxes_);
276 for (bb_it.mark_cycle_pt(); !bb_it.cycled_list(); bb_it.forward()) {
277 BLOBNBOX* bblob = bb_it.data();
278 ASSERT_HOST(bblob->owner() == this || bblob->owner() == NULL);
279 bblob->set_owner(NULL);
280 }
281 }
282
283 // Delete the boxes that this partition owns.
284 void ColPartition::DeleteBoxes() {
285 // Although the boxes_ list is a C_LIST, in some cases it owns the
286 // BLOBNBOXes, as the ColPartition takes ownership from the grid,
287 // and the BLOBNBOXes own the underlying C_BLOBs.
288 for (BLOBNBOX_C_IT bb_it(&boxes_); !bb_it.empty(); bb_it.forward()) {
289 BLOBNBOX* bblob = bb_it.extract();
290 delete bblob->cblob();
291 delete bblob;
292 }
293 }
294
295 // Reflects the partition in the y-axis, assuming that its blobs have
296 // already been done. Corrects only a limited part of the members, since
297 // this function is assumed to be used shortly after initial creation, which
298 // is before a lot of the members are used.
299 void ColPartition::ReflectInYAxis() {
300 ColPartition_CLIST reversed_boxes;
301 ColPartition_C_IT reversed_it(&reversed_boxes);
302 // Reverse the order of the boxes_.
303 BLOBNBOX_C_IT bb_it(&boxes_);
304 for (bb_it.mark_cycle_pt(); !bb_it.cycled_list(); bb_it.forward()) {
305 reversed_it.add_before_then_move(bb_it.extract());
306 }
307 bb_it.add_list_after(&reversed_boxes);
308 ASSERT_HOST(!left_key_tab_ && !right_key_tab_);
309 int tmp = left_margin_;
310 left_margin_ = -right_margin_;
311 right_margin_ = -tmp;
312 ComputeLimits();
313 }
314
315 // Returns true if this is a legal partition - meaning that the conditions
316 // left_margin <= bounding_box left
317 // left_key <= bounding box left key
318 // bounding box left <= bounding box right
319 // and likewise for right margin and key
320 // are all met.
321 bool ColPartition::IsLegal() {
322 if (bounding_box_.left() > bounding_box_.right()) {
323 if (textord_debug_bugs) {
324 tprintf("Bounding box invalid\n");
325 Print();
326 }
327 return false; // Bounding box invalid.
328 }
329 if (left_margin_ > bounding_box_.left() ||
330 right_margin_ < bounding_box_.right()) {
331 if (textord_debug_bugs) {
332 tprintf("Margins invalid\n");
333 Print();
334 }
335 return false; // Margins invalid.
336 }
337 if (left_key_ > BoxLeftKey() || right_key_ < BoxRightKey()) {
338 if (textord_debug_bugs) {
339 tprintf("Key inside box: %d v %d or %d v %d\n",
340 left_key_, BoxLeftKey(), right_key_, BoxRightKey());
341 Print();
342 }
343 return false; // Keys inside the box.
344 }
345 return true;
346 }
347
348 // Returns true if the left and right edges are approximately equal.
349 bool ColPartition::MatchingColumns(const ColPartition& other) const {
350 int y = (MidY() + other.MidY()) / 2;
351 if (!NearlyEqual(other.LeftAtY(y) / kColumnWidthFactor,
352 LeftAtY(y) / kColumnWidthFactor, 1))
353 return false;
354 if (!NearlyEqual(other.RightAtY(y) / kColumnWidthFactor,
355 RightAtY(y) / kColumnWidthFactor, 1))
356 return false;
357 return true;
358 }
359
360 // Returns true if the colors match for two text partitions.
361 bool ColPartition::MatchingTextColor(const ColPartition& other) const {
362 if (color1_[L_ALPHA_CHANNEL] > kMaxRMSColorNoise &&
363 other.color1_[L_ALPHA_CHANNEL] > kMaxRMSColorNoise)
364 return false; // Too noisy.
365
366 // Colors must match for other to count.
367 double d_this1_o = ImageFind::ColorDistanceFromLine(other.color1_,
368 other.color2_,
369 color1_);
370 double d_this2_o = ImageFind::ColorDistanceFromLine(other.color1_,
371 other.color2_,
372 color2_);
373 double d_o1_this = ImageFind::ColorDistanceFromLine(color1_, color2_,
374 other.color1_);
375 double d_o2_this = ImageFind::ColorDistanceFromLine(color1_, color2_,
376 other.color2_);
377 // All 4 distances must be small enough.
378 return d_this1_o < kMaxColorDistance && d_this2_o < kMaxColorDistance &&
379 d_o1_this < kMaxColorDistance && d_o2_this < kMaxColorDistance;
380 }
381
382 // Returns true if the sizes match for two text partitions,
383 // taking orientation into account. See also SizesSimilar.
384 bool ColPartition::MatchingSizes(const ColPartition& other) const {
385 if (blob_type_ == BRT_VERT_TEXT || other.blob_type_ == BRT_VERT_TEXT)
386 return !TabFind::DifferentSizes(median_width_, other.median_width_);
387 else
388 return !TabFind::DifferentSizes(median_size_, other.median_size_);
389 }
390
391 // Returns true if there is no tabstop violation in merging this and other.
392 bool ColPartition::ConfirmNoTabViolation(const ColPartition& other) const {
393 if (bounding_box_.right() < other.bounding_box_.left() &&
394 bounding_box_.right() < other.LeftBlobRule())
395 return false;
396 if (other.bounding_box_.right() < bounding_box_.left() &&
397 other.bounding_box_.right() < LeftBlobRule())
398 return false;
399 if (bounding_box_.left() > other.bounding_box_.right() &&
400 bounding_box_.left() > other.RightBlobRule())
401 return false;
402 if (other.bounding_box_.left() > bounding_box_.right() &&
403 other.bounding_box_.left() > RightBlobRule())
404 return false;
405 return true;
406 }
407
408 // Returns true if other has a similar stroke width to this.
409 bool ColPartition::MatchingStrokeWidth(const ColPartition& other,
410 double fractional_tolerance,
411 double constant_tolerance) const {
412 int match_count = 0;
413 int nonmatch_count = 0;
414 BLOBNBOX_C_IT box_it(const_cast<BLOBNBOX_CLIST*>(&boxes_));
415 BLOBNBOX_C_IT other_it(const_cast<BLOBNBOX_CLIST*>(&other.boxes_));
416 box_it.mark_cycle_pt();
417 other_it.mark_cycle_pt();
418 while (!box_it.cycled_list() && !other_it.cycled_list()) {
419 if (box_it.data()->MatchingStrokeWidth(*other_it.data(),
420 fractional_tolerance,
421 constant_tolerance))
422 ++match_count;
423 else
424 ++nonmatch_count;
425 box_it.forward();
426 other_it.forward();
427 }
428 return match_count > nonmatch_count;
429 }
430
431 // Returns true if base is an acceptable diacritic base char merge
432 // with this as the diacritic.
433 // Returns true if:
434 // (1) this is a ColPartition containing only diacritics, and
435 // (2) the base characters indicated on the diacritics all believably lie
436 // within the text line of the candidate ColPartition.
437 bool ColPartition::OKDiacriticMerge(const ColPartition& candidate,
438 bool debug) const {
439 BLOBNBOX_C_IT it(const_cast<BLOBNBOX_CLIST*>(&boxes_));
440 int min_top = MAX_INT32;
441 int max_bottom = -MAX_INT32;
442 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
443 BLOBNBOX* blob = it.data();
444 if (!blob->IsDiacritic()) {
445 if (debug) {
446 tprintf("Blob is not a diacritic:");
447 blob->bounding_box().print();
448 }
449 return false; // All blobs must have diacritic bases.
450 }
451 if (blob->base_char_top() < min_top)
452 min_top = blob->base_char_top();
453 if (blob->base_char_bottom() > max_bottom)
454 max_bottom = blob->base_char_bottom();
455 }
456 // If the intersection of all vertical ranges of all base characters
457 // overlaps the median range of this, then it is OK.
458 bool result = min_top > candidate.median_bottom_ &&
459 max_bottom < candidate.median_top_;
460 if (debug) {
461 if (result)
462 tprintf("OKDiacritic!\n");
463 else
464 tprintf("y ranges don\'t overlap: %d-%d / %d-%d\n",
465 max_bottom, min_top, median_bottom_, median_top_);
466 }
467 return result;
468 }
469
470 // Sets the sort key using either the tab vector, or the bounding box if
471 // the tab vector is NULL. If the tab_vector lies inside the bounding_box,
472 // use the edge of the box as a key any way.
473 void ColPartition::SetLeftTab(const TabVector* tab_vector) {
474 if (tab_vector != NULL) {
475 left_key_ = tab_vector->sort_key();
476 left_key_tab_ = left_key_ <= BoxLeftKey();
477 } else {
478 left_key_tab_ = false;
479 }
480 if (!left_key_tab_)
481 left_key_ = BoxLeftKey();
482 }
483
484 // As SetLeftTab, but with the right.
485 void ColPartition::SetRightTab(const TabVector* tab_vector) {
486 if (tab_vector != NULL) {
487 right_key_ = tab_vector->sort_key();
488 right_key_tab_ = right_key_ >= BoxRightKey();
489 } else {
490 right_key_tab_ = false;
491 }
492 if (!right_key_tab_)
493 right_key_ = BoxRightKey();
494 }
495
496 // Copies the left/right tab from the src partition, but if take_box is
497 // true, copies the box instead and uses that as a key.
498 void ColPartition::CopyLeftTab(const ColPartition& src, bool take_box) {
499 left_key_tab_ = take_box ? false : src.left_key_tab_;
500 if (left_key_tab_) {
501 left_key_ = src.left_key_;
502 } else {
503 bounding_box_.set_left(XAtY(src.BoxLeftKey(), MidY()));
504 left_key_ = BoxLeftKey();
505 }
506 if (left_margin_ > bounding_box_.left())
507 left_margin_ = src.left_margin_;
508 }
509
510 // As CopyLeftTab, but with the right.
511 void ColPartition::CopyRightTab(const ColPartition& src, bool take_box) {
512 right_key_tab_ = take_box ? false : src.right_key_tab_;
513 if (right_key_tab_) {
514 right_key_ = src.right_key_;
515 } else {
516 bounding_box_.set_right(XAtY(src.BoxRightKey(), MidY()));
517 right_key_ = BoxRightKey();
518 }
519 if (right_margin_ < bounding_box_.right())
520 right_margin_ = src.right_margin_;
521 }
522
523 // Returns the left rule line x coord of the leftmost blob.
524 int ColPartition::LeftBlobRule() const {
525 BLOBNBOX_C_IT it(const_cast<BLOBNBOX_CLIST*>(&boxes_));
526 return it.data()->left_rule();
527 }
528 // Returns the right rule line x coord of the rightmost blob.
529 int ColPartition::RightBlobRule() const {
530 BLOBNBOX_C_IT it(const_cast<BLOBNBOX_CLIST*>(&boxes_));
531 it.move_to_last();
532 return it.data()->right_rule();
533 }
534
535 float ColPartition::SpecialBlobsDensity(const BlobSpecialTextType type) const {
536 ASSERT_HOST(type < BSTT_COUNT);
537 return special_blobs_densities_[type];
538 }
539
540 int ColPartition::SpecialBlobsCount(const BlobSpecialTextType type) {
541 ASSERT_HOST(type < BSTT_COUNT);
542 BLOBNBOX_C_IT blob_it(&boxes_);
543 int count = 0;
544 for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
545 BLOBNBOX* blob = blob_it.data();
546 BlobSpecialTextType blob_type = blob->special_text_type();
547 if (blob_type == type) {
548 count++;
549 }
550 }
551
552 return count;
553 }
554
555 void ColPartition::SetSpecialBlobsDensity(
556 const BlobSpecialTextType type, const float density) {
557 ASSERT_HOST(type < BSTT_COUNT);
558 special_blobs_densities_[type] = density;
559 }
560
561 void ColPartition::ComputeSpecialBlobsDensity() {
562 memset(special_blobs_densities_, 0, sizeof(special_blobs_densities_));
563 if (boxes_.empty()) {
564 return;
565 }
566
567 BLOBNBOX_C_IT blob_it(&boxes_);
568 for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
569 BLOBNBOX* blob = blob_it.data();
570 BlobSpecialTextType type = blob->special_text_type();
571 special_blobs_densities_[type]++;
572 }
573
574 for (int type = 0; type < BSTT_COUNT; ++type) {
575 special_blobs_densities_[type] /= boxes_.length();
576 }
577 }
578
579 // Add a partner above if upper, otherwise below.
580 // Add them uniquely and keep the list sorted by box left.
581 // Partnerships are added symmetrically to partner and this.
582 void ColPartition::AddPartner(bool upper, ColPartition* partner) {
583 if (upper) {
584 partner->lower_partners_.add_sorted(SortByBoxLeft<ColPartition>,
585 true, this);
586 upper_partners_.add_sorted(SortByBoxLeft<ColPartition>, true, partner);
587 } else {
588 partner->upper_partners_.add_sorted(SortByBoxLeft<ColPartition>,
589 true, this);
590 lower_partners_.add_sorted(SortByBoxLeft<ColPartition>, true, partner);
591 }
592 }
593
594 // Removes the partner from this, but does not remove this from partner.
595 // This asymmetric removal is so as not to mess up the iterator that is
596 // working on partner's partner list.
597 void ColPartition::RemovePartner(bool upper, ColPartition* partner) {
598 ColPartition_C_IT it(upper ? &upper_partners_ : &lower_partners_);
599 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
600 if (it.data() == partner) {
601 it.extract();
602 break;
603 }
604 }
605 }
606
607 // Returns the partner if the given partner is a singleton, otherwise NULL.
608 ColPartition* ColPartition::SingletonPartner(bool upper) {
609 ColPartition_CLIST* partners = upper ? &upper_partners_ : &lower_partners_;
610 if (!partners->singleton())
611 return NULL;
612 ColPartition_C_IT it(partners);
613 return it.data();
614 }
615
616 // Merge with the other partition and delete it.
617 void ColPartition::Absorb(ColPartition* other, WidthCallback* cb) {
618 // The result has to either own all of the blobs or none of them.
619 // Verify the flag is consisent.
620 ASSERT_HOST(owns_blobs() == other->owns_blobs());
621 // TODO(nbeato): check owns_blobs better. Right now owns_blobs
622 // should always be true when this is called. So there is no issues.
623 if (TabFind::WithinTestRegion(2, bounding_box_.left(),
624 bounding_box_.bottom()) ||
625 TabFind::WithinTestRegion(2, other->bounding_box_.left(),
626 other->bounding_box_.bottom())) {
627 tprintf("Merging:");
628 Print();
629 other->Print();
630 }
631
632 // Update the special_blobs_densities_.
633 memset(special_blobs_densities_, 0, sizeof(special_blobs_densities_));
634 for (int type = 0; type < BSTT_COUNT; ++type) {
635 int w1 = boxes_.length(), w2 = other->boxes_.length();
636 float new_val = special_blobs_densities_[type] * w1 +
637 other->special_blobs_densities_[type] * w2;
638 if (!w1 || !w2) {
639 special_blobs_densities_[type] = new_val / (w1 + w2);
640 }
641 }
642
643 // Merge the two sorted lists.
644 BLOBNBOX_C_IT it(&boxes_);
645 BLOBNBOX_C_IT it2(&other->boxes_);
646 for (; !it2.empty(); it2.forward()) {
647 BLOBNBOX* bbox2 = it2.extract();
648 ColPartition* prev_owner = bbox2->owner();
649 if (prev_owner != other && prev_owner != NULL) {
650 // A blob on other's list is owned by someone else; let them have it.
651 continue;
652 }
653 ASSERT_HOST(prev_owner == other || prev_owner == NULL);
654 if (prev_owner == other)
655 bbox2->set_owner(this);
656 it.add_to_end(bbox2);
657 }
658 left_margin_ = MIN(left_margin_, other->left_margin_);
659 right_margin_ = MAX(right_margin_, other->right_margin_);
660 if (other->left_key_ < left_key_) {
661 left_key_ = other->left_key_;
662 left_key_tab_ = other->left_key_tab_;
663 }
664 if (other->right_key_ > right_key_) {
665 right_key_ = other->right_key_;
666 right_key_tab_ = other->right_key_tab_;
667 }
668 // Combine the flow and blob_type in a sensible way.
669 // Dominant flows stay.
670 if (!DominatesInMerge(flow_, other->flow_)) {
671 flow_ = other->flow_;
672 blob_type_ = other->blob_type_;
673 }
674 SetBlobTypes();
675 if (IsVerticalType()) {
676 boxes_.sort(SortByBoxBottom<BLOBNBOX>);
677 last_add_was_vertical_ = true;
678 } else {
679 boxes_.sort(SortByBoxLeft<BLOBNBOX>);
680 last_add_was_vertical_ = false;
681 }
682 ComputeLimits();
683 // Fix partner lists. other is going away, so remove it as a
684 // partner of all its partners and add this in its place.
685 for (int upper = 0; upper < 2; ++upper) {
686 ColPartition_CLIST partners;
687 ColPartition_C_IT part_it(&partners);
688 part_it.add_list_after(upper ? &other->upper_partners_
689 : &other->lower_partners_);
690 for (part_it.move_to_first(); !part_it.empty(); part_it.forward()) {
691 ColPartition* partner = part_it.extract();
692 partner->RemovePartner(!upper, other);
693 partner->RemovePartner(!upper, this);
694 partner->AddPartner(!upper, this);
695 }
696 }
697 delete other;
698 if (cb != NULL) {
699 SetColumnGoodness(cb);
700 }
701 }
702
703 // Merge1 and merge2 are candidates to be merged, yet their combined box
704 // overlaps this. Is that allowed?
705 // Returns true if the overlap between this and the merged pair of
706 // merge candidates is sufficiently trivial to be allowed.
707 // The merged box can graze the edge of this by the ok_box_overlap
708 // if that exceeds the margin to the median top and bottom.
709 // ok_box_overlap should be set by the caller appropriate to the sizes of
710 // the text involved, and is usually a fraction of the median size of merge1
711 // and/or merge2, or this.
712 // TODO(rays) Determine whether vertical text needs to be considered.
713 bool ColPartition::OKMergeOverlap(const ColPartition& merge1,
714 const ColPartition& merge2,
715 int ok_box_overlap, bool debug) {
716 // Vertical partitions are not allowed to be involved.
717 if (IsVerticalType() || merge1.IsVerticalType() || merge2.IsVerticalType()) {
718 if (debug)
719 tprintf("Vertical partition\n");
720 return false;
721 }
722 // The merging partitions must strongly overlap each other.
723 if (!merge1.VSignificantCoreOverlap(merge2)) {
724 if (debug)
725 tprintf("Voverlap %d (%d)\n",
726 merge1.VCoreOverlap(merge2),
727 merge1.VSignificantCoreOverlap(merge2));
728 return false;
729 }
730 // The merged box must not overlap the median bounds of this.
731 TBOX merged_box(merge1.bounding_box());
732 merged_box += merge2.bounding_box();
733 if (merged_box.bottom() < median_top_ && merged_box.top() > median_bottom_ &&
734 merged_box.bottom() < bounding_box_.top() - ok_box_overlap &&
735 merged_box.top() > bounding_box_.bottom() + ok_box_overlap) {
736 if (debug)
737 tprintf("Excessive box overlap\n");
738 return false;
739 }
740 // Looks OK!
741 return true;
742 }
743
744 // Find the blob at which to split this to minimize the overlap with the
745 // given box. Returns the first blob to go in the second partition.
746 BLOBNBOX* ColPartition::OverlapSplitBlob(const TBOX& box) {
747 if (boxes_.empty() || boxes_.singleton())
748 return NULL;
749 BLOBNBOX_C_IT it(&boxes_);
750 TBOX left_box(it.data()->bounding_box());
751 for (it.forward(); !it.at_first(); it.forward()) {
752 BLOBNBOX* bbox = it.data();
753 left_box += bbox->bounding_box();
754 if (left_box.overlap(box))
755 return bbox;
756 }
757 return NULL;
758 }
759
760 // Split this partition keeping the first half in this and returning
761 // the second half.
762 // Splits by putting the split_blob and the blobs that follow
763 // in the second half, and the rest in the first half.
764 ColPartition* ColPartition::SplitAtBlob(BLOBNBOX* split_blob) {
765 ColPartition* split_part = ShallowCopy();
766 split_part->set_owns_blobs(owns_blobs());
767 BLOBNBOX_C_IT it(&boxes_);
768 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
769 BLOBNBOX* bbox = it.data();
770 ColPartition* prev_owner = bbox->owner();
771 ASSERT_HOST(!owns_blobs() || prev_owner == this || prev_owner == NULL);
772 if (bbox == split_blob || !split_part->boxes_.empty()) {
773 split_part->AddBox(it.extract());
774 if (owns_blobs() && prev_owner != NULL)
775 bbox->set_owner(split_part);
776 }
777 }
778 ASSERT_HOST(!it.empty());
779 if (split_part->IsEmpty()) {
780 // Split part ended up with nothing. Possible if split_blob is not
781 // in the list of blobs.
782 delete split_part;
783 return NULL;
784 }
785 right_key_tab_ = false;
786 split_part->left_key_tab_ = false;
787 ComputeLimits();
788 // TODO(nbeato) Merge Ray's CL like this:
789 // if (owns_blobs())
790 // SetBlobTextlineGoodness();
791 split_part->ComputeLimits();
792 // TODO(nbeato) Merge Ray's CL like this:
793 // if (split_part->owns_blobs())
794 // split_part->SetBlobTextlineGoodness();
795 return split_part;
796 }
797
798 // Split this partition at the given x coordinate, returning the right
799 // half and keeping the left half in this.
800 ColPartition* ColPartition::SplitAt(int split_x) {
801 if (split_x <= bounding_box_.left() || split_x >= bounding_box_.right())
802 return NULL; // There will be no change.
803 ColPartition* split_part = ShallowCopy();
804 split_part->set_owns_blobs(owns_blobs());
805 BLOBNBOX_C_IT it(&boxes_);
806 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
807 BLOBNBOX* bbox = it.data();
808 ColPartition* prev_owner = bbox->owner();
809 ASSERT_HOST(!owns_blobs() || prev_owner == this || prev_owner == NULL);
810 const TBOX& box = bbox->bounding_box();
811 if (box.left() >= split_x) {
812 split_part->AddBox(it.extract());
813 if (owns_blobs() && prev_owner != NULL)
814 bbox->set_owner(split_part);
815 }
816 }
817 ASSERT_HOST(!it.empty());
818 if (split_part->IsEmpty()) {
819 // Split part ended up with nothing. Possible if split_x passes
820 // through the last blob.
821 delete split_part;
822 return NULL;
823 }
824 right_key_tab_ = false;
825 split_part->left_key_tab_ = false;
826 right_margin_ = split_x;
827 split_part->left_margin_ = split_x;
828 ComputeLimits();
829 split_part->ComputeLimits();
830 return split_part;
831 }
832
833 // Recalculates all the coordinate limits of the partition.
834 void ColPartition::ComputeLimits() {
835 bounding_box_ = TBOX(); // Clear it
836 BLOBNBOX_C_IT it(&boxes_);
837 BLOBNBOX* bbox = NULL;
838 int non_leader_count = 0;
839 if (it.empty()) {
840 bounding_box_.set_left(left_margin_);
841 bounding_box_.set_right(right_margin_);
842 bounding_box_.set_bottom(0);
843 bounding_box_.set_top(0);
844 } else {
845 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
846 bbox = it.data();
847 bounding_box_ += bbox->bounding_box();
848 if (bbox->flow() != BTFT_LEADER)
849 ++non_leader_count;
850 }
851 }
852 if (!left_key_tab_)
853 left_key_ = BoxLeftKey();
854 if (left_key_ > BoxLeftKey() && textord_debug_bugs) {
855 // TODO(rays) investigate the causes of these error messages, to find
856 // out if they are genuinely harmful, or just indicative of junk input.
857 tprintf("Computed left-illegal partition\n");
858 Print();
859 }
860 if (!right_key_tab_)
861 right_key_ = BoxRightKey();
862 if (right_key_ < BoxRightKey() && textord_debug_bugs) {
863 tprintf("Computed right-illegal partition\n");
864 Print();
865 }
866 if (it.empty())
867 return;
868 if (IsImageType() || blob_type() == BRT_RECTIMAGE ||
869 blob_type() == BRT_POLYIMAGE) {
870 median_top_ = bounding_box_.top();
871 median_bottom_ = bounding_box_.bottom();
872 median_size_ = bounding_box_.height();
873 median_left_ = bounding_box_.left();
874 median_right_ = bounding_box_.right();
875 median_width_ = bounding_box_.width();
876 } else {
877 STATS top_stats(bounding_box_.bottom(), bounding_box_.top() + 1);
878 STATS bottom_stats(bounding_box_.bottom(), bounding_box_.top() + 1);
879 STATS size_stats(0, bounding_box_.height() + 1);
880 STATS left_stats(bounding_box_.left(), bounding_box_.right() + 1);
881 STATS right_stats(bounding_box_.left(), bounding_box_.right() + 1);
882 STATS width_stats(0, bounding_box_.width() + 1);
883 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
884 bbox = it.data();
885 if (non_leader_count == 0 || bbox->flow() != BTFT_LEADER) {
886 TBOX box = bbox->bounding_box();
887 int area = box.area();
888 top_stats.add(box.top(), area);
889 bottom_stats.add(box.bottom(), area);
890 size_stats.add(box.height(), area);
891 left_stats.add(box.left(), area);
892 right_stats.add(box.right(), area);
893 width_stats.add(box.width(), area);
894 }
895 }
896 median_top_ = static_cast<int>(top_stats.median() + 0.5);
897 median_bottom_ = static_cast<int>(bottom_stats.median() + 0.5);
898 median_size_ = static_cast<int>(size_stats.median() + 0.5);
899 median_left_ = static_cast<int>(left_stats.median() + 0.5);
900 median_right_ = static_cast<int>(right_stats.median() + 0.5);
901 median_width_ = static_cast<int>(width_stats.median() + 0.5);
902 }
903
904 if (right_margin_ < bounding_box_.right() && textord_debug_bugs) {
905 tprintf("Made partition with bad right coords");
906 Print();
907 }
908 if (left_margin_ > bounding_box_.left() && textord_debug_bugs) {
909 tprintf("Made partition with bad left coords");
910 Print();
911 }
912 // Fix partner lists. The bounding box has changed and partners are stored
913 // in bounding box order, so remove and reinsert this as a partner
914 // of all its partners.
915 for (int upper = 0; upper < 2; ++upper) {
916 ColPartition_CLIST partners;
917 ColPartition_C_IT part_it(&partners);
918 part_it.add_list_after(upper ? &upper_partners_ : &lower_partners_);
919 for (part_it.move_to_first(); !part_it.empty(); part_it.forward()) {
920 ColPartition* partner = part_it.extract();
921 partner->RemovePartner(!upper, this);
922 partner->AddPartner(!upper, this);
923 }
924 }
925 if (TabFind::WithinTestRegion(2, bounding_box_.left(),
926 bounding_box_.bottom())) {
927 tprintf("Recomputed box for partition %p\n", this);
928 Print();
929 }
930 }
931
932 // Returns the number of boxes that overlap the given box.
933 int ColPartition::CountOverlappingBoxes(const TBOX& box) {
934 BLOBNBOX_C_IT it(&boxes_);
935 int overlap_count = 0;
936 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
937 BLOBNBOX* bbox = it.data();
938 if (box.overlap(bbox->bounding_box()))
939 ++overlap_count;
940 }
941 return overlap_count;
942 }
943
944 // Computes and sets the type_ and first_colum_, last_column_ and column_set_.
945 // resolution refers to the ppi resolution of the image.
946 void ColPartition::SetPartitionType(int resolution, ColPartitionSet* columns) {
947 int first_spanned_col = -1;
948 ColumnSpanningType span_type =
949 columns->SpanningType(resolution,
950 bounding_box_.left(), bounding_box_.right(),
951 MidY(), left_margin_, right_margin_,
952 &first_column_, &last_column_,
953 &first_spanned_col);
954 column_set_ = columns;
955 if (first_column_ < last_column_ && span_type == CST_PULLOUT &&
956 !IsLineType()) {
957 // Unequal columns may indicate that the pullout spans one of the columns
958 // it lies in, so force it to be allocated to just that column.
959 if (first_spanned_col >= 0) {
960 first_column_ = first_spanned_col;
961 last_column_ = first_spanned_col;
962 } else {
963 if ((first_column_ & 1) == 0)
964 last_column_ = first_column_;
965 else if ((last_column_ & 1) == 0)
966 first_column_ = last_column_;
967 else
968 first_column_ = last_column_ = (first_column_ + last_column_) / 2;
969 }
970 }
971 type_ = PartitionType(span_type);
972 }
973
974 // Returns the PartitionType from the current BlobRegionType and a column
975 // flow spanning type ColumnSpanningType, generated by
976 // ColPartitionSet::SpanningType, that indicates how the partition sits
977 // in the columns.
978 PolyBlockType ColPartition::PartitionType(ColumnSpanningType flow) const {
979 if (flow == CST_NOISE) {
980 if (blob_type_ != BRT_HLINE && blob_type_ != BRT_VLINE &&
981 blob_type_ != BRT_RECTIMAGE && blob_type_ != BRT_VERT_TEXT)
982 return PT_NOISE;
983 flow = CST_FLOWING;
984 }
985
986 switch (blob_type_) {
987 case BRT_NOISE:
988 return PT_NOISE;
989 case BRT_HLINE:
990 return PT_HORZ_LINE;
991 case BRT_VLINE:
992 return PT_VERT_LINE;
993 case BRT_RECTIMAGE:
994 case BRT_POLYIMAGE:
995 switch (flow) {
996 case CST_FLOWING:
997 return PT_FLOWING_IMAGE;
998 case CST_HEADING:
999 return PT_HEADING_IMAGE;
1000 case CST_PULLOUT:
1001 return PT_PULLOUT_IMAGE;
1002 default:
1003 ASSERT_HOST(!"Undefined flow type for image!");
1004 }
1005 break;
1006 case BRT_VERT_TEXT:
1007 return PT_VERTICAL_TEXT;
1008 case BRT_TEXT:
1009 case BRT_UNKNOWN:
1010 default:
1011 switch (flow) {
1012 case CST_FLOWING:
1013 return PT_FLOWING_TEXT;
1014 case CST_HEADING:
1015 return PT_HEADING_TEXT;
1016 case CST_PULLOUT:
1017 return PT_PULLOUT_TEXT;
1018 default:
1019 ASSERT_HOST(!"Undefined flow type for text!");
1020 }
1021 }
1022 ASSERT_HOST(!"Should never get here!");
1023 return PT_NOISE;
1024 }
1025
1026 // Returns the first and last column touched by this partition.
1027 // resolution refers to the ppi resolution of the image.
1028 void ColPartition::ColumnRange(int resolution, ColPartitionSet* columns,
1029 int* first_col, int* last_col) {
1030 int first_spanned_col = -1;
1031 ColumnSpanningType span_type =
1032 columns->SpanningType(resolution,
1033 bounding_box_.left(), bounding_box_.right(),
1034 MidY(), left_margin_, right_margin_,
1035 first_col, last_col,
1036 &first_spanned_col);
1037 type_ = PartitionType(span_type);
1038 }
1039
1040 // Sets the internal flags good_width_ and good_column_.
1041 void ColPartition::SetColumnGoodness(WidthCallback* cb) {
1042 int y = MidY();
1043 int width = RightAtY(y) - LeftAtY(y);
1044 good_width_ = cb->Run(width);
1045 good_column_ = blob_type_ == BRT_TEXT && left_key_tab_ && right_key_tab_;
1046 }
1047
1048 // Determines whether the blobs in this partition mostly represent
1049 // a leader (fixed pitch sequence) and sets the member blobs accordingly.
1050 // Note that height is assumed to have been tested elsewhere, and that this
1051 // function will find most fixed-pitch text as leader without a height filter.
1052 // Leader detection is limited to sequences of identical width objects,
1053 // such as .... or ----, so patterns, such as .-.-.-.-. will not be found.
1054 bool ColPartition::MarkAsLeaderIfMonospaced() {
1055 bool result = false;
1056 // Gather statistics on the gaps between blobs and the widths of the blobs.
1057 int part_width = bounding_box_.width();
1058 STATS gap_stats(0, part_width);
1059 STATS width_stats(0, part_width);
1060 BLOBNBOX_C_IT it(&boxes_);
1061 BLOBNBOX* prev_blob = it.data();
1062 prev_blob->set_flow(BTFT_NEIGHBOURS);
1063 width_stats.add(prev_blob->bounding_box().width(), 1);
1064 int blob_count = 1;
1065 for (it.forward(); !it.at_first(); it.forward()) {
1066 BLOBNBOX* blob = it.data();
1067 int left = blob->bounding_box().left();
1068 int right = blob->bounding_box().right();
1069 gap_stats.add(left - prev_blob->bounding_box().right(), 1);
1070 width_stats.add(right - left, 1);
1071 blob->set_flow(BTFT_NEIGHBOURS);
1072 prev_blob = blob;
1073 ++blob_count;
1074 }
1075 double median_gap = gap_stats.median();
1076 double median_width = width_stats.median();
1077 double max_width = MAX(median_gap, median_width);
1078 double min_width = MIN(median_gap, median_width);
1079 double gap_iqr = gap_stats.ile(0.75f) - gap_stats.ile(0.25f);
1080 if (textord_debug_tabfind >= 4) {
1081 tprintf("gap iqr = %g, blob_count=%d, limits=%g,%g\n",
1082 gap_iqr, blob_count, max_width * kMaxLeaderGapFractionOfMax,
1083 min_width * kMaxLeaderGapFractionOfMin);
1084 }
1085 if (gap_iqr < max_width * kMaxLeaderGapFractionOfMax &&
1086 gap_iqr < min_width * kMaxLeaderGapFractionOfMin &&
1087 blob_count >= kMinLeaderCount) {
1088 // This is stable enough to be called a leader, so check the widths.
1089 // Since leader dashes can join, run a dp cutting algorithm and go
1090 // on the cost.
1091 int offset = static_cast<int>(ceil(gap_iqr * 2));
1092 int min_step = static_cast<int>(median_gap + median_width + 0.5);
1093 int max_step = min_step + offset;
1094 min_step -= offset;
1095 // Pad the buffer with min_step/2 on each end.
1096 int part_left = bounding_box_.left() - min_step / 2;
1097 part_width += min_step;
1098 DPPoint* projection = new DPPoint[part_width];
1099 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1100 BLOBNBOX* blob = it.data();
1101 int left = blob->bounding_box().left();
1102 int right = blob->bounding_box().right();
1103 int height = blob->bounding_box().height();
1104 for (int x = left; x < right; ++x) {
1105 projection[left - part_left].AddLocalCost(height);
1106 }
1107 }
1108 DPPoint* best_end = DPPoint::Solve(min_step, max_step, false,
1109 &DPPoint::CostWithVariance,
1110 part_width, projection);
1111 if (best_end != NULL && best_end->total_cost() < blob_count) {
1112 // Good enough. Call it a leader.
1113 result = true;
1114 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1115 BLOBNBOX* blob = it.data();
1116 TBOX box = blob->bounding_box();
1117 // If the first or last blob is spaced too much, don't mark it.
1118 if (it.at_first()) {
1119 int gap = it.data_relative(1)->bounding_box().left() -
1120 blob->bounding_box().right();
1121 if (blob->bounding_box().width() + gap > max_step) {
1122 it.extract();
1123 continue;
1124 }
1125 }
1126 if (it.at_last()) {
1127 int gap = blob->bounding_box().left() -
1128 it.data_relative(-1)->bounding_box().right();
1129 if (blob->bounding_box().width() + gap > max_step) {
1130 it.extract();
1131 break;
1132 }
1133 }
1134 blob->set_region_type(BRT_TEXT);
1135 blob->set_flow(BTFT_LEADER);
1136 }
1137 blob_type_ = BRT_TEXT;
1138 flow_ = BTFT_LEADER;
1139 } else if (textord_debug_tabfind) {
1140 if (best_end == NULL) {
1141 tprintf("No path\n");
1142 } else {
1143 tprintf("Total cost = %d vs allowed %d\n",
1144 best_end->total_cost() < blob_count);
1145 }
1146 }
1147 delete [] projection;
1148 }
1149 return result;
1150 }
1151
1152 // Given the result of TextlineProjection::EvaluateColPartition, (positive for
1153 // horizontal text, negative for vertical text, and near zero for non-text),
1154 // sets the blob_type_ and flow_ for this partition to indicate whether it
1155 // is strongly or weakly vertical or horizontal text, or non-text.
1156 // The function assumes that the blob neighbours are valid (from
1157 // StrokeWidth::SetNeighbours) and that those neighbours have their
1158 // region_type() set.
1159 void ColPartition::SetRegionAndFlowTypesFromProjectionValue(int value) {
1160 int blob_count = 0; // Total # blobs.
1161 int good_blob_score_ = 0; // Total # good strokewidth neighbours.
1162 int noisy_count = 0; // Total # neighbours marked as noise.
1163 int hline_count = 0;
1164 int vline_count = 0;
1165 BLOBNBOX_C_IT it(&boxes_);
1166 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1167 BLOBNBOX* blob = it.data();
1168 ++blob_count;
1169 noisy_count += blob->NoisyNeighbours();
1170 good_blob_score_ += blob->GoodTextBlob();
1171 if (blob->region_type() == BRT_HLINE) ++hline_count;
1172 if (blob->region_type() == BRT_VLINE) ++vline_count;
1173 }
1174 flow_ = BTFT_NEIGHBOURS;
1175 blob_type_ = BRT_UNKNOWN;
1176 if (hline_count > vline_count) {
1177 flow_ = BTFT_NONE;
1178 blob_type_ = BRT_HLINE;
1179 } else if (vline_count > hline_count) {
1180 flow_ = BTFT_NONE;
1181 blob_type_ = BRT_VLINE;
1182 } else if (value < -1 || 1 < value) {
1183 int long_side;
1184 int short_side;
1185 if (value > 0) {
1186 long_side = bounding_box_.width();
1187 short_side = bounding_box_.height();
1188 blob_type_ = BRT_TEXT;
1189 } else {
1190 long_side = bounding_box_.height();
1191 short_side = bounding_box_.width();
1192 blob_type_ = BRT_VERT_TEXT;
1193 }
1194 // We will combine the old metrics using aspect ratio and blob counts
1195 // with the input value by allowing a strong indication to flip the
1196 // STRONG_CHAIN/CHAIN flow values.
1197 int strong_score = blob_count >= kHorzStrongTextlineCount ? 1 : 0;
1198 if (short_side > kHorzStrongTextlineHeight) ++strong_score;
1199 if (short_side * kHorzStrongTextlineAspect < long_side) ++strong_score;
1200 if (abs(value) >= kMinStrongTextValue)
1201 flow_ = BTFT_STRONG_CHAIN;
1202 else if (abs(value) >= kMinChainTextValue)
1203 flow_ = BTFT_CHAIN;
1204 else
1205 flow_ = BTFT_NEIGHBOURS;
1206 // Upgrade chain to strong chain if the other indicators are good
1207 if (flow_ == BTFT_CHAIN && strong_score == 3)
1208 flow_ = BTFT_STRONG_CHAIN;
1209 // Downgrade strong vertical text to chain if the indicators are bad.
1210 if (flow_ == BTFT_STRONG_CHAIN && value < 0 && strong_score < 2)
1211 flow_ = BTFT_CHAIN;
1212 }
1213 if (flow_ == BTFT_NEIGHBOURS) {
1214 // Check for noisy neighbours.
1215 if (noisy_count >= blob_count) {
1216 flow_ = BTFT_NONTEXT;
1217 blob_type_= BRT_NOISE;
1218 }
1219 }
1220 if (TabFind::WithinTestRegion(2, bounding_box_.left(),
1221 bounding_box_.bottom())) {
1222 tprintf("RegionFlowTypesFromProjectionValue count=%d, noisy=%d, score=%d,",
1223 blob_count, noisy_count, good_blob_score_);
1224 tprintf(" Projection value=%d, flow=%d, blob_type=%d\n",
1225 value, flow_, blob_type_);
1226 Print();
1227 }
1228 SetBlobTypes();
1229 }
1230
1231 // Sets all blobs with the partition blob type and flow, but never overwrite
1232 // leader blobs, as we need to be able to identify them later.
1233 void ColPartition::SetBlobTypes() {
1234 if (!owns_blobs())
1235 return;
1236 BLOBNBOX_C_IT it(&boxes_);
1237 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1238 BLOBNBOX* blob = it.data();
1239 if (blob->flow() != BTFT_LEADER)
1240 blob->set_flow(flow_);
1241 blob->set_region_type(blob_type_);
1242 ASSERT_HOST(blob->owner() == NULL || blob->owner() == this);
1243 }
1244 }
1245
1246 // Returns true if a decent baseline can be fitted through the blobs.
1247 // Works for both horizontal and vertical text.
1248 bool ColPartition::HasGoodBaseline() {
1249 // Approximation of the baseline.
1250 DetLineFit linepoints;
1251 // Calculation of the mean height on this line segment. Note that these
1252 // variable names apply to the context of a horizontal line, and work
1253 // analogously, rather than literally in the case of a vertical line.
1254 int total_height = 0;
1255 int coverage = 0;
1256 int height_count = 0;
1257 int width = 0;
1258 BLOBNBOX_C_IT it(&boxes_);
1259 TBOX box(it.data()->bounding_box());
1260 // Accumulate points representing the baseline at the middle of each blob,
1261 // but add an additional point for each end of the line. This makes it
1262 // harder to fit a severe skew angle, as it is most likely not right.
1263 if (IsVerticalType()) {
1264 // For a vertical line, use the right side as the baseline.
1265 ICOORD first_pt(box.right(), box.bottom());
1266 // Use the bottom-right of the first (bottom) box, the top-right of the
1267 // last, and the middle-right of all others.
1268 linepoints.Add(first_pt);
1269 for (it.forward(); !it.at_last(); it.forward()) {
1270 BLOBNBOX* blob = it.data();
1271 box = blob->bounding_box();
1272 ICOORD box_pt(box.right(), (box.top() + box.bottom()) / 2);
1273 linepoints.Add(box_pt);
1274 total_height += box.width();
1275 coverage += box.height();
1276 ++height_count;
1277 }
1278 box = it.data()->bounding_box();
1279 ICOORD last_pt(box.right(), box.top());
1280 linepoints.Add(last_pt);
1281 width = last_pt.y() - first_pt.y();
1282
1283 } else {
1284 // Horizontal lines use the bottom as the baseline.
1285 TBOX box(it.data()->bounding_box());
1286 // Use the bottom-left of the first box, the the bottom-right of the last,
1287 // and the middle of all others.
1288 ICOORD first_pt(box.left(), box.bottom());
1289 linepoints.Add(first_pt);
1290 for (it.forward(); !it.at_last(); it.forward()) {
1291 BLOBNBOX* blob = it.data();
1292 box = blob->bounding_box();
1293 ICOORD box_pt((box.left() + box.right()) / 2, box.bottom());
1294 linepoints.Add(box_pt);
1295 total_height += box.height();
1296 coverage += box.width();
1297 ++height_count;
1298 }
1299 box = it.data()->bounding_box();
1300 ICOORD last_pt(box.right(), box.bottom());
1301 linepoints.Add(last_pt);
1302 width = last_pt.x() - first_pt.x();
1303 }
1304 // Maximum median error allowed to be a good text line.
1305 double max_error = kMaxBaselineError * total_height / height_count;
1306 ICOORD start_pt, end_pt;
1307 double error = linepoints.Fit(&start_pt, &end_pt);
1308 return error < max_error && coverage >= kMinBaselineCoverage * width;
1309 }
1310
1311 // Adds this ColPartition to a matching WorkingPartSet if one can be found,
1312 // otherwise starts a new one in the appropriate column, ending the previous.
1313 void ColPartition::AddToWorkingSet(const ICOORD& bleft, const ICOORD& tright,
1314 int resolution,
1315 ColPartition_LIST* used_parts,
1316 WorkingPartSet_LIST* working_sets) {
1317 if (block_owned_)
1318 return; // Done it already.
1319 block_owned_ = true;
1320 WorkingPartSet_IT it(working_sets);
1321 // If there is an upper partner use its working_set_ directly.
1322 ColPartition* partner = SingletonPartner(true);
1323 if (partner != NULL && partner->working_set_ != NULL) {
1324 working_set_ = partner->working_set_;
1325 working_set_->AddPartition(this);
1326 return;
1327 }
1328 if (partner != NULL && textord_debug_bugs) {
1329 tprintf("Partition with partner has no working set!:");
1330 Print();
1331 partner->Print();
1332 }
1333 // Search for the column that the left edge fits in.
1334 WorkingPartSet* work_set = NULL;
1335 it.move_to_first();
1336 int col_index = 0;
1337 for (it.mark_cycle_pt(); !it.cycled_list() &&
1338 col_index != first_column_;
1339 it.forward(), ++col_index);
1340 if (textord_debug_tabfind >= 2) {
1341 tprintf("Match is %s for:", (col_index & 1) ? "Real" : "Between");
1342 Print();
1343 }
1344 if (it.cycled_list() && textord_debug_bugs) {
1345 tprintf("Target column=%d, only had %d\n", first_column_, col_index);
1346 }
1347 ASSERT_HOST(!it.cycled_list());
1348 work_set = it.data();
1349 // If last_column_ != first_column, then we need to scoop up all blocks
1350 // between here and the last_column_ and put back in work_set.
1351 if (!it.cycled_list() && last_column_ != first_column_) {
1352 // Find the column that the right edge falls in.
1353 BLOCK_LIST completed_blocks;
1354 TO_BLOCK_LIST to_blocks;
1355 for (; !it.cycled_list() && col_index <= last_column_;
1356 it.forward(), ++col_index) {
1357 WorkingPartSet* end_set = it.data();
1358 end_set->ExtractCompletedBlocks(bleft, tright, resolution, used_parts,
1359 &completed_blocks, &to_blocks);
1360 }
1361 work_set->InsertCompletedBlocks(&completed_blocks, &to_blocks);
1362 }
1363 working_set_ = work_set;
1364 work_set->AddPartition(this);
1365 }
1366
1367 // From the given block_parts list, builds one or more BLOCKs and
1368 // corresponding TO_BLOCKs, such that the line spacing is uniform in each.
1369 // Created blocks are appended to the end of completed_blocks and to_blocks.
1370 // The used partitions are put onto used_parts, as they may still be referred
1371 // to in the partition grid. bleft, tright and resolution are the bounds
1372 // and resolution of the original image.
1373 void ColPartition::LineSpacingBlocks(const ICOORD& bleft, const ICOORD& tright,
1374 int resolution,
1375 ColPartition_LIST* block_parts,
1376 ColPartition_LIST* used_parts,
1377 BLOCK_LIST* completed_blocks,
1378 TO_BLOCK_LIST* to_blocks) {
1379 int page_height = tright.y() - bleft.y();
1380 // Compute the initial spacing stats.
1381 ColPartition_IT it(block_parts);
1382 int part_count = 0;
1383 int max_line_height = 0;
1384
1385 // TODO(joeliu): We should add some special logic for PT_INLINE_EQUATION type
1386 // because their line spacing with their neighbors maybe smaller and their
1387 // height may be slightly larger.
1388
1389 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1390 ColPartition* part = it.data();
1391 ASSERT_HOST(!part->boxes()->empty());
1392 STATS side_steps(0, part->bounding_box().height());
1393 if (part->bounding_box().height() > max_line_height)
1394 max_line_height = part->bounding_box().height();
1395 BLOBNBOX_C_IT blob_it(part->boxes());
1396 int prev_bottom = blob_it.data()->bounding_box().bottom();
1397 for (blob_it.forward(); !blob_it.at_first(); blob_it.forward()) {
1398 BLOBNBOX* blob = blob_it.data();
1399 int bottom = blob->bounding_box().bottom();
1400 int step = bottom - prev_bottom;
1401 if (step < 0)
1402 step = -step;
1403 side_steps.add(step, 1);
1404 prev_bottom = bottom;
1405 }
1406 part->set_side_step(static_cast<int>(side_steps.median() + 0.5));
1407 if (!it.at_last()) {
1408 ColPartition* next_part = it.data_relative(1);
1409 part->set_bottom_spacing(part->median_bottom() -
1410 next_part->median_bottom());
1411 part->set_top_spacing(part->median_top() - next_part->median_top());
1412 } else {
1413 part->set_bottom_spacing(page_height);
1414 part->set_top_spacing(page_height);
1415 }
1416 if (textord_debug_tabfind) {
1417 part->Print();
1418 tprintf("side step = %.2f, top spacing = %d, bottom spacing=%d\n",
1419 side_steps.median(), part->top_spacing(), part->bottom_spacing());
1420 }
1421 ++part_count;
1422 }
1423 if (part_count == 0)
1424 return;
1425
1426 SmoothSpacings(resolution, page_height, block_parts);
1427
1428 // Move the partitions into individual block lists and make the blocks.
1429 BLOCK_IT block_it(completed_blocks);
1430 TO_BLOCK_IT to_block_it(to_blocks);
1431 ColPartition_LIST spacing_parts;
1432 ColPartition_IT sp_block_it(&spacing_parts);
1433 int same_block_threshold = max_line_height * kMaxSameBlockLineSpacing;
1434 for (it.mark_cycle_pt(); !it.empty();) {
1435 ColPartition* part = it.extract();
1436 sp_block_it.add_to_end(part);
1437 it.forward();
1438 if (it.empty() || part->bottom_spacing() > same_block_threshold ||
1439 !part->SpacingsEqual(*it.data(), resolution)) {
1440 // There is a spacing boundary. Check to see if it.data() belongs
1441 // better in the current block or the next one.
1442 if (!it.empty() && part->bottom_spacing() <= same_block_threshold) {
1443 ColPartition* next_part = it.data();
1444 // If there is a size match one-way, then the middle line goes with
1445 // its matched size, otherwise it goes with the smallest spacing.
1446 ColPartition* third_part = it.at_last() ? NULL : it.data_relative(1);
1447 if (textord_debug_tabfind) {
1448 tprintf("Spacings unequal: upper:%d/%d, lower:%d/%d,"
1449 " sizes %d %d %d\n",
1450 part->top_spacing(), part->bottom_spacing(),
1451 next_part->top_spacing(), next_part->bottom_spacing(),
1452 part->median_size(), next_part->median_size(),
1453 third_part != NULL ? third_part->median_size() : 0);
1454 }
1455 // We can only consider adding the next line to the block if the sizes
1456 // match and the lines are close enough for their size.
1457 if (part->SizesSimilar(*next_part) &&
1458 next_part->median_size() * kMaxSameBlockLineSpacing >
1459 part->bottom_spacing() &&
1460 part->median_size() * kMaxSameBlockLineSpacing >
1461 part->top_spacing()) {
1462 // Even now, we can only add it as long as the third line doesn't
1463 // match in the same way and have a smaller bottom spacing.
1464 if (third_part == NULL ||
1465 !next_part->SizesSimilar(*third_part) ||
1466 third_part->median_size() * kMaxSameBlockLineSpacing <=
1467 next_part->bottom_spacing() ||
1468 next_part->median_size() * kMaxSameBlockLineSpacing <=
1469 next_part->top_spacing() ||
1470 next_part->bottom_spacing() > part->bottom_spacing()) {
1471 // Add to the current block.
1472 sp_block_it.add_to_end(it.extract());
1473 it.forward();
1474 if (textord_debug_tabfind) {
1475 tprintf("Added line to current block.\n");
1476 }
1477 }
1478 }
1479 }
1480 TO_BLOCK* to_block = MakeBlock(bleft, tright, &spacing_parts, used_parts);
1481 if (to_block != NULL) {
1482 to_block_it.add_to_end(to_block);
1483 block_it.add_to_end(to_block->block);
1484 }
1485 sp_block_it.set_to_list(&spacing_parts);
1486 } else {
1487 if (textord_debug_tabfind && !it.empty()) {
1488 ColPartition* next_part = it.data();
1489 tprintf("Spacings equal: upper:%d/%d, lower:%d/%d\n",
1490 part->top_spacing(), part->bottom_spacing(),
1491 next_part->top_spacing(), next_part->bottom_spacing(),
1492 part->median_size(), next_part->median_size());
1493 }
1494 }
1495 }
1496 }
1497
1498 // Helper function to clip the input pos to the given bleft, tright bounds.
1499 static void ClipCoord(const ICOORD& bleft, const ICOORD& tright, ICOORD* pos) {
1500 if (pos->x() < bleft.x())
1501 pos->set_x(bleft.x());
1502 if (pos->x() > tright.x())
1503 pos->set_x(tright.x());
1504 if (pos->y() < bleft.y())
1505 pos->set_y(bleft.y());
1506 if (pos->y() > tright.y())
1507 pos->set_y(tright.y());
1508 }
1509
1510 // Helper moves the blobs from the given list of block_parts into the block
1511 // itself. Sets up the block for (old) textline formation correctly for
1512 // vertical and horizontal text. The partitions are moved to used_parts
1513 // afterwards, as they cannot be deleted yet.
1514 static TO_BLOCK* MoveBlobsToBlock(bool vertical_text, int line_spacing,
1515 BLOCK* block,
1516 ColPartition_LIST* block_parts,
1517 ColPartition_LIST* used_parts) {
1518 // Make a matching TO_BLOCK and put all the BLOBNBOXes from the parts in it.
1519 // Move all the parts to a done list as they are no longer needed, except
1520 // that have have to continue to exist until the part grid is deleted.
1521 // Compute the median blob size as we go, as the block needs to know.
1522 TBOX block_box(block->bounding_box());
1523 STATS sizes(0, MAX(block_box.width(), block_box.height()));
1524 bool text_type = block->poly_block()->IsText();
1525 ColPartition_IT it(block_parts);
1526 TO_BLOCK* to_block = new TO_BLOCK(block);
1527 BLOBNBOX_IT blob_it(&to_block->blobs);
1528 ColPartition_IT used_it(used_parts);
1529 for (it.move_to_first(); !it.empty(); it.forward()) {
1530 ColPartition* part = it.extract();
1531 // Transfer blobs from all regions to the output blocks.
1532 // Blobs for non-text regions will be used to define the polygonal
1533 // bounds of the region.
1534 for (BLOBNBOX_C_IT bb_it(part->boxes()); !bb_it.empty();
1535 bb_it.forward()) {
1536 BLOBNBOX* bblob = bb_it.extract();
1537 if (bblob->owner() != part) {
1538 tprintf("Ownership incorrect for blob:");
1539 bblob->bounding_box().print();
1540 tprintf("Part=");
1541 part->Print();
1542 if (bblob->owner() == NULL) {
1543 tprintf("Not owned\n");
1544 } else {
1545 tprintf("Owner part:");
1546 bblob->owner()->Print();
1547 }
1548 }
1549 ASSERT_HOST(bblob->owner() == part);
1550 // Assert failure here is caused by arbitrarily changing the partition
1551 // type without also changing the blob type, such as in
1552 // InsertSmallBlobsAsUnknowns.
1553 ASSERT_HOST(!text_type || bblob->region_type() >= BRT_UNKNOWN);
1554 C_OUTLINE_LIST* outlines = bblob->cblob()->out_list();
1555 C_OUTLINE_IT ol_it(outlines);
1556 if (outlines->singleton()) {
1557 ASSERT_HOST(!text_type || ol_it.data()->pathlength() > 0);
1558 if (vertical_text)
1559 sizes.add(bblob->bounding_box().width(), 1);
1560 else
1561 sizes.add(bblob->bounding_box().height(), 1);
1562 blob_it.add_after_then_move(bblob);
1563 } else {
1564 // This blob has multiple outlines from CJK repair.
1565 // Explode the blob back into individual outlines.
1566 for (;!ol_it.empty(); ol_it.forward()) {
1567 C_OUTLINE* outline = ol_it.extract();
1568 BLOBNBOX* blob = BLOBNBOX::RealBlob(outline);
1569 if (vertical_text)
1570 sizes.add(blob->bounding_box().width(), 1);
1571 else
1572 sizes.add(blob->bounding_box().height(), 1);
1573 blob_it.add_after_then_move(blob);
1574 }
1575 delete bblob->cblob();
1576 delete bblob;
1577 }
1578 }
1579 used_it.add_to_end(part);
1580 }
1581 if (text_type && blob_it.empty()) {
1582 delete block;
1583 delete to_block;
1584 return NULL;
1585 }
1586 to_block->line_size = sizes.median();
1587 if (vertical_text) {
1588 int block_width = block->bounding_box().width();
1589 if (block_width < line_spacing)
1590 line_spacing = block_width;
1591 to_block->line_spacing = static_cast<float>(line_spacing);
1592 to_block->max_blob_size = static_cast<float>(block_width + 1);
1593 } else {
1594 int block_height = block->bounding_box().height();
1595 if (block_height < line_spacing)
1596 line_spacing = block_height;
1597 to_block->line_spacing = static_cast<float>(line_spacing);
1598 to_block->max_blob_size = static_cast<float>(block_height + 1);
1599 }
1600 return to_block;
1601 }
1602
1603 // Constructs a block from the given list of partitions.
1604 // Arguments are as LineSpacingBlocks above.
1605 TO_BLOCK* ColPartition::MakeBlock(const ICOORD& bleft, const ICOORD& tright,
1606 ColPartition_LIST* block_parts,
1607 ColPartition_LIST* used_parts) {
1608 if (block_parts->empty())
1609 return NULL; // Nothing to do.
1610 ColPartition_IT it(block_parts);
1611 ColPartition* part = it.data();
1612 PolyBlockType type = part->type();
1613 if (type == PT_VERTICAL_TEXT)
1614 return MakeVerticalTextBlock(bleft, tright, block_parts, used_parts);
1615 // LineSpacingBlocks has handed us a collection of evenly spaced lines and
1616 // put the average spacing in each partition, so we can just take the
1617 // linespacing from the first partition.
1618 int line_spacing = part->bottom_spacing();
1619 if (line_spacing < part->median_size())
1620 line_spacing = part->bounding_box().height();
1621 ICOORDELT_LIST vertices;
1622 ICOORDELT_IT vert_it(&vertices);
1623 ICOORD start, end;
1624 int min_x = MAX_INT32;
1625 int max_x = -MAX_INT32;
1626 int min_y = MAX_INT32;
1627 int max_y = -MAX_INT32;
1628 int iteration = 0;
1629 do {
1630 if (iteration == 0)
1631 ColPartition::LeftEdgeRun(&it, &start, &end);
1632 else
1633 ColPartition::RightEdgeRun(&it, &start, &end);
1634 ClipCoord(bleft, tright, &start);
1635 ClipCoord(bleft, tright, &end);
1636 vert_it.add_after_then_move(new ICOORDELT(start));
1637 vert_it.add_after_then_move(new ICOORDELT(end));
1638 UpdateRange(start.x(), &min_x, &max_x);
1639 UpdateRange(end.x(), &min_x, &max_x);
1640 UpdateRange(start.y(), &min_y, &max_y);
1641 UpdateRange(end.y(), &min_y, &max_y);
1642 if ((iteration == 0 && it.at_first()) ||
1643 (iteration == 1 && it.at_last())) {
1644 ++iteration;
1645 it.move_to_last();
1646 }
1647 } while (iteration < 2);
1648 if (textord_debug_tabfind)
1649 tprintf("Making block at (%d,%d)->(%d,%d)\n",
1650 min_x, min_y, max_x, max_y);
1651 BLOCK* block = new BLOCK("", true, 0, 0, min_x, min_y, max_x, max_y);
1652 block->set_poly_block(new POLY_BLOCK(&vertices, type));
1653 return MoveBlobsToBlock(false, line_spacing, block, block_parts, used_parts);
1654 }
1655
1656 // Constructs a block from the given list of vertical text partitions.
1657 // Currently only creates rectangular blocks.
1658 TO_BLOCK* ColPartition::MakeVerticalTextBlock(const ICOORD& bleft,
1659 const ICOORD& tright,
1660 ColPartition_LIST* block_parts,
1661 ColPartition_LIST* used_parts) {
1662 if (block_parts->empty())
1663 return NULL; // Nothing to do.
1664 ColPartition_IT it(block_parts);
1665 ColPartition* part = it.data();
1666 TBOX block_box = part->bounding_box();
1667 int line_spacing = block_box.width();
1668 PolyBlockType type = it.data()->type();
1669 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1670 block_box += it.data()->bounding_box();
1671 }
1672 if (textord_debug_tabfind) {
1673 tprintf("Making block at:");
1674 block_box.print();
1675 }
1676 BLOCK* block = new BLOCK("", true, 0, 0, block_box.left(), block_box.bottom(),
1677 block_box.right(), block_box.top());
1678 block->set_poly_block(new POLY_BLOCK(block_box, type));
1679 return MoveBlobsToBlock(true, line_spacing, block, block_parts, used_parts);
1680 }
1681
1682 // Returns a copy of everything except the list of boxes. The resulting
1683 // ColPartition is only suitable for keeping in a column candidate list.
1684 ColPartition* ColPartition::ShallowCopy() const {
1685 ColPartition* part = new ColPartition(blob_type_, vertical_);
1686 part->left_margin_ = left_margin_;
1687 part->right_margin_ = right_margin_;
1688 part->bounding_box_ = bounding_box_;
1689 memcpy(part->special_blobs_densities_, special_blobs_densities_,
1690 sizeof(special_blobs_densities_));
1691 part->median_bottom_ = median_bottom_;
1692 part->median_top_ = median_top_;
1693 part->median_size_ = median_size_;
1694 part->median_left_ = median_left_;
1695 part->median_right_ = median_right_;
1696 part->median_width_ = median_width_;
1697 part->good_width_ = good_width_;
1698 part->good_column_ = good_column_;
1699 part->left_key_tab_ = left_key_tab_;
1700 part->right_key_tab_ = right_key_tab_;
1701 part->type_ = type_;
1702 part->flow_ = flow_;
1703 part->left_key_ = left_key_;
1704 part->right_key_ = right_key_;
1705 part->first_column_ = first_column_;
1706 part->last_column_ = last_column_;
1707 part->owns_blobs_ = false;
1708 return part;
1709 }
1710
1711 ColPartition* ColPartition::CopyButDontOwnBlobs() {
1712 ColPartition* copy = ShallowCopy();
1713 copy->set_owns_blobs(false);
1714 BLOBNBOX_C_IT inserter(copy->boxes());
1715 BLOBNBOX_C_IT traverser(boxes());
1716 for (traverser.mark_cycle_pt(); !traverser.cycled_list(); traverser.forward())
1717 inserter.add_after_then_move(traverser.data());
1718 return copy;
1719 }
1720
1721 #ifndef GRAPHICS_DISABLED
1722 // Provides a color for BBGrid to draw the rectangle.
1723 // Must be kept in sync with PolyBlockType.
1724 ScrollView::Color ColPartition::BoxColor() const {
1725 if (type_ == PT_UNKNOWN)
1726 return BLOBNBOX::TextlineColor(blob_type_, flow_);
1727 return POLY_BLOCK::ColorForPolyBlockType(type_);
1728 }
1729 #endif // GRAPHICS_DISABLED
1730
1731 // Keep in sync with BlobRegionType.
1732 static char kBlobTypes[BRT_COUNT + 1] = "NHSRIUVT";
1733
1734 // Prints debug information on this.
1735 void ColPartition::Print() const {
1736 int y = MidY();
1737 tprintf("ColPart:%c(M%d-%c%d-B%d/%d,%d/%d)->(%dB-%d%c-%dM/%d,%d/%d)"
1738 " w-ok=%d, v-ok=%d, type=%d%c%d, fc=%d, lc=%d, boxes=%d"
1739 " ts=%d bs=%d ls=%d rs=%d\n",
1740 boxes_.empty() ? 'E' : ' ',
1741 left_margin_, left_key_tab_ ? 'T' : 'B', LeftAtY(y),
1742 bounding_box_.left(), median_left_,
1743 bounding_box_.bottom(), median_bottom_,
1744 bounding_box_.right(), RightAtY(y), right_key_tab_ ? 'T' : 'B',
1745 right_margin_, median_right_, bounding_box_.top(), median_top_,
1746 good_width_, good_column_, type_,
1747 kBlobTypes[blob_type_], flow_,
1748 first_column_, last_column_, boxes_.length(),
1749 space_above_, space_below_, space_to_left_, space_to_right_);
1750 }
1751
1752 // Prints debug information on the colors.
1753 void ColPartition::PrintColors() {
1754 tprintf("Colors:(%d, %d, %d)%d -> (%d, %d, %d)\n",
1755 color1_[COLOR_RED], color1_[COLOR_GREEN], color1_[COLOR_BLUE],
1756 color1_[L_ALPHA_CHANNEL],
1757 color2_[COLOR_RED], color2_[COLOR_GREEN], color2_[COLOR_BLUE]);
1758 }
1759
1760 // Sets the types of all partitions in the run to be the max of the types.
1761 void ColPartition::SmoothPartnerRun(int working_set_count) {
1762 STATS left_stats(0, working_set_count);
1763 STATS right_stats(0, working_set_count);
1764 PolyBlockType max_type = type_;
1765 ColPartition* partner;
1766 for (partner = SingletonPartner(false); partner != NULL;
1767 partner = partner->SingletonPartner(false)) {
1768 if (partner->type_ > max_type)
1769 max_type = partner->type_;
1770 if (column_set_ == partner->column_set_) {
1771 left_stats.add(partner->first_column_, 1);
1772 right_stats.add(partner->last_column_, 1);
1773 }
1774 }
1775 type_ = max_type;
1776 // TODO(rays) Either establish that it isn't necessary to set the columns,
1777 // or find a way to do it that does not cause an assert failure in
1778 // AddToWorkingSet.
1779 #if 0
1780 first_column_ = left_stats.mode();
1781 last_column_ = right_stats.mode();
1782 if (last_column_ < first_column_)
1783 last_column_ = first_column_;
1784 #endif
1785
1786 for (partner = SingletonPartner(false); partner != NULL;
1787 partner = partner->SingletonPartner(false)) {
1788 partner->type_ = max_type;
1789 #if 0 // See TODO above
1790 if (column_set_ == partner->column_set_) {
1791 partner->first_column_ = first_column_;
1792 partner->last_column_ = last_column_;
1793 }
1794 #endif
1795 }
1796 }
1797
1798 // ======= Scenario common to all Refine*Partners* functions =======
1799 // ColPartitions are aiming to represent textlines, or horizontal slices
1800 // of images, and we are trying to form bi-directional (upper/lower) chains
1801 // of UNIQUE partner ColPartitions that can be made into blocks.
1802 // The ColPartitions have previously been typed (see SetPartitionType)
1803 // according to a combination of the content type and
1804 // how they lie on the columns. We want to chain text into
1805 // groups of a single type, but image ColPartitions may have been typed
1806 // differently in different parts of the image, due to being non-rectangular.
1807 //
1808 // We previously ran a search for upper and lower partners, but there may
1809 // be more than one, and they may be of mixed types, so now we wish to
1810 // refine the partners down to at most one.
1811 // A heading may have multiple partners:
1812 // ===============================
1813 // ======== ========== =========
1814 // ======== ========== =========
1815 // but it should be a different type.
1816 // A regular flowing text line may have multiple partners:
1817 // ================== ===================
1818 // ======= ================= ===========
1819 // This could be the start of a pull-out, or it might all be in a single
1820 // column and might be caused by tightly spaced text, bold words, bullets,
1821 // funny punctuation etc, all of which can cause textlines to be split into
1822 // multiple ColPartitions. Pullouts and figure captions should now be different
1823 // types so we can more aggressively merge groups of partners that all sit
1824 // in a single column.
1825 //
1826 // Cleans up the partners of the given type so that there is at most
1827 // one partner. This makes block creation simpler.
1828 // If get_desperate is true, goes to more desperate merge methods
1829 // to merge flowing text before breaking partnerships.
1830 void ColPartition::RefinePartners(PolyBlockType type, bool get_desperate,
1831 ColPartitionGrid* grid) {
1832 if (TypesSimilar(type_, type)) {
1833 RefinePartnersInternal(true, get_desperate, grid);
1834 RefinePartnersInternal(false, get_desperate, grid);
1835 } else if (type == PT_COUNT) {
1836 // This is the final pass. Make sure only the correctly typed
1837 // partners surivive, however many there are.
1838 RefinePartnersByType(true, &upper_partners_);
1839 RefinePartnersByType(false, &lower_partners_);
1840 // It is possible for a merge to have given a partition multiple
1841 // partners again, so the last resort is to use overlap which is
1842 // guaranteed to leave at most one partner left.
1843 if (!upper_partners_.empty() && !upper_partners_.singleton())
1844 RefinePartnersByOverlap(true, &upper_partners_);
1845 if (!lower_partners_.empty() && !lower_partners_.singleton())
1846 RefinePartnersByOverlap(false, &lower_partners_);
1847 }
1848 }
1849
1851
1852 // Cleans up the partners above if upper is true, else below.
1853 // If get_desperate is true, goes to more desperate merge methods
1854 // to merge flowing text before breaking partnerships.
1855 void ColPartition::RefinePartnersInternal(bool upper, bool get_desperate,
1856 ColPartitionGrid* grid) {
1857 ColPartition_CLIST* partners = upper ? &upper_partners_ : &lower_partners_;
1858 if (!partners->empty() && !partners->singleton()) {
1859 RefinePartnersByType(upper, partners);
1860 if (!partners->empty() && !partners->singleton()) {
1861 // Check for transitive partnerships and break the cycle.
1862 RefinePartnerShortcuts(upper, partners);
1863 if (!partners->empty() && !partners->singleton()) {
1864 // Types didn't fix it. Flowing text keeps the one with the longest
1865 // sequence of singleton matching partners. All others max overlap.
1866 if (TypesSimilar(type_, PT_FLOWING_TEXT) && get_desperate) {
1867 RefineTextPartnersByMerge(upper, false, partners, grid);
1868 if (!partners->empty() && !partners->singleton())
1869 RefineTextPartnersByMerge(upper, true, partners, grid);
1870 }
1871 // The last resort is to use overlap.
1872 if (!partners->empty() && !partners->singleton())
1873 RefinePartnersByOverlap(upper, partners);
1874 }
1875 }
1876 }
1877 }
1878
1879 // Cleans up the partners above if upper is true, else below.
1880 // Restricts the partners to only desirable types. For text and BRT_HLINE this
1881 // means the same type_ , and for image types it means any image type.
1882 void ColPartition::RefinePartnersByType(bool upper,
1883 ColPartition_CLIST* partners) {
1884 bool debug = TabFind::WithinTestRegion(2, bounding_box_.left(),
1885 bounding_box_.bottom());
1886 if (debug) {
1887 tprintf("Refining %d %s partners by type for:\n",
1888 partners->length(), upper ? "Upper" : "Lower");
1889 Print();
1890 }
1891 ColPartition_C_IT it(partners);
1892 // Purify text by type.
1893 if (!IsImageType()) {
1894 // Keep only partners matching type_.
1895 // Exception: PT_VERTICAL_TEXT is allowed to stay with the other
1896 // text types if it is the only partner.
1897 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1898 ColPartition* partner = it.data();
1899 if (!TypesSimilar(type_, partner->type_)) {
1900 if (debug) {
1901 tprintf("Removing partner:");
1902 partner->Print();
1903 }
1904 partner->RemovePartner(!upper, this);
1905 it.extract();
1906 } else if (debug) {
1907 tprintf("Keeping partner:");
1908 partner->Print();
1909 }
1910 }
1911 } else {
1912 // Only polyimages are allowed to have partners of any kind!
1913 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1914 ColPartition* partner = it.data();
1915 if (partner->blob_type() != BRT_POLYIMAGE ||
1916 blob_type() != BRT_POLYIMAGE) {
1917 if (debug) {
1918 tprintf("Removing partner:");
1919 partner->Print();
1920 }
1921 partner->RemovePartner(!upper, this);
1922 it.extract();
1923 } else if (debug) {
1924 tprintf("Keeping partner:");
1925 partner->Print();
1926 }
1927 }
1928 }
1929 }
1930
1931 // Cleans up the partners above if upper is true, else below.
1932 // Remove transitive partnerships: this<->a, and a<->b and this<->b.
1933 // Gets rid of this<->b, leaving a clean chain.
1934 // Also if we have this<->a and a<->this, then gets rid of this<->a, as
1935 // this has multiple partners.
1936 void ColPartition::RefinePartnerShortcuts(bool upper,
1937 ColPartition_CLIST* partners) {
1938 bool done_any = false;
1939 do {
1940 done_any = false;
1941 ColPartition_C_IT it(partners);
1942 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1943 ColPartition* a = it.data();
1944 // Check for a match between all of a's partners (it1/b1) and all
1945 // of this's partners (it2/b2).
1946 ColPartition_C_IT it1(upper ? &a->upper_partners_ : &a->lower_partners_);
1947 for (it1.mark_cycle_pt(); !it1.cycled_list(); it1.forward()) {
1948 ColPartition* b1 = it1.data();
1949 if (b1 == this) {
1950 done_any = true;
1951 it.extract();
1952 a->RemovePartner(!upper, this);
1953 break;
1954 }
1955 ColPartition_C_IT it2(partners);
1956 for (it2.mark_cycle_pt(); !it2.cycled_list(); it2.forward()) {
1957 ColPartition* b2 = it2.data();
1958 if (b1 == b2) {
1959 // Jackpot! b2 should not be a partner of this.
1960 it2.extract();
1961 b2->RemovePartner(!upper, this);
1962 done_any = true;
1963 // That potentially invalidated all the iterators, so break out
1964 // and start again.
1965 break;
1966 }
1967 }
1968 if (done_any)
1969 break;
1970 }
1971 if (done_any)
1972 break;
1973 }
1974 } while (done_any && !partners->empty() && !partners->singleton());
1975 }
1976
1977 // Cleans up the partners above if upper is true, else below.
1978 // If multiple text partners can be merged, (with each other, NOT with this),
1979 // then do so.
1980 // If desperate is true, then an increase in overlap with the merge is
1981 // allowed. If the overlap increases, then the desperately_merged_ flag
1982 // is set, indicating that the textlines probably need to be regenerated
1983 // by aggressive line fitting/splitting, as there are probably vertically
1984 // joined blobs that cross textlines.
1985 void ColPartition::RefineTextPartnersByMerge(bool upper, bool desperate,
1986 ColPartition_CLIST* partners,
1987 ColPartitionGrid* grid) {
1988 bool debug = TabFind::WithinTestRegion(2, bounding_box_.left(),
1989 bounding_box_.bottom());
1990 if (debug) {
1991 tprintf("Refining %d %s partners by merge for:\n",
1992 partners->length(), upper ? "Upper" : "Lower");
1993 Print();
1994 }
1995 while (!partners->empty() && !partners->singleton()) {
1996 // Absorb will mess up the iterators, so we have to merge one partition
1997 // at a time and rebuild the iterators each time.
1998 ColPartition_C_IT it(partners);
1999 ColPartition* part = it.data();
2000 // Gather a list of merge candidates, from the list of partners, that
2001 // are all in the same single column. See general scenario comment above.
2002 ColPartition_CLIST candidates;
2003 ColPartition_C_IT cand_it(&candidates);
2004 for (it.forward(); !it.at_first(); it.forward()) {
2005 ColPartition* candidate = it.data();
2006 if (part->first_column_ == candidate->last_column_ &&
2007 part->last_column_ == candidate->first_column_)
2008 cand_it.add_after_then_move(it.data());
2009 }
2010 int overlap_increase;
2011 ColPartition* candidate = grid->BestMergeCandidate(part, &candidates, debug,
2012 NULL, &overlap_increase);
2013 if (candidate != NULL && (overlap_increase <= 0 || desperate)) {
2014 if (debug) {
2015 tprintf("Merging:hoverlap=%d, voverlap=%d, OLI=%d\n",
2016 part->HCoreOverlap(*candidate), part->VCoreOverlap(*candidate),
2017 overlap_increase);
2018 }
2019 // Remove before merge and re-insert to keep the integrity of the grid.
2020 grid->RemoveBBox(candidate);
2021 grid->RemoveBBox(part);
2022 part->Absorb(candidate, NULL);
2023 // We modified the box of part, so re-insert it into the grid.
2024 grid->InsertBBox(true, true, part);
2025 if (overlap_increase > 0)
2026 part->desperately_merged_ = true;
2027 } else {
2028 break; // Can't merge.
2029 }
2030 }
2031 }
2032
2033 // Cleans up the partners above if upper is true, else below.
2034 // Keep the partner with the biggest overlap.
2035 void ColPartition::RefinePartnersByOverlap(bool upper,
2036 ColPartition_CLIST* partners) {
2037 bool debug = TabFind::WithinTestRegion(2, bounding_box_.left(),
2038 bounding_box_.bottom());
2039 if (debug) {
2040 tprintf("Refining %d %s partners by overlap for:\n",
2041 partners->length(), upper ? "Upper" : "Lower");
2042 Print();
2043 }
2044 ColPartition_C_IT it(partners);
2045 ColPartition* best_partner = it.data();
2046 // Find the partner with the best overlap.
2047 int best_overlap = 0;
2048 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
2049 ColPartition* partner = it.data();
2050 int overlap = MIN(bounding_box_.right(), partner->bounding_box_.right())
2051 - MAX(bounding_box_.left(), partner->bounding_box_.left());
2052 if (overlap > best_overlap) {
2053 best_overlap = overlap;
2054 best_partner = partner;
2055 }
2056 }
2057 // Keep only the best partner.
2058 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
2059 ColPartition* partner = it.data();
2060 if (partner != best_partner) {
2061 if (debug) {
2062 tprintf("Removing partner:");
2063 partner->Print();
2064 }
2065 partner->RemovePartner(!upper, this);
2066 it.extract();
2067 }
2068 }
2069 }
2070
2071 // Return true if bbox belongs better in this than other.
2072 bool ColPartition::ThisPartitionBetter(BLOBNBOX* bbox,
2073 const ColPartition& other) {
2074 TBOX box = bbox->bounding_box();
2075 // Margins take priority.
2076 int left = box.left();
2077 int right = box.right();
2078 if (left < left_margin_ || right > right_margin_)
2079 return false;
2080 if (left < other.left_margin_ || right > other.right_margin_)
2081 return true;
2082 int top = box.top();
2083 int bottom = box.bottom();
2084 int this_overlap = MIN(top, median_top_) - MAX(bottom, median_bottom_);
2085 int other_overlap = MIN(top, other.median_top_) -
2086 MAX(bottom, other.median_bottom_);
2087 int this_miss = median_top_ - median_bottom_ - this_overlap;
2088 int other_miss = other.median_top_ - other.median_bottom_ - other_overlap;
2089 if (TabFind::WithinTestRegion(3, box.left(), box.bottom())) {
2090 tprintf("Unique on (%d,%d)->(%d,%d) overlap %d/%d, miss %d/%d, mt=%d/%d\n",
2091 box.left(), box.bottom(), box.right(), box.top(),
2092 this_overlap, other_overlap, this_miss, other_miss,
2093 median_top_, other.median_top_);
2094 }
2095 if (this_miss < other_miss)
2096 return true;
2097 if (this_miss > other_miss)
2098 return false;
2099 if (this_overlap > other_overlap)
2100 return true;
2101 if (this_overlap < other_overlap)
2102 return false;
2103 return median_top_ >= other.median_top_;
2104 }
2105
2106 // Returns the median line-spacing between the current position and the end
2107 // of the list.
2108 // The iterator is passed by value so the iteration does not modify the
2109 // caller's iterator.
2110 static int MedianSpacing(int page_height, ColPartition_IT it) {
2111 STATS stats(0, page_height);
2112 while (!it.cycled_list()) {
2113 ColPartition* part = it.data();
2114 it.forward();
2115 stats.add(part->bottom_spacing(), 1);
2116 stats.add(part->top_spacing(), 1);
2117 }
2118 return static_cast<int>(stats.median() + 0.5);
2119 }
2120
2121 // Returns true if this column partition is in the same column as
2122 // part. This function will only work after the SetPartitionType function
2123 // has been called on both column partitions. This is useful for
2124 // doing a SideSearch when you want things in the same page column.
2125 //
2126 // Currently called by the table detection code to identify if potential table
2127 // partitions exist in the same column.
2128 bool ColPartition::IsInSameColumnAs(const ColPartition& part) const {
2129 // Overlap does not occur when last < part.first or first > part.last.
2130 // In other words, one is completely to the side of the other.
2131 // This is just DeMorgan's law applied to that so the function returns true.
2132 return (last_column_ >= part.first_column_) &&
2133 (first_column_ <= part.last_column_);
2134 }
2135
2136 // Smoothes the spacings in the list into groups of equal linespacing.
2137 // resolution is the resolution of the original image, used as a basis
2138 // for thresholds in change of spacing. page_height is in pixels.
2139 void ColPartition::SmoothSpacings(int resolution, int page_height,
2140 ColPartition_LIST* parts) {
2141 // The task would be trivial if we didn't have to allow for blips -
2142 // occasional offsets in spacing caused by anomolous text, such as all
2143 // caps, groups of descenders, joined words, Arabic etc.
2144 // The neighbourhood stores a consecutive group of partitions so that
2145 // blips can be detected correctly, yet conservatively enough to not
2146 // mistake genuine spacing changes for blips. See example below.
2147 ColPartition* neighbourhood[PN_COUNT];
2148 ColPartition_IT it(parts);
2149 it.mark_cycle_pt();
2150 // Although we know nothing about the spacings is this list, the median is
2151 // used as an approximation to allow blips.
2152 // If parts of this block aren't spaced to the median, then we can't
2153 // accept blips in those parts, but we'll recalculate it each time we
2154 // split the block, so the median becomes more likely to match all the text.
2155 int median_space = MedianSpacing(page_height, it);
2156 ColPartition_IT start_it(it);
2157 ColPartition_IT end_it(it);
2158 for (int i = 0; i < PN_COUNT; ++i) {
2159 if (i < PN_UPPER || it.cycled_list()) {
2160 neighbourhood[i] = NULL;
2161 } else {
2162 if (i == PN_LOWER)
2163 end_it = it;
2164 neighbourhood[i] = it.data();
2165 it.forward();
2166 }
2167 }
2168 while (neighbourhood[PN_UPPER] != NULL) {
2169 // Test for end of a group. Normally SpacingsEqual is true within a group,
2170 // but in the case of a blip, it will be false. Here is an example:
2171 // Line enum Spacing below (spacing between tops of lines)
2172 // 1 ABOVE2 20
2173 // 2 ABOVE1 20
2174 // 3 UPPER 15
2175 // 4 LOWER 25
2176 // 5 BELOW1 20
2177 // 6 BELOW2 20
2178 // Line 4 is all in caps (regular caps), so the spacing between line 3
2179 // and line 4 (looking at the tops) is smaller than normal, and the
2180 // spacing between line 4 and line 5 is larger than normal, but the
2181 // two of them add to twice the normal spacing.
2182 // The following if has to accept unequal spacings 3 times to pass the
2183 // blip (20/15, 15/25 and 25/20)
2184 // When the blip is in the middle, OKSpacingBlip tests that one of
2185 // ABOVE1 and BELOW1 matches the median.
2186 // The first time, everything is shifted down 1, so we present
2187 // OKSpacingBlip with neighbourhood+1 and check that PN_UPPER is median.
2188 // The last time, everything is shifted up 1, so we present OKSpacingBlip
2189 // with neighbourhood-1 and check that PN_LOWER matches the median.
2190 if (neighbourhood[PN_LOWER] == NULL ||
2191 (!neighbourhood[PN_UPPER]->SpacingsEqual(*neighbourhood[PN_LOWER],
2192 resolution) &&
2193 !OKSpacingBlip(resolution, median_space, neighbourhood) &&
2194 (!OKSpacingBlip(resolution, median_space, neighbourhood - 1) ||
2195 !neighbourhood[PN_LOWER]->SpacingEqual(median_space, resolution)) &&
2196 (!OKSpacingBlip(resolution, median_space, neighbourhood + 1) ||
2197 !neighbourhood[PN_UPPER]->SpacingEqual(median_space, resolution)))) {
2198 // The group has ended. PN_UPPER is the last member.
2199 // Compute the mean spacing over the group.
2200 ColPartition_IT sum_it(start_it);
2201 ColPartition* last_part = neighbourhood[PN_UPPER];
2202 double total_bottom = 0.0;
2203 double total_top = 0.0;
2204 int total_count = 0;
2205 ColPartition* upper = sum_it.data();
2206 // We do not process last_part, as its spacing is different.
2207 while (upper != last_part) {
2208 total_bottom += upper->bottom_spacing();
2209 total_top += upper->top_spacing();
2210 ++total_count;
2211 sum_it.forward();
2212 upper = sum_it.data();
2213 }
2214 if (total_count > 0) {
2215 // There were at least 2 lines, so set them all to the mean.
2216 int top_spacing = static_cast<int>(total_top / total_count + 0.5);
2217 int bottom_spacing = static_cast<int>(total_bottom / total_count + 0.5);
2218 if (textord_debug_tabfind) {
2219 tprintf("Spacing run ended. Cause:");
2220 if (neighbourhood[PN_LOWER] == NULL) {
2221 tprintf("No more lines\n");
2222 } else {
2223 tprintf("Spacing change. Spacings:\n");
2224 for (int i = 0; i < PN_COUNT; ++i) {
2225 if (neighbourhood[i] == NULL) {
2226 tprintf("NULL");
2227 if (i > 0 && neighbourhood[i - 1] != NULL) {
2228 if (neighbourhood[i - 1]->SingletonPartner(false) != NULL) {
2229 tprintf(" Lower partner:");
2230 neighbourhood[i - 1]->SingletonPartner(false)->Print();
2231 } else {
2232 tprintf(" NULL lower partner:\n");
2233 }
2234 } else {
2235 tprintf("\n");
2236 }
2237 } else {
2238 tprintf("Top = %d, bottom = %d\n",
2239 neighbourhood[i]->top_spacing(),
2240 neighbourhood[i]->bottom_spacing());
2241 }
2242 }
2243 }
2244 tprintf("Mean spacing = %d/%d\n", top_spacing, bottom_spacing);
2245 }
2246 sum_it = start_it;
2247 upper = sum_it.data();
2248 while (upper != last_part) {
2249 upper->set_top_spacing(top_spacing);
2250 upper->set_bottom_spacing(bottom_spacing);
2251 if (textord_debug_tabfind) {
2252 tprintf("Setting mean on:");
2253 upper->Print();
2254 }
2255 sum_it.forward();
2256 upper = sum_it.data();
2257 }
2258 }
2259 // PN_LOWER starts the next group and end_it is the next start_it.
2260 start_it = end_it;
2261 // Recalculate the median spacing to maximize the chances of detecting
2262 // spacing blips.
2263 median_space = MedianSpacing(page_height, end_it);
2264 }
2265 // Shuffle pointers.
2266 for (int j = 1; j < PN_COUNT; ++j) {
2267 neighbourhood[j - 1] = neighbourhood[j];
2268 }
2269 if (it.cycled_list()) {
2270 neighbourhood[PN_COUNT - 1] = NULL;
2271 } else {
2272 neighbourhood[PN_COUNT - 1] = it.data();
2273 it.forward();
2274 }
2275 end_it.forward();
2276 }
2277 }
2278
2279 // Returns true if the parts array of pointers to partitions matches the
2280 // condition for a spacing blip. See SmoothSpacings for what this means
2281 // and how it is used.
2282 bool ColPartition::OKSpacingBlip(int resolution, int median_spacing,
2283 ColPartition** parts) {
2284 if (parts[PN_UPPER] == NULL || parts[PN_LOWER] == NULL)
2285 return false;
2286 // The blip is OK if upper and lower sum to an OK value and at least
2287 // one of above1 and below1 is equal to the median.
2288 return parts[PN_UPPER]->SummedSpacingOK(*parts[PN_LOWER],
2289 median_spacing, resolution) &&
2290 ((parts[PN_ABOVE1] != NULL &&
2291 parts[PN_ABOVE1]->SpacingEqual(median_spacing, resolution)) ||
2292 (parts[PN_BELOW1] != NULL &&
2293 parts[PN_BELOW1]->SpacingEqual(median_spacing, resolution)));
2294 }
2295
2296 // Returns true if both the top and bottom spacings of this match the given
2297 // spacing to within suitable margins dictated by the image resolution.
2298 bool ColPartition::SpacingEqual(int spacing, int resolution) const {
2299 int bottom_error = BottomSpacingMargin(resolution);
2300 int top_error = TopSpacingMargin(resolution);
2301 return NearlyEqual(bottom_spacing_, spacing, bottom_error) &&
2302 NearlyEqual(top_spacing_, spacing, top_error);
2303 }
2304
2305 // Returns true if both the top and bottom spacings of this and other
2306 // match to within suitable margins dictated by the image resolution.
2307 bool ColPartition::SpacingsEqual(const ColPartition& other,
2308 int resolution) const {
2309 int bottom_error = MAX(BottomSpacingMargin(resolution),
2310 other.BottomSpacingMargin(resolution));
2311 int top_error = MAX(TopSpacingMargin(resolution),
2312 other.TopSpacingMargin(resolution));
2313 return NearlyEqual(bottom_spacing_, other.bottom_spacing_, bottom_error) &&
2314 (NearlyEqual(top_spacing_, other.top_spacing_, top_error) ||
2315 NearlyEqual(top_spacing_ + other.top_spacing_, bottom_spacing_ * 2,
2316 bottom_error));
2317 }
2318
2319 // Returns true if the sum spacing of this and other match the given
2320 // spacing (or twice the given spacing) to within a suitable margin dictated
2321 // by the image resolution.
2322 bool ColPartition::SummedSpacingOK(const ColPartition& other,
2323 int spacing, int resolution) const {
2324 int bottom_error = MAX(BottomSpacingMargin(resolution),
2325 other.BottomSpacingMargin(resolution));
2326 int top_error = MAX(TopSpacingMargin(resolution),
2327 other.TopSpacingMargin(resolution));
2328 int bottom_total = bottom_spacing_ + other.bottom_spacing_;
2329 int top_total = top_spacing_ + other.top_spacing_;
2330 return (NearlyEqual(spacing, bottom_total, bottom_error) &&
2331 NearlyEqual(spacing, top_total, top_error)) ||
2332 (NearlyEqual(spacing * 2, bottom_total, bottom_error) &&
2333 NearlyEqual(spacing * 2, top_total, top_error));
2334 }
2335
2336 // Returns a suitable spacing margin that can be applied to bottoms of
2337 // text lines, based on the resolution and the stored side_step_.
2338 int ColPartition::BottomSpacingMargin(int resolution) const {
2339 return static_cast<int>(kMaxSpacingDrift * resolution + 0.5) + side_step_;
2340 }
2341
2342 // Returns a suitable spacing margin that can be applied to tops of
2343 // text lines, based on the resolution and the stored side_step_.
2344 int ColPartition::TopSpacingMargin(int resolution) const {
2345 return static_cast<int>(kMaxTopSpacingFraction * median_size_ + 0.5) +
2346 BottomSpacingMargin(resolution);
2347 }
2348
2349 // Returns true if the median text sizes of this and other agree to within
2350 // a reasonable multiplicative factor.
2351 bool ColPartition::SizesSimilar(const ColPartition& other) const {
2352 return median_size_ <= other.median_size_ * kMaxSizeRatio &&
2353 other.median_size_ <= median_size_ * kMaxSizeRatio;
2354 }
2355
2356 // Helper updates margin_left and margin_right, being the bounds of the left
2357 // margin of part of a block. Returns false and does not update the bounds if
2358 // this partition has a disjoint margin with the established margin.
2359 static bool UpdateLeftMargin(const ColPartition& part,
2360 int* margin_left, int* margin_right) {
2361 const TBOX& part_box = part.bounding_box();
2362 int top = part_box.top();
2363 int bottom = part_box.bottom();
2364 int tl_key = part.SortKey(part.left_margin(), top);
2365 int tr_key = part.SortKey(part_box.left(), top);
2366 int bl_key = part.SortKey(part.left_margin(), bottom);
2367 int br_key = part.SortKey(part_box.left(), bottom);
2368 int left_key = MAX(tl_key, bl_key);
2369 int right_key = MIN(tr_key, br_key);
2370 if (left_key <= *margin_right && right_key >= *margin_left) {
2371 // This part is good - let's keep it.
2372 *margin_right = MIN(*margin_right, right_key);
2373 *margin_left = MAX(*margin_left, left_key);
2374 return true;
2375 }
2376 return false;
2377 }
2378
2379 // Computes and returns in start, end a line segment formed from a
2380 // forwards-iterated group of left edges of partitions that satisfy the
2381 // condition that the intersection of the left margins is non-empty, ie the
2382 // rightmost left margin is to the left of the leftmost left bounding box edge.
2383 // On return the iterator is set to the start of the next run.
2384 void ColPartition::LeftEdgeRun(ColPartition_IT* part_it,
2385 ICOORD* start, ICOORD* end) {
2386 ColPartition* part = part_it->data();
2387 ColPartition* start_part = part;
2388 int start_y = part->bounding_box_.top();
2389 if (!part_it->at_first()) {
2390 int prev_bottom = part_it->data_relative(-1)->bounding_box_.bottom();
2391 if (prev_bottom < start_y)
2392 start_y = prev_bottom;
2393 else if (prev_bottom > start_y)
2394 start_y = (start_y + prev_bottom) / 2;
2395 }
2396 int end_y = part->bounding_box_.bottom();
2397 int margin_right = MAX_INT32;
2398 int margin_left = -MAX_INT32;
2399 UpdateLeftMargin(*part, &margin_left, &margin_right);
2400 do {
2401 part_it->forward();
2402 part = part_it->data();
2403 } while (!part_it->at_first() &&
2404 UpdateLeftMargin(*part, &margin_left, &margin_right));
2405 // The run ended. If we were pushed inwards, compute the next run and
2406 // extend it backwards into the run we just calculated to find the end of
2407 // this run that provides a tight box.
2408 int next_margin_right = MAX_INT32;
2409 int next_margin_left = -MAX_INT32;
2410 UpdateLeftMargin(*part, &next_margin_left, &next_margin_right);
2411 if (next_margin_left > margin_right) {
2412 ColPartition_IT next_it(*part_it);
2413 do {
2414 next_it.forward();
2415 part = next_it.data();
2416 } while (!next_it.at_first() &&
2417 UpdateLeftMargin(*part, &next_margin_left, &next_margin_right));
2418 // Now extend the next run backwards into the original run to get the
2419 // tightest fit.
2420 do {
2421 part_it->backward();
2422 part = part_it->data();
2423 } while (part != start_part &&
2424 UpdateLeftMargin(*part, &next_margin_left, &next_margin_right));
2425 part_it->forward();
2426 }
2427 // Now calculate the end_y.
2428 part = part_it->data_relative(-1);
2429 end_y = part->bounding_box_.bottom();
2430 if (!part_it->at_first() && part_it->data()->bounding_box_.top() < end_y)
2431 end_y = (end_y + part_it->data()->bounding_box_.top()) / 2;
2432 start->set_y(start_y);
2433 start->set_x(part->XAtY(margin_right, start_y));
2434 end->set_y(end_y);
2435 end->set_x(part->XAtY(margin_right, end_y));
2436 if (textord_debug_tabfind && !part_it->at_first())
2437 tprintf("Left run from y=%d to %d terminated with sum %d-%d, new %d-%d\n",
2438 start_y, end_y, part->XAtY(margin_left, end_y),
2439 end->x(), part->left_margin_, part->bounding_box_.left());
2440 }
2441
2442 // Helper updates margin_left and margin_right, being the bounds of the right
2443 // margin of part of a block. Returns false and does not update the bounds if
2444 // this partition has a disjoint margin with the established margin.
2445 static bool UpdateRightMargin(const ColPartition& part,
2446 int* margin_left, int* margin_right) {
2447 const TBOX& part_box = part.bounding_box();
2448 int top = part_box.top();
2449 int bottom = part_box.bottom();
2450 int tl_key = part.SortKey(part_box.right(), top);
2451 int tr_key = part.SortKey(part.right_margin(), top);
2452 int bl_key = part.SortKey(part_box.right(), bottom);
2453 int br_key = part.SortKey(part.right_margin(), bottom);
2454 int left_key = MAX(tl_key, bl_key);
2455 int right_key = MIN(tr_key, br_key);
2456 if (left_key <= *margin_right && right_key >= *margin_left) {
2457 // This part is good - let's keep it.
2458 *margin_right = MIN(*margin_right, right_key);
2459 *margin_left = MAX(*margin_left, left_key);
2460 return true;
2461 }
2462 return false;
2463 }
2464
2465 // Computes and returns in start, end a line segment formed from a
2466 // backwards-iterated group of right edges of partitions that satisfy the
2467 // condition that the intersection of the right margins is non-empty, ie the
2468 // leftmost right margin is to the right of the rightmost right bounding box
2469 // edge.
2470 // On return the iterator is set to the start of the next run.
2471 void ColPartition::RightEdgeRun(ColPartition_IT* part_it,
2472 ICOORD* start, ICOORD* end) {
2473 ColPartition* part = part_it->data();
2474 ColPartition* start_part = part;
2475 int start_y = part->bounding_box_.bottom();
2476 if (!part_it->at_last()) {
2477 int next_y = part_it->data_relative(1)->bounding_box_.top();
2478 if (next_y > start_y)
2479 start_y = next_y;
2480 else if (next_y < start_y)
2481 start_y = (start_y + next_y) / 2;
2482 }
2483 int end_y = part->bounding_box_.top();
2484 int margin_right = MAX_INT32;
2485 int margin_left = -MAX_INT32;
2486 UpdateRightMargin(*part, &margin_left, &margin_right);
2487 do {
2488 part_it->backward();
2489 part = part_it->data();
2490 } while (!part_it->at_last() &&
2491 UpdateRightMargin(*part, &margin_left, &margin_right));
2492 // The run ended. If we were pushed inwards, compute the next run and
2493 // extend it backwards to find the end of this run for a tight box.
2494 int next_margin_right = MAX_INT32;
2495 int next_margin_left = -MAX_INT32;
2496 UpdateRightMargin(*part, &next_margin_left, &next_margin_right);
2497 if (next_margin_right < margin_left) {
2498 ColPartition_IT next_it(*part_it);
2499 do {
2500 next_it.backward();
2501 part = next_it.data();
2502 } while (!next_it.at_last() &&
2503 UpdateRightMargin(*part, &next_margin_left,
2504 &next_margin_right));
2505 // Now extend the next run forwards into the original run to get the
2506 // tightest fit.
2507 do {
2508 part_it->forward();
2509 part = part_it->data();
2510 } while (part != start_part &&
2511 UpdateRightMargin(*part, &next_margin_left,
2512 &next_margin_right));
2513 part_it->backward();
2514 }
2515 // Now calculate the end_y.
2516 part = part_it->data_relative(1);
2517 end_y = part->bounding_box().top();
2518 if (!part_it->at_last() &&
2519 part_it->data()->bounding_box_.bottom() > end_y)
2520 end_y = (end_y + part_it->data()->bounding_box_.bottom()) / 2;
2521 start->set_y(start_y);
2522 start->set_x(part->XAtY(margin_left, start_y));
2523 end->set_y(end_y);
2524 end->set_x(part->XAtY(margin_left, end_y));
2525 if (textord_debug_tabfind && !part_it->at_last())
2526 tprintf("Right run from y=%d to %d terminated with sum %d-%d, new %d-%d\n",
2527 start_y, end_y, end->x(), part->XAtY(margin_right, end_y),
2528 part->bounding_box_.right(), part->right_margin_);
2529 }
2530
2531 } // namespace tesseract.