1 /*******************************************************************************
2
3 License:
4 This software was developed at the National Institute of Standards and
5 Technology (NIST) by employees of the Federal Government in the course
6 of their official duties. Pursuant to title 17 Section 105 of the
7 United States Code, this software is not subject to copyright protection
8 and is in the public domain. NIST assumes no responsibility whatsoever for
9 its use by other parties, and makes no guarantees, expressed or implied,
10 about its quality, reliability, or any other characteristic.
11
12 Disclaimer:
13 This software was developed to promote biometric standards and biometric
14 technology testing for the Federal Government in accordance with the USA
15 PATRIOT Act and the Enhanced Border Security and Visa Entry Reform Act.
16 Specific hardware and software products identified in this software were used
17 in order to perform the software development. In no case does such
18 identification imply recommendation or endorsement by the National Institute
19 of Standards and Technology, nor does it imply that the products and equipment
20 identified are necessarily the best available for the purpose.
21
22 *******************************************************************************/
23
24 /***********************************************************************
25 LIBRARY: LFS - NIST Latent Fingerprint System
26
27 FILE: IMGUTIL.C
28 AUTHOR: Michael D. Garris
29 DATE: 03/16/1999
30 UPDATED: 03/16/2005 by MDG
31
32 Contains general support image routines required by the NIST
33 Latent Fingerprint System (LFS).
34
35 ***********************************************************************
36 ROUTINES:
37 bits_6to8()
38 bits_8to6()
39 gray2bin()
40 pad_uchar_image()
41 fill_holes()
42 free_path()
43 search_in_direction()
44
45 ***********************************************************************/
46
47 #include <stdio.h>
48 #include <stdlib.h>
49 #include <memory.h>
50 #include <lfs.h>
51
52 /*************************************************************************
53 **************************************************************************
54 #cat: bits_6to8 - Takes an array of unsigned characters and bitwise shifts
55 #cat: each value 2 postitions to the left. This is equivalent
56 #cat: to multiplying each value by 4. This puts original values
57 #cat: on the range [0..64) now on the range [0..256). Another
58 #cat: way to say this, is the original 6-bit values now fit in
59 #cat: 8 bits. This is to be used to undo the effects of bits_8to6.
60
61 Input:
62 idata - input array of unsigned characters
63 iw - width (in characters) of the input array
64 ih - height (in characters) of the input array
65 Output:
66 idata - contains the bit-shifted results
67 **************************************************************************/
bits_6to8(unsigned char * idata,const int iw,const int ih)68 void bits_6to8(unsigned char *idata, const int iw, const int ih)
69 {
70 int i, isize;
71 unsigned char *iptr;
72
73 isize = iw * ih;
74 iptr = idata;
75 for(i = 0; i < isize; i++){
76 /* Multiply every pixel value by 4 so that [0..64) -> [0..255) */
77 *iptr++ <<= 2;
78 }
79 }
80
81 /*************************************************************************
82 **************************************************************************
83 #cat: bits_8to6 - Takes an array of unsigned characters and bitwise shifts
84 #cat: each value 2 postitions to the right. This is equivalent
85 #cat: to dividing each value by 4. This puts original values
86 #cat: on the range [0..256) now on the range [0..64). Another
87 #cat: way to say this, is the original 8-bit values now fit in
88 #cat: 6 bits. I would really like to make this dependency
89 #cat: go away.
90
91 Input:
92 idata - input array of unsigned characters
93 iw - width (in characters) of the input array
94 ih - height (in characters) of the input array
95 Output:
96 idata - contains the bit-shifted results
97 **************************************************************************/
bits_8to6(unsigned char * idata,const int iw,const int ih)98 void bits_8to6(unsigned char *idata, const int iw, const int ih)
99 {
100 int i, isize;
101 unsigned char *iptr;
102
103 isize = iw * ih;
104 iptr = idata;
105 for(i = 0; i < isize; i++){
106 /* Divide every pixel value by 4 so that [0..256) -> [0..64) */
107 *iptr++ >>= 2;
108 }
109 }
110
111 /*************************************************************************
112 **************************************************************************
113 #cat: gray2bin - Takes an 8-bit threshold value and two 8-bit pixel values.
114 #cat: Those pixels in the image less than the threhsold are set
115 #cat: to the first specified pixel value, whereas those pixels
116 #cat: greater than or equal to the threshold are set to the second
117 #cat: specified pixel value. On application for this routine is
118 #cat: to convert binary images from 8-bit pixels valued {0,255} to
119 #cat: {1,0} and vice versa.
120
121 Input:
122 thresh - 8-bit pixel threshold
123 less_pix - pixel value used when image pixel is < threshold
124 greater_pix - pixel value used when image pixel is >= threshold
125 bdata - 8-bit image data
126 iw - width (in pixels) of the image
127 ih - height (in pixels) of the image
128 Output:
129 bdata - altered 8-bit image data
130 **************************************************************************/
gray2bin(const int thresh,const int less_pix,const int greater_pix,unsigned char * bdata,const int iw,const int ih)131 void gray2bin(const int thresh, const int less_pix, const int greater_pix,
132 unsigned char *bdata, const int iw, const int ih)
133 {
134 int i;
135
136 for(i = 0; i < iw*ih; i++){
137 if(bdata[i] >= thresh)
138 bdata[i] = (unsigned char)greater_pix;
139 else
140 bdata[i] = (unsigned char)less_pix;
141 }
142 }
143
144 /*************************************************************************
145 **************************************************************************
146 #cat: pad_uchar_image - Copies an 8-bit grayscale images into a larger
147 #cat: output image centering the input image so as to
148 #cat: add a specified amount of pixel padding along the
149 #cat: entire perimeter of the input image. The amount of
150 #cat: pixel padding and the intensity of the pixel padding
151 #cat: are specified. An alternative to padding with a
152 #cat: constant intensity would be to copy the edge pixels
153 #cat: of the centered image into the adjacent pad area.
154
155 Input:
156 idata - input 8-bit grayscale image
157 iw - width (in pixels) of the input image
158 ih - height (in pixels) of the input image
159 pad - size of padding (in pixels) to be added
160 pad_value - intensity of the padded area
161 Output:
162 optr - points to the newly padded image
163 ow - width (in pixels) of the padded image
164 oh - height (in pixels) of the padded image
165 Return Code:
166 Zero - successful completion
167 Negative - system error
168 **************************************************************************/
pad_uchar_image(unsigned char ** optr,int * ow,int * oh,unsigned char * idata,const int iw,const int ih,const int pad,const int pad_value)169 int pad_uchar_image(unsigned char **optr, int *ow, int *oh,
170 unsigned char *idata, const int iw, const int ih,
171 const int pad, const int pad_value)
172 {
173 unsigned char *pdata, *pptr, *iptr;
174 int i, pw, ph;
175 int pad2, psize;
176
177 /* Account for pad on both sides of image */
178 pad2 = pad<<1;
179
180 /* Compute new pad sizes */
181 pw = iw + pad2;
182 ph = ih + pad2;
183 psize = pw * ph;
184
185 /* Allocate padded image */
186 pdata = (unsigned char *)malloc(psize * sizeof(unsigned char));
187 if(pdata == (unsigned char *)NULL){
188 fprintf(stderr, "ERROR : pad_uchar_image : malloc : pdata\n");
189 return(-160);
190 }
191
192 /* Initialize values to a constant PAD value */
193 memset(pdata, pad_value, psize);
194
195 /* Copy input image into padded image one scanline at a time */
196 iptr = idata;
197 pptr = pdata + (pad * pw) + pad;
198 for(i = 0; i < ih; i++){
199 memcpy(pptr, iptr, iw);
200 iptr += iw;
201 pptr += pw;
202 }
203
204 *optr = pdata;
205 *ow = pw;
206 *oh = ph;
207 return(0);
208 }
209
210 /*************************************************************************
211 **************************************************************************
212 #cat: fill_holes - Takes an input image and analyzes triplets of horizontal
213 #cat: pixels first and then triplets of vertical pixels, filling
214 #cat: in holes of width 1. A hole is defined as the case where
215 #cat: the neighboring 2 pixels are equal, AND the center pixel
216 #cat: is different. Each hole is filled with the value of its
217 #cat: immediate neighbors. This routine modifies the input image.
218
219 Input:
220 bdata - binary image data to be processed
221 iw - width (in pixels) of the binary input image
222 ih - height (in pixels) of the binary input image
223 Output:
224 bdata - points to the results
225 **************************************************************************/
fill_holes(unsigned char * bdata,const int iw,const int ih)226 void fill_holes(unsigned char *bdata, const int iw, const int ih)
227 {
228 int ix, iy, iw2;
229 unsigned char *lptr, *mptr, *rptr, *tptr, *bptr, *sptr;
230
231 /* 1. Fill 1-pixel wide holes in horizontal runs first ... */
232 sptr = bdata + 1;
233 /* Foreach row in image ... */
234 for(iy = 0; iy < ih; iy++){
235 /* Initialize pointers to start of next line ... */
236 lptr = sptr-1; /* Left pixel */
237 mptr = sptr; /* Middle pixel */
238 rptr = sptr+1; /* Right pixel */
239 /* Foreach column in image (less far left and right pixels) ... */
240 for(ix = 1; ix < iw-1; ix++){
241 /* Do we have a horizontal hole of length 1? */
242 if((*lptr != *mptr) && (*lptr == *rptr)){
243 /* If so, then fill it. */
244 *mptr = *lptr;
245 /* Bump passed right pixel because we know it will not */
246 /* be a hole. */
247 lptr+=2;
248 mptr+=2;
249 rptr+=2;
250 /* We bump ix once here and then the FOR bumps it again. */
251 ix++;
252 }
253 else{
254 /* Otherwise, bump to the next pixel to the right. */
255 lptr++;
256 mptr++;
257 rptr++;
258 }
259 }
260 /* Bump to start of next row. */
261 sptr += iw;
262 }
263
264 /* 2. Now, fill 1-pixel wide holes in vertical runs ... */
265 iw2 = iw<<1;
266 /* Start processing column one row down from the top of the image. */
267 sptr = bdata + iw;
268 /* Foreach column in image ... */
269 for(ix = 0; ix < iw; ix++){
270 /* Initialize pointers to start of next column ... */
271 tptr = sptr-iw; /* Top pixel */
272 mptr = sptr; /* Middle pixel */
273 bptr = sptr+iw; /* Bottom pixel */
274 /* Foreach row in image (less top and bottom row) ... */
275 for(iy = 1; iy < ih-1; iy++){
276 /* Do we have a vertical hole of length 1? */
277 if((*tptr != *mptr) && (*tptr == *bptr)){
278 /* If so, then fill it. */
279 *mptr = *tptr;
280 /* Bump passed bottom pixel because we know it will not */
281 /* be a hole. */
282 tptr+=iw2;
283 mptr+=iw2;
284 bptr+=iw2;
285 /* We bump iy once here and then the FOR bumps it again. */
286 iy++;
287 }
288 else{
289 /* Otherwise, bump to the next pixel below. */
290 tptr+=iw;
291 mptr+=iw;
292 bptr+=iw;
293 }
294 }
295 /* Bump to start of next column. */
296 sptr++;
297 }
298 }
299
300 /*************************************************************************
301 **************************************************************************
302 #cat: free_path - Traverses a straight line between 2 pixel points in an
303 #cat: image and determines if a "free path" exists between the
304 #cat: 2 points by counting the number of pixel value transitions
305 #cat: between adjacent pixels along the trajectory.
306
307 Input:
308 x1 - x-pixel coord of first point
309 y1 - y-pixel coord of first point
310 x2 - x-pixel coord of second point
311 y2 - y-pixel coord of second point
312 bdata - binary image data (0==while & 1==black)
313 iw - width (in pixels) of image
314 ih - height (in pixels) of image
315 lfsparms - parameters and threshold for controlling LFS
316 Return Code:
317 TRUE - free path determined to exist
318 FALSE - free path determined not to exist
319 Negative - system error
320 **************************************************************************/
free_path(const int x1,const int y1,const int x2,const int y2,unsigned char * bdata,const int iw,const int ih,const LFSPARMS * lfsparms)321 int free_path(const int x1, const int y1, const int x2, const int y2,
322 unsigned char *bdata, const int iw, const int ih,
323 const LFSPARMS *lfsparms)
324 {
325 int *x_list, *y_list, num;
326 int ret;
327 int i, trans, preval, nextval;
328
329 /* Compute points along line segment between the two points. */
330 if((ret = line_points(&x_list, &y_list, &num, x1, y1, x2, y2)))
331 return(ret);
332
333 /* Intialize the number of transitions to 0. */
334 trans = 0;
335 /* Get the pixel value of first point along line segment. */
336 preval = *(bdata+(y1*iw)+x1);
337
338 /* Foreach remaining point along line segment ... */
339 for(i = 1; i < num; i++){
340 /* Get pixel value of next point along line segment. */
341 nextval = *(bdata+(y_list[i]*iw)+x_list[i]);
342
343 /* If next pixel value different from previous pixel value ... */
344 if(nextval != preval){
345 /* Then we have detected a transition, so bump counter. */
346 trans++;
347 /* If number of transitions seen > than threshold (ex. 2) ... */
348 if(trans > lfsparms->maxtrans){
349 /* Deallocate the line segment's coordinate lists. */
350 free(x_list);
351 free(y_list);
352 /* Return free path to be FALSE. */
353 return(FALSE);
354 }
355 /* Otherwise, maximum number of transitions not yet exceeded. */
356 /* Assign the next pixel value to the previous pixel value. */
357 preval = nextval;
358 }
359 /* Otherwise, no transition detected this interation. */
360
361 }
362
363 /* If we get here we did not exceed the maximum allowable number */
364 /* of transitions. So, deallocate the line segment's coordinate lists. */
365 free(x_list);
366 free(y_list);
367
368 /* Return free path to be TRUE. */
369 return(TRUE);
370 }
371
372 /*************************************************************************
373 **************************************************************************
374 #cat: search_in_direction - Takes a specified maximum number of steps in a
375 #cat: specified direction looking for the first occurence of
376 #cat: a pixel with specified value. (Once found, adjustments
377 #cat: are potentially made to make sure the resulting pixel
378 #cat: and its associated edge pixel are 4-connected.)
379
380 Input:
381 pix - value of pixel to be searched for
382 strt_x - x-pixel coord to start search
383 strt_y - y-pixel coord to start search
384 delta_x - increment in x for each step
385 delta_y - increment in y for each step
386 maxsteps - maximum number of steps to conduct search
387 bdata - binary image data (0==while & 1==black)
388 iw - width (in pixels) of image
389 ih - height (in pixels) of image
390 Output:
391 ox - x coord of located pixel
392 oy - y coord of located pixel
393 oex - x coord of associated edge pixel
394 oey - y coord of associated edge pixel
395 Return Code:
396 TRUE - pixel of specified value found
397 FALSE - pixel of specified value NOT found
398 **************************************************************************/
search_in_direction(int * ox,int * oy,int * oex,int * oey,const int pix,const int strt_x,const int strt_y,const double delta_x,const double delta_y,const int maxsteps,unsigned char * bdata,const int iw,const int ih)399 int search_in_direction(int *ox, int *oy, int *oex, int *oey, const int pix,
400 const int strt_x, const int strt_y,
401 const double delta_x, const double delta_y, const int maxsteps,
402 unsigned char *bdata, const int iw, const int ih)
403 {
404
405 int i, x, y, px, py;
406 double fx, fy;
407
408 /* Set previous point to starting point. */
409 px = strt_x;
410 py = strt_y;
411 /* Set floating point accumulators to starting point. */
412 fx = (double)strt_x;
413 fy = (double)strt_y;
414
415 /* Foreach step up to the specified maximum ... */
416 for(i = 0; i < maxsteps; i++){
417
418 /* Increment accumulators. */
419 fx += delta_x;
420 fy += delta_y;
421 /* Round to get next step. */
422 x = sround(fx);
423 y = sround(fy);
424
425 /* If we stepped outside the image boundaries ... */
426 if((x < 0) || (x >= iw) ||
427 (y < 0) || (y >= ih)){
428 /* Return FALSE (we did not find what we were looking for). */
429 *ox = -1;
430 *oy = -1;
431 *oex = -1;
432 *oey = -1;
433 return(FALSE);
434 }
435
436 /* Otherwise, test to see if we found our pixel with value 'pix'. */
437 if(*(bdata+(y*iw)+x) == pix){
438 /* The previous and current pixels form a feature, edge pixel */
439 /* pair, which we would like to use for edge following. The */
440 /* previous pixel may be a diagonal neighbor however to the */
441 /* current pixel, in which case the pair could not be used by */
442 /* the contour tracing (which requires the edge pixel in the */
443 /* pair neighbor to the N,S,E or W. */
444 /* This routine adjusts the pair so that the results may be */
445 /* used by the contour tracing. */
446 fix_edge_pixel_pair(&x, &y, &px, &py, bdata, iw, ih);
447
448 /* Return TRUE (we found what we were looking for). */
449 *ox = x;
450 *oy = y;
451 *oex = px;
452 *oey = py;
453 return(TRUE);
454 }
455
456 /* Otherwise, still haven't found pixel with desired value, */
457 /* so set current point to previous and take another step. */
458 px = x;
459 py = y;
460 }
461
462 /* Return FALSE (we did not find what we were looking for). */
463 *ox = -1;
464 *oy = -1;
465 *oex = -1;
466 *oey = -1;
467 return(FALSE);
468 }
469
470