19 #define _USE_MATH_DEFINES // for M_PI
22 #include "config_auto.h"
30 #include "allheaders.h"
65 : blobs_(to_row->blob_list()),
66 baseline_pt1_(0.0f, 0.0f), baseline_pt2_(0.0f, 0.0f),
67 baseline_error_(0.0), good_baseline_(false) {
81 row->
set_line(gradient, para_c, baseline_error_);
87 tprintf(
"Baseline (%g,%g)->(%g,%g), angle=%g, intercept=%g\n",
88 baseline_pt1_.
x(), baseline_pt1_.
y(),
89 baseline_pt2_.
x(), baseline_pt2_.
y(),
91 tprintf(
"Quant factor=%g, error=%g, good=%d, box:",
92 disp_quant_factor_, baseline_error_, good_baseline_);
93 bounding_box_.
print();
98 FCOORD baseline_dir(baseline_pt2_ - baseline_pt1_);
99 double angle = baseline_dir.
angle();
102 return fmod(angle + M_PI * 1.5, M_PI) - M_PI * 0.5;
109 float x = (std::max(bounding_box_.
left(), other.bounding_box_.
left()) +
110 std::min(bounding_box_.
right(), other.bounding_box_.
right())) / 2.0f;
115 return PerpDistanceFromBaseline(pt) + other.PerpDistanceFromBaseline(pt);
121 float middle_x = (bounding_box_.
left() + bounding_box_.
right()) / 2.0f;
123 return direction * middle_pos / direction.
length();
129 double denominator = baseline_pt2_.
x() - baseline_pt1_.
x();
130 if (denominator == 0.0)
131 return (baseline_pt1_.
y() + baseline_pt2_.
y()) / 2.0;
132 return baseline_pt1_.
y() +
133 (x - baseline_pt1_.
x()) * (baseline_pt2_.
y() - baseline_pt1_.
y()) /
146 BLOBNBOX_IT blob_it(blobs_);
148 for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
152 int x_middle = (box.
left() + box.
right()) / 2;
154 if (box.
bottom() < kDebugYCoord && box.
top() > kDebugYCoord) {
155 tprintf(
"Box bottom = %d, baseline pos=%d for box at:",
165 baseline_error_ = fitter_.
Fit(&pt1, &pt2);
168 if (baseline_error_ > max_baseline_error_ &&
174 if (error < baseline_error_ / 2.0) {
175 baseline_error_ = error;
183 debug = bounding_box_.
bottom() < kDebugYCoord &&
184 bounding_box_.
top() > kDebugYCoord
189 FCOORD direction(pt2 - pt1);
190 double target_offset = direction * pt1;
191 good_baseline_ =
false;
192 FitConstrainedIfBetter(debug, direction, 0.0, target_offset);
198 if (fabs(angle) > M_PI * 0.25) {
201 baseline_pt2_ = baseline_pt1_ +
FCOORD(1.0f, llsq.
m());
204 double c = llsq.
c(m);
205 baseline_error_ = llsq.
rms(m, c);
206 good_baseline_ =
false;
208 return good_baseline_;
214 const FCOORD& direction) {
215 SetupBlobDisplacements(direction);
216 if (displacement_modes_.
empty())
219 if (bounding_box_.
bottom() < kDebugYCoord &&
220 bounding_box_.
top() > kDebugYCoord && debug < 3)
223 FitConstrainedIfBetter(debug, direction, 0.0, displacement_modes_[0]);
231 double line_offset) {
232 if (blobs_->empty()) {
235 bounding_box_.
print();
240 double best_error = 0.0;
242 for (
int i = 0; i < displacement_modes_.
size(); ++i) {
243 double blob_y = displacement_modes_[i];
247 tprintf(
"Mode at %g has error %g from model \n", blob_y, error);
249 if (best_index < 0 || error < best_error) {
256 double model_margin = max_baseline_error_ - best_error;
257 if (best_index >= 0 && model_margin > 0.0) {
260 double perp_disp =
PerpDisp(direction);
261 double shift = displacement_modes_[best_index] - perp_disp;
262 if (fabs(shift) > max_baseline_error_) {
264 tprintf(
"Attempting linespacing model fit with mode %g to row at:",
265 displacement_modes_[best_index]);
266 bounding_box_.
print();
268 FitConstrainedIfBetter(debug, direction, model_margin,
269 displacement_modes_[best_index]);
270 }
else if (debug > 1) {
271 tprintf(
"Linespacing model only moves current line by %g for row at:",
273 bounding_box_.
print();
275 }
else if (debug > 1) {
276 tprintf(
"Linespacing model not close enough to any mode for row at:");
277 bounding_box_.
print();
279 return fmod(
PerpDisp(direction), line_spacing);
284 void BaselineRow::SetupBlobDisplacements(
const FCOORD& direction) {
290 double min_dist = FLT_MAX;
291 double max_dist = -FLT_MAX;
292 BLOBNBOX_IT blob_it(blobs_);
296 for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
300 if (box.
bottom() < kDebugYCoord && box.
top() > kDebugYCoord) debug =
true;
304 double offset = direction * blob_pos;
308 tprintf(
"Displacement %g for blob at:", offset);
317 for (
int i = 0; i < perp_blob_dists.
size(); ++i) {
318 dist_stats.add(
IntCastRounded(perp_blob_dists[i] / disp_quant_factor_), 1);
324 for (
int i = 0; i < scaled_modes.
size(); ++i) {
325 tprintf(
"Top mode = %g * %d\n",
326 scaled_modes[i].key * disp_quant_factor_, scaled_modes[i].data);
330 for (
int i = 0; i < scaled_modes.
size(); ++i)
331 displacement_modes_.
push_back(disp_quant_factor_ * scaled_modes[i].key);
344 void BaselineRow::FitConstrainedIfBetter(
int debug,
346 double cheat_allowance,
347 double target_offset) {
348 double halfrange = fit_halfrange_ * direction.
length();
349 double min_dist = target_offset - halfrange;
350 double max_dist = target_offset + halfrange;
352 double new_error = fitter_.
ConstrainedFit(direction, min_dist, max_dist,
353 debug > 2, &line_pt);
355 new_error -= cheat_allowance;
357 double new_angle = direction.
angle();
359 tprintf(
"Constrained error = %g, original = %g",
360 new_error, baseline_error_);
361 tprintf(
" angles = %g, %g, delta=%g vs threshold %g\n",
362 old_angle, new_angle,
365 bool new_good_baseline = new_error <= max_baseline_error_ &&
372 if (new_error <= baseline_error_ ||
373 (!good_baseline_ && new_good_baseline) ||
375 baseline_error_ = new_error;
376 baseline_pt1_ = line_pt;
377 baseline_pt2_ = baseline_pt1_ + direction;
378 good_baseline_ = new_good_baseline;
380 tprintf(
"Replacing with constrained baseline, good = %d\n",
383 }
else if (debug > 1) {
384 tprintf(
"Keeping old baseline\n");
390 double BaselineRow::PerpDistanceFromBaseline(
const FCOORD& pt)
const {
391 FCOORD baseline_vector(baseline_pt2_ - baseline_pt1_);
392 FCOORD offset_vector(pt - baseline_pt1_);
393 double distance = baseline_vector * offset_vector;
398 void BaselineRow::ComputeBoundingBox() {
399 BLOBNBOX_IT it(blobs_);
401 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
402 box += it.data()->bounding_box();
409 : block_(block), debug_level_(debug_level), non_text_block_(non_text),
410 good_skew_angle_(false), skew_angle_(0.0),
411 line_spacing_(block->line_spacing), line_offset_(0.0), model_error_(0.0) {
412 TO_ROW_IT row_it(block_->
get_rows());
413 for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
423 double line_offset) {
425 int multiple =
IntCastRounded((perp_disp - line_offset) / line_spacing);
426 double model_y = line_spacing * multiple + line_offset;
427 return fabs(perp_disp - model_y);
435 if (non_text_block_)
return false;
437 for (
int r = 0; r < rows_.size(); ++r) {
443 if (debug_level_ > 1)
447 if (!angles.
empty()) {
449 good_skew_angle_ =
true;
452 good_skew_angle_ =
false;
454 if (debug_level_ > 0) {
455 tprintf(
"Initial block skew angle = %g, good = %d\n",
456 skew_angle_, good_skew_angle_);
458 return good_skew_angle_;
464 if (non_text_block_)
return;
465 if (!good_skew_angle_) skew_angle_ = default_block_skew;
466 if (debug_level_ > 0)
467 tprintf(
"Adjusting block to skew angle %g\n", skew_angle_);
468 FCOORD direction(cos(skew_angle_), sin(skew_angle_));
469 for (
int r = 0; r < rows_.size(); ++r) {
472 if (debug_level_ > 1)
475 if (rows_.size() < 3 || !ComputeLineSpacing())
482 line_spacing_, line_offset_);
483 for (
int r = 1; r < rows_.size(); ++r) {
485 line_spacing_, line_offset_);
486 if (error < best_error) {
492 double offset = line_offset_;
493 for (
int r = best_row + 1; r < rows_.size(); ++r) {
494 offset = rows_[r]->AdjustBaselineToGrid(debug_level_, direction,
495 line_spacing_, offset);
497 offset = line_offset_;
498 for (
int r = best_row - 1; r >= 0; --r) {
499 offset = rows_[r]->AdjustBaselineToGrid(debug_level_, direction,
500 line_spacing_, offset);
506 if (line_spacing_ > 0.0) {
508 float min_spacing = std::min(block_->
line_spacing, static_cast<float>(line_spacing_));
509 if (min_spacing < block_->line_size)
516 TO_ROW_IT row_it(block_->
get_rows());
517 for (
int r = 0; r < rows_.size(); ++r, row_it.forward()) {
519 TO_ROW* to_row = row_it.data();
533 if (non_text_block_)
return;
537 FCOORD rotation(1.0f, 0.0f);
538 double gradient = tan(skew_angle_);
549 bool show_final_rows,
551 double gradient = tan(skew_angle_);
552 FCOORD rotation(1.0f, 0.0f);
554 if (enable_splines) {
559 TO_ROW_IT row_it = block_->
get_rows();
560 for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
561 TO_ROW* row = row_it.data();
562 int32_t xstarts[2] = { block_box.
left(), block_box.
right() };
563 double coeffs[3] = { 0.0, row->
line_m(), row->
line_c() };
578 #ifndef GRAPHICS_DISABLED
579 if (non_text_block_)
return;
580 double gradient = tan(skew_angle_);
581 FCOORD rotation(1.0f, 0.0f);
585 TO_ROW_IT row_it = block_->
get_rows();
586 for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
588 colour = static_cast<ScrollView::Color>(colour + 1);
596 if (block_->
blobs.length() > 0)
597 tprintf(
"%d blobs discarded as noise\n", block_->
blobs.length());
603 if (non_text_block_)
return;
604 TO_ROW_IT row_it = block_->
get_rows();
605 for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
606 row_it.data()->baseline.plot(pix_in);
616 bool BaselineBlock::ComputeLineSpacing() {
617 FCOORD direction(cos(skew_angle_), sin(skew_angle_));
619 ComputeBaselinePositions(direction, &row_positions);
620 if (row_positions.
size() < 2)
return false;
621 EstimateLineSpacing();
622 RefineLineSpacing(row_positions);
625 int non_trivial_gaps = 0;
626 int fitting_gaps = 0;
627 for (
int i = 1; i < row_positions.
size(); ++i) {
628 double row_gap = fabs(row_positions[i - 1] - row_positions[i]);
629 if (row_gap > max_baseline_error) {
631 if (fabs(row_gap - line_spacing_) <= max_baseline_error)
635 if (debug_level_ > 0) {
636 tprintf(
"Spacing %g, in %d rows, %d gaps fitted out of %d non-trivial\n",
637 line_spacing_, row_positions.
size(), fitting_gaps,
651 void BaselineBlock::ComputeBaselinePositions(
const FCOORD& direction,
654 for (
int r = 0; r < rows_.size(); ++r) {
655 BaselineRow* row = rows_[r];
656 const TBOX& row_box = row->bounding_box();
657 float x_middle = (row_box.
left() + row_box.
right()) / 2.0f;
658 FCOORD row_pos(x_middle, static_cast<float>(row->StraightYAtX(x_middle)));
659 float offset = direction * row_pos;
666 void BaselineBlock::EstimateLineSpacing() {
668 for (
int r = 0; r < rows_.size(); ++r) {
669 BaselineRow* row = rows_[r];
671 if (fabs(row->BaselineAngle()) > M_PI * 0.25)
continue;
673 const TBOX& row_box = row->bounding_box();
675 for (r2 = r + 1; r2 < rows_.size() &&
678 if (r2 < rows_.size()) {
679 BaselineRow* row2 = rows_[r2];
681 if (fabs(row2->BaselineAngle()) > M_PI * 0.25)
continue;
682 float spacing = row->SpaceBetween(*row2);
688 if (!spacings.
empty()) {
690 if (debug_level_ > 1)
691 tprintf(
"Estimate of linespacing = %g\n", line_spacing_);
700 double spacings[3], offsets[3], errors[3];
702 errors[0] = FitLineSpacingModel(positions, line_spacing_,
703 &spacings[0], &offsets[0], &index_range);
704 if (index_range > 1) {
705 double spacing_plus = line_spacing_ / (1.0 + 1.0 / index_range);
707 errors[1] = FitLineSpacingModel(positions, spacing_plus,
708 &spacings[1], &offsets[1],
nullptr);
709 double spacing_minus = line_spacing_ / (1.0 - 1.0 / index_range);
710 errors[2] = FitLineSpacingModel(positions, spacing_minus,
711 &spacings[2], &offsets[2],
nullptr);
712 for (
int i = 1; i <= 2; ++i) {
713 if (errors[i] < errors[0]) {
714 spacings[0] = spacings[i];
715 offsets[0] = offsets[i];
716 errors[0] = errors[i];
720 if (spacings[0] > 0.0) {
721 line_spacing_ = spacings[0];
722 line_offset_ = offsets[0];
723 model_error_ = errors[0];
724 if (debug_level_ > 0) {
725 tprintf(
"Final linespacing model = %g + offset %g, error %g\n",
726 line_spacing_, line_offset_, model_error_);
736 double BaselineBlock::FitLineSpacingModel(
738 double* m_out,
double* c_out,
int* index_delta) {
739 if (m_in == 0.0f || positions.
size() < 2) {
742 if (index_delta !=
nullptr) *index_delta = 0;
747 for (
int i = 0; i < positions.
size(); ++i)
748 offsets.
push_back(fmod(positions[i], m_in));
753 int min_index = INT32_MAX;
754 int max_index = -INT32_MAX;
755 for (
int i = 0; i < positions.
size(); ++i) {
756 double y_pos = positions[i];
759 llsq.
add(row_index, y_pos);
765 for (
int i = 0; i < positions.
size(); ++i)
766 offsets.
push_back(fmod(positions[i], *m_out));
768 if (debug_level_ > 2) {
769 for (
int i = 0; i < offsets.
size(); ++i)
770 tprintf(
"%d: %g\n", i, offsets[i]);
773 if (debug_level_ > 1) {
774 tprintf(
"Median offset = %g, compared to mean of %g.\n",
775 *c_out, llsq.
c(*m_out));
778 if (index_delta !=
nullptr)
779 *index_delta = max_index - min_index;
782 double rms_error = llsq.
rms(*m_out, llsq.
c(*m_out));
783 if (debug_level_ > 1) {
784 tprintf(
"Linespacing of y=%g x + %g improved to %g x + %g, rms=%g\n",
785 m_in, median_offset, *m_out, *c_out, rms_error);
791 TO_BLOCK_LIST* blocks)
792 : page_skew_(page_skew), debug_level_(debug_level) {
793 TO_BLOCK_IT it(blocks);
794 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
804 bool non_text = pb !=
nullptr && !pb->
IsText();
805 blocks_.push_back(
new BaselineBlock(debug_level_, non_text, to_block));
814 for (
int i = 0; i < blocks_.size(); ++i) {
816 if (debug_level_ > 0)
817 tprintf(
"Fitting initial baselines...\n");
823 double default_block_skew = page_skew_.
angle();
824 if (!block_skew_angles.
empty()) {
827 if (debug_level_ > 0) {
828 tprintf(
"Page skew angle = %g\n", default_block_skew);
832 for (
int i = 0; i < blocks_.size(); ++i) {
847 bool show_final_rows,
849 for (
int i = 0; i < blocks_.size(); ++i) {
854 if (show_final_rows) {