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