tesseract  5.0.0-alpha-619-ge9db
bbgrid.cpp
Go to the documentation of this file.
1 // File: bbgrid.cpp
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 #include "bbgrid.h"
21 #include <tesseract/helpers.h>
22 #include "ocrblock.h"
23 
24 namespace tesseract {
25 
27 // BBGrid IMPLEMENTATION.
29 GridBase::GridBase(int gridsize, const ICOORD& bleft, const ICOORD& tright) {
31 }
32 
33 // Destructor.
34 // It is defined here, so the compiler can create a single vtable
35 // instead of weak vtables in every compilation unit.
36 GridBase::~GridBase() = default;
37 
38 // (Re)Initialize the grid. The gridsize is the size in pixels of each cell,
39 // and bleft, tright are the bounding box of everything to go in it.
40 void GridBase::Init(int gridsize, const ICOORD& bleft, const ICOORD& tright) {
42  bleft_ = bleft;
43  tright_ = tright;
44  if (gridsize_ == 0)
45  gridsize_ = 1;
46  gridwidth_ = (tright.x() - bleft.x() + gridsize_ - 1) / gridsize_;
47  gridheight_ = (tright.y() - bleft.y() + gridsize_ - 1) / gridsize_;
49 }
50 
51 // Compute the given grid coordinates from image coords.
52 void GridBase::GridCoords(int x, int y, int* grid_x, int* grid_y) const {
53  *grid_x = (x - bleft_.x()) / gridsize_;
54  *grid_y = (y - bleft_.y()) / gridsize_;
55  ClipGridCoords(grid_x, grid_y);
56 }
57 
58 // Clip the given grid coordinates to fit within the grid.
59 void GridBase::ClipGridCoords(int* x, int* y) const {
60  *x = ClipToRange(*x, 0, gridwidth_ - 1);
61  *y = ClipToRange(*y, 0, gridheight_ - 1);
62 }
63 
65  grid_ = nullptr;
66 }
67 
68 IntGrid::IntGrid(int gridsize, const ICOORD& bleft, const ICOORD& tright)
69  : grid_(nullptr) {
71 }
72 
74  delete [] grid_;
75 }
76 
77 // (Re)Initialize the grid. The gridsize is the size in pixels of each cell,
78 // and bleft, tright are the bounding box of everything to go in it.
79 void IntGrid::Init(int gridsize, const ICOORD& bleft, const ICOORD& tright) {
81  delete [] grid_;
82  grid_ = new int[gridbuckets_];
83  Clear();
84 }
85 
86 // Clear all the ints in the grid to zero.
88  for (int i = 0; i < gridbuckets_; ++i) {
89  grid_[i] = 0;
90  }
91 }
92 
93 // Rotate the grid by rotation, keeping cell contents.
94 // rotation must be a multiple of 90 degrees.
95 // NOTE: due to partial cells, cell coverage in the rotated grid will be
96 // inexact. This is why there is no Rotate for the generic BBGrid.
97 // TODO(rays) investigate fixing this inaccuracy by moving the origin after
98 // rotation.
99 void IntGrid::Rotate(const FCOORD& rotation) {
100  ASSERT_HOST(rotation.x() == 0.0f || rotation.y() == 0.0f);
101  ICOORD old_bleft(bleft());
102  //ICOORD old_tright(tright());
103  int old_width = gridwidth();
104  int old_height = gridheight();
105  TBOX box(bleft(), tright());
106  box.rotate(rotation);
107  int* old_grid = grid_;
108  grid_ = nullptr;
109  Init(gridsize(), box.botleft(), box.topright());
110  // Iterate over the old grid, copying data to the rotated position in the new.
111  int oldi = 0;
112  FCOORD x_step(rotation);
113  x_step *= gridsize();
114  for (int oldy = 0; oldy < old_height; ++oldy) {
115  FCOORD line_pos(old_bleft.x(), old_bleft.y() + gridsize() * oldy);
116  line_pos.rotate(rotation);
117  for (int oldx = 0; oldx < old_width; ++oldx, line_pos += x_step, ++oldi) {
118  int grid_x, grid_y;
119  GridCoords(static_cast<int>(line_pos.x() + 0.5),
120  static_cast<int>(line_pos.y() + 0.5),
121  &grid_x, &grid_y);
122  grid_[grid_y * gridwidth() + grid_x] = old_grid[oldi];
123  }
124  }
125  delete [] old_grid;
126 }
127 
128 // Returns a new IntGrid containing values equal to the sum of all the
129 // neighbouring cells. The returned grid must be deleted after use.
130 // For ease of implementation, edge cells are double counted, to make them
131 // have the same range as the non-edge cells.
133  auto* sumgrid = new IntGrid(gridsize(), bleft(), tright());
134  for (int y = 0; y < gridheight(); ++y) {
135  for (int x = 0; x < gridwidth(); ++x) {
136  int cell_count = 0;
137  for (int yoffset = -1; yoffset <= 1; ++yoffset) {
138  for (int xoffset = -1; xoffset <= 1; ++xoffset) {
139  int grid_x = x + xoffset;
140  int grid_y = y + yoffset;
141  ClipGridCoords(&grid_x, &grid_y);
142  cell_count += GridCellValue(grid_x, grid_y);
143  }
144  }
145  if (GridCellValue(x, y) > 1)
146  sumgrid->SetGridCell(x, y, cell_count);
147  }
148  }
149  return sumgrid;
150 }
151 
152 // Returns true if more than half the area of the rect is covered by grid
153 // cells that are over the threshold.
154 bool IntGrid::RectMostlyOverThreshold(const TBOX& rect, int threshold) const {
155  int min_x, min_y, max_x, max_y;
156  GridCoords(rect.left(), rect.bottom(), &min_x, &min_y);
157  GridCoords(rect.right(), rect.top(), &max_x, &max_y);
158  int total_area = 0;
159  for (int y = min_y; y <= max_y; ++y) {
160  for (int x = min_x; x <= max_x; ++x) {
161  int value = GridCellValue(x, y);
162  if (value > threshold) {
163  TBOX cell_box(x * gridsize_, y * gridsize_,
164  (x + 1) * gridsize_, (y + 1) * gridsize_);
165  cell_box &= rect; // This is in-place box intersection.
166  total_area += cell_box.area();
167  }
168  }
169  }
170  return total_area * 2 > rect.area();
171 }
172 
173 // Returns true if any cell value in the given rectangle is zero.
174 bool IntGrid::AnyZeroInRect(const TBOX& rect) const {
175  int min_x, min_y, max_x, max_y;
176  GridCoords(rect.left(), rect.bottom(), &min_x, &min_y);
177  GridCoords(rect.right(), rect.top(), &max_x, &max_y);
178  for (int y = min_y; y <= max_y; ++y) {
179  for (int x = min_x; x <= max_x; ++x) {
180  if (GridCellValue(x, y) == 0)
181  return true;
182  }
183  }
184  return false;
185 }
186 
187 // Returns a full-resolution binary pix in which each cell over the given
188 // threshold is filled as a black square. pixDestroy after use.
189 // Edge cells, which have a zero 4-neighbour, are not marked.
190 Pix* IntGrid::ThresholdToPix(int threshold) const {
191  Pix* pix = pixCreate(tright().x() - bleft().x(),
192  tright().y() - bleft().y(), 1);
193  int cellsize = gridsize();
194  for (int y = 0; y < gridheight(); ++y) {
195  for (int x = 0; x < gridwidth(); ++x) {
196  if (GridCellValue(x, y) > threshold &&
197  GridCellValue(x - 1, y) > 0 && GridCellValue(x + 1, y) > 0 &&
198  GridCellValue(x, y - 1) > 0 && GridCellValue(x, y + 1) > 0) {
199  pixRasterop(pix, x * cellsize, tright().y() - ((y + 1) * cellsize),
200  cellsize, cellsize, PIX_SET, nullptr, 0, 0);
201  }
202  }
203  }
204  return pix;
205 }
206 
207 // Make a Pix of the correct scaled size for the TraceOutline functions.
208 static Pix* GridReducedPix(const TBOX& box, int gridsize,
209  ICOORD bleft, int* left, int* bottom) {
210  // Compute grid bounds of the outline and pad all round by 1.
211  int grid_left = (box.left() - bleft.x()) / gridsize - 1;
212  int grid_bottom = (box.bottom() - bleft.y()) / gridsize - 1;
213  int grid_right = (box.right() - bleft.x()) / gridsize + 1;
214  int grid_top = (box.top() - bleft.y()) / gridsize + 1;
215  *left = grid_left;
216  *bottom = grid_bottom;
217  return pixCreate(grid_right - grid_left + 1,
218  grid_top - grid_bottom + 1,
219  1);
220 }
221 
222 // Helper function to return a scaled Pix with one pixel per grid cell,
223 // set (black) where the given outline enters the corresponding grid cell,
224 // and clear where the outline does not touch the grid cell.
225 // Also returns the grid coords of the bottom-left of the Pix, in *left
226 // and *bottom, which corresponds to (0, 0) on the Pix.
227 // Note that the Pix is used upside-down, with (0, 0) being the bottom-left.
228 Pix* TraceOutlineOnReducedPix(C_OUTLINE* outline, int gridsize,
229  ICOORD bleft, int* left, int* bottom) {
230  const TBOX& box = outline->bounding_box();
231  Pix* pix = GridReducedPix(box, gridsize, bleft, left, bottom);
232  int wpl = pixGetWpl(pix);
233  l_uint32* data = pixGetData(pix);
234  int length = outline->pathlength();
235  ICOORD pos = outline->start_pos();
236  for (int i = 0; i < length; ++i) {
237  int grid_x = (pos.x() - bleft.x()) / gridsize - *left;
238  int grid_y = (pos.y() - bleft.y()) / gridsize - *bottom;
239  SET_DATA_BIT(data + grid_y * wpl, grid_x);
240  pos += outline->step(i);
241  }
242  return pix;
243 }
244 #if 0 // Example code shows how to use TraceOutlineOnReducedPix.
245  C_OUTLINE_IT ol_it(blob->cblob()->out_list());
246  int grid_left, grid_bottom;
247  Pix* pix = TraceOutlineOnReducedPix(ol_it.data(), gridsize_, bleft_,
248  &grid_left, &grid_bottom);
249  grid->InsertPixPtBBox(grid_left, grid_bottom, pix, blob);
250  pixDestroy(&pix);
251 #endif
252 
253 // As TraceOutlineOnReducedPix above, but on a BLOCK instead of a C_OUTLINE.
254 Pix* TraceBlockOnReducedPix(BLOCK* block, int gridsize,
255  ICOORD bleft, int* left, int* bottom) {
256  const TBOX& box = block->pdblk.bounding_box();
257  Pix* pix = GridReducedPix(box, gridsize, bleft, left, bottom);
258  int wpl = pixGetWpl(pix);
259  l_uint32* data = pixGetData(pix);
260  ICOORDELT_IT it(block->pdblk.poly_block()->points());
261  for (it.mark_cycle_pt(); !it.cycled_list();) {
262  ICOORD pos = *it.data();
263  it.forward();
264  ICOORD next_pos = *it.data();
265  ICOORD line_vector = next_pos - pos;
266  int major, minor;
267  ICOORD major_step, minor_step;
268  line_vector.setup_render(&major_step, &minor_step, &major, &minor);
269  int accumulator = major / 2;
270  while (pos != next_pos) {
271  int grid_x = (pos.x() - bleft.x()) / gridsize - *left;
272  int grid_y = (pos.y() - bleft.y()) / gridsize - *bottom;
273  SET_DATA_BIT(data + grid_y * wpl, grid_x);
274  pos += major_step;
275  accumulator += minor;
276  if (accumulator >= major) {
277  accumulator -= major;
278  pos += minor_step;
279  }
280  }
281  }
282  return pix;
283 }
284 
285 } // namespace tesseract.
ClipToRange
T ClipToRange(const T &x, const T &lower_bound, const T &upper_bound)
Definition: helpers.h:106
tesseract::GridBase::~GridBase
virtual ~GridBase()
PDBLK::bounding_box
void bounding_box(ICOORD &bottom_left, ICOORD &top_right) const
get box
Definition: pdblock.h:58
tesseract::GridBase::gridheight_
int gridheight_
Definition: bbgrid.h:88
ASSERT_HOST
#define ASSERT_HOST(x)
Definition: errcode.h:87
tesseract::IntGrid
Definition: bbgrid.h:97
bbgrid.h
tesseract::GridBase::tright_
ICOORD tright_
Definition: bbgrid.h:91
FCOORD::y
float y() const
Definition: points.h:209
ICOORD
integer coordinate
Definition: points.h:30
tesseract::GridBase::gridwidth
int gridwidth() const
Definition: bbgrid.h:66
tesseract::IntGrid::NeighbourhoodSum
IntGrid * NeighbourhoodSum() const
Definition: bbgrid.cpp:132
FCOORD::x
float x() const
Definition: points.h:206
tesseract::IntGrid::Clear
void Clear()
Definition: bbgrid.cpp:87
TBOX::top
int16_t top() const
Definition: rect.h:57
TBOX::area
int32_t area() const
Definition: rect.h:121
tesseract::IntGrid::RectMostlyOverThreshold
bool RectMostlyOverThreshold(const TBOX &rect, int threshold) const
Definition: bbgrid.cpp:154
tesseract::GridBase::GridBase
GridBase()=default
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
TBOX::rotate
void rotate(const FCOORD &vec)
Definition: rect.h:196
C_OUTLINE
Definition: coutln.h:71
tesseract::GridBase::tright
const ICOORD & tright() const
Definition: bbgrid.h:75
ICOORD::setup_render
void setup_render(ICOORD *major_step, ICOORD *minor_step, int *major, int *minor) const
Definition: points.cpp:82
BLOCK
Definition: ocrblock.h:28
BLOCK::pdblk
PDBLK pdblk
Page Description Block.
Definition: ocrblock.h:189
PDBLK::poly_block
POLY_BLOCK * poly_block() const
Definition: pdblock.h:54
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
TBOX::bottom
int16_t bottom() const
Definition: rect.h:64
TBOX::topright
const ICOORD & topright() const
Definition: rect.h:103
tesseract::GridBase::bleft_
ICOORD bleft_
Definition: bbgrid.h:90
helpers.h
tesseract
Definition: baseapi.h:65
FCOORD::rotate
void rotate(const FCOORD vec)
Definition: points.h:736
TBOX::botleft
const ICOORD & botleft() const
Definition: rect.h:91
tesseract::IntGrid::GridCellValue
int GridCellValue(int grid_x, int grid_y) const
Definition: bbgrid.h:120
tesseract::IntGrid::Init
void Init(int gridsize, const ICOORD &bleft, const ICOORD &tright)
Definition: bbgrid.cpp:79
POLY_BLOCK::points
ICOORDELT_LIST * points()
Definition: polyblk.h:52
tesseract::IntGrid::IntGrid
IntGrid()
Definition: bbgrid.cpp:64
tesseract::GridBase::gridsize
int gridsize() const
Definition: bbgrid.h:63
tesseract::IntGrid::~IntGrid
~IntGrid() override
Definition: bbgrid.cpp:73
tesseract::GridBase::gridsize_
int gridsize_
Definition: bbgrid.h:86
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
ocrblock.h
C_OUTLINE::bounding_box
const TBOX & bounding_box() const
Definition: coutln.h:112
TBOX::right
int16_t right() const
Definition: rect.h:78
C_OUTLINE::pathlength
int32_t pathlength() const
Definition: coutln.h:134
tesseract::IntGrid::Rotate
void Rotate(const FCOORD &rotation)
Definition: bbgrid.cpp:99
C_OUTLINE::step
ICOORD step(int index) const
Definition: coutln.h:143
tesseract::GridBase::gridheight
int gridheight() const
Definition: bbgrid.h:69
tesseract::IntGrid::AnyZeroInRect
bool AnyZeroInRect(const TBOX &rect) const
Definition: bbgrid.cpp:174
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
C_OUTLINE::start_pos
const ICOORD & start_pos() const
Definition: coutln.h:147
ICOORD::y
int16_t y() const
access_function
Definition: points.h:55
tesseract::IntGrid::ThresholdToPix
Pix * ThresholdToPix(int threshold) const
Definition: bbgrid.cpp:190
TBOX
Definition: rect.h:33