1 /**********************************************************************
2 * File: coutln.h
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 #ifndef COUTLN_H
20 #define COUTLN_H
21
22 #include "elst.h" // for ELIST_ITERATOR, ELISTIZEH, ELIST_LINK
23 #include "mod128.h" // for DIR128, DIRBITS
24 #include "points.h" // for ICOORD, FCOORD
25 #include "rect.h" // for TBOX
26 #include "scrollview.h" // for ScrollView, ScrollView::Color
27
28 #include <tesseract/export.h> // for DLLSYM
29
30 #include <cstdint> // for int16_t, int32_t
31 #include <bitset> // for std::bitset<16>
32
33 struct Pix;
34
35 namespace tesseract {
36
37 class CRACKEDGE;
38 class DENORM;
39
40 #define INTERSECTING INT16_MAX // no winding number
41
42 // mask to get step
43 #define STEP_MASK 3
44
45 enum C_OUTLINE_FLAGS {
46 COUT_INVERSE // White on black blob
47 };
48
49 // Simple struct to hold the 3 values needed to compute a more precise edge
50 // position and direction. The offset_numerator is the difference between the
51 // grey threshold and the mean pixel value. pixel_diff is the difference between
52 // the pixels in the edge. Consider the following row of pixels: p1 p2 p3 p4 p5
53 // Say the image was thresholded at threshold t, making p1, p2, p3 black
54 // and p4, p5 white (p1, p2, p3 < t, and p4, p5 >= t), but suppose that
55 // max(p[i+1] - p[i]) is p3 - p2. Then the extrapolated position of the edge,
56 // based on the maximum gradient, is at the crack between p2 and p3 plus the
57 // offset (t - (p2+p3)/2)/(p3 - p2). We store the pixel difference p3-p2
58 // denominator in pixel_diff and the offset numerator, relative to the original
59 // binary edge (t - (p2+p3)/2) - (p3 -p2) in offset_numerator.
60 // The sign of offset_numerator and pixel_diff are manipulated to ensure
61 // that the pixel_diff, which will be used as a weight, is always positive.
62 // The direction stores the quantized feature direction for the given step
63 // computed from the edge gradient. (Using binary_angle_plus_pi.)
64 // If the pixel_diff is zero, it means that the direction of the gradient
65 // is in conflict with the step direction, so this step is to be ignored.
66 struct EdgeOffset {
67 int8_t offset_numerator;
68 uint8_t pixel_diff;
69 uint8_t direction;
70 };
71
72 class C_OUTLINE; // forward declaration
73
ELISTIZEH(C_OUTLINE)74 ELISTIZEH(C_OUTLINE)
75 class C_OUTLINE : public ELIST_LINK {
76 public:
77 C_OUTLINE() {
78 stepcount = 0;
79 offsets = nullptr;
80 }
81 C_OUTLINE( // constructor
82 CRACKEDGE *startpt, // from edge detector
83 ICOORD bot_left, // bounding box //length of loop
84 ICOORD top_right, int16_t length);
85 C_OUTLINE(ICOORD startpt, // start of loop
86 DIR128 *new_steps, // steps in loop
87 int16_t length); // length of loop
88 // outline to copy
89 C_OUTLINE(C_OUTLINE *srcline, FCOORD rotation); // and rotate
90
91 // Build a fake outline, given just a bounding box and append to the list.
92 static void FakeOutline(const TBOX &box, C_OUTLINE_LIST *outlines);
93
94 ~C_OUTLINE() { // destructor
95 delete[] offsets;
96 }
97
98 bool flag( // test flag
99 C_OUTLINE_FLAGS mask) const { // flag to test
100 return flags[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(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) | (steps[stepindex / 4] & ~mask);
122 // squeeze 4 into byte
123 }
124 void set_step( // set a step
125 int16_t stepindex, // index of step
126 DIR128 stepdir) { // direction
127 // clean it
128 int8_t chaindir = stepdir.get_dir() >> (DIRBITS - 2);
129 // difference
130 set_step(stepindex, chaindir);
131 // squeeze 4 into byte
132 }
133
134 int32_t pathlength() const { // get path length
135 return stepcount;
136 }
137 // Return step at a given index as a DIR128.
138 DIR128 step_dir(int index) const {
139 return DIR128(
140 static_cast<int16_t>(((steps[index / 4] >> (index % 4 * 2)) & STEP_MASK) << (DIRBITS - 2)));
141 }
142 // Return the step vector for the given outline position.
143 ICOORD step(int index) const { // index of step
144 return step_coords[chain_code(index)];
145 }
146 // get start position
147 const ICOORD &start_pos() const {
148 return start;
149 }
150 // Returns the position at the given index on the outline.
151 // NOT to be used lightly, as it has to iterate the outline to find out.
152 ICOORD position_at_index(int index) const {
153 ICOORD pos = start;
154 for (int i = 0; i < index; ++i) {
155 pos += step(i);
156 }
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, pos.y() + step_to_next.y() / 2.0f);
166 if (offsets != nullptr && offsets[index].pixel_diff > 0) {
167 float offset = offsets[index].offset_numerator;
168 offset /= offsets[index].pixel_diff;
169 if (step_to_next.x() != 0) {
170 f_pos.set_y(f_pos.y() + offset);
171 } else {
172 f_pos.set_x(f_pos.x() + offset);
173 }
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 }
182 return -1;
183 }
184 // Returns the edge strength for the given index.
185 // If there are no recorded edge strengths, returns 1 (assuming the image
186 // is binary). Returns 0 if the gradient direction conflicts with the
187 // step direction, indicating that this position could be skipped.
188 int edge_strength_at_index(int index) const {
189 if (offsets != nullptr) {
190 return offsets[index].pixel_diff;
191 }
192 return 1;
193 }
194 // Return the step as a chain code (0-3) related to the standard feature
195 // direction of binary_angle_plus_pi by:
196 // chain_code * 64 = feature direction.
197 int chain_code(int index) const { // index of step
198 return (steps[index / 4] >> (index % 4 * 2)) & STEP_MASK;
199 }
200
201 int32_t area() const; // Returns area of self and 1st level children.
202 int32_t perimeter() const; // Total perimeter of self and 1st level children.
203 int32_t outer_area() const; // Returns area of self only.
204 int32_t count_transitions( // count maxima
205 int32_t threshold); // size threshold
206
207 bool operator<( // containment test
208 const C_OUTLINE &other) const;
209 bool operator>( // containment test
210 C_OUTLINE &other) const {
211 return other < *this; // use the < to do it
212 }
213 int16_t winding_number( // get winding number
214 ICOORD testpt) const; // around this point
215 // get direction
216 int16_t turn_direction() const;
217 void reverse(); // reverse direction
218
219 void move( // reposition outline
220 const ICOORD vec); // by vector
221
222 // Returns true if *this and its children are legally nested.
223 // The outer area of a child should have the opposite sign to the
224 // parent. If not, it means we have discarded an outline in between
225 // (probably due to excessive length).
226 bool IsLegallyNested() const;
227
228 // If this outline is smaller than the given min_size, delete this and
229 // remove from its list, via *it, after checking that *it points to this.
230 // Otherwise, if any children of this are too small, delete them.
231 // On entry, *it must be an iterator pointing to this. If this gets deleted
232 // then this is extracted from *it, so an iteration can continue.
233 void RemoveSmallRecursive(int min_size, C_OUTLINE_IT *it);
234
235 // Adds sub-pixel resolution EdgeOffsets for the outline if the supplied
236 // pix is 8-bit. Does nothing otherwise.
237 void ComputeEdgeOffsets(int threshold, Image pix);
238 // Adds sub-pixel resolution EdgeOffsets for the outline using only
239 // a binary image source.
240 void ComputeBinaryOffsets();
241
242 // Renders the outline to the given pix, with left and top being
243 // the coords of the upper-left corner of the pix.
244 void render(int left, int top, Image pix) const;
245
246 // Renders just the outline to the given pix (no fill), with left and top
247 // being the coords of the upper-left corner of the pix.
248 void render_outline(int left, int top, Image pix) const;
249
250 #ifndef GRAPHICS_DISABLED
251 void plot( // draw one
252 ScrollView *window, // window to draw in
253 ScrollView::Color colour) const; // colour to draw it
254 // Draws the outline in the given colour, normalized using the given denorm,
255 // making use of sub-pixel accurate information if available.
256 void plot_normed(const DENORM &denorm, ScrollView::Color colour, 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 auto *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, int *pos_totals) const;
281 int step_mem() const {
282 return (stepcount + 3) / 4;
283 }
284
285 TBOX box; // bounding box
286 ICOORD start; // start coord
287 int16_t stepcount; // no of steps
288 std::bitset<16> flags; // flags about outline
289 std::vector<uint8_t> steps; // step array
290 EdgeOffset *offsets; // Higher precision edge.
291 C_OUTLINE_LIST children; // child elements
292 static ICOORD step_coords[4];
293 };
294
295 } // namespace tesseract
296
297 #endif
298