-
Notifications
You must be signed in to change notification settings - Fork 9.7k
/
Copy pathstrokewidth.cpp
2018 lines (1944 loc) · 80.8 KB
/
strokewidth.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
///////////////////////////////////////////////////////////////////////
// File: strokewidth.cpp
// Description: Subclass of BBGrid to find uniformity of strokewidth.
// Author: Ray Smith
// Created: Mon Mar 31 16:17:01 PST 2008
//
// (C) Copyright 2008, Google Inc.
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
// http://www.apache.org/licenses/LICENSE-2.0
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
///////////////////////////////////////////////////////////////////////
#ifdef _MSC_VER
#pragma warning(disable:4244) // Conversion warnings
#endif
#ifdef HAVE_CONFIG_H
#include "config_auto.h"
#endif
#include "strokewidth.h"
#include <math.h>
#include "blobbox.h"
#include "colpartition.h"
#include "colpartitiongrid.h"
#include "imagefind.h"
#include "linlsq.h"
#include "statistc.h"
#include "tabfind.h"
#include "textlineprojection.h"
#include "tordmain.h" // For SetBlobStrokeWidth.
namespace tesseract {
INT_VAR(textord_tabfind_show_strokewidths, 0, "Show stroke widths");
BOOL_VAR(textord_tabfind_only_strokewidths, false, "Only run stroke widths");
/** Allowed proportional change in stroke width to be the same font. */
const double kStrokeWidthFractionTolerance = 0.125;
/**
* Allowed constant change in stroke width to be the same font.
* Really 1.5 pixels.
*/
const double kStrokeWidthTolerance = 1.5;
// Same but for CJK we are a bit more generous.
const double kStrokeWidthFractionCJK = 0.25;
const double kStrokeWidthCJK = 2.0;
// Radius in grid cells of search for broken CJK. Doesn't need to be very
// large as the grid size should be about the size of a character anyway.
const int kCJKRadius = 2;
// Max distance fraction of size to join close but broken CJK characters.
const double kCJKBrokenDistanceFraction = 0.25;
// Max number of components in a broken CJK character.
const int kCJKMaxComponents = 8;
// Max aspect ratio of CJK broken characters when put back together.
const double kCJKAspectRatio = 1.25;
// Max increase in aspect ratio of CJK broken characters when merged.
const double kCJKAspectRatioIncrease = 1.0625;
// Max multiple of the grid size that will be used in computing median CJKsize.
const int kMaxCJKSizeRatio = 5;
// Min fraction of blobs broken CJK to iterate and run it again.
const double kBrokenCJKIterationFraction = 0.125;
// Multiple of gridsize as x-padding for a search box for diacritic base
// characters.
const double kDiacriticXPadRatio = 7.0;
// Multiple of gridsize as y-padding for a search box for diacritic base
// characters.
const double kDiacriticYPadRatio = 1.75;
// Min multiple of diacritic height that a neighbour must be to be a
// convincing base character.
const double kMinDiacriticSizeRatio = 1.0625;
// Max multiple of a textline's median height as a threshold for the sum of
// a diacritic's farthest x and y distances (gap + size).
const double kMaxDiacriticDistanceRatio = 1.25;
// Max x-gap between a diacritic and its base char as a fraction of the height
// of the base char (allowing other blobs to fill the gap.)
const double kMaxDiacriticGapToBaseCharHeight = 1.0;
// Ratio between longest side of a line and longest side of a character.
// (neighbor_min > blob_min * kLineTrapShortest &&
// neighbor_max < blob_max / kLineTrapLongest)
// => neighbor is a grapheme and blob is a line.
const int kLineTrapLongest = 4;
// Ratio between shortest side of a line and shortest side of a character.
const int kLineTrapShortest = 2;
// Max aspect ratio of the total box before CountNeighbourGaps
// decides immediately based on the aspect ratio.
const int kMostlyOneDirRatio = 3;
// Aspect ratio for a blob to be considered as line residue.
const double kLineResidueAspectRatio = 8.0;
// Padding ratio for line residue search box.
const int kLineResiduePadRatio = 3;
// Min multiple of neighbour size for a line residue to be genuine.
const double kLineResidueSizeRatio = 1.75;
// Aspect ratio filter for OSD.
const float kSizeRatioToReject = 2.0;
// Expansion factor for search box for good neighbours.
const double kNeighbourSearchFactor = 2.5;
// Factor of increase of overlap when adding diacritics to make an image noisy.
const double kNoiseOverlapGrowthFactor = 4.0;
// Fraction of the image size to add overlap when adding diacritics for an
// image to qualify as noisy.
const double kNoiseOverlapAreaFactor = 1.0 / 512;
StrokeWidth::StrokeWidth(int gridsize,
const ICOORD& bleft, const ICOORD& tright)
: BlobGrid(gridsize, bleft, tright), nontext_map_(NULL), projection_(NULL),
denorm_(NULL), grid_box_(bleft, tright), rerotation_(1.0f, 0.0f) {
leaders_win_ = NULL;
widths_win_ = NULL;
initial_widths_win_ = NULL;
chains_win_ = NULL;
diacritics_win_ = NULL;
textlines_win_ = NULL;
smoothed_win_ = NULL;
}
StrokeWidth::~StrokeWidth() {
if (widths_win_ != NULL) {
#ifndef GRAPHICS_DISABLED
delete widths_win_->AwaitEvent(SVET_DESTROY);
#endif // GRAPHICS_DISABLED
if (textord_tabfind_only_strokewidths)
exit(0);
delete widths_win_;
}
delete leaders_win_;
delete initial_widths_win_;
delete chains_win_;
delete textlines_win_;
delete smoothed_win_;
delete diacritics_win_;
}
// Sets the neighbours member of the medium-sized blobs in the block.
// Searches on 4 sides of each blob for similar-sized, similar-strokewidth
// blobs and sets pointers to the good neighbours.
void StrokeWidth::SetNeighboursOnMediumBlobs(TO_BLOCK* block) {
// Run a preliminary strokewidth neighbour detection on the medium blobs.
InsertBlobList(&block->blobs);
BLOBNBOX_IT blob_it(&block->blobs);
for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
SetNeighbours(false, false, blob_it.data());
}
Clear();
}
// Sets the neighbour/textline writing direction members of the medium
// and large blobs with optional repair of broken CJK characters first.
// Repair of broken CJK is needed here because broken CJK characters
// can fool the textline direction detection algorithm.
void StrokeWidth::FindTextlineDirectionAndFixBrokenCJK(PageSegMode pageseg_mode,
bool cjk_merge,
TO_BLOCK* input_block) {
// Setup the grid with the remaining (non-noise) blobs.
InsertBlobs(input_block);
// Repair broken CJK characters if needed.
while (cjk_merge && FixBrokenCJK(input_block));
// Grade blobs by inspection of neighbours.
FindTextlineFlowDirection(pageseg_mode, false);
// Clear the grid ready for rotation or leader finding.
Clear();
}
// Helper to collect and count horizontal and vertical blobs from a list.
static void CollectHorizVertBlobs(BLOBNBOX_LIST* input_blobs,
int* num_vertical_blobs,
int* num_horizontal_blobs,
BLOBNBOX_CLIST* vertical_blobs,
BLOBNBOX_CLIST* horizontal_blobs,
BLOBNBOX_CLIST* nondescript_blobs) {
BLOBNBOX_C_IT v_it(vertical_blobs);
BLOBNBOX_C_IT h_it(horizontal_blobs);
BLOBNBOX_C_IT n_it(nondescript_blobs);
BLOBNBOX_IT blob_it(input_blobs);
for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
BLOBNBOX* blob = blob_it.data();
const TBOX& box = blob->bounding_box();
float y_x = static_cast<float>(box.height()) / box.width();
float x_y = 1.0f / y_x;
// Select a >= 1.0 ratio
float ratio = x_y > y_x ? x_y : y_x;
// If the aspect ratio is small and we want them for osd, save the blob.
bool ok_blob = ratio <= kSizeRatioToReject;
if (blob->UniquelyVertical()) {
++*num_vertical_blobs;
if (ok_blob) v_it.add_after_then_move(blob);
} else if (blob->UniquelyHorizontal()) {
++*num_horizontal_blobs;
if (ok_blob) h_it.add_after_then_move(blob);
} else if (ok_blob) {
n_it.add_after_then_move(blob);
}
}
}
// Types all the blobs as vertical or horizontal text or unknown and
// returns true if the majority are vertical.
// If the blobs are rotated, it is necessary to call CorrectForRotation
// after rotating everything, otherwise the work done here will be enough.
// If osd_blobs is not null, a list of blobs from the dominant textline
// direction are returned for use in orientation and script detection.
bool StrokeWidth::TestVerticalTextDirection(double find_vertical_text_ratio,
TO_BLOCK* block,
BLOBNBOX_CLIST* osd_blobs) {
int vertical_boxes = 0;
int horizontal_boxes = 0;
// Count vertical normal and large blobs.
BLOBNBOX_CLIST vertical_blobs;
BLOBNBOX_CLIST horizontal_blobs;
BLOBNBOX_CLIST nondescript_blobs;
CollectHorizVertBlobs(&block->blobs, &vertical_boxes, &horizontal_boxes,
&vertical_blobs, &horizontal_blobs, &nondescript_blobs);
CollectHorizVertBlobs(&block->large_blobs, &vertical_boxes, &horizontal_boxes,
&vertical_blobs, &horizontal_blobs, &nondescript_blobs);
if (textord_debug_tabfind)
tprintf("TextDir hbox=%d vs vbox=%d, %dH, %dV, %dN osd blobs\n",
horizontal_boxes, vertical_boxes,
horizontal_blobs.length(), vertical_blobs.length(),
nondescript_blobs.length());
if (osd_blobs != NULL && vertical_boxes == 0 && horizontal_boxes == 0) {
// Only nondescript blobs available, so return those.
BLOBNBOX_C_IT osd_it(osd_blobs);
osd_it.add_list_after(&nondescript_blobs);
return false;
}
int min_vert_boxes = static_cast<int>((vertical_boxes + horizontal_boxes) *
find_vertical_text_ratio);
if (vertical_boxes >= min_vert_boxes) {
if (osd_blobs != NULL) {
BLOBNBOX_C_IT osd_it(osd_blobs);
osd_it.add_list_after(&vertical_blobs);
}
return true;
} else {
if (osd_blobs != NULL) {
BLOBNBOX_C_IT osd_it(osd_blobs);
osd_it.add_list_after(&horizontal_blobs);
}
return false;
}
}
// Corrects the data structures for the given rotation.
void StrokeWidth::CorrectForRotation(const FCOORD& rotation,
ColPartitionGrid* part_grid) {
Init(part_grid->gridsize(), part_grid->bleft(), part_grid->tright());
grid_box_ = TBOX(bleft(), tright());
rerotation_.set_x(rotation.x());
rerotation_.set_y(-rotation.y());
}
// Finds leader partitions and inserts them into the given part_grid.
void StrokeWidth::FindLeaderPartitions(TO_BLOCK* block,
ColPartitionGrid* part_grid) {
Clear();
// Find and isolate leaders in the noise list.
ColPartition_LIST leader_parts;
FindLeadersAndMarkNoise(block, &leader_parts);
// Setup the strokewidth grid with the block's remaining (non-noise) blobs.
InsertBlobList(&block->blobs);
// Mark blobs that have leader neighbours.
for (ColPartition_IT it(&leader_parts); !it.empty(); it.forward()) {
ColPartition* part = it.extract();
part->ClaimBoxes();
MarkLeaderNeighbours(part, LR_LEFT);
MarkLeaderNeighbours(part, LR_RIGHT);
part_grid->InsertBBox(true, true, part);
}
}
// Finds and marks noise those blobs that look like bits of vertical lines
// that would otherwise screw up layout analysis.
void StrokeWidth::RemoveLineResidue(ColPartition_LIST* big_part_list) {
BlobGridSearch gsearch(this);
BLOBNBOX* bbox;
// For every vertical line-like bbox in the grid, search its neighbours
// to find the tallest, and if the original box is taller by sufficient
// margin, then call it line residue and delete it.
gsearch.StartFullSearch();
while ((bbox = gsearch.NextFullSearch()) != NULL) {
TBOX box = bbox->bounding_box();
if (box.height() < box.width() * kLineResidueAspectRatio)
continue;
// Set up a rectangle search around the blob to find the size of its
// neighbours.
int padding = box.height() * kLineResiduePadRatio;
TBOX search_box = box;
search_box.pad(padding, padding);
bool debug = AlignedBlob::WithinTestRegion(2, box.left(),
box.bottom());
// Find the largest object in the search box not equal to bbox.
BlobGridSearch rsearch(this);
int max_size = 0;
BLOBNBOX* n;
rsearch.StartRectSearch(search_box);
while ((n = rsearch.NextRectSearch()) != NULL) {
if (n == bbox) continue;
TBOX nbox = n->bounding_box();
if (nbox.height() > max_size) {
max_size = nbox.height();
}
}
if (debug) {
tprintf("Max neighbour size=%d for candidate line box at:", max_size);
box.print();
}
if (max_size * kLineResidueSizeRatio < box.height()) {
#ifndef GRAPHICS_DISABLED
if (leaders_win_ != NULL) {
// We are debugging, so display deleted in pink blobs in the same
// window that we use to display leader detection.
leaders_win_->Pen(ScrollView::PINK);
leaders_win_->Rectangle(box.left(), box.bottom(),
box.right(), box.top());
}
#endif // GRAPHICS_DISABLED
ColPartition::MakeBigPartition(bbox, big_part_list);
}
}
}
// Types all the blobs as vertical text or horizontal text or unknown and
// puts them into initial ColPartitions in the supplied part_grid.
// rerotation determines how to get back to the image coordinates from the
// blob coordinates (since they may have been rotated for vertical text).
// block is the single block for the whole page or rectangle to be OCRed.
// nontext_pix (full-size), is a binary mask used to prevent merges across
// photo/text boundaries. It is not kept beyond this function.
// denorm provides a mapping back to the image from the current blob
// coordinate space.
// projection provides a measure of textline density over the image and
// provides functions to assist with diacritic detection. It should be a
// pointer to a new TextlineProjection, and will be setup here.
// part_grid is the output grid of textline partitions.
// Large blobs that cause overlap are put in separate partitions and added
// to the big_parts list.
void StrokeWidth::GradeBlobsIntoPartitions(
PageSegMode pageseg_mode, const FCOORD& rerotation, TO_BLOCK* block,
Pix* nontext_pix, const DENORM* denorm, bool cjk_script,
TextlineProjection* projection, BLOBNBOX_LIST* diacritic_blobs,
ColPartitionGrid* part_grid, ColPartition_LIST* big_parts) {
nontext_map_ = nontext_pix;
projection_ = projection;
denorm_ = denorm;
// Clear and re Insert to take advantage of the tab stops in the blobs.
Clear();
// Setup the strokewidth grid with the remaining non-noise, non-leader blobs.
InsertBlobs(block);
// Run FixBrokenCJK() again if the page is CJK.
if (cjk_script) {
FixBrokenCJK(block);
}
FindTextlineFlowDirection(pageseg_mode, false);
projection_->ConstructProjection(block, rerotation, nontext_map_);
if (textord_tabfind_show_strokewidths) {
ScrollView* line_blobs_win = MakeWindow(0, 0, "Initial textline Blobs");
projection_->PlotGradedBlobs(&block->blobs, line_blobs_win);
projection_->PlotGradedBlobs(&block->small_blobs, line_blobs_win);
}
projection_->MoveNonTextlineBlobs(&block->blobs, &block->noise_blobs);
projection_->MoveNonTextlineBlobs(&block->small_blobs, &block->noise_blobs);
// Clear and re Insert to take advantage of the removed diacritics.
Clear();
InsertBlobs(block);
FCOORD skew;
FindTextlineFlowDirection(pageseg_mode, true);
PartitionFindResult r =
FindInitialPartitions(pageseg_mode, rerotation, true, block,
diacritic_blobs, part_grid, big_parts, &skew);
if (r == PFR_NOISE) {
tprintf("Detected %d diacritics\n", diacritic_blobs->length());
// Noise was found, and removed.
Clear();
InsertBlobs(block);
FindTextlineFlowDirection(pageseg_mode, true);
r = FindInitialPartitions(pageseg_mode, rerotation, false, block,
diacritic_blobs, part_grid, big_parts, &skew);
}
nontext_map_ = NULL;
projection_ = NULL;
denorm_ = NULL;
}
static void PrintBoxWidths(BLOBNBOX* neighbour) {
const TBOX& nbox = neighbour->bounding_box();
tprintf("Box (%d,%d)->(%d,%d): h-width=%.1f, v-width=%.1f p-width=%1.f\n",
nbox.left(), nbox.bottom(), nbox.right(), nbox.top(),
neighbour->horz_stroke_width(), neighbour->vert_stroke_width(),
2.0 * neighbour->cblob()->area()/neighbour->cblob()->perimeter());
}
/** Handles a click event in a display window. */
void StrokeWidth::HandleClick(int x, int y) {
BBGrid<BLOBNBOX, BLOBNBOX_CLIST, BLOBNBOX_C_IT>::HandleClick(x, y);
// Run a radial search for blobs that overlap.
BlobGridSearch radsearch(this);
radsearch.StartRadSearch(x, y, 1);
BLOBNBOX* neighbour;
FCOORD click(static_cast<float>(x), static_cast<float>(y));
while ((neighbour = radsearch.NextRadSearch()) != NULL) {
TBOX nbox = neighbour->bounding_box();
if (nbox.contains(click) && neighbour->cblob() != NULL) {
PrintBoxWidths(neighbour);
if (neighbour->neighbour(BND_LEFT) != NULL)
PrintBoxWidths(neighbour->neighbour(BND_LEFT));
if (neighbour->neighbour(BND_RIGHT) != NULL)
PrintBoxWidths(neighbour->neighbour(BND_RIGHT));
if (neighbour->neighbour(BND_ABOVE) != NULL)
PrintBoxWidths(neighbour->neighbour(BND_ABOVE));
if (neighbour->neighbour(BND_BELOW) != NULL)
PrintBoxWidths(neighbour->neighbour(BND_BELOW));
int gaps[BND_COUNT];
neighbour->NeighbourGaps(gaps);
tprintf("Left gap=%d, right=%d, above=%d, below=%d, horz=%d, vert=%d\n"
"Good= %d %d %d %d\n",
gaps[BND_LEFT], gaps[BND_RIGHT],
gaps[BND_ABOVE], gaps[BND_BELOW],
neighbour->horz_possible(),
neighbour->vert_possible(),
neighbour->good_stroke_neighbour(BND_LEFT),
neighbour->good_stroke_neighbour(BND_RIGHT),
neighbour->good_stroke_neighbour(BND_ABOVE),
neighbour->good_stroke_neighbour(BND_BELOW));
break;
}
}
}
// Detects and marks leader dots/dashes.
// Leaders are horizontal chains of small or noise blobs that look
// monospace according to ColPartition::MarkAsLeaderIfMonospaced().
// Detected leaders become the only occupants of the block->small_blobs list.
// Non-leader small blobs get moved to the blobs list.
// Non-leader noise blobs remain singletons in the noise list.
// All small and noise blobs in high density regions are marked BTFT_NONTEXT.
// block is the single block for the whole page or rectangle to be OCRed.
// leader_parts is the output.
void StrokeWidth::FindLeadersAndMarkNoise(TO_BLOCK* block,
ColPartition_LIST* leader_parts) {
InsertBlobList(&block->small_blobs);
InsertBlobList(&block->noise_blobs);
BlobGridSearch gsearch(this);
BLOBNBOX* bbox;
// For every bbox in the grid, set its neighbours.
gsearch.StartFullSearch();
while ((bbox = gsearch.NextFullSearch()) != NULL) {
SetNeighbours(true, false, bbox);
}
ColPartition_IT part_it(leader_parts);
gsearch.StartFullSearch();
while ((bbox = gsearch.NextFullSearch()) != NULL) {
if (bbox->flow() == BTFT_NONE) {
if (bbox->neighbour(BND_RIGHT) == NULL &&
bbox->neighbour(BND_LEFT) == NULL)
continue;
// Put all the linked blobs into a ColPartition.
ColPartition* part = new ColPartition(BRT_UNKNOWN, ICOORD(0, 1));
BLOBNBOX* blob;
for (blob = bbox; blob != NULL && blob->flow() == BTFT_NONE;
blob = blob->neighbour(BND_RIGHT))
part->AddBox(blob);
for (blob = bbox->neighbour(BND_LEFT); blob != NULL &&
blob->flow() == BTFT_NONE;
blob = blob->neighbour(BND_LEFT))
part->AddBox(blob);
if (part->MarkAsLeaderIfMonospaced())
part_it.add_after_then_move(part);
else
delete part;
}
}
if (textord_tabfind_show_strokewidths) {
leaders_win_ = DisplayGoodBlobs("LeaderNeighbours", 0, 0);
}
// Move any non-leaders from the small to the blobs list, as they are
// most likely dashes or broken characters.
BLOBNBOX_IT blob_it(&block->blobs);
BLOBNBOX_IT small_it(&block->small_blobs);
for (small_it.mark_cycle_pt(); !small_it.cycled_list(); small_it.forward()) {
BLOBNBOX* blob = small_it.data();
if (blob->flow() != BTFT_LEADER) {
if (blob->flow() == BTFT_NEIGHBOURS)
blob->set_flow(BTFT_NONE);
blob->ClearNeighbours();
blob_it.add_to_end(small_it.extract());
}
}
// Move leaders from the noise list to the small list, leaving the small
// list exclusively leaders, so they don't get processed further,
// and the remaining small blobs all in the noise list.
BLOBNBOX_IT noise_it(&block->noise_blobs);
for (noise_it.mark_cycle_pt(); !noise_it.cycled_list(); noise_it.forward()) {
BLOBNBOX* blob = noise_it.data();
if (blob->flow() == BTFT_LEADER || blob->joined_to_prev()) {
small_it.add_to_end(noise_it.extract());
} else if (blob->flow() == BTFT_NEIGHBOURS) {
blob->set_flow(BTFT_NONE);
blob->ClearNeighbours();
}
}
// Clear the grid as we don't want the small stuff hanging around in it.
Clear();
}
/** Inserts the block blobs (normal and large) into this grid.
* Blobs remain owned by the block. */
void StrokeWidth::InsertBlobs(TO_BLOCK* block) {
InsertBlobList(&block->blobs);
InsertBlobList(&block->large_blobs);
}
// Checks the left or right side of the given leader partition and sets the
// (opposite) leader_on_right or leader_on_left flags for blobs
// that are next to the given side of the given leader partition.
void StrokeWidth::MarkLeaderNeighbours(const ColPartition* part,
LeftOrRight side) {
const TBOX& part_box = part->bounding_box();
BlobGridSearch blobsearch(this);
// Search to the side of the leader for the nearest neighbour.
BLOBNBOX* best_blob = NULL;
int best_gap = 0;
blobsearch.StartSideSearch(side == LR_LEFT ? part_box.left()
: part_box.right(),
part_box.bottom(), part_box.top());
BLOBNBOX* blob;
while ((blob = blobsearch.NextSideSearch(side == LR_LEFT)) != NULL) {
const TBOX& blob_box = blob->bounding_box();
if (!blob_box.y_overlap(part_box))
continue;
int x_gap = blob_box.x_gap(part_box);
if (x_gap > 2 * gridsize()) {
break;
} else if (best_blob == NULL || x_gap < best_gap) {
best_blob = blob;
best_gap = x_gap;
}
}
if (best_blob != NULL) {
if (side == LR_LEFT)
best_blob->set_leader_on_right(true);
else
best_blob->set_leader_on_left(true);
#ifndef GRAPHICS_DISABLED
if (leaders_win_ != NULL) {
leaders_win_->Pen(side == LR_LEFT ? ScrollView::RED : ScrollView::GREEN);
const TBOX& blob_box = best_blob->bounding_box();
leaders_win_->Rectangle(blob_box.left(), blob_box.bottom(),
blob_box.right(), blob_box.top());
}
#endif // GRAPHICS_DISABLED
}
}
// Helper to compute the UQ of the square-ish CJK charcters.
static int UpperQuartileCJKSize(int gridsize, BLOBNBOX_LIST* blobs) {
STATS sizes(0, gridsize * kMaxCJKSizeRatio);
BLOBNBOX_IT it(blobs);
for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
BLOBNBOX* blob = it.data();
int width = blob->bounding_box().width();
int height = blob->bounding_box().height();
if (width <= height * kCJKAspectRatio && height < width * kCJKAspectRatio)
sizes.add(height, 1);
}
return static_cast<int>(sizes.ile(0.75f) + 0.5);
}
// Fix broken CJK characters, using the fake joined blobs mechanism.
// Blobs are really merged, ie the master takes all the outlines and the
// others are deleted.
// Returns true if sufficient blobs are merged that it may be worth running
// again, due to a better estimate of character size.
bool StrokeWidth::FixBrokenCJK(TO_BLOCK* block) {
BLOBNBOX_LIST* blobs = &block->blobs;
int median_height = UpperQuartileCJKSize(gridsize(), blobs);
int max_dist = static_cast<int>(median_height * kCJKBrokenDistanceFraction);
int max_size = static_cast<int>(median_height * kCJKAspectRatio);
int num_fixed = 0;
BLOBNBOX_IT blob_it(blobs);
for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
BLOBNBOX* blob = blob_it.data();
if (blob->cblob() == NULL || blob->cblob()->out_list()->empty())
continue;
TBOX bbox = blob->bounding_box();
bool debug = AlignedBlob::WithinTestRegion(3, bbox.left(),
bbox.bottom());
if (debug) {
tprintf("Checking for Broken CJK (max size=%d):", max_size);
bbox.print();
}
// Generate a list of blobs that overlap or are near enough to merge.
BLOBNBOX_CLIST overlapped_blobs;
AccumulateOverlaps(blob, debug, max_size, max_dist,
&bbox, &overlapped_blobs);
if (!overlapped_blobs.empty()) {
// There are overlapping blobs, so qualify them as being satisfactory
// before removing them from the grid and replacing them with the union.
// The final box must be roughly square.
if (bbox.width() > bbox.height() * kCJKAspectRatio ||
bbox.height() > bbox.width() * kCJKAspectRatio) {
if (debug) {
tprintf("Bad final aspectratio:");
bbox.print();
}
continue;
}
// There can't be too many blobs to merge.
if (overlapped_blobs.length() >= kCJKMaxComponents) {
if (debug)
tprintf("Too many neighbours: %d\n", overlapped_blobs.length());
continue;
}
// The strokewidths must match amongst the join candidates.
BLOBNBOX_C_IT n_it(&overlapped_blobs);
for (n_it.mark_cycle_pt(); !n_it.cycled_list(); n_it.forward()) {
BLOBNBOX* neighbour = NULL;
neighbour = n_it.data();
if (!blob->MatchingStrokeWidth(*neighbour, kStrokeWidthFractionCJK,
kStrokeWidthCJK))
break;
}
if (!n_it.cycled_list()) {
if (debug) {
tprintf("Bad stroke widths:");
PrintBoxWidths(blob);
}
continue; // Not good enough.
}
// Merge all the candidates into blob.
// We must remove blob from the grid and reinsert it after merging
// to maintain the integrity of the grid.
RemoveBBox(blob);
// Everything else will be calculated later.
for (n_it.mark_cycle_pt(); !n_it.cycled_list(); n_it.forward()) {
BLOBNBOX* neighbour = n_it.data();
RemoveBBox(neighbour);
// Mark empty blob for deletion.
neighbour->set_region_type(BRT_NOISE);
blob->really_merge(neighbour);
if (rerotation_.x() != 1.0f || rerotation_.y() != 0.0f) {
blob->rotate_box(rerotation_);
}
}
InsertBBox(true, true, blob);
++num_fixed;
if (debug) {
tprintf("Done! Final box:");
bbox.print();
}
}
}
// Count remaining blobs.
int num_remaining = 0;
for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
BLOBNBOX* blob = blob_it.data();
if (blob->cblob() != NULL && !blob->cblob()->out_list()->empty()) {
++num_remaining;
}
}
// Permanently delete all the marked blobs after first removing all
// references in the neighbour members.
block->DeleteUnownedNoise();
return num_fixed > num_remaining * kBrokenCJKIterationFraction;
}
// Helper function to determine whether it is reasonable to merge the
// bbox and the nbox for repairing broken CJK.
// The distance apart must not exceed max_dist, the combined size must
// not exceed max_size, and the aspect ratio must either improve or at
// least not get worse by much.
static bool AcceptableCJKMerge(const TBOX& bbox, const TBOX& nbox,
bool debug, int max_size, int max_dist,
int* x_gap, int* y_gap) {
*x_gap = bbox.x_gap(nbox);
*y_gap = bbox.y_gap(nbox);
TBOX merged(nbox);
merged += bbox;
if (debug) {
tprintf("gaps = %d, %d, merged_box:", *x_gap, *y_gap);
merged.print();
}
if (*x_gap <= max_dist && *y_gap <= max_dist &&
merged.width() <= max_size && merged.height() <= max_size) {
// Close enough to call overlapping. Check aspect ratios.
double old_ratio = static_cast<double>(bbox.width()) / bbox.height();
if (old_ratio < 1.0) old_ratio = 1.0 / old_ratio;
double new_ratio = static_cast<double>(merged.width()) / merged.height();
if (new_ratio < 1.0) new_ratio = 1.0 / new_ratio;
if (new_ratio <= old_ratio * kCJKAspectRatioIncrease)
return true;
}
return false;
}
// Collect blobs that overlap or are within max_dist of the input bbox.
// Return them in the list of blobs and expand the bbox to be the union
// of all the boxes. not_this is excluded from the search, as are blobs
// that cause the merged box to exceed max_size in either dimension.
void StrokeWidth::AccumulateOverlaps(const BLOBNBOX* not_this, bool debug,
int max_size, int max_dist,
TBOX* bbox, BLOBNBOX_CLIST* blobs) {
// While searching, nearests holds the nearest failed blob in each
// direction. When we have a nearest in each of the 4 directions, then
// the search is over, and at this point the final bbox must not overlap
// any of the nearests.
BLOBNBOX* nearests[BND_COUNT];
for (int i = 0; i < BND_COUNT; ++i) {
nearests[i] = NULL;
}
int x = (bbox->left() + bbox->right()) / 2;
int y = (bbox->bottom() + bbox->top()) / 2;
// Run a radial search for blobs that overlap or are sufficiently close.
BlobGridSearch radsearch(this);
radsearch.StartRadSearch(x, y, kCJKRadius);
BLOBNBOX* neighbour;
while ((neighbour = radsearch.NextRadSearch()) != NULL) {
if (neighbour == not_this) continue;
TBOX nbox = neighbour->bounding_box();
int x_gap, y_gap;
if (AcceptableCJKMerge(*bbox, nbox, debug, max_size, max_dist,
&x_gap, &y_gap)) {
// Close enough to call overlapping. Merge boxes.
*bbox += nbox;
blobs->add_sorted(SortByBoxLeft<BLOBNBOX>, true, neighbour);
if (debug) {
tprintf("Added:");
nbox.print();
}
// Since we merged, search the nearests, as some might now me mergeable.
for (int dir = 0; dir < BND_COUNT; ++dir) {
if (nearests[dir] == NULL) continue;
nbox = nearests[dir]->bounding_box();
if (AcceptableCJKMerge(*bbox, nbox, debug, max_size,
max_dist, &x_gap, &y_gap)) {
// Close enough to call overlapping. Merge boxes.
*bbox += nbox;
blobs->add_sorted(SortByBoxLeft<BLOBNBOX>, true, nearests[dir]);
if (debug) {
tprintf("Added:");
nbox.print();
}
nearests[dir] = NULL;
dir = -1; // Restart the search.
}
}
} else if (x_gap < 0 && x_gap <= y_gap) {
// A vertical neighbour. Record the nearest.
BlobNeighbourDir dir = nbox.top() > bbox->top() ? BND_ABOVE : BND_BELOW;
if (nearests[dir] == NULL ||
y_gap < bbox->y_gap(nearests[dir]->bounding_box())) {
nearests[dir] = neighbour;
}
} else if (y_gap < 0 && y_gap <= x_gap) {
// A horizontal neighbour. Record the nearest.
BlobNeighbourDir dir = nbox.left() > bbox->left() ? BND_RIGHT : BND_LEFT;
if (nearests[dir] == NULL ||
x_gap < bbox->x_gap(nearests[dir]->bounding_box())) {
nearests[dir] = neighbour;
}
}
// If all nearests are non-null, then we have finished.
if (nearests[BND_LEFT] && nearests[BND_RIGHT] &&
nearests[BND_ABOVE] && nearests[BND_BELOW])
break;
}
// Final overlap with a nearest is not allowed.
for (int dir = 0; dir < BND_COUNT; ++dir) {
if (nearests[dir] == NULL) continue;
const TBOX& nbox = nearests[dir]->bounding_box();
if (debug) {
tprintf("Testing for overlap with:");
nbox.print();
}
if (bbox->overlap(nbox)) {
blobs->shallow_clear();
if (debug)
tprintf("Final box overlaps nearest\n");
return;
}
}
}
// For each blob in this grid, Finds the textline direction to be horizontal
// or vertical according to distance to neighbours and 1st and 2nd order
// neighbours. Non-text tends to end up without a definite direction.
// Result is setting of the neighbours and vert_possible/horz_possible
// flags in the BLOBNBOXes currently in this grid.
// This function is called more than once if page orientation is uncertain,
// so display_if_debugging is true on the final call to display the results.
void StrokeWidth::FindTextlineFlowDirection(PageSegMode pageseg_mode,
bool display_if_debugging) {
BlobGridSearch gsearch(this);
BLOBNBOX* bbox;
// For every bbox in the grid, set its neighbours.
gsearch.StartFullSearch();
while ((bbox = gsearch.NextFullSearch()) != NULL) {
SetNeighbours(false, display_if_debugging, bbox);
}
// Where vertical or horizontal wins by a big margin, clarify it.
gsearch.StartFullSearch();
while ((bbox = gsearch.NextFullSearch()) != NULL) {
SimplifyObviousNeighbours(bbox);
}
// Now try to make the blobs only vertical or horizontal using neighbours.
gsearch.StartFullSearch();
while ((bbox = gsearch.NextFullSearch()) != NULL) {
if (FindingVerticalOnly(pageseg_mode)) {
bbox->set_vert_possible(true);
bbox->set_horz_possible(false);
} else if (FindingHorizontalOnly(pageseg_mode)) {
bbox->set_vert_possible(false);
bbox->set_horz_possible(true);
} else {
SetNeighbourFlows(bbox);
}
}
if ((textord_tabfind_show_strokewidths && display_if_debugging) ||
textord_tabfind_show_strokewidths > 1) {
initial_widths_win_ = DisplayGoodBlobs("InitialStrokewidths", 400, 0);
}
// Improve flow direction with neighbours.
gsearch.StartFullSearch();
while ((bbox = gsearch.NextFullSearch()) != NULL) {
SmoothNeighbourTypes(pageseg_mode, false, bbox);
}
// Now allow reset of firm values to fix renegades.
gsearch.StartFullSearch();
while ((bbox = gsearch.NextFullSearch()) != NULL) {
SmoothNeighbourTypes(pageseg_mode, true, bbox);
}
// Repeat.
gsearch.StartFullSearch();
while ((bbox = gsearch.NextFullSearch()) != NULL) {
SmoothNeighbourTypes(pageseg_mode, true, bbox);
}
if ((textord_tabfind_show_strokewidths && display_if_debugging) ||
textord_tabfind_show_strokewidths > 1) {
widths_win_ = DisplayGoodBlobs("ImprovedStrokewidths", 800, 0);
}
}
// Sets the neighbours and good_stroke_neighbours members of the blob by
// searching close on all 4 sides.
// When finding leader dots/dashes, there is a slightly different rule for
// what makes a good neighbour.
void StrokeWidth::SetNeighbours(bool leaders, bool activate_line_trap,
BLOBNBOX* blob) {
int line_trap_count = 0;
for (int dir = 0; dir < BND_COUNT; ++dir) {
BlobNeighbourDir bnd = static_cast<BlobNeighbourDir>(dir);
line_trap_count += FindGoodNeighbour(bnd, leaders, blob);
}
if (line_trap_count > 0 && activate_line_trap) {
// It looks like a line so isolate it by clearing its neighbours.
blob->ClearNeighbours();
const TBOX& box = blob->bounding_box();
blob->set_region_type(box.width() > box.height() ? BRT_HLINE : BRT_VLINE);
}
}
// Sets the good_stroke_neighbours member of the blob if it has a
// GoodNeighbour on the given side.
// Also sets the neighbour in the blob, whether or not a good one is found.
// Returns the number of blobs in the nearby search area that would lead us to
// believe that this blob is a line separator.
// Leaders get extra special lenient treatment.
int StrokeWidth::FindGoodNeighbour(BlobNeighbourDir dir, bool leaders,
BLOBNBOX* blob) {
// Search for neighbours that overlap vertically.
TBOX blob_box = blob->bounding_box();
bool debug = AlignedBlob::WithinTestRegion(2, blob_box.left(),
blob_box.bottom());
if (debug) {
tprintf("FGN in dir %d for blob:", dir);
blob_box.print();
}
int top = blob_box.top();
int bottom = blob_box.bottom();
int left = blob_box.left();
int right = blob_box.right();
int width = right - left;
int height = top - bottom;
// A trap to detect lines tests for the min dimension of neighbours
// being larger than a multiple of the min dimension of the line
// and the larger dimension being smaller than a fraction of the max
// dimension of the line.
int line_trap_max = MAX(width, height) / kLineTrapLongest;
int line_trap_min = MIN(width, height) * kLineTrapShortest;
int line_trap_count = 0;
int min_good_overlap = (dir == BND_LEFT || dir == BND_RIGHT)
? height / 2 : width / 2;
int min_decent_overlap = (dir == BND_LEFT || dir == BND_RIGHT)
? height / 3 : width / 3;
if (leaders)
min_good_overlap = min_decent_overlap = 1;
int search_pad = static_cast<int>(
sqrt(static_cast<double>(width * height)) * kNeighbourSearchFactor);
if (gridsize() > search_pad)
search_pad = gridsize();
TBOX search_box = blob_box;
// Pad the search in the appropriate direction.
switch (dir) {
case BND_LEFT:
search_box.set_left(search_box.left() - search_pad);
break;
case BND_RIGHT:
search_box.set_right(search_box.right() + search_pad);
break;
case BND_BELOW:
search_box.set_bottom(search_box.bottom() - search_pad);
break;
case BND_ABOVE:
search_box.set_top(search_box.top() + search_pad);
break;
case BND_COUNT:
return 0;
}
BlobGridSearch rectsearch(this);
rectsearch.StartRectSearch(search_box);
BLOBNBOX* best_neighbour = NULL;
double best_goodness = 0.0;
bool best_is_good = false;
BLOBNBOX* neighbour;
while ((neighbour = rectsearch.NextRectSearch()) != NULL) {
TBOX nbox = neighbour->bounding_box();
if (neighbour == blob)
continue;
int mid_x = (nbox.left() + nbox.right()) / 2;
if (mid_x < blob->left_rule() || mid_x > blob->right_rule())
continue; // In a different column.
if (debug) {
tprintf("Neighbour at:");
nbox.print();
}
// Last-minute line detector. There is a small upper limit to the line
// width accepted by the morphological line detector.
int n_width = nbox.width();
int n_height = nbox.height();
if (MIN(n_width, n_height) > line_trap_min &&
MAX(n_width, n_height) < line_trap_max)
++line_trap_count;
// Heavily joined text, such as Arabic may have very different sizes when
// looking at the maxes, but the heights may be almost identical, so check
// for a difference in height if looking sideways or width vertically.
if (TabFind::VeryDifferentSizes(MAX(n_width, n_height),
MAX(width, height)) &&
(((dir == BND_LEFT || dir ==BND_RIGHT) &&
TabFind::DifferentSizes(n_height, height)) ||
((dir == BND_BELOW || dir ==BND_ABOVE) &&
TabFind::DifferentSizes(n_width, width)))) {
if (debug) tprintf("Bad size\n");
continue; // Could be a different font size or non-text.
}
// Amount of vertical overlap between the blobs.
int overlap;
// If the overlap is along the short side of the neighbour, and it
// is fully overlapped, then perp_overlap holds the length of the long
// side of the neighbour. A measure to include hyphens and dashes as
// legitimate neighbours.
int perp_overlap;
int gap;
if (dir == BND_LEFT || dir == BND_RIGHT) {
overlap = MIN(nbox.top(), top) - MAX(nbox.bottom(), bottom);
if (overlap == nbox.height() && nbox.width() > nbox.height())
perp_overlap = nbox.width();
else
perp_overlap = overlap;
gap = dir == BND_LEFT ? left - nbox.left() : nbox.right() - right;
if (gap <= 0) {
if (debug) tprintf("On wrong side\n");
continue; // On the wrong side.
}
gap -= n_width;
} else {
overlap = MIN(nbox.right(), right) - MAX(nbox.left(), left);
if (overlap == nbox.width() && nbox.height() > nbox.width())
perp_overlap = nbox.height();
else
perp_overlap = overlap;
gap = dir == BND_BELOW ? bottom - nbox.bottom() : nbox.top() - top;
if (gap <= 0) {