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