Tesseract  3.02
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
colpartition.h
Go to the documentation of this file.
1 
2 // File: colpartition.h
3 // Description: Class to hold partitions of the page that correspond
4 // roughly to text lines.
5 // Author: Ray Smith
6 // Created: Thu Aug 14 10:50:01 PDT 2008
7 //
8 // (C) Copyright 2008, Google Inc.
9 // Licensed under the Apache License, Version 2.0 (the "License");
10 // you may not use this file except in compliance with the License.
11 // You may obtain a copy of the License at
12 // http://www.apache.org/licenses/LICENSE-2.0
13 // Unless required by applicable law or agreed to in writing, software
14 // distributed under the License is distributed on an "AS IS" BASIS,
15 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 // See the License for the specific language governing permissions and
17 // limitations under the License.
18 //
20 
21 #ifndef TESSERACT_TEXTORD_COLPARTITION_H__
22 #define TESSERACT_TEXTORD_COLPARTITION_H__
23 
24 #include "bbgrid.h"
25 #include "blobbox.h" // For BlobRegionType.
26 #include "ndminx.h"
27 #include "ocrblock.h"
28 #include "rect.h" // For TBOX.
29 #include "scrollview.h"
30 #include "tabfind.h" // For WidthCallback.
31 #include "tabvector.h" // For BLOBNBOX_CLIST.
32 
33 namespace tesseract {
34 
35 // Number of colors in the color1, color2 arrays.
36 const int kRGBRMSColors = 4;
37 
38 class ColPartition;
39 class ColPartitionSet;
40 class ColPartitionGrid;
41 class WorkingPartSet;
42 class WorkingPartSet_LIST;
43 
44 // An enum to indicate how a partition sits on the columns.
45 // The order of flowing/heading/pullout must be kept consistent with
46 // PolyBlockType.
48  CST_NOISE, // Strictly between columns.
49  CST_FLOWING, // Strictly within a single column.
50  CST_HEADING, // Spans multiple columns.
51  CST_PULLOUT, // Touches multiple columns, but doesn't span them.
52  CST_COUNT // Number of entries.
53 };
54 
55 ELIST2IZEH(ColPartition)
56 CLISTIZEH(ColPartition)
57 
67 class ColPartition : public ELIST2_LINK {
68  public:
70  // This empty constructor is here only so that the class can be ELISTIZED.
71  // TODO(rays) change deep_copy in elst.h line 955 to take a callback copier
72  // and eliminate CLASSNAME##_copier.
73  }
78  ColPartition(BlobRegionType blob_type, const ICOORD& vertical);
83  static ColPartition* MakeLinePartition(BlobRegionType blob_type,
84  const ICOORD& vertical,
85  int left, int bottom,
86  int right, int top);
87 
88  // Constructs and returns a fake ColPartition with a single fake BLOBNBOX,
89  // all made from a single TBOX.
90  // WARNING: Despite being on C_LISTs, the BLOBNBOX owns the C_BLOB and
91  // the ColPartition owns the BLOBNBOX!!!
92  // Call DeleteBoxes before deleting the ColPartition.
93  static ColPartition* FakePartition(const TBOX& box,
94  PolyBlockType block_type,
95  BlobRegionType blob_type,
96  BlobTextFlowType flow);
97 
98  // Constructs and returns a ColPartition with the given real BLOBNBOX,
99  // and sets it up to be a "big" partition (single-blob partition bigger
100  // than the surrounding text that may be a dropcap, two or more vertically
101  // touching characters, or some graphic element.
102  // If the given list is not NULL, the partition is also added to the list.
103  static ColPartition* MakeBigPartition(BLOBNBOX* box,
104  ColPartition_LIST* big_part_list);
105 
106  ~ColPartition();
107 
108  // Simple accessors.
109  const TBOX& bounding_box() const {
110  return bounding_box_;
111  }
112  int left_margin() const {
113  return left_margin_;
114  }
115  void set_left_margin(int margin) {
116  left_margin_ = margin;
117  }
118  int right_margin() const {
119  return right_margin_;
120  }
121  void set_right_margin(int margin) {
122  right_margin_ = margin;
123  }
124  int median_top() const {
125  return median_top_;
126  }
127  int median_bottom() const {
128  return median_bottom_;
129  }
130  int median_left() const {
131  return median_left_;
132  }
133  int median_right() const {
134  return median_right_;
135  }
136  int median_size() const {
137  return median_size_;
138  }
139  void set_median_size(int size) {
140  median_size_ = size;
141  }
142  int median_width() const {
143  return median_width_;
144  }
145  void set_median_width(int width) {
146  median_width_ = width;
147  }
149  return blob_type_;
150  }
152  blob_type_ = t;
153  }
155  return flow_;
156  }
158  flow_ = f;
159  }
160  int good_blob_score() const {
161  return good_blob_score_;
162  }
163  bool good_width() const {
164  return good_width_;
165  }
166  bool good_column() const {
167  return good_column_;
168  }
169  bool left_key_tab() const {
170  return left_key_tab_;
171  }
172  int left_key() const {
173  return left_key_;
174  }
175  bool right_key_tab() const {
176  return right_key_tab_;
177  }
178  int right_key() const {
179  return right_key_;
180  }
181  PolyBlockType type() const {
182  return type_;
183  }
185  type_ = t;
186  }
187  BLOBNBOX_CLIST* boxes() {
188  return &boxes_;
189  }
190  int boxes_count() const {
191  return boxes_.length();
192  }
193  void set_vertical(const ICOORD& v) {
194  vertical_ = v;
195  }
196  ColPartition_CLIST* upper_partners() {
197  return &upper_partners_;
198  }
199  ColPartition_CLIST* lower_partners() {
200  return &lower_partners_;
201  }
202  void set_working_set(WorkingPartSet* working_set) {
203  working_set_ = working_set;
204  }
205  bool block_owned() const {
206  return block_owned_;
207  }
208  void set_block_owned(bool owned) {
209  block_owned_ = owned;
210  }
211  bool desperately_merged() const {
212  return desperately_merged_;
213  }
215  return column_set_;
216  }
217  void set_side_step(int step) {
218  side_step_ = step;
219  }
220  int bottom_spacing() const {
221  return bottom_spacing_;
222  }
223  void set_bottom_spacing(int spacing) {
224  bottom_spacing_ = spacing;
225  }
226  int top_spacing() const {
227  return top_spacing_;
228  }
229  void set_top_spacing(int spacing) {
230  top_spacing_ = spacing;
231  }
232 
233  void set_table_type() {
234  if (type_ != PT_TABLE) {
235  type_before_table_ = type_;
236  type_ = PT_TABLE;
237  }
238  }
240  if (type_ == PT_TABLE)
241  type_ = type_before_table_;
242  }
244  return inside_table_column_;
245  }
246  void set_inside_table_column(bool val) {
247  inside_table_column_ = val;
248  }
250  return nearest_neighbor_above_;
251  }
253  nearest_neighbor_above_ = part;
254  }
256  return nearest_neighbor_below_;
257  }
259  nearest_neighbor_below_ = part;
260  }
261  int space_above() const {
262  return space_above_;
263  }
264  void set_space_above(int space) {
265  space_above_ = space;
266  }
267  int space_below() const {
268  return space_below_;
269  }
270  void set_space_below(int space) {
271  space_below_ = space;
272  }
273  int space_to_left() const {
274  return space_to_left_;
275  }
276  void set_space_to_left(int space) {
277  space_to_left_ = space;
278  }
279  int space_to_right() const {
280  return space_to_right_;
281  }
282  void set_space_to_right(int space) {
283  space_to_right_ = space;
284  }
286  return color1_;
287  }
289  return color2_;
290  }
291  bool owns_blobs() const {
292  return owns_blobs_;
293  }
294  void set_owns_blobs(bool owns_blobs) {
295  // Do NOT change ownership flag when there are blobs in the list.
296  // Immediately set the ownership flag when creating copies.
297  ASSERT_HOST(boxes_.empty());
298  owns_blobs_ = owns_blobs;
299  }
300 
301  // Inline quasi-accessors that require some computation.
302 
303  // Returns the middle y-coord of the bounding box.
304  int MidY() const {
305  return (bounding_box_.top() + bounding_box_.bottom()) / 2;
306  }
307  // Returns the middle y-coord of the median top and bottom.
308  int MedianY() const {
309  return (median_top_ + median_bottom_) / 2;
310  }
311  // Returns the middle x-coord of the bounding box.
312  int MidX() const {
313  return (bounding_box_.left() + bounding_box_.right()) / 2;
314  }
315  // Returns the sort key at any given x,y.
316  int SortKey(int x, int y) const {
317  return TabVector::SortKey(vertical_, x, y);
318  }
319  // Returns the x corresponding to the sortkey, y pair.
320  int XAtY(int sort_key, int y) const {
321  return TabVector::XAtY(vertical_, sort_key, y);
322  }
323  // Returns the x difference between the two sort keys.
324  int KeyWidth(int left_key, int right_key) const {
325  return (right_key - left_key) / vertical_.y();
326  }
327  // Returns the column width between the left and right keys.
328  int ColumnWidth() const {
329  return KeyWidth(left_key_, right_key_);
330  }
331  // Returns the sort key of the box left edge.
332  int BoxLeftKey() const {
333  return SortKey(bounding_box_.left(), MidY());
334  }
335  // Returns the sort key of the box right edge.
336  int BoxRightKey() const {
337  return SortKey(bounding_box_.right(), MidY());
338  }
339  // Returns the left edge at the given y, using the sort key.
340  int LeftAtY(int y) const {
341  return XAtY(left_key_, y);
342  }
343  // Returns the right edge at the given y, using the sort key.
344  int RightAtY(int y) const {
345  return XAtY(right_key_, y);
346  }
347  // Returns true if the right edge of this is to the left of the right
348  // edge of other.
349  bool IsLeftOf(const ColPartition& other) const {
350  return bounding_box_.right() < other.bounding_box_.right();
351  }
352  // Returns true if the partition contains the given x coordinate at the y.
353  bool ColumnContains(int x, int y) const {
354  return LeftAtY(y) - 1 <= x && x <= RightAtY(y) + 1;
355  }
356  // Returns true if there are no blobs in the list.
357  bool IsEmpty() const {
358  return boxes_.empty();
359  }
360  // Returns true if there is a single blob in the list.
361  bool IsSingleton() const {
362  return boxes_.singleton();
363  }
364  // Returns true if this and other overlap horizontally by bounding box.
365  bool HOverlaps(const ColPartition& other) const {
366  return bounding_box_.x_overlap(other.bounding_box_);
367  }
368  // Returns true if this and other's bounding boxes overlap vertically.
369  // TODO(rays) Make HOverlaps and VOverlaps truly symmetric.
370  bool VOverlaps(const ColPartition& other) const {
371  return bounding_box_.y_gap(other.bounding_box_) < 0;
372  }
373  // Returns the vertical overlap (by median) of this and other.
374  // WARNING! Only makes sense on horizontal partitions!
375  int VCoreOverlap(const ColPartition& other) const {
376  return MIN(median_top_, other.median_top_) -
377  MAX(median_bottom_, other.median_bottom_);
378  }
379  // Returns the horizontal overlap (by median) of this and other.
380  // WARNING! Only makes sense on vertical partitions!
381  int HCoreOverlap(const ColPartition& other) const {
382  return MIN(median_right_, other.median_right_) -
383  MAX(median_left_, other.median_left_);
384  }
385  // Returns true if this and other overlap significantly vertically.
386  // WARNING! Only makes sense on horizontal partitions!
387  bool VSignificantCoreOverlap(const ColPartition& other) const {
388  int overlap = VCoreOverlap(other);
389  int height = MIN(median_top_ - median_bottom_,
390  other.median_top_ - other.median_bottom_);
391  return overlap * 3 > height;
392  }
393  // Returns true if this and other can be combined without putting a
394  // horizontal step in either left or right edge of the resulting block.
395  bool WithinSameMargins(const ColPartition& other) const {
396  return left_margin_ <= other.bounding_box_.left() &&
397  bounding_box_.left() >= other.left_margin_ &&
398  bounding_box_.right() <= other.right_margin_ &&
399  right_margin_ >= other.bounding_box_.right();
400  }
401  // Returns true if the region types (aligned_text_) match.
402  // Lines never match anything, as they should never be merged or chained.
403  bool TypesMatch(const ColPartition& other) const {
404  return TypesMatch(blob_type_, other.blob_type_);
405  }
406  static bool TypesMatch(BlobRegionType type1, BlobRegionType type2) {
407  return (type1 == type2 || type1 == BRT_UNKNOWN || type2 == BRT_UNKNOWN) &&
408  !BLOBNBOX::IsLineType(type1) && !BLOBNBOX::IsLineType(type2);
409  }
410 
411  // Returns true if the types are similar to each other.
412  static bool TypesSimilar(PolyBlockType type1, PolyBlockType type2) {
413  return (type1 == type2 ||
414  (type1 == PT_FLOWING_TEXT && type2 == PT_INLINE_EQUATION) ||
415  (type2 == PT_FLOWING_TEXT && type1 == PT_INLINE_EQUATION));
416  }
417 
418  // Returns true if partitions is of horizontal line type
419  bool IsLineType() const {
420  return PTIsLineType(type_);
421  }
422  // Returns true if partitions is of image type
423  bool IsImageType() const {
424  return PTIsImageType(type_);
425  }
426  // Returns true if partitions is of text type
427  bool IsTextType() const {
428  return PTIsTextType(type_);
429  }
430  // Returns true if the partition is of an exclusively vertical type.
431  bool IsVerticalType() const {
432  return blob_type_ == BRT_VERT_TEXT || blob_type_ == BRT_VLINE;
433  }
434  // Returns true if the partition is of a definite horizontal type.
435  bool IsHorizontalType() const {
436  return blob_type_ == BRT_TEXT || blob_type_ == BRT_HLINE;
437  }
438  // Returns true is the partition is of a type that cannot be merged.
439  bool IsUnMergeableType() const {
440  return BLOBNBOX::UnMergeableType(blob_type_) || type_ == PT_NOISE;
441  }
442  // Returns true if this partition is a vertical line
443  // TODO(nbeato): Use PartitionType enum when Ray's code is submitted.
444  bool IsVerticalLine() const {
445  return IsVerticalType() && IsLineType();
446  }
447  // Returns true if this partition is a horizontal line
448  // TODO(nbeato): Use PartitionType enum when Ray's code is submitted.
449  bool IsHorizontalLine() const {
450  return IsHorizontalType() && IsLineType();
451  }
452 
453  // Adds the given box to the partition, updating the partition bounds.
454  // The list of boxes in the partition is updated, ensuring that no box is
455  // recorded twice, and the boxes are kept in increasing left position.
456  void AddBox(BLOBNBOX* box);
457 
458  // Removes the given box from the partition, updating the bounds.
459  void RemoveBox(BLOBNBOX* box);
460 
461  // Returns the tallest box in the partition, as measured perpendicular to the
462  // presumed flow of text.
463  BLOBNBOX* BiggestBox();
464 
465  // Returns the bounding box excluding the given box.
466  TBOX BoundsWithoutBox(BLOBNBOX* box);
467 
468  // Claims the boxes in the boxes_list by marking them with a this owner
469  // pointer.
470  void ClaimBoxes();
471 
472  // NULL the owner of the blobs in this partition, so they can be deleted
473  // independently of the ColPartition.
474  void DisownBoxes();
475 
476  // Delete the boxes that this partition owns.
477  void DeleteBoxes();
478 
479  // Reflects the partition in the y-axis, assuming that its blobs have
480  // already been done. Corrects only a limited part of the members, since
481  // this function is assumed to be used shortly after initial creation, which
482  // is before a lot of the members are used.
483  void ReflectInYAxis();
484 
485  // Returns true if this is a legal partition - meaning that the conditions
486  // left_margin <= bounding_box left
487  // left_key <= bounding box left key
488  // bounding box left <= bounding box right
489  // and likewise for right margin and key
490  // are all met.
491  bool IsLegal();
492 
493  // Returns true if the left and right edges are approximately equal.
494  bool MatchingColumns(const ColPartition& other) const;
495 
496  // Returns true if the colors match for two text partitions.
497  bool MatchingTextColor(const ColPartition& other) const;
498 
499  // Returns true if the sizes match for two text partitions,
500  // taking orientation into account
501  bool MatchingSizes(const ColPartition& other) const;
502 
503  // Returns true if there is no tabstop violation in merging this and other.
504  bool ConfirmNoTabViolation(const ColPartition& other) const;
505 
506  // Returns true if other has a similar stroke width to this.
507  bool MatchingStrokeWidth(const ColPartition& other,
508  double fractional_tolerance,
509  double constant_tolerance) const;
510  // Returns true if candidate is an acceptable diacritic base char merge
511  // with this as the diacritic.
512  bool OKDiacriticMerge(const ColPartition& candidate, bool debug) const;
513 
514  // Sets the sort key using either the tab vector, or the bounding box if
515  // the tab vector is NULL. If the tab_vector lies inside the bounding_box,
516  // use the edge of the box as a key any way.
517  void SetLeftTab(const TabVector* tab_vector);
518  void SetRightTab(const TabVector* tab_vector);
519 
520  // Copies the left/right tab from the src partition, but if take_box is
521  // true, copies the box instead and uses that as a key.
522  void CopyLeftTab(const ColPartition& src, bool take_box);
523  void CopyRightTab(const ColPartition& src, bool take_box);
524 
525  // Returns the left rule line x coord of the leftmost blob.
526  int LeftBlobRule() const;
527  // Returns the right rule line x coord of the rightmost blob.
528  int RightBlobRule() const;
529 
530  // Returns the density value for a particular BlobSpecialTextType.
531  float SpecialBlobsDensity(const BlobSpecialTextType type) const;
532  // Returns the number of blobs for a particular BlobSpecialTextType.
533  int SpecialBlobsCount(const BlobSpecialTextType type);
534  // Set the density value for a particular BlobSpecialTextType, should ONLY be
535  // used for debugging or testing. In production code, use
536  // ComputeSpecialBlobsDensity instead.
537  void SetSpecialBlobsDensity(
538  const BlobSpecialTextType type, const float density);
539  // Compute the SpecialTextType density of blobs, where we assume
540  // that the SpecialTextType in the boxes_ has been set.
541  void ComputeSpecialBlobsDensity();
542 
543  // Add a partner above if upper, otherwise below.
544  // Add them uniquely and keep the list sorted by box left.
545  // Partnerships are added symmetrically to partner and this.
546  void AddPartner(bool upper, ColPartition* partner);
547  // Removes the partner from this, but does not remove this from partner.
548  // This asymmetric removal is so as not to mess up the iterator that is
549  // working on partner's partner list.
550  void RemovePartner(bool upper, ColPartition* partner);
551  // Returns the partner if the given partner is a singleton, otherwise NULL.
552  ColPartition* SingletonPartner(bool upper);
553 
554  // Merge with the other partition and delete it.
555  void Absorb(ColPartition* other, WidthCallback* cb);
556 
557  // Returns true if the overlap between this and the merged pair of
558  // merge candidates is sufficiently trivial to be allowed.
559  // The merged box can graze the edge of this by the ok_box_overlap
560  // if that exceeds the margin to the median top and bottom.
561  bool OKMergeOverlap(const ColPartition& merge1, const ColPartition& merge2,
562  int ok_box_overlap, bool debug);
563 
564  // Find the blob at which to split this to minimize the overlap with the
565  // given box. Returns the first blob to go in the second partition.
566  BLOBNBOX* OverlapSplitBlob(const TBOX& box);
567 
568  // Split this partition keeping the first half in this and returning
569  // the second half.
570  // Splits by putting the split_blob and the blobs that follow
571  // in the second half, and the rest in the first half.
572  ColPartition* SplitAtBlob(BLOBNBOX* split_blob);
573 
574  // Splits this partition at the given x coordinate, returning the right
575  // half and keeping the left half in this.
576  ColPartition* SplitAt(int split_x);
577 
578  // Recalculates all the coordinate limits of the partition.
579  void ComputeLimits();
580 
581  // Returns the number of boxes that overlap the given box.
582  int CountOverlappingBoxes(const TBOX& box);
583 
584  // Computes and sets the type_, first_column_, last_column_ and column_set_.
585  // resolution refers to the ppi resolution of the image.
586  void SetPartitionType(int resolution, ColPartitionSet* columns);
587 
588  // Returns the PartitionType from the current BlobRegionType and a column
589  // flow spanning type ColumnSpanningType, generated by
590  // ColPartitionSet::SpanningType, that indicates how the partition sits
591  // in the columns.
592  PolyBlockType PartitionType(ColumnSpanningType flow) const;
593 
594  // Returns the first and last column touched by this partition.
595  // resolution refers to the ppi resolution of the image.
596  void ColumnRange(int resolution, ColPartitionSet* columns,
597  int* first_col, int* last_col);
598 
599  // Sets the internal flags good_width_ and good_column_.
600  void SetColumnGoodness(WidthCallback* cb);
601 
602  // Determines whether the blobs in this partition mostly represent
603  // a leader (fixed pitch sequence) and sets the member blobs accordingly.
604  // Note that height is assumed to have been tested elsewhere, and that this
605  // function will find most fixed-pitch text as leader without a height filter.
606  // Leader detection is limited to sequences of identical width objects,
607  // such as .... or ----, so patterns, such as .-.-.-.-. will not be found.
608  bool MarkAsLeaderIfMonospaced();
609  // Given the result of TextlineProjection::EvaluateColPartition, (positive for
610  // horizontal text, negative for vertical text, and near zero for non-text),
611  // sets the blob_type_ and flow_ for this partition to indicate whether it
612  // is strongly or weakly vertical or horizontal text, or non-text.
613  void SetRegionAndFlowTypesFromProjectionValue(int value);
614 
615  // Sets all blobs with the partition blob type and flow, but never overwrite
616  // leader blobs, as we need to be able to identify them later.
617  void SetBlobTypes();
618 
619  // Returns true if a decent baseline can be fitted through the blobs.
620  // Works for both horizontal and vertical text.
621  bool HasGoodBaseline();
622 
623  // Adds this ColPartition to a matching WorkingPartSet if one can be found,
624  // otherwise starts a new one in the appropriate column, ending the previous.
625  void AddToWorkingSet(const ICOORD& bleft, const ICOORD& tright,
626  int resolution, ColPartition_LIST* used_parts,
627  WorkingPartSet_LIST* working_set);
628 
629  // From the given block_parts list, builds one or more BLOCKs and
630  // corresponding TO_BLOCKs, such that the line spacing is uniform in each.
631  // Created blocks are appended to the end of completed_blocks and to_blocks.
632  // The used partitions are put onto used_parts, as they may still be referred
633  // to in the partition grid. bleft, tright and resolution are the bounds
634  // and resolution of the original image.
635  static void LineSpacingBlocks(const ICOORD& bleft, const ICOORD& tright,
636  int resolution,
637  ColPartition_LIST* block_parts,
638  ColPartition_LIST* used_parts,
639  BLOCK_LIST* completed_blocks,
640  TO_BLOCK_LIST* to_blocks);
641  // Constructs a block from the given list of partitions.
642  // Arguments are as LineSpacingBlocks above.
643  static TO_BLOCK* MakeBlock(const ICOORD& bleft, const ICOORD& tright,
644  ColPartition_LIST* block_parts,
645  ColPartition_LIST* used_parts);
646 
647  // Constructs a block from the given list of vertical text partitions.
648  // Currently only creates rectangular blocks.
649  static TO_BLOCK* MakeVerticalTextBlock(const ICOORD& bleft,
650  const ICOORD& tright,
651  ColPartition_LIST* block_parts,
652  ColPartition_LIST* used_parts);
653 
654 
655  // Returns a copy of everything except the list of boxes. The resulting
656  // ColPartition is only suitable for keeping in a column candidate list.
657  ColPartition* ShallowCopy() const;
658  // Returns a copy of everything with a shallow copy of the blobs.
659  // The blobs are still owned by their original parent, so they are
660  // treated as read-only.
661  ColPartition* CopyButDontOwnBlobs();
662 
663  #ifndef GRAPHICS_DISABLED
664  // Provides a color for BBGrid to draw the rectangle.
665  ScrollView::Color BoxColor() const;
666  #endif // GRAPHICS_DISABLED
667 
668  // Prints debug information on this.
669  void Print() const;
670  // Prints debug information on the colors.
671  void PrintColors();
672 
673  // Sets the types of all partitions in the run to be the max of the types.
674  void SmoothPartnerRun(int working_set_count);
675 
676  // Cleans up the partners of the given type so that there is at most
677  // one partner. This makes block creation simpler.
678  // If get_desperate is true, goes to more desperate merge methods
679  // to merge flowing text before breaking partnerships.
680  void RefinePartners(PolyBlockType type, bool get_desparate,
681  ColPartitionGrid* grid);
682 
683  // Returns true if this column partition is in the same column as
684  // part. This function will only work after the SetPartitionType function
685  // has been called on both column partitions. This is useful for
686  // doing a SideSearch when you want things in the same page column.
687  bool IsInSameColumnAs(const ColPartition& part) const;
688 
689  // Sets the column bounds. Primarily used in testing.
690  void set_first_column(int column) {
691  first_column_ = column;
692  }
693  void set_last_column(int column) {
694  last_column_ = column;
695  }
696 
697  private:
698  // enum to refer to the entries in a neigbourhood of lines.
699  // Used by SmoothSpacings to test for blips with OKSpacingBlip.
700  enum SpacingNeighbourhood {
701  PN_ABOVE2,
702  PN_ABOVE1,
703  PN_UPPER,
704  PN_LOWER,
705  PN_BELOW1,
706  PN_BELOW2,
707  PN_COUNT
708  };
709 
710  // Cleans up the partners above if upper is true, else below.
711  // If get_desperate is true, goes to more desperate merge methods
712  // to merge flowing text before breaking partnerships.
713  void RefinePartnersInternal(bool upper, bool get_desperate,
714  ColPartitionGrid* grid);
715  // Restricts the partners to only desirable types. For text and BRT_HLINE this
716  // means the same type_ , and for image types it means any image type.
717  void RefinePartnersByType(bool upper, ColPartition_CLIST* partners);
718  // Remove transitive partnerships: this<->a, and a<->b and this<->b.
719  // Gets rid of this<->b, leaving a clean chain.
720  // Also if we have this<->a and a<->this, then gets rid of this<->a, as
721  // this has multiple partners.
722  void RefinePartnerShortcuts(bool upper, ColPartition_CLIST* partners);
723  // If multiple text partners can be merged, then do so.
724  // If desperate is true, then an increase in overlap with the merge is
725  // allowed. If the overlap increases, then the desperately_merged_ flag
726  // is set, indicating that the textlines probably need to be regenerated
727  // by aggressive line fitting/splitting, as there are probably vertically
728  // joined blobs that cross textlines.
729  void RefineTextPartnersByMerge(bool upper, bool desperate,
730  ColPartition_CLIST* partners,
731  ColPartitionGrid* grid);
732  // Keep the partner with the biggest overlap.
733  void RefinePartnersByOverlap(bool upper, ColPartition_CLIST* partners);
734 
735  // Return true if bbox belongs better in this than other.
736  bool ThisPartitionBetter(BLOBNBOX* bbox, const ColPartition& other);
737 
738  // Smoothes the spacings in the list into groups of equal linespacing.
739  // resolution is the resolution of the original image, used as a basis
740  // for thresholds in change of spacing. page_height is in pixels.
741  static void SmoothSpacings(int resolution, int page_height,
742  ColPartition_LIST* parts);
743 
744  // Returns true if the parts array of pointers to partitions matches the
745  // condition for a spacing blip. See SmoothSpacings for what this means
746  // and how it is used.
747  static bool OKSpacingBlip(int resolution, int median_spacing,
748  ColPartition** parts);
749 
750  // Returns true if both the top and bottom spacings of this match the given
751  // spacing to within suitable margins dictated by the image resolution.
752  bool SpacingEqual(int spacing, int resolution) const;
753 
754  // Returns true if both the top and bottom spacings of this and other
755  // match to within suitable margins dictated by the image resolution.
756  bool SpacingsEqual(const ColPartition& other, int resolution) const;
757 
758  // Returns true if the sum spacing of this and other match the given
759  // spacing (or twice the given spacing) to within a suitable margin dictated
760  // by the image resolution.
761  bool SummedSpacingOK(const ColPartition& other,
762  int spacing, int resolution) const;
763 
764  // Returns a suitable spacing margin that can be applied to bottoms of
765  // text lines, based on the resolution and the stored side_step_.
766  int BottomSpacingMargin(int resolution) const;
767 
768  // Returns a suitable spacing margin that can be applied to tops of
769  // text lines, based on the resolution and the stored side_step_.
770  int TopSpacingMargin(int resolution) const;
771 
772  // Returns true if the median text sizes of this and other agree to within
773  // a reasonable multiplicative factor.
774  bool SizesSimilar(const ColPartition& other) const;
775 
776  // Computes and returns in start, end a line segment formed from a
777  // forwards-iterated group of left edges of partitions that satisfy the
778  // condition that the rightmost left margin is to the left of the
779  // leftmost left bounding box edge.
780  // TODO(rays) Not good enough. Needs improving to tightly wrap text in both
781  // directions, and to loosely wrap images.
782  static void LeftEdgeRun(ColPartition_IT* part_it,
783  ICOORD* start, ICOORD* end);
784  // Computes and returns in start, end a line segment formed from a
785  // backwards-iterated group of right edges of partitions that satisfy the
786  // condition that the leftmost right margin is to the right of the
787  // rightmost right bounding box edge.
788  // TODO(rays) Not good enough. Needs improving to tightly wrap text in both
789  // directions, and to loosely wrap images.
790  static void RightEdgeRun(ColPartition_IT* part_it,
791  ICOORD* start, ICOORD* end);
792 
793  // The margins are determined by the position of the nearest vertically
794  // overlapping neighbour to the side. They indicate the maximum extent
795  // that the block/column may be extended without touching something else.
796  // Leftmost coordinate that the region may occupy over the y limits.
797  int left_margin_;
798  // Rightmost coordinate that the region may occupy over the y limits.
799  int right_margin_;
800  // Bounding box of all blobs in the partition.
801  TBOX bounding_box_;
802  // Median top and bottom of blobs in this partition.
803  int median_bottom_;
804  int median_top_;
805  // Median height of blobs in this partition.
806  // TODO(rays) rename median_height_.
807  int median_size_;
808  // Median left and right of blobs in this partition.
809  int median_left_;
810  int median_right_;
811  // Median width of blobs in this partition.
812  int median_width_;
813  // blob_region_type_ for the blobs in this partition.
814  BlobRegionType blob_type_;
815  BlobTextFlowType flow_; // Quality of text flow.
816  // Total of GoodTextBlob results for all blobs in the partition.
817  int good_blob_score_;
818  // True if this partition has a common width.
819  bool good_width_;
820  // True if this is a good column candidate.
821  bool good_column_;
822  // True if the left_key_ is from a tab vector.
823  bool left_key_tab_;
824  // True if the right_key_ is from a tab vector.
825  bool right_key_tab_;
826  // Left and right sort keys for the edges of the partition.
827  // If the respective *_key_tab_ is true then this key came from a tab vector.
828  // If not, then the class promises to keep the key equal to the sort key
829  // for the respective edge of the bounding box at the MidY, so that
830  // LeftAtY and RightAtY always returns an x coordinate on the line parallel
831  // to vertical_ through the bounding box edge at MidY.
832  int left_key_;
833  int right_key_;
834  // Type of this partition after looking at its relation to the columns.
835  PolyBlockType type_;
836  // All boxes in the partition stored in increasing left edge coordinate.
837  BLOBNBOX_CLIST boxes_;
838  // The global vertical skew direction.
839  ICOORD vertical_;
840  // The partitions above that matched this.
841  ColPartition_CLIST upper_partners_;
842  // The partitions below that matched this.
843  ColPartition_CLIST lower_partners_;
844  // The WorkingPartSet it lives in while blocks are being made.
845  WorkingPartSet* working_set_;
846  // Flag is true when AddBox is sorting vertically, false otherwise.
847  bool last_add_was_vertical_;
848  // True when the partition's ownership has been taken from the grid and
849  // placed in a working set, or, after that, in the good_parts_ list.
850  bool block_owned_;
851  // Flag to indicate that this partition was subjected to a desperate merge,
852  // and therefore the textlines need rebuilding.
853  bool desperately_merged_;
854  // The first and last column that this partition applies to.
855  // Flowing partitions (see type_) will have an equal first and last value
856  // of the form 2n + 1, where n is the zero-based index into the partitions
857  // in column_set_. (See ColPartitionSet::GetColumnByIndex).
858  // Heading partitions will have unequal values of the same form.
859  // Pullout partitions will have equal values, but may have even values,
860  // indicating placement between columns.
861  int first_column_;
862  int last_column_;
863  // Column_set_ is the column layout applicable to this ColPartition.
864  ColPartitionSet* column_set_;
865  // Linespacing data.
866  int side_step_; // Median y-shift to next blob on same line.
867  int top_spacing_; // Line spacing from median_top_.
868  int bottom_spacing_; // Line spacing from median_bottom_.
869 
870  // Type of this partition before considering it as a table cell. This is
871  // used to revert the type if a partition is first marked as a table cell but
872  // later filtering steps decide it does not belong to a table
873  PolyBlockType type_before_table_;
874  bool inside_table_column_; // Check whether the current partition has been
875  // assigned to a table column
876  // Nearest neighbor above with major x-overlap
877  ColPartition* nearest_neighbor_above_;
878  // Nearest neighbor below with major x-overlap
879  ColPartition* nearest_neighbor_below_;
880  int space_above_; // Distance from nearest_neighbor_above
881  int space_below_; // Distance from nearest_neighbor_below
882  int space_to_left_; // Distance from the left edge of the column
883  int space_to_right_; // Distance from the right edge of the column
884  // Color foreground/background data.
885  uinT8 color1_[kRGBRMSColors];
886  uinT8 color2_[kRGBRMSColors];
887  bool owns_blobs_; // Does the partition own its blobs?
888  // The density of special blobs.
889  float special_blobs_densities_[BSTT_COUNT];
890 };
891 
892 // Typedef it now in case it becomes a class later.
893 typedef GridSearch<ColPartition,
894  ColPartition_CLIST,
895  ColPartition_C_IT> ColPartitionGridSearch;
896 
897 } // namespace tesseract.
898 
899 #endif // TESSERACT_TEXTORD_COLPARTITION_H__