19#define _USE_MATH_DEFINES
22# include "config_auto.h"
27#include <allheaders.h>
66 : blobs_(to_row->blob_list()),
67 baseline_pt1_(0.0f, 0.0f),
68 baseline_pt2_(0.0f, 0.0f),
70 good_baseline_(false) {
84 row->
set_line(gradient, para_c, baseline_error_);
90 tprintf(
"Baseline (%g,%g)->(%g,%g), angle=%g, intercept=%g\n",
91 baseline_pt1_.
x(), baseline_pt1_.
y(), baseline_pt2_.
x(),
93 tprintf(
"Quant factor=%g, error=%g, good=%d, box:", disp_quant_factor_,
94 baseline_error_, good_baseline_);
95 bounding_box_.
print();
100 FCOORD baseline_dir(baseline_pt2_ - baseline_pt1_);
101 double angle = baseline_dir.
angle();
104 return fmod(angle + M_PI * 1.5, M_PI) - M_PI * 0.5;
111 float x = (std::max(bounding_box_.
left(), other.bounding_box_.
left()) +
112 std::min(bounding_box_.
right(), other.bounding_box_.
right())) /
118 return PerpDistanceFromBaseline(pt) + other.PerpDistanceFromBaseline(pt);
124 float middle_x = (bounding_box_.
left() + bounding_box_.
right()) / 2.0f;
126 return direction * middle_pos / direction.
length();
132 double denominator = baseline_pt2_.
x() - baseline_pt1_.
x();
133 if (denominator == 0.0) {
134 return (baseline_pt1_.
y() + baseline_pt2_.
y()) / 2.0;
136 return baseline_pt1_.
y() + (
x - baseline_pt1_.
x()) *
137 (baseline_pt2_.
y() - baseline_pt1_.
y()) /
150 BLOBNBOX_IT blob_it(blobs_);
152 for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
154 if (!use_box_bottoms) {
158 int x_middle = (box.
left() + box.
right()) / 2;
160 if (box.
bottom() < kDebugYCoord && box.
top() > kDebugYCoord) {
161 tprintf(
"Box bottom = %d, baseline pos=%d for box at:", box.
bottom(),
171 baseline_error_ = fitter_.
Fit(&pt1, &pt2);
174 if (baseline_error_ > max_baseline_error_ &&
180 if (error < baseline_error_ / 2.0) {
181 baseline_error_ = error;
189 debug = bounding_box_.
bottom() < kDebugYCoord &&
190 bounding_box_.
top() > kDebugYCoord
196 FCOORD direction(pt2 - pt1);
197 double target_offset = direction * pt1;
198 good_baseline_ =
false;
199 FitConstrainedIfBetter(debug, direction, 0.0, target_offset);
205 if (fabs(angle) > M_PI * 0.25) {
208 baseline_pt2_ = baseline_pt1_ +
FCOORD(1.0f, llsq.
m());
211 double c = llsq.
c(m);
212 baseline_error_ = llsq.
rms(m, c);
213 good_baseline_ =
false;
215 return good_baseline_;
221 SetupBlobDisplacements(direction);
222 if (displacement_modes_.empty()) {
226 if (bounding_box_.
bottom() < kDebugYCoord &&
227 bounding_box_.
top() > kDebugYCoord && debug < 3)
230 FitConstrainedIfBetter(debug, direction, 0.0, displacement_modes_[0]);
237 double line_offset) {
238 if (blobs_->empty()) {
241 bounding_box_.
print();
246 double best_error = 0.0;
248 for (
unsigned i = 0;
i < displacement_modes_.size(); ++
i) {
249 double blob_y = displacement_modes_[
i];
253 tprintf(
"Mode at %g has error %g from model \n", blob_y, error);
255 if (best_index < 0 || error < best_error) {
262 double model_margin = max_baseline_error_ - best_error;
263 if (best_index >= 0 && model_margin > 0.0) {
266 double perp_disp =
PerpDisp(direction);
267 double shift = displacement_modes_[best_index] - perp_disp;
268 if (fabs(shift) > max_baseline_error_) {
270 tprintf(
"Attempting linespacing model fit with mode %g to row at:",
271 displacement_modes_[best_index]);
272 bounding_box_.
print();
274 FitConstrainedIfBetter(debug, direction, model_margin,
275 displacement_modes_[best_index]);
276 }
else if (debug > 1) {
277 tprintf(
"Linespacing model only moves current line by %g for row at:",
279 bounding_box_.
print();
281 }
else if (debug > 1) {
282 tprintf(
"Linespacing model not close enough to any mode for row at:");
283 bounding_box_.
print();
285 return fmod(
PerpDisp(direction), line_spacing);
290void BaselineRow::SetupBlobDisplacements(
const FCOORD &direction) {
293 std::vector<double> perp_blob_dists;
294 displacement_modes_.clear();
296 double min_dist = FLT_MAX;
297 double max_dist = -FLT_MAX;
298 BLOBNBOX_IT blob_it(blobs_);
302 for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
306 if (box.
bottom() < kDebugYCoord && box.
top() > kDebugYCoord)
311 double offset = direction * blob_pos;
312 perp_blob_dists.push_back(offset);
315 tprintf(
"Displacement %g for blob at:", offset);
324 for (
double perp_blob_dist : perp_blob_dists) {
325 dist_stats.add(
IntCastRounded(perp_blob_dist / disp_quant_factor_), 1);
327 std::vector<KDPairInc<float, int>> scaled_modes;
331 for (
int i = 0;
i < scaled_modes.size(); ++
i) {
332 tprintf(
"Top mode = %g * %d\n", scaled_modes[
i].key * disp_quant_factor_,
333 scaled_modes[
i].data());
337 for (
auto &scaled_mode : scaled_modes) {
338 displacement_modes_.push_back(disp_quant_factor_ * scaled_mode.key());
352void BaselineRow::FitConstrainedIfBetter(
int debug,
const FCOORD &direction,
353 double cheat_allowance,
354 double target_offset) {
355 double halfrange = fit_halfrange_ * direction.length();
356 double min_dist = target_offset - halfrange;
357 double max_dist = target_offset + halfrange;
359 double new_error = fitter_.
ConstrainedFit(direction, min_dist, max_dist,
360 debug > 2, &line_pt);
362 new_error -= cheat_allowance;
364 double new_angle = direction.angle();
366 tprintf(
"Constrained error = %g, original = %g", new_error,
368 tprintf(
" angles = %g, %g, delta=%g vs threshold %g\n", old_angle,
371 bool new_good_baseline =
372 new_error <= max_baseline_error_ &&
379 if (new_error <= baseline_error_ || (!good_baseline_ && new_good_baseline) ||
381 baseline_error_ = new_error;
382 baseline_pt1_ = line_pt;
383 baseline_pt2_ = baseline_pt1_ + direction;
384 good_baseline_ = new_good_baseline;
386 tprintf(
"Replacing with constrained baseline, good = %d\n",
389 }
else if (debug > 1) {
390 tprintf(
"Keeping old baseline\n");
396float BaselineRow::PerpDistanceFromBaseline(
const FCOORD &pt)
const {
397 FCOORD baseline_vector(baseline_pt2_ - baseline_pt1_);
398 FCOORD offset_vector(pt - baseline_pt1_);
399 float distance = baseline_vector * offset_vector;
400 float sqlength = baseline_vector.sqlength();
401 if (sqlength == 0.0f) {
402 tprintf(
"unexpected baseline vector (0,0)\n");
409void BaselineRow::ComputeBoundingBox() {
410 BLOBNBOX_IT it(blobs_);
412 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
413 box += it.data()->bounding_box();
420 debug_level_(debug_level),
421 non_text_block_(non_text),
422 good_skew_angle_(false),
424 line_spacing_(block->line_spacing),
427 TO_ROW_IT row_it(block_->
get_rows());
428 for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
438 double line_offset) {
440 int multiple =
IntCastRounded((perp_disp - line_offset) / line_spacing);
441 double model_y = line_spacing * multiple + line_offset;
442 return fabs(perp_disp - model_y);
450 if (non_text_block_) {
453 std::vector<double> angles;
454 for (
auto row : rows_) {
455 if (row->FitBaseline(use_box_bottoms)) {
456 double angle = row->BaselineAngle();
457 angles.push_back(angle);
459 if (debug_level_ > 1) {
464 if (!angles.empty()) {
466 good_skew_angle_ =
true;
469 good_skew_angle_ =
false;
471 if (debug_level_ > 0) {
472 tprintf(
"Initial block skew angle = %g, good = %d\n", skew_angle_,
475 return good_skew_angle_;
481 if (non_text_block_) {
484 if (!good_skew_angle_) {
485 skew_angle_ = default_block_skew;
487 if (debug_level_ > 0) {
488 tprintf(
"Adjusting block to skew angle %g\n", skew_angle_);
490 FCOORD direction(cos(skew_angle_), sin(skew_angle_));
491 for (
auto row : rows_) {
492 row->AdjustBaselineToParallel(debug_level_, direction);
493 if (debug_level_ > 1) {
497 if (rows_.size() < 3 || !ComputeLineSpacing()) {
503 unsigned best_row = 0;
505 line_spacing_, line_offset_);
506 for (
unsigned r = 1; r < rows_.size(); ++r) {
508 line_spacing_, line_offset_);
509 if (error < best_error) {
515 double offset = line_offset_;
516 for (
auto r = best_row + 1; r < rows_.size(); ++r) {
517 offset = rows_[r]->AdjustBaselineToGrid(debug_level_, direction,
518 line_spacing_, offset);
520 offset = line_offset_;
521 for (
int r = best_row - 1; r >= 0; --r) {
522 offset = rows_[r]->AdjustBaselineToGrid(debug_level_, direction,
523 line_spacing_, offset);
529 if (line_spacing_ > 0.0) {
532 std::min(block_->
line_spacing,
static_cast<float>(line_spacing_));
533 if (min_spacing < block_->line_size) {
541 TO_ROW_IT row_it(block_->
get_rows());
542 for (
unsigned r = 0; r < rows_.size(); ++r, row_it.forward()) {
544 TO_ROW *to_row = row_it.data();
558 if (non_text_block_) {
564 FCOORD rotation(1.0f, 0.0f);
565 double gradient = tan(skew_angle_);
576 bool show_final_rows,
Textord *textord) {
577 double gradient = tan(skew_angle_);
578 FCOORD rotation(1.0f, 0.0f);
580 if (enable_splines) {
585 TO_ROW_IT row_it = block_->
get_rows();
586 for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
587 TO_ROW *row = row_it.data();
588 int32_t xstarts[2] = {block_box.
left(), block_box.
right()};
602#ifndef GRAPHICS_DISABLED
607 if (non_text_block_) {
610 double gradient = tan(skew_angle_);
611 FCOORD rotation(1.0f, 0.0f);
615 TO_ROW_IT row_it = block_->
get_rows();
616 for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
627 if (block_->
blobs.length() > 0) {
628 tprintf(
"%d blobs discarded as noise\n", block_->
blobs.length());
636 if (non_text_block_) {
639 TO_ROW_IT row_it = block_->
get_rows();
640 for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
641 row_it.data()->baseline.plot(pix_in);
651bool BaselineBlock::ComputeLineSpacing() {
652 FCOORD direction(cos(skew_angle_), sin(skew_angle_));
653 std::vector<double> row_positions;
654 ComputeBaselinePositions(direction, &row_positions);
655 if (row_positions.size() < 2) {
658 EstimateLineSpacing();
659 RefineLineSpacing(row_positions);
662 int non_trivial_gaps = 0;
663 int fitting_gaps = 0;
664 for (
unsigned i = 1;
i < row_positions.size(); ++
i) {
665 double row_gap = fabs(row_positions[
i - 1] - row_positions[
i]);
666 if (row_gap > max_baseline_error) {
668 if (fabs(row_gap - line_spacing_) <= max_baseline_error) {
673 if (debug_level_ > 0) {
674 tprintf(
"Spacing %g, in %zu rows, %d gaps fitted out of %d non-trivial\n",
675 line_spacing_, row_positions.size(), fitting_gaps,
689void BaselineBlock::ComputeBaselinePositions(
const FCOORD &direction,
690 std::vector<double> *positions) {
692 for (
auto row : rows_) {
693 const TBOX &row_box = row->bounding_box();
694 float x_middle = (row_box.left() + row_box.right()) / 2.0f;
695 FCOORD row_pos(x_middle,
static_cast<float>(row->StraightYAtX(x_middle)));
696 float offset = direction * row_pos;
697 positions->push_back(offset);
703void BaselineBlock::EstimateLineSpacing() {
704 std::vector<float> spacings;
705 for (
unsigned r = 0; r < rows_.size(); ++r) {
706 BaselineRow *row = rows_[r];
708 if (fabs(row->BaselineAngle()) > M_PI * 0.25) {
712 const TBOX &row_box = row->bounding_box();
714 for (r2 = r + 1; r2 < rows_.size() &&
715 !row_box.major_x_overlap(rows_[r2]->bounding_box());
719 if (r2 < rows_.size()) {
720 BaselineRow *row2 = rows_[r2];
722 if (fabs(row2->BaselineAngle()) > M_PI * 0.25) {
725 float spacing = row->SpaceBetween(*row2);
726 spacings.push_back(spacing);
731 if (!spacings.empty()) {
732 std::nth_element(spacings.begin(), spacings.begin() + spacings.size() / 2,
734 line_spacing_ = spacings[spacings.size() / 2];
735 if (debug_level_ > 1) {
736 tprintf(
"Estimate of linespacing = %g\n", line_spacing_);
745void BaselineBlock::RefineLineSpacing(
const std::vector<double> &positions) {
746 double spacings[3], offsets[3], errors[3];
748 errors[0] = FitLineSpacingModel(positions, line_spacing_, &spacings[0],
749 &offsets[0], &index_range);
750 if (index_range > 1) {
751 double spacing_plus = line_spacing_ / (1.0 + 1.0 / index_range);
753 errors[1] = FitLineSpacingModel(positions, spacing_plus, &spacings[1],
754 &offsets[1],
nullptr);
755 double spacing_minus = line_spacing_ / (1.0 - 1.0 / index_range);
756 errors[2] = FitLineSpacingModel(positions, spacing_minus, &spacings[2],
757 &offsets[2],
nullptr);
758 for (
int i = 1;
i <= 2; ++
i) {
759 if (errors[
i] < errors[0]) {
760 spacings[0] = spacings[
i];
761 offsets[0] = offsets[
i];
762 errors[0] = errors[
i];
766 if (spacings[0] > 0.0) {
767 line_spacing_ = spacings[0];
768 line_offset_ = offsets[0];
769 model_error_ = errors[0];
770 if (debug_level_ > 0) {
771 tprintf(
"Final linespacing model = %g + offset %g, error %g\n",
772 line_spacing_, line_offset_, model_error_);
782double BaselineBlock::FitLineSpacingModel(
const std::vector<double> &positions,
783 double m_in,
double *m_out,
784 double *c_out,
int *index_delta) {
785 if (m_in == 0.0f || positions.size() < 2) {
788 if (index_delta !=
nullptr) {
793 std::vector<double> offsets;
795 offsets.reserve(positions.size());
796 for (
double position : positions) {
797 offsets.push_back(fmod(position, m_in));
803 int min_index = INT32_MAX;
804 int max_index = -INT32_MAX;
805 for (
double y_pos : positions) {
808 llsq.add(row_index, y_pos);
815 for (
double position : positions) {
816 offsets.push_back(fmod(position, *m_out));
819 if (debug_level_ > 2) {
820 for (
unsigned i = 0;
i < offsets.size(); ++
i) {
828 if (debug_level_ > 1) {
829 tprintf(
"Median offset = %g, compared to mean of %g.\n", *c_out,
833 if (index_delta !=
nullptr) {
834 *index_delta = max_index - min_index;
838 double rms_error = llsq.rms(*m_out, llsq.c(*m_out));
839 if (debug_level_ > 1) {
840 tprintf(
"Linespacing of y=%g x + %g improved to %g x + %g, rms=%g\n", m_in,
841 median_offset, *m_out, *c_out, rms_error);
847 TO_BLOCK_LIST *blocks)
848 : page_skew_(page_skew), debug_level_(debug_level) {
849 TO_BLOCK_IT it(blocks);
850 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
860 bool non_text = pb !=
nullptr && !pb->
IsText();
861 blocks_.push_back(
new BaselineBlock(debug_level_, non_text, to_block));
869 std::vector<double> block_skew_angles;
870 for (
auto bl_block : blocks_) {
871 if (debug_level_ > 0) {
872 tprintf(
"Fitting initial baselines...\n");
874 if (bl_block->FitBaselinesAndFindSkew(use_box_bottoms)) {
875 block_skew_angles.push_back(bl_block->skew_angle());
879 double default_block_skew = page_skew_.
angle();
880 if (!block_skew_angles.empty()) {
883 if (debug_level_ > 0) {
884 tprintf(
"Page skew angle = %g\n", default_block_skew);
888 for (
auto bl_block : blocks_) {
889 bl_block->ParallelizeBaselines(default_block_skew);
890 bl_block->SetupBlockParameters();
902 bool show_final_rows,
904 for (
auto bl_block : blocks_) {
905 if (enable_splines) {
906 bl_block->PrepareForSplineFitting(page_tr, remove_noise);
908 bl_block->FitBaselineSplines(enable_splines, show_final_rows, textord);
909#ifndef GRAPHICS_DISABLED
910 if (show_final_rows) {
911 bl_block->DrawFinalRows(page_tr);
const double kMaxBaselineError
const double kMaxBlobSizeMultiple
const double kFitHalfrangeFactor
const double kOffsetQuantizationFactor
const int kMaxDisplacementsModes
const double kMaxSkewDeviation
const double kMinFittingLinespacings
UnicodeText::const_iterator::difference_type distance(const UnicodeText::const_iterator &first, const UnicodeText::const_iterator &last)
void pre_associate_blobs(ICOORD page_tr, TO_BLOCK *block, FCOORD rotation, bool testing_on)
void tprintf(const char *format,...)
int IntCastRounded(double x)
bool textord_restore_underlines
void vigorous_noise_removal(TO_BLOCK *block)
void restore_underlined_blobs(TO_BLOCK *block)
void plot_blob_list(ScrollView *win, BLOBNBOX_LIST *list, ScrollView::Color body_colour, ScrollView::Color child_colour)
const double kMaxBaselineError
void plot_parallel_row(TO_ROW *row, float gradient, int32_t left, ScrollView::Color colour, FCOORD rotation)
void draw_meanlines(TO_BLOCK *block, float gradient, int32_t left, ScrollView::Color colour, FCOORD rotation)
T MedianOfCircularValues(T modulus, std::vector< T > &v)
void separate_underlines(TO_BLOCK *block, float gradient, FCOORD rotation, bool testing_on)
void UpdateRange(const T1 &x, T2 *lower_bound, T2 *upper_bound)
ScrollView * create_to_win(ICOORD page_tr)
int blob_x_order(const void *item1, const void *item2)
const TBOX & bounding_box() const
void EstimateBaselinePosition()
int baseline_position() const
void set_line(float new_m, float new_c, float new_error)
void set_parallel_line(float gradient, float new_c, float new_error)
void Add(const ICOORD &pt)
double ConstrainedFit(const FCOORD &direction, double min_dist, double max_dist, bool debug, ICOORD *line_pt)
double Fit(ICOORD *pt1, ICOORD *pt2)
bool SufficientPointsForIndependentFit() const
void add(double x, double y)
FCOORD mean_point() const
double rms(double m, double c) const
FCOORD classify_rotation() const
PDBLK pdblk
Page Description Block.
void set_xheight(int32_t height)
set char size
POLY_BLOCK * poly_block() const
void bounding_box(ICOORD &bottom_left, ICOORD &top_right) const
get box
float length() const
find length
float angle() const
find angle
TDimension bottom() const
bool FitBaseline(bool use_box_bottoms)
double PerpDisp(const FCOORD &direction) const
double BaselineAngle() const
void AdjustBaselineToParallel(int debug, const FCOORD &direction)
double SpaceBetween(const BaselineRow &other) const
BaselineRow(double line_size, TO_ROW *to_row)
double StraightYAtX(double x) const
double AdjustBaselineToGrid(int debug, const FCOORD &direction, double line_spacing, double line_offset)
void SetupOldLineParameters(TO_ROW *row) const
void SetupBlockParameters() const
void FitBaselineSplines(bool enable_splines, bool show_final_rows, Textord *textord)
bool FitBaselinesAndFindSkew(bool use_box_bottoms)
BaselineBlock(int debug_level, bool non_text, TO_BLOCK *block)
void DrawFinalRows(const ICOORD &page_tr)
void ParallelizeBaselines(double default_block_skew)
void DrawPixSpline(Image pix_in)
void PrepareForSplineFitting(ICOORD page_tr, bool remove_noise)
static double SpacingModelError(double perp_disp, double line_spacing, double line_offset)
BaselineDetect(int debug_level, const FCOORD &page_skew, TO_BLOCK_LIST *blocks)
void ComputeBaselineSplinesAndXheights(const ICOORD &page_tr, bool enable_splines, bool remove_noise, bool show_final_rows, Textord *textord)
void ComputeStraightBaselines(bool use_box_bottoms)
void compute_row_xheight(TO_ROW *row, const FCOORD &rotation, float gradient, int block_line_size)
void make_spline_rows(TO_BLOCK *block, float gradient, bool testing_on)
void compute_block_xheight(TO_BLOCK *block, float gradient)