Line | Branch | Exec | Source |
---|---|---|---|
1 | /******************************************************************************* | ||
2 | |||
3 | License: | ||
4 | This software and/or related materials was developed at the National Institute | ||
5 | of Standards and Technology (NIST) by employees of the Federal Government | ||
6 | in the course of their official duties. Pursuant to title 17 Section 105 | ||
7 | of the United States Code, this software is not subject to copyright | ||
8 | protection and is in the public domain. | ||
9 | |||
10 | This software and/or related materials have been determined to be not subject | ||
11 | to the EAR (see Part 734.3 of the EAR for exact details) because it is | ||
12 | a publicly available technology and software, and is freely distributed | ||
13 | to any interested party with no licensing requirements. Therefore, it is | ||
14 | permissible to distribute this software as a free download from the internet. | ||
15 | |||
16 | Disclaimer: | ||
17 | This software and/or related materials was developed to promote biometric | ||
18 | standards and biometric technology testing for the Federal Government | ||
19 | in accordance with the USA PATRIOT Act and the Enhanced Border Security | ||
20 | and Visa Entry Reform Act. Specific hardware and software products identified | ||
21 | in this software were used in order to perform the software development. | ||
22 | In no case does such identification imply recommendation or endorsement | ||
23 | by the National Institute of Standards and Technology, nor does it imply that | ||
24 | the products and equipment identified are necessarily the best available | ||
25 | for the purpose. | ||
26 | |||
27 | This software and/or related materials are provided "AS-IS" without warranty | ||
28 | of any kind including NO WARRANTY OF PERFORMANCE, MERCHANTABILITY, | ||
29 | NO WARRANTY OF NON-INFRINGEMENT OF ANY 3RD PARTY INTELLECTUAL PROPERTY | ||
30 | or FITNESS FOR A PARTICULAR PURPOSE or for any purpose whatsoever, for the | ||
31 | licensed product, however used. In no event shall NIST be liable for any | ||
32 | damages and/or costs, including but not limited to incidental or consequential | ||
33 | damages of any kind, including economic damage or injury to property and lost | ||
34 | profits, regardless of whether NIST shall be advised, have reason to know, | ||
35 | or in fact shall know of the possibility. | ||
36 | |||
37 | By using this software, you agree to bear all risk relating to quality, | ||
38 | use and performance of the software and/or related materials. You agree | ||
39 | to hold the Government harmless from any claim arising from your use | ||
40 | of the software. | ||
41 | |||
42 | *******************************************************************************/ | ||
43 | |||
44 | |||
45 | /*********************************************************************** | ||
46 | LIBRARY: LFS - NIST Latent Fingerprint System | ||
47 | |||
48 | FILE: DETECT.C | ||
49 | AUTHOR: Michael D. Garris | ||
50 | DATE: 08/16/1999 | ||
51 | UPDATED: 10/04/1999 Version 2 by MDG | ||
52 | UPDATED: 03/16/2005 by MDG | ||
53 | |||
54 | Takes an 8-bit grayscale fingerpinrt image and detects minutiae | ||
55 | as part of the NIST Latent Fingerprint System (LFS). | ||
56 | |||
57 | *********************************************************************** | ||
58 | ROUTINES: | ||
59 | lfs_detect_minutiae() | ||
60 | lfs_detect_minutiae_V2() | ||
61 | |||
62 | ***********************************************************************/ | ||
63 | |||
64 | #include <stdio.h> | ||
65 | #include <lfs.h> | ||
66 | #include <mytime.h> | ||
67 | #include <log.h> | ||
68 | |||
69 | /************************************************************************* | ||
70 | #cat: lfs_detect_minutiae - Takes a grayscale fingerprint image (of arbitrary | ||
71 | #cat: size), and returns a map of directional ridge flow in the image | ||
72 | #cat: (2 versions), a binarized image designating ridges from valleys, | ||
73 | #cat: and a list of minutiae (including position, type, direction, | ||
74 | #cat: neighbors, and ridge counts to neighbors). | ||
75 | |||
76 | Input: | ||
77 | idata - input 8-bit grayscale fingerprint image data | ||
78 | iw - width (in pixels) of the image | ||
79 | ih - height (in pixels) of the image | ||
80 | lfsparms - parameters and thresholds for controlling LFS | ||
81 | Output: | ||
82 | ominutiae - resulting list of minutiae | ||
83 | oimap - resulting IMAP | ||
84 | {invalid (-1) or valid ridge directions} | ||
85 | onmap - resulting NMAP | ||
86 | {invalid (-1), high-curvature (-2), blanked blocks {-3} or | ||
87 | valid ridge directions} | ||
88 | omw - width (in blocks) of image maps | ||
89 | omh - height (in blocks) of image maps | ||
90 | obdata - resulting binarized image | ||
91 | {0 = black pixel (ridge) and 255 = white pixel (valley)} | ||
92 | obw - width (in pixels) of the binary image | ||
93 | obh - height (in pixels) of the binary image | ||
94 | Return Code: | ||
95 | Zero - successful completion | ||
96 | Negative - system error | ||
97 | **************************************************************************/ | ||
98 | |||
99 | /************************************************************************* | ||
100 | #cat: lfs_detect_minutiae_V2 - Takes a grayscale fingerprint image (of | ||
101 | #cat: arbitrary size), and returns a set of image block maps, | ||
102 | #cat: a binarized image designating ridges from valleys, | ||
103 | #cat: and a list of minutiae (including position, reliability, | ||
104 | #cat: type, direction, neighbors, and ridge counts to neighbors). | ||
105 | #cat: The image maps include a ridge flow directional map, | ||
106 | #cat: a map of low contrast blocks, a map of low ridge flow blocks. | ||
107 | #cat: and a map of high-curvature blocks. | ||
108 | |||
109 | Input: | ||
110 | idata - input 8-bit grayscale fingerprint image data | ||
111 | iw - width (in pixels) of the image | ||
112 | ih - height (in pixels) of the image | ||
113 | lfsparms - parameters and thresholds for controlling LFS | ||
114 | |||
115 | Output: | ||
116 | ominutiae - resulting list of minutiae | ||
117 | odmap - resulting Direction Map | ||
118 | {invalid (-1) or valid ridge directions} | ||
119 | olcmap - resulting Low Contrast Map | ||
120 | {low contrast (TRUE), high contrast (FALSE)} | ||
121 | olfmap - resulting Low Ridge Flow Map | ||
122 | {low ridge flow (TRUE), high ridge flow (FALSE)} | ||
123 | ohcmap - resulting High Curvature Map | ||
124 | {high curvature (TRUE), low curvature (FALSE)} | ||
125 | omw - width (in blocks) of image maps | ||
126 | omh - height (in blocks) of image maps | ||
127 | obdata - resulting binarized image | ||
128 | {0 = black pixel (ridge) and 255 = white pixel (valley)} | ||
129 | obw - width (in pixels) of the binary image | ||
130 | obh - height (in pixels) of the binary image | ||
131 | Return Code: | ||
132 | Zero - successful completion | ||
133 | Negative - system error | ||
134 | **************************************************************************/ | ||
135 | 48 | int lfs_detect_minutiae_V2(MINUTIAE **ominutiae, | |
136 | int **odmap, int **olcmap, int **olfmap, int **ohcmap, | ||
137 | int *omw, int *omh, | ||
138 | unsigned char **obdata, int *obw, int *obh, | ||
139 | unsigned char *idata, const int iw, const int ih, | ||
140 | const LFSPARMS *lfsparms) | ||
141 | { | ||
142 | 48 | unsigned char *pdata, *bdata; | |
143 | 48 | int pw, ph, bw, bh; | |
144 | 48 | DIR2RAD *dir2rad; | |
145 | 48 | DFTWAVES *dftwaves; | |
146 | 48 | ROTGRIDS *dftgrids; | |
147 | 48 | ROTGRIDS *dirbingrids; | |
148 | 48 | int *direction_map, *low_contrast_map, *low_flow_map, *high_curve_map; | |
149 | 48 | int mw, mh; | |
150 | 48 | int ret, maxpad; | |
151 | 48 | MINUTIAE *minutiae; | |
152 | |||
153 | 48 | set_timer(total_timer); | |
154 | |||
155 | /******************/ | ||
156 | /* INITIALIZATION */ | ||
157 | /******************/ | ||
158 | |||
159 | /* If LOG_REPORT defined, open log report file. */ | ||
160 |
1/2✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
|
48 | if((ret = open_logfile())) |
161 | /* If system error, exit with error code. */ | ||
162 | return(ret); | ||
163 | |||
164 | /* Determine the maximum amount of image padding required to support */ | ||
165 | /* LFS processes. */ | ||
166 | 96 | maxpad = get_max_padding_V2(lfsparms->windowsize, lfsparms->windowoffset, | |
167 | 48 | lfsparms->dirbin_grid_w, lfsparms->dirbin_grid_h); | |
168 | |||
169 | /* Initialize lookup table for converting integer directions */ | ||
170 | /* to angles in radians. */ | ||
171 |
1/2✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
|
48 | if((ret = init_dir2rad(&dir2rad, lfsparms->num_directions))){ |
172 | /* Free memory allocated to this point. */ | ||
173 | return(ret); | ||
174 | } | ||
175 | |||
176 | /* Initialize wave form lookup tables for DFT analyses. */ | ||
177 | /* used for direction binarization. */ | ||
178 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
|
48 | if((ret = init_dftwaves(&dftwaves, g_dft_coefs, lfsparms->num_dft_waves, |
179 | 48 | lfsparms->windowsize))){ | |
180 | /* Free memory allocated to this point. */ | ||
181 | ✗ | free_dir2rad(dir2rad); | |
182 | ✗ | return(ret); | |
183 | } | ||
184 | |||
185 | /* Initialize lookup table for pixel offsets to rotated grids */ | ||
186 | /* used for DFT analyses. */ | ||
187 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
|
48 | if((ret = init_rotgrids(&dftgrids, iw, ih, maxpad, |
188 | 48 | lfsparms->start_dir_angle, lfsparms->num_directions, | |
189 | 48 | lfsparms->windowsize, lfsparms->windowsize, | |
190 | RELATIVE2ORIGIN))){ | ||
191 | /* Free memory allocated to this point. */ | ||
192 | ✗ | free_dir2rad(dir2rad); | |
193 | ✗ | free_dftwaves(dftwaves); | |
194 | ✗ | return(ret); | |
195 | } | ||
196 | |||
197 | /* Pad input image based on max padding. */ | ||
198 |
1/2✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
|
48 | if(maxpad > 0){ /* May not need to pad at all */ |
199 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
|
48 | if((ret = pad_uchar_image(&pdata, &pw, &ph, idata, iw, ih, |
200 | 48 | maxpad, lfsparms->pad_value))){ | |
201 | /* Free memory allocated to this point. */ | ||
202 | ✗ | free_dir2rad(dir2rad); | |
203 | ✗ | free_dftwaves(dftwaves); | |
204 | ✗ | free_rotgrids(dftgrids); | |
205 | ✗ | return(ret); | |
206 | } | ||
207 | } | ||
208 | else{ | ||
209 | /* If padding is unnecessary, then copy the input image. */ | ||
210 | ✗ | pdata = (unsigned char *)g_malloc(iw * ih); | |
211 | ✗ | memcpy(pdata, idata, iw*ih); | |
212 | ✗ | pw = iw; | |
213 | ✗ | ph = ih; | |
214 | } | ||
215 | |||
216 | /* Scale input image to 6 bits [0..63] */ | ||
217 | /* !!! Would like to remove this dependency eventualy !!! */ | ||
218 | /* But, the DFT computations will need to be changed, and */ | ||
219 | /* could not get this work upon first attempt. Also, if not */ | ||
220 | /* careful, I think accumulated power magnitudes may overflow */ | ||
221 | /* doubles. */ | ||
222 | 48 | bits_8to6(pdata, pw, ph); | |
223 | |||
224 | 48 | print2log("\nINITIALIZATION AND PADDING DONE\n"); | |
225 | |||
226 | /******************/ | ||
227 | /* MAPS */ | ||
228 | /******************/ | ||
229 | 48 | set_timer(imap_timer); | |
230 | |||
231 | /* Generate block maps from the input image. */ | ||
232 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
|
48 | if((ret = gen_image_maps(&direction_map, &low_contrast_map, |
233 | &low_flow_map, &high_curve_map, &mw, &mh, | ||
234 | pdata, pw, ph, dir2rad, dftwaves, dftgrids, lfsparms))){ | ||
235 | /* Free memory allocated to this point. */ | ||
236 | ✗ | free_dir2rad(dir2rad); | |
237 | ✗ | free_dftwaves(dftwaves); | |
238 | ✗ | free_rotgrids(dftgrids); | |
239 | ✗ | g_free(pdata); | |
240 | ✗ | return(ret); | |
241 | } | ||
242 | /* Deallocate working memories. */ | ||
243 | 48 | free_dir2rad(dir2rad); | |
244 | 48 | free_dftwaves(dftwaves); | |
245 | 48 | free_rotgrids(dftgrids); | |
246 | |||
247 | 48 | print2log("\nMAPS DONE\n"); | |
248 | |||
249 | 48 | time_accum(imap_timer, imap_time); | |
250 | |||
251 | /******************/ | ||
252 | /* BINARIZARION */ | ||
253 | /******************/ | ||
254 | 48 | set_timer(bin_timer); | |
255 | |||
256 | /* Initialize lookup table for pixel offsets to rotated grids */ | ||
257 | /* used for directional binarization. */ | ||
258 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
|
48 | if((ret = init_rotgrids(&dirbingrids, iw, ih, maxpad, |
259 | 48 | lfsparms->start_dir_angle, lfsparms->num_directions, | |
260 | 48 | lfsparms->dirbin_grid_w, lfsparms->dirbin_grid_h, | |
261 | RELATIVE2CENTER))){ | ||
262 | /* Free memory allocated to this point. */ | ||
263 | ✗ | g_free(pdata); | |
264 | ✗ | g_free(direction_map); | |
265 | ✗ | g_free(low_contrast_map); | |
266 | ✗ | g_free(low_flow_map); | |
267 | ✗ | g_free(high_curve_map); | |
268 | ✗ | return(ret); | |
269 | } | ||
270 | |||
271 | /* Binarize input image based on NMAP information. */ | ||
272 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
|
48 | if((ret = binarize_V2(&bdata, &bw, &bh, |
273 | pdata, pw, ph, direction_map, mw, mh, | ||
274 | dirbingrids, lfsparms))){ | ||
275 | /* Free memory allocated to this point. */ | ||
276 | ✗ | g_free(pdata); | |
277 | ✗ | g_free(direction_map); | |
278 | ✗ | g_free(low_contrast_map); | |
279 | ✗ | g_free(low_flow_map); | |
280 | ✗ | g_free(high_curve_map); | |
281 | ✗ | free_rotgrids(dirbingrids); | |
282 | ✗ | return(ret); | |
283 | } | ||
284 | |||
285 | /* Deallocate working memory. */ | ||
286 | 48 | free_rotgrids(dirbingrids); | |
287 | |||
288 | /* Check dimension of binary image. If they are different from */ | ||
289 | /* the input image, then ERROR. */ | ||
290 |
2/4✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 48 times.
|
48 | if((iw != bw) || (ih != bh)){ |
291 | /* Free memory allocated to this point. */ | ||
292 | ✗ | g_free(pdata); | |
293 | ✗ | g_free(direction_map); | |
294 | ✗ | g_free(low_contrast_map); | |
295 | ✗ | g_free(low_flow_map); | |
296 | ✗ | g_free(high_curve_map); | |
297 | ✗ | g_free(bdata); | |
298 | ✗ | fprintf(stderr, "ERROR : lfs_detect_minutiae_V2 :"); | |
299 | ✗ | fprintf(stderr,"binary image has bad dimensions : %d, %d\n", | |
300 | bw, bh); | ||
301 | ✗ | return(-581); | |
302 | } | ||
303 | |||
304 | 48 | print2log("\nBINARIZATION DONE\n"); | |
305 | |||
306 | 48 | time_accum(bin_timer, bin_time); | |
307 | |||
308 | /******************/ | ||
309 | /* DETECTION */ | ||
310 | /******************/ | ||
311 | 48 | set_timer(minutia_timer); | |
312 | |||
313 | /* Convert 8-bit grayscale binary image [0,255] to */ | ||
314 | /* 8-bit binary image [0,1]. */ | ||
315 | 48 | gray2bin(1, 1, 0, bdata, iw, ih); | |
316 | |||
317 | /* Allocate initial list of minutia pointers. */ | ||
318 |
1/2✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
|
48 | if((ret = alloc_minutiae(&minutiae, MAX_MINUTIAE))){ |
319 | return(ret); | ||
320 | } | ||
321 | |||
322 | /* Detect the minutiae in the binarized image. */ | ||
323 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
|
48 | if((ret = detect_minutiae_V2(minutiae, bdata, iw, ih, |
324 | direction_map, low_flow_map, high_curve_map, | ||
325 | mw, mh, lfsparms))){ | ||
326 | /* Free memory allocated to this point. */ | ||
327 | ✗ | g_free(pdata); | |
328 | ✗ | g_free(direction_map); | |
329 | ✗ | g_free(low_contrast_map); | |
330 | ✗ | g_free(low_flow_map); | |
331 | ✗ | g_free(high_curve_map); | |
332 | ✗ | g_free(bdata); | |
333 | ✗ | return(ret); | |
334 | } | ||
335 | |||
336 | 48 | time_accum(minutia_timer, minutia_time); | |
337 | |||
338 | 48 | set_timer(rm_minutia_timer); | |
339 | |||
340 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
|
48 | if((ret = remove_false_minutia_V2(minutiae, bdata, iw, ih, |
341 | direction_map, low_flow_map, high_curve_map, mw, mh, | ||
342 | lfsparms))){ | ||
343 | /* Free memory allocated to this point. */ | ||
344 | ✗ | g_free(pdata); | |
345 | ✗ | g_free(direction_map); | |
346 | ✗ | g_free(low_contrast_map); | |
347 | ✗ | g_free(low_flow_map); | |
348 | ✗ | g_free(high_curve_map); | |
349 | ✗ | g_free(bdata); | |
350 | ✗ | free_minutiae(minutiae); | |
351 | ✗ | return(ret); | |
352 | } | ||
353 | |||
354 | 48 | print2log("\nMINUTIA DETECTION DONE\n"); | |
355 | |||
356 | 48 | time_accum(rm_minutia_timer, rm_minutia_time); | |
357 | |||
358 | /******************/ | ||
359 | /* RIDGE COUNTS */ | ||
360 | /******************/ | ||
361 | 48 | set_timer(ridge_count_timer); | |
362 | |||
363 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
|
48 | if((ret = count_minutiae_ridges(minutiae, bdata, iw, ih, lfsparms))){ |
364 | /* Free memory allocated to this point. */ | ||
365 | ✗ | g_free(pdata); | |
366 | ✗ | g_free(direction_map); | |
367 | ✗ | g_free(low_contrast_map); | |
368 | ✗ | g_free(low_flow_map); | |
369 | ✗ | g_free(high_curve_map); | |
370 | ✗ | free_minutiae(minutiae); | |
371 | ✗ | return(ret); | |
372 | } | ||
373 | |||
374 | |||
375 | 48 | print2log("\nNEIGHBOR RIDGE COUNT DONE\n"); | |
376 | |||
377 | 48 | time_accum(ridge_count_timer, ridge_count_time); | |
378 | |||
379 | /******************/ | ||
380 | /* WRAP-UP */ | ||
381 | /******************/ | ||
382 | |||
383 | /* Convert 8-bit binary image [0,1] to 8-bit */ | ||
384 | /* grayscale binary image [0,255]. */ | ||
385 | 48 | gray2bin(1, 255, 0, bdata, iw, ih); | |
386 | |||
387 | /* Deallocate working memory. */ | ||
388 | 48 | g_free(pdata); | |
389 | |||
390 | /* Assign results to output pointers. */ | ||
391 | 48 | *odmap = direction_map; | |
392 | 48 | *olcmap = low_contrast_map; | |
393 | 48 | *olfmap = low_flow_map; | |
394 | 48 | *ohcmap = high_curve_map; | |
395 | 48 | *omw = mw; | |
396 | 48 | *omh = mh; | |
397 | 48 | *obdata = bdata; | |
398 | 48 | *obw = bw; | |
399 | 48 | *obh = bh; | |
400 | 48 | *ominutiae = minutiae; | |
401 | |||
402 | 48 | time_accum(total_timer, total_time); | |
403 | |||
404 | /******************/ | ||
405 | /* PRINT TIMINGS */ | ||
406 | /******************/ | ||
407 | /* These Timings will print when TIMER is defined. */ | ||
408 | /* print MAP generation timing statistics */ | ||
409 | 48 | print_time(stderr, "TIMER: MAPS time = %f (secs)\n", imap_time); | |
410 | /* print binarization timing statistics */ | ||
411 | 48 | print_time(stderr, "TIMER: Binarization time = %f (secs)\n", bin_time); | |
412 | /* print minutia detection timing statistics */ | ||
413 | 48 | print_time(stderr, "TIMER: Minutia Detection time = %f (secs)\n", | |
414 | 48 | minutia_time); | |
415 | /* print minutia removal timing statistics */ | ||
416 | 48 | print_time(stderr, "TIMER: Minutia Removal time = %f (secs)\n", | |
417 | 48 | rm_minutia_time); | |
418 | /* print neighbor ridge count timing statistics */ | ||
419 | 48 | print_time(stderr, "TIMER: Neighbor Ridge Counting time = %f (secs)\n", | |
420 | 48 | ridge_count_time); | |
421 | /* print total timing statistics */ | ||
422 | 48 | print_time(stderr, "TIMER: Total time = %f (secs)\n", total_time); | |
423 | |||
424 | /* If LOG_REPORT defined, close log report file. */ | ||
425 | 48 | if((ret = close_logfile())) | |
426 | return(ret); | ||
427 | |||
428 | return(0); | ||
429 | } | ||
430 | |||
431 |