Tesseract  3.02
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
strokewidth.cpp
Go to the documentation of this file.
1 
2 // File: strokewidth.cpp
3 // Description: Subclass of BBGrid to find uniformity of strokewidth.
4 // Author: Ray Smith
5 // Created: Mon Mar 31 16:17:01 PST 2008
6 //
7 // (C) Copyright 2008, Google Inc.
8 // Licensed under the Apache License, Version 2.0 (the "License");
9 // you may not use this file except in compliance with the License.
10 // You may obtain a copy of the License at
11 // http://www.apache.org/licenses/LICENSE-2.0
12 // Unless required by applicable law or agreed to in writing, software
13 // distributed under the License is distributed on an "AS IS" BASIS,
14 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 // See the License for the specific language governing permissions and
16 // limitations under the License.
17 //
19 
20 #ifdef _MSC_VER
21 #pragma warning(disable:4244) // Conversion warnings
22 #endif
23 
24 #include "strokewidth.h"
25 
26 #include <math.h>
27 
28 #include "blobbox.h"
29 #include "colpartition.h"
30 #include "colpartitiongrid.h"
31 #include "imagefind.h"
32 #include "linlsq.h"
33 #include "statistc.h"
34 #include "tabfind.h"
35 #include "textlineprojection.h"
36 #include "tordmain.h" // For SetBlobStrokeWidth.
37 
38 // Include automatically generated configuration file if running autoconf.
39 #ifdef HAVE_CONFIG_H
40 #include "config_auto.h"
41 #endif
42 
43 namespace tesseract {
44 
45 INT_VAR(textord_tabfind_show_strokewidths, 0, "Show stroke widths");
46 BOOL_VAR(textord_tabfind_only_strokewidths, false, "Only run stroke widths");
47 BOOL_VAR(textord_tabfind_vertical_text, true, "Enable vertical detection");
49  "Force using vertical text page mode");
51  "find horizontal lines such as headers in vertical page mode");
53  "Fraction of textlines deemed vertical to use vertical page mode");
54 
56 const double kStrokeWidthFractionTolerance = 0.125;
61 const double kStrokeWidthTolerance = 1.5;
62 // Same but for CJK we are a bit more generous.
63 const double kStrokeWidthFractionCJK = 0.25;
64 const double kStrokeWidthCJK = 2.0;
65 // Radius in grid cells of search for broken CJK. Doesn't need to be very
66 // large as the grid size should be about the size of a character anyway.
67 const int kCJKRadius = 2;
68 // Max distance fraction of size to join close but broken CJK characters.
69 const double kCJKBrokenDistanceFraction = 0.25;
70 // Max number of components in a broken CJK character.
71 const int kCJKMaxComponents = 8;
72 // Max aspect ratio of CJK broken characters when put back together.
73 const double kCJKAspectRatio = 1.25;
74 // Max increase in aspect ratio of CJK broken characters when merged.
75 const double kCJKAspectRatioIncrease = 1.0625;
76 // Max multiple of the grid size that will be used in computing median CJKsize.
77 const int kMaxCJKSizeRatio = 5;
78 // Min fraction of blobs broken CJK to iterate and run it again.
79 const double kBrokenCJKIterationFraction = 0.125;
80 // Multiple of gridsize as x-padding for a search box for diacritic base
81 // characters.
82 const double kDiacriticXPadRatio = 7.0;
83 // Multiple of gridsize as y-padding for a search box for diacritic base
84 // characters.
85 const double kDiacriticYPadRatio = 1.75;
86 // Min multiple of diacritic height that a neighbour must be to be a
87 // convincing base character.
88 const double kMinDiacriticSizeRatio = 1.0625;
89 // Max multiple of a textline's median height as a threshold for the sum of
90 // a diacritic's farthest x and y distances (gap + size).
91 const double kMaxDiacriticDistanceRatio = 1.25;
92 // Max x-gap between a diacritic and its base char as a fraction of the height
93 // of the base char (allowing other blobs to fill the gap.)
95 // Radius of a search for diacritics in grid units.
96 const int kSearchRadius = 2;
97 // Ratio between longest side of a line and longest side of a character.
98 // (neighbor_min > blob_min * kLineTrapShortest &&
99 // neighbor_max < blob_max / kLineTrapLongest)
100 // => neighbor is a grapheme and blob is a line.
101 const int kLineTrapLongest = 4;
102 // Ratio between shortest side of a line and shortest side of a character.
103 const int kLineTrapShortest = 2;
104 // Max aspect ratio of the total box before CountNeighbourGaps
105 // decides immediately based on the aspect ratio.
106 const int kMostlyOneDirRatio = 3;
107 // Aspect ratio for a blob to be considered as line residue.
108 const double kLineResidueAspectRatio = 8.0;
109 // Padding ratio for line residue search box.
110 const int kLineResiduePadRatio = 3;
111 // Min multiple of neighbour size for a line residue to be genuine.
112 const double kLineResidueSizeRatio = 1.75;
113 // Aspect ratio filter for OSD.
114 const float kSizeRatioToReject = 2.0;
115 // Max number of normal blobs a large blob may overlap before it is rejected
116 // and determined to be image
117 const int kMaxLargeOverlaps = 3;
118 // Expansion factor for search box for good neighbours.
119 const double kNeighbourSearchFactor = 2.5;
120 
122  const ICOORD& bleft, const ICOORD& tright)
123  : BlobGrid(gridsize, bleft, tright), nontext_map_(NULL), projection_(NULL),
124  denorm_(NULL), grid_box_(bleft, tright), rerotation_(1.0f, 0.0f) {
125  leaders_win_ = NULL;
126  widths_win_ = NULL;
127  initial_widths_win_ = NULL;
128  chains_win_ = NULL;
129  diacritics_win_ = NULL;
130  textlines_win_ = NULL;
131  smoothed_win_ = NULL;
132 }
133 
135  if (widths_win_ != NULL) {
136  #ifndef GRAPHICS_DISABLED
137  delete widths_win_->AwaitEvent(SVET_DESTROY);
138  #endif // GRAPHICS_DISABLED
140  exit(0);
141  delete widths_win_;
142  }
143  delete leaders_win_;
144  delete initial_widths_win_;
145  delete chains_win_;
146  delete textlines_win_;
147  delete smoothed_win_;
148  delete diacritics_win_;
149 }
150 
151 // Sets the neighbours member of the medium-sized blobs in the block.
152 // Searches on 4 sides of each blob for similar-sized, similar-strokewidth
153 // blobs and sets pointers to the good neighbours.
155  // Run a preliminary strokewidth neighbour detection on the medium blobs.
156  InsertBlobList(&block->blobs);
157  BLOBNBOX_IT blob_it(&block->blobs);
158  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
159  SetNeighbours(false, false, blob_it.data());
160  }
161  Clear();
162 }
163 
164 // Sets the neighbour/textline writing direction members of the medium
165 // and large blobs with optional repair of broken CJK characters first.
166 // Repair of broken CJK is needed here because broken CJK characters
167 // can fool the textline direction detection algorithm.
169  TO_BLOCK* input_block) {
170  // Setup the grid with the remaining (non-noise) blobs.
171  InsertBlobs(input_block);
172  // Repair broken CJK characters if needed.
173  while (cjk_merge && FixBrokenCJK(input_block));
174  // Grade blobs by inspection of neighbours.
175  FindTextlineFlowDirection(false);
176  // Clear the grid ready for rotation or leader finding.
177  Clear();
178 }
179 
180 // Helper to collect and count horizontal and vertical blobs from a list.
181 static void CollectHorizVertBlobs(BLOBNBOX_LIST* input_blobs,
182  int* num_vertical_blobs,
183  int* num_horizontal_blobs,
184  BLOBNBOX_CLIST* vertical_blobs,
185  BLOBNBOX_CLIST* horizontal_blobs,
186  BLOBNBOX_CLIST* nondescript_blobs) {
187  BLOBNBOX_C_IT v_it(vertical_blobs);
188  BLOBNBOX_C_IT h_it(horizontal_blobs);
189  BLOBNBOX_C_IT n_it(nondescript_blobs);
190  BLOBNBOX_IT blob_it(input_blobs);
191  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
192  BLOBNBOX* blob = blob_it.data();
193  const TBOX& box = blob->bounding_box();
194  float y_x = static_cast<float>(box.height()) / box.width();
195  float x_y = 1.0f / y_x;
196  // Select a >= 1.0 ratio
197  float ratio = x_y > y_x ? x_y : y_x;
198  // If the aspect ratio is small and we want them for osd, save the blob.
199  bool ok_blob = ratio <= kSizeRatioToReject;
200  if (blob->UniquelyVertical()) {
201  ++*num_vertical_blobs;
202  if (ok_blob) v_it.add_after_then_move(blob);
203  } else if (blob->UniquelyHorizontal()) {
204  ++*num_horizontal_blobs;
205  if (ok_blob) h_it.add_after_then_move(blob);
206  } else if (ok_blob) {
207  n_it.add_after_then_move(blob);
208  }
209  }
210 }
211 
212 
213 // Types all the blobs as vertical or horizontal text or unknown and
214 // returns true if the majority are vertical.
215 // If the blobs are rotated, it is necessary to call CorrectForRotation
216 // after rotating everything, otherwise the work done here will be enough.
217 // If osd_blobs is not null, a list of blobs from the dominant textline
218 // direction are returned for use in orientation and script detection.
220  BLOBNBOX_CLIST* osd_blobs) {
221  if (textord_tabfind_force_vertical_text) return true;
222  if (!textord_tabfind_vertical_text) return false;
223 
224  int vertical_boxes = 0;
225  int horizontal_boxes = 0;
226  // Count vertical normal and large blobs.
227  BLOBNBOX_CLIST vertical_blobs;
228  BLOBNBOX_CLIST horizontal_blobs;
229  BLOBNBOX_CLIST nondescript_blobs;
230  CollectHorizVertBlobs(&block->blobs, &vertical_boxes, &horizontal_boxes,
231  &vertical_blobs, &horizontal_blobs, &nondescript_blobs);
232  CollectHorizVertBlobs(&block->large_blobs, &vertical_boxes, &horizontal_boxes,
233  &vertical_blobs, &horizontal_blobs, &nondescript_blobs);
235  tprintf("TextDir hbox=%d vs vbox=%d, %dH, %dV, %dN osd blobs\n",
236  horizontal_boxes, vertical_boxes,
237  horizontal_blobs.length(), vertical_blobs.length(),
238  nondescript_blobs.length());
239  if (osd_blobs != NULL && vertical_boxes == 0 && horizontal_boxes == 0) {
240  // Only nondescript blobs available, so return those.
241  BLOBNBOX_C_IT osd_it(osd_blobs);
242  osd_it.add_list_after(&nondescript_blobs);
243  return false;
244  }
245  int min_vert_boxes = static_cast<int>((vertical_boxes + horizontal_boxes) *
247  if (vertical_boxes >= min_vert_boxes) {
248  if (osd_blobs != NULL) {
249  BLOBNBOX_C_IT osd_it(osd_blobs);
250  osd_it.add_list_after(&vertical_blobs);
251  }
252  return true;
253  } else {
254  if (osd_blobs != NULL) {
255  BLOBNBOX_C_IT osd_it(osd_blobs);
256  osd_it.add_list_after(&horizontal_blobs);
257  }
258  return false;
259  }
260 }
261 
262 // Corrects the data structures for the given rotation.
264  ColPartitionGrid* part_grid) {
265  Init(part_grid->gridsize(), part_grid->bleft(), part_grid->tright());
266  grid_box_ = TBOX(bleft(), tright());
267  rerotation_.set_x(rotation.x());
268  rerotation_.set_y(-rotation.y());
269 }
270 
271 // Finds leader partitions and inserts them into the given part_grid.
273  ColPartitionGrid* part_grid) {
274  Clear();
275  // Find and isolate leaders in the noise list.
276  ColPartition_LIST leader_parts;
277  FindLeadersAndMarkNoise(block, &leader_parts);
278  // Setup the strokewidth grid with the block's remaining (non-noise) blobs.
279  InsertBlobList(&block->blobs);
280  // Mark blobs that have leader neighbours.
281  for (ColPartition_IT it(&leader_parts); !it.empty(); it.forward()) {
282  ColPartition* part = it.extract();
283  part->ClaimBoxes();
284  MarkLeaderNeighbours(part, LR_LEFT);
285  MarkLeaderNeighbours(part, LR_RIGHT);
286  part_grid->InsertBBox(true, true, part);
287  }
288 }
289 
290 // Finds and marks noise those blobs that look like bits of vertical lines
291 // that would otherwise screw up layout analysis.
292 void StrokeWidth::RemoveLineResidue(ColPartition_LIST* big_part_list) {
293  BlobGridSearch gsearch(this);
294  BLOBNBOX* bbox;
295  // For every vertical line-like bbox in the grid, search its neighbours
296  // to find the tallest, and if the original box is taller by sufficient
297  // margin, then call it line residue and delete it.
298  gsearch.StartFullSearch();
299  while ((bbox = gsearch.NextFullSearch()) != NULL) {
300  TBOX box = bbox->bounding_box();
301  if (box.height() < box.width() * kLineResidueAspectRatio)
302  continue;
303  // Set up a rectangle search around the blob to find the size of its
304  // neighbours.
305  int padding = box.height() * kLineResiduePadRatio;
306  TBOX search_box = box;
307  search_box.pad(padding, padding);
308  bool debug = AlignedBlob::WithinTestRegion(2, box.left(),
309  box.bottom());
310  // Find the largest object in the search box not equal to bbox.
311  BlobGridSearch rsearch(this);
312  int max_size = 0;
313  BLOBNBOX* n;
314  rsearch.StartRectSearch(search_box);
315  while ((n = rsearch.NextRectSearch()) != NULL) {
316  if (n == bbox) continue;
317  TBOX nbox = n->bounding_box();
318  if (nbox.height() > max_size) {
319  max_size = nbox.height();
320  }
321  }
322  if (debug) {
323  tprintf("Max neighbour size=%d for candidate line box at:", max_size);
324  box.print();
325  }
326  if (max_size * kLineResidueSizeRatio < box.height()) {
327  #ifndef GRAPHICS_DISABLED
328  if (leaders_win_ != NULL) {
329  // We are debugging, so display deleted in pink blobs in the same
330  // window that we use to display leader detection.
331  leaders_win_->Pen(ScrollView::PINK);
332  leaders_win_->Rectangle(box.left(), box.bottom(),
333  box.right(), box.top());
334  }
335  #endif // GRAPHICS_DISABLED
336  ColPartition::MakeBigPartition(bbox, big_part_list);
337  }
338  }
339 }
340 
341 // Types all the blobs as vertical text or horizontal text or unknown and
342 // puts them into initial ColPartitions in the supplied part_grid.
343 // rerotation determines how to get back to the image coordinates from the
344 // blob coordinates (since they may have been rotated for vertical text).
345 // block is the single block for the whole page or rectangle to be OCRed.
346 // nontext_pix (full-size), is a binary mask used to prevent merges across
347 // photo/text boundaries. It is not kept beyond this function.
348 // denorm provides a mapping back to the image from the current blob
349 // coordinate space.
350 // projection provides a measure of textline density over the image and
351 // provides functions to assist with diacritic detection. It should be a
352 // pointer to a new TextlineProjection, and will be setup here.
353 // part_grid is the output grid of textline partitions.
354 // Large blobs that cause overlap are put in separate partitions and added
355 // to the big_parts list.
357  TO_BLOCK* block,
358  Pix* nontext_pix,
359  const DENORM* denorm,
360  TextlineProjection* projection,
361  ColPartitionGrid* part_grid,
362  ColPartition_LIST* big_parts) {
363  nontext_map_ = nontext_pix;
364  projection_ = projection;
365  denorm_ = denorm;
366  // Clear and re Insert to take advantage of the tab stops in the blobs.
367  Clear();
368  // Setup the strokewidth grid with the remaining non-noise, non-leader blobs.
369  InsertBlobs(block);
370 
371  // Run FixBrokenCJK() again if the page is rotated and the blobs
372  // lists are reset and re-flitered, because we may have some new
373  // blobs in the medium blob list.
374  if (rerotation_.x() != 1.0f || rerotation_.y() != 0.0f) {
375  FixBrokenCJK(block);
376  }
377  FindTextlineFlowDirection(true);
378  projection_->ConstructProjection(block, rerotation, nontext_map_);
380  ScrollView* line_blobs_win = MakeWindow(0, 0, "Initial textline Blobs");
381  projection_->PlotGradedBlobs(&block->blobs, line_blobs_win);
382  projection_->PlotGradedBlobs(&block->small_blobs, line_blobs_win);
383  }
384  projection_->MoveNonTextlineBlobs(&block->blobs, &block->noise_blobs);
385  projection_->MoveNonTextlineBlobs(&block->small_blobs, &block->noise_blobs);
386  // Clear and re Insert to take advantage of the removed diacritics.
387  Clear();
388  InsertBlobs(block);
389  FindInitialPartitions(rerotation, block, part_grid, big_parts);
390  nontext_map_ = NULL;
391  projection_ = NULL;
392  denorm_ = NULL;
393 }
394 
395 static void PrintBoxWidths(BLOBNBOX* neighbour) {
396  TBOX nbox = neighbour->bounding_box();
397  tprintf("Box (%d,%d)->(%d,%d): h-width=%.1f, v-width=%.1f p-width=%1.f\n",
398  nbox.left(), nbox.bottom(), nbox.right(), nbox.top(),
399  neighbour->horz_stroke_width(), neighbour->vert_stroke_width(),
400  2.0 * neighbour->cblob()->area()/neighbour->cblob()->perimeter());
401 }
402 
404 void StrokeWidth::HandleClick(int x, int y) {
406  // Run a radial search for blobs that overlap.
407  BlobGridSearch radsearch(this);
408  radsearch.StartRadSearch(x, y, 1);
409  BLOBNBOX* neighbour;
410  FCOORD click(static_cast<float>(x), static_cast<float>(y));
411  while ((neighbour = radsearch.NextRadSearch()) != NULL) {
412  TBOX nbox = neighbour->bounding_box();
413  if (nbox.contains(click) && neighbour->cblob() != NULL) {
414  PrintBoxWidths(neighbour);
415  if (neighbour->neighbour(BND_LEFT) != NULL)
416  PrintBoxWidths(neighbour->neighbour(BND_LEFT));
417  if (neighbour->neighbour(BND_RIGHT) != NULL)
418  PrintBoxWidths(neighbour->neighbour(BND_RIGHT));
419  if (neighbour->neighbour(BND_ABOVE) != NULL)
420  PrintBoxWidths(neighbour->neighbour(BND_ABOVE));
421  if (neighbour->neighbour(BND_BELOW) != NULL)
422  PrintBoxWidths(neighbour->neighbour(BND_BELOW));
423  int gaps[BND_COUNT];
424  neighbour->NeighbourGaps(gaps);
425  tprintf("Left gap=%d, right=%d, above=%d, below=%d, horz=%d, vert=%d\n"
426  "Good= %d %d %d %d\n",
427  gaps[BND_LEFT], gaps[BND_RIGHT],
428  gaps[BND_ABOVE], gaps[BND_BELOW],
429  neighbour->horz_possible(),
430  neighbour->vert_possible(),
431  neighbour->good_stroke_neighbour(BND_LEFT),
432  neighbour->good_stroke_neighbour(BND_RIGHT),
433  neighbour->good_stroke_neighbour(BND_ABOVE),
434  neighbour->good_stroke_neighbour(BND_BELOW));
435  break;
436  }
437  }
438 }
439 
440 // Detects and marks leader dots/dashes.
441 // Leaders are horizontal chains of small or noise blobs that look
442 // monospace according to ColPartition::MarkAsLeaderIfMonospaced().
443 // Detected leaders become the only occupants of the block->small_blobs list.
444 // Non-leader small blobs get moved to the blobs list.
445 // Non-leader noise blobs remain singletons in the noise list.
446 // All small and noise blobs in high density regions are marked BTFT_NONTEXT.
447 // block is the single block for the whole page or rectangle to be OCRed.
448 // leader_parts is the output.
449 void StrokeWidth::FindLeadersAndMarkNoise(TO_BLOCK* block,
450  ColPartition_LIST* leader_parts) {
451  InsertBlobList(&block->small_blobs);
452  InsertBlobList(&block->noise_blobs);
453  BlobGridSearch gsearch(this);
454  BLOBNBOX* bbox;
455  // For every bbox in the grid, set its neighbours.
456  gsearch.StartFullSearch();
457  while ((bbox = gsearch.NextFullSearch()) != NULL) {
458  SetNeighbours(true, false, bbox);
459  }
460  ColPartition_IT part_it(leader_parts);
461  gsearch.StartFullSearch();
462  while ((bbox = gsearch.NextFullSearch()) != NULL) {
463  if (bbox->flow() == BTFT_NONE) {
464  if (bbox->neighbour(BND_RIGHT) == NULL &&
465  bbox->neighbour(BND_LEFT) == NULL)
466  continue;
467  // Put all the linked blobs into a ColPartition.
468  ColPartition* part = new ColPartition(BRT_UNKNOWN, ICOORD(0, 1));
469  BLOBNBOX* blob;
470  for (blob = bbox; blob != NULL && blob->flow() == BTFT_NONE;
471  blob = blob->neighbour(BND_RIGHT))
472  part->AddBox(blob);
473  for (blob = bbox->neighbour(BND_LEFT); blob != NULL &&
474  blob->flow() == BTFT_NONE;
475  blob = blob->neighbour(BND_LEFT))
476  part->AddBox(blob);
477  if (part->MarkAsLeaderIfMonospaced())
478  part_it.add_after_then_move(part);
479  else
480  delete part;
481  }
482  }
484  leaders_win_ = DisplayGoodBlobs("LeaderNeighbours", 0, 0);
485  }
486  // Move any non-leaders from the small to the blobs list, as they are
487  // most likely dashes or broken characters.
488  BLOBNBOX_IT blob_it(&block->blobs);
489  BLOBNBOX_IT small_it(&block->small_blobs);
490  for (small_it.mark_cycle_pt(); !small_it.cycled_list(); small_it.forward()) {
491  BLOBNBOX* blob = small_it.data();
492  if (blob->flow() != BTFT_LEADER) {
493  if (blob->flow() == BTFT_NEIGHBOURS)
494  blob->set_flow(BTFT_NONE);
495  blob->ClearNeighbours();
496  blob_it.add_to_end(small_it.extract());
497  }
498  }
499  // Move leaders from the noise list to the small list, leaving the small
500  // list exclusively leaders, so they don't get processed further,
501  // and the remaining small blobs all in the noise list.
502  BLOBNBOX_IT noise_it(&block->noise_blobs);
503  for (noise_it.mark_cycle_pt(); !noise_it.cycled_list(); noise_it.forward()) {
504  BLOBNBOX* blob = noise_it.data();
505  if (blob->flow() == BTFT_LEADER || blob->joined_to_prev()) {
506  small_it.add_to_end(noise_it.extract());
507  } else if (blob->flow() == BTFT_NEIGHBOURS) {
508  blob->set_flow(BTFT_NONE);
509  blob->ClearNeighbours();
510  }
511  }
512  // Clear the grid as we don't want the small stuff hanging around in it.
513  Clear();
514 }
515 
518 void StrokeWidth::InsertBlobs(TO_BLOCK* block) {
519  InsertBlobList(&block->blobs);
520  InsertBlobList(&block->large_blobs);
521 }
522 
523 // Checks the left or right side of the given leader partition and sets the
524 // (opposite) leader_on_right or leader_on_left flags for blobs
525 // that are next to the given side of the given leader partition.
526 void StrokeWidth::MarkLeaderNeighbours(const ColPartition* part,
527  LeftOrRight side) {
528  const TBOX& part_box = part->bounding_box();
529  BlobGridSearch blobsearch(this);
530  // Search to the side of the leader for the nearest neighbour.
531  BLOBNBOX* best_blob = NULL;
532  int best_gap = 0;
533  blobsearch.StartSideSearch(side == LR_LEFT ? part_box.left()
534  : part_box.right(),
535  part_box.bottom(), part_box.top());
536  BLOBNBOX* blob;
537  while ((blob = blobsearch.NextSideSearch(side == LR_LEFT)) != NULL) {
538  const TBOX& blob_box = blob->bounding_box();
539  if (!blob_box.y_overlap(part_box))
540  continue;
541  int x_gap = blob_box.x_gap(part_box);
542  if (x_gap > 2 * gridsize()) {
543  break;
544  } else if (best_blob == NULL || x_gap < best_gap) {
545  best_blob = blob;
546  best_gap = x_gap;
547  }
548  }
549  if (best_blob != NULL) {
550  if (side == LR_LEFT)
551  best_blob->set_leader_on_right(true);
552  else
553  best_blob->set_leader_on_left(true);
554  #ifndef GRAPHICS_DISABLED
555  if (leaders_win_ != NULL) {
556  leaders_win_->Pen(side == LR_LEFT ? ScrollView::RED : ScrollView::GREEN);
557  const TBOX& blob_box = best_blob->bounding_box();
558  leaders_win_->Rectangle(blob_box.left(), blob_box.bottom(),
559  blob_box.right(), blob_box.top());
560  }
561  #endif // GRAPHICS_DISABLED
562  }
563 }
564 
565 // Helper to compute the UQ of the square-ish CJK charcters.
566 static int UpperQuartileCJKSize(int gridsize, BLOBNBOX_LIST* blobs) {
567  STATS sizes(0, gridsize * kMaxCJKSizeRatio);
568  BLOBNBOX_IT it(blobs);
569  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
570  BLOBNBOX* blob = it.data();
571  int width = blob->bounding_box().width();
572  int height = blob->bounding_box().height();
573  if (width <= height * kCJKAspectRatio && height < width * kCJKAspectRatio)
574  sizes.add(height, 1);
575  }
576  return static_cast<int>(sizes.ile(0.75f) + 0.5);
577 }
578 
579 // Fix broken CJK characters, using the fake joined blobs mechanism.
580 // Blobs are really merged, ie the master takes all the outlines and the
581 // others are deleted.
582 // Returns true if sufficient blobs are merged that it may be worth running
583 // again, due to a better estimate of character size.
584 bool StrokeWidth::FixBrokenCJK(TO_BLOCK* block) {
585  BLOBNBOX_LIST* blobs = &block->blobs;
586  int median_height = UpperQuartileCJKSize(gridsize(), blobs);
587  int max_dist = static_cast<int>(median_height * kCJKBrokenDistanceFraction);
588  int max_size = static_cast<int>(median_height * kCJKAspectRatio);
589  int num_fixed = 0;
590  BLOBNBOX_IT blob_it(blobs);
591 
592  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
593  BLOBNBOX* blob = blob_it.data();
594  if (blob->cblob() == NULL || blob->cblob()->out_list()->empty())
595  continue;
596  TBOX bbox = blob->bounding_box();
597  bool debug = AlignedBlob::WithinTestRegion(3, bbox.left(),
598  bbox.bottom());
599  if (debug) {
600  tprintf("Checking for Broken CJK (max size=%d):", max_size);
601  bbox.print();
602  }
603  // Generate a list of blobs that overlap or are near enough to merge.
604  BLOBNBOX_CLIST overlapped_blobs;
605  AccumulateOverlaps(blob, debug, max_size, max_dist,
606  &bbox, &overlapped_blobs);
607  if (!overlapped_blobs.empty()) {
608  // There are overlapping blobs, so qualify them as being satisfactory
609  // before removing them from the grid and replacing them with the union.
610  // The final box must be roughly square.
611  if (bbox.width() > bbox.height() * kCJKAspectRatio ||
612  bbox.height() > bbox.width() * kCJKAspectRatio) {
613  if (debug) {
614  tprintf("Bad final aspectratio:");
615  bbox.print();
616  }
617  continue;
618  }
619  // There can't be too many blobs to merge.
620  if (overlapped_blobs.length() >= kCJKMaxComponents) {
621  if (debug)
622  tprintf("Too many neighbours: %d\n", overlapped_blobs.length());
623  continue;
624  }
625  // The strokewidths must match amongst the join candidates.
626  BLOBNBOX_C_IT n_it(&overlapped_blobs);
627  for (n_it.mark_cycle_pt(); !n_it.cycled_list(); n_it.forward()) {
628  BLOBNBOX* neighbour = NULL;
629  neighbour = n_it.data();
630  if (!blob->MatchingStrokeWidth(*neighbour, kStrokeWidthFractionCJK,
632  break;
633  }
634  if (!n_it.cycled_list()) {
635  if (debug) {
636  tprintf("Bad stroke widths:");
637  PrintBoxWidths(blob);
638  }
639  continue; // Not good enough.
640  }
641 
642  // Merge all the candidates into blob.
643  // We must remove blob from the grid and reinsert it after merging
644  // to maintain the integrity of the grid.
645  RemoveBBox(blob);
646  // Everything else will be calculated later.
647  for (n_it.mark_cycle_pt(); !n_it.cycled_list(); n_it.forward()) {
648  BLOBNBOX* neighbour = n_it.data();
649  RemoveBBox(neighbour);
650  blob->really_merge(neighbour);
651  if (rerotation_.x() != 1.0f || rerotation_.y() != 0.0f) {
652  blob->rotate_box(rerotation_);
653  }
654  }
655  InsertBBox(true, true, blob);
656  ++num_fixed;
657  if (debug) {
658  tprintf("Done! Final box:");
659  bbox.print();
660  }
661  }
662  }
663  // Mark for deletion all the empty shell blobs that contain no outlines.
664  int num_remaining = 0;
665  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
666  BLOBNBOX* blob = blob_it.data();
667  if (blob->cblob() == NULL || blob->cblob()->out_list()->empty()) {
668  // Mark blob for deletion.
669  blob->set_region_type(BRT_NOISE);
670  } else {
671  ++num_remaining;
672  }
673  }
674  // Permanently delete all the marked blobs after first removing all
675  // references in the neighbour members.
676  block->DeleteUnownedNoise();
677  return num_fixed > num_remaining * kBrokenCJKIterationFraction;
678 }
679 
680 // Helper function to determine whether it is reasonable to merge the
681 // bbox and the nbox for repairing broken CJK.
682 // The distance apart must not exceed max_dist, the combined size must
683 // not exceed max_size, and the aspect ratio must either improve or at
684 // least not get worse by much.
685 static bool AcceptableCJKMerge(const TBOX& bbox, const TBOX& nbox,
686  bool debug, int max_size, int max_dist,
687  int* x_gap, int* y_gap) {
688  *x_gap = bbox.x_gap(nbox);
689  *y_gap = bbox.y_gap(nbox);
690  TBOX merged(nbox);
691  merged += bbox;
692  if (debug) {
693  tprintf("gaps = %d, %d, merged_box:", *x_gap, *y_gap);
694  merged.print();
695  }
696  if (*x_gap <= max_dist && *y_gap <= max_dist &&
697  merged.width() <= max_size && merged.height() <= max_size) {
698  // Close enough to call overlapping. Check aspect ratios.
699  double old_ratio = static_cast<double>(bbox.width()) / bbox.height();
700  if (old_ratio < 1.0) old_ratio = 1.0 / old_ratio;
701  double new_ratio = static_cast<double>(merged.width()) / merged.height();
702  if (new_ratio < 1.0) new_ratio = 1.0 / new_ratio;
703  if (new_ratio <= old_ratio * kCJKAspectRatioIncrease)
704  return true;
705  }
706  return false;
707 }
708 
709 // Collect blobs that overlap or are within max_dist of the input bbox.
710 // Return them in the list of blobs and expand the bbox to be the union
711 // of all the boxes. not_this is excluded from the search, as are blobs
712 // that cause the merged box to exceed max_size in either dimension.
713 void StrokeWidth::AccumulateOverlaps(const BLOBNBOX* not_this, bool debug,
714  int max_size, int max_dist,
715  TBOX* bbox, BLOBNBOX_CLIST* blobs) {
716  // While searching, nearests holds the nearest failed blob in each
717  // direction. When we have a nearest in each of the 4 directions, then
718  // the search is over, and at this point the final bbox must not overlap
719  // any of the nearests.
720  BLOBNBOX* nearests[BND_COUNT];
721  for (int i = 0; i < BND_COUNT; ++i) {
722  nearests[i] = NULL;
723  }
724  int x = (bbox->left() + bbox->right()) / 2;
725  int y = (bbox->bottom() + bbox->top()) / 2;
726  // Run a radial search for blobs that overlap or are sufficiently close.
727  BlobGridSearch radsearch(this);
728  radsearch.StartRadSearch(x, y, kCJKRadius);
729  BLOBNBOX* neighbour;
730  while ((neighbour = radsearch.NextRadSearch()) != NULL) {
731  if (neighbour == not_this) continue;
732  TBOX nbox = neighbour->bounding_box();
733  int x_gap, y_gap;
734  if (AcceptableCJKMerge(*bbox, nbox, debug, max_size, max_dist,
735  &x_gap, &y_gap)) {
736  // Close enough to call overlapping. Merge boxes.
737  *bbox += nbox;
738  blobs->add_sorted(SortByBoxLeft<BLOBNBOX>, true, neighbour);
739  if (debug) {
740  tprintf("Added:");
741  nbox.print();
742  }
743  // Since we merged, search the nearests, as some might now me mergeable.
744  for (int dir = 0; dir < BND_COUNT; ++dir) {
745  if (nearests[dir] == NULL) continue;
746  nbox = nearests[dir]->bounding_box();
747  if (AcceptableCJKMerge(*bbox, nbox, debug, max_size,
748  max_dist, &x_gap, &y_gap)) {
749  // Close enough to call overlapping. Merge boxes.
750  *bbox += nbox;
751  blobs->add_sorted(SortByBoxLeft<BLOBNBOX>, true, nearests[dir]);
752  if (debug) {
753  tprintf("Added:");
754  nbox.print();
755  }
756  nearests[dir] = NULL;
757  dir = -1; // Restart the search.
758  }
759  }
760  } else if (x_gap < 0 && x_gap <= y_gap) {
761  // A vertical neighbour. Record the nearest.
762  BlobNeighbourDir dir = nbox.top() > bbox->top() ? BND_ABOVE : BND_BELOW;
763  if (nearests[dir] == NULL ||
764  y_gap < bbox->y_gap(nearests[dir]->bounding_box())) {
765  nearests[dir] = neighbour;
766  }
767  } else if (y_gap < 0 && y_gap <= x_gap) {
768  // A horizontal neighbour. Record the nearest.
769  BlobNeighbourDir dir = nbox.left() > bbox->left() ? BND_RIGHT : BND_LEFT;
770  if (nearests[dir] == NULL ||
771  x_gap < bbox->x_gap(nearests[dir]->bounding_box())) {
772  nearests[dir] = neighbour;
773  }
774  }
775  // If all nearests are non-null, then we have finished.
776  if (nearests[BND_LEFT] && nearests[BND_RIGHT] &&
777  nearests[BND_ABOVE] && nearests[BND_BELOW])
778  break;
779  }
780  // Final overlap with a nearest is not allowed.
781  for (int dir = 0; dir < BND_COUNT; ++dir) {
782  if (nearests[dir] == NULL) continue;
783  const TBOX& nbox = nearests[dir]->bounding_box();
784  if (debug) {
785  tprintf("Testing for overlap with:");
786  nbox.print();
787  }
788  if (bbox->overlap(nbox)) {
789  blobs->shallow_clear();
790  if (debug)
791  tprintf("Final box overlaps nearest\n");
792  return;
793  }
794  }
795 }
796 
797 // For each blob in this grid, Finds the textline direction to be horizontal
798 // or vertical according to distance to neighbours and 1st and 2nd order
799 // neighbours. Non-text tends to end up without a definite direction.
800 // Result is setting of the neighbours and vert_possible/horz_possible
801 // flags in the BLOBNBOXes currently in this grid.
802 // This function is called more than once if page orientation is uncertain,
803 // so display_if_debugging is true on the final call to display the results.
804 void StrokeWidth::FindTextlineFlowDirection(bool display_if_debugging) {
805  BlobGridSearch gsearch(this);
806  BLOBNBOX* bbox;
807  // For every bbox in the grid, set its neighbours.
808  gsearch.StartFullSearch();
809  while ((bbox = gsearch.NextFullSearch()) != NULL) {
810  SetNeighbours(false, display_if_debugging, bbox);
811  }
812  // Where vertical or horizontal wins by a big margin, clarify it.
813  gsearch.StartFullSearch();
814  while ((bbox = gsearch.NextFullSearch()) != NULL) {
815  SimplifyObviousNeighbours(bbox);
816  }
817  // Now try to make the blobs only vertical or horizontal using neighbours.
818  gsearch.StartFullSearch();
819  while ((bbox = gsearch.NextFullSearch()) != NULL) {
820  SetNeighbourFlows(bbox);
821  }
822  if ((textord_tabfind_show_strokewidths && display_if_debugging) ||
824  initial_widths_win_ = DisplayGoodBlobs("InitialStrokewidths", 400, 0);
825  }
826  // Improve flow direction with neighbours.
827  gsearch.StartFullSearch();
828  while ((bbox = gsearch.NextFullSearch()) != NULL) {
829  SmoothNeighbourTypes(bbox, false);
830  }
831  // Now allow reset of firm values to fix renegades.
832  gsearch.StartFullSearch();
833  while ((bbox = gsearch.NextFullSearch()) != NULL) {
834  SmoothNeighbourTypes(bbox, true);
835  }
836  // Repeat.
837  gsearch.StartFullSearch();
838  while ((bbox = gsearch.NextFullSearch()) != NULL) {
839  SmoothNeighbourTypes(bbox, true);
840  }
841  if ((textord_tabfind_show_strokewidths && display_if_debugging) ||
843  widths_win_ = DisplayGoodBlobs("ImprovedStrokewidths", 800, 0);
844  }
845 }
846 
847 // Sets the neighbours and good_stroke_neighbours members of the blob by
848 // searching close on all 4 sides.
849 // When finding leader dots/dashes, there is a slightly different rule for
850 // what makes a good neighbour.
851 void StrokeWidth::SetNeighbours(bool leaders, bool activate_line_trap,
852  BLOBNBOX* blob) {
853  int line_trap_count = 0;
854  for (int dir = 0; dir < BND_COUNT; ++dir) {
855  BlobNeighbourDir bnd = static_cast<BlobNeighbourDir>(dir);
856  line_trap_count += FindGoodNeighbour(bnd, leaders, blob);
857  }
858  if (line_trap_count > 0 && activate_line_trap) {
859  // It looks like a line so isolate it by clearing its neighbours.
860  blob->ClearNeighbours();
861  const TBOX& box = blob->bounding_box();
862  blob->set_region_type(box.width() > box.height() ? BRT_HLINE : BRT_VLINE);
863  }
864 }
865 
866 
867 // Sets the good_stroke_neighbours member of the blob if it has a
868 // GoodNeighbour on the given side.
869 // Also sets the neighbour in the blob, whether or not a good one is found.
870 // Returns the number of blobs in the nearby search area that would lead us to
871 // believe that this blob is a line separator.
872 // Leaders get extra special lenient treatment.
873 int StrokeWidth::FindGoodNeighbour(BlobNeighbourDir dir, bool leaders,
874  BLOBNBOX* blob) {
875  // Search for neighbours that overlap vertically.
876  TBOX blob_box = blob->bounding_box();
877  bool debug = AlignedBlob::WithinTestRegion(2, blob_box.left(),
878  blob_box.bottom());
879  if (debug) {
880  tprintf("FGN in dir %d for blob:", dir);
881  blob_box.print();
882  }
883  int top = blob_box.top();
884  int bottom = blob_box.bottom();
885  int left = blob_box.left();
886  int right = blob_box.right();
887  int width = right - left;
888  int height = top - bottom;
889 
890  // A trap to detect lines tests for the min dimension of neighbours
891  // being larger than a multiple of the min dimension of the line
892  // and the larger dimension being smaller than a fraction of the max
893  // dimension of the line.
894  int line_trap_max = MAX(width, height) / kLineTrapLongest;
895  int line_trap_min = MIN(width, height) * kLineTrapShortest;
896  int line_trap_count = 0;
897 
898  int min_good_overlap = (dir == BND_LEFT || dir == BND_RIGHT)
899  ? height / 2 : width / 2;
900  int min_decent_overlap = (dir == BND_LEFT || dir == BND_RIGHT)
901  ? height / 3 : width / 3;
902  if (leaders)
903  min_good_overlap = min_decent_overlap = 1;
904 
905  int search_pad = static_cast<int>(
906  sqrt(static_cast<double>(width * height)) * kNeighbourSearchFactor);
907  if (gridsize() > search_pad)
908  search_pad = gridsize();
909  TBOX search_box = blob_box;
910  // Pad the search in the appropriate direction.
911  switch (dir) {
912  case BND_LEFT:
913  search_box.set_left(search_box.left() - search_pad);
914  break;
915  case BND_RIGHT:
916  search_box.set_right(search_box.right() + search_pad);
917  break;
918  case BND_BELOW:
919  search_box.set_bottom(search_box.bottom() - search_pad);
920  break;
921  case BND_ABOVE:
922  search_box.set_top(search_box.top() + search_pad);
923  break;
924  case BND_COUNT:
925  return 0;
926  }
927 
928  BlobGridSearch rectsearch(this);
929  rectsearch.StartRectSearch(search_box);
930  BLOBNBOX* best_neighbour = NULL;
931  double best_goodness = 0.0;
932  bool best_is_good = false;
933  BLOBNBOX* neighbour;
934  while ((neighbour = rectsearch.NextRectSearch()) != NULL) {
935  TBOX nbox = neighbour->bounding_box();
936  if (neighbour == blob)
937  continue;
938  int mid_x = (nbox.left() + nbox.right()) / 2;
939  if (mid_x < blob->left_rule() || mid_x > blob->right_rule())
940  continue; // In a different column.
941  if (debug) {
942  tprintf("Neighbour at:");
943  nbox.print();
944  }
945 
946  // Last-minute line detector. There is a small upper limit to the line
947  // width accepted by the morphological line detector.
948  int n_width = nbox.width();
949  int n_height = nbox.height();
950  if (MIN(n_width, n_height) > line_trap_min &&
951  MAX(n_width, n_height) < line_trap_max)
952  ++line_trap_count;
953  // Heavily joined text, such as Arabic may have very different sizes when
954  // looking at the maxes, but the heights may be almost identical, so check
955  // for a difference in height if looking sideways or width vertically.
956  if (TabFind::VeryDifferentSizes(MAX(n_width, n_height),
957  MAX(width, height)) &&
958  (((dir == BND_LEFT || dir ==BND_RIGHT) &&
959  TabFind::DifferentSizes(n_height, height)) ||
960  ((dir == BND_BELOW || dir ==BND_ABOVE) &&
961  TabFind::DifferentSizes(n_width, width)))) {
962  if (debug) tprintf("Bad size\n");
963  continue; // Could be a different font size or non-text.
964  }
965  // Amount of vertical overlap between the blobs.
966  int overlap;
967  // If the overlap is along the short side of the neighbour, and it
968  // is fully overlapped, then perp_overlap holds the length of the long
969  // side of the neighbour. A measure to include hyphens and dashes as
970  // legitimate neighbours.
971  int perp_overlap;
972  int gap;
973  if (dir == BND_LEFT || dir == BND_RIGHT) {
974  overlap = MIN(nbox.top(), top) - MAX(nbox.bottom(), bottom);
975  if (overlap == nbox.height() && nbox.width() > nbox.height())
976  perp_overlap = nbox.width();
977  else
978  perp_overlap = overlap;
979  gap = dir == BND_LEFT ? left - nbox.left() : nbox.right() - right;
980  if (gap <= 0) {
981  if (debug) tprintf("On wrong side\n");
982  continue; // On the wrong side.
983  }
984  gap -= n_width;
985  } else {
986  overlap = MIN(nbox.right(), right) - MAX(nbox.left(), left);
987  if (overlap == nbox.width() && nbox.height() > nbox.width())
988  perp_overlap = nbox.height();
989  else
990  perp_overlap = overlap;
991  gap = dir == BND_BELOW ? bottom - nbox.bottom() : nbox.top() - top;
992  if (gap <= 0) {
993  if (debug) tprintf("On wrong side\n");
994  continue; // On the wrong side.
995  }
996  gap -= n_height;
997  }
998  if (-gap > overlap) {
999  if (debug) tprintf("Overlaps wrong way\n");
1000  continue; // Overlaps the wrong way.
1001  }
1002  if (perp_overlap < min_decent_overlap) {
1003  if (debug) tprintf("Doesn't overlap enough\n");
1004  continue; // Doesn't overlap enough.
1005  }
1006  bool bad_sizes = TabFind::DifferentSizes(height, n_height) &&
1007  TabFind::DifferentSizes(width, n_width);
1008  bool is_good = overlap >= min_good_overlap && !bad_sizes &&
1009  blob->MatchingStrokeWidth(*neighbour,
1012  // Best is a fuzzy combination of gap, overlap and is good.
1013  // Basically if you make one thing twice as good without making
1014  // anything else twice as bad, then it is better.
1015  if (gap < 1) gap = 1;
1016  double goodness = (1.0 + is_good) * overlap / gap;
1017  if (debug) {
1018  tprintf("goodness = %g vs best of %g, good=%d, overlap=%d, gap=%d\n",
1019  goodness, best_goodness, is_good, overlap, gap);
1020  }
1021  if (goodness > best_goodness) {
1022  best_neighbour = neighbour;
1023  best_goodness = goodness;
1024  best_is_good = is_good;
1025  }
1026  }
1027  blob->set_neighbour(dir, best_neighbour, best_is_good);
1028  return line_trap_count;
1029 }
1030 
1031 // Helper to get a list of 1st-order neighbours.
1032 static void ListNeighbours(const BLOBNBOX* blob,
1033  BLOBNBOX_CLIST* neighbours) {
1034  for (int dir = 0; dir < BND_COUNT; ++dir) {
1035  BlobNeighbourDir bnd = static_cast<BlobNeighbourDir>(dir);
1036  BLOBNBOX* neighbour = blob->neighbour(bnd);
1037  if (neighbour != NULL) {
1038  neighbours->add_sorted(SortByBoxLeft<BLOBNBOX>, true, neighbour);
1039  }
1040  }
1041 }
1042 
1043 // Helper to get a list of 1st and 2nd order neighbours.
1044 static void List2ndNeighbours(const BLOBNBOX* blob,
1045  BLOBNBOX_CLIST* neighbours) {
1046  ListNeighbours(blob, neighbours);
1047  for (int dir = 0; dir < BND_COUNT; ++dir) {
1048  BlobNeighbourDir bnd = static_cast<BlobNeighbourDir>(dir);
1049  BLOBNBOX* neighbour = blob->neighbour(bnd);
1050  if (neighbour != NULL) {
1051  ListNeighbours(neighbour, neighbours);
1052  }
1053  }
1054 }
1055 
1056 // Helper to get a list of 1st, 2nd and 3rd order neighbours.
1057 static void List3rdNeighbours(const BLOBNBOX* blob,
1058  BLOBNBOX_CLIST* neighbours) {
1059  List2ndNeighbours(blob, neighbours);
1060  for (int dir = 0; dir < BND_COUNT; ++dir) {
1061  BlobNeighbourDir bnd = static_cast<BlobNeighbourDir>(dir);
1062  BLOBNBOX* neighbour = blob->neighbour(bnd);
1063  if (neighbour != NULL) {
1064  List2ndNeighbours(neighbour, neighbours);
1065  }
1066  }
1067 }
1068 
1069 // Helper to count the evidence for verticalness or horizontalness
1070 // in a list of neighbours.
1071 static void CountNeighbourGaps(bool debug, BLOBNBOX_CLIST* neighbours,
1072  int* pure_h_count, int* pure_v_count) {
1073  if (neighbours->length() <= kMostlyOneDirRatio)
1074  return;
1075  BLOBNBOX_C_IT it(neighbours);
1076  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1077  BLOBNBOX* blob = it.data();
1078  int h_min, h_max, v_min, v_max;
1079  blob->MinMaxGapsClipped(&h_min, &h_max, &v_min, &v_max);
1080  if (debug)
1081  tprintf("Hgaps [%d,%d], vgaps [%d,%d]:", h_min, h_max, v_min, v_max);
1082  if (h_max < v_min ||
1083  blob->leader_on_left() || blob->leader_on_right()) {
1084  // Horizontal gaps are clear winners. Count a pure horizontal.
1085  ++*pure_h_count;
1086  if (debug) tprintf("Horz at:");
1087  } else if (v_max < h_min) {
1088  // Vertical gaps are clear winners. Clear a pure vertical.
1089  ++*pure_v_count;
1090  if (debug) tprintf("Vert at:");
1091  } else {
1092  if (debug) tprintf("Neither at:");
1093  }
1094  if (debug)
1095  blob->bounding_box().print();
1096  }
1097 }
1098 
1099 // Makes the blob to be only horizontal or vertical where evidence
1100 // is clear based on gaps of 2nd order neighbours, or definite individual
1101 // blobs.
1102 void StrokeWidth::SetNeighbourFlows(BLOBNBOX* blob) {
1103  if (blob->DefiniteIndividualFlow())
1104  return;
1105  bool debug = AlignedBlob::WithinTestRegion(2, blob->bounding_box().left(),
1106  blob->bounding_box().bottom());
1107  if (debug) {
1108  tprintf("SetNeighbourFlows (current flow=%d, type=%d) on:",
1109  blob->flow(), blob->region_type());
1110  blob->bounding_box().print();
1111  }
1112  BLOBNBOX_CLIST neighbours;
1113  List3rdNeighbours(blob, &neighbours);
1114  // The number of pure horizontal and vertical neighbours.
1115  int pure_h_count = 0;
1116  int pure_v_count = 0;
1117  CountNeighbourGaps(debug, &neighbours, &pure_h_count, &pure_v_count);
1118  if (debug) {
1119  HandleClick(blob->bounding_box().left() + 1,
1120  blob->bounding_box().bottom() + 1);
1121  tprintf("SetFlows: h_count=%d, v_count=%d\n",
1122  pure_h_count, pure_v_count);
1123  }
1124  if (!neighbours.empty()) {
1125  blob->set_vert_possible(true);
1126  blob->set_horz_possible(true);
1127  if (pure_h_count > 2 * pure_v_count) {
1128  // Horizontal gaps are clear winners. Clear vertical neighbours.
1129  blob->set_vert_possible(false);
1130  } else if (pure_v_count > 2 * pure_h_count) {
1131  // Vertical gaps are clear winners. Clear horizontal neighbours.
1132  blob->set_horz_possible(false);
1133  }
1134  } else {
1135  // Lonely blob. Can't tell its flow direction.
1136  blob->set_vert_possible(false);
1137  blob->set_horz_possible(false);
1138  }
1139 }
1140 
1141 
1142 // Helper to count the number of horizontal and vertical blobs in a list.
1143 static void CountNeighbourTypes(BLOBNBOX_CLIST* neighbours,
1144  int* pure_h_count, int* pure_v_count) {
1145  BLOBNBOX_C_IT it(neighbours);
1146  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1147  BLOBNBOX* blob = it.data();
1148  if (blob->UniquelyHorizontal())
1149  ++*pure_h_count;
1150  if (blob->UniquelyVertical())
1151  ++*pure_v_count;
1152  }
1153 }
1154 
1155 // Nullify the neighbours in the wrong directions where the direction
1156 // is clear-cut based on a distance margin. Good for isolating vertical
1157 // text from neighbouring horizontal text.
1158 void StrokeWidth::SimplifyObviousNeighbours(BLOBNBOX* blob) {
1159  // Case 1: We have text that is likely several characters, blurry and joined
1160  // together.
1161  if ((blob->bounding_box().width() > 3 * blob->area_stroke_width() &&
1162  blob->bounding_box().height() > 3 * blob->area_stroke_width())) {
1163  // The blob is complex (not stick-like).
1164  if (blob->bounding_box().width() > 4 * blob->bounding_box().height()) {
1165  // Horizontal conjoined text.
1166  blob->set_neighbour(BND_ABOVE, NULL, false);
1167  blob->set_neighbour(BND_BELOW, NULL, false);
1168  return;
1169  }
1170  if (blob->bounding_box().height() > 4 * blob->bounding_box().width()) {
1171  // Vertical conjoined text.
1172  blob->set_neighbour(BND_LEFT, NULL, false);
1173  blob->set_neighbour(BND_RIGHT, NULL, false);
1174  return;
1175  }
1176  }
1177 
1178  // Case 2: This blob is likely a single character.
1179  int margin = gridsize() / 2;
1180  int h_min, h_max, v_min, v_max;
1181  blob->MinMaxGapsClipped(&h_min, &h_max, &v_min, &v_max);
1182  if ((h_max + margin < v_min && h_max < margin / 2) ||
1183  blob->leader_on_left() || blob->leader_on_right()) {
1184  // Horizontal gaps are clear winners. Clear vertical neighbours.
1185  blob->set_neighbour(BND_ABOVE, NULL, false);
1186  blob->set_neighbour(BND_BELOW, NULL, false);
1187  } else if (v_max + margin < h_min && v_max < margin / 2) {
1188  // Vertical gaps are clear winners. Clear horizontal neighbours.
1189  blob->set_neighbour(BND_LEFT, NULL, false);
1190  blob->set_neighbour(BND_RIGHT, NULL, false);
1191  }
1192 }
1193 
1194 // Smoothes the vertical/horizontal type of the blob based on the
1195 // 2nd-order neighbours. If reset_all is true, then all blobs are
1196 // changed. Otherwise, only ambiguous blobs are processed.
1197 void StrokeWidth::SmoothNeighbourTypes(BLOBNBOX* blob, bool reset_all) {
1198  if ((blob->vert_possible() && blob->horz_possible()) || reset_all) {
1199  // There are both horizontal and vertical so try to fix it.
1200  BLOBNBOX_CLIST neighbours;
1201  List2ndNeighbours(blob, &neighbours);
1202  // The number of pure horizontal and vertical neighbours.
1203  int pure_h_count = 0;
1204  int pure_v_count = 0;
1205  CountNeighbourTypes(&neighbours, &pure_h_count, &pure_v_count);
1207  blob->bounding_box().bottom())) {
1208  HandleClick(blob->bounding_box().left() + 1,
1209  blob->bounding_box().bottom() + 1);
1210  tprintf("pure_h=%d, pure_v=%d\n",
1211  pure_h_count, pure_v_count);
1212  }
1213  if (pure_h_count > pure_v_count) {
1214  // Horizontal gaps are clear winners. Clear vertical neighbours.
1215  blob->set_vert_possible(false);
1216  blob->set_horz_possible(true);
1217  } else if (pure_v_count > pure_h_count) {
1218  // Vertical gaps are clear winners. Clear horizontal neighbours.
1219  blob->set_horz_possible(false);
1220  blob->set_vert_possible(true);
1221  }
1222  } else if (AlignedBlob::WithinTestRegion(2, blob->bounding_box().left(),
1223  blob->bounding_box().bottom())) {
1224  HandleClick(blob->bounding_box().left() + 1,
1225  blob->bounding_box().bottom() + 1);
1226  tprintf("Clean on pass 3!\n");
1227  }
1228 }
1229 
1230 // Partition creation. Accumulates vertical and horizontal text chains,
1231 // puts the remaining blobs in as unknowns, and then merges/splits to
1232 // minimize overlap and smoothes the types with neighbours and the color
1233 // image if provided. rerotation is used to rotate the coordinate space
1234 // back to the nontext_map_ image.
1235 void StrokeWidth::FindInitialPartitions(const FCOORD& rerotation,
1236  TO_BLOCK* block,
1237  ColPartitionGrid* part_grid,
1238  ColPartition_LIST* big_parts) {
1239  FindVerticalTextChains(part_grid);
1240  FindHorizontalTextChains(part_grid);
1242  chains_win_ = MakeWindow(0, 400, "Initial text chains");
1243  part_grid->DisplayBoxes(chains_win_);
1244  projection_->DisplayProjection();
1245  }
1246  part_grid->SplitOverlappingPartitions(big_parts);
1247  EasyMerges(part_grid);
1248  RemoveLargeUnusedBlobs(block, part_grid, big_parts);
1249  TBOX grid_box(bleft(), tright());
1250  while (part_grid->GridSmoothNeighbours(BTFT_CHAIN, nontext_map_, grid_box,
1251  rerotation));
1252  while (part_grid->GridSmoothNeighbours(BTFT_NEIGHBOURS, nontext_map_,
1253  grid_box, rerotation));
1254  TestDiacritics(part_grid, block);
1255  MergeDiacritics(block, part_grid);
1257  textlines_win_ = MakeWindow(400, 400, "GoodTextline blobs");
1258  part_grid->DisplayBoxes(textlines_win_);
1259  diacritics_win_ = DisplayDiacritics("Diacritics", 0, 0, block);
1260  }
1261  PartitionRemainingBlobs(part_grid);
1262  part_grid->SplitOverlappingPartitions(big_parts);
1263  EasyMerges(part_grid);
1264  while (part_grid->GridSmoothNeighbours(BTFT_CHAIN, nontext_map_, grid_box,
1265  rerotation));
1266  while (part_grid->GridSmoothNeighbours(BTFT_NEIGHBOURS, nontext_map_,
1267  grid_box, rerotation));
1268  // Now eliminate strong stuff in a sea of the opposite.
1269  while (part_grid->GridSmoothNeighbours(BTFT_STRONG_CHAIN, nontext_map_,
1270  grid_box, rerotation));
1272  smoothed_win_ = MakeWindow(800, 400, "Smoothed blobs");
1273  part_grid->DisplayBoxes(smoothed_win_);
1274  }
1275 }
1276 
1277 // Helper verifies that blob's neighbour in direction dir is good to add to a
1278 // vertical text chain by returning the neighbour if it is not null, not owned,
1279 // and not uniquely horizontal, as well as its neighbour in the opposite
1280 // direction is blob.
1281 static BLOBNBOX* MutualUnusedVNeighbour(const BLOBNBOX* blob,
1282  BlobNeighbourDir dir) {
1283  BLOBNBOX* next_blob = blob->neighbour(dir);
1284  if (next_blob == NULL || next_blob->owner() != NULL ||
1285  next_blob->UniquelyHorizontal())
1286  return NULL;
1287  if (next_blob->neighbour(DirOtherWay(dir)) == blob)
1288  return next_blob;
1289  return NULL;
1290 }
1291 
1292 // Finds vertical chains of text-like blobs and puts them in ColPartitions.
1293 void StrokeWidth::FindVerticalTextChains(ColPartitionGrid* part_grid) {
1294  BlobGridSearch gsearch(this);
1295  BLOBNBOX* bbox;
1296  gsearch.StartFullSearch();
1297  while ((bbox = gsearch.NextFullSearch()) != NULL) {
1298  // Only process boxes that have no horizontal hope and have not yet
1299  // been included in a chain.
1300  BLOBNBOX* blob;
1301  if (bbox->owner() == NULL && bbox->UniquelyVertical() &&
1302  (blob = MutualUnusedVNeighbour(bbox, BND_ABOVE)) != NULL) {
1303  // Put all the linked blobs into a ColPartition.
1304  ColPartition* part = new ColPartition(BRT_VERT_TEXT, ICOORD(0, 1));
1305  part->AddBox(bbox);
1306  while (blob != NULL) {
1307  part->AddBox(blob);
1308  blob = MutualUnusedVNeighbour(blob, BND_ABOVE);
1309  }
1310  blob = MutualUnusedVNeighbour(bbox, BND_BELOW);
1311  while (blob != NULL) {
1312  part->AddBox(blob);
1313  blob = MutualUnusedVNeighbour(blob, BND_BELOW);
1314  }
1315  CompletePartition(part, part_grid);
1316  }
1317  }
1318 }
1319 
1320 // Helper verifies that blob's neighbour in direction dir is good to add to a
1321 // horizontal text chain by returning the neighbour if it is not null, not
1322 // owned, and not uniquely vertical, as well as its neighbour in the opposite
1323 // direction is blob.
1324 static BLOBNBOX* MutualUnusedHNeighbour(const BLOBNBOX* blob,
1325  BlobNeighbourDir dir) {
1326  BLOBNBOX* next_blob = blob->neighbour(dir);
1327  if (next_blob == NULL || next_blob->owner() != NULL ||
1328  next_blob->UniquelyVertical())
1329  return NULL;
1330  if (next_blob->neighbour(DirOtherWay(dir)) == blob)
1331  return next_blob;
1332  return NULL;
1333 }
1334 
1335 // Finds horizontal chains of text-like blobs and puts them in ColPartitions.
1336 void StrokeWidth::FindHorizontalTextChains(ColPartitionGrid* part_grid) {
1337  BlobGridSearch gsearch(this);
1338  BLOBNBOX* bbox;
1339  gsearch.StartFullSearch();
1340  while ((bbox = gsearch.NextFullSearch()) != NULL) {
1341  BLOBNBOX* blob;
1342  if (bbox->owner() == NULL && bbox->UniquelyHorizontal() &&
1343  (blob = MutualUnusedHNeighbour(bbox, BND_RIGHT)) != NULL) {
1344  // Put all the linked blobs into a ColPartition.
1345  ColPartition* part = new ColPartition(BRT_TEXT, ICOORD(0, 1));
1346  part->AddBox(bbox);
1347  while (blob != NULL) {
1348  part->AddBox(blob);
1349  blob = MutualUnusedHNeighbour(blob, BND_RIGHT);
1350  }
1351  blob = MutualUnusedHNeighbour(bbox, BND_LEFT);
1352  while (blob != NULL) {
1353  part->AddBox(blob);
1354  blob = MutualUnusedVNeighbour(blob, BND_LEFT);
1355  }
1356  CompletePartition(part, part_grid);
1357  }
1358  }
1359 }
1360 
1361 // Finds diacritics and saves their base character in the blob.
1362 // The objective is to move all diacritics to the noise_blobs list, so
1363 // they don't mess up early textline finding/merging, or force splits
1364 // on textlines that overlap a bit. Blobs that become diacritics must be
1365 // either part of no ColPartition (NULL owner) or in a small partition in
1366 // which ALL the blobs are diacritics, in which case the partition is
1367 // exploded (deleted) back to its blobs.
1368 void StrokeWidth::TestDiacritics(ColPartitionGrid* part_grid, TO_BLOCK* block) {
1369  BlobGrid small_grid(gridsize(), bleft(), tright());
1370  small_grid.InsertBlobList(&block->noise_blobs);
1371  small_grid.InsertBlobList(&block->blobs);
1372  int medium_diacritics = 0;
1373  int small_diacritics = 0;
1374  BLOBNBOX_IT small_it(&block->noise_blobs);
1375  for (small_it.mark_cycle_pt(); !small_it.cycled_list(); small_it.forward()) {
1376  BLOBNBOX* blob = small_it.data();
1377  if (blob->owner() == NULL && !blob->IsDiacritic() &&
1378  DiacriticBlob(&small_grid, blob)) {
1379  ++small_diacritics;
1380  }
1381  }
1382  BLOBNBOX_IT blob_it(&block->blobs);
1383  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
1384  BLOBNBOX* blob = blob_it.data();
1385  if (blob->IsDiacritic()) {
1386  small_it.add_to_end(blob_it.extract());
1387  continue; // Already a diacritic.
1388  }
1389  ColPartition* part = blob->owner();
1390  if (part == NULL && DiacriticBlob(&small_grid, blob)) {
1391  ++medium_diacritics;
1392  RemoveBBox(blob);
1393  small_it.add_to_end(blob_it.extract());
1394  } else if (part != NULL && !part->block_owned() &&
1395  part->boxes_count() < 3) {
1396  // We allow blobs in small partitions to become diacritics if ALL the
1397  // blobs in the partition qualify as we can then cleanly delete the
1398  // partition, turn all the blobs in it to diacritics and they can be
1399  // merged into the base character partition more easily than merging
1400  // the partitions.
1401  BLOBNBOX_C_IT box_it(part->boxes());
1402  for (box_it.mark_cycle_pt(); !box_it.cycled_list() &&
1403  DiacriticBlob(&small_grid, box_it.data());
1404  box_it.forward());
1405  if (box_it.cycled_list()) {
1406  // They are all good.
1407  while (!box_it.empty()) {
1408  // Liberate the blob from its partition so it can be treated
1409  // as a diacritic and merged explicitly with the base part.
1410  // The blob is really owned by the block. The partition "owner"
1411  // is NULLed to allow the blob to get merged with its base character
1412  // partition.
1413  BLOBNBOX* box = box_it.extract();
1414  box->set_owner(NULL);
1415  box_it.forward();
1416  ++medium_diacritics;
1417  // We remove the blob from the grid so it isn't found by subsequent
1418  // searches where we might not want to include diacritics.
1419  RemoveBBox(box);
1420  }
1421  // We only move the one blob to the small list here, but the others
1422  // all get moved by the test at the top of the loop.
1423  small_it.add_to_end(blob_it.extract());
1424  part_grid->RemoveBBox(part);
1425  delete part;
1426  }
1427  } else if (AlignedBlob::WithinTestRegion(2, blob->bounding_box().left(),
1428  blob->bounding_box().bottom())) {
1429  tprintf("Blob not available to be a diacritic at:");
1430  blob->bounding_box().print();
1431  }
1432  }
1434  tprintf("Found %d small diacritics, %d medium\n",
1435  small_diacritics, medium_diacritics);
1436  }
1437 }
1438 
1439 // Searches this grid for an appropriately close and sized neighbour of the
1440 // given [small] blob. If such a blob is found, the diacritic base is saved
1441 // in the blob and true is returned.
1442 // The small_grid is a secondary grid that contains the small/noise objects
1443 // that are not in this grid, but may be useful for determining a connection
1444 // between blob and its potential base character. (See DiacriticXGapFilled.)
1445 bool StrokeWidth::DiacriticBlob(BlobGrid* small_grid, BLOBNBOX* blob) {
1446  if (BLOBNBOX::UnMergeableType(blob->region_type()) ||
1447  blob->region_type() == BRT_VERT_TEXT)
1448  return false;
1449  TBOX small_box(blob->bounding_box());
1450  bool debug = AlignedBlob::WithinTestRegion(2, small_box.left(),
1451  small_box.bottom());
1452  if (debug) {
1453  tprintf("Testing blob for diacriticness at:");
1454  small_box.print();
1455  }
1456  int x = (small_box.left() + small_box.right()) / 2;
1457  int y = (small_box.bottom() + small_box.top()) / 2;
1458  int grid_x, grid_y;
1459  GridCoords(x, y, &grid_x, &grid_y);
1460  int height = small_box.height();
1461  // Setup a rectangle search to find its nearest base-character neighbour.
1462  // We keep 2 different best candidates:
1463  // best_x_overlap is a category of base characters that have an overlap in x
1464  // (like a acute) in which we look for the least y-gap, computed using the
1465  // projection to favor base characters in the same textline.
1466  // best_y_overlap is a category of base characters that have no x overlap,
1467  // (nominally a y-overlap is preferrecd but not essential) in which we
1468  // look for the least weighted sum of x-gap and y-gap, with x-gap getting
1469  // a lower weight to catch quotes at the end of a textline.
1470  // NOTE that x-gap and y-gap are measured from the nearest side of the base
1471  // character to the FARTHEST side of the diacritic to allow small diacritics
1472  // to be a reasonable distance away, but not big diacritics.
1473  BLOBNBOX* best_x_overlap = NULL;
1474  BLOBNBOX* best_y_overlap = NULL;
1475  int best_total_dist = 0;
1476  int best_y_gap = 0;
1477  TBOX best_xbox;
1478  // TODO(rays) the search box could be setup using the projection as a guide.
1479  TBOX search_box(small_box);
1480  int x_pad = IntCastRounded(gridsize() * kDiacriticXPadRatio);
1481  int y_pad = IntCastRounded(gridsize() * kDiacriticYPadRatio);
1482  search_box.pad(x_pad, y_pad);
1483  BlobGridSearch rsearch(this);
1484  rsearch.SetUniqueMode(true);
1485  int min_height = height * kMinDiacriticSizeRatio;
1486  rsearch.StartRectSearch(search_box);
1487  BLOBNBOX* neighbour;
1488  while ((neighbour = rsearch.NextRectSearch()) != NULL) {
1489  if (BLOBNBOX::UnMergeableType(neighbour->region_type()) ||
1490  neighbour == blob || neighbour->owner() == blob->owner())
1491  continue;
1492  TBOX nbox = neighbour->bounding_box();
1493  if (neighbour->owner() == NULL || neighbour->owner()->IsVerticalType() ||
1494  (neighbour->flow() != BTFT_CHAIN &&
1495  neighbour->flow() != BTFT_STRONG_CHAIN)) {
1496  if (debug) {
1497  tprintf("Neighbour not strong enough:");
1498  nbox.print();
1499  }
1500  continue; // Diacritics must be attached to strong text.
1501  }
1502  if (nbox.height() < min_height) {
1503  if (debug) {
1504  tprintf("Neighbour not big enough:");
1505  nbox.print();
1506  }
1507  continue; // Too small to be the base character.
1508  }
1509  int x_gap = small_box.x_gap(nbox);
1510  int y_gap = small_box.y_gap(nbox);
1511  int total_distance = projection_->DistanceOfBoxFromBox(small_box, nbox,
1512  true, denorm_,
1513  debug);
1514  if (debug) tprintf("xgap=%d, y=%d, total dist=%d\n",
1515  x_gap, y_gap, total_distance);
1516  if (total_distance >
1517  neighbour->owner()->median_size() * kMaxDiacriticDistanceRatio) {
1518  if (debug) {
1519  tprintf("Neighbour with median size %d too far away:",
1520  neighbour->owner()->median_size());
1521  neighbour->bounding_box().print();
1522  }
1523  continue; // Diacritics must not be too distant.
1524  }
1525  if (x_gap <= 0) {
1526  if (debug) {
1527  tprintf("Computing reduced box for :");
1528  nbox.print();
1529  }
1530  int left = small_box.left() - small_box.width();
1531  int right = small_box.right() + small_box.width();
1532  nbox = neighbour->BoundsWithinLimits(left, right);
1533  y_gap = small_box.y_gap(nbox);
1534  if (best_x_overlap == NULL || y_gap < best_y_gap) {
1535  best_x_overlap = neighbour;
1536  best_xbox = nbox;
1537  best_y_gap = y_gap;
1538  if (debug) {
1539  tprintf("New best:");
1540  nbox.print();
1541  }
1542  } else if (debug) {
1543  tprintf("Shrunken box doesn't win:");
1544  nbox.print();
1545  }
1546  } else if (blob->ConfirmNoTabViolation(*neighbour)) {
1547  if (best_y_overlap == NULL || total_distance < best_total_dist) {
1548  if (debug) {
1549  tprintf("New best y overlap:");
1550  nbox.print();
1551  }
1552  best_y_overlap = neighbour;
1553  best_total_dist = total_distance;
1554  } else if (debug) {
1555  tprintf("New y overlap box doesn't win:");
1556  nbox.print();
1557  }
1558  } else if (debug) {
1559  tprintf("Neighbour wrong side of a tab:");
1560  nbox.print();
1561  }
1562  }
1563  if (best_x_overlap != NULL &&
1564  (best_y_overlap == NULL ||
1565  best_xbox.major_y_overlap(best_y_overlap->bounding_box()))) {
1566  blob->set_diacritic_box(best_xbox);
1567  blob->set_base_char_blob(best_x_overlap);
1568  if (debug) {
1569  tprintf("DiacriticBlob OK! (x-overlap:");
1570  small_box.print();
1571  best_xbox.print();
1572  }
1573  return true;
1574  }
1575  if (best_y_overlap != NULL &&
1576  DiacriticXGapFilled(small_grid, small_box,
1577  best_y_overlap->bounding_box()) &&
1578  NoNoiseInBetween(small_box, best_y_overlap->bounding_box())) {
1579  blob->set_diacritic_box(best_y_overlap->bounding_box());
1580  blob->set_base_char_blob(best_y_overlap);
1581  if (debug) {
1582  tprintf("DiacriticBlob OK! (y-overlap:");
1583  small_box.print();
1584  best_y_overlap->bounding_box().print();
1585  }
1586  return true;
1587  }
1588  if (debug) {
1589  tprintf("DiacriticBlob fails:");
1590  small_box.print();
1591  tprintf("Best x+y gap = %d, y = %d\n", best_total_dist, best_y_gap);
1592  if (best_y_overlap != NULL) {
1593  tprintf("XGapFilled=%d, NoiseBetween=%d\n",
1594  DiacriticXGapFilled(small_grid, small_box,
1595  best_y_overlap->bounding_box()),
1596  NoNoiseInBetween(small_box, best_y_overlap->bounding_box()));
1597  }
1598  }
1599  return false;
1600 }
1601 
1602 // Returns true if there is no gap between the base char and the diacritic
1603 // bigger than a fraction of the height of the base char:
1604 // Eg: line end.....'
1605 // The quote is a long way from the end of the line, yet it needs to be a
1606 // diacritic. To determine that the quote is not part of an image, or
1607 // a different text block, we check for other marks in the gap between
1608 // the base char and the diacritic.
1609 // '<--Diacritic
1610 // |---------|
1611 // | |<-toobig-gap->
1612 // | Base |<ok gap>
1613 // |---------| x<-----Dot occupying gap
1614 // The grid is const really.
1615 bool StrokeWidth::DiacriticXGapFilled(BlobGrid* grid,
1616  const TBOX& diacritic_box,
1617  const TBOX& base_box) {
1618  // Since most gaps are small, use an iterative algorithm to search the gap.
1619  int max_gap = IntCastRounded(base_box.height() *
1621  TBOX occupied_box(base_box);
1622  int diacritic_gap;
1623  while ((diacritic_gap = diacritic_box.x_gap(occupied_box)) > max_gap) {
1624  TBOX search_box(occupied_box);
1625  if (diacritic_box.left() > search_box.right()) {
1626  // We are looking right.
1627  search_box.set_left(search_box.right());
1628  search_box.set_right(search_box.left() + max_gap);
1629  } else {
1630  // We are looking left.
1631  search_box.set_right(search_box.left());
1632  search_box.set_left(search_box.left() - max_gap);
1633  }
1634  BlobGridSearch rsearch(grid);
1635  rsearch.StartRectSearch(search_box);
1636  BLOBNBOX* neighbour;
1637  while ((neighbour = rsearch.NextRectSearch()) != NULL) {
1638  const TBOX& nbox = neighbour->bounding_box();
1639  if (nbox.x_gap(diacritic_box) < diacritic_gap) {
1640  if (nbox.left() < occupied_box.left())
1641  occupied_box.set_left(nbox.left());
1642  if (nbox.right() > occupied_box.right())
1643  occupied_box.set_right(nbox.right());
1644  break;
1645  }
1646  }
1647  if (neighbour == NULL)
1648  return false; // Found a big gap.
1649  }
1650  return true; // The gap was filled.
1651 }
1652 
1653 // Merges diacritics with the ColPartition of the base character blob.
1654 void StrokeWidth::MergeDiacritics(TO_BLOCK* block,
1655  ColPartitionGrid* part_grid) {
1656  BLOBNBOX_IT small_it(&block->noise_blobs);
1657  for (small_it.mark_cycle_pt(); !small_it.cycled_list(); small_it.forward()) {
1658  BLOBNBOX* blob = small_it.data();
1659  if (blob->base_char_blob() != NULL) {
1660  ColPartition* part = blob->base_char_blob()->owner();
1661  // The base character must be owned by a partition and that partition
1662  // must not be on the big_parts list (not block owned).
1663  if (part != NULL && !part->block_owned() && blob->owner() == NULL &&
1664  blob->IsDiacritic()) {
1665  // The partition has to be removed from the grid and reinserted
1666  // because its bounding box may change.
1667  part_grid->RemoveBBox(part);
1668  part->AddBox(blob);
1669  blob->set_region_type(part->blob_type());
1670  blob->set_flow(part->flow());
1671  blob->set_owner(part);
1672  part_grid->InsertBBox(true, true, part);
1673  }
1674  // Set all base chars to NULL before any blobs get deleted.
1675  blob->set_base_char_blob(NULL);
1676  }
1677  }
1678 }
1679 
1680 // Any blobs on the large_blobs list of block that are still unowned by a
1681 // ColPartition, are probably drop-cap or vertically touching so the blobs
1682 // are removed to the big_parts list and treated separately.
1683 void StrokeWidth::RemoveLargeUnusedBlobs(TO_BLOCK* block,
1684  ColPartitionGrid* part_grid,
1685  ColPartition_LIST* big_parts) {
1686  BLOBNBOX_IT large_it(&block->large_blobs);
1687  for (large_it.mark_cycle_pt(); !large_it.cycled_list(); large_it.forward()) {
1688  BLOBNBOX* blob = large_it.data();
1689  ColPartition* big_part = blob->owner();
1690  if (big_part == NULL) {
1691  // Large blobs should have gone into partitions by now if they are
1692  // genuine characters, so move any unowned ones out to the big parts
1693  // list. This will include drop caps and vertically touching characters.
1694  ColPartition::MakeBigPartition(blob, big_parts);
1695  }
1696  }
1697 }
1698 
1699 // All remaining unused blobs are put in individual ColPartitions.
1700 void StrokeWidth::PartitionRemainingBlobs(ColPartitionGrid* part_grid) {
1701  BlobGridSearch gsearch(this);
1702  BLOBNBOX* bbox;
1703  int prev_grid_x = -1;
1704  int prev_grid_y = -1;
1705  BLOBNBOX_CLIST cell_list;
1706  BLOBNBOX_C_IT cell_it(&cell_list);
1707  bool cell_all_noise = true;
1708  gsearch.StartFullSearch();
1709  while ((bbox = gsearch.NextFullSearch()) != NULL) {
1710  int grid_x = gsearch.GridX();
1711  int grid_y = gsearch.GridY();
1712  if (grid_x != prev_grid_x || grid_y != prev_grid_y) {
1713  // New cell. Process old cell.
1714  MakePartitionsFromCellList(cell_all_noise, part_grid, &cell_list);
1715  cell_it.set_to_list(&cell_list);
1716  prev_grid_x = grid_x;
1717  prev_grid_y = grid_y;
1718  cell_all_noise = true;
1719  }
1720  if (bbox->owner() == NULL) {
1721  cell_it.add_to_end(bbox);
1722  if (bbox->flow() != BTFT_NONTEXT)
1723  cell_all_noise = false;
1724  } else {
1725  cell_all_noise = false;
1726  }
1727  }
1728  MakePartitionsFromCellList(cell_all_noise, part_grid, &cell_list);
1729 }
1730 
1731 // If combine, put all blobs in the cell_list into a single partition, otherwise
1732 // put each one into its own partition.
1733 void StrokeWidth::MakePartitionsFromCellList(bool combine,
1734  ColPartitionGrid* part_grid,
1735  BLOBNBOX_CLIST* cell_list) {
1736  if (cell_list->empty())
1737  return;
1738  BLOBNBOX_C_IT cell_it(cell_list);
1739  if (combine) {
1740  BLOBNBOX* bbox = cell_it.extract();
1741  ColPartition* part = new ColPartition(bbox->region_type(), ICOORD(0, 1));
1742  part->AddBox(bbox);
1743  part->set_flow(bbox->flow());
1744  for (cell_it.forward(); !cell_it.empty(); cell_it.forward()) {
1745  part->AddBox(cell_it.extract());
1746  }
1747  CompletePartition(part, part_grid);
1748  } else {
1749  for (; !cell_it.empty(); cell_it.forward()) {
1750  BLOBNBOX* bbox = cell_it.extract();
1751  ColPartition* part = new ColPartition(bbox->region_type(), ICOORD(0, 1));
1752  part->set_flow(bbox->flow());
1753  part->AddBox(bbox);
1754  CompletePartition(part, part_grid);
1755  }
1756  }
1757 }
1758 
1759 // Helper function to finish setting up a ColPartition and insert into
1760 // part_grid.
1761 void StrokeWidth::CompletePartition(ColPartition* part,
1762  ColPartitionGrid* part_grid) {
1763  part->ComputeLimits();
1764  TBOX box = part->bounding_box();
1765  bool debug = AlignedBlob::WithinTestRegion(2, box.left(),
1766  box.bottom());
1767  int value = projection_->EvaluateColPartition(*part, denorm_, debug);
1768  part->SetRegionAndFlowTypesFromProjectionValue(value);
1769  part->ClaimBoxes();
1770  part_grid->InsertBBox(true, true, part);
1771 }
1772 
1773 // Merge partitions where the merge appears harmless.
1774 // As this
1775 void StrokeWidth::EasyMerges(ColPartitionGrid* part_grid) {
1776  part_grid->Merges(
1777  NewPermanentTessCallback(this, &StrokeWidth::OrientationSearchBox),
1778  NewPermanentTessCallback(this, &StrokeWidth::ConfirmEasyMerge));
1779 }
1780 
1781 // Compute a search box based on the orientation of the partition.
1782 // Returns true if a suitable box can be calculated.
1783 // Callback for EasyMerges.
1784 bool StrokeWidth::OrientationSearchBox(ColPartition* part, TBOX* box) {
1785  if (part->IsVerticalType()) {
1786  box->set_top(box->top() + box->width());
1787  box->set_bottom(box->bottom() - box->width());
1788  } else {
1789  box->set_left(box->left() - box->height());
1790  box->set_right(box->right() + box->height());
1791  }
1792  return true;
1793 }
1794 
1795 // Merge confirmation callback for EasyMerges.
1796 bool StrokeWidth::ConfirmEasyMerge(const ColPartition* p1,
1797  const ColPartition* p2) {
1798  ASSERT_HOST(p1 != NULL && p2 != NULL);
1799  ASSERT_HOST(!p1->IsEmpty() && !p2->IsEmpty());
1800  if ((p1->flow() == BTFT_NONTEXT && p2->flow() >= BTFT_CHAIN) ||
1801  (p1->flow() >= BTFT_CHAIN && p2->flow() == BTFT_NONTEXT))
1802  return false; // Don't merge confirmed image with text.
1803  if ((p1->IsVerticalType() || p2->IsVerticalType()) &&
1804  p1->HCoreOverlap(*p2) <= 0 &&
1805  ((!p1->IsSingleton() &&
1806  !p2->IsSingleton()) ||
1807  !p1->bounding_box().major_overlap(p2->bounding_box())))
1808  return false; // Overlap must be in the text line.
1809  if ((p1->IsHorizontalType() || p2->IsHorizontalType()) &&
1810  p1->VCoreOverlap(*p2) <= 0 &&
1811  ((!p1->IsSingleton() &&
1812  !p2->IsSingleton()) ||
1813  (!p1->bounding_box().major_overlap(p2->bounding_box()) &&
1814  !p1->OKDiacriticMerge(*p2, false) &&
1815  !p2->OKDiacriticMerge(*p1, false))))
1816  return false; // Overlap must be in the text line.
1817  if (!p1->ConfirmNoTabViolation(*p2))
1818  return false;
1819  if (p1->flow() <= BTFT_NONTEXT && p2->flow() <= BTFT_NONTEXT)
1820  return true;
1821  return NoNoiseInBetween(p1->bounding_box(), p2->bounding_box());
1822 }
1823 
1824 // Returns true if there is no significant noise in between the boxes.
1825 bool StrokeWidth::NoNoiseInBetween(const TBOX& box1, const TBOX& box2) const {
1826  return ImageFind::BlankImageInBetween(box1, box2, grid_box_, rerotation_,
1827  nontext_map_);
1828 }
1829 
1833 ScrollView* StrokeWidth::DisplayGoodBlobs(const char* window_name,
1834  int x, int y) {
1835  ScrollView* window = NULL;
1836 #ifndef GRAPHICS_DISABLED
1837  window = MakeWindow(x, y, window_name);
1838  // For every blob in the grid, display it.
1839  window->Brush(ScrollView::NONE);
1840 
1841  // For every bbox in the grid, display it.
1842  BlobGridSearch gsearch(this);
1843  gsearch.StartFullSearch();
1844  BLOBNBOX* bbox;
1845  while ((bbox = gsearch.NextFullSearch()) != NULL) {
1846  TBOX box = bbox->bounding_box();
1847  int left_x = box.left();
1848  int right_x = box.right();
1849  int top_y = box.top();
1850  int bottom_y = box.bottom();
1851  int goodness = bbox->GoodTextBlob();
1852  BlobRegionType blob_type = bbox->region_type();
1853  if (bbox->UniquelyVertical())
1854  blob_type = BRT_VERT_TEXT;
1855  if (bbox->UniquelyHorizontal())
1856  blob_type = BRT_TEXT;
1857  BlobTextFlowType flow = bbox->flow();
1858  if (flow == BTFT_NONE) {
1859  if (goodness == 0)
1860  flow = BTFT_NEIGHBOURS;
1861  else if (goodness == 1)
1862  flow = BTFT_CHAIN;
1863  else
1864  flow = BTFT_STRONG_CHAIN;
1865  }
1866  window->Pen(BLOBNBOX::TextlineColor(blob_type, flow));
1867  window->Rectangle(left_x, bottom_y, right_x, top_y);
1868  }
1869  window->Update();
1870 #endif
1871  return window;
1872 }
1873 
1874 static void DrawDiacriticJoiner(const BLOBNBOX* blob, ScrollView* window) {
1875  const TBOX& blob_box(blob->bounding_box());
1876  int top = MAX(blob_box.top(), blob->base_char_top());
1877  int bottom = MIN(blob_box.bottom(), blob->base_char_bottom());
1878  int x = (blob_box.left() + blob_box.right()) / 2;
1879  #ifndef GRAPHICS_DISABLED
1880  window->Line(x, top, x, bottom);
1881  #endif // GRAPHICS_DISABLED
1882 }
1883 
1884 // Displays blobs colored according to whether or not they are diacritics.
1885 ScrollView* StrokeWidth::DisplayDiacritics(const char* window_name,
1886  int x, int y, TO_BLOCK* block) {
1887  ScrollView* window = NULL;
1888 #ifndef GRAPHICS_DISABLED
1889  window = MakeWindow(x, y, window_name);
1890  // For every blob in the grid, display it.
1891  window->Brush(ScrollView::NONE);
1892 
1893  BLOBNBOX_IT it(&block->blobs);
1894  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1895  BLOBNBOX* blob = it.data();
1896  if (blob->IsDiacritic()) {
1897  window->Pen(ScrollView::GREEN);
1898  DrawDiacriticJoiner(blob, window);
1899  } else {
1900  window->Pen(blob->BoxColor());
1901  }
1902  const TBOX& box = blob->bounding_box();
1903  window->Rectangle(box.left(), box. bottom(), box.right(), box.top());
1904  }
1905  it.set_to_list(&block->noise_blobs);
1906  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
1907  BLOBNBOX* blob = it.data();
1908  if (blob->IsDiacritic()) {
1909  window->Pen(ScrollView::GREEN);
1910  DrawDiacriticJoiner(blob, window);
1911  } else {
1912  window->Pen(ScrollView::WHITE);
1913  }
1914  const TBOX& box = blob->bounding_box();
1915  window->Rectangle(box.left(), box. bottom(), box.right(), box.top());
1916  }
1917  window->Update();
1918 #endif
1919  return window;
1920 }
1921 
1922 } // namespace tesseract.