Tesseract 3.02

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

- File List
- File Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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");
48 BOOL_VAR(textord_tabfind_force_vertical_text, false,
49 "Force using vertical text page mode");
50 BOOL_VAR(textord_tabfind_vertical_horizontal_mix, true,
51 "find horizontal lines such as headers in vertical page mode");
52 double_VAR(textord_tabfind_vertical_text_ratio, 0.5,
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.)
94 const double kMaxDiacriticGapToBaseCharHeight = 1.0;
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
121 StrokeWidth::StrokeWidth(int gridsize,
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
134 StrokeWidth::~StrokeWidth() {
135 if (widths_win_ != NULL) {
136 #ifndef GRAPHICS_DISABLED
137 delete widths_win_->AwaitEvent(SVET_DESTROY);
138 #endif // GRAPHICS_DISABLED
139 if (textord_tabfind_only_strokewidths)
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.
154 void StrokeWidth::SetNeighboursOnMediumBlobs(TO_BLOCK* block) {
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.
168 void StrokeWidth::FindTextlineDirectionAndFixBrokenCJK(bool cjk_merge,
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.
219 bool StrokeWidth::TestVerticalTextDirection(TO_BLOCK* block,
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);
234 if (textord_debug_tabfind)
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) *
246 textord_tabfind_vertical_text_ratio);
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.
263 void StrokeWidth::CorrectForRotation(const FCOORD& 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.
272 void StrokeWidth::FindLeaderPartitions(TO_BLOCK* block,
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.
356 void StrokeWidth::GradeBlobsIntoPartitions(const FCOORD& rerotation,
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_);
379 if (textord_tabfind_show_strokewidths) {
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) {
405 BBGrid<BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT>::HandleClick(x, 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 }
483 if (textord_tabfind_show_strokewidths) {
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,
631 kStrokeWidthCJK))
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) ||
823 textord_tabfind_show_strokewidths > 1) {
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) ||
842 textord_tabfind_show_strokewidths > 1) {
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,
1010 kStrokeWidthFractionTolerance,
1011 kStrokeWidthTolerance);
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);
1206 if (AlignedBlob::WithinTestRegion(2, blob->bounding_box().left(),
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);
1241 if (textord_tabfind_show_strokewidths) {
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);
1256 if (textord_tabfind_show_strokewidths) {
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));
1271 if (textord_tabfind_show_strokewidths) {
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 }
1433 if (textord_tabfind_show_strokewidths) {
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() *
1620 kMaxDiacriticGapToBaseCharHeight);
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.