/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 |