tesseract  5.0.0
oldbasel.cpp
Go to the documentation of this file.
1 /**********************************************************************
2  * File: oldbasel.cpp (Formerly oldbl.c)
3  * Description: A re-implementation of the old baseline algorithm.
4  * Author: Ray Smith
5  *
6  * (C) Copyright 1993, 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 "oldbasel.h"
25 
26 #include "ccstruct.h"
27 #include "detlinefit.h"
28 #include "drawtord.h"
29 #include "makerow.h"
30 #include "quadlsq.h"
31 #include "statistc.h"
32 #include "textord.h"
33 #include "tprintf.h"
34 
35 #include <cmath>
36 #include <vector> // for std::vector
37 
38 #include <algorithm>
39 
40 namespace tesseract {
41 
42 static BOOL_VAR(textord_really_old_xheight, false, "Use original wiseowl xheight");
43 BOOL_VAR(textord_oldbl_debug, false, "Debug old baseline generation");
44 static BOOL_VAR(textord_debug_baselines, false, "Debug baseline generation");
45 static BOOL_VAR(textord_oldbl_paradef, true, "Use para default mechanism");
46 static BOOL_VAR(textord_oldbl_split_splines, true, "Split stepped splines");
47 static BOOL_VAR(textord_oldbl_merge_parts, true, "Merge suspect partitions");
48 static BOOL_VAR(oldbl_corrfix, true, "Improve correlation of heights");
49 static BOOL_VAR(oldbl_xhfix, false, "Fix bug in modes threshold for xheights");
50 static BOOL_VAR(textord_ocropus_mode, false, "Make baselines for ocropus");
51 static double_VAR(oldbl_xhfract, 0.4, "Fraction of est allowed in calc");
52 static INT_VAR(oldbl_holed_losscount, 10, "Max lost before fallback line used");
53 static double_VAR(oldbl_dot_error_size, 1.26, "Max aspect ratio of a dot");
54 static double_VAR(textord_oldbl_jumplimit, 0.15, "X fraction for new partition");
55 
56 #define TURNLIMIT 1 /*min size for turning point */
57 #define X_HEIGHT_FRACTION 0.7 /*x-height/caps height */
58 #define DESCENDER_FRACTION 0.5 /*descender/x-height */
59 #define MIN_ASC_FRACTION 0.20 /*min size of ascenders */
60 #define MIN_DESC_FRACTION 0.25 /*min size of descenders */
61 #define MINASCRISE 2.0 /*min ascender/desc step */
62 #define MAXHEIGHTVARIANCE 0.15 /*accepted variation in x-height */
63 #define MAXHEIGHT 300 /*max blob height */
64 #define MAXOVERLAP 0.1 /*max 10% missed overlap */
65 #define MAXBADRUN 2 /*max non best for failed */
66 #define HEIGHTBUCKETS 200 /* Num of buckets */
67 #define MODENUM 10
68 #define MAXPARTS 6
69 #define SPLINESIZE 23
70 
71 #define ABS(x) ((x) < 0 ? (-(x)) : (x))
72 
73 /**********************************************************************
74  * make_old_baselines
75  *
76  * Top level function to make baselines the old way.
77  **********************************************************************/
78 
79 void Textord::make_old_baselines(TO_BLOCK *block, // block to do
80  bool testing_on, // correct orientation
81  float gradient) {
82  QSPLINE *prev_baseline; // baseline of previous row
83  TO_ROW *row; // current row
84  TO_ROW_IT row_it = block->get_rows();
85  BLOBNBOX_IT blob_it;
86 
87  prev_baseline = nullptr; // nothing yet
88  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
89  row = row_it.data();
90  find_textlines(block, row, 2, nullptr);
91  if (row->xheight <= 0 && prev_baseline != nullptr) {
92  find_textlines(block, row, 2, prev_baseline);
93  }
94  if (row->xheight > 0) { // was a good one
95  prev_baseline = &row->baseline;
96  } else {
97  prev_baseline = nullptr;
98  blob_it.set_to_list(row->blob_list());
99  if (textord_debug_baselines) {
100  tprintf("Row baseline generation failed on row at (%d,%d)\n",
101  blob_it.data()->bounding_box().left(), blob_it.data()->bounding_box().bottom());
102  }
103  }
104  }
105  correlate_lines(block, gradient);
106  block->block->set_xheight(block->xheight);
107 }
108 
109 /**********************************************************************
110  * correlate_lines
111  *
112  * Correlate the x-heights and ascender heights of a block to fill-in
113  * the ascender height and descender height for rows without one.
114  * Also fix baselines of rows without a decent fit.
115  **********************************************************************/
116 
117 void Textord::correlate_lines(TO_BLOCK *block, float gradient) {
118  int rowcount; /*no of rows to do */
119  int rowindex; /*no of row */
120  // iterator
121  TO_ROW_IT row_it = block->get_rows();
122 
123  rowcount = row_it.length();
124  if (rowcount == 0) {
125  // default value
126  block->xheight = block->line_size;
127  return; /*none to do */
128  }
129  // array of ptrs
130  std::vector<TO_ROW *> rows(rowcount);
131  rowindex = 0;
132  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
133  // make array
134  rows[rowindex++] = row_it.data();
135  }
136 
137  /*try to fix bad lines */
138  correlate_neighbours(block, &rows[0], rowcount);
139 
140  if (textord_really_old_xheight || textord_old_xheight) {
141  block->xheight = static_cast<float>(correlate_with_stats(&rows[0], rowcount, block));
142  if (block->xheight <= 0) {
143  block->xheight = block->line_size * tesseract::CCStruct::kXHeightFraction;
144  }
145  if (block->xheight < textord_min_xheight) {
146  block->xheight = (float)textord_min_xheight;
147  }
148  } else {
149  compute_block_xheight(block, gradient);
150  }
151 }
152 
153 /**********************************************************************
154  * correlate_neighbours
155  *
156  * Try to fix rows that had a bad spline fit by using neighbours.
157  **********************************************************************/
158 
159 void Textord::correlate_neighbours(TO_BLOCK *block, // block rows are in.
160  TO_ROW **rows, // rows of block.
161  int rowcount) { // no of rows to do.
162  TO_ROW *row; /*current row */
163  int rowindex; /*no of row */
164  int otherrow; /*second row */
165  int upperrow; /*row above to use */
166  int lowerrow; /*row below to use */
167  float biggest;
168 
169  for (rowindex = 0; rowindex < rowcount; rowindex++) {
170  row = rows[rowindex]; /*current row */
171  if (row->xheight < 0) {
172  /*quadratic failed */
173  for (otherrow = rowindex - 2;
174  otherrow >= 0 && (rows[otherrow]->xheight < 0.0 ||
175  !row->baseline.overlap(&rows[otherrow]->baseline, MAXOVERLAP));
176  otherrow--) {
177  ;
178  }
179  upperrow = otherrow; /*decent row above */
180  for (otherrow = rowindex + 1;
181  otherrow < rowcount && (rows[otherrow]->xheight < 0.0 ||
182  !row->baseline.overlap(&rows[otherrow]->baseline, MAXOVERLAP));
183  otherrow++) {
184  ;
185  }
186  lowerrow = otherrow; /*decent row below */
187  if (upperrow >= 0) {
188  find_textlines(block, row, 2, &rows[upperrow]->baseline);
189  }
190  if (row->xheight < 0 && lowerrow < rowcount) {
191  find_textlines(block, row, 2, &rows[lowerrow]->baseline);
192  }
193  if (row->xheight < 0) {
194  if (upperrow >= 0) {
195  find_textlines(block, row, 1, &rows[upperrow]->baseline);
196  } else if (lowerrow < rowcount) {
197  find_textlines(block, row, 1, &rows[lowerrow]->baseline);
198  }
199  }
200  }
201  }
202 
203  for (biggest = 0.0f, rowindex = 0; rowindex < rowcount; rowindex++) {
204  row = rows[rowindex]; /*current row */
205  if (row->xheight < 0) { /*linear failed */
206  /*make do */
207  row->xheight = -row->xheight;
208  }
209  biggest = std::max(biggest, row->xheight);
210  }
211 }
212 
213 /**********************************************************************
214  * correlate_with_stats
215  *
216  * correlate the x-heights and ascender heights of a block to fill-in
217  * the ascender height and descender height for rows without one.
218  **********************************************************************/
219 
220 int Textord::correlate_with_stats(TO_ROW **rows, // rows of block.
221  int rowcount, // no of rows to do.
222  TO_BLOCK *block) {
223  TO_ROW *row; /*current row */
224  int rowindex; /*no of row */
225  float lineheight; /*mean x-height */
226  float ascheight; /*average ascenders */
227  float minascheight; /*min allowed ascheight */
228  int xcount; /*no of samples for xheight */
229  float fullheight; /*mean top height */
230  int fullcount; /*no of samples */
231  float descheight; /*mean descender drop */
232  float mindescheight; /*min allowed descheight */
233  int desccount; /*no of samples */
234 
235  /*no samples */
236  xcount = fullcount = desccount = 0;
237  lineheight = ascheight = fullheight = descheight = 0.0;
238  for (rowindex = 0; rowindex < rowcount; rowindex++) {
239  row = rows[rowindex]; /*current row */
240  if (row->ascrise > 0.0) { /*got ascenders? */
241  lineheight += row->xheight; /*average x-heights */
242  ascheight += row->ascrise; /*average ascenders */
243  xcount++;
244  } else {
245  fullheight += row->xheight; /*assume full height */
246  fullcount++;
247  }
248  if (row->descdrop < 0.0) { /*got descenders? */
249  /*average descenders */
250  descheight += row->descdrop;
251  desccount++;
252  }
253  }
254 
255  if (xcount > 0 && (!oldbl_corrfix || xcount >= fullcount)) {
256  lineheight /= xcount; /*average x-height */
257  /*average caps height */
258  fullheight = lineheight + ascheight / xcount;
259  /*must be decent size */
260  if (fullheight < lineheight * (1 + MIN_ASC_FRACTION)) {
261  fullheight = lineheight * (1 + MIN_ASC_FRACTION);
262  }
263  } else {
264  fullheight /= fullcount; /*average max height */
265  /*guess x-height */
266  lineheight = fullheight * X_HEIGHT_FRACTION;
267  }
268  if (desccount > 0 && (!oldbl_corrfix || desccount >= rowcount / 2)) {
269  descheight /= desccount; /*average descenders */
270  } else {
271  /*guess descenders */
272  descheight = -lineheight * DESCENDER_FRACTION;
273  }
274 
275  if (lineheight > 0.0f) {
276  block->block->set_cell_over_xheight((fullheight - descheight) / lineheight);
277  }
278 
279  minascheight = lineheight * MIN_ASC_FRACTION;
280  mindescheight = -lineheight * MIN_DESC_FRACTION;
281  for (rowindex = 0; rowindex < rowcount; rowindex++) {
282  row = rows[rowindex]; /*do each row */
283  row->all_caps = false;
284  if (row->ascrise / row->xheight < MIN_ASC_FRACTION) {
285  /*no ascenders */
286  if (row->xheight >= lineheight * (1 - MAXHEIGHTVARIANCE) &&
287  row->xheight <= lineheight * (1 + MAXHEIGHTVARIANCE)) {
288  row->ascrise = fullheight - lineheight;
289  /*set to average */
290  row->xheight = lineheight;
291 
292  } else if (row->xheight >= fullheight * (1 - MAXHEIGHTVARIANCE) &&
293  row->xheight <= fullheight * (1 + MAXHEIGHTVARIANCE)) {
294  row->ascrise = row->xheight - lineheight;
295  /*set to average */
296  row->xheight = lineheight;
297  row->all_caps = true;
298  } else {
299  row->ascrise = (fullheight - lineheight) * row->xheight / fullheight;
300  /*scale it */
301  row->xheight -= row->ascrise;
302  row->all_caps = true;
303  }
304  if (row->ascrise < minascheight) {
305  row->ascrise = row->xheight * ((1.0 - X_HEIGHT_FRACTION) / X_HEIGHT_FRACTION);
306  }
307  }
308  if (row->descdrop > mindescheight) {
309  if (row->xheight >= lineheight * (1 - MAXHEIGHTVARIANCE) &&
310  row->xheight <= lineheight * (1 + MAXHEIGHTVARIANCE)) {
311  /*set to average */
312  row->descdrop = descheight;
313  } else {
314  row->descdrop = -row->xheight * DESCENDER_FRACTION;
315  }
316  }
317  }
318  return static_cast<int>(lineheight); // block xheight
319 }
320 
321 /**********************************************************************
322  * find_textlines
323  *
324  * Compute the baseline for the given row.
325  **********************************************************************/
326 
327 void Textord::find_textlines(TO_BLOCK *block, // block row is in
328  TO_ROW *row, // row to do
329  int degree, // required approximation
330  QSPLINE *spline) { // starting spline
331  int partcount; /*no of partitions of */
332  bool holed_line = false; // lost too many blobs
333  int bestpart; /*biggest partition */
334  int partsizes[MAXPARTS]; /*no in each partition */
335  int lineheight; /*guessed x-height */
336  float jumplimit; /*allowed delta change */
337  int blobcount; /*no of blobs on line */
338  int pointcount; /*no of coords */
339  int xstarts[SPLINESIZE + 1]; // segment boundaries
340  int segments; // no of segments
341 
342  // no of blobs in row
343  blobcount = row->blob_list()->length();
344  // partition no of each blob
345  std::vector<char> partids(blobcount);
346  // useful sample points
347  std::vector<int> xcoords(blobcount);
348  // useful sample points
349  std::vector<int> ycoords(blobcount);
350  // edges of blob rectangles
351  std::vector<TBOX> blobcoords(blobcount);
352  // diffs from 1st approx
353  std::vector<float> ydiffs(blobcount);
354 
355  lineheight = get_blob_coords(row, static_cast<int>(block->line_size), &blobcoords[0], holed_line,
356  blobcount);
357  /*limit for line change */
358  jumplimit = lineheight * textord_oldbl_jumplimit;
359  if (jumplimit < MINASCRISE) {
360  jumplimit = MINASCRISE;
361  }
362 
363  if (textord_oldbl_debug) {
364  tprintf("\nInput height=%g, Estimate x-height=%d pixels, jumplimit=%.2f\n", block->line_size,
365  lineheight, jumplimit);
366  }
367  if (holed_line) {
368  make_holed_baseline(&blobcoords[0], blobcount, spline, &row->baseline, row->line_m());
369  } else {
370  make_first_baseline(&blobcoords[0], blobcount, &xcoords[0], &ycoords[0], spline, &row->baseline,
371  jumplimit);
372  }
373 #ifndef GRAPHICS_DISABLED
375  row->baseline.plot(to_win, ScrollView::GOLDENROD);
376  }
377 #endif
378  if (blobcount > 1) {
379  bestpart = partition_line(&blobcoords[0], blobcount, &partcount, &partids[0], partsizes,
380  &row->baseline, jumplimit, &ydiffs[0]);
381  pointcount = partition_coords(&blobcoords[0], blobcount, &partids[0], bestpart, &xcoords[0],
382  &ycoords[0]);
383  segments = segment_spline(&blobcoords[0], blobcount, &xcoords[0], &ycoords[0], degree,
384  pointcount, xstarts);
385  if (!holed_line) {
386  do {
387  row->baseline = QSPLINE(xstarts, segments, &xcoords[0], &ycoords[0], pointcount, degree);
388  } while (textord_oldbl_split_splines &&
389  split_stepped_spline(&row->baseline, jumplimit / 2, &xcoords[0], xstarts, segments));
390  }
391  find_lesser_parts(row, &blobcoords[0], blobcount, &partids[0], partsizes, partcount, bestpart);
392 
393  } else {
394  row->xheight = -1.0f; /*failed */
395  row->descdrop = 0.0f;
396  row->ascrise = 0.0f;
397  }
398  row->baseline.extrapolate(row->line_m(), block->block->pdblk.bounding_box().left(),
399  block->block->pdblk.bounding_box().right());
400 
401  if (textord_really_old_xheight) {
402  old_first_xheight(row, &blobcoords[0], lineheight, blobcount, &row->baseline, jumplimit);
403  } else if (textord_old_xheight) {
404  make_first_xheight(row, &blobcoords[0], lineheight, static_cast<int>(block->line_size),
405  blobcount, &row->baseline, jumplimit);
406  } else {
407  compute_row_xheight(row, block->block->classify_rotation(), row->line_m(), block->line_size);
408  }
409 }
410 
411 /**********************************************************************
412  * get_blob_coords
413  *
414  * Fill the blobcoords array with the coordinates of the blobs
415  * in the row. The return value is the first guess at the line height.
416  **********************************************************************/
417 
418 int get_blob_coords( // get boxes
419  TO_ROW *row, // row to use
420  int32_t lineheight, // block level
421  TBOX *blobcoords, // output boxes
422  bool &holed_line, // lost a lot of blobs
423  int &outcount // no of real blobs
424 ) {
425  // blobs
426  BLOBNBOX_IT blob_it = row->blob_list();
427  int blobindex; /*no along text line */
428  int losscount; // lost blobs
429  int maxlosscount; // greatest lost blobs
430  /*height stat collection */
431  STATS heightstat(0, MAXHEIGHT);
432 
433  if (blob_it.empty()) {
434  return 0; // none
435  }
436  maxlosscount = 0;
437  losscount = 0;
438  blob_it.mark_cycle_pt();
439  blobindex = 0;
440  do {
441  blobcoords[blobindex] = box_next_pre_chopped(&blob_it);
442  if (blobcoords[blobindex].height() > lineheight * 0.25) {
443  heightstat.add(blobcoords[blobindex].height(), 1);
444  }
445  if (blobindex == 0 || blobcoords[blobindex].height() > lineheight * 0.25 ||
446  blob_it.cycled_list()) {
447  blobindex++; /*no of merged blobs */
448  losscount = 0;
449  } else {
450  if (blobcoords[blobindex].height() < blobcoords[blobindex].width() * oldbl_dot_error_size &&
451  blobcoords[blobindex].width() < blobcoords[blobindex].height() * oldbl_dot_error_size) {
452  // counts as dot
453  blobindex++;
454  losscount = 0;
455  } else {
456  losscount++; // lost it
457  if (losscount > maxlosscount) {
458  // remember max
459  maxlosscount = losscount;
460  }
461  }
462  }
463  } while (!blob_it.cycled_list());
464 
465  holed_line = maxlosscount > oldbl_holed_losscount;
466  outcount = blobindex; /*total blobs */
467 
468  if (heightstat.get_total() > 1) {
469  /*guess x-height */
470  return static_cast<int>(heightstat.ile(0.25));
471  } else {
472  return blobcoords[0].height();
473  }
474 }
475 
476 /**********************************************************************
477  * make_first_baseline
478  *
479  * Make the first estimate at a baseline, either by shifting
480  * a supplied previous spline, or by doing a piecewise linear
481  * approximation using all the blobs.
482  **********************************************************************/
483 
484 void make_first_baseline( // initial approximation
485  TBOX blobcoords[], /*blob bounding boxes */
486  int blobcount, /*no of blobcoords */
487  int xcoords[], /*coords for spline */
488  int ycoords[], /*approximator */
489  QSPLINE *spline, /*initial spline */
490  QSPLINE *baseline, /*output spline */
491  float jumplimit /*guess half descenders */
492 ) {
493  int leftedge; /*left edge of line */
494  int rightedge; /*right edge of line */
495  int blobindex; /*current blob */
496  int segment; /*current segment */
497  float prevy, thisy, nexty; /*3 y coords */
498  float y1, y2, y3; /*3 smooth blobs */
499  float maxmax, minmin; /*absolute limits */
500  int x2 = 0; /*right edge of old y3 */
501  int ycount; /*no of ycoords in use */
502  float yturns[SPLINESIZE]; /*y coords of turn pts */
503  int xturns[SPLINESIZE]; /*xcoords of turn pts */
504  int xstarts[SPLINESIZE + 1];
505  int segments; // no of segments
506  ICOORD shift; // shift of spline
507 
508  prevy = 0;
509  /*left edge of row */
510  leftedge = blobcoords[0].left();
511  /*right edge of line */
512  rightedge = blobcoords[blobcount - 1].right();
513  if (spline == nullptr /*no given spline */
514  || spline->segments < 3 /*or trivial */
515  /*or too non-overlap */
516  || spline->xcoords[1] > leftedge + MAXOVERLAP * (rightedge - leftedge) ||
517  spline->xcoords[spline->segments - 1] < rightedge - MAXOVERLAP * (rightedge - leftedge)) {
518  if (textord_oldbl_paradef) {
519  return; // use default
520  }
521  xstarts[0] = blobcoords[0].left() - 1;
522  for (blobindex = 0; blobindex < blobcount; blobindex++) {
523  xcoords[blobindex] = (blobcoords[blobindex].left() + blobcoords[blobindex].right()) / 2;
524  ycoords[blobindex] = blobcoords[blobindex].bottom();
525  }
526  xstarts[1] = blobcoords[blobcount - 1].right() + 1;
527  segments = 1; /*no of segments */
528 
529  /*linear */
530  *baseline = QSPLINE(xstarts, segments, xcoords, ycoords, blobcount, 1);
531 
532  if (blobcount >= 3) {
533  y1 = y2 = y3 = 0.0f;
534  ycount = 0;
535  segment = 0; /*no of segments */
536  maxmax = minmin = 0.0f;
537  thisy = ycoords[0] - baseline->y(xcoords[0]);
538  nexty = ycoords[1] - baseline->y(xcoords[1]);
539  for (blobindex = 2; blobindex < blobcount; blobindex++) {
540  prevy = thisy; /*shift ycoords */
541  thisy = nexty;
542  nexty = ycoords[blobindex] - baseline->y(xcoords[blobindex]);
543  /*middle of smooth y */
544  if (ABS(thisy - prevy) < jumplimit && ABS(thisy - nexty) < jumplimit) {
545  y1 = y2; /*shift window */
546  y2 = y3;
547  y3 = thisy; /*middle point */
548  ycount++;
549  /*local max */
550  if (ycount >= 3 && ((y1 < y2 && y2 >= y3)
551  /*local min */
552  || (y1 > y2 && y2 <= y3))) {
553  if (segment < SPLINESIZE - 2) {
554  /*turning pt */
555  xturns[segment] = x2;
556  yturns[segment] = y2;
557  segment++; /*no of spline segs */
558  }
559  }
560  if (ycount == 1) {
561  maxmax = minmin = y3; /*initialise limits */
562  } else {
563  if (y3 > maxmax) {
564  maxmax = y3; /*biggest max */
565  }
566  if (y3 < minmin) {
567  minmin = y3; /*smallest min */
568  }
569  }
570  /*possible turning pt */
571  x2 = blobcoords[blobindex - 1].right();
572  }
573  }
574 
575  jumplimit *= 1.2f;
576  /*must be wavy */
577  if (maxmax - minmin > jumplimit) {
578  ycount = segment; /*no of segments */
579  for (blobindex = 0, segment = 1; blobindex < ycount; blobindex++) {
580  if (yturns[blobindex] > minmin + jumplimit || yturns[blobindex] < maxmax - jumplimit) {
581  /*significant peak */
582  if (segment == 1 || yturns[blobindex] > prevy + jumplimit ||
583  yturns[blobindex] < prevy - jumplimit) {
584  /*different to previous */
585  xstarts[segment] = xturns[blobindex];
586  segment++;
587  prevy = yturns[blobindex];
588  }
589  /*bigger max */
590  else if ((prevy > minmin + jumplimit && yturns[blobindex] > prevy)
591  /*smaller min */
592  || (prevy < maxmax - jumplimit && yturns[blobindex] < prevy)) {
593  xstarts[segment - 1] = xturns[blobindex];
594  /*improved previous */
595  prevy = yturns[blobindex];
596  }
597  }
598  }
599  xstarts[segment] = blobcoords[blobcount - 1].right() + 1;
600  segments = segment; /*no of segments */
601  /*linear */
602  *baseline = QSPLINE(xstarts, segments, xcoords, ycoords, blobcount, 1);
603  }
604  }
605  } else {
606  *baseline = *spline; /*copy it */
607  shift =
608  ICOORD(0, static_cast<int16_t>(blobcoords[0].bottom() - spline->y(blobcoords[0].right())));
609  baseline->move(shift);
610  }
611 }
612 
613 /**********************************************************************
614  * make_holed_baseline
615  *
616  * Make the first estimate at a baseline, either by shifting
617  * a supplied previous spline, or by doing a piecewise linear
618  * approximation using all the blobs.
619  **********************************************************************/
620 
621 void make_holed_baseline( // initial approximation
622  TBOX blobcoords[], /*blob bounding boxes */
623  int blobcount, /*no of blobcoords */
624  QSPLINE *spline, /*initial spline */
625  QSPLINE *baseline, /*output spline */
626  float gradient // of line
627 ) {
628  int leftedge; /*left edge of line */
629  int rightedge; /*right edge of line */
630  int blobindex; /*current blob */
631  float x; // centre of row
632  ICOORD shift; // shift of spline
633 
634  tesseract::DetLineFit lms; // straight baseline
635  int32_t xstarts[2]; // straight line
636  double coeffs[3];
637  float c; // line parameter
638 
639  /*left edge of row */
640  leftedge = blobcoords[0].left();
641  /*right edge of line */
642  rightedge = blobcoords[blobcount - 1].right();
643  for (blobindex = 0; blobindex < blobcount; blobindex++) {
644  lms.Add(ICOORD((blobcoords[blobindex].left() + blobcoords[blobindex].right()) / 2,
645  blobcoords[blobindex].bottom()));
646  }
647  lms.ConstrainedFit(gradient, &c);
648  xstarts[0] = leftedge;
649  xstarts[1] = rightedge;
650  coeffs[0] = 0;
651  coeffs[1] = gradient;
652  coeffs[2] = c;
653  *baseline = QSPLINE(1, xstarts, coeffs);
654  if (spline != nullptr /*no given spline */
655  && spline->segments >= 3 /*or trivial */
656  /*or too non-overlap */
657  && spline->xcoords[1] <= leftedge + MAXOVERLAP * (rightedge - leftedge) &&
658  spline->xcoords[spline->segments - 1] >= rightedge - MAXOVERLAP * (rightedge - leftedge)) {
659  *baseline = *spline; /*copy it */
660  x = (leftedge + rightedge) / 2.0;
661  shift = ICOORD(0, static_cast<int16_t>(gradient * x + c - spline->y(x)));
662  baseline->move(shift);
663  }
664 }
665 
666 /**********************************************************************
667  * partition_line
668  *
669  * Partition a row of blobs into different groups of continuous
670  * y position. jumplimit specifies the max allowable limit on a jump
671  * before a new partition is started.
672  * The return value is the biggest partition
673  **********************************************************************/
674 
675 int partition_line( // partition blobs
676  TBOX blobcoords[], // bounding boxes
677  int blobcount, /*no of blobs on row */
678  int *numparts, /*number of partitions */
679  char partids[], /*partition no of each blob */
680  int partsizes[], /*no in each partition */
681  QSPLINE *spline, /*curve to fit to */
682  float jumplimit, /*allowed delta change */
683  float ydiffs[] /*diff from spline */
684 ) {
685  int blobindex; /*no along text line */
686  int bestpart; /*best new partition */
687  int biggestpart; /*part with most members */
688  float diff; /*difference from line */
689  int startx; /*index of start blob */
690  float partdiffs[MAXPARTS]; /*step between parts */
691 
692  for (bestpart = 0; bestpart < MAXPARTS; bestpart++) {
693  partsizes[bestpart] = 0; /*zero them all */
694  }
695 
696  startx = get_ydiffs(blobcoords, blobcount, spline, ydiffs);
697  *numparts = 1; /*1 partition */
698  bestpart = -1; /*first point */
699  float drift = 0.0f;
700  float last_delta = 0.0f;
701  for (blobindex = startx; blobindex < blobcount; blobindex++) {
702  /*do each blob in row */
703  diff = ydiffs[blobindex]; /*diff from line */
704  if (textord_oldbl_debug) {
705  tprintf("%d(%d,%d), ", blobindex, blobcoords[blobindex].left(),
706  blobcoords[blobindex].bottom());
707  }
708  bestpart =
709  choose_partition(diff, partdiffs, bestpart, jumplimit, &drift, &last_delta, numparts);
710  /*record partition */
711  partids[blobindex] = bestpart;
712  partsizes[bestpart]++; /*another in it */
713  }
714 
715  bestpart = -1; /*first point */
716  drift = 0.0f;
717  last_delta = 0.0f;
718  partsizes[0]--; /*doing 1st pt again */
719  /*do each blob in row */
720  for (blobindex = startx; blobindex >= 0; blobindex--) {
721  diff = ydiffs[blobindex]; /*diff from line */
722  if (textord_oldbl_debug) {
723  tprintf("%d(%d,%d), ", blobindex, blobcoords[blobindex].left(),
724  blobcoords[blobindex].bottom());
725  }
726  bestpart =
727  choose_partition(diff, partdiffs, bestpart, jumplimit, &drift, &last_delta, numparts);
728  /*record partition */
729  partids[blobindex] = bestpart;
730  partsizes[bestpart]++; /*another in it */
731  }
732 
733  for (biggestpart = 0, bestpart = 1; bestpart < *numparts; bestpart++) {
734  if (partsizes[bestpart] >= partsizes[biggestpart]) {
735  biggestpart = bestpart; /*new biggest */
736  }
737  }
738  if (textord_oldbl_merge_parts) {
739  merge_oldbl_parts(blobcoords, blobcount, partids, partsizes, biggestpart, jumplimit);
740  }
741  return biggestpart; /*biggest partition */
742 }
743 
744 /**********************************************************************
745  * merge_oldbl_parts
746  *
747  * For any adjacent group of blobs in a different part, put them in the
748  * main part if they fit closely to neighbours in the main part.
749  **********************************************************************/
750 
751 void merge_oldbl_parts( // partition blobs
752  TBOX blobcoords[], // bounding boxes
753  int blobcount, /*no of blobs on row */
754  char partids[], /*partition no of each blob */
755  int partsizes[], /*no in each partition */
756  int biggestpart, // major partition
757  float jumplimit /*allowed delta change */
758 ) {
759  bool found_one; // found a bestpart blob
760  bool close_one; // found was close enough
761  int blobindex; /*no along text line */
762  int prevpart; // previous iteration
763  int runlength; // no in this part
764  float diff; /*difference from line */
765  int startx; /*index of start blob */
766  int test_blob; // another index
767  FCOORD coord; // blob coordinate
768  float m, c; // fitted line
769  QLSQ stats; // line stuff
770 
771  prevpart = biggestpart;
772  runlength = 0;
773  startx = 0;
774  for (blobindex = 0; blobindex < blobcount; blobindex++) {
775  if (partids[blobindex] != prevpart) {
776  // tprintf("Partition change at (%d,%d) from %d to %d
777  // after run of %d\n",
778  // blobcoords[blobindex].left(),blobcoords[blobindex].bottom(),
779  // prevpart,partids[blobindex],runlength);
780  if (prevpart != biggestpart && runlength > MAXBADRUN) {
781  stats.clear();
782  for (test_blob = startx; test_blob < blobindex; test_blob++) {
783  coord = FCOORD((blobcoords[test_blob].left() + blobcoords[test_blob].right()) / 2.0,
784  blobcoords[test_blob].bottom());
785  stats.add(coord.x(), coord.y());
786  }
787  stats.fit(1);
788  m = stats.get_b();
789  c = stats.get_c();
790  if (textord_oldbl_debug) {
791  tprintf("Fitted line y=%g x + %g\n", m, c);
792  }
793  found_one = false;
794  close_one = false;
795  for (test_blob = 1;
796  !found_one && (startx - test_blob >= 0 || blobindex + test_blob <= blobcount);
797  test_blob++) {
798  if (startx - test_blob >= 0 && partids[startx - test_blob] == biggestpart) {
799  found_one = true;
800  coord = FCOORD(
801  (blobcoords[startx - test_blob].left() + blobcoords[startx - test_blob].right()) /
802  2.0,
803  blobcoords[startx - test_blob].bottom());
804  diff = m * coord.x() + c - coord.y();
805  if (textord_oldbl_debug) {
806  tprintf("Diff of common blob to suspect part=%g at (%g,%g)\n", diff, coord.x(),
807  coord.y());
808  }
809  if (diff < jumplimit && -diff < jumplimit) {
810  close_one = true;
811  }
812  }
813  if (blobindex + test_blob <= blobcount &&
814  partids[blobindex + test_blob - 1] == biggestpart) {
815  found_one = true;
816  coord = FCOORD((blobcoords[blobindex + test_blob - 1].left() +
817  blobcoords[blobindex + test_blob - 1].right()) /
818  2.0,
819  blobcoords[blobindex + test_blob - 1].bottom());
820  diff = m * coord.x() + c - coord.y();
821  if (textord_oldbl_debug) {
822  tprintf("Diff of common blob to suspect part=%g at (%g,%g)\n", diff, coord.x(),
823  coord.y());
824  }
825  if (diff < jumplimit && -diff < jumplimit) {
826  close_one = true;
827  }
828  }
829  }
830  if (close_one) {
831  if (textord_oldbl_debug) {
832  tprintf(
833  "Merged %d blobs back into part %d from %d starting at "
834  "(%d,%d)\n",
835  runlength, biggestpart, prevpart, blobcoords[startx].left(),
836  blobcoords[startx].bottom());
837  }
838  // switch sides
839  partsizes[prevpart] -= runlength;
840  for (test_blob = startx; test_blob < blobindex; test_blob++) {
841  partids[test_blob] = biggestpart;
842  }
843  }
844  }
845  prevpart = partids[blobindex];
846  runlength = 1;
847  startx = blobindex;
848  } else {
849  runlength++;
850  }
851  }
852 }
853 
854 /**********************************************************************
855  * get_ydiffs
856  *
857  * Get the differences between the blobs and the spline,
858  * putting them in ydiffs. The return value is the index
859  * of the blob in the middle of the "best behaved" region
860  **********************************************************************/
861 
862 int get_ydiffs( // evaluate differences
863  TBOX blobcoords[], // bounding boxes
864  int blobcount, /*no of blobs */
865  QSPLINE *spline, /*approximating spline */
866  float ydiffs[] /*output */
867 ) {
868  int blobindex; /*current blob */
869  int xcentre; /*xcoord */
870  int lastx; /*last xcentre */
871  float diffsum; /*sum of diffs */
872  float diff; /*current difference */
873  float drift; /*sum of spline steps */
874  float bestsum; /*smallest diffsum */
875  int bestindex; /*index of bestsum */
876 
877  diffsum = 0.0f;
878  bestindex = 0;
879  bestsum = static_cast<float>(INT32_MAX);
880  drift = 0.0f;
881  lastx = blobcoords[0].left();
882  /*do each blob in row */
883  for (blobindex = 0; blobindex < blobcount; blobindex++) {
884  /*centre of blob */
885  xcentre = (blobcoords[blobindex].left() + blobcoords[blobindex].right()) >> 1;
886  // step functions in spline
887  drift += spline->step(lastx, xcentre);
888  lastx = xcentre;
889  diff = blobcoords[blobindex].bottom();
890  diff -= spline->y(xcentre);
891  diff += drift;
892  ydiffs[blobindex] = diff; /*store difference */
893  if (blobindex > 2) {
894  /*remove old one */
895  diffsum -= ABS(ydiffs[blobindex - 3]);
896  }
897  diffsum += ABS(diff); /*add new one */
898  if (blobindex >= 2 && diffsum < bestsum) {
899  bestsum = diffsum; /*find min sum */
900  bestindex = blobindex - 1; /*middle of set */
901  }
902  }
903  return bestindex;
904 }
905 
906 /**********************************************************************
907  * choose_partition
908  *
909  * Choose a partition for the point and return the index.
910  **********************************************************************/
911 
912 int choose_partition( // select partition
913  float diff, /*diff from spline */
914  float partdiffs[], /*diff on all parts */
915  int lastpart, /*last assigned partition */
916  float jumplimit, /*new part threshold */
917  float *drift, float *lastdelta, int *partcount /*no of partitions */
918 ) {
919  int partition; /*partition no */
920  int bestpart; /*best new partition */
921  float bestdelta; /*best gap from a part */
922  float delta; /*diff from part */
923 
924  if (lastpart < 0) {
925  partdiffs[0] = diff;
926  lastpart = 0; /*first point */
927  *drift = 0.0f;
928  *lastdelta = 0.0f;
929  }
930  /*adjusted diff from part */
931  delta = diff - partdiffs[lastpart] - *drift;
932  if (textord_oldbl_debug) {
933  tprintf("Diff=%.2f, Delta=%.3f, Drift=%.3f, ", diff, delta, *drift);
934  }
935  if (ABS(delta) > jumplimit / 2) {
936  /*delta on part 0 */
937  bestdelta = diff - partdiffs[0] - *drift;
938  bestpart = 0; /*0 best so far */
939  for (partition = 1; partition < *partcount; partition++) {
940  delta = diff - partdiffs[partition] - *drift;
941  if (ABS(delta) < ABS(bestdelta)) {
942  bestdelta = delta;
943  bestpart = partition; /*part with nearest jump */
944  }
945  }
946  delta = bestdelta;
947  /*too far away */
948  if (ABS(bestdelta) > jumplimit && *partcount < MAXPARTS) { /*and spare part left */
949  bestpart = (*partcount)++; /*best was new one */
950  /*start new one */
951  partdiffs[bestpart] = diff - *drift;
952  delta = 0.0f;
953  }
954  } else {
955  bestpart = lastpart; /*best was last one */
956  }
957 
958  if (bestpart == lastpart &&
959  (ABS(delta - *lastdelta) < jumplimit / 2 || ABS(delta) < jumplimit / 2)) {
960  /*smooth the drift */
961  *drift = (3 * *drift + delta) / 3;
962  }
963  *lastdelta = delta;
964 
965  if (textord_oldbl_debug) {
966  tprintf("P=%d\n", bestpart);
967  }
968 
969  return bestpart;
970 }
971 
972 /**********************************************************************
973  * partition_coords
974  *
975  * Get the x,y coordinates of all points in the bestpart and put them
976  * in xcoords,ycoords. Return the number of points found.
977  **********************************************************************/
978 
979 int partition_coords( // find relevant coords
980  TBOX blobcoords[], // bounding boxes
981  int blobcount, /*no of blobs in row */
982  char partids[], /*partition no of each blob */
983  int bestpart, /*best new partition */
984  int xcoords[], /*points to work on */
985  int ycoords[] /*points to work on */
986 ) {
987  int blobindex; /*no along text line */
988  int pointcount; /*no of points */
989 
990  pointcount = 0;
991  for (blobindex = 0; blobindex < blobcount; blobindex++) {
992  if (partids[blobindex] == bestpart) {
993  /*centre of blob */
994  xcoords[pointcount] = (blobcoords[blobindex].left() + blobcoords[blobindex].right()) >> 1;
995  ycoords[pointcount++] = blobcoords[blobindex].bottom();
996  }
997  }
998  return pointcount; /*no of points found */
999 }
1000 
1001 /**********************************************************************
1002  * segment_spline
1003  *
1004  * Segment the row at midpoints between maxima and minima of the x,y pairs.
1005  * The xstarts of the segments are returned and the number found.
1006  **********************************************************************/
1007 
1008 int segment_spline( // make xstarts
1009  TBOX blobcoords[], // boundign boxes
1010  int blobcount, /*no of blobs in row */
1011  int xcoords[], /*points to work on */
1012  int ycoords[], /*points to work on */
1013  int degree, int pointcount, /*no of points */
1014  int xstarts[] // result
1015 ) {
1016  int ptindex; /*no along text line */
1017  int segment; /*partition no */
1018  int lastmin, lastmax; /*possible turn points */
1019  int turnpoints[SPLINESIZE]; /*good turning points */
1020  int turncount; /*no of turning points */
1021  int max_x; // max specified coord
1022 
1023  xstarts[0] = xcoords[0] - 1; // leftmost defined pt
1024  max_x = xcoords[pointcount - 1] + 1;
1025  if (degree < 2) {
1026  pointcount = 0;
1027  }
1028  turncount = 0; /*no turning points yet */
1029  if (pointcount > 3) {
1030  ptindex = 1;
1031  lastmax = lastmin = 0; /*start with first one */
1032  while (ptindex < pointcount - 1 && turncount < SPLINESIZE - 1) {
1033  /*minimum */
1034  if (ycoords[ptindex - 1] > ycoords[ptindex] && ycoords[ptindex] <= ycoords[ptindex + 1]) {
1035  if (ycoords[ptindex] < ycoords[lastmax] - TURNLIMIT) {
1036  if (turncount == 0 || turnpoints[turncount - 1] != lastmax) {
1037  /*new max point */
1038  turnpoints[turncount++] = lastmax;
1039  }
1040  lastmin = ptindex; /*latest minimum */
1041  } else if (ycoords[ptindex] < ycoords[lastmin]) {
1042  lastmin = ptindex; /*lower minimum */
1043  }
1044  }
1045 
1046  /*maximum */
1047  if (ycoords[ptindex - 1] < ycoords[ptindex] && ycoords[ptindex] >= ycoords[ptindex + 1]) {
1048  if (ycoords[ptindex] > ycoords[lastmin] + TURNLIMIT) {
1049  if (turncount == 0 || turnpoints[turncount - 1] != lastmin) {
1050  /*new min point */
1051  turnpoints[turncount++] = lastmin;
1052  }
1053  lastmax = ptindex; /*latest maximum */
1054  } else if (ycoords[ptindex] > ycoords[lastmax]) {
1055  lastmax = ptindex; /*higher maximum */
1056  }
1057  }
1058  ptindex++;
1059  }
1060  /*possible global min */
1061  if (ycoords[ptindex] < ycoords[lastmax] - TURNLIMIT &&
1062  (turncount == 0 || turnpoints[turncount - 1] != lastmax)) {
1063  if (turncount < SPLINESIZE - 1) {
1064  /*2 more turns */
1065  turnpoints[turncount++] = lastmax;
1066  }
1067  if (turncount < SPLINESIZE - 1) {
1068  turnpoints[turncount++] = ptindex;
1069  }
1070  } else if (ycoords[ptindex] > ycoords[lastmin] + TURNLIMIT
1071  /*possible global max */
1072  && (turncount == 0 || turnpoints[turncount - 1] != lastmin)) {
1073  if (turncount < SPLINESIZE - 1) {
1074  /*2 more turns */
1075  turnpoints[turncount++] = lastmin;
1076  }
1077  if (turncount < SPLINESIZE - 1) {
1078  turnpoints[turncount++] = ptindex;
1079  }
1080  } else if (turncount > 0 && turnpoints[turncount - 1] == lastmin &&
1081  turncount < SPLINESIZE - 1) {
1082  if (ycoords[ptindex] > ycoords[lastmax]) {
1083  turnpoints[turncount++] = ptindex;
1084  } else {
1085  turnpoints[turncount++] = lastmax;
1086  }
1087  } else if (turncount > 0 && turnpoints[turncount - 1] == lastmax &&
1088  turncount < SPLINESIZE - 1) {
1089  if (ycoords[ptindex] < ycoords[lastmin]) {
1090  turnpoints[turncount++] = ptindex;
1091  } else {
1092  turnpoints[turncount++] = lastmin;
1093  }
1094  }
1095  }
1096 
1097  if (textord_oldbl_debug && turncount > 0) {
1098  tprintf("First turn is %d at (%d,%d)\n", turnpoints[0], xcoords[turnpoints[0]],
1099  ycoords[turnpoints[0]]);
1100  }
1101  for (segment = 1; segment < turncount; segment++) {
1102  /*centre y coord */
1103  lastmax = (ycoords[turnpoints[segment - 1]] + ycoords[turnpoints[segment]]) / 2;
1104 
1105  /* fix alg so that it works with both rising and falling sections */
1106  if (ycoords[turnpoints[segment - 1]] < ycoords[turnpoints[segment]]) {
1107  /*find rising y centre */
1108  for (ptindex = turnpoints[segment - 1] + 1;
1109  ptindex < turnpoints[segment] && ycoords[ptindex + 1] <= lastmax; ptindex++) {
1110  ;
1111  }
1112  } else {
1113  /*find falling y centre */
1114  for (ptindex = turnpoints[segment - 1] + 1;
1115  ptindex < turnpoints[segment] && ycoords[ptindex + 1] >= lastmax; ptindex++) {
1116  ;
1117  }
1118  }
1119 
1120  /*centre x */
1121  xstarts[segment] = (xcoords[ptindex - 1] + xcoords[ptindex] + xcoords[turnpoints[segment - 1]] +
1122  xcoords[turnpoints[segment]] + 2) /
1123  4;
1124  /*halfway between turns */
1125  if (textord_oldbl_debug) {
1126  tprintf("Turn %d is %d at (%d,%d), mid pt is %d@%d, final @%d\n", segment,
1127  turnpoints[segment], xcoords[turnpoints[segment]], ycoords[turnpoints[segment]],
1128  ptindex - 1, xcoords[ptindex - 1], xstarts[segment]);
1129  }
1130  }
1131 
1132  xstarts[segment] = max_x;
1133  return segment; /*no of splines */
1134 }
1135 
1136 /**********************************************************************
1137  * split_stepped_spline
1138  *
1139  * Re-segment the spline in cases where there is a big step function.
1140  * Return true if any were done.
1141  **********************************************************************/
1142 
1143 bool split_stepped_spline( // make xstarts
1144  QSPLINE *baseline, // current shot
1145  float jumplimit, // max step function
1146  int *xcoords, /*points to work on */
1147  int *xstarts, // result
1148  int &segments // no of segments
1149 ) {
1150  bool doneany; // return value
1151  int segment; /*partition no */
1152  int startindex, centreindex, endindex;
1153  float leftcoord, rightcoord;
1154  int leftindex, rightindex;
1155  float step; // spline step
1156 
1157  doneany = false;
1158  startindex = 0;
1159  for (segment = 1; segment < segments - 1; segment++) {
1160  step = baseline->step((xstarts[segment - 1] + xstarts[segment]) / 2.0,
1161  (xstarts[segment] + xstarts[segment + 1]) / 2.0);
1162  if (step < 0) {
1163  step = -step;
1164  }
1165  if (step > jumplimit) {
1166  while (xcoords[startindex] < xstarts[segment - 1]) {
1167  startindex++;
1168  }
1169  centreindex = startindex;
1170  while (xcoords[centreindex] < xstarts[segment]) {
1171  centreindex++;
1172  }
1173  endindex = centreindex;
1174  while (xcoords[endindex] < xstarts[segment + 1]) {
1175  endindex++;
1176  }
1177  if (segments >= SPLINESIZE) {
1178  if (textord_debug_baselines) {
1179  tprintf("Too many segments to resegment spline!!\n");
1180  }
1181  } else if (endindex - startindex >= textord_spline_medianwin * 3) {
1182  while (centreindex - startindex < textord_spline_medianwin * 3 / 2) {
1183  centreindex++;
1184  }
1185  while (endindex - centreindex < textord_spline_medianwin * 3 / 2) {
1186  centreindex--;
1187  }
1188  leftindex = (startindex + startindex + centreindex) / 3;
1189  rightindex = (centreindex + endindex + endindex) / 3;
1190  leftcoord = (xcoords[startindex] * 2 + xcoords[centreindex]) / 3.0;
1191  rightcoord = (xcoords[centreindex] + xcoords[endindex] * 2) / 3.0;
1192  while (xcoords[leftindex] > leftcoord &&
1193  leftindex - startindex > textord_spline_medianwin) {
1194  leftindex--;
1195  }
1196  while (xcoords[leftindex] < leftcoord &&
1197  centreindex - leftindex > textord_spline_medianwin / 2) {
1198  leftindex++;
1199  }
1200  if (xcoords[leftindex] - leftcoord > leftcoord - xcoords[leftindex - 1]) {
1201  leftindex--;
1202  }
1203  while (xcoords[rightindex] > rightcoord &&
1204  rightindex - centreindex > textord_spline_medianwin / 2) {
1205  rightindex--;
1206  }
1207  while (xcoords[rightindex] < rightcoord &&
1208  endindex - rightindex > textord_spline_medianwin) {
1209  rightindex++;
1210  }
1211  if (xcoords[rightindex] - rightcoord > rightcoord - xcoords[rightindex - 1]) {
1212  rightindex--;
1213  }
1214  if (textord_debug_baselines) {
1215  tprintf("Splitting spline at %d with step %g at (%d,%d)\n", xstarts[segment],
1216  baseline->step((xstarts[segment - 1] + xstarts[segment]) / 2.0,
1217  (xstarts[segment] + xstarts[segment + 1]) / 2.0),
1218  (xcoords[leftindex - 1] + xcoords[leftindex]) / 2,
1219  (xcoords[rightindex - 1] + xcoords[rightindex]) / 2);
1220  }
1221  insert_spline_point(xstarts, segment, (xcoords[leftindex - 1] + xcoords[leftindex]) / 2,
1222  (xcoords[rightindex - 1] + xcoords[rightindex]) / 2, segments);
1223  doneany = true;
1224  } else if (textord_debug_baselines) {
1225  tprintf("Resegmenting spline failed - insufficient pts (%d,%d,%d,%d)\n", startindex,
1226  centreindex, endindex, (int32_t)textord_spline_medianwin);
1227  }
1228  }
1229  // else tprintf("Spline step at %d is %g\n",
1230  // xstarts[segment],
1231  // baseline->step((xstarts[segment-1]+xstarts[segment])/2.0,
1232  // (xstarts[segment]+xstarts[segment+1])/2.0));
1233  }
1234  return doneany;
1235 }
1236 
1237 /**********************************************************************
1238  * insert_spline_point
1239  *
1240  * Insert a new spline point and shuffle up the others.
1241  **********************************************************************/
1242 
1243 void insert_spline_point( // get descenders
1244  int xstarts[], // starts to shuffle
1245  int segment, // insertion pt
1246  int coord1, // coords to add
1247  int coord2, int &segments // total segments
1248 ) {
1249  int index; // for shuffling
1250 
1251  for (index = segments; index > segment; index--) {
1252  xstarts[index + 1] = xstarts[index];
1253  }
1254  segments++;
1255  xstarts[segment] = coord1;
1256  xstarts[segment + 1] = coord2;
1257 }
1258 
1259 /**********************************************************************
1260  * find_lesser_parts
1261  *
1262  * Average the step from the spline for the other partitions
1263  * and find the commonest partition which has a descender.
1264  **********************************************************************/
1265 
1266 void find_lesser_parts( // get descenders
1267  TO_ROW *row, // row to process
1268  TBOX blobcoords[], // bounding boxes
1269  int blobcount, /*no of blobs */
1270  char partids[], /*partition of each blob */
1271  int partsizes[], /*size of each part */
1272  int partcount, /*no of partitions */
1273  int bestpart /*biggest partition */
1274 ) {
1275  int blobindex; /*index of blob */
1276  int partition; /*current partition */
1277  int xcentre; /*centre of blob */
1278  int poscount; /*count of best up step */
1279  int negcount; /*count of best down step */
1280  float partsteps[MAXPARTS]; /*average step to part */
1281  float bestneg; /*best down step */
1282  int runlength; /*length of bad run */
1283  int biggestrun; /*biggest bad run */
1284 
1285  biggestrun = 0;
1286  for (partition = 0; partition < partcount; partition++) {
1287  partsteps[partition] = 0.0; /*zero accumulators */
1288  }
1289  for (runlength = 0, blobindex = 0; blobindex < blobcount; blobindex++) {
1290  xcentre = (blobcoords[blobindex].left() + blobcoords[blobindex].right()) >> 1;
1291  /*in other parts */
1292  int part_id = static_cast<int>(static_cast<unsigned char>(partids[blobindex]));
1293  if (part_id != bestpart) {
1294  runlength++; /*run of non bests */
1295  if (runlength > biggestrun) {
1296  biggestrun = runlength;
1297  }
1298  partsteps[part_id] += blobcoords[blobindex].bottom() - row->baseline.y(xcentre);
1299  } else {
1300  runlength = 0;
1301  }
1302  }
1303  if (biggestrun > MAXBADRUN) {
1304  row->xheight = -1.0f; /*failed */
1305  } else {
1306  row->xheight = 1.0f; /*success */
1307  }
1308  poscount = negcount = 0;
1309  bestneg = 0.0; /*no step yet */
1310  for (partition = 0; partition < partcount; partition++) {
1311  if (partition != bestpart) {
1312  // by jetsoft divide by zero possible
1313  if (partsizes[partition] == 0) {
1314  partsteps[partition] = 0;
1315  } else {
1316  partsteps[partition] /= partsizes[partition];
1317  }
1318  //
1319 
1320  if (partsteps[partition] >= MINASCRISE && partsizes[partition] > poscount) {
1321  poscount = partsizes[partition];
1322  }
1323  if (partsteps[partition] <= -MINASCRISE && partsizes[partition] > negcount) {
1324  /*ascender rise */
1325  bestneg = partsteps[partition];
1326  /*2nd most popular */
1327  negcount = partsizes[partition];
1328  }
1329  }
1330  }
1331  /*average x-height */
1332  partsteps[bestpart] /= blobcount;
1333  row->descdrop = bestneg;
1334 }
1335 
1336 /**********************************************************************
1337  * old_first_xheight
1338  *
1339  * Makes an x-height spline by copying the baseline and shifting it.
1340  * It estimates the x-height across the line to use as the shift.
1341  * It also finds the ascender height if it can.
1342  **********************************************************************/
1343 
1344 void old_first_xheight( // the wiseowl way
1345  TO_ROW *row, /*current row */
1346  TBOX blobcoords[], /*blob bounding boxes */
1347  int initialheight, // initial guess
1348  int blobcount, /*blobs in blobcoords */
1349  QSPLINE *baseline, /*established */
1350  float jumplimit /*min ascender height */
1351 ) {
1352  int blobindex; /*current blob */
1353  /*height statistics */
1354  STATS heightstat(0, MAXHEIGHT);
1355  int height; /*height of blob */
1356  int xcentre; /*centre of blob */
1357  int lineheight; /*approx xheight */
1358  float ascenders; /*ascender sum */
1359  int asccount; /*no of ascenders */
1360  float xsum; /*xheight sum */
1361  int xcount; /*xheight count */
1362  float diff; /*height difference */
1363 
1364  if (blobcount > 1) {
1365  for (blobindex = 0; blobindex < blobcount; blobindex++) {
1366  xcentre = (blobcoords[blobindex].left() + blobcoords[blobindex].right()) / 2;
1367  /*height of blob */
1368  height = static_cast<int>(blobcoords[blobindex].top() - baseline->y(xcentre) + 0.5);
1369  if (height > initialheight * oldbl_xhfract && height > textord_min_xheight) {
1370  heightstat.add(height, 1);
1371  }
1372  }
1373  if (heightstat.get_total() > 3) {
1374  lineheight = static_cast<int>(heightstat.ile(0.25));
1375  if (lineheight <= 0) {
1376  lineheight = static_cast<int>(heightstat.ile(0.5));
1377  }
1378  } else {
1379  lineheight = initialheight;
1380  }
1381  } else {
1382  lineheight =
1383  static_cast<int>(blobcoords[0].top() -
1384  baseline->y((blobcoords[0].left() + blobcoords[0].right()) / 2) + 0.5);
1385  }
1386 
1387  xsum = 0.0f;
1388  xcount = 0;
1389  for (ascenders = 0.0f, asccount = 0, blobindex = 0; blobindex < blobcount; blobindex++) {
1390  xcentre = (blobcoords[blobindex].left() + blobcoords[blobindex].right()) / 2;
1391  diff = blobcoords[blobindex].top() - baseline->y(xcentre);
1392  /*is it ascender */
1393  if (diff > lineheight + jumplimit) {
1394  ascenders += diff;
1395  asccount++; /*count ascenders */
1396  } else if (diff > lineheight - jumplimit) {
1397  xsum += diff; /*mean xheight */
1398  xcount++;
1399  }
1400  }
1401  if (xcount > 0) {
1402  xsum /= xcount; /*average xheight */
1403  } else {
1404  xsum = static_cast<float>(lineheight); /*guess it */
1405  }
1406  row->xheight *= xsum;
1407  if (asccount > 0) {
1408  row->ascrise = ascenders / asccount - xsum;
1409  } else {
1410  row->ascrise = 0.0f; /*had none */
1411  }
1412  if (row->xheight == 0) {
1413  row->xheight = -1.0f;
1414  }
1415 }
1416 
1417 /**********************************************************************
1418  * make_first_xheight
1419  *
1420  * Makes an x-height spline by copying the baseline and shifting it.
1421  * It estimates the x-height across the line to use as the shift.
1422  * It also finds the ascender height if it can.
1423  **********************************************************************/
1424 
1425 void make_first_xheight( // find xheight
1426  TO_ROW *row, /*current row */
1427  TBOX blobcoords[], /*blob bounding boxes */
1428  int lineheight, // initial guess
1429  int init_lineheight, // block level guess
1430  int blobcount, /*blobs in blobcoords */
1431  QSPLINE *baseline, /*established */
1432  float jumplimit /*min ascender height */
1433 ) {
1434  STATS heightstat(0, HEIGHTBUCKETS);
1435  int lefts[HEIGHTBUCKETS];
1436  int rights[HEIGHTBUCKETS];
1437  int modelist[MODENUM];
1438  int blobindex;
1439  int mode_count; // blobs to count in thr
1440  int sign_bit;
1441  int mode_threshold;
1442  const int kBaselineTouch = 2; // This really should change with resolution.
1443  const int kGoodStrength = 8; // Strength of baseline-touching heights.
1444  const float kMinHeight = 0.25; // Min fraction of lineheight to use.
1445 
1446  sign_bit = row->xheight > 0 ? 1 : -1;
1447 
1448  memset(lefts, 0, HEIGHTBUCKETS * sizeof(lefts[0]));
1449  memset(rights, 0, HEIGHTBUCKETS * sizeof(rights[0]));
1450  mode_count = 0;
1451  for (blobindex = 0; blobindex < blobcount; blobindex++) {
1452  int xcenter = (blobcoords[blobindex].left() + blobcoords[blobindex].right()) / 2;
1453  float base = baseline->y(xcenter);
1454  float bottomdiff = std::fabs(base - blobcoords[blobindex].bottom());
1455  int strength = textord_ocropus_mode && bottomdiff <= kBaselineTouch ? kGoodStrength : 1;
1456  int height = static_cast<int>(blobcoords[blobindex].top() - base + 0.5);
1457  if (blobcoords[blobindex].height() > init_lineheight * kMinHeight) {
1458  if (height > lineheight * oldbl_xhfract && height > textord_min_xheight) {
1459  heightstat.add(height, strength);
1460  if (height < HEIGHTBUCKETS) {
1461  if (xcenter > rights[height]) {
1462  rights[height] = xcenter;
1463  }
1464  if (xcenter > 0 && (lefts[height] == 0 || xcenter < lefts[height])) {
1465  lefts[height] = xcenter;
1466  }
1467  }
1468  }
1469  mode_count += strength;
1470  }
1471  }
1472 
1473  mode_threshold = static_cast<int>(blobcount * 0.1);
1474  if (oldbl_dot_error_size > 1 || oldbl_xhfix) {
1475  mode_threshold = static_cast<int>(mode_count * 0.1);
1476  }
1477 
1478  if (textord_oldbl_debug) {
1479  tprintf("blobcount=%d, mode_count=%d, mode_t=%d\n", blobcount, mode_count, mode_threshold);
1480  }
1481  find_top_modes(&heightstat, HEIGHTBUCKETS, modelist, MODENUM);
1482  if (textord_oldbl_debug) {
1483  for (blobindex = 0; blobindex < MODENUM; blobindex++) {
1484  tprintf("mode[%d]=%d ", blobindex, modelist[blobindex]);
1485  }
1486  tprintf("\n");
1487  }
1488  pick_x_height(row, modelist, lefts, rights, &heightstat, mode_threshold);
1489 
1490  if (textord_oldbl_debug) {
1491  tprintf("Output xheight=%g\n", row->xheight);
1492  }
1493  if (row->xheight < 0 && textord_oldbl_debug) {
1494  tprintf("warning: Row Line height < 0; %4.2f\n", row->xheight);
1495  }
1496 
1497  if (sign_bit < 0) {
1498  row->xheight = -row->xheight;
1499  }
1500 }
1501 
1502 /**********************************************************************
1503  * find_top_modes
1504  *
1505  * Fill the input array with the indices of the top ten modes of the
1506  * input distribution.
1507  **********************************************************************/
1508 
1509 const int kMinModeFactorOcropus = 32;
1510 const int kMinModeFactor = 12;
1511 
1512 void find_top_modes( // get modes
1513  STATS *stats, // stats to hack
1514  int statnum, // no of piles
1515  int modelist[], int modenum // no of modes to get
1516 ) {
1517  int mode_count;
1518  int last_i = 0;
1519  int last_max = INT32_MAX;
1520  int i;
1521  int mode;
1522  int total_max = 0;
1523  int mode_factor = textord_ocropus_mode ? kMinModeFactorOcropus : kMinModeFactor;
1524 
1525  for (mode_count = 0; mode_count < modenum; mode_count++) {
1526  mode = 0;
1527  for (i = 0; i < statnum; i++) {
1528  if (stats->pile_count(i) > stats->pile_count(mode)) {
1529  if ((stats->pile_count(i) < last_max) ||
1530  ((stats->pile_count(i) == last_max) && (i > last_i))) {
1531  mode = i;
1532  }
1533  }
1534  }
1535  last_i = mode;
1536  last_max = stats->pile_count(last_i);
1537  total_max += last_max;
1538  if (last_max <= total_max / mode_factor) {
1539  mode = 0;
1540  }
1541  modelist[mode_count] = mode;
1542  }
1543 }
1544 
1545 /**********************************************************************
1546  * pick_x_height
1547  *
1548  * Choose based on the height modes the best x height value.
1549  **********************************************************************/
1550 
1551 void pick_x_height(TO_ROW *row, // row to do
1552  int modelist[], int lefts[], int rights[], STATS *heightstat,
1553  int mode_threshold) {
1554  int x;
1555  int y;
1556  int z;
1557  float ratio;
1558  int found_one_bigger = false;
1559  int best_x_height = 0;
1560  int best_asc = 0;
1561  int num_in_best;
1562 
1563  for (x = 0; x < MODENUM; x++) {
1564  for (y = 0; y < MODENUM; y++) {
1565  /* Check for two modes */
1566  if (modelist[x] && modelist[y] && heightstat->pile_count(modelist[x]) > mode_threshold &&
1567  (!textord_ocropus_mode || std::min(rights[modelist[x]], rights[modelist[y]]) >
1568  std::max(lefts[modelist[x]], lefts[modelist[y]]))) {
1569  ratio = static_cast<float>(modelist[y]) / static_cast<float>(modelist[x]);
1570  if (1.2 < ratio && ratio < 1.8) {
1571  /* Two modes found */
1572  best_x_height = modelist[x];
1573  num_in_best = heightstat->pile_count(modelist[x]);
1574 
1575  /* Try to get one higher */
1576  do {
1577  found_one_bigger = false;
1578  for (z = 0; z < MODENUM; z++) {
1579  if (modelist[z] == best_x_height + 1 &&
1580  (!textord_ocropus_mode || std::min(rights[modelist[x]], rights[modelist[y]]) >
1581  std::max(lefts[modelist[x]], lefts[modelist[y]]))) {
1582  ratio = static_cast<float>(modelist[y]) / static_cast<float>(modelist[z]);
1583  if ((1.2 < ratio && ratio < 1.8) &&
1584  /* Should be half of best */
1585  heightstat->pile_count(modelist[z]) > num_in_best * 0.5) {
1586  best_x_height++;
1587  found_one_bigger = true;
1588  break;
1589  }
1590  }
1591  }
1592  } while (found_one_bigger);
1593 
1594  /* try to get a higher ascender */
1595 
1596  best_asc = modelist[y];
1597  num_in_best = heightstat->pile_count(modelist[y]);
1598 
1599  /* Try to get one higher */
1600  do {
1601  found_one_bigger = false;
1602  for (z = 0; z < MODENUM; z++) {
1603  if (modelist[z] > best_asc &&
1604  (!textord_ocropus_mode || std::min(rights[modelist[x]], rights[modelist[y]]) >
1605  std::max(lefts[modelist[x]], lefts[modelist[y]]))) {
1606  ratio = static_cast<float>(modelist[z]) / static_cast<float>(best_x_height);
1607  if ((1.2 < ratio && ratio < 1.8) &&
1608  /* Should be half of best */
1609  heightstat->pile_count(modelist[z]) > num_in_best * 0.5) {
1610  best_asc = modelist[z];
1611  found_one_bigger = true;
1612  break;
1613  }
1614  }
1615  }
1616  } while (found_one_bigger);
1617 
1618  row->xheight = static_cast<float>(best_x_height);
1619  row->ascrise = static_cast<float>(best_asc) - best_x_height;
1620  return;
1621  }
1622  }
1623  }
1624  }
1625 
1626  best_x_height = modelist[0]; /* Single Mode found */
1627  num_in_best = heightstat->pile_count(best_x_height);
1628  do {
1629  /* Try to get one higher */
1630  found_one_bigger = false;
1631  for (z = 1; z < MODENUM; z++) {
1632  /* Should be half of best */
1633  if ((modelist[z] == best_x_height + 1) &&
1634  (heightstat->pile_count(modelist[z]) > num_in_best * 0.5)) {
1635  best_x_height++;
1636  found_one_bigger = true;
1637  break;
1638  }
1639  }
1640  } while (found_one_bigger);
1641 
1642  row->ascrise = 0.0f;
1643  row->xheight = static_cast<float>(best_x_height);
1644  if (row->xheight == 0) {
1645  row->xheight = -1.0f;
1646  }
1647 }
1648 
1649 } // namespace tesseract
#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 MAXBADRUN
Definition: oldbasel.cpp:65
#define MAXOVERLAP
Definition: oldbasel.cpp:64
#define SPLINESIZE
Definition: oldbasel.cpp:69
#define MAXPARTS
Definition: oldbasel.cpp:68
#define DESCENDER_FRACTION
Definition: oldbasel.cpp:58
#define HEIGHTBUCKETS
Definition: oldbasel.cpp:66
#define X_HEIGHT_FRACTION
Definition: oldbasel.cpp:57
#define MODENUM
Definition: oldbasel.cpp:67
#define TURNLIMIT
Definition: oldbasel.cpp:56
#define ABS(x)
Definition: oldbasel.cpp:71
#define MIN_DESC_FRACTION
Definition: oldbasel.cpp:60
#define MIN_ASC_FRACTION
Definition: oldbasel.cpp:59
#define MAXHEIGHT
Definition: oldbasel.cpp:63
#define MINASCRISE
Definition: oldbasel.cpp:61
#define MAXHEIGHTVARIANCE
Definition: oldbasel.cpp:62
int segment_spline(TBOX blobcoords[], int blobcount, int xcoords[], int ycoords[], int degree, int pointcount, int xstarts[])
Definition: oldbasel.cpp:1008
int get_ydiffs(TBOX blobcoords[], int blobcount, QSPLINE *spline, float ydiffs[])
Definition: oldbasel.cpp:862
bool textord_show_final_rows
Definition: makerow.cpp:50
void make_first_baseline(TBOX blobcoords[], int blobcount, int xcoords[], int ycoords[], QSPLINE *spline, QSPLINE *baseline, float jumplimit)
Definition: oldbasel.cpp:484
void find_top_modes(STATS *stats, int statnum, int modelist[], int modenum)
Definition: oldbasel.cpp:1512
const int kMinModeFactor
Definition: oldbasel.cpp:1510
int textord_min_xheight
Definition: makerow.cpp:70
void tprintf(const char *format,...)
Definition: tprintf.cpp:41
void pick_x_height(TO_ROW *row, int modelist[], int lefts[], int rights[], STATS *heightstat, int mode_threshold)
Definition: oldbasel.cpp:1551
void insert_spline_point(int xstarts[], int segment, int coord1, int coord2, int &segments)
Definition: oldbasel.cpp:1243
int textord_spline_medianwin
Definition: makerow.cpp:68
void old_first_xheight(TO_ROW *row, TBOX blobcoords[], int initialheight, int blobcount, QSPLINE *baseline, float jumplimit)
Definition: oldbasel.cpp:1344
@ baseline
Definition: mfoutline.h:53
ScrollView * to_win
Definition: drawtord.cpp:37
int partition_coords(TBOX blobcoords[], int blobcount, char partids[], int bestpart, int xcoords[], int ycoords[])
Definition: oldbasel.cpp:979
int choose_partition(float diff, float partdiffs[], int lastpart, float jumplimit, float *drift, float *lastdelta, int *partcount)
Definition: oldbasel.cpp:912
void make_holed_baseline(TBOX blobcoords[], int blobcount, QSPLINE *spline, QSPLINE *baseline, float gradient)
Definition: oldbasel.cpp:621
bool textord_oldbl_debug
Definition: oldbasel.cpp:43
const int kMinModeFactorOcropus
Definition: oldbasel.cpp:1509
bool split_stepped_spline(QSPLINE *baseline, float jumplimit, int *xcoords, int *xstarts, int &segments)
Definition: oldbasel.cpp:1143
int partition_line(TBOX blobcoords[], int blobcount, int *numparts, char partids[], int partsizes[], QSPLINE *spline, float jumplimit, float ydiffs[])
Definition: oldbasel.cpp:675
void find_lesser_parts(TO_ROW *row, TBOX blobcoords[], int blobcount, char partids[], int partsizes[], int partcount, int bestpart)
Definition: oldbasel.cpp:1266
void make_first_xheight(TO_ROW *row, TBOX blobcoords[], int lineheight, int init_lineheight, int blobcount, QSPLINE *baseline, float jumplimit)
Definition: oldbasel.cpp:1425
TBOX box_next_pre_chopped(BLOBNBOX_IT *it)
Definition: blobbox.cpp:667
void merge_oldbl_parts(TBOX blobcoords[], int blobcount, char partids[], int partsizes[], int biggestpart, float jumplimit)
Definition: oldbasel.cpp:751
int get_blob_coords(TO_ROW *row, int32_t lineheight, TBOX *blobcoords, bool &holed_line, int &outcount)
Definition: oldbasel.cpp:418
bool textord_old_xheight
Definition: makerow.cpp:56
QSPLINE baseline
Definition: blobbox.h:676
BLOBNBOX_LIST * blob_list()
Definition: blobbox.h:608
static const double kXHeightFraction
Definition: ccstruct.h:34
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
integer coordinate
Definition: points.h:36
float y() const
Definition: points.h:209
float x() const
Definition: points.h:206
void fit(int degree)
Definition: quadlsq.cpp:100
void clear()
Definition: quadlsq.cpp:37
double get_b() const
Definition: quadlsq.h:48
double get_c() const
Definition: quadlsq.h:51
void add(double x, double y)
Definition: quadlsq.cpp:58
double y(double x) const
Definition: quspline.cpp:203
double step(double x1, double x2)
Definition: quspline.cpp:180
TDimension left() const
Definition: rect.h:82
TDimension height() const
Definition: rect.h:118
TDimension top() const
Definition: rect.h:68
TDimension right() const
Definition: rect.h:89
TDimension bottom() const
Definition: rect.h:75
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 ile(double frac) const
Definition: statistc.cpp:173
void compute_row_xheight(TO_ROW *row, const FCOORD &rotation, float gradient, int block_line_size)
Definition: makerow.cpp:1384
void compute_block_xheight(TO_BLOCK *block, float gradient)
Definition: makerow.cpp:1278