Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/tesseract/src/textord/oldbasel.cpp @ 2:b50eed0cc0ef upstream

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