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