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
scanedg.cpp
Go to the documentation of this file.
1 /**********************************************************************
2 * File: scanedg.c (Formerly scanedge.c)
3 * Description: Raster scanning crack based edge extractor.
4 * Author: Ray Smith
5 * Created: Fri Mar 22 16:11:50 GMT 1991
6 *
7 * (C) Copyright 1991, Hewlett-Packard Ltd.
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 *
18 **********************************************************************/
19
20 #include "mfcpch.h"
21 #include "edgloop.h"
22 #include "scanedg.h"
23
24 #define WHITE_PIX 1 /*thresholded colours */
25 #define BLACK_PIX 0
26 /*W->B->W */
27 #define FLIP_COLOUR(pix) (1-(pix))
28
29 /**********************************************************************
30 * block_edges
31 *
32 * Extract edges from a PDBLK.
33 **********************************************************************/
34
35 void block_edges(IMAGE *t_image, // thresholded image
36 PDBLK *block, // block in image
37 C_OUTLINE_IT* outline_it) {
38 uinT8 margin; // margin colour
39 inT16 x; // line coords
40 inT16 y; // current line
41 ICOORD bleft; // bounding box
42 ICOORD tright;
43 ICOORD block_bleft; // bounding box
44 ICOORD block_tright;
45 int xindex; // index to pixel
46 BLOCK_LINE_IT line_it = block; // line iterator
47 IMAGELINE bwline; // thresholded line
48 // lines in progress
49 CRACKEDGE **ptrline = new CRACKEDGE*[t_image->get_xsize()+1];
50 CRACKEDGE *free_cracks = NULL;
51
52 block->bounding_box(bleft, tright); // block box
53 block_bleft = bleft;
54 block_tright = tright;
55 for (x = tright.x() - bleft.x(); x >= 0; x--)
56 ptrline[x] = NULL; //no lines in progress
57
58 bwline.init(t_image->get_xsize());
59
60 margin = WHITE_PIX;
61
62 for (y = tright.y() - 1; y >= bleft.y() - 1; y--) {
63 if (y >= block_bleft.y() && y < block_tright.y()) {
64 t_image->get_line(bleft.x(), y, tright.x() - bleft.x(), &bwline, 0);
65 make_margins(block, &line_it, bwline.pixels, margin, bleft.x(),
66 tright.x(), y);
67 } else {
68 x = tright.x() - bleft.x();
69 for (xindex = 0; xindex < x; xindex++)
70 bwline.pixels[xindex] = margin;
71 }
72 line_edges(bleft.x(), y, tright.x() - bleft.x(),
73 margin, bwline.pixels, ptrline, &free_cracks, outline_it);
74 }
75
76 free_crackedges(free_cracks); // really free them
77 delete[] ptrline;
78 }
79
80
81 /**********************************************************************
82 * make_margins
83 *
84 * Get an image line and set to margin non-text pixels.
85 **********************************************************************/
86
87 void make_margins( //get a line
88 PDBLK *block, //block in image
89 BLOCK_LINE_IT *line_it, //for old style
90 uinT8 *pixels, //pixels to strip
91 uinT8 margin, //white-out pixel
92 inT16 left, //block edges
93 inT16 right,
94 inT16 y //line coord
95 ) {
96 PB_LINE_IT *lines;
97 ICOORDELT_LIST *segments; //bits of a line
98 ICOORDELT_IT seg_it;
99 inT32 start; //of segment
100 inT16 xext; //of segment
101 int xindex; //index to pixel
102
103 if (block->poly_block () != NULL) {
104 lines = new PB_LINE_IT (block->poly_block ());
105 segments = lines->get_line (y);
106 if (!segments->empty ()) {
107 seg_it.set_to_list (segments);
108 seg_it.mark_cycle_pt ();
109 start = seg_it.data ()->x ();
110 xext = seg_it.data ()->y ();
111 for (xindex = left; xindex < right; xindex++) {
112 if (xindex >= start && !seg_it.cycled_list ()) {
113 xindex = start + xext - 1;
114 seg_it.forward ();
115 start = seg_it.data ()->x ();
116 xext = seg_it.data ()->y ();
117 }
118 else
119 pixels[xindex - left] = margin;
120 }
121 }
122 else {
123 for (xindex = left; xindex < right; xindex++)
124 pixels[xindex - left] = margin;
125 }
126 delete segments;
127 delete lines;
128 }
129 else {
130 start = line_it->get_line (y, xext);
131 for (xindex = left; xindex < start; xindex++)
132 pixels[xindex - left] = margin;
133 for (xindex = start + xext; xindex < right; xindex++)
134 pixels[xindex - left] = margin;
135 }
136 }
137
138
139 /**********************************************************************
140 * whiteout_block
141 *
142 * Extract edges from a PDBLK.
143 **********************************************************************/
144
145 void whiteout_block( //clean it
146 IMAGE *t_image, //threshold image
147 PDBLK *block //block in image
148 ) {
149 inT16 x; //line coords
150 inT16 y; //current line
151 inT16 xext; //line width
152 int xindex; //index to pixel
153 uinT8 *dest; //destination pixel
154 TBOX block_box; //bounding box
155 BLOCK_LINE_IT line_it = block; //line iterator
156 IMAGELINE bwline; //thresholded line
157
158 block_box = block->bounding_box ();
159 for (y = block_box.bottom (); y < block_box.top (); y++) {
160 //find line limits
161 x = line_it.get_line (y, xext);
162 t_image->get_line (x, y, xext, &bwline, 0);
163 dest = bwline.pixels; //destination pixel
164 for (xindex = 0; xindex < xext; xindex++)
165 *dest++ = 1;
166 t_image->put_line (x, y, xext, &bwline, 0);
167 }
168 }
169
170
171 /**********************************************************************
172 * line_edges
173 *
174 * Scan a line for edges and update the edges in progress.
175 * When edges close into loops, send them for approximation.
176 **********************************************************************/
177
178 void line_edges(inT16 x, // coord of line start
179 inT16 y, // coord of line
180 inT16 xext, // width of line
181 uinT8 uppercolour, // start of prev line
182 uinT8 * bwpos, // thresholded line
183 CRACKEDGE ** prevline, // edges in progress
184 CRACKEDGE **free_cracks,
185 C_OUTLINE_IT* outline_it) {
186 CrackPos pos = {free_cracks, x, y };
187 int xmax; // max x coord
188 int colour; // of current pixel
189 int prevcolour; // of previous pixel
190 CRACKEDGE *current; // current h edge
191 CRACKEDGE *newcurrent; // new h edge
192
193 xmax = x + xext; // max allowable coord
194 prevcolour = uppercolour; // forced plain margin
195 current = NULL; // nothing yet
196
197 // do each pixel
198 for (; pos.x < xmax; pos.x++, prevline++) {
199 colour = *bwpos++; // current pixel
200 if (*prevline != NULL) {
201 // changed above
202 // change colour
203 uppercolour = FLIP_COLOUR(uppercolour);
204 if (colour == prevcolour) {
205 if (colour == uppercolour) {
206 // finish a line
207 join_edges(current, *prevline, free_cracks, outline_it);
208 current = NULL; // no edge now
209 } else {
210 // new horiz edge
211 current = h_edge(uppercolour - colour, *prevline, &pos);
212 }
213 *prevline = NULL; // no change this time
214 } else {
215 if (colour == uppercolour)
216 *prevline = v_edge(colour - prevcolour, *prevline, &pos);
217 // 8 vs 4 connection
218 else if (colour == WHITE_PIX) {
219 join_edges(current, *prevline, free_cracks, outline_it);
220 current = h_edge(uppercolour - colour, NULL, &pos);
221 *prevline = v_edge(colour - prevcolour, current, &pos);
222 } else {
223 newcurrent = h_edge(uppercolour - colour, *prevline, &pos);
224 *prevline = v_edge(colour - prevcolour, current, &pos);
225 current = newcurrent; // right going h edge
226 }
227 prevcolour = colour; // remember new colour
228 }
229 } else {
230 if (colour != prevcolour) {
231 *prevline = current = v_edge(colour - prevcolour, current, &pos);
232 prevcolour = colour;
233 }
234 if (colour != uppercolour)
235 current = h_edge(uppercolour - colour, current, &pos);
236 else
237 current = NULL; // no edge now
238 }
239 }
240 if (current != NULL) {
241 // out of block
242 if (*prevline != NULL) { // got one to join to?
243 join_edges(current, *prevline, free_cracks, outline_it);
244 *prevline = NULL; // tidy now
245 } else {
246 // fake vertical
247 *prevline = v_edge(FLIP_COLOUR(prevcolour)-prevcolour, current, &pos);
248 }
249 } else if (*prevline != NULL) {
250 //continue fake
251 *prevline = v_edge(FLIP_COLOUR(prevcolour)-prevcolour, *prevline, &pos);
252 }
253 }
254
255
256 /**********************************************************************
257 * h_edge
258 *
259 * Create a new horizontal CRACKEDGE and join it to the given edge.
260 **********************************************************************/
261
262 CRACKEDGE *h_edge(int sign, // sign of edge
263 CRACKEDGE* join, // edge to join to
264 CrackPos* pos) {
265 CRACKEDGE *newpt; // return value
266
267 if (*pos->free_cracks != NULL) {
268 newpt = *pos->free_cracks;
269 *pos->free_cracks = newpt->next; // get one fast
270 } else {
271 newpt = new CRACKEDGE;
272 }
273 newpt->pos.set_y(pos->y + 1); // coords of pt
274 newpt->stepy = 0; // edge is horizontal
275
276 if (sign > 0) {
277 newpt->pos.set_x(pos->x + 1); // start location
278 newpt->stepx = -1;
279 newpt->stepdir = 0;
280 } else {
281 newpt->pos.set_x(pos->x); // start location
282 newpt->stepx = 1;
283 newpt->stepdir = 2;
284 }
285
286 if (join == NULL) {
287 newpt->next = newpt; // ptrs to other ends
288 newpt->prev = newpt;
289 } else {
290 if (newpt->pos.x() + newpt->stepx == join->pos.x()
291 && newpt->pos.y() == join->pos.y()) {
292 newpt->prev = join->prev; // update other ends
293 newpt->prev->next = newpt;
294 newpt->next = join; // join up
295 join->prev = newpt;
296 } else {
297 newpt->next = join->next; // update other ends
298 newpt->next->prev = newpt;
299 newpt->prev = join; // join up
300 join->next = newpt;
301 }
302 }
303 return newpt;
304 }
305
306
307 /**********************************************************************
308 * v_edge
309 *
310 * Create a new vertical CRACKEDGE and join it to the given edge.
311 **********************************************************************/
312
313 CRACKEDGE *v_edge(int sign, // sign of edge
314 CRACKEDGE* join,
315 CrackPos* pos) {
316 CRACKEDGE *newpt; // return value
317
318 if (*pos->free_cracks != NULL) {
319 newpt = *pos->free_cracks;
320 *pos->free_cracks = newpt->next; // get one fast
321 } else {
322 newpt = new CRACKEDGE;
323 }
324 newpt->pos.set_x(pos->x); // coords of pt
325 newpt->stepx = 0; // edge is vertical
326
327 if (sign > 0) {
328 newpt->pos.set_y(pos->y); // start location
329 newpt->stepy = 1;
330 newpt->stepdir = 3;
331 } else {
332 newpt->pos.set_y(pos->y + 1); // start location
333 newpt->stepy = -1;
334 newpt->stepdir = 1;
335 }
336
337 if (join == NULL) {
338 newpt->next = newpt; //ptrs to other ends
339 newpt->prev = newpt;
340 } else {
341 if (newpt->pos.x() == join->pos.x()
342 && newpt->pos.y() + newpt->stepy == join->pos.y()) {
343 newpt->prev = join->prev; // update other ends
344 newpt->prev->next = newpt;
345 newpt->next = join; // join up
346 join->prev = newpt;
347 } else {
348 newpt->next = join->next; // update other ends
349 newpt->next->prev = newpt;
350 newpt->prev = join; // join up
351 join->next = newpt;
352 }
353 }
354 return newpt;
355 }
356
357
358 /**********************************************************************
359 * join_edges
360 *
361 * Join 2 edges together. Send the outline for approximation when a
362 * closed loop is formed.
363 **********************************************************************/
364
365 void join_edges(CRACKEDGE *edge1, // edges to join
366 CRACKEDGE *edge2, // no specific order
367 CRACKEDGE **free_cracks,
368 C_OUTLINE_IT* outline_it) {
369 if (edge1->pos.x() + edge1->stepx != edge2->pos.x()
370 || edge1->pos.y() + edge1->stepy != edge2->pos.y()) {
371 CRACKEDGE *tempedge = edge1;
372 edge1 = edge2; // swap araound
373 edge2 = tempedge;
374 }
375
376 if (edge1->next == edge2) {
377 // already closed
378 complete_edge(edge1, outline_it);
379 // attach freelist to end
380 edge1->prev->next = *free_cracks;
381 *free_cracks = edge1; // and free list
382 } else {
383 // update opposite ends
384 edge2->prev->next = edge1->next;
385 edge1->next->prev = edge2->prev;
386 edge1->next = edge2; // make joins
387 edge2->prev = edge1;
388 }
389 }
390
391
392 /**********************************************************************
393 * free_crackedges
394 *
395 * Really free the CRACKEDGEs by giving them back to delete.
396 **********************************************************************/
397
398 void free_crackedges(CRACKEDGE *start) {
399 CRACKEDGE *current; // current edge to free
400 CRACKEDGE *next; // next one to free
401
402 for (current = start; current != NULL; current = next) {
403 next = current->next;
404 delete current; // delete them all
405 }
406 }