Coverage Report

Created: 2025-06-13 07:02

/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