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