tesseract  5.0.0-alpha-619-ge9db
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 "coutln.h"
20 #include <algorithm> // for max, min
21 #include <cmath> // for abs
22 #include <cstdlib> // for abs
23 #include <cstring> // for memset, memcpy, memmove
24 #include "allheaders.h" // for pixSetPixel, pixGetData, pixRasterop, pixGe...
25 #include "arrayaccess.h" // for GET_DATA_BYTE
26 #include "blobs.h" // for TPOINT
27 #include "crakedge.h" // for CRACKEDGE
28 #include "environ.h" // for l_uint32
29 #include "errcode.h" // for ASSERT_HOST
30 #include <tesseract/helpers.h> // for ClipToRange, IntCastRounded, Modulo
31 #include "normalis.h" // for DENORM
32 #include "pix.h" // for Pix (ptr only), PIX_DST, PIX_NOT
33 
34 // Include automatically generated configuration file if running autoconf.
35 #ifdef HAVE_CONFIG_H
36 #include "config_auto.h"
37 #endif
38 
40 ICOORD C_OUTLINE::step_coords[4] = {
41  ICOORD (-1, 0), ICOORD (0, -1), ICOORD (1, 0), ICOORD (0, 1)
42 };
43 
54 C_OUTLINE::C_OUTLINE(CRACKEDGE* startpt, ICOORD bot_left, ICOORD top_right,
55  int16_t length)
56  : box(bot_left, top_right), start(startpt->pos), offsets(nullptr) {
57  int16_t stepindex; //index to step
58  CRACKEDGE *edgept; //current point
59 
60  stepcount = length; //no of steps
61  if (length == 0) {
62  steps = nullptr;
63  return;
64  }
65  //get memory
66  steps = static_cast<uint8_t *>(calloc(step_mem(), 1));
67  edgept = startpt;
68 
69  for (stepindex = 0; stepindex < length; stepindex++) {
70  //set compact step
71  set_step (stepindex, edgept->stepdir);
72  edgept = edgept->next;
73  }
74 }
75 
82 //constructor
83  //steps to copy
84 ICOORD startpt, DIR128 * new_steps,
85 int16_t length //length of loop
86 ):start (startpt), offsets(nullptr) {
87  int8_t dirdiff; //direction difference
88  DIR128 prevdir; //previous direction
89  DIR128 dir; //current direction
90  DIR128 lastdir; //dir of last step
91  TBOX new_box; //easy bounding
92  int16_t stepindex; //index to step
93  int16_t srcindex; //source steps
94  ICOORD pos; //current position
95 
96  pos = startpt;
97  stepcount = length; // No. of steps.
98  ASSERT_HOST(length >= 0);
99  steps = static_cast<uint8_t*>(calloc(step_mem(), 1)); // Get memory.
100 
101  lastdir = new_steps[length - 1];
102  prevdir = lastdir;
103  for (stepindex = 0, srcindex = 0; srcindex < length;
104  stepindex++, srcindex++) {
105  new_box = TBOX (pos, pos);
106  box += new_box;
107  //copy steps
108  dir = new_steps[srcindex];
109  set_step(stepindex, dir);
110  dirdiff = dir - prevdir;
111  pos += step (stepindex);
112  if ((dirdiff == 64 || dirdiff == -64) && stepindex > 0) {
113  stepindex -= 2; //cancel there-and-back
114  prevdir = stepindex >= 0 ? step_dir (stepindex) : lastdir;
115  }
116  else
117  prevdir = dir;
118  }
119  ASSERT_HOST (pos.x () == startpt.x () && pos.y () == startpt.y ());
120  do {
121  dirdiff = step_dir (stepindex - 1) - step_dir (0);
122  if (dirdiff == 64 || dirdiff == -64) {
123  start += step (0);
124  stepindex -= 2; //cancel there-and-back
125  for (int i = 0; i < stepindex; ++i)
126  set_step(i, step_dir(i + 1));
127  }
128  }
129  while (stepindex > 1 && (dirdiff == 64 || dirdiff == -64));
130  stepcount = stepindex;
131  ASSERT_HOST (stepcount >= 4);
132 }
133 
142 C_OUTLINE::C_OUTLINE(C_OUTLINE* srcline, FCOORD rotation) : offsets(nullptr) {
143  TBOX new_box; //easy bounding
144  int16_t stepindex; //index to step
145  int16_t dirdiff; //direction change
146  ICOORD pos; //current position
147  ICOORD prevpos; //previous dest point
148 
149  ICOORD destpos; //destination point
150  int16_t destindex = INT16_MAX; //index to step
151  DIR128 dir; //coded direction
152  uint8_t new_step;
153 
154  stepcount = srcline->stepcount * 2;
155  if (stepcount == 0) {
156  steps = nullptr;
157  box = srcline->box;
158  box.rotate(rotation);
159  return;
160  }
161  //get memory
162  steps = static_cast<uint8_t *>(calloc(step_mem(), 1));
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 =
188  step_dir (destindex - 1) - step_dir (destindex - 2)) !=
189  -64 && dirdiff != 64)) {
190  set_step(destindex++, dir + round2);
191  prevpos += step(destindex - 1);
192  } else {
193  prevpos -= step(destindex - 1);
194  destindex--;
195  prevpos -= step(destindex - 1);
196  set_step(destindex - 1, dir + round2);
197  prevpos += step(destindex - 1);
198  }
199  }
200  else {
201  set_step(destindex++, dir);
202  prevpos += step(destindex - 1);
203  }
204  while (destindex >= 2 &&
205  ((dirdiff =
206  step_dir (destindex - 1) - step_dir (destindex - 2)) == -64 ||
207  dirdiff == 64)) {
208  prevpos -= step(destindex - 1);
209  prevpos -= step(destindex - 2);
210  destindex -= 2; // Forget u turn
211  }
212  //ASSERT_HOST(prevpos.x() == destpos.x() && prevpos.y() == destpos.y());
213  new_box = TBOX (destpos, destpos);
214  box += new_box;
215  }
216  }
217  ASSERT_HOST (destpos.x () == start.x () && destpos.y () == start.y ());
218  dirdiff = step_dir (destindex - 1) - step_dir (0);
219  while ((dirdiff == 64 || dirdiff == -64) && destindex > 1) {
220  start += step (0);
221  destindex -= 2;
222  for (int i = 0; i < destindex; ++i)
223  set_step(i, step_dir(i + 1));
224  dirdiff = step_dir (destindex - 1) - step_dir (0);
225  }
226  if (destindex >= 4)
227  break;
228  }
229  ASSERT_HOST(destindex <= stepcount);
230  stepcount = destindex;
231  destpos = start;
232  for (stepindex = 0; stepindex < stepcount; stepindex++) {
233  destpos += step (stepindex);
234  }
235  ASSERT_HOST (destpos.x () == start.x () && destpos.y () == start.y ());
236 }
237 
238 // Build a fake outline, given just a bounding box and append to the list.
239 void C_OUTLINE::FakeOutline(const TBOX& box, C_OUTLINE_LIST* outlines) {
240  C_OUTLINE_IT ol_it(outlines);
241  // Make a C_OUTLINE from the bounds. This is a bit of a hack,
242  // as there is no outline, just a bounding box, but it works nicely.
243  CRACKEDGE start;
244  start.pos = box.topleft();
245  C_OUTLINE* outline = new C_OUTLINE(&start, box.topleft(), box.botright(), 0);
246  ol_it.add_to_end(outline);
247 }
248 
255 int32_t C_OUTLINE::area() const {
256  int stepindex; //current step
257  int32_t total_steps; //steps to do
258  int32_t total; //total area
259  ICOORD pos; //position of point
260  ICOORD next_step; //step to next pix
261  // We aren't going to modify the list, or its contents, but there is
262  // no const iterator.
263  C_OUTLINE_IT it(const_cast<C_OUTLINE_LIST*>(&children));
264 
265  pos = start_pos ();
266  total_steps = pathlength ();
267  total = 0;
268  for (stepindex = 0; stepindex < total_steps; stepindex++) {
269  //all intersected
270  next_step = step (stepindex);
271  if (next_step.x () < 0)
272  total += pos.y ();
273  else if (next_step.x () > 0)
274  total -= pos.y ();
275  pos += next_step;
276  }
277  for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ())
278  total += it.data ()->area ();//add areas of children
279 
280  return total;
281 }
282 
289 int32_t C_OUTLINE::perimeter() const {
290  int32_t total_steps; // Return value.
291  // We aren't going to modify the list, or its contents, but there is
292  // no const iterator.
293  C_OUTLINE_IT it(const_cast<C_OUTLINE_LIST*>(&children));
294 
295  total_steps = pathlength();
296  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward())
297  total_steps += it.data()->pathlength(); // Add perimeters of children.
298 
299  return total_steps;
300 }
301 
308 int32_t C_OUTLINE::outer_area() const {
309  int stepindex; //current step
310  int32_t total_steps; //steps to do
311  int32_t total; //total area
312  ICOORD pos; //position of point
313  ICOORD next_step; //step to next pix
314 
315  pos = start_pos ();
316  total_steps = pathlength ();
317  if (total_steps == 0)
318  return box.area();
319  total = 0;
320  for (stepindex = 0; stepindex < total_steps; stepindex++) {
321  //all intersected
322  next_step = step (stepindex);
323  if (next_step.x () < 0)
324  total += pos.y ();
325  else if (next_step.x () > 0)
326  total -= pos.y ();
327  pos += next_step;
328  }
329 
330  return total;
331 }
332 
340 int32_t C_OUTLINE::count_transitions(int32_t threshold) {
341  bool first_was_max_x; //what was first
342  bool first_was_max_y;
343  bool looking_for_max_x; //what is next
344  bool looking_for_min_x;
345  bool looking_for_max_y; //what is next
346  bool looking_for_min_y;
347  int stepindex; //current step
348  int32_t total_steps; //steps to do
349  //current limits
350  int32_t max_x, min_x, max_y, min_y;
351  int32_t initial_x, initial_y; //initial limits
352  int32_t total; //total changes
353  ICOORD pos; //position of point
354  ICOORD next_step; //step to next pix
355 
356  pos = start_pos();
357  total_steps = pathlength();
358  total = 0;
359  max_x = min_x = pos.x();
360  max_y = min_y = pos.y();
361  looking_for_max_x = true;
362  looking_for_min_x = true;
363  looking_for_max_y = true;
364  looking_for_min_y = true;
365  first_was_max_x = false;
366  first_was_max_y = false;
367  initial_x = pos.x();
368  initial_y = pos.y(); //stop uninit warning
369  for (stepindex = 0; stepindex < total_steps; stepindex++) {
370  //all intersected
371  next_step = step(stepindex);
372  pos += next_step;
373  if (next_step.x() < 0) {
374  if (looking_for_max_x && pos.x() < min_x)
375  min_x = pos.x();
376  if (looking_for_min_x && max_x - pos.x() > threshold) {
377  if (looking_for_max_x) {
378  initial_x = max_x;
379  first_was_max_x = false;
380  }
381  total++;
382  looking_for_max_x = true;
383  looking_for_min_x = false;
384  min_x = pos.x(); //reset min
385  }
386  }
387  else if (next_step.x() > 0) {
388  if (looking_for_min_x && pos.x() > max_x)
389  max_x = pos.x();
390  if (looking_for_max_x && pos.x() - min_x > threshold) {
391  if (looking_for_min_x) {
392  initial_x = min_x; //remember first min
393  first_was_max_x = true;
394  }
395  total++;
396  looking_for_max_x = false;
397  looking_for_min_x = true;
398  max_x = pos.x();
399  }
400  }
401  else if (next_step.y() < 0) {
402  if (looking_for_max_y && pos.y() < min_y)
403  min_y = pos.y();
404  if (looking_for_min_y && max_y - pos.y() > threshold) {
405  if (looking_for_max_y) {
406  initial_y = max_y; //remember first max
407  first_was_max_y = false;
408  }
409  total++;
410  looking_for_max_y = true;
411  looking_for_min_y = false;
412  min_y = pos.y(); //reset min
413  }
414  }
415  else {
416  if (looking_for_min_y && pos.y() > max_y)
417  max_y = pos.y();
418  if (looking_for_max_y && pos.y() - min_y > threshold) {
419  if (looking_for_min_y) {
420  initial_y = min_y; //remember first min
421  first_was_max_y = true;
422  }
423  total++;
424  looking_for_max_y = false;
425  looking_for_min_y = true;
426  max_y = pos.y();
427  }
428  }
429 
430  }
431  if (first_was_max_x && looking_for_min_x) {
432  if (max_x - initial_x > threshold)
433  total++;
434  else
435  total--;
436  }
437  else if (!first_was_max_x && looking_for_max_x) {
438  if (initial_x - min_x > threshold)
439  total++;
440  else
441  total--;
442  }
443  if (first_was_max_y && looking_for_min_y) {
444  if (max_y - initial_y > threshold)
445  total++;
446  else
447  total--;
448  }
449  else if (!first_was_max_y && looking_for_max_y) {
450  if (initial_y - min_y > threshold)
451  total++;
452  else
453  total--;
454  }
455 
456  return total;
457 }
458 
466 bool
467 C_OUTLINE::operator<(const C_OUTLINE& other) const {
468  int16_t count = 0; //winding count
469  ICOORD pos; //position of point
470  int32_t stepindex; //index to cstep
471 
472  if (!box.overlap (other.box))
473  return false; //can't be contained
474  if (stepcount == 0)
475  return other.box.contains(this->box);
476 
477  pos = start;
478  for (stepindex = 0; stepindex < stepcount
479  && (count = other.winding_number (pos)) == INTERSECTING; stepindex++)
480  pos += step (stepindex); //try all points
481  if (count == INTERSECTING) {
482  //all intersected
483  pos = other.start;
484  for (stepindex = 0; stepindex < other.stepcount
485  && (count = winding_number (pos)) == INTERSECTING; stepindex++)
486  //try other way round
487  pos += other.step (stepindex);
488  return count == INTERSECTING || count == 0;
489  }
490  return count != 0;
491 }
492 
500 int16_t C_OUTLINE::winding_number(ICOORD point) const {
501  int16_t stepindex; //index to cstep
502  int16_t count; //winding count
503  ICOORD vec; //to current point
504  ICOORD stepvec; //step vector
505  int32_t cross; //cross product
506 
507  vec = start - point; //vector to it
508  count = 0;
509  for (stepindex = 0; stepindex < stepcount; stepindex++) {
510  stepvec = step (stepindex); //get the step
511  //crossing the line
512  if (vec.y () <= 0 && vec.y () + stepvec.y () > 0) {
513  cross = vec * stepvec; //cross product
514  if (cross > 0)
515  count++; //crossing right half
516  else if (cross == 0)
517  return INTERSECTING; //going through point
518  }
519  else if (vec.y () > 0 && vec.y () + stepvec.y () <= 0) {
520  cross = vec * stepvec;
521  if (cross < 0)
522  count--; //crossing back
523  else if (cross == 0)
524  return INTERSECTING; //illegal
525  }
526  vec += stepvec; //sum vectors
527  }
528  return count; //winding number
529 }
530 
537 int16_t C_OUTLINE::turn_direction() const { //winding number
538  DIR128 prevdir; //previous direction
539  DIR128 dir; //current direction
540  int16_t stepindex; //index to cstep
541  int8_t dirdiff; //direction difference
542  int16_t count; //winding count
543 
544  if (stepcount == 0)
545  return 128;
546  count = 0;
547  prevdir = step_dir (stepcount - 1);
548  for (stepindex = 0; stepindex < stepcount; stepindex++) {
549  dir = step_dir (stepindex);
550  dirdiff = dir - prevdir;
551  ASSERT_HOST (dirdiff == 0 || dirdiff == 32 || dirdiff == -32);
552  count += dirdiff;
553  prevdir = dir;
554  }
555  ASSERT_HOST (count == 128 || count == -128);
556  return count; //winding number
557 }
558 
565 void C_OUTLINE::reverse() { //reverse drection
566  DIR128 halfturn = MODULUS / 2; //amount to shift
567  DIR128 stepdir; //direction of step
568  int16_t stepindex; //index to cstep
569  int16_t farindex; //index to other side
570  int16_t halfsteps; //half of stepcount
571 
572  halfsteps = (stepcount + 1) / 2;
573  for (stepindex = 0; stepindex < halfsteps; stepindex++) {
574  farindex = stepcount - stepindex - 1;
575  stepdir = step_dir (stepindex);
576  set_step (stepindex, step_dir (farindex) + halfturn);
577  set_step (farindex, stepdir + halfturn);
578  }
579 }
580 
588 void C_OUTLINE::move(const ICOORD vec) {
589  C_OUTLINE_IT it(&children); // iterator
590 
591  box.move (vec);
592  start += vec;
593 
594  for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ())
595  it.data ()->move (vec); // move child outlines
596 }
597 
605  if (stepcount == 0) return true;
606  int64_t parent_area = outer_area();
607  // We aren't going to modify the list, or its contents, but there is
608  // no const iterator.
609  C_OUTLINE_IT child_it(const_cast<C_OUTLINE_LIST*>(&children));
610  for (child_it.mark_cycle_pt(); !child_it.cycled_list(); child_it.forward()) {
611  const C_OUTLINE* child = child_it.data();
612  if (child->outer_area() * parent_area > 0 || !child->IsLegallyNested())
613  return false;
614  }
615  return true;
616 }
617 
627 void C_OUTLINE::RemoveSmallRecursive(int min_size, C_OUTLINE_IT* it) {
628  if (box.width() < min_size || box.height() < min_size) {
629  ASSERT_HOST(this == it->data());
630  delete it->extract(); // Too small so get rid of it and any children.
631  } else if (!children.empty()) {
632  // Search the children of this, deleting any that are too small.
633  C_OUTLINE_IT child_it(&children);
634  for (child_it.mark_cycle_pt(); !child_it.cycled_list();
635  child_it.forward()) {
636  C_OUTLINE* child = child_it.data();
637  child->RemoveSmallRecursive(min_size, &child_it);
638  }
639  }
640 }
641 
642 // Factored out helpers below are used only by ComputeEdgeOffsets to operate
643 // on data from an 8-bit Pix, and assume that any input x and/or y are already
644 // constrained to be legal Pix coordinates.
645 
651 static void ComputeGradient(const l_uint32* data, int wpl,
652  int x, int y, int width, int height,
653  ICOORD* gradient) {
654  const l_uint32* line = data + y * wpl;
655  int pix_x_y = x < width && y < height ? GET_DATA_BYTE(line, x) : 255;
656  int pix_x_prevy = x < width && y > 0 ? GET_DATA_BYTE(line - wpl, x) : 255;
657  int pix_prevx_prevy = x > 0 && y > 0 ? GET_DATA_BYTE(line - wpl, x - 1) : 255;
658  int pix_prevx_y = x > 0 && y < height ? GET_DATA_BYTE(line, x - 1) : 255;
659  gradient->set_x(pix_x_y + pix_x_prevy - (pix_prevx_y + pix_prevx_prevy));
660  gradient->set_y(pix_x_prevy + pix_prevx_prevy - (pix_x_y + pix_prevx_y));
661 }
662 
668 static bool EvaluateVerticalDiff(const l_uint32* data, int wpl, int diff_sign,
669  int x, int y, int height,
670  int* best_diff, int* best_sum, int* best_y) {
671  if (y <= 0 || y >= height)
672  return false;
673  const l_uint32* line = data + y * wpl;
674  int pixel1 = GET_DATA_BYTE(line - wpl, x);
675  int pixel2 = GET_DATA_BYTE(line, x);
676  int diff = (pixel2 - pixel1) * diff_sign;
677  if (diff > *best_diff) {
678  *best_diff = diff;
679  *best_sum = pixel1 + pixel2;
680  *best_y = y;
681  }
682  return diff > 0;
683 }
684 
690 static bool EvaluateHorizontalDiff(const l_uint32* line, int diff_sign,
691  int x, int width,
692  int* best_diff, int* best_sum, int* best_x) {
693  if (x <= 0 || x >= width)
694  return false;
695  int pixel1 = GET_DATA_BYTE(line, x - 1);
696  int pixel2 = GET_DATA_BYTE(line, x);
697  int diff = (pixel2 - pixel1) * diff_sign;
698  if (diff > *best_diff) {
699  *best_diff = diff;
700  *best_sum = pixel1 + pixel2;
701  *best_x = x;
702  }
703  return diff > 0;
704 }
705 
721 void C_OUTLINE::ComputeEdgeOffsets(int threshold, Pix* pix) {
722  if (pixGetDepth(pix) != 8) return;
723  const l_uint32* data = pixGetData(pix);
724  int wpl = pixGetWpl(pix);
725  int width = pixGetWidth(pix);
726  int height = pixGetHeight(pix);
727  bool negative = flag(COUT_INVERSE);
728  delete [] offsets;
729  offsets = new EdgeOffset[stepcount];
730  ICOORD pos = start;
731  ICOORD prev_gradient;
732  ComputeGradient(data, wpl, pos.x(), height - pos.y(), width, height,
733  &prev_gradient);
734  for (int s = 0; s < stepcount; ++s) {
735  ICOORD step_vec = step(s);
736  TPOINT pt1(pos);
737  pos += step_vec;
738  TPOINT pt2(pos);
739  ICOORD next_gradient;
740  ComputeGradient(data, wpl, pos.x(), height - pos.y(), width, height,
741  &next_gradient);
742  // Use the sum of the prev and next as the working gradient.
743  ICOORD gradient = prev_gradient + next_gradient;
744  // best_diff will be manipulated to be always positive.
745  int best_diff = 0;
746  // offset will be the extrapolation of the location of the greyscale
747  // threshold from the edge with the largest difference, relative to the
748  // location of the binary edge.
749  int offset = 0;
750  if (pt1.y == pt2.y && abs(gradient.y()) * 2 >= abs(gradient.x())) {
751  // Horizontal step. diff_sign == 1 indicates black above.
752  int diff_sign = (pt1.x > pt2.x) == negative ? 1 : -1;
753  int x = std::min(pt1.x, pt2.x);
754  int y = height - pt1.y;
755  int best_sum = 0;
756  int best_y = y;
757  EvaluateVerticalDiff(data, wpl, diff_sign, x, y, height,
758  &best_diff, &best_sum, &best_y);
759  // Find the strongest edge.
760  int test_y = y;
761  do {
762  ++test_y;
763  } while (EvaluateVerticalDiff(data, wpl, diff_sign, x, test_y, height,
764  &best_diff, &best_sum, &best_y));
765  test_y = y;
766  do {
767  --test_y;
768  } while (EvaluateVerticalDiff(data, wpl, diff_sign, x, test_y, height,
769  &best_diff, &best_sum, &best_y));
770  offset = diff_sign * (best_sum / 2 - threshold) +
771  (y - best_y) * best_diff;
772  } else if (pt1.x == pt2.x && abs(gradient.x()) * 2 >= abs(gradient.y())) {
773  // Vertical step. diff_sign == 1 indicates black on the left.
774  int diff_sign = (pt1.y > pt2.y) == negative ? 1 : -1;
775  int x = pt1.x;
776  int y = height - std::max(pt1.y, pt2.y);
777  const l_uint32* line = pixGetData(pix) + y * wpl;
778  int best_sum = 0;
779  int best_x = x;
780  EvaluateHorizontalDiff(line, diff_sign, x, width,
781  &best_diff, &best_sum, &best_x);
782  // Find the strongest edge.
783  int test_x = x;
784  do {
785  ++test_x;
786  } while (EvaluateHorizontalDiff(line, diff_sign, test_x, width,
787  &best_diff, &best_sum, &best_x));
788  test_x = x;
789  do {
790  --test_x;
791  } while (EvaluateHorizontalDiff(line, diff_sign, test_x, width,
792  &best_diff, &best_sum, &best_x));
793  offset = diff_sign * (threshold - best_sum / 2) +
794  (best_x - x) * best_diff;
795  }
796  offsets[s].offset_numerator =
797  ClipToRange<int>(offset, -INT8_MAX, INT8_MAX);
798  offsets[s].pixel_diff = ClipToRange<int>(best_diff, 0, UINT8_MAX);
799  if (negative) gradient = -gradient;
800  // Compute gradient angle quantized to 256 directions, rotated by 64 (pi/2)
801  // to convert from gradient direction to edge direction.
802  offsets[s].direction =
803  Modulo(FCOORD::binary_angle_plus_pi(gradient.angle()) + 64, 256);
804  prev_gradient = next_gradient;
805  }
806 }
807 
838  delete [] offsets;
839  offsets = new EdgeOffset[stepcount];
840  // Count of the number of steps in each direction in the sliding window.
841  int dir_counts[4];
842  // Sum of the positions (y for a horizontal step, x for vertical) in each
843  // direction in the sliding window.
844  int pos_totals[4];
845  memset(dir_counts, 0, sizeof(dir_counts));
846  memset(pos_totals, 0, sizeof(pos_totals));
847  ICOORD pos = start;
848  ICOORD tail_pos = pos;
849  // tail_pos is the trailing position, with the next point to be lost from
850  // the window.
851  tail_pos -= step(stepcount - 1);
852  tail_pos -= step(stepcount - 2);
853  // head_pos is the leading position, with the next point to be added to the
854  // window.
855  ICOORD head_pos = tail_pos;
856  // Set up the initial window with 4 points in [-2, 2)
857  for (int s = -2; s < 2; ++s) {
858  increment_step(s, 1, &head_pos, dir_counts, pos_totals);
859  }
860  for (int s = 0; s < stepcount; pos += step(s++)) {
861  // At step s, s in in the middle of [s-2, s+2].
862  increment_step(s + 2, 1, &head_pos, dir_counts, pos_totals);
863  int dir_index = chain_code(s);
864  ICOORD step_vec = step(s);
865  int best_diff = 0;
866  int offset = 0;
867  // Use only steps that have a count of >=2 OR the strong U-turn with a
868  // single d and 2 at d-1 and 2 at d+1 (mod 4).
869  if (dir_counts[dir_index] >= 2 || (dir_counts[dir_index] == 1 &&
870  dir_counts[Modulo(dir_index - 1, 4)] == 2 &&
871  dir_counts[Modulo(dir_index + 1, 4)] == 2)) {
872  // Valid step direction.
873  best_diff = dir_counts[dir_index];
874  int edge_pos = step_vec.x() == 0 ? pos.x() : pos.y();
875  // The offset proposes that the actual step should be positioned at
876  // the mean position of the steps in the window of the same direction.
877  // See ASCII art above.
878  offset = pos_totals[dir_index] - best_diff * edge_pos;
879  }
880  offsets[s].offset_numerator =
881  ClipToRange<int>(offset, -INT8_MAX, INT8_MAX);
882  offsets[s].pixel_diff = ClipToRange<int>(best_diff, 0, UINT8_MAX);
883  // The direction is just the vector from start to end of the window.
884  FCOORD direction(head_pos.x() - tail_pos.x(), head_pos.y() - tail_pos.y());
885  offsets[s].direction = direction.to_direction();
886  increment_step(s - 2, -1, &tail_pos, dir_counts, pos_totals);
887  }
888 }
889 
894 void C_OUTLINE::render(int left, int top, Pix* pix) const {
895  ICOORD pos = start;
896  for (int stepindex = 0; stepindex < stepcount; ++stepindex) {
897  ICOORD next_step = step(stepindex);
898  if (next_step.y() < 0) {
899  pixRasterop(pix, 0, top - pos.y(), pos.x() - left, 1,
900  PIX_NOT(PIX_DST), nullptr, 0, 0);
901  } else if (next_step.y() > 0) {
902  pixRasterop(pix, 0, top - pos.y() - 1, pos.x() - left, 1,
903  PIX_NOT(PIX_DST), nullptr, 0, 0);
904  }
905  pos += next_step;
906  }
907 }
908 
916 void C_OUTLINE::render_outline(int left, int top, Pix* pix) const {
917  ICOORD pos = start;
918  for (int stepindex = 0; stepindex < stepcount; ++stepindex) {
919  ICOORD next_step = step(stepindex);
920  if (next_step.y() < 0) {
921  pixSetPixel(pix, pos.x() - left, top - pos.y(), 1);
922  } else if (next_step.y() > 0) {
923  pixSetPixel(pix, pos.x() - left - 1, top - pos.y() - 1, 1);
924  } else if (next_step.x() < 0) {
925  pixSetPixel(pix, pos.x() - left - 1, top - pos.y(), 1);
926  } else if (next_step.x() > 0) {
927  pixSetPixel(pix, pos.x() - left, top - pos.y() - 1, 1);
928  }
929  pos += next_step;
930  }
931 }
932 
941 #ifndef GRAPHICS_DISABLED
942 void C_OUTLINE::plot(ScrollView* window, ScrollView::Color colour) const {
943  int16_t stepindex; // index to cstep
944  ICOORD pos; // current position
945  DIR128 stepdir; // direction of step
946 
947  pos = start; // current position
948  window->Pen(colour);
949  if (stepcount == 0) {
950  window->Rectangle(box.left(), box.top(), box.right(), box.bottom());
951  return;
952  }
953  window->SetCursor(pos.x(), pos.y());
954 
955  stepindex = 0;
956  while (stepindex < stepcount) {
957  pos += step(stepindex); // step to next
958  stepdir = step_dir(stepindex);
959  stepindex++; // count steps
960  // merge straight lines
961  while (stepindex < stepcount &&
962  stepdir.get_dir() == step_dir(stepindex).get_dir()) {
963  pos += step(stepindex);
964  stepindex++;
965  }
966  window->DrawTo(pos.x(), pos.y());
967  }
968 }
969 
975  ScrollView* window) const {
976  window->Pen(colour);
977  if (stepcount == 0) {
978  window->Rectangle(box.left(), box.top(), box.right(), box.bottom());
979  return;
980  }
981  const DENORM* root_denorm = denorm.RootDenorm();
982  ICOORD pos = start; // current position
983  FCOORD f_pos = sub_pixel_pos_at_index(pos, 0);
984  FCOORD pos_normed;
985  denorm.NormTransform(root_denorm, f_pos, &pos_normed);
986  window->SetCursor(IntCastRounded(pos_normed.x()),
987  IntCastRounded(pos_normed.y()));
988  for (int s = 0; s < stepcount; pos += step(s++)) {
989  int edge_weight = edge_strength_at_index(s);
990  if (edge_weight == 0) {
991  // This point has conflicting gradient and step direction, so ignore it.
992  continue;
993  }
994  FCOORD f_pos = sub_pixel_pos_at_index(pos, s);
995  FCOORD pos_normed;
996  denorm.NormTransform(root_denorm, f_pos, &pos_normed);
997  window->DrawTo(IntCastRounded(pos_normed.x()),
998  IntCastRounded(pos_normed.y()));
999  }
1000 }
1001 #endif
1002 
1011  box = source.box;
1012  start = source.start;
1013  free(steps);
1014  stepcount = source.stepcount;
1015  steps = static_cast<uint8_t *>(malloc(step_mem()));
1016  memmove (steps, source.steps, step_mem());
1017  if (!children.empty ())
1018  children.clear ();
1019  children.deep_copy(&source.children, &deep_copy);
1020  delete [] offsets;
1021  if (source.offsets != nullptr) {
1022  offsets = new EdgeOffset[stepcount];
1023  memcpy(offsets, source.offsets, stepcount * sizeof(*offsets));
1024  } else {
1025  offsets = nullptr;
1026  }
1027  return *this;
1028 }
1029 
1036 void C_OUTLINE::increment_step(int s, int increment, ICOORD* pos,
1037  int* dir_counts, int* pos_totals) const {
1038  int step_index = Modulo(s, stepcount);
1039  int dir_index = chain_code(step_index);
1040  dir_counts[dir_index] += increment;
1041  ICOORD step_vec = step(step_index);
1042  if (step_vec.x() == 0)
1043  pos_totals[dir_index] += pos->x() * increment;
1044  else
1045  pos_totals[dir_index] += pos->y() * increment;
1046  *pos += step_vec;
1047 }
1048 
1050  return step_coords[chaindir % 4];
1051 }
TBOX
Definition: cleanapi_test.cc:19
C_OUTLINE::sub_pixel_pos_at_index
FCOORD sub_pixel_pos_at_index(const ICOORD &pos, int index) const
Definition: coutln.h:162
C_OUTLINE::edge_strength_at_index
int edge_strength_at_index(int index) const
Definition: coutln.h:186
ScrollView
Definition: scrollview.h:97
C_OUTLINE::chain_code
int chain_code(int index) const
Definition: coutln.h:194
ICOORD::set_x
void set_x(int16_t xin)
rewrite function
Definition: points.h:60
normalis.h
TBOX::move
void move(const ICOORD vec)
Definition: rect.h:156
CRACKEDGE::next
CRACKEDGE * next
Definition: crakedge.h:50
C_OUTLINE::flag
bool flag(C_OUTLINE_FLAGS mask) const
Definition: coutln.h:97
TPOINT
Definition: blobs.h:49
DENORM::NormTransform
void NormTransform(const DENORM *first_norm, const TPOINT &pt, TPOINT *transformed) const
Definition: normalis.cpp:334
DIR128
Definition: mod128.h:28
ASSERT_HOST
#define ASSERT_HOST(x)
Definition: errcode.h:87
EdgeOffset::direction
uint8_t direction
Definition: coutln.h:64
TBOX::overlap
bool overlap(const TBOX &box) const
Definition: rect.h:350
FCOORD::y
float y() const
Definition: points.h:209
ICOORD
integer coordinate
Definition: points.h:30
ICOORD::rotate
void rotate(const FCOORD &vec)
Definition: points.h:522
MODULUS
#define MODULUS
Definition: mod128.h:24
FCOORD::x
float x() const
Definition: points.h:206
C_OUTLINE::C_OUTLINE
C_OUTLINE()
Definition: coutln.h:73
TBOX::top
int16_t top() const
Definition: rect.h:57
TBOX::contains
bool contains(const FCOORD pt) const
Definition: rect.h:330
TBOX::area
int32_t area() const
Definition: rect.h:121
ScrollView::Pen
void Pen(Color color)
Definition: scrollview.cpp:717
ScrollView::DrawTo
void DrawTo(int x, int y)
Definition: scrollview.cpp:524
IntCastRounded
int IntCastRounded(double x)
Definition: helpers.h:173
TBOX::topleft
ICOORD topleft() const
Definition: rect.h:99
DENORM::RootDenorm
const DENORM * RootDenorm() const
Definition: normalis.h:257
C_OUTLINE::perimeter
int32_t perimeter() const
Definition: coutln.cpp:289
ICOORD::x
int16_t x() const
access function
Definition: points.h:51
FCOORD
Definition: points.h:187
blobs.h
C_OUTLINE::outer_area
int32_t outer_area() const
Definition: coutln.cpp:308
C_OUTLINE::render
void render(int left, int top, Pix *pix) const
Definition: coutln.cpp:894
ICOORD::set_y
void set_y(int16_t yin)
rewrite function
Definition: points.h:64
TBOX::rotate
void rotate(const FCOORD &vec)
Definition: rect.h:196
C_OUTLINE
Definition: coutln.h:71
TBOX::height
int16_t height() const
Definition: rect.h:107
C_OUTLINE::operator=
C_OUTLINE & operator=(const C_OUTLINE &source)
Definition: coutln.cpp:1010
INTERSECTING
#define INTERSECTING
Definition: coutln.h:34
COUT_INVERSE
Definition: coutln.h:41
C_OUTLINE::FakeOutline
static void FakeOutline(const TBOX &box, C_OUTLINE_LIST *outlines)
Definition: coutln.cpp:239
TPOINT::x
int16_t x
Definition: blobs.h:91
C_OUTLINE::IsLegallyNested
bool IsLegallyNested() const
Definition: coutln.cpp:604
C_OUTLINE::step_dir
DIR128 step_dir(int index) const
Definition: coutln.h:138
C_OUTLINE::RemoveSmallRecursive
void RemoveSmallRecursive(int min_size, C_OUTLINE_IT *it)
Definition: coutln.cpp:627
TPOINT::y
int16_t y
Definition: blobs.h:92
TBOX::width
int16_t width() const
Definition: rect.h:114
TBOX::bottom
int16_t bottom() const
Definition: rect.h:64
coutln.h
helpers.h
C_OUTLINE::plot_normed
void plot_normed(const DENORM &denorm, ScrollView::Color colour, ScrollView *window) const
Definition: coutln.cpp:974
CRACKEDGE::pos
ICOORD pos
Definition: crakedge.h:45
C_OUTLINE::set_step
void set_step(int16_t stepindex, int8_t stepdir)
Definition: coutln.h:115
CRACKEDGE::stepdir
int8_t stepdir
Definition: crakedge.h:48
C_OUTLINE::reverse
void reverse()
Definition: coutln.cpp:565
count
int count(LIST var_list)
Definition: oldlist.cpp:79
C_OUTLINE::winding_number
int16_t winding_number(ICOORD testpt) const
Definition: coutln.cpp:500
TBOX::left
int16_t left() const
Definition: rect.h:71
CRACKEDGE
Definition: crakedge.h:25
C_OUTLINE::plot
void plot(ScrollView *window, ScrollView::Color colour) const
Definition: coutln.cpp:942
crakedge.h
DIR128::get_dir
int8_t get_dir() const
Definition: mod128.h:75
TBOX::right
int16_t right() const
Definition: rect.h:78
C_OUTLINE::deep_copy
static C_OUTLINE * deep_copy(const C_OUTLINE *src)
Definition: coutln.h:260
FCOORD::binary_angle_plus_pi
static uint8_t binary_angle_plus_pi(double angle)
Definition: points.cpp:120
Modulo
int Modulo(int a, int b)
Definition: helpers.h:156
TBOX::botright
ICOORD botright() const
Definition: rect.h:95
errcode.h
EdgeOffset
Definition: coutln.h:61
C_OUTLINE::turn_direction
int16_t turn_direction() const
Definition: coutln.cpp:537
ScrollView::SetCursor
void SetCursor(int x, int y)
Definition: scrollview.cpp:518
C_OUTLINE::pathlength
int32_t pathlength() const
Definition: coutln.h:134
C_OUTLINE::chain_step
static ICOORD chain_step(int chaindir)
Definition: coutln.cpp:1049
C_OUTLINE::count_transitions
int32_t count_transitions(int32_t threshold)
Definition: coutln.cpp:340
EdgeOffset::pixel_diff
uint8_t pixel_diff
Definition: coutln.h:63
C_OUTLINE::ComputeBinaryOffsets
void ComputeBinaryOffsets()
Definition: coutln.cpp:837
C_OUTLINE::step
ICOORD step(int index) const
Definition: coutln.h:143
ScrollView::Color
Color
Definition: scrollview.h:100
C_OUTLINE::ComputeEdgeOffsets
void ComputeEdgeOffsets(int threshold, Pix *pix)
Definition: coutln.cpp:721
ScrollView::Rectangle
void Rectangle(int x1, int y1, int x2, int y2)
Definition: scrollview.cpp:599
EdgeOffset::offset_numerator
int8_t offset_numerator
Definition: coutln.h:62
C_OUTLINE::child
C_OUTLINE_LIST * child()
Definition: coutln.h:107
C_OUTLINE::operator<
bool operator<(const C_OUTLINE &other) const
Definition: coutln.cpp:467
C_OUTLINE::area
int32_t area() const
Definition: coutln.cpp:255
C_OUTLINE::render_outline
void render_outline(int left, int top, Pix *pix) const
Definition: coutln.cpp:916
ELISTIZE
#define ELISTIZE(CLASSNAME)
Definition: elst.h:919
C_OUTLINE::start_pos
const ICOORD & start_pos() const
Definition: coutln.h:147
ICOORD::y
int16_t y() const
access_function
Definition: points.h:55
C_OUTLINE::move
void move(const ICOORD vec)
Definition: coutln.cpp:588
TBOX
Definition: rect.h:33
DENORM
Definition: normalis.h:49