28 static BOOL_VAR(textord_space_size_is_variable,
false,
29 "If true, word delimiter spaces are assumed to have "
30 "variable width, even though characters have fixed pitch.");
35 static const float kFPTolerance = 0.1;
39 static const float kFixedPitchThreshold = 0.35;
44 SimpleStats(): finalized_(false), values_() { }
52 void Add(
float value) {
53 values_.push_back(value);
58 values_.sort(float_compare);
62 float ile(
double frac) {
63 if (!finalized_) Finish();
64 if (values_.empty())
return 0.0;
65 if (frac >= 1.0)
return values_.back();
66 if (frac <= 0.0 || values_.size() == 1)
return values_[0];
67 int index = static_cast<int>((values_.size() - 1) * frac);
68 float reminder = (values_.size() - 1) * frac - index;
70 return values_[index] * (1.0 - reminder) +
71 values_[index + 1] * reminder;
79 if (!finalized_) Finish();
80 if (values_.empty())
return 0.0;
85 return values_.size();
89 static int float_compare(
const void* a,
const void* b) {
90 const auto* f_a = static_cast<const float*>(a);
91 const auto* f_b = static_cast<const float*>(b);
92 return (*f_a > *f_b) ? 1 : ((*f_a < *f_b) ? -1 : 0);
102 class LocalCorrelation {
109 LocalCorrelation(): finalized_(false) { }
110 ~LocalCorrelation() { }
113 values_.sort(float_pair_compare);
121 void Add(
float x,
float y,
int v) {
122 struct float_pair value;
126 values_.push_back(value);
130 float EstimateYFor(
float x,
float r) {
132 int start = 0, end = values_.size();
135 while (start < values_.size() && values_[start].x < x * (1.0 - r)) start++;
136 while (end - 1 >= 0 && values_[end - 1].x > x * (1.0 + r)) end--;
142 end = values_.size();
148 for (
int i = start; i < end; i++) {
149 rc += values_[i].vote * x * values_[i].y / values_[i].x;
150 vote += values_[i].vote;
157 static int float_pair_compare(
const void* a,
const void* b) {
158 const auto* f_a = static_cast<const float_pair*>(a);
159 const auto* f_b = static_cast<const float_pair*>(b);
160 return (f_a->x > f_b->x) ? 1 : ((f_a->x < f_b->x) ? -1 : 0);
172 ALIGN_UNKNOWN, ALIGN_GOOD, ALIGN_BAD
175 FPChar(): box_(), real_body_(),
176 from_(nullptr), to_(nullptr), num_blobs_(0), max_gap_(0),
177 final_(false), alignment_(ALIGN_UNKNOWN),
178 merge_to_prev_(false), delete_flag_(false) {
191 void Merge(
const FPChar &next) {
192 int gap = real_body_.x_gap(next.real_body_);
193 if (gap > max_gap_) max_gap_ = gap;
196 real_body_ += next.real_body_;
198 num_blobs_ += next.num_blobs_;
202 const TBOX &box()
const {
return box_; }
203 void set_box(
const TBOX &box) {
206 const TBOX &real_body()
const {
return real_body_; }
208 bool is_final()
const {
return final_; }
209 void set_final(
bool flag) {
213 const Alignment& alignment()
const {
216 void set_alignment(Alignment alignment) {
217 alignment_ = alignment;
220 bool merge_to_prev()
const {
221 return merge_to_prev_;
223 void set_merge_to_prev(
bool flag) {
224 merge_to_prev_ = flag;
227 bool delete_flag()
const {
230 void set_delete_flag(
bool flag) {
234 int max_gap()
const {
238 int num_blobs()
const {
254 Alignment alignment_;
267 FPRow() : all_pitches_(), all_gaps_(), good_pitches_(), good_gaps_(),
268 heights_(), characters_() {
280 void EstimatePitch(
bool pass1);
296 void MergeFragments();
300 void FinalizeLargeChars();
303 void OutputEstimations();
305 void DebugOutputResult(
int row_index);
308 return good_pitches_.size();
315 float estimated_pitch() {
316 return estimated_pitch_;
319 void set_estimated_pitch(
float v) {
320 estimated_pitch_ = v;
327 float height_pitch_ratio() {
328 if (good_pitches_.size() < 2)
return -1.0;
329 return height_ / good_pitches_.median();
337 return characters_.size();
340 return &characters_[i];
343 const TBOX &box(
int i) {
344 return characters_[i].box();
347 const TBOX &real_body(
int i) {
348 return characters_[i].real_body();
351 bool is_box_modified(
int i) {
352 return !(characters_[i].box() == characters_[i].real_body());
355 float center_x(
int i) {
356 return (characters_[i].box().left() + characters_[i].box().right()) / 2.0;
359 bool is_final(
int i) {
360 return characters_[i].is_final();
363 void finalize(
int i) {
364 characters_[i].set_final(
true);
367 bool is_good(
int i) {
368 return characters_[i].alignment() == FPChar::ALIGN_GOOD;
371 void mark_good(
int i) {
372 characters_[i].set_alignment(FPChar::ALIGN_GOOD);
375 void mark_bad(
int i) {
376 characters_[i].set_alignment(FPChar::ALIGN_BAD);
379 void clear_alignment(
int i) {
380 characters_[i].set_alignment(FPChar::ALIGN_UNKNOWN);
384 static float x_overlap_fraction(
const TBOX& box1,
const TBOX& box2) {
385 if (std::min(box1.
width(), box2.
width()) == 0)
return 0.0;
386 return -box1.
x_gap(box2) / static_cast<float>(std::min(box1.
width(), box2.
width()));
389 static bool mostly_overlap(
const TBOX& box1,
const TBOX& box2) {
390 return x_overlap_fraction(box1, box2) > 0.9;
393 static bool significant_overlap(
const TBOX& box1,
const TBOX& box2) {
394 if (std::min(box1.
width(), box2.
width()) == 0)
return false;
395 int overlap = -box1.
x_gap(box2);
396 return overlap > 1 || x_overlap_fraction(box1, box2) > 0.1;
399 static float box_pitch(
const TBOX& ref,
const TBOX& box) {
404 static bool is_good_pitch(
float pitch,
const TBOX& box1,
const TBOX& box2) {
406 if (box1.
width() >= pitch * (1.0 + kFPTolerance) ||
407 box2.
width() >= pitch * (1.0 + kFPTolerance) ||
408 box1.
height() >= pitch * (1.0 + kFPTolerance) ||
409 box2.
height() >= pitch * (1.0 + kFPTolerance))
return false;
411 const float real_pitch = box_pitch(box1, box2);
412 if (fabs(real_pitch - pitch) < pitch * kFPTolerance)
return true;
414 if (textord_space_size_is_variable) {
417 if (real_pitch > pitch && real_pitch < pitch * 2.0 &&
418 real_pitch - box1.
x_gap(box2) < pitch) {
425 static bool is_interesting_blob(
const BLOBNBOX *blob) {
432 for (
int i = 0; i < characters_.size(); ++i) {
433 if (!characters_[i].delete_flag()) {
434 if (index != i) characters_[index] = characters_[i];
438 characters_.truncate(index);
442 float estimated_pitch_ = 0.0f;
444 float height_ = 0.0f;
448 SimpleStats all_pitches_;
450 SimpleStats all_gaps_;
453 SimpleStats good_pitches_;
456 SimpleStats good_gaps_;
458 SimpleStats heights_;
461 TO_ROW *real_row_ =
nullptr;
464 void FPRow::Init(
TO_ROW *row) {
473 for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
474 if (is_interesting_blob(blob_it.data())) {
476 fp_char.Init(blob_it.data());
478 if (!characters_.empty() &&
479 significant_overlap(fp_char.box(), characters_.back().box())) {
480 characters_.back().Merge(fp_char);
482 characters_.push_back(fp_char);
484 TBOX bound = blob_it.data()->bounding_box();
486 heights_.Add(bound.
height());
491 height_ = heights_.ile(0.875);
494 void FPRow::OutputEstimations() {
495 if (good_pitches_.size() == 0) {
501 pitch_ = good_pitches_.median();
502 real_row_->fixed_pitch = pitch_;
506 real_row_->kern_size = real_row_->pr_nonsp =
507 std::min(good_gaps_.ile(0.125), std::max(pitch_ - height_, 0.0f));
508 real_row_->body_size = pitch_ - real_row_->kern_size;
510 if (good_pitches_.size() < all_pitches_.size() * kFixedPitchThreshold) {
519 }
else if (good_pitches_.size() > all_pitches_.size() * 0.75) {
525 real_row_->space_size = real_row_->pr_space = pitch_;
528 real_row_->min_space = (pitch_ + good_gaps_.minimum()) * 0.5;
532 real_row_->max_nonspace = std::max(pitch_ * 0.25 + good_gaps_.minimum(),
533 static_cast<double>(good_gaps_.ile(0.875)));
535 int space_threshold =
536 std::min((real_row_->max_nonspace + real_row_->min_space) / 2,
537 static_cast<int>(real_row_->xheight));
541 for (
size_t i = 0; i < num_chars(); ++i) {
542 if (characters_[i].max_gap() > real_row_->max_nonspace) {
543 real_row_->max_nonspace = characters_[i].max_gap();
546 real_row_->space_threshold =
547 std::min((real_row_->max_nonspace + real_row_->min_space) / 2,
548 static_cast<int>(real_row_->xheight));
549 real_row_->used_dm_model =
false;
552 ICOORDELT_IT cell_it = &real_row_->char_cells;
553 auto *cell =
new ICOORDELT(real_body(0).left(), 0);
554 cell_it.add_after_then_move(cell);
556 int right = real_body(0).right();
557 for (
size_t i = 1; i < num_chars(); ++i) {
562 if ((is_final(i - 1) || is_final(i)) &&
563 real_body(i - 1).x_gap(real_body(i)) > space_threshold) {
565 cell_it.add_after_then_move(cell);
566 while (right + pitch_ < box(i).left()) {
569 cell_it.add_after_then_move(cell);
571 right = box(i).
left();
573 cell =
new ICOORDELT((right + real_body(i).left()) / 2, 0);
574 cell_it.add_after_then_move(cell);
575 right = real_body(i).right();
579 cell_it.add_after_then_move(cell);
586 void FPRow::EstimatePitch(
bool pass1) {
587 good_pitches_.Clear();
588 all_pitches_.Clear();
592 if (num_chars() == 0)
return;
595 bool prev_was_good = is_good(0);
598 heights_.Add(box(0).height());
599 for (
size_t i = 1; i < num_chars(); i++) {
601 int32_t pitch = cx1 - cx0;
602 int32_t gap = std::max(0, real_body(i - 1).x_gap(real_body(i)));
604 heights_.Add(box(i).height());
607 if (pitch > height_ * 0.5) {
608 all_pitches_.Add(pitch);
617 if (pass1 || (prev_was_good &&
618 fabs(estimated_pitch_ - pitch) <
619 kFPTolerance * estimated_pitch_)) {
620 good_pitches_.Add(pitch);
621 if (!is_box_modified(i - 1) && !is_box_modified(i)) {
625 prev_was_good =
true;
627 prev_was_good =
false;
633 good_pitches_.Finish();
634 all_pitches_.Finish();
639 height_ = heights_.ile(0.875);
640 if (all_pitches_.size() == 0) {
643 }
else if (good_pitches_.size() < 2) {
646 pitch_ = all_pitches_.median();
648 gap_ = all_gaps_.ile(0.125);
650 pitch_ = good_pitches_.median();
652 gap_ = good_gaps_.ile(0.125);
656 void FPRow::DebugOutputResult(
int row_index) {
657 if (num_chars() > 0) {
658 tprintf(
"Row %d: pitch_decision=%d, fixed_pitch=%f, max_nonspace=%d, "
659 "space_size=%f, space_threshold=%d, xheight=%f\n",
660 row_index, static_cast<int>(real_row_->pitch_decision),
661 real_row_->fixed_pitch, real_row_->max_nonspace,
662 real_row_->space_size, real_row_->space_threshold,
665 for (
unsigned i = 0; i < num_chars(); i++) {
666 tprintf(
"Char %u: is_final=%d is_good=%d num_blobs=%d: ",
667 i, is_final(i), is_good(i),
character(i)->num_blobs());
673 void FPRow::Pass1Analyze() {
674 if (num_chars() < 2)
return;
676 if (estimated_pitch_ > 0.0f) {
677 for (
size_t i = 2; i < num_chars(); i++) {
678 if (is_good_pitch(estimated_pitch_, box(i - 2), box(i-1)) &&
679 is_good_pitch(estimated_pitch_, box(i - 1), box(i))) {
684 for (
size_t i = 2; i < num_chars(); i++) {
685 if (is_good_pitch(box_pitch(box(i-2), box(i-1)), box(i - 1), box(i))) {
691 character(num_chars() - 1)->set_alignment(
692 character(num_chars() - 2)->alignment());
695 bool FPRow::Pass2Analyze() {
696 bool changed =
false;
697 if (num_chars() <= 1 || estimated_pitch_ == 0.0f) {
700 for (
size_t i = 0; i < num_chars(); i++) {
701 if (is_final(i))
continue;
703 FPChar::Alignment alignment =
character(i)->alignment();
704 bool intersecting =
false;
705 bool not_intersecting =
false;
707 if (i < num_chars() - 1 && is_final(i + 1)) {
711 bool skipped_whitespaces =
false;
712 float c1 = center_x(i + 1) - 1.5 * estimated_pitch_;
713 while (c1 > box(i).right()) {
714 skipped_whitespaces =
true;
715 c1 -= estimated_pitch_;
717 TBOX ibody(c1, box(i).bottom(), c1 + estimated_pitch_, box(i).top());
723 while (j >= 0 && !is_final(j) && mostly_overlap(ibody, box(j)) &&
725 estimated_pitch_ * (1 + kFPTolerance)) {
730 if (j >= 0 && significant_overlap(ibody, box(j))) {
733 if (!is_final(j)) intersecting =
true;
735 not_intersecting =
true;
741 if (!skipped_whitespaces) mark_good(i);
745 if (box(i).width() <= estimated_pitch_ * 0.5) {
752 for (
int k = i; k > j + 1; k--) {
759 if (i > 0 && is_final(i - 1)) {
763 bool skipped_whitespaces =
false;
764 float c1 = center_x(i - 1) + 1.5 * estimated_pitch_;
765 while (c1 < box(i).left()) {
766 skipped_whitespaces =
true;
767 c1 += estimated_pitch_;
769 TBOX ibody(c1 - estimated_pitch_, box(i).bottom(), c1, box(i).top());
773 while (j < num_chars() && !is_final(j) && mostly_overlap(ibody, box(j)) &&
775 estimated_pitch_ * (1 + kFPTolerance)) {
780 if (j < num_chars() && significant_overlap(ibody, box(j))) {
781 if (!is_final(j)) intersecting =
true;
783 not_intersecting =
true;
786 if (!skipped_whitespaces) mark_good(i);
787 if (box(i).width() <= estimated_pitch_ * 0.5) {
794 for (
size_t k = i + 1; k < j; k++) {
804 if (intersecting && !not_intersecting) mark_bad(i);
805 if (
character(i)->alignment() != alignment ||
814 void FPRow::MergeFragments() {
817 for (
size_t j = 0; j < num_chars(); ++j) {
821 clear_alignment(last_char);
822 character(j-1)->set_merge_to_prev(
false);
830 void FPRow::FinalizeLargeChars() {
831 float row_pitch = estimated_pitch();
832 for (
size_t i = 0; i < num_chars(); i++) {
833 if (is_final(i))
continue;
836 if (i > 0 && is_final(i - 1) && i < num_chars() - 1 && is_final(i + 1)) {
841 float cx = center_x(i);
842 TBOX ibody(cx - 0.5 * row_pitch, 0, cx + 0.5 * row_pitch, 1);
847 if (x_overlap_fraction(ibody, box(i - 1)) > 0.1)
continue;
848 if (!is_final(i - 1)) {
849 TBOX merged = box(i);
850 merged += box(i - 1);
851 if (merged.
width() < row_pitch)
continue;
857 if (i < num_chars() - 1) {
858 if (x_overlap_fraction(ibody, box(i + 1)) > 0.1)
continue;
859 if (!is_final(i + 1)) {
860 TBOX merged = box(i);
861 merged += box(i + 1);
862 if (merged.
width() < row_pitch)
continue;
873 for (
size_t i = 0; i < num_chars(); i++) {
874 if (!is_final(i))
continue;
875 bool good_pitch =
false;
876 bool bad_pitch =
false;
877 if (i > 0 && is_final(i - 1)) {
878 if (is_good_pitch(row_pitch, box(i - 1), box(i))) {
884 if (i < num_chars() - 1 && is_final(i + 1)) {
885 if (is_good_pitch(row_pitch, box(i), box(i + 1))) {
891 if (good_pitch && !bad_pitch) mark_good(i);
892 else if (!good_pitch && bad_pitch) mark_bad(i);
898 FPAnalyzer(
ICOORD page_tr, TO_BLOCK_LIST *port_blocks);
901 void Pass1Analyze() {
902 for (
auto & row : rows_) row.Pass1Analyze();
908 void EstimatePitch(
bool pass1);
910 bool maybe_fixed_pitch() {
912 rows_.size() <= num_bad_rows_ + num_tall_rows_ + 1)
return false;
916 void MergeFragments() {
917 for (
auto & row : rows_) row.MergeFragments();
920 void FinalizeLargeChars() {
921 for (
auto & row : rows_) row.FinalizeLargeChars();
924 bool Pass2Analyze() {
925 bool changed =
false;
926 for (
auto & row : rows_) {
927 if (row.Pass2Analyze()) {
934 void OutputEstimations() {
935 for (
auto & row : rows_) row.OutputEstimations();
939 void DebugOutputResult() {
940 tprintf(
"FPAnalyzer: final result\n");
941 for (
size_t i = 0; i < rows_.size(); i++) rows_[i].DebugOutputResult(i);
949 unsigned max_iteration() {
952 return max_chars_per_row_ + 100;
957 std::vector<FPRow> rows_;
958 unsigned num_tall_rows_;
959 unsigned num_bad_rows_;
961 unsigned num_empty_rows_;
962 unsigned max_chars_per_row_;
965 FPAnalyzer::FPAnalyzer(
ICOORD page_tr, TO_BLOCK_LIST *port_blocks)
970 max_chars_per_row_(0)
972 TO_BLOCK_IT block_it(port_blocks);
974 for (block_it.mark_cycle_pt(); !block_it.cycled_list();
975 block_it.forward()) {
983 for (block_it.mark_cycle_pt(); !block_it.cycled_list();
984 block_it.forward()) {
985 TO_ROW_IT row_it = block_it.data()->get_rows();
986 for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
988 row.Init(row_it.data());
989 rows_.push_back(row);
990 size_t num_chars = rows_.back().num_chars();
991 if (num_chars <= 1) num_empty_rows_++;
992 if (num_chars > max_chars_per_row_) max_chars_per_row_ = num_chars;
997 void FPAnalyzer::EstimatePitch(
bool pass1) {
998 LocalCorrelation pitch_height_stats;
1002 pitch_height_stats.Clear();
1003 for (
auto & row : rows_) {
1004 row.EstimatePitch(pass1);
1005 if (row.good_pitches()) {
1006 pitch_height_stats.Add(row.height() + row.gap(),
1007 row.pitch(), row.good_pitches());
1008 if (row.height_pitch_ratio() > 1.1) num_tall_rows_++;
1014 pitch_height_stats.Finish();
1015 for (
auto & row : rows_) {
1016 if (row.good_pitches() >= 5) {
1019 row.set_estimated_pitch(row.pitch());
1020 }
else if (row.num_chars() > 1) {
1021 float estimated_pitch =
1022 pitch_height_stats.EstimateYFor(row.height() + row.gap(),
1028 if (estimated_pitch > row.pitch() ||
1029 row.pitch() > row.height() * 2.0) {
1030 row.set_estimated_pitch(estimated_pitch);
1032 row.set_estimated_pitch(row.pitch());
1041 TO_BLOCK_LIST *port_blocks) {
1042 FPAnalyzer analyzer(page_tr, port_blocks);
1043 if (analyzer.num_rows() == 0)
return;
1045 analyzer.Pass1Analyze();
1046 analyzer.EstimatePitch(
true);
1050 analyzer.Pass1Analyze();
1051 analyzer.EstimatePitch(
true);
1054 if (!analyzer.maybe_fixed_pitch()) {
1056 tprintf(
"Page doesn't seem to contain fixed pitch rows\n");
1061 unsigned iteration = 0;
1063 analyzer.MergeFragments();
1064 analyzer.FinalizeLargeChars();
1065 analyzer.EstimatePitch(
false);
1067 }
while (analyzer.Pass2Analyze() && iteration < analyzer.max_iteration());
1070 tprintf(
"compute_fixed_pitch_cjk finished after %u iteration (limit=%u)\n",
1071 iteration, analyzer.max_iteration());
1074 analyzer.OutputEstimations();