Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/tesseract/src/textord/pitsync1.cpp @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
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