tesseract 4.1.1
Loading...
Searching...
No Matches
bbgrid.h
Go to the documentation of this file.
1
2// File: bbgrid.h
3// Description: Class to hold BLOBNBOXs in a grid for fast access
4// to neighbours.
5// Author: Ray Smith
6//
7// (C) Copyright 2007, Google Inc.
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//
19
20#ifndef TESSERACT_TEXTORD_BBGRID_H_
21#define TESSERACT_TEXTORD_BBGRID_H_
22
23#include <unordered_set>
24
25#include "clst.h"
26#include "coutln.h"
27#include "rect.h"
28#include "scrollview.h"
29
30#include "allheaders.h"
31
32class BLOCK;
33
34namespace tesseract {
35
36// Helper function to return a scaled Pix with one pixel per grid cell,
37// set (black) where the given outline enters the corresponding grid cell,
38// and clear where the outline does not touch the grid cell.
39// Also returns the grid coords of the bottom-left of the Pix, in *left
40// and *bottom, which corresponds to (0, 0) on the Pix.
41// Note that the Pix is used upside-down, with (0, 0) being the bottom-left.
42Pix* TraceOutlineOnReducedPix(C_OUTLINE* outline, int gridsize,
43 ICOORD bleft, int* left, int* bottom);
44// As TraceOutlineOnReducedPix above, but on a BLOCK instead of a C_OUTLINE.
45Pix* TraceBlockOnReducedPix(BLOCK* block, int gridsize,
46 ICOORD bleft, int* left, int* bottom);
47
48template<class BBC, class BBC_CLIST, class BBC_C_IT> class GridSearch;
49
50// The GridBase class is the base class for BBGrid and IntGrid.
51// It holds the geometry and scale of the grid.
52class GridBase {
53 public:
54 GridBase() = default;
55 GridBase(int gridsize, const ICOORD& bleft, const ICOORD& tright);
56 virtual ~GridBase();
57
58 // (Re)Initialize the grid. The gridsize is the size in pixels of each cell,
59 // and bleft, tright are the bounding box of everything to go in it.
60 void Init(int gridsize, const ICOORD& bleft, const ICOORD& tright);
61
62 // Simple accessors.
63 int gridsize() const {
64 return gridsize_;
65 }
66 int gridwidth() const {
67 return gridwidth_;
68 }
69 int gridheight() const {
70 return gridheight_;
71 }
72 const ICOORD& bleft() const {
73 return bleft_;
74 }
75 const ICOORD& tright() const {
76 return tright_;
77 }
78 // Compute the given grid coordinates from image coords.
79 void GridCoords(int x, int y, int* grid_x, int* grid_y) const;
80
81 // Clip the given grid coordinates to fit within the grid.
82 void ClipGridCoords(int* x, int* y) const;
83
84 protected:
85 // TODO(rays) Make these private and migrate to the accessors in subclasses.
86 int gridsize_; // Pixel size of each grid cell.
87 int gridwidth_; // Size of the grid in cells.
89 int gridbuckets_; // Total cells in grid.
90 ICOORD bleft_; // Pixel coords of bottom-left of grid.
91 ICOORD tright_; // Pixel coords of top-right of grid.
92
93 private:
94};
95
96// The IntGrid maintains a single int for each cell in a grid.
97class IntGrid : public GridBase {
98 public:
99 IntGrid();
100 IntGrid(int gridsize, const ICOORD& bleft, const ICOORD& tright);
101 ~IntGrid() override;
102
103 // (Re)Initialize the grid. The gridsize is the size in pixels of each cell,
104 // and bleft, tright are the bounding box of everything to go in it.
105 void Init(int gridsize, const ICOORD& bleft, const ICOORD& tright);
106
107 // Clear all the ints in the grid to zero.
108 void Clear();
109
110 // Rotate the grid by rotation, keeping cell contents.
111 // rotation must be a multiple of 90 degrees.
112 // NOTE: due to partial cells, cell coverage in the rotated grid will be
113 // inexact. This is why there is no Rotate for the generic BBGrid.
114 void Rotate(const FCOORD& rotation);
115
116 // Returns a new IntGrid containing values equal to the sum of all the
117 // neighbouring cells. The returned grid must be deleted after use.
118 IntGrid* NeighbourhoodSum() const;
119
120 int GridCellValue(int grid_x, int grid_y) const {
121 ClipGridCoords(&grid_x, &grid_y);
122 return grid_[grid_y * gridwidth_ + grid_x];
123 }
124 void SetGridCell(int grid_x, int grid_y, int value) {
125 ASSERT_HOST(grid_x >= 0 && grid_x < gridwidth());
126 ASSERT_HOST(grid_y >= 0 && grid_y < gridheight());
127 grid_[grid_y * gridwidth_ + grid_x] = value;
128 }
129 // Returns true if more than half the area of the rect is covered by grid
130 // cells that are over the threshold.
131 bool RectMostlyOverThreshold(const TBOX& rect, int threshold) const;
132
133 // Returns true if any cell value in the given rectangle is zero.
134 bool AnyZeroInRect(const TBOX& rect) const;
135
136 // Returns a full-resolution binary pix in which each cell over the given
137 // threshold is filled as a black square. pixDestroy after use.
138 Pix* ThresholdToPix(int threshold) const;
139
140 private:
141 int* grid_; // 2-d array of ints.
142};
143
144// The BBGrid class holds C_LISTs of template classes BBC (bounding box class)
145// in a grid for fast neighbour access.
146// The BBC class must have a member const TBOX& bounding_box() const.
147// The BBC class must have been CLISTIZEH'ed elsewhere to make the
148// list class BBC_CLIST and the iterator BBC_C_IT.
149// Use of C_LISTs enables BBCs to exist in multiple cells simultaneously.
150// As a consequence, ownership of BBCs is assumed to be elsewhere and
151// persistent for at least the life of the BBGrid, or at least until Clear is
152// called which removes all references to inserted objects without actually
153// deleting them.
154// Most uses derive a class from a specific instantiation of BBGrid,
155// thereby making most of the ugly template notation go away.
156// The friend class GridSearch, with the same template arguments, is
157// used to search a grid efficiently in one of several search patterns.
158template<class BBC, class BBC_CLIST, class BBC_C_IT> class BBGrid
159 : public GridBase {
160 friend class GridSearch<BBC, BBC_CLIST, BBC_C_IT>;
161 public:
163 BBGrid(int gridsize, const ICOORD& bleft, const ICOORD& tright);
164 ~BBGrid() override;
165
166 // (Re)Initialize the grid. The gridsize is the size in pixels of each cell,
167 // and bleft, tright are the bounding box of everything to go in it.
168 void Init(int gridsize, const ICOORD& bleft, const ICOORD& tright);
169
170 // Empty all the lists but leave the grid itself intact.
171 void Clear();
172 // Deallocate the data in the lists but otherwise leave the lists and the grid
173 // intact.
174 void ClearGridData(void (*free_method)(BBC*));
175
176 // Insert a bbox into the appropriate place in the grid.
177 // If h_spread, then all cells covered horizontally by the box are
178 // used, otherwise, just the bottom-left. Similarly for v_spread.
179 // WARNING: InsertBBox may invalidate an active GridSearch. Call
180 // RepositionIterator() on any GridSearches that are active on this grid.
181 void InsertBBox(bool h_spread, bool v_spread, BBC* bbox);
182
183 // Using a pix from TraceOutlineOnReducedPix or TraceBlockOnReducedPix, in
184 // which each pixel corresponds to a grid cell, insert a bbox into every
185 // place in the grid where the corresponding pixel is 1. The Pix is handled
186 // upside-down to match the Tesseract coordinate system. (As created by
187 // TraceOutlineOnReducedPix or TraceBlockOnReducedPix.)
188 // (0, 0) in the pix corresponds to (left, bottom) in the
189 // grid (in grid coords), and the pix works up the grid from there.
190 // WARNING: InsertPixPtBBox may invalidate an active GridSearch. Call
191 // RepositionIterator() on any GridSearches that are active on this grid.
192 void InsertPixPtBBox(int left, int bottom, Pix* pix, BBC* bbox);
193
194 // Remove the bbox from the grid.
195 // WARNING: Any GridSearch operating on this grid could be invalidated!
196 // If a GridSearch is operating, call GridSearch::RemoveBBox() instead.
197 void RemoveBBox(BBC* bbox);
198
199 // Returns true if the given rectangle has no overlapping elements.
200 bool RectangleEmpty(const TBOX& rect);
201
202 // Returns an IntGrid showing the number of elements in each cell.
203 // Returned IntGrid must be deleted after use.
205
206 // Make a window of an appropriate size to display things in the grid.
207 ScrollView* MakeWindow(int x, int y, const char* window_name);
208
209 // Display the bounding boxes of the BLOBNBOXes in this grid.
210 // Use of this function requires an additional member of the BBC class:
211 // ScrollView::Color BBC::BoxColor() const.
213
214 // ASSERT_HOST that every cell contains no more than one copy of each entry.
216
217 // Handle a click event in a display window.
218 virtual void HandleClick(int x, int y);
219
220 protected:
221 BBC_CLIST* grid_; // 2-d array of CLISTS of BBC elements.
222
223 private:
224};
225
226// Hash functor for generic pointers.
227template<typename T> struct PtrHash {
228 size_t operator()(const T* ptr) const {
229 return reinterpret_cast<uintptr_t>(ptr) / sizeof(T);
230 }
231};
232
233
234// The GridSearch class enables neighbourhood searching on a BBGrid.
235template<class BBC, class BBC_CLIST, class BBC_C_IT> class GridSearch {
236 public:
238 : grid_(grid) {
239 }
240
241 // Get the grid x, y coords of the most recently returned BBC.
242 int GridX() const {
243 return x_;
244 }
245 int GridY() const {
246 return y_;
247 }
248
249 // Sets the search mode to return a box only once.
250 // Efficiency warning: Implementation currently uses a squared-order
251 // search in the number of returned elements. Use only where a small
252 // number of elements are spread over a wide area, eg ColPartitions.
253 void SetUniqueMode(bool mode) {
254 unique_mode_ = mode;
255 }
256 // TODO(rays) Replace calls to ReturnedSeedElement with SetUniqueMode.
257 // It only works if the search includes the bottom-left corner.
258 // Apart from full search, all other searches return a box several
259 // times if the box is inserted with h_spread or v_spread.
260 // This method will return true for only one occurrence of each box
261 // that was inserted with both h_spread and v_spread as true.
262 // It will usually return false for boxes that were not inserted with
263 // both h_spread=true and v_spread=true
264 bool ReturnedSeedElement() const {
265 TBOX box = previous_return_->bounding_box();
266 int x_center = (box.left()+box.right())/2;
267 int y_center = (box.top()+box.bottom())/2;
268 int grid_x, grid_y;
269 grid_->GridCoords(x_center, y_center, &grid_x, &grid_y);
270 return (x_ == grid_x) && (y_ == grid_y);
271 }
272
273 // Various searching iterations... Note that these iterations
274 // all share data members, so you can't run more than one iteration
275 // in parallel in a single GridSearch instance, but multiple instances
276 // can search the same BBGrid in parallel.
277 // Note that all the searches can return blobs that may not exactly
278 // match the search conditions, since they return everything in the
279 // covered grid cells. It is up to the caller to check for
280 // appropriateness.
281 // TODO(rays) NextRectSearch only returns valid elements. Make the other
282 // searches test before return also and remove the tests from code
283 // that uses GridSearch.
284
285 // Start a new full search. Will iterate all stored blobs, from the top.
286 // If the blobs have been inserted using InsertBBox, (not InsertPixPtBBox)
287 // then the full search guarantees to return each blob in the grid once.
288 // Other searches may return a blob more than once if they have been
289 // inserted using h_spread or v_spread.
290 void StartFullSearch();
291 // Return the next bbox in the search or nullptr if done.
292 BBC* NextFullSearch();
293
294 // Start a new radius search. Will search in a spiral up to a
295 // given maximum radius in grid cells from the given center in pixels.
296 void StartRadSearch(int x, int y, int max_radius);
297 // Return the next bbox in the radius search or nullptr if the
298 // maximum radius has been reached.
299 BBC* NextRadSearch();
300
301 // Start a new left or right-looking search. Will search to the side
302 // for a box that vertically overlaps the given vertical line segment.
303 // CAVEAT: This search returns all blobs from the cells to the side
304 // of the start, and somewhat below, since there is no guarantee
305 // that there may not be a taller object in a lower cell. The
306 // blobs returned will include all those that vertically overlap and
307 // are no more than twice as high, but may also include some that do
308 // not overlap and some that are more than twice as high.
309 void StartSideSearch(int x, int ymin, int ymax);
310 // Return the next bbox in the side search or nullptr if the
311 // edge has been reached. Searches left to right or right to left
312 // according to the flag.
313 BBC* NextSideSearch(bool right_to_left);
314
315 // Start a vertical-looking search. Will search up or down
316 // for a box that horizontally overlaps the given line segment.
317 void StartVerticalSearch(int xmin, int xmax, int y);
318 // Return the next bbox in the vertical search or nullptr if the
319 // edge has been reached. Searches top to bottom or bottom to top
320 // according to the flag.
321 BBC* NextVerticalSearch(bool top_to_bottom);
322
323 // Start a rectangular search. Will search for a box that overlaps the
324 // given rectangle.
325 void StartRectSearch(const TBOX& rect);
326 // Return the next bbox in the rectangular search or nullptr if complete.
327 BBC* NextRectSearch();
328
329 // Remove the last returned BBC. Will not invalidate this. May invalidate
330 // any other concurrent GridSearch on the same grid. If any others are
331 // in use, call RepositionIterator on those, to continue without harm.
332 void RemoveBBox();
333 void RepositionIterator();
334
335 private:
336 // Factored out helper to start a search.
337 void CommonStart(int x, int y);
338 // Factored out helper to complete a next search.
339 BBC* CommonNext();
340 // Factored out final return when search is exhausted.
341 BBC* CommonEnd();
342 // Factored out function to set the iterator to the current x_, y_
343 // grid coords and mark the cycle pt.
344 void SetIterator();
345
346 private:
347 // The grid we are searching.
348 BBGrid<BBC, BBC_CLIST, BBC_C_IT>* grid_ = nullptr;
349 // For executing a search. The different search algorithms use these in
350 // different ways, but most use x_origin_ and y_origin_ as the start position.
351 int x_origin_ = 0;
352 int y_origin_ = 0;
353 int max_radius_ = 0;
354 int radius_ = 0;
355 int rad_index_ = 0;
356 int rad_dir_ = 0;
357 TBOX rect_;
358 int x_ = 0; // The current location in grid coords, of the current search.
359 int y_ = 0;
360 bool unique_mode_ = false;
361 BBC* previous_return_ = nullptr; // Previous return from Next*.
362 BBC* next_return_ = nullptr; // Current value of it_.data() used for repositioning.
363 // An iterator over the list at (x_, y_) in the grid_.
364 BBC_C_IT it_;
365 // Set of unique returned elements used when unique_mode_ is true.
366 std::unordered_set<BBC*, PtrHash<BBC> > returns_;
367};
368
369// Sort function to sort a BBC by bounding_box().left().
370template<class BBC>
371int SortByBoxLeft(const void* void1, const void* void2) {
372 // The void*s are actually doubly indirected, so get rid of one level.
373 const BBC* p1 = *static_cast<const BBC* const*>(void1);
374 const BBC* p2 = *static_cast<const BBC* const*>(void2);
375 int result = p1->bounding_box().left() - p2->bounding_box().left();
376 if (result != 0)
377 return result;
378 result = p1->bounding_box().right() - p2->bounding_box().right();
379 if (result != 0)
380 return result;
381 result = p1->bounding_box().bottom() - p2->bounding_box().bottom();
382 if (result != 0)
383 return result;
384 return p1->bounding_box().top() - p2->bounding_box().top();
385}
386
387// Sort function to sort a BBC by bounding_box().right() in right-to-left order.
388template<class BBC>
389int SortRightToLeft(const void* void1, const void* void2) {
390 // The void*s are actually doubly indirected, so get rid of one level.
391 const BBC* p1 = *static_cast<const BBC* const*>(void1);
392 const BBC* p2 = *static_cast<const BBC* const*>(void2);
393 int result = p2->bounding_box().right() - p1->bounding_box().right();
394 if (result != 0)
395 return result;
396 result = p2->bounding_box().left() - p1->bounding_box().left();
397 if (result != 0)
398 return result;
399 result = p1->bounding_box().bottom() - p2->bounding_box().bottom();
400 if (result != 0)
401 return result;
402 return p1->bounding_box().top() - p2->bounding_box().top();
403}
404
405// Sort function to sort a BBC by bounding_box().bottom().
406template<class BBC>
407int SortByBoxBottom(const void* void1, const void* void2) {
408 // The void*s are actually doubly indirected, so get rid of one level.
409 const BBC* p1 = *static_cast<const BBC* const*>(void1);
410 const BBC* p2 = *static_cast<const BBC* const*>(void2);
411 int result = p1->bounding_box().bottom() - p2->bounding_box().bottom();
412 if (result != 0)
413 return result;
414 result = p1->bounding_box().top() - p2->bounding_box().top();
415 if (result != 0)
416 return result;
417 result = p1->bounding_box().left() - p2->bounding_box().left();
418 if (result != 0)
419 return result;
420 return p1->bounding_box().right() - p2->bounding_box().right();
421}
422
424// BBGrid IMPLEMENTATION.
426template<class BBC, class BBC_CLIST, class BBC_C_IT>
428}
429
430template<class BBC, class BBC_CLIST, class BBC_C_IT>
432 int gridsize, const ICOORD& bleft, const ICOORD& tright)
433 : grid_(nullptr) {
435}
436
437template<class BBC, class BBC_CLIST, class BBC_C_IT>
439 delete [] grid_;
440}
441
442// (Re)Initialize the grid. The gridsize is the size in pixels of each cell,
443// and bleft, tright are the bounding box of everything to go in it.
444template<class BBC, class BBC_CLIST, class BBC_C_IT>
446 const ICOORD& bleft,
447 const ICOORD& tright) {
448 GridBase::Init(gridsize, bleft, tright);
449 delete [] grid_;
450 grid_ = new BBC_CLIST[gridbuckets_];
451}
452
453// Clear all lists, but leave the array of lists present.
454template<class BBC, class BBC_CLIST, class BBC_C_IT>
456 for (int i = 0; i < gridbuckets_; ++i) {
457 grid_[i].shallow_clear();
458 }
459}
460
461// Deallocate the data in the lists but otherwise leave the lists and the grid
462// intact.
463template<class BBC, class BBC_CLIST, class BBC_C_IT>
465 void (*free_method)(BBC*)) {
466 if (grid_ == nullptr) return;
468 search.StartFullSearch();
469 BBC* bb;
470 BBC_CLIST bb_list;
471 BBC_C_IT it(&bb_list);
472 while ((bb = search.NextFullSearch()) != nullptr) {
473 it.add_after_then_move(bb);
474 }
475 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
476 free_method(it.data());
477 }
478}
479
480// Insert a bbox into the appropriate place in the grid.
481// If h_spread, then all cells covered horizontally by the box are
482// used, otherwise, just the bottom-left. Similarly for v_spread.
483// WARNING: InsertBBox may invalidate an active GridSearch. Call
484// RepositionIterator() on any GridSearches that are active on this grid.
485template<class BBC, class BBC_CLIST, class BBC_C_IT>
486void BBGrid<BBC, BBC_CLIST, BBC_C_IT>::InsertBBox(bool h_spread, bool v_spread,
487 BBC* bbox) {
488 TBOX box = bbox->bounding_box();
489 int start_x, start_y, end_x, end_y;
490 GridCoords(box.left(), box.bottom(), &start_x, &start_y);
491 GridCoords(box.right(), box.top(), &end_x, &end_y);
492 if (!h_spread)
493 end_x = start_x;
494 if (!v_spread)
495 end_y = start_y;
496 int grid_index = start_y * gridwidth_;
497 for (int y = start_y; y <= end_y; ++y, grid_index += gridwidth_) {
498 for (int x = start_x; x <= end_x; ++x) {
499 grid_[grid_index + x].add_sorted(SortByBoxLeft<BBC>, true, bbox);
500 }
501 }
502}
503
504// Using a pix from TraceOutlineOnReducedPix or TraceBlockOnReducedPix, in
505// which each pixel corresponds to a grid cell, insert a bbox into every
506// place in the grid where the corresponding pixel is 1. The Pix is handled
507// upside-down to match the Tesseract coordinate system. (As created by
508// TraceOutlineOnReducedPix or TraceBlockOnReducedPix.)
509// (0, 0) in the pix corresponds to (left, bottom) in the
510// grid (in grid coords), and the pix works up the grid from there.
511// WARNING: InsertPixPtBBox may invalidate an active GridSearch. Call
512// RepositionIterator() on any GridSearches that are active on this grid.
513template<class BBC, class BBC_CLIST, class BBC_C_IT>
515 Pix* pix, BBC* bbox) {
516 int width = pixGetWidth(pix);
517 int height = pixGetHeight(pix);
518 for (int y = 0; y < height; ++y) {
519 l_uint32* data = pixGetData(pix) + y * pixGetWpl(pix);
520 for (int x = 0; x < width; ++x) {
521 if (GET_DATA_BIT(data, x)) {
522 grid_[(bottom + y) * gridwidth_ + x + left].
523 add_sorted(SortByBoxLeft<BBC>, true, bbox);
524 }
525 }
526 }
527}
528
529// Remove the bbox from the grid.
530// WARNING: Any GridSearch operating on this grid could be invalidated!
531// If a GridSearch is operating, call GridSearch::RemoveBBox() instead.
532template<class BBC, class BBC_CLIST, class BBC_C_IT>
534 TBOX box = bbox->bounding_box();
535 int start_x, start_y, end_x, end_y;
536 GridCoords(box.left(), box.bottom(), &start_x, &start_y);
537 GridCoords(box.right(), box.top(), &end_x, &end_y);
538 int grid_index = start_y * gridwidth_;
539 for (int y = start_y; y <= end_y; ++y, grid_index += gridwidth_) {
540 for (int x = start_x; x <= end_x; ++x) {
541 BBC_C_IT it(&grid_[grid_index + x]);
542 for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
543 if (it.data() == bbox)
544 it.extract();
545 }
546 }
547 }
548}
549
550// Returns true if the given rectangle has no overlapping elements.
551template<class BBC, class BBC_CLIST, class BBC_C_IT>
554 rsearch.StartRectSearch(rect);
555 return rsearch.NextRectSearch() == nullptr;
556}
557
558// Returns an IntGrid showing the number of elements in each cell.
559// Returned IntGrid must be deleted after use.
560template<class BBC, class BBC_CLIST, class BBC_C_IT>
562 auto* intgrid = new IntGrid(gridsize(), bleft(), tright());
563 for (int y = 0; y < gridheight(); ++y) {
564 for (int x = 0; x < gridwidth(); ++x) {
565 int cell_count = grid_[y * gridwidth() + x].length();
566 intgrid->SetGridCell(x, y, cell_count);
567 }
568 }
569 return intgrid;
570}
571
572
573template<class G> class TabEventHandler : public SVEventHandler {
574 public:
575 explicit TabEventHandler(G* grid) : grid_(grid) {
576 }
577 void Notify(const SVEvent* sv_event) override {
578 if (sv_event->type == SVET_CLICK) {
579 grid_->HandleClick(sv_event->x, sv_event->y);
580 }
581 }
582 private:
583 G* grid_;
584};
585
586// Make a window of an appropriate size to display things in the grid.
587// Position the window at the given x,y.
588template<class BBC, class BBC_CLIST, class BBC_C_IT>
590 int x, int y, const char* window_name) {
591 ScrollView* tab_win = nullptr;
592#ifndef GRAPHICS_DISABLED
593 tab_win = new ScrollView(window_name, x, y,
594 tright_.x() - bleft_.x(),
595 tright_.y() - bleft_.y(),
596 tright_.x() - bleft_.x(),
597 tright_.y() - bleft_.y(),
598 true);
599 auto* handler =
601 tab_win->AddEventHandler(handler);
602 tab_win->Pen(ScrollView::GREY);
603 tab_win->Rectangle(0, 0, tright_.x() - bleft_.x(), tright_.y() - bleft_.y());
604#endif
605 return tab_win;
606}
607
608// Create a window at (x,y) and display the bounding boxes of the
609// BLOBNBOXes in this grid.
610// Use of this function requires an additional member of the BBC class:
611// ScrollView::Color BBC::BoxColor() const.
612template<class BBC, class BBC_CLIST, class BBC_C_IT>
614#ifndef GRAPHICS_DISABLED
615 tab_win->Pen(ScrollView::BLUE);
616 tab_win->Brush(ScrollView::NONE);
617
618 // For every bbox in the grid, display it.
620 gsearch.StartFullSearch();
621 BBC* bbox;
622 while ((bbox = gsearch.NextFullSearch()) != nullptr) {
623 const TBOX& box = bbox->bounding_box();
624 int left_x = box.left();
625 int right_x = box.right();
626 int top_y = box.top();
627 int bottom_y = box.bottom();
628 ScrollView::Color box_color = bbox->BoxColor();
629 tab_win->Pen(box_color);
630 tab_win->Rectangle(left_x, bottom_y, right_x, top_y);
631 }
632 tab_win->Update();
633#endif
634}
635
636// ASSERT_HOST that every cell contains no more than one copy of each entry.
637template<class BBC, class BBC_CLIST, class BBC_C_IT>
639 // Process all grid cells.
640 for (int i = gridwidth_ * gridheight_ - 1; i >= 0; --i) {
641 // Iterate over all elements excent the last.
642 for (BBC_C_IT it(&grid_[i]); !it.at_last(); it.forward()) {
643 BBC* ptr = it.data();
644 BBC_C_IT it2(it);
645 // None of the rest of the elements in the list should equal ptr.
646 for (it2.forward(); !it2.at_first(); it2.forward()) {
647 ASSERT_HOST(it2.data() != ptr);
648 }
649 }
650 }
651}
652
653// Handle a click event in a display window.
654template<class BBC, class BBC_CLIST, class BBC_C_IT>
656 tprintf("Click at (%d, %d)\n", x, y);
657}
658
660// GridSearch IMPLEMENTATION.
662
663// Start a new full search. Will iterate all stored blobs.
664template<class BBC, class BBC_CLIST, class BBC_C_IT>
666 // Full search uses x_ and y_ as the current grid
667 // cell being searched.
668 CommonStart(grid_->bleft_.x(), grid_->tright_.y());
669}
670
671// Return the next bbox in the search or nullptr if done.
672// The other searches will return a box that overlaps the grid cell
673// thereby duplicating boxes, but NextFullSearch only returns each box once.
674template<class BBC, class BBC_CLIST, class BBC_C_IT>
676 int x;
677 int y;
678 do {
679 while (it_.cycled_list()) {
680 ++x_;
681 if (x_ >= grid_->gridwidth_) {
682 --y_;
683 if (y_ < 0)
684 return CommonEnd();
685 x_ = 0;
686 }
687 SetIterator();
688 }
689 CommonNext();
690 TBOX box = previous_return_->bounding_box();
691 grid_->GridCoords(box.left(), box.bottom(), &x, &y);
692 } while (x != x_ || y != y_);
693 return previous_return_;
694}
695
696// Start a new radius search.
697template<class BBC, class BBC_CLIST, class BBC_C_IT>
699 int max_radius) {
700 // Rad search uses x_origin_ and y_origin_ as the center of the circle.
701 // The radius_ is the radius of the (diamond-shaped) circle and
702 // rad_index/rad_dir_ combine to determine the position around it.
703 max_radius_ = max_radius;
704 radius_ = 0;
705 rad_index_ = 0;
706 rad_dir_ = 3;
707 CommonStart(x, y);
708}
709
710// Return the next bbox in the radius search or nullptr if the
711// maximum radius has been reached.
712template<class BBC, class BBC_CLIST, class BBC_C_IT>
714 do {
715 while (it_.cycled_list()) {
716 ++rad_index_;
717 if (rad_index_ >= radius_) {
718 ++rad_dir_;
719 rad_index_ = 0;
720 if (rad_dir_ >= 4) {
721 ++radius_;
722 if (radius_ > max_radius_)
723 return CommonEnd();
724 rad_dir_ = 0;
725 }
726 }
727 ICOORD offset = C_OUTLINE::chain_step(rad_dir_);
728 offset *= radius_ - rad_index_;
729 offset += C_OUTLINE::chain_step(rad_dir_ + 1) * rad_index_;
730 x_ = x_origin_ + offset.x();
731 y_ = y_origin_ + offset.y();
732 if (x_ >= 0 && x_ < grid_->gridwidth_ &&
733 y_ >= 0 && y_ < grid_->gridheight_)
734 SetIterator();
735 }
736 CommonNext();
737 } while (unique_mode_ && returns_.find(previous_return_) != returns_.end());
738 if (unique_mode_)
739 returns_.insert(previous_return_);
740 return previous_return_;
741}
742
743// Start a new left or right-looking search. Will search to the side
744// for a box that vertically overlaps the given vertical line segment.
745template<class BBC, class BBC_CLIST, class BBC_C_IT>
747 int ymin, int ymax) {
748 // Right search records the x in x_origin_, the ymax in y_origin_
749 // and the size of the vertical strip to search in radius_.
750 // To guarantee finding overlapping objects of up to twice the
751 // given size, double the height.
752 radius_ = ((ymax - ymin) * 2 + grid_->gridsize_ - 1) / grid_->gridsize_;
753 rad_index_ = 0;
754 CommonStart(x, ymax);
755}
756
757// Return the next bbox in the side search or nullptr if the
758// edge has been reached. Searches left to right or right to left
759// according to the flag.
760template<class BBC, class BBC_CLIST, class BBC_C_IT>
762 do {
763 while (it_.cycled_list()) {
764 ++rad_index_;
765 if (rad_index_ > radius_) {
766 if (right_to_left)
767 --x_;
768 else
769 ++x_;
770 rad_index_ = 0;
771 if (x_ < 0 || x_ >= grid_->gridwidth_)
772 return CommonEnd();
773 }
774 y_ = y_origin_ - rad_index_;
775 if (y_ >= 0 && y_ < grid_->gridheight_)
776 SetIterator();
777 }
778 CommonNext();
779 } while (unique_mode_ && returns_.find(previous_return_) != returns_.end());
780 if (unique_mode_)
781 returns_.insert(previous_return_);
782 return previous_return_;
783}
784
785// Start a vertical-looking search. Will search up or down
786// for a box that horizontally overlaps the given line segment.
787template<class BBC, class BBC_CLIST, class BBC_C_IT>
789 int xmax,
790 int y) {
791 // Right search records the xmin in x_origin_, the y in y_origin_
792 // and the size of the horizontal strip to search in radius_.
793 radius_ = (xmax - xmin + grid_->gridsize_ - 1) / grid_->gridsize_;
794 rad_index_ = 0;
795 CommonStart(xmin, y);
796}
797
798// Return the next bbox in the vertical search or nullptr if the
799// edge has been reached. Searches top to bottom or bottom to top
800// according to the flag.
801template<class BBC, class BBC_CLIST, class BBC_C_IT>
803 bool top_to_bottom) {
804 do {
805 while (it_.cycled_list()) {
806 ++rad_index_;
807 if (rad_index_ > radius_) {
808 if (top_to_bottom)
809 --y_;
810 else
811 ++y_;
812 rad_index_ = 0;
813 if (y_ < 0 || y_ >= grid_->gridheight_)
814 return CommonEnd();
815 }
816 x_ = x_origin_ + rad_index_;
817 if (x_ >= 0 && x_ < grid_->gridwidth_)
818 SetIterator();
819 }
820 CommonNext();
821 } while (unique_mode_ && returns_.find(previous_return_) != returns_.end());
822 if (unique_mode_)
823 returns_.insert(previous_return_);
824 return previous_return_;
825}
826
827// Start a rectangular search. Will search for a box that overlaps the
828// given rectangle.
829template<class BBC, class BBC_CLIST, class BBC_C_IT>
831 // Rect search records the xmin in x_origin_, the ymin in y_origin_
832 // and the xmax in max_radius_.
833 // The search proceeds left to right, top to bottom.
834 rect_ = rect;
835 CommonStart(rect.left(), rect.top());
836 grid_->GridCoords(rect.right(), rect.bottom(), // - rect.height(),
837 &max_radius_, &y_origin_);
838}
839
840// Return the next bbox in the rectangular search or nullptr if complete.
841template<class BBC, class BBC_CLIST, class BBC_C_IT>
843 do {
844 while (it_.cycled_list()) {
845 ++x_;
846 if (x_ > max_radius_) {
847 --y_;
848 x_ = x_origin_;
849 if (y_ < y_origin_)
850 return CommonEnd();
851 }
852 SetIterator();
853 }
854 CommonNext();
855 } while (!rect_.overlap(previous_return_->bounding_box()) ||
856 (unique_mode_ && returns_.find(previous_return_) != returns_.end()));
857 if (unique_mode_)
858 returns_.insert(previous_return_);
859 return previous_return_;
860}
861
862// Remove the last returned BBC. Will not invalidate this. May invalidate
863// any other concurrent GridSearch on the same grid. If any others are
864// in use, call RepositionIterator on those, to continue without harm.
865template<class BBC, class BBC_CLIST, class BBC_C_IT>
867 if (previous_return_ != nullptr) {
868 // Remove all instances of previous_return_ from the list, so the iterator
869 // remains valid after removal from the rest of the grid cells.
870 // if previous_return_ is not on the list, then it has been removed already.
871 BBC* prev_data = nullptr;
872 BBC* new_previous_return = nullptr;
873 it_.move_to_first();
874 for (it_.mark_cycle_pt(); !it_.cycled_list();) {
875 if (it_.data() == previous_return_) {
876 new_previous_return = prev_data;
877 it_.extract();
878 it_.forward();
879 next_return_ = it_.cycled_list() ? nullptr : it_.data();
880 } else {
881 prev_data = it_.data();
882 it_.forward();
883 }
884 }
885 grid_->RemoveBBox(previous_return_);
886 previous_return_ = new_previous_return;
887 RepositionIterator();
888 }
889}
890
891template<class BBC, class BBC_CLIST, class BBC_C_IT>
893 // Something was deleted, so we have little choice but to clear the
894 // returns list.
895 returns_.clear();
896 // Reset the iterator back to one past the previous return.
897 // If the previous_return_ is no longer in the list, then
898 // next_return_ serves as a backup.
899 it_.move_to_first();
900 // Special case, the first element was removed and reposition
901 // iterator was called. In this case, the data is fine, but the
902 // cycle point is not. Detect it and return.
903 if (!it_.empty() && it_.data() == next_return_) {
904 it_.mark_cycle_pt();
905 return;
906 }
907 for (it_.mark_cycle_pt(); !it_.cycled_list(); it_.forward()) {
908 if (it_.data() == previous_return_ ||
909 it_.data_relative(1) == next_return_) {
910 CommonNext();
911 return;
912 }
913 }
914 // We ran off the end of the list. Move to a new cell next time.
915 previous_return_ = nullptr;
916 next_return_ = nullptr;
917}
918
919// Factored out helper to start a search.
920template<class BBC, class BBC_CLIST, class BBC_C_IT>
922 grid_->GridCoords(x, y, &x_origin_, &y_origin_);
923 x_ = x_origin_;
924 y_ = y_origin_;
925 SetIterator();
926 previous_return_ = nullptr;
927 next_return_ = it_.empty() ? nullptr : it_.data();
928 returns_.clear();
929}
930
931// Factored out helper to complete a next search.
932template<class BBC, class BBC_CLIST, class BBC_C_IT>
933BBC* GridSearch<BBC, BBC_CLIST, BBC_C_IT>::CommonNext() {
934 previous_return_ = it_.data();
935 it_.forward();
936 next_return_ = it_.cycled_list() ? nullptr : it_.data();
937 return previous_return_;
938}
939
940// Factored out final return when search is exhausted.
941template<class BBC, class BBC_CLIST, class BBC_C_IT>
942BBC* GridSearch<BBC, BBC_CLIST, BBC_C_IT>::CommonEnd() {
943 previous_return_ = nullptr;
944 next_return_ = nullptr;
945 return nullptr;
946}
947
948// Factored out function to set the iterator to the current x_, y_
949// grid coords and mark the cycle pt.
950template<class BBC, class BBC_CLIST, class BBC_C_IT>
951void GridSearch<BBC, BBC_CLIST, BBC_C_IT>::SetIterator() {
952 it_= &(grid_->grid_[y_ * grid_->gridwidth_ + x_]);
953 it_.mark_cycle_pt();
954}
955
956} // namespace tesseract.
957
958#endif // TESSERACT_TEXTORD_BBGRID_H_
#define ASSERT_HOST(x)
Definition: errcode.h:88
DLLSYM void tprintf(const char *format,...)
Definition: tprintf.cpp:35
LIST search(LIST list, void *key, int_compare is_equal)
Definition: oldlist.cpp:258
@ SVET_CLICK
Definition: scrollview.h:48
int SortByBoxBottom(const void *void1, const void *void2)
Definition: bbgrid.h:407
Pix * TraceBlockOnReducedPix(BLOCK *block, int gridsize, ICOORD bleft, int *left, int *bottom)
Definition: bbgrid.cpp:254
int SortByBoxLeft(const void *void1, const void *void2)
Definition: bbgrid.h:371
Pix * TraceOutlineOnReducedPix(C_OUTLINE *outline, int gridsize, ICOORD bleft, int *left, int *bottom)
Definition: bbgrid.cpp:228
int SortRightToLeft(const void *void1, const void *void2)
Definition: bbgrid.h:389
static ICOORD chain_step(int chaindir)
Definition: coutln.cpp:1049
Definition: ocrblock.h:31
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 left() const
Definition: rect.h:72
int16_t bottom() const
Definition: rect.h:65
int16_t right() const
Definition: rect.h:79
bool ReturnedSeedElement() const
Definition: bbgrid.h:264
void StartVerticalSearch(int xmin, int xmax, int y)
Definition: bbgrid.h:788
void StartRadSearch(int x, int y, int max_radius)
Definition: bbgrid.h:698
void SetUniqueMode(bool mode)
Definition: bbgrid.h:253
int GridX() const
Definition: bbgrid.h:242
int GridY() const
Definition: bbgrid.h:245
GridSearch(BBGrid< BBC, BBC_CLIST, BBC_C_IT > *grid)
Definition: bbgrid.h:237
BBC * NextSideSearch(bool right_to_left)
Definition: bbgrid.h:761
BBC * NextRectSearch()
Definition: bbgrid.h:842
void StartSideSearch(int x, int ymin, int ymax)
Definition: bbgrid.h:746
void StartFullSearch()
Definition: bbgrid.h:665
BBC * NextVerticalSearch(bool top_to_bottom)
Definition: bbgrid.h:802
void RepositionIterator()
Definition: bbgrid.h:892
void StartRectSearch(const TBOX &rect)
Definition: bbgrid.h:830
BBC * NextFullSearch()
Definition: bbgrid.h:675
BBC * NextRadSearch()
Definition: bbgrid.h:713
int gridsize() const
Definition: bbgrid.h:63
int gridheight() const
Definition: bbgrid.h:69
void ClipGridCoords(int *x, int *y) const
Definition: bbgrid.cpp:59
void Init(int gridsize, const ICOORD &bleft, const ICOORD &tright)
Definition: bbgrid.cpp:40
const ICOORD & bleft() const
Definition: bbgrid.h:72
int gridwidth() const
Definition: bbgrid.h:66
ICOORD tright_
Definition: bbgrid.h:91
void GridCoords(int x, int y, int *grid_x, int *grid_y) const
Definition: bbgrid.cpp:52
const ICOORD & tright() const
Definition: bbgrid.h:75
IntGrid * NeighbourhoodSum() const
Definition: bbgrid.cpp:132
Pix * ThresholdToPix(int threshold) const
Definition: bbgrid.cpp:190
int GridCellValue(int grid_x, int grid_y) const
Definition: bbgrid.h:120
void Init(int gridsize, const ICOORD &bleft, const ICOORD &tright)
Definition: bbgrid.cpp:79
bool RectMostlyOverThreshold(const TBOX &rect, int threshold) const
Definition: bbgrid.cpp:154
void SetGridCell(int grid_x, int grid_y, int value)
Definition: bbgrid.h:124
~IntGrid() override
Definition: bbgrid.cpp:73
void Rotate(const FCOORD &rotation)
Definition: bbgrid.cpp:99
bool AnyZeroInRect(const TBOX &rect) const
Definition: bbgrid.cpp:174
void DisplayBoxes(ScrollView *window)
Definition: bbgrid.h:613
void Clear()
Definition: bbgrid.h:455
void AssertNoDuplicates()
Definition: bbgrid.h:638
void Init(int gridsize, const ICOORD &bleft, const ICOORD &tright)
Definition: bbgrid.h:445
~BBGrid() override
Definition: bbgrid.h:438
IntGrid * CountCellElements()
Definition: bbgrid.h:561
void InsertPixPtBBox(int left, int bottom, Pix *pix, BBC *bbox)
Definition: bbgrid.h:514
void InsertBBox(bool h_spread, bool v_spread, BBC *bbox)
Definition: bbgrid.h:486
virtual void HandleClick(int x, int y)
Definition: bbgrid.h:655
void ClearGridData(void(*free_method)(BBC *))
Definition: bbgrid.h:464
ScrollView * MakeWindow(int x, int y, const char *window_name)
Definition: bbgrid.h:589
bool RectangleEmpty(const TBOX &rect)
Definition: bbgrid.h:552
void RemoveBBox(BBC *bbox)
Definition: bbgrid.h:533
BBC_CLIST * grid_
Definition: bbgrid.h:221
BBGrid(int gridsize, const ICOORD &bleft, const ICOORD &tright)
Definition: bbgrid.h:431
size_t operator()(const T *ptr) const
Definition: bbgrid.h:228
void Notify(const SVEvent *sv_event) override
Definition: bbgrid.h:577
int x
Definition: scrollview.h:67
SVEventType type
Definition: scrollview.h:64
int y
Definition: scrollview.h:68
static void Update()
Definition: scrollview.cpp:709
void AddEventHandler(SVEventHandler *listener)
Add an Event Listener to this ScrollView Window.
Definition: scrollview.cpp:414
void Pen(Color color)
Definition: scrollview.cpp:719
void Rectangle(int x1, int y1, int x2, int y2)
Definition: scrollview.cpp:600
void Brush(Color color)
Definition: scrollview.cpp:725