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: REMOVE.C
28 AUTHOR: Michael D. Garris
29 DATE: 08/02/1999
30 UPDATED: 10/04/1999 Version 2 by MDG
31 UPDATED: 03/16/2005 by MDG
32
33 Contains routines responsible for detecting and removing false
34 minutiae as part of the NIST Latent Fingerprint System (LFS).
35
36 ***********************************************************************
37 ROUTINES:
38 remove_false_minutia_V2()
39 remove_holes()
40 remove_hooks()
41 remove_islands_and_lakes()
42 remove_malformations()
43 remove_near_invblock_V2()
44 remove_pointing_invblock_V2()
45 remove_overlaps()
46 remove_pores_V2()
47 remove_or_adjust_side_minutiae_V2()
48
49 ***********************************************************************/
50
51 #include <stdio.h>
52 #include <lfs.h>
53 #include <log.h>
54
55 /*************************************************************************
56 **************************************************************************
57 #cat: remove_holes - Removes minutia points on small loops around valleys.
58
59 Input:
60 minutiae - list of true and false minutiae
61 bdata - binary image data (0==while & 1==black)
62 iw - width (in pixels) of image
63 ih - height (in pixels) of image
64 lfsparms - parameters and thresholds for controlling LFS
65 Output:
66 minutiae - list of pruned minutiae
67 Return Code:
68 Zero - successful completion
69 Negative - system error
70 **************************************************************************/
remove_holes(MINUTIAE * minutiae,unsigned char * bdata,const int iw,const int ih,const LFSPARMS * lfsparms)71 static int remove_holes(MINUTIAE *minutiae,
72 unsigned char *bdata, const int iw, const int ih,
73 const LFSPARMS *lfsparms)
74 {
75 int i, ret;
76 MINUTIA *minutia;
77
78 print2log("\nREMOVING HOLES:\n");
79
80 i = 0;
81 /* Foreach minutia remaining in list ... */
82 while(i < minutiae->num){
83 /* Assign a temporary pointer. */
84 minutia = minutiae->list[i];
85 /* If current minutia is a bifurcation ... */
86 if(minutia->type == BIFURCATION){
87 /* Check to see if it is on a loop of specified length (ex. 15). */
88 ret = on_loop(minutia, lfsparms->small_loop_len, bdata, iw, ih);
89 /* If minutia is on a loop ... or loop test IGNORED */
90 if((ret == LOOP_FOUND) || (ret == IGNORE)){
91
92 print2log("%d,%d RM\n", minutia->x, minutia->y);
93
94 /* Then remove the minutia from list. */
95 if((ret = remove_minutia(i, minutiae))){
96 /* Return error code. */
97 return(ret);
98 }
99 /* No need to advance because next minutia has "slid" */
100 /* into position pointed to by 'i'. */
101 }
102 /* If the minutia is NOT on a loop... */
103 else if (ret == FALSE){
104 /* Simply advance to next minutia in the list. */
105 i++;
106 }
107 /* Otherwise, an ERROR occurred while looking for loop. */
108 else{
109 /* Return error code. */
110 return(ret);
111 }
112 }
113 /* Otherwise, the current minutia is a ridge-ending... */
114 else{
115 /* Advance to next minutia in the list. */
116 i++;
117 }
118 }
119
120 /* Return normally. */
121 return(0);
122 }
123
124 /*************************************************************************
125 **************************************************************************
126 #cat: remove_hooks - Takes a list of true and false minutiae and
127 #cat: attempts to detect and remove those false minutiae that
128 #cat: are on a hook (white or black).
129
130 Input:
131 minutiae - list of true and false minutiae
132 bdata - binary image data (0==while & 1==black)
133 iw - width (in pixels) of image
134 ih - height (in pixels) of image
135 lfsparms - parameters and thresholds for controlling LFS
136 Output:
137 minutiae - list of pruned minutiae
138 Return Code:
139 Zero - successful completion
140 Negative - system error
141 **************************************************************************/
remove_hooks(MINUTIAE * minutiae,unsigned char * bdata,const int iw,const int ih,const LFSPARMS * lfsparms)142 static int remove_hooks(MINUTIAE *minutiae,
143 unsigned char *bdata, const int iw, const int ih,
144 const LFSPARMS *lfsparms)
145 {
146 int *to_remove;
147 int i, f, s, ret;
148 int delta_y, full_ndirs, qtr_ndirs, deltadir, min_deltadir;
149 MINUTIA *minutia1, *minutia2;
150 double dist;
151
152 print2log("\nREMOVING HOOKS:\n");
153
154 /* Allocate list of minutia indices that upon completion of testing */
155 /* should be removed from the minutiae lists. Note: That using */
156 /* "calloc" initializes the list to FALSE. */
157 to_remove = (int *)calloc(minutiae->num, sizeof(int));
158 if(to_remove == (int *)NULL){
159 fprintf(stderr, "ERROR : remove_hooks : calloc : to_remove\n");
160 return(-640);
161 }
162
163 /* Compute number directions in full circle. */
164 full_ndirs = lfsparms->num_directions<<1;
165 /* Compute number of directions in 45=(180/4) degrees. */
166 qtr_ndirs = lfsparms->num_directions>>2;
167
168 /* Minimum allowable deltadir to consider joining minutia. */
169 /* (The closer the deltadir is to 180 degrees, the more likely the join. */
170 /* When ndirs==16, then this value is 11=(3*4)-1 == 123.75 degrees. */
171 /* I chose to parameterize this threshold based on a fixed fraction of */
172 /* 'ndirs' rather than on passing in a parameter in degrees and doing */
173 /* the conversion. I doubt the difference matters. */
174 min_deltadir = (3 * qtr_ndirs) - 1;
175
176 f = 0;
177 /* Foreach primary (first) minutia (except for last one in list) ... */
178 while(f < minutiae->num-1){
179
180 /* If current first minutia not previously set to be removed. */
181 if(!to_remove[f]){
182
183 print2log("\n");
184
185 /* Set first minutia to temporary pointer. */
186 minutia1 = minutiae->list[f];
187 /* Foreach secondary (second) minutia to right of first minutia ... */
188 s = f+1;
189 while(s < minutiae->num){
190 /* Set second minutia to temporary pointer. */
191 minutia2 = minutiae->list[s];
192
193 print2log("1:%d(%d,%d)%d 2:%d(%d,%d)%d ",
194 f, minutia1->x, minutia1->y, minutia1->type,
195 s, minutia2->x, minutia2->y, minutia2->type);
196
197 /* The binary image is potentially being edited during each */
198 /* iteration of the secondary minutia loop, therefore */
199 /* minutia pixel values may be changed. We need to catch */
200 /* these events by using the next 2 tests. */
201
202 /* If the first minutia's pixel has been previously changed... */
203 if(*(bdata+(minutia1->y*iw)+minutia1->x) != minutia1->type){
204 print2log("\n");
205 /* Then break out of secondary loop and skip to next first. */
206 break;
207 }
208
209 /* If the second minutia's pixel has been previously changed... */
210 if(*(bdata+(minutia2->y*iw)+minutia2->x) != minutia2->type)
211 /* Set to remove second minutia. */
212 to_remove[s] = TRUE;
213
214 /* If the second minutia not previously set to be removed. */
215 if(!to_remove[s]){
216
217 /* Compute delta y between 1st & 2nd minutiae and test. */
218 delta_y = minutia2->y - minutia1->y;
219 /* If delta y small enough (ex. < 8 pixels) ... */
220 if(delta_y <= lfsparms->max_rmtest_dist){
221
222 print2log("1DY ");
223
224 /* Compute Euclidean distance between 1st & 2nd mintuae. */
225 dist = distance(minutia1->x, minutia1->y,
226 minutia2->x, minutia2->y);
227 /* If distance is NOT too large (ex. < 8 pixels) ... */
228 if(dist <= lfsparms->max_rmtest_dist){
229
230 print2log("2DS ");
231
232 /* Compute "inner" difference between directions on */
233 /* a full circle and test. */
234 if((deltadir = closest_dir_dist(minutia1->direction,
235 minutia2->direction, full_ndirs)) ==
236 INVALID_DIR){
237 free(to_remove);
238 fprintf(stderr,
239 "ERROR : remove_hooks : INVALID direction\n");
240 return(-641);
241 }
242 /* If the difference between dirs is large enough ... */
243 /* (the more 1st & 2nd point away from each other the */
244 /* more likely they should be joined) */
245 if(deltadir > min_deltadir){
246
247 print2log("3DD ");
248
249 /* If 1st & 2nd minutiae are NOT same type ... */
250 if(minutia1->type != minutia2->type){
251 /* Check to see if pair on a hook with contour */
252 /* of specified length (ex. 15 pixels) ... */
253
254 ret = on_hook(minutia1, minutia2,
255 lfsparms->max_hook_len,
256 bdata, iw, ih);
257
258 /* If hook detected between pair ... */
259 if(ret == HOOK_FOUND){
260
261 print2log("4HK RM\n");
262
263 /* Set to remove first minutia. */
264 to_remove[f] = TRUE;
265 /* Set to remove second minutia. */
266 to_remove[s] = TRUE;
267 }
268 /* If hook test IGNORED ... */
269 else if (ret == IGNORE){
270
271 print2log("RM\n");
272
273 /* Set to remove first minutia. */
274 to_remove[f] = TRUE;
275 /* Skip to next 1st minutia by breaking out of */
276 /* inner secondary loop. */
277 break;
278 }
279 /* If system error occurred during hook test ... */
280 else if (ret < 0){
281 free(to_remove);
282 return(ret);
283 }
284 /* Otherwise, no hook found, so skip to next */
285 /* second minutia. */
286 else
287 print2log("\n");
288 }
289 else
290 print2log("\n");
291 /* End different type test. */
292 }/* End deltadir test. */
293 else
294 print2log("\n");
295 }/* End distance test. */
296 else
297 print2log("\n");
298 }
299 /* Otherwise, current 2nd too far below 1st, so skip to next */
300 /* 1st minutia. */
301 else{
302
303 print2log("\n");
304
305 /* Break out of inner secondary loop. */
306 break;
307 }/* End delta-y test. */
308
309 }/* End if !to_remove[s] */
310 else
311 print2log("\n");
312
313 /* Bump to next second minutia in minutiae list. */
314 s++;
315 }/* End secondary minutiae loop. */
316
317 }/* Otherwise, first minutia already flagged to be removed. */
318
319 /* Bump to next first minutia in minutiae list. */
320 f++;
321 }/* End primary minutiae loop. */
322
323 /* Now remove all minutiae in list that have been flagged for removal. */
324 /* NOTE: Need to remove the minutia from their lists in reverse */
325 /* order, otherwise, indices will be off. */
326 for(i = minutiae->num-1; i >= 0; i--){
327 /* If the current minutia index is flagged for removal ... */
328 if(to_remove[i]){
329 /* Remove the minutia from the minutiae list. */
330 if((ret = remove_minutia(i, minutiae))){
331 free(to_remove);
332 return(ret);
333 }
334 }
335 }
336
337 /* Deallocate flag list. */
338 free(to_remove);
339
340 /* Return normally. */
341 return(0);
342 }
343
344 /*************************************************************************
345 **************************************************************************
346 #cat: remove_islands_and_lakes - Takes a list of true and false minutiae and
347 #cat: attempts to detect and remove those false minutiae that
348 #cat: are either on a common island (filled with black pixels)
349 #cat: or a lake (filled with white pixels).
350 #cat: Note that this routine edits the binary image by filling
351 #cat: detected lakes or islands.
352
353 Input:
354 minutiae - list of true and false minutiae
355 bdata - binary image data (0==while & 1==black)
356 iw - width (in pixels) of image
357 ih - height (in pixels) of image
358 lfsparms - parameters and thresholds for controlling LFS
359 Output:
360 minutiae - list of pruned minutiae
361 Return Code:
362 Zero - successful completion
363 Negative - system error
364 **************************************************************************/
remove_islands_and_lakes(MINUTIAE * minutiae,unsigned char * bdata,const int iw,const int ih,const LFSPARMS * lfsparms)365 static int remove_islands_and_lakes(MINUTIAE *minutiae,
366 unsigned char *bdata, const int iw, const int ih,
367 const LFSPARMS *lfsparms)
368 {
369 int *to_remove;
370 int i, f, s, ret;
371 int delta_y, full_ndirs, qtr_ndirs, deltadir, min_deltadir;
372 int *loop_x, *loop_y, *loop_ex, *loop_ey, nloop;
373 MINUTIA *minutia1, *minutia2;
374 double dist;
375 int dist_thresh, half_loop;
376
377 print2log("\nREMOVING ISLANDS AND LAKES:\n");
378
379 dist_thresh = lfsparms->max_rmtest_dist;
380 half_loop = lfsparms->max_half_loop;
381
382 /* Allocate list of minutia indices that upon completion of testing */
383 /* should be removed from the minutiae lists. Note: That using */
384 /* "calloc" initializes the list to FALSE. */
385 to_remove = (int *)calloc(minutiae->num, sizeof(int));
386 if(to_remove == (int *)NULL){
387 fprintf(stderr,
388 "ERROR : remove_islands_and_lakes : calloc : to_remove\n");
389 return(-610);
390 }
391
392 /* Compute number directions in full circle. */
393 full_ndirs = lfsparms->num_directions<<1;
394 /* Compute number of directions in 45=(180/4) degrees. */
395 qtr_ndirs = lfsparms->num_directions>>2;
396
397 /* Minimum allowable deltadir to consider joining minutia. */
398 /* (The closer the deltadir is to 180 degrees, the more likely the join. */
399 /* When ndirs==16, then this value is 11=(3*4)-1 == 123.75 degrees. */
400 /* I chose to parameterize this threshold based on a fixed fraction of */
401 /* 'ndirs' rather than on passing in a parameter in degrees and doing */
402 /* the conversion. I doubt the difference matters. */
403 min_deltadir = (3 * qtr_ndirs) - 1;
404
405 /* Foreach primary (first) minutia (except for last one in list) ... */
406 f = 0;
407 while(f < minutiae->num-1){
408
409 /* If current first minutia not previously set to be removed. */
410 if(!to_remove[f]){
411
412 print2log("\n");
413
414 /* Set first minutia to temporary pointer. */
415 minutia1 = minutiae->list[f];
416
417 /* Foreach secondary minutia to right of first minutia ... */
418 s = f+1;
419 while(s < minutiae->num){
420 /* Set second minutia to temporary pointer. */
421 minutia2 = minutiae->list[s];
422
423 /* If the secondary minutia is desired type ... */
424 if(minutia2->type == minutia1->type){
425
426 print2log("1:%d(%d,%d)%d 2:%d(%d,%d)%d ",
427 f, minutia1->x, minutia1->y, minutia1->type,
428 s, minutia2->x, minutia2->y, minutia2->type);
429
430 /* The binary image is potentially being edited during */
431 /* each iteration of the secondary minutia loop, */
432 /* therefore minutia pixel values may be changed. We */
433 /* need to catch these events by using the next 2 tests. */
434
435 /* If the first minutia's pixel has been previously */
436 /* changed... */
437 if(*(bdata+(minutia1->y*iw)+minutia1->x) != minutia1->type){
438 print2log("\n");
439 /* Then break out of secondary loop and skip to next */
440 /* first. */
441 break;
442 }
443
444 /* If the second minutia's pixel has been previously */
445 /* changed... */
446 if(*(bdata+(minutia2->y*iw)+minutia2->x) != minutia2->type)
447 /* Set to remove second minutia. */
448 to_remove[s] = TRUE;
449
450 /* If the second minutia not previously set to be removed. */
451 if(!to_remove[s]){
452
453 /* Compute delta y between 1st & 2nd minutiae and test. */
454 delta_y = minutia2->y - minutia1->y;
455 /* If delta y small enough (ex. <16 pixels)... */
456 if(delta_y <= dist_thresh){
457
458 print2log("1DY ");
459
460 /* Compute Euclidean distance between 1st & 2nd */
461 /* mintuae. */
462 dist = distance(minutia1->x, minutia1->y,
463 minutia2->x, minutia2->y);
464
465 /* If distance is NOT too large (ex. <16 pixels)... */
466 if(dist <= dist_thresh){
467
468 print2log("2DS ");
469
470 /* Compute "inner" difference between directions */
471 /* on a full circle and test. */
472 if((deltadir = closest_dir_dist(minutia1->direction,
473 minutia2->direction, full_ndirs)) ==
474 INVALID_DIR){
475 free(to_remove);
476 fprintf(stderr,
477 "ERROR : remove_islands_and_lakes : INVALID direction\n");
478 return(-611);
479 }
480 /* If the difference between dirs is large */
481 /* enough ... */
482 /* (the more 1st & 2nd point away from each */
483 /* other the more likely they should be joined) */
484 if(deltadir > min_deltadir){
485
486 print2log("3DD ");
487
488 /* Pair is the same type, so test to see */
489 /* if both are on an island or lake. */
490
491 /* Check to see if pair on a loop of specified */
492 /* half length (ex. 30 pixels) ... */
493 ret = on_island_lake(&loop_x, &loop_y,
494 &loop_ex, &loop_ey, &nloop,
495 minutia1, minutia2,
496 half_loop, bdata, iw, ih);
497 /* If pair is on island/lake ... */
498 if(ret == LOOP_FOUND){
499
500 print2log("4IL RM\n");
501
502 /* Fill the loop. */
503 if((ret = fill_loop(loop_x, loop_y, nloop,
504 bdata, iw, ih))){
505 free_contour(loop_x, loop_y,
506 loop_ex, loop_ey);
507 free(to_remove);
508 return(ret);
509 }
510 /* Set to remove first minutia. */
511 to_remove[f] = TRUE;
512 /* Set to remove second minutia. */
513 to_remove[s] = TRUE;
514 /* Deallocate loop contour. */
515 free_contour(loop_x,loop_y,loop_ex,loop_ey);
516 }
517 /* If island/lake test IGNORED ... */
518 else if (ret == IGNORE){
519
520 print2log("RM\n");
521
522 /* Set to remove first minutia. */
523 to_remove[f] = TRUE;
524 /* Skip to next 1st minutia by breaking out */
525 /* of inner secondary loop. */
526 break;
527 }
528 /* If ERROR while looking for island/lake ... */
529 else if (ret < 0){
530 free(to_remove);
531 return(ret);
532 }
533 else
534 print2log("\n");
535 }/* End deltadir test. */
536 else
537 print2log("\n");
538 }/* End distance test. */
539 else
540 print2log("\n");
541 }
542 /* Otherwise, current 2nd too far below 1st, so skip to */
543 /* next 1st minutia. */
544 else{
545
546 print2log("\n");
547
548 /* Break out of inner secondary loop. */
549 break;
550 }/* End delta-y test. */
551 }/* End if !to_remove[s] */
552 else
553 print2log("\n");
554
555 }/* End if 2nd not desired type */
556
557 /* Bump to next second minutia in minutiae list. */
558 s++;
559 }/* End secondary minutiae loop. */
560
561 }/* Otherwise, first minutia already flagged to be removed. */
562
563 /* Bump to next first minutia in minutiae list. */
564 f++;
565 }/* End primary minutiae loop. */
566
567 /* Now remove all minutiae in list that have been flagged for removal. */
568 /* NOTE: Need to remove the minutia from their lists in reverse */
569 /* order, otherwise, indices will be off. */
570 for(i = minutiae->num-1; i >= 0; i--){
571 /* If the current minutia index is flagged for removal ... */
572 if(to_remove[i]){
573 /* Remove the minutia from the minutiae list. */
574 if((ret = remove_minutia(i, minutiae))){
575 free(to_remove);
576 return(ret);
577 }
578 }
579 }
580
581 /* Deallocate flag list. */
582 free(to_remove);
583
584 /* Return normally. */
585 return(0);
586 }
587
588 /*************************************************************************
589 **************************************************************************
590 #cat: remove_malformations - Attempts to detect and remove minutia points
591 #cat: that are "irregularly" shaped. Irregularity is measured
592 #cat: by measuring across the interior of the feature at
593 #cat: two progressive points down the feature's contour. The
594 #cat: test is triggered if a pixel of opposite color from the
595 #cat: feture's type is found. The ratio of the distances across
596 #cat: the feature at the two points is computed and if the ratio
597 #cat: is too large then the minutia is determined to be malformed.
598 #cat: A cursory test is conducted prior to the general tests in
599 #cat: the event that the minutia lies in a block with LOW RIDGE
600 #cat: FLOW. In this case, the distance across the feature at
601 #cat: the second progressive contour point is measured and if
602 #cat: too large, the point is determined to be malformed.
603
604 Input:
605 minutiae - list of true and false minutiae
606 bdata - binary image data (0==while & 1==black)
607 iw - width (in pixels) of image
608 ih - height (in pixels) of image
609 low_flow_map - map of image blocks flagged as LOW RIDGE FLOW
610 mw - width in blocks of the map
611 mh - height in blocks of the map
612 lfsparms - parameters and thresholds for controlling LFS
613 Output:
614 minutiae - list of pruned minutiae
615 Return Code:
616 Zero - successful completion
617 Negative - system error
618 **************************************************************************/
remove_malformations(MINUTIAE * minutiae,unsigned char * bdata,const int iw,const int ih,int * low_flow_map,const int mw,const int mh,const LFSPARMS * lfsparms)619 static int remove_malformations(MINUTIAE *minutiae,
620 unsigned char *bdata, const int iw, const int ih,
621 int *low_flow_map, const int mw, const int mh,
622 const LFSPARMS *lfsparms)
623 {
624 int i, j, ret;
625 MINUTIA *minutia;
626 int *contour_x, *contour_y, *contour_ex, *contour_ey, ncontour;
627 int ax1, ay1, bx1, by1;
628 int ax2, ay2, bx2, by2;
629 int *x_list, *y_list, num;
630 double a_dist, b_dist, ratio;
631 int fmapval, removed;
632 int blk_x, blk_y;
633
634 print2log("\nREMOVING MALFORMATIONS:\n");
635
636 for(i = minutiae->num-1; i >= 0; i--){
637 minutia = minutiae->list[i];
638 ret = trace_contour(&contour_x, &contour_y,
639 &contour_ex, &contour_ey, &ncontour,
640 lfsparms->malformation_steps_2,
641 minutia->x, minutia->y,
642 minutia->x, minutia->y, minutia->ex, minutia->ey,
643 SCAN_COUNTER_CLOCKWISE, bdata, iw, ih);
644
645 /* If system error occurred during trace ... */
646 if(ret < 0){
647 /* Return error code. */
648 return(ret);
649 }
650
651 /* If trace was not possible OR loop found OR */
652 /* contour is incomplete ... */
653 if((ret == IGNORE) ||
654 (ret == LOOP_FOUND) ||
655 (ncontour < lfsparms->malformation_steps_2)){
656 /* If contour allocated and returned ... */
657 if((ret == LOOP_FOUND) ||
658 (ncontour < lfsparms->malformation_steps_2))
659 /* Deallocate the contour. */
660 free_contour(contour_x, contour_y, contour_ex, contour_ey);
661
662 print2log("%d,%d RMA\n", minutia->x, minutia->y);
663
664 /* Then remove the minutia. */
665 if((ret = remove_minutia(i, minutiae)))
666 /* If system error, return error code. */
667 return(ret);
668 }
669 /* Otherwise, traced contour is complete. */
670 else{
671 /* Store 'A1' contour point. */
672 ax1 = contour_x[lfsparms->malformation_steps_1-1];
673 ay1 = contour_y[lfsparms->malformation_steps_1-1];
674
675 /* Store 'B1' contour point. */
676 bx1 = contour_x[lfsparms->malformation_steps_2-1];
677 by1 = contour_y[lfsparms->malformation_steps_2-1];
678
679 /* Deallocate the contours. */
680 free_contour(contour_x, contour_y, contour_ex, contour_ey);
681
682 ret = trace_contour(&contour_x, &contour_y,
683 &contour_ex, &contour_ey, &ncontour,
684 lfsparms->malformation_steps_2,
685 minutia->x, minutia->y,
686 minutia->x, minutia->y, minutia->ex, minutia->ey,
687 SCAN_CLOCKWISE, bdata, iw, ih);
688
689 /* If system error occurred during trace ... */
690 if(ret < 0){
691 /* Return error code. */
692 return(ret);
693 }
694
695 /* If trace was not possible OR loop found OR */
696 /* contour is incomplete ... */
697 if((ret == IGNORE) ||
698 (ret == LOOP_FOUND) ||
699 (ncontour < lfsparms->malformation_steps_2)){
700 /* If contour allocated and returned ... */
701 if((ret == LOOP_FOUND) ||
702 (ncontour < lfsparms->malformation_steps_2))
703 /* Deallocate the contour. */
704 free_contour(contour_x, contour_y, contour_ex, contour_ey);
705
706 print2log("%d,%d RMB\n", minutia->x, minutia->y);
707
708 /* Then remove the minutia. */
709 if((ret = remove_minutia(i, minutiae)))
710 /* If system error, return error code. */
711 return(ret);
712 }
713 /* Otherwise, traced contour is complete. */
714 else{
715 /* Store 'A2' contour point. */
716 ax2 = contour_x[lfsparms->malformation_steps_1-1];
717 ay2 = contour_y[lfsparms->malformation_steps_1-1];
718
719 /* Store 'B2' contour point. */
720 bx2 = contour_x[lfsparms->malformation_steps_2-1];
721 by2 = contour_y[lfsparms->malformation_steps_2-1];
722
723 /* Deallocate the contour. */
724 free_contour(contour_x, contour_y, contour_ex, contour_ey);
725
726 /* Compute distances along A & B paths. */
727 a_dist = distance(ax1, ay1, ax2, ay2);
728 b_dist = distance(bx1, by1, bx2, by2);
729
730 /* Compute block coords from minutia's pixel location. */
731 blk_x = minutia->x/lfsparms->blocksize;
732 blk_y = minutia->y/lfsparms->blocksize;
733
734 removed = FALSE;
735
736 /* Check to see if distances are not zero. */
737 if((a_dist == 0.0) || (b_dist == 0.0)){
738 /* Remove the malformation minutia. */
739 print2log("%d,%d RMMAL1\n", minutia->x, minutia->y);
740 if((ret = remove_minutia(i, minutiae)))
741 /* If system error, return error code. */
742 return(ret);
743 removed = TRUE;
744 }
745
746 if(!removed){
747 /* Determine if minutia is in LOW RIDGE FLOW block. */
748 fmapval = *(low_flow_map+(blk_y*mw)+blk_x);
749 if(fmapval){
750 /* If in LOW RIDGE LFOW, conduct a cursory distance test. */
751 /* Need to test this out! */
752 if(b_dist > lfsparms->max_malformation_dist){
753 /* Remove the malformation minutia. */
754 print2log("%d,%d RMMAL2\n", minutia->x, minutia->y);
755 if((ret = remove_minutia(i, minutiae)))
756 /* If system error, return error code. */
757 return(ret);
758 removed = TRUE;
759 }
760 }
761 }
762
763 if(!removed){
764 /* Compute points on line between the points A & B. */
765 if((ret = line_points(&x_list, &y_list, &num,
766 bx1, by1, bx2, by2)))
767 return(ret);
768 /* Foreach remaining point along line segment ... */
769 for(j = 0; j < num; j++){
770 /* If B path contains pixel opposite minutia type ... */
771 if(*(bdata+(y_list[j]*iw)+x_list[j]) != minutia->type){
772 /* Compute ratio of A & B path lengths. */
773 ratio = b_dist / a_dist;
774 /* Need to truncate precision so that answers are */
775 /* consistent on different computer architectures. */
776 ratio = trunc_dbl_precision(ratio, TRUNC_SCALE);
777 /* If the B path is sufficiently longer than A path ... */
778 if(ratio > lfsparms->min_malformation_ratio){
779 /* Remove the malformation minutia. */
780 /* Then remove the minutia. */
781 print2log("%d,%d RMMAL3 (%f)\n",
782 minutia->x, minutia->y, ratio);
783 if((ret = remove_minutia(i, minutiae))){
784 free(x_list);
785 free(y_list);
786 /* If system error, return error code. */
787 return(ret);
788 }
789 /* Break out of FOR loop. */
790 break;
791 }
792 }
793 }
794
795 free(x_list);
796 free(y_list);
797
798 }
799 }
800 }
801 }
802
803 return(0);
804 }
805
806 /*************************************************************************
807 **************************************************************************
808 #cat: remove_near_invblocks_V2 - Removes minutia points from the given list
809 #cat: that are sufficiently close to a block with invalid
810 #cat: ridge flow or to the edge of the image.
811
812 Input:
813 minutiae - list of true and false minutiae
814 direction_map - map of image blocks containing direction ridge flow
815 mw - width in blocks of the map
816 mh - height in blocks of the map
817 lfsparms - parameters and thresholds for controlling LFS
818 Output:
819 minutiae - list of pruned minutiae
820 Return Code:
821 Zero - successful completion
822 Negative - system error
823 **************************************************************************/
remove_near_invblock_V2(MINUTIAE * minutiae,int * direction_map,const int mw,const int mh,const LFSPARMS * lfsparms)824 static int remove_near_invblock_V2(MINUTIAE *minutiae, int *direction_map,
825 const int mw, const int mh, const LFSPARMS *lfsparms)
826 {
827 int i, ret;
828 int ni, nbx, nby, nvalid;
829 int ix, iy, sbi, ebi;
830 int bx, by, px, py;
831 int removed;
832 MINUTIA *minutia;
833 int lo_margin, hi_margin;
834
835 /* The next 2 lookup tables are indexed by 'ix' and 'iy'. */
836 /* When a feature pixel lies within a 6-pixel margin of a */
837 /* block, this routine examines neighboring blocks to */
838 /* determine appropriate actions. */
839 /* 'ix' may take on values: */
840 /* 0 == x-pixel coord in leftmost margin */
841 /* 1 == x-pixel coord in middle of block */
842 /* 2 == x-pixel coord in rightmost margin */
843 /* 'iy' may take on values: */
844 /* 0 == y-pixel coord in topmost margin */
845 /* 1 == y-pixel coord in middle of block */
846 /* 2 == y-pixel coord in bottommost margin */
847 /* Given (ix, iy): */
848 /* 'startblk[ix][iy]' == starting neighbor index (sbi) */
849 /* 'endblk[ix][iy]' == ending neighbor index (ebi) */
850 /* so that neighbors begin to be analized from index */
851 /* 'sbi' to 'ebi'. */
852 /* Ex. (ix, iy) = (2, 0) */
853 /* ix==2 ==> x-pixel coord in rightmost margin */
854 /* iy==0 ==> y-pixel coord in topmost margin */
855 /* X - marks the region in the current block */
856 /* corresponding to (ix=2, iy=0). */
857 /* sbi = 0 = startblk[2][0] */
858 /* ebi = 2 = endblk[2][0] */
859 /* so neighbors are analized on index range [0..2] */
860 /* | */
861 /* nbr block 0 | nbr block 1 */
862 /* --------------------------+------------ */
863 /* top margin | X | */
864 /* _._._._._._._._._._._._._.| */
865 /* | | */
866 /* current block .r m| nbr block 2 */
867 /* |i a| */
868 /* .g g| */
869 /* |h i| */
870 /* .t n| */
871 /* | | */
872
873 /* LUT for starting neighbor index given (ix, iy). */
874 static int startblk[9] = { 6, 0, 0,
875 6,-1, 2,
876 4, 4, 2 };
877 /* LUT for ending neighbor index given (ix, iy). */
878 static int endblk[9] = { 8, 0, 2,
879 6,-1, 2,
880 6, 4, 4 };
881
882 /* Pixel coord offsets specifying the order in which neighboring */
883 /* blocks are searched. The current block is in the middle of */
884 /* 8 surrounding neighbors. The following illustrates the order */
885 /* of neighbor indices. (Note that 9 overlaps 1.) */
886 /* 8 */
887 /* 7 0 1 */
888 /* 6 C 2 */
889 /* 5 4 3 */
890 /* */
891 /* 0 1 2 3 4 5 6 7 8 */
892 static int blkdx[9] = { 0, 1, 1, 1, 0,-1,-1,-1, 0 }; /* Delta-X */
893 static int blkdy[9] = { -1,-1, 0, 1, 1, 1, 0,-1,-1 }; /* Delta-Y */
894
895 print2log("\nREMOVING MINUTIA NEAR INVALID BLOCKS:\n");
896
897 /* If the margin covers more than the entire block ... */
898 if(lfsparms->inv_block_margin > (lfsparms->blocksize>>1)){
899 /* Then treat this as an error. */
900 fprintf(stderr,
901 "ERROR : remove_near_invblock_V2 : margin too large for blocksize\n");
902 return(-620);
903 }
904
905 /* Compute the low and high pixel margin boundaries (ex. 6 pixels wide) */
906 /* in the block. */
907 lo_margin = lfsparms->inv_block_margin;
908 hi_margin = lfsparms->blocksize - lfsparms->inv_block_margin - 1;
909
910 i = 0;
911 /* Foreach minutia remaining in the list ... */
912 while(i < minutiae->num){
913 /* Assign temporary minutia pointer. */
914 minutia = minutiae->list[i];
915
916 /* Compute block coords from minutia's pixel location. */
917 bx = minutia->x/lfsparms->blocksize;
918 by = minutia->y/lfsparms->blocksize;
919
920 /* Compute pixel offset into the image block corresponding to the */
921 /* minutia's pixel location. */
922 /* NOTE: The margins used here will not necessarily correspond to */
923 /* the actual block boundaries used to compute the map values. */
924 /* This will be true when the image width and/or height is not an */
925 /* even multiple of 'blocksize' and we are processing minutia */
926 /* located in the right-most column (or bottom-most row) of */
927 /* blocks. I don't think this will pose a problem in practice. */
928 px = minutia->x % lfsparms->blocksize;
929 py = minutia->y % lfsparms->blocksize;
930
931 /* Determine if x pixel offset into the block is in the margins. */
932 /* If x pixel offset is in left margin ... */
933 if(px < lo_margin)
934 ix = 0;
935 /* If x pixel offset is in right margin ... */
936 else if(px > hi_margin)
937 ix = 2;
938 /* Otherwise, x pixel offset is in middle of block. */
939 else
940 ix = 1;
941
942 /* Determine if y pixel offset into the block is in the margins. */
943 /* If y pixel offset is in top margin ... */
944 if(py < lo_margin)
945 iy = 0;
946 /* If y pixel offset is in bottom margin ... */
947 else if(py > hi_margin)
948 iy = 2;
949 /* Otherwise, y pixel offset is in middle of block. */
950 else
951 iy = 1;
952
953 /* Set remove flag to FALSE. */
954 removed = FALSE;
955
956 /* If one of the minutia's pixel offsets is in a margin ... */
957 if((ix != 1) || (iy != 1)){
958
959 /* Compute the starting neighbor block index for processing. */
960 sbi = *(startblk+(iy*3)+ix);
961 /* Compute the ending neighbor block index for processing. */
962 ebi = *(endblk+(iy*3)+ix);
963
964 /* Foreach neighbor in the range to be processed ... */
965 for(ni = sbi; ni <= ebi; ni++){
966 /* Compute the neighbor's block coords relative to */
967 /* the block the current minutia is in. */
968 nbx = bx + blkdx[ni];
969 nby = by + blkdy[ni];
970
971 /* If neighbor's block coords are outside of map boundaries... */
972 if((nbx < 0) || (nbx >= mw) ||
973 (nby < 0) || (nby >= mh)){
974
975 print2log("%d,%d RM1\n", minutia->x, minutia->y);
976
977 /* Then the minutia is in a margin adjacent to the edge of */
978 /* the image. */
979 /* NOTE: This is true when the image width and/or height */
980 /* is an even multiple of blocksize. When the image is not*/
981 /* an even multiple, then some minutia may not be detected */
982 /* as being in the margin of "the image" (not the block). */
983 /* In practice, I don't think this will impact performance.*/
984 if((ret = remove_minutia(i, minutiae)))
985 /* If system error occurred while removing minutia, */
986 /* then return error code. */
987 return(ret);
988 /* Set remove flag to TURE. */
989 removed = TRUE;
990 /* Break out of neighboring block loop. */
991 break;
992 }
993 /* If the neighboring block has INVALID direction ... */
994 else if (*(direction_map+(nby*mw)+nbx) == INVALID_DIR){
995 /* Count the number of valid blocks neighboring */
996 /* the current neighbor. */
997 nvalid = num_valid_8nbrs(direction_map, nbx, nby, mw, mh);
998 /* If the number of valid neighbors is < threshold */
999 /* (ex. 7)... */
1000 if(nvalid < lfsparms->rm_valid_nbr_min){
1001
1002 print2log("%d,%d RM2\n", minutia->x, minutia->y);
1003
1004 /* Then remove the current minutia from the list. */
1005 if((ret = remove_minutia(i, minutiae)))
1006 /* If system error occurred while removing minutia, */
1007 /* then return error code. */
1008 return(ret);
1009 /* Set remove flag to TURE. */
1010 removed = TRUE;
1011 /* Break out of neighboring block loop. */
1012 break;
1013 }
1014 /* Otherwise enough valid neighbors, so don't remove minutia */
1015 /* based on this neighboring block. */
1016 }
1017 /* Otherwise neighboring block has valid direction, */
1018 /* so don't remove minutia based on this neighboring block. */
1019 }
1020
1021 } /* Otherwise not in margin, so skip to next minutia in list. */
1022
1023 /* If current minutia not removed ... */
1024 if(!removed)
1025 /* Advance to the next minutia in the list. */
1026 i++;
1027 /* Otherwise the next minutia has slid into the spot where current */
1028 /* minutia was removed, so don't bump minutia index. */
1029 } /* End minutia loop */
1030
1031 /* Return normally. */
1032 return(0);
1033 }
1034
1035 /*************************************************************************
1036 **************************************************************************
1037 #cat: remove_pointing_invblock_V2 - Removes minutia points that are relatively
1038 #cat: close in the direction opposite the minutia to a
1039 #cat: block with INVALID ridge flow.
1040
1041 Input:
1042 minutiae - list of true and false minutiae
1043 direction_map - map of image blocks containing directional ridge flow
1044 mw - width in blocks of the map
1045 mh - height in blocks of the map
1046 lfsparms - parameters and thresholds for controlling LFS
1047 Output:
1048 minutiae - list of pruned minutiae
1049 Return Code:
1050 Zero - successful completion
1051 Negative - system error
1052 **************************************************************************/
remove_pointing_invblock_V2(MINUTIAE * minutiae,int * direction_map,const int mw,const int mh,const LFSPARMS * lfsparms)1053 static int remove_pointing_invblock_V2(MINUTIAE *minutiae,
1054 int *direction_map, const int mw, const int mh,
1055 const LFSPARMS *lfsparms)
1056 {
1057 int i, ret;
1058 int delta_x, delta_y, dmapval;
1059 int nx, ny, bx, by;
1060 MINUTIA *minutia;
1061 double pi_factor, theta;
1062 double dx, dy;
1063
1064 print2log("\nREMOVING MINUTIA POINTING TO INVALID BLOCKS:\n");
1065
1066 /* Compute factor for converting integer directions to radians. */
1067 pi_factor = M_PI / (double)lfsparms->num_directions;
1068
1069 i = 0;
1070 /* Foreach minutia remaining in list ... */
1071 while(i < minutiae->num){
1072 /* Set temporary minutia pointer. */
1073 minutia = minutiae->list[i];
1074 /* Convert minutia's direction to radians. */
1075 theta = minutia->direction * pi_factor;
1076 /* Compute translation offsets (ex. 6 pixels). */
1077 dx = sin(theta) * (double)(lfsparms->trans_dir_pix);
1078 dy = cos(theta) * (double)(lfsparms->trans_dir_pix);
1079 /* Need to truncate precision so that answers are consistent */
1080 /* on different computer architectures when rounding doubles. */
1081 dx = trunc_dbl_precision(dx, TRUNC_SCALE);
1082 dy = trunc_dbl_precision(dy, TRUNC_SCALE);
1083 delta_x = sround(dx);
1084 delta_y = sround(dy);
1085 /* Translate the minutia's coords. */
1086 nx = minutia->x - delta_x;
1087 ny = minutia->y + delta_y;
1088 /* Convert pixel coords to block coords. */
1089 bx = (int)(nx / lfsparms->blocksize);
1090 by = (int)(ny / lfsparms->blocksize);
1091 /* The translation could move the point out of image boundaries, */
1092 /* and therefore the corresponding block coords can be out of */
1093 /* map boundaries, so limit the block coords to within boundaries. */
1094 bx = max(0, bx);
1095 bx = min(mw-1, bx);
1096 by = max(0, by);
1097 by = min(mh-1, by);
1098
1099 /* Get corresponding block's ridge flow direction. */
1100 dmapval = *(direction_map+(by*mw)+bx);
1101
1102 /* If the block's direction is INVALID ... */
1103 if(dmapval == INVALID_DIR){
1104
1105 print2log("%d,%d RM\n", minutia->x, minutia->y);
1106
1107 /* Remove the minutia from the minutiae list. */
1108 if((ret = remove_minutia(i, minutiae))){
1109 return(ret);
1110 }
1111 /* No need to advance because next minutia has slid into slot. */
1112 }
1113 else{
1114 /* Advance to next minutia in list. */
1115 i++;
1116 }
1117 }
1118
1119 /* Return normally. */
1120 return(0);
1121 }
1122
1123 /*************************************************************************
1124 **************************************************************************
1125 #cat: remove_overlaps - Takes a list of true and false minutiae and
1126 #cat: attempts to detect and remove those false minutiae that
1127 #cat: are on opposite sides of an overlap. Note that this
1128 #cat: routine does NOT edit the binary image when overlaps
1129 #cat: are removed.
1130
1131 Input:
1132 minutiae - list of true and false minutiae
1133 bdata - binary image data (0==while & 1==black)
1134 iw - width (in pixels) of image
1135 ih - height (in pixels) of image
1136 lfsparms - parameters and thresholds for controlling LFS
1137 Output:
1138 minutiae - list of pruned minutiae
1139 Return Code:
1140 Zero - successful completion
1141 Negative - system error
1142 **************************************************************************/
remove_overlaps(MINUTIAE * minutiae,unsigned char * bdata,const int iw,const int ih,const LFSPARMS * lfsparms)1143 static int remove_overlaps(MINUTIAE *minutiae,
1144 unsigned char *bdata, const int iw, const int ih,
1145 const LFSPARMS *lfsparms)
1146 {
1147 int *to_remove;
1148 int i, f, s, ret;
1149 int delta_y, full_ndirs, qtr_ndirs, deltadir, min_deltadir;
1150 MINUTIA *minutia1, *minutia2;
1151 double dist;
1152 int joindir, opp1dir, half_ndirs;
1153
1154 print2log("\nREMOVING OVERLAPS:\n");
1155
1156 /* Allocate list of minutia indices that upon completion of testing */
1157 /* should be removed from the minutiae lists. Note: That using */
1158 /* "calloc" initializes the list to FALSE. */
1159 to_remove = (int *)calloc(minutiae->num, sizeof(int));
1160 if(to_remove == (int *)NULL){
1161 fprintf(stderr, "ERROR : remove_overlaps : calloc : to_remove\n");
1162 return(-650);
1163 }
1164
1165 /* Compute number directions in full circle. */
1166 full_ndirs = lfsparms->num_directions<<1;
1167 /* Compute number of directions in 45=(180/4) degrees. */
1168 qtr_ndirs = lfsparms->num_directions>>2;
1169 /* Compute number of directions in 90=(180/2) degrees. */
1170 half_ndirs = lfsparms->num_directions>>1;
1171
1172 /* Minimum allowable deltadir to consider joining minutia. */
1173 /* (The closer the deltadir is to 180 degrees, the more likely the join. */
1174 /* When ndirs==16, then this value is 11=(3*4)-1 == 123.75 degrees. */
1175 /* I chose to parameterize this threshold based on a fixed fraction of */
1176 /* 'ndirs' rather than on passing in a parameter in degrees and doing */
1177 /* the conversion. I doubt the difference matters. */
1178 min_deltadir = (3 * qtr_ndirs) - 1;
1179
1180 f = 0;
1181 /* Foreach primary (first) minutia (except for last one in list) ... */
1182 while(f < minutiae->num-1){
1183
1184 /* If current first minutia not previously set to be removed. */
1185 if(!to_remove[f]){
1186
1187 print2log("\n");
1188
1189 /* Set first minutia to temporary pointer. */
1190 minutia1 = minutiae->list[f];
1191 /* Foreach secondary (second) minutia to right of first minutia ... */
1192 s = f+1;
1193 while(s < minutiae->num){
1194 /* Set second minutia to temporary pointer. */
1195 minutia2 = minutiae->list[s];
1196
1197 print2log("1:%d(%d,%d)%d 2:%d(%d,%d)%d ",
1198 f, minutia1->x, minutia1->y, minutia1->type,
1199 s, minutia2->x, minutia2->y, minutia2->type);
1200
1201 /* The binary image is potentially being edited during each */
1202 /* iteration of the secondary minutia loop, therefore */
1203 /* minutia pixel values may be changed. We need to catch */
1204 /* these events by using the next 2 tests. */
1205
1206 /* If the first minutia's pixel has been previously changed... */
1207 if(*(bdata+(minutia1->y*iw)+minutia1->x) != minutia1->type){
1208 print2log("\n");
1209 /* Then break out of secondary loop and skip to next first. */
1210 break;
1211 }
1212
1213 /* If the second minutia's pixel has been previously changed... */
1214 if(*(bdata+(minutia2->y*iw)+minutia2->x) != minutia2->type)
1215 /* Set to remove second minutia. */
1216 to_remove[s] = TRUE;
1217
1218 /* If the second minutia not previously set to be removed. */
1219 if(!to_remove[s]){
1220
1221 /* Compute delta y between 1st & 2nd minutiae and test. */
1222 delta_y = minutia2->y - minutia1->y;
1223 /* If delta y small enough (ex. < 8 pixels) ... */
1224 if(delta_y <= lfsparms->max_overlap_dist){
1225
1226 print2log("1DY ");
1227
1228 /* Compute Euclidean distance between 1st & 2nd mintuae. */
1229 dist = distance(minutia1->x, minutia1->y,
1230 minutia2->x, minutia2->y);
1231 /* If distance is NOT too large (ex. < 8 pixels) ... */
1232 if(dist <= lfsparms->max_overlap_dist){
1233
1234 print2log("2DS ");
1235
1236 /* Compute "inner" difference between directions on */
1237 /* a full circle and test. */
1238 if((deltadir = closest_dir_dist(minutia1->direction,
1239 minutia2->direction, full_ndirs)) ==
1240 INVALID_DIR){
1241 free(to_remove);
1242 fprintf(stderr,
1243 "ERROR : remove_overlaps : INVALID direction\n");
1244 return(-651);
1245 }
1246 /* If the difference between dirs is large enough ... */
1247 /* (the more 1st & 2nd point away from each other the */
1248 /* more likely they should be joined) */
1249 if(deltadir > min_deltadir){
1250
1251 print2log("3DD ");
1252
1253 /* If 1st & 2nd minutiae are same type ... */
1254 if(minutia1->type == minutia2->type){
1255 /* Test to see if both are on opposite sides */
1256 /* of an overlap. */
1257
1258 /* Compute direction of "joining" vector. */
1259 /* First, compute direction of line from first */
1260 /* to second minutia points. */
1261 joindir = line2direction(minutia1->x, minutia1->y,
1262 minutia2->x, minutia2->y,
1263 lfsparms->num_directions);
1264
1265 /* Comptue opposite direction of first minutia. */
1266 opp1dir = (minutia1->direction+
1267 lfsparms->num_directions)%full_ndirs;
1268 /* Take "inner" distance on full circle between */
1269 /* the first minutia's opposite direction and */
1270 /* the joining direction. */
1271 joindir = abs(opp1dir - joindir);
1272 joindir = min(joindir, full_ndirs - joindir);
1273
1274 print2log("joindir=%d dist=%f ", joindir,dist);
1275
1276 /* If the joining angle is <= 90 degrees OR */
1277 /* the 2 points are sufficiently close AND */
1278 /* a free path exists between pair ... */
1279 if(((joindir <= half_ndirs) ||
1280 (dist <= lfsparms->max_overlap_join_dist)) &&
1281 free_path(minutia1->x, minutia1->y,
1282 minutia2->x, minutia2->y,
1283 bdata, iw, ih, lfsparms)){
1284
1285 print2log("4OV RM\n");
1286
1287 /* Then assume overlap, so ... */
1288 /* Set to remove first minutia. */
1289 to_remove[f] = TRUE;
1290 /* Set to remove second minutia. */
1291 to_remove[s] = TRUE;
1292 }
1293 /* Otherwise, pair not on an overlap, so skip */
1294 /* to next second minutia. */
1295 else
1296 print2log("\n");
1297 }
1298 else
1299 print2log("\n");
1300 /* End same type test. */
1301 }/* End deltadir test. */
1302 else
1303 print2log("\n");
1304 }/* End distance test. */
1305 else
1306 print2log("\n");
1307 }
1308 /* Otherwise, current 2nd too far below 1st, so skip to next */
1309 /* 1st minutia. */
1310 else{
1311
1312 print2log("\n");
1313
1314 /* Break out of inner secondary loop. */
1315 break;
1316 }/* End delta-y test. */
1317
1318 }/* End if !to_remove[s] */
1319 else
1320 print2log("\n");
1321
1322 /* Bump to next second minutia in minutiae list. */
1323 s++;
1324 }/* End secondary minutiae loop. */
1325
1326 }/* Otherwise, first minutia already flagged to be removed. */
1327
1328 /* Bump to next first minutia in minutiae list. */
1329 f++;
1330 }/* End primary minutiae loop. */
1331
1332 /* Now remove all minutiae in list that have been flagged for removal. */
1333 /* NOTE: Need to remove the minutia from their lists in reverse */
1334 /* order, otherwise, indices will be off. */
1335 for(i = minutiae->num-1; i >= 0; i--){
1336 /* If the current minutia index is flagged for removal ... */
1337 if(to_remove[i]){
1338 /* Remove the minutia from the minutiae list. */
1339 if((ret = remove_minutia(i, minutiae))){
1340 free(to_remove);
1341 return(ret);
1342 }
1343 }
1344 }
1345
1346 /* Deallocate flag list. */
1347 free(to_remove);
1348
1349 /* Return normally. */
1350 return(0);
1351 }
1352
mark_minutiae_in_range(MINUTIAE * minutiae,int * to_remove,int x,int y,const LFSPARMS * lfsparms)1353 static void mark_minutiae_in_range(MINUTIAE *minutiae, int *to_remove, int x, int y,
1354 const LFSPARMS *lfsparms)
1355 {
1356 int i, dist;
1357 for (i = 0; i < minutiae->num; i++) {
1358 if (to_remove[i])
1359 continue;
1360 dist = (int)sqrt((x - minutiae->list[i]->x) * (x - minutiae->list[i]->x) +
1361 (y - minutiae->list[i]->y) * (y - minutiae->list[i]->y));
1362 if (dist < lfsparms->min_pp_distance) {
1363 to_remove[i] = 1;
1364 }
1365 }
1366 }
1367
1368 /*************************************************************************
1369 **************************************************************************
1370 #cat: remove_perimeter_pts - Takes a list of true and false minutiae and
1371 #cat: attempts to detect and remove those false minutiae that
1372 #cat: belong to image edge
1373
1374 Input:
1375 minutiae - list of true and false minutiae
1376 bdata - binary image data (0==while & 1==black)
1377 iw - width (in pixels) of image
1378 ih - height (in pixels) of image
1379 lfsparms - parameters and thresholds for controlling LFS
1380 Output:
1381 minutiae - list of pruned minutiae
1382 Return Code:
1383 Zero - successful completion
1384 Negative - system error
1385 **************************************************************************/
remove_perimeter_pts(MINUTIAE * minutiae,unsigned char * bdata,const int iw,const int ih,const LFSPARMS * lfsparms)1386 static int remove_perimeter_pts(MINUTIAE *minutiae,
1387 unsigned char *bdata, const int iw, const int ih,
1388 const LFSPARMS *lfsparms)
1389 {
1390 int i, j, ret, *to_remove;
1391 int *left, *left_up, *left_down;
1392 int *right, *right_up, *right_down;
1393 int removed = 0;
1394 int left_min, right_max;
1395
1396 if (!lfsparms->remove_perimeter_pts)
1397 return(0);
1398
1399 to_remove = calloc(minutiae->num, sizeof(int));
1400 left = calloc(ih, sizeof(int));
1401 left_up = calloc(ih, sizeof(int));
1402 left_down = calloc(ih, sizeof(int));
1403 right = calloc(ih, sizeof(int));
1404 right_up = calloc(ih, sizeof(int));
1405 right_down = calloc(ih, sizeof(int));
1406
1407 /* Pass downwards */
1408 left_min = iw - 1;
1409 right_max = 0;
1410 for (i = 0; i < ih; i++) {
1411 for (j = 0; j < left_min; j++) {
1412 if ((bdata[i * iw + j] != 0)) {
1413 left_min = j;
1414 break;
1415 }
1416 }
1417 if (left_min == (iw - 1))
1418 left_down[i] = -1;
1419 else
1420 left_down[i] = left_min;
1421 for (j = iw - 1; j >= right_max; j--) {
1422 if ((bdata[i * iw + j] != 0)) {
1423 right_max = j;
1424 break;
1425 }
1426 }
1427 if (right_max == 0)
1428 right_down[i] = -1;
1429 else
1430 right_down[i] = right_max;
1431 }
1432
1433 /* Pass upwards */
1434 left_min = iw - 1;
1435 right_max = 0;
1436 for (i = ih - 1; i >= 0; i--) {
1437 for (j = 0; j < left_min; j++) {
1438 if ((bdata[i * iw + j] != 0)) {
1439 left_min = j;
1440 break;
1441 }
1442 }
1443 if (left_min == (iw - 1))
1444 left_up[i] = -1;
1445 else
1446 left_up[i] = left_min;
1447 for (j = iw - 1; j >= right_max; j--) {
1448 if ((bdata[i * iw + j] != 0)) {
1449 right_max = j;
1450 break;
1451 }
1452 }
1453 if (right_max == 0)
1454 right_up[i] = -1;
1455 else
1456 right_up[i] = right_max;
1457 }
1458
1459 /* Merge */
1460 left_min = left_down[ih - 1];
1461 right_max = right_down[ih - 1];
1462 for (i = 0; i < ih; i++) {
1463 if (left_down[i] != left_min)
1464 left[i] = left_down[i];
1465 else
1466 left[i] = left_up[i];
1467
1468 if (right_down[i] != right_max)
1469 right[i] = right_down[i];
1470 else
1471 right[i] = right_up[i];
1472 }
1473 free(left_up);
1474 free(left_down);
1475 free(right_up);
1476 free(right_down);
1477
1478 /* Mark minitiae close to the edge */
1479 for (i = 0; i < ih; i++) {
1480 if (left[i] != -1)
1481 mark_minutiae_in_range(minutiae, to_remove, left[i], i, lfsparms);
1482 if (right[i] != -1)
1483 mark_minutiae_in_range(minutiae, to_remove, right[i], i, lfsparms);
1484 }
1485
1486 free(left);
1487 free(right);
1488
1489 for (i = minutiae->num - 1; i >= 0; i--) {
1490 /* If the current minutia index is flagged for removal ... */
1491 if (to_remove[i]){
1492 removed ++;
1493 /* Remove the minutia from the minutiae list. */
1494 if((ret = remove_minutia(i, minutiae))){
1495 free(to_remove);
1496 return(ret);
1497 }
1498 }
1499 }
1500
1501 free(to_remove);
1502
1503 return (0);
1504 }
1505
1506 /*************************************************************************
1507 **************************************************************************
1508 #cat: remove_pores_V2 - Attempts to detect and remove minutia points located on
1509 #cat: pore-shaped valleys and/or ridges. Detection for
1510 #cat: these features are only performed in blocks with
1511 #cat: LOW RIDGE FLOW or HIGH CURVATURE.
1512
1513 Input:
1514 minutiae - list of true and false minutiae
1515 bdata - binary image data (0==while & 1==black)
1516 iw - width (in pixels) of image
1517 ih - height (in pixels) of image
1518 direction_map - map of image blocks containing directional ridge flow
1519 low_flow_map - map of image blocks flagged as LOW RIDGE FLOW
1520 high_curve_map - map of image blocks flagged as HIGH CURVATURE
1521 mw - width in blocks of the maps
1522 mh - height in blocks of the maps
1523 lfsparms - parameters and thresholds for controlling LFS
1524 Output:
1525 minutiae - list of pruned minutiae
1526 Return Code:
1527 Zero - successful completion
1528 Negative - system error
1529 **************************************************************************/
remove_pores_V2(MINUTIAE * minutiae,unsigned char * bdata,const int iw,const int ih,int * direction_map,int * low_flow_map,int * high_curve_map,const int mw,const int mh,const LFSPARMS * lfsparms)1530 static int remove_pores_V2(MINUTIAE *minutiae,
1531 unsigned char *bdata, const int iw, const int ih,
1532 int *direction_map, int *low_flow_map,
1533 int *high_curve_map, const int mw, const int mh,
1534 const LFSPARMS *lfsparms)
1535 {
1536 int i, ret;
1537 int removed, blk_x, blk_y;
1538 int rx, ry;
1539 int px, py, pex, pey, bx, by, dx, dy;
1540 int qx, qy, qex, qey, ax, ay, cx, cy;
1541 MINUTIA *minutia;
1542 double pi_factor, theta, sin_theta, cos_theta;
1543 double ab2, cd2, ratio;
1544 int *contour_x, *contour_y, *contour_ex, *contour_ey, ncontour;
1545 double drx, dry;
1546
1547 /* This routine attempts to locate the following points on all */
1548 /* minutia within the feature list. */
1549 /* 1. Compute R 3 pixels opposite the feature direction from */
1550 /* feature point F. */
1551 /* 2. Find white pixel transitions P & Q within 12 steps from */
1552 /* from R perpendicular to the feature's direction. */
1553 /* 3. Find points B & D by walking white edge from P. */
1554 /* 4. Find points A & C by walking white edge from Q. */
1555 /* 5. Measure squared distances between A-B and C-D. */
1556 /* 6. Compute ratio of squared distances and compare against */
1557 /* threshold (2.25). If A-B sufficiently larger than C-D, */
1558 /* then assume NOT pore, otherwise flag the feature point F.*/
1559 /* If along the way, finding any of these points fails, then */
1560 /* assume the feature is a pore and flag it. */
1561 /* */
1562 /* A */
1563 /* _____._ */
1564 /* ----___ Q C */
1565 /* ------____ ---_.________.___ */
1566 /* ---_ */
1567 /* (valley) F.\ .R (ridge) */
1568 /* ____/ */
1569 /* ______---- ___-.--------.--- */
1570 /* ____--- P D */
1571 /* -----.- */
1572 /* B */
1573 /* */
1574 /* AB^2/CD^2 <= 2.25 then flag feature */
1575 /* */
1576
1577
1578 print2log("\nREMOVING PORES:\n");
1579
1580 /* Factor for converting integer directions into radians. */
1581 pi_factor = M_PI/(double)lfsparms->num_directions;
1582
1583 /* Initialize to the beginning of the minutia list. */
1584 i = 0;
1585 /* Foreach minutia remaining in the list ... */
1586 while(i < minutiae->num){
1587 /* Set temporary minutia pointer. */
1588 minutia = minutiae->list[i];
1589
1590 /* Initialize remove flag to FALSE. */
1591 removed = FALSE;
1592
1593 /* Compute block coords from minutia point. */
1594 blk_x = minutia->x / lfsparms->blocksize;
1595 blk_y = minutia->y / lfsparms->blocksize;
1596
1597 /* If minutia in LOW RIDGE FLOW or HIGH CURVATURE block */
1598 /* with a valid direction ... */
1599 if((*(low_flow_map+(blk_y*mw)+blk_x) ||
1600 *(high_curve_map+(blk_y*mw)+blk_x)) &&
1601 (*(direction_map+(blk_y*mw)+blk_x) >= 0)){
1602 /* Compute radian angle from minutia direction. */
1603 theta = (double)minutia->direction * pi_factor;
1604 /* Compute sine and cosine factors of this angle. */
1605 sin_theta = sin(theta);
1606 cos_theta = cos(theta);
1607 /* Translate the minutia point (ex. 3 pixels) in opposite */
1608 /* direction minutia is pointing. Call this point 'R'. */
1609 drx = (double)minutia->x -
1610 (sin_theta * (double)lfsparms->pores_trans_r);
1611 dry = (double)minutia->y +
1612 (cos_theta * (double)lfsparms->pores_trans_r);
1613 /* Need to truncate precision so that answers are consistent */
1614 /* on different computer architectures when rounding doubles. */
1615 drx = trunc_dbl_precision(drx, TRUNC_SCALE);
1616 dry = trunc_dbl_precision(dry, TRUNC_SCALE);
1617 rx = sround(drx);
1618 ry = sround(dry);
1619
1620 /* If 'R' is opposite color from minutia type ... */
1621 if(*(bdata+(ry*iw)+rx) != minutia->type){
1622
1623 /* Search a specified number of steps (ex. 12) from 'R' in a */
1624 /* perpendicular direction from the minutia direction until */
1625 /* the first white pixel is found. If a white pixel is */
1626 /* found within the specified number of steps, then call */
1627 /* this point 'P' (storing the point's edge pixel as well). */
1628 if(search_in_direction(&px, &py, &pex, &pey,
1629 minutia->type,
1630 rx, ry, -cos_theta, -sin_theta,
1631 lfsparms->pores_perp_steps,
1632 bdata, iw, ih)){
1633 /* Trace contour from P's edge pixel in counter-clockwise */
1634 /* scan and step along specified number of steps (ex. 10). */
1635 ret = trace_contour(&contour_x, &contour_y,
1636 &contour_ex, &contour_ey, &ncontour,
1637 lfsparms->pores_steps_fwd,
1638 px, py, px, py, pex, pey,
1639 SCAN_COUNTER_CLOCKWISE, bdata, iw, ih);
1640
1641 /* If system error occurred during trace ... */
1642 if(ret < 0){
1643 /* Return error code. */
1644 return(ret);
1645 }
1646
1647 /* If trace was not possible OR loop found OR */
1648 /* contour is incomplete ... */
1649 if((ret == IGNORE) ||
1650 (ret == LOOP_FOUND) ||
1651 (ncontour < lfsparms->pores_steps_fwd)){
1652 /* If contour allocated and returned ... */
1653 if((ret == LOOP_FOUND) ||
1654 (ncontour < lfsparms->pores_steps_fwd))
1655 /* Deallocate the contour. */
1656 free_contour(contour_x, contour_y,
1657 contour_ex, contour_ey);
1658
1659 print2log("%d,%d RMB\n", minutia->x, minutia->y);
1660
1661 /* Then remove the minutia. */
1662 if((ret = remove_minutia(i, minutiae)))
1663 /* If system error, return error code. */
1664 return(ret);
1665 /* Set remove flag to TRUE. */
1666 removed = TRUE;
1667 }
1668 /* Otherwise, traced contour is complete. */
1669 else{
1670 /* Store last point in contour as point 'B'. */
1671 bx = contour_x[ncontour-1];
1672 by = contour_y[ncontour-1];
1673 /* Deallocate the contour. */
1674 free_contour(contour_x, contour_y,
1675 contour_ex, contour_ey);
1676
1677 /* Trace contour from P's edge pixel in clockwise scan */
1678 /* and step along specified number of steps (ex. 8). */
1679 ret = trace_contour(&contour_x, &contour_y,
1680 &contour_ex, &contour_ey, &ncontour,
1681 lfsparms->pores_steps_bwd,
1682 px, py, px, py, pex, pey,
1683 SCAN_CLOCKWISE, bdata, iw, ih);
1684
1685 /* If system error occurred during trace ... */
1686 if(ret < 0){
1687 /* Return error code. */
1688 return(ret);
1689 }
1690
1691 /* If trace was not possible OR loop found OR */
1692 /* contour is incomplete ... */
1693 if((ret == IGNORE) ||
1694 (ret == LOOP_FOUND) ||
1695 (ncontour < lfsparms->pores_steps_bwd)){
1696 /* If contour allocated and returned ... */
1697 if((ret == LOOP_FOUND) ||
1698 (ncontour < lfsparms->pores_steps_bwd))
1699 /* Deallocate the contour. */
1700 free_contour(contour_x, contour_y,
1701 contour_ex, contour_ey);
1702
1703 print2log("%d,%d RMD\n", minutia->x, minutia->y);
1704
1705 /* Then remove the minutia. */
1706 if((ret = remove_minutia(i, minutiae)))
1707 /* If system error, return error code. */
1708 return(ret);
1709 /* Set remove flag to TRUE. */
1710 removed = TRUE;
1711 }
1712 /* Otherwise, traced contour is complete. */
1713 else{
1714 /* Store last point in contour as point 'D'. */
1715 dx = contour_x[ncontour-1];
1716 dy = contour_y[ncontour-1];
1717 /* Deallocate the contour. */
1718 free_contour(contour_x, contour_y,
1719 contour_ex, contour_ey);
1720 /* Search a specified number of steps (ex. 12) from */
1721 /* 'R' in opposite direction of that used to find */
1722 /* 'P' until the first white pixel is found. If a */
1723 /* white pixel is found within the specified number */
1724 /* of steps, then call this point 'Q' (storing the */
1725 /* point's edge pixel as well). */
1726 if(search_in_direction(&qx, &qy, &qex, &qey,
1727 minutia->type,
1728 rx, ry, cos_theta, sin_theta,
1729 lfsparms->pores_perp_steps,
1730 bdata, iw, ih)){
1731 /* Trace contour from Q's edge pixel in clockwise */
1732 /* scan and step along specified number of steps */
1733 /* (ex. 10). */
1734 ret = trace_contour(&contour_x, &contour_y,
1735 &contour_ex, &contour_ey, &ncontour,
1736 lfsparms->pores_steps_fwd,
1737 qx, qy, qx, qy, qex, qey,
1738 SCAN_CLOCKWISE, bdata, iw, ih);
1739
1740 /* If system error occurred during trace ... */
1741 if(ret < 0){
1742 /* Return error code. */
1743 return(ret);
1744 }
1745
1746 /* If trace was not possible OR loop found OR */
1747 /* contour is incomplete ... */
1748 if((ret == IGNORE) ||
1749 (ret == LOOP_FOUND) ||
1750 (ncontour < lfsparms->pores_steps_fwd)){
1751 /* If contour allocated and returned ... */
1752 if((ret == LOOP_FOUND) ||
1753 (ncontour < lfsparms->pores_steps_fwd))
1754 /* Deallocate the contour. */
1755 free_contour(contour_x, contour_y,
1756 contour_ex, contour_ey);
1757
1758 print2log("%d,%d RMA\n", minutia->x, minutia->y);
1759
1760 /* Then remove the minutia. */
1761 if((ret = remove_minutia(i, minutiae)))
1762 /* If system error, return error code. */
1763 return(ret);
1764 /* Set remove flag to TRUE. */
1765 removed = TRUE;
1766 }
1767 /* Otherwise, traced contour is complete. */
1768 else{
1769 /* Store last point in contour as point 'A'. */
1770 ax = contour_x[ncontour-1];
1771 ay = contour_y[ncontour-1];
1772 /* Deallocate the contour. */
1773 free_contour(contour_x, contour_y,
1774 contour_ex, contour_ey);
1775
1776 /* Trace contour from Q's edge pixel in */
1777 /* counter-clockwise scan and step along a */
1778 /* specified number of steps (ex. 8). */
1779 ret = trace_contour(&contour_x, &contour_y,
1780 &contour_ex, &contour_ey, &ncontour,
1781 lfsparms->pores_steps_bwd,
1782 qx, qy, qx, qy, qex, qey,
1783 SCAN_COUNTER_CLOCKWISE, bdata, iw, ih);
1784
1785 /* If system error occurred during scan ... */
1786 if(ret < 0){
1787 /* Return error code. */
1788 return(ret);
1789 }
1790
1791 /* If trace was not possible OR loop found OR */
1792 /* contour is incomplete ... */
1793 if((ret == IGNORE) ||
1794 (ret == LOOP_FOUND) ||
1795 (ncontour < lfsparms->pores_steps_bwd)){
1796 /* If contour allocated and returned ... */
1797 if((ret == LOOP_FOUND) ||
1798 (ncontour < lfsparms->pores_steps_bwd))
1799 /* Deallocate the contour. */
1800 free_contour(contour_x, contour_y,
1801 contour_ex, contour_ey);
1802
1803 print2log("%d,%d RMC\n",
1804 minutia->x, minutia->y);
1805
1806 /* Then remove the minutia. */
1807 if((ret = remove_minutia(i, minutiae)))
1808 /* If system error, return error code. */
1809 return(ret);
1810 /* Set remove flag to TRUE. */
1811 removed = TRUE;
1812 }
1813 /* Otherwise, traced contour is complete. */
1814 else{
1815 /* Store last point in contour as 'C'. */
1816 cx = contour_x[ncontour-1];
1817 cy = contour_y[ncontour-1];
1818 /* Deallocate the contour. */
1819 free_contour(contour_x, contour_y,
1820 contour_ex, contour_ey);
1821
1822 /* Compute squared distance between points */
1823 /* 'A' and 'B'. */
1824 ab2 = squared_distance(ax, ay, bx, by);
1825 /* Compute squared distance between points */
1826 /* 'C' and 'D'. */
1827 cd2 = squared_distance(cx, cy, dx, dy);
1828 /* If CD distance is not near zero */
1829 /* (ex. 0.5) ... */
1830 if(cd2 > lfsparms->pores_min_dist2){
1831 /* Compute ratio of squared distances. */
1832 ratio = ab2 / cd2;
1833
1834 /* If ratio is small enough (ex. 2.25)...*/
1835 if(ratio <= lfsparms->pores_max_ratio){
1836
1837 print2log("%d,%d ",
1838 minutia->x, minutia->y);
1839 print2log("R=%d,%d P=%d,%d B=%d,%d D=%d,%d Q=%d,%d A=%d,%d C=%d,%d ",
1840 rx, ry, px, py, bx, by, dx, dy, qx, qy, ax, ay, cx, cy);
1841 print2log("RMRATIO %f\n", ratio);
1842
1843 /* Then assume pore & remove minutia. */
1844 if((ret = remove_minutia(i, minutiae)))
1845 /* If system error, return code. */
1846 return(ret);
1847 /* Set remove flag to TRUE. */
1848 removed = TRUE;
1849 }
1850 /* Otherwise, ratio to big, so assume */
1851 /* legitimate minutia. */
1852 } /* Else, cd2 too small. */
1853 } /* Done with C. */
1854 } /* Done with A. */
1855 }
1856 /* Otherwise, Q not found ... */
1857 else{
1858
1859 print2log("%d,%d RMQ\n", minutia->x, minutia->y);
1860
1861 /* Then remove the minutia. */
1862 if((ret = remove_minutia(i, minutiae)))
1863 /* If system error, return error code. */
1864 return(ret);
1865 /* Set remove flag to TRUE. */
1866 removed = TRUE;
1867 } /* Done with Q. */
1868 } /* Done with D. */
1869 } /* Done with B. */
1870 }
1871 /* Otherwise, P not found ... */
1872 else{
1873
1874 print2log("%d,%d RMP\n", minutia->x, minutia->y);
1875
1876 /* Then remove the minutia. */
1877 if((ret = remove_minutia(i, minutiae)))
1878 /* If system error, return error code. */
1879 return(ret);
1880 /* Set remove flag to TRUE. */
1881 removed = TRUE;
1882 }
1883 } /* Else, R is on pixel the same color as type, so do not */
1884 /* remove minutia point and skip to next one. */
1885 } /* Else block is unreliable or has INVALID direction. */
1886
1887 /* If current minutia not removed ... */
1888 if(!removed)
1889 /* Bump to next minutia in list. */
1890 i++;
1891 /* Otherwise, next minutia has slid into slot of current removed one. */
1892
1893 } /* End While minutia remaining in list. */
1894
1895 /* Return normally. */
1896 return(0);
1897 }
1898
1899 /*************************************************************************
1900 **************************************************************************
1901 #cat: remove_or_adjust_side_minutiae_V2 - Removes loops or minutia points that
1902 #cat: are not on complete contours of specified length. If the
1903 #cat: contour is complete, then the minutia is adjusted based
1904 #cat: on a minmax analysis of the rotated y-coords of the contour.
1905
1906 Input:
1907 minutiae - list of true and false minutiae
1908 bdata - binary image data (0==while & 1==black)
1909 iw - width (in pixels) of image
1910 ih - height (in pixels) of image
1911 direction_map - map of image blocks containing directional ridge flow
1912 mw - width (in blocks) of the map
1913 mh - height (in blocks) of the map
1914 lfsparms - parameters and thresholds for controlling LFS
1915 Output:
1916 minutiae - list of pruned minutiae
1917 Return Code:
1918 Zero - successful completion
1919 Negative - system error
1920 **************************************************************************/
remove_or_adjust_side_minutiae_V2(MINUTIAE * minutiae,unsigned char * bdata,const int iw,const int ih,int * direction_map,const int mw,const int mh,const LFSPARMS * lfsparms)1921 static int remove_or_adjust_side_minutiae_V2(MINUTIAE *minutiae,
1922 unsigned char *bdata, const int iw, const int ih,
1923 int *direction_map, const int mw, const int mh,
1924 const LFSPARMS *lfsparms)
1925 {
1926 int i, j, ret;
1927 MINUTIA *minutia;
1928 double pi_factor, theta, sin_theta, cos_theta;
1929 int *contour_x, *contour_y, *contour_ex, *contour_ey, ncontour;
1930 int *rot_y, minloc;
1931 int *minmax_val, *minmax_i, *minmax_type, minmax_alloc, minmax_num;
1932 double drot_y;
1933 int bx, by;
1934
1935 print2log("\nADJUSTING SIDE MINUTIA:\n");
1936
1937 /* Allocate working memory for holding rotated y-coord of a */
1938 /* minutia's contour. */
1939 rot_y = (int *)malloc(((lfsparms->side_half_contour<<1)+1) * sizeof(int));
1940 if(rot_y == (int *)NULL){
1941 fprintf(stderr,
1942 "ERROR : remove_or_adjust_side_minutiae_V2 : malloc : rot_y\n");
1943 return(-630);
1944 }
1945
1946 /* Compute factor for converting integer directions to radians. */
1947 pi_factor = M_PI / (double)lfsparms->num_directions;
1948
1949 i = 0;
1950 /* Foreach minutia remaining in list ... */
1951 while(i < minutiae->num){
1952 /* Assign a temporary pointer. */
1953 minutia = minutiae->list[i];
1954
1955 /* Extract a contour centered on the minutia point (ex. 7 pixels */
1956 /* in both directions). */
1957 ret = get_centered_contour(&contour_x, &contour_y,
1958 &contour_ex, &contour_ey, &ncontour,
1959 lfsparms->side_half_contour,
1960 minutia->x, minutia->y, minutia->ex, minutia->ey,
1961 bdata, iw, ih);
1962
1963 /* If system error occurred ... */
1964 if(ret < 0){
1965 /* Deallocate working memory. */
1966 free(rot_y);
1967 /* Return error code. */
1968 return(ret);
1969 }
1970
1971 /* If we didn't succeed in extracting a complete contour for any */
1972 /* other reason ... */
1973 if((ret == LOOP_FOUND) ||
1974 (ret == IGNORE) ||
1975 (ret == INCOMPLETE)){
1976
1977 print2log("%d,%d RM1\n", minutia->x, minutia->y);
1978
1979 /* Remove minutia from list. */
1980 if((ret = remove_minutia(i, minutiae))){
1981 /* Deallocate working memory. */
1982 free(rot_y);
1983 /* Return error code. */
1984 return(ret);
1985 }
1986 /* No need to advance because next minutia has "slid" */
1987 /* into position pointed to by 'i'. */
1988 }
1989 /* Otherwise, a complete contour was found and extracted ... */
1990 else{
1991 /* Rotate contour points by negative angle of feature's direction. */
1992 /* The contour of a well-formed minutia point will form a bowl */
1993 /* shape concaved in the direction of the minutia. By rotating */
1994 /* the contour points by the negative angle of feature's direction */
1995 /* the bowl will be transformed to be concaved upwards and minima */
1996 /* and maxima of the transformed y-coords can be analyzed to */
1997 /* determine if the minutia is "well-formed" or not. If well- */
1998 /* formed then the position of the minutia point is adjusted. If */
1999 /* not well-formed, then the minutia point is removed altogether. */
2000
2001 /* Normal rotation of T degrees around the origin of */
2002 /* the point (x,y): */
2003 /* rx = x*cos(T) - y*sin(T) */
2004 /* ry = x*cos(T) + y*sin(T) */
2005 /* The rotation here is for -T degrees: */
2006 /* rx = x*cos(-T) - y*sin(-T) */
2007 /* ry = x*cos(-T) + y*sin(-T) */
2008 /* which can be written: */
2009 /* rx = x*cos(T) + y*sin(T) */
2010 /* ry = x*sin(T) - y*cos(T) */
2011
2012 /* Convert minutia's direction to radians. */
2013 theta = (double)minutia->direction * pi_factor;
2014 /* Compute sine and cosine values at theta for rotation. */
2015 sin_theta = sin(theta);
2016 cos_theta = cos(theta);
2017
2018 for(j = 0; j < ncontour; j++){
2019 /* We only need to rotate the y-coord (don't worry */
2020 /* about rotating the x-coord or contour edge pixels). */
2021 drot_y = ((double)contour_x[j] * sin_theta) -
2022 ((double)contour_y[j] * cos_theta);
2023 /* Need to truncate precision so that answers are consistent */
2024 /* on different computer architectures when rounding doubles. */
2025 drot_y = trunc_dbl_precision(drot_y, TRUNC_SCALE);
2026 rot_y[j] = sround(drot_y);
2027 }
2028
2029 /* Locate relative minima and maxima in vector of rotated */
2030 /* y-coords of current minutia's contour. */
2031 if((ret = minmaxs(&minmax_val, &minmax_type, &minmax_i,
2032 &minmax_alloc, &minmax_num,
2033 rot_y, ncontour))){
2034 /* If system error, then deallocate working memories. */
2035 free(rot_y);
2036 free_contour(contour_x, contour_y, contour_ex, contour_ey);
2037 /* Return error code. */
2038 return(ret);
2039 }
2040
2041 /* If one and only one minima was found in rotated y-coord */
2042 /* of contour ... */
2043 if((minmax_num == 1) &&
2044 (minmax_type[0] == -1)){
2045
2046 print2log("%d,%d ", minutia->x, minutia->y);
2047
2048 /* Reset loation of minutia point to contour point at minima. */
2049 minutia->x = contour_x[minmax_i[0]];
2050 minutia->y = contour_y[minmax_i[0]];
2051 minutia->ex = contour_ex[minmax_i[0]];
2052 minutia->ey = contour_ey[minmax_i[0]];
2053
2054 /* Must check if adjusted minutia is now in INVALID block ... */
2055 bx = minutia->x/lfsparms->blocksize;
2056 by = minutia->y/lfsparms->blocksize;
2057 if(*(direction_map+(by*mw)+bx) == INVALID_DIR){
2058 /* Remove minutia from list. */
2059 if((ret = remove_minutia(i, minutiae))){
2060 /* Deallocate working memory. */
2061 free(rot_y);
2062 free_contour(contour_x, contour_y, contour_ex, contour_ey);
2063 if(minmax_alloc > 0){
2064 free(minmax_val);
2065 free(minmax_type);
2066 free(minmax_i);
2067 }
2068 /* Return error code. */
2069 return(ret);
2070 }
2071 /* No need to advance because next minutia has "slid" */
2072 /* into position pointed to by 'i'. */
2073
2074 print2log("RM2\n");
2075 }
2076 else{
2077 /* Advance to the next minutia in the list. */
2078 i++;
2079 print2log("AD1 %d,%d\n", minutia->x, minutia->y);
2080 }
2081
2082 }
2083 /* If exactly 3 min/max found and they are min-max-min ... */
2084 else if((minmax_num == 3) &&
2085 (minmax_type[0] == -1)){
2086 /* Choose minima location with smallest rotated y-coord. */
2087 if(minmax_val[0] < minmax_val[2])
2088 minloc = minmax_i[0];
2089 else
2090 minloc = minmax_i[2];
2091
2092 print2log("%d,%d ", minutia->x, minutia->y);
2093
2094 /* Reset loation of minutia point to contour point at minima. */
2095 minutia->x = contour_x[minloc];
2096 minutia->y = contour_y[minloc];
2097 minutia->ex = contour_ex[minloc];
2098 minutia->ey = contour_ey[minloc];
2099
2100 /* Must check if adjusted minutia is now in INVALID block ... */
2101 bx = minutia->x/lfsparms->blocksize;
2102 by = minutia->y/lfsparms->blocksize;
2103 if(*(direction_map+(by*mw)+bx) == INVALID_DIR){
2104 /* Remove minutia from list. */
2105 if((ret = remove_minutia(i, minutiae))){
2106 /* Deallocate working memory. */
2107 free(rot_y);
2108 free_contour(contour_x, contour_y, contour_ex, contour_ey);
2109 if(minmax_alloc > 0){
2110 free(minmax_val);
2111 free(minmax_type);
2112 free(minmax_i);
2113 }
2114 /* Return error code. */
2115 return(ret);
2116 }
2117 /* No need to advance because next minutia has "slid" */
2118 /* into position pointed to by 'i'. */
2119
2120 print2log("RM3\n");
2121 }
2122 else{
2123 /* Advance to the next minutia in the list. */
2124 i++;
2125 print2log("AD2 %d,%d\n", minutia->x, minutia->y);
2126 }
2127 }
2128 /* Otherwise, ... */
2129 else{
2130
2131 print2log("%d,%d RM4\n", minutia->x, minutia->y);
2132
2133 /* Remove minutia from list. */
2134 if((ret = remove_minutia(i, minutiae))){
2135 /* If system error, then deallocate working memories. */
2136 free(rot_y);
2137 free_contour(contour_x, contour_y, contour_ex, contour_ey);
2138 if(minmax_alloc > 0){
2139 free(minmax_val);
2140 free(minmax_type);
2141 free(minmax_i);
2142 }
2143 /* Return error code. */
2144 return(ret);
2145 }
2146 /* No need to advance because next minutia has "slid" */
2147 /* into position pointed to by 'i'. */
2148 }
2149
2150 /* Deallocate contour and min/max buffers. */
2151 free_contour(contour_x, contour_y, contour_ex, contour_ey);
2152 if(minmax_alloc > 0){
2153 free(minmax_val);
2154 free(minmax_type);
2155 free(minmax_i);
2156 }
2157 } /* End else contour extracted. */
2158 } /* End while not end of minutiae list. */
2159
2160 /* Deallocate working memory. */
2161 free(rot_y);
2162
2163 /* Return normally. */
2164 return(0);
2165 }
2166
2167 /*************************************************************************
2168 **************************************************************************
2169 #cat: remove_false_minutia_V2 - Takes a list of true and false minutiae and
2170 #cat: attempts to detect and remove the false minutiae based
2171 #cat: on a series of tests.
2172
2173 Input:
2174 minutiae - list of true and false minutiae
2175 bdata - binary image data (0==while & 1==black)
2176 iw - width (in pixels) of image
2177 ih - height (in pixels) of image
2178 direction_map - map of image blocks containing directional ridge flow
2179 low_flow_map - map of image blocks flagged as LOW RIDGE FLOW
2180 high_curve_map - map of image blocks flagged as HIGH CURVATURE
2181 mw - width in blocks of the maps
2182 mh - height in blocks of the maps
2183 lfsparms - parameters and thresholds for controlling LFS
2184 Output:
2185 minutiae - list of pruned minutiae
2186 Return Code:
2187 Zero - successful completion
2188 Negative - system error
2189 **************************************************************************/
remove_false_minutia_V2(MINUTIAE * minutiae,unsigned char * bdata,const int iw,const int ih,int * direction_map,int * low_flow_map,int * high_curve_map,const int mw,const int mh,const LFSPARMS * lfsparms)2190 int remove_false_minutia_V2(MINUTIAE *minutiae,
2191 unsigned char *bdata, const int iw, const int ih,
2192 int *direction_map, int *low_flow_map, int *high_curve_map,
2193 const int mw, const int mh, const LFSPARMS *lfsparms)
2194 {
2195 int ret;
2196
2197 /* 1. Sort minutiae points top-to-bottom and left-to-right. */
2198 if((ret = sort_minutiae_y_x(minutiae, iw, ih))){
2199 return(ret);
2200 }
2201
2202 /* 2. Remove minutiae on lakes (filled with white pixels) and */
2203 /* islands (filled with black pixels), both defined by a pair of */
2204 /* minutia points. */
2205 if((ret = remove_islands_and_lakes(minutiae, bdata, iw, ih, lfsparms))){
2206 return(ret);
2207 }
2208
2209 /* 3. Remove minutiae on holes in the binary image defined by a */
2210 /* single point. */
2211 if((ret = remove_holes(minutiae, bdata, iw, ih, lfsparms))){
2212 return(ret);
2213 }
2214
2215 /* 4. Remove minutiae that point sufficiently close to a block with */
2216 /* INVALID direction. */
2217 if((ret = remove_pointing_invblock_V2(minutiae, direction_map, mw, mh,
2218 lfsparms))){
2219 return(ret);
2220 }
2221
2222 /* 5. Remove minutiae that are sufficiently close to a block with */
2223 /* INVALID direction. */
2224 if((ret = remove_near_invblock_V2(minutiae, direction_map, mw, mh,
2225 lfsparms))){
2226 return(ret);
2227 }
2228
2229 /* 6. Remove or adjust minutiae that reside on the side of a ridge */
2230 /* or valley. */
2231 if((ret = remove_or_adjust_side_minutiae_V2(minutiae, bdata, iw, ih,
2232 direction_map, mw, mh, lfsparms))){
2233 return(ret);
2234 }
2235
2236 /* 7. Remove minutiae that form a hook on the side of a ridge or valley. */
2237 if((ret = remove_hooks(minutiae, bdata, iw, ih, lfsparms))){
2238 return(ret);
2239 }
2240
2241 /* 8. Remove minutiae that are on opposite sides of an overlap. */
2242 if((ret = remove_overlaps(minutiae, bdata, iw, ih, lfsparms))){
2243 return(ret);
2244 }
2245
2246 /* 9. Remove minutiae that are "irregularly" shaped. */
2247 if((ret = remove_malformations(minutiae, bdata, iw, ih,
2248 low_flow_map, mw, mh, lfsparms))){
2249 return(ret);
2250 }
2251
2252 /* 10. Remove minutiae that form long, narrow, loops in the */
2253 /* "unreliable" regions in the binary image. */
2254 if((ret = remove_pores_V2(minutiae, bdata, iw, ih,
2255 direction_map, low_flow_map, high_curve_map,
2256 mw, mh, lfsparms))){
2257 return(ret);
2258 }
2259
2260 /* 11. Remove minutiae on image edge */
2261 if((ret = remove_perimeter_pts(minutiae, bdata, iw, ih, lfsparms))) {
2262 return (ret);
2263 }
2264
2265 return(0);
2266 }
2267
2268