Tesseract 3.02

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

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