tesseract  5.0.0
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 
43 namespace tesseract {
44 
45 ICOORD C_OUTLINE::step_coords[4] = {ICOORD(-1, 0), ICOORD(0, -1), ICOORD(1, 0), ICOORD(0, 1)};
46 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 
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 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 
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 
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 
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 
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 
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 
1059  return step_coords[chaindir % 4];
1060 }
1061 
1062 } // namespace tesseract
#define INTERSECTING
Definition: coutln.h:40
#define MODULUS
Definition: mod128.h:26
#define ASSERT_HOST(x)
Definition: errcode.h:59
@ TBOX
int IntCastRounded(double x)
Definition: helpers.h:175
@ COUT_INVERSE
Definition: coutln.h:46
int Modulo(int a, int b)
Definition: helpers.h:158
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
C_OUTLINE_LIST * child()
Definition: coutln.h:108
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
const ICOORD & start_pos() const
Definition: coutln.h:147
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
static C_OUTLINE * deep_copy(const C_OUTLINE *src)
Definition: coutln.h:261
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
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:338
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:723
void Rectangle(int x1, int y1, int x2, int y2)
Definition: scrollview.cpp:589
void SetCursor(int x, int y)
Definition: scrollview.cpp:498
void DrawTo(int x, int y)
Definition: scrollview.cpp:504