Tesseract 3.02

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
bbgrid.h
Go to the documentation of this file.
1
2 // File: bbgrid.h
3 // Description: Class to hold BLOBNBOXs in a grid for fast access
4 // to neighbours.
5 // Author: Ray Smith
6 // 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 "clst.h"
25 #include "coutln.h"
26 #include "rect.h"
27 #include "scrollview.h"
28
29 // Some code is dependent upon leptonica. If you don't have it,
30 // you don't get this functionality.
31 #ifdef HAVE_CONFIG_H
32 #include "config_auto.h"
33 #endif
34
35 #include "allheaders.h"
36
37 class BLOCK;
38
39 namespace tesseract {
40
41 // Helper function to return a scaled Pix with one pixel per grid cell,
42 // set (black) where the given outline enters the corresponding grid cell,
43 // and clear where the outline does not touch the grid cell.
44 // Also returns the grid coords of the bottom-left of the Pix, in *left
45 // and *bottom, which corresponds to (0, 0) on the Pix.
46 // Note that the Pix is used upside-down, with (0, 0) being the bottom-left.
47 Pix* TraceOutlineOnReducedPix(C_OUTLINE* outline, int gridsize,
48 ICOORD bleft, int* left, int* bottom);
49 // As TraceOutlineOnReducedPix above, but on a BLOCK instead of a C_OUTLINE.
50 Pix* TraceBlockOnReducedPix(BLOCK* block, int gridsize,
51 ICOORD bleft, int* left, int* bottom);
52
53 template<class BBC, class BBC_CLIST, class BBC_C_IT> class GridSearch;
54
55 // The GridBase class is the base class for BBGrid and IntGrid.
56 // It holds the geometry and scale of the grid.
57 class GridBase {
58 public:
59 GridBase();
60 GridBase(int gridsize, const ICOORD& bleft, const ICOORD& tright);
61 virtual ~GridBase();
62
63 // (Re)Initialize the grid. The gridsize is the size in pixels of each cell,
64 // and bleft, tright are the bounding box of everything to go in it.
65 void Init(int gridsize, const ICOORD& bleft, const ICOORD& tright);
66
67 // Simple accessors.
68 int gridsize() const {
69 return gridsize_;
70 }
71 int gridwidth() const {
72 return gridwidth_;
73 }
74 int gridheight() const {
75 return gridheight_;
76 }
77 const ICOORD& bleft() const {
78 return bleft_;
79 }
80 const ICOORD& tright() const {
81 return tright_;
82 }
83 // Compute the given grid coordinates from image coords.
84 void GridCoords(int x, int y, int* grid_x, int* grid_y) const;
85
86 // Clip the given grid coordinates to fit within the grid.
87 void ClipGridCoords(int* x, int* y) const;
88
89 protected:
90 // TODO(rays) Make these private and migrate to the accessors in subclasses.
91 int gridsize_; // Pixel size of each grid cell.
92 int gridwidth_; // Size of the grid in cells.
93 int gridheight_;
94 int gridbuckets_; // Total cells in grid.
95 ICOORD bleft_; // Pixel coords of bottom-left of grid.
96 ICOORD tright_; // Pixel coords of top-right of grid.
97
98 private:
99 };
100
101 // The IntGrid maintains a single int for each cell in a grid.
102 class IntGrid : public GridBase {
103 public:
104 IntGrid();
105 IntGrid(int gridsize, const ICOORD& bleft, const ICOORD& tright);
106 virtual ~IntGrid();
107
108 // (Re)Initialize the grid. The gridsize is the size in pixels of each cell,
109 // and bleft, tright are the bounding box of everything to go in it.
110 void Init(int gridsize, const ICOORD& bleft, const ICOORD& tright);
111
112 // Clear all the ints in the grid to zero.
113 void Clear();
114
115 // Rotate the grid by rotation, keeping cell contents.
116 // rotation must be a multiple of 90 degrees.
117 // NOTE: due to partial cells, cell coverage in the rotated grid will be
118 // inexact. This is why there is no Rotate for the generic BBGrid.
119 void Rotate(const FCOORD& rotation);
120
121 // Returns a new IntGrid containing values equal to the sum of all the
122 // neighbouring cells. The returned grid must be deleted after use.
123 IntGrid* NeighbourhoodSum() const;
124
125 int GridCellValue(int grid_x, int grid_y) const {
126 ClipGridCoords(&grid_x, &grid_y);
127 return grid_[grid_y * gridwidth_ + grid_x];
128 }
129 void SetGridCell(int grid_x, int grid_y, int value) {
130 ASSERT_HOST(grid_x >= 0 && grid_x < gridwidth());
131 ASSERT_HOST(grid_y >= 0 && grid_y < gridheight());
132 grid_[grid_y * gridwidth_ + grid_x] = value;
133 }
134 // Returns true if more than half the area of the rect is covered by grid
135 // cells that are over the theshold.
136 bool RectMostlyOverThreshold(const TBOX& rect, int threshold) const;
137
138 // Returns true if any cell value in the given rectangle is zero.
139 bool AnyZeroInRect(const TBOX& rect) const;
140
141 // Returns a full-resolution binary pix in which each cell over the given
142 // threshold is filled as a black square. pixDestroy after use.
143 Pix* ThresholdToPix(int threshold) const;
144
145 private:
146 int* grid_; // 2-d array of ints.
147 };
148
149 // The BBGrid class holds C_LISTs of template classes BBC (bounding box class)
150 // in a grid for fast neighbour access.
151 // The BBC class must have a member const TBOX& bounding_box() const.
152 // The BBC class must have been CLISTIZEH'ed elsewhere to make the
153 // list class BBC_CLIST and the iterator BBC_C_IT.
154 // Use of C_LISTs enables BBCs to exist in multiple cells simultaneously.
155 // As a consequence, ownership of BBCs is assumed to be elsewhere and
156 // persistent for at least the life of the BBGrid, or at least until Clear is
157 // called which removes all references to inserted objects without actually
158 // deleting them.
159 // Most uses derive a class from a specific instantiation of BBGrid,
160 // thereby making most of the ugly template notation go away.
161 // The friend class GridSearch, with the same template arguments, is
162 // used to search a grid efficiently in one of several search patterns.
163 template<class BBC, class BBC_CLIST, class BBC_C_IT> class BBGrid
164 : public GridBase {
165 friend class GridSearch<BBC, BBC_CLIST, BBC_C_IT>;
166 public:
167 BBGrid();
168 BBGrid(int gridsize, const ICOORD& bleft, const ICOORD& tright);
169 virtual ~BBGrid();
170
171 // (Re)Initialize the grid. The gridsize is the size in pixels of each cell,
172 // and bleft, tright are the bounding box of everything to go in it.
173 void Init(int gridsize, const ICOORD& bleft, const ICOORD& tright);
174
175 // Empty all the lists but leave the grid itself intact.
176 void Clear();
177 // Deallocate the data in the lists but otherwise leave the lists and the grid
178 // intact.
179 void ClearGridData(void (*free_method)(BBC*));
180
181 // Insert a bbox into the appropriate place in the grid.
182 // If h_spread, then all cells covered horizontally by the box are
183 // used, otherwise, just the bottom-left. Similarly for v_spread.
184 // WARNING: InsertBBox may invalidate an active GridSearch. Call
185 // RepositionIterator() on any GridSearches that are active on this grid.
186 void InsertBBox(bool h_spread, bool v_spread, BBC* bbox);
187
188 // Using a pix from TraceOutlineOnReducedPix or TraceBlockOnReducedPix, in
189 // which each pixel corresponds to a grid cell, insert a bbox into every
190 // place in the grid where the corresponding pixel is 1. The Pix is handled
191 // upside-down to match the Tesseract coordinate system. (As created by
192 // TraceOutlineOnReducedPix or TraceBlockOnReducedPix.)
193 // (0, 0) in the pix corresponds to (left, bottom) in the
194 // grid (in grid coords), and the pix works up the grid from there.
195 // WARNING: InsertPixPtBBox may invalidate an active GridSearch. Call
196 // RepositionIterator() on any GridSearches that are active on this grid.
197 void InsertPixPtBBox(int left, int bottom, Pix* pix, BBC* bbox);
198
199 // Remove the bbox from the grid.
200 // WARNING: Any GridSearch operating on this grid could be invalidated!
201 // If a GridSearch is operating, call GridSearch::RemoveBBox() instead.
202 void RemoveBBox(BBC* bbox);
203
204 // Returns true if the given rectangle has no overlapping elements.
205 bool RectangleEmpty(const TBOX& rect);
206
207 // Returns an IntGrid showing the number of elements in each cell.
208 // Returned IntGrid must be deleted after use.
209 IntGrid* CountCellElements();
210
211 // Make a window of an appropriate size to display things in the grid.
212 ScrollView* MakeWindow(int x, int y, const char* window_name);
213
214 // Display the bounding boxes of the BLOBNBOXes in this grid.
215 // Use of this function requires an additional member of the BBC class:
216 // ScrollView::Color BBC::BoxColor() const.
217 void DisplayBoxes(ScrollView* window);
218
219 // ASSERT_HOST that every cell contains no more than one copy of each entry.
220 void AssertNoDuplicates();
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> class GridSearch {
233 public:
234 GridSearch(BBGrid<BBC, BBC_CLIST, BBC_C_IT>* grid)
235 : grid_(grid), unique_mode_(false),
236 previous_return_(NULL), next_return_(NULL) {
237 }
238
239 // Get the grid x, y coords of the most recently returned BBC.
240 int GridX() const {
241 return x_;
242 }
243 int GridY() const {
244 return y_;
245 }
246
247 // Sets the search mode to return a box only once.
248 // Efficiency warning: Implementation currently uses a squared-order
249 // search in the number of returned elements. Use only where a small
250 // number of elements are spread over a wide area, eg ColPartitions.
251 void SetUniqueMode(bool mode) {
252 unique_mode_ = mode;
253 }
254 // TODO(rays) Replace calls to ReturnedSeedElement with SetUniqueMode.
255 // It only works if the search includes the bottom-left corner.
256 // Apart from full search, all other searches return a box several
257 // times if the box is inserted with h_spread or v_spread.
258 // This method will return true for only one occurrence of each box
259 // that was inserted with both h_spread and v_spread as true.
260 // It will usually return false for boxes that were not inserted with
261 // both h_spread=true and v_spread=true
262 bool ReturnedSeedElement() const {
263 TBOX box = previous_return_->bounding_box();
264 int x_center = (box.left()+box.right())/2;
265 int y_center = (box.top()+box.bottom())/2;
266 int grid_x, grid_y;
267 grid_->GridCoords(x_center, y_center, &grid_x, &grid_y);
268 return (x_ == grid_x) && (y_ == grid_y);
269 }
270
271 // Various searching iterations... Note that these iterations
272 // all share data members, so you can't run more than one iteration
273 // in parallel in a single GridSearch instance, but multiple instances
274 // can search the same BBGrid in parallel.
275 // Note that all the searches can return blobs that may not exactly
276 // match the search conditions, since they return everything in the
277 // covered grid cells. It is up to the caller to check for
278 // appropriateness.
279 // TODO(rays) NextRectSearch only returns valid elements. Make the other
280 // searches test before return also and remove the tests from code
281 // that uses GridSearch.
282
283 // Start a new full search. Will iterate all stored blobs, from the top.
284 // If the blobs have been inserted using InsertBBox, (not InsertPixPtBBox)
285 // then the full search guarantees to return each blob in the grid once.
286 // Other searches may return a blob more than once if they have been
287 // inserted using h_spread or v_spread.
288 void StartFullSearch();
289 // Return the next bbox in the search or NULL if done.
290 BBC* NextFullSearch();
291
292 // Start a new radius search. Will search in a spiral upto a
293 // given maximum radius in grid cells from the given center in pixels.
294 void StartRadSearch(int x, int y, int max_radius);
295 // Return the next bbox in the radius search or NULL if the
296 // maximum radius has been reached.
297 BBC* NextRadSearch();
298
299 // Start a new left or right-looking search. Will search to the side
300 // for a box that vertically overlaps the given vertical line segment.
301 // CAVEAT: This search returns all blobs from the cells to the side
302 // of the start, and somewhat below, since there is no guarantee
303 // that there may not be a taller object in a lower cell. The
304 // blobs returned will include all those that vertically overlap and
305 // are no more than twice as high, but may also include some that do
306 // not overlap and some that are more than twice as high.
307 void StartSideSearch(int x, int ymin, int ymax);
308 // Return the next bbox in the side search or NULL if the
309 // edge has been reached. Searches left to right or right to left
310 // according to the flag.
311 BBC* NextSideSearch(bool right_to_left);
312
313 // Start a vertical-looking search. Will search up or down
314 // for a box that horizontally overlaps the given line segment.
315 void StartVerticalSearch(int xmin, int xmax, int y);
316 // Return the next bbox in the vertical search or NULL if the
317 // edge has been reached. Searches top to bottom or bottom to top
318 // according to the flag.
319 BBC* NextVerticalSearch(bool top_to_bottom);
320
321 // Start a rectangular search. Will search for a box that overlaps the
322 // given rectangle.
323 void StartRectSearch(const TBOX& rect);
324 // Return the next bbox in the rectangular search or NULL if complete.
325 BBC* NextRectSearch();
326
327 // Remove the last returned BBC. Will not invalidate this. May invalidate
328 // any other concurrent GridSearch on the same grid. If any others are
329 // in use, call RepositionIterator on those, to continue without harm.
330 void RemoveBBox();
331 void RepositionIterator();
332
333 private:
334 // Factored out helper to start a search.
335 void CommonStart(int x, int y);
336 // Factored out helper to complete a next search.
337 BBC* CommonNext();
338 // Factored out final return when search is exhausted.
339 BBC* CommonEnd();
340 // Factored out function to set the iterator to the current x_, y_
341 // grid coords and mark the cycle pt.
342 void SetIterator();
343
344 private:
345 // The grid we are searching.
346 BBGrid<BBC, BBC_CLIST, BBC_C_IT>* grid_;
347 // For executing a search. The different search algorithms use these in
348 // different ways, but most use x_origin_ and y_origin_ as the start position.
349 int x_origin_;
350 int y_origin_;
351 int max_radius_;
352 int radius_;
353 int rad_index_;
354 int rad_dir_;
355 TBOX rect_;
356 int x_; // The current location in grid coords, of the current search.
357 int y_;
358 bool unique_mode_;
359 BBC* previous_return_; // Previous return from Next*.
360 BBC* next_return_; // Current value of it_.data() used for repositioning.
361 // An iterator over the list at (x_, y_) in the grid_.
362 BBC_C_IT it_;
363 // List of unique returned elements used when unique_mode_ is true.
364 BBC_CLIST returns_;
365 };
366
367 // Sort function to sort a BBC by bounding_box().left().
368 template<class BBC>
369 int SortByBoxLeft(const void* void1, const void* void2) {
370 // The void*s are actually doubly indirected, so get rid of one level.
371 const BBC* p1 = *reinterpret_cast<const BBC* const *>(void1);
372 const BBC* p2 = *reinterpret_cast<const BBC* const *>(void2);
373 int result = p1->bounding_box().left() - p2->bounding_box().left();
374 if (result != 0)
375 return result;
376 result = p1->bounding_box().right() - p2->bounding_box().right();
377 if (result != 0)
378 return result;
379 result = p1->bounding_box().bottom() - p2->bounding_box().bottom();
380 if (result != 0)
381 return result;
382 return p1->bounding_box().top() - p2->bounding_box().top();
383 }
384
385 // Sort function to sort a BBC by bounding_box().right() in right-to-left order.
386 template<class BBC>
387 int SortRightToLeft(const void* void1, const void* void2) {
388 // The void*s are actually doubly indirected, so get rid of one level.
389 const BBC* p1 = *reinterpret_cast<const BBC* const *>(void1);
390 const BBC* p2 = *reinterpret_cast<const BBC* const *>(void2);
391 int result = p2->bounding_box().right() - p1->bounding_box().right();
392 if (result != 0)
393 return result;
394 result = p2->bounding_box().left() - p1->bounding_box().left();
395 if (result != 0)
396 return result;
397 result = p1->bounding_box().bottom() - p2->bounding_box().bottom();
398 if (result != 0)
399 return result;
400 return p1->bounding_box().top() - p2->bounding_box().top();
401 }
402
403 // Sort function to sort a BBC by bounding_box().bottom().
404 template<class BBC>
405 int SortByBoxBottom(const void* void1, const void* void2) {
406 // The void*s are actually doubly indirected, so get rid of one level.
407 const BBC* p1 = *reinterpret_cast<const BBC* const *>(void1);
408 const BBC* p2 = *reinterpret_cast<const BBC* const *>(void2);
409 int result = p1->bounding_box().bottom() - p2->bounding_box().bottom();
410 if (result != 0)
411 return result;
412 result = p1->bounding_box().top() - p2->bounding_box().top();
413 if (result != 0)
414 return result;
415 result = p1->bounding_box().left() - p2->bounding_box().left();
416 if (result != 0)
417 return result;
418 return p1->bounding_box().right() - p2->bounding_box().right();
419 }
420
422 // BBGrid IMPLEMENTATION.
424 template<class BBC, class BBC_CLIST, class BBC_C_IT>
425 BBGrid<BBC, BBC_CLIST, BBC_C_IT>::BBGrid() : grid_(NULL) {
426 }
427
428 template<class BBC, class BBC_CLIST, class BBC_C_IT>
429 BBGrid<BBC, BBC_CLIST, BBC_C_IT>::BBGrid(
430 int gridsize, const ICOORD& bleft, const ICOORD& tright)
431 : grid_(NULL) {
432 Init(gridsize, bleft, tright);
433 }
434
435 template<class BBC, class BBC_CLIST, class BBC_C_IT>
436 BBGrid<BBC, BBC_CLIST, BBC_C_IT>::~BBGrid() {
437 if (grid_ != NULL)
438 delete [] grid_;
439 }
440
441 // (Re)Initialize the grid. The gridsize is the size in pixels of each cell,
442 // and bleft, tright are the bounding box of everything to go in it.
443 template<class BBC, class BBC_CLIST, class BBC_C_IT>
444 void BBGrid<BBC, BBC_CLIST, BBC_C_IT>::Init(int gridsize,
445 const ICOORD& bleft,
446 const ICOORD& tright) {
447 GridBase::Init(gridsize, bleft, tright);
448 if (grid_ != NULL)
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>
455 void BBGrid<BBC, BBC_CLIST, BBC_C_IT>::Clear() {
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>
464 void BBGrid<BBC, BBC_CLIST, BBC_C_IT>::ClearGridData(
465 void (*free_method)(BBC*)) {
466 if (grid_ == NULL) return;
467 GridSearch<BBC, BBC_CLIST, BBC_C_IT> search(this);
468 search.StartFullSearch();
469 BBC* bb;
470 BBC_CLIST bb_list;
471 BBC_C_IT it(&bb_list);
472 while ((bb = search.NextFullSearch()) != NULL) {
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>
514 void BBGrid<BBC, BBC_CLIST, BBC_C_IT>::InsertPixPtBBox(int left, int bottom,
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>
533 void BBGrid<BBC, BBC_CLIST, BBC_C_IT>::RemoveBBox(BBC* bbox) {
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>
552 bool BBGrid<BBC, BBC_CLIST, BBC_C_IT>::RectangleEmpty(const TBOX& rect) {
553 GridSearch<BBC, BBC_CLIST, BBC_C_IT> rsearch(this);
554 rsearch.StartRectSearch(rect);
555 return rsearch.NextRectSearch() == NULL;
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>
561 IntGrid* BBGrid<BBC, BBC_CLIST, BBC_C_IT>::CountCellElements() {
562 IntGrid* 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) {
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>
589 ScrollView* BBGrid<BBC, BBC_CLIST, BBC_C_IT>::MakeWindow(
590 int x, int y, const char* window_name) {
591 ScrollView* tab_win = NULL;
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 TabEventHandler<BBGrid<BBC, BBC_CLIST, BBC_C_IT> >* handler =
600 new TabEventHandler<BBGrid<BBC, BBC_CLIST, BBC_C_IT> >(this);
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>
613 void BBGrid<BBC, BBC_CLIST, BBC_C_IT>::DisplayBoxes(ScrollView* tab_win) {
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.
619 GridSearch<BBC, BBC_CLIST, BBC_C_IT> gsearch(this);
620 gsearch.StartFullSearch();
621 BBC* bbox;
622 while ((bbox = gsearch.NextFullSearch()) != NULL) {
623 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>
638 void BBGrid<BBC, BBC_CLIST, BBC_C_IT>::AssertNoDuplicates() {
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>
655 void BBGrid<BBC, BBC_CLIST, BBC_C_IT>::HandleClick(int x, int y) {
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>
665 void GridSearch<BBC, BBC_CLIST, BBC_C_IT>::StartFullSearch() {
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 NULL 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>
675 BBC* GridSearch<BBC, BBC_CLIST, BBC_C_IT>::NextFullSearch() {
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>
698 void GridSearch<BBC, BBC_CLIST, BBC_C_IT>::StartRadSearch(int x, int y,
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 NULL if the
711 // maximum radius has been reached.
712 template<class BBC, class BBC_CLIST, class BBC_C_IT>
713 BBC* GridSearch<BBC, BBC_CLIST, BBC_C_IT>::NextRadSearch() {
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_ &&
738 !returns_.add_sorted(SortByBoxLeft<BBC>, true, previous_return_));
739 return previous_return_;
740 }
741
742 // Start a new left or right-looking search. Will search to the side
743 // for a box that vertically overlaps the given vertical line segment.
744 template<class BBC, class BBC_CLIST, class BBC_C_IT>
745 void GridSearch<BBC, BBC_CLIST, BBC_C_IT>::StartSideSearch(int x,
746 int ymin, int ymax) {
747 // Right search records the x in x_origin_, the ymax in y_origin_
748 // and the size of the vertical strip to search in radius_.
749 // To guarantee finding overlapping objects of upto twice the
750 // given size, double the height.
751 radius_ = ((ymax - ymin) * 2 + grid_->gridsize_ - 1) / grid_->gridsize_;
752 rad_index_ = 0;
753 CommonStart(x, ymax);
754 }
755
756 // Return the next bbox in the side search or NULL if the
757 // edge has been reached. Searches left to right or right to left
758 // according to the flag.
759 template<class BBC, class BBC_CLIST, class BBC_C_IT>
760 BBC* GridSearch<BBC, BBC_CLIST, BBC_C_IT>::NextSideSearch(bool right_to_left) {
761 do {
762 while (it_.cycled_list()) {
763 ++rad_index_;
764 if (rad_index_ > radius_) {
765 if (right_to_left)
766 --x_;
767 else
768 ++x_;
769 rad_index_ = 0;
770 if (x_ < 0 || x_ >= grid_->gridwidth_)
771 return CommonEnd();
772 }
773 y_ = y_origin_ - rad_index_;
774 if (y_ >= 0 && y_ < grid_->gridheight_)
775 SetIterator();
776 }
777 CommonNext();
778 } while (unique_mode_ &&
779 !returns_.add_sorted(SortByBoxLeft<BBC>, true, previous_return_));
780 return previous_return_;
781 }
782
783 // Start a vertical-looking search. Will search up or down
784 // for a box that horizontally overlaps the given line segment.
785 template<class BBC, class BBC_CLIST, class BBC_C_IT>
786 void GridSearch<BBC, BBC_CLIST, BBC_C_IT>::StartVerticalSearch(int xmin,
787 int xmax,
788 int y) {
789 // Right search records the xmin in x_origin_, the y in y_origin_
790 // and the size of the horizontal strip to search in radius_.
791 radius_ = (xmax - xmin + grid_->gridsize_ - 1) / grid_->gridsize_;
792 rad_index_ = 0;
793 CommonStart(xmin, y);
794 }
795
796 // Return the next bbox in the vertical search or NULL if the
797 // edge has been reached. Searches top to bottom or bottom to top
798 // according to the flag.
799 template<class BBC, class BBC_CLIST, class BBC_C_IT>
800 BBC* GridSearch<BBC, BBC_CLIST, BBC_C_IT>::NextVerticalSearch(
801 bool top_to_bottom) {
802 do {
803 while (it_.cycled_list()) {
804 ++rad_index_;
805 if (rad_index_ > radius_) {
806 if (top_to_bottom)
807 --y_;
808 else
809 ++y_;
810 rad_index_ = 0;
811 if (y_ < 0 || y_ >= grid_->gridheight_)
812 return CommonEnd();
813 }
814 x_ = x_origin_ + rad_index_;
815 if (x_ >= 0 && x_ < grid_->gridwidth_)
816 SetIterator();
817 }
818 CommonNext();
819 } while (unique_mode_ &&
820 !returns_.add_sorted(SortByBoxLeft<BBC>, true, previous_return_));
821 return previous_return_;
822 }
823
824 // Start a rectangular search. Will search for a box that overlaps the
825 // given rectangle.
826 template<class BBC, class BBC_CLIST, class BBC_C_IT>
827 void GridSearch<BBC, BBC_CLIST, BBC_C_IT>::StartRectSearch(const TBOX& rect) {
828 // Rect search records the xmin in x_origin_, the ymin in y_origin_
829 // and the xmax in max_radius_.
830 // The search proceeds left to right, top to bottom.
831 rect_ = rect;
832 CommonStart(rect.left(), rect.top());
833 grid_->GridCoords(rect.right(), rect.bottom(), // - rect.height(),
834 &max_radius_, &y_origin_);
835 }
836
837 // Return the next bbox in the rectangular search or NULL if complete.
838 template<class BBC, class BBC_CLIST, class BBC_C_IT>
839 BBC* GridSearch<BBC, BBC_CLIST, BBC_C_IT>::NextRectSearch() {
840 do {
841 while (it_.cycled_list()) {
842 ++x_;
843 if (x_ > max_radius_) {
844 --y_;
845 x_ = x_origin_;
846 if (y_ < y_origin_)
847 return CommonEnd();
848 }
849 SetIterator();
850 }
851 CommonNext();
852 } while (!rect_.overlap(previous_return_->bounding_box()) ||
853 (unique_mode_ &&
854 !returns_.add_sorted(SortByBoxLeft<BBC>, true, previous_return_)));
855 return previous_return_;
856 }
857
858 // Remove the last returned BBC. Will not invalidate this. May invalidate
859 // any other concurrent GridSearch on the same grid. If any others are
860 // in use, call RepositionIterator on those, to continue without harm.
861 template<class BBC, class BBC_CLIST, class BBC_C_IT>
862 void GridSearch<BBC, BBC_CLIST, BBC_C_IT>::RemoveBBox() {
863 if (previous_return_ != NULL) {
864 // Remove all instances of previous_return_ from the list, so the iterator
865 // remains valid after removal from the rest of the grid cells.
866 // if previous_return_ is not on the list, then it has been removed already.
867 BBC* prev_data = NULL;
868 BBC* new_previous_return = NULL;
869 it_.move_to_first();
870 for (it_.mark_cycle_pt(); !it_.cycled_list();) {
871 if (it_.data() == previous_return_) {
872 new_previous_return = prev_data;
873 it_.extract();
874 it_.forward();
875 next_return_ = it_.cycled_list() ? NULL : it_.data();
876 } else {
877 prev_data = it_.data();
878 it_.forward();
879 }
880 }
881 grid_->RemoveBBox(previous_return_);
882 previous_return_ = new_previous_return;
883 RepositionIterator();
884 }
885 }
886
887 template<class BBC, class BBC_CLIST, class BBC_C_IT>
888 void GridSearch<BBC, BBC_CLIST, BBC_C_IT>::RepositionIterator() {
889 // Something was deleted, so we have little choice but to clear the
890 // returns list.
891 returns_.shallow_clear();
892 // Reset the iterator back to one past the previous return.
893 // If the previous_return_ is no longer in the list, then
894 // next_return_ serves as a backup.
895 it_.move_to_first();
896 // Special case, the first element was removed and reposition
897 // iterator was called. In this case, the data is fine, but the
898 // cycle point is not. Detect it and return.
899 if (!it_.empty() && it_.data() == next_return_) {
900 it_.mark_cycle_pt();
901 return;
902 }
903 for (it_.mark_cycle_pt(); !it_.cycled_list(); it_.forward()) {
904 if (it_.data() == previous_return_ ||
905 it_.data_relative(1) == next_return_) {
906 CommonNext();
907 return;
908 }
909 }
910 // We ran off the end of the list. Move to a new cell next time.
911 previous_return_ = NULL;
912 next_return_ = NULL;
913 }
914
915 // Factored out helper to start a search.
916 template<class BBC, class BBC_CLIST, class BBC_C_IT>
917 void GridSearch<BBC, BBC_CLIST, BBC_C_IT>::CommonStart(int x, int y) {
918 grid_->GridCoords(x, y, &x_origin_, &y_origin_);
919 x_ = x_origin_;
920 y_ = y_origin_;
921 SetIterator();
922 previous_return_ = NULL;
923 next_return_ = it_.empty() ? NULL : it_.data();
924 returns_.shallow_clear();
925 }
926
927 // Factored out helper to complete a next search.
928 template<class BBC, class BBC_CLIST, class BBC_C_IT>
929 BBC* GridSearch<BBC, BBC_CLIST, BBC_C_IT>::CommonNext() {
930 previous_return_ = it_.data();
931 it_.forward();
932 next_return_ = it_.cycled_list() ? NULL : it_.data();
933 return previous_return_;
934 }
935
936 // Factored out final return when search is exhausted.
937 template<class BBC, class BBC_CLIST, class BBC_C_IT>
938 BBC* GridSearch<BBC, BBC_CLIST, BBC_C_IT>::CommonEnd() {
939 previous_return_ = NULL;
940 next_return_ = NULL;
941 return NULL;
942 }
943
944 // Factored out function to set the iterator to the current x_, y_
945 // grid coords and mark the cycle pt.
946 template<class BBC, class BBC_CLIST, class BBC_C_IT>
947 void GridSearch<BBC, BBC_CLIST, BBC_C_IT>::SetIterator() {
948 it_= &(grid_->grid_[y_ * grid_->gridwidth_ + x_]);
949 it_.mark_cycle_pt();
950 }
951
952 } // namespace tesseract.
953
954 #endif // TESSERACT_TEXTORD_BBGRID_H__