1 /* thin-image.c: thin binary image
2
3 Copyright (C) 2001, 2002 Martin Weber
4
5 This library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public License
7 as published by the Free Software Foundation; either version 2.1 of
8 the License, or (at your option) any later version.
9
10 This library is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public
16 License along with this library; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
18 USA. */
19
20 #ifdef HAVE_CONFIG_H
21 #include "config.h"
22 #endif /* Def: HAVE_CONFIG_H */
23
24 #include <stdlib.h>
25 #include <stdio.h>
26 #include "thin-image.h"
27 #include "logreport.h"
28 #include "message.h"
29 #include "types.h"
30 #include "bitmap.h"
31 #include "xstd.h"
32 #include <string.h>
33
34 #define PIXEL_SET(p, new) ((void)memcpy((p), (new), sizeof(Pixel)))
35 #define PIXEL_EQUAL(p1, p2) \
36 ((p1)[0] == (p2)[0] && (p1)[1] == (p2)[1] && (p1)[2] == (p2)[2])
37
38
39 typedef unsigned char Pixel[3]; /* RGB pixel data type */
40
41
42 void thin3(bitmap_type *image, Pixel colour);
43 void thin1(bitmap_type *image, unsigned char colour);
44
45
46 /* -------------------------------- ThinImage - Thin binary image. --------------------------- *
47 *
48 * Description:
49 * Thins the supplied binary image using Rosenfeld's parallel
50 * thinning algorithm.
51 *
52 * On Entry:
53 * image = Image to thin.
54 *
55 * -------------------------------------------------------------------------------------------- */
56
57
58 /* Direction masks: */
59 /* N S W E */
60 static unsigned int masks[] = { 0200, 0002, 0040, 0010 };
61
62 /* True if pixel neighbor map indicates the pixel is 8-simple and */
63 /* not an end point and thus can be deleted. The neighborhood */
64 /* map is defined as an integer of bits abcdefghi with a non-zero */
65 /* bit representing a non-zero pixel. The bit assignment for the */
66 /* neighborhood is: */
67 /* */
68 /* a b c */
69 /* d e f */
70 /* g h i */
71
72 static unsigned char todelete[512] = {
73 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
74 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1,
75 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
76 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1,
77 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
78 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1,
79 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
80 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1,
81 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
82 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1,
83 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
84 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
85 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
86 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1,
87 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
88 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
89 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
90 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
91 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
92 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1,
93 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
94 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
95 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
96 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1,
97 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
98 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1,
99 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
100 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
101 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
102 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1,
103 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
104 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
105
106 static color_type background = { 0xff, 0xff, 0xff };
107
108
thin_image(bitmap_type * image,const color_type * bg,at_exception_type * exp)109 void thin_image(bitmap_type *image, const color_type *bg, at_exception_type * exp)
110 {
111 /* This is nasty as we need to call thin once for each
112 * colour in the image the way I do this is to keep a second
113 * copy of the bitmap and to use this to keep
114 * track of which colours have not yet been processed,
115 * trades time for pathological case memory.....*/
116 long m, n, num_pixels;
117 bitmap_type bm;
118 unsigned int
119 spp = BITMAP_PLANES(*image),
120 width = BITMAP_WIDTH(*image),
121 height = BITMAP_HEIGHT(*image);
122
123 if (bg) background = *bg;
124
125 bm.height = image->height;
126 bm.width = image->width;
127 bm.np = image->np;
128 XMALLOC(bm.bitmap, height * width * spp);
129 memcpy(bm.bitmap, image->bitmap, height * width * spp);
130 /* that clones the image */
131
132 num_pixels = height * width;
133 switch (spp)
134 {
135 case 3:
136 {
137 Pixel *ptr = (Pixel*)BITMAP_BITS(bm);
138 Pixel bg_color;
139 bg_color[0] = background.r;
140 bg_color[1] = background.g;
141 bg_color[2] = background.b;
142
143 for (n = num_pixels - 1; n >= 0L; --n)
144 {
145 Pixel p;
146
147 PIXEL_SET(p, ptr[n]);
148 if (!PIXEL_EQUAL(p, bg_color))
149 {
150 /* we have a new colour in the image */
151 LOG3("Thinning colour (%x, %x, %x)\n", p[0], p[1], p[2]);
152 for (m = n - 1; m >= 0L; --m)
153 {
154 if (PIXEL_EQUAL(ptr[m], p))
155 PIXEL_SET(ptr[m], bg_color);
156 }
157 thin3(image, p);
158 }
159 }
160 break;
161 }
162
163 case 1:
164 {
165 unsigned char *ptr = BITMAP_BITS(bm);
166 unsigned char bg_color;
167
168 if (background.r == background.g && background.g == background.b)
169 bg_color = background.r;
170 else bg_color = COLOR_LUMINANCE(background);
171
172 for (n = num_pixels - 1; n >= 0L; --n)
173 {
174 unsigned char c = ptr[n];
175 if (c != bg_color)
176 {
177 LOG1 ("Thinning colour %x\n", c);
178 for (m = n - 1; m >= 0L; --m)
179 if (ptr[m] == c) ptr[m] = bg_color;
180 thin1(image, c);
181 }
182 }
183 break;
184 }
185
186 default:
187 {
188 LOG1 ("thin_image: %u-plane images are not supported", spp);
189 at_exception_fatal(exp, "thin_image: wrong plane images are passed");
190 goto cleanup;
191 }
192 }
193 cleanup:
194 free (bm.bitmap);
195 }
196
197
thin3(bitmap_type * image,Pixel colour)198 void thin3(bitmap_type *image, Pixel colour)
199 {
200 Pixel *ptr, *y_ptr, *y1_ptr;
201 Pixel bg_color;
202 unsigned int xsize, ysize; /* Image resolution */
203 unsigned int x, y; /* Pixel location */
204 unsigned int i; /* Pass index */
205 unsigned int pc = 0; /* Pass count */
206 unsigned int count = 1; /* Deleted pixel count */
207 unsigned int p, q; /* Neighborhood maps of adjacent*/
208 /* cells */
209 unsigned char *qb; /* Neighborhood maps of previous*/
210 /* scanline */
211 unsigned int m; /* Deletion direction mask */
212
213 bg_color[0] = background.r;
214 bg_color[1] = background.g;
215 bg_color[2] = background.b;
216
217 LOG (" Thinning image.....\n ");
218 xsize = BITMAP_WIDTH(*image);
219 ysize = BITMAP_HEIGHT(*image);
220 XMALLOC (qb, xsize*sizeof(unsigned char));
221 qb[xsize-1] = 0; /* Used for lower-right pixel */
222 ptr = (Pixel*)BITMAP_BITS(*image);
223
224 while ( count ) { /* Scan image while deletions */
225 pc++;
226 count = 0;
227
228 for ( i = 0 ; i < 4 ; i++ ) {
229
230 m = masks[i];
231
232 /* Build initial previous scan buffer. */
233 p = PIXEL_EQUAL(ptr[0], colour);
234 for ( x = 0 ; x < xsize-1 ; x++ )
235 qb[x] = (unsigned char) (p = ((p<<1)&0006) | (unsigned int) PIXEL_EQUAL(ptr[x+1],
236 colour));
237
238 /* Scan image for pixel deletion candidates. */
239 y_ptr = ptr; y1_ptr = ptr + xsize;
240 for (y = 0; y < ysize - 1; y++, y_ptr += xsize, y1_ptr += xsize)
241 {
242 q = qb[0];
243 p = ((q<<2)&0330) | (unsigned int) PIXEL_EQUAL(y1_ptr[0], colour);
244
245 for ( x = 0 ; x < xsize-1 ; x++ ) {
246 q = qb[x];
247 p = ((p<<1)&0666) | ((q<<3)&0110) |
248 (unsigned int) PIXEL_EQUAL(y1_ptr[x+1], colour);
249 qb[x] = (unsigned char) p;
250 if ((i != 2 || x != 0) && ((p&m) == 0) && todelete[p] ) {
251 count++; /* delete the pixel */
252 PIXEL_SET(y_ptr[x], bg_color);
253 }
254 }
255
256 /* Process right edge pixel. */
257 p = (p<<1)&0666;
258 if (i != 3 && (p&m) == 0 && todelete[p] ) {
259 count++;
260 PIXEL_SET(y_ptr[xsize-1], bg_color);
261 }
262 }
263
264 if (i != 1)
265 {
266 /* Process bottom scan line. */
267 q = qb[0];
268 p = ((q<<2)&0330);
269
270 y_ptr = ptr + xsize * (ysize - 1);
271 for ( x = 0 ; x < xsize ; x++ ) {
272 q = qb[x];
273 p = ((p<<1)&0666) | ((q<<3)&0110);
274 if ((i != 2 || x != 0) && (p&m) == 0 && todelete[p]) {
275 count++;
276 PIXEL_SET(y_ptr[x], bg_color);
277 }
278 }
279 }
280 }
281 LOG2 ("ThinImage: pass %d, %d pixels deleted\n", pc, count);
282 }
283 free (qb);
284 }
285
286
thin1(bitmap_type * image,unsigned char colour)287 void thin1(bitmap_type *image, unsigned char colour)
288 {
289 unsigned char *ptr, *y_ptr, *y1_ptr;
290 unsigned char bg_color;
291 unsigned int xsize, ysize; /* Image resolution */
292 unsigned int x, y; /* Pixel location */
293 unsigned int i; /* Pass index */
294 unsigned int pc = 0; /* Pass count */
295 unsigned int count = 1; /* Deleted pixel count */
296 unsigned int p, q; /* Neighborhood maps of adjacent*/
297 /* cells */
298 unsigned char *qb; /* Neighborhood maps of previous*/
299 /* scanline */
300 unsigned int m; /* Deletion direction mask */
301
302 if (background.r == background.g && background.g == background.b)
303 bg_color = background.r;
304 else bg_color = COLOR_LUMINANCE(background);
305
306 LOG (" Thinning image.....\n ");
307 xsize = BITMAP_WIDTH(*image);
308 ysize = BITMAP_HEIGHT(*image);
309 XMALLOC (qb, xsize*sizeof(unsigned char));
310 qb[xsize-1] = 0; /* Used for lower-right pixel */
311 ptr = BITMAP_BITS(*image);
312
313 while ( count ) { /* Scan image while deletions */
314 pc++;
315 count = 0;
316
317 for ( i = 0 ; i < 4 ; i++ ) {
318
319 m = masks[i];
320
321 /* Build initial previous scan buffer. */
322 p = (ptr[0] == colour);
323 for ( x = 0 ; x < xsize-1 ; x++ )
324 qb[x] = (unsigned char) (p = ((p<<1)&0006) | (unsigned int)(ptr[x+1] == colour));
325
326 /* Scan image for pixel deletion candidates. */
327 y_ptr = ptr; y1_ptr = ptr + xsize;
328 for (y = 0; y < ysize - 1; y++, y_ptr += xsize, y1_ptr += xsize)
329 {
330 q = qb[0];
331 p = ((q<<2)&0330) | (y1_ptr[0] == colour);
332
333 for ( x = 0 ; x < xsize-1 ; x++ ) {
334 q = qb[x];
335 p = ((p<<1)&0666) | ((q<<3)&0110) | (unsigned int) (y1_ptr[x+1]==colour);
336 qb[x] = (unsigned char) p;
337 if ( ((p&m) == 0) && todelete[p] ) {
338 count++;
339 y_ptr[x] = bg_color; /* delete the pixel */
340 }
341 }
342
343 /* Process right edge pixel. */
344 p = (p<<1)&0666;
345 if ( (p&m) == 0 && todelete[p] ) {
346 count++;
347 y_ptr[xsize-1] = bg_color;
348 }
349 }
350
351 /* Process bottom scan line. */
352 q = qb[0];
353 p = ((q<<2)&0330);
354
355 y_ptr = ptr + xsize * (ysize - 1);
356 for ( x = 0 ; x < xsize ; x++ ) {
357 q = qb[x];
358 p = ((p<<1)&0666) | ((q<<3)&0110);
359 if ( (p&m) == 0 && todelete[p] ) {
360 count++;
361 y_ptr[x] = bg_color;
362 }
363 }
364 }
365 LOG2("thin1: pass %d, %d pixels deleted\n", pc, count);
366 }
367 free (qb);
368 }
369