tesseract  5.0.0
pitsync1.cpp
Go to the documentation of this file.
1 /**********************************************************************
2  * File: pitsync1.cpp (Formerly pitsync.c)
3  * Description: Code to find the optimum fixed pitch segmentation of some blobs.
4  * Author: Ray Smith
5  *
6  * (C) Copyright 1992, Hewlett-Packard Ltd.
7  ** Licensed under the Apache License, Version 2.0 (the "License");
8  ** you may not use this file except in compliance with the License.
9  ** You may obtain a copy of the License at
10  ** http://www.apache.org/licenses/LICENSE-2.0
11  ** Unless required by applicable law or agreed to in writing, software
12  ** distributed under the License is distributed on an "AS IS" BASIS,
13  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  ** See the License for the specific language governing permissions and
15  ** limitations under the License.
16  *
17  **********************************************************************/
18 
19 #include "pitsync1.h"
20 
21 #include <cfloat> // for FLT_MAX
22 #include <cmath>
23 
24 namespace tesseract {
25 
26 INT_VAR(pitsync_linear_version, 6, "Use new fast algorithm");
27 double_VAR(pitsync_joined_edge, 0.75, "Dist inside big blob for chopping");
28 double_VAR(pitsync_offset_freecut_fraction, 0.25, "Fraction of cut for free cuts");
29 
30 /**********************************************************************
31  * FPSEGPT::FPSEGPT
32  *
33  * Constructor to make a new FPSEGPT.
34  * The existing FPCUTPT is duplicated.
35  **********************************************************************/
36 
37 FPSEGPT::FPSEGPT( // constructor
38  FPCUTPT *cutpt // create from new form
39 ) {
40  pred = nullptr;
41  mean_sum = cutpt->sum();
42  sq_sum = cutpt->squares();
43  cost = cutpt->cost_function();
44  faked = cutpt->faked;
45  terminal = cutpt->terminal;
46  fake_count = cutpt->fake_count;
47  xpos = cutpt->position();
48  mid_cuts = cutpt->cheap_cuts();
49 }
50 
51 /**********************************************************************
52  * FPSEGPT::FPSEGPT
53  *
54  * Constructor to make a new FPSEGPT.
55  **********************************************************************/
56 
57 FPSEGPT::FPSEGPT( // constructor
58  int16_t x // position
59  )
60  : xpos(x) {
61  pred = nullptr;
62  mean_sum = 0;
63  sq_sum = 0;
64  cost = 0;
65  faked = false;
66  terminal = false;
67  fake_count = 0;
68  mid_cuts = 0;
69 }
70 
71 /**********************************************************************
72  * FPSEGPT::FPSEGPT
73  *
74  * Constructor to make a new FPSEGPT.
75  **********************************************************************/
76 
77 FPSEGPT::FPSEGPT( // constructor
78  int16_t x, // position
79  bool faking, // faking this one
80  int16_t offset, // dist to gap
81  int16_t region_index, // segment number
82  int16_t pitch, // proposed pitch
83  int16_t pitch_error, // allowed tolerance
84  FPSEGPT_LIST *prev_list // previous segment
85  )
86  : fake_count(0), xpos(x), mean_sum(0.0), sq_sum(0.0) {
87  int16_t best_fake; // on previous
88  FPSEGPT *segpt; // segment point
89  int32_t dist; // from prev segment
90  double sq_dist; // squared distance
91  double mean; // mean pitch
92  double total; // total dists
93  double factor; // cost function
94  FPSEGPT_IT pred_it = prev_list; // for previuos segment
95 
96  cost = FLT_MAX;
97  pred = nullptr;
98  faked = faking;
99  terminal = false;
100  best_fake = INT16_MAX;
101  mid_cuts = 0;
102  for (pred_it.mark_cycle_pt(); !pred_it.cycled_list(); pred_it.forward()) {
103  segpt = pred_it.data();
104  if (segpt->fake_count < best_fake) {
105  best_fake = segpt->fake_count;
106  }
107  dist = x - segpt->xpos;
108  if (dist >= pitch - pitch_error && dist <= pitch + pitch_error && !segpt->terminal) {
109  total = segpt->mean_sum + dist;
110  sq_dist = dist * dist + segpt->sq_sum + offset * offset;
111  // sum of squarees
112  mean = total / region_index;
113  factor = mean - pitch;
114  factor *= factor;
115  factor += sq_dist / (region_index)-mean * mean;
116  if (factor < cost) {
117  cost = factor; // find least cost
118  pred = segpt; // save path
119  mean_sum = total;
120  sq_sum = sq_dist;
121  fake_count = segpt->fake_count + faked;
122  }
123  }
124  }
125  if (fake_count > best_fake + 1) {
126  pred = nullptr; // fail it
127  }
128 }
129 
130 /**********************************************************************
131  * check_pitch_sync
132  *
133  * Construct the lattice of possible segmentation points and choose the
134  * optimal path. Return the optimal path only.
135  * The return value is a measure of goodness of the sync.
136  **********************************************************************/
137 
138 double check_pitch_sync( // find segmentation
139  BLOBNBOX_IT *blob_it, // blobs to do
140  int16_t blob_count, // no of blobs
141  int16_t pitch, // pitch estimate
142  int16_t pitch_error, // tolerance
143  STATS *projection, // vertical
144  FPSEGPT_LIST *seg_list // output list
145 ) {
146  int16_t x; // current coord
147  int16_t min_index; // blob number
148  int16_t max_index; // blob number
149  int16_t left_edge; // of word
150  int16_t right_edge; // of word
151  int16_t right_max; // max allowed x
152  int16_t min_x; // in this region
153  int16_t max_x;
154  int16_t region_index;
155  int16_t best_region_index = 0; // for best result
156  int16_t offset; // dist to legal area
157  int16_t left_best_x; // edge of good region
158  int16_t right_best_x; // right edge
159  TBOX min_box; // bounding box
160  TBOX max_box; // bounding box
161  TBOX next_box; // box of next blob
162  FPSEGPT *segpt; // segment point
163  FPSEGPT_LIST *segpts; // points in a segment
164  double best_cost; // best path
165  double mean_sum; // computes result
166  FPSEGPT *best_end; // end of best path
167  BLOBNBOX_IT min_it; // copy iterator
168  BLOBNBOX_IT max_it; // copy iterator
169  FPSEGPT_IT segpt_it; // iterator
170  // output segments
171  FPSEGPT_IT outseg_it = seg_list;
172  FPSEGPT_LIST_CLIST lattice; // list of lists
173  // region iterator
174  FPSEGPT_LIST_C_IT lattice_it = &lattice;
175 
176  // tprintf("Computing sync on word of %d blobs with pitch %d\n",
177  // blob_count, pitch);
178  // if (blob_count==8 && pitch==27)
179  // projection->print(stdout,true);
180  if (pitch < 3) {
181  pitch = 3; // nothing ludicrous
182  }
183  if ((pitch - 3) / 2 < pitch_error) {
184  pitch_error = (pitch - 3) / 2;
185  }
186  min_it = *blob_it;
187  min_box = box_next(&min_it); // get box
188  // if (blob_count==8 && pitch==27)
189  // tprintf("1st box at (%d,%d)->(%d,%d)\n",
190  // min_box.left(),min_box.bottom(),
191  // min_box.right(),min_box.top());
192  // left of word
193  left_edge = min_box.left() + pitch_error;
194  for (min_index = 1; min_index < blob_count; min_index++) {
195  min_box = box_next(&min_it);
196  // if (blob_count==8 && pitch==27)
197  // tprintf("Box at (%d,%d)->(%d,%d)\n",
198  // min_box.left(),min_box.bottom(),
199  // min_box.right(),min_box.top());
200  }
201  right_edge = min_box.right(); // end of word
202  max_x = left_edge;
203  // min permissible
204  min_x = max_x - pitch + pitch_error * 2 + 1;
205  right_max = right_edge + pitch - pitch_error - 1;
206  segpts = new FPSEGPT_LIST; // list of points
207  segpt_it.set_to_list(segpts);
208  for (x = min_x; x <= max_x; x++) {
209  segpt = new FPSEGPT(x); // make a new one
210  // put in list
211  segpt_it.add_after_then_move(segpt);
212  }
213  // first segment
214  lattice_it.add_before_then_move(segpts);
215  min_index = 0;
216  region_index = 1;
217  best_cost = FLT_MAX;
218  best_end = nullptr;
219  min_it = *blob_it;
220  min_box = box_next(&min_it); // first box
221  do {
222  left_best_x = -1;
223  right_best_x = -1;
224  segpts = new FPSEGPT_LIST; // list of points
225  segpt_it.set_to_list(segpts);
226  min_x += pitch - pitch_error; // next limits
227  max_x += pitch + pitch_error;
228  while (min_box.right() < min_x && min_index < blob_count) {
229  min_index++;
230  min_box = box_next(&min_it);
231  }
232  max_it = min_it;
233  max_index = min_index;
234  max_box = min_box;
235  next_box = box_next(&max_it);
236  for (x = min_x; x <= max_x && x <= right_max; x++) {
237  while (x < right_edge && max_index < blob_count && x > max_box.right()) {
238  max_index++;
239  max_box = next_box;
240  next_box = box_next(&max_it);
241  }
242  if (x <= max_box.left() + pitch_error || x >= max_box.right() - pitch_error ||
243  x >= right_edge || (max_index < blob_count - 1 && x >= next_box.left()) ||
244  (x - max_box.left() > pitch * pitsync_joined_edge &&
245  max_box.right() - x > pitch * pitsync_joined_edge)) {
246  // || projection->local_min(x))
247  if (x - max_box.left() > 0 && x - max_box.left() <= pitch_error) {
248  // dist to real break
249  offset = x - max_box.left();
250  } else if (max_box.right() - x > 0 && max_box.right() - x <= pitch_error &&
251  (max_index >= blob_count - 1 || x < next_box.left())) {
252  offset = max_box.right() - x;
253  } else {
254  offset = 0;
255  }
256  // offset=pitsync_offset_freecut_fraction*projection->pile_count(x);
257  segpt = new FPSEGPT(x, false, offset, region_index, pitch, pitch_error, lattice_it.data());
258  } else {
259  offset = projection->pile_count(x);
260  segpt = new FPSEGPT(x, true, offset, region_index, pitch, pitch_error, lattice_it.data());
261  }
262  if (segpt->previous() != nullptr) {
263  segpt_it.add_after_then_move(segpt);
264  if (x >= right_edge - pitch_error) {
265  segpt->terminal = true; // no more wanted
266  if (segpt->cost_function() < best_cost) {
267  best_cost = segpt->cost_function();
268  // find least
269  best_end = segpt;
270  best_region_index = region_index;
271  left_best_x = x;
272  right_best_x = x;
273  } else if (segpt->cost_function() == best_cost && right_best_x == x - 1) {
274  right_best_x = x;
275  }
276  }
277  } else {
278  delete segpt; // no good
279  }
280  }
281  if (segpts->empty()) {
282  if (best_end != nullptr) {
283  break; // already found one
284  }
285  make_illegal_segment(lattice_it.data(), min_box, min_it, region_index, pitch, pitch_error,
286  segpts);
287  } else {
288  if (right_best_x > left_best_x + 1) {
289  left_best_x = (left_best_x + right_best_x + 1) / 2;
290  for (segpt_it.mark_cycle_pt();
291  !segpt_it.cycled_list() && segpt_it.data()->position() != left_best_x;
292  segpt_it.forward()) {
293  ;
294  }
295  if (segpt_it.data()->position() == left_best_x) {
296  // middle of region
297  best_end = segpt_it.data();
298  }
299  }
300  }
301  // new segment
302  lattice_it.add_before_then_move(segpts);
303  region_index++;
304  } while (min_x < right_edge);
305  ASSERT_HOST(best_end != nullptr); // must always find some
306 
307  for (lattice_it.mark_cycle_pt(); !lattice_it.cycled_list(); lattice_it.forward()) {
308  segpts = lattice_it.data();
309  segpt_it.set_to_list(segpts);
310  // if (blob_count==8 && pitch==27)
311  // {
312  // for
313  // (segpt_it.mark_cycle_pt();!segpt_it.cycled_list();segpt_it.forward())
314  // {
315  // segpt=segpt_it.data();
316  // tprintf("At %d, (%x) cost=%g, m=%g, sq=%g,
317  // pred=%x\n",
318  // segpt->position(),segpt,segpt->cost_function(),
319  // segpt->sum(),segpt->squares(),segpt->previous());
320  // }
321  // tprintf("\n");
322  // }
323  for (segpt_it.mark_cycle_pt(); !segpt_it.cycled_list() && segpt_it.data() != best_end;
324  segpt_it.forward()) {
325  ;
326  }
327  if (segpt_it.data() == best_end) {
328  // save good one
329  segpt = segpt_it.extract();
330  outseg_it.add_before_then_move(segpt);
331  best_end = segpt->previous();
332  }
333  }
334  ASSERT_HOST(best_end == nullptr);
335  ASSERT_HOST(!outseg_it.empty());
336  outseg_it.move_to_last();
337  mean_sum = outseg_it.data()->sum();
338  mean_sum = mean_sum * mean_sum / best_region_index;
339  if (outseg_it.data()->squares() - mean_sum < 0) {
340  tprintf("Impossible sqsum=%g, mean=%g, total=%d\n", outseg_it.data()->squares(),
341  outseg_it.data()->sum(), best_region_index);
342  }
343  lattice.deep_clear(); // shift the lot
344  return outseg_it.data()->squares() - mean_sum;
345 }
346 
347 /**********************************************************************
348  * make_illegal_segment
349  *
350  * Make a fake set of chop points due to having no legal places.
351  **********************************************************************/
352 
353 void make_illegal_segment( // find segmentation
354  FPSEGPT_LIST *prev_list, // previous segments
355  TBOX blob_box, // bounding box
356  BLOBNBOX_IT blob_it, // iterator
357  int16_t region_index, // number of segment
358  int16_t pitch, // pitch estimate
359  int16_t pitch_error, // tolerance
360  FPSEGPT_LIST *seg_list // output list
361 ) {
362  int16_t x; // current coord
363  int16_t min_x = 0; // in this region
364  int16_t max_x = 0;
365  int16_t offset; // dist to edge
366  FPSEGPT *segpt; // segment point
367  FPSEGPT *prevpt; // previous point
368  float best_cost; // best path
369  FPSEGPT_IT segpt_it = seg_list; // iterator
370  // previous points
371  FPSEGPT_IT prevpt_it = prev_list;
372 
373  best_cost = FLT_MAX;
374  for (prevpt_it.mark_cycle_pt(); !prevpt_it.cycled_list(); prevpt_it.forward()) {
375  prevpt = prevpt_it.data();
376  if (prevpt->cost_function() < best_cost) {
377  // find least
378  best_cost = prevpt->cost_function();
379  min_x = prevpt->position();
380  max_x = min_x; // limits on coords
381  } else if (prevpt->cost_function() == best_cost) {
382  max_x = prevpt->position();
383  }
384  }
385  min_x += pitch - pitch_error;
386  max_x += pitch + pitch_error;
387  for (x = min_x; x <= max_x; x++) {
388  while (x > blob_box.right()) {
389  blob_box = box_next(&blob_it);
390  }
391  offset = x - blob_box.left();
392  if (blob_box.right() - x < offset) {
393  offset = blob_box.right() - x;
394  }
395  segpt = new FPSEGPT(x, false, offset, region_index, pitch, pitch_error, prev_list);
396  if (segpt->previous() != nullptr) {
397  ASSERT_HOST(offset >= 0);
398  fprintf(stderr, "made fake at %d\n", x);
399  // make one up
400  segpt_it.add_after_then_move(segpt);
401  segpt->faked = true;
402  segpt->fake_count++;
403  } else {
404  delete segpt;
405  }
406  }
407 }
408 
409 } // namespace tesseract
#define ASSERT_HOST(x)
Definition: errcode.h:59
#define INT_VAR(name, val, comment)
Definition: params.h:356
#define double_VAR(name, val, comment)
Definition: params.h:365
void tprintf(const char *format,...)
Definition: tprintf.cpp:41
double pitsync_offset_freecut_fraction
Definition: pitsync1.cpp:28
int pitsync_linear_version
Definition: pitsync1.cpp:26
double pitsync_joined_edge
Definition: pitsync1.cpp:27
void make_illegal_segment(FPSEGPT_LIST *prev_list, TBOX blob_box, BLOBNBOX_IT blob_it, int16_t region_index, int16_t pitch, int16_t pitch_error, FPSEGPT_LIST *seg_list)
Definition: pitsync1.cpp:353
double check_pitch_sync(BLOBNBOX_IT *blob_it, int16_t blob_count, int16_t pitch, int16_t pitch_error, STATS *projection, FPSEGPT_LIST *seg_list)
Definition: pitsync1.cpp:138
TBOX box_next(BLOBNBOX_IT *it)
Definition: blobbox.cpp:638
TDimension left() const
Definition: rect.h:82
TDimension right() const
Definition: rect.h:89
int32_t pile_count(int32_t value) const
Definition: statistc.h:75
double cost_function()
Definition: pithsync.h:71
double sum()
Definition: pithsync.h:77
int16_t cheap_cuts() const
Definition: pithsync.h:83
int32_t position()
Definition: pithsync.h:68
int16_t fake_count
Definition: pithsync.h:92
double squares()
Definition: pithsync.h:74
int16_t fake_count
Definition: pitsync1.h:70
FPSEGPT * previous()
Definition: pitsync1.h:61
int32_t position()
Definition: pitsync1.h:49
double cost_function()
Definition: pitsync1.h:52