tesseract  v4.0.0-17-g361f3264
Open Source OCR Engine
coutln.h
1 /**********************************************************************
2  * File: coutln.h
3  * Description: Code for the C_OUTLINE class.
4  * Author: Ray Smith
5  * Created: Mon Oct 07 16:01:57 BST 1991
6  *
7  * (C) Copyright 1991, Hewlett-Packard Ltd.
8  ** Licensed under the Apache License, Version 2.0 (the "License");
9  ** you may not use this file except in compliance with the License.
10  ** You may obtain a copy of the License at
11  ** http://www.apache.org/licenses/LICENSE-2.0
12  ** Unless required by applicable law or agreed to in writing, software
13  ** distributed under the License is distributed on an "AS IS" BASIS,
14  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15  ** See the License for the specific language governing permissions and
16  ** limitations under the License.
17  *
18  **********************************************************************/
19 
20 #ifndef COUTLN_H
21 #define COUTLN_H
22 
23 #include <cstdint> // for int16_t, int32_t
24 #include "bits16.h" // for BITS16
25 #include "elst.h" // for ELIST_ITERATOR, ELISTIZEH, ELIST_LINK
26 #include "mod128.h" // for DIR128, DIRBITS
27 #include "platform.h" // for DLLSYM
28 #include "points.h" // for ICOORD, FCOORD
29 #include "rect.h" // for TBOX
30 #include "scrollview.h" // for ScrollView, ScrollView::Color
31 
32 class CRACKEDGE;
33 class DENORM;
34 
35 #define INTERSECTING INT16_MAX//no winding number
36 
37  //mask to get step
38 #define STEP_MASK 3
39 
40 enum C_OUTLINE_FLAGS
41 {
42  COUT_INVERSE //White on black blob
43 };
44 
45 // Simple struct to hold the 3 values needed to compute a more precise edge
46 // position and direction. The offset_numerator is the difference between the
47 // grey threshold and the mean pixel value. pixel_diff is the difference between
48 // the pixels in the edge. Consider the following row of pixels: p1 p2 p3 p4 p5
49 // Say the image was thresholded at threshold t, making p1, p2, p3 black
50 // and p4, p5 white (p1, p2, p3 < t, and p4, p5 >= t), but suppose that
51 // max(p[i+1] - p[i]) is p3 - p2. Then the extrapolated position of the edge,
52 // based on the maximum gradient, is at the crack between p2 and p3 plus the
53 // offset (t - (p2+p3)/2)/(p3 - p2). We store the pixel difference p3-p2
54 // denominator in pixel_diff and the offset numerator, relative to the original
55 // binary edge (t - (p2+p3)/2) - (p3 -p2) in offset_numerator.
56 // The sign of offset_numerator and pixel_diff are manipulated to ensure
57 // that the pixel_diff, which will be used as a weight, is always positive.
58 // The direction stores the quantized feature direction for the given step
59 // computed from the edge gradient. (Using binary_angle_plus_pi.)
60 // If the pixel_diff is zero, it means that the direction of the gradient
61 // is in conflict with the step direction, so this step is to be ignored.
62 struct EdgeOffset {
64  uint8_t pixel_diff;
65  uint8_t direction;
66 };
67 
68 class DLLSYM C_OUTLINE; //forward declaration
69 struct Pix;
70 
71 ELISTIZEH (C_OUTLINE)
72 class DLLSYM C_OUTLINE:public ELIST_LINK {
73  public:
75  stepcount = 0;
76  steps = nullptr;
77  offsets = nullptr;
78  }
79  C_OUTLINE( //constructor
80  CRACKEDGE *startpt, //from edge detector
81  ICOORD bot_left, //bounding box //length of loop
82  ICOORD top_right,
83  int16_t length);
84  C_OUTLINE(ICOORD startpt, //start of loop
85  DIR128 *new_steps, //steps in loop
86  int16_t length); //length of loop
87  //outline to copy
88  C_OUTLINE(C_OUTLINE *srcline, FCOORD rotation); //and rotate
89 
90  // Build a fake outline, given just a bounding box and append to the list.
91  static void FakeOutline(const TBOX& box, C_OUTLINE_LIST* outlines);
92 
93  ~C_OUTLINE () { //destructor
94  free(steps);
95  delete [] offsets;
96  }
97 
98  bool flag( //test flag
99  C_OUTLINE_FLAGS mask) const { //flag to test
100  return flags.bit(mask);
101  }
102  void set_flag( //set flag value
103  C_OUTLINE_FLAGS mask, //flag to test
104  bool value) { //value to set
105  flags.set_bit(mask, value);
106  }
107 
108  C_OUTLINE_LIST *child() { //get child list
109  return &children;
110  }
111 
112  //access function
113  const TBOX &bounding_box() const {
114  return box;
115  }
116  void set_step( //set a step
117  int16_t stepindex, //index of step
118  int8_t stepdir) { //chain code
119  int shift = stepindex%4 * 2;
120  uint8_t mask = 3 << shift;
121  steps[stepindex/4] = ((stepdir << shift) & mask) |
122  (steps[stepindex/4] & ~mask);
123  //squeeze 4 into byte
124  }
125  void set_step( //set a step
126  int16_t stepindex, //index of step
127  DIR128 stepdir) { //direction
128  //clean it
129  int8_t chaindir = stepdir.get_dir() >> (DIRBITS - 2);
130  //difference
131  set_step(stepindex, chaindir);
132  //squeeze 4 into byte
133  }
134 
135  int32_t pathlength() const { //get path length
136  return stepcount;
137  }
138  // Return step at a given index as a DIR128.
139  DIR128 step_dir(int index) const {
140  return DIR128((int16_t)(((steps[index/4] >> (index%4 * 2)) & STEP_MASK) <<
141  (DIRBITS - 2)));
142  }
143  // Return the step vector for the given outline position.
144  ICOORD step(int index) const { // index of step
145  return step_coords[chain_code(index)];
146  }
147  // get start position
148  const ICOORD &start_pos() const {
149  return start;
150  }
151  // Returns the position at the given index on the outline.
152  // NOT to be used lightly, as it has to iterate the outline to find out.
153  ICOORD position_at_index(int index) const {
154  ICOORD pos = start;
155  for (int i = 0; i < index; ++i)
156  pos += step(i);
157  return pos;
158  }
159  // Returns the sub-pixel accurate position given the integer position pos
160  // at the given index on the outline. pos may be a return value of
161  // position_at_index, or computed by repeatedly adding step to the
162  // start_pos() in the usual way.
163  FCOORD sub_pixel_pos_at_index(const ICOORD& pos, int index) const {
164  const ICOORD& step_to_next(step(index));
165  FCOORD f_pos(pos.x() + step_to_next.x() / 2.0f,
166  pos.y() + step_to_next.y() / 2.0f);
167  if (offsets != nullptr && offsets[index].pixel_diff > 0) {
168  float offset = offsets[index].offset_numerator;
169  offset /= offsets[index].pixel_diff;
170  if (step_to_next.x() != 0)
171  f_pos.set_y(f_pos.y() + offset);
172  else
173  f_pos.set_x(f_pos.x() + offset);
174  }
175  return f_pos;
176  }
177  // Returns the step direction for the given index or -1 if there is none.
178  int direction_at_index(int index) const {
179  if (offsets != nullptr && offsets[index].pixel_diff > 0)
180  return offsets[index].direction;
181  return -1;
182  }
183  // Returns the edge strength for the given index.
184  // If there are no recorded edge strengths, returns 1 (assuming the image
185  // is binary). Returns 0 if the gradient direction conflicts with the
186  // step direction, indicating that this position could be skipped.
187  int edge_strength_at_index(int index) const {
188  if (offsets != nullptr)
189  return offsets[index].pixel_diff;
190  return 1;
191  }
192  // Return the step as a chain code (0-3) related to the standard feature
193  // direction of binary_angle_plus_pi by:
194  // chain_code * 64 = feature direction.
195  int chain_code(int index) const { // index of step
196  return (steps[index / 4] >> (index % 4 * 2)) & STEP_MASK;
197  }
198 
199  int32_t area() const; // Returns area of self and 1st level children.
200  int32_t perimeter() const; // Total perimeter of self and 1st level children.
201  int32_t outer_area() const; // Returns area of self only.
202  int32_t count_transitions( //count maxima
203  int32_t threshold); //size threshold
204 
205  bool operator< ( //containment test
206  const C_OUTLINE & other) const;
207  bool operator> ( //containment test
208  C_OUTLINE & other) const
209  {
210  return other < *this; //use the < to do it
211  }
212  int16_t winding_number( //get winding number
213  ICOORD testpt) const; //around this point
214  //get direction
215  int16_t turn_direction() const;
216  void reverse(); //reverse direction
217 
218  void move( // reposition outline
219  const ICOORD vec); // by vector
220 
221  // Returns true if *this and its children are legally nested.
222  // The outer area of a child should have the opposite sign to the
223  // parent. If not, it means we have discarded an outline in between
224  // (probably due to excessive length).
225  bool IsLegallyNested() const;
226 
227  // If this outline is smaller than the given min_size, delete this and
228  // remove from its list, via *it, after checking that *it points to this.
229  // Otherwise, if any children of this are too small, delete them.
230  // On entry, *it must be an iterator pointing to this. If this gets deleted
231  // then this is extracted from *it, so an iteration can continue.
232  void RemoveSmallRecursive(int min_size, C_OUTLINE_IT* it);
233 
234  // Adds sub-pixel resolution EdgeOffsets for the outline if the supplied
235  // pix is 8-bit. Does nothing otherwise.
236  void ComputeEdgeOffsets(int threshold, Pix* pix);
237  // Adds sub-pixel resolution EdgeOffsets for the outline using only
238  // a binary image source.
239  void ComputeBinaryOffsets();
240 
241  // Renders the outline to the given pix, with left and top being
242  // the coords of the upper-left corner of the pix.
243  void render(int left, int top, Pix* pix) const;
244 
245  // Renders just the outline to the given pix (no fill), with left and top
246  // being the coords of the upper-left corner of the pix.
247  void render_outline(int left, int top, Pix* pix) const;
248 
249  #ifndef GRAPHICS_DISABLED
250  void plot( //draw one
251  ScrollView* window, //window to draw in
252  ScrollView::Color colour) const; //colour to draw it
253  // Draws the outline in the given colour, normalized using the given denorm,
254  // making use of sub-pixel accurate information if available.
255  void plot_normed(const DENORM& denorm, ScrollView::Color colour,
256  ScrollView* window) const;
257  #endif // GRAPHICS_DISABLED
258 
259  C_OUTLINE& operator=(const C_OUTLINE& source);
260 
261  static C_OUTLINE* deep_copy(const C_OUTLINE* src) {
262  C_OUTLINE* outline = new C_OUTLINE;
263  *outline = *src;
264  return outline;
265  }
266 
267  static ICOORD chain_step(int chaindir);
268 
269  // The maximum length of any outline. The stepcount is stored as 16 bits,
270  // but it is probably not a good idea to increase this constant by much
271  // and switch to 32 bits, as it plays an important role in keeping huge
272  // outlines invisible, which prevents bad speed behavior.
273  static const int kMaxOutlineLength = 16000;
274 
275  private:
276  // Helper for ComputeBinaryOffsets. Increments pos, dir_counts, pos_totals
277  // by the step, increment, and vertical step ? x : y position * increment
278  // at step s Mod stepcount respectively. Used to add or subtract the
279  // direction and position to/from accumulators of a small neighbourhood.
280  void increment_step(int s, int increment, ICOORD* pos, int* dir_counts,
281  int* pos_totals) const;
282  int step_mem() const { return (stepcount+3) / 4; }
283 
284  TBOX box; // bounding box
285  ICOORD start; // start coord
286  int16_t stepcount; // no of steps
287  BITS16 flags; // flags about outline
288  uint8_t *steps; // step array
289  EdgeOffset* offsets; // Higher precision edge.
290  C_OUTLINE_LIST children; // child elements
291  static ICOORD step_coords[4];
292 };
293 #endif
uint8_t pixel_diff
Definition: coutln.h:64
C_OUTLINE_LIST * child()
Definition: coutln.h:108
void set_step(int16_t stepindex, int8_t stepdir)
Definition: coutln.h:116
int direction_at_index(int index) const
Definition: coutln.h:178
int16_t x() const
access function
Definition: points.h:53
Definition: bits16.h:25
int step_mem() const
Definition: coutln.h:282
static C_OUTLINE * deep_copy(const C_OUTLINE *src)
Definition: coutln.h:261
const TBOX & bounding_box() const
Definition: coutln.h:113
Color
Definition: scrollview.h:105
Definition: rect.h:34
int chain_code(int index) const
Definition: coutln.h:195
C_OUTLINE_LIST children
Definition: coutln.h:290
int edge_strength_at_index(int index) const
Definition: coutln.h:187
EdgeOffset * offsets
Definition: coutln.h:289
TBOX box
Definition: coutln.h:284
FCOORD sub_pixel_pos_at_index(const ICOORD &pos, int index) const
Definition: coutln.h:163
int16_t stepcount
Definition: coutln.h:286
Definition: scrollview.h:102
BITS16 flags
Definition: coutln.h:287
Definition: crakedge.h:26
void set_y(float yin)
rewrite function
Definition: points.h:219
C_OUTLINE()
Definition: coutln.h:74
int16_t y() const
access_function
Definition: points.h:57
ICOORD step(int index) const
Definition: coutln.h:144
Definition: coutln.h:62
uint8_t * steps
Definition: coutln.h:288
~C_OUTLINE()
Definition: coutln.h:93
integer coordinate
Definition: points.h:32
void set_step(int16_t stepindex, DIR128 stepdir)
Definition: coutln.h:125
uint8_t direction
Definition: coutln.h:65
Definition: normalis.h:50
int8_t offset_numerator
Definition: coutln.h:63
ICOORD start
Definition: coutln.h:285
Definition: mod128.h:29
int32_t pathlength() const
Definition: coutln.h:135
ICOORD position_at_index(int index) const
Definition: coutln.h:153
const ICOORD & start_pos() const
Definition: coutln.h:148
DIR128 step_dir(int index) const
Definition: coutln.h:139
int8_t get_dir() const
Definition: mod128.h:76
bool flag(C_OUTLINE_FLAGS mask) const
Definition: coutln.h:98
Definition: points.h:189
void set_flag(C_OUTLINE_FLAGS mask, bool value)
Definition: coutln.h:102
Definition: coutln.h:72