tesseract  5.0.0
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 Image TraceOutlineOnReducedPix(C_OUTLINE *outline, int gridsize, ICOORD bleft, int *left,
43  int *bottom);
44 // As TraceOutlineOnReducedPix above, but on a BLOCK instead of a C_OUTLINE.
45 Image TraceBlockOnReducedPix(BLOCK *block, int gridsize, ICOORD bleft, int *left, int *bottom);
46 
47 template <class BBC, class BBC_CLIST, class BBC_C_IT>
48 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.
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  Image 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>
159 class BBGrid : public GridBase {
160  friend class GridSearch<BBC, BBC_CLIST, BBC_C_IT>;
161 
162 public:
164  BBGrid(int gridsize, const ICOORD &bleft, const ICOORD &tright);
165  ~BBGrid() override;
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, Image 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.
206 
207 #ifndef GRAPHICS_DISABLED
208 
209  // Make a window of an appropriate size to display things in the grid.
210  ScrollView *MakeWindow(int x, int y, const char *window_name);
211 
212  // Display the bounding boxes of the BLOBNBOXes in this grid.
213  // Use of this function requires an additional member of the BBC class:
214  // ScrollView::Color BBC::BoxColor() const.
215  void DisplayBoxes(ScrollView *window);
216 
217 #endif // !GRAPHICS_DISABLED
218 
219  // ASSERT_HOST that every cell contains no more than one copy of each entry.
221 
222  // Handle a click event in a display window.
223  virtual void HandleClick(int x, int y);
224 
225 protected:
226  BBC_CLIST *grid_; // 2-d array of CLISTS of BBC elements.
227 
228 private:
229 };
230 
231 // The GridSearch class enables neighbourhood searching on a BBGrid.
232 template <class BBC, class BBC_CLIST, class BBC_C_IT>
233 class GridSearch {
234 public:
236 
237  // Get the grid x, y coords of the most recently returned BBC.
238  int GridX() const {
239  return x_;
240  }
241  int GridY() const {
242  return y_;
243  }
244 
245  // Sets the search mode to return a box only once.
246  // Efficiency warning: Implementation currently uses a squared-order
247  // search in the number of returned elements. Use only where a small
248  // number of elements are spread over a wide area, eg ColPartitions.
249  void SetUniqueMode(bool mode) {
250  unique_mode_ = mode;
251  }
252  // TODO(rays) Replace calls to ReturnedSeedElement with SetUniqueMode.
253  // It only works if the search includes the bottom-left corner.
254  // Apart from full search, all other searches return a box several
255  // times if the box is inserted with h_spread or v_spread.
256  // This method will return true for only one occurrence of each box
257  // that was inserted with both h_spread and v_spread as true.
258  // It will usually return false for boxes that were not inserted with
259  // both h_spread=true and v_spread=true
260  bool ReturnedSeedElement() const {
261  TBOX box = previous_return_->bounding_box();
262  int x_center = (box.left() + box.right()) / 2;
263  int y_center = (box.top() + box.bottom()) / 2;
264  int grid_x, grid_y;
265  grid_->GridCoords(x_center, y_center, &grid_x, &grid_y);
266  return (x_ == grid_x) && (y_ == grid_y);
267  }
268 
269  // Various searching iterations... Note that these iterations
270  // all share data members, so you can't run more than one iteration
271  // in parallel in a single GridSearch instance, but multiple instances
272  // can search the same BBGrid in parallel.
273  // Note that all the searches can return blobs that may not exactly
274  // match the search conditions, since they return everything in the
275  // covered grid cells. It is up to the caller to check for
276  // appropriateness.
277  // TODO(rays) NextRectSearch only returns valid elements. Make the other
278  // searches test before return also and remove the tests from code
279  // that uses GridSearch.
280 
281  // Start a new full search. Will iterate all stored blobs, from the top.
282  // If the blobs have been inserted using InsertBBox, (not InsertPixPtBBox)
283  // then the full search guarantees to return each blob in the grid once.
284  // Other searches may return a blob more than once if they have been
285  // inserted using h_spread or v_spread.
286  void StartFullSearch();
287  // Return the next bbox in the search or nullptr if done.
288  BBC *NextFullSearch();
289 
290  // Start a new radius search. Will search in a spiral up to a
291  // given maximum radius in grid cells from the given center in pixels.
292  void StartRadSearch(int x, int y, int max_radius);
293  // Return the next bbox in the radius search or nullptr if the
294  // maximum radius has been reached.
295  BBC *NextRadSearch();
296 
297  // Start a new left or right-looking search. Will search to the side
298  // for a box that vertically overlaps the given vertical line segment.
299  // CAVEAT: This search returns all blobs from the cells to the side
300  // of the start, and somewhat below, since there is no guarantee
301  // that there may not be a taller object in a lower cell. The
302  // blobs returned will include all those that vertically overlap and
303  // are no more than twice as high, but may also include some that do
304  // not overlap and some that are more than twice as high.
305  void StartSideSearch(int x, int ymin, int ymax);
306  // Return the next bbox in the side search or nullptr if the
307  // edge has been reached. Searches left to right or right to left
308  // according to the flag.
309  BBC *NextSideSearch(bool right_to_left);
310 
311  // Start a vertical-looking search. Will search up or down
312  // for a box that horizontally overlaps the given line segment.
313  void StartVerticalSearch(int xmin, int xmax, int y);
314  // Return the next bbox in the vertical search or nullptr if the
315  // edge has been reached. Searches top to bottom or bottom to top
316  // according to the flag.
317  BBC *NextVerticalSearch(bool top_to_bottom);
318 
319  // Start a rectangular search. Will search for a box that overlaps the
320  // given rectangle.
321  void StartRectSearch(const TBOX &rect);
322  // Return the next bbox in the rectangular search or nullptr if complete.
323  BBC *NextRectSearch();
324 
325  // Remove the last returned BBC. Will not invalidate this. May invalidate
326  // any other concurrent GridSearch on the same grid. If any others are
327  // in use, call RepositionIterator on those, to continue without harm.
328  void RemoveBBox();
329  void RepositionIterator();
330 
331 private:
332  // Factored out helper to start a search.
333  void CommonStart(int x, int y);
334  // Factored out helper to complete a next search.
335  BBC *CommonNext();
336  // Factored out final return when search is exhausted.
337  BBC *CommonEnd();
338  // Factored out function to set the iterator to the current x_, y_
339  // grid coords and mark the cycle pt.
340  void SetIterator();
341 
342 private:
343  // The grid we are searching.
344  BBGrid<BBC, BBC_CLIST, BBC_C_IT> *grid_ = nullptr;
345  // For executing a search. The different search algorithms use these in
346  // different ways, but most use x_origin_ and y_origin_ as the start position.
347  int x_origin_ = 0;
348  int y_origin_ = 0;
349  int max_radius_ = 0;
350  int radius_ = 0;
351  int rad_index_ = 0;
352  int rad_dir_ = 0;
353  TBOX rect_;
354  int x_ = 0; // The current location in grid coords, of the current search.
355  int y_ = 0;
356  bool unique_mode_ = false;
357  BBC *previous_return_ = nullptr; // Previous return from Next*.
358  BBC *next_return_ = nullptr; // Current value of it_.data() used for repositioning.
359  // An iterator over the list at (x_, y_) in the grid_.
360  BBC_C_IT it_;
361  // Set of unique returned elements used when unique_mode_ is true.
362  std::unordered_set<BBC *> returns_;
363 };
364 
365 // Sort function to sort a BBC by bounding_box().left().
366 template <class BBC>
367 int SortByBoxLeft(const void *void1, const void *void2) {
368  // The void*s are actually doubly indirected, so get rid of one level.
369  const BBC *p1 = *static_cast<const BBC *const *>(void1);
370  const BBC *p2 = *static_cast<const BBC *const *>(void2);
371  int result = p1->bounding_box().left() - p2->bounding_box().left();
372  if (result != 0) {
373  return result;
374  }
375  result = p1->bounding_box().right() - p2->bounding_box().right();
376  if (result != 0) {
377  return result;
378  }
379  result = p1->bounding_box().bottom() - p2->bounding_box().bottom();
380  if (result != 0) {
381  return result;
382  }
383  return p1->bounding_box().top() - p2->bounding_box().top();
384 }
385 
386 template <class BBC>
387 bool StdSortByBoxLeft(const void *void1, const void *void2) {
388  // The void*s are actually doubly indirected, so get rid of one level.
389  const BBC *p1 = *static_cast<const BBC *const *>(void1);
390  const BBC *p2 = *static_cast<const BBC *const *>(void2);
391  int result = p1->bounding_box().left() - p2->bounding_box().left();
392  if (result != 0) {
393  return result < 0;
394  }
395  result = p1->bounding_box().right() - p2->bounding_box().right();
396  if (result != 0) {
397  return result < 0;
398  }
399  result = p1->bounding_box().bottom() - p2->bounding_box().bottom();
400  if (result != 0) {
401  return result < 0;
402  }
403  return p1->bounding_box().top() < p2->bounding_box().top();
404 }
405 
406 // Sort function to sort a BBC by bounding_box().right() in right-to-left order.
407 template <class BBC>
408 int SortRightToLeft(const void *void1, const void *void2) {
409  // The void*s are actually doubly indirected, so get rid of one level.
410  const BBC *p1 = *static_cast<const BBC *const *>(void1);
411  const BBC *p2 = *static_cast<const BBC *const *>(void2);
412  int result = p2->bounding_box().right() - p1->bounding_box().right();
413  if (result != 0) {
414  return result;
415  }
416  result = p2->bounding_box().left() - p1->bounding_box().left();
417  if (result != 0) {
418  return result;
419  }
420  result = p1->bounding_box().bottom() - p2->bounding_box().bottom();
421  if (result != 0) {
422  return result;
423  }
424  return p1->bounding_box().top() - p2->bounding_box().top();
425 }
426 
427 template <class BBC>
428 bool StdSortRightToLeft(const void *void1, const void *void2) {
429  // The void*s are actually doubly indirected, so get rid of one level.
430  const BBC *p1 = *static_cast<const BBC *const *>(void1);
431  const BBC *p2 = *static_cast<const BBC *const *>(void2);
432  int result = p2->bounding_box().right() - p1->bounding_box().right();
433  if (result != 0) {
434  return result < 0;
435  }
436  result = p2->bounding_box().left() - p1->bounding_box().left();
437  if (result != 0) {
438  return result < 0;
439  }
440  result = p1->bounding_box().bottom() - p2->bounding_box().bottom();
441  if (result != 0) {
442  return result < 0;
443  }
444  return p1->bounding_box().top() < p2->bounding_box().top();
445 }
446 
447 // Sort function to sort a BBC by bounding_box().bottom().
448 template <class BBC>
449 int SortByBoxBottom(const void *void1, const void *void2) {
450  // The void*s are actually doubly indirected, so get rid of one level.
451  const BBC *p1 = *static_cast<const BBC *const *>(void1);
452  const BBC *p2 = *static_cast<const BBC *const *>(void2);
453  int result = p1->bounding_box().bottom() - p2->bounding_box().bottom();
454  if (result != 0) {
455  return result;
456  }
457  result = p1->bounding_box().top() - p2->bounding_box().top();
458  if (result != 0) {
459  return result;
460  }
461  result = p1->bounding_box().left() - p2->bounding_box().left();
462  if (result != 0) {
463  return result;
464  }
465  return p1->bounding_box().right() - p2->bounding_box().right();
466 }
467 
469 // BBGrid IMPLEMENTATION.
471 template <class BBC, class BBC_CLIST, class BBC_C_IT>
473 
474 template <class BBC, class BBC_CLIST, class BBC_C_IT>
475 BBGrid<BBC, BBC_CLIST, BBC_C_IT>::BBGrid(int gridsize, const ICOORD &bleft, const ICOORD &tright)
476  : grid_(nullptr) {
478 }
479 
480 template <class BBC, class BBC_CLIST, class BBC_C_IT>
482  delete[] grid_;
483 }
484 
485 // (Re)Initialize the grid. The gridsize is the size in pixels of each cell,
486 // and bleft, tright are the bounding box of everything to go in it.
487 template <class BBC, class BBC_CLIST, class BBC_C_IT>
488 void BBGrid<BBC, BBC_CLIST, BBC_C_IT>::Init(int gridsize, const ICOORD &bleft,
489  const ICOORD &tright) {
490  GridBase::Init(gridsize, bleft, tright);
491  delete[] grid_;
492  grid_ = new BBC_CLIST[gridbuckets_];
493 }
494 
495 // Clear all lists, but leave the array of lists present.
496 template <class BBC, class BBC_CLIST, class BBC_C_IT>
498  for (int i = 0; i < gridbuckets_; ++i) {
499  grid_[i].shallow_clear();
500  }
501 }
502 
503 // Deallocate the data in the lists but otherwise leave the lists and the grid
504 // intact.
505 template <class BBC, class BBC_CLIST, class BBC_C_IT>
506 void BBGrid<BBC, BBC_CLIST, BBC_C_IT>::ClearGridData(void (*free_method)(BBC *)) {
507  if (grid_ == nullptr) {
508  return;
509  }
511  search.StartFullSearch();
512  BBC *bb;
513  BBC_CLIST bb_list;
514  BBC_C_IT it(&bb_list);
515  while ((bb = search.NextFullSearch()) != nullptr) {
516  it.add_after_then_move(bb);
517  }
518  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
519  free_method(it.data());
520  }
521 }
522 
523 // Insert a bbox into the appropriate place in the grid.
524 // If h_spread, then all cells covered horizontally by the box are
525 // used, otherwise, just the bottom-left. Similarly for v_spread.
526 // WARNING: InsertBBox may invalidate an active GridSearch. Call
527 // RepositionIterator() on any GridSearches that are active on this grid.
528 template <class BBC, class BBC_CLIST, class BBC_C_IT>
529 void BBGrid<BBC, BBC_CLIST, BBC_C_IT>::InsertBBox(bool h_spread, bool v_spread, BBC *bbox) {
530  TBOX box = bbox->bounding_box();
531  int start_x, start_y, end_x, end_y;
532  GridCoords(box.left(), box.bottom(), &start_x, &start_y);
533  GridCoords(box.right(), box.top(), &end_x, &end_y);
534  if (!h_spread) {
535  end_x = start_x;
536  }
537  if (!v_spread) {
538  end_y = start_y;
539  }
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  grid_[grid_index + x].add_sorted(SortByBoxLeft<BBC>, true, bbox);
544  }
545  }
546 }
547 
548 // Using a pix from TraceOutlineOnReducedPix or TraceBlockOnReducedPix, in
549 // which each pixel corresponds to a grid cell, insert a bbox into every
550 // place in the grid where the corresponding pixel is 1. The Pix is handled
551 // upside-down to match the Tesseract coordinate system. (As created by
552 // TraceOutlineOnReducedPix or TraceBlockOnReducedPix.)
553 // (0, 0) in the pix corresponds to (left, bottom) in the
554 // grid (in grid coords), and the pix works up the grid from there.
555 // WARNING: InsertPixPtBBox may invalidate an active GridSearch. Call
556 // RepositionIterator() on any GridSearches that are active on this grid.
557 template <class BBC, class BBC_CLIST, class BBC_C_IT>
558 void BBGrid<BBC, BBC_CLIST, BBC_C_IT>::InsertPixPtBBox(int left, int bottom, Image pix, BBC *bbox) {
559  int width = pixGetWidth(pix);
560  int height = pixGetHeight(pix);
561  for (int y = 0; y < height; ++y) {
562  l_uint32 *data = pixGetData(pix) + y * pixGetWpl(pix);
563  for (int x = 0; x < width; ++x) {
564  if (GET_DATA_BIT(data, x)) {
565  grid_[(bottom + y) * gridwidth_ + x + left].add_sorted(SortByBoxLeft<BBC>, true, bbox);
566  }
567  }
568  }
569 }
570 
571 // Remove the bbox from the grid.
572 // WARNING: Any GridSearch operating on this grid could be invalidated!
573 // If a GridSearch is operating, call GridSearch::RemoveBBox() instead.
574 template <class BBC, class BBC_CLIST, class BBC_C_IT>
576  TBOX box = bbox->bounding_box();
577  int start_x, start_y, end_x, end_y;
578  GridCoords(box.left(), box.bottom(), &start_x, &start_y);
579  GridCoords(box.right(), box.top(), &end_x, &end_y);
580  int grid_index = start_y * gridwidth_;
581  for (int y = start_y; y <= end_y; ++y, grid_index += gridwidth_) {
582  for (int x = start_x; x <= end_x; ++x) {
583  BBC_C_IT it(&grid_[grid_index + x]);
584  for (it.mark_cycle_pt(); !it.cycled_list(); it.forward()) {
585  if (it.data() == bbox) {
586  it.extract();
587  }
588  }
589  }
590  }
591 }
592 
593 // Returns true if the given rectangle has no overlapping elements.
594 template <class BBC, class BBC_CLIST, class BBC_C_IT>
597  rsearch.StartRectSearch(rect);
598  return rsearch.NextRectSearch() == nullptr;
599 }
600 
601 // Returns an IntGrid showing the number of elements in each cell.
602 // Returned IntGrid must be deleted after use.
603 template <class BBC, class BBC_CLIST, class BBC_C_IT>
605  auto *intgrid = new IntGrid(gridsize(), bleft(), tright());
606  for (int y = 0; y < gridheight(); ++y) {
607  for (int x = 0; x < gridwidth(); ++x) {
608  int cell_count = grid_[y * gridwidth() + x].length();
609  intgrid->SetGridCell(x, y, cell_count);
610  }
611  }
612  return intgrid;
613 }
614 
615 #ifndef GRAPHICS_DISABLED
616 template <class G>
618 public:
619  explicit TabEventHandler(G *grid) : grid_(grid) {}
620  void Notify(const SVEvent *sv_event) override {
621  if (sv_event->type == SVET_CLICK) {
622  grid_->HandleClick(sv_event->x, sv_event->y);
623  }
624  }
625 
626 private:
627  G *grid_;
628 };
629 
630 // Make a window of an appropriate size to display things in the grid.
631 // Position the window at the given x,y.
632 template <class BBC, class BBC_CLIST, class BBC_C_IT>
633 ScrollView *BBGrid<BBC, BBC_CLIST, BBC_C_IT>::MakeWindow(int x, int y, const char *window_name) {
634  auto tab_win =
635  new ScrollView(window_name, x, y, tright_.x() - bleft_.x(), tright_.y() - bleft_.y(),
636  tright_.x() - bleft_.x(), tright_.y() - bleft_.y(), true);
637  auto *handler = new TabEventHandler<BBGrid<BBC, BBC_CLIST, BBC_C_IT>>(this);
638  tab_win->AddEventHandler(handler);
639  tab_win->Pen(ScrollView::GREY);
640  tab_win->Rectangle(0, 0, tright_.x() - bleft_.x(), tright_.y() - bleft_.y());
641  return tab_win;
642 }
643 
644 // Create a window at (x,y) and display the bounding boxes of the
645 // BLOBNBOXes in this grid.
646 // Use of this function requires an additional member of the BBC class:
647 // ScrollView::Color BBC::BoxColor() const.
648 template <class BBC, class BBC_CLIST, class BBC_C_IT>
650  tab_win->Pen(ScrollView::BLUE);
651  tab_win->Brush(ScrollView::NONE);
652 
653  // For every bbox in the grid, display it.
655  gsearch.StartFullSearch();
656  BBC *bbox;
657  while ((bbox = gsearch.NextFullSearch()) != nullptr) {
658  const TBOX &box = bbox->bounding_box();
659  int left_x = box.left();
660  int right_x = box.right();
661  int top_y = box.top();
662  int bottom_y = box.bottom();
663  ScrollView::Color box_color = bbox->BoxColor();
664  tab_win->Pen(box_color);
665  tab_win->Rectangle(left_x, bottom_y, right_x, top_y);
666  }
667  tab_win->Update();
668 }
669 
670 #endif // !GRAPHICS_DISABLED
671 
672 // ASSERT_HOST that every cell contains no more than one copy of each entry.
673 template <class BBC, class BBC_CLIST, class BBC_C_IT>
675  // Process all grid cells.
676  for (int i = gridwidth_ * gridheight_ - 1; i >= 0; --i) {
677  // Iterate over all elements excent the last.
678  for (BBC_C_IT it(&grid_[i]); !it.at_last(); it.forward()) {
679  BBC *ptr = it.data();
680  BBC_C_IT it2(it);
681  // None of the rest of the elements in the list should equal ptr.
682  for (it2.forward(); !it2.at_first(); it2.forward()) {
683  ASSERT_HOST(it2.data() != ptr);
684  }
685  }
686  }
687 }
688 
689 // Handle a click event in a display window.
690 template <class BBC, class BBC_CLIST, class BBC_C_IT>
692  tprintf("Click at (%d, %d)\n", x, y);
693 }
694 
696 // GridSearch IMPLEMENTATION.
698 
699 // Start a new full search. Will iterate all stored blobs.
700 template <class BBC, class BBC_CLIST, class BBC_C_IT>
702  // Full search uses x_ and y_ as the current grid
703  // cell being searched.
704  CommonStart(grid_->bleft_.x(), grid_->tright_.y());
705 }
706 
707 // Return the next bbox in the search or nullptr if done.
708 // The other searches will return a box that overlaps the grid cell
709 // thereby duplicating boxes, but NextFullSearch only returns each box once.
710 template <class BBC, class BBC_CLIST, class BBC_C_IT>
712  int x;
713  int y;
714  do {
715  while (it_.cycled_list()) {
716  ++x_;
717  if (x_ >= grid_->gridwidth_) {
718  --y_;
719  if (y_ < 0) {
720  return CommonEnd();
721  }
722  x_ = 0;
723  }
724  SetIterator();
725  }
726  CommonNext();
727  TBOX box = previous_return_->bounding_box();
728  grid_->GridCoords(box.left(), box.bottom(), &x, &y);
729  } while (x != x_ || y != y_);
730  return previous_return_;
731 }
732 
733 // Start a new radius search.
734 template <class BBC, class BBC_CLIST, class BBC_C_IT>
735 void GridSearch<BBC, BBC_CLIST, BBC_C_IT>::StartRadSearch(int x, int y, int max_radius) {
736  // Rad search uses x_origin_ and y_origin_ as the center of the circle.
737  // The radius_ is the radius of the (diamond-shaped) circle and
738  // rad_index/rad_dir_ combine to determine the position around it.
739  max_radius_ = max_radius;
740  radius_ = 0;
741  rad_index_ = 0;
742  rad_dir_ = 3;
743  CommonStart(x, y);
744 }
745 
746 // Return the next bbox in the radius search or nullptr if the
747 // maximum radius has been reached.
748 template <class BBC, class BBC_CLIST, class BBC_C_IT>
750  for (;;) {
751  while (it_.cycled_list()) {
752  ++rad_index_;
753  if (rad_index_ >= radius_) {
754  ++rad_dir_;
755  rad_index_ = 0;
756  if (rad_dir_ >= 4) {
757  ++radius_;
758  if (radius_ > max_radius_) {
759  return CommonEnd();
760  }
761  rad_dir_ = 0;
762  }
763  }
764  ICOORD offset = C_OUTLINE::chain_step(rad_dir_);
765  offset *= radius_ - rad_index_;
766  offset += C_OUTLINE::chain_step(rad_dir_ + 1) * rad_index_;
767  x_ = x_origin_ + offset.x();
768  y_ = y_origin_ + offset.y();
769  if (x_ >= 0 && x_ < grid_->gridwidth_ && y_ >= 0 && y_ < grid_->gridheight_) {
770  SetIterator();
771  }
772  }
773  CommonNext();
774  if (!unique_mode_) {
775  break;
776  }
777  auto inserted = returns_.insert(previous_return_);
778  if (inserted.second) {
779  break;
780  }
781  }
782  return previous_return_;
783 }
784 
785 // Start a new left or right-looking search. Will search to the side
786 // for a box that vertically overlaps the given vertical line segment.
787 template <class BBC, class BBC_CLIST, class BBC_C_IT>
789  // Right search records the x in x_origin_, the ymax in y_origin_
790  // and the size of the vertical strip to search in radius_.
791  // To guarantee finding overlapping objects of up to twice the
792  // given size, double the height.
793  radius_ = ((ymax - ymin) * 2 + grid_->gridsize_ - 1) / grid_->gridsize_;
794  rad_index_ = 0;
795  CommonStart(x, ymax);
796 }
797 
798 // Return the next bbox in the side search or nullptr if the
799 // edge has been reached. Searches left to right or right to left
800 // according to the flag.
801 template <class BBC, class BBC_CLIST, class BBC_C_IT>
803  for (;;) {
804  while (it_.cycled_list()) {
805  ++rad_index_;
806  if (rad_index_ > radius_) {
807  if (right_to_left) {
808  --x_;
809  } else {
810  ++x_;
811  }
812  rad_index_ = 0;
813  if (x_ < 0 || x_ >= grid_->gridwidth_) {
814  return CommonEnd();
815  }
816  }
817  y_ = y_origin_ - rad_index_;
818  if (y_ >= 0 && y_ < grid_->gridheight_) {
819  SetIterator();
820  }
821  }
822  CommonNext();
823  if (!unique_mode_) {
824  break;
825  }
826  auto inserted = returns_.insert(previous_return_);
827  if (inserted.second) {
828  break;
829  }
830  }
831  return previous_return_;
832 }
833 
834 // Start a vertical-looking search. Will search up or down
835 // for a box that horizontally overlaps the given line segment.
836 template <class BBC, class BBC_CLIST, class BBC_C_IT>
838  // Right search records the xmin in x_origin_, the y in y_origin_
839  // and the size of the horizontal strip to search in radius_.
840  radius_ = (xmax - xmin + grid_->gridsize_ - 1) / grid_->gridsize_;
841  rad_index_ = 0;
842  CommonStart(xmin, y);
843 }
844 
845 // Return the next bbox in the vertical search or nullptr if the
846 // edge has been reached. Searches top to bottom or bottom to top
847 // according to the flag.
848 template <class BBC, class BBC_CLIST, class BBC_C_IT>
850  for (;;) {
851  while (it_.cycled_list()) {
852  ++rad_index_;
853  if (rad_index_ > radius_) {
854  if (top_to_bottom) {
855  --y_;
856  } else {
857  ++y_;
858  }
859  rad_index_ = 0;
860  if (y_ < 0 || y_ >= grid_->gridheight_) {
861  return CommonEnd();
862  }
863  }
864  x_ = x_origin_ + rad_index_;
865  if (x_ >= 0 && x_ < grid_->gridwidth_) {
866  SetIterator();
867  }
868  }
869  CommonNext();
870  if (!unique_mode_) {
871  break;
872  }
873  auto inserted = returns_.insert(previous_return_);
874  if (inserted.second) {
875  break;
876  }
877  }
878  return previous_return_;
879 }
880 
881 // Start a rectangular search. Will search for a box that overlaps the
882 // given rectangle.
883 template <class BBC, class BBC_CLIST, class BBC_C_IT>
885  // Rect search records the xmin in x_origin_, the ymin in y_origin_
886  // and the xmax in max_radius_.
887  // The search proceeds left to right, top to bottom.
888  rect_ = rect;
889  CommonStart(rect.left(), rect.top());
890  grid_->GridCoords(rect.right(), rect.bottom(), // - rect.height(),
891  &max_radius_, &y_origin_);
892 }
893 
894 // Return the next bbox in the rectangular search or nullptr if complete.
895 template <class BBC, class BBC_CLIST, class BBC_C_IT>
897  for (;;) {
898  while (it_.cycled_list()) {
899  ++x_;
900  if (x_ > max_radius_) {
901  --y_;
902  x_ = x_origin_;
903  if (y_ < y_origin_) {
904  return CommonEnd();
905  }
906  }
907  SetIterator();
908  }
909  CommonNext();
910  if (!rect_.overlap(previous_return_->bounding_box())) {
911  continue;
912  }
913  if (!unique_mode_) {
914  break;
915  }
916  auto inserted = returns_.insert(previous_return_);
917  if (inserted.second) {
918  break;
919  }
920  }
921  return previous_return_;
922 }
923 
924 // Remove the last returned BBC. Will not invalidate this. May invalidate
925 // any other concurrent GridSearch on the same grid. If any others are
926 // in use, call RepositionIterator on those, to continue without harm.
927 template <class BBC, class BBC_CLIST, class BBC_C_IT>
929  if (previous_return_ != nullptr) {
930  // Remove all instances of previous_return_ from the list, so the iterator
931  // remains valid after removal from the rest of the grid cells.
932  // if previous_return_ is not on the list, then it has been removed already.
933  BBC *prev_data = nullptr;
934  BBC *new_previous_return = nullptr;
935  it_.move_to_first();
936  for (it_.mark_cycle_pt(); !it_.cycled_list();) {
937  if (it_.data() == previous_return_) {
938  new_previous_return = prev_data;
939  it_.extract();
940  it_.forward();
941  next_return_ = it_.cycled_list() ? nullptr : it_.data();
942  } else {
943  prev_data = it_.data();
944  it_.forward();
945  }
946  }
947  grid_->RemoveBBox(previous_return_);
948  previous_return_ = new_previous_return;
949  RepositionIterator();
950  }
951 }
952 
953 template <class BBC, class BBC_CLIST, class BBC_C_IT>
955  // Something was deleted, so we have little choice but to clear the
956  // returns list.
957  returns_.clear();
958  // Reset the iterator back to one past the previous return.
959  // If the previous_return_ is no longer in the list, then
960  // next_return_ serves as a backup.
961  it_.move_to_first();
962  // Special case, the first element was removed and reposition
963  // iterator was called. In this case, the data is fine, but the
964  // cycle point is not. Detect it and return.
965  if (!it_.empty() && it_.data() == next_return_) {
966  it_.mark_cycle_pt();
967  return;
968  }
969  for (it_.mark_cycle_pt(); !it_.cycled_list(); it_.forward()) {
970  if (it_.data() == previous_return_ || it_.data_relative(1) == next_return_) {
971  CommonNext();
972  return;
973  }
974  }
975  // We ran off the end of the list. Move to a new cell next time.
976  previous_return_ = nullptr;
977  next_return_ = nullptr;
978 }
979 
980 // Factored out helper to start a search.
981 template <class BBC, class BBC_CLIST, class BBC_C_IT>
983  grid_->GridCoords(x, y, &x_origin_, &y_origin_);
984  x_ = x_origin_;
985  y_ = y_origin_;
986  SetIterator();
987  previous_return_ = nullptr;
988  next_return_ = it_.empty() ? nullptr : it_.data();
989  returns_.clear();
990 }
991 
992 // Factored out helper to complete a next search.
993 template <class BBC, class BBC_CLIST, class BBC_C_IT>
994 BBC *GridSearch<BBC, BBC_CLIST, BBC_C_IT>::CommonNext() {
995  previous_return_ = it_.data();
996  it_.forward();
997  next_return_ = it_.cycled_list() ? nullptr : it_.data();
998  return previous_return_;
999 }
1000 
1001 // Factored out final return when search is exhausted.
1002 template <class BBC, class BBC_CLIST, class BBC_C_IT>
1003 BBC *GridSearch<BBC, BBC_CLIST, BBC_C_IT>::CommonEnd() {
1004  previous_return_ = nullptr;
1005  next_return_ = nullptr;
1006  return nullptr;
1007 }
1008 
1009 // Factored out function to set the iterator to the current x_, y_
1010 // grid coords and mark the cycle pt.
1011 template <class BBC, class BBC_CLIST, class BBC_C_IT>
1012 void GridSearch<BBC, BBC_CLIST, BBC_C_IT>::SetIterator() {
1013  it_ = &(grid_->grid_[y_ * grid_->gridwidth_ + x_]);
1014  it_.mark_cycle_pt();
1015 }
1016 
1017 } // namespace tesseract.
1018 
1019 #endif // TESSERACT_TEXTORD_BBGRID_H_
#define ASSERT_HOST(x)
Definition: errcode.h:59
void tprintf(const char *format,...)
Definition: tprintf.cpp:41
bool StdSortRightToLeft(const void *void1, const void *void2)
Definition: bbgrid.h:428
@ SVET_CLICK
Definition: scrollview.h:55
int SortByBoxBottom(const void *void1, const void *void2)
Definition: bbgrid.h:449
Image TraceOutlineOnReducedPix(C_OUTLINE *outline, int gridsize, ICOORD bleft, int *left, int *bottom)
Definition: bbgrid.cpp:224
Image TraceBlockOnReducedPix(BLOCK *block, int gridsize, ICOORD bleft, int *left, int *bottom)
Definition: bbgrid.cpp:250
int SortByBoxLeft(const void *void1, const void *void2)
Definition: bbgrid.h:367
bool StdSortByBoxLeft(const void *void1, const void *void2)
Definition: bbgrid.h:387
LIST search(LIST list, void *key, int_compare is_equal)
Definition: oldlist.cpp:211
int SortRightToLeft(const void *void1, const void *void2)
Definition: bbgrid.h:408
static ICOORD chain_step(int chaindir)
Definition: coutln.cpp:1058
integer coordinate
Definition: points.h:36
TDimension y() const
access_function
Definition: points.h:62
TDimension x() const
access function
Definition: points.h:58
TDimension left() const
Definition: rect.h:82
TDimension top() const
Definition: rect.h:68
TDimension right() const
Definition: rect.h:89
TDimension bottom() const
Definition: rect.h:75
bool ReturnedSeedElement() const
Definition: bbgrid.h:260
void StartVerticalSearch(int xmin, int xmax, int y)
Definition: bbgrid.h:837
void StartRadSearch(int x, int y, int max_radius)
Definition: bbgrid.h:735
void SetUniqueMode(bool mode)
Definition: bbgrid.h:249
int GridX() const
Definition: bbgrid.h:238
int GridY() const
Definition: bbgrid.h:241
GridSearch(BBGrid< BBC, BBC_CLIST, BBC_C_IT > *grid)
Definition: bbgrid.h:235
BBC * NextSideSearch(bool right_to_left)
Definition: bbgrid.h:802
BBC * NextRectSearch()
Definition: bbgrid.h:896
void StartSideSearch(int x, int ymin, int ymax)
Definition: bbgrid.h:788
void StartFullSearch()
Definition: bbgrid.h:701
BBC * NextVerticalSearch(bool top_to_bottom)
Definition: bbgrid.h:849
void RepositionIterator()
Definition: bbgrid.h:954
void StartRectSearch(const TBOX &rect)
Definition: bbgrid.h:884
BBC * NextFullSearch()
Definition: bbgrid.h:711
BBC * NextRadSearch()
Definition: bbgrid.h:749
int gridsize() const
Definition: bbgrid.h:63
int gridheight() const
Definition: bbgrid.h:69
void ClipGridCoords(int *x, int *y) const
Definition: bbgrid.cpp:60
void Init(int gridsize, const ICOORD &bleft, const ICOORD &tright)
Definition: bbgrid.cpp:40
int gridwidth() const
Definition: bbgrid.h:66
ICOORD tright_
Definition: bbgrid.h:91
const ICOORD & bleft() const
Definition: bbgrid.h:72
const ICOORD & tright() const
Definition: bbgrid.h:75
IntGrid * NeighbourhoodSum() const
Definition: bbgrid.cpp:131
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
Image ThresholdToPix(int threshold) const
Definition: bbgrid.cpp:190
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:173
void DisplayBoxes(ScrollView *window)
Definition: bbgrid.h:649
void Clear()
Definition: bbgrid.h:497
void AssertNoDuplicates()
Definition: bbgrid.h:674
void Init(int gridsize, const ICOORD &bleft, const ICOORD &tright)
Definition: bbgrid.h:488
~BBGrid() override
Definition: bbgrid.h:481
IntGrid * CountCellElements()
Definition: bbgrid.h:604
void InsertBBox(bool h_spread, bool v_spread, BBC *bbox)
Definition: bbgrid.h:529
virtual void HandleClick(int x, int y)
Definition: bbgrid.h:691
void ClearGridData(void(*free_method)(BBC *))
Definition: bbgrid.h:506
void InsertPixPtBBox(int left, int bottom, Image pix, BBC *bbox)
Definition: bbgrid.h:558
ScrollView * MakeWindow(int x, int y, const char *window_name)
Definition: bbgrid.h:633
bool RectangleEmpty(const TBOX &rect)
Definition: bbgrid.h:595
void RemoveBBox(BBC *bbox)
Definition: bbgrid.h:575
BBC_CLIST * grid_
Definition: bbgrid.h:226
BBGrid(int gridsize, const ICOORD &bleft, const ICOORD &tright)
Definition: bbgrid.h:475
void Notify(const SVEvent *sv_event) override
Definition: bbgrid.h:620
SVEventType type
Definition: scrollview.h:73
void Pen(Color color)
Definition: scrollview.cpp:723
static void Update()
Definition: scrollview.cpp:713
void Brush(Color color)
Definition: scrollview.cpp:729
void Rectangle(int x1, int y1, int x2, int y2)
Definition: scrollview.cpp:589
#define TESS_API
Definition: export.h:34