tesseract  4.1.1
colpartitiongrid.cpp
Go to the documentation of this file.
1 // 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 
29 namespace tesseract {
30 
31 // Max pad factor used to search the neighbourhood of a partition to smooth
32 // partition types.
33 const 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.
38 const int kMaxCaptionLines = 7;
39 // Min ratio between biggest and smallest gap to bound a caption.
40 const double kMinCaptionGapRatio = 2.0;
41 // Min ratio between biggest gap and mean line height to bound a caption.
42 const double kMinCaptionGapHeightRatio = 0.5;
43 // Min fraction of ColPartition height to be overlapping for margin purposes.
44 const double kMarginOverlapFraction = 0.25;
45 // Size ratio required to consider an unmerged overlapping partition to be big.
46 const 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.
61 const double kMaxPartitionSpacing = 1.75;
62 // Margin by which text has to beat image or vice-versa to make a firm
63 // decision in GridSmoothNeighbour.
64 const int kSmoothDecisionMargin = 4;
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.
73 void ColPartitionGrid::HandleClick(int x, int y) {
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.
101  TessResultCallback2<bool, const ColPartition*,
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.
122  TessResultCallback2<bool, const ColPartition*,
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.
181 static 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.
229 static 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.
288 static 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.
499 static 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)) {
690  : PT_FLOWING_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.
733 void 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.
874 void 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.
1314 void 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.
1398 bool 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.
1467 static 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.
1514 };
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.
1522 BlobRegionType 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.
1605 void 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.
1681 void 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.
1712 int 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.
int HCoreOverlap(const ColPartition &other) const
Definition: colpartition.h:385
int16_t width() const
Definition: rect.h:115
PolyBlockType
Definition: publictypes.h:53
integer coordinate
Definition: points.h:31
void set_left(int x)
Definition: rect.h:75
static bool WithinTestRegion(int detail_level, int x, int y)
DLLSYM void tprintf(const char *format,...)
Definition: tprintf.cpp:35
void StartFullSearch()
Definition: bbgrid.h:665
const int kColumnWidthFactor
Definition: tabfind.h:42
void AddPartner(bool upper, ColPartition *partner)
int32_t area() const
Definition: rect.h:122
const int kMaxCaptionLines
bool VOverlaps(const ColPartition &other) const
Definition: colpartition.h:371
static int CountPixelsInRotatedBox(TBOX box, const TBOX &im_box, const FCOORD &rotation, Pix *pix)
Definition: imagefind.cpp:597
const int kMaxNeighbourDistFactor
void Merges(TessResultCallback2< bool, ColPartition *, TBOX *> *box_cb, TessResultCallback2< bool, const ColPartition *, const ColPartition *> *confirm_cb)
Definition: points.h:188
const double kTinyEnoughTextlineOverlapFraction
const double kMarginOverlapFraction
bool contains(const FCOORD pt) const
Definition: rect.h:333
void ReTypeBlobs(BLOBNBOX_LIST *im_blobs)
ColPartition * BestMergeCandidate(const ColPartition *part, ColPartition_CLIST *candidates, bool debug, TessResultCallback2< bool, const ColPartition *, const ColPartition *> *confirm_cb, int *overlap_increase)
void SetTabStops(TabFind *tabgrid)
const TBOX & bounding_box() const
Definition: blobbox.h:230
static bool IsTextType(BlobRegionType type)
Definition: blobbox.h:418
int gridheight() const
Definition: bbgrid.h:69
bool OKDiacriticMerge(const ColPartition &candidate, bool debug) const
static bool IsLineType(BlobRegionType type)
Definition: blobbox.h:426
Definition: capi.h:143
int x_gap(const TBOX &box) const
Definition: rect.h:225
Definition: capi.h:135
const int kSmoothDecisionMargin
void FindOverlappingPartitions(const TBOX &box, const ColPartition *not_this, ColPartition_CLIST *parts)
void set_flow(BlobTextFlowType value)
Definition: blobbox.h:298
void set_poly_block(POLY_BLOCK *blk)
set the poly block
Definition: pdblock.h:57
void Absorb(ColPartition *other, WidthCallback *cb)
void SetUniqueMode(bool mode)
Definition: bbgrid.h:253
ColPartitionSet * MakeSingleColumnSet(WidthCallback *cb)
BBC * NextSideSearch(bool right_to_left)
Definition: bbgrid.h:761
virtual R Run(A1, A2)=0
bool IsRightTab() const
Definition: tabvector.h:216
int VCoreOverlap(const ColPartition &other) const
Definition: colpartition.h:376
Definition: capi.h:144
void set_right(int x)
Definition: rect.h:82
void RepositionIterator()
Definition: bbgrid.h:892
static ColPartition * MakeBigPartition(BLOBNBOX *box, ColPartition_LIST *big_part_list)
PDBLK pdblk
Page Description Block.
Definition: ocrblock.h:190
WidthCallback * WidthCB()
Definition: tabfind.h:158
int16_t left() const
Definition: rect.h:72
void FindVPartitionPartners(bool to_the_left, ColPartition *part)
GridSearch< ColPartition, ColPartition_CLIST, ColPartition_C_IT > ColPartitionGridSearch
Definition: colpartition.h:936
const int kMaxPadFactor
bool IsLeftTab() const
Definition: tabvector.h:212
TabVector * LeftTabForBox(const TBOX &box, bool crossing, bool extended)
Definition: tabfind.cpp:348
int gridsize() const
Definition: bbgrid.h:63
int16_t height() const
Definition: rect.h:108
void CopyLeftTab(const ColPartition &src, bool take_box)
void set_block_owned(bool owned)
Definition: colpartition.h:209
BLOBNBOX_CLIST * boxes()
Definition: colpartition.h:188
const double kMaxPartitionSpacing
void set_owner(tesseract::ColPartition *new_owner)
Definition: blobbox.h:355
void pad(int xpad, int ypad)
Definition: rect.h:131
BlobTextFlowType flow() const
Definition: blobbox.h:295
BBC * NextVerticalSearch(bool top_to_bottom)
Definition: bbgrid.h:802
void rotate_large(const FCOORD &vec)
Definition: rect.cpp:72
TabVector * RightTabForBox(const TBOX &box, bool crossing, bool extended)
Definition: tabfind.cpp:304
bool TypesMatch(const ColPartition &other) const
Definition: colpartition.h:410
BlobRegionType region_type() const
Definition: blobbox.h:283
const double kBigPartSizeRatio
bool MergePart(TessResultCallback2< bool, ColPartition *, TBOX *> *box_cb, TessResultCallback2< bool, const ColPartition *, const ColPartition *> *confirm_cb, ColPartition *part)
BBC * NextFullSearch()
Definition: bbgrid.h:675
void set_flow(BlobTextFlowType f)
Definition: colpartition.h:158
BLOBNBOX * OverlapSplitBlob(const TBOX &box)
void DeleteUnknownParts(TO_BLOCK *block)
BlobNeighbourDir
Definition: blobbox.h:87
ColPartition * SingletonPartner(bool upper)
void StartRadSearch(int x, int y, int max_radius)
Definition: bbgrid.h:698
ColPartition * SplitAtBlob(BLOBNBOX *split_blob)
void RecomputeBounds(int gridsize, const ICOORD &bleft, const ICOORD &tright, const ICOORD &vertical)
void Deskew(const FCOORD &deskew)
static bool BlankImageInBetween(const TBOX &box1, const TBOX &box2, const TBOX &im_box, const FCOORD &rotation, Pix *pix)
Definition: imagefind.cpp:576
int32_t area()
Definition: stepblob.cpp:273
void set_top(int y)
Definition: rect.h:61
int16_t x() const
access function
Definition: points.h:52
const TBOX & bounding_box() const
Definition: colpartition.h:110
void InsertBBox(bool h_spread, bool v_spread, ColPartition *bbox)
Definition: bbgrid.h:486
int16_t bottom() const
Definition: rect.h:65
void SetRightTab(const TabVector *tab_vector)
TBOX intersection(const TBOX &box) const
Definition: rect.cpp:87
bool IsSingleton() const
Definition: colpartition.h:362
Definition: ocrblock.h:29
void GridCoords(int x, int y, int *grid_x, int *grid_y) const
Definition: bbgrid.cpp:52
bool IsVerticalType() const
Definition: colpartition.h:442
const double kMinCaptionGapHeightRatio
bool IsImageType() const
Definition: colpartition.h:430
void RefinePartners(PolyBlockType type, bool get_desperate, ColPartitionGrid *grid)
const ICOORD & botleft() const
Definition: rect.h:92
BBC * NextRadSearch()
Definition: bbgrid.h:713
PolyBlockType type() const
Definition: colpartition.h:182
void reserve(int size)
void GridFindMargins(ColPartitionSet **best_columns)
bool OKMergeOverlap(const ColPartition &merge1, const ColPartition &merge2, int ok_box_overlap, bool debug)
bool HOverlaps(const ColPartition &other) const
Definition: colpartition.h:366
void print() const
Definition: rect.h:278
ColPartition_CLIST * upper_partners()
Definition: colpartition.h:197
void Init(int gridsize, const ICOORD &bleft, const ICOORD &tright)
Definition: bbgrid.h:445
const ICOORD & tright() const
Definition: bbgrid.h:75
bool WithinSameMargins(const ColPartition &other) const
Definition: colpartition.h:402
bool GridSmoothNeighbours(BlobTextFlowType source_type, Pix *nontext_map, const TBOX &im_box, const FCOORD &rerotation)
bool VSignificantCoreOverlap(const ColPartition &other) const
Definition: colpartition.h:391
BBC * NextRectSearch()
Definition: bbgrid.h:842
const double kMinCaptionGapRatio
void SetLeftTab(const TabVector *tab_vector)
BlobRegionType
Definition: blobbox.h:72
void RemoveBox(BLOBNBOX *box)
BlobTextFlowType flow() const
Definition: colpartition.h:155
TBOX bounding_union(const TBOX &box) const
Definition: rect.cpp:129
C_BLOB * cblob() const
Definition: blobbox.h:268
Definition: rect.h:34
int y_gap(const TBOX &box) const
Definition: rect.h:233
void StartVerticalSearch(int xmin, int xmax, int y)
Definition: bbgrid.h:788
bool MakeColPartSets(PartSetVector *part_sets)
void ListFindMargins(ColPartitionSet **best_columns, ColPartition_LIST *parts)
void HandleClick(int x, int y) override
void SplitOverlappingPartitions(ColPartition_LIST *big_parts)
int ComputeTotalOverlap(ColPartitionGrid **overlap_grid)
void set_bottom(int y)
Definition: rect.h:68
bool overlap(const TBOX &box) const
Definition: rect.h:355
void ExtractPartitionsAsBlocks(BLOCK_LIST *blocks, TO_BLOCK_LIST *to_blocks)
const ICOORD & topright() const
Definition: rect.h:104
int16_t y() const
access_function
Definition: points.h:56
int push_back(T object)
BlobRegionType blob_type() const
Definition: colpartition.h:149
ColPartition * ShallowCopy() const
void CopyRightTab(const ColPartition &src, bool take_box)
void set_type(PolyBlockType t)
Definition: colpartition.h:185
void set_vertical(const ICOORD &v)
Definition: colpartition.h:194
void RefinePartitionPartners(bool get_desperate)
void SetColumnGoodness(WidthCallback *cb)
ColPartition_CLIST * lower_partners()
Definition: colpartition.h:200
void set_region_type(BlobRegionType new_type)
Definition: blobbox.h:286
ICOORD tright_
Definition: bbgrid.h:91
int16_t right() const
Definition: rect.h:79
#define ASSERT_HOST(x)
Definition: errcode.h:88
void DeleteUnownedNoise()
Definition: blobbox.cpp:1037
int GridY() const
Definition: bbgrid.h:245
int16_t top() const
Definition: rect.h:58
void set_blob_type(BlobRegionType t)
Definition: colpartition.h:152
int CountOverlappingBoxes(const TBOX &box)
void StartSideSearch(int x, int ymin, int ymax)
Definition: bbgrid.h:746
bool IsUnMergeableType() const
Definition: colpartition.h:450
BlobTextFlowType
Definition: blobbox.h:114
TBOX BoundsWithoutBox(BLOBNBOX *box)
void StartRectSearch(const TBOX &rect)
Definition: bbgrid.h:830
const ICOORD & bleft() const
Definition: bbgrid.h:72