tesseract  5.0.0-alpha-619-ge9db
bbgrid.h
Go to the documentation of this file.
1 // 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 
32 class BLOCK;
33 
34 namespace 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.
42 Pix* 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.
45 Pix* TraceBlockOnReducedPix(BLOCK* block, int gridsize,
46  ICOORD bleft, int* left, int* bottom);
47 
48 template<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.
52 class 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.
97 class 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.
158 template<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:
162  BBGrid();
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.
212  void DisplayBoxes(ScrollView* window);
213 
214  // ASSERT_HOST that every cell contains no more than one copy of each entry.
215  void AssertNoDuplicates();
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.
227 template<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.
235 template<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().
370 template<class BBC>
371 int 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.
388 template<class BBC>
389 int 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().
406 template<class BBC>
407 int 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.
426 template<class BBC, class BBC_CLIST, class BBC_C_IT>
428 }
429 
430 template<class BBC, class BBC_CLIST, class BBC_C_IT>
432  int gridsize, const ICOORD& bleft, const ICOORD& tright)
433  : grid_(nullptr) {
434  Init(gridsize, bleft, tright);
435 }
436 
437 template<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.
444 template<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.
454 template<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.
463 template<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.
485 template<class BBC, class BBC_CLIST, class BBC_C_IT>
486 void 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.
513 template<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.
532 template<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.
551 template<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.
560 template<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 
573 template<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.
588 template<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.
612 template<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.
637 template<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.
654 template<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.
664 template<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.
674 template<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.
697 template<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.
712 template<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.
745 template<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.
760 template<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.
787 template<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.
801 template<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.
829 template<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.
841 template<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.
865 template<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 
891 template<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.
920 template<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.
932 template<class BBC, class BBC_CLIST, class BBC_C_IT>
933 BBC* 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.
941 template<class BBC, class BBC_CLIST, class BBC_C_IT>
942 BBC* 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.
950 template<class BBC, class BBC_CLIST, class BBC_C_IT>
951 void 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_
ScrollView::GREY
Definition: scrollview.h:133
tesseract::GridBase::~GridBase
virtual ~GridBase()
ScrollView
Definition: scrollview.h:97
ScrollView::Brush
void Brush(Color color)
Definition: scrollview.cpp:723
tesseract::GridSearch::StartRectSearch
void StartRectSearch(const TBOX &rect)
Definition: bbgrid.h:830
tesseract::BBGrid::AssertNoDuplicates
void AssertNoDuplicates()
Definition: bbgrid.h:638
tesseract::GridSearch::StartSideSearch
void StartSideSearch(int x, int ymin, int ymax)
Definition: bbgrid.h:746
tesseract::GridSearch::RepositionIterator
void RepositionIterator()
Definition: bbgrid.h:892
SVET_CLICK
Definition: scrollview.h:47
tesseract::BBGrid::InsertBBox
void InsertBBox(bool h_spread, bool v_spread, BBC *bbox)
Definition: bbgrid.h:486
tesseract::GridBase::gridheight_
int gridheight_
Definition: bbgrid.h:88
tesseract::BBGrid::CountCellElements
IntGrid * CountCellElements()
Definition: bbgrid.h:561
tesseract::BBGrid::MakeWindow
ScrollView * MakeWindow(int x, int y, const char *window_name)
Definition: bbgrid.h:589
tesseract::TabEventHandler::TabEventHandler
TabEventHandler(G *grid)
Definition: bbgrid.h:575
tesseract::GridSearch::StartVerticalSearch
void StartVerticalSearch(int xmin, int xmax, int y)
Definition: bbgrid.h:788
ASSERT_HOST
#define ASSERT_HOST(x)
Definition: errcode.h:87
tesseract::GridSearch::ReturnedSeedElement
bool ReturnedSeedElement() const
Definition: bbgrid.h:264
tesseract::IntGrid
Definition: bbgrid.h:97
tesseract::GridSearch::NextRectSearch
BBC * NextRectSearch()
Definition: bbgrid.h:842
SVEventHandler
Definition: scrollview.h:81
tesseract::GridBase::tright_
ICOORD tright_
Definition: bbgrid.h:91
ICOORD
integer coordinate
Definition: points.h:30
tesseract::GridBase::gridwidth
int gridwidth() const
Definition: bbgrid.h:66
tesseract::BBGrid::RemoveBBox
void RemoveBBox(BBC *bbox)
Definition: bbgrid.h:533
tesseract::GridSearch::StartFullSearch
void StartFullSearch()
Definition: bbgrid.h:665
tesseract::IntGrid::NeighbourhoodSum
IntGrid * NeighbourhoodSum() const
Definition: bbgrid.cpp:132
tesseract::SortRightToLeft
int SortRightToLeft(const void *void1, const void *void2)
Definition: bbgrid.h:389
tesseract::IntGrid::Clear
void Clear()
Definition: bbgrid.cpp:87
TBOX::top
int16_t top() const
Definition: rect.h:57
tesseract::BBGrid::Clear
void Clear()
Definition: bbgrid.h:455
tesseract::GridSearch::GridSearch
GridSearch(BBGrid< BBC, BBC_CLIST, BBC_C_IT > *grid)
Definition: bbgrid.h:237
tesseract::SortByBoxBottom
int SortByBoxBottom(const void *void1, const void *void2)
Definition: bbgrid.h:407
ScrollView::NONE
Definition: scrollview.h:101
tesseract::TabEventHandler
Definition: bbgrid.h:573
ScrollView::Pen
void Pen(Color color)
Definition: scrollview.cpp:717
tesseract::IntGrid::RectMostlyOverThreshold
bool RectMostlyOverThreshold(const TBOX &rect, int threshold) const
Definition: bbgrid.cpp:154
tesseract::GridBase::GridBase
GridBase()=default
tesseract::GridSearch::StartRadSearch
void StartRadSearch(int x, int y, int max_radius)
Definition: bbgrid.h:698
rect.h
ICOORD::x
int16_t x() const
access function
Definition: points.h:51
FCOORD
Definition: points.h:187
tesseract::GridBase::Init
void Init(int gridsize, const ICOORD &bleft, const ICOORD &tright)
Definition: bbgrid.cpp:40
ScrollView::BLUE
Definition: scrollview.h:108
C_OUTLINE
Definition: coutln.h:71
tesseract::GridBase::tright
const ICOORD & tright() const
Definition: bbgrid.h:75
SVEvent::y
int y
Definition: scrollview.h:67
tesseract::BBGrid::~BBGrid
~BBGrid() override
Definition: bbgrid.h:438
tesseract::GridSearch::NextRadSearch
BBC * NextRadSearch()
Definition: bbgrid.h:713
tesseract::GridSearch::GridY
int GridY() const
Definition: bbgrid.h:245
BLOCK
Definition: ocrblock.h:28
tesseract::GridSearch::NextSideSearch
BBC * NextSideSearch(bool right_to_left)
Definition: bbgrid.h:761
tesseract::GridBase
Definition: bbgrid.h:52
tesseract::GridSearch::GridX
int GridX() const
Definition: bbgrid.h:242
tesseract::TraceBlockOnReducedPix
Pix * TraceBlockOnReducedPix(BLOCK *block, int gridsize, ICOORD bleft, int *left, int *bottom)
Definition: bbgrid.cpp:254
tesseract::GridBase::gridwidth_
int gridwidth_
Definition: bbgrid.h:87
tesseract::TraceOutlineOnReducedPix
Pix * TraceOutlineOnReducedPix(C_OUTLINE *outline, int gridsize, ICOORD bleft, int *left, int *bottom)
Definition: bbgrid.cpp:228
tesseract::TabEventHandler::Notify
void Notify(const SVEvent *sv_event) override
Definition: bbgrid.h:577
TBOX::bottom
int16_t bottom() const
Definition: rect.h:64
tesseract::BBGrid
Definition: bbgrid.h:158
tesseract::SortByBoxLeft
int SortByBoxLeft(const void *void1, const void *void2)
Definition: bbgrid.h:371
coutln.h
tesseract::GridBase::bleft_
ICOORD bleft_
Definition: bbgrid.h:90
tesseract::PtrHash::operator()
size_t operator()(const T *ptr) const
Definition: bbgrid.h:228
tesseract::GridSearch
Definition: bbgrid.h:48
tesseract
Definition: baseapi.h:65
SVEvent::type
SVEventType type
Definition: scrollview.h:63
tesseract::IntGrid::GridCellValue
int GridCellValue(int grid_x, int grid_y) const
Definition: bbgrid.h:120
tesseract::GridSearch::NextVerticalSearch
BBC * NextVerticalSearch(bool top_to_bottom)
Definition: bbgrid.h:802
tesseract::IntGrid::Init
void Init(int gridsize, const ICOORD &bleft, const ICOORD &tright)
Definition: bbgrid.cpp:79
tesseract::BBGrid::grid_
BBC_CLIST * grid_
Definition: bbgrid.h:221
tesseract::IntGrid::IntGrid
IntGrid()
Definition: bbgrid.cpp:64
tesseract::GridBase::gridsize
int gridsize() const
Definition: bbgrid.h:63
tesseract::BBGrid::InsertPixPtBBox
void InsertPixPtBBox(int left, int bottom, Pix *pix, BBC *bbox)
Definition: bbgrid.h:514
tesseract::IntGrid::~IntGrid
~IntGrid() override
Definition: bbgrid.cpp:73
tesseract::BBGrid::ClearGridData
void ClearGridData(void(*free_method)(BBC *))
Definition: bbgrid.h:464
tesseract::BBGrid::DisplayBoxes
void DisplayBoxes(ScrollView *window)
Definition: bbgrid.h:613
tesseract::GridBase::gridsize_
int gridsize_
Definition: bbgrid.h:86
tesseract::BBGrid::Init
void Init(int gridsize, const ICOORD &bleft, const ICOORD &tright)
Definition: bbgrid.h:445
tesseract::GridBase::gridbuckets_
int gridbuckets_
Definition: bbgrid.h:89
tesseract::GridBase::ClipGridCoords
void ClipGridCoords(int *x, int *y) const
Definition: bbgrid.cpp:59
TBOX::left
int16_t left() const
Definition: rect.h:71
SVEvent
Definition: scrollview.h:60
tesseract::BBGrid::HandleClick
virtual void HandleClick(int x, int y)
Definition: bbgrid.h:655
TBOX::right
int16_t right() const
Definition: rect.h:78
tprintf
DLLSYM void tprintf(const char *format,...)
Definition: tprintf.cpp:34
ScrollView::AddEventHandler
void AddEventHandler(SVEventHandler *listener)
Add an Event Listener to this ScrollView Window.
Definition: scrollview.cpp:415
SVEvent::x
int x
Definition: scrollview.h:66
tesseract::GridSearch::SetUniqueMode
void SetUniqueMode(bool mode)
Definition: bbgrid.h:253
ScrollView::Update
static void Update()
Definition: scrollview.cpp:708
C_OUTLINE::chain_step
static ICOORD chain_step(int chaindir)
Definition: coutln.cpp:1049
tesseract::PtrHash
Definition: bbgrid.h:227
tesseract::IntGrid::SetGridCell
void SetGridCell(int grid_x, int grid_y, int value)
Definition: bbgrid.h:124
tesseract::IntGrid::Rotate
void Rotate(const FCOORD &rotation)
Definition: bbgrid.cpp:99
tesseract::BBGrid::BBGrid
BBGrid()
Definition: bbgrid.h:427
ScrollView::Color
Color
Definition: scrollview.h:100
ScrollView::Rectangle
void Rectangle(int x1, int y1, int x2, int y2)
Definition: scrollview.cpp:599
tesseract::BBGrid::RectangleEmpty
bool RectangleEmpty(const TBOX &rect)
Definition: bbgrid.h:552
scrollview.h
tesseract::GridBase::gridheight
int gridheight() const
Definition: bbgrid.h:69
tesseract::GridSearch::RemoveBBox
void RemoveBBox()
Definition: bbgrid.h:866
tesseract::IntGrid::AnyZeroInRect
bool AnyZeroInRect(const TBOX &rect) const
Definition: bbgrid.cpp:174
search
LIST search(LIST list, void *key, int_compare is_equal)
Definition: oldlist.cpp:202
tesseract::GridBase::bleft
const ICOORD & bleft() const
Definition: bbgrid.h:72
tesseract::GridBase::GridCoords
void GridCoords(int x, int y, int *grid_x, int *grid_y) const
Definition: bbgrid.cpp:52
clst.h
ICOORD::y
int16_t y() const
access_function
Definition: points.h:55
tesseract::GridSearch::NextFullSearch
BBC * NextFullSearch()
Definition: bbgrid.h:675
tesseract::IntGrid::ThresholdToPix
Pix * ThresholdToPix(int threshold) const
Definition: bbgrid.cpp:190
TBOX
Definition: rect.h:33