Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/tesseract/src/ccstruct/coutln.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: coutln.cpp (Formerly coutline.c)
3 * Description: Code for the C_OUTLINE class.
4 * Author: Ray Smith
5 *
6 * (C) Copyright 1991, 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 automatically generated configuration file if running autoconf.
20 #ifdef HAVE_CONFIG_H
21 # include "config_auto.h"
22 #endif
23
24 #include "coutln.h"
25
26 #include "arrayaccess.h" // for GET_DATA_BYTE
27 #include "blobs.h" // for TPOINT
28 #include "crakedge.h" // for CRACKEDGE
29 #include "environ.h" // for l_uint32
30 #include "errcode.h" // for ASSERT_HOST
31 #include "normalis.h" // for DENORM
32
33 #include "helpers.h" // for ClipToRange, IntCastRounded, Modulo
34
35 #include <allheaders.h> // for pixSetPixel, pixGetData, pixRasterop, pixGe...
36 #include "pix.h" // for Pix (ptr only), PIX_DST, PIX_NOT
37
38 #include <algorithm> // for max, min
39 #include <cmath> // for abs
40 #include <cstdlib> // for abs
41 #include <cstring> // for memset, memcpy, memmove
42
43 namespace tesseract {
44
45 ICOORD C_OUTLINE::step_coords[4] = {ICOORD(-1, 0), ICOORD(0, -1), ICOORD(1, 0), ICOORD(0, 1)};
46
47 /**
48 * @name C_OUTLINE::C_OUTLINE
49 *
50 * Constructor to build a C_OUTLINE from a CRACKEDGE LOOP.
51 * @param startpt outline to convert
52 * @param bot_left bounding box
53 * @param top_right bounding box
54 * @param length length of loop
55 */
56
57 C_OUTLINE::C_OUTLINE(CRACKEDGE *startpt, ICOORD bot_left, ICOORD top_right, int16_t length)
58 : box(bot_left, top_right), start(startpt->pos), offsets(nullptr) {
59 int16_t stepindex; // index to step
60 CRACKEDGE *edgept; // current point
61
62 stepcount = length; // no of steps
63 if (length == 0) {
64 return;
65 }
66 // get memory
67 steps.resize(step_mem());
68 edgept = startpt;
69
70 for (stepindex = 0; stepindex < length; stepindex++) {
71 // set compact step
72 set_step(stepindex, edgept->stepdir);
73 edgept = edgept->next;
74 }
75 }
76
77 /**
78 * @name C_OUTLINE::C_OUTLINE
79 *
80 * Constructor to build a C_OUTLINE from a C_OUTLINE_FRAG.
81 */
82 C_OUTLINE::C_OUTLINE(
83 // constructor
84 // steps to copy
85 ICOORD startpt, DIR128 *new_steps,
86 int16_t length // length of loop
87 )
88 : start(startpt), offsets(nullptr) {
89 int8_t dirdiff; // direction difference
90 DIR128 prevdir; // previous direction
91 DIR128 dir; // current direction
92 DIR128 lastdir; // dir of last step
93 TBOX new_box; // easy bounding
94 int16_t stepindex; // index to step
95 int16_t srcindex; // source steps
96 ICOORD pos; // current position
97
98 pos = startpt;
99 stepcount = length; // No. of steps.
100 ASSERT_HOST(length >= 0);
101 steps.resize(step_mem()); // Get memory.
102
103 lastdir = new_steps[length - 1];
104 prevdir = lastdir;
105 for (stepindex = 0, srcindex = 0; srcindex < length; stepindex++, srcindex++) {
106 new_box = TBOX(pos, pos);
107 box += new_box;
108 // copy steps
109 dir = new_steps[srcindex];
110 set_step(stepindex, dir);
111 dirdiff = dir - prevdir;
112 pos += step(stepindex);
113 if ((dirdiff == 64 || dirdiff == -64) && stepindex > 0) {
114 stepindex -= 2; // cancel there-and-back
115 prevdir = stepindex >= 0 ? step_dir(stepindex) : lastdir;
116 } else {
117 prevdir = dir;
118 }
119 }
120 ASSERT_HOST(pos.x() == startpt.x() && pos.y() == startpt.y());
121 do {
122 dirdiff = step_dir(stepindex - 1) - step_dir(0);
123 if (dirdiff == 64 || dirdiff == -64) {
124 start += step(0);
125 stepindex -= 2; // cancel there-and-back
126 for (int i = 0; i < stepindex; ++i) {
127 set_step(i, step_dir(i + 1));
128 }
129 }
130 } while (stepindex > 1 && (dirdiff == 64 || dirdiff == -64));
131 stepcount = stepindex;
132 ASSERT_HOST(stepcount >= 4);
133 }
134
135 /**
136 * @name C_OUTLINE::C_OUTLINE
137 *
138 * Constructor to build a C_OUTLINE from a rotation of a C_OUTLINE.
139 * @param srcline outline to rotate
140 * @param rotation rotate to coord
141 */
142
143 C_OUTLINE::C_OUTLINE(C_OUTLINE *srcline, FCOORD rotation) : offsets(nullptr) {
144 TBOX new_box; // easy bounding
145 int16_t stepindex; // index to step
146 int16_t dirdiff; // direction change
147 ICOORD pos; // current position
148 ICOORD prevpos; // previous dest point
149
150 ICOORD destpos; // destination point
151 int16_t destindex = INT16_MAX; // index to step
152 DIR128 dir; // coded direction
153 uint8_t new_step;
154
155 stepcount = srcline->stepcount * 2;
156 if (stepcount == 0) {
157 box = srcline->box;
158 box.rotate(rotation);
159 return;
160 }
161 // get memory
162 steps.resize(step_mem());
163
164 for (int iteration = 0; iteration < 2; ++iteration) {
165 DIR128 round1 = iteration == 0 ? 32 : 0;
166 DIR128 round2 = iteration != 0 ? 32 : 0;
167 pos = srcline->start;
168 prevpos = pos;
169 prevpos.rotate(rotation);
170 start = prevpos;
171 box = TBOX(start, start);
172 destindex = 0;
173 for (stepindex = 0; stepindex < srcline->stepcount; stepindex++) {
174 pos += srcline->step(stepindex);
175 destpos = pos;
176 destpos.rotate(rotation);
177 // tprintf("%i %i %i %i ", destpos.x(), destpos.y(), pos.x(), pos.y());
178 while (destpos.x() != prevpos.x() || destpos.y() != prevpos.y()) {
179 dir = DIR128(FCOORD(destpos - prevpos));
180 dir += 64; // turn to step style
181 new_step = dir.get_dir();
182 // tprintf(" %i\n", new_step);
183 if (new_step & 31) {
184 set_step(destindex++, dir + round1);
185 prevpos += step(destindex - 1);
186 if (destindex < 2 ||
187 ((dirdiff = step_dir(destindex - 1) - step_dir(destindex - 2)) != -64 &&
188 dirdiff != 64)) {
189 set_step(destindex++, dir + round2);
190 prevpos += step(destindex - 1);
191 } else {
192 prevpos -= step(destindex - 1);
193 destindex--;
194 prevpos -= step(destindex - 1);
195 set_step(destindex - 1, dir + round2);
196 prevpos += step(destindex - 1);
197 }
198 } else {
199 set_step(destindex++, dir);
200 prevpos += step(destindex - 1);
201 }
202 while (destindex >= 2 &&
203 ((dirdiff = step_dir(destindex - 1) - step_dir(destindex - 2)) == -64 ||
204 dirdiff == 64)) {
205 prevpos -= step(destindex - 1);
206 prevpos -= step(destindex - 2);
207 destindex -= 2; // Forget u turn
208 }
209 // ASSERT_HOST(prevpos.x() == destpos.x() && prevpos.y() ==
210 // destpos.y());
211 new_box = TBOX(destpos, destpos);
212 box += new_box;
213 }
214 }
215 ASSERT_HOST(destpos.x() == start.x() && destpos.y() == start.y());
216 while (destindex > 1) {
217 dirdiff = step_dir(destindex - 1) - step_dir(0);
218 if (dirdiff != 64 && dirdiff != -64) {
219 break;
220 }
221 start += step(0);
222 destindex -= 2;
223 for (int i = 0; i < destindex; ++i) {
224 set_step(i, step_dir(i + 1));
225 }
226 }
227 if (destindex >= 4) {
228 break;
229 }
230 }
231 ASSERT_HOST(destindex <= stepcount);
232 stepcount = destindex;
233 destpos = start;
234 for (stepindex = 0; stepindex < stepcount; stepindex++) {
235 destpos += step(stepindex);
236 }
237 ASSERT_HOST(destpos.x() == start.x() && destpos.y() == start.y());
238 }
239
240 // Build a fake outline, given just a bounding box and append to the list.
241 void C_OUTLINE::FakeOutline(const TBOX &box, C_OUTLINE_LIST *outlines) {
242 C_OUTLINE_IT ol_it(outlines);
243 // Make a C_OUTLINE from the bounds. This is a bit of a hack,
244 // as there is no outline, just a bounding box, but it works nicely.
245 CRACKEDGE start;
246 start.pos = box.topleft();
247 auto *outline = new C_OUTLINE(&start, box.topleft(), box.botright(), 0);
248 ol_it.add_to_end(outline);
249 }
250
251 /**
252 * @name C_OUTLINE::area
253 *
254 * Compute the area of the outline.
255 */
256
257 int32_t C_OUTLINE::area() const {
258 int stepindex; // current step
259 int32_t total_steps; // steps to do
260 int32_t total; // total area
261 ICOORD pos; // position of point
262 ICOORD next_step; // step to next pix
263 // We aren't going to modify the list, or its contents, but there is
264 // no const iterator.
265 C_OUTLINE_IT it(const_cast<C_OUTLINE_LIST *>(&children));
266
267 pos = start_pos();
268 total_steps = pathlength();
269 total = 0;
270 for (stepindex = 0; stepindex < total_steps; stepindex++) {
271 // all intersected
272 next_step = step(stepindex);
273 if (next_step.x() < 0) {
274 total += pos.y();
275 } else if (next_step.x() > 0) {
276 total -= pos.y();
277 }
278 pos += next_step;
279 }
280 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
281 total += it.data()->area(); // add areas of children
282 }
283
284 return total;
285 }
286
287 /**
288 * @name C_OUTLINE::perimeter
289 *
290 * Compute the perimeter of the outline and its first level children.
291 */
292
293 int32_t C_OUTLINE::perimeter() const {
294 int32_t total_steps; // Return value.
295 // We aren't going to modify the list, or its contents, but there is
296 // no const iterator.
297 C_OUTLINE_IT it(const_cast<C_OUTLINE_LIST *>(&children));
298
299 total_steps = pathlength();
300 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
301 total_steps += it.data()->pathlength(); // Add perimeters of children.
302 }
303
304 return total_steps;
305 }
306
307 /**
308 * @name C_OUTLINE::outer_area
309 *
310 * Compute the area of the outline.
311 */
312
313 int32_t C_OUTLINE::outer_area() const {
314 int stepindex; // current step
315 int32_t total_steps; // steps to do
316 int32_t total; // total area
317 ICOORD pos; // position of point
318 ICOORD next_step; // step to next pix
319
320 pos = start_pos();
321 total_steps = pathlength();
322 if (total_steps == 0) {
323 return box.area();
324 }
325 total = 0;
326 for (stepindex = 0; stepindex < total_steps; stepindex++) {
327 // all intersected
328 next_step = step(stepindex);
329 if (next_step.x() < 0) {
330 total += pos.y();
331 } else if (next_step.x() > 0) {
332 total -= pos.y();
333 }
334 pos += next_step;
335 }
336
337 return total;
338 }
339
340 /**
341 * @name C_OUTLINE::count_transitions
342 *
343 * Compute the number of x and y maxes and mins in the outline.
344 * @param threshold winding number on size
345 */
346
347 int32_t C_OUTLINE::count_transitions(int32_t threshold) {
348 bool first_was_max_x; // what was first
349 bool first_was_max_y;
350 bool looking_for_max_x; // what is next
351 bool looking_for_min_x;
352 bool looking_for_max_y; // what is next
353 bool looking_for_min_y;
354 int stepindex; // current step
355 int32_t total_steps; // steps to do
356 // current limits
357 int32_t max_x, min_x, max_y, min_y;
358 int32_t initial_x, initial_y; // initial limits
359 int32_t total; // total changes
360 ICOORD pos; // position of point
361 ICOORD next_step; // step to next pix
362
363 pos = start_pos();
364 total_steps = pathlength();
365 total = 0;
366 max_x = min_x = pos.x();
367 max_y = min_y = pos.y();
368 looking_for_max_x = true;
369 looking_for_min_x = true;
370 looking_for_max_y = true;
371 looking_for_min_y = true;
372 first_was_max_x = false;
373 first_was_max_y = false;
374 initial_x = pos.x();
375 initial_y = pos.y(); // stop uninit warning
376 for (stepindex = 0; stepindex < total_steps; stepindex++) {
377 // all intersected
378 next_step = step(stepindex);
379 pos += next_step;
380 if (next_step.x() < 0) {
381 if (looking_for_max_x && pos.x() < min_x) {
382 min_x = pos.x();
383 }
384 if (looking_for_min_x && max_x - pos.x() > threshold) {
385 if (looking_for_max_x) {
386 initial_x = max_x;
387 first_was_max_x = false;
388 }
389 total++;
390 looking_for_max_x = true;
391 looking_for_min_x = false;
392 min_x = pos.x(); // reset min
393 }
394 } else if (next_step.x() > 0) {
395 if (looking_for_min_x && pos.x() > max_x) {
396 max_x = pos.x();
397 }
398 if (looking_for_max_x && pos.x() - min_x > threshold) {
399 if (looking_for_min_x) {
400 initial_x = min_x; // remember first min
401 first_was_max_x = true;
402 }
403 total++;
404 looking_for_max_x = false;
405 looking_for_min_x = true;
406 max_x = pos.x();
407 }
408 } else if (next_step.y() < 0) {
409 if (looking_for_max_y && pos.y() < min_y) {
410 min_y = pos.y();
411 }
412 if (looking_for_min_y && max_y - pos.y() > threshold) {
413 if (looking_for_max_y) {
414 initial_y = max_y; // remember first max
415 first_was_max_y = false;
416 }
417 total++;
418 looking_for_max_y = true;
419 looking_for_min_y = false;
420 min_y = pos.y(); // reset min
421 }
422 } else {
423 if (looking_for_min_y && pos.y() > max_y) {
424 max_y = pos.y();
425 }
426 if (looking_for_max_y && pos.y() - min_y > threshold) {
427 if (looking_for_min_y) {
428 initial_y = min_y; // remember first min
429 first_was_max_y = true;
430 }
431 total++;
432 looking_for_max_y = false;
433 looking_for_min_y = true;
434 max_y = pos.y();
435 }
436 }
437 }
438 if (first_was_max_x && looking_for_min_x) {
439 if (max_x - initial_x > threshold) {
440 total++;
441 } else {
442 total--;
443 }
444 } else if (!first_was_max_x && looking_for_max_x) {
445 if (initial_x - min_x > threshold) {
446 total++;
447 } else {
448 total--;
449 }
450 }
451 if (first_was_max_y && looking_for_min_y) {
452 if (max_y - initial_y > threshold) {
453 total++;
454 } else {
455 total--;
456 }
457 } else if (!first_was_max_y && looking_for_max_y) {
458 if (initial_y - min_y > threshold) {
459 total++;
460 } else {
461 total--;
462 }
463 }
464
465 return total;
466 }
467
468 /**
469 * @name C_OUTLINE::operator<
470 *
471 * @return true if the left operand is inside the right one.
472 * @param other other outline
473 */
474
475 bool C_OUTLINE::operator<(const C_OUTLINE &other) const {
476 int16_t count = 0; // winding count
477 ICOORD pos; // position of point
478 int32_t stepindex; // index to cstep
479
480 if (!box.overlap(other.box)) {
481 return false; // can't be contained
482 }
483 if (stepcount == 0) {
484 return other.box.contains(this->box);
485 }
486
487 pos = start;
488 for (stepindex = 0; stepindex < stepcount && (count = other.winding_number(pos)) == INTERSECTING;
489 stepindex++) {
490 pos += step(stepindex); // try all points
491 }
492 if (count == INTERSECTING) {
493 // all intersected
494 pos = other.start;
495 for (stepindex = 0;
496 stepindex < other.stepcount && (count = winding_number(pos)) == INTERSECTING;
497 stepindex++) {
498 // try other way round
499 pos += other.step(stepindex);
500 }
501 return count == INTERSECTING || count == 0;
502 }
503 return count != 0;
504 }
505
506 /**
507 * @name C_OUTLINE::winding_number
508 *
509 * @return the winding number of the outline around the given point.
510 * @param point point to wind around
511 */
512
513 int16_t C_OUTLINE::winding_number(ICOORD point) const {
514 int16_t stepindex; // index to cstep
515 int16_t count; // winding count
516 ICOORD vec; // to current point
517 ICOORD stepvec; // step vector
518 int32_t cross; // cross product
519
520 vec = start - point; // vector to it
521 count = 0;
522 for (stepindex = 0; stepindex < stepcount; stepindex++) {
523 stepvec = step(stepindex); // get the step
524 // crossing the line
525 if (vec.y() <= 0 && vec.y() + stepvec.y() > 0) {
526 cross = vec * stepvec; // cross product
527 if (cross > 0) {
528 count++; // crossing right half
529 } else if (cross == 0) {
530 return INTERSECTING; // going through point
531 }
532 } else if (vec.y() > 0 && vec.y() + stepvec.y() <= 0) {
533 cross = vec * stepvec;
534 if (cross < 0) {
535 count--; // crossing back
536 } else if (cross == 0) {
537 return INTERSECTING; // illegal
538 }
539 }
540 vec += stepvec; // sum vectors
541 }
542 return count; // winding number
543 }
544
545 /**
546 * C_OUTLINE::turn_direction
547 *
548 * @return the sum direction delta of the outline.
549 */
550
551 int16_t C_OUTLINE::turn_direction() const { // winding number
552 DIR128 prevdir; // previous direction
553 DIR128 dir; // current direction
554 int16_t stepindex; // index to cstep
555 int8_t dirdiff; // direction difference
556 int16_t count; // winding count
557
558 if (stepcount == 0) {
559 return 128;
560 }
561 count = 0;
562 prevdir = step_dir(stepcount - 1);
563 for (stepindex = 0; stepindex < stepcount; stepindex++) {
564 dir = step_dir(stepindex);
565 dirdiff = dir - prevdir;
566 ASSERT_HOST(dirdiff == 0 || dirdiff == 32 || dirdiff == -32);
567 count += dirdiff;
568 prevdir = dir;
569 }
570 ASSERT_HOST(count == 128 || count == -128);
571 return count; // winding number
572 }
573
574 /**
575 * @name C_OUTLINE::reverse
576 *
577 * Reverse the direction of an outline.
578 */
579
580 void C_OUTLINE::reverse() { // reverse drection
581 DIR128 halfturn = MODULUS / 2; // amount to shift
582 DIR128 stepdir; // direction of step
583 int16_t stepindex; // index to cstep
584 int16_t farindex; // index to other side
585 int16_t halfsteps; // half of stepcount
586
587 halfsteps = (stepcount + 1) / 2;
588 for (stepindex = 0; stepindex < halfsteps; stepindex++) {
589 farindex = stepcount - stepindex - 1;
590 stepdir = step_dir(stepindex);
591 set_step(stepindex, step_dir(farindex) + halfturn);
592 set_step(farindex, stepdir + halfturn);
593 }
594 }
595
596 /**
597 * @name C_OUTLINE::move
598 *
599 * Move C_OUTLINE by vector
600 * @param vec vector to reposition OUTLINE by
601 */
602
603 void C_OUTLINE::move(const ICOORD vec) {
604 C_OUTLINE_IT it(&children); // iterator
605
606 box.move(vec);
607 start += vec;
608
609 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
610 it.data()->move(vec); // move child outlines
611 }
612 }
613
614 /**
615 * Returns true if *this and its children are legally nested.
616 * The outer area of a child should have the opposite sign to the
617 * parent. If not, it means we have discarded an outline in between
618 * (probably due to excessive length).
619 */
620 bool C_OUTLINE::IsLegallyNested() const {
621 if (stepcount == 0) {
622 return true;
623 }
624 int64_t parent_area = outer_area();
625 // We aren't going to modify the list, or its contents, but there is
626 // no const iterator.
627 C_OUTLINE_IT child_it(const_cast<C_OUTLINE_LIST *>(&children));
628 for (child_it.mark_cycle_pt(); !child_it.cycled_list(); child_it.forward()) {
629 const C_OUTLINE *child = child_it.data();
630 if (child->outer_area() * parent_area > 0 || !child->IsLegallyNested()) {
631 return false;
632 }
633 }
634 return true;
635 }
636
637 /**
638 * If this outline is smaller than the given min_size, delete this and
639 * remove from its list, via *it, after checking that *it points to this.
640 * Otherwise, if any children of this are too small, delete them.
641 * On entry, *it must be an iterator pointing to this. If this gets deleted
642 * then this is extracted from *it, so an iteration can continue.
643 * @param min_size minimum size for outline
644 * @param it outline iterator
645 */
646 void C_OUTLINE::RemoveSmallRecursive(int min_size, C_OUTLINE_IT *it) {
647 if (box.width() < min_size || box.height() < min_size) {
648 ASSERT_HOST(this == it->data());
649 delete it->extract(); // Too small so get rid of it and any children.
650 } else if (!children.empty()) {
651 // Search the children of this, deleting any that are too small.
652 C_OUTLINE_IT child_it(&children);
653 for (child_it.mark_cycle_pt(); !child_it.cycled_list(); child_it.forward()) {
654 C_OUTLINE *child = child_it.data();
655 child->RemoveSmallRecursive(min_size, &child_it);
656 }
657 }
658 }
659
660 // Factored out helpers below are used only by ComputeEdgeOffsets to operate
661 // on data from an 8-bit Pix, and assume that any input x and/or y are already
662 // constrained to be legal Pix coordinates.
663
664 /**
665 * Helper computes the local 2-D gradient (dx, dy) from the 2x2 cell centered
666 * on the given (x,y). If the cell would go outside the image, it is padded
667 * with white.
668 */
669 static void ComputeGradient(const l_uint32 *data, int wpl, int x, int y, int width, int height,
670 ICOORD *gradient) {
671 const l_uint32 *line = data + y * wpl;
672 int pix_x_y = x < width && y < height ? GET_DATA_BYTE(line, x) : 255;
673 int pix_x_prevy = x < width && y > 0 ? GET_DATA_BYTE(line - wpl, x) : 255;
674 int pix_prevx_prevy = x > 0 && y > 0 ? GET_DATA_BYTE(line - wpl, x - 1) : 255;
675 int pix_prevx_y = x > 0 && y < height ? GET_DATA_BYTE(line, x - 1) : 255;
676 gradient->set_x(pix_x_y + pix_x_prevy - (pix_prevx_y + pix_prevx_prevy));
677 gradient->set_y(pix_x_prevy + pix_prevx_prevy - (pix_x_y + pix_prevx_y));
678 }
679
680 /**
681 * Helper evaluates a vertical difference, (x,y) - (x,y-1), returning true if
682 * the difference, matches diff_sign and updating the best_diff, best_sum,
683 * best_y if a new max.
684 */
685 static bool EvaluateVerticalDiff(const l_uint32 *data, int wpl, int diff_sign, int x, int y,
686 int height, int *best_diff, int *best_sum, int *best_y) {
687 if (y <= 0 || y >= height) {
688 return false;
689 }
690 const l_uint32 *line = data + y * wpl;
691 int pixel1 = GET_DATA_BYTE(line - wpl, x);
692 int pixel2 = GET_DATA_BYTE(line, x);
693 int diff = (pixel2 - pixel1) * diff_sign;
694 if (diff > *best_diff) {
695 *best_diff = diff;
696 *best_sum = pixel1 + pixel2;
697 *best_y = y;
698 }
699 return diff > 0;
700 }
701
702 /**
703 * Helper evaluates a horizontal difference, (x,y) - (x-1,y), where y is implied
704 * by the input image line, returning true if the difference matches diff_sign
705 * and updating the best_diff, best_sum, best_x if a new max.
706 */
707 static bool EvaluateHorizontalDiff(const l_uint32 *line, int diff_sign, int x, int width,
708 int *best_diff, int *best_sum, int *best_x) {
709 if (x <= 0 || x >= width) {
710 return false;
711 }
712 int pixel1 = GET_DATA_BYTE(line, x - 1);
713 int pixel2 = GET_DATA_BYTE(line, x);
714 int diff = (pixel2 - pixel1) * diff_sign;
715 if (diff > *best_diff) {
716 *best_diff = diff;
717 *best_sum = pixel1 + pixel2;
718 *best_x = x;
719 }
720 return diff > 0;
721 }
722
723 /**
724 * Adds sub-pixel resolution EdgeOffsets for the outline if the supplied
725 * pix is 8-bit. Does nothing otherwise.
726 * Operation: Consider the following near-horizontal line:
727 * @verbatim
728 * _________
729 * |________
730 * |________
731 * @endverbatim
732 * At *every* position along this line, the gradient direction will be close
733 * to vertical. Extrapoaltion/interpolation of the position of the threshold
734 * that was used to binarize the image gives a more precise vertical position
735 * for each horizontal step, and the conflict in step direction and gradient
736 * direction can be used to ignore the vertical steps.
737 */
738 void C_OUTLINE::ComputeEdgeOffsets(int threshold, Image pix) {
739 if (pixGetDepth(pix) != 8) {
740 return;
741 }
742 const l_uint32 *data = pixGetData(pix);
743 int wpl = pixGetWpl(pix);
744 int width = pixGetWidth(pix);
745 int height = pixGetHeight(pix);
746 bool negative = flag(COUT_INVERSE);
747 delete[] offsets;
748 offsets = new EdgeOffset[stepcount];
749 ICOORD pos = start;
750 ICOORD prev_gradient;
751 ComputeGradient(data, wpl, pos.x(), height - pos.y(), width, height, &prev_gradient);
752 for (int s = 0; s < stepcount; ++s) {
753 ICOORD step_vec = step(s);
754 TPOINT pt1(pos);
755 pos += step_vec;
756 TPOINT pt2(pos);
757 ICOORD next_gradient;
758 ComputeGradient(data, wpl, pos.x(), height - pos.y(), width, height, &next_gradient);
759 // Use the sum of the prev and next as the working gradient.
760 ICOORD gradient = prev_gradient + next_gradient;
761 // best_diff will be manipulated to be always positive.
762 int best_diff = 0;
763 // offset will be the extrapolation of the location of the greyscale
764 // threshold from the edge with the largest difference, relative to the
765 // location of the binary edge.
766 int offset = 0;
767 if (pt1.y == pt2.y && abs(gradient.y()) * 2 >= abs(gradient.x())) {
768 // Horizontal step. diff_sign == 1 indicates black above.
769 int diff_sign = (pt1.x > pt2.x) == negative ? 1 : -1;
770 int x = std::min(pt1.x, pt2.x);
771 int y = height - pt1.y;
772 int best_sum = 0;
773 int best_y = y;
774 EvaluateVerticalDiff(data, wpl, diff_sign, x, y, height, &best_diff, &best_sum, &best_y);
775 // Find the strongest edge.
776 int test_y = y;
777 do {
778 ++test_y;
779 } while (EvaluateVerticalDiff(data, wpl, diff_sign, x, test_y, height, &best_diff, &best_sum,
780 &best_y));
781 test_y = y;
782 do {
783 --test_y;
784 } while (EvaluateVerticalDiff(data, wpl, diff_sign, x, test_y, height, &best_diff, &best_sum,
785 &best_y));
786 offset = diff_sign * (best_sum / 2 - threshold) + (y - best_y) * best_diff;
787 } else if (pt1.x == pt2.x && abs(gradient.x()) * 2 >= abs(gradient.y())) {
788 // Vertical step. diff_sign == 1 indicates black on the left.
789 int diff_sign = (pt1.y > pt2.y) == negative ? 1 : -1;
790 int x = pt1.x;
791 int y = height - std::max(pt1.y, pt2.y);
792 const l_uint32 *line = pixGetData(pix) + y * wpl;
793 int best_sum = 0;
794 int best_x = x;
795 EvaluateHorizontalDiff(line, diff_sign, x, width, &best_diff, &best_sum, &best_x);
796 // Find the strongest edge.
797 int test_x = x;
798 do {
799 ++test_x;
800 } while (
801 EvaluateHorizontalDiff(line, diff_sign, test_x, width, &best_diff, &best_sum, &best_x));
802 test_x = x;
803 do {
804 --test_x;
805 } while (
806 EvaluateHorizontalDiff(line, diff_sign, test_x, width, &best_diff, &best_sum, &best_x));
807 offset = diff_sign * (threshold - best_sum / 2) + (best_x - x) * best_diff;
808 }
809 offsets[s].offset_numerator = ClipToRange<int>(offset, -INT8_MAX, INT8_MAX);
810 offsets[s].pixel_diff = ClipToRange<int>(best_diff, 0, UINT8_MAX);
811 if (negative) {
812 gradient = -gradient;
813 }
814 // Compute gradient angle quantized to 256 directions, rotated by 64 (pi/2)
815 // to convert from gradient direction to edge direction.
816 offsets[s].direction = Modulo(FCOORD::binary_angle_plus_pi(gradient.angle()) + 64, 256);
817 prev_gradient = next_gradient;
818 }
819 }
820
821 /**
822 * Adds sub-pixel resolution EdgeOffsets for the outline using only
823 * a binary image source.
824 *
825 * Runs a sliding window of 5 edge steps over the outline, maintaining a count
826 * of the number of steps in each of the 4 directions in the window, and a
827 * sum of the x or y position of each step (as appropriate to its direction.)
828 * Ignores single-count steps EXCEPT the sharp U-turn and smoothes out the
829 * perpendicular direction. Eg
830 * @verbatim
831 * ___ ___ Chain code from the left:
832 * |___ ___ ___| 222122212223221232223000
833 * |___| |_| Corresponding counts of each direction:
834 * 0 00000000000000000123
835 * 1 11121111001111100000
836 * 2 44434443443333343321
837 * 3 00000001111111112111
838 * Count of direction at center 41434143413313143313
839 * Step gets used? YNYYYNYYYNYYNYNYYYyY (y= U-turn exception)
840 * Path redrawn showing only the used points:
841 * ___ ___
842 * ___ ___ ___|
843 * ___ _
844 * @endverbatim
845 * Sub-pixel edge position cannot be shown well with ASCII-art, but each
846 * horizontal step's y position is the mean of the y positions of the steps
847 * in the same direction in the sliding window, which makes a much smoother
848 * outline, without losing important detail.
849 */
850 void C_OUTLINE::ComputeBinaryOffsets() {
851 delete[] offsets;
852 offsets = new EdgeOffset[stepcount];
853 // Count of the number of steps in each direction in the sliding window.
854 int dir_counts[4];
855 // Sum of the positions (y for a horizontal step, x for vertical) in each
856 // direction in the sliding window.
857 int pos_totals[4];
858 memset(dir_counts, 0, sizeof(dir_counts));
859 memset(pos_totals, 0, sizeof(pos_totals));
860 ICOORD pos = start;
861 ICOORD tail_pos = pos;
862 // tail_pos is the trailing position, with the next point to be lost from
863 // the window.
864 tail_pos -= step(stepcount - 1);
865 tail_pos -= step(stepcount - 2);
866 // head_pos is the leading position, with the next point to be added to the
867 // window.
868 ICOORD head_pos = tail_pos;
869 // Set up the initial window with 4 points in [-2, 2)
870 for (int s = -2; s < 2; ++s) {
871 increment_step(s, 1, &head_pos, dir_counts, pos_totals);
872 }
873 for (int s = 0; s < stepcount; pos += step(s++)) {
874 // At step s, s in the middle of [s-2, s+2].
875 increment_step(s + 2, 1, &head_pos, dir_counts, pos_totals);
876 int dir_index = chain_code(s);
877 ICOORD step_vec = step(s);
878 int best_diff = 0;
879 int offset = 0;
880 // Use only steps that have a count of >=2 OR the strong U-turn with a
881 // single d and 2 at d-1 and 2 at d+1 (mod 4).
882 if (dir_counts[dir_index] >= 2 ||
883 (dir_counts[dir_index] == 1 && dir_counts[Modulo(dir_index - 1, 4)] == 2 &&
884 dir_counts[Modulo(dir_index + 1, 4)] == 2)) {
885 // Valid step direction.
886 best_diff = dir_counts[dir_index];
887 int edge_pos = step_vec.x() == 0 ? pos.x() : pos.y();
888 // The offset proposes that the actual step should be positioned at
889 // the mean position of the steps in the window of the same direction.
890 // See ASCII art above.
891 offset = pos_totals[dir_index] - best_diff * edge_pos;
892 }
893 offsets[s].offset_numerator = ClipToRange<int>(offset, -INT8_MAX, INT8_MAX);
894 offsets[s].pixel_diff = ClipToRange<int>(best_diff, 0, UINT8_MAX);
895 // The direction is just the vector from start to end of the window.
896 FCOORD direction(head_pos.x() - tail_pos.x(), head_pos.y() - tail_pos.y());
897 offsets[s].direction = direction.to_direction();
898 increment_step(s - 2, -1, &tail_pos, dir_counts, pos_totals);
899 }
900 }
901
902 /**
903 * Renders the outline to the given pix, with left and top being
904 * the coords of the upper-left corner of the pix.
905 */
906 void C_OUTLINE::render(int left, int top, Image pix) const {
907 ICOORD pos = start;
908 for (int stepindex = 0; stepindex < stepcount; ++stepindex) {
909 ICOORD next_step = step(stepindex);
910 if (next_step.y() < 0) {
911 pixRasterop(pix, 0, top - pos.y(), pos.x() - left, 1, PIX_NOT(PIX_DST), nullptr, 0, 0);
912 } else if (next_step.y() > 0) {
913 pixRasterop(pix, 0, top - pos.y() - 1, pos.x() - left, 1, PIX_NOT(PIX_DST), nullptr, 0, 0);
914 }
915 pos += next_step;
916 }
917 }
918
919 /**
920 * Renders just the outline to the given pix (no fill), with left and top
921 * being the coords of the upper-left corner of the pix.
922 * @param left coord
923 * @param top coord
924 * @param pix the pix to outline
925 */
926 void C_OUTLINE::render_outline(int left, int top, Image pix) const {
927 ICOORD pos = start;
928 for (int stepindex = 0; stepindex < stepcount; ++stepindex) {
929 ICOORD next_step = step(stepindex);
930 if (next_step.y() < 0) {
931 pixSetPixel(pix, pos.x() - left, top - pos.y(), 1);
932 } else if (next_step.y() > 0) {
933 pixSetPixel(pix, pos.x() - left - 1, top - pos.y() - 1, 1);
934 } else if (next_step.x() < 0) {
935 pixSetPixel(pix, pos.x() - left - 1, top - pos.y(), 1);
936 } else if (next_step.x() > 0) {
937 pixSetPixel(pix, pos.x() - left, top - pos.y() - 1, 1);
938 }
939 pos += next_step;
940 }
941 }
942
943 /**
944 * @name C_OUTLINE::plot
945 *
946 * Draw the outline in the given colour.
947 * @param window window to draw in
948 * @param colour colour to draw in
949 */
950
951 #ifndef GRAPHICS_DISABLED
952 void C_OUTLINE::plot(ScrollView *window, ScrollView::Color colour) const {
953 int16_t stepindex; // index to cstep
954 ICOORD pos; // current position
955 DIR128 stepdir; // direction of step
956
957 pos = start; // current position
958 window->Pen(colour);
959 if (stepcount == 0) {
960 window->Rectangle(box.left(), box.top(), box.right(), box.bottom());
961 return;
962 }
963 window->SetCursor(pos.x(), pos.y());
964
965 stepindex = 0;
966 while (stepindex < stepcount) {
967 pos += step(stepindex); // step to next
968 stepdir = step_dir(stepindex);
969 stepindex++; // count steps
970 // merge straight lines
971 while (stepindex < stepcount && stepdir.get_dir() == step_dir(stepindex).get_dir()) {
972 pos += step(stepindex);
973 stepindex++;
974 }
975 window->DrawTo(pos.x(), pos.y());
976 }
977 }
978
979 /**
980 * Draws the outline in the given colour, normalized using the given denorm,
981 * making use of sub-pixel accurate information if available.
982 */
983 void C_OUTLINE::plot_normed(const DENORM &denorm, ScrollView::Color colour,
984 ScrollView *window) const {
985 window->Pen(colour);
986 if (stepcount == 0) {
987 window->Rectangle(box.left(), box.top(), box.right(), box.bottom());
988 return;
989 }
990 const DENORM *root_denorm = denorm.RootDenorm();
991 ICOORD pos = start; // current position
992 FCOORD f_pos = sub_pixel_pos_at_index(pos, 0);
993 FCOORD pos_normed;
994 denorm.NormTransform(root_denorm, f_pos, &pos_normed);
995 window->SetCursor(IntCastRounded(pos_normed.x()), IntCastRounded(pos_normed.y()));
996 for (int s = 0; s < stepcount; pos += step(s++)) {
997 int edge_weight = edge_strength_at_index(s);
998 if (edge_weight == 0) {
999 // This point has conflicting gradient and step direction, so ignore it.
1000 continue;
1001 }
1002 FCOORD f_pos = sub_pixel_pos_at_index(pos, s);
1003 FCOORD pos_normed;
1004 denorm.NormTransform(root_denorm, f_pos, &pos_normed);
1005 window->DrawTo(IntCastRounded(pos_normed.x()), IntCastRounded(pos_normed.y()));
1006 }
1007 }
1008 #endif
1009
1010 /**
1011 * @name C_OUTLINE::operator=
1012 *
1013 * Assignment - deep copy data
1014 * @param source assign from this
1015 */
1016
1017 C_OUTLINE &C_OUTLINE::operator=(const C_OUTLINE &source) {
1018 box = source.box;
1019 start = source.start;
1020 if (!children.empty()) {
1021 children.clear();
1022 }
1023 children.deep_copy(&source.children, &deep_copy);
1024 delete[] offsets;
1025 offsets = nullptr;
1026 stepcount = source.stepcount;
1027 if (stepcount > 0) {
1028 steps.resize(step_mem());
1029 memmove(&steps[0], &source.steps[0], step_mem());
1030 if (source.offsets != nullptr) {
1031 offsets = new EdgeOffset[stepcount];
1032 memcpy(offsets, source.offsets, stepcount * sizeof(*offsets));
1033 }
1034 }
1035 return *this;
1036 }
1037
1038 /**
1039 * Helper for ComputeBinaryOffsets. Increments pos, dir_counts, pos_totals
1040 * by the step, increment, and vertical step ? x : y position * increment
1041 * at step s Mod stepcount respectively. Used to add or subtract the
1042 * direction and position to/from accumulators of a small neighbourhood.
1043 */
1044 void C_OUTLINE::increment_step(int s, int increment, ICOORD *pos, int *dir_counts,
1045 int *pos_totals) const {
1046 int step_index = Modulo(s, stepcount);
1047 int dir_index = chain_code(step_index);
1048 dir_counts[dir_index] += increment;
1049 ICOORD step_vec = step(step_index);
1050 if (step_vec.x() == 0) {
1051 pos_totals[dir_index] += pos->x() * increment;
1052 } else {
1053 pos_totals[dir_index] += pos->y() * increment;
1054 }
1055 *pos += step_vec;
1056 }
1057
1058 ICOORD C_OUTLINE::chain_step(int chaindir) {
1059 return step_coords[chaindir % 4];
1060 }
1061
1062 } // namespace tesseract