tesseract v5.3.3.20231005
coutln.cpp
Go to the documentation of this file.
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
43namespace tesseract {
44
45ICOORD C_OUTLINE::step_coords[4] = {ICOORD(-1, 0), ICOORD(0, -1), ICOORD(1, 0), ICOORD(0, 1)};
46
57C_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
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
143C_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.
241void 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
257int32_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
293int32_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
313int32_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
347int32_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
475bool 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
513int16_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
551int16_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
580void 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
603void 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
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
646void 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
669static 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
685static 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
707static 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
738void 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
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
906void 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
926void 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
951#ifndef GRAPHICS_DISABLED
952void 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
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
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
1044void 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
1059 return step_coords[chaindir % 4];
1060}
1061
1062} // namespace tesseract
#define ASSERT_HOST(x)
Definition: errcode.h:54
#define MODULUS
Definition: mod128.h:26
#define INTERSECTING
Definition: coutln.h:40
@ TBOX
const double y
int * count
int IntCastRounded(double x)
Definition: helpers.h:170
@ COUT_INVERSE
Definition: coutln.h:46
int Modulo(int a, int b)
Definition: helpers.h:153
TDimension x
Definition: blobs.h:89
TDimension y
Definition: blobs.h:90
uint8_t direction
Definition: coutln.h:69
uint8_t pixel_diff
Definition: coutln.h:68
int8_t offset_numerator
Definition: coutln.h:67
static ICOORD chain_step(int chaindir)
Definition: coutln.cpp:1058
int32_t pathlength() const
Definition: coutln.h:134
void set_step(int16_t stepindex, int8_t stepdir)
Definition: coutln.h:116
C_OUTLINE & operator=(const C_OUTLINE &source)
Definition: coutln.cpp:1017
bool IsLegallyNested() const
Definition: coutln.cpp:620
int32_t area() const
Definition: coutln.cpp:257
ICOORD step(int index) const
Definition: coutln.h:143
void plot(ScrollView *window, ScrollView::Color colour) const
Definition: coutln.cpp:952
int32_t perimeter() const
Definition: coutln.cpp:293
static C_OUTLINE * deep_copy(const C_OUTLINE *src)
Definition: coutln.h:261
void move(const ICOORD vec)
Definition: coutln.cpp:603
int16_t turn_direction() const
Definition: coutln.cpp:551
int16_t winding_number(ICOORD testpt) const
Definition: coutln.cpp:513
DIR128 step_dir(int index) const
Definition: coutln.h:138
int32_t outer_area() const
Definition: coutln.cpp:313
void ComputeBinaryOffsets()
Definition: coutln.cpp:850
C_OUTLINE_LIST * child()
Definition: coutln.h:108
int chain_code(int index) const
Definition: coutln.h:197
void plot_normed(const DENORM &denorm, ScrollView::Color colour, ScrollView *window) const
Definition: coutln.cpp:983
void render_outline(int left, int top, Image pix) const
Definition: coutln.cpp:926
bool operator<(const C_OUTLINE &other) const
Definition: coutln.cpp:475
FCOORD sub_pixel_pos_at_index(const ICOORD &pos, int index) const
Definition: coutln.h:163
int32_t count_transitions(int32_t threshold)
Definition: coutln.cpp:347
void RemoveSmallRecursive(int min_size, C_OUTLINE_IT *it)
Definition: coutln.cpp:646
int edge_strength_at_index(int index) const
Definition: coutln.h:188
static void FakeOutline(const TBOX &box, C_OUTLINE_LIST *outlines)
Definition: coutln.cpp:241
const ICOORD & start_pos() const
Definition: coutln.h:147
void ComputeEdgeOffsets(int threshold, Image pix)
Definition: coutln.cpp:738
bool flag(C_OUTLINE_FLAGS mask) const
Definition: coutln.h:98
void render(int left, int top, Image pix) const
Definition: coutln.cpp:906
CRACKEDGE * next
Definition: crakedge.h:37
int8_t get_dir() const
Definition: mod128.h:79
void NormTransform(const DENORM *first_norm, const TPOINT &pt, TPOINT *transformed) const
Definition: normalis.cpp:340
const DENORM * RootDenorm() const
Definition: normalis.h:249
integer coordinate
Definition: points.h:36
void rotate(const FCOORD &vec)
Definition: points.h:511
void set_x(TDimension xin)
rewrite function
Definition: points.h:67
TDimension y() const
access_function
Definition: points.h:62
void set_y(TDimension yin)
rewrite function
Definition: points.h:71
TDimension x() const
access function
Definition: points.h:58
float angle() const
find angle
Definition: points.h:103
uint8_t to_direction() const
Definition: points.cpp:123
float y() const
Definition: points.h:209
float x() const
Definition: points.h:206
static uint8_t binary_angle_plus_pi(double angle)
Definition: points.cpp:136
TDimension left() const
Definition: rect.h:82
TDimension height() const
Definition: rect.h:118
TDimension width() const
Definition: rect.h:126
void move(const ICOORD vec)
Definition: rect.h:170
void rotate(const FCOORD &vec)
Definition: rect.h:210
TDimension top() const
Definition: rect.h:68
ICOORD botright() const
Definition: rect.h:106
ICOORD topleft() const
Definition: rect.h:110
TDimension right() const
Definition: rect.h:89
bool overlap(const TBOX &box) const
Definition: rect.h:363
TDimension bottom() const
Definition: rect.h:75
bool contains(const FCOORD pt) const
Definition: rect.h:344
int32_t area() const
Definition: rect.h:134
void Pen(Color color)
Definition: scrollview.cpp:710
void Rectangle(int x1, int y1, int x2, int y2)
Definition: scrollview.cpp:576
void SetCursor(int x, int y)
Definition: scrollview.cpp:485
void DrawTo(int x, int y)
Definition: scrollview.cpp:491