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