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: QUALITY.C
28 AUTHOR: Michael D. Garris
29 DATE: 09/25/2000
30 UPDATED: 03/16/2005 by MDG
31
32 Contains routines responsible for assessing minutia quality
33 and assigning different reliability measures. These routines
34 are primarily to support the rejection of bad minutiae.
35
36 ***********************************************************************
37 ROUTINES:
38 gen_quality_map()
39 combined_minutia_quality()
40 grayscale_reliability()
41 get_neighborhood_stats()
42
43 ***********************************************************************/
44
45 #include <stdio.h>
46 #include <stdlib.h>
47 #include <string.h>
48 #include <math.h>
49 #include <lfs.h>
50
51 /***********************************************************************
52 ************************************************************************
53 #cat: gen_quality_map - Takes a direction map, low contrast map, low ridge
54 #cat: flow map, and high curvature map, and combines them
55 #cat: into a single map containing 5 levels of decreasing
56 #cat: quality. This is done through a set of heuristics.
57
58 Code originally written by Austin Hicklin for FBI ATU
59 Modified by Michael D. Garris (NIST) Sept. 1, 2000
60
61 Set quality of 0(unusable)..4(good) (I call these grades A..F)
62 0/F: low contrast OR no direction
63 1/D: low flow OR high curve
64 (with low contrast OR no direction neighbor)
65 (or within NEIGHBOR_DELTA of edge)
66 2/C: low flow OR high curve
67 (or good quality with low contrast/no direction neighbor)
68 3/B: good quality with low flow / high curve neighbor
69 4/A: good quality (none of the above)
70
71 Generally, the features in A/B quality are useful, the C/D quality
72 ones are not.
73
74 Input:
75 direction_map - map with blocks assigned dominant ridge flow direction
76 low_contrast_map - map with blocks flagged as low contrast
77 low_flow_map - map with blocks flagged as low ridge flow
78 high_curve_map - map with blocks flagged as high curvature
79 map_w - width (in blocks) of the maps
80 map_h - height (in blocks) of the maps
81 Output:
82 oqmap - points to new quality map
83 Return Code:
84 Zero - successful completion
85 Negative - system error
86 ************************************************************************/
gen_quality_map(int ** oqmap,int * direction_map,int * low_contrast_map,int * low_flow_map,int * high_curve_map,const int map_w,const int map_h)87 int gen_quality_map(int **oqmap, int *direction_map, int *low_contrast_map,
88 int *low_flow_map, int *high_curve_map,
89 const int map_w, const int map_h)
90 {
91
92 int *QualMap;
93 int thisX, thisY;
94 int compX, compY;
95 int arrayPos, arrayPos2;
96 int QualOffset;
97
98 QualMap = (int *)malloc(map_w * map_h * sizeof(int));
99 if(QualMap == (int *)NULL){
100 fprintf(stderr, "ERROR : gen_quality_map : malloc : QualMap\n");
101 return(-2);
102 }
103
104 /* Foreach row of blocks in maps ... */
105 for(thisY=0; thisY<map_h; thisY++){
106 /* Foreach block in current row ... */
107 for(thisX=0; thisX<map_w; thisX++) {
108 /* Compute block index. */
109 arrayPos=(thisY*map_w)+thisX;
110 /* If current block has low contrast or INVALID direction ... */
111 if(low_contrast_map[arrayPos] || direction_map[arrayPos]<0)
112 /* Set block's quality to 0/F. */
113 QualMap[arrayPos]=0;
114 else{
115 /* Set baseline quality before looking at neighbors */
116 /* (will subtract QualOffset below) */
117 /* If current block has low flow or high curvature ... */
118 if(low_flow_map[arrayPos] || high_curve_map[arrayPos])
119 /* Set block's quality initially to 3/B. */
120 QualMap[arrayPos] = 3; /* offset will be -1..-2 */
121 /* Otherwise, block is NOT low flow AND NOT high curvature... */
122 else
123 /* Set block's quality to 4/A. */
124 QualMap[arrayPos]=4; /* offset will be 0..-2 */
125
126 /* If block within NEIGHBOR_DELTA of edge ... */
127 if(thisY < NEIGHBOR_DELTA || thisY > map_h - 1 - NEIGHBOR_DELTA ||
128 thisX < NEIGHBOR_DELTA || thisX > map_w - 1 - NEIGHBOR_DELTA)
129 /* Set block's quality to 1/E. */
130 QualMap[arrayPos]=1;
131 /* Otherwise, test neighboring blocks ... */
132 else{
133 /* Initialize quality adjustment to 0. */
134 QualOffset=0;
135 /* Foreach row in neighborhood ... */
136 for(compY=thisY-NEIGHBOR_DELTA;
137 compY<=thisY+NEIGHBOR_DELTA;compY++){
138 /* Foreach block in neighborhood */
139 /* (including current block)... */
140 for(compX=thisX-NEIGHBOR_DELTA;
141 compX<=thisX+NEIGHBOR_DELTA;compX++) {
142 /* Compute neighboring block's index. */
143 arrayPos2 = (compY*map_w)+compX;
144 /* If neighbor block (which might be itself) has */
145 /* low contrast or INVALID direction .. */
146 if(low_contrast_map[arrayPos2] ||
147 direction_map[arrayPos2]<0) {
148 /* Set quality adjustment to -2. */
149 QualOffset=-2;
150 /* Done with neighborhood row. */
151 break;
152 }
153 /* Otherwise, if neighbor block (which might be */
154 /* itself) has low flow or high curvature ... */
155 else if(low_flow_map[arrayPos2] ||
156 high_curve_map[arrayPos2]) {
157 /* Set quality to -1 if not already -2. */
158 QualOffset=min(QualOffset,-1);
159 }
160 }
161 }
162 /* Decrement minutia quality by neighborhood adjustment. */
163 QualMap[arrayPos]+=QualOffset;
164 }
165 }
166 }
167 }
168
169 /* Set output pointer. */
170 *oqmap = QualMap;
171 /* Return normally. */
172 return(0);
173 }
174
175 /***********************************************************************
176 ************************************************************************
177 #cat: get_neighborhood_stats - Given a minutia point, computes the mean
178 #cat: and stdev of the 8-bit grayscale pixels values in a
179 #cat: surrounding neighborhood with specified radius.
180
181 Code originally written by Austin Hicklin for FBI ATU
182 Modified by Michael D. Garris (NIST) Sept. 25, 2000
183
184 Input:
185 minutia - structure containing detected minutia
186 idata - 8-bit grayscale fingerprint image
187 iw - width (in pixels) of the image
188 ih - height (in pixels) of the image
189 radius_pix - pixel radius of surrounding neighborhood
190 Output:
191 mean - mean of neighboring pixels
192 stdev - standard deviation of neighboring pixels
193 ************************************************************************/
get_neighborhood_stats(double * mean,double * stdev,MINUTIA * minutia,unsigned char * idata,const int iw,const int ih,const int radius_pix)194 static void get_neighborhood_stats(double *mean, double *stdev, MINUTIA *minutia,
195 unsigned char *idata, const int iw, const int ih,
196 const int radius_pix)
197 {
198 int i, x, y, rows, cols;
199 int n = 0, sumX = 0, sumXX = 0;
200 int histogram[256];
201
202 /* Zero out histogram. */
203 memset(histogram, 0, 256 * sizeof(int));
204
205 /* Set minutia's coordinate variables. */
206 x = minutia->x;
207 y = minutia->y;
208
209
210 /* If minutiae point is within sampleboxsize distance of image border, */
211 /* a value of 0 reliability is returned. */
212 if ((x < radius_pix) || (x > iw-radius_pix-1) ||
213 (y < radius_pix) || (y > ih-radius_pix-1)) {
214 *mean = 0.0;
215 *stdev = 0.0;
216 return;
217
218 }
219
220 /* Foreach row in neighborhood ... */
221 for(rows = y - radius_pix;
222 rows <= y + radius_pix;
223 rows++){
224 /* Foreach column in neighborhood ... */
225 for(cols = x - radius_pix;
226 cols <= x + radius_pix;
227 cols++){
228 /* Bump neighbor's pixel value bin in histogram. */
229 histogram[*(idata+(rows * iw)+cols)]++;
230 }
231 }
232
233 /* Foreach grayscale pixel bin ... */
234 for(i = 0; i < 256; i++){
235 if(histogram[i]){
236 /* Accumulate Sum(X[i]) */
237 sumX += (i * histogram[i]);
238 /* Accumulate Sum(X[i]^2) */
239 sumXX += (i * i * histogram[i]);
240 /* Accumulate N samples */
241 n += histogram[i];
242 }
243 }
244
245 /* Mean = Sum(X[i])/N */
246 *mean = sumX/(double)n;
247 /* Stdev = sqrt((Sum(X[i]^2)/N) - Mean^2) */
248 *stdev = sqrt((sumXX/(double)n) - ((*mean)*(*mean)));
249 }
250
251 /***********************************************************************
252 ************************************************************************
253 #cat: grayscale_reliability - Given a minutia point, computes a reliability
254 #cat: measure from the stdev and mean of its pixel neighborhood.
255
256 Code originally written by Austin Hicklin for FBI ATU
257 Modified by Michael D. Garris (NIST) Sept. 25, 2000
258
259 GrayScaleReliability - reasonable reliability heuristic, returns
260 0.0 .. 1.0 based on stdev and Mean of a localized histogram where
261 "ideal" stdev is >=64; "ideal" Mean is 127. In a 1 ridge radius
262 (11 pixels), if the bytevalue (shade of gray) in the image has a
263 stdev of >= 64 & a mean of 127, returns 1.0 (well defined
264 light & dark areas in equal proportions).
265
266 Input:
267 minutia - structure containing detected minutia
268 idata - 8-bit grayscale fingerprint image
269 iw - width (in pixels) of the image
270 ih - height (in pixels) of the image
271 radius_pix - pixel radius of surrounding neighborhood
272 Return Value:
273 reliability - computed reliability measure
274 ************************************************************************/
grayscale_reliability(MINUTIA * minutia,unsigned char * idata,const int iw,const int ih,const int radius_pix)275 static double grayscale_reliability(MINUTIA *minutia, unsigned char *idata,
276 const int iw, const int ih, const int radius_pix)
277 {
278 double mean, stdev;
279 double reliability;
280
281 get_neighborhood_stats(&mean, &stdev, minutia, idata, iw, ih, radius_pix);
282
283 reliability = min((stdev>IDEALSTDEV ? 1.0 : stdev/(double)IDEALSTDEV),
284 (1.0-(fabs(mean-IDEALMEAN)/(double)IDEALMEAN)));
285
286 return(reliability);
287 }
288
289 /***********************************************************************
290 ************************************************************************
291 #cat: combined_minutia_quality - Combines quality measures derived from
292 #cat: the quality map and neighboring pixel statistics to
293 #cat: infer a reliability measure on the scale [0...1].
294
295 Input:
296 minutiae - structure contining the detected minutia
297 quality_map - map with blocks assigned 1 of 5 quality levels
298 map_w - width (in blocks) of the map
299 map_h - height (in blocks) of the map
300 blocksize - size (in pixels) of each block in the map
301 idata - 8-bit grayscale fingerprint image
302 iw - width (in pixels) of the image
303 ih - height (in pixels) of the image
304 id - depth (in pixels) of the image
305 ppmm - scan resolution of the image in pixels/mm
306 Output:
307 minutiae - updated reliability members
308 Return Code:
309 Zero - successful completion
310 Negative - system error
311 ************************************************************************/
combined_minutia_quality(MINUTIAE * minutiae,int * quality_map,const int mw,const int mh,const int blocksize,unsigned char * idata,const int iw,const int ih,const int id,const double ppmm)312 int combined_minutia_quality(MINUTIAE *minutiae,
313 int *quality_map, const int mw, const int mh, const int blocksize,
314 unsigned char *idata, const int iw, const int ih, const int id,
315 const double ppmm)
316 {
317 int ret, i, index, radius_pix;
318 int *pquality_map, qmap_value;
319 MINUTIA *minutia;
320 double gs_reliability, reliability;
321
322 /* If image is not 8-bit grayscale ... */
323 if(id != 8){
324 fprintf(stderr, "ERROR : combined_miutia_quality : ");
325 fprintf(stderr, "image must pixel depth = %d must be 8 ", id);
326 fprintf(stderr, "to compute reliability\n");
327 return(-2);
328 }
329
330 /* Compute pixel radius of neighborhood based on image's scan resolution. */
331 radius_pix = sround(RADIUS_MM * ppmm);
332
333 /* Expand block map values to pixel map. */
334 if((ret = pixelize_map(&pquality_map, iw, ih,
335 quality_map, mw, mh, blocksize))){
336 return(ret);
337 }
338
339 /* Foreach minutiae detected ... */
340 for(i = 0; i < minutiae->num; i++){
341 /* Assign minutia pointer. */
342 minutia = minutiae->list[i];
343
344 /* Compute reliability from stdev and mean of pixel neighborhood. */
345 gs_reliability = grayscale_reliability(minutia,
346 idata, iw, ih, radius_pix);
347
348 /* Lookup quality map value. */
349 /* Compute minutia pixel index. */
350 index = (minutia->y * iw) + minutia->x;
351 /* Switch on pixel's quality value ... */
352 qmap_value = pquality_map[index];
353
354 /* Combine grayscale reliability and quality map value. */
355 switch(qmap_value){
356 /* Quality A : [50..99]% */
357 case 4 :
358 reliability = 0.50 + (0.49 * gs_reliability);
359 break;
360 /* Quality B : [25..49]% */
361 case 3 :
362 reliability = 0.25 + (0.24 * gs_reliability);
363 break;
364 /* Quality C : [10..24]% */
365 case 2 :
366 reliability = 0.10 + (0.14 * gs_reliability);
367 break;
368 /* Quality D : [5..9]% */
369 case 1 :
370 reliability = 0.05 + (0.04 * gs_reliability);
371 break;
372 /* Quality E : 1% */
373 case 0 :
374 reliability = 0.01;
375 break;
376 /* Error if quality value not in range [0..4]. */
377 default:
378 fprintf(stderr, "ERROR : combined_miutia_quality : ");
379 fprintf(stderr, "unexpected quality map value %d ", qmap_value);
380 fprintf(stderr, "not in range [0..4]\n");
381 free(pquality_map);
382 return(-3);
383 }
384 minutia->reliability = reliability;
385 }
386
387 /* NEW 05-08-2002 */
388 free(pquality_map);
389
390 /* Return normally. */
391 return(0);
392 }
393
394