tesseract 4.1.1
Loading...
Searching...
No Matches
colpartitiongrid.cpp
Go to the documentation of this file.
1
2// File: colpartitiongrid.cpp
3// Description: Class collecting code that acts on a BBGrid of ColPartitions.
4// Author: Ray Smith
5//
6// (C) Copyright 2009, Google Inc.
7// Licensed under the Apache License, Version 2.0 (the "License");
8// you may not use this file except in compliance with the License.
9// You may obtain a copy of the License at
10// http://www.apache.org/licenses/LICENSE-2.0
11// Unless required by applicable law or agreed to in writing, software
12// distributed under the License is distributed on an "AS IS" BASIS,
13// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14// See the License for the specific language governing permissions and
15// limitations under the License.
16//
18
19#ifdef HAVE_CONFIG_H
20#include "config_auto.h"
21#endif
22
23#include "colpartitiongrid.h"
24#include "colpartitionset.h"
25#include "imagefind.h"
26
27#include <algorithm>
28
29namespace tesseract {
30
31// Max pad factor used to search the neighbourhood of a partition to smooth
32// partition types.
33const int kMaxPadFactor = 6;
34// Max multiple of size (min(height, width)) for the distance of the nearest
35// neighbour for the change of type to be used.
37// Maximum number of lines in a credible figure caption.
38const int kMaxCaptionLines = 7;
39// Min ratio between biggest and smallest gap to bound a caption.
40const double kMinCaptionGapRatio = 2.0;
41// Min ratio between biggest gap and mean line height to bound a caption.
42const double kMinCaptionGapHeightRatio = 0.5;
43// Min fraction of ColPartition height to be overlapping for margin purposes.
44const double kMarginOverlapFraction = 0.25;
45// Size ratio required to consider an unmerged overlapping partition to be big.
46const double kBigPartSizeRatio = 1.75;
47// Fraction of gridsize to allow arbitrary overlap between partitions.
49// Max vertical distance of neighbouring ColPartition as a multiple of
50// partition height for it to be a partner.
51// TODO(rays) fix the problem that causes a larger number to not work well.
52// The value needs to be larger as sparse text blocks in a page that gets
53// marked as single column will not find adjacent lines as partners, and
54// will merge horizontally distant, but aligned lines. See rep.4B3 p5.
55// The value needs to be small because double-spaced legal docs written
56// in a single column, but justified courier have widely spaced lines
57// that need to get merged before they partner-up with the lines above
58// and below. See legal.3B5 p13/17. Neither of these should depend on
59// the value of kMaxPartitionSpacing to be successful, and ColPartition
60// merging needs attention to fix this problem.
61const double kMaxPartitionSpacing = 1.75;
62// Margin by which text has to beat image or vice-versa to make a firm
63// decision in GridSmoothNeighbour.
65
67 const ICOORD& bleft, const ICOORD& tright)
68 : BBGrid<ColPartition, ColPartition_CLIST, ColPartition_C_IT>(gridsize,
69 bleft, tright) {
70}
71
72// Handles a click event in a display window.
75 ColPartition_CLIST, ColPartition_C_IT>::HandleClick(x, y);
76 // Run a radial search for partitions that overlap.
77 ColPartitionGridSearch radsearch(this);
78 radsearch.SetUniqueMode(true);
79 radsearch.StartRadSearch(x, y, 1);
80 ColPartition* neighbour;
81 FCOORD click(x, y);
82 while ((neighbour = radsearch.NextRadSearch()) != nullptr) {
83 const TBOX& nbox = neighbour->bounding_box();
84 if (nbox.contains(click)) {
85 tprintf("Block box:");
86 neighbour->bounding_box().print();
87 neighbour->Print();
88 }
89 }
90}
91
92// Merges ColPartitions in the grid that look like they belong in the same
93// textline.
94// For all partitions in the grid, calls the box_cb permanent callback
95// to compute the search box, searches the box, and if a candidate is found,
96// calls the confirm_cb to check any more rules. If the confirm_cb returns
97// true, then the partitions are merged.
98// Both callbacks are deleted before returning.
102 const ColPartition*>* confirm_cb) {
103 // Iterate the ColPartitions in the grid.
104 ColPartitionGridSearch gsearch(this);
105 gsearch.StartFullSearch();
106 ColPartition* part;
107 while ((part = gsearch.NextFullSearch()) != nullptr) {
108 if (MergePart(box_cb, confirm_cb, part))
109 gsearch.RepositionIterator();
110 }
111 delete box_cb;
112 delete confirm_cb;
113}
114
115// For the given partition, calls the box_cb permanent callback
116// to compute the search box, searches the box, and if a candidate is found,
117// calls the confirm_cb to check any more rules. If the confirm_cb returns
118// true, then the partitions are merged.
119// Returns true if the partition is consumed by one or more merges.
123 const ColPartition*>* confirm_cb,
124 ColPartition* part) {
125 if (part->IsUnMergeableType())
126 return false;
127 bool any_done = false;
128 // Repeatedly merge part while we find a best merge candidate that works.
129 bool merge_done = false;
130 do {
131 merge_done = false;
132 TBOX box = part->bounding_box();
133 bool debug = AlignedBlob::WithinTestRegion(2, box.left(), box.bottom());
134 if (debug) {
135 tprintf("Merge candidate:");
136 box.print();
137 }
138 // Set up a rectangle search bounded by the part.
139 if (!box_cb->Run(part, &box))
140 continue;
141 // Create a list of merge candidates.
142 ColPartition_CLIST merge_candidates;
143 FindMergeCandidates(part, box, debug, &merge_candidates);
144 // Find the best merge candidate based on minimal overlap increase.
145 int overlap_increase;
146 ColPartition* neighbour = BestMergeCandidate(part, &merge_candidates, debug,
147 confirm_cb,
148 &overlap_increase);
149 if (neighbour != nullptr && overlap_increase <= 0) {
150 if (debug) {
151 tprintf("Merging:hoverlap=%d, voverlap=%d, OLI=%d\n",
152 part->HCoreOverlap(*neighbour), part->VCoreOverlap(*neighbour),
153 overlap_increase);
154 }
155 // Looks like a good candidate so merge it.
156 RemoveBBox(neighbour);
157 // We will modify the box of part, so remove it from the grid, merge
158 // it and then re-insert it into the grid.
159 RemoveBBox(part);
160 part->Absorb(neighbour, nullptr);
161 InsertBBox(true, true, part);
162 merge_done = true;
163 any_done = true;
164 } else if (neighbour != nullptr) {
165 if (debug) {
166 tprintf("Overlapped when merged with increase %d: ", overlap_increase);
167 neighbour->bounding_box().print();
168 }
169 } else if (debug) {
170 tprintf("No candidate neighbour returned\n");
171 }
172 } while (merge_done);
173 return any_done;
174}
175
176// Returns true if the given part and merge candidate might believably
177// be part of a single text line according to the default rules.
178// In general we only want to merge partitions that look like they
179// are on the same text line, ie their median limits overlap, but we have
180// to make exceptions for diacritics and stray punctuation.
181static bool OKMergeCandidate(const ColPartition* part,
182 const ColPartition* candidate,
183 bool debug) {
184 const TBOX& part_box = part->bounding_box();
185 if (candidate == part)
186 return false; // Ignore itself.
187 if (!part->TypesMatch(*candidate) || candidate->IsUnMergeableType())
188 return false; // Don't mix inappropriate types.
189
190 const TBOX& c_box = candidate->bounding_box();
191 if (debug) {
192 tprintf("Examining merge candidate:");
193 c_box.print();
194 }
195 // Candidates must be within a reasonable distance.
196 if (candidate->IsVerticalType() || part->IsVerticalType()) {
197 int h_dist = -part->HCoreOverlap(*candidate);
198 if (h_dist >= std::max(part_box.width(), c_box.width()) / 2) {
199 if (debug)
200 tprintf("Too far away: h_dist = %d\n", h_dist);
201 return false;
202 }
203 } else {
204 // Coarse filter by vertical distance between partitions.
205 int v_dist = -part->VCoreOverlap(*candidate);
206 if (v_dist >= std::max(part_box.height(), c_box.height()) / 2) {
207 if (debug)
208 tprintf("Too far away: v_dist = %d\n", v_dist);
209 return false;
210 }
211 // Candidates must either overlap in median y,
212 // or part or candidate must be an acceptable diacritic.
213 if (!part->VSignificantCoreOverlap(*candidate) &&
214 !part->OKDiacriticMerge(*candidate, debug) &&
215 !candidate->OKDiacriticMerge(*part, debug)) {
216 if (debug)
217 tprintf("Candidate fails overlap and diacritic tests!\n");
218 return false;
219 }
220 }
221 return true;
222}
223
224// Helper function to compute the increase in overlap of the parts list of
225// Colpartitions with the combination of merge1 and merge2, compared to
226// the overlap with them uncombined.
227// An overlap is not counted if passes the OKMergeOverlap test with ok_overlap
228// as the pixel overlap limit. merge1 and merge2 must both be non-nullptr.
229static int IncreaseInOverlap(const ColPartition* merge1,
230 const ColPartition* merge2,
231 int ok_overlap,
232 ColPartition_CLIST* parts) {
233 ASSERT_HOST(merge1 != nullptr && merge2 != nullptr);
234 int total_area = 0;
235 ColPartition_C_IT it(parts);
236 TBOX merged_box(merge1->bounding_box());
237 merged_box += merge2->bounding_box();
238 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
239 ColPartition* part = it.data();
240 if (part == merge1 || part == merge2)
241 continue;
242 TBOX part_box = part->bounding_box();
243 // Compute the overlap of the merged box with part.
244 int overlap_area = part_box.intersection(merged_box).area();
245 if (overlap_area > 0 && !part->OKMergeOverlap(*merge1, *merge2,
246 ok_overlap, false)) {
247 total_area += overlap_area;
248 // Subtract the overlap of merge1 and merge2 individually.
249 overlap_area = part_box.intersection(merge1->bounding_box()).area();
250 if (overlap_area > 0)
251 total_area -= overlap_area;
252 TBOX intersection_box = part_box.intersection(merge2->bounding_box());
253 overlap_area = intersection_box.area();
254 if (overlap_area > 0) {
255 total_area -= overlap_area;
256 // Add back the 3-way area.
257 intersection_box &= merge1->bounding_box(); // In-place intersection.
258 overlap_area = intersection_box.area();
259 if (overlap_area > 0)
260 total_area += overlap_area;
261 }
262 }
263 }
264 return total_area;
265}
266
267// Helper function to test that each partition in candidates is either a
268// good diacritic merge with part or an OK merge candidate with all others
269// in the candidates list.
270// ASCII Art Scenario:
271// We sometimes get text such as "join-this" where the - is actually a long
272// dash culled from a standard set of extra characters that don't match the
273// font of the text. This makes its strokewidth not match and forms a broken
274// set of 3 partitions for "join", "-" and "this" and the dash may slightly
275// overlap BOTH words.
276// ------- -------
277// | ==== |
278// ------- -------
279// The standard merge rule: "you can merge 2 partitions as long as there is
280// no increase in overlap elsewhere" fails miserably here. Merge any pair
281// of partitions and the combined box overlaps more with the third than
282// before. To allow the merge, we need to consider whether it is safe to
283// merge everything, without merging separate text lines. For that we need
284// everything to be an OKMergeCandidate (which is supposed to prevent
285// separate text lines merging), but this is hard for diacritics to satisfy,
286// so an alternative to being OKMergeCandidate with everything is to be an
287// OKDiacriticMerge with part as the base character.
288static bool TestCompatibleCandidates(const ColPartition& part, bool debug,
289 ColPartition_CLIST* candidates) {
290 ColPartition_C_IT it(candidates);
291 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
292 ColPartition* candidate = it.data();
293 if (!candidate->OKDiacriticMerge(part, false)) {
294 ColPartition_C_IT it2(it);
295 for (it2.mark_cycle_pt(); !it2.cycled_list(); it2.forward()) {
296 ColPartition* candidate2 = it2.data();
297 if (candidate2 != candidate &&
298 !OKMergeCandidate(candidate, candidate2, false)) {
299 if (debug) {
300 tprintf("NC overlap failed:Candidate:");
301 candidate2->bounding_box().print();
302 tprintf("fails to be a good merge with:");
303 candidate->bounding_box().print();
304 }
305 return false;
306 }
307 }
308 }
309 }
310 return true;
311}
312
313// Computes and returns the total overlap of all partitions in the grid.
314// If overlap_grid is non-null, it is filled with a grid that holds empty
315// partitions representing the union of all overlapped partitions.
317 int total_overlap = 0;
318 // Iterate the ColPartitions in the grid.
319 ColPartitionGridSearch gsearch(this);
320 gsearch.StartFullSearch();
321 ColPartition* part;
322 while ((part = gsearch.NextFullSearch()) != nullptr) {
323 ColPartition_CLIST neighbors;
324 const TBOX& part_box = part->bounding_box();
325 FindOverlappingPartitions(part_box, part, &neighbors);
326 ColPartition_C_IT n_it(&neighbors);
327 bool any_part_overlap = false;
328 for (n_it.mark_cycle_pt(); !n_it.cycled_list(); n_it.forward()) {
329 const TBOX& n_box = n_it.data()->bounding_box();
330 int overlap = n_box.intersection(part_box).area();
331 if (overlap > 0 && overlap_grid != nullptr) {
332 if (*overlap_grid == nullptr) {
333 *overlap_grid = new ColPartitionGrid(gridsize(), bleft(), tright());
334 }
335 (*overlap_grid)->InsertBBox(true, true, n_it.data()->ShallowCopy());
336 if (!any_part_overlap) {
337 (*overlap_grid)->InsertBBox(true, true, part->ShallowCopy());
338 }
339 }
340 any_part_overlap = true;
341 total_overlap += overlap;
342 }
343 }
344 return total_overlap;
345}
346
347// Finds all the ColPartitions in the grid that overlap with the given
348// box and returns them SortByBoxLeft(ed) and uniqued in the given list.
349// Any partition equal to not_this (may be nullptr) is excluded.
351 const ColPartition* not_this,
352 ColPartition_CLIST* parts) {
353 ColPartitionGridSearch rsearch(this);
354 rsearch.StartRectSearch(box);
355 ColPartition* part;
356 while ((part = rsearch.NextRectSearch()) != nullptr) {
357 if (part != not_this)
358 parts->add_sorted(SortByBoxLeft<ColPartition>, true, part);
359 }
360}
361
362// Finds and returns the best candidate ColPartition to merge with part,
363// selected from the candidates list, based on the minimum increase in
364// pairwise overlap among all the partitions overlapped by the combined box.
365// If overlap_increase is not nullptr then it returns the increase in overlap
366// that would result from the merge.
367// confirm_cb is a permanent callback that (if non-null) will be used to
368// confirm the validity of a proposed merge candidate before selecting it.
369//
370// ======HOW MERGING WORKS======
371// The problem:
372// We want to merge all the parts of a textline together, but avoid merging
373// separate textlines. Diacritics, i dots, punctuation, and broken characters
374// are examples of small bits that need merging with the main textline.
375// Drop-caps and descenders in one line that touch ascenders in the one below
376// are examples of cases where we don't want to merge.
377//
378// The solution:
379// Merges that increase overlap among other partitions are generally bad.
380// Those that don't increase overlap (much) and minimize the total area
381// seem to be good.
382//
383// Ascii art example:
384// The text:
385// groggy descenders
386// minimum ascenders
387// The boxes: The === represents a small box near or overlapping the lower box.
388// -----------------
389// | |
390// -----------------
391// -===-------------
392// | |
393// -----------------
394// In considering what to do with the small === box, we find the 2 larger
395// boxes as neighbours and possible merge candidates, but merging with the
396// upper box increases overlap with the lower box, whereas merging with the
397// lower box does not increase overlap.
398// If the small === box didn't overlap either to start with, total area
399// would be minimized by merging with the nearer (lower) box.
400//
401// This is a simple example. In reality, we have to allow some increase
402// in overlap, or tightly spaced text would end up in bits.
404 const ColPartition* part, ColPartition_CLIST* candidates, bool debug,
406 int* overlap_increase) {
407 if (overlap_increase != nullptr)
408 *overlap_increase = 0;
409 if (candidates->empty())
410 return nullptr;
411 int ok_overlap =
412 static_cast<int>(kTinyEnoughTextlineOverlapFraction * gridsize() + 0.5);
413 // The best neighbour to merge with is the one that causes least
414 // total pairwise overlap among all the neighbours.
415 // If more than one offers the same total overlap, choose the one
416 // with the least total area.
417 const TBOX& part_box = part->bounding_box();
418 ColPartition_C_IT it(candidates);
419 ColPartition* best_candidate = nullptr;
420 // Find the total combined box of all candidates and the original.
421 TBOX full_box(part_box);
422 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
423 ColPartition* candidate = it.data();
424 full_box += candidate->bounding_box();
425 }
426 // Keep valid neighbours in a list.
427 ColPartition_CLIST neighbours;
428 // Now run a rect search of the merged box for overlapping neighbours, as
429 // we need anything that might be overlapped by the merged box.
430 FindOverlappingPartitions(full_box, part, &neighbours);
431 if (debug) {
432 tprintf("Finding best merge candidate from %d, %d neighbours for box:",
433 candidates->length(), neighbours.length());
434 part_box.print();
435 }
436 // If the best increase in overlap is positive, then we also check the
437 // worst non-candidate overlap. This catches the case of multiple good
438 // candidates that overlap each other when merged. If the worst
439 // non-candidate overlap is better than the best overlap, then return
440 // the worst non-candidate overlap instead.
441 ColPartition_CLIST non_candidate_neighbours;
442 non_candidate_neighbours.set_subtract(SortByBoxLeft<ColPartition>, true,
443 &neighbours, candidates);
444 int worst_nc_increase = 0;
445 int best_increase = INT32_MAX;
446 int best_area = 0;
447 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
448 ColPartition* candidate = it.data();
449 if (confirm_cb != nullptr && !confirm_cb->Run(part, candidate)) {
450 if (debug) {
451 tprintf("Candidate not confirmed:");
452 candidate->bounding_box().print();
453 }
454 continue;
455 }
456 int increase = IncreaseInOverlap(part, candidate, ok_overlap, &neighbours);
457 const TBOX& cand_box = candidate->bounding_box();
458 if (best_candidate == nullptr || increase < best_increase) {
459 best_candidate = candidate;
460 best_increase = increase;
461 best_area = cand_box.bounding_union(part_box).area() - cand_box.area();
462 if (debug) {
463 tprintf("New best merge candidate has increase %d, area %d, over box:",
464 increase, best_area);
465 full_box.print();
466 candidate->Print();
467 }
468 } else if (increase == best_increase) {
469 int area = cand_box.bounding_union(part_box).area() - cand_box.area();
470 if (area < best_area) {
471 best_area = area;
472 best_candidate = candidate;
473 }
474 }
475 increase = IncreaseInOverlap(part, candidate, ok_overlap,
476 &non_candidate_neighbours);
477 if (increase > worst_nc_increase)
478 worst_nc_increase = increase;
479 }
480 if (best_increase > 0) {
481 // If the worst non-candidate increase is less than the best increase
482 // including the candidates, then all the candidates can merge together
483 // and the increase in outside overlap would be less, so use that result,
484 // but only if each candidate is either a good diacritic merge with part,
485 // or an ok merge candidate with all the others.
486 // See TestCompatibleCandidates for more explanation and a picture.
487 if (worst_nc_increase < best_increase &&
488 TestCompatibleCandidates(*part, debug, candidates)) {
489 best_increase = worst_nc_increase;
490 }
491 }
492 if (overlap_increase != nullptr)
493 *overlap_increase = best_increase;
494 return best_candidate;
495}
496
497// Helper to remove the given box from the given partition, put it in its
498// own partition, and add to the partition list.
499static void RemoveBadBox(BLOBNBOX* box, ColPartition* part,
500 ColPartition_LIST* part_list) {
501 part->RemoveBox(box);
502 ColPartition::MakeBigPartition(box, part_list);
503}
504
505
506// Split partitions where it reduces overlap between their bounding boxes.
507// ColPartitions are after all supposed to be a partitioning of the blobs
508// AND of the space on the page!
509// Blobs that cause overlaps get removed, put in individual partitions
510// and added to the big_parts list. They are most likely characters on
511// 2 textlines that touch, or something big like a dropcap.
513 ColPartition_LIST* big_parts) {
514 int ok_overlap =
515 static_cast<int>(kTinyEnoughTextlineOverlapFraction * gridsize() + 0.5);
516 // Iterate the ColPartitions in the grid.
517 ColPartitionGridSearch gsearch(this);
518 gsearch.StartFullSearch();
519 ColPartition* part;
520 while ((part = gsearch.NextFullSearch()) != nullptr) {
521 // Set up a rectangle search bounded by the part.
522 const TBOX& box = part->bounding_box();
523 ColPartitionGridSearch rsearch(this);
524 rsearch.SetUniqueMode(true);
525 rsearch.StartRectSearch(box);
526 int unresolved_overlaps = 0;
527
528 ColPartition* neighbour;
529 while ((neighbour = rsearch.NextRectSearch()) != nullptr) {
530 if (neighbour == part)
531 continue;
532 const TBOX& neighbour_box = neighbour->bounding_box();
533 if (neighbour->OKMergeOverlap(*part, *part, ok_overlap, false) &&
534 part->OKMergeOverlap(*neighbour, *neighbour, ok_overlap, false))
535 continue; // The overlap is OK both ways.
536
537 // If removal of the biggest box from either partition eliminates the
538 // overlap, and it is much bigger than the box left behind, then
539 // it is either a drop-cap, an inter-line join, or some junk that
540 // we don't want anyway, so put it in the big_parts list.
541 if (!part->IsSingleton()) {
542 BLOBNBOX* excluded = part->BiggestBox();
543 TBOX shrunken = part->BoundsWithoutBox(excluded);
544 if (!shrunken.overlap(neighbour_box) &&
545 excluded->bounding_box().height() >
546 kBigPartSizeRatio * shrunken.height()) {
547 // Removing the biggest box fixes the overlap, so do it!
548 gsearch.RemoveBBox();
549 RemoveBadBox(excluded, part, big_parts);
550 InsertBBox(true, true, part);
551 gsearch.RepositionIterator();
552 break;
553 }
554 } else if (box.contains(neighbour_box)) {
555 ++unresolved_overlaps;
556 continue; // No amount of splitting will fix it.
557 }
558 if (!neighbour->IsSingleton()) {
559 BLOBNBOX* excluded = neighbour->BiggestBox();
560 TBOX shrunken = neighbour->BoundsWithoutBox(excluded);
561 if (!shrunken.overlap(box) &&
562 excluded->bounding_box().height() >
563 kBigPartSizeRatio * shrunken.height()) {
564 // Removing the biggest box fixes the overlap, so do it!
565 rsearch.RemoveBBox();
566 RemoveBadBox(excluded, neighbour, big_parts);
567 InsertBBox(true, true, neighbour);
568 gsearch.RepositionIterator();
569 break;
570 }
571 }
572 int part_overlap_count = part->CountOverlappingBoxes(neighbour_box);
573 int neighbour_overlap_count = neighbour->CountOverlappingBoxes(box);
574 ColPartition* right_part = nullptr;
575 if (neighbour_overlap_count <= part_overlap_count ||
576 part->IsSingleton()) {
577 // Try to split the neighbour to reduce overlap.
578 BLOBNBOX* split_blob = neighbour->OverlapSplitBlob(box);
579 if (split_blob != nullptr) {
580 rsearch.RemoveBBox();
581 right_part = neighbour->SplitAtBlob(split_blob);
582 InsertBBox(true, true, neighbour);
583 ASSERT_HOST(right_part != nullptr);
584 }
585 } else {
586 // Try to split part to reduce overlap.
587 BLOBNBOX* split_blob = part->OverlapSplitBlob(neighbour_box);
588 if (split_blob != nullptr) {
589 gsearch.RemoveBBox();
590 right_part = part->SplitAtBlob(split_blob);
591 InsertBBox(true, true, part);
592 ASSERT_HOST(right_part != nullptr);
593 }
594 }
595 if (right_part != nullptr) {
596 InsertBBox(true, true, right_part);
597 gsearch.RepositionIterator();
598 rsearch.RepositionIterator();
599 break;
600 }
601 }
602 if (unresolved_overlaps > 2 && part->IsSingleton()) {
603 // This part is no good so just add to big_parts.
604 RemoveBBox(part);
605 ColPartition_IT big_it(big_parts);
606 part->set_block_owned(true);
607 big_it.add_to_end(part);
608 gsearch.RepositionIterator();
609 }
610 }
611}
612
613// Filters partitions of source_type by looking at local neighbours.
614// Where a majority of neighbours have a text type, the partitions are
615// changed to text, where the neighbours have image type, they are changed
616// to image, and partitions that have no definite neighbourhood type are
617// left unchanged.
618// im_box and rerotation are used to map blob coordinates onto the
619// nontext_map, which is used to prevent the spread of text neighbourhoods
620// into images.
621// Returns true if anything was changed.
623 Pix* nontext_map,
624 const TBOX& im_box,
625 const FCOORD& rotation) {
626 // Iterate the ColPartitions in the grid.
627 ColPartitionGridSearch gsearch(this);
628 gsearch.StartFullSearch();
629 ColPartition* part;
630 bool any_changed = false;
631 while ((part = gsearch.NextFullSearch()) != nullptr) {
632 if (part->flow() != source_type || BLOBNBOX::IsLineType(part->blob_type()))
633 continue;
634 const TBOX& box = part->bounding_box();
635 bool debug = AlignedBlob::WithinTestRegion(2, box.left(), box.bottom());
636 if (SmoothRegionType(nontext_map, im_box, rotation, debug, part))
637 any_changed = true;
638 }
639 return any_changed;
640}
641
642// Reflects the grid and its colpartitions in the y-axis, assuming that
643// all blob boxes have already been done.
645 ColPartition_LIST parts;
646 ColPartition_IT part_it(&parts);
647 // Iterate the ColPartitions in the grid to extract them.
648 ColPartitionGridSearch gsearch(this);
649 gsearch.StartFullSearch();
650 ColPartition* part;
651 while ((part = gsearch.NextFullSearch()) != nullptr) {
652 part_it.add_after_then_move(part);
653 }
654 ICOORD bot_left(-tright().x(), bleft().y());
655 ICOORD top_right(-bleft().x(), tright().y());
656 // Reinitializing the grid with reflected coords also clears all the
657 // pointers, so parts will now own the ColPartitions. (Briefly).
658 Init(gridsize(), bot_left, top_right);
659 for (part_it.move_to_first(); !part_it.empty(); part_it.forward()) {
660 part = part_it.extract();
661 part->ReflectInYAxis();
662 InsertBBox(true, true, part);
663 }
664}
665
666// Transforms the grid of partitions to the output blocks, putting each
667// partition into a separate block. We don't really care about the order,
668// as we just want to get as much text as possible without trying to organize
669// it into proper blocks or columns.
670// TODO(rays) some kind of sort function would be useful and probably better
671// than the default here, which is to sort by order of the grid search.
673 TO_BLOCK_LIST* to_blocks) {
674 TO_BLOCK_IT to_block_it(to_blocks);
675 BLOCK_IT block_it(blocks);
676 // All partitions will be put on this list and deleted on return.
677 ColPartition_LIST parts;
678 ColPartition_IT part_it(&parts);
679 // Iterate the ColPartitions in the grid to extract them.
680 ColPartitionGridSearch gsearch(this);
681 gsearch.StartFullSearch();
682 ColPartition* part;
683 while ((part = gsearch.NextFullSearch()) != nullptr) {
684 part_it.add_after_then_move(part);
685 // The partition has to be at least vaguely like text.
686 BlobRegionType blob_type = part->blob_type();
687 if (BLOBNBOX::IsTextType(blob_type) ||
688 (blob_type == BRT_UNKNOWN && part->boxes_count() > 1)) {
689 PolyBlockType type = blob_type == BRT_VERT_TEXT ? PT_VERTICAL_TEXT
691 // Get metrics from the row that will be used for the block.
692 TBOX box = part->bounding_box();
693 int median_width = part->median_width();
694 int median_height = part->median_height();
695 // Turn the partition into a TO_ROW.
696 TO_ROW* row = part->MakeToRow();
697 if (row == nullptr) {
698 // This partition is dead.
699 part->DeleteBoxes();
700 continue;
701 }
702 auto* block = new BLOCK("", true, 0, 0, box.left(), box.bottom(),
703 box.right(), box.top());
704 block->pdblk.set_poly_block(new POLY_BLOCK(box, type));
705 auto* to_block = new TO_BLOCK(block);
706 TO_ROW_IT row_it(to_block->get_rows());
707 row_it.add_after_then_move(row);
708 // We haven't differentially rotated vertical and horizontal text at
709 // this point, so use width or height as appropriate.
710 if (blob_type == BRT_VERT_TEXT) {
711 to_block->line_size = static_cast<float>(median_width);
712 to_block->line_spacing = static_cast<float>(box.width());
713 to_block->max_blob_size = static_cast<float>(box.width() + 1);
714 } else {
715 to_block->line_size = static_cast<float>(median_height);
716 to_block->line_spacing = static_cast<float>(box.height());
717 to_block->max_blob_size = static_cast<float>(box.height() + 1);
718 }
719 if (to_block->line_size == 0) to_block->line_size = 1;
720 block_it.add_to_end(block);
721 to_block_it.add_to_end(to_block);
722 } else {
723 // This partition is dead.
724 part->DeleteBoxes();
725 }
726 }
727 Clear();
728 // Now it is safe to delete the ColPartitions as parts goes out of scope.
729}
730
731// Rotates the grid and its colpartitions by the given angle, assuming that
732// all blob boxes have already been done.
733void ColPartitionGrid::Deskew(const FCOORD& deskew) {
734 ColPartition_LIST parts;
735 ColPartition_IT part_it(&parts);
736 // Iterate the ColPartitions in the grid to extract them.
737 ColPartitionGridSearch gsearch(this);
738 gsearch.StartFullSearch();
739 ColPartition* part;
740 while ((part = gsearch.NextFullSearch()) != nullptr) {
741 part_it.add_after_then_move(part);
742 }
743 // Rebuild the grid to the new size.
744 TBOX grid_box(bleft_, tright_);
745 grid_box.rotate_large(deskew);
746 Init(gridsize(), grid_box.botleft(), grid_box.topright());
747 // Reinitializing the grid with rotated coords also clears all the
748 // pointers, so parts will now own the ColPartitions. (Briefly).
749 for (part_it.move_to_first(); !part_it.empty(); part_it.forward()) {
750 part = part_it.extract();
751 part->ComputeLimits();
752 InsertBBox(true, true, part);
753 }
754}
755
756// Sets the left and right tabs of the partitions in the grid.
758 // Iterate the ColPartitions in the grid.
759 ColPartitionGridSearch gsearch(this);
760 gsearch.StartFullSearch();
761 ColPartition* part;
762 while ((part = gsearch.NextFullSearch()) != nullptr) {
763 const TBOX& part_box = part->bounding_box();
764 TabVector* left_line = tabgrid->LeftTabForBox(part_box, true, false);
765 // If the overlapping line is not a left tab, try for non-overlapping.
766 if (left_line != nullptr && !left_line->IsLeftTab())
767 left_line = tabgrid->LeftTabForBox(part_box, false, false);
768 if (left_line != nullptr && left_line->IsLeftTab())
769 part->SetLeftTab(left_line);
770 TabVector* right_line = tabgrid->RightTabForBox(part_box, true, false);
771 if (right_line != nullptr && !right_line->IsRightTab())
772 right_line = tabgrid->RightTabForBox(part_box, false, false);
773 if (right_line != nullptr && right_line->IsRightTab())
774 part->SetRightTab(right_line);
775 part->SetColumnGoodness(tabgrid->WidthCB());
776 }
777}
778
779// Makes the ColPartSets and puts them in the PartSetVector ready
780// for finding column bounds. Returns false if no partitions were found.
782 auto* part_lists = new ColPartition_LIST[gridheight()];
783 part_sets->reserve(gridheight());
784 // Iterate the ColPartitions in the grid to get parts onto lists for the
785 // y bottom of each.
786 ColPartitionGridSearch gsearch(this);
787 gsearch.StartFullSearch();
788 ColPartition* part;
789 bool any_parts_found = false;
790 while ((part = gsearch.NextFullSearch()) != nullptr) {
791 BlobRegionType blob_type = part->blob_type();
792 if (blob_type != BRT_NOISE &&
793 (blob_type != BRT_UNKNOWN || !part->boxes()->singleton())) {
794 int grid_x, grid_y;
795 const TBOX& part_box = part->bounding_box();
796 GridCoords(part_box.left(), part_box.bottom(), &grid_x, &grid_y);
797 ColPartition_IT part_it(&part_lists[grid_y]);
798 part_it.add_to_end(part);
799 any_parts_found = true;
800 }
801 }
802 if (any_parts_found) {
803 for (int grid_y = 0; grid_y < gridheight(); ++grid_y) {
804 ColPartitionSet* line_set = nullptr;
805 if (!part_lists[grid_y].empty()) {
806 line_set = new ColPartitionSet(&part_lists[grid_y]);
807 }
808 part_sets->push_back(line_set);
809 }
810 }
811 delete [] part_lists;
812 return any_parts_found;
813}
814
815// Makes a single ColPartitionSet consisting of a single ColPartition that
816// represents the total horizontal extent of the significant content on the
817// page. Used for the single column setting in place of automatic detection.
818// Returns nullptr if the page is empty of significant content.
820 ColPartition* single_column_part = nullptr;
821 // Iterate the ColPartitions in the grid to get parts onto lists for the
822 // y bottom of each.
823 ColPartitionGridSearch gsearch(this);
824 gsearch.StartFullSearch();
825 ColPartition* part;
826 while ((part = gsearch.NextFullSearch()) != nullptr) {
827 BlobRegionType blob_type = part->blob_type();
828 if (blob_type != BRT_NOISE &&
829 (blob_type != BRT_UNKNOWN || !part->boxes()->singleton())) {
830 // Consider for single column.
831 BlobTextFlowType flow = part->flow();
832 if ((blob_type == BRT_TEXT &&
833 (flow == BTFT_STRONG_CHAIN || flow == BTFT_CHAIN ||
834 flow == BTFT_LEADER || flow == BTFT_TEXT_ON_IMAGE)) ||
835 blob_type == BRT_RECTIMAGE || blob_type == BRT_POLYIMAGE) {
836 if (single_column_part == nullptr) {
837 single_column_part = part->ShallowCopy();
838 single_column_part->set_blob_type(BRT_TEXT);
839 // Copy the tabs from itself to properly setup the margins.
840 single_column_part->CopyLeftTab(*single_column_part, false);
841 single_column_part->CopyRightTab(*single_column_part, false);
842 } else {
843 if (part->left_key() < single_column_part->left_key())
844 single_column_part->CopyLeftTab(*part, false);
845 if (part->right_key() > single_column_part->right_key())
846 single_column_part->CopyRightTab(*part, false);
847 }
848 }
849 }
850 }
851 if (single_column_part != nullptr) {
852 // Make a ColPartitionSet out of the single_column_part as a candidate
853 // for the single column case.
854 single_column_part->SetColumnGoodness(cb);
855 return new ColPartitionSet(single_column_part);
856 }
857 return nullptr;
858}
859
860// Mark the BLOBNBOXes in each partition as being owned by that partition.
862 // Iterate the ColPartitions in the grid.
863 ColPartitionGridSearch gsearch(this);
864 gsearch.StartFullSearch();
865 ColPartition* part;
866 while ((part = gsearch.NextFullSearch()) != nullptr) {
867 part->ClaimBoxes();
868 }
869}
870
871// Retypes all the blobs referenced by the partitions in the grid.
872// Image blobs are found and returned in the im_blobs list, as they are not
873// owned by the block.
874void ColPartitionGrid::ReTypeBlobs(BLOBNBOX_LIST* im_blobs) {
875 BLOBNBOX_IT im_blob_it(im_blobs);
876 ColPartition_LIST dead_parts;
877 ColPartition_IT dead_part_it(&dead_parts);
878 // Iterate the ColPartitions in the grid.
879 ColPartitionGridSearch gsearch(this);
880 gsearch.StartFullSearch();
881 ColPartition* part;
882 while ((part = gsearch.NextFullSearch()) != nullptr) {
883 BlobRegionType blob_type = part->blob_type();
884 BlobTextFlowType flow = part->flow();
885 bool any_blobs_moved = false;
886 if (blob_type == BRT_POLYIMAGE || blob_type == BRT_RECTIMAGE) {
887 BLOBNBOX_C_IT blob_it(part->boxes());
888 for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
889 BLOBNBOX* blob = blob_it.data();
890 im_blob_it.add_after_then_move(blob);
891 }
892 } else if (blob_type != BRT_NOISE) {
893 // Make sure the blobs are marked with the correct type and flow.
894 BLOBNBOX_C_IT blob_it(part->boxes());
895 for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
896 BLOBNBOX* blob = blob_it.data();
897 if (blob->region_type() == BRT_NOISE) {
898 // TODO(rays) Deprecated. Change this section to an assert to verify
899 // and then delete.
900 ASSERT_HOST(blob->cblob()->area() != 0);
901 blob->set_owner(nullptr);
902 blob_it.extract();
903 any_blobs_moved = true;
904 } else {
905 blob->set_region_type(blob_type);
906 if (blob->flow() != BTFT_LEADER)
907 blob->set_flow(flow);
908 }
909 }
910 }
911 if (blob_type == BRT_NOISE || part->boxes()->empty()) {
912 BLOBNBOX_C_IT blob_it(part->boxes());
913 part->DisownBoxes();
914 dead_part_it.add_to_end(part);
915 gsearch.RemoveBBox();
916 for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
917 BLOBNBOX* blob = blob_it.data();
918 if (blob->cblob()->area() == 0) {
919 // Any blob with zero area is a fake image blob and should be deleted.
920 delete blob->cblob();
921 delete blob;
922 }
923 }
924 } else if (any_blobs_moved) {
925 gsearch.RemoveBBox();
926 part->ComputeLimits();
927 InsertBBox(true, true, part);
928 gsearch.RepositionIterator();
929 }
930 }
931}
932
933// The boxes within the partitions have changed (by deskew) so recompute
934// the bounds of all the partitions and reinsert them into the grid.
936 const ICOORD& bleft,
937 const ICOORD& tright,
938 const ICOORD& vertical) {
939 ColPartition_LIST saved_parts;
940 ColPartition_IT part_it(&saved_parts);
941 // Iterate the ColPartitions in the grid to get parts onto a list.
942 ColPartitionGridSearch gsearch(this);
943 gsearch.StartFullSearch();
944 ColPartition* part;
945 while ((part = gsearch.NextFullSearch()) != nullptr) {
946 part_it.add_to_end(part);
947 }
948 // Reinitialize grid to the new size.
950 // Recompute the bounds of the parts and put them back in the new grid.
951 for (part_it.move_to_first(); !part_it.empty(); part_it.forward()) {
952 part = part_it.extract();
953 part->set_vertical(vertical);
954 part->ComputeLimits();
955 InsertBBox(true, true, part);
956 }
957}
958
959// Improves the margins of the ColPartitions in the grid by calling
960// FindPartitionMargins on each.
961// best_columns, which may be nullptr, is an array of pointers indicating the
962// column set at each y-coordinate in the grid.
963// best_columns is usually the best_columns_ member of ColumnFinder.
965 // Iterate the ColPartitions in the grid.
966 ColPartitionGridSearch gsearch(this);
967 gsearch.StartFullSearch();
968 ColPartition* part;
969 while ((part = gsearch.NextFullSearch()) != nullptr) {
970 // Set up a rectangle search x-bounded by the column and y by the part.
971 ColPartitionSet* columns = best_columns != nullptr
972 ? best_columns[gsearch.GridY()]
973 : nullptr;
974 FindPartitionMargins(columns, part);
975 const TBOX& box = part->bounding_box();
976 if (AlignedBlob::WithinTestRegion(2, box.left(), box.bottom())) {
977 tprintf("Computed margins for part:");
978 part->Print();
979 }
980 }
981}
982
983// Improves the margins of the ColPartitions in the list by calling
984// FindPartitionMargins on each.
985// best_columns, which may be nullptr, is an array of pointers indicating the
986// column set at each y-coordinate in the grid.
987// best_columns is usually the best_columns_ member of ColumnFinder.
989 ColPartition_LIST* parts) {
990 ColPartition_IT part_it(parts);
991 for (part_it.mark_cycle_pt(); !part_it.cycled_list(); part_it.forward()) {
992 ColPartition* part = part_it.data();
993 ColPartitionSet* columns = nullptr;
994 if (best_columns != nullptr) {
995 const TBOX& part_box = part->bounding_box();
996 // Get the columns from the y grid coord.
997 int grid_x, grid_y;
998 GridCoords(part_box.left(), part_box.bottom(), &grid_x, &grid_y);
999 columns = best_columns[grid_y];
1000 }
1001 FindPartitionMargins(columns, part);
1002 }
1003}
1004
1005// Deletes all the partitions in the grid after disowning all the blobs.
1007 ColPartition_LIST dead_parts;
1008 ColPartition_IT dead_it(&dead_parts);
1009 ColPartitionGridSearch gsearch(this);
1010 gsearch.StartFullSearch();
1011 ColPartition* part;
1012 while ((part = gsearch.NextFullSearch()) != nullptr) {
1013 part->DisownBoxes();
1014 dead_it.add_to_end(part); // Parts will be deleted on return.
1015 }
1016 Clear();
1017}
1018
1019// Deletes all the partitions in the grid that are of type BRT_UNKNOWN and
1020// all the blobs in them.
1022 ColPartitionGridSearch gsearch(this);
1023 gsearch.StartFullSearch();
1024 ColPartition* part;
1025 while ((part = gsearch.NextFullSearch()) != nullptr) {
1026 if (part->blob_type() == BRT_UNKNOWN) {
1027 gsearch.RemoveBBox();
1028 // Once marked, the blobs will be swept up by DeleteUnownedNoise.
1029 part->set_flow(BTFT_NONTEXT);
1030 part->set_blob_type(BRT_NOISE);
1031 part->SetBlobTypes();
1032 part->DisownBoxes();
1033 delete part;
1034 }
1035 }
1036 block->DeleteUnownedNoise();
1037}
1038
1039// Deletes all the partitions in the grid that are NOT of flow type BTFT_LEADER.
1041 ColPartitionGridSearch gsearch(this);
1042 gsearch.StartFullSearch();
1043 ColPartition* part;
1044 while ((part = gsearch.NextFullSearch()) != nullptr) {
1045 if (part->flow() != BTFT_LEADER) {
1046 gsearch.RemoveBBox();
1047 if (part->ReleaseNonLeaderBoxes()) {
1048 InsertBBox(true, true, part);
1049 gsearch.RepositionIterator();
1050 } else {
1051 delete part;
1052 }
1053 }
1054 }
1055}
1056
1057// Finds and marks text partitions that represent figure captions.
1059 // For each image region find its best candidate text caption region,
1060 // if any and mark it as such.
1061 ColPartitionGridSearch gsearch(this);
1062 gsearch.StartFullSearch();
1063 ColPartition* part;
1064 while ((part = gsearch.NextFullSearch()) != nullptr) {
1065 if (part->IsImageType()) {
1066 const TBOX& part_box = part->bounding_box();
1067 bool debug = AlignedBlob::WithinTestRegion(2, part_box.left(),
1068 part_box.bottom());
1069 ColPartition* best_caption = nullptr;
1070 int best_dist = 0; // Distance to best_caption.
1071 int best_upper = 0; // Direction of best_caption.
1072 // Handle both lower and upper directions.
1073 for (int upper = 0; upper < 2; ++upper) {
1074 ColPartition_C_IT partner_it(upper ? part->upper_partners()
1075 : part->lower_partners());
1076 // If there are no image partners, then this direction is ok.
1077 for (partner_it.mark_cycle_pt(); !partner_it.cycled_list();
1078 partner_it.forward()) {
1079 ColPartition* partner = partner_it.data();
1080 if (partner->IsImageType()) {
1081 break;
1082 }
1083 }
1084 if (!partner_it.cycled_list()) continue;
1085 // Find the nearest totally overlapping text partner.
1086 for (partner_it.mark_cycle_pt(); !partner_it.cycled_list();
1087 partner_it.forward()) {
1088 ColPartition* partner = partner_it.data();
1089 if (!partner->IsTextType() || partner->type() == PT_TABLE) continue;
1090 const TBOX& partner_box = partner->bounding_box();
1091 if (debug) {
1092 tprintf("Finding figure captions for image part:");
1093 part_box.print();
1094 tprintf("Considering partner:");
1095 partner_box.print();
1096 }
1097 if (partner_box.left() >= part_box.left() &&
1098 partner_box.right() <= part_box.right()) {
1099 int dist = partner_box.y_gap(part_box);
1100 if (best_caption == nullptr || dist < best_dist) {
1101 best_dist = dist;
1102 best_caption = partner;
1103 best_upper = upper;
1104 }
1105 }
1106 }
1107 }
1108 if (best_caption != nullptr) {
1109 if (debug) {
1110 tprintf("Best caption candidate:");
1111 best_caption->bounding_box().print();
1112 }
1113 // We have a candidate caption. Qualify it as being separable from
1114 // any body text. We are looking for either a small number of lines
1115 // or a big gap that indicates a separation from the body text.
1116 int line_count = 0;
1117 int biggest_gap = 0;
1118 int smallest_gap = INT16_MAX;
1119 int total_height = 0;
1120 int mean_height = 0;
1121 ColPartition* end_partner = nullptr;
1122 ColPartition* next_partner = nullptr;
1123 for (ColPartition* partner = best_caption; partner != nullptr &&
1124 line_count <= kMaxCaptionLines;
1125 partner = next_partner) {
1126 if (!partner->IsTextType()) {
1127 end_partner = partner;
1128 break;
1129 }
1130 ++line_count;
1131 total_height += partner->bounding_box().height();
1132 next_partner = partner->SingletonPartner(best_upper);
1133 if (next_partner != nullptr) {
1134 int gap = partner->bounding_box().y_gap(
1135 next_partner->bounding_box());
1136 if (gap > biggest_gap) {
1137 biggest_gap = gap;
1138 end_partner = next_partner;
1139 mean_height = total_height / line_count;
1140 } else if (gap < smallest_gap) {
1141 smallest_gap = gap;
1142 }
1143 // If the gap looks big compared to the text size and the smallest
1144 // gap seen so far, then we can stop.
1145 if (biggest_gap > mean_height * kMinCaptionGapHeightRatio &&
1146 biggest_gap > smallest_gap * kMinCaptionGapRatio)
1147 break;
1148 }
1149 }
1150 if (debug) {
1151 tprintf("Line count=%d, biggest gap %d, smallest%d, mean height %d\n",
1152 line_count, biggest_gap, smallest_gap, mean_height);
1153 if (end_partner != nullptr) {
1154 tprintf("End partner:");
1155 end_partner->bounding_box().print();
1156 }
1157 }
1158 if (next_partner == nullptr && line_count <= kMaxCaptionLines)
1159 end_partner = nullptr; // No gap, but line count is small.
1160 if (line_count <= kMaxCaptionLines) {
1161 // This is a qualified caption. Mark the text as caption.
1162 for (ColPartition* partner = best_caption; partner != nullptr &&
1163 partner != end_partner;
1164 partner = next_partner) {
1165 partner->set_type(PT_CAPTION_TEXT);
1166 partner->SetBlobTypes();
1167 if (debug) {
1168 tprintf("Set caption type for partition:");
1169 partner->bounding_box().print();
1170 }
1171 next_partner = partner->SingletonPartner(best_upper);
1172 }
1173 }
1174 }
1175 }
1176 }
1177}
1178
1181
1182// For every ColPartition in the grid, finds its upper and lower neighbours.
1184 ColPartitionGridSearch gsearch(this);
1185 gsearch.StartFullSearch();
1186 ColPartition* part;
1187 while ((part = gsearch.NextFullSearch()) != nullptr) {
1188 if (part->IsVerticalType()) {
1189 FindVPartitionPartners(true, part);
1190 FindVPartitionPartners(false, part);
1191 } else {
1192 FindPartitionPartners(true, part);
1193 FindPartitionPartners(false, part);
1194 }
1195 }
1196}
1197
1198// Finds the best partner in the given direction for the given partition.
1199// Stores the result with AddPartner.
1201 if (part->type() == PT_NOISE)
1202 return; // Noise is not allowed to partner anything.
1203 const TBOX& box = part->bounding_box();
1204 int top = part->median_top();
1205 int bottom = part->median_bottom();
1206 int height = top - bottom;
1207 int mid_y = (bottom + top) / 2;
1208 ColPartitionGridSearch vsearch(this);
1209 // Search down for neighbour below
1210 vsearch.StartVerticalSearch(box.left(), box.right(), part->MidY());
1211 ColPartition* neighbour;
1212 ColPartition* best_neighbour = nullptr;
1213 int best_dist = INT32_MAX;
1214 while ((neighbour = vsearch.NextVerticalSearch(!upper)) != nullptr) {
1215 if (neighbour == part || neighbour->type() == PT_NOISE)
1216 continue; // Noise is not allowed to partner anything.
1217 int neighbour_bottom = neighbour->median_bottom();
1218 int neighbour_top = neighbour->median_top();
1219 int neighbour_y = (neighbour_bottom + neighbour_top) / 2;
1220 if (upper != (neighbour_y > mid_y))
1221 continue;
1222 if (!part->HOverlaps(*neighbour) && !part->WithinSameMargins(*neighbour))
1223 continue;
1224 if (!part->TypesMatch(*neighbour)) {
1225 if (best_neighbour == nullptr)
1226 best_neighbour = neighbour;
1227 continue;
1228 }
1229 int dist = upper ? neighbour_bottom - top : bottom - neighbour_top;
1230 if (dist <= kMaxPartitionSpacing * height) {
1231 if (dist < best_dist) {
1232 best_dist = dist;
1233 best_neighbour = neighbour;
1234 }
1235 } else {
1236 break;
1237 }
1238 }
1239 if (best_neighbour != nullptr)
1240 part->AddPartner(upper, best_neighbour);
1241}
1242
1243// Finds the best partner in the given direction for the given partition.
1244// Stores the result with AddPartner.
1246 ColPartition* part) {
1247 if (part->type() == PT_NOISE)
1248 return; // Noise is not allowed to partner anything.
1249 const TBOX& box = part->bounding_box();
1250 int left = part->median_left();
1251 int right = part->median_right();
1252 int width = right >= left ? right - left : -1;
1253 int mid_x = (left + right) / 2;
1254 ColPartitionGridSearch hsearch(this);
1255 // Search left for neighbour to_the_left
1256 hsearch.StartSideSearch(mid_x, box.bottom(), box.top());
1257 ColPartition* neighbour;
1258 ColPartition* best_neighbour = nullptr;
1259 int best_dist = INT32_MAX;
1260 while ((neighbour = hsearch.NextSideSearch(to_the_left)) != nullptr) {
1261 if (neighbour == part || neighbour->type() == PT_NOISE)
1262 continue; // Noise is not allowed to partner anything.
1263 int neighbour_left = neighbour->median_left();
1264 int neighbour_right = neighbour->median_right();
1265 int neighbour_x = (neighbour_left + neighbour_right) / 2;
1266 if (to_the_left != (neighbour_x < mid_x))
1267 continue;
1268 if (!part->VOverlaps(*neighbour))
1269 continue;
1270 if (!part->TypesMatch(*neighbour))
1271 continue; // Only match to other vertical text.
1272 int dist = to_the_left ? left - neighbour_right : neighbour_left - right;
1273 if (dist <= kMaxPartitionSpacing * width) {
1274 if (dist < best_dist || best_neighbour == nullptr) {
1275 best_dist = dist;
1276 best_neighbour = neighbour;
1277 }
1278 } else {
1279 break;
1280 }
1281 }
1282 // For vertical partitions, the upper partner is to the left, and lower is
1283 // to the right.
1284 if (best_neighbour != nullptr)
1285 part->AddPartner(to_the_left, best_neighbour);
1286}
1287
1288// For every ColPartition with multiple partners in the grid, reduces the
1289// number of partners to 0 or 1. If get_desperate is true, goes to more
1290// desperate merge methods to merge flowing text before breaking partnerships.
1292 ColPartitionGridSearch gsearch(this);
1293 // Refine in type order so that chasing multiple partners can be done
1294 // before eliminating type mis-matching partners.
1295 for (int type = PT_UNKNOWN + 1; type <= PT_COUNT; type++) {
1296 // Iterate the ColPartitions in the grid.
1297 gsearch.StartFullSearch();
1298 ColPartition* part;
1299 while ((part = gsearch.NextFullSearch()) != nullptr) {
1300 part->RefinePartners(static_cast<PolyBlockType>(type),
1301 get_desperate, this);
1302 // Iterator may have been messed up by a merge.
1303 gsearch.RepositionIterator();
1304 }
1305 }
1306}
1307
1308
1309// ========================== PRIVATE CODE ========================
1310
1311// Finds and returns a list of candidate ColPartitions to merge with part.
1312// The candidates must overlap search_box, and when merged must not
1313// overlap any other partitions that are not overlapped by each individually.
1314void ColPartitionGrid::FindMergeCandidates(const ColPartition* part,
1315 const TBOX& search_box, bool debug,
1316 ColPartition_CLIST* candidates) {
1317 int ok_overlap =
1318 static_cast<int>(kTinyEnoughTextlineOverlapFraction * gridsize() + 0.5);
1319 const TBOX& part_box = part->bounding_box();
1320 // Now run the rect search.
1321 ColPartitionGridSearch rsearch(this);
1322 rsearch.SetUniqueMode(true);
1323 rsearch.StartRectSearch(search_box);
1324 ColPartition* candidate;
1325 while ((candidate = rsearch.NextRectSearch()) != nullptr) {
1326 if (!OKMergeCandidate(part, candidate, debug))
1327 continue;
1328 const TBOX& c_box = candidate->bounding_box();
1329 // Candidate seems to be a potential merge with part. If one contains
1330 // the other, then the merge is a no-brainer. Otherwise, search the
1331 // combined box to see if anything else is inappropriately overlapped.
1332 if (!part_box.contains(c_box) && !c_box.contains(part_box)) {
1333 // Search the combined rectangle to see if anything new is overlapped.
1334 // This is a preliminary test designed to quickly weed-out poor
1335 // merge candidates that would create a big list of overlapped objects
1336 // for the squared-order overlap analysis. Eg. vertical and horizontal
1337 // line-like objects that overlap real text when merged:
1338 // || ==========================
1339 // ||
1340 // || r e a l t e x t
1341 // ||
1342 // ||
1343 TBOX merged_box(part_box);
1344 merged_box += c_box;
1345 ColPartitionGridSearch msearch(this);
1346 msearch.SetUniqueMode(true);
1347 msearch.StartRectSearch(merged_box);
1348 ColPartition* neighbour;
1349 while ((neighbour = msearch.NextRectSearch()) != nullptr) {
1350 if (neighbour == part || neighbour == candidate)
1351 continue; // Ignore itself.
1352 if (neighbour->OKMergeOverlap(*part, *candidate, ok_overlap, false))
1353 continue; // This kind of merge overlap is OK.
1354 TBOX n_box = neighbour->bounding_box();
1355 // The overlap is OK if:
1356 // * the n_box already overlapped the part or the candidate OR
1357 // * the n_box is a suitable merge with either part or candidate
1358 if (!n_box.overlap(part_box) && !n_box.overlap(c_box) &&
1359 !OKMergeCandidate(part, neighbour, false) &&
1360 !OKMergeCandidate(candidate, neighbour, false))
1361 break;
1362 }
1363 if (neighbour != nullptr) {
1364 if (debug) {
1365 tprintf("Combined box overlaps another that is not OK despite"
1366 " allowance of %d:", ok_overlap);
1367 neighbour->bounding_box().print();
1368 tprintf("Reason:");
1369 OKMergeCandidate(part, neighbour, true);
1370 tprintf("...and:");
1371 OKMergeCandidate(candidate, neighbour, true);
1372 tprintf("Overlap:");
1373 neighbour->OKMergeOverlap(*part, *candidate, ok_overlap, true);
1374 }
1375 continue;
1376 }
1377 }
1378 if (debug) {
1379 tprintf("Adding candidate:");
1380 candidate->bounding_box().print();
1381 }
1382 // Unique elements as they arrive.
1383 candidates->add_sorted(SortByBoxLeft<ColPartition>, true, candidate);
1384 }
1385}
1386
1387// Smoothes the region type/flow type of the given part by looking at local
1388// neighbours and the given image mask. Searches a padded rectangle with the
1389// padding truncated on one size of the part's box in turn for each side,
1390// using the result (if any) that has the least distance to all neighbours
1391// that contribute to the decision. This biases in favor of rectangular
1392// regions without completely enforcing them.
1393// If a good decision cannot be reached, the part is left unchanged.
1394// im_box and rerotation are used to map blob coordinates onto the
1395// nontext_map, which is used to prevent the spread of text neighbourhoods
1396// into images.
1397// Returns true if the partition was changed.
1398bool ColPartitionGrid::SmoothRegionType(Pix* nontext_map,
1399 const TBOX& im_box,
1400 const FCOORD& rerotation,
1401 bool debug,
1402 ColPartition* part) {
1403 const TBOX& part_box = part->bounding_box();
1404 if (debug) {
1405 tprintf("Smooothing part at:");
1406 part_box.print();
1407 }
1408 BlobRegionType best_type = BRT_UNKNOWN;
1409 int best_dist = INT32_MAX;
1410 int max_dist = std::min(part_box.width(), part_box.height());
1411 max_dist = std::max(max_dist * kMaxNeighbourDistFactor, gridsize() * 2);
1412 // Search with the pad truncated on each side of the box in turn.
1413 bool any_image = false;
1414 bool all_image = true;
1415 for (int d = 0; d < BND_COUNT; ++d) {
1416 int dist;
1417 auto dir = static_cast<BlobNeighbourDir>(d);
1418 BlobRegionType type = SmoothInOneDirection(dir, nontext_map, im_box,
1419 rerotation, debug, *part,
1420 &dist);
1421 if (debug) {
1422 tprintf("Result in dir %d = %d at dist %d\n", dir, type, dist);
1423 }
1424 if (type != BRT_UNKNOWN && dist < best_dist) {
1425 best_dist = dist;
1426 best_type = type;
1427 }
1428 if (type == BRT_POLYIMAGE)
1429 any_image = true;
1430 else
1431 all_image = false;
1432 }
1433 if (best_dist > max_dist)
1434 return false; // Too far away to set the type with it.
1435 if (part->flow() == BTFT_STRONG_CHAIN && !all_image) {
1436 return false; // We are not modifying it.
1437 }
1438 BlobRegionType new_type = part->blob_type();
1439 BlobTextFlowType new_flow = part->flow();
1440 if (best_type == BRT_TEXT && !any_image) {
1441 new_flow = BTFT_STRONG_CHAIN;
1442 new_type = BRT_TEXT;
1443 } else if (best_type == BRT_VERT_TEXT && !any_image) {
1444 new_flow = BTFT_STRONG_CHAIN;
1445 new_type = BRT_VERT_TEXT;
1446 } else if (best_type == BRT_POLYIMAGE) {
1447 new_flow = BTFT_NONTEXT;
1448 new_type = BRT_UNKNOWN;
1449 }
1450 if (new_type != part->blob_type() || new_flow != part->flow()) {
1451 part->set_flow(new_flow);
1452 part->set_blob_type(new_type);
1453 part->SetBlobTypes();
1454 if (debug) {
1455 tprintf("Modified part:");
1456 part->Print();
1457 }
1458 return true;
1459 } else {
1460 return false;
1461 }
1462}
1463
1464// Sets up a search box based on the part_box, padded in all directions
1465// except direction. Also setup dist_scaling to weight x,y distances according
1466// to the given direction.
1467static void ComputeSearchBoxAndScaling(BlobNeighbourDir direction,
1468 const TBOX& part_box,
1469 int min_padding,
1470 TBOX* search_box,
1471 ICOORD* dist_scaling) {
1472 *search_box = part_box;
1473 // Generate a pad value based on the min dimension of part_box, but at least
1474 // min_padding and then scaled by kMaxPadFactor.
1475 int padding = std::min(part_box.height(), part_box.width());
1476 padding = std::max(padding, min_padding);
1477 padding *= kMaxPadFactor;
1478 search_box->pad(padding, padding);
1479 // Truncate the box in the appropriate direction and make the distance
1480 // metric slightly biased in the truncated direction.
1481 switch (direction) {
1482 case BND_LEFT:
1483 search_box->set_left(part_box.left());
1484 *dist_scaling = ICOORD(2, 1);
1485 break;
1486 case BND_BELOW:
1487 search_box->set_bottom(part_box.bottom());
1488 *dist_scaling = ICOORD(1, 2);
1489 break;
1490 case BND_RIGHT:
1491 search_box->set_right(part_box.right());
1492 *dist_scaling = ICOORD(2, 1);
1493 break;
1494 case BND_ABOVE:
1495 search_box->set_top(part_box.top());
1496 *dist_scaling = ICOORD(1, 2);
1497 break;
1498 default:
1499 ASSERT_HOST(false);
1500 }
1501}
1502
1503// Local enum used by SmoothInOneDirection and AccumulatePartDistances
1504// for the different types of partition neighbour.
1506 NPT_HTEXT, // Definite horizontal text.
1507 NPT_VTEXT, // Definite vertical text.
1508 NPT_WEAK_HTEXT, // Weakly horizontal text. Counts as HTEXT for HTEXT, but
1509 // image for image and VTEXT.
1510 NPT_WEAK_VTEXT, // Weakly vertical text. Counts as VTEXT for VTEXT, but
1511 // image for image and HTEXT.
1512 NPT_IMAGE, // Defininte non-text.
1513 NPT_COUNT // Number of array elements.
1515
1516// Executes the search for SmoothRegionType in a single direction.
1517// Creates a bounding box that is padded in all directions except direction,
1518// and searches it for other partitions. Finds the nearest collection of
1519// partitions that makes a decisive result (if any) and returns the type
1520// and the distance of the collection. If there are any pixels in the
1521// nontext_map, then the decision is biased towards image.
1522BlobRegionType ColPartitionGrid::SmoothInOneDirection(
1523 BlobNeighbourDir direction, Pix* nontext_map,
1524 const TBOX& im_box, const FCOORD& rerotation,
1525 bool debug, const ColPartition& part, int* best_distance) {
1526 // Set up a rectangle search bounded by the part.
1527 const TBOX& part_box = part.bounding_box();
1528 TBOX search_box;
1529 ICOORD dist_scaling;
1530 ComputeSearchBoxAndScaling(direction, part_box, gridsize(),
1531 &search_box, &dist_scaling);
1532 bool image_region = ImageFind::CountPixelsInRotatedBox(search_box, im_box,
1533 rerotation,
1534 nontext_map) > 0;
1536 AccumulatePartDistances(part, dist_scaling, search_box,
1537 nontext_map, im_box, rerotation, debug, dists);
1538 // By iteratively including the next smallest distance across the vectors,
1539 // (as in a merge sort) we can use the vector indices as counts of each type
1540 // and find the nearest set of objects that give us a definite decision.
1541 int counts[NPT_COUNT];
1542 memset(counts, 0, sizeof(counts[0]) * NPT_COUNT);
1543 // If there is image in the search box, tip the balance in image's favor.
1544 int image_bias = image_region ? kSmoothDecisionMargin / 2 : 0;
1545 BlobRegionType text_dir = part.blob_type();
1546 BlobTextFlowType flow_type = part.flow();
1547 int min_dist = 0;
1548 do {
1549 // Find the minimum new entry across the vectors
1550 min_dist = INT32_MAX;
1551 for (int i = 0; i < NPT_COUNT; ++i) {
1552 if (counts[i] < dists[i].size() && dists[i][counts[i]] < min_dist)
1553 min_dist = dists[i][counts[i]];
1554 }
1555 // Step all the indices/counts forward to include min_dist.
1556 for (int i = 0; i < NPT_COUNT; ++i) {
1557 while (counts[i] < dists[i].size() && dists[i][counts[i]] <= min_dist)
1558 ++counts[i];
1559 }
1560 *best_distance = min_dist;
1561 if (debug) {
1562 tprintf("Totals: htext=%d+%d, vtext=%d+%d, image=%d+%d, at dist=%d\n",
1563 counts[NPT_HTEXT], counts[NPT_WEAK_HTEXT],
1564 counts[NPT_VTEXT], counts[NPT_WEAK_VTEXT],
1565 counts[NPT_IMAGE], image_bias, min_dist);
1566 }
1567 // See if we have a decision yet.
1568 int image_count = counts[NPT_IMAGE];
1569 int htext_score = counts[NPT_HTEXT] + counts[NPT_WEAK_HTEXT] -
1570 (image_count + counts[NPT_WEAK_VTEXT]);
1571 int vtext_score = counts[NPT_VTEXT] + counts[NPT_WEAK_VTEXT] -
1572 (image_count + counts[NPT_WEAK_HTEXT]);
1573 if (image_count > 0 &&
1574 image_bias - htext_score >= kSmoothDecisionMargin &&
1575 image_bias - vtext_score >= kSmoothDecisionMargin) {
1576 *best_distance = dists[NPT_IMAGE][0];
1577 if (!dists[NPT_WEAK_VTEXT].empty() &&
1578 *best_distance > dists[NPT_WEAK_VTEXT][0])
1579 *best_distance = dists[NPT_WEAK_VTEXT][0];
1580 if (!dists[NPT_WEAK_HTEXT].empty() &&
1581 *best_distance > dists[NPT_WEAK_HTEXT][0])
1582 *best_distance = dists[NPT_WEAK_HTEXT][0];
1583 return BRT_POLYIMAGE;
1584 }
1585 if ((text_dir != BRT_VERT_TEXT || flow_type != BTFT_CHAIN) &&
1586 counts[NPT_HTEXT] > 0 && htext_score >= kSmoothDecisionMargin) {
1587 *best_distance = dists[NPT_HTEXT][0];
1588 return BRT_TEXT;
1589 } else if ((text_dir != BRT_TEXT || flow_type != BTFT_CHAIN) &&
1590 counts[NPT_VTEXT] > 0 && vtext_score >= kSmoothDecisionMargin) {
1591 *best_distance = dists[NPT_VTEXT][0];
1592 return BRT_VERT_TEXT;
1593 }
1594 } while (min_dist < INT32_MAX);
1595 return BRT_UNKNOWN;
1596}
1597
1598// Counts the partitions in the given search_box by appending the gap
1599// distance (scaled by dist_scaling) of the part from the base_part to the
1600// vector of the appropriate type for the partition. Prior to return, the
1601// vectors in the dists array are sorted in increasing order.
1602// The nontext_map (+im_box, rerotation) is used to make text invisible if
1603// there is non-text in between.
1604// dists must be an array of GenericVectors of size NPT_COUNT.
1605void ColPartitionGrid::AccumulatePartDistances(const ColPartition& base_part,
1606 const ICOORD& dist_scaling,
1607 const TBOX& search_box,
1608 Pix* nontext_map,
1609 const TBOX& im_box,
1610 const FCOORD& rerotation,
1611 bool debug,
1612 GenericVector<int>* dists) {
1613 const TBOX& part_box = base_part.bounding_box();
1614 ColPartitionGridSearch rsearch(this);
1615 rsearch.SetUniqueMode(true);
1616 rsearch.StartRectSearch(search_box);
1617 ColPartition* neighbour;
1618 // Search for compatible neighbours with a similar strokewidth, but not
1619 // on the other side of a tab vector.
1620 while ((neighbour = rsearch.NextRectSearch()) != nullptr) {
1621 if (neighbour->IsUnMergeableType() ||
1622 !base_part.ConfirmNoTabViolation(*neighbour) ||
1623 neighbour == &base_part)
1624 continue;
1625 TBOX nbox = neighbour->bounding_box();
1626 BlobRegionType n_type = neighbour->blob_type();
1627 if ((n_type == BRT_TEXT || n_type == BRT_VERT_TEXT) &&
1628 !ImageFind::BlankImageInBetween(part_box, nbox, im_box, rerotation,
1629 nontext_map))
1630 continue; // Text not visible the other side of image.
1631 if (BLOBNBOX::IsLineType(n_type))
1632 continue; // Don't use horizontal lines as neighbours.
1633 int x_gap = std::max(part_box.x_gap(nbox), 0);
1634 int y_gap = std::max(part_box.y_gap(nbox), 0);
1635 int n_dist = x_gap * dist_scaling.x() + y_gap* dist_scaling.y();
1636 if (debug) {
1637 tprintf("Part has x-gap=%d, y=%d, dist=%d at:",
1638 x_gap, y_gap, n_dist);
1639 nbox.print();
1640 }
1641 // Truncate the number of boxes, so text doesn't get too much advantage.
1642 int n_boxes = std::min(neighbour->boxes_count(), kSmoothDecisionMargin);
1643 BlobTextFlowType n_flow = neighbour->flow();
1644 GenericVector<int>* count_vector = nullptr;
1645 if (n_flow == BTFT_STRONG_CHAIN) {
1646 if (n_type == BRT_TEXT)
1647 count_vector = &dists[NPT_HTEXT];
1648 else
1649 count_vector = &dists[NPT_VTEXT];
1650 if (debug) {
1651 tprintf("%s %d\n", n_type == BRT_TEXT ? "Htext" : "Vtext", n_boxes);
1652 }
1653 } else if ((n_type == BRT_TEXT || n_type == BRT_VERT_TEXT) &&
1654 (n_flow == BTFT_CHAIN || n_flow == BTFT_NEIGHBOURS)) {
1655 // Medium text counts as weak, and all else counts as image.
1656 if (n_type == BRT_TEXT)
1657 count_vector = &dists[NPT_WEAK_HTEXT];
1658 else
1659 count_vector = &dists[NPT_WEAK_VTEXT];
1660 if (debug) tprintf("Weak %d\n", n_boxes);
1661 } else {
1662 count_vector = &dists[NPT_IMAGE];
1663 if (debug) tprintf("Image %d\n", n_boxes);
1664 }
1665 if (count_vector != nullptr) {
1666 for (int i = 0; i < n_boxes; ++i)
1667 count_vector->push_back(n_dist);
1668 }
1669 if (debug) {
1670 neighbour->Print();
1671 }
1672 }
1673 for (int i = 0; i < NPT_COUNT; ++i)
1674 dists[i].sort();
1675}
1676
1677// Improves the margins of the part ColPartition by searching for
1678// neighbours that vertically overlap significantly.
1679// columns may be nullptr, and indicates the assigned column structure this
1680// is applicable to part.
1681void ColPartitionGrid::FindPartitionMargins(ColPartitionSet* columns,
1682 ColPartition* part) {
1683 // Set up a rectangle search x-bounded by the column and y by the part.
1684 TBOX box = part->bounding_box();
1685 int y = part->MidY();
1686 // Initial left margin is based on the column, if there is one.
1687 int left_margin = bleft().x();
1688 int right_margin = tright().x();
1689 if (columns != nullptr) {
1690 ColPartition* column = columns->ColumnContaining(box.left(), y);
1691 if (column != nullptr)
1692 left_margin = column->LeftAtY(y);
1693 column = columns->ColumnContaining(box.right(), y);
1694 if (column != nullptr)
1695 right_margin = column->RightAtY(y);
1696 }
1697 left_margin -= kColumnWidthFactor;
1698 right_margin += kColumnWidthFactor;
1699 // Search for ColPartitions that reduce the margin.
1700 left_margin = FindMargin(box.left() + box.height(), true, left_margin,
1701 box.bottom(), box.top(), part);
1702 part->set_left_margin(left_margin);
1703 // Search for ColPartitions that reduce the margin.
1704 right_margin = FindMargin(box.right() - box.height(), false, right_margin,
1705 box.bottom(), box.top(), part);
1706 part->set_right_margin(right_margin);
1707}
1708
1709// Starting at x, and going in the specified direction, up to x_limit, finds
1710// the margin for the given y range by searching sideways,
1711// and ignoring not_this.
1712int ColPartitionGrid::FindMargin(int x, bool right_to_left, int x_limit,
1713 int y_bottom, int y_top,
1714 const ColPartition* not_this) {
1715 int height = y_top - y_bottom;
1716 // Iterate the ColPartitions in the grid.
1717 ColPartitionGridSearch side_search(this);
1718 side_search.SetUniqueMode(true);
1719 side_search.StartSideSearch(x, y_bottom, y_top);
1720 ColPartition* part;
1721 while ((part = side_search.NextSideSearch(right_to_left)) != nullptr) {
1722 // Ignore itself.
1723 if (part == not_this) // || part->IsLineType())
1724 continue;
1725 // Must overlap by enough, based on the min of the heights, so
1726 // large partitions can't smash through small ones.
1727 TBOX box = part->bounding_box();
1728 int min_overlap = std::min(height, static_cast<int>(box.height()));
1729 min_overlap = static_cast<int>(min_overlap * kMarginOverlapFraction + 0.5);
1730 int y_overlap = std::min(y_top, static_cast<int>(box.top())) - std::max(y_bottom, static_cast<int>(box.bottom()));
1731 if (y_overlap < min_overlap)
1732 continue;
1733 // Must be going the right way.
1734 int x_edge = right_to_left ? box.right() : box.left();
1735 if ((x_edge < x) != right_to_left)
1736 continue;
1737 // If we have gone past x_limit, then x_limit will do.
1738 if ((x_edge < x_limit) == right_to_left)
1739 break;
1740 // It reduces x limit, so save the new one.
1741 x_limit = x_edge;
1742 }
1743 return x_limit;
1744}
1745
1746
1747} // namespace tesseract.
@ PT_COUNT
Definition: capi.h:144
@ PT_TABLE
Definition: capi.h:135
@ PT_NOISE
Definition: capi.h:143
@ PT_FLOWING_TEXT
Definition: capi.h:130
@ PT_UNKNOWN
Definition: capi.h:129
@ PT_VERTICAL_TEXT
Definition: capi.h:136
@ PT_CAPTION_TEXT
Definition: capi.h:137
BlobNeighbourDir
Definition: blobbox.h:87
@ BND_COUNT
Definition: blobbox.h:92
@ BND_ABOVE
Definition: blobbox.h:91
@ BND_LEFT
Definition: blobbox.h:88
@ BND_BELOW
Definition: blobbox.h:89
@ BND_RIGHT
Definition: blobbox.h:90
BlobTextFlowType
Definition: blobbox.h:114
@ BTFT_TEXT_ON_IMAGE
Definition: blobbox.h:120
@ BTFT_LEADER
Definition: blobbox.h:121
@ BTFT_CHAIN
Definition: blobbox.h:118
@ BTFT_STRONG_CHAIN
Definition: blobbox.h:119
@ BTFT_NEIGHBOURS
Definition: blobbox.h:117
@ BTFT_NONTEXT
Definition: blobbox.h:116
BlobRegionType
Definition: blobbox.h:72
@ BRT_RECTIMAGE
Definition: blobbox.h:76
@ BRT_POLYIMAGE
Definition: blobbox.h:77
@ BRT_TEXT
Definition: blobbox.h:80
@ BRT_UNKNOWN
Definition: blobbox.h:78
@ BRT_NOISE
Definition: blobbox.h:73
@ BRT_VERT_TEXT
Definition: blobbox.h:79
PolyBlockType
Definition: publictypes.h:53
#define ASSERT_HOST(x)
Definition: errcode.h:88
DLLSYM void tprintf(const char *format,...)
Definition: tprintf.cpp:35
const double kMaxPartitionSpacing
const int kSmoothDecisionMargin
const int kColumnWidthFactor
Definition: tabfind.h:42
const int kMaxCaptionLines
const double kTinyEnoughTextlineOverlapFraction
const double kMinCaptionGapHeightRatio
const double kBigPartSizeRatio
GridSearch< ColPartition, ColPartition_CLIST, ColPartition_C_IT > ColPartitionGridSearch
Definition: colpartition.h:936
const int kMaxPadFactor
const double kMarginOverlapFraction
const int kMaxNeighbourDistFactor
const double kMinCaptionGapRatio
int push_back(T object)
void reserve(int size)
virtual R Run(A1, A2)=0
static bool IsTextType(BlobRegionType type)
Definition: blobbox.h:418
BlobRegionType region_type() const
Definition: blobbox.h:283
void set_flow(BlobTextFlowType value)
Definition: blobbox.h:298
static bool IsLineType(BlobRegionType type)
Definition: blobbox.h:426
void set_region_type(BlobRegionType new_type)
Definition: blobbox.h:286
const TBOX & bounding_box() const
Definition: blobbox.h:230
C_BLOB * cblob() const
Definition: blobbox.h:268
BlobTextFlowType flow() const
Definition: blobbox.h:295
void set_owner(tesseract::ColPartition *new_owner)
Definition: blobbox.h:355
void DeleteUnownedNoise()
Definition: blobbox.cpp:1037
Definition: ocrblock.h:31
integer coordinate
Definition: points.h:32
int16_t y() const
access_function
Definition: points.h:56
int16_t x() const
access function
Definition: points.h:52
Definition: points.h:189
Definition: rect.h:34
const ICOORD & botleft() const
Definition: rect.h:92
void set_right(int x)
Definition: rect.h:82
void rotate_large(const FCOORD &vec)
Definition: rect.cpp:72
int16_t top() const
Definition: rect.h:58
void print() const
Definition: rect.h:278
void set_bottom(int y)
Definition: rect.h:68
int16_t width() const
Definition: rect.h:115
int32_t area() const
Definition: rect.h:122
int16_t height() const
Definition: rect.h:108
bool overlap(const TBOX &box) const
Definition: rect.h:355
void set_top(int y)
Definition: rect.h:61
int16_t left() const
Definition: rect.h:72
int y_gap(const TBOX &box) const
Definition: rect.h:233
int16_t bottom() const
Definition: rect.h:65
TBOX bounding_union(const TBOX &box) const
Definition: rect.cpp:129
TBOX intersection(const TBOX &box) const
Definition: rect.cpp:87
bool contains(const FCOORD pt) const
Definition: rect.h:333
void pad(int xpad, int ypad)
Definition: rect.h:131
const ICOORD & topright() const
Definition: rect.h:104
void set_left(int x)
Definition: rect.h:75
int x_gap(const TBOX &box) const
Definition: rect.h:225
int16_t right() const
Definition: rect.h:79
int32_t area()
Definition: stepblob.cpp:273
static bool WithinTestRegion(int detail_level, int x, int y)
void StartVerticalSearch(int xmin, int xmax, int y)
Definition: bbgrid.h:788
void StartRadSearch(int x, int y, int max_radius)
Definition: bbgrid.h:698
void SetUniqueMode(bool mode)
Definition: bbgrid.h:253
int GridY() const
Definition: bbgrid.h:245
BBC * NextSideSearch(bool right_to_left)
Definition: bbgrid.h:761
BBC * NextRectSearch()
Definition: bbgrid.h:842
void StartSideSearch(int x, int ymin, int ymax)
Definition: bbgrid.h:746
void StartFullSearch()
Definition: bbgrid.h:665
BBC * NextVerticalSearch(bool top_to_bottom)
Definition: bbgrid.h:802
void RepositionIterator()
Definition: bbgrid.h:892
void StartRectSearch(const TBOX &rect)
Definition: bbgrid.h:830
BBC * NextFullSearch()
Definition: bbgrid.h:675
BBC * NextRadSearch()
Definition: bbgrid.h:713
int gridsize() const
Definition: bbgrid.h:63
int gridheight() const
Definition: bbgrid.h:69
const ICOORD & bleft() const
Definition: bbgrid.h:72
ICOORD tright_
Definition: bbgrid.h:91
void GridCoords(int x, int y, int *grid_x, int *grid_y) const
Definition: bbgrid.cpp:52
const ICOORD & tright() const
Definition: bbgrid.h:75
void Init(int gridsize, const ICOORD &bleft, const ICOORD &tright)
Definition: bbgrid.h:445
void InsertBBox(bool h_spread, bool v_spread, ColPartition *bbox)
Definition: bbgrid.h:486
bool IsImageType() const
Definition: colpartition.h:430
BlobTextFlowType flow() const
Definition: colpartition.h:155
BLOBNBOX_CLIST * boxes()
Definition: colpartition.h:188
TBOX BoundsWithoutBox(BLOBNBOX *box)
bool TypesMatch(const ColPartition &other) const
Definition: colpartition.h:410
PolyBlockType type() const
Definition: colpartition.h:182
static ColPartition * MakeBigPartition(BLOBNBOX *box, ColPartition_LIST *big_part_list)
void RefinePartners(PolyBlockType type, bool get_desperate, ColPartitionGrid *grid)
ColPartition_CLIST * upper_partners()
Definition: colpartition.h:197
void SetRightTab(const TabVector *tab_vector)
bool VOverlaps(const ColPartition &other) const
Definition: colpartition.h:371
bool VSignificantCoreOverlap(const ColPartition &other) const
Definition: colpartition.h:391
BlobRegionType blob_type() const
Definition: colpartition.h:149
BLOBNBOX * OverlapSplitBlob(const TBOX &box)
void set_blob_type(BlobRegionType t)
Definition: colpartition.h:152
int VCoreOverlap(const ColPartition &other) const
Definition: colpartition.h:376
const TBOX & bounding_box() const
Definition: colpartition.h:110
int HCoreOverlap(const ColPartition &other) const
Definition: colpartition.h:385
bool IsVerticalType() const
Definition: colpartition.h:442
void SetLeftTab(const TabVector *tab_vector)
bool HOverlaps(const ColPartition &other) const
Definition: colpartition.h:366
int CountOverlappingBoxes(const TBOX &box)
void set_vertical(const ICOORD &v)
Definition: colpartition.h:194
bool OKDiacriticMerge(const ColPartition &candidate, bool debug) const
bool OKMergeOverlap(const ColPartition &merge1, const ColPartition &merge2, int ok_box_overlap, bool debug)
void SetColumnGoodness(WidthCallback *cb)
bool WithinSameMargins(const ColPartition &other) const
Definition: colpartition.h:402
void set_type(PolyBlockType t)
Definition: colpartition.h:185
ColPartition * ShallowCopy() const
void CopyRightTab(const ColPartition &src, bool take_box)
ColPartition * SplitAtBlob(BLOBNBOX *split_blob)
ColPartition * SingletonPartner(bool upper)
bool IsSingleton() const
Definition: colpartition.h:362
ColPartition_CLIST * lower_partners()
Definition: colpartition.h:200
bool IsUnMergeableType() const
Definition: colpartition.h:450
void set_block_owned(bool owned)
Definition: colpartition.h:209
void Absorb(ColPartition *other, WidthCallback *cb)
void RemoveBox(BLOBNBOX *box)
void AddPartner(bool upper, ColPartition *partner)
void set_flow(BlobTextFlowType f)
Definition: colpartition.h:158
void CopyLeftTab(const ColPartition &src, bool take_box)
void FindVPartitionPartners(bool to_the_left, ColPartition *part)
ColPartition * BestMergeCandidate(const ColPartition *part, ColPartition_CLIST *candidates, bool debug, TessResultCallback2< bool, const ColPartition *, const ColPartition * > *confirm_cb, int *overlap_increase)
void ExtractPartitionsAsBlocks(BLOCK_LIST *blocks, TO_BLOCK_LIST *to_blocks)
void SetTabStops(TabFind *tabgrid)
void RefinePartitionPartners(bool get_desperate)
void RecomputeBounds(int gridsize, const ICOORD &bleft, const ICOORD &tright, const ICOORD &vertical)
void Merges(TessResultCallback2< bool, ColPartition *, TBOX * > *box_cb, TessResultCallback2< bool, const ColPartition *, const ColPartition * > *confirm_cb)
int ComputeTotalOverlap(ColPartitionGrid **overlap_grid)
void GridFindMargins(ColPartitionSet **best_columns)
bool MakeColPartSets(PartSetVector *part_sets)
ColPartitionSet * MakeSingleColumnSet(WidthCallback *cb)
void SplitOverlappingPartitions(ColPartition_LIST *big_parts)
bool GridSmoothNeighbours(BlobTextFlowType source_type, Pix *nontext_map, const TBOX &im_box, const FCOORD &rerotation)
bool MergePart(TessResultCallback2< bool, ColPartition *, TBOX * > *box_cb, TessResultCallback2< bool, const ColPartition *, const ColPartition * > *confirm_cb, ColPartition *part)
void HandleClick(int x, int y) override
void DeleteUnknownParts(TO_BLOCK *block)
void FindOverlappingPartitions(const TBOX &box, const ColPartition *not_this, ColPartition_CLIST *parts)
void Deskew(const FCOORD &deskew)
void ReTypeBlobs(BLOBNBOX_LIST *im_blobs)
void ListFindMargins(ColPartitionSet **best_columns, ColPartition_LIST *parts)
static int CountPixelsInRotatedBox(TBOX box, const TBOX &im_box, const FCOORD &rotation, Pix *pix)
Definition: imagefind.cpp:597
static bool BlankImageInBetween(const TBOX &box1, const TBOX &box2, const TBOX &im_box, const FCOORD &rotation, Pix *pix)
Definition: imagefind.cpp:576
TabVector * RightTabForBox(const TBOX &box, bool crossing, bool extended)
Definition: tabfind.cpp:304
WidthCallback * WidthCB()
Definition: tabfind.h:158
TabVector * LeftTabForBox(const TBOX &box, bool crossing, bool extended)
Definition: tabfind.cpp:348
bool IsRightTab() const
Definition: tabvector.h:216
bool IsLeftTab() const
Definition: tabvector.h:212