tesseract 4.1.1
Loading...
Searching...
No Matches
stepblob.cpp
Go to the documentation of this file.
1/**********************************************************************
2 * File: stepblob.cpp (Formerly cblob.c)
3 * Description: Code for C_BLOB 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// Include automatically generated configuration file if running autoconf.
20#ifdef HAVE_CONFIG_H
21#include "config_auto.h"
22#endif
23
24#include "stepblob.h"
25#include "allheaders.h" // for pixCreate, pixGetDepth
26#include "genericvector.h" // for GenericVector
27#include "points.h" // for operator+=, FCOORD, ICOORD
28
29class DENORM;
30
31// Max perimeter to width ratio for a baseline position above box bottom.
32const double kMaxPerimeterWidthRatio = 8.0;
33
35/**********************************************************************
36 * position_outline
37 *
38 * Position the outline in the given list at the relevant place
39 * according to its nesting.
40 **********************************************************************/
41static void position_outline( //put in place
42 C_OUTLINE *outline, //thing to place
43 C_OUTLINE_LIST *destlist //desstination list
44 ) {
45 C_OUTLINE *dest_outline; //outline from dest list
46 C_OUTLINE_IT it = destlist; //iterator
47 //iterator on children
48 C_OUTLINE_IT child_it = outline->child ();
49
50 if (!it.empty ()) {
51 do {
52 dest_outline = it.data (); //get destination
53 //encloses dest
54 if (*dest_outline < *outline) {
55 //take off list
56 dest_outline = it.extract ();
57 //put this in place
58 it.add_after_then_move (outline);
59 //make it a child
60 child_it.add_to_end (dest_outline);
61 while (!it.at_last ()) {
62 it.forward (); //do rest of list
63 //check for other children
64 dest_outline = it.data ();
65 if (*dest_outline < *outline) {
66 //take off list
67 dest_outline = it.extract ();
68 child_it.add_to_end (dest_outline);
69 //make it a child
70 if (it.empty ())
71 break;
72 }
73 }
74 return; //finished
75 }
76 //enclosed by dest
77 else if (*outline < *dest_outline) {
78 position_outline (outline, dest_outline->child ());
79 //place in child list
80 return; //finished
81 }
82 it.forward ();
83 }
84 while (!it.at_first ());
85 }
86 it.add_to_end (outline); //at outer level
87}
88
89
90/**********************************************************************
91 * plot_outline_list
92 *
93 * Draw a list of outlines in the given colour and their children
94 * in the child colour.
95 **********************************************************************/
96
97#ifndef GRAPHICS_DISABLED
98static void plot_outline_list( //draw outlines
99 C_OUTLINE_LIST *list, //outline to draw
100 ScrollView* window, //window to draw in
101 ScrollView::Color colour, //colour to use
102 ScrollView::Color child_colour //colour of children
103 ) {
104 C_OUTLINE *outline; //current outline
105 C_OUTLINE_IT it = list; //iterator
106
107 for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ()) {
108 outline = it.data ();
109 //draw it
110 outline->plot (window, colour);
111 if (!outline->child ()->empty ())
112 plot_outline_list (outline->child (), window,
113 child_colour, child_colour);
114 }
115}
116// Draws the outlines in the given colour, and child_colour, normalized
117// using the given denorm, making use of sub-pixel accurate information
118// if available.
119static void plot_normed_outline_list(const DENORM& denorm,
120 C_OUTLINE_LIST *list,
121 ScrollView::Color colour,
122 ScrollView::Color child_colour,
123 ScrollView* window) {
124 C_OUTLINE_IT it(list);
125 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
126 C_OUTLINE* outline = it.data();
127 outline->plot_normed(denorm, colour, window);
128 if (!outline->child()->empty())
129 plot_normed_outline_list(denorm, outline->child(), child_colour,
130 child_colour, window);
131 }
132}
133#endif
134
135
136/**********************************************************************
137 * reverse_outline_list
138 *
139 * Reverse a list of outlines and their children.
140 **********************************************************************/
141
142static void reverse_outline_list(C_OUTLINE_LIST *list) {
143 C_OUTLINE_IT it = list; // iterator
144
145 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
146 C_OUTLINE* outline = it.data();
147 outline->reverse(); // reverse it
148 outline->set_flag(COUT_INVERSE, true);
149 if (!outline->child()->empty())
150 reverse_outline_list(outline->child());
151 }
152}
153
154
155/**********************************************************************
156 * C_BLOB::C_BLOB
157 *
158 * Constructor to build a C_BLOB from a list of C_OUTLINEs.
159 * The C_OUTLINEs are not copied so the source list is emptied.
160 * The C_OUTLINEs are nested correctly in the blob.
161 **********************************************************************/
162
163C_BLOB::C_BLOB(C_OUTLINE_LIST *outline_list) {
164 for (C_OUTLINE_IT ol_it(outline_list); !ol_it.empty(); ol_it.forward()) {
165 C_OUTLINE* outline = ol_it.extract();
166 // Position this outline in appropriate position in the hierarchy.
167 position_outline(outline, &outlines);
168 }
170}
171
172// Simpler constructor to build a blob from a single outline that has
173// already been fully initialized.
175 C_OUTLINE_IT it(&outlines);
176 it.add_to_end(outline);
177}
178
179// Builds a set of one or more blobs from a list of outlines.
180// Input: one outline on outline_list contains all the others, but the
181// nesting and order are undefined.
182// If good_blob is true, the blob is added to good_blobs_it, unless
183// an illegal (generation-skipping) parent-child relationship is found.
184// If so, the parent blob goes to bad_blobs_it, and the immediate children
185// are promoted to the top level, recursively being sent to good_blobs_it.
186// If good_blob is false, all created blobs will go to the bad_blobs_it.
187// Output: outline_list is empty. One or more blobs are added to
188// good_blobs_it and/or bad_blobs_it.
190 C_OUTLINE_LIST* outline_list,
191 C_BLOB_IT* good_blobs_it,
192 C_BLOB_IT* bad_blobs_it) {
193 // List of top-level outlines with correctly nested children.
194 C_OUTLINE_LIST nested_outlines;
195 for (C_OUTLINE_IT ol_it(outline_list); !ol_it.empty(); ol_it.forward()) {
196 C_OUTLINE* outline = ol_it.extract();
197 // Position this outline in appropriate position in the hierarchy.
198 position_outline(outline, &nested_outlines);
199 }
200 // Check for legal nesting and reassign as required.
201 for (C_OUTLINE_IT ol_it(&nested_outlines); !ol_it.empty(); ol_it.forward()) {
202 C_OUTLINE* outline = ol_it.extract();
203 bool blob_is_good = good_blob;
204 if (!outline->IsLegallyNested()) {
205 // The blob is illegally nested.
206 // Mark it bad, and add all its children to the top-level list.
207 blob_is_good = false;
208 ol_it.add_list_after(outline->child());
209 }
210 auto* blob = new C_BLOB(outline);
211 // Set inverse flag and reverse if needed.
212 blob->CheckInverseFlagAndDirection();
213 // Put on appropriate list.
214 if (!blob_is_good && bad_blobs_it != nullptr)
215 bad_blobs_it->add_after_then_move(blob);
216 else
217 good_blobs_it->add_after_then_move(blob);
218 }
219}
220
221// Sets the COUT_INVERSE flag appropriately on the outlines and their
222// children recursively, reversing the outlines if needed so that
223// everything has an anticlockwise top-level.
225 C_OUTLINE_IT ol_it(&outlines);
226 for (ol_it.mark_cycle_pt(); !ol_it.cycled_list(); ol_it.forward()) {
227 C_OUTLINE* outline = ol_it.data();
228 if (outline->turn_direction() < 0) {
229 outline->reverse();
230 reverse_outline_list(outline->child());
231 outline->set_flag(COUT_INVERSE, true);
232 } else {
233 outline->set_flag(COUT_INVERSE, false);
234 }
235 }
236}
237
238
239// Build and return a fake blob containing a single fake outline with no
240// steps.
242 C_OUTLINE_LIST outlines;
243 C_OUTLINE::FakeOutline(box, &outlines);
244 return new C_BLOB(&outlines);
245}
246
247/**********************************************************************
248 * C_BLOB::bounding_box
249 *
250 * Return the bounding box of the blob.
251 **********************************************************************/
252
253TBOX C_BLOB::bounding_box() const { // bounding box
254 C_OUTLINE *outline; // current outline
255 // This is a read-only iteration of the outlines.
256 C_OUTLINE_IT it = const_cast<C_OUTLINE_LIST*>(&outlines);
257 TBOX box; // bounding box
258
259 for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ()) {
260 outline = it.data ();
261 box += outline->bounding_box ();
262 }
263 return box;
264}
265
266
267/**********************************************************************
268 * C_BLOB::area
269 *
270 * Return the area of the blob.
271 **********************************************************************/
272
273int32_t C_BLOB::area() { //area
274 C_OUTLINE *outline; //current outline
275 C_OUTLINE_IT it = &outlines; //outlines of blob
276 int32_t total; //total area
277
278 total = 0;
279 for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ()) {
280 outline = it.data ();
281 total += outline->area ();
282 }
283 return total;
284}
285
286/**********************************************************************
287 * C_BLOB::perimeter
288 *
289 * Return the perimeter of the top and 2nd level outlines.
290 **********************************************************************/
291
293 C_OUTLINE *outline; // current outline
294 C_OUTLINE_IT it = &outlines; // outlines of blob
295 int32_t total; // total perimeter
296
297 total = 0;
298 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
299 outline = it.data();
300 total += outline->perimeter();
301 }
302 return total;
303}
304
305
306/**********************************************************************
307 * C_BLOB::outer_area
308 *
309 * Return the area of the blob.
310 **********************************************************************/
311
312int32_t C_BLOB::outer_area() { //area
313 C_OUTLINE *outline; //current outline
314 C_OUTLINE_IT it = &outlines; //outlines of blob
315 int32_t total; //total area
316
317 total = 0;
318 for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ()) {
319 outline = it.data ();
320 total += outline->outer_area ();
321 }
322 return total;
323}
324
325
326/**********************************************************************
327 * C_BLOB::count_transitions
328 *
329 * Return the total x and y maxes and mins in the blob.
330 * Chlid outlines are not counted.
331 **********************************************************************/
332
334 int32_t threshold //on size
335 ) {
336 C_OUTLINE *outline; //current outline
337 C_OUTLINE_IT it = &outlines; //outlines of blob
338 int32_t total; //total area
339
340 total = 0;
341 for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ()) {
342 outline = it.data ();
343 total += outline->count_transitions (threshold);
344 }
345 return total;
346}
347
348
349/**********************************************************************
350 * C_BLOB::move
351 *
352 * Move C_BLOB by vector
353 **********************************************************************/
354
355void C_BLOB::move( // reposition blob
356 const ICOORD vec // by vector
357 ) {
358 C_OUTLINE_IT it(&outlines); // iterator
359
360 for (it.mark_cycle_pt (); !it.cycled_list (); it.forward ())
361 it.data ()->move (vec); // move each outline
362}
363
364// Static helper for C_BLOB::rotate to allow recursion of child outlines.
365static void RotateOutlineList(const FCOORD& rotation,
366 C_OUTLINE_LIST* outlines) {
367 C_OUTLINE_LIST new_outlines;
368 C_OUTLINE_IT src_it(outlines);
369 C_OUTLINE_IT dest_it(&new_outlines);
370 while (!src_it.empty()) {
371 C_OUTLINE* old_outline = src_it.extract();
372 src_it.forward();
373 auto* new_outline = new C_OUTLINE(old_outline, rotation);
374 if (!old_outline->child()->empty()) {
375 RotateOutlineList(rotation, old_outline->child());
376 C_OUTLINE_IT child_it(new_outline->child());
377 child_it.add_list_after(old_outline->child());
378 }
379 delete old_outline;
380 dest_it.add_to_end(new_outline);
381 }
382 src_it.add_list_after(&new_outlines);
383}
384
385/**********************************************************************
386 * C_BLOB::rotate
387 *
388 * Rotate C_BLOB by rotation.
389 * Warning! has to rebuild all the C_OUTLINEs.
390 **********************************************************************/
391void C_BLOB::rotate(const FCOORD& rotation) {
392 RotateOutlineList(rotation, &outlines);
393}
394
395// Helper calls ComputeEdgeOffsets or ComputeBinaryOffsets recursively on the
396// outline list and its children.
397static void ComputeEdgeOffsetsOutlineList(int threshold, Pix* pix,
398 C_OUTLINE_LIST *list) {
399 C_OUTLINE_IT it(list);
400 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
401 C_OUTLINE* outline = it.data();
402 if (pix != nullptr && pixGetDepth(pix) == 8)
403 outline->ComputeEdgeOffsets(threshold, pix);
404 else
405 outline->ComputeBinaryOffsets();
406 if (!outline->child()->empty())
407 ComputeEdgeOffsetsOutlineList(threshold, pix, outline->child());
408 }
409}
410
411// Adds sub-pixel resolution EdgeOffsets for the outlines using greyscale
412// if the supplied pix is 8-bit or the binary edges if nullptr.
413void C_BLOB::ComputeEdgeOffsets(int threshold, Pix* pix) {
414 ComputeEdgeOffsetsOutlineList(threshold, pix, &outlines);
415}
416
417// Estimates and returns the baseline position based on the shape of the
418// outlines.
419// We first find the minimum y-coord (y_mins) at each x-coord within the blob.
420// If there is a run of some y or y+1 in y_mins that is longer than the total
421// number of positions at bottom or bottom+1, subject to the additional
422// condition that at least one side of the y/y+1 run is higher than y+1, so it
423// is not a local minimum, then y, not the bottom, makes a good candidate
424// baseline position for this blob. Eg
425// | ---|
426// | |
427// |- -----------| <= Good candidate baseline position.
428// |- -|
429// | -|
430// |---| <= Bottom of blob
432 TBOX box = bounding_box();
433 int left = box.left();
434 int width = box.width();
435 int bottom = box.bottom();
436 if (outlines.empty() || perimeter() > width * kMaxPerimeterWidthRatio)
437 return bottom; // This is only for non-CJK blobs.
438 // Get the minimum y coordinate at each x-coordinate.
439 GenericVector<int> y_mins;
440 y_mins.init_to_size(width + 1, box.top());
441 C_OUTLINE_IT it(&outlines);
442 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
443 C_OUTLINE* outline = it.data();
444 ICOORD pos = outline->start_pos();
445 for (int s = 0; s < outline->pathlength(); ++s) {
446 if (pos.y() < y_mins[pos.x() - left])
447 y_mins[pos.x() - left] = pos.y();
448 pos += outline->step(s);
449 }
450 }
451 // Find the total extent of the bottom or bottom + 1.
452 int bottom_extent = 0;
453 for (int x = 0; x <= width; ++x) {
454 if (y_mins[x] == bottom || y_mins[x] == bottom + 1)
455 ++bottom_extent;
456 }
457 // Find the lowest run longer than the bottom extent that is not the bottom.
458 int best_min = box.top();
459 int prev_run = 0;
460 int prev_y = box.top();
461 int prev_prev_y = box.top();
462 for (int x = 0; x < width; x += prev_run) {
463 // Find the length of the current run.
464 int y_at_x = y_mins[x];
465 int run = 1;
466 while (x + run <= width && y_mins[x + run] == y_at_x) ++run;
467 if (y_at_x > bottom + 1) {
468 // Possible contender.
469 int total_run = run;
470 // Find extent of current value or +1 to the right of x.
471 while (x + total_run <= width &&
472 (y_mins[x + total_run] == y_at_x ||
473 y_mins[x + total_run] == y_at_x + 1)) ++total_run;
474 // At least one end has to be higher so it is not a local max.
475 if (prev_prev_y > y_at_x + 1 || x + total_run > width ||
476 y_mins[x + total_run] > y_at_x + 1) {
477 // If the prev_run is at y + 1, then we can add that too. There cannot
478 // be a suitable run at y before that or we would have found it already.
479 if (prev_run > 0 && prev_y == y_at_x + 1) total_run += prev_run;
480 if (total_run > bottom_extent && y_at_x < best_min) {
481 best_min = y_at_x;
482 }
483 }
484 }
485 prev_run = run;
486 prev_prev_y = prev_y;
487 prev_y = y_at_x;
488 }
489 return best_min == box.top() ? bottom : best_min;
490}
491
492static void render_outline_list(C_OUTLINE_LIST *list,
493 int left, int top, Pix* pix) {
494 C_OUTLINE_IT it(list);
495 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
496 C_OUTLINE* outline = it.data();
497 outline->render(left, top, pix);
498 if (!outline->child()->empty())
499 render_outline_list(outline->child(), left, top, pix);
500 }
501}
502
503static void render_outline_list_outline(C_OUTLINE_LIST *list,
504 int left, int top, Pix* pix) {
505 C_OUTLINE_IT it(list);
506 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
507 C_OUTLINE* outline = it.data();
508 outline->render_outline(left, top, pix);
509 }
510}
511
512// Returns a Pix rendering of the blob. pixDestroy after use.
514 TBOX box = bounding_box();
515 Pix* pix = pixCreate(box.width(), box.height(), 1);
516 render_outline_list(&outlines, box.left(), box.top(), pix);
517 return pix;
518}
519
520// Returns a Pix rendering of the outline of the blob. (no fill).
521// pixDestroy after use.
523 TBOX box = bounding_box();
524 Pix* pix = pixCreate(box.width(), box.height(), 1);
525 render_outline_list_outline(&outlines, box.left(), box.top(), pix);
526 return pix;
527}
528
529/**********************************************************************
530 * C_BLOB::plot
531 *
532 * Draw the C_BLOB in the given colour.
533 **********************************************************************/
534
535#ifndef GRAPHICS_DISABLED
536void C_BLOB::plot(ScrollView* window, // window to draw in
537 ScrollView::Color blob_colour, // main colour
538 ScrollView::Color child_colour) { // for holes
539 plot_outline_list(&outlines, window, blob_colour, child_colour);
540}
541// Draws the blob in the given colour, and child_colour, normalized
542// using the given denorm, making use of sub-pixel accurate information
543// if available.
544void C_BLOB::plot_normed(const DENORM& denorm,
545 ScrollView::Color blob_colour,
546 ScrollView::Color child_colour,
547 ScrollView* window) {
548 plot_normed_outline_list(denorm, &outlines, blob_colour, child_colour,
549 window);
550}
551#endif
@ COUT_INVERSE
Definition: coutln.h:42
const double kMaxPerimeterWidthRatio
Definition: stepblob.cpp:32
#define ELISTIZE(CLASSNAME)
Definition: elst.h:931
void init_to_size(int size, const T &t)
bool IsLegallyNested() const
Definition: coutln.cpp:604
C_OUTLINE_LIST * child()
Definition: coutln.h:108
ICOORD step(int index) const
Definition: coutln.h:144
const TBOX & bounding_box() const
Definition: coutln.h:113
void reverse()
Definition: coutln.cpp:565
void render_outline(int left, int top, Pix *pix) const
Definition: coutln.cpp:916
const ICOORD & start_pos() const
Definition: coutln.h:148
int32_t area() const
Definition: coutln.cpp:255
int32_t perimeter() const
Definition: coutln.cpp:289
void plot(ScrollView *window, ScrollView::Color colour) const
Definition: coutln.cpp:942
int32_t outer_area() const
Definition: coutln.cpp:308
void ComputeBinaryOffsets()
Definition: coutln.cpp:837
void ComputeEdgeOffsets(int threshold, Pix *pix)
Definition: coutln.cpp:721
void set_flag(C_OUTLINE_FLAGS mask, bool value)
Definition: coutln.h:102
static void FakeOutline(const TBOX &box, C_OUTLINE_LIST *outlines)
Definition: coutln.cpp:239
int32_t pathlength() const
Definition: coutln.h:135
void render(int left, int top, Pix *pix) const
Definition: coutln.cpp:894
int32_t count_transitions(int32_t threshold)
Definition: coutln.cpp:340
int16_t turn_direction() const
Definition: coutln.cpp:537
void plot_normed(const DENORM &denorm, ScrollView::Color colour, ScrollView *window) const
Definition: coutln.cpp:974
Pix * pix() const
Definition: normalis.h:246
integer coordinate
Definition: points.h:32
int16_t y() const
access_function
Definition: points.h:56
int16_t x() const
access function
Definition: points.h:52
Definition: points.h:189
Definition: rect.h:34
int16_t top() const
Definition: rect.h:58
int16_t width() const
Definition: rect.h:115
int16_t height() const
Definition: rect.h:108
int16_t left() const
Definition: rect.h:72
int16_t bottom() const
Definition: rect.h:65
Pix * render_outline()
Definition: stepblob.cpp:522
void plot(ScrollView *window, ScrollView::Color blob_colour, ScrollView::Color child_colour)
Definition: stepblob.cpp:536
static C_BLOB * FakeBlob(const TBOX &box)
Definition: stepblob.cpp:241
int16_t EstimateBaselinePosition()
Definition: stepblob.cpp:431
int32_t count_transitions(int32_t threshold)
Definition: stepblob.cpp:333
int32_t area()
Definition: stepblob.cpp:273
TBOX bounding_box() const
Definition: stepblob.cpp:253
C_BLOB()=default
void plot_normed(const DENORM &denorm, ScrollView::Color blob_colour, ScrollView::Color child_colour, ScrollView *window)
Definition: stepblob.cpp:544
void ComputeEdgeOffsets(int threshold, Pix *pix)
Definition: stepblob.cpp:413
int32_t outer_area()
Definition: stepblob.cpp:312
void move(const ICOORD vec)
Definition: stepblob.cpp:355
void CheckInverseFlagAndDirection()
Definition: stepblob.cpp:224
int32_t perimeter()
Definition: stepblob.cpp:292
Pix * render()
Definition: stepblob.cpp:513
void rotate(const FCOORD &rotation)
Definition: stepblob.cpp:391
static void ConstructBlobsFromOutlines(bool good_blob, C_OUTLINE_LIST *outline_list, C_BLOB_IT *good_blobs_it, C_BLOB_IT *bad_blobs_it)
Definition: stepblob.cpp:189