Tesseract  3.02
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
topitch.cpp
Go to the documentation of this file.
1 /**********************************************************************
2  * File: topitch.cpp (Formerly to_pitch.c)
3  * Description: Code to determine fixed pitchness and the pitch if fixed.
4  * Author: Ray Smith
5  * Created: Tue Aug 24 16:57:29 BST 1993
6  *
7  * (C) Copyright 1993, 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 "pithsync.h"
31 #include "tovars.h"
32 #include "wordseg.h"
33 #include "topitch.h"
34 #include "secname.h"
35 #include "helpers.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_all_prop, FALSE, "All doc is proportial text");
46 "Debug on fixed pitch test");
48 "Turn off dp fixed pitch algorithm");
50 "Do even faster pitch algorithm");
52 "Write full metric stuff");
53 EXTERN BOOL_VAR (textord_show_row_cuts, FALSE, "Draw row-level cuts");
54 EXTERN BOOL_VAR (textord_show_page_cuts, FALSE, "Draw page-level cuts");
56 "Use correct answer for fixed/prop");
58 "Attempt whole doc/block fixed pitch");
59 EXTERN double_VAR (textord_projection_scale, 0.200, "Ding rate for mid-cuts");
61 "Ding rate for unbalanced char cells");
62 
63 #define FIXED_WIDTH_MULTIPLE 5
64 #define BLOCK_STATS_CLUSTERS 10
65 #define MAX_ALLOWED_PITCH 100 //max pixel pitch.
66 
67 /**********************************************************************
68  * compute_fixed_pitch
69  *
70  * Decide whether each row is fixed pitch individually.
71  * Correlate definite and uncertain results to obtain an individual
72  * result for each row in the TO_ROW class.
73  **********************************************************************/
74 
75 void compute_fixed_pitch(ICOORD page_tr, // top right
76  TO_BLOCK_LIST *port_blocks, // input list
77  float gradient, // page skew
78  FCOORD rotation, // for drawing
79  BOOL8 testing_on) { // correct orientation
80  TO_BLOCK_IT block_it; //iterator
81  TO_BLOCK *block; //current block;
82  TO_ROW_IT row_it; //row iterator
83  TO_ROW *row; //current row
84  int block_index; //block number
85  int row_index; //row number
86 
87 #ifndef GRAPHICS_DISABLED
88  if (textord_show_initial_words && testing_on) {
89  if (to_win == NULL)
90  create_to_win(page_tr);
91  }
92 #endif
93 
94  block_it.set_to_list (port_blocks);
95  block_index = 1;
96  for (block_it.mark_cycle_pt (); !block_it.cycled_list ();
97  block_it.forward ()) {
98  block = block_it.data ();
99  compute_block_pitch(block, rotation, block_index, testing_on);
100  block_index++;
101  }
102 
103  if (!try_doc_fixed (page_tr, port_blocks, gradient)) {
104  block_index = 1;
105  for (block_it.mark_cycle_pt (); !block_it.cycled_list ();
106  block_it.forward ()) {
107  block = block_it.data ();
108  if (!try_block_fixed (block, block_index))
109  try_rows_fixed(block, block_index, testing_on);
110  block_index++;
111  }
112  }
113 
114  block_index = 1;
115  for (block_it.mark_cycle_pt(); !block_it.cycled_list();
116  block_it.forward()) {
117  block = block_it.data ();
118  POLY_BLOCK* pb = block->block->poly_block();
119  if (pb != NULL && !pb->IsText()) continue; // Non-text doesn't exist!
120  row_it.set_to_list (block->get_rows ());
121  row_index = 1;
122  for (row_it.mark_cycle_pt (); !row_it.cycled_list (); row_it.forward ()) {
123  row = row_it.data ();
124  fix_row_pitch(row, block, port_blocks, row_index, block_index);
125  row_index++;
126  }
127  block_index++;
128  }
129 #ifndef GRAPHICS_DISABLED
130  if (textord_show_initial_words && testing_on) {
132  }
133 #endif
134 }
135 
136 
137 /**********************************************************************
138  * fix_row_pitch
139  *
140  * Get a pitch_decision for this row by voting among similar rows in the
141  * block, then similar rows over all the page, or any other rows at all.
142  **********************************************************************/
143 
144 void fix_row_pitch(TO_ROW *bad_row, // row to fix
145  TO_BLOCK *bad_block, // block of bad_row
146  TO_BLOCK_LIST *blocks, // blocks to scan
147  inT32 row_target, // number of row
148  inT32 block_target) { // number of block
149  inT16 mid_cuts;
150  int block_votes; //votes in block
151  int like_votes; //votes over page
152  int other_votes; //votes of unlike blocks
153  int block_index; //number of block
154  int row_index; //number of row
155  int maxwidth; //max pitch
156  TO_BLOCK_IT block_it = blocks; //block iterator
157  TO_ROW_IT row_it;
158  TO_BLOCK *block; //current block
159  TO_ROW *row; //current row
160  float sp_sd; //space deviation
161  STATS block_stats; //pitches in block
162  STATS like_stats; //pitches in page
163 
164  block_votes = like_votes = other_votes = 0;
165  maxwidth = (inT32) ceil (bad_row->xheight * textord_words_maxspace);
166  if (bad_row->pitch_decision != PITCH_DEF_FIXED
167  && bad_row->pitch_decision != PITCH_DEF_PROP) {
168  block_stats.set_range (0, maxwidth);
169  like_stats.set_range (0, maxwidth);
170  block_index = 1;
171  for (block_it.mark_cycle_pt(); !block_it.cycled_list();
172  block_it.forward()) {
173  block = block_it.data();
174  POLY_BLOCK* pb = block->block->poly_block();
175  if (pb != NULL && !pb->IsText()) continue; // Non text doesn't exist!
176  row_index = 1;
177  row_it.set_to_list (block->get_rows ());
178  for (row_it.mark_cycle_pt (); !row_it.cycled_list ();
179  row_it.forward ()) {
180  row = row_it.data ();
181  if ((bad_row->all_caps
182  && row->xheight + row->ascrise
183  <
184  (bad_row->xheight + bad_row->ascrise) * (1 +
186  && row->xheight + row->ascrise >
187  (bad_row->xheight + bad_row->ascrise) * (1 -
189  || (!bad_row->all_caps
190  && row->xheight <
191  bad_row->xheight * (1 + textord_pitch_rowsimilarity)
192  && row->xheight >
193  bad_row->xheight * (1 - textord_pitch_rowsimilarity))) {
194  if (block_index == block_target) {
195  if (row->pitch_decision == PITCH_DEF_FIXED) {
196  block_votes += textord_words_veto_power;
197  block_stats.add ((inT32) row->fixed_pitch,
199  }
200  else if (row->pitch_decision == PITCH_MAYBE_FIXED
201  || row->pitch_decision == PITCH_CORR_FIXED) {
202  block_votes++;
203  block_stats.add ((inT32) row->fixed_pitch, 1);
204  }
205  else if (row->pitch_decision == PITCH_DEF_PROP)
206  block_votes -= textord_words_veto_power;
207  else if (row->pitch_decision == PITCH_MAYBE_PROP
208  || row->pitch_decision == PITCH_CORR_PROP)
209  block_votes--;
210  }
211  else {
212  if (row->pitch_decision == PITCH_DEF_FIXED) {
213  like_votes += textord_words_veto_power;
214  like_stats.add ((inT32) row->fixed_pitch,
216  }
217  else if (row->pitch_decision == PITCH_MAYBE_FIXED
218  || row->pitch_decision == PITCH_CORR_FIXED) {
219  like_votes++;
220  like_stats.add ((inT32) row->fixed_pitch, 1);
221  }
222  else if (row->pitch_decision == PITCH_DEF_PROP)
223  like_votes -= textord_words_veto_power;
224  else if (row->pitch_decision == PITCH_MAYBE_PROP
225  || row->pitch_decision == PITCH_CORR_PROP)
226  like_votes--;
227  }
228  }
229  else {
230  if (row->pitch_decision == PITCH_DEF_FIXED)
231  other_votes += textord_words_veto_power;
232  else if (row->pitch_decision == PITCH_MAYBE_FIXED
233  || row->pitch_decision == PITCH_CORR_FIXED)
234  other_votes++;
235  else if (row->pitch_decision == PITCH_DEF_PROP)
236  other_votes -= textord_words_veto_power;
237  else if (row->pitch_decision == PITCH_MAYBE_PROP
238  || row->pitch_decision == PITCH_CORR_PROP)
239  other_votes--;
240  }
241  row_index++;
242  }
243  block_index++;
244  }
245  if (block_votes > textord_words_veto_power) {
246  bad_row->fixed_pitch = block_stats.ile (0.5);
247  bad_row->pitch_decision = PITCH_CORR_FIXED;
248  }
249  else if (block_votes <= textord_words_veto_power && like_votes > 0) {
250  bad_row->fixed_pitch = like_stats.ile (0.5);
251  bad_row->pitch_decision = PITCH_CORR_FIXED;
252  }
253  else {
254  bad_row->pitch_decision = PITCH_CORR_PROP;
255  #ifndef SECURE_NAMES
256  if (block_votes == 0 && like_votes == 0 && other_votes > 0
258  tprintf
259  ("Warning:row %d of block %d set prop with no like rows against trend\n",
260  row_target, block_target);
261  #endif
262  }
263  }
265  tprintf(":b_votes=%d:l_votes=%d:o_votes=%d",
266  block_votes, like_votes, other_votes);
267  tprintf("x=%g:asc=%g\n", bad_row->xheight, bad_row->ascrise);
268  }
269  if (bad_row->pitch_decision == PITCH_CORR_FIXED) {
270  if (bad_row->fixed_pitch < textord_min_xheight) {
271  if (block_votes > 0)
272  bad_row->fixed_pitch = block_stats.ile (0.5);
273  else if (block_votes == 0 && like_votes > 0)
274  bad_row->fixed_pitch = like_stats.ile (0.5);
275  else {
276  tprintf
277  ("Warning:guessing pitch as xheight on row %d, block %d\n",
278  row_target, block_target);
279  bad_row->fixed_pitch = bad_row->xheight;
280  }
281  }
282  if (bad_row->fixed_pitch < textord_min_xheight)
283  bad_row->fixed_pitch = (float) textord_min_xheight;
284  bad_row->kern_size = bad_row->fixed_pitch / 4;
285  bad_row->min_space = (inT32) (bad_row->fixed_pitch * 0.6);
286  bad_row->max_nonspace = (inT32) (bad_row->fixed_pitch * 0.4);
287  bad_row->space_threshold =
288  (bad_row->min_space + bad_row->max_nonspace) / 2;
289  bad_row->space_size = bad_row->fixed_pitch;
290  if (bad_row->char_cells.empty ())
291  tune_row_pitch (bad_row, &bad_row->projection,
292  bad_row->projection_left, bad_row->projection_right,
293  (bad_row->fixed_pitch +
294  bad_row->max_nonspace * 3) / 4, bad_row->fixed_pitch,
295  sp_sd, mid_cuts, &bad_row->char_cells, FALSE);
296  }
297  else if (bad_row->pitch_decision == PITCH_CORR_PROP
298  || bad_row->pitch_decision == PITCH_DEF_PROP) {
299  bad_row->fixed_pitch = 0.0f;
300  bad_row->char_cells.clear ();
301  }
302 }
303 
304 
305 /**********************************************************************
306  * compute_block_pitch
307  *
308  * Decide whether each block is fixed pitch individually.
309  **********************************************************************/
310 
311 void compute_block_pitch(TO_BLOCK *block, // input list
312  FCOORD rotation, // for drawing
313  inT32 block_index, // block number
314  BOOL8 testing_on) { // correct orientation
315  TBOX block_box; //bounding box
316 
317  block_box = block->block->bounding_box ();
318  if (testing_on && textord_debug_pitch_test) {
319  tprintf ("Block %d at (%d,%d)->(%d,%d)\n",
320  block_index,
321  block_box.left (), block_box.bottom (),
322  block_box.right (), block_box.top ());
323  }
324  block->min_space = (inT32) floor (block->xheight
326  block->max_nonspace = (inT32) ceil (block->xheight
328  block->fixed_pitch = 0.0f;
329  block->space_size = (float) block->min_space;
330  block->kern_size = (float) block->max_nonspace;
331  block->pr_nonsp = block->xheight * words_default_prop_nonspace;
333  if (!block->get_rows ()->empty ()) {
334  ASSERT_HOST (block->xheight > 0);
335  find_repeated_chars(block, textord_show_initial_words && testing_on);
336 #ifndef GRAPHICS_DISABLED
337  if (textord_show_initial_words && testing_on)
338  //overlap_picture_ops(TRUE);
340 #endif
341  compute_rows_pitch(block,
342  block_index,
343  textord_debug_pitch_test &&testing_on);
344  }
345 }
346 
347 
348 /**********************************************************************
349  * compute_rows_pitch
350  *
351  * Decide whether each row is fixed pitch individually.
352  **********************************************************************/
353 
354 BOOL8 compute_rows_pitch( //find line stats
355  TO_BLOCK *block, //block to do
356  inT32 block_index, //block number
357  BOOL8 testing_on //correct orientation
358  ) {
359  inT32 maxwidth; //of spaces
360  TO_ROW *row; //current row
361  inT32 row_index; //row number.
362  float lower, upper; //cluster thresholds
363  TO_ROW_IT row_it = block->get_rows ();
364 
365  row_index = 1;
366  for (row_it.mark_cycle_pt (); !row_it.cycled_list (); row_it.forward ()) {
367  row = row_it.data ();
368  ASSERT_HOST (row->xheight > 0);
370  maxwidth = (inT32) ceil (row->xheight * textord_words_maxspace);
371  if (row_pitch_stats (row, maxwidth, testing_on)
372  && find_row_pitch (row, maxwidth,
373  textord_dotmatrix_gap + 1, block, block_index,
374  row_index, testing_on)) {
375  if (row->fixed_pitch == 0) {
376  lower = row->pr_nonsp;
377  upper = row->pr_space;
378  row->space_size = upper;
379  row->kern_size = lower;
380  }
381  }
382  else {
383  row->fixed_pitch = 0.0f; //insufficient data
385  }
386  row_index++;
387  }
388  return FALSE;
389 }
390 
391 
392 /**********************************************************************
393  * try_doc_fixed
394  *
395  * Attempt to call the entire document fixed pitch.
396  **********************************************************************/
397 
398 BOOL8 try_doc_fixed( //determine pitch
399  ICOORD page_tr, //top right
400  TO_BLOCK_LIST *port_blocks, //input list
401  float gradient //page skew
402  ) {
403  inT16 master_x; //uniform shifts
404  inT16 pitch; //median pitch.
405  int x; //profile coord
406  int prop_blocks; //correct counts
407  int fixed_blocks;
408  int total_row_count; //total in page
409  //iterator
410  TO_BLOCK_IT block_it = port_blocks;
411  TO_BLOCK *block; //current block;
412  TO_ROW_IT row_it; //row iterator
413  TO_ROW *row; //current row
414  inT16 projection_left; //edges
415  inT16 projection_right;
416  inT16 row_left; //edges of row
417  inT16 row_right;
418  ICOORDELT_LIST *master_cells; //cells for page
419  float master_y; //uniform shifts
420  float shift_factor; //page skew correction
421  float row_shift; //shift for row
422  float final_pitch; //output pitch
423  float row_y; //baseline
424  STATS projection; //entire page
425  STATS pitches (0, MAX_ALLOWED_PITCH);
426  //for median
427  float sp_sd; //space sd
428  inT16 mid_cuts; //no of cheap cuts
429  float pitch_sd; //sync rating
430 
431  if (block_it.empty ()
432  // || block_it.data()==block_it.data_relative(1)
434  return FALSE;
435  shift_factor = gradient / (gradient * gradient + 1);
436  row_it.set_to_list (block_it.data ()->get_rows ());
437  master_x = row_it.data ()->projection_left;
438  master_y = row_it.data ()->baseline.y (master_x);
439  projection_left = MAX_INT16;
440  projection_right = -MAX_INT16;
441  prop_blocks = 0;
442  fixed_blocks = 0;
443  total_row_count = 0;
444 
445  for (block_it.mark_cycle_pt (); !block_it.cycled_list ();
446  block_it.forward ()) {
447  block = block_it.data ();
448  row_it.set_to_list (block->get_rows ());
449  for (row_it.mark_cycle_pt (); !row_it.cycled_list (); row_it.forward ()) {
450  row = row_it.data ();
451  total_row_count++;
452  if (row->fixed_pitch > 0)
453  pitches.add ((inT32) (row->fixed_pitch), 1);
454  //find median
455  row_y = row->baseline.y (master_x);
456  row_left =
457  (inT16) (row->projection_left -
458  shift_factor * (master_y - row_y));
459  row_right =
460  (inT16) (row->projection_right -
461  shift_factor * (master_y - row_y));
462  if (row_left < projection_left)
463  projection_left = row_left;
464  if (row_right > projection_right)
465  projection_right = row_right;
466  }
467  }
468  if (pitches.get_total () == 0)
469  return FALSE;
470  projection.set_range (projection_left, projection_right);
471 
472  for (block_it.mark_cycle_pt (); !block_it.cycled_list ();
473  block_it.forward ()) {
474  block = block_it.data ();
475  row_it.set_to_list (block->get_rows ());
476  for (row_it.mark_cycle_pt (); !row_it.cycled_list (); row_it.forward ()) {
477  row = row_it.data ();
478  row_y = row->baseline.y (master_x);
479  row_left =
480  (inT16) (row->projection_left -
481  shift_factor * (master_y - row_y));
482  for (x = row->projection_left; x < row->projection_right;
483  x++, row_left++) {
484  projection.add (row_left, row->projection.pile_count (x));
485  }
486  }
487  }
488 
489  row_it.set_to_list (block_it.data ()->get_rows ());
490  row = row_it.data ();
491 #ifndef GRAPHICS_DISABLED
493  projection.plot (to_win, projection_left,
494  row->intercept (), 1.0f, -1.0f, ScrollView::CORAL);
495 #endif
496  final_pitch = pitches.ile (0.5);
497  pitch = (inT16) final_pitch;
498  pitch_sd =
499  tune_row_pitch (row, &projection, projection_left, projection_right,
500  pitch * 0.75, final_pitch, sp_sd, mid_cuts,
501  &row->char_cells, FALSE);
502 
504  tprintf
505  ("try_doc:props=%d:fixed=%d:pitch=%d:final_pitch=%g:pitch_sd=%g:sp_sd=%g:sd/trc=%g:sd/p=%g:sd/trc/p=%g\n",
506  prop_blocks, fixed_blocks, pitch, final_pitch, pitch_sd, sp_sd,
507  pitch_sd / total_row_count, pitch_sd / pitch,
508  pitch_sd / total_row_count / pitch);
509 
510 #ifndef GRAPHICS_DISABLED
511  if (textord_show_page_cuts && to_win != NULL) {
512  master_cells = &row->char_cells;
513  for (block_it.mark_cycle_pt (); !block_it.cycled_list ();
514  block_it.forward ()) {
515  block = block_it.data ();
516  row_it.set_to_list (block->get_rows ());
517  for (row_it.mark_cycle_pt (); !row_it.cycled_list ();
518  row_it.forward ()) {
519  row = row_it.data ();
520  row_y = row->baseline.y (master_x);
521  row_shift = shift_factor * (master_y - row_y);
522  plot_row_cells(to_win, ScrollView::GOLDENROD, row, row_shift, master_cells);
523  }
524  }
525  }
526 #endif
527  row->char_cells.clear ();
528  return FALSE;
529 }
530 
531 
532 /**********************************************************************
533  * try_block_fixed
534  *
535  * Try to call the entire block fixed.
536  **********************************************************************/
537 
538 BOOL8 try_block_fixed( //find line stats
539  TO_BLOCK *block, //block to do
540  inT32 block_index //block number
541  ) {
542  return FALSE;
543 }
544 
545 
546 /**********************************************************************
547  * try_rows_fixed
548  *
549  * Decide whether each row is fixed pitch individually.
550  **********************************************************************/
551 
552 BOOL8 try_rows_fixed( //find line stats
553  TO_BLOCK *block, //block to do
554  inT32 block_index, //block number
555  BOOL8 testing_on //correct orientation
556  ) {
557  inT32 maxwidth; //of spaces
558  TO_ROW *row; //current row
559  inT32 row_index; //row number.
560  inT32 def_fixed = 0; //counters
561  inT32 def_prop = 0;
562  inT32 maybe_fixed = 0;
563  inT32 maybe_prop = 0;
564  inT32 dunno = 0;
565  inT32 corr_fixed = 0;
566  inT32 corr_prop = 0;
567  float lower, upper; //cluster thresholds
568  TO_ROW_IT row_it = block->get_rows ();
569 
570  row_index = 1;
571  for (row_it.mark_cycle_pt (); !row_it.cycled_list (); row_it.forward ()) {
572  row = row_it.data ();
573  ASSERT_HOST (row->xheight > 0);
574  maxwidth = (inT32) ceil (row->xheight * textord_words_maxspace);
575  if (row->fixed_pitch > 0 &&
576  fixed_pitch_row(row, block->block, block_index)) {
577  if (row->fixed_pitch == 0) {
578  lower = row->pr_nonsp;
579  upper = row->pr_space;
580  row->space_size = upper;
581  row->kern_size = lower;
582  }
583  }
584  row_index++;
585  }
586  count_block_votes(block,
587  def_fixed,
588  def_prop,
589  maybe_fixed,
590  maybe_prop,
591  corr_fixed,
592  corr_prop,
593  dunno);
594  if (testing_on
597  tprintf ("Initially:");
598  print_block_counts(block, block_index);
599  }
600  if (def_fixed > def_prop * textord_words_veto_power)
602  else if (def_prop > def_fixed * textord_words_veto_power)
604  else if (def_fixed > 0 || def_prop > 0)
605  block->pitch_decision = PITCH_DUNNO;
606  else if (maybe_fixed > maybe_prop * textord_words_veto_power)
608  else if (maybe_prop > maybe_fixed * textord_words_veto_power)
610  else
611  block->pitch_decision = PITCH_DUNNO;
612  return FALSE;
613 }
614 
615 
616 /**********************************************************************
617  * print_block_counts
618  *
619  * Count up how many rows have what decision and print the results.
620  **********************************************************************/
621 
622 void print_block_counts( //find line stats
623  TO_BLOCK *block, //block to do
624  inT32 block_index //block number
625  ) {
626  inT32 def_fixed = 0; //counters
627  inT32 def_prop = 0;
628  inT32 maybe_fixed = 0;
629  inT32 maybe_prop = 0;
630  inT32 dunno = 0;
631  inT32 corr_fixed = 0;
632  inT32 corr_prop = 0;
633 
634  count_block_votes(block,
635  def_fixed,
636  def_prop,
637  maybe_fixed,
638  maybe_prop,
639  corr_fixed,
640  corr_prop,
641  dunno);
642  tprintf ("Block %d has (%d,%d,%d)",
643  block_index, def_fixed, maybe_fixed, corr_fixed);
644  if (textord_blocksall_prop && (def_fixed || maybe_fixed || corr_fixed))
645  tprintf (" (Wrongly)");
646  tprintf (" fixed, (%d,%d,%d)", def_prop, maybe_prop, corr_prop);
647  if (textord_blocksall_fixed && (def_prop || maybe_prop || corr_prop))
648  tprintf (" (Wrongly)");
649  tprintf (" prop, %d dunno\n", dunno);
650 }
651 
652 
653 /**********************************************************************
654  * count_block_votes
655  *
656  * Count the number of rows in the block with each kind of pitch_decision.
657  **********************************************************************/
658 
659 void count_block_votes( //find line stats
660  TO_BLOCK *block, //block to do
661  inT32 &def_fixed, //add to counts
662  inT32 &def_prop,
663  inT32 &maybe_fixed,
664  inT32 &maybe_prop,
665  inT32 &corr_fixed,
666  inT32 &corr_prop,
667  inT32 &dunno) {
668  TO_ROW *row; //current row
669  TO_ROW_IT row_it = block->get_rows ();
670 
671  for (row_it.mark_cycle_pt (); !row_it.cycled_list (); row_it.forward ()) {
672  row = row_it.data ();
673  switch (row->pitch_decision) {
674  case PITCH_DUNNO:
675  dunno++;
676  break;
677  case PITCH_DEF_PROP:
678  def_prop++;
679  break;
680  case PITCH_MAYBE_PROP:
681  maybe_prop++;
682  break;
683  case PITCH_DEF_FIXED:
684  def_fixed++;
685  break;
686  case PITCH_MAYBE_FIXED:
687  maybe_fixed++;
688  break;
689  case PITCH_CORR_PROP:
690  corr_prop++;
691  break;
692  case PITCH_CORR_FIXED:
693  corr_fixed++;
694  break;
695  }
696  }
697 }
698 
699 
700 /**********************************************************************
701  * row_pitch_stats
702  *
703  * Decide whether each row is fixed pitch individually.
704  **********************************************************************/
705 
706 BOOL8 row_pitch_stats( //find line stats
707  TO_ROW *row, //current row
708  inT32 maxwidth, //of spaces
709  BOOL8 testing_on //correct orientation
710  ) {
711  BLOBNBOX *blob; //current blob
712  int gap_index; //current gap
713  inT32 prev_x; //end of prev blob
714  inT32 cluster_count; //no of clusters
715  inT32 prev_count; //of clusters
716  inT32 smooth_factor; //for smoothing stats
717  TBOX blob_box; //bounding box
718  float lower, upper; //cluster thresholds
719  //gap sizes
720  float gaps[BLOCK_STATS_CLUSTERS];
721  //blobs
722  BLOBNBOX_IT blob_it = row->blob_list ();
723  STATS gap_stats (0, maxwidth);
724  STATS cluster_stats[BLOCK_STATS_CLUSTERS + 1];
725  //clusters
726 
727  smooth_factor =
729  if (!blob_it.empty ()) {
730  prev_x = blob_it.data ()->bounding_box ().right ();
731  blob_it.forward ();
732  while (!blob_it.at_first ()) {
733  blob = blob_it.data ();
734  if (!blob->joined_to_prev ()) {
735  blob_box = blob->bounding_box ();
736  if (blob_box.left () - prev_x < maxwidth)
737  gap_stats.add (blob_box.left () - prev_x, 1);
738  prev_x = blob_box.right ();
739  }
740  blob_it.forward ();
741  }
742  }
743  if (gap_stats.get_total () == 0) {
744  return FALSE;
745  }
746  cluster_count = 0;
747  lower = row->xheight * words_initial_lower;
748  upper = row->xheight * words_initial_upper;
749  gap_stats.smooth (smooth_factor);
750  do {
751  prev_count = cluster_count;
752  cluster_count = gap_stats.cluster (lower, upper,
754  BLOCK_STATS_CLUSTERS, cluster_stats);
755  }
756  while (cluster_count > prev_count && cluster_count < BLOCK_STATS_CLUSTERS);
757  if (cluster_count < 1) {
758  return FALSE;
759  }
760  for (gap_index = 0; gap_index < cluster_count; gap_index++)
761  gaps[gap_index] = cluster_stats[gap_index + 1].ile (0.5);
762  //get medians
763  if (testing_on) {
764  tprintf ("cluster_count=%d:", cluster_count);
765  for (gap_index = 0; gap_index < cluster_count; gap_index++)
766  tprintf (" %g(%d)", gaps[gap_index],
767  cluster_stats[gap_index + 1].get_total ());
768  tprintf ("\n");
769  }
770  qsort (gaps, cluster_count, sizeof (float), sort_floats);
771 
772  //Try to find proportional non-space and space for row.
773  lower = row->xheight * words_default_prop_nonspace;
774  upper = row->xheight * textord_words_min_minspace;
775  for (gap_index = 0; gap_index < cluster_count
776  && gaps[gap_index] < lower; gap_index++);
777  if (gap_index == 0) {
778  if (testing_on)
779  tprintf ("No clusters below nonspace threshold!!\n");
780  if (cluster_count > 1) {
781  row->pr_nonsp = gaps[0];
782  row->pr_space = gaps[1];
783  }
784  else {
785  row->pr_nonsp = lower;
786  row->pr_space = gaps[0];
787  }
788  }
789  else {
790  row->pr_nonsp = gaps[gap_index - 1];
791  while (gap_index < cluster_count && gaps[gap_index] < upper)
792  gap_index++;
793  if (gap_index == cluster_count) {
794  if (testing_on)
795  tprintf ("No clusters above nonspace threshold!!\n");
796  row->pr_space = lower * textord_spacesize_ratioprop;
797  }
798  else
799  row->pr_space = gaps[gap_index];
800  }
801 
802  //Now try to find the fixed pitch space and non-space.
803  upper = row->xheight * words_default_fixed_space;
804  for (gap_index = 0; gap_index < cluster_count
805  && gaps[gap_index] < upper; gap_index++);
806  if (gap_index == 0) {
807  if (testing_on)
808  tprintf ("No clusters below space threshold!!\n");
809  row->fp_nonsp = upper;
810  row->fp_space = gaps[0];
811  }
812  else {
813  row->fp_nonsp = gaps[gap_index - 1];
814  if (gap_index == cluster_count) {
815  if (testing_on)
816  tprintf ("No clusters above space threshold!!\n");
817  row->fp_space = row->xheight;
818  }
819  else
820  row->fp_space = gaps[gap_index];
821  }
822  if (testing_on) {
823  tprintf
824  ("Initial estimates:pr_nonsp=%g, pr_space=%g, fp_nonsp=%g, fp_space=%g\n",
825  row->pr_nonsp, row->pr_space, row->fp_nonsp, row->fp_space);
826  }
827  return TRUE; //computed some stats
828 }
829 
830 
831 /**********************************************************************
832  * find_row_pitch
833  *
834  * Check to see if this row could be fixed pitch using the given spacings.
835  * Blobs with gaps smaller than the lower threshold are assumed to be one.
836  * The larger threshold is the word gap threshold.
837  **********************************************************************/
838 
839 BOOL8 find_row_pitch( //find lines
840  TO_ROW *row, //row to do
841  inT32 maxwidth, //max permitted space
842  inT32 dm_gap, //ignorable gaps
843  TO_BLOCK *block, //block of row
844  inT32 block_index, //block_number
845  inT32 row_index, //number of row
846  BOOL8 testing_on //correct orientation
847  ) {
848  BOOL8 used_dm_model; //looks lik dot matrix
849  float min_space; //estimate threshold
850  float non_space; //gap size
851  float gap_iqr; //interquartile range
852  float pitch_iqr;
853  float dm_gap_iqr; //interquartile range
854  float dm_pitch_iqr;
855  float dm_pitch; //pitch with dm on
856  float pitch; //revised estimate
857  float initial_pitch; //guess at pitch
858  STATS gap_stats (0, maxwidth);
859  //centre-centre
860  STATS pitch_stats (0, maxwidth);
861 
862  row->fixed_pitch = 0.0f;
863  initial_pitch = row->fp_space;
864  if (initial_pitch > row->xheight * (1 + words_default_fixed_limit))
865  initial_pitch = row->xheight;//keep pitch decent
866  non_space = row->fp_nonsp;
867  if (non_space > initial_pitch)
868  non_space = initial_pitch;
869  min_space = (initial_pitch + non_space) / 2;
870 
871  if (!count_pitch_stats (row, &gap_stats, &pitch_stats,
872  initial_pitch, min_space, TRUE, FALSE, dm_gap)) {
873  dm_gap_iqr = 0.0001;
874  dm_pitch_iqr = maxwidth * 2.0f;
875  dm_pitch = initial_pitch;
876  }
877  else {
878  dm_gap_iqr = gap_stats.ile (0.75) - gap_stats.ile (0.25);
879  dm_pitch_iqr = pitch_stats.ile (0.75) - pitch_stats.ile (0.25);
880  dm_pitch = pitch_stats.ile (0.5);
881  }
882  gap_stats.clear ();
883  pitch_stats.clear ();
884  if (!count_pitch_stats (row, &gap_stats, &pitch_stats,
885  initial_pitch, min_space, TRUE, FALSE, 0)) {
886  gap_iqr = 0.0001;
887  pitch_iqr = maxwidth * 3.0f;
888  }
889  else {
890  gap_iqr = gap_stats.ile (0.75) - gap_stats.ile (0.25);
891  pitch_iqr = pitch_stats.ile (0.75) - pitch_stats.ile (0.25);
892  if (testing_on)
893  tprintf
894  ("First fp iteration:initial_pitch=%g, gap_iqr=%g, pitch_iqr=%g, pitch=%g\n",
895  initial_pitch, gap_iqr, pitch_iqr, pitch_stats.ile (0.5));
896  initial_pitch = pitch_stats.ile (0.5);
897  if (min_space > initial_pitch
898  && count_pitch_stats (row, &gap_stats, &pitch_stats,
899  initial_pitch, initial_pitch, TRUE, FALSE, 0)) {
900  min_space = initial_pitch;
901  gap_iqr = gap_stats.ile (0.75) - gap_stats.ile (0.25);
902  pitch_iqr = pitch_stats.ile (0.75) - pitch_stats.ile (0.25);
903  if (testing_on)
904  tprintf
905  ("Revised fp iteration:initial_pitch=%g, gap_iqr=%g, pitch_iqr=%g, pitch=%g\n",
906  initial_pitch, gap_iqr, pitch_iqr, pitch_stats.ile (0.5));
907  initial_pitch = pitch_stats.ile (0.5);
908  }
909  }
911  tprintf("Blk=%d:Row=%d:%c:p_iqr=%g:g_iqr=%g:dm_p_iqr=%g:dm_g_iqr=%g:%c:",
912  block_index, row_index, 'X',
913  pitch_iqr, gap_iqr, dm_pitch_iqr, dm_gap_iqr,
914  pitch_iqr > maxwidth && dm_pitch_iqr > maxwidth ? 'D' :
915  (pitch_iqr * dm_gap_iqr <= dm_pitch_iqr * gap_iqr ? 'S' : 'M'));
916  if (pitch_iqr > maxwidth && dm_pitch_iqr > maxwidth) {
919  tprintf ("\n");
920  return FALSE; //insufficient data
921  }
922  if (pitch_iqr * dm_gap_iqr <= dm_pitch_iqr * gap_iqr) {
923  if (testing_on)
924  tprintf
925  ("Choosing non dm version:pitch_iqr=%g, gap_iqr=%g, dm_pitch_iqr=%g, dm_gap_iqr=%g\n",
926  pitch_iqr, gap_iqr, dm_pitch_iqr, dm_gap_iqr);
927  gap_iqr = gap_stats.ile (0.75) - gap_stats.ile (0.25);
928  pitch_iqr = pitch_stats.ile (0.75) - pitch_stats.ile (0.25);
929  pitch = pitch_stats.ile (0.5);
930  used_dm_model = FALSE;
931  }
932  else {
933  if (testing_on)
934  tprintf
935  ("Choosing dm version:pitch_iqr=%g, gap_iqr=%g, dm_pitch_iqr=%g, dm_gap_iqr=%g\n",
936  pitch_iqr, gap_iqr, dm_pitch_iqr, dm_gap_iqr);
937  gap_iqr = dm_gap_iqr;
938  pitch_iqr = dm_pitch_iqr;
939  pitch = dm_pitch;
940  used_dm_model = TRUE;
941  }
943  tprintf ("rev_p_iqr=%g:rev_g_iqr=%g:pitch=%g:",
944  pitch_iqr, gap_iqr, pitch);
945  tprintf ("p_iqr/g=%g:p_iqr/x=%g:iqr_res=%c:",
946  pitch_iqr / gap_iqr, pitch_iqr / block->xheight,
947  pitch_iqr < gap_iqr * textord_fpiqr_ratio
948  && pitch_iqr < block->xheight * textord_max_pitch_iqr
949  && pitch < block->xheight * textord_words_default_maxspace
950  ? 'F' : 'P');
951  }
952  if (pitch_iqr < gap_iqr * textord_fpiqr_ratio
953  && pitch_iqr < block->xheight * textord_max_pitch_iqr
954  && pitch < block->xheight * textord_words_default_maxspace)
956  else
958  row->fixed_pitch = pitch;
959  row->kern_size = gap_stats.ile (0.5);
960  row->min_space = (inT32) (row->fixed_pitch + non_space) / 2;
961  if (row->min_space > row->fixed_pitch)
962  row->min_space = (inT32) row->fixed_pitch;
963  row->max_nonspace = row->min_space;
964  row->space_size = row->fixed_pitch;
965  row->space_threshold = (row->max_nonspace + row->min_space) / 2;
966  row->used_dm_model = used_dm_model;
967  return TRUE;
968 }
969 
970 
971 /**********************************************************************
972  * fixed_pitch_row
973  *
974  * Check to see if this row could be fixed pitch using the given spacings.
975  * Blobs with gaps smaller than the lower threshold are assumed to be one.
976  * The larger threshold is the word gap threshold.
977  **********************************************************************/
978 
979 BOOL8 fixed_pitch_row(TO_ROW *row, // row to do
980  BLOCK* block,
981  inT32 block_index // block_number
982  ) {
983  const char *res_string; //pitch result
984  inT16 mid_cuts; //no of cheap cuts
985  float non_space; //gap size
986  float pitch_sd; //error on pitch
987  float sp_sd; //space sd
988 
989  non_space = row->fp_nonsp;
990  if (non_space > row->fixed_pitch)
991  non_space = row->fixed_pitch;
992  POLY_BLOCK* pb = block != NULL ? block->poly_block() : NULL;
993  if (textord_all_prop || (pb != NULL && !pb->IsText())) {
994  // Set the decision to definitely proportional.
995  pitch_sd = textord_words_def_prop * row->fixed_pitch;
997  } else {
998  pitch_sd = tune_row_pitch (row, &row->projection, row->projection_left,
999  row->projection_right,
1000  (row->fixed_pitch + non_space * 3) / 4,
1001  row->fixed_pitch, sp_sd, mid_cuts,
1002  &row->char_cells,
1003  block_index == textord_debug_block);
1004  if (pitch_sd < textord_words_pitchsd_threshold * row->fixed_pitch
1005  && ((pitsync_linear_version & 3) < 3
1006  || ((pitsync_linear_version & 3) >= 3 && (row->used_dm_model
1007  || sp_sd > 20
1008  || (pitch_sd == 0 && sp_sd > 10))))) {
1009  if (pitch_sd < textord_words_def_fixed * row->fixed_pitch
1010  && !row->all_caps
1011  && ((pitsync_linear_version & 3) < 3 || sp_sd > 20))
1013  else
1015  }
1016  else if ((pitsync_linear_version & 3) < 3
1017  || sp_sd > 20
1018  || mid_cuts > 0
1019  || pitch_sd >= textord_words_pitchsd_threshold * row->fixed_pitch) {
1020  if (pitch_sd < textord_words_def_prop * row->fixed_pitch)
1022  else
1024  }
1025  else
1026  row->pitch_decision = PITCH_DUNNO;
1027  }
1028 
1030  res_string = "??";
1031  switch (row->pitch_decision) {
1032  case PITCH_DEF_PROP:
1033  res_string = "DP";
1034  break;
1035  case PITCH_MAYBE_PROP:
1036  res_string = "MP";
1037  break;
1038  case PITCH_DEF_FIXED:
1039  res_string = "DF";
1040  break;
1041  case PITCH_MAYBE_FIXED:
1042  res_string = "MF";
1043  default:
1044  res_string = "??";
1045  }
1046  tprintf (":sd/p=%g:occ=%g:init_res=%s\n",
1047  pitch_sd / row->fixed_pitch, sp_sd, res_string);
1048  }
1049  return TRUE;
1050 }
1051 
1052 
1053 /**********************************************************************
1054  * count_pitch_stats
1055  *
1056  * Count up the gap and pitch stats on the block to see if it is fixed pitch.
1057  * Blobs with gaps smaller than the lower threshold are assumed to be one.
1058  * The larger threshold is the word gap threshold.
1059  * The return value indicates whether there were any decent values to use.
1060  **********************************************************************/
1061 
1063  TO_ROW *row, //row to do
1064  STATS *gap_stats, //blob gaps
1065  STATS *pitch_stats, //centre-centre stats
1066  float initial_pitch, //guess at pitch
1067  float min_space, //estimate space size
1068  BOOL8 ignore_outsize, //discard big objects
1069  BOOL8 split_outsize, //split big objects
1070  inT32 dm_gap //ignorable gaps
1071  ) {
1072  BOOL8 prev_valid; //not word broken
1073  BLOBNBOX *blob; //current blob
1074  //blobs
1075  BLOBNBOX_IT blob_it = row->blob_list ();
1076  inT32 prev_right; //end of prev blob
1077  inT32 prev_centre; //centre of previous blob
1078  inT32 x_centre; //centre of this blob
1079  inT32 blob_width; //width of blob
1080  inT32 width_units; //no of widths in blob
1081  float width; //blob width
1082  TBOX blob_box; //bounding box
1083  TBOX joined_box; //of super blob
1084 
1085  gap_stats->clear ();
1086  pitch_stats->clear ();
1087  if (blob_it.empty ())
1088  return FALSE;
1089  prev_valid = FALSE;
1090  prev_centre = 0;
1091  prev_right = 0; //stop complier warning
1092  joined_box = blob_it.data ()->bounding_box ();
1093  do {
1094  blob_it.forward ();
1095  blob = blob_it.data ();
1096  if (!blob->joined_to_prev ()) {
1097  blob_box = blob->bounding_box ();
1098  if ((blob_box.left () - joined_box.right () < dm_gap
1099  && !blob_it.at_first ())
1100  || blob->cblob() == NULL)
1101  joined_box += blob_box; //merge blobs
1102  else {
1103  blob_width = joined_box.width ();
1104  if (split_outsize) {
1105  width_units =
1106  (inT32) floor ((float) blob_width / initial_pitch + 0.5);
1107  if (width_units < 1)
1108  width_units = 1;
1109  width_units--;
1110  }
1111  else if (ignore_outsize) {
1112  width = (float) blob_width / initial_pitch;
1113  width_units = width < 1 + words_default_fixed_limit
1114  && width > 1 - words_default_fixed_limit ? 0 : -1;
1115  }
1116  else
1117  width_units = 0; //everything in
1118  x_centre = (inT32) (joined_box.left ()
1119  + (blob_width -
1120  width_units * initial_pitch) / 2);
1121  if (prev_valid && width_units >= 0) {
1122  // if (width_units>0)
1123  // {
1124  // tprintf("wu=%d, width=%d, xc=%d, adding %d\n",
1125  // width_units,blob_width,x_centre,x_centre-prev_centre);
1126  // }
1127  gap_stats->add (joined_box.left () - prev_right, 1);
1128  pitch_stats->add (x_centre - prev_centre, 1);
1129  }
1130  prev_centre = (inT32) (x_centre + width_units * initial_pitch);
1131  prev_right = joined_box.right ();
1132  prev_valid = blob_box.left () - joined_box.right () < min_space;
1133  prev_valid = prev_valid && width_units >= 0;
1134  joined_box = blob_box;
1135  }
1136  }
1137  }
1138  while (!blob_it.at_first ());
1139  return gap_stats->get_total () >= 3;
1140 }
1141 
1142 
1143 /**********************************************************************
1144  * tune_row_pitch
1145  *
1146  * Use a dp algorithm to fit the character cells and return the sd of
1147  * the cell size over the row.
1148  **********************************************************************/
1149 
1150 float tune_row_pitch( //find fp cells
1151  TO_ROW *row, //row to do
1152  STATS *projection, //vertical projection
1153  inT16 projection_left, //edge of projection
1154  inT16 projection_right, //edge of projection
1155  float space_size, //size of blank
1156  float &initial_pitch, //guess at pitch
1157  float &best_sp_sd, //space sd
1158  inT16 &best_mid_cuts, //no of cheap cuts
1159  ICOORDELT_LIST *best_cells, //row cells
1160  BOOL8 testing_on //inidividual words
1161  ) {
1162  int pitch_delta; //offset pitch
1163  inT16 mid_cuts; //cheap cuts
1164  float pitch_sd; //current sd
1165  float best_sd; //best result
1166  float best_pitch; //pitch for best result
1167  float initial_sd; //starting error
1168  float sp_sd; //space sd
1169  ICOORDELT_LIST test_cells; //row cells
1170  ICOORDELT_IT best_it; //start of best list
1171 
1173  return tune_row_pitch2 (row, projection, projection_left,
1174  projection_right, space_size, initial_pitch,
1175  best_sp_sd,
1176  //space sd
1177  best_mid_cuts, best_cells, testing_on);
1179  best_sp_sd = initial_pitch;
1180  return initial_pitch;
1181  }
1182  initial_sd =
1183  compute_pitch_sd(row,
1184  projection,
1185  projection_left,
1186  projection_right,
1187  space_size,
1188  initial_pitch,
1189  best_sp_sd,
1190  best_mid_cuts,
1191  best_cells,
1192  testing_on);
1193  best_sd = initial_sd;
1194  best_pitch = initial_pitch;
1195  if (testing_on)
1196  tprintf ("tune_row_pitch:start pitch=%g, sd=%g\n", best_pitch, best_sd);
1197  for (pitch_delta = 1; pitch_delta <= textord_pitch_range; pitch_delta++) {
1198  pitch_sd =
1199  compute_pitch_sd (row, projection, projection_left, projection_right,
1200  space_size, initial_pitch + pitch_delta, sp_sd,
1201  mid_cuts, &test_cells, testing_on);
1202  if (testing_on)
1203  tprintf ("testing pitch at %g, sd=%g\n", initial_pitch + pitch_delta,
1204  pitch_sd);
1205  if (pitch_sd < best_sd) {
1206  best_sd = pitch_sd;
1207  best_mid_cuts = mid_cuts;
1208  best_sp_sd = sp_sd;
1209  best_pitch = initial_pitch + pitch_delta;
1210  best_cells->clear ();
1211  best_it.set_to_list (best_cells);
1212  best_it.add_list_after (&test_cells);
1213  }
1214  else
1215  test_cells.clear ();
1216  if (pitch_sd > initial_sd)
1217  break; //getting worse
1218  }
1219  for (pitch_delta = 1; pitch_delta <= textord_pitch_range; pitch_delta++) {
1220  pitch_sd =
1221  compute_pitch_sd (row, projection, projection_left, projection_right,
1222  space_size, initial_pitch - pitch_delta, sp_sd,
1223  mid_cuts, &test_cells, testing_on);
1224  if (testing_on)
1225  tprintf ("testing pitch at %g, sd=%g\n", initial_pitch - pitch_delta,
1226  pitch_sd);
1227  if (pitch_sd < best_sd) {
1228  best_sd = pitch_sd;
1229  best_mid_cuts = mid_cuts;
1230  best_sp_sd = sp_sd;
1231  best_pitch = initial_pitch - pitch_delta;
1232  best_cells->clear ();
1233  best_it.set_to_list (best_cells);
1234  best_it.add_list_after (&test_cells);
1235  }
1236  else
1237  test_cells.clear ();
1238  if (pitch_sd > initial_sd)
1239  break;
1240  }
1241  initial_pitch = best_pitch;
1242 
1244  print_pitch_sd(row,
1245  projection,
1246  projection_left,
1247  projection_right,
1248  space_size,
1249  best_pitch);
1250 
1251  return best_sd;
1252 }
1253 
1254 
1255 /**********************************************************************
1256  * tune_row_pitch
1257  *
1258  * Use a dp algorithm to fit the character cells and return the sd of
1259  * the cell size over the row.
1260  **********************************************************************/
1261 
1262 float tune_row_pitch2( //find fp cells
1263  TO_ROW *row, //row to do
1264  STATS *projection, //vertical projection
1265  inT16 projection_left, //edge of projection
1266  inT16 projection_right, //edge of projection
1267  float space_size, //size of blank
1268  float &initial_pitch, //guess at pitch
1269  float &best_sp_sd, //space sd
1270  inT16 &best_mid_cuts, //no of cheap cuts
1271  ICOORDELT_LIST *best_cells, //row cells
1272  BOOL8 testing_on //inidividual words
1273  ) {
1274  int pitch_delta; //offset pitch
1275  inT16 pixel; //pixel coord
1276  inT16 best_pixel; //pixel coord
1277  inT16 best_delta; //best pitch
1278  inT16 best_pitch; //best pitch
1279  inT16 start; //of good range
1280  inT16 end; //of good range
1281  inT32 best_count; //lowest sum
1282  float best_sd; //best result
1283  STATS *sum_proj; //summed projection
1284 
1285  best_sp_sd = initial_pitch;
1286 
1288  return initial_pitch;
1289  }
1290  sum_proj = new STATS[textord_pitch_range * 2 + 1];
1291  if (sum_proj == NULL)
1292  return initial_pitch;
1293  best_pitch = (inT32) initial_pitch;
1294 
1295  for (pitch_delta = -textord_pitch_range; pitch_delta <= textord_pitch_range;
1296  pitch_delta++)
1297  sum_proj[textord_pitch_range + pitch_delta].set_range (0,
1298  best_pitch +
1299  pitch_delta + 1);
1300  for (pixel = projection_left; pixel <= projection_right; pixel++) {
1301  for (pitch_delta = -textord_pitch_range;
1302  pitch_delta <= textord_pitch_range; pitch_delta++)
1303  sum_proj[textord_pitch_range +
1304  pitch_delta].add ((pixel - projection_left) % (best_pitch +
1305  pitch_delta),
1306  projection->pile_count (pixel));
1307  }
1308  best_count = sum_proj[textord_pitch_range].pile_count (0);
1309  best_delta = 0;
1310  best_pixel = 0;
1311  for (pitch_delta = -textord_pitch_range; pitch_delta <= textord_pitch_range;
1312  pitch_delta++) {
1313  for (pixel = 0; pixel < best_pitch + pitch_delta; pixel++) {
1314  if (sum_proj[textord_pitch_range + pitch_delta].pile_count (pixel)
1315  < best_count) {
1316  best_count =
1317  sum_proj[textord_pitch_range +
1318  pitch_delta].pile_count (pixel);
1319  best_delta = pitch_delta;
1320  best_pixel = pixel;
1321  }
1322  }
1323  }
1324  if (testing_on)
1325  tprintf ("tune_row_pitch:start pitch=%g, best_delta=%d, count=%d\n",
1326  initial_pitch, best_delta, best_count);
1327  best_pitch += best_delta;
1328  initial_pitch = best_pitch;
1329  best_count++;
1330  best_count += best_count;
1331  for (start = best_pixel - 2; start > best_pixel - best_pitch
1332  && sum_proj[textord_pitch_range +
1333  best_delta].pile_count (start % best_pitch) <= best_count;
1334  start--);
1335  for (end = best_pixel + 2;
1336  end < best_pixel + best_pitch
1337  && sum_proj[textord_pitch_range +
1338  best_delta].pile_count (end % best_pitch) <= best_count;
1339  end++);
1340 
1341  best_sd =
1342  compute_pitch_sd(row,
1343  projection,
1344  projection_left,
1345  projection_right,
1346  space_size,
1347  initial_pitch,
1348  best_sp_sd,
1349  best_mid_cuts,
1350  best_cells,
1351  testing_on,
1352  start,
1353  end);
1354  if (testing_on)
1355  tprintf ("tune_row_pitch:output pitch=%g, sd=%g\n", initial_pitch,
1356  best_sd);
1357 
1359  print_pitch_sd(row,
1360  projection,
1361  projection_left,
1362  projection_right,
1363  space_size,
1364  initial_pitch);
1365 
1366  delete[]sum_proj;
1367 
1368  return best_sd;
1369 }
1370 
1371 
1372 /**********************************************************************
1373  * compute_pitch_sd
1374  *
1375  * Use a dp algorithm to fit the character cells and return the sd of
1376  * the cell size over the row.
1377  **********************************************************************/
1378 
1379 float compute_pitch_sd( //find fp cells
1380  TO_ROW *row, //row to do
1381  STATS *projection, //vertical projection
1382  inT16 projection_left, //edge
1383  inT16 projection_right, //edge
1384  float space_size, //size of blank
1385  float initial_pitch, //guess at pitch
1386  float &sp_sd, //space sd
1387  inT16 &mid_cuts, //no of free cuts
1388  ICOORDELT_LIST *row_cells, //list of chop pts
1389  BOOL8 testing_on, //inidividual words
1390  inT16 start, //start of good range
1391  inT16 end //end of good range
1392  ) {
1393  inT16 occupation; //no of cells in word.
1394  //blobs
1395  BLOBNBOX_IT blob_it = row->blob_list ();
1396  BLOBNBOX_IT start_it; //start of word
1397  BLOBNBOX_IT plot_it; //for plotting
1398  inT16 blob_count; //no of blobs
1399  TBOX blob_box; //bounding box
1400  TBOX prev_box; //of super blob
1401  inT32 prev_right; //of word sync
1402  int scale_factor; //on scores for big words
1403  inT32 sp_count; //spaces
1404  FPSEGPT_LIST seg_list; //char cells
1405  FPSEGPT_IT seg_it; //iterator
1406  inT16 segpos; //position of segment
1407  inT16 cellpos; //previous cell boundary
1408  //iterator
1409  ICOORDELT_IT cell_it = row_cells;
1410  ICOORDELT *cell; //new cell
1411  double sqsum; //sum of squares
1412  double spsum; //of spaces
1413  double sp_var; //space error
1414  double word_sync; //result for word
1415  inT32 total_count; //total blobs
1416 
1417  if ((pitsync_linear_version & 3) > 1) {
1418  word_sync = compute_pitch_sd2 (row, projection, projection_left,
1419  projection_right, initial_pitch,
1420  occupation, mid_cuts, row_cells,
1421  testing_on, start, end);
1422  sp_sd = occupation;
1423  return word_sync;
1424  }
1425  mid_cuts = 0;
1426  cellpos = 0;
1427  total_count = 0;
1428  sqsum = 0;
1429  sp_count = 0;
1430  spsum = 0;
1431  prev_right = -1;
1432  if (blob_it.empty ())
1433  return space_size * 10;
1434 #ifndef GRAPHICS_DISABLED
1435  if (testing_on && to_win > 0) {
1436  blob_box = blob_it.data ()->bounding_box ();
1437  projection->plot (to_win, projection_left,
1438  row->intercept (), 1.0f, -1.0f, ScrollView::CORAL);
1439  }
1440 #endif
1441  start_it = blob_it;
1442  blob_count = 0;
1443  blob_box = box_next (&blob_it);//first blob
1444  blob_it.mark_cycle_pt ();
1445  do {
1446  for (; blob_count > 0; blob_count--)
1447  box_next(&start_it);
1448  do {
1449  prev_box = blob_box;
1450  blob_count++;
1451  blob_box = box_next (&blob_it);
1452  }
1453  while (!blob_it.cycled_list ()
1454  && blob_box.left () - prev_box.right () < space_size);
1455  plot_it = start_it;
1456  if (pitsync_linear_version & 3)
1457  word_sync =
1458  check_pitch_sync2 (&start_it, blob_count, (inT16) initial_pitch, 2,
1459  projection, projection_left, projection_right,
1461  occupation, &seg_list, start, end);
1462  else
1463  word_sync =
1464  check_pitch_sync (&start_it, blob_count, (inT16) initial_pitch, 2,
1465  projection, &seg_list);
1466  if (testing_on) {
1467  tprintf ("Word ending at (%d,%d), len=%d, sync rating=%g, ",
1468  prev_box.right (), prev_box.top (),
1469  seg_list.length () - 1, word_sync);
1470  seg_it.set_to_list (&seg_list);
1471  for (seg_it.mark_cycle_pt (); !seg_it.cycled_list ();
1472  seg_it.forward ()) {
1473  if (seg_it.data ()->faked)
1474  tprintf ("(F)");
1475  tprintf ("%d, ", seg_it.data ()->position ());
1476  // tprintf("C=%g, s=%g, sq=%g\n",
1477  // seg_it.data()->cost_function(),
1478  // seg_it.data()->sum(),
1479  // seg_it.data()->squares());
1480  }
1481  tprintf ("\n");
1482  }
1483 #ifndef GRAPHICS_DISABLED
1484  if (textord_show_fixed_cuts && blob_count > 0 && to_win > 0)
1485  plot_fp_cells2(to_win, ScrollView::GOLDENROD, row, &seg_list);
1486 #endif
1487  seg_it.set_to_list (&seg_list);
1488  if (prev_right >= 0) {
1489  sp_var = seg_it.data ()->position () - prev_right;
1490  sp_var -= floor (sp_var / initial_pitch + 0.5) * initial_pitch;
1491  sp_var *= sp_var;
1492  spsum += sp_var;
1493  sp_count++;
1494  }
1495  for (seg_it.mark_cycle_pt (); !seg_it.cycled_list (); seg_it.forward ()) {
1496  segpos = seg_it.data ()->position ();
1497  if (cell_it.empty () || segpos > cellpos + initial_pitch / 2) {
1498  //big gap
1499  while (!cell_it.empty () && segpos > cellpos + initial_pitch * 3 / 2) {
1500  cell = new ICOORDELT (cellpos + (inT16) initial_pitch, 0);
1501  cell_it.add_after_then_move (cell);
1502  cellpos += (inT16) initial_pitch;
1503  }
1504  //make new one
1505  cell = new ICOORDELT (segpos, 0);
1506  cell_it.add_after_then_move (cell);
1507  cellpos = segpos;
1508  }
1509  else if (segpos > cellpos - initial_pitch / 2) {
1510  cell = cell_it.data ();
1511  //average positions
1512  cell->set_x ((cellpos + segpos) / 2);
1513  cellpos = cell->x ();
1514  }
1515  }
1516  seg_it.move_to_last ();
1517  prev_right = seg_it.data ()->position ();
1519  scale_factor = (seg_list.length () - 2) / 2;
1520  if (scale_factor < 1)
1521  scale_factor = 1;
1522  }
1523  else
1524  scale_factor = 1;
1525  sqsum += word_sync * scale_factor;
1526  total_count += (seg_list.length () - 1) * scale_factor;
1527  seg_list.clear ();
1528  }
1529  while (!blob_it.cycled_list ());
1530  sp_sd = sp_count > 0 ? sqrt (spsum / sp_count) : 0;
1531  return total_count > 0 ? sqrt (sqsum / total_count) : space_size * 10;
1532 }
1533 
1534 
1535 /**********************************************************************
1536  * compute_pitch_sd2
1537  *
1538  * Use a dp algorithm to fit the character cells and return the sd of
1539  * the cell size over the row.
1540  **********************************************************************/
1541 
1542 float compute_pitch_sd2( //find fp cells
1543  TO_ROW *row, //row to do
1544  STATS *projection, //vertical projection
1545  inT16 projection_left, //edge
1546  inT16 projection_right, //edge
1547  float initial_pitch, //guess at pitch
1548  inT16 &occupation, //no of occupied cells
1549  inT16 &mid_cuts, //no of free cuts
1550  ICOORDELT_LIST *row_cells, //list of chop pts
1551  BOOL8 testing_on, //inidividual words
1552  inT16 start, //start of good range
1553  inT16 end //end of good range
1554  ) {
1555  //blobs
1556  BLOBNBOX_IT blob_it = row->blob_list ();
1557  BLOBNBOX_IT plot_it;
1558  inT16 blob_count; //no of blobs
1559  TBOX blob_box; //bounding box
1560  FPSEGPT_LIST seg_list; //char cells
1561  FPSEGPT_IT seg_it; //iterator
1562  inT16 segpos; //position of segment
1563  //iterator
1564  ICOORDELT_IT cell_it = row_cells;
1565  ICOORDELT *cell; //new cell
1566  double word_sync; //result for word
1567 
1568  mid_cuts = 0;
1569  if (blob_it.empty ()) {
1570  occupation = 0;
1571  return initial_pitch * 10;
1572  }
1573 #ifndef GRAPHICS_DISABLED
1574  if (testing_on && to_win > 0) {
1575  projection->plot (to_win, projection_left,
1576  row->intercept (), 1.0f, -1.0f, ScrollView::CORAL);
1577  }
1578 #endif
1579  blob_count = 0;
1580  blob_it.mark_cycle_pt ();
1581  do {
1582  //first blob
1583  blob_box = box_next (&blob_it);
1584  blob_count++;
1585  }
1586  while (!blob_it.cycled_list ());
1587  plot_it = blob_it;
1588  word_sync = check_pitch_sync2 (&blob_it, blob_count, (inT16) initial_pitch,
1589  2, projection, projection_left,
1590  projection_right,
1592  occupation, &seg_list, start, end);
1593  if (testing_on) {
1594  tprintf ("Row ending at (%d,%d), len=%d, sync rating=%g, ",
1595  blob_box.right (), blob_box.top (),
1596  seg_list.length () - 1, word_sync);
1597  seg_it.set_to_list (&seg_list);
1598  for (seg_it.mark_cycle_pt (); !seg_it.cycled_list (); seg_it.forward ()) {
1599  if (seg_it.data ()->faked)
1600  tprintf ("(F)");
1601  tprintf ("%d, ", seg_it.data ()->position ());
1602  // tprintf("C=%g, s=%g, sq=%g\n",
1603  // seg_it.data()->cost_function(),
1604  // seg_it.data()->sum(),
1605  // seg_it.data()->squares());
1606  }
1607  tprintf ("\n");
1608  }
1609 #ifndef GRAPHICS_DISABLED
1610  if (textord_show_fixed_cuts && blob_count > 0 && to_win > 0)
1611  plot_fp_cells2(to_win, ScrollView::GOLDENROD, row, &seg_list);
1612 #endif
1613  seg_it.set_to_list (&seg_list);
1614  for (seg_it.mark_cycle_pt (); !seg_it.cycled_list (); seg_it.forward ()) {
1615  segpos = seg_it.data ()->position ();
1616  //make new one
1617  cell = new ICOORDELT (segpos, 0);
1618  cell_it.add_after_then_move (cell);
1619  if (seg_it.at_last ())
1620  mid_cuts = seg_it.data ()->cheap_cuts ();
1621  }
1622  seg_list.clear ();
1623  return occupation > 0 ? sqrt (word_sync / occupation) : initial_pitch * 10;
1624 }
1625 
1626 
1627 /**********************************************************************
1628  * print_pitch_sd
1629  *
1630  * Use a dp algorithm to fit the character cells and return the sd of
1631  * the cell size over the row.
1632  **********************************************************************/
1633 
1634 void print_pitch_sd( //find fp cells
1635  TO_ROW *row, //row to do
1636  STATS *projection, //vertical projection
1637  inT16 projection_left, //edges //size of blank
1638  inT16 projection_right,
1639  float space_size,
1640  float initial_pitch //guess at pitch
1641  ) {
1642  const char *res2; //pitch result
1643  inT16 occupation; //used cells
1644  float sp_sd; //space sd
1645  //blobs
1646  BLOBNBOX_IT blob_it = row->blob_list ();
1647  BLOBNBOX_IT start_it; //start of word
1648  BLOBNBOX_IT row_start; //start of row
1649  inT16 blob_count; //no of blobs
1650  inT16 total_blob_count; //total blobs in line
1651  TBOX blob_box; //bounding box
1652  TBOX prev_box; //of super blob
1653  inT32 prev_right; //of word sync
1654  int scale_factor; //on scores for big words
1655  inT32 sp_count; //spaces
1656  FPSEGPT_LIST seg_list; //char cells
1657  FPSEGPT_IT seg_it; //iterator
1658  double sqsum; //sum of squares
1659  double spsum; //of spaces
1660  double sp_var; //space error
1661  double word_sync; //result for word
1662  double total_count; //total cuts
1663 
1664  if (blob_it.empty ())
1665  return;
1666  row_start = blob_it;
1667  total_blob_count = 0;
1668 
1669  total_count = 0;
1670  sqsum = 0;
1671  sp_count = 0;
1672  spsum = 0;
1673  prev_right = -1;
1674  blob_it = row_start;
1675  start_it = blob_it;
1676  blob_count = 0;
1677  blob_box = box_next (&blob_it);//first blob
1678  blob_it.mark_cycle_pt ();
1679  do {
1680  for (; blob_count > 0; blob_count--)
1681  box_next(&start_it);
1682  do {
1683  prev_box = blob_box;
1684  blob_count++;
1685  blob_box = box_next (&blob_it);
1686  }
1687  while (!blob_it.cycled_list ()
1688  && blob_box.left () - prev_box.right () < space_size);
1689  word_sync =
1690  check_pitch_sync2 (&start_it, blob_count, (inT16) initial_pitch, 2,
1691  projection, projection_left, projection_right,
1693  occupation, &seg_list, 0, 0);
1694  total_blob_count += blob_count;
1695  seg_it.set_to_list (&seg_list);
1696  if (prev_right >= 0) {
1697  sp_var = seg_it.data ()->position () - prev_right;
1698  sp_var -= floor (sp_var / initial_pitch + 0.5) * initial_pitch;
1699  sp_var *= sp_var;
1700  spsum += sp_var;
1701  sp_count++;
1702  }
1703  seg_it.move_to_last ();
1704  prev_right = seg_it.data ()->position ();
1706  scale_factor = (seg_list.length () - 2) / 2;
1707  if (scale_factor < 1)
1708  scale_factor = 1;
1709  }
1710  else
1711  scale_factor = 1;
1712  sqsum += word_sync * scale_factor;
1713  total_count += (seg_list.length () - 1) * scale_factor;
1714  seg_list.clear ();
1715  }
1716  while (!blob_it.cycled_list ());
1717  sp_sd = sp_count > 0 ? sqrt (spsum / sp_count) : 0;
1718  word_sync = total_count > 0 ? sqrt (sqsum / total_count) : space_size * 10;
1719  tprintf ("new_sd=%g:sd/p=%g:new_sp_sd=%g:res=%c:",
1720  word_sync, word_sync / initial_pitch, sp_sd,
1721  word_sync < textord_words_pitchsd_threshold * initial_pitch
1722  ? 'F' : 'P');
1723 
1724  start_it = row_start;
1725  blob_it = row_start;
1726  word_sync =
1727  check_pitch_sync2 (&blob_it, total_blob_count, (inT16) initial_pitch, 2,
1728  projection, projection_left, projection_right,
1729  row->xheight * textord_projection_scale, occupation,
1730  &seg_list, 0, 0);
1731  if (occupation > 1)
1732  word_sync /= occupation;
1733  word_sync = sqrt (word_sync);
1734 
1735 #ifndef GRAPHICS_DISABLED
1736  if (textord_show_row_cuts && to_win != NULL)
1737  plot_fp_cells2(to_win, ScrollView::CORAL, row, &seg_list);
1738 #endif
1739  seg_list.clear ();
1740  if (word_sync < textord_words_pitchsd_threshold * initial_pitch) {
1741  if (word_sync < textord_words_def_fixed * initial_pitch
1742  && !row->all_caps)
1743  res2 = "DF";
1744  else
1745  res2 = "MF";
1746  }
1747  else
1748  res2 = word_sync < textord_words_def_prop * initial_pitch ? "MP" : "DP";
1749  tprintf
1750  ("row_sd=%g:sd/p=%g:res=%c:N=%d:res2=%s,init pitch=%g, row_pitch=%g, all_caps=%d\n",
1751  word_sync, word_sync / initial_pitch,
1752  word_sync < textord_words_pitchsd_threshold * initial_pitch ? 'F' : 'P',
1753  occupation, res2, initial_pitch, row->fixed_pitch, row->all_caps);
1754 }
1755 
1756 /**********************************************************************
1757  * find_repeated_chars
1758  *
1759  * Extract marked leader blobs and put them
1760  * into words in advance of fixed pitch checking and word generation.
1761  **********************************************************************/
1762 void find_repeated_chars(TO_BLOCK *block, // Block to search.
1763  BOOL8 testing_on) { // Debug mode.
1764  POLY_BLOCK* pb = block->block->poly_block();
1765  if (pb != NULL && !pb->IsText())
1766  return; // Don't find repeated chars in non-text blocks.
1767 
1768  TO_ROW *row;
1769  BLOBNBOX_IT box_it;
1770  BLOBNBOX_IT search_it; // forward search
1771  WERD_IT word_it; // new words
1772  WERD *word; // new word
1773  TBOX word_box; // for plotting
1774  int blobcount, repeated_set;
1775 
1776  TO_ROW_IT row_it = block->get_rows();
1777  if (row_it.empty()) return; // empty block
1778  for (row_it.mark_cycle_pt(); !row_it.cycled_list(); row_it.forward()) {
1779  row = row_it.data();
1780  box_it.set_to_list(row->blob_list());
1781  if (box_it.empty()) continue; // no blobs in this row
1782  if (!row->rep_chars_marked()) {
1783  mark_repeated_chars(row);
1784  }
1785  if (row->num_repeated_sets() == 0) continue; // nothing to do for this row
1786  word_it.set_to_list(&row->rep_words);
1787  do {
1788  if (box_it.data()->repeated_set() != 0 &&
1789  !box_it.data()->joined_to_prev()) {
1790  blobcount = 1;
1791  repeated_set = box_it.data()->repeated_set();
1792  search_it = box_it;
1793  search_it.forward();
1794  while (!search_it.at_first() &&
1795  search_it.data()->repeated_set() == repeated_set) {
1796  blobcount++;
1797  search_it.forward();
1798  }
1799  // After the call to make_real_word() all the blobs from this
1800  // repeated set will be removed from the blob list. box_it will be
1801  // set to point to the blob after the end of the extracted sequence.
1802  word = make_real_word(&box_it, blobcount, box_it.at_first(), 1);
1803  if (!box_it.empty() && box_it.data()->joined_to_prev()) {
1804  tprintf("Bad box joined to prev at");
1805  box_it.data()->bounding_box().print();
1806  tprintf("After repeated word:");
1807  word->bounding_box().print();
1808  }
1809  ASSERT_HOST(box_it.empty() || !box_it.data()->joined_to_prev());
1810  word->set_flag(W_REP_CHAR, true);
1811  word->set_flag(W_DONT_CHOP, true);
1812  word_it.add_after_then_move(word);
1813  } else {
1814  box_it.forward();
1815  }
1816  } while (!box_it.at_first());
1817  }
1818 }
1819 
1820 
1821 /**********************************************************************
1822  * plot_fp_word
1823  *
1824  * Plot a block of words as if fixed pitch.
1825  **********************************************************************/
1826 
1827 #ifndef GRAPHICS_DISABLED
1828 void plot_fp_word( //draw block of words
1829  TO_BLOCK *block, //block to draw
1830  float pitch, //pitch to draw with
1831  float nonspace //for space threshold
1832  ) {
1833  TO_ROW *row; //current row
1834  TO_ROW_IT row_it = block->get_rows ();
1835 
1836  for (row_it.mark_cycle_pt (); !row_it.cycled_list (); row_it.forward ()) {
1837  row = row_it.data ();
1838  row->min_space = (inT32) ((pitch + nonspace) / 2);
1839  row->max_nonspace = row->min_space;
1840  row->space_threshold = row->min_space;
1841  plot_word_decisions (to_win, (inT16) pitch, row);
1842  }
1843 }
1844 #endif