tesseract  5.0.0
makerow.cpp
Go to the documentation of this file.
1 /**********************************************************************
2  * File: makerow.cpp (Formerly makerows.c)
3  * Description: Code to arrange blobs into rows of text.
4  * Author: Ray Smith
5  *
6  * (C) Copyright 1992, Hewlett-Packard Ltd.
7  ** Licensed under the Apache License, Version 2.0 (the "License");
8  ** you may not use this file except in compliance with the License.
9  ** You may obtain a copy of the License at
10  ** http://www.apache.org/licenses/LICENSE-2.0
11  ** Unless required by applicable law or agreed to in writing, software
12  ** distributed under the License is distributed on an "AS IS" BASIS,
13  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  ** See the License for the specific language governing permissions and
15  ** limitations under the License.
16  *
17  **********************************************************************/
18 
19 // Include automatically generated configuration file if running autoconf.
20 #ifdef HAVE_CONFIG_H
21 # include "config_auto.h"
22 #endif
23 
24 #include "makerow.h"
25 
26 #include "blkocc.h"
27 #include "blobbox.h"
28 #include "ccstruct.h"
29 #include "detlinefit.h"
30 #include "drawtord.h"
31 #include "oldbasel.h"
32 #include "sortflts.h"
33 #include "statistc.h"
34 #include "textord.h"
35 #include "tordmain.h"
36 #include "tovars.h"
37 #include "tprintf.h"
38 #include "underlin.h"
39 
40 #include <algorithm>
41 #include <cmath>
42 #include <vector> // for std::vector
43 
44 namespace tesseract {
45 
46 BOOL_VAR(textord_heavy_nr, false, "Vigorously remove noise");
47 BOOL_VAR(textord_show_initial_rows, false, "Display row accumulation");
48 BOOL_VAR(textord_show_parallel_rows, false, "Display page correlated rows");
49 BOOL_VAR(textord_show_expanded_rows, false, "Display rows after expanding");
50 BOOL_VAR(textord_show_final_rows, false, "Display rows after final fitting");
51 BOOL_VAR(textord_show_final_blobs, false, "Display blob bounds after pre-ass");
52 BOOL_VAR(textord_test_landscape, false, "Tests refer to land/port");
53 BOOL_VAR(textord_parallel_baselines, true, "Force parallel baselines");
54 BOOL_VAR(textord_straight_baselines, false, "Force straight baselines");
55 BOOL_VAR(textord_old_baselines, true, "Use old baseline algorithm");
56 BOOL_VAR(textord_old_xheight, false, "Use old xheight algorithm");
57 BOOL_VAR(textord_fix_xheight_bug, true, "Use spline baseline");
58 BOOL_VAR(textord_fix_makerow_bug, true, "Prevent multiple baselines");
59 BOOL_VAR(textord_debug_xheights, false, "Test xheight algorithms");
60 static BOOL_VAR(textord_biased_skewcalc, true, "Bias skew estimates with line length");
61 static BOOL_VAR(textord_interpolating_skew, true, "Interpolate across gaps");
62 static INT_VAR(textord_skewsmooth_offset, 4, "For smooth factor");
63 static INT_VAR(textord_skewsmooth_offset2, 1, "For smooth factor");
64 INT_VAR(textord_test_x, -INT32_MAX, "coord of test pt");
65 INT_VAR(textord_test_y, -INT32_MAX, "coord of test pt");
66 INT_VAR(textord_min_blobs_in_row, 4, "Min blobs before gradient counted");
67 INT_VAR(textord_spline_minblobs, 8, "Min blobs in each spline segment");
68 INT_VAR(textord_spline_medianwin, 6, "Size of window for spline segmentation");
69 static INT_VAR(textord_max_blob_overlaps, 4, "Max number of blobs a big blob can overlap");
70 INT_VAR(textord_min_xheight, 10, "Min credible pixel xheight");
71 double_VAR(textord_spline_shift_fraction, 0.02, "Fraction of line spacing for quad");
72 double_VAR(textord_skew_ile, 0.5, "Ile of gradients for page skew");
73 double_VAR(textord_skew_lag, 0.02, "Lag for skew on row accumulation");
74 double_VAR(textord_linespace_iqrlimit, 0.2, "Max iqr/median for linespace");
75 double_VAR(textord_width_limit, 8, "Max width of blobs to make rows");
76 double_VAR(textord_chop_width, 1.5, "Max width before chopping");
77 static double_VAR(textord_expansion_factor, 1.0, "Factor to expand rows by in expand_rows");
78 static double_VAR(textord_overlap_x, 0.375, "Fraction of linespace for good overlap");
79 double_VAR(textord_minxh, 0.25, "fraction of linesize for min xheight");
80 double_VAR(textord_min_linesize, 1.25, "* blob height for initial linesize");
81 double_VAR(textord_excess_blobsize, 1.3, "New row made if blob makes row this big");
82 double_VAR(textord_occupancy_threshold, 0.4, "Fraction of neighbourhood");
83 double_VAR(textord_underline_width, 2.0, "Multiple of line_size for underline");
85  "Min blob height/top to include blob top into xheight stats");
86 double_VAR(textord_xheight_mode_fraction, 0.4, "Min pile height to make xheight");
87 double_VAR(textord_ascheight_mode_fraction, 0.08, "Min pile height to make ascheight");
88 static double_VAR(textord_descheight_mode_fraction, 0.08, "Min pile height to make descheight");
89 double_VAR(textord_ascx_ratio_min, 1.25, "Min cap/xheight");
90 double_VAR(textord_ascx_ratio_max, 1.8, "Max cap/xheight");
91 double_VAR(textord_descx_ratio_min, 0.25, "Min desc/xheight");
92 double_VAR(textord_descx_ratio_max, 0.6, "Max desc/xheight");
93 double_VAR(textord_xheight_error_margin, 0.1, "Accepted variation");
94 INT_VAR(textord_lms_line_trials, 12, "Number of linew fits to do");
95 BOOL_VAR(textord_new_initial_xheight, true, "Use test xheight mechanism");
96 BOOL_VAR(textord_debug_blob, false, "Print test blob information");
97 
98 #define MAX_HEIGHT_MODES 12
99 
100 const int kMinLeaderCount = 5;
101 
107 static int row_y_order( // sort function
108  const void *item1, // items to compare
109  const void *item2) {
110  // converted ptr
111  const TO_ROW *row1 = *reinterpret_cast<const TO_ROW *const *>(item1);
112  // converted ptr
113  const TO_ROW *row2 = *reinterpret_cast<const TO_ROW *const *>(item2);
114 
115  if (row1->parallel_c() > row2->parallel_c()) {
116  return -1;
117  } else if (row1->parallel_c() < row2->parallel_c()) {
118  return 1;
119  } else {
120  return 0;
121  }
122 }
123 
129 static int row_spacing_order( // sort function
130  const TO_ROW *row1, // items to compare
131  const TO_ROW *row2) {
132  return row1->spacing < row2->spacing;
133 }
134 
135 // Factored-out helper to build a single row from a list of blobs.
136 // Returns the mean blob size.
137 static float MakeRowFromBlobs(float line_size, BLOBNBOX_IT *blob_it, TO_ROW_IT *row_it) {
138  blob_it->sort(blob_x_order);
139  blob_it->move_to_first();
140  TO_ROW *row = nullptr;
141  float total_size = 0.0f;
142  int blob_count = 0;
143  // Add all the blobs to a single TO_ROW.
144  for (; !blob_it->empty(); blob_it->forward()) {
145  BLOBNBOX *blob = blob_it->extract();
146  int top = blob->bounding_box().top();
147  int bottom = blob->bounding_box().bottom();
148  if (row == nullptr) {
149  row = new TO_ROW(blob, top, bottom, line_size);
150  row_it->add_before_then_move(row);
151  } else {
152  row->add_blob(blob, top, bottom, line_size);
153  }
154  total_size += top - bottom;
155  ++blob_count;
156  }
157  return blob_count > 0 ? total_size / blob_count : total_size;
158 }
159 
160 // Helper to make a row using the children of a single blob.
161 // Returns the mean size of the blobs created.
162 static float MakeRowFromSubBlobs(TO_BLOCK *block, C_BLOB *blob, TO_ROW_IT *row_it) {
163  // The blobs made from the children will go in the small_blobs list.
164  BLOBNBOX_IT bb_it(&block->small_blobs);
165  C_OUTLINE_IT ol_it(blob->out_list());
166  // Get the children.
167  ol_it.set_to_list(ol_it.data()->child());
168  if (ol_it.empty()) {
169  return 0.0f;
170  }
171  for (ol_it.mark_cycle_pt(); !ol_it.cycled_list(); ol_it.forward()) {
172  // Deep copy the child outline and use that to make a blob.
173  blob = new C_BLOB(C_OUTLINE::deep_copy(ol_it.data()));
174  // Correct direction as needed.
175  blob->CheckInverseFlagAndDirection();
176  auto *bbox = new BLOBNBOX(blob);
177  bb_it.add_after_then_move(bbox);
178  }
179  // Now we can make a row from the blobs.
180  return MakeRowFromBlobs(block->line_size, &bb_it, row_it);
181 }
182 
190 float make_single_row(ICOORD page_tr, bool allow_sub_blobs, TO_BLOCK *block,
191  TO_BLOCK_LIST *blocks) {
192  BLOBNBOX_IT blob_it = &block->blobs;
193  TO_ROW_IT row_it = block->get_rows();
194 
195  // Include all the small blobs and large blobs.
196  blob_it.add_list_after(&block->small_blobs);
197  blob_it.add_list_after(&block->noise_blobs);
198  blob_it.add_list_after(&block->large_blobs);
199  if (block->blobs.singleton() && allow_sub_blobs) {
200  blob_it.move_to_first();
201  float size = MakeRowFromSubBlobs(block, blob_it.data()->cblob(), &row_it);
202  if (size > block->line_size) {
203  block->line_size = size;
204  }
205  } else if (block->blobs.empty()) {
206  // Make a fake blob.
207  C_BLOB *blob = C_BLOB::FakeBlob(block->block->pdblk.bounding_box());
208  // The blobnbox owns the blob.
209  auto *bblob = new BLOBNBOX(blob);
210  blob_it.add_after_then_move(bblob);
211  }
212  MakeRowFromBlobs(block->line_size, &blob_it, &row_it);
213  // Fit an LMS line to the rows.
214  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
215  fit_lms_line(row_it.data());
216  }
217  float gradient;
218  float fit_error;
219  // Compute the skew based on the fitted line.
220  compute_page_skew(blocks, gradient, fit_error);
221  return gradient;
222 }
223 
229 float make_rows(ICOORD page_tr, TO_BLOCK_LIST *port_blocks) {
230  float port_m; // global skew
231  float port_err; // global noise
232  TO_BLOCK_IT block_it; // iterator
233 
234  block_it.set_to_list(port_blocks);
235  for (block_it.mark_cycle_pt(); !block_it.cycled_list(); block_it.forward()) {
236  make_initial_textrows(page_tr, block_it.data(), FCOORD(1.0f, 0.0f), !textord_test_landscape);
237  }
238  // compute globally
239  compute_page_skew(port_blocks, port_m, port_err);
240  block_it.set_to_list(port_blocks);
241  for (block_it.mark_cycle_pt(); !block_it.cycled_list(); block_it.forward()) {
242  cleanup_rows_making(page_tr, block_it.data(), port_m, FCOORD(1.0f, 0.0f),
243  block_it.data()->block->pdblk.bounding_box().left(),
245  }
246  return port_m; // global skew
247 }
248 
254 void make_initial_textrows( // find lines
255  ICOORD page_tr,
256  TO_BLOCK *block, // block to do
257  FCOORD rotation, // for drawing
258  bool testing_on // correct orientation
259 ) {
260  TO_ROW_IT row_it = block->get_rows();
261 
262 #ifndef GRAPHICS_DISABLED
263  ScrollView::Color colour; // of row
264 
265  if (textord_show_initial_rows && testing_on) {
266  if (to_win == nullptr) {
267  create_to_win(page_tr);
268  }
269  }
270 #endif
271  // guess skew
272  assign_blobs_to_rows(block, nullptr, 0, true, true, textord_show_initial_rows && testing_on);
273  row_it.move_to_first();
274  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
275  fit_lms_line(row_it.data());
276  }
277 #ifndef GRAPHICS_DISABLED
278  if (textord_show_initial_rows && testing_on) {
279  colour = ScrollView::RED;
280  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
281  plot_to_row(row_it.data(), colour, rotation);
282  colour = static_cast<ScrollView::Color>(colour + 1);
283  if (colour > ScrollView::MAGENTA) {
284  colour = ScrollView::RED;
285  }
286  }
287  }
288 #endif
289 }
290 
296 void fit_lms_line(TO_ROW *row) {
297  float m, c; // fitted line
299  BLOBNBOX_IT blob_it = row->blob_list();
300 
301  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
302  const TBOX &box = blob_it.data()->bounding_box();
303  lms.Add(ICOORD((box.left() + box.right()) / 2, box.bottom()));
304  }
305  double error = lms.Fit(&m, &c);
306  row->set_line(m, c, error);
307 }
308 
315 void compute_page_skew( // get average gradient
316  TO_BLOCK_LIST *blocks, // list of blocks
317  float &page_m, // average gradient
318  float &page_err // average error
319 ) {
320  int32_t row_count; // total rows
321  int32_t blob_count; // total_blobs
322  int32_t row_err; // integer error
323  int32_t row_index; // of total
324  TO_ROW *row; // current row
325  TO_BLOCK_IT block_it = blocks; // iterator
326 
327  row_count = 0;
328  blob_count = 0;
329  for (block_it.mark_cycle_pt(); !block_it.cycled_list(); block_it.forward()) {
330  POLY_BLOCK *pb = block_it.data()->block->pdblk.poly_block();
331  if (pb != nullptr && !pb->IsText()) {
332  continue; // Pretend non-text blocks don't exist.
333  }
334  row_count += block_it.data()->get_rows()->length();
335  // count up rows
336  TO_ROW_IT row_it(block_it.data()->get_rows());
337  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
338  blob_count += row_it.data()->blob_list()->length();
339  }
340  }
341  if (row_count == 0) {
342  page_m = 0.0f;
343  page_err = 0.0f;
344  return;
345  }
346  // of rows
347  std::vector<float> gradients(blob_count);
348  // of rows
349  std::vector<float> errors(blob_count);
350 
351  row_index = 0;
352  for (block_it.mark_cycle_pt(); !block_it.cycled_list(); block_it.forward()) {
353  POLY_BLOCK *pb = block_it.data()->block->pdblk.poly_block();
354  if (pb != nullptr && !pb->IsText()) {
355  continue; // Pretend non-text blocks don't exist.
356  }
357  TO_ROW_IT row_it(block_it.data()->get_rows());
358  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
359  row = row_it.data();
360  blob_count = row->blob_list()->length();
361  row_err = static_cast<int32_t>(std::ceil(row->line_error()));
362  if (row_err <= 0) {
363  row_err = 1;
364  }
365  if (textord_biased_skewcalc) {
366  blob_count /= row_err;
367  for (blob_count /= row_err; blob_count > 0; blob_count--) {
368  gradients[row_index] = row->line_m();
369  errors[row_index] = row->line_error();
370  row_index++;
371  }
372  } else if (blob_count >= textord_min_blobs_in_row) {
373  // get gradient
374  gradients[row_index] = row->line_m();
375  errors[row_index] = row->line_error();
376  row_index++;
377  }
378  }
379  }
380  if (row_index == 0) {
381  // desperate
382  for (block_it.mark_cycle_pt(); !block_it.cycled_list(); block_it.forward()) {
383  POLY_BLOCK *pb = block_it.data()->block->pdblk.poly_block();
384  if (pb != nullptr && !pb->IsText()) {
385  continue; // Pretend non-text blocks don't exist.
386  }
387  TO_ROW_IT row_it(block_it.data()->get_rows());
388  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
389  row = row_it.data();
390  gradients[row_index] = row->line_m();
391  errors[row_index] = row->line_error();
392  row_index++;
393  }
394  }
395  }
396  row_count = row_index;
397  row_index = static_cast<int32_t>(row_count * textord_skew_ile);
398  gradients.resize(row_count);
399  std::nth_element(gradients.begin(), gradients.begin() + row_index, gradients.end());
400  page_m = gradients[row_index];
401  row_index = static_cast<int32_t>(row_count * textord_skew_ile);
402  errors.resize(row_count);
403  std::nth_element(errors.begin(), errors.begin() + row_index, errors.end());
404  page_err = errors[row_index];
405 }
406 
407 const double kNoiseSize = 0.5; // Fraction of xheight.
408 const int kMinSize = 8; // Min pixels to be xheight.
409 
414 static bool dot_of_i(BLOBNBOX *dot, BLOBNBOX *i, TO_ROW *row) {
415  const TBOX &ibox = i->bounding_box();
416  const TBOX &dotbox = dot->bounding_box();
417 
418  // Must overlap horizontally by enough and be high enough.
419  int overlap = std::min(dotbox.right(), ibox.right()) - std::max(dotbox.left(), ibox.left());
420  if (ibox.height() <= 2 * dotbox.height() ||
421  (overlap * 2 < ibox.width() && overlap < dotbox.width())) {
422  return false;
423  }
424 
425  // If the i is tall and thin then it is good.
426  if (ibox.height() > ibox.width() * 2) {
427  return true; // The i or ! must be tall and thin.
428  }
429 
430  // It might still be tall and thin, but it might be joined to something.
431  // So search the outline for a piece of large height close to the edges
432  // of the dot.
433  const double kHeightFraction = 0.6;
434  double target_height = std::min(dotbox.bottom(), ibox.top());
435  target_height -= row->line_m() * dotbox.left() + row->line_c();
436  target_height *= kHeightFraction;
437  int left_min = dotbox.left() - dotbox.width();
438  int middle = (dotbox.left() + dotbox.right()) / 2;
439  int right_max = dotbox.right() + dotbox.width();
440  int left_miny = 0;
441  int left_maxy = 0;
442  int right_miny = 0;
443  int right_maxy = 0;
444  bool found_left = false;
445  bool found_right = false;
446  bool in_left = false;
447  bool in_right = false;
448  C_BLOB *blob = i->cblob();
449  C_OUTLINE_IT o_it = blob->out_list();
450  for (o_it.mark_cycle_pt(); !o_it.cycled_list(); o_it.forward()) {
451  C_OUTLINE *outline = o_it.data();
452  int length = outline->pathlength();
453  ICOORD pos = outline->start_pos();
454  for (int step = 0; step < length; pos += outline->step(step++)) {
455  int x = pos.x();
456  int y = pos.y();
457  if (x >= left_min && x < middle && !found_left) {
458  // We are in the left part so find min and max y.
459  if (in_left) {
460  if (y > left_maxy) {
461  left_maxy = y;
462  }
463  if (y < left_miny) {
464  left_miny = y;
465  }
466  } else {
467  left_maxy = left_miny = y;
468  in_left = true;
469  }
470  } else if (in_left) {
471  // We just left the left so look for size.
472  if (left_maxy - left_miny > target_height) {
473  if (found_right) {
474  return true;
475  }
476  found_left = true;
477  }
478  in_left = false;
479  }
480  if (x <= right_max && x > middle && !found_right) {
481  // We are in the right part so find min and max y.
482  if (in_right) {
483  if (y > right_maxy) {
484  right_maxy = y;
485  }
486  if (y < right_miny) {
487  right_miny = y;
488  }
489  } else {
490  right_maxy = right_miny = y;
491  in_right = true;
492  }
493  } else if (in_right) {
494  // We just left the right so look for size.
495  if (right_maxy - right_miny > target_height) {
496  if (found_left) {
497  return true;
498  }
499  found_right = true;
500  }
501  in_right = false;
502  }
503  }
504  }
505  return false;
506 }
507 
509  TO_ROW_IT row_it = block->get_rows();
510  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
511  TO_ROW *row = row_it.data();
512  BLOBNBOX_IT b_it = row->blob_list();
513  // Estimate the xheight on the row.
514  int max_height = 0;
515  for (b_it.mark_cycle_pt(); !b_it.cycled_list(); b_it.forward()) {
516  BLOBNBOX *blob = b_it.data();
517  if (blob->bounding_box().height() > max_height) {
518  max_height = blob->bounding_box().height();
519  }
520  }
521  STATS hstats(0, max_height + 1);
522  for (b_it.mark_cycle_pt(); !b_it.cycled_list(); b_it.forward()) {
523  BLOBNBOX *blob = b_it.data();
524  int height = blob->bounding_box().height();
525  if (height >= kMinSize) {
526  hstats.add(blob->bounding_box().height(), 1);
527  }
528  }
529  float xheight = hstats.median();
530  // Delete small objects.
531  BLOBNBOX *prev = nullptr;
532  for (b_it.mark_cycle_pt(); !b_it.cycled_list(); b_it.forward()) {
533  BLOBNBOX *blob = b_it.data();
534  const TBOX &box = blob->bounding_box();
535  if (box.height() < kNoiseSize * xheight) {
536  // Small so delete unless it looks like an i dot.
537  if (prev != nullptr) {
538  if (dot_of_i(blob, prev, row)) {
539  continue; // Looks OK.
540  }
541  }
542  if (!b_it.at_last()) {
543  BLOBNBOX *next = b_it.data_relative(1);
544  if (dot_of_i(blob, next, row)) {
545  continue; // Looks OK.
546  }
547  }
548  // It might be noise so get rid of it.
549  delete blob->cblob();
550  delete b_it.extract();
551  } else {
552  prev = blob;
553  }
554  }
555  }
556 }
557 
563 void cleanup_rows_making( // find lines
564  ICOORD page_tr, // top right
565  TO_BLOCK *block, // block to do
566  float gradient, // gradient to fit
567  FCOORD rotation, // for drawing
568  int32_t block_edge, // edge of block
569  bool testing_on // correct orientation
570 ) {
571  // iterators
572  BLOBNBOX_IT blob_it = &block->blobs;
573  TO_ROW_IT row_it = block->get_rows();
574 
575 #ifndef GRAPHICS_DISABLED
576  if (textord_show_parallel_rows && testing_on) {
577  if (to_win == nullptr) {
578  create_to_win(page_tr);
579  }
580  }
581 #endif
582  // get row coords
583  fit_parallel_rows(block, gradient, rotation, block_edge,
584  textord_show_parallel_rows && testing_on);
585  delete_non_dropout_rows(block, gradient, rotation, block_edge,
586  textord_show_parallel_rows && testing_on);
587  expand_rows(page_tr, block, gradient, rotation, block_edge, testing_on);
588  blob_it.set_to_list(&block->blobs);
589  row_it.set_to_list(block->get_rows());
590  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
591  blob_it.add_list_after(row_it.data()->blob_list());
592  }
593  // give blobs back
594  assign_blobs_to_rows(block, &gradient, 1, false, false, false);
595  // now new rows must be genuine
596  blob_it.set_to_list(&block->blobs);
597  blob_it.add_list_after(&block->large_blobs);
598  assign_blobs_to_rows(block, &gradient, 2, true, true, false);
599  // safe to use big ones now
600  blob_it.set_to_list(&block->blobs);
601  // throw all blobs in
602  blob_it.add_list_after(&block->noise_blobs);
603  blob_it.add_list_after(&block->small_blobs);
604  assign_blobs_to_rows(block, &gradient, 3, false, false, false);
605 }
606 
612 void delete_non_dropout_rows( // find lines
613  TO_BLOCK *block, // block to do
614  float gradient, // global skew
615  FCOORD rotation, // deskew vector
616  int32_t block_edge, // left edge
617  bool testing_on // correct orientation
618 ) {
619  TBOX block_box; // deskewed block
620  int32_t max_y; // in block
621  int32_t min_y;
622  int32_t line_index; // of scan line
623  int32_t line_count; // no of scan lines
624  int32_t distance; // to drop-out
625  int32_t xleft; // of block
626  int32_t ybottom; // of block
627  TO_ROW *row; // current row
628  TO_ROW_IT row_it = block->get_rows();
629  BLOBNBOX_IT blob_it = &block->blobs;
630 
631  if (row_it.empty()) {
632  return; // empty block
633  }
634  block_box = deskew_block_coords(block, gradient);
635  xleft = block->block->pdblk.bounding_box().left();
636  ybottom = block->block->pdblk.bounding_box().bottom();
637  min_y = block_box.bottom() - 1;
638  max_y = block_box.top() + 1;
639  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
640  line_index = static_cast<int32_t>(std::floor(row_it.data()->intercept()));
641  if (line_index <= min_y) {
642  min_y = line_index - 1;
643  }
644  if (line_index >= max_y) {
645  max_y = line_index + 1;
646  }
647  }
648  line_count = max_y - min_y + 1;
649  if (line_count <= 0) {
650  return; // empty block
651  }
652  // change in occupation
653  std::vector<int32_t> deltas(line_count);
654  // of pixel coords
655  std::vector<int32_t> occupation(line_count);
656 
657  compute_line_occupation(block, gradient, min_y, max_y, &occupation[0], &deltas[0]);
659  static_cast<int32_t>(ceil(block->line_spacing * (tesseract::CCStruct::kDescenderFraction +
661  static_cast<int32_t>(ceil(block->line_spacing * (tesseract::CCStruct::kXHeightFraction +
663  max_y - min_y + 1, &occupation[0], &deltas[0]);
664 #ifndef GRAPHICS_DISABLED
665  if (testing_on) {
666  draw_occupation(xleft, ybottom, min_y, max_y, &occupation[0], &deltas[0]);
667  }
668 #endif
669  compute_dropout_distances(&occupation[0], &deltas[0], line_count);
670  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
671  row = row_it.data();
672  line_index = static_cast<int32_t>(std::floor(row->intercept()));
673  distance = deltas[line_index - min_y];
674  if (find_best_dropout_row(row, distance, block->line_spacing / 2, line_index, &row_it,
675  testing_on)) {
676 #ifndef GRAPHICS_DISABLED
677  if (testing_on) {
678  plot_parallel_row(row, gradient, block_edge, ScrollView::WHITE, rotation);
679  }
680 #endif
681  blob_it.add_list_after(row_it.data()->blob_list());
682  delete row_it.extract(); // too far away
683  }
684  }
685  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
686  blob_it.add_list_after(row_it.data()->blob_list());
687  }
688 }
689 
696 bool find_best_dropout_row( // find neighbours
697  TO_ROW *row, // row to test
698  int32_t distance, // dropout dist
699  float dist_limit, // threshold distance
700  int32_t line_index, // index of row
701  TO_ROW_IT *row_it, // current position
702  bool testing_on // correct orientation
703 ) {
704  int32_t next_index; // of neighbouring row
705  int32_t row_offset; // from current row
706  int32_t abs_dist; // absolute distance
707  int8_t row_inc; // increment to row_index
708  TO_ROW *next_row; // nextious row
709 
710  if (testing_on) {
711  tprintf("Row at %g(%g), dropout dist=%d,", row->intercept(), row->parallel_c(), distance);
712  }
713  if (distance < 0) {
714  row_inc = 1;
715  abs_dist = -distance;
716  } else {
717  row_inc = -1;
718  abs_dist = distance;
719  }
720  if (abs_dist > dist_limit) {
721  if (testing_on) {
722  tprintf(" too far - deleting\n");
723  }
724  return true;
725  }
726  if ((distance < 0 && !row_it->at_last()) || (distance >= 0 && !row_it->at_first())) {
727  row_offset = row_inc;
728  do {
729  next_row = row_it->data_relative(row_offset);
730  next_index = static_cast<int32_t>(std::floor(next_row->intercept()));
731  if ((distance < 0 && next_index < line_index &&
732  next_index > line_index + distance + distance) ||
733  (distance >= 0 && next_index > line_index &&
734  next_index < line_index + distance + distance)) {
735  if (testing_on) {
736  tprintf(" nearer neighbour (%d) at %g\n", line_index + distance - next_index,
737  next_row->intercept());
738  }
739  return true; // other is nearer
740  } else if (next_index == line_index || next_index == line_index + distance + distance) {
741  if (row->believability() <= next_row->believability()) {
742  if (testing_on) {
743  tprintf(" equal but more believable at %g (%g/%g)\n", next_row->intercept(),
744  row->believability(), next_row->believability());
745  }
746  return true; // other is more believable
747  }
748  }
749  row_offset += row_inc;
750  } while ((next_index == line_index || next_index == line_index + distance + distance) &&
751  row_offset < row_it->length());
752  if (testing_on) {
753  tprintf(" keeping\n");
754  }
755  }
756  return false;
757 }
758 
766  TO_BLOCK *block, // block to do
767  float gradient // global skew
768 ) {
769  TBOX result; // block bounds
770  TBOX blob_box; // of block
771  FCOORD rotation; // deskew vector
772  float length; // of gradient vector
773  TO_ROW_IT row_it = block->get_rows();
774  TO_ROW *row; // current row
775  BLOBNBOX *blob; // current blob
776  BLOBNBOX_IT blob_it; // iterator
777 
778  length = std::sqrt(gradient * gradient + 1);
779  rotation = FCOORD(1 / length, -gradient / length);
780  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
781  row = row_it.data();
782  blob_it.set_to_list(row->blob_list());
783  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
784  blob = blob_it.data();
785  blob_box = blob->bounding_box();
786  blob_box.rotate(rotation); // de-skew it
787  result += blob_box;
788  }
789  }
790  return result;
791 }
792 
799 void compute_line_occupation( // project blobs
800  TO_BLOCK *block, // block to do
801  float gradient, // global skew
802  int32_t min_y, // min coord in block
803  int32_t max_y, // in block
804  int32_t *occupation, // output projection
805  int32_t *deltas // derivative
806 ) {
807  int32_t line_count; // maxy-miny+1
808  int32_t line_index; // of scan line
809  int index; // array index for daft compilers
810  TO_ROW *row; // current row
811  TO_ROW_IT row_it = block->get_rows();
812  BLOBNBOX *blob; // current blob
813  BLOBNBOX_IT blob_it; // iterator
814  float length; // of skew vector
815  TBOX blob_box; // bounding box
816  FCOORD rotation; // inverse of skew
817 
818  line_count = max_y - min_y + 1;
819  length = std::sqrt(gradient * gradient + 1);
820  rotation = FCOORD(1 / length, -gradient / length);
821  for (line_index = 0; line_index < line_count; line_index++) {
822  deltas[line_index] = 0;
823  }
824  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
825  row = row_it.data();
826  blob_it.set_to_list(row->blob_list());
827  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
828  blob = blob_it.data();
829  blob_box = blob->bounding_box();
830  blob_box.rotate(rotation); // de-skew it
831  int32_t width = blob_box.right() - blob_box.left();
832  index = blob_box.bottom() - min_y;
833  ASSERT_HOST(index >= 0 && index < line_count);
834  // count transitions
835  deltas[index] += width;
836  index = blob_box.top() - min_y;
837  ASSERT_HOST(index >= 0 && index < line_count);
838  deltas[index] -= width;
839  }
840  }
841  occupation[0] = deltas[0];
842  for (line_index = 1; line_index < line_count; line_index++) {
843  occupation[line_index] = occupation[line_index - 1] + deltas[line_index];
844  }
845 }
846 
852 void compute_occupation_threshold( // project blobs
853  int32_t low_window, // below result point
854  int32_t high_window, // above result point
855  int32_t line_count, // array sizes
856  int32_t *occupation, // input projection
857  int32_t *thresholds // output thresholds
858 ) {
859  int32_t line_index; // of thresholds line
860  int32_t low_index; // in occupation
861  int32_t high_index; // in occupation
862  int32_t sum; // current average
863  int32_t divisor; // to get thresholds
864  int32_t min_index; // of min occ
865  int32_t min_occ; // min in locality
866  int32_t test_index; // for finding min
867 
868  divisor = static_cast<int32_t>(ceil((low_window + high_window) / textord_occupancy_threshold));
869  if (low_window + high_window < line_count) {
870  for (sum = 0, high_index = 0; high_index < low_window; high_index++) {
871  sum += occupation[high_index];
872  }
873  for (low_index = 0; low_index < high_window; low_index++, high_index++) {
874  sum += occupation[high_index];
875  }
876  min_occ = occupation[0];
877  min_index = 0;
878  for (test_index = 1; test_index < high_index; test_index++) {
879  if (occupation[test_index] <= min_occ) {
880  min_occ = occupation[test_index];
881  min_index = test_index; // find min in region
882  }
883  }
884  for (line_index = 0; line_index < low_window; line_index++) {
885  thresholds[line_index] = (sum - min_occ) / divisor + min_occ;
886  }
887  // same out to end
888  for (low_index = 0; high_index < line_count; low_index++, high_index++) {
889  sum -= occupation[low_index];
890  sum += occupation[high_index];
891  if (occupation[high_index] <= min_occ) {
892  // find min in region
893  min_occ = occupation[high_index];
894  min_index = high_index;
895  }
896  // lost min from region
897  if (min_index <= low_index) {
898  min_occ = occupation[low_index + 1];
899  min_index = low_index + 1;
900  for (test_index = low_index + 2; test_index <= high_index; test_index++) {
901  if (occupation[test_index] <= min_occ) {
902  min_occ = occupation[test_index];
903  // find min in region
904  min_index = test_index;
905  }
906  }
907  }
908  thresholds[line_index++] = (sum - min_occ) / divisor + min_occ;
909  }
910  } else {
911  min_occ = occupation[0];
912  min_index = 0;
913  for (sum = 0, low_index = 0; low_index < line_count; low_index++) {
914  if (occupation[low_index] < min_occ) {
915  min_occ = occupation[low_index];
916  min_index = low_index;
917  }
918  sum += occupation[low_index];
919  }
920  line_index = 0;
921  }
922  for (; line_index < line_count; line_index++) {
923  thresholds[line_index] = (sum - min_occ) / divisor + min_occ;
924  }
925  // same out to end
926 }
927 
933 void compute_dropout_distances( // project blobs
934  int32_t *occupation, // input projection
935  int32_t *thresholds, // output thresholds
936  int32_t line_count // array sizes
937 ) {
938  int32_t line_index; // of thresholds line
939  int32_t distance; // from prev dropout
940  int32_t next_dist; // to next dropout
941  int32_t back_index; // for back filling
942  int32_t prev_threshold; // before overwrite
943 
944  distance = -line_count;
945  line_index = 0;
946  do {
947  do {
948  distance--;
949  prev_threshold = thresholds[line_index];
950  // distance from prev
951  thresholds[line_index] = distance;
952  line_index++;
953  } while (line_index < line_count && (occupation[line_index] < thresholds[line_index] ||
954  occupation[line_index - 1] >= prev_threshold));
955  if (line_index < line_count) {
956  back_index = line_index - 1;
957  next_dist = 1;
958  while (next_dist < -distance && back_index >= 0) {
959  thresholds[back_index] = next_dist;
960  back_index--;
961  next_dist++;
962  distance++;
963  }
964  distance = 1;
965  }
966  } while (line_index < line_count);
967 }
968 
976 void expand_rows( // find lines
977  ICOORD page_tr, // top right
978  TO_BLOCK *block, // block to do
979  float gradient, // gradient to fit
980  FCOORD rotation, // for drawing
981  int32_t block_edge, // edge of block
982  bool testing_on // correct orientation
983 ) {
984  bool swallowed_row; // eaten a neighbour
985  float y_max, y_min; // new row limits
986  float y_bottom, y_top; // allowed limits
987  TO_ROW *test_row; // next row
988  TO_ROW *row; // current row
989  // iterators
990  BLOBNBOX_IT blob_it = &block->blobs;
991  TO_ROW_IT row_it = block->get_rows();
992 
993 #ifndef GRAPHICS_DISABLED
994  if (textord_show_expanded_rows && testing_on) {
995  if (to_win == nullptr) {
996  create_to_win(page_tr);
997  }
998  }
999 #endif
1000 
1001  adjust_row_limits(block); // shift min,max.
1003  if (block->get_rows()->empty()) {
1004  return;
1005  }
1006  compute_row_stats(block, textord_show_expanded_rows && testing_on);
1007  }
1008  assign_blobs_to_rows(block, &gradient, 4, true, false, false);
1009  // get real membership
1010  if (block->get_rows()->empty()) {
1011  return;
1012  }
1013  fit_parallel_rows(block, gradient, rotation, block_edge,
1014  textord_show_expanded_rows && testing_on);
1016  compute_row_stats(block, textord_show_expanded_rows && testing_on);
1017  }
1018  row_it.move_to_last();
1019  do {
1020  row = row_it.data();
1021  y_max = row->max_y(); // get current limits
1022  y_min = row->min_y();
1023  y_bottom = row->intercept() - block->line_size * textord_expansion_factor *
1025  y_top = row->intercept() +
1026  block->line_size * textord_expansion_factor *
1028  if (y_min > y_bottom) { // expansion allowed
1029  if (textord_show_expanded_rows && testing_on) {
1030  tprintf("Expanding bottom of row at %f from %f to %f\n", row->intercept(), y_min, y_bottom);
1031  }
1032  // expandable
1033  swallowed_row = true;
1034  while (swallowed_row && !row_it.at_last()) {
1035  swallowed_row = false;
1036  // get next one
1037  test_row = row_it.data_relative(1);
1038  // overlaps space
1039  if (test_row->max_y() > y_bottom) {
1040  if (test_row->min_y() > y_bottom) {
1041  if (textord_show_expanded_rows && testing_on) {
1042  tprintf("Eating row below at %f\n", test_row->intercept());
1043  }
1044  row_it.forward();
1045 #ifndef GRAPHICS_DISABLED
1046  if (textord_show_expanded_rows && testing_on) {
1047  plot_parallel_row(test_row, gradient, block_edge, ScrollView::WHITE, rotation);
1048  }
1049 #endif
1050  blob_it.set_to_list(row->blob_list());
1051  blob_it.add_list_after(test_row->blob_list());
1052  // swallow complete row
1053  delete row_it.extract();
1054  row_it.backward();
1055  swallowed_row = true;
1056  } else if (test_row->max_y() < y_min) {
1057  // shorter limit
1058  y_bottom = test_row->max_y();
1059  if (textord_show_expanded_rows && testing_on) {
1060  tprintf("Truncating limit to %f due to touching row at %f\n", y_bottom,
1061  test_row->intercept());
1062  }
1063  } else {
1064  y_bottom = y_min; // can't expand it
1065  if (textord_show_expanded_rows && testing_on) {
1066  tprintf("Not expanding limit beyond %f due to touching row at %f\n", y_bottom,
1067  test_row->intercept());
1068  }
1069  }
1070  }
1071  }
1072  y_min = y_bottom; // expand it
1073  }
1074  if (y_max < y_top) { // expansion allowed
1075  if (textord_show_expanded_rows && testing_on) {
1076  tprintf("Expanding top of row at %f from %f to %f\n", row->intercept(), y_max, y_top);
1077  }
1078  swallowed_row = true;
1079  while (swallowed_row && !row_it.at_first()) {
1080  swallowed_row = false;
1081  // get one above
1082  test_row = row_it.data_relative(-1);
1083  if (test_row->min_y() < y_top) {
1084  if (test_row->max_y() < y_top) {
1085  if (textord_show_expanded_rows && testing_on) {
1086  tprintf("Eating row above at %f\n", test_row->intercept());
1087  }
1088  row_it.backward();
1089  blob_it.set_to_list(row->blob_list());
1090 #ifndef GRAPHICS_DISABLED
1091  if (textord_show_expanded_rows && testing_on) {
1092  plot_parallel_row(test_row, gradient, block_edge, ScrollView::WHITE, rotation);
1093  }
1094 #endif
1095  blob_it.add_list_after(test_row->blob_list());
1096  // swallow complete row
1097  delete row_it.extract();
1098  row_it.forward();
1099  swallowed_row = true;
1100  } else if (test_row->min_y() < y_max) {
1101  // shorter limit
1102  y_top = test_row->min_y();
1103  if (textord_show_expanded_rows && testing_on) {
1104  tprintf("Truncating limit to %f due to touching row at %f\n", y_top,
1105  test_row->intercept());
1106  }
1107  } else {
1108  y_top = y_max; // can't expand it
1109  if (textord_show_expanded_rows && testing_on) {
1110  tprintf("Not expanding limit beyond %f due to touching row at %f\n", y_top,
1111  test_row->intercept());
1112  }
1113  }
1114  }
1115  }
1116  y_max = y_top;
1117  }
1118  // new limits
1119  row->set_limits(y_min, y_max);
1120  row_it.backward();
1121  } while (!row_it.at_last());
1122 }
1123 
1129 void adjust_row_limits( // tidy limits
1130  TO_BLOCK *block // block to do
1131 ) {
1132  TO_ROW *row; // current row
1133  float size; // size of row
1134  float ymax; // top of row
1135  float ymin; // bottom of row
1136  TO_ROW_IT row_it = block->get_rows();
1137 
1139  tprintf("Adjusting row limits for block(%d,%d)\n", block->block->pdblk.bounding_box().left(),
1140  block->block->pdblk.bounding_box().top());
1141  }
1142  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
1143  row = row_it.data();
1144  size = row->max_y() - row->min_y();
1146  tprintf("Row at %f has min %f, max %f, size %f\n", row->intercept(), row->min_y(),
1147  row->max_y(), size);
1148  }
1153  row->set_limits(row->intercept() + ymin, row->intercept() + ymax);
1154  row->merged = false;
1155  }
1156 }
1157 
1163 void compute_row_stats( // find lines
1164  TO_BLOCK *block, // block to do
1165  bool testing_on // correct orientation
1166 ) {
1167  int32_t row_index; // of median
1168  TO_ROW *row; // current row
1169  TO_ROW *prev_row; // previous row
1170  float iqr; // inter quartile range
1171  TO_ROW_IT row_it = block->get_rows();
1172  // number of rows
1173  int16_t rowcount = row_it.length();
1174  // for choose nth
1175  std::vector<TO_ROW *> rows(rowcount);
1176  rowcount = 0;
1177  prev_row = nullptr;
1178  row_it.move_to_last(); // start at bottom
1179  do {
1180  row = row_it.data();
1181  if (prev_row != nullptr) {
1182  rows[rowcount++] = prev_row;
1183  prev_row->spacing = row->intercept() - prev_row->intercept();
1184  if (prev_row->spacing < 0.1 && prev_row->spacing > -0.1) {
1185  // Avoid small spacing values which give a small disp_quant_factor_.
1186  // That can cause large memory allocations with out-of-memory.
1187  prev_row->spacing = 0;
1188  }
1189  if (testing_on) {
1190  tprintf("Row at %g yields spacing of %g\n", row->intercept(), prev_row->spacing);
1191  }
1192  }
1193  prev_row = row;
1194  row_it.backward();
1195  } while (!row_it.at_last());
1196  block->key_row = prev_row;
1197  block->baseline_offset = std::fmod(prev_row->parallel_c(), block->line_spacing);
1198  if (testing_on) {
1199  tprintf("Blob based spacing=(%g,%g), offset=%g", block->line_size, block->line_spacing,
1200  block->baseline_offset);
1201  }
1202  if (rowcount > 0) {
1203  rows.resize(rowcount);
1204  row_index = rowcount * 3 / 4;
1205  std::nth_element(rows.begin(), rows.begin() + row_index, rows.end(), row_spacing_order);
1206  iqr = rows[row_index]->spacing;
1207  row_index = rowcount / 4;
1208  std::nth_element(rows.begin(), rows.begin() + row_index, rows.end(), row_spacing_order);
1209  iqr -= rows[row_index]->spacing;
1210  row_index = rowcount / 2;
1211  std::nth_element(rows.begin(), rows.begin() + row_index, rows.end(), row_spacing_order);
1212  block->key_row = rows[row_index];
1213  if (testing_on) {
1214  tprintf(" row based=%g(%g)", rows[row_index]->spacing, iqr);
1215  }
1216  if (rowcount > 2 && iqr < rows[row_index]->spacing * textord_linespace_iqrlimit) {
1218  if (rows[row_index]->spacing < block->line_spacing &&
1219  rows[row_index]->spacing > block->line_size) {
1220  // within range
1221  block->line_size = rows[row_index]->spacing;
1222  // spacing=size
1223  } else if (rows[row_index]->spacing > block->line_spacing) {
1224  block->line_size = block->line_spacing;
1225  }
1226  // too big so use max
1227  } else {
1228  if (rows[row_index]->spacing < block->line_spacing) {
1229  block->line_size = rows[row_index]->spacing;
1230  } else {
1231  block->line_size = block->line_spacing;
1232  }
1233  // too big so use max
1234  }
1235  if (block->line_size < textord_min_xheight) {
1236  block->line_size = (float)textord_min_xheight;
1237  }
1238  block->line_spacing = rows[row_index]->spacing;
1240  }
1241  block->baseline_offset = std::fmod(rows[row_index]->intercept(), block->line_spacing);
1242  }
1243  if (testing_on) {
1244  tprintf("\nEstimate line size=%g, spacing=%g, offset=%g\n", block->line_size,
1245  block->line_spacing, block->baseline_offset);
1246  }
1247 }
1248 
1278 void Textord::compute_block_xheight(TO_BLOCK *block, float gradient) {
1279  TO_ROW *row; // current row
1280  float asc_frac_xheight = CCStruct::kAscenderFraction / CCStruct::kXHeightFraction;
1281  float desc_frac_xheight = CCStruct::kDescenderFraction / CCStruct::kXHeightFraction;
1282  int32_t min_height, max_height; // limits on xheight
1283  TO_ROW_IT row_it = block->get_rows();
1284  if (row_it.empty()) {
1285  return; // no rows
1286  }
1287 
1288  // Compute the best guess of xheight of each row individually.
1289  // Use xheight and ascrise values of the rows where ascenders were found.
1290  get_min_max_xheight(block->line_size, &min_height, &max_height);
1291  STATS row_asc_xheights(min_height, max_height + 1);
1292  STATS row_asc_ascrise(static_cast<int>(min_height * asc_frac_xheight),
1293  static_cast<int>(max_height * asc_frac_xheight) + 1);
1294  int min_desc_height = static_cast<int>(min_height * desc_frac_xheight);
1295  int max_desc_height = static_cast<int>(max_height * desc_frac_xheight);
1296  STATS row_asc_descdrop(min_desc_height, max_desc_height + 1);
1297  STATS row_desc_xheights(min_height, max_height + 1);
1298  STATS row_desc_descdrop(min_desc_height, max_desc_height + 1);
1299  STATS row_cap_xheights(min_height, max_height + 1);
1300  STATS row_cap_floating_xheights(min_height, max_height + 1);
1301  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
1302  row = row_it.data();
1303  // Compute the xheight of this row if it has not been computed before.
1304  if (row->xheight <= 0) {
1305  compute_row_xheight(row, block->block->classify_rotation(), gradient, block->line_size);
1306  }
1307  ROW_CATEGORY row_category = get_row_category(row);
1308  if (row_category == ROW_ASCENDERS_FOUND) {
1309  row_asc_xheights.add(static_cast<int32_t>(row->xheight), row->xheight_evidence);
1310  row_asc_ascrise.add(static_cast<int32_t>(row->ascrise), row->xheight_evidence);
1311  row_asc_descdrop.add(static_cast<int32_t>(-row->descdrop), row->xheight_evidence);
1312  } else if (row_category == ROW_DESCENDERS_FOUND) {
1313  row_desc_xheights.add(static_cast<int32_t>(row->xheight), row->xheight_evidence);
1314  row_desc_descdrop.add(static_cast<int32_t>(-row->descdrop), row->xheight_evidence);
1315  } else if (row_category == ROW_UNKNOWN) {
1316  fill_heights(row, gradient, min_height, max_height, &row_cap_xheights,
1317  &row_cap_floating_xheights);
1318  }
1319  }
1320 
1321  float xheight = 0.0;
1322  float ascrise = 0.0;
1323  float descdrop = 0.0;
1324  // Compute our best guess of xheight of this block.
1325  if (row_asc_xheights.get_total() > 0) {
1326  // Determine xheight from rows where ascenders were found.
1327  xheight = row_asc_xheights.median();
1328  ascrise = row_asc_ascrise.median();
1329  descdrop = -row_asc_descdrop.median();
1330  } else if (row_desc_xheights.get_total() > 0) {
1331  // Determine xheight from rows where descenders were found.
1332  xheight = row_desc_xheights.median();
1333  descdrop = -row_desc_descdrop.median();
1334  } else if (row_cap_xheights.get_total() > 0) {
1335  // All the rows in the block were (a/de)scenderless.
1336  // Try to search for two modes in row_cap_heights that could
1337  // be the xheight and the capheight (e.g. some of the rows
1338  // were lowercase, but did not have enough (a/de)scenders.
1339  // If such two modes can not be found, this block is most
1340  // likely all caps (or all small caps, in which case the code
1341  // still works as intended).
1343  &row_cap_xheights, &row_cap_floating_xheights,
1344  textord_single_height_mode && block->block->classify_rotation().y() == 0.0, min_height,
1345  max_height, &(xheight), &(ascrise));
1346  if (ascrise == 0) { // assume only caps in the whole block
1347  xheight = row_cap_xheights.median() * CCStruct::kXHeightCapRatio;
1348  }
1349  } else { // default block sizes
1350  xheight = block->line_size * CCStruct::kXHeightFraction;
1351  }
1352  // Correct xheight, ascrise and descdrop if necessary.
1353  bool corrected_xheight = false;
1354  if (xheight < textord_min_xheight) {
1355  xheight = static_cast<float>(textord_min_xheight);
1356  corrected_xheight = true;
1357  }
1358  if (corrected_xheight || ascrise <= 0) {
1359  ascrise = xheight * asc_frac_xheight;
1360  }
1361  if (corrected_xheight || descdrop >= 0) {
1362  descdrop = -(xheight * desc_frac_xheight);
1363  }
1364  block->xheight = xheight;
1365 
1366  if (textord_debug_xheights) {
1367  tprintf("Block average xheight=%.4f, ascrise=%.4f, descdrop=%.4f\n", xheight, ascrise,
1368  descdrop);
1369  }
1370  // Correct xheight, ascrise, descdrop of rows based on block averages.
1371  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
1372  correct_row_xheight(row_it.data(), xheight, ascrise, descdrop);
1373  }
1374 }
1375 
1384 void Textord::compute_row_xheight(TO_ROW *row, // row to do
1385  const FCOORD &rotation,
1386  float gradient, // global skew
1387  int block_line_size) {
1388  // Find blobs representing repeated characters in rows and mark them.
1389  // This information is used for computing row xheight and at a later
1390  // stage when words are formed by make_words.
1391  if (!row->rep_chars_marked()) {
1392  mark_repeated_chars(row);
1393  }
1394 
1395  int min_height, max_height;
1396  get_min_max_xheight(block_line_size, &min_height, &max_height);
1397  STATS heights(min_height, max_height + 1);
1398  STATS floating_heights(min_height, max_height + 1);
1399  fill_heights(row, gradient, min_height, max_height, &heights, &floating_heights);
1400  row->ascrise = 0.0f;
1401  row->xheight = 0.0f;
1403  &heights, &floating_heights, textord_single_height_mode && rotation.y() == 0.0, min_height,
1404  max_height, &(row->xheight), &(row->ascrise));
1405  row->descdrop = 0.0f;
1406  if (row->xheight > 0) {
1407  row->descdrop =
1408  static_cast<float>(compute_row_descdrop(row, gradient, row->xheight_evidence, &heights));
1409  }
1410 }
1411 
1418 void fill_heights(TO_ROW *row, float gradient, int min_height, int max_height, STATS *heights,
1419  STATS *floating_heights) {
1420  float xcentre; // centre of blob
1421  float top; // top y coord of blob
1422  float height; // height of blob
1423  BLOBNBOX *blob; // current blob
1424  int repeated_set;
1425  BLOBNBOX_IT blob_it = row->blob_list();
1426  if (blob_it.empty()) {
1427  return; // no blobs in this row
1428  }
1429  bool has_rep_chars = row->rep_chars_marked() && row->num_repeated_sets() > 0;
1430  do {
1431  blob = blob_it.data();
1432  if (!blob->joined_to_prev()) {
1433  xcentre = (blob->bounding_box().left() + blob->bounding_box().right()) / 2.0f;
1434  top = blob->bounding_box().top();
1435  height = blob->bounding_box().height();
1437  top -= row->baseline.y(xcentre);
1438  } else {
1439  top -= gradient * xcentre + row->parallel_c();
1440  }
1441  if (top >= min_height && top <= max_height) {
1442  heights->add(static_cast<int32_t>(floor(top + 0.5)), 1);
1443  if (height / top < textord_min_blob_height_fraction) {
1444  floating_heights->add(static_cast<int32_t>(floor(top + 0.5)), 1);
1445  }
1446  }
1447  }
1448  // Skip repeated chars, since they are likely to skew the height stats.
1449  if (has_rep_chars && blob->repeated_set() != 0) {
1450  repeated_set = blob->repeated_set();
1451  blob_it.forward();
1452  while (!blob_it.at_first() && blob_it.data()->repeated_set() == repeated_set) {
1453  blob_it.forward();
1454  if (textord_debug_xheights) {
1455  tprintf("Skipping repeated char when computing xheight\n");
1456  }
1457  }
1458  } else {
1459  blob_it.forward();
1460  }
1461  } while (!blob_it.at_first());
1462 }
1463 
1480 int compute_xheight_from_modes(STATS *heights, STATS *floating_heights, bool cap_only,
1481  int min_height, int max_height, float *xheight, float *ascrise) {
1482  int blob_index = heights->mode(); // find mode
1483  int blob_count = heights->pile_count(blob_index); // get count of mode
1484  if (textord_debug_xheights) {
1485  tprintf("min_height=%d, max_height=%d, mode=%d, count=%d, total=%d\n", min_height, max_height,
1486  blob_index, blob_count, heights->get_total());
1487  heights->print();
1488  floating_heights->print();
1489  }
1490  if (blob_count == 0) {
1491  return 0;
1492  }
1493  int modes[MAX_HEIGHT_MODES]; // biggest piles
1494  bool in_best_pile = false;
1495  int prev_size = -INT32_MAX;
1496  int best_count = 0;
1497  int mode_count = compute_height_modes(heights, min_height, max_height, modes, MAX_HEIGHT_MODES);
1498  if (cap_only && mode_count > 1) {
1499  mode_count = 1;
1500  }
1501  int x;
1502  if (textord_debug_xheights) {
1503  tprintf("found %d modes: ", mode_count);
1504  for (x = 0; x < mode_count; x++) {
1505  tprintf("%d ", modes[x]);
1506  }
1507  tprintf("\n");
1508  }
1509 
1510  for (x = 0; x < mode_count - 1; x++) {
1511  if (modes[x] != prev_size + 1) {
1512  in_best_pile = false; // had empty height
1513  }
1514  int modes_x_count = heights->pile_count(modes[x]) - floating_heights->pile_count(modes[x]);
1515  if ((modes_x_count >= blob_count * textord_xheight_mode_fraction) &&
1516  (in_best_pile || modes_x_count > best_count)) {
1517  for (int asc = x + 1; asc < mode_count; asc++) {
1518  float ratio = static_cast<float>(modes[asc]) / static_cast<float>(modes[x]);
1519  if (textord_ascx_ratio_min < ratio && ratio < textord_ascx_ratio_max &&
1520  (heights->pile_count(modes[asc]) >= blob_count * textord_ascheight_mode_fraction)) {
1521  if (modes_x_count > best_count) {
1522  in_best_pile = true;
1523  best_count = modes_x_count;
1524  }
1525  if (textord_debug_xheights) {
1526  tprintf("X=%d, asc=%d, count=%d, ratio=%g\n", modes[x], modes[asc] - modes[x],
1527  modes_x_count, ratio);
1528  }
1529  prev_size = modes[x];
1530  *xheight = static_cast<float>(modes[x]);
1531  *ascrise = static_cast<float>(modes[asc] - modes[x]);
1532  }
1533  }
1534  }
1535  }
1536  if (*xheight == 0) { // single mode
1537  // Remove counts of the "floating" blobs (the one whose height is too
1538  // small in relation to it's top end of the bounding box) from heights
1539  // before computing the single-mode xheight.
1540  // Restore the counts in heights after the mode is found, since
1541  // floating blobs might be useful for determining potential ascenders
1542  // in compute_row_descdrop().
1543  if (floating_heights->get_total() > 0) {
1544  for (x = min_height; x < max_height; ++x) {
1545  heights->add(x, -(floating_heights->pile_count(x)));
1546  }
1547  blob_index = heights->mode(); // find the modified mode
1548  for (x = min_height; x < max_height; ++x) {
1549  heights->add(x, floating_heights->pile_count(x));
1550  }
1551  }
1552  *xheight = static_cast<float>(blob_index);
1553  *ascrise = 0.0f;
1554  best_count = heights->pile_count(blob_index);
1555  if (textord_debug_xheights) {
1556  tprintf("Single mode xheight set to %g\n", *xheight);
1557  }
1558  } else if (textord_debug_xheights) {
1559  tprintf("Multi-mode xheight set to %g, asc=%g\n", *xheight, *ascrise);
1560  }
1561  return best_count;
1562 }
1563 
1576 int32_t compute_row_descdrop(TO_ROW *row, float gradient, int xheight_blob_count,
1577  STATS *asc_heights) {
1578  // Count how many potential ascenders are in this row.
1579  int i_min = asc_heights->min_bucket();
1580  if ((i_min / row->xheight) < textord_ascx_ratio_min) {
1581  i_min = static_cast<int>(floor(row->xheight * textord_ascx_ratio_min + 0.5));
1582  }
1583  int i_max = asc_heights->max_bucket();
1584  if ((i_max / row->xheight) > textord_ascx_ratio_max) {
1585  i_max = static_cast<int>(floor(row->xheight * textord_ascx_ratio_max));
1586  }
1587  int num_potential_asc = 0;
1588  for (int i = i_min; i <= i_max; ++i) {
1589  num_potential_asc += asc_heights->pile_count(i);
1590  }
1591  auto min_height = static_cast<int32_t>(floor(row->xheight * textord_descx_ratio_min + 0.5));
1592  auto max_height = static_cast<int32_t>(floor(row->xheight * textord_descx_ratio_max));
1593  float xcentre; // centre of blob
1594  float height; // height of blob
1595  BLOBNBOX_IT blob_it = row->blob_list();
1596  BLOBNBOX *blob; // current blob
1597  STATS heights(min_height, max_height + 1);
1598  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
1599  blob = blob_it.data();
1600  if (!blob->joined_to_prev()) {
1601  xcentre = (blob->bounding_box().left() + blob->bounding_box().right()) / 2.0f;
1602  height = (gradient * xcentre + row->parallel_c() - blob->bounding_box().bottom());
1603  if (height >= min_height && height <= max_height) {
1604  heights.add(static_cast<int>(floor(height + 0.5)), 1);
1605  }
1606  }
1607  }
1608  int blob_index = heights.mode(); // find mode
1609  int blob_count = heights.pile_count(blob_index); // get count of mode
1610  float total_fraction = (textord_descheight_mode_fraction + textord_ascheight_mode_fraction);
1611  if (static_cast<float>(blob_count + num_potential_asc) < xheight_blob_count * total_fraction) {
1612  blob_count = 0;
1613  }
1614  int descdrop = blob_count > 0 ? -blob_index : 0;
1615  if (textord_debug_xheights) {
1616  tprintf("Descdrop: %d (potential ascenders %d, descenders %d)\n", descdrop, num_potential_asc,
1617  blob_count);
1618  heights.print();
1619  }
1620  return descdrop;
1621 }
1622 
1629 int32_t compute_height_modes(STATS *heights, // stats to search
1630  int32_t min_height, // bottom of range
1631  int32_t max_height, // top of range
1632  int32_t *modes, // output array
1633  int32_t maxmodes) { // size of modes
1634  int32_t pile_count; // no in source pile
1635  int32_t src_count; // no of source entries
1636  int32_t src_index; // current entry
1637  int32_t least_count; // height of smalllest
1638  int32_t least_index; // index of least
1639  int32_t dest_count; // index in modes
1640 
1641  src_count = max_height + 1 - min_height;
1642  dest_count = 0;
1643  least_count = INT32_MAX;
1644  least_index = -1;
1645  for (src_index = 0; src_index < src_count; src_index++) {
1646  pile_count = heights->pile_count(min_height + src_index);
1647  if (pile_count > 0) {
1648  if (dest_count < maxmodes) {
1649  if (pile_count < least_count) {
1650  // find smallest in array
1651  least_count = pile_count;
1652  least_index = dest_count;
1653  }
1654  modes[dest_count++] = min_height + src_index;
1655  } else if (pile_count >= least_count) {
1656  while (least_index < maxmodes - 1) {
1657  modes[least_index] = modes[least_index + 1];
1658  // shuffle up
1659  least_index++;
1660  }
1661  // new one on end
1662  modes[maxmodes - 1] = min_height + src_index;
1663  if (pile_count == least_count) {
1664  // new smallest
1665  least_index = maxmodes - 1;
1666  } else {
1667  least_count = heights->pile_count(modes[0]);
1668  least_index = 0;
1669  for (dest_count = 1; dest_count < maxmodes; dest_count++) {
1670  pile_count = heights->pile_count(modes[dest_count]);
1671  if (pile_count < least_count) {
1672  // find smallest
1673  least_count = pile_count;
1674  least_index = dest_count;
1675  }
1676  }
1677  }
1678  }
1679  }
1680  }
1681  return dest_count;
1682 }
1683 
1690 void correct_row_xheight(TO_ROW *row, float xheight, float ascrise, float descdrop) {
1691  ROW_CATEGORY row_category = get_row_category(row);
1692  if (textord_debug_xheights) {
1693  tprintf(
1694  "correcting row xheight: row->xheight %.4f"
1695  ", row->acrise %.4f row->descdrop %.4f\n",
1696  row->xheight, row->ascrise, row->descdrop);
1697  }
1698  bool normal_xheight = within_error_margin(row->xheight, xheight, textord_xheight_error_margin);
1699  bool cap_xheight =
1700  within_error_margin(row->xheight, xheight + ascrise, textord_xheight_error_margin);
1701  // Use the average xheight/ascrise for the following cases:
1702  // -- the xheight of the row could not be determined at all
1703  // -- the row has descenders (e.g. "many groups", "ISBN 12345 p.3")
1704  // and its xheight is close to either cap height or average xheight
1705  // -- the row does not have ascenders or descenders, but its xheight
1706  // is close to the average block xheight (e.g. row with "www.mmm.com")
1707  if (row_category == ROW_ASCENDERS_FOUND) {
1708  if (row->descdrop >= 0) {
1709  row->descdrop = row->xheight * (descdrop / xheight);
1710  }
1711  } else if (row_category == ROW_INVALID ||
1712  (row_category == ROW_DESCENDERS_FOUND && (normal_xheight || cap_xheight)) ||
1713  (row_category == ROW_UNKNOWN && normal_xheight)) {
1714  if (textord_debug_xheights) {
1715  tprintf("using average xheight\n");
1716  }
1717  row->xheight = xheight;
1718  row->ascrise = ascrise;
1719  row->descdrop = descdrop;
1720  } else if (row_category == ROW_DESCENDERS_FOUND) {
1721  // Assume this is a row with mostly lowercase letters and it's xheight
1722  // is computed correctly (unfortunately there is no way to distinguish
1723  // this from the case when descenders are found, but the most common
1724  // height is capheight).
1725  if (textord_debug_xheights) {
1726  tprintf("lowercase, corrected ascrise\n");
1727  }
1728  row->ascrise = row->xheight * (ascrise / xheight);
1729  } else if (row_category == ROW_UNKNOWN) {
1730  // Otherwise assume this row is an all-caps or small-caps row
1731  // and adjust xheight and ascrise of the row.
1732 
1733  row->all_caps = true;
1734  if (cap_xheight) { // regular all caps
1735  if (textord_debug_xheights) {
1736  tprintf("all caps\n");
1737  }
1738  row->xheight = xheight;
1739  row->ascrise = ascrise;
1740  row->descdrop = descdrop;
1741  } else { // small caps or caps with an odd xheight
1742  if (textord_debug_xheights) {
1743  if (row->xheight < xheight + ascrise && row->xheight > xheight) {
1744  tprintf("small caps\n");
1745  } else {
1746  tprintf("all caps with irregular xheight\n");
1747  }
1748  }
1749  row->ascrise = row->xheight * (ascrise / (xheight + ascrise));
1750  row->xheight -= row->ascrise;
1751  row->descdrop = row->xheight * (descdrop / xheight);
1752  }
1753  }
1754  if (textord_debug_xheights) {
1755  tprintf(
1756  "corrected row->xheight = %.4f, row->acrise = %.4f, row->descdrop"
1757  " = %.4f\n",
1758  row->xheight, row->ascrise, row->descdrop);
1759  }
1760 }
1761 
1762 static int CountOverlaps(const TBOX &box, int min_height, BLOBNBOX_LIST *blobs) {
1763  int overlaps = 0;
1764  BLOBNBOX_IT blob_it(blobs);
1765  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
1766  BLOBNBOX *blob = blob_it.data();
1767  const TBOX &blob_box = blob->bounding_box();
1768  if (blob_box.height() >= min_height && box.major_overlap(blob_box)) {
1769  ++overlaps;
1770  }
1771  }
1772  return overlaps;
1773 }
1774 
1781 void separate_underlines(TO_BLOCK *block, // block to do
1782  float gradient, // skew angle
1783  FCOORD rotation, // inverse landscape
1784  bool testing_on) { // correct orientation
1785  BLOBNBOX *blob; // current blob
1786  C_BLOB *rotated_blob; // rotated blob
1787  TO_ROW *row; // current row
1788  float length; // of g_vec
1789  TBOX blob_box;
1790  FCOORD blob_rotation; // inverse of rotation
1791  FCOORD g_vec; // skew rotation
1792  BLOBNBOX_IT blob_it; // iterator
1793  // iterator
1794  BLOBNBOX_IT under_it = &block->underlines;
1795  BLOBNBOX_IT large_it = &block->large_blobs;
1796  TO_ROW_IT row_it = block->get_rows();
1797  int min_blob_height = static_cast<int>(textord_min_blob_height_fraction * block->line_size + 0.5);
1798 
1799  // length of vector
1800  length = std::sqrt(1 + gradient * gradient);
1801  g_vec = FCOORD(1 / length, -gradient / length);
1802  blob_rotation = FCOORD(rotation.x(), -rotation.y());
1803  blob_rotation.rotate(g_vec); // undoing everything
1804  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
1805  row = row_it.data();
1806  // get blobs
1807  blob_it.set_to_list(row->blob_list());
1808  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
1809  blob = blob_it.data();
1810  blob_box = blob->bounding_box();
1811  if (blob_box.width() > block->line_size * textord_underline_width) {
1812  ASSERT_HOST(blob->cblob() != nullptr);
1813  rotated_blob = crotate_cblob(blob->cblob(), blob_rotation);
1814  if (test_underline(testing_on && textord_show_final_rows, rotated_blob,
1815  static_cast<int16_t>(row->intercept()),
1816  static_cast<int16_t>(block->line_size *
1819  under_it.add_after_then_move(blob_it.extract());
1820  if (testing_on && textord_show_final_rows) {
1821  tprintf("Underlined blob at:");
1822  rotated_blob->bounding_box().print();
1823  tprintf("Was:");
1824  blob_box.print();
1825  }
1826  } else if (CountOverlaps(blob->bounding_box(), min_blob_height, row->blob_list()) >
1827  textord_max_blob_overlaps) {
1828  large_it.add_after_then_move(blob_it.extract());
1829  if (testing_on && textord_show_final_rows) {
1830  tprintf("Large blob overlaps %d blobs at:",
1831  CountOverlaps(blob_box, min_blob_height, row->blob_list()));
1832  blob_box.print();
1833  }
1834  }
1835  delete rotated_blob;
1836  }
1837  }
1838  }
1839 }
1840 
1846 void pre_associate_blobs( // make rough chars
1847  ICOORD page_tr, // top right
1848  TO_BLOCK *block, // block to do
1849  FCOORD rotation, // inverse landscape
1850  bool testing_on // correct orientation
1851 ) {
1852 #ifndef GRAPHICS_DISABLED
1853  ScrollView::Color colour; // of boxes
1854 #endif
1855  BLOBNBOX *blob; // current blob
1856  BLOBNBOX *nextblob; // next in list
1857  TBOX blob_box;
1858  FCOORD blob_rotation; // inverse of rotation
1859  BLOBNBOX_IT blob_it; // iterator
1860  BLOBNBOX_IT start_it; // iterator
1861  TO_ROW_IT row_it = block->get_rows();
1862 
1863 #ifndef GRAPHICS_DISABLED
1864  colour = ScrollView::RED;
1865 #endif
1866 
1867  blob_rotation = FCOORD(rotation.x(), -rotation.y());
1868  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
1869  // get blobs
1870  blob_it.set_to_list(row_it.data()->blob_list());
1871  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
1872  blob = blob_it.data();
1873  blob_box = blob->bounding_box();
1874  start_it = blob_it; // save start point
1875  // if (testing_on && textord_show_final_blobs)
1876  // {
1877  // tprintf("Blob at (%d,%d)->(%d,%d),
1878  // addr=%x, count=%d\n",
1879  // blob_box.left(),blob_box.bottom(),
1880  // blob_box.right(),blob_box.top(),
1881  // (void*)blob,blob_it.length());
1882  // }
1883  bool overlap;
1884  do {
1885  overlap = false;
1886  if (!blob_it.at_last()) {
1887  nextblob = blob_it.data_relative(1);
1888  overlap = blob_box.major_x_overlap(nextblob->bounding_box());
1889  if (overlap) {
1890  blob->merge(nextblob); // merge new blob
1891  blob_box = blob->bounding_box(); // get bigger box
1892  blob_it.forward();
1893  }
1894  }
1895  } while (overlap);
1896  blob->chop(&start_it, &blob_it, blob_rotation,
1898  // attempt chop
1899  }
1900 #ifndef GRAPHICS_DISABLED
1901  if (testing_on && textord_show_final_blobs) {
1902  if (to_win == nullptr) {
1903  create_to_win(page_tr);
1904  }
1905  to_win->Pen(colour);
1906  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
1907  blob = blob_it.data();
1908  blob_box = blob->bounding_box();
1909  blob_box.rotate(rotation);
1910  if (!blob->joined_to_prev()) {
1911  to_win->Rectangle(blob_box.left(), blob_box.bottom(), blob_box.right(), blob_box.top());
1912  }
1913  }
1914  colour = static_cast<ScrollView::Color>(colour + 1);
1915  if (colour > ScrollView::MAGENTA) {
1916  colour = ScrollView::RED;
1917  }
1918  }
1919 #endif
1920  }
1921 }
1922 
1928 void fit_parallel_rows( // find lines
1929  TO_BLOCK *block, // block to do
1930  float gradient, // gradient to fit
1931  FCOORD rotation, // for drawing
1932  int32_t block_edge, // edge of block
1933  bool testing_on // correct orientation
1934 ) {
1935 #ifndef GRAPHICS_DISABLED
1936  ScrollView::Color colour; // of row
1937 #endif
1938  TO_ROW_IT row_it = block->get_rows();
1939 
1940  row_it.move_to_first();
1941  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
1942  if (row_it.data()->blob_list()->empty()) {
1943  delete row_it.extract(); // nothing in it
1944  } else {
1945  fit_parallel_lms(gradient, row_it.data());
1946  }
1947  }
1948 #ifndef GRAPHICS_DISABLED
1949  if (testing_on) {
1950  colour = ScrollView::RED;
1951  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
1952  plot_parallel_row(row_it.data(), gradient, block_edge, colour, rotation);
1953  colour = static_cast<ScrollView::Color>(colour + 1);
1954  if (colour > ScrollView::MAGENTA) {
1955  colour = ScrollView::RED;
1956  }
1957  }
1958  }
1959 #endif
1960  row_it.sort(row_y_order); // may have gone out of order
1961 }
1962 
1970 void fit_parallel_lms(float gradient, TO_ROW *row) {
1971  float c; // fitted line
1972  int blobcount; // no of blobs
1974  BLOBNBOX_IT blob_it = row->blob_list();
1975 
1976  blobcount = 0;
1977  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
1978  if (!blob_it.data()->joined_to_prev()) {
1979  const TBOX &box = blob_it.data()->bounding_box();
1980  lms.Add(ICOORD((box.left() + box.right()) / 2, box.bottom()));
1981  blobcount++;
1982  }
1983  }
1984  double error = lms.ConstrainedFit(gradient, &c);
1985  row->set_parallel_line(gradient, c, error);
1987  error = lms.Fit(&gradient, &c);
1988  }
1989  // set the other too
1990  row->set_line(gradient, c, error);
1991 }
1992 
1998 void Textord::make_spline_rows(TO_BLOCK *block, // block to do
1999  float gradient, // gradient to fit
2000  bool testing_on) {
2001 #ifndef GRAPHICS_DISABLED
2002  ScrollView::Color colour; // of row
2003 #endif
2004  TO_ROW_IT row_it = block->get_rows();
2005 
2006  row_it.move_to_first();
2007  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
2008  if (row_it.data()->blob_list()->empty()) {
2009  delete row_it.extract(); // nothing in it
2010  } else {
2011  make_baseline_spline(row_it.data(), block);
2012  }
2013  }
2014  if (textord_old_baselines) {
2015 #ifndef GRAPHICS_DISABLED
2016  if (testing_on) {
2017  colour = ScrollView::RED;
2018  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
2019  row_it.data()->baseline.plot(to_win, colour);
2020  colour = static_cast<ScrollView::Color>(colour + 1);
2021  if (colour > ScrollView::MAGENTA) {
2022  colour = ScrollView::RED;
2023  }
2024  }
2025  }
2026 #endif
2027  make_old_baselines(block, testing_on, gradient);
2028  }
2029 #ifndef GRAPHICS_DISABLED
2030  if (testing_on) {
2031  colour = ScrollView::RED;
2032  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
2033  row_it.data()->baseline.plot(to_win, colour);
2034  colour = static_cast<ScrollView::Color>(colour + 1);
2035  if (colour > ScrollView::MAGENTA) {
2036  colour = ScrollView::RED;
2037  }
2038  }
2039  }
2040 #endif
2041 }
2042 
2050 void make_baseline_spline(TO_ROW *row, // row to fit
2051  TO_BLOCK *block) {
2052  double *coeffs; // quadratic coeffs
2053  int32_t segments; // no of segments
2054 
2055  // spline boundaries
2056  auto *xstarts = new int32_t[row->blob_list()->length() + 1];
2057  if (segment_baseline(row, block, segments, xstarts) && !textord_straight_baselines &&
2059  coeffs = linear_spline_baseline(row, block, segments, xstarts);
2060  } else {
2061  xstarts[1] = xstarts[segments];
2062  segments = 1;
2063  coeffs = new double[3];
2064  coeffs[0] = 0;
2065  coeffs[1] = row->line_m();
2066  coeffs[2] = row->line_c();
2067  }
2068  row->baseline = QSPLINE(segments, xstarts, coeffs);
2069  delete[] coeffs;
2070  delete[] xstarts;
2071 }
2072 
2080 bool segment_baseline( // split baseline
2081  TO_ROW *row, // row to fit
2082  TO_BLOCK *block, // block it came from
2083  int32_t &segments, // no fo segments
2084  int32_t *xstarts // coords of segments
2085 ) {
2086  bool needs_curve; // needs curved line
2087  int blobcount; // no of blobs
2088  int blobindex; // current blob
2089  int last_state; // above, on , below
2090  int state; // of current blob
2091  float yshift; // from baseline
2092  TBOX box; // blob box
2093  TBOX new_box; // new_it box
2094  float middle; // xcentre of blob
2095  // blobs
2096  BLOBNBOX_IT blob_it = row->blob_list();
2097  BLOBNBOX_IT new_it = blob_it; // front end
2098  SORTED_FLOATS yshifts; // shifts from baseline
2099 
2100  needs_curve = false;
2101  box = box_next_pre_chopped(&blob_it);
2102  xstarts[0] = box.left();
2103  segments = 1;
2104  blobcount = row->blob_list()->length();
2105  if (textord_oldbl_debug) {
2106  tprintf("Segmenting baseline of %d blobs at (%d,%d)\n", blobcount, box.left(), box.bottom());
2107  }
2108  if (blobcount <= textord_spline_medianwin || blobcount < textord_spline_minblobs) {
2109  blob_it.move_to_last();
2110  box = blob_it.data()->bounding_box();
2111  xstarts[1] = box.right();
2112  return false;
2113  }
2114  last_state = 0;
2115  new_it.mark_cycle_pt();
2116  for (blobindex = 0; blobindex < textord_spline_medianwin; blobindex++) {
2117  new_box = box_next_pre_chopped(&new_it);
2118  middle = (new_box.left() + new_box.right()) / 2.0;
2119  yshift = new_box.bottom() - row->line_m() * middle - row->line_c();
2120  // record shift
2121  yshifts.add(yshift, blobindex);
2122  if (new_it.cycled_list()) {
2123  xstarts[1] = new_box.right();
2124  return false;
2125  }
2126  }
2127  for (blobcount = 0; blobcount < textord_spline_medianwin / 2; blobcount++) {
2128  box = box_next_pre_chopped(&blob_it);
2129  }
2130  do {
2131  new_box = box_next_pre_chopped(&new_it);
2132  // get middle one
2133  yshift = yshifts[textord_spline_medianwin / 2];
2134  if (yshift > textord_spline_shift_fraction * block->line_size) {
2135  state = 1;
2136  } else if (-yshift > textord_spline_shift_fraction * block->line_size) {
2137  state = -1;
2138  } else {
2139  state = 0;
2140  }
2141  if (state != 0) {
2142  needs_curve = true;
2143  }
2144  // tprintf("State=%d, prev=%d, shift=%g\n",
2145  // state,last_state,yshift);
2146  if (state != last_state && blobcount > textord_spline_minblobs) {
2147  xstarts[segments++] = box.left();
2148  blobcount = 0;
2149  }
2150  last_state = state;
2151  yshifts.remove(blobindex - textord_spline_medianwin);
2152  box = box_next_pre_chopped(&blob_it);
2153  middle = (new_box.left() + new_box.right()) / 2.0;
2154  yshift = new_box.bottom() - row->line_m() * middle - row->line_c();
2155  yshifts.add(yshift, blobindex);
2156  blobindex++;
2157  blobcount++;
2158  } while (!new_it.cycled_list());
2159  if (blobcount > textord_spline_minblobs || segments == 1) {
2160  xstarts[segments] = new_box.right();
2161  } else {
2162  xstarts[--segments] = new_box.right();
2163  }
2164  if (textord_oldbl_debug) {
2165  tprintf("Made %d segments on row at (%d,%d)\n", segments, box.right(), box.bottom());
2166  }
2167  return needs_curve;
2168 }
2169 
2177 double *linear_spline_baseline( // split baseline
2178  TO_ROW *row, // row to fit
2179  TO_BLOCK *block, // block it came from
2180  int32_t &segments, // no fo segments
2181  int32_t xstarts[] // coords of segments
2182 ) {
2183  int blobcount; // no of blobs
2184  int blobindex; // current blob
2185  int index1, index2; // blob numbers
2186  int blobs_per_segment; // blobs in each
2187  TBOX box; // blob box
2188  TBOX new_box; // new_it box
2189  // blobs
2190  BLOBNBOX_IT blob_it = row->blob_list();
2191  BLOBNBOX_IT new_it = blob_it; // front end
2192  float b, c; // fitted curve
2194  int32_t segment; // current segment
2195 
2196  box = box_next_pre_chopped(&blob_it);
2197  xstarts[0] = box.left();
2198  blobcount = 1;
2199  while (!blob_it.at_first()) {
2200  blobcount++;
2201  box = box_next_pre_chopped(&blob_it);
2202  }
2203  segments = blobcount / textord_spline_medianwin;
2204  if (segments < 1) {
2205  segments = 1;
2206  }
2207  blobs_per_segment = blobcount / segments;
2208  // quadratic coeffs
2209  auto *coeffs = new double[segments * 3];
2210  if (textord_oldbl_debug) {
2211  tprintf(
2212  "Linear splining baseline of %d blobs at (%d,%d), into %d segments of "
2213  "%d blobs\n",
2214  blobcount, box.left(), box.bottom(), segments, blobs_per_segment);
2215  }
2216  segment = 1;
2217  for (index2 = 0; index2 < blobs_per_segment / 2; index2++) {
2218  box_next_pre_chopped(&new_it);
2219  }
2220  index1 = 0;
2221  blobindex = index2;
2222  do {
2223  blobindex += blobs_per_segment;
2224  lms.Clear();
2225  while (index1 < blobindex || (segment == segments && index1 < blobcount)) {
2226  box = box_next_pre_chopped(&blob_it);
2227  int middle = (box.left() + box.right()) / 2;
2228  lms.Add(ICOORD(middle, box.bottom()));
2229  index1++;
2230  if (index1 == blobindex - blobs_per_segment / 2 || index1 == blobcount - 1) {
2231  xstarts[segment] = box.left();
2232  }
2233  }
2234  lms.Fit(&b, &c);
2235  coeffs[segment * 3 - 3] = 0;
2236  coeffs[segment * 3 - 2] = b;
2237  coeffs[segment * 3 - 1] = c;
2238  segment++;
2239  if (segment > segments) {
2240  break;
2241  }
2242 
2243  blobindex += blobs_per_segment;
2244  lms.Clear();
2245  while (index2 < blobindex || (segment == segments && index2 < blobcount)) {
2246  new_box = box_next_pre_chopped(&new_it);
2247  int middle = (new_box.left() + new_box.right()) / 2;
2248  lms.Add(ICOORD(middle, new_box.bottom()));
2249  index2++;
2250  if (index2 == blobindex - blobs_per_segment / 2 || index2 == blobcount - 1) {
2251  xstarts[segment] = new_box.left();
2252  }
2253  }
2254  lms.Fit(&b, &c);
2255  coeffs[segment * 3 - 3] = 0;
2256  coeffs[segment * 3 - 2] = b;
2257  coeffs[segment * 3 - 1] = c;
2258  segment++;
2259  } while (segment <= segments);
2260  return coeffs;
2261 }
2262 
2269 void assign_blobs_to_rows( // find lines
2270  TO_BLOCK *block, // block to do
2271  float *gradient, // block skew
2272  int pass, // identification
2273  bool reject_misses, // chuck big ones out
2274  bool make_new_rows, // add rows for unmatched
2275  bool drawing_skew // draw smoothed skew
2276 ) {
2277  OVERLAP_STATE overlap_result; // what to do with it
2278  float ycoord; // current y
2279  float top, bottom; // of blob
2280  float g_length = 1.0f; // from gradient
2281  int16_t row_count; // no of rows
2282  int16_t left_x; // left edge
2283  int16_t last_x; // previous edge
2284  float block_skew; // y delta
2285  float smooth_factor; // for new coords
2286  float near_dist; // dist to nearest row
2287  ICOORD testpt; // testing only
2288  BLOBNBOX *blob; // current blob
2289  TO_ROW *row; // current row
2290  TO_ROW *dest_row = nullptr; // row to put blob in
2291  // iterators
2292  BLOBNBOX_IT blob_it = &block->blobs;
2293  TO_ROW_IT row_it = block->get_rows();
2294 
2295  ycoord =
2296  (block->block->pdblk.bounding_box().bottom() + block->block->pdblk.bounding_box().top()) /
2297  2.0f;
2298  if (gradient != nullptr) {
2299  g_length = std::sqrt(1 + *gradient * *gradient);
2300  }
2301 #ifndef GRAPHICS_DISABLED
2302  if (drawing_skew) {
2303  to_win->SetCursor(block->block->pdblk.bounding_box().left(), ycoord);
2304  }
2305 #endif
2307  blob_it.sort(blob_x_order);
2308  smooth_factor = 1.0;
2309  block_skew = 0.0f;
2310  row_count = row_it.length(); // might have rows
2311  if (!blob_it.empty()) {
2312  left_x = blob_it.data()->bounding_box().left();
2313  } else {
2314  left_x = block->block->pdblk.bounding_box().left();
2315  }
2316  last_x = left_x;
2317  for (blob_it.mark_cycle_pt(); !blob_it.cycled_list(); blob_it.forward()) {
2318  blob = blob_it.data();
2319  if (gradient != nullptr) {
2320  block_skew = (1 - 1 / g_length) * blob->bounding_box().bottom() +
2321  *gradient / g_length * blob->bounding_box().left();
2322  } else if (blob->bounding_box().left() - last_x > block->line_size / 2 &&
2323  last_x - left_x > block->line_size * 2 && textord_interpolating_skew) {
2324  // tprintf("Interpolating skew from %g",block_skew);
2325  block_skew *= static_cast<float>(blob->bounding_box().left() - left_x) / (last_x - left_x);
2326  // tprintf("to %g\n",block_skew);
2327  }
2328  last_x = blob->bounding_box().left();
2329  top = blob->bounding_box().top() - block_skew;
2330  bottom = blob->bounding_box().bottom() - block_skew;
2331 #ifndef GRAPHICS_DISABLED
2332  if (drawing_skew) {
2333  to_win->DrawTo(blob->bounding_box().left(), ycoord + block_skew);
2334  }
2335 #endif
2336  if (!row_it.empty()) {
2337  for (row_it.move_to_first(); !row_it.at_last() && row_it.data()->min_y() > top;
2338  row_it.forward()) {
2339  ;
2340  }
2341  row = row_it.data();
2342  if (row->min_y() <= top && row->max_y() >= bottom) {
2343  // any overlap
2344  dest_row = row;
2345  overlap_result = most_overlapping_row(&row_it, dest_row, top, bottom, block->line_size,
2346  blob->bounding_box().contains(testpt));
2347  if (overlap_result == NEW_ROW && !reject_misses) {
2348  overlap_result = ASSIGN;
2349  }
2350  } else {
2351  overlap_result = NEW_ROW;
2352  if (!make_new_rows) {
2353  near_dist = row_it.data_relative(-1)->min_y() - top;
2354  // below bottom
2355  if (bottom < row->min_y()) {
2356  if (row->min_y() - bottom <= (block->line_spacing - block->line_size) *
2358  // done it
2359  overlap_result = ASSIGN;
2360  dest_row = row;
2361  }
2362  } else if (near_dist > 0 && near_dist < bottom - row->max_y()) {
2363  row_it.backward();
2364  dest_row = row_it.data();
2365  if (dest_row->min_y() - bottom <= (block->line_spacing - block->line_size) *
2367  // done it
2368  overlap_result = ASSIGN;
2369  }
2370  } else {
2371  if (top - row->max_y() <=
2372  (block->line_spacing - block->line_size) *
2373  (textord_overlap_x + tesseract::CCStruct::kAscenderFraction)) {
2374  // done it
2375  overlap_result = ASSIGN;
2376  dest_row = row;
2377  }
2378  }
2379  }
2380  }
2381  if (overlap_result == ASSIGN) {
2382  dest_row->add_blob(blob_it.extract(), top, bottom, block->line_size);
2383  }
2384  if (overlap_result == NEW_ROW) {
2385  if (make_new_rows && top - bottom < block->max_blob_size) {
2386  dest_row = new TO_ROW(blob_it.extract(), top, bottom, block->line_size);
2387  row_count++;
2388  if (bottom > row_it.data()->min_y()) {
2389  row_it.add_before_then_move(dest_row);
2390  // insert in right place
2391  } else {
2392  row_it.add_after_then_move(dest_row);
2393  }
2394  smooth_factor = 1.0 / (row_count * textord_skew_lag + textord_skewsmooth_offset);
2395  } else {
2396  overlap_result = REJECT;
2397  }
2398  }
2399  } else if (make_new_rows && top - bottom < block->max_blob_size) {
2400  overlap_result = NEW_ROW;
2401  dest_row = new TO_ROW(blob_it.extract(), top, bottom, block->line_size);
2402  row_count++;
2403  row_it.add_after_then_move(dest_row);
2404  smooth_factor = 1.0 / (row_count * textord_skew_lag + textord_skewsmooth_offset2);
2405  } else {
2406  overlap_result = REJECT;
2407  }
2408  if (blob->bounding_box().contains(testpt) && textord_debug_blob) {
2409  if (overlap_result != REJECT) {
2410  tprintf("Test blob assigned to row at (%g,%g) on pass %d\n", dest_row->min_y(),
2411  dest_row->max_y(), pass);
2412  } else {
2413  tprintf("Test blob assigned to no row on pass %d\n", pass);
2414  }
2415  }
2416  if (overlap_result != REJECT) {
2417  while (!row_it.at_first() && row_it.data()->min_y() > row_it.data_relative(-1)->min_y()) {
2418  row = row_it.extract();
2419  row_it.backward();
2420  row_it.add_before_then_move(row);
2421  }
2422  while (!row_it.at_last() && row_it.data()->min_y() < row_it.data_relative(1)->min_y()) {
2423  row = row_it.extract();
2424  row_it.forward();
2425  // Keep rows in order.
2426  row_it.add_after_then_move(row);
2427  }
2428  BLOBNBOX_IT added_blob_it(dest_row->blob_list());
2429  added_blob_it.move_to_last();
2430  TBOX prev_box = added_blob_it.data_relative(-1)->bounding_box();
2431  if (dest_row->blob_list()->singleton() || !prev_box.major_x_overlap(blob->bounding_box())) {
2432  block_skew = (1 - smooth_factor) * block_skew +
2433  smooth_factor * (blob->bounding_box().bottom() - dest_row->initial_min_y());
2434  }
2435  }
2436  }
2437  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
2438  if (row_it.data()->blob_list()->empty()) {
2439  delete row_it.extract(); // Discard empty rows.
2440  }
2441  }
2442 }
2443 
2450  TO_ROW_IT *row_it, // iterator
2451  TO_ROW *&best_row, // output row
2452  float top, // top of blob
2453  float bottom, // bottom of blob
2454  float rowsize, // max row size
2455  bool testing_blob // test stuff
2456 ) {
2457  OVERLAP_STATE result; // result of tests
2458  float overlap; // of blob & row
2459  float bestover; // nearest row
2460  float merge_top, merge_bottom; // size of merged row
2461  ICOORD testpt; // testing only
2462  TO_ROW *row; // current row
2463  TO_ROW *test_row; // for multiple overlaps
2464  BLOBNBOX_IT blob_it; // for merging rows
2465 
2466  result = ASSIGN;
2467  row = row_it->data();
2468  bestover = top - bottom;
2469  if (top > row->max_y()) {
2470  bestover -= top - row->max_y();
2471  }
2472  if (bottom < row->min_y()) {
2473  // compute overlap
2474  bestover -= row->min_y() - bottom;
2475  }
2476  if (testing_blob && textord_debug_blob) {
2477  tprintf("Test blob y=(%g,%g), row=(%f,%f), size=%g, overlap=%f\n", bottom, top, row->min_y(),
2478  row->max_y(), rowsize, bestover);
2479  }
2480  test_row = row;
2481  do {
2482  if (!row_it->at_last()) {
2483  row_it->forward();
2484  test_row = row_it->data();
2485  if (test_row->min_y() <= top && test_row->max_y() >= bottom) {
2486  merge_top = test_row->max_y() > row->max_y() ? test_row->max_y() : row->max_y();
2487  merge_bottom = test_row->min_y() < row->min_y() ? test_row->min_y() : row->min_y();
2488  if (merge_top - merge_bottom <= rowsize) {
2489  if (testing_blob && textord_debug_blob) {
2490  tprintf("Merging rows at (%g,%g), (%g,%g)\n", row->min_y(), row->max_y(),
2491  test_row->min_y(), test_row->max_y());
2492  }
2493  test_row->set_limits(merge_bottom, merge_top);
2494  blob_it.set_to_list(test_row->blob_list());
2495  blob_it.add_list_after(row->blob_list());
2496  blob_it.sort(blob_x_order);
2497  row_it->backward();
2498  delete row_it->extract();
2499  row_it->forward();
2500  bestover = -1.0f; // force replacement
2501  }
2502  overlap = top - bottom;
2503  if (top > test_row->max_y()) {
2504  overlap -= top - test_row->max_y();
2505  }
2506  if (bottom < test_row->min_y()) {
2507  overlap -= test_row->min_y() - bottom;
2508  }
2509  if (bestover >= rowsize - 1 && overlap >= rowsize - 1) {
2510  result = REJECT;
2511  }
2512  if (overlap > bestover) {
2513  bestover = overlap; // find biggest overlap
2514  row = test_row;
2515  }
2516  if (testing_blob && textord_debug_blob) {
2517  tprintf("Test blob y=(%g,%g), row=(%f,%f), size=%g, overlap=%f->%f\n", bottom, top,
2518  test_row->min_y(), test_row->max_y(), rowsize, overlap, bestover);
2519  }
2520  }
2521  }
2522  } while (!row_it->at_last() && test_row->min_y() <= top && test_row->max_y() >= bottom);
2523  while (row_it->data() != row) {
2524  row_it->backward(); // make it point to row
2525  }
2526  // doesn't overlap much
2527  if (top - bottom - bestover > rowsize * textord_overlap_x &&
2528  (!textord_fix_makerow_bug || bestover < rowsize * textord_overlap_x) && result == ASSIGN) {
2529  result = NEW_ROW; // doesn't overlap enough
2530  }
2531  best_row = row;
2532  return result;
2533 }
2534 
2540 int blob_x_order( // sort function
2541  const void *item1, // items to compare
2542  const void *item2) {
2543  // converted ptr
2544  const BLOBNBOX *blob1 = *reinterpret_cast<const BLOBNBOX *const *>(item1);
2545  // converted ptr
2546  const BLOBNBOX *blob2 = *reinterpret_cast<const BLOBNBOX *const *>(item2);
2547 
2548  if (blob1->bounding_box().left() < blob2->bounding_box().left()) {
2549  return -1;
2550  } else if (blob1->bounding_box().left() > blob2->bounding_box().left()) {
2551  return 1;
2552  } else {
2553  return 0;
2554  }
2555 }
2556 
2564  BLOBNBOX_IT box_it(row->blob_list()); // Iterator.
2565  int num_repeated_sets = 0;
2566  if (!box_it.empty()) {
2567  do {
2568  BLOBNBOX *bblob = box_it.data();
2569  int repeat_length = 1;
2570  if (bblob->flow() == BTFT_LEADER && !bblob->joined_to_prev() && bblob->cblob() != nullptr) {
2571  BLOBNBOX_IT test_it(box_it);
2572  for (test_it.forward(); !test_it.at_first();) {
2573  bblob = test_it.data();
2574  if (bblob->flow() != BTFT_LEADER) {
2575  break;
2576  }
2577  test_it.forward();
2578  bblob = test_it.data();
2579  if (bblob->joined_to_prev() || bblob->cblob() == nullptr) {
2580  repeat_length = 0;
2581  break;
2582  }
2583  ++repeat_length;
2584  }
2585  }
2586  if (repeat_length >= kMinLeaderCount) {
2587  num_repeated_sets++;
2588  for (; repeat_length > 0; box_it.forward(), --repeat_length) {
2589  bblob = box_it.data();
2590  bblob->set_repeated_set(num_repeated_sets);
2591  }
2592  } else {
2593  bblob->set_repeated_set(0);
2594  box_it.forward();
2595  }
2596  } while (!box_it.at_first()); // until all done
2597  }
2598  row->set_num_repeated_sets(num_repeated_sets);
2599 }
2600 
2601 } // namespace tesseract
#define ASSERT_HOST(x)
Definition: errcode.h:59
#define BOOL_VAR(name, val, comment)
Definition: params.h:359
#define INT_VAR(name, val, comment)
Definition: params.h:356
#define double_VAR(name, val, comment)
Definition: params.h:365
#define MAX_HEIGHT_MODES
Definition: makerow.cpp:98
@ TBOX
UnicodeText::const_iterator::difference_type distance(const UnicodeText::const_iterator &first, const UnicodeText::const_iterator &last)
Definition: unicodetext.cc:44
bool textord_old_baselines
Definition: makerow.cpp:55
C_BLOB * crotate_cblob(C_BLOB *blob, FCOORD rotation)
Definition: blobbox.cpp:614
void expand_rows(ICOORD page_tr, TO_BLOCK *block, float gradient, FCOORD rotation, int32_t block_edge, bool testing_on)
Definition: makerow.cpp:976
bool textord_show_final_rows
Definition: makerow.cpp:50
void delete_non_dropout_rows(TO_BLOCK *block, float gradient, FCOORD rotation, int32_t block_edge, bool testing_on)
Definition: makerow.cpp:612
void get_min_max_xheight(int block_linesize, int *min_height, int *max_height)
Definition: makerow.h:86
double textord_xheight_error_margin
Definition: makerow.cpp:93
void make_baseline_spline(TO_ROW *row, TO_BLOCK *block)
Definition: makerow.cpp:2050
void fit_parallel_lms(float gradient, TO_ROW *row)
Definition: makerow.cpp:1970
double textord_minxh
Definition: makerow.cpp:79
int textord_spline_minblobs
Definition: makerow.cpp:67
void pre_associate_blobs(ICOORD page_tr, TO_BLOCK *block, FCOORD rotation, bool testing_on)
Definition: makerow.cpp:1846
void cleanup_rows_making(ICOORD page_tr, TO_BLOCK *block, float gradient, FCOORD rotation, int32_t block_edge, bool testing_on)
Definition: makerow.cpp:563
void compute_row_stats(TO_BLOCK *block, bool testing_on)
Definition: makerow.cpp:1163
int32_t compute_height_modes(STATS *heights, int32_t min_height, int32_t max_height, int32_t *modes, int32_t maxmodes)
Definition: makerow.cpp:1629
int textord_min_xheight
Definition: makerow.cpp:70
double textord_chop_width
Definition: makerow.cpp:76
bool textord_show_initial_rows
Definition: makerow.cpp:47
bool textord_show_expanded_rows
Definition: makerow.cpp:49
int textord_test_y
Definition: makerow.cpp:65
double textord_ascheight_mode_fraction
Definition: makerow.cpp:87
int textord_test_x
Definition: makerow.cpp:64
double textord_spline_shift_fraction
Definition: makerow.cpp:71
double textord_descx_ratio_min
Definition: makerow.cpp:91
void tprintf(const char *format,...)
Definition: tprintf.cpp:41
ROW_CATEGORY
Definition: makerow.h:36
@ ROW_ASCENDERS_FOUND
Definition: makerow.h:37
@ ROW_DESCENDERS_FOUND
Definition: makerow.h:38
@ ROW_INVALID
Definition: makerow.h:40
@ ROW_UNKNOWN
Definition: makerow.h:39
bool textord_debug_xheights
Definition: makerow.cpp:59
void adjust_row_limits(TO_BLOCK *block)
Definition: makerow.cpp:1129
int textord_spline_medianwin
Definition: makerow.cpp:68
double textord_skew_lag
Definition: makerow.cpp:73
double textord_excess_blobsize
Definition: makerow.cpp:81
void mark_repeated_chars(TO_ROW *row)
Definition: makerow.cpp:2563
ScrollView * to_win
Definition: drawtord.cpp:37
bool test_underline(bool testing_on, C_BLOB *blob, int16_t baseline, int16_t xheight)
Definition: blkocc.cpp:47
void assign_blobs_to_rows(TO_BLOCK *block, float *gradient, int pass, bool reject_misses, bool make_new_rows, bool drawing_skew)
Definition: makerow.cpp:2269
void fill_heights(TO_ROW *row, float gradient, int min_height, int max_height, STATS *heights, STATS *floating_heights)
Definition: makerow.cpp:1418
bool textord_parallel_baselines
Definition: makerow.cpp:53
void make_initial_textrows(ICOORD page_tr, TO_BLOCK *block, FCOORD rotation, bool testing_on)
Definition: makerow.cpp:254
void fit_lms_line(TO_ROW *row)
Definition: makerow.cpp:296
double textord_min_blob_height_fraction
Definition: makerow.cpp:85
bool textord_show_parallel_rows
Definition: makerow.cpp:48
bool textord_fix_makerow_bug
Definition: makerow.cpp:58
void vigorous_noise_removal(TO_BLOCK *block)
Definition: makerow.cpp:508
void compute_page_skew(TO_BLOCK_LIST *blocks, float &page_m, float &page_err)
Definition: makerow.cpp:315
double textord_occupancy_threshold
Definition: makerow.cpp:82
double textord_underline_width
Definition: makerow.cpp:83
double textord_skew_ile
Definition: makerow.cpp:72
double * linear_spline_baseline(TO_ROW *row, TO_BLOCK *block, int32_t &segments, int32_t xstarts[])
Definition: makerow.cpp:2177
int textord_lms_line_trials
Definition: makerow.cpp:94
double textord_ascx_ratio_max
Definition: makerow.cpp:90
bool within_error_margin(float test, float num, float margin)
Definition: makerow.h:102
double textord_ascx_ratio_min
Definition: makerow.cpp:89
TBOX deskew_block_coords(TO_BLOCK *block, float gradient)
Definition: makerow.cpp:765
void plot_to_row(TO_ROW *row, ScrollView::Color colour, FCOORD rotation)
Definition: drawtord.cpp:89
float make_rows(ICOORD page_tr, TO_BLOCK_LIST *port_blocks)
Definition: makerow.cpp:229
bool textord_oldbl_debug
Definition: oldbasel.cpp:43
void plot_parallel_row(TO_ROW *row, float gradient, int32_t left, ScrollView::Color colour, FCOORD rotation)
Definition: drawtord.cpp:122
bool textord_heavy_nr
Definition: makerow.cpp:46
const int kMinLeaderCount
const double kNoiseSize
Definition: makerow.cpp:407
const int kMinSize
Definition: makerow.cpp:408
@ BTFT_LEADER
Definition: blobbox.h:117
bool textord_test_landscape
Definition: makerow.cpp:52
bool textord_new_initial_xheight
Definition: makerow.cpp:95
void separate_underlines(TO_BLOCK *block, float gradient, FCOORD rotation, bool testing_on)
Definition: makerow.cpp:1781
void fit_parallel_rows(TO_BLOCK *block, float gradient, FCOORD rotation, int32_t block_edge, bool testing_on)
Definition: makerow.cpp:1928
OVERLAP_STATE
Definition: makerow.h:30
@ ASSIGN
Definition: makerow.h:31
@ NEW_ROW
Definition: makerow.h:33
@ REJECT
Definition: makerow.h:32
double textord_linespace_iqrlimit
Definition: makerow.cpp:74
int compute_xheight_from_modes(STATS *heights, STATS *floating_heights, bool cap_only, int min_height, int max_height, float *xheight, float *ascrise)
Definition: makerow.cpp:1480
double textord_min_linesize
Definition: makerow.cpp:80
ScrollView * create_to_win(ICOORD page_tr)
Definition: drawtord.cpp:47
void correct_row_xheight(TO_ROW *row, float xheight, float ascrise, float descdrop)
Definition: makerow.cpp:1690
int textord_min_blobs_in_row
Definition: makerow.cpp:66
OVERLAP_STATE most_overlapping_row(TO_ROW_IT *row_it, TO_ROW *&best_row, float top, float bottom, float rowsize, bool testing_blob)
Definition: makerow.cpp:2449
double textord_width_limit
Definition: makerow.cpp:75
int32_t compute_row_descdrop(TO_ROW *row, float gradient, int xheight_blob_count, STATS *asc_heights)
Definition: makerow.cpp:1576
double textord_xheight_mode_fraction
Definition: makerow.cpp:86
bool textord_fix_xheight_bug
Definition: makerow.cpp:57
ROW_CATEGORY get_row_category(const TO_ROW *row)
Definition: makerow.h:94
int blob_x_order(const void *item1, const void *item2)
Definition: makerow.cpp:2540
bool textord_debug_blob
Definition: makerow.cpp:96
void compute_occupation_threshold(int32_t low_window, int32_t high_window, int32_t line_count, int32_t *occupation, int32_t *thresholds)
Definition: makerow.cpp:852
TBOX box_next_pre_chopped(BLOBNBOX_IT *it)
Definition: blobbox.cpp:667
bool textord_show_final_blobs
Definition: makerow.cpp:51
float make_single_row(ICOORD page_tr, bool allow_sub_blobs, TO_BLOCK *block, TO_BLOCK_LIST *blocks)
Definition: makerow.cpp:190
void compute_dropout_distances(int32_t *occupation, int32_t *thresholds, int32_t line_count)
Definition: makerow.cpp:933
bool textord_straight_baselines
Definition: makerow.cpp:54
void compute_line_occupation(TO_BLOCK *block, float gradient, int32_t min_y, int32_t max_y, int32_t *occupation, int32_t *deltas)
Definition: makerow.cpp:799
bool segment_baseline(TO_ROW *row, TO_BLOCK *block, int32_t &segments, int32_t *xstarts)
Definition: makerow.cpp:2080
double textord_descx_ratio_max
Definition: makerow.cpp:92
bool find_best_dropout_row(TO_ROW *row, int32_t distance, float dist_limit, int32_t line_index, TO_ROW_IT *row_it, bool testing_on)
Definition: makerow.cpp:696
bool textord_old_xheight
Definition: makerow.cpp:56
void draw_occupation(int32_t xleft, int32_t ybottom, int32_t min_y, int32_t max_y, int32_t occupation[], int32_t thresholds[])
Definition: drawtord.cpp:161
int repeated_set() const
Definition: blobbox.h:271
const TBOX & bounding_box() const
Definition: blobbox.h:239
void set_repeated_set(int set_id)
Definition: blobbox.h:274
void merge(BLOBNBOX *nextblob)
Definition: blobbox.cpp:92
C_BLOB * cblob() const
Definition: blobbox.h:277
BlobTextFlowType flow() const
Definition: blobbox.h:310
void chop(BLOBNBOX_IT *start_it, BLOBNBOX_IT *blob_it, FCOORD rotation, float xheight)
Definition: blobbox.cpp:118
bool joined_to_prev() const
Definition: blobbox.h:265
float max_y() const
Definition: blobbox.h:568
bool rep_chars_marked() const
Definition: blobbox.h:637
int xheight_evidence
Definition: blobbox.h:664
QSPLINE baseline
Definition: blobbox.h:676
void add_blob(BLOBNBOX *blob, float top, float bottom, float row_size)
Definition: blobbox.cpp:734
float believability() const
Definition: blobbox.h:595
void set_num_repeated_sets(int num_sets)
Definition: blobbox.h:646
float initial_min_y() const
Definition: blobbox.h:577
float line_error() const
Definition: blobbox.h:586
void set_line(float new_m, float new_c, float new_error)
Definition: blobbox.h:612
int num_repeated_sets() const
Definition: blobbox.h:643
float min_y() const
Definition: blobbox.h:571
void set_limits(float new_min, float new_max)
Definition: blobbox.h:628
float line_m() const
Definition: blobbox.h:580
float intercept() const
Definition: blobbox.h:598
float parallel_c() const
Definition: blobbox.h:589
BLOBNBOX_LIST * blob_list()
Definition: blobbox.h:608
void set_parallel_line(float gradient, float new_c, float new_error)
Definition: blobbox.h:619
float line_c() const
Definition: blobbox.h:583
BLOBNBOX_LIST underlines
Definition: blobbox.h:777
float baseline_offset
Definition: blobbox.h:791
BLOBNBOX_LIST blobs
Definition: blobbox.h:776
TO_ROW * key_row
Definition: blobbox.h:802
BLOBNBOX_LIST small_blobs
Definition: blobbox.h:779
TO_ROW_LIST * get_rows()
Definition: blobbox.h:709
BLOBNBOX_LIST large_blobs
Definition: blobbox.h:780
BLOBNBOX_LIST noise_blobs
Definition: blobbox.h:778
static const double kXHeightCapRatio
Definition: ccstruct.h:37
static const double kXHeightFraction
Definition: ccstruct.h:34
static const double kDescenderFraction
Definition: ccstruct.h:33
static const double kAscenderFraction
Definition: ccstruct.h:35
int32_t pathlength() const
Definition: coutln.h:134
ICOORD step(int index) const
Definition: coutln.h:143
const ICOORD & start_pos() const
Definition: coutln.h:147
static C_OUTLINE * deep_copy(const C_OUTLINE *src)
Definition: coutln.h:261
void Add(const ICOORD &pt)
Definition: detlinefit.cpp:50
double ConstrainedFit(const FCOORD &direction, double min_dist, double max_dist, bool debug, ICOORD *line_pt)
Definition: detlinefit.cpp:133
double Fit(ICOORD *pt1, ICOORD *pt2)
Definition: detlinefit.h:73
FCOORD classify_rotation() const
Definition: ocrblock.h:135
PDBLK pdblk
Page Description Block.
Definition: ocrblock.h:185
void bounding_box(ICOORD &bottom_left, ICOORD &top_right) const
get box
Definition: pdblock.h:67
integer coordinate
Definition: points.h:36
TDimension y() const
access_function
Definition: points.h:62
TDimension x() const
access function
Definition: points.h:58
void rotate(const FCOORD vec)
Definition: points.h:712
float y() const
Definition: points.h:209
float x() const
Definition: points.h:206
bool IsText() const
Definition: polyblk.h:52
double y(double x) const
Definition: quspline.cpp:203
TDimension left() const
Definition: rect.h:82
TDimension height() const
Definition: rect.h:118
TDimension width() const
Definition: rect.h:126
void rotate(const FCOORD &vec)
Definition: rect.h:210
TDimension top() const
Definition: rect.h:68
bool major_x_overlap(const TBOX &box) const
Definition: rect.h:419
void print() const
Definition: rect.h:289
TDimension right() const
Definition: rect.h:89
TDimension bottom() const
Definition: rect.h:75
bool contains(const FCOORD pt) const
Definition: rect.h:344
void print() const
Definition: statistc.cpp:548
void add(int32_t value, int32_t count)
Definition: statistc.cpp:99
int32_t pile_count(int32_t value) const
Definition: statistc.h:75
int32_t get_total() const
Definition: statistc.h:85
double median() const
Definition: statistc.cpp:242
int32_t min_bucket() const
Definition: statistc.cpp:205
int32_t mode() const
Definition: statistc.cpp:113
int32_t max_bucket() const
Definition: statistc.cpp:222
static C_BLOB * FakeBlob(const TBOX &box)
Definition: stepblob.cpp:238
TBOX bounding_box() const
Definition: stepblob.cpp:250
C_OUTLINE_LIST * out_list()
Definition: stepblob.h:70
void remove(int32_t key)
Definition: sortflts.cpp:53
void add(float value, int32_t key)
Definition: sortflts.cpp:28
void compute_row_xheight(TO_ROW *row, const FCOORD &rotation, float gradient, int block_line_size)
Definition: makerow.cpp:1384
void make_spline_rows(TO_BLOCK *block, float gradient, bool testing_on)
Definition: makerow.cpp:1998
void compute_block_xheight(TO_BLOCK *block, float gradient)
Definition: makerow.cpp:1278
void Pen(Color color)
Definition: scrollview.cpp:723
void Rectangle(int x1, int y1, int x2, int y2)
Definition: scrollview.cpp:589
void SetCursor(int x, int y)
Definition: scrollview.cpp:498
void DrawTo(int x, int y)
Definition: scrollview.cpp:504