GCC Code Coverage Report

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