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
wordseg.cpp
Go to the documentation of this file.
1 /**********************************************************************
2 * File: wordseg.cpp (Formerly wspace.c)
3 * Description: Code to segment the blobs into words.
4 * Author: Ray Smith
5 * Created: Fri Oct 16 11:32:28 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 "statistc.h"
27 #include "drawtord.h"
28 #include "makerow.h"
29 #include "pitsync1.h"
30 #include "tovars.h"
31 #include "topitch.h"
32 #include "cjkpitch.h"
33 #include "textord.h"
34 #include "fpchop.h"
35 #include "wordseg.h"
36
37 // Include automatically generated configuration file if running autoconf.
38 #ifdef HAVE_CONFIG_H
39 #include "config_auto.h"
40 #endif
41
42 #define EXTERN
43
44 EXTERN BOOL_VAR(textord_fp_chopping, TRUE, "Do fixed pitch chopping");
45 EXTERN BOOL_VAR(textord_force_make_prop_words, FALSE,
46 "Force proportional word segmentation on all rows");
47 EXTERN BOOL_VAR(textord_chopper_test, FALSE,
48 "Chopper is being tested.");
49
50 #define FIXED_WIDTH_MULTIPLE 5
51 #define BLOCK_STATS_CLUSTERS 10
52
53
61 void make_single_word(bool one_blob, TO_ROW_LIST *rows, ROW_LIST* real_rows) {
62 TO_ROW_IT to_row_it(rows);
63 ROW_IT row_it(real_rows);
64 for (to_row_it.mark_cycle_pt(); !to_row_it.cycled_list();
65 to_row_it.forward()) {
66 TO_ROW* row = to_row_it.data();
67 // The blobs have to come out of the BLOBNBOX into the C_BLOB_LIST ready
68 // to create the word.
69 C_BLOB_LIST cblobs;
70 C_BLOB_IT cblob_it(&cblobs);
71 BLOBNBOX_IT box_it(row->blob_list());
72 for (;!box_it.empty(); box_it.forward()) {
73 BLOBNBOX* bblob= box_it.extract();
74 if (bblob->joined_to_prev() || (one_blob && !cblob_it.empty())) {
75 if (bblob->cblob() != NULL) {
76 C_OUTLINE_IT cout_it(cblob_it.data()->out_list());
77 cout_it.move_to_last();
78 cout_it.add_list_after(bblob->cblob()->out_list());
79 delete bblob->cblob();
80 }
81 } else {
82 if (bblob->cblob() != NULL)
83 cblob_it.add_after_then_move(bblob->cblob());
84 }
85 delete bblob;
86 }
87 // Convert the TO_ROW to a ROW.
88 ROW* real_row = new ROW(row, static_cast<inT16>(row->kern_size),
89 static_cast<inT16>(row->space_size));
90 WERD_IT word_it(real_row->word_list());
91 WERD* word = new WERD(&cblobs, 0, NULL);
92 word->set_flag(W_BOL, TRUE);
93 word->set_flag(W_EOL, TRUE);
94 word->set_flag(W_DONT_CHOP, one_blob);
95 word_it.add_after_then_move(word);
96 row_it.add_after_then_move(real_row);
97 }
98 }
99
105 void make_words(tesseract::Textord *textord,
106 ICOORD page_tr, // top right
107 float gradient, // page skew
108 BLOCK_LIST *blocks, // block list
109 TO_BLOCK_LIST *port_blocks) { // output list
110 TO_BLOCK_IT block_it; // iterator
111 TO_BLOCK *block; // current block
112
113 if (textord->use_cjk_fp_model()) {
114 compute_fixed_pitch_cjk(page_tr, port_blocks);
115 } else {
116 compute_fixed_pitch(page_tr, port_blocks, gradient, FCOORD(0.0f, -1.0f),
117 !(BOOL8) textord_test_landscape);
118 }
119 textord->to_spacing(page_tr, port_blocks);
120 block_it.set_to_list(port_blocks);
121 for (block_it.mark_cycle_pt(); !block_it.cycled_list(); block_it.forward()) {
122 block = block_it.data();
123 make_real_words(textord, block, FCOORD(1.0f, 0.0f));
124 }
125 }
126
127
135 void set_row_spaces( //find space sizes
136 TO_BLOCK *block, //block to do
137 FCOORD rotation, //for drawing
138 BOOL8 testing_on //correct orientation
139 ) {
140 inT32 maxwidth; //of widest space
141 TO_ROW *row; //current row
142 TO_ROW_IT row_it = block->get_rows ();
143
144 if (row_it.empty ())
145 return; //empty block
146 maxwidth = (inT32) ceil (block->xheight * textord_words_maxspace);
147 for (row_it.mark_cycle_pt (); !row_it.cycled_list (); row_it.forward ()) {
148 row = row_it.data ();
149 if (row->fixed_pitch == 0) {
150 // if (!textord_test_mode
151 // && row_words(block,row,maxwidth,rotation,testing_on)==0
152 // || textord_test_mode
153 // && row_words2(block,row,maxwidth,rotation,testing_on)==0)
154 // {
155 row->min_space =
156 (inT32) ceil (row->pr_space -
157 (row->pr_space -
158 row->pr_nonsp) * textord_words_definite_spread);
159 row->max_nonspace =
160 (inT32) floor (row->pr_nonsp +
161 (row->pr_space -
162 row->pr_nonsp) * textord_words_definite_spread);
163 if (testing_on && textord_show_initial_words) {
164 tprintf ("Assigning defaults %d non, %d space to row at %g\n",
165 row->max_nonspace, row->min_space, row->intercept ());
166 }
167 row->space_threshold = (row->max_nonspace + row->min_space) / 2;
168 row->space_size = row->pr_space;
169 row->kern_size = row->pr_nonsp;
170 // }
171 }
172 #ifndef GRAPHICS_DISABLED
173 if (textord_show_initial_words && testing_on) {
174 plot_word_decisions (to_win, (inT16) row->fixed_pitch, row);
175 }
176 #endif
177 }
178 }
179
180
187 inT32 row_words( //compute space size
188 TO_BLOCK *block, //block it came from
189 TO_ROW *row, //row to operate on
190 inT32 maxwidth, //max expected space size
191 FCOORD rotation, //for drawing
192 BOOL8 testing_on //for debug
193 ) {
194 BOOL8 testing_row; //contains testpt
195 BOOL8 prev_valid; //if decent size
196 BOOL8 this_valid; //current blob big enough
197 inT32 prev_x; //end of prev blob
198 inT32 min_gap; //min interesting gap
199 inT32 cluster_count; //no of clusters
200 inT32 gap_index; //which cluster
201 inT32 smooth_factor; //for smoothing stats
202 BLOBNBOX *blob; //current blob
203 float lower, upper; //clustering parameters
204 float gaps[3]; //gap clusers
205 ICOORD testpt;
206 TBOX blob_box; //bounding box
207 //iterator
208 BLOBNBOX_IT blob_it = row->blob_list ();
209 STATS gap_stats (0, maxwidth);
210 STATS cluster_stats[4]; //clusters
211
212 testpt = ICOORD (textord_test_x, textord_test_y);
213 smooth_factor =
214 (inT32) (block->xheight * textord_wordstats_smooth_factor + 1.5);
215 // if (testing_on)
216 // tprintf("Row smooth factor=%d\n",smooth_factor);
217 prev_valid = FALSE;
218 prev_x = -MAX_INT32;
219 testing_row = FALSE;
220 for (blob_it.mark_cycle_pt (); !blob_it.cycled_list (); blob_it.forward ()) {
221 blob = blob_it.data ();
222 blob_box = blob->bounding_box ();
223 if (blob_box.contains (testpt))
224 testing_row = TRUE;
225 gap_stats.add (blob_box.width (), 1);
226 }
227 min_gap = (inT32) floor (gap_stats.ile (textord_words_width_ile));
228 gap_stats.clear ();
229 for (blob_it.mark_cycle_pt (); !blob_it.cycled_list (); blob_it.forward ()) {
230 blob = blob_it.data ();
231 if (!blob->joined_to_prev ()) {
232 blob_box = blob->bounding_box ();
233 // this_valid=blob_box.width()>=min_gap;
234 this_valid = TRUE;
235 if (this_valid && prev_valid
236 && blob_box.left () - prev_x < maxwidth) {
237 gap_stats.add (blob_box.left () - prev_x, 1);
238 }
239 prev_x = blob_box.right ();
240 prev_valid = this_valid;
241 }
242 }
243 if (gap_stats.get_total () == 0) {
244 row->min_space = 0; //no evidence
245 row->max_nonspace = 0;
246 return 0;
247 }
248 gap_stats.smooth (smooth_factor);
249 lower = row->xheight * textord_words_initial_lower;
250 upper = row->xheight * textord_words_initial_upper;
251 cluster_count = gap_stats.cluster (lower, upper,
252 textord_spacesize_ratioprop, 3,
253 cluster_stats);
254 while (cluster_count < 2 && ceil (lower) < floor (upper)) {
255 //shrink gap
256 upper = (upper * 3 + lower) / 4;
257 lower = (lower * 3 + upper) / 4;
258 cluster_count = gap_stats.cluster (lower, upper,
259 textord_spacesize_ratioprop, 3,
260 cluster_stats);
261 }
262 if (cluster_count < 2) {
263 row->min_space = 0; //no evidence
264 row->max_nonspace = 0;
265 return 0;
266 }
267 for (gap_index = 0; gap_index < cluster_count; gap_index++)
268 gaps[gap_index] = cluster_stats[gap_index + 1].ile (0.5);
269 //get medians
270 if (cluster_count > 2) {
271 if (testing_on && textord_show_initial_words) {
272 tprintf ("Row at %g has 3 sizes of gap:%g,%g,%g\n",
273 row->intercept (),
274 cluster_stats[1].ile (0.5),
275 cluster_stats[2].ile (0.5), cluster_stats[3].ile (0.5));
276 }
277 lower = gaps[0];
278 if (gaps[1] > lower) {
279 upper = gaps[1]; //prefer most frequent
280 if (upper < block->xheight * textord_words_min_minspace
281 && gaps[2] > gaps[1]) {
282 upper = gaps[2];
283 }
284 }
285 else if (gaps[2] > lower
286 && gaps[2] >= block->xheight * textord_words_min_minspace)
287 upper = gaps[2];
288 else if (lower >= block->xheight * textord_words_min_minspace) {
289 upper = lower; //not nice
290 lower = gaps[1];
291 if (testing_on && textord_show_initial_words) {
292 tprintf ("Had to switch most common from lower to upper!!\n");
293 gap_stats.print();
294 }
295 }
296 else {
297 row->min_space = 0; //no evidence
298 row->max_nonspace = 0;
299 return 0;
300 }
301 }
302 else {
303 if (gaps[1] < gaps[0]) {
304 if (testing_on && textord_show_initial_words) {
305 tprintf ("Had to switch most common from lower to upper!!\n");
306 gap_stats.print();
307 }
308 lower = gaps[1];
309 upper = gaps[0];
310 }
311 else {
312 upper = gaps[1];
313 lower = gaps[0];
314 }
315 }
316 if (upper < block->xheight * textord_words_min_minspace) {
317 row->min_space = 0; //no evidence
318 row->max_nonspace = 0;
319 return 0;
320 }
321 if (upper * 3 < block->min_space * 2 + block->max_nonspace
322 || lower * 3 > block->min_space * 2 + block->max_nonspace) {
323 if (testing_on && textord_show_initial_words) {
324 tprintf ("Disagreement between block and row at %g!!\n",
325 row->intercept ());
326 tprintf ("Lower=%g, upper=%g, Stats:\n", lower, upper);
327 gap_stats.print();
328 }
329 }
330 row->min_space =
331 (inT32) ceil (upper - (upper - lower) * textord_words_definite_spread);
332 row->max_nonspace =
333 (inT32) floor (lower + (upper - lower) * textord_words_definite_spread);
334 row->space_threshold = (row->max_nonspace + row->min_space) / 2;
335 row->space_size = upper;
336 row->kern_size = lower;
337 if (testing_on && textord_show_initial_words) {
338 if (testing_row) {
339 tprintf ("GAP STATS\n");
340 gap_stats.print();
341 tprintf ("SPACE stats\n");
342 cluster_stats[2].print_summary();
343 tprintf ("NONSPACE stats\n");
344 cluster_stats[1].print_summary();
345 }
346 tprintf ("Row at %g has minspace=%d(%g), max_non=%d(%g)\n",
347 row->intercept (), row->min_space, upper,
348 row->max_nonspace, lower);
349 }
350 return cluster_stats[2].get_total ();
351 }
352
353
360 inT32 row_words2( //compute space size
361 TO_BLOCK *block, //block it came from
362 TO_ROW *row, //row to operate on
363 inT32 maxwidth, //max expected space size
364 FCOORD rotation, //for drawing
365 BOOL8 testing_on //for debug
366 ) {
367 BOOL8 testing_row; //contains testpt
368 BOOL8 prev_valid; //if decent size
369 BOOL8 this_valid; //current blob big enough
370 inT32 prev_x; //end of prev blob
371 inT32 min_width; //min interesting width
372 inT32 valid_count; //good gaps
373 inT32 total_count; //total gaps
374 inT32 cluster_count; //no of clusters
375 inT32 prev_count; //previous cluster_count
376 inT32 gap_index; //which cluster
377 inT32 smooth_factor; //for smoothing stats
378 BLOBNBOX *blob; //current blob
379 float lower, upper; //clustering parameters
380 ICOORD testpt;
381 TBOX blob_box; //bounding box
382 //iterator
383 BLOBNBOX_IT blob_it = row->blob_list ();
384 STATS gap_stats (0, maxwidth);
385 //gap sizes
386 float gaps[BLOCK_STATS_CLUSTERS];
387 STATS cluster_stats[BLOCK_STATS_CLUSTERS + 1];
388 //clusters
389
390 testpt = ICOORD (textord_test_x, textord_test_y);
391 smooth_factor =
392 (inT32) (block->xheight * textord_wordstats_smooth_factor + 1.5);
393 // if (testing_on)
394 // tprintf("Row smooth factor=%d\n",smooth_factor);
395 prev_valid = FALSE;
396 prev_x = -MAX_INT16;
397 testing_row = FALSE;
398 //min blob size
399 min_width = (inT32) block->pr_space;
400 total_count = 0;
401 for (blob_it.mark_cycle_pt (); !blob_it.cycled_list (); blob_it.forward ()) {
402 blob = blob_it.data ();
403 if (!blob->joined_to_prev ()) {
404 blob_box = blob->bounding_box ();
405 this_valid = blob_box.width () >= min_width;
406 this_valid = TRUE;
407 if (this_valid && prev_valid
408 && blob_box.left () - prev_x < maxwidth) {
409 gap_stats.add (blob_box.left () - prev_x, 1);
410 }
411 total_count++; //count possibles
412 prev_x = blob_box.right ();
413 prev_valid = this_valid;
414 }
415 }
416 valid_count = gap_stats.get_total ();
417 if (valid_count < total_count * textord_words_minlarge) {
418 gap_stats.clear ();
419 prev_x = -MAX_INT16;
420 for (blob_it.mark_cycle_pt (); !blob_it.cycled_list ();
421 blob_it.forward ()) {
422 blob = blob_it.data ();
423 if (!blob->joined_to_prev ()) {
424 blob_box = blob->bounding_box ();
425 if (blob_box.left () - prev_x < maxwidth) {
426 gap_stats.add (blob_box.left () - prev_x, 1);
427 }
428 prev_x = blob_box.right ();
429 }
430 }
431 }
432 if (gap_stats.get_total () == 0) {
433 row->min_space = 0; //no evidence
434 row->max_nonspace = 0;
435 return 0;
436 }
437
438 cluster_count = 0;
439 lower = block->xheight * words_initial_lower;
440 upper = block->xheight * words_initial_upper;
441 gap_stats.smooth (smooth_factor);
442 do {
443 prev_count = cluster_count;
444 cluster_count = gap_stats.cluster (lower, upper,
445 textord_spacesize_ratioprop,
446 BLOCK_STATS_CLUSTERS, cluster_stats);
447 }
448 while (cluster_count > prev_count && cluster_count < BLOCK_STATS_CLUSTERS);
449 if (cluster_count < 1) {
450 row->min_space = 0;
451 row->max_nonspace = 0;
452 return 0;
453 }
454 for (gap_index = 0; gap_index < cluster_count; gap_index++)
455 gaps[gap_index] = cluster_stats[gap_index + 1].ile (0.5);
456 //get medians
457 if (testing_on) {
458 tprintf ("cluster_count=%d:", cluster_count);
459 for (gap_index = 0; gap_index < cluster_count; gap_index++)
460 tprintf (" %g(%d)", gaps[gap_index],
461 cluster_stats[gap_index + 1].get_total ());
462 tprintf ("\n");
463 }
464
465 //Try to find proportional non-space and space for row.
466 for (gap_index = 0; gap_index < cluster_count
467 && gaps[gap_index] > block->max_nonspace; gap_index++);
468 if (gap_index < cluster_count)
469 lower = gaps[gap_index]; //most frequent below
470 else {
471 if (testing_on)
472 tprintf ("No cluster below block threshold!, using default=%g\n",
473 block->pr_nonsp);
474 lower = block->pr_nonsp;
475 }
476 for (gap_index = 0; gap_index < cluster_count
477 && gaps[gap_index] <= block->max_nonspace; gap_index++);
478 if (gap_index < cluster_count)
479 upper = gaps[gap_index]; //most frequent above
480 else {
481 if (testing_on)
482 tprintf ("No cluster above block threshold!, using default=%g\n",
483 block->pr_space);
484 upper = block->pr_space;
485 }
486 row->min_space =
487 (inT32) ceil (upper - (upper - lower) * textord_words_definite_spread);
488 row->max_nonspace =
489 (inT32) floor (lower + (upper - lower) * textord_words_definite_spread);
490 row->space_threshold = (row->max_nonspace + row->min_space) / 2;
491 row->space_size = upper;
492 row->kern_size = lower;
493 if (testing_on) {
494 if (testing_row) {
495 tprintf ("GAP STATS\n");
496 gap_stats.print();
497 tprintf ("SPACE stats\n");
498 cluster_stats[2].print_summary();
499 tprintf ("NONSPACE stats\n");
500 cluster_stats[1].print_summary();
501 }
502 tprintf ("Row at %g has minspace=%d(%g), max_non=%d(%g)\n",
503 row->intercept (), row->min_space, upper,
504 row->max_nonspace, lower);
505 }
506 return 1;
507 }
508
509
516 void make_real_words(
517 tesseract::Textord *textord,
518 TO_BLOCK *block, //block to do
519 FCOORD rotation //for drawing
520 ) {
521 TO_ROW *row; //current row
522 TO_ROW_IT row_it = block->get_rows ();
523 ROW *real_row = NULL; //output row
524 ROW_IT real_row_it = block->block->row_list ();
525
526 if (row_it.empty ())
527 return; //empty block
528 for (row_it.mark_cycle_pt (); !row_it.cycled_list (); row_it.forward ()) {
529 row = row_it.data ();
530 if (row->blob_list ()->empty () && !row->rep_words.empty ()) {
531 real_row = make_rep_words (row, block);
532 } else if (!row->blob_list()->empty()) {
533 // In a fixed pitch document, some lines may be detected as fixed pitch
534 // while others don't, and will go through different path.
535 // For non-space delimited language like CJK, fixed pitch chop always
536 // leave the entire line as one word. We can force consistent chopping
537 // with force_make_prop_words flag.
538 POLY_BLOCK* pb = block->block->poly_block();
539 if (textord_chopper_test) {
540 real_row = textord->make_blob_words (row, rotation);
541 } else if (textord_force_make_prop_words ||
542 (pb != NULL && !pb->IsText()) ||
543 row->pitch_decision == PITCH_DEF_PROP ||
544 row->pitch_decision == PITCH_CORR_PROP) {
545 real_row = textord->make_prop_words (row, rotation);
546 } else if (row->pitch_decision == PITCH_DEF_FIXED ||
547 row->pitch_decision == PITCH_CORR_FIXED) {
548 real_row = fixed_pitch_words (row, rotation);
549 } else {
550 ASSERT_HOST(FALSE);
551 }
552 }
553 if (real_row != NULL) {
554 //put row in block
555 real_row_it.add_after_then_move (real_row);
556 }
557 }
558 block->block->set_stats (block->fixed_pitch == 0, (inT16) block->kern_size,
559 (inT16) block->space_size,
560 (inT16) block->fixed_pitch);
561 block->block->check_pitch ();
562 }
563
564
572 ROW *make_rep_words( //make a row
573 TO_ROW *row, //row to convert
574 TO_BLOCK *block //block it lives in
575 ) {
576 inT32 xstarts[2]; //ends of row
577 ROW *real_row; //output row
578 TBOX word_box; //bounding box
579 double coeffs[3]; //spline
580 //iterator
581 WERD_IT word_it = &row->rep_words;
582
583 if (word_it.empty ())
584 return NULL;
585 word_box = word_it.data ()->bounding_box ();
586 for (word_it.mark_cycle_pt (); !word_it.cycled_list (); word_it.forward ())
587 word_box += word_it.data ()->bounding_box ();
588 xstarts[0] = word_box.left ();
589 xstarts[1] = word_box.right ();
590 coeffs[0] = 0;
591 coeffs[1] = row->line_m ();
592 coeffs[2] = row->line_c ();
593 row->xheight = block->xheight;
594 real_row = new ROW(row,
595 (inT16) block->kern_size, (inT16) block->space_size);
596 word_it.set_to_list (real_row->word_list ());
597 //put words in row
598 word_it.add_list_after (&row->rep_words);
599 real_row->recalc_bounding_box ();
600 return real_row;
601 }
602
603
611 WERD *make_real_word(BLOBNBOX_IT *box_it, //iterator
612 inT32 blobcount, //no of blobs to use
613 BOOL8 bol, //start of line
614 uinT8 blanks //no of blanks
615 ) {
616 C_OUTLINE_IT cout_it;
617 C_BLOB_LIST cblobs;
618 C_BLOB_IT cblob_it = &cblobs;
619 WERD *word; // new word
620 BLOBNBOX *bblob; // current blob
621 inT32 blobindex; // in row
622
623 for (blobindex = 0; blobindex < blobcount; blobindex++) {
624 bblob = box_it->extract();
625 if (bblob->joined_to_prev()) {
626 if (bblob->cblob() != NULL) {
627 cout_it.set_to_list(cblob_it.data()->out_list());
628 cout_it.move_to_last();
629 cout_it.add_list_after(bblob->cblob()->out_list());
630 delete bblob->cblob();
631 }
632 }
633 else {
634 if (bblob->cblob() != NULL)
635 cblob_it.add_after_then_move(bblob->cblob());
636 }
637 delete bblob;
638 box_it->forward(); // next one
639 }
640
641 if (blanks < 1)
642 blanks = 1;
643
644 word = new WERD(&cblobs, blanks, NULL);
645
646 if (bol)
647 word->set_flag(W_BOL, TRUE);
648 if (box_it->at_first())
649 word->set_flag(W_EOL, TRUE); // at end of line
650
651 return word;
652 }