/src/tesseract/src/ccstruct/coutln.h
Line | Count | Source (jump to first uncovered line) |
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 | 2.29M | #define INTERSECTING INT16_MAX // no winding number |
41 | | |
42 | | // mask to get step |
43 | 491M | #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 | | |
74 | | ELISTIZEH(C_OUTLINE) |
75 | | class C_OUTLINE : public ELIST<C_OUTLINE>::LINK { |
76 | | public: |
77 | 215k | C_OUTLINE() { |
78 | 215k | stepcount = 0; |
79 | 215k | offsets = nullptr; |
80 | 215k | } |
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 | 920k | ~C_OUTLINE() { // destructor |
95 | 920k | delete[] offsets; |
96 | 920k | } |
97 | | |
98 | | bool flag( // test flag |
99 | 1.22M | C_OUTLINE_FLAGS mask) const { // flag to test |
100 | 1.22M | return flags[mask]; |
101 | 1.22M | } |
102 | | void set_flag( // set flag value |
103 | | C_OUTLINE_FLAGS mask, // flag to test |
104 | 655k | bool value) { // value to set |
105 | 655k | flags.set(mask, value); |
106 | 655k | } |
107 | | |
108 | 4.01M | C_OUTLINE_LIST *child() { // get child list |
109 | 4.01M | return &children; |
110 | 4.01M | } |
111 | | |
112 | | // access function |
113 | 37.9M | const TBOX &bounding_box() const { |
114 | 37.9M | return box; |
115 | 37.9M | } |
116 | | void set_step( // set a step |
117 | | int16_t stepindex, // index of step |
118 | 20.5M | int8_t stepdir) { // chain code |
119 | 20.5M | int shift = stepindex % 4 * 2; |
120 | 20.5M | uint8_t mask = 3 << shift; |
121 | 20.5M | steps[stepindex / 4] = ((stepdir << shift) & mask) | (steps[stepindex / 4] & ~mask); |
122 | | // squeeze 4 into byte |
123 | 20.5M | } |
124 | | void set_step( // set a step |
125 | | int16_t stepindex, // index of step |
126 | 6.14M | DIR128 stepdir) { // direction |
127 | | // clean it |
128 | 6.14M | int8_t chaindir = stepdir.get_dir() >> (DIRBITS - 2); |
129 | | // difference |
130 | 6.14M | set_step(stepindex, chaindir); |
131 | | // squeeze 4 into byte |
132 | 6.14M | } |
133 | | |
134 | 56.4M | int32_t pathlength() const { // get path length |
135 | 56.4M | return stepcount; |
136 | 56.4M | } |
137 | | // Return step at a given index as a DIR128. |
138 | 65.2M | DIR128 step_dir(int index) const { |
139 | 65.2M | return DIR128( |
140 | 65.2M | static_cast<int16_t>(((steps[index / 4] >> (index % 4 * 2)) & STEP_MASK) << (DIRBITS - 2))); |
141 | 65.2M | } |
142 | | // Return the step vector for the given outline position. |
143 | 384M | ICOORD step(int index) const { // index of step |
144 | 384M | return step_coords[chain_code(index)]; |
145 | 384M | } |
146 | | // get start position |
147 | 7.67M | const ICOORD &start_pos() const { |
148 | 7.67M | return start; |
149 | 7.67M | } |
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 | 0 | ICOORD position_at_index(int index) const { |
153 | 0 | ICOORD pos = start; |
154 | 0 | for (int i = 0; i < index; ++i) { |
155 | 0 | pos += step(i); |
156 | 0 | } |
157 | 0 | return pos; |
158 | 0 | } |
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 | 0 | FCOORD sub_pixel_pos_at_index(const ICOORD &pos, int index) const { |
164 | 0 | const ICOORD &step_to_next(step(index)); |
165 | 0 | FCOORD f_pos(pos.x() + step_to_next.x() / 2.0f, pos.y() + step_to_next.y() / 2.0f); |
166 | 0 | if (offsets != nullptr && offsets[index].pixel_diff > 0) { |
167 | 0 | float offset = offsets[index].offset_numerator; |
168 | 0 | offset /= offsets[index].pixel_diff; |
169 | 0 | if (step_to_next.x() != 0) { |
170 | 0 | f_pos.set_y(f_pos.y() + offset); |
171 | 0 | } else { |
172 | 0 | f_pos.set_x(f_pos.x() + offset); |
173 | 0 | } |
174 | 0 | } |
175 | 0 | return f_pos; |
176 | 0 | } |
177 | | // Returns the step direction for the given index or -1 if there is none. |
178 | 0 | int direction_at_index(int index) const { |
179 | 0 | if (offsets != nullptr && offsets[index].pixel_diff > 0) { |
180 | 0 | return offsets[index].direction; |
181 | 0 | } |
182 | 0 | return -1; |
183 | 0 | } |
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 | 0 | int edge_strength_at_index(int index) const { |
189 | 0 | if (offsets != nullptr) { |
190 | 0 | return offsets[index].pixel_diff; |
191 | 0 | } |
192 | 0 | return 1; |
193 | 0 | } |
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 | 425M | int chain_code(int index) const { // index of step |
198 | 425M | return (steps[index / 4] >> (index % 4 * 2)) & STEP_MASK; |
199 | 425M | } |
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 | 0 | C_OUTLINE &other) const { |
211 | 0 | return other < *this; // use the < to do it |
212 | 0 | } |
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 | 215k | static C_OUTLINE *deep_copy(const C_OUTLINE *src) { |
262 | 215k | auto *outline = new C_OUTLINE; |
263 | 215k | *outline = *src; |
264 | 215k | return outline; |
265 | 215k | } |
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 | 1.08M | int step_mem() const { |
282 | 1.08M | return (stepcount + 3) / 4; |
283 | 1.08M | } |
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 |