Coverage Report

Created: 2025-06-13 07:15

/src/tesseract/src/ccstruct/blobs.h
Line
Count
Source (jump to first uncovered line)
1
/******************************************************************************
2
 *
3
 * File:        blobs.h
4
 * Description: Blob definition
5
 * Author:      Mark Seaman, OCR Technology
6
 *
7
 * (c) Copyright 1989, Hewlett-Packard Company.
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 BLOBS_H
21
#define BLOBS_H
22
23
#include "clst.h"       // for CLIST_ITERATOR, CLISTIZEH
24
#include "normalis.h"   // for DENORM
25
#include "points.h"     // for FCOORD, ICOORD
26
#include "rect.h"       // for TBOX
27
#include "scrollview.h" // for ScrollView, ScrollView::Color
28
29
#include <tesseract/publictypes.h> // for OcrEngineMode
30
31
#include "tesstypes.h" // for TDimension
32
33
struct Pix;
34
35
namespace tesseract {
36
37
class BLOCK;
38
class C_BLOB;
39
class C_OUTLINE;
40
class LLSQ;
41
class ROW;
42
class WERD;
43
44
/*----------------------------------------------------------------------
45
              T y p e s
46
----------------------------------------------------------------------*/
47
48
struct TPOINT {
49
1.61G
  TPOINT() = default;
50
3.09M
  TPOINT(TDimension vx, TDimension vy) : x(vx), y(vy) {}
51
0
  TPOINT(const ICOORD &ic) : x(ic.x()), y(ic.y()) {}
52
53
128M
  void operator+=(const TPOINT &other) {
54
128M
    x += other.x;
55
128M
    y += other.y;
56
128M
  }
57
128M
  void operator/=(int divisor) {
58
128M
    x /= divisor;
59
128M
    y /= divisor;
60
128M
  }
61
821M
  bool operator==(const TPOINT &other) const {
62
821M
    return x == other.x && y == other.y;
63
821M
  }
64
  // Returns true when the two line segments cross each other.
65
  // (Moved from outlines.cpp).
66
  static bool IsCrossed(const TPOINT &a0, const TPOINT &a1, const TPOINT &b0, const TPOINT &b1);
67
68
  // Assign the difference from point p1 to point p2.
69
26.6M
  void diff(const TPOINT &p1, const TPOINT &p2) {
70
26.6M
    x = p1.x - p2.x;
71
26.6M
    y = p1.y - p2.y;
72
26.6M
  }
73
74
  // Return cross product.
75
103M
  int cross(const TPOINT &other) const {
76
103M
    return x * other.y - y * other.x;
77
103M
  }
78
79
  // Return scalar or dot product.
80
51.9M
  int dot(const TPOINT &other) const {
81
51.9M
    return x * other.x + y * other.y;
82
51.9M
  }
83
84
  // Calculate square of vector length.
85
143M
  int length2() const {
86
143M
    return x * x + y * y;
87
143M
  }
88
89
  TDimension x = 0; // absolute x coord.
90
  TDimension y = 0; // absolute y coord.
91
};
92
93
using VECTOR = TPOINT; // structure for coordinates.
94
95
struct EDGEPT {
96
690M
  EDGEPT() = default;
97
7.74M
  EDGEPT(const EDGEPT &src) : next(nullptr), prev(nullptr) {
98
7.74M
    CopyFrom(src);
99
7.74M
  }
100
0
  EDGEPT &operator=(const EDGEPT &src) {
101
0
    CopyFrom(src);
102
0
    return *this;
103
0
  }
104
  // Copies the data elements, but leaves the pointers untouched.
105
7.74M
  void CopyFrom(const EDGEPT &src) {
106
7.74M
    pos = src.pos;
107
7.74M
    vec = src.vec;
108
7.74M
    is_hidden = src.is_hidden;
109
7.74M
    runlength = src.runlength;
110
7.74M
    dir = src.dir;
111
7.74M
    fixed = src.fixed;
112
7.74M
    src_outline = src.src_outline;
113
7.74M
    start_step = src.start_step;
114
7.74M
    step_count = src.step_count;
115
7.74M
  }
116
  // Returns the squared distance between the points, with the x-component
117
  // weighted by x_factor.
118
25.8M
  int WeightedDistance(const EDGEPT &other, int x_factor) const {
119
25.8M
    int x_dist = pos.x - other.pos.x;
120
25.8M
    int y_dist = pos.y - other.pos.y;
121
25.8M
    return x_dist * x_dist * x_factor + y_dist * y_dist;
122
25.8M
  }
123
  // Returns true if the positions are equal.
124
818M
  bool EqualPos(const EDGEPT &other) const {
125
818M
    return pos == other.pos;
126
818M
  }
127
  // Returns the bounding box of the outline segment from *this to *end.
128
  // Ignores hidden edge flags.
129
122M
  TBOX SegmentBox(const EDGEPT *end) const {
130
122M
    TBOX box(pos.x, pos.y, pos.x, pos.y);
131
122M
    const EDGEPT *pt = this;
132
2.61G
    do {
133
2.61G
      pt = pt->next;
134
2.61G
      if (pt->pos.x < box.left()) {
135
297M
        box.set_left(pt->pos.x);
136
297M
      }
137
2.61G
      if (pt->pos.x > box.right()) {
138
300M
        box.set_right(pt->pos.x);
139
300M
      }
140
2.61G
      if (pt->pos.y < box.bottom()) {
141
346M
        box.set_bottom(pt->pos.y);
142
346M
      }
143
2.61G
      if (pt->pos.y > box.top()) {
144
346M
        box.set_top(pt->pos.y);
145
346M
      }
146
2.61G
    } while (pt != end && pt != this);
147
122M
    return box;
148
122M
  }
149
  // Returns the area of the outline segment from *this to *end.
150
  // Ignores hidden edge flags.
151
276k
  int SegmentArea(const EDGEPT *end) const {
152
276k
    int area = 0;
153
276k
    const EDGEPT *pt = this->next;
154
878k
    do {
155
878k
      TPOINT origin_vec(pt->pos.x - pos.x, pt->pos.y - pos.y);
156
878k
      area += origin_vec.cross(pt->vec);
157
878k
      pt = pt->next;
158
878k
    } while (pt != end && pt != this);
159
276k
    return area;
160
276k
  }
161
  // Returns true if the number of points in the outline segment from *this to
162
  // *end is less that min_points and false if we get back to *this first.
163
  // Ignores hidden edge flags.
164
615k
  bool ShortNonCircularSegment(int min_points, const EDGEPT *end) const {
165
615k
    int count = 0;
166
615k
    const EDGEPT *pt = this;
167
3.72M
    do {
168
3.72M
      if (pt == end) {
169
276k
        return true;
170
276k
      }
171
3.45M
      pt = pt->next;
172
3.45M
      ++count;
173
3.45M
    } while (pt != this && count <= min_points);
174
339k
    return false;
175
615k
  }
176
177
  // Accessors to hide or reveal a cut edge from feature extractors.
178
361k
  void Hide() {
179
361k
    is_hidden = true;
180
361k
  }
181
384k
  void Reveal() {
182
384k
    is_hidden = false;
183
384k
  }
184
186M
  bool IsHidden() const {
185
186M
    return is_hidden;
186
186M
  }
187
82.6k
  void MarkChop() {
188
82.6k
    dir = 1;
189
82.6k
  }
190
21.2M
  bool IsChopPt() const {
191
21.2M
    return dir != 0;
192
21.2M
  }
193
194
  TPOINT pos; // position
195
  VECTOR vec; // vector to next point
196
  bool is_hidden = false;
197
  uint8_t runlength = 0;
198
  int8_t dir = 0;
199
  bool fixed = false;
200
  EDGEPT *next = nullptr;           // anticlockwise element
201
  EDGEPT *prev = nullptr;           // clockwise element
202
  C_OUTLINE *src_outline = nullptr; // Outline it came from.
203
  // The following fields are not used if src_outline is nullptr.
204
  int start_step = 0; // Location of pos in src_outline.
205
  int step_count = 0; // Number of steps used (may wrap around).
206
};
207
208
// For use in chop and findseam to keep a list of which EDGEPTs were inserted.
209
CLISTIZEH(EDGEPT)
210
211
struct TESSLINE {
212
2.23M
  TESSLINE() : is_hole(false), loop(nullptr), next(nullptr) {}
213
1.78M
  TESSLINE(const TESSLINE &src) : loop(nullptr), next(nullptr) {
214
1.78M
    CopyFrom(src);
215
1.78M
  }
216
4.01M
  ~TESSLINE() {
217
4.01M
    Clear();
218
4.01M
  }
219
0
  TESSLINE &operator=(const TESSLINE &src) {
220
0
    CopyFrom(src);
221
0
    return *this;
222
0
  }
223
  // Consume the circular list of EDGEPTs to make a TESSLINE.
224
  static TESSLINE *BuildFromOutlineList(EDGEPT *outline);
225
  // Copies the data and the outline, but leaves next untouched.
226
  void CopyFrom(const TESSLINE &src);
227
  // Deletes owned data.
228
  void Clear();
229
  // Normalize in-place using the DENORM.
230
  void Normalize(const DENORM &denorm);
231
  // Rotates by the given rotation in place.
232
  void Rotate(const FCOORD rotation);
233
  // Moves by the given vec in place.
234
  void Move(const ICOORD vec);
235
  // Scales by the given factor in place.
236
  void Scale(float factor);
237
  // Sets up the start and vec members of the loop from the pos members.
238
  void SetupFromPos();
239
  // Recomputes the bounding box from the points in the loop.
240
  void ComputeBoundingBox();
241
  // Computes the min and max cross product of the outline points with the
242
  // given vec and returns the results in min_xp and max_xp. Geometrically
243
  // this is the left and right edge of the outline perpendicular to the
244
  // given direction, but to get the distance units correct, you would
245
  // have to divide by the modulus of vec.
246
  void MinMaxCrossProduct(const TPOINT vec, int *min_xp, int *max_xp) const;
247
248
  TBOX bounding_box() const;
249
  // Returns true if *this and other have equal bounding boxes.
250
2.54M
  bool SameBox(const TESSLINE &other) const {
251
2.54M
    return topleft == other.topleft && botright == other.botright;
252
2.54M
  }
253
  // Returns true if the given line segment crosses any outline of this blob.
254
590k
  bool SegmentCrosses(const TPOINT &pt1, const TPOINT &pt2) const {
255
590k
    if (Contains(pt1) && Contains(pt2)) {
256
159k
      EDGEPT *pt = loop;
257
5.12M
      do {
258
5.12M
        if (TPOINT::IsCrossed(pt1, pt2, pt->pos, pt->next->pos)) {
259
19.8k
          return true;
260
19.8k
        }
261
5.10M
        pt = pt->next;
262
5.10M
      } while (pt != loop);
263
159k
    }
264
571k
    return false;
265
590k
  }
266
  // Returns true if the point is contained within the outline box.
267
4.13M
  bool Contains(const TPOINT &pt) const {
268
4.13M
    return topleft.x <= pt.x && pt.x <= botright.x && botright.y <= pt.y && pt.y <= topleft.y;
269
4.13M
  }
270
271
#ifndef GRAPHICS_DISABLED
272
  void plot(ScrollView *window, ScrollView::Color color, ScrollView::Color child_color);
273
#endif // !GRAPHICS_DISABLED
274
275
  // Returns the first outline point that has a different src_outline to its
276
  // predecessor, or, if all the same, the lowest indexed point.
277
  EDGEPT *FindBestStartPt() const;
278
279
0
  int BBArea() const {
280
0
    return (botright.x - topleft.x) * (topleft.y - botright.y);
281
0
  }
282
283
  TPOINT topleft;  // Top left of loop.
284
  TPOINT botright; // Bottom right of loop.
285
  TPOINT start;    // Start of loop.
286
  bool is_hole;    // True if this is a hole/child outline.
287
  EDGEPT *loop;    // Edgeloop.
288
  TESSLINE *next;  // Next outline in blob.
289
};                 // Outline structure.
290
291
struct TBLOB {
292
1.93M
  TBLOB() : outlines(nullptr) {}
293
1.23M
  TBLOB(const TBLOB &src) : outlines(nullptr) {
294
1.23M
    CopyFrom(src);
295
1.23M
  }
296
3.16M
  ~TBLOB() {
297
3.16M
    Clear();
298
3.16M
  }
299
0
  TBLOB &operator=(const TBLOB &src) {
300
0
    CopyFrom(src);
301
0
    return *this;
302
0
  }
303
  // Factory to build a TBLOB from a C_BLOB with polygonal approximation along
304
  // the way. If allow_detailed_fx is true, the EDGEPTs in the returned TBLOB
305
  // contain pointers to the input C_OUTLINEs that enable higher-resolution
306
  // feature extraction that does not use the polygonal approximation.
307
  static TBLOB *PolygonalCopy(bool allow_detailed_fx, C_BLOB *src);
308
  // Factory builds a blob with no outlines, but copies the other member data.
309
  static TBLOB *ShallowCopy(const TBLOB &src);
310
  // Normalizes the blob for classification only if needed.
311
  // (Normally this means a non-zero classify rotation.)
312
  // If no Normalization is needed, then nullptr is returned, and the input blob
313
  // can be used directly. Otherwise a new TBLOB is returned which must be
314
  // deleted after use.
315
  TBLOB *ClassifyNormalizeIfNeeded() const;
316
317
  // Copies the data and the outlines, but leaves next untouched.
318
  void CopyFrom(const TBLOB &src);
319
  // Deletes owned data.
320
  void Clear();
321
  // Sets up the built-in DENORM and normalizes the blob in-place.
322
  // For parameters see DENORM::SetupNormalization, plus the inverse flag for
323
  // this blob and the Pix for the full image.
324
  void Normalize(const BLOCK *block, const FCOORD *rotation, const DENORM *predecessor,
325
                 float x_origin, float y_origin, float x_scale, float y_scale, float final_xshift,
326
                 float final_yshift, bool inverse, Image pix);
327
  // Rotates by the given rotation in place.
328
  void Rotate(const FCOORD rotation);
329
  // Moves by the given vec in place.
330
  void Move(const ICOORD vec);
331
  // Scales by the given factor in place.
332
  void Scale(float factor);
333
  // Recomputes the bounding boxes of the outlines.
334
  void ComputeBoundingBoxes();
335
336
  // Returns the number of outlines.
337
  int NumOutlines() const;
338
339
  TBOX bounding_box() const;
340
341
  // Returns true if the given line segment crosses any outline of this blob.
342
156k
  bool SegmentCrossesOutline(const TPOINT &pt1, const TPOINT &pt2) const {
343
727k
    for (const TESSLINE *outline = outlines; outline != nullptr; outline = outline->next) {
344
590k
      if (outline->SegmentCrosses(pt1, pt2)) {
345
19.8k
        return true;
346
19.8k
      }
347
590k
    }
348
137k
    return false;
349
156k
  }
350
  // Returns true if the point is contained within any of the outline boxes.
351
2.20M
  bool Contains(const TPOINT &pt) const {
352
3.50M
    for (const TESSLINE *outline = outlines; outline != nullptr; outline = outline->next) {
353
3.36M
      if (outline->Contains(pt)) {
354
2.06M
        return true;
355
2.06M
      }
356
3.36M
    }
357
133k
    return false;
358
2.20M
  }
359
360
  // Finds and deletes any duplicate outlines in this blob, without deleting
361
  // their EDGEPTs.
362
  void EliminateDuplicateOutlines();
363
364
  // Swaps the outlines of *this and next if needed to keep the centers in
365
  // increasing x.
366
  void CorrectBlobOrder(TBLOB *next);
367
368
28.1M
  const DENORM &denorm() const {
369
28.1M
    return denorm_;
370
28.1M
  }
371
372
#ifndef GRAPHICS_DISABLED
373
  void plot(ScrollView *window, ScrollView::Color color, ScrollView::Color child_color);
374
#endif // !GRAPHICS_DISABLED
375
376
0
  int BBArea() const {
377
0
    int total_area = 0;
378
0
    for (TESSLINE *outline = outlines; outline != nullptr; outline = outline->next) {
379
0
      total_area += outline->BBArea();
380
0
    }
381
0
    return total_area;
382
0
  }
383
384
  // Computes the center of mass and second moments for the old baseline and
385
  // 2nd moment normalizations. Returns the outline length.
386
  // The input denorm should be the normalizations that have been applied from
387
  // the image to the current state of this TBLOB.
388
  int ComputeMoments(FCOORD *center, FCOORD *second_moments) const;
389
  // Computes the precise bounding box of the coords that are generated by
390
  // GetEdgeCoords. This may be different from the bounding box of the polygon.
391
  void GetPreciseBoundingBox(TBOX *precise_box) const;
392
  // Adds edges to the given vectors.
393
  // For all the edge steps in all the outlines, or polygonal approximation
394
  // where there are no edge steps, collects the steps into x_coords/y_coords.
395
  // x_coords is a collection of the x-coords of vertical edges for each
396
  // y-coord starting at box.bottom().
397
  // y_coords is a collection of the y-coords of horizontal edges for each
398
  // x-coord starting at box.left().
399
  // Eg x_coords[0] is a collection of the x-coords of edges at y=bottom.
400
  // Eg x_coords[1] is a collection of the x-coords of edges at y=bottom + 1.
401
  void GetEdgeCoords(const TBOX &box, std::vector<std::vector<int>> &x_coords,
402
                     std::vector<std::vector<int>> &y_coords) const;
403
404
  TESSLINE *outlines; // List of outlines in blob.
405
406
private: // TODO(rays) Someday the data members will be private too.
407
  // For all the edge steps in all the outlines, or polygonal approximation
408
  // where there are no edge steps, collects the steps into the bounding_box,
409
  // llsq and/or the x_coords/y_coords. Both are used in different kinds of
410
  // normalization.
411
  // For a description of x_coords, y_coords, see GetEdgeCoords above.
412
  void CollectEdges(const TBOX &box, TBOX *bounding_box, LLSQ *llsq,
413
                    std::vector<std::vector<int>> *x_coords,
414
                    std::vector<std::vector<int>> *y_coords) const;
415
416
private:
417
  // DENORM indicating the transformations that this blob has undergone so far.
418
  DENORM denorm_;
419
}; // Blob structure.
420
421
struct TWERD {
422
419k
  TWERD() : latin_script(false) {}
423
40.0k
  TWERD(const TWERD &src) {
424
40.0k
    CopyFrom(src);
425
40.0k
  }
426
459k
  ~TWERD() {
427
459k
    Clear();
428
459k
  }
429
0
  TWERD &operator=(const TWERD &src) {
430
0
    CopyFrom(src);
431
0
    return *this;
432
0
  }
433
  // Factory to build a TWERD from a (C_BLOB) WERD, with polygonal
434
  // approximation along the way.
435
  static TWERD *PolygonalCopy(bool allow_detailed_fx, WERD *src);
436
  // Baseline normalizes the blobs in-place, recording the normalization in the
437
  // DENORMs in the blobs.
438
  void BLNormalize(const BLOCK *block, const ROW *row, Image pix, bool inverse, float x_height,
439
                   float baseline_shift, bool numeric_mode, tesseract::OcrEngineMode hint,
440
                   const TBOX *norm_box, DENORM *word_denorm);
441
  // Copies the data and the blobs, but leaves next untouched.
442
  void CopyFrom(const TWERD &src);
443
  // Deletes owned data.
444
  void Clear();
445
  // Recomputes the bounding boxes of the blobs.
446
  void ComputeBoundingBoxes();
447
448
  // Returns the number of blobs in the word.
449
5.49M
  unsigned NumBlobs() const {
450
5.49M
    return blobs.size();
451
5.49M
  }
452
  TBOX bounding_box() const;
453
454
  // Merges the blobs from start to end, not including end, and deletes
455
  // the blobs between start and end.
456
  void MergeBlobs(unsigned start, unsigned end);
457
458
#ifndef GRAPHICS_DISABLED
459
  void plot(ScrollView *window);
460
#endif // !GRAPHICS_DISABLED
461
462
  std::vector<TBLOB *> blobs; // Blobs in word.
463
  bool latin_script;          // This word is in a latin-based script.
464
};
465
466
/*----------------------------------------------------------------------
467
              F u n c t i o n s
468
----------------------------------------------------------------------*/
469
// TODO(rays) Make divisible_blob and divide_blobs members of TBLOB.
470
bool divisible_blob(TBLOB *blob, bool italic_blob, TPOINT *location);
471
472
void divide_blobs(TBLOB *blob, TBLOB *other_blob, bool italic_blob, const TPOINT &location);
473
474
} // namespace tesseract
475
476
#endif