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