GCC Code Coverage Report

Directory: ./
File: libfprint/nbis/mindtct/minutia.c
Date: 2024-09-16 14:36:32
Exec Total Coverage
Lines: 310 379 81.8%
Functions: 18 21 85.7%
Branches: 140 204 68.6%
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: MINUTIA.C
49 AUTHOR: Michael D. Garris
50 DATE: 05/11/1999
51 UPDATED: 10/04/1999 Version 2 by MDG
52 UPDATED: 09/13/2004
53
54 Contains routines responsible for detecting initial minutia
55 points as part of the NIST Latent Fingerprint System (LFS).
56
57 ***********************************************************************
58 ROUTINES:
59 alloc_minutiae()
60 realloc_minutiae()
61 detect_minutiae()
62 detect_minutiae_V2()
63 update_minutiae()
64 update_minutiae_V2()
65 sort_minutiae_y_x()
66 sort_minutiae_x_y()
67 rm_dup_minutiae()
68 dump_minutiae()
69 dump_minutiae_pts()
70 dump_reliable_minutiae_pts()
71 create_minutia()
72 free_minutiae()
73 free_minutia()
74 remove_minutia()
75 join_minutia()
76 minutia_type()
77 is_minutia_appearing()
78 choose_scan_direction()
79 scan4minutiae()
80 scan4minutiae_horizontally()
81 scan4minutiae_horizontally_V2()
82 scan4minutiae_vertically()
83 scan4minutiae_vertically_V2()
84 rescan4minutiae_horizontally()
85 rescan4minutiae_vertically()
86 rescan_partial_horizontally()
87 rescan_partial_vertically()
88 get_nbr_block_index()
89 adjust_horizontal_rescan()
90 adjust_vertical_rescan()
91 process_horizontal_scan_minutia()
92 process_horizontal_scan_minutia_V2()
93 process_vertical_scan_minutia()
94 process_vertical_scan_minutia_V2()
95 adjust_high_curvature_minutia()
96 adjust_high_curvature_minutia_V2()
97 get_low_curvature_direction()
98
99 ***********************************************************************/
100
101 #include <stdio.h>
102 #include <lfs.h>
103
104 /*************************************************************************
105 **************************************************************************
106 #cat: alloc_minutiae - Allocates and initializes a minutia list based on the
107 #cat: specified maximum number of minutiae to be detected.
108
109 Input:
110 DEFAULT_BOZORTH_MINUTIAE - number of minutia to be allocated in list
111 Output:
112 ominutiae - points to the allocated minutiae list
113 Return Code:
114 Zero - successful completion
115 Negative - system error
116 **************************************************************************/
117 48 int alloc_minutiae(MINUTIAE **ominutiae, const int DEFAULT_BOZORTH_MINUTIAE)
118 {
119 48 MINUTIAE *minutiae;
120
121 48 minutiae = (MINUTIAE *)g_malloc(sizeof(MINUTIAE));
122 48 minutiae->list = (MINUTIA **)g_malloc(DEFAULT_BOZORTH_MINUTIAE * sizeof(MINUTIA *));
123
124 48 minutiae->alloc = DEFAULT_BOZORTH_MINUTIAE;
125 48 minutiae->num = 0;
126
127 48 *ominutiae = minutiae;
128 48 return(0);
129 }
130
131 /*************************************************************************
132 **************************************************************************
133 #cat: realloc_minutiae - Reallocates a previously allocated minutia list
134 #cat: extending its allocated length based on the specified
135 #cat: increment.
136
137 Input:
138 minutiae - previously allocated list of minutiae points
139 DEFAULT_BOZORTH_MINUTIAE - number of minutia to be allocated in list
140 Output:
141 minutiae - extended list of minutiae points
142 Return Code:
143 Zero - successful completion
144 Negative - system error
145 **************************************************************************/
146 2 int realloc_minutiae(MINUTIAE *minutiae, const int incr_minutiae)
147 {
148 2 minutiae->alloc += incr_minutiae;
149 4 minutiae->list = (MINUTIA **)g_realloc(minutiae->list,
150 2 minutiae->alloc * sizeof(MINUTIA *));
151
152 2 return(0);
153 }
154
155 /*************************************************************************
156 **************************************************************************
157 #cat: detect_minutiae - Takes a binary image and its associated IMAP and
158 #cat: NMAP matrices and scans each image block for potential
159 #cat: minutia points.
160
161 Input:
162 bdata - binary image data (0==while & 1==black)
163 iw - width (in pixels) of image
164 ih - height (in pixels) of image
165 imap - matrix of ridge flow directions
166 nmap - IMAP augmented with blocks of HIGH-CURVATURE and
167 blocks which have no neighboring valid directions.
168 mw - width (in blocks) of IMAP and NMAP matrices.
169 mh - height (in blocks) of IMAP and NMAP matrices.
170 lfsparms - parameters and thresholds for controlling LFS
171 Output:
172 minutiae - points to a list of detected minutia structures
173 Return Code:
174 Zero - successful completion
175 Negative - system error
176 **************************************************************************/
177
178 /*************************************************************************
179 **************************************************************************
180 #cat: detect_minutiae_V2 - Takes a binary image and its associated
181 #cat: Direction and Low Flow Maps and scans each image block
182 #cat: with valid direction for minutia points. Minutia points
183 #cat: detected in LOW FLOW blocks are set with lower reliability.
184
185 Input:
186 bdata - binary image data (0==while & 1==black)
187 iw - width (in pixels) of image
188 ih - height (in pixels) of image
189 direction_map - map of image blocks containing directional ridge flow
190 low_flow_map - map of image blocks flagged as LOW RIDGE FLOW
191 high_curve_map - map of image blocks flagged as HIGH CURVATURE
192 mw - width (in blocks) of the maps
193 mh - height (in blocks) of the maps
194 lfsparms - parameters and thresholds for controlling LFS
195 Output:
196 minutiae - points to a list of detected minutia structures
197 Return Code:
198 Zero - successful completion
199 Negative - system error
200 **************************************************************************/
201 48 int detect_minutiae_V2(MINUTIAE *minutiae,
202 unsigned char *bdata, const int iw, const int ih,
203 int *direction_map, int *low_flow_map, int *high_curve_map,
204 const int mw, const int mh,
205 const LFSPARMS *lfsparms)
206 {
207 48 int ret;
208 48 int *pdirection_map, *plow_flow_map, *phigh_curve_map;
209
210 /* Pixelize the maps by assigning block values to individual pixels. */
211
1/2
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
 48 if((ret = pixelize_map(&pdirection_map, iw, ih, direction_map, mw, mh,
212 48 lfsparms->blocksize))){
213 return(ret);
214 }
215
216
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 if((ret = pixelize_map(&plow_flow_map, iw, ih, low_flow_map, mw, mh,
217 48 lfsparms->blocksize))){
218 ✗ g_free(pdirection_map);
219 ✗ return(ret);
220 }
221
222
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 if((ret = pixelize_map(&phigh_curve_map, iw, ih, high_curve_map, mw, mh,
223 48 lfsparms->blocksize))){
224 ✗ g_free(pdirection_map);
225 ✗ g_free(plow_flow_map);
226 ✗ return(ret);
227 }
228
229
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
 48 if((ret = scan4minutiae_horizontally_V2(minutiae, bdata, iw, ih,
230 pdirection_map, plow_flow_map, phigh_curve_map, lfsparms))){
231 ✗ g_free(pdirection_map);
232 ✗ g_free(plow_flow_map);
233 ✗ g_free(phigh_curve_map);
234 ✗ return(ret);
235 }
236
237
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
 48 if((ret = scan4minutiae_vertically_V2(minutiae, bdata, iw, ih,
238 pdirection_map, plow_flow_map, phigh_curve_map, lfsparms))){
239 ✗ g_free(pdirection_map);
240 ✗ g_free(plow_flow_map);
241 ✗ g_free(phigh_curve_map);
242 ✗ return(ret);
243 }
244
245 /* Deallocate working memories. */
246 48 g_free(pdirection_map);
247 48 g_free(plow_flow_map);
248 48 g_free(phigh_curve_map);
249
250 /* Return normally. */
251 48 return(0);
252 }
253
254 /*************************************************************************
255 **************************************************************************
256 #cat: update_minutiae - Takes a detected minutia point and (if it is not
257 #cat: determined to already be in the minutiae list) adds it to
258 #cat: the list.
259
260 Input:
261 minutia - minutia structure for detected point
262 bdata - binary image data (0==while & 1==black)
263 iw - width (in pixels) of image
264 ih - height (in pixels) of image
265 lfsparms - parameters and thresholds for controlling LFS
266 Output:
267 minutiae - points to a list of detected minutia structures
268 Return Code:
269 Zero - minutia added to successfully added to minutiae list
270 IGNORE - minutia is to be ignored (already in the minutiae list)
271 Negative - system error
272 **************************************************************************/
273 ✗ int update_minutiae(MINUTIAE *minutiae, MINUTIA *minutia,
274 unsigned char *bdata, const int iw, const int ih,
275 const LFSPARMS *lfsparms)
276 {
277 ✗ int i, ret, dy, dx, delta_dir;
278 ✗ int qtr_ndirs, full_ndirs;
279
280 /* Check to see if minutiae list is full ... if so, then extend */
281 /* the length of the allocated list of minutia points. */
282 ✗ if(minutiae->num >= minutiae->alloc){
283 ✗ if((ret = realloc_minutiae(minutiae, MAX_MINUTIAE)))
284 return(ret);
285 }
286
287 /* Otherwise, there is still room for more minutia. */
288
289 /* Compute quarter of possible directions in a semi-circle */
290 /* (ie. 45 degrees). */
291 ✗ qtr_ndirs = lfsparms->num_directions>>2;
292
293 /* Compute number of directions in full circle. */
294 ✗ full_ndirs = lfsparms->num_directions<<1;
295
296 /* Is the minutiae list empty? */
297 ✗ if(minutiae->num > 0){
298 /* Foreach minutia stored in the list... */
299 ✗ for(i = 0; i < minutiae->num; i++){
300 /* If x distance between new minutia and current list minutia */
301 /* are sufficiently close... */
302 ✗ dx = abs(minutiae->list[i]->x - minutia->x);
303 ✗ if(dx < lfsparms->max_minutia_delta){
304 /* If y distance between new minutia and current list minutia */
305 /* are sufficiently close... */
306 ✗ dy = abs(minutiae->list[i]->y - minutia->y);
307 ✗ if(dy < lfsparms->max_minutia_delta){
308 /* If new minutia and current list minutia are same type... */
309 ✗ if(minutiae->list[i]->type == minutia->type){
310 /* Test to see if minutiae have similar directions. */
311 /* Take minimum of computed inner and outer */
312 /* direction differences. */
313 ✗ delta_dir = abs(minutiae->list[i]->direction -
314 ✗ minutia->direction);
315 ✗ delta_dir = min(delta_dir, full_ndirs-delta_dir);
316 /* If directional difference is <= 45 degrees... */
317 ✗ if(delta_dir <= qtr_ndirs){
318 /* If new minutia and current list minutia share */
319 /* the same point... */
320 ✗ if((dx==0) && (dy==0)){
321 /* Then the minutiae match, so don't add the new one */
322 /* to the list. */
323 return(IGNORE);
324 }
325 /* Othewise, check if they share the same contour. */
326 /* Start by searching "max_minutia_delta" steps */
327 /* clockwise. */
328 /* If new minutia point found on contour... */
329 ✗ if(search_contour(minutia->x, minutia->y,
330 lfsparms->max_minutia_delta,
331 minutiae->list[i]->x, minutiae->list[i]->y,
332 minutiae->list[i]->ex, minutiae->list[i]->ey,
333 SCAN_CLOCKWISE, bdata, iw, ih)){
334 /* Consider the new minutia to be the same as the */
335 /* current list minutia, so don't add the new one */
336 /* to the list. */
337 return(IGNORE);
338 }
339 /* Now search "max_minutia_delta" steps counter- */
340 /* clockwise along contour. */
341 /* If new minutia point found on contour... */
342 ✗ if(search_contour(minutia->x, minutia->y,
343 ✗ lfsparms->max_minutia_delta,
344 minutiae->list[i]->x, minutiae->list[i]->y,
345 ✗ minutiae->list[i]->ex, minutiae->list[i]->ey,
346 SCAN_COUNTER_CLOCKWISE, bdata, iw, ih)){
347 /* Consider the new minutia to be the same as the */
348 /* current list minutia, so don't add the new one */
349 /* to the list. */
350 return(IGNORE);
351 }
352
353 /* Otherwise, new minutia and current list minutia do */
354 /* not share the same contour, so although they are */
355 /* similar in type and location, treat them as 2 */
356 /* different minutia. */
357
358 } /* Otherwise, directions are too different. */
359 } /* Otherwise, minutiae are different type. */
360 } /* Otherwise, minutiae too far apart in Y. */
361 } /* Otherwise, minutiae too far apart in X. */
362 } /* End FOR minutia in list. */
363 } /* Otherwise, minutiae list is empty. */
364
365 /* Otherwise, assume new minutia is not in the list, so add it. */
366 ✗ minutiae->list[minutiae->num] = minutia;
367 ✗ (minutiae->num)++;
368
369 /* New minutia was successfully added to the list. */
370 /* Return normally. */
371 ✗ return(0);
372 }
373
374 /*************************************************************************
375 **************************************************************************
376 #cat: update_minutiae_V2 - Takes a detected minutia point and (if it is not
377 #cat: determined to already be in the minutiae list or the
378 #cat: new point is determined to be "more compatible") adds
379 #cat: it to the list.
380
381 Input:
382 minutia - minutia structure for detected point
383 scan_dir - orientation of scan when minutia was detected
384 dmapval - directional ridge flow of block minutia is in
385 bdata - binary image data (0==while & 1==black)
386 iw - width (in pixels) of image
387 ih - height (in pixels) of image
388 lfsparms - parameters and thresholds for controlling LFS
389 Output:
390 minutiae - points to a list of detected minutia structures
391 Return Code:
392 Zero - minutia added to successfully added to minutiae list
393 IGNORE - minutia is to be ignored (already in the minutiae list)
394 Negative - system error
395 **************************************************************************/
396 50149 int update_minutiae_V2(MINUTIAE *minutiae, MINUTIA *minutia,
397 const int scan_dir, const int dmapval,
398 unsigned char *bdata, const int iw, const int ih,
399 const LFSPARMS *lfsparms)
400 {
401 50149 int i, ret, dy, dx, delta_dir;
402 50149 int qtr_ndirs, full_ndirs;
403 50149 int map_scan_dir;
404
405 /* Check to see if minutiae list is full ... if so, then extend */
406 /* the length of the allocated list of minutia points. */
407
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 50147 times.
 50149 if(minutiae->num >= minutiae->alloc){
408
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 if((ret = realloc_minutiae(minutiae, MAX_MINUTIAE)))
409 return(ret);
410 }
411
412 /* Otherwise, there is still room for more minutia. */
413
414 /* Compute quarter of possible directions in a semi-circle */
415 /* (ie. 45 degrees). */
416 50149 qtr_ndirs = lfsparms->num_directions>>2;
417
418 /* Compute number of directions in full circle. */
419 50149 full_ndirs = lfsparms->num_directions<<1;
420
421 /* Is the minutiae list empty? */
422
2/2
✓ Branch 0 taken 50101 times.
✓ Branch 1 taken 48 times.
 50149 if(minutiae->num > 0){
423 /* Foreach minutia stored in the list (in reverse order) ... */
424
2/2
✓ Branch 0 taken 21818512 times.
✓ Branch 1 taken 41537 times.
 21860049 for(i = minutiae->num-1; i >= 0; i--){
425 /* If x distance between new minutia and current list minutia */
426 /* are sufficiently close... */
427 21818512 dx = abs(minutiae->list[i]->x - minutia->x);
428
2/2
✓ Branch 0 taken 1922139 times.
✓ Branch 1 taken 19896373 times.
 21818512 if(dx < lfsparms->max_minutia_delta){
429 /* If y distance between new minutia and current list minutia */
430 /* are sufficiently close... */
431 1922139 dy = abs(minutiae->list[i]->y - minutia->y);
432
2/2
✓ Branch 0 taken 191544 times.
✓ Branch 1 taken 1730595 times.
 1922139 if(dy < lfsparms->max_minutia_delta){
433 /* If new minutia and current list minutia are same type... */
434
2/2
✓ Branch 0 taken 113548 times.
✓ Branch 1 taken 77996 times.
 191544 if(minutiae->list[i]->type == minutia->type){
435 /* Test to see if minutiae have similar directions. */
436 /* Take minimum of computed inner and outer */
437 /* direction differences. */
438 113548 delta_dir = abs(minutiae->list[i]->direction -
439 113548 minutia->direction);
440 113548 delta_dir = min(delta_dir, full_ndirs-delta_dir);
441 /* If directional difference is <= 45 degrees... */
442
2/2
✓ Branch 0 taken 57312 times.
✓ Branch 1 taken 56236 times.
 113548 if(delta_dir <= qtr_ndirs){
443 /* If new minutia and current list minutia share */
444 /* the same point... */
445
2/2
✓ Branch 0 taken 2418 times.
✓ Branch 1 taken 54894 times.
 57312 if((dx==0) && (dy==0)){
446 /* Then the minutiae match, so don't add the new one */
447 /* to the list. */
448 return(IGNORE);
449 }
450 /* Othewise, check if they share the same contour. */
451 /* Start by searching "max_minutia_delta" steps */
452 /* clockwise. */
453 /* If new minutia point found on contour... */
454
2/2
✓ Branch 1 taken 44805 times.
✓ Branch 2 taken 10089 times.
 54894 if(search_contour(minutia->x, minutia->y,
455 lfsparms->max_minutia_delta,
456 minutiae->list[i]->x, minutiae->list[i]->y,
457 minutiae->list[i]->ex, minutiae->list[i]->ey,
458
2/2
✓ Branch 0 taken 5932 times.
✓ Branch 1 taken 38873 times.
 44805 SCAN_CLOCKWISE, bdata, iw, ih) ||
459 44805 search_contour(minutia->x, minutia->y,
460 44805 lfsparms->max_minutia_delta,
461 minutiae->list[i]->x, minutiae->list[i]->y,
462 44805 minutiae->list[i]->ex, minutiae->list[i]->ey,
463 SCAN_COUNTER_CLOCKWISE, bdata, iw, ih)){
464 /* If new minutia has VALID block direction ... */
465
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 16021 times.
 16021 if(dmapval >= 0){
466 /* Derive feature scan direction compatible */
467 /* with VALID direction. */
468 32042 map_scan_dir = choose_scan_direction(dmapval,
469 16021 lfsparms->num_directions);
470 /* If map scan direction compatible with scan */
471 /* direction in which new minutia was found ... */
472
2/2
✓ Branch 0 taken 6146 times.
✓ Branch 1 taken 9875 times.
 16021 if(map_scan_dir == scan_dir){
473 /* Then choose the new minutia over the one */
474 /* currently in the list. */
475
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 9875 times.
 9875 if((ret = remove_minutia(i, minutiae))){
476 ✗ return(ret);
477 }
478 /* Continue on ... */
479 }
480 else
481 /* Othersize, scan directions not compatible...*/
482 /* so choose to keep the current minutia in */
483 /* the list and ignore the new one. */
484 return(IGNORE);
485 }
486 else{
487 /* Otherwise, no reason to believe new minutia */
488 /* is any better than the current one in the list,*/
489 /* so consider the new minutia to be the same as */
490 /* the current list minutia, and don't add the new*/
491 /* one to the list. */
492 return(IGNORE);
493 }
494 }
495
496 /* Otherwise, new minutia and current list minutia do */
497 /* not share the same contour, so although they are */
498 /* similar in type and location, treat them as 2 */
499 /* different minutia. */
500
501 } /* Otherwise, directions are too different. */
502 } /* Otherwise, minutiae are different type. */
503 } /* Otherwise, minutiae too far apart in Y. */
504 } /* Otherwise, minutiae too far apart in X. */
505 } /* End FOR minutia in list. */
506 } /* Otherwise, minutiae list is empty. */
507
508 /* Otherwise, assume new minutia is not in the list, or those that */
509 /* were close neighbors were selectively removed, so add it. */
510 41585 minutiae->list[minutiae->num] = minutia;
511 41585 (minutiae->num)++;
512
513 /* New minutia was successfully added to the list. */
514 /* Return normally. */
515 41585 return(0);
516 }
517
518 /*************************************************************************
519 **************************************************************************
520 #cat: sort_minutiae_y_x - Takes a list of minutia points and sorts them
521 #cat: top-to-bottom and then left-to-right.
522
523 Input:
524 minutiae - list of minutiae
525 iw - width (in pixels) of image
526 ih - height (in pixels) of image
527 Output:
528 minutiae - list of sorted minutiae
529 Return Code:
530 Zero - successful completion
531 Negative - system error
532 **************************************************************************/
533 48 int sort_minutiae_y_x(MINUTIAE *minutiae, const int iw, const int ih)
534 {
535 48 int *ranks, *order;
536 48 int i, ret;
537 48 MINUTIA **newlist;
538
539 /* Allocate a list of integers to hold 1-D image pixel offsets */
540 /* for each of the 2-D minutia coordinate points. */
541 48 ranks = (int *)g_malloc(minutiae->num * sizeof(int));
542
543 /* Compute 1-D image pixel offsets form 2-D minutia coordinate points. */
544
2/2
✓ Branch 1 taken 31710 times.
✓ Branch 2 taken 48 times.
 31806 for(i = 0; i < minutiae->num; i++)
545 31710 ranks[i] = (minutiae->list[i]->y * iw) + minutiae->list[i]->x;
546
547 /* Get sorted order of minutiae. */
548
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
 48 if((ret = sort_indices_int_inc(&order, ranks, minutiae->num))){
549 ✗ g_free(ranks);
550 ✗ return(ret);
551 }
552
553 /* Allocate new MINUTIA list to hold sorted minutiae. */
554 48 newlist = (MINUTIA **)g_malloc(minutiae->num * sizeof(MINUTIA *));
555
556 /* Put minutia into sorted order in new list. */
557
2/2
✓ Branch 1 taken 31710 times.
✓ Branch 2 taken 48 times.
 31806 for(i = 0; i < minutiae->num; i++)
558 31710 newlist[i] = minutiae->list[order[i]];
559
560 /* Deallocate non-sorted list of minutia pointers. */
561 48 g_free(minutiae->list);
562 /* Assign new sorted list of minutia to minutiae list. */
563 48 minutiae->list = newlist;
564
565 /* Free the working memories supporting the sort. */
566 48 g_free(order);
567 48 g_free(ranks);
568
569 /* Return normally. */
570 48 return(0);
571 }
572
573 /*************************************************************************
574 **************************************************************************
575 #cat: sort_minutiae_x_y - Takes a list of minutia points and sorts them
576 #cat: left-to-right and then top-to-bottom.
577
578 Input:
579 minutiae - list of minutiae
580 iw - width (in pixels) of image
581 ih - height (in pixels) of image
582 Output:
583 minutiae - list of sorted minutiae
584 Return Code:
585 Zero - successful completion
586 Negative - system error
587 **************************************************************************/
588 48 int sort_minutiae_x_y(MINUTIAE *minutiae, const int iw, const int ih)
589 {
590 48 int *ranks, *order;
591 48 int i, ret;
592 48 MINUTIA **newlist;
593
594 /* Allocate a list of integers to hold 1-D image pixel offsets */
595 /* for each of the 2-D minutia coordinate points. */
596 48 ranks = (int *)g_malloc(minutiae->num * sizeof(int));
597
598 /* Compute 1-D image pixel offsets form 2-D minutia coordinate points. */
599
2/2
✓ Branch 1 taken 3495 times.
✓ Branch 2 taken 48 times.
 3591 for(i = 0; i < minutiae->num; i++)
600 3495 ranks[i] = (minutiae->list[i]->x * iw) + minutiae->list[i]->y;
601
602 /* Get sorted order of minutiae. */
603
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 48 times.
 48 if((ret = sort_indices_int_inc(&order, ranks, minutiae->num))){
604 ✗ g_free(ranks);
605 ✗ return(ret);
606 }
607
608 /* Allocate new MINUTIA list to hold sorted minutiae. */
609 48 newlist = (MINUTIA **)g_malloc(minutiae->num * sizeof(MINUTIA *));
610
611 /* Put minutia into sorted order in new list. */
612
2/2
✓ Branch 1 taken 3495 times.
✓ Branch 2 taken 48 times.
 3591 for(i = 0; i < minutiae->num; i++)
613 3495 newlist[i] = minutiae->list[order[i]];
614
615 /* Deallocate non-sorted list of minutia pointers. */
616 48 g_free(minutiae->list);
617 /* Assign new sorted list of minutia to minutiae list. */
618 48 minutiae->list = newlist;
619
620 /* Free the working memories supporting the sort. */
621 48 g_free(order);
622 48 g_free(ranks);
623
624 /* Return normally. */
625 48 return(0);
626 }
627
628 /*************************************************************************
629 **************************************************************************
630 #cat: rm_dup_minutiae - Takes a list of minutiae sorted in some adjacent order
631 #cat: and detects and removes redundant minutia that have the
632 #cat: same exact pixel coordinate locations (even if other
633 #cat: attributes may differ).
634
635 Input:
636 mintuiae - list of sorted minutiae
637 Output:
638 mintuiae - list of sorted minutiae with duplicates removed
639 Return Code:
640 Zero - successful completion
641 Negative - system error
642 **************************************************************************/
643 48 int rm_dup_minutiae(MINUTIAE *minutiae)
644 {
645 48 int i, ret;
646 48 MINUTIA *minutia1, *minutia2;
647
648 /* Work backward from the end of the list of minutiae. This way */
649 /* we can selectively remove minutia from the list and not cause */
650 /* problems with keeping track of current indices. */
651
2/2
✓ Branch 0 taken 3447 times.
✓ Branch 1 taken 48 times.
 3495 for(i = minutiae->num-1; i > 0; i--){
652 3447 minutia1 = minutiae->list[i];
653 3447 minutia2 = minutiae->list[i-1];
654 /* If minutia pair has identical coordinates ... */
655
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3447 times.
 3447 if((minutia1->x == minutia2->x) &&
656 (minutia1->y == minutia2->y)){
657 /* Remove the 2nd minutia from the minutiae list. */
658 ✗ if((ret = remove_minutia(i-1, minutiae)))
659 ✗ return(ret);
660 /* The first minutia slides into the position of the 2nd. */
661 }
662 }
663
664 /* Return successfully. */
665 return(0);
666 }
667
668 /*************************************************************************
669 **************************************************************************
670 #cat: dump_minutiae - Given a minutiae list, writes a formatted text report of
671 #cat: the list's contents to the specified open file pointer.
672
673 Input:
674 minutiae - list of minutia structures
675 Output:
676 fpout - open file pointer
677 **************************************************************************/
678
679 /*************************************************************************
680 **************************************************************************
681 #cat: dump_minutiae_pts - Given a minutiae list, writes the coordinate point
682 #cat: for each minutia in the list to the specified open
683 #cat: file pointer.
684
685 Input:
686 minutiae - list of minutia structures
687 Output:
688 fpout - open file pointer
689 **************************************************************************/
690
691
692 /*************************************************************************
693 **************************************************************************
694 #cat: dump_reliable_minutiae_pts - Given a minutiae list, writes the
695 #cat: coordinate point for each minutia in the list that has
696 #cat: the specified reliability to the specified open
697 #cat: file pointer.
698
699 Input:
700 minutiae - list of minutia structures
701 reliability - desired reliability level for minutiae to be reported
702 Output:
703 fpout - open file pointer
704 **************************************************************************/
705
706 /*************************************************************************
707 **************************************************************************
708 #cat: create_minutia - Takes attributes associated with a detected minutia
709 #cat: point and allocates and initializes a minutia structure.
710
711 Input:
712 x_loc - x-pixel coord of minutia (interior to feature)
713 y_loc - y-pixel coord of minutia (interior to feature)
714 x_edge - x-pixel coord of corresponding edge pixel (exterior to feature)
715 y_edge - y-pixel coord of corresponding edge pixel (exterior to feature)
716 idir - integer direction of the minutia
717 reliability - floating point measure of minutia's reliability
718 type - type of the minutia (ridge-ending or bifurcation)
719 appearing - designates the minutia as appearing or disappearing
720 feature_id - index of minutia's matching g_feature_patterns[]
721 Output:
722 ominutia - ponter to an allocated and initialized minutia structure
723 Return Code:
724 Zero - minutia structure successfully allocated and initialized
725 Negative - system error
726 *************************************************************************/
727 50149 int create_minutia(MINUTIA **ominutia, const int x_loc, const int y_loc,
728 const int x_edge, const int y_edge, const int idir,
729 const double reliability,
730 const int type, const int appearing, const int feature_id)
731 {
732 50149 MINUTIA *minutia;
733
734 /* Allocate a minutia structure. */
735 50149 minutia = (MINUTIA *)g_malloc(sizeof(MINUTIA));
736
737 /* Assign minutia structure attributes. */
738 50149 minutia->x = x_loc;
739 50149 minutia->y = y_loc;
740 50149 minutia->ex = x_edge;
741 50149 minutia->ey = y_edge;
742 50149 minutia->direction = idir;
743 50149 minutia->reliability = reliability;
744 50149 minutia->type = type;
745 50149 minutia->appearing = appearing;
746 50149 minutia->feature_id = feature_id;
747 50149 minutia->nbrs = (int *)NULL;
748 50149 minutia->ridge_counts = (int *)NULL;
749 50149 minutia->num_nbrs = 0;
750
751 /* Set minutia object to output pointer. */
752 50149 *ominutia = minutia;
753 /* Return normally. */
754 50149 return(0);
755 }
756
757 /*************************************************************************
758 **************************************************************************
759 #cat: free_minutiae - Takes a minutiae list and deallocates all memory
760 #cat: associated with it.
761
762 Input:
763 minutiae - pointer to allocated list of minutia structures
764 *************************************************************************/
765 48 void free_minutiae(MINUTIAE *minutiae)
766 {
767 48 int i;
768
769 /* Deallocate minutia structures in the list. */
770
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 for(i = 0; i < minutiae->num; i++)
771 ✗ free_minutia(minutiae->list[i]);
772 /* Deallocate list of minutia pointers. */
773 48 g_free(minutiae->list);
774
775 /* Deallocate the list structure. */
776 48 g_free(minutiae);
777 48 }
778
779 /*************************************************************************
780 **************************************************************************
781 #cat: free_minutia - Takes a minutia pointer and deallocates all memory
782 #cat: associated with it.
783
784 Input:
785 minutia - pointer to allocated minutia structure
786 *************************************************************************/
787 50149 void free_minutia(MINUTIA *minutia)
788 {
789 /* Deallocate sublists. */
790
2/2
✓ Branch 0 taken 3447 times.
✓ Branch 1 taken 46702 times.
 50149 if(minutia->nbrs != (int *)NULL)
791 3447 g_free(minutia->nbrs);
792
2/2
✓ Branch 0 taken 3447 times.
✓ Branch 1 taken 46702 times.
 50149 if(minutia->ridge_counts != (int *)NULL)
793 3447 g_free(minutia->ridge_counts);
794
795 /* Deallocate the minutia structure. */
796 50149 g_free(minutia);
797 50149 }
798
799 /*************************************************************************
800 **************************************************************************
801 #cat: remove_minutia - Removes the specified minutia point from the input
802 #cat: list of minutiae.
803
804 Input:
805 index - position of minutia to be removed from list
806 minutiae - input list of minutiae
807 Output:
808 minutiae - list with minutia removed
809 Return Code:
810 Zero - successful completion
811 Negative - system error
812 **************************************************************************/
813 38090 int remove_minutia(const int index, MINUTIAE *minutiae)
814 {
815 38090 int fr, to;
816
817 /* Make sure the requested index is within range. */
818
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 38090 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 38090 if((index < 0) && (index >= minutiae->num)){
819 ✗ fprintf(stderr, "ERROR : remove_minutia : index out of range\n");
820 ✗ return(-380);
821 }
822
823 /* Deallocate the minutia structure to be removed. */
824 38090 free_minutia(minutiae->list[index]);
825
826 /* Slide the remaining list of minutiae up over top of the */
827 /* position of the minutia being removed. */
828
2/2
✓ Branch 0 taken 11119012 times.
✓ Branch 1 taken 38090 times.
 11157102 for(to = index, fr = index+1; fr < minutiae->num; to++, fr++)
829 11119012 minutiae->list[to] = minutiae->list[fr];
830
831 /* Decrement the number of minutiae remaining in the list. */
832 38090 minutiae->num--;
833
834 /* Return normally. */
835 38090 return(0);
836 }
837
838 /*************************************************************************
839 **************************************************************************
840 #cat: join_minutia - Takes 2 minutia points and connectes their features in
841 #cat: the input binary image. A line is drawn in the image
842 #cat: between the 2 minutia with a specified line-width radius
843 #cat: and a conditional border of pixels opposite in color
844 #cat: from the interior line.
845
846 Input:
847 minutia1 - first minutia point to be joined
848 minutia2 - second minutia point to be joined
849 bdata - binary image data (0==while & 1==black)
850 iw - width (in pixels) of image
851 ih - height (in pixels) of image
852 with_boundary - signifies the inclusion of border pixels
853 line_radius - line-width radius of join line
854 Output:
855 bdata - edited image with minutia features joined
856 Return Code:
857 Zero - successful completion
858 Negative - system error
859 **************************************************************************/
860
861 /*************************************************************************
862 **************************************************************************
863 #cat: minutia_type - Given the pixel color of the detected feature, returns
864 #cat: whether the minutia is a ridge-ending (black pixel) or
865 #cat: bifurcation (white pixel).
866
867 Input:
868 feature_pix - pixel color of the feature's interior
869 Return Code:
870 RIDGE_ENDING - minutia is a ridge-ending
871 BIFURCATION - minutia is a bifurcation (valley-ending)
872 **************************************************************************/
873 ✗ int minutia_type(const int feature_pix)
874 {
875 ✗ int type;
876
877 /* If feature pixel is white ... */
878 ✗ if(feature_pix == 0)
879 /* Then the feature is a valley-ending, so BIFURCATION. */
880 type = BIFURCATION;
881 /* Otherwise, the feature pixel is black ... */
882 else
883 /* So the feature is a RIDGE-ENDING. */
884 ✗ type = RIDGE_ENDING;
885
886 /* Return the type. */
887 ✗ return(type);
888 }
889
890 /*************************************************************************
891 **************************************************************************
892 #cat: is_minutia_appearing - Given the pixel location of a minutia feature
893 #cat: and its corresponding adjacent edge pixel, returns whether
894 #cat: the minutia is appearing or disappearing. Remeber, that
895 #cat: "feature" refers to either a ridge or valley-ending.
896
897 Input:
898 x_loc - x-pixel coord of feature (interior to feature)
899 y_loc - y-pixel coord of feature (interior to feature)
900 x_edge - x-pixel coord of corresponding edge pixel
901 (exterior to feature)
902 y_edge - y-pixel coord of corresponding edge pixel
903 (exterior to feature)
904 Return Code:
905 APPEARING - minutia is appearing (TRUE==1)
906 DISAPPEARING - minutia is disappearing (FALSE==0)
907 Negative - system error
908 **************************************************************************/
909 ✗ int is_minutia_appearing(const int x_loc, const int y_loc,
910 const int x_edge, const int y_edge)
911 {
912 /* Edge pixels will always be N,S,E,W of feature pixel. */
913
914 /* 1. When scanning for feature's HORIZONTALLY... */
915 /* If the edge is above the feature, then appearing. */
916 ✗ if(x_edge < x_loc)
917 return(APPEARING);
918 /* If the edge is below the feature, then disappearing. */
919 ✗ if(x_edge > x_loc)
920 return(DISAPPEARING);
921
922 /* 1. When scanning for feature's VERTICALLY... */
923 /* If the edge is left of feature, then appearing. */
924 ✗ if(y_edge < y_loc)
925 return(APPEARING);
926 /* If the edge is right of feature, then disappearing. */
927 ✗ if(y_edge > y_loc)
928 return(DISAPPEARING);
929
930 /* Should never get here, but just in case. */
931 ✗ fprintf(stderr,
932 "ERROR : is_minutia_appearing : bad configuration of pixels\n");
933 ✗ return(-240);
934 }
935
936 /*************************************************************************
937 **************************************************************************
938 #cat: choose_scan_direction - Determines the orientation (horizontal or
939 #cat: vertical) in which a block is to be scanned for minutiae.
940 #cat: The orientation is based on the blocks corresponding IMAP
941 #cat: direction.
942
943 Input:
944 imapval - Block's IMAP direction
945 ndirs - number of possible IMAP directions (within semicircle)
946 Return Code:
947 SCAN_HORIZONTAL - horizontal orientation
948 SCAN_VERTICAL - vertical orientation
949 **************************************************************************/
950 16021 int choose_scan_direction(const int imapval, const int ndirs)
951 {
952 16021 int qtr_ndirs;
953
954 /* Compute quarter of directions in semi-circle. */
955 16021 qtr_ndirs = ndirs>>2;
956
957 /* If ridge flow in block is relatively vertical, then we want */
958 /* to scan for minutia features in the opposite direction */
959 /* (ie. HORIZONTALLY). */
960
4/4
✓ Branch 0 taken 11784 times.
✓ Branch 1 taken 4237 times.
✓ Branch 2 taken 10670 times.
✓ Branch 3 taken 1114 times.
 16021 if((imapval <= qtr_ndirs) || (imapval > (qtr_ndirs*3)))
961 return(SCAN_HORIZONTAL);
962 /* Otherwise, ridge flow is realtively horizontal, and we want */
963 /* to scan for minutia features in the opposite direction */
964 /* (ie. VERTICALLY). */
965 else
966 10670 return(SCAN_VERTICAL);
967
968 }
969
970 /*************************************************************************
971 **************************************************************************
972 #cat: scan4minutiae - Scans a block of binary image data detecting potential
973 #cat: minutiae points.
974
975 Input:
976 bdata - binary image data (0==while & 1==black)
977 iw - width (in pixels) of image
978 ih - height (in pixels) of image
979 imap - matrix of ridge flow directions
980 nmap - IMAP augmented with blocks of HIGH-CURVATURE and
981 blocks which have no neighboring valid directions.
982 blk_x - x-block coord to be scanned
983 blk_y - y-block coord to be scanned
984 mw - width (in blocks) of IMAP and NMAP matrices.
985 mh - height (in blocks) of IMAP and NMAP matrices.
986 scan_x - x-pixel coord of origin of region to be scanned
987 scan_y - y-pixel coord of origin of region to be scanned
988 scan_w - width (in pixels) of region to be scanned
989 scan_h - height (in pixels) of region to be scanned
990 scan_dir - the scan orientation (horizontal or vertical)
991 lfsparms - parameters and thresholds for controlling LFS
992 Output:
993 minutiae - points to a list of detected minutia structures
994 Return Code:
995 Zero - successful completion
996 Negative - system error
997 **************************************************************************/
998
999 /*************************************************************************
1000 **************************************************************************
1001 #cat: scan4minutiae_horizontally - Scans a specified region of binary image
1002 #cat: data horizontally, detecting potential minutiae points.
1003 #cat: Minutia detected via the horizontal scan process are
1004 #cat: by nature vertically oriented (orthogonal to the scan).
1005 #cat: The region actually scanned is slightly larger than that
1006 #cat: specified. This overlap attempts to minimize the number
1007 #cat: of minutiae missed at the region boundaries.
1008 #cat: HOWEVER, some minutiae will still be missed!
1009
1010 Input:
1011 bdata - binary image data (0==while & 1==black)
1012 iw - width (in pixels) of image
1013 ih - height (in pixels) of image
1014 imapval - IMAP value associated with this image region
1015 nmapval - NMAP value associated with this image region
1016 scan_x - x-pixel coord of origin of region to be scanned
1017 scan_y - y-pixel coord of origin of region to be scanned
1018 scan_w - width (in pixels) of region to be scanned
1019 scan_h - height (in pixels) of region to be scanned
1020 lfsparms - parameters and thresholds for controlling LFS
1021 Output:
1022 minutiae - points to a list of detected minutia structures
1023 Return Code:
1024 Zero - successful completion
1025 Negative - system error
1026 **************************************************************************/
1027
1028 /*************************************************************************
1029 **************************************************************************
1030 #cat: scan4minutiae_horizontally_V2 - Scans an entire binary image
1031 #cat: horizontally, detecting potential minutiae points.
1032 #cat: Minutia detected via the horizontal scan process are
1033 #cat: by nature vertically oriented (orthogonal to the scan).
1034
1035 Input:
1036 bdata - binary image data (0==while & 1==black)
1037 iw - width (in pixels) of image
1038 ih - height (in pixels) of image
1039 pdirection_map - pixelized Direction Map
1040 plow_flow_map - pixelized Low Ridge Flow Map
1041 phigh_curve_map - pixelized High Curvature Map
1042 lfsparms - parameters and thresholds for controlling LFS
1043 Output:
1044 minutiae - points to a list of detected minutia structures
1045 Return Code:
1046 Zero - successful completion
1047 Negative - system error
1048 **************************************************************************/
1049 48 int scan4minutiae_horizontally_V2(MINUTIAE *minutiae,
1050 unsigned char *bdata, const int iw, const int ih,
1051 int *pdirection_map, int *plow_flow_map, int *phigh_curve_map,
1052 const LFSPARMS *lfsparms)
1053 {
1054 48 int sx, sy, ex, ey, cx, cy, x2;
1055 48 unsigned char *p1ptr, *p2ptr;
1056 48 int possible[NFEATURES], nposs;
1057 48 int ret;
1058
1059 /* Set scan region to entire image. */
1060 48 sx = 0;
1061 48 ex = iw;
1062 48 sy = 0;
1063 48 ey = ih;
1064
1065 /* Start at first row in region. */
1066 48 cy = sy;
1067 /* While second scan row not outside the bottom of the scan region... */
1068
2/2
✓ Branch 0 taken 13213 times.
✓ Branch 1 taken 48 times.
 13261 while(cy+1 < ey){
1069 /* Start at beginning of new scan row in region. */
1070 13213 cx = sx;
1071 /* While not at end of region's current scan row. */
1072
2/2
✓ Branch 0 taken 2638597 times.
✓ Branch 1 taken 13213 times.
 2651810 while(cx < ex){
1073 /* Get pixel pair from current x position in current and next */
1074 /* scan rows. */
1075 2638597 p1ptr = bdata+(cy*iw)+cx;
1076 2638597 p2ptr = bdata+((cy+1)*iw)+cx;
1077 /* If scan pixel pair matches first pixel pair of */
1078 /* 1 or more features... */
1079
1/2
✓ Branch 1 taken 2638597 times.
✗ Branch 2 not taken.
 2638597 if(match_1st_pair(*p1ptr, *p2ptr, possible, &nposs)){
1080 /* Bump forward to next scan pixel pair. */
1081 2638597 cx++;
1082 2638597 p1ptr++;
1083 2638597 p2ptr++;
1084 /* If not at end of region's current scan row... */
1085
2/2
✓ Branch 0 taken 2625384 times.
✓ Branch 1 taken 13213 times.
 2638597 if(cx < ex){
1086 /* If scan pixel pair matches second pixel pair of */
1087 /* 1 or more features... */
1088
2/2
✓ Branch 1 taken 268078 times.
✓ Branch 2 taken 2357306 times.
 2625384 if(match_2nd_pair(*p1ptr, *p2ptr, possible, &nposs)){
1089 /* Store current x location. */
1090 268078 x2 = cx;
1091 /* Skip repeated pixel pairs. */
1092 268078 skip_repeated_horizontal_pair(&cx, ex, &p1ptr, &p2ptr,
1093 iw, ih);
1094 /* If not at end of region's current scan row... */
1095
1/2
✓ Branch 0 taken 268078 times.
✗ Branch 1 not taken.
 268078 if(cx < ex){
1096 /* If scan pixel pair matches third pixel pair of */
1097 /* a single feature... */
1098
2/2
✓ Branch 1 taken 29404 times.
✓ Branch 2 taken 238674 times.
 268078 if(match_3rd_pair(*p1ptr, *p2ptr, possible, &nposs)){
1099 /* Process detected minutia point. */
1100
2/2
✓ Branch 1 taken 1791 times.
✓ Branch 2 taken 27613 times.
 29404 if((ret = process_horizontal_scan_minutia_V2(minutiae,
1101 cx, cy, x2, possible[0],
1102 bdata, iw, ih, pdirection_map,
1103 plow_flow_map, phigh_curve_map,
1104 lfsparms))){
1105 /* Return code may be: */
1106 /* 1. ret< 0 (implying system error) */
1107 /* 2. ret==IGNORE (ignore current feature) */
1108
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1791 times.
 1791 if(ret < 0)
1109 ✗ return(ret);
1110 /* Otherwise, IGNORE and continue. */
1111 }
1112 }
1113
1114 /* Set up to resume scan. */
1115 /* Test to see if 3rd pair can slide into 2nd pair. */
1116 /* The values of the 2nd pair MUST be different. */
1117 /* If 3rd pair values are different ... */
1118
2/2
✓ Branch 0 taken 148 times.
✓ Branch 1 taken 267930 times.
 268078 if(*p1ptr != *p2ptr){
1119 /* Set next first pair to last of repeated */
1120 /* 2nd pairs, ie. back up one pair. */
1121 148 cx--;
1122 }
1123
1124 /* Otherwise, 3rd pair can't be a 2nd pair, so */
1125 /* keep pointing to 3rd pair so that it is used */
1126 /* in the next first pair test. */
1127
1128 } /* Else, at end of current scan row. */
1129 }
1130
1131 /* Otherwise, 2nd pair failed, so keep pointing to it */
1132 /* so that it is used in the next first pair test. */
1133
1134 } /* Else, at end of current scan row. */
1135 }
1136 /* Otherwise, 1st pair failed... */
1137 else{
1138 /* Bump forward to next pixel pair. */
1139 ✗ cx++;
1140 }
1141 } /* While not at end of current scan row. */
1142 /* Bump forward to next scan row. */
1143 cy++;
1144 } /* While not out of scan rows. */
1145
1146 /* Return normally. */
1147 return(0);
1148 }
1149
1150 /*************************************************************************
1151 **************************************************************************
1152 #cat: scan4minutiae_vertically - Scans a specified region of binary image data
1153 #cat: vertically, detecting potential minutiae points.
1154 #cat: Minutia detected via the vetical scan process are
1155 #cat: by nature horizontally oriented (orthogonal to the scan).
1156 #cat: The region actually scanned is slightly larger than that
1157 #cat: specified. This overlap attempts to minimize the number
1158 #cat: of minutiae missed at the region boundaries.
1159 #cat: HOWEVER, some minutiae will still be missed!
1160
1161 Input:
1162 bdata - binary image data (0==while & 1==black)
1163 iw - width (in pixels) of image
1164 ih - height (in pixels) of image
1165 imapval - IMAP value associated with this image region
1166 nmapval - NMAP value associated with this image region
1167 scan_x - x-pixel coord of origin of region to be scanned
1168 scan_y - y-pixel coord of origin of region to be scanned
1169 scan_w - width (in pixels) of region to be scanned
1170 scan_h - height (in pixels) of region to be scanned
1171 lfsparms - parameters and thresholds for controlling LFS
1172 Output:
1173 minutiae - points to a list of detected minutia structures
1174 Return Code:
1175 Zero - successful completion
1176 Negative - system error
1177 **************************************************************************/
1178
1179 /*************************************************************************
1180 **************************************************************************
1181 #cat: scan4minutiae_vertically_V2 - Scans an entire binary image
1182 #cat: vertically, detecting potential minutiae points.
1183 #cat: Minutia detected via the vetical scan process are
1184 #cat: by nature horizontally oriented (orthogonal to the scan).
1185
1186 Input:
1187 bdata - binary image data (0==while & 1==black)
1188 iw - width (in pixels) of image
1189 ih - height (in pixels) of image
1190 pdirection_map - pixelized Direction Map
1191 plow_flow_map - pixelized Low Ridge Flow Map
1192 phigh_curve_map - pixelized High Curvature Map
1193 lfsparms - parameters and thresholds for controlling LFS
1194 Output:
1195 minutiae - points to a list of detected minutia structures
1196 Return Code:
1197 Zero - successful completion
1198 Negative - system error
1199 **************************************************************************/
1200 48 int scan4minutiae_vertically_V2(MINUTIAE *minutiae,
1201 unsigned char *bdata, const int iw, const int ih,
1202 int *pdirection_map, int *plow_flow_map, int *phigh_curve_map,
1203 const LFSPARMS *lfsparms)
1204 {
1205 48 int sx, sy, ex, ey, cx, cy, y2;
1206 48 unsigned char *p1ptr, *p2ptr;
1207 48 int possible[NFEATURES], nposs;
1208 48 int ret;
1209
1210 /* Set scan region to entire image. */
1211 48 sx = 0;
1212 48 ex = iw;
1213 48 sy = 0;
1214 48 ey = ih;
1215
1216 /* Start at first column in region. */
1217 48 cx = sx;
1218 /* While second scan column not outside the right of the region ... */
1219
2/2
✓ Branch 0 taken 11936 times.
✓ Branch 1 taken 48 times.
 11984 while(cx+1 < ex){
1220 /* Start at beginning of new scan column in region. */
1221 11936 cy = sy;
1222 /* While not at end of region's current scan column. */
1223
2/2
✓ Branch 0 taken 2736902 times.
✓ Branch 1 taken 11936 times.
 2748838 while(cy < ey){
1224 /* Get pixel pair from current y position in current and next */
1225 /* scan columns. */
1226 2736902 p1ptr = bdata+(cy*iw)+cx;
1227 2736902 p2ptr = p1ptr+1;
1228 /* If scan pixel pair matches first pixel pair of */
1229 /* 1 or more features... */
1230
1/2
✓ Branch 1 taken 2736902 times.
✗ Branch 2 not taken.
 2736902 if(match_1st_pair(*p1ptr, *p2ptr, possible, &nposs)){
1231 /* Bump forward to next scan pixel pair. */
1232 2736902 cy++;
1233 2736902 p1ptr+=iw;
1234 2736902 p2ptr+=iw;
1235 /* If not at end of region's current scan column... */
1236
2/2
✓ Branch 0 taken 2724966 times.
✓ Branch 1 taken 11936 times.
 2736902 if(cy < ey){
1237 /* If scan pixel pair matches second pixel pair of */
1238 /* 1 or more features... */
1239
2/2
✓ Branch 1 taken 267896 times.
✓ Branch 2 taken 2457070 times.
 2724966 if(match_2nd_pair(*p1ptr, *p2ptr, possible, &nposs)){
1240 /* Store current y location. */
1241 267896 y2 = cy;
1242 /* Skip repeated pixel pairs. */
1243 267896 skip_repeated_vertical_pair(&cy, ey, &p1ptr, &p2ptr,
1244 iw, ih);
1245 /* If not at end of region's current scan column... */
1246
1/2
✓ Branch 0 taken 267896 times.
✗ Branch 1 not taken.
 267896 if(cy < ey){
1247 /* If scan pixel pair matches third pixel pair of */
1248 /* a single feature... */
1249
2/2
✓ Branch 1 taken 24206 times.
✓ Branch 2 taken 243690 times.
 267896 if(match_3rd_pair(*p1ptr, *p2ptr, possible, &nposs)){
1250 /* Process detected minutia point. */
1251
2/2
✓ Branch 1 taken 1670 times.
✓ Branch 2 taken 22536 times.
 24206 if((ret = process_vertical_scan_minutia_V2(minutiae,
1252 cx, cy, y2, possible[0],
1253 bdata, iw, ih, pdirection_map,
1254 plow_flow_map, phigh_curve_map,
1255 lfsparms))){
1256 /* Return code may be: */
1257 /* 1. ret< 0 (implying system error) */
1258 /* 2. ret==IGNORE (ignore current feature) */
1259
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1670 times.
 1670 if(ret < 0)
1260 ✗ return(ret);
1261 /* Otherwise, IGNORE and continue. */
1262 }
1263 }
1264
1265 /* Set up to resume scan. */
1266 /* Test to see if 3rd pair can slide into 2nd pair. */
1267 /* The values of the 2nd pair MUST be different. */
1268 /* If 3rd pair values are different ... */
1269
2/2
✓ Branch 0 taken 146 times.
✓ Branch 1 taken 267750 times.
 267896 if(*p1ptr != *p2ptr){
1270 /* Set next first pair to last of repeated */
1271 /* 2nd pairs, ie. back up one pair. */
1272 146 cy--;
1273 }
1274
1275 /* Otherwise, 3rd pair can't be a 2nd pair, so */
1276 /* keep pointing to 3rd pair so that it is used */
1277 /* in the next first pair test. */
1278
1279 } /* Else, at end of current scan row. */
1280 }
1281
1282 /* Otherwise, 2nd pair failed, so keep pointing to it */
1283 /* so that it is used in the next first pair test. */
1284
1285 } /* Else, at end of current scan column. */
1286 }
1287 /* Otherwise, 1st pair failed... */
1288 else{
1289 /* Bump forward to next pixel pair. */
1290 ✗ cy++;
1291 }
1292 } /* While not at end of current scan column. */
1293 /* Bump forward to next scan column. */
1294 cx++;
1295 } /* While not out of scan columns. */
1296
1297 /* Return normally. */
1298 return(0);
1299 }
1300
1301 /*************************************************************************
1302 **************************************************************************
1303 #cat: rescan4minutiae_horizontally - Rescans portions of a block of binary
1304 #cat: image data horizontally for potential minutiae. The areas
1305 #cat: rescanned within the block are based on the current
1306 #cat: block's neighboring blocks' IMAP and NMAP values.
1307
1308 Input:
1309 bdata - binary image data (0==while & 1==black)
1310 iw - width (in pixels) of image
1311 ih - height (in pixels) of image
1312 imap - matrix of ridge flow directions
1313 nmap - IMAP augmented with blocks of HIGH-CURVATURE and
1314 blocks which have no neighboring valid directions.
1315 blk_x - x-block coord to be rescanned
1316 blk_y - y-block coord to be rescanned
1317 mw - width (in blocks) of IMAP and NMAP matrices.
1318 mh - height (in blocks) of IMAP and NMAP matrices.
1319 scan_x - x-pixel coord of origin of region to be rescanned
1320 scan_y - y-pixel coord of origin of region to be rescanned
1321 scan_w - width (in pixels) of region to be rescanned
1322 scan_h - height (in pixels) of region to be rescanned
1323 lfsparms - parameters and thresholds for controlling LFS
1324 Output:
1325 minutiae - points to a list of detected minutia structures
1326 Return Code:
1327 Zero - successful completion
1328 Negative - system error
1329 **************************************************************************/
1330
1331 /*************************************************************************
1332 **************************************************************************
1333 #cat: rescan4minutiae_vertically - Rescans portions of a block of binary
1334 #cat: image data vertically for potential minutiae. The areas
1335 #cat: rescanned within the block are based on the current
1336 #cat: block's neighboring blocks' IMAP and NMAP values.
1337
1338 Input:
1339 bdata - binary image data (0==while & 1==black)
1340 iw - width (in pixels) of image
1341 ih - height (in pixels) of image
1342 imap - matrix of ridge flow directions
1343 nmap - IMAP augmented with blocks of HIGH-CURVATURE and
1344 blocks which have no neighboring valid directions.
1345 blk_x - x-block coord to be rescanned
1346 blk_y - y-block coord to be rescanned
1347 mw - width (in blocks) of IMAP and NMAP matrices.
1348 mh - height (in blocks) of IMAP and NMAP matrices.
1349 scan_x - x-pixel coord of origin of region to be rescanned
1350 scan_y - y-pixel coord of origin of region to be rescanned
1351 scan_w - width (in pixels) of region to be rescanned
1352 scan_h - height (in pixels) of region to be rescanned
1353 lfsparms - parameters and thresholds for controlling LFS
1354 Output:
1355 minutiae - points to a list of detected minutia structures
1356 Return Code:
1357 Zero - successful completion
1358 Negative - system error
1359 **************************************************************************/
1360
1361 /*************************************************************************
1362 **************************************************************************
1363 #cat: rescan_partial_horizontally - Rescans a portion of a block of binary
1364 #cat: image data horizontally based on the IMAP and NMAP values
1365 #cat: of a specified neighboring block.
1366
1367 Input:
1368 nbr_dir - specifies which block neighbor {NORTH, SOUTH, EAST, WEST}
1369 bdata - binary image data (0==while & 1==black)
1370 iw - width (in pixels) of image
1371 ih - height (in pixels) of image
1372 imap - matrix of ridge flow directions
1373 nmap - IMAP augmented with blocks of HIGH-CURVATURE and
1374 blocks which have no neighboring valid directions.
1375 blk_x - x-block coord to be rescanned
1376 blk_y - y-block coord to be rescanned
1377 mw - width (in blocks) of IMAP and NMAP matrices.
1378 mh - height (in blocks) of IMAP and NMAP matrices.
1379 scan_x - x-pixel coord of origin of image region
1380 scan_y - y-pixel coord of origin of image region
1381 scan_w - width (in pixels) of image region
1382 scan_h - height (in pixels) of image region
1383 lfsparms - parameters and thresholds for controlling LFS
1384 Output:
1385 minutiae - points to a list of detected minutia structures
1386 Return Code:
1387 Zero - successful completion
1388 Negative - system error
1389 **************************************************************************/
1390
1391 /*************************************************************************
1392 **************************************************************************
1393 #cat: rescan_partial_vertically - Rescans a portion of a block of binary
1394 #cat: image data vertically based on the IMAP and NMAP values
1395 #cat: of a specified neighboring block.
1396
1397 Input:
1398 nbr_dir - specifies which block neighbor {NORTH, SOUTH, EAST, WEST}
1399 bdata - binary image data (0==while & 1==black)
1400 iw - width (in pixels) of image
1401 ih - height (in pixels) of image
1402 imap - matrix of ridge flow directions
1403 nmap - IMAP augmented with blocks of HIGH-CURVATURE and
1404 blocks which have no neighboring valid directions.
1405 blk_x - x-block coord to be rescanned
1406 blk_y - y-block coord to be rescanned
1407 mw - width (in blocks) of IMAP and NMAP matrices.
1408 mh - height (in blocks) of IMAP and NMAP matrices.
1409 scan_x - x-pixel coord of origin of image region
1410 scan_y - y-pixel coord of origin of image region
1411 scan_w - width (in pixels) of image region
1412 scan_h - height (in pixels) of image region
1413 lfsparms - parameters and thresholds for controlling LFS
1414 Output:
1415 minutiae - points to a list of detected minutia structures
1416 Return Code:
1417 Zero - successful completion
1418 Negative - system error
1419 **************************************************************************/
1420
1421 /*************************************************************************
1422 **************************************************************************
1423 #cat: get_nbr_block_index - Determines the block index (if one exists)
1424 #cat: for a specified neighbor of a block in the image.
1425
1426 Input:
1427 nbr_dir - specifies which block neighbor {NORTH, SOUTH, EAST, WEST}
1428 blk_x - x-block coord to find neighbor of
1429 blk_y - y-block coord to find neighbor of
1430 mw - width (in blocks) of IMAP and NMAP matrices.
1431 mh - height (in blocks) of IMAP and NMAP matrices.
1432 Output:
1433 oblk_i - points to neighbor's block index
1434 Return Code:
1435 NOT_FOUND - neighbor index does not exist
1436 FOUND - neighbor index exists and returned
1437 Negative - system error
1438 **************************************************************************/
1439
1440 /*************************************************************************
1441 **************************************************************************
1442 #cat: adjust_horizontal_rescan - Determines the portion of an image block to
1443 #cat: be rescanned horizontally based on a specified neighbor.
1444
1445 Input:
1446 nbr_dir - specifies which block neighbor {NORTH, SOUTH, EAST, WEST}
1447 scan_x - x-pixel coord of origin of image region
1448 scan_y - y-pixel coord of origin of image region
1449 scan_w - width (in pixels) of image region
1450 scan_h - height (in pixels) of image region
1451 blocksize - dimension of image blocks (in pixels)
1452 Output:
1453 rescan_x - x-pixel coord of origin of region to be rescanned
1454 rescan_y - y-pixel coord of origin of region to be rescanned
1455 rescan_w - width (in pixels) of region to be rescanned
1456 rescan_h - height (in pixels) of region to be rescanned
1457 Return Code:
1458 Zero - successful completion
1459 Negative - system error
1460 **************************************************************************/
1461
1462 /*************************************************************************
1463 **************************************************************************
1464 #cat: adjust_vertical_rescan - Determines the portion of an image block to
1465 #cat: be rescanned vertically based on a specified neighbor.
1466
1467 Input:
1468 nbr_dir - specifies which block neighbor {NORTH, SOUTH, EAST, WEST}
1469 scan_x - x-pixel coord of origin of image region
1470 scan_y - y-pixel coord of origin of image region
1471 scan_w - width (in pixels) of image region
1472 scan_h - height (in pixels) of image region
1473 blocksize - dimension of image blocks (in pixels)
1474 Output:
1475 rescan_x - x-pixel coord of origin of region to be rescanned
1476 rescan_y - y-pixel coord of origin of region to be rescanned
1477 rescan_w - width (in pixels) of region to be rescanned
1478 rescan_h - height (in pixels) of region to be rescanned
1479 Return Code:
1480 Zero - successful completion
1481 Negative - system error
1482 **************************************************************************/
1483
1484 /*************************************************************************
1485 **************************************************************************
1486 #cat: process_horizontal_scan_minutia - Takes a minutia point that was
1487 #cat: detected via the horizontal scan process and
1488 #cat: adjusts its location (if necessary), determines its
1489 #cat: direction, and (if it is not already in the minutiae
1490 #cat: list) adds it to the list. These minutia are by nature
1491 #cat: vertical in orientation (orthogonal to the scan).
1492
1493 Input:
1494 cx - x-pixel coord where 3rd pattern pair of mintuia was detected
1495 cy - y-pixel coord where 3rd pattern pair of mintuia was detected
1496 y2 - y-pixel coord where 2nd pattern pair of mintuia was detected
1497 feature_id - type of minutia (ex. index into g_feature_patterns[] list)
1498 bdata - binary image data (0==while & 1==black)
1499 iw - width (in pixels) of image
1500 ih - height (in pixels) of image
1501 imapval - IMAP value associated with this image region
1502 nmapval - NMAP value associated with this image region
1503 lfsparms - parameters and thresholds for controlling LFS
1504 Output:
1505 minutiae - points to a list of detected minutia structures
1506 Return Code:
1507 Zero - successful completion
1508 IGNORE - minutia is to be ignored
1509 Negative - system error
1510 **************************************************************************/
1511
1512 /*************************************************************************
1513 **************************************************************************
1514 #cat: process_horizontal_scan_minutia_V2 - Takes a minutia point that was
1515 #cat: detected via the horizontal scan process and
1516 #cat: adjusts its location (if necessary), determines its
1517 #cat: direction, and (if it is not already in the minutiae
1518 #cat: list) adds it to the list. These minutia are by nature
1519 #cat: vertical in orientation (orthogonal to the scan).
1520
1521 Input:
1522 cx - x-pixel coord where 3rd pattern pair of mintuia was detected
1523 cy - y-pixel coord where 3rd pattern pair of mintuia was detected
1524 y2 - y-pixel coord where 2nd pattern pair of mintuia was detected
1525 feature_id - type of minutia (ex. index into g_feature_patterns[] list)
1526 bdata - binary image data (0==while & 1==black)
1527 iw - width (in pixels) of image
1528 ih - height (in pixels) of image
1529 pdirection_map - pixelized Direction Map
1530 plow_flow_map - pixelized Low Ridge Flow Map
1531 phigh_curve_map - pixelized High Curvature Map
1532 lfsparms - parameters and thresholds for controlling LFS
1533 Output:
1534 minutiae - points to a list of detected minutia structures
1535 Return Code:
1536 Zero - successful completion
1537 IGNORE - minutia is to be ignored
1538 Negative - system error
1539 **************************************************************************/
1540 29404 int process_horizontal_scan_minutia_V2(MINUTIAE *minutiae,
1541 const int cx, const int cy,
1542 const int x2, const int feature_id,
1543 unsigned char *bdata, const int iw, const int ih,
1544 int *pdirection_map, int *plow_flow_map, int *phigh_curve_map,
1545 const LFSPARMS *lfsparms)
1546 {
1547 29404 MINUTIA *minutia;
1548 29404 int x_loc, y_loc;
1549 29404 int x_edge, y_edge;
1550 29404 int idir, ret;
1551 29404 int dmapval, fmapval, cmapval;
1552 29404 double reliability;
1553
1554 /* Set x location of minutia point to be half way between */
1555 /* first position of second feature pair and position of */
1556 /* third feature pair. */
1557 29404 x_loc = (cx + x2)>>1;
1558
1559 /* Set same x location to neighboring edge pixel. */
1560 29404 x_edge = x_loc;
1561
1562 /* Feature location should always point to either ending */
1563 /* of ridge or (for bifurcations) ending of valley. */
1564 /* So, if detected feature is APPEARING... */
1565
2/2
✓ Branch 0 taken 14782 times.
✓ Branch 1 taken 14622 times.
 29404 if(g_feature_patterns[feature_id].appearing){
1566 /* Set y location to second scan row. */
1567 14782 y_loc = cy+1;
1568 /* Set y location of neighboring edge pixel to the first scan row. */
1569 14782 y_edge = cy;
1570 }
1571 /* Otherwise, feature is DISAPPEARING... */
1572 else{
1573 /* Set y location to first scan row. */
1574 14622 y_loc = cy;
1575 /* Set y location of neighboring edge pixel to the second scan row. */
1576 14622 y_edge = cy+1;
1577 }
1578
1579 29404 dmapval = *(pdirection_map+(y_loc*iw)+x_loc);
1580 29404 fmapval = *(plow_flow_map+(y_loc*iw)+x_loc);
1581 29404 cmapval = *(phigh_curve_map+(y_loc*iw)+x_loc);
1582
1583 /* If the minutia point is in a block with INVALID direction ... */
1584
2/2
✓ Branch 0 taken 28418 times.
✓ Branch 1 taken 986 times.
 29404 if(dmapval == INVALID_DIR)
1585 /* Then, IGNORE the point. */
1586 return(IGNORE);
1587
1588 /* If current minutia is in a HIGH CURVATURE block ... */
1589
2/2
✓ Branch 0 taken 1945 times.
✓ Branch 1 taken 26473 times.
 28418 if(cmapval){
1590 /* Adjust location and direction locally. */
1591
2/2
✓ Branch 1 taken 1140 times.
✓ Branch 2 taken 805 times.
 1945 if((ret = adjust_high_curvature_minutia_V2(&idir, &x_loc, &y_loc,
1592 &x_edge, &y_edge, x_loc, y_loc, x_edge, y_edge,
1593 bdata, iw, ih, plow_flow_map, minutiae, lfsparms))){
1594 /* Could be a system error or IGNORE minutia. */
1595 return(ret);
1596 }
1597 /* Otherwise, we have our high-curvature minutia attributes. */
1598 }
1599 /* Otherwise, minutia is in fairly low-curvature block... */
1600 else{
1601 /* Get minutia direction based on current block's direction. */
1602 26473 idir = get_low_curvature_direction(SCAN_HORIZONTAL,
1603 g_feature_patterns[feature_id].appearing, dmapval,
1604 26473 lfsparms->num_directions);
1605 }
1606
1607 /* If current minutia is in a LOW RIDGE FLOW block ... */
1608
2/2
✓ Branch 0 taken 12023 times.
✓ Branch 1 taken 15590 times.
 27613 if(fmapval)
1609 reliability = MEDIUM_RELIABILITY;
1610 else
1611 /* Otherwise, minutia is in a block with reliable direction and */
1612 /* binarization. */
1613 12023 reliability = HIGH_RELIABILITY;
1614
1615 /* Create a minutia object based on derived attributes. */
1616
1/2
✓ Branch 1 taken 27613 times.
✗ Branch 2 not taken.
 27613 if((ret = create_minutia(&minutia, x_loc, y_loc, x_edge, y_edge, idir,
1617 reliability,
1618 g_feature_patterns[feature_id].type,
1619 g_feature_patterns[feature_id].appearing, feature_id)))
1620 /* Return system error. */
1621 return(ret);
1622
1623 /* Update the minutiae list with potential new minutia. */
1624 27613 ret = update_minutiae_V2(minutiae, minutia, SCAN_HORIZONTAL,
1625 dmapval, bdata, iw, ih, lfsparms);
1626
1627 /* If minuitia IGNORED and not added to the minutia list ... */
1628
2/2
✓ Branch 0 taken 1077 times.
✓ Branch 1 taken 26536 times.
 27613 if(ret != 0)
1629 /* Deallocate the minutia. */
1630 1077 free_minutia(minutia);
1631
1632 /* Otherwise, return normally. */
1633 return(0);
1634 }
1635
1636 /*************************************************************************
1637 **************************************************************************
1638 #cat: process_vertical_scan_minutia - Takes a minutia point that was
1639 #cat: detected in via the vertical scan process and
1640 #cat: adjusts its location (if necessary), determines its
1641 #cat: direction, and (if it is not already in the minutiae
1642 #cat: list) adds it to the list. These minutia are by nature
1643 #cat: horizontal in orientation (orthogonal to the scan).
1644
1645 Input:
1646 cx - x-pixel coord where 3rd pattern pair of mintuia was detected
1647 cy - y-pixel coord where 3rd pattern pair of mintuia was detected
1648 x2 - x-pixel coord where 2nd pattern pair of mintuia was detected
1649 feature_id - type of minutia (ex. index into g_feature_patterns[] list)
1650 bdata - binary image data (0==while & 1==black)
1651 iw - width (in pixels) of image
1652 ih - height (in pixels) of image
1653 imapval - IMAP value associated with this image region
1654 nmapval - NMAP value associated with this image region
1655 lfsparms - parameters and thresholds for controlling LFS
1656 Output:
1657 minutiae - points to a list of detected minutia structures
1658 Return Code:
1659 Zero - successful completion
1660 IGNORE - minutia is to be ignored
1661 Negative - system error
1662 **************************************************************************/
1663
1664 /*************************************************************************
1665 **************************************************************************
1666 #cat: process_vertical_scan_minutia_V2 - Takes a minutia point that was
1667 #cat: detected in via the vertical scan process and
1668 #cat: adjusts its location (if necessary), determines its
1669 #cat: direction, and (if it is not already in the minutiae
1670 #cat: list) adds it to the list. These minutia are by nature
1671 #cat: horizontal in orientation (orthogonal to the scan).
1672
1673 Input:
1674 cx - x-pixel coord where 3rd pattern pair of mintuia was detected
1675 cy - y-pixel coord where 3rd pattern pair of mintuia was detected
1676 x2 - x-pixel coord where 2nd pattern pair of mintuia was detected
1677 feature_id - type of minutia (ex. index into g_feature_patterns[] list)
1678 bdata - binary image data (0==while & 1==black)
1679 iw - width (in pixels) of image
1680 ih - height (in pixels) of image
1681 pdirection_map - pixelized Direction Map
1682 plow_flow_map - pixelized Low Ridge Flow Map
1683 phigh_curve_map - pixelized High Curvature Map
1684 lfsparms - parameters and thresholds for controlling LFS
1685 Output:
1686 minutiae - points to a list of detected minutia structures
1687 Return Code:
1688 Zero - successful completion
1689 IGNORE - minutia is to be ignored
1690 Negative - system error
1691 **************************************************************************/
1692 24206 int process_vertical_scan_minutia_V2(MINUTIAE *minutiae,
1693 const int cx, const int cy,
1694 const int y2, const int feature_id,
1695 unsigned char *bdata, const int iw, const int ih,
1696 int *pdirection_map, int *plow_flow_map, int *phigh_curve_map,
1697 const LFSPARMS *lfsparms)
1698 {
1699 24206 MINUTIA *minutia;
1700 24206 int x_loc, y_loc;
1701 24206 int x_edge, y_edge;
1702 24206 int idir, ret;
1703 24206 int dmapval, fmapval, cmapval;
1704 24206 double reliability;
1705
1706 /* Feature location should always point to either ending */
1707 /* of ridge or (for bifurcations) ending of valley. */
1708 /* So, if detected feature is APPEARING... */
1709
2/2
✓ Branch 0 taken 12104 times.
✓ Branch 1 taken 12102 times.
 24206 if(g_feature_patterns[feature_id].appearing){
1710 /* Set x location to second scan column. */
1711 12104 x_loc = cx+1;
1712 /* Set x location of neighboring edge pixel to the first scan column. */
1713 12104 x_edge = cx;
1714 }
1715 /* Otherwise, feature is DISAPPEARING... */
1716 else{
1717 /* Set x location to first scan column. */
1718 12102 x_loc = cx;
1719 /* Set x location of neighboring edge pixel to the second scan column. */
1720 12102 x_edge = cx+1;
1721 }
1722
1723 /* Set y location of minutia point to be half way between */
1724 /* first position of second feature pair and position of */
1725 /* third feature pair. */
1726 24206 y_loc = (cy + y2)>>1;
1727 /* Set same y location to neighboring edge pixel. */
1728 24206 y_edge = y_loc;
1729
1730 24206 dmapval = *(pdirection_map+(y_loc*iw)+x_loc);
1731 24206 fmapval = *(plow_flow_map+(y_loc*iw)+x_loc);
1732 24206 cmapval = *(phigh_curve_map+(y_loc*iw)+x_loc);
1733
1734 /* If the minutia point is in a block with INVALID direction ... */
1735
2/2
✓ Branch 0 taken 23240 times.
✓ Branch 1 taken 966 times.
 24206 if(dmapval == INVALID_DIR)
1736 /* Then, IGNORE the point. */
1737 return(IGNORE);
1738
1739 /* If current minutia is in a HIGH CURVATURE block... */
1740
2/2
✓ Branch 0 taken 1771 times.
✓ Branch 1 taken 21469 times.
 23240 if(cmapval){
1741 /* Adjust location and direction locally. */
1742
2/2
✓ Branch 1 taken 1067 times.
✓ Branch 2 taken 704 times.
 1771 if((ret = adjust_high_curvature_minutia_V2(&idir, &x_loc, &y_loc,
1743 &x_edge, &y_edge, x_loc, y_loc, x_edge, y_edge,
1744 bdata, iw, ih, plow_flow_map, minutiae, lfsparms))){
1745 /* Could be a system error or IGNORE minutia. */
1746 return(ret);
1747 }
1748 /* Otherwise, we have our high-curvature minutia attributes. */
1749 }
1750 /* Otherwise, minutia is in fairly low-curvature block... */
1751 else{
1752 /* Get minutia direction based on current block's direction. */
1753 21469 idir = get_low_curvature_direction(SCAN_VERTICAL,
1754 g_feature_patterns[feature_id].appearing, dmapval,
1755 21469 lfsparms->num_directions);
1756 }
1757
1758 /* If current minutia is in a LOW RIDGE FLOW block ... */
1759
2/2
✓ Branch 0 taken 10373 times.
✓ Branch 1 taken 12163 times.
 22536 if(fmapval)
1760 reliability = MEDIUM_RELIABILITY;
1761 else
1762 /* Otherwise, minutia is in a block with reliable direction and */
1763 /* binarization. */
1764 10373 reliability = HIGH_RELIABILITY;
1765
1766 /* Create a minutia object based on derived attributes. */
1767
1/2
✓ Branch 1 taken 22536 times.
✗ Branch 2 not taken.
 22536 if((ret = create_minutia(&minutia, x_loc, y_loc, x_edge, y_edge, idir,
1768 reliability,
1769 g_feature_patterns[feature_id].type,
1770 g_feature_patterns[feature_id].appearing, feature_id)))
1771 /* Return system error. */
1772 return(ret);
1773
1774 /* Update the minutiae list with potential new minutia. */
1775 22536 ret = update_minutiae_V2(minutiae, minutia, SCAN_VERTICAL,
1776 dmapval, bdata, iw, ih, lfsparms);
1777
1778 /* If minuitia IGNORED and not added to the minutia list ... */
1779
2/2
✓ Branch 0 taken 7487 times.
✓ Branch 1 taken 15049 times.
 22536 if(ret != 0)
1780 /* Deallocate the minutia. */
1781 7487 free_minutia(minutia);
1782
1783 /* Otherwise, return normally. */
1784 return(0);
1785 }
1786
1787 /*************************************************************************
1788 **************************************************************************
1789 #cat: adjust_high_curvature_minutia - Takes an initial minutia point detected
1790 #cat: in a high-curvature area and adjusts its location and
1791 #cat: direction. First, it walks and extracts the contour
1792 #cat: of the detected feature looking for and processing any loop
1793 #cat: discovered along the way. Once the contour is extracted,
1794 #cat: the point of highest-curvature is determined and used to
1795 #cat: adjust the location of the minutia point. The angle of
1796 #cat: the line perpendicular to the tangent on the high-curvature
1797 #cat: contour at the minutia point is used as the mintutia's
1798 #cat: direction.
1799
1800 Input:
1801 x_loc - starting x-pixel coord of feature (interior to feature)
1802 y_loc - starting y-pixel coord of feature (interior to feature)
1803 x_edge - x-pixel coord of corresponding edge pixel
1804 (exterior to feature)
1805 y_edge - y-pixel coord of corresponding edge pixel
1806 (exterior to feature)
1807 bdata - binary image data (0==while & 1==black)
1808 iw - width (in pixels) of image
1809 ih - height (in pixels) of image
1810 lfsparms - parameters and thresholds for controlling LFS
1811 Output:
1812 oidir - direction of adjusted minutia point
1813 ox_loc - adjusted x-pixel coord of feature
1814 oy_loc - adjusted y-pixel coord of feature
1815 ox_edge - adjusted x-pixel coord of corresponding edge pixel
1816 oy_edge - adjusted y-pixel coord of corresponding edge pixel
1817 minutiae - points to a list of detected minutia structures
1818 Return Code:
1819 Zero - minutia point processed successfully
1820 IGNORE - minutia point is to be ignored
1821 Negative - system error
1822 **************************************************************************/
1823
1824 /*************************************************************************
1825 **************************************************************************
1826 #cat: adjust_high_curvature_minutia_V2 - Takes an initial minutia point
1827 #cat: in a high-curvature area and adjusts its location and
1828 #cat: direction. First, it walks and extracts the contour
1829 #cat: of the detected feature looking for and processing any loop
1830 #cat: discovered along the way. Once the contour is extracted,
1831 #cat: the point of highest-curvature is determined and used to
1832 #cat: adjust the location of the minutia point. The angle of
1833 #cat: the line perpendicular to the tangent on the high-curvature
1834 #cat: contour at the minutia point is used as the mintutia's
1835 #cat: direction.
1836
1837 Input:
1838 x_loc - starting x-pixel coord of feature (interior to feature)
1839 y_loc - starting y-pixel coord of feature (interior to feature)
1840 x_edge - x-pixel coord of corresponding edge pixel
1841 (exterior to feature)
1842 y_edge - y-pixel coord of corresponding edge pixel
1843 (exterior to feature)
1844 bdata - binary image data (0==while & 1==black)
1845 iw - width (in pixels) of image
1846 ih - height (in pixels) of image
1847 plow_flow_map - pixelized Low Ridge Flow Map
1848 lfsparms - parameters and thresholds for controlling LFS
1849 Output:
1850 oidir - direction of adjusted minutia point
1851 ox_loc - adjusted x-pixel coord of feature
1852 oy_loc - adjusted y-pixel coord of feature
1853 ox_edge - adjusted x-pixel coord of corresponding edge pixel
1854 oy_edge - adjusted y-pixel coord of corresponding edge pixel
1855 minutiae - points to a list of detected minutia structures
1856 Return Code:
1857 Zero - minutia point processed successfully
1858 IGNORE - minutia point is to be ignored
1859 Negative - system error
1860 **************************************************************************/
1861 3716 int adjust_high_curvature_minutia_V2(int *oidir, int *ox_loc, int *oy_loc,
1862 int *ox_edge, int *oy_edge,
1863 const int x_loc, const int y_loc,
1864 const int x_edge, const int y_edge,
1865 unsigned char *bdata, const int iw, const int ih,
1866 int *plow_flow_map, MINUTIAE *minutiae, const LFSPARMS *lfsparms)
1867 {
1868 3716 int ret;
1869 3716 int *contour_x, *contour_y, *contour_ex, *contour_ey, ncontour;
1870 3716 int min_i;
1871 3716 double min_theta;
1872 3716 int feature_pix;
1873 3716 int mid_x, mid_y, mid_pix;
1874 3716 int idir;
1875 3716 int half_contour, angle_edge;
1876
1877 /* Set variable from parameter structure. */
1878 3716 half_contour = lfsparms->high_curve_half_contour;
1879
1880 /* Set edge length for computing contour's angle of curvature */
1881 /* to one quarter of desired pixel length of entire contour. */
1882 /* Ex. If half_contour==14, then contour length==29=(2X14)+1 */
1883 /* and angle_edge==7=(14/2). */
1884 3716 angle_edge = half_contour>>1;
1885
1886 /* Get the pixel value of current feature. */
1887 3716 feature_pix = *(bdata + (y_loc * iw) + x_loc);
1888
1889 /* Extract feature's contour. */
1890
2/2
✓ Branch 1 taken 167 times.
✓ Branch 2 taken 3549 times.
 3716 if((ret = get_high_curvature_contour(&contour_x, &contour_y,
1891 &contour_ex, &contour_ey, &ncontour, half_contour,
1892 x_loc, y_loc, x_edge, y_edge, bdata, iw, ih))){
1893 /* Returns with: */
1894 /* 1. Successful or empty contour == 0 */
1895 /* If contour is empty, then contour lists are not allocated. */
1896 /* 2. Contour forms loop == LOOP_FOUND */
1897 /* 3. Sysetm error < 0 */
1898
1899 /* If the contour forms a loop... */
1900
1/2
✓ Branch 0 taken 167 times.
✗ Branch 1 not taken.
 167 if(ret == LOOP_FOUND){
1901
1902 /* If the order of the contour is clockwise, then the loops's */
1903 /* contour pixels are outside the corresponding edge pixels. We */
1904 /* definitely do NOT want to fill based on the feature pixel in */
1905 /* this case, because it is OUTSIDE the loop. For now we will */
1906 /* ignore the loop and the minutia that triggered its tracing. */
1907 /* It is likely that other minutia on the loop will be */
1908 /* detected that create a contour on the "inside" of the loop. */
1909 /* There is another issue here that could be addressed ... */
1910 /* It seems that many/multiple minutia are often detected within */
1911 /* the same loop, which currently requires retracing the loop, */
1912 /* locating minutia on opposite ends of the major axis of the */
1913 /* loop, and then determining that the minutia have already been */
1914 /* entered into the minutiae list upon processing the very first */
1915 /* minutia detected in the loop. There is a lot of redundant */
1916 /* work being done here! */
1917 /* Is_loop_clockwise takes a default value to be returned if the */
1918 /* routine is unable to determine the direction of the contour. */
1919 /* In this case, we want to IGNORE the loop if we can't tell its */
1920 /* direction so that we do not inappropriately fill the loop, so */
1921 /* we are passing the default value TRUE. */
1922
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 167 times.
 167 if((ret = is_loop_clockwise(contour_x, contour_y, ncontour, TRUE))){
1923 /* Deallocate contour lists. */
1924 ✗ free_contour(contour_x, contour_y, contour_ex, contour_ey);
1925 /* If we had a system error... */
1926 ✗ if(ret < 0)
1927 /* Return the error code. */
1928 return(ret);
1929 /* Otherwise, loop is clockwise, so return IGNORE. */
1930 return(IGNORE);
1931 }
1932
1933 /* Otherwise, process the clockwise-ordered contour of the loop */
1934 /* as it may contain minutia. If no minutia found, then it is */
1935 /* filled in. */
1936 167 ret = process_loop_V2(minutiae, contour_x, contour_y,
1937 contour_ex, contour_ey, ncontour,
1938 bdata, iw, ih, plow_flow_map, lfsparms);
1939 /* Returns with: */
1940 /* 1. Successful processing of loop == 0 */
1941 /* 2. System error < 0 */
1942
1943 /* Deallocate contour lists. */
1944 167 free_contour(contour_x, contour_y, contour_ex, contour_ey);
1945
1946 /* If loop processed successfully ... */
1947
1/2
✓ Branch 0 taken 167 times.
✗ Branch 1 not taken.
 167 if(ret == 0)
1948 /* Then either a minutia pair was extracted or the loop was */
1949 /* filled. Either way we want to IGNORE the minutia that */
1950 /* started the whole loop processing in the beginning. */
1951 return(IGNORE);
1952
1953 /* Otherwise, there was a system error. */
1954 /* Return the resulting code. */
1955 return(ret);
1956 }
1957
1958 /* Otherwise not a loop, so get_high_curvature_contour incurred */
1959 /* a system error. Return the error code. */
1960 return(ret);
1961 }
1962
1963 /* If contour is empty ... then contour lists were not allocated, so */
1964 /* simply return IGNORE. The contour comes back empty when there */
1965 /* were not a sufficient number of points found on the contour. */
1966
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3549 times.
 3549 if(ncontour == 0)
1967 return(IGNORE);
1968
1969 /* Otherwise, there are contour points to process. */
1970
1971 /* Given the contour, determine the point of highest curvature */
1972 /* (ie. forming the minimum angle between contour walls). */
1973
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 3549 times.
 3549 if((ret = min_contour_theta(&min_i, &min_theta, angle_edge,
1974 contour_x, contour_y, ncontour))){
1975 /* Deallocate contour lists. */
1976 ✗ free_contour(contour_x, contour_y, contour_ex, contour_ey);
1977 /* Returns IGNORE or system error. Either way */
1978 /* free the contour and return the code. */
1979 ✗ return(ret);
1980 }
1981
1982 /* If the minimum theta found along the contour is too large... */
1983
2/2
✓ Branch 0 taken 935 times.
✓ Branch 1 taken 2614 times.
 3549 if(min_theta >= lfsparms->max_high_curve_theta){
1984 /* Deallocate contour lists. */
1985 935 free_contour(contour_x, contour_y, contour_ex, contour_ey);
1986 /* Reject the high-curvature minutia, and return IGNORE. */
1987 935 return(IGNORE);
1988 }
1989
1990 /* Test to see if interior of curvature is OK. Compute midpoint */
1991 /* between left and right points symmetrically distant (angle_edge */
1992 /* pixels) from the contour's point of minimum theta. */
1993 2614 mid_x = (contour_x[min_i-angle_edge] + contour_x[min_i+angle_edge])>>1;
1994 2614 mid_y = (contour_y[min_i-angle_edge] + contour_y[min_i+angle_edge])>>1;
1995 2614 mid_pix = *(bdata + (mid_y * iw) + mid_x);
1996 /* If the interior pixel value is not the same as the feature's... */
1997
2/2
✓ Branch 0 taken 407 times.
✓ Branch 1 taken 2207 times.
 2614 if(mid_pix != feature_pix){
1998 /* Deallocate contour lists. */
1999 407 free_contour(contour_x, contour_y, contour_ex, contour_ey);
2000 /* Reject the high-curvature minutia and return IGNORE. */
2001 407 return(IGNORE);
2002 }
2003
2004 /* Compute new direction based on line connecting adjusted feature */
2005 /* location and the midpoint in the feature's interior. */
2006 4414 idir = line2direction(contour_x[min_i], contour_y[min_i],
2007 2207 mid_x, mid_y, lfsparms->num_directions);
2008
2009 /* Set minutia location to minimum theta position on the contour. */
2010 2207 *oidir = idir;
2011 2207 *ox_loc = contour_x[min_i];
2012 2207 *oy_loc = contour_y[min_i];
2013 2207 *ox_edge = contour_ex[min_i];
2014 2207 *oy_edge = contour_ey[min_i];
2015
2016 /* Deallocate contour buffers. */
2017 2207 free_contour(contour_x, contour_y, contour_ex, contour_ey);
2018
2019 /*Return normally. */
2020 2207 return(0);
2021 }
2022
2023 /*************************************************************************
2024 **************************************************************************
2025 #cat: get_low_curvature_direction - Converts a bi-direcitonal IMAP direction
2026 #cat: (based on a semi-circle) to a uni-directional value covering
2027 #cat: a full circle based on the scan orientation used to detect
2028 #cat: a minutia feature (horizontal or vertical) and whether the
2029 #cat: detected minutia is appearing or disappearing.
2030
2031 Input:
2032 scan_dir - designates the feature scan orientation
2033 appearing - designates the minutia as appearing or disappearing
2034 imapval - IMAP block direction
2035 ndirs - number of IMAP directions (in semicircle)
2036 Return Code:
2037 New direction - bi-directonal integer direction on full circle
2038 *************************************************************************/
2039 47942 int get_low_curvature_direction(const int scan_dir, const int appearing,
2040 const int imapval, const int ndirs)
2041 {
2042 47942 int idir;
2043
2044 /* Start direction out with IMAP value. */
2045 47942 idir = imapval;
2046
2047 /* NOTE! */
2048 /* The logic in this routine should hold whether for ridge endings */
2049 /* or for bifurcations. The examples in the comments show ridge */
2050 /* ending conditions only. */
2051
2052 /* CASE I : Ridge flow in Quadrant I; directions [0..8] */
2053
2/2
✓ Branch 0 taken 27757 times.
✓ Branch 1 taken 20185 times.
 47942 if(imapval <= (ndirs>>1)){
2054 /* I.A: HORIZONTAL scan */
2055
2/2
✓ Branch 0 taken 15159 times.
✓ Branch 1 taken 12598 times.
 27757 if(scan_dir == SCAN_HORIZONTAL){
2056 /* I.A.1: Appearing Minutia */
2057
2/2
✓ Branch 0 taken 7656 times.
✓ Branch 1 taken 7503 times.
 15159 if(appearing){
2058 /* Ex. 0 0 0 */
2059 /* 0 1 0 */
2060 /* ? ? */
2061 /* Ridge flow is up and to the right, whereas */
2062 /* actual ridge is running down and to the */
2063 /* left. */
2064 /* Thus: HORIZONTAL : appearing : should be */
2065 /* OPPOSITE the ridge flow direction. */
2066 7656 idir += ndirs;
2067 }
2068 /* Otherwise: */
2069 /* I.A.2: Disappearing Minutia */
2070 /* Ex. ? ? */
2071 /* 0 1 0 */
2072 /* 0 0 0 */
2073 /* Ridge flow is up and to the right, which */
2074 /* should be SAME direction from which ridge */
2075 /* is projecting. */
2076 /* Thus: HORIZONTAL : disappearing : should */
2077 /* be the same as ridge flow direction. */
2078 } /* End if HORIZONTAL scan */
2079 /* Otherwise: */
2080 /* I.B: VERTICAL scan */
2081 else{
2082 /* I.B.1: Disappearing Minutia */
2083
2/2
✓ Branch 0 taken 5939 times.
✓ Branch 1 taken 6659 times.
 12598 if(!appearing){
2084 /* Ex. 0 0 */
2085 /* ? 1 0 */
2086 /* ? 0 0 */
2087 /* Ridge flow is up and to the right, whereas */
2088 /* actual ridge is projecting down and to the */
2089 /* left. */
2090 /* Thus: VERTICAL : disappearing : should be */
2091 /* OPPOSITE the ridge flow direction. */
2092 5939 idir += ndirs;
2093 }
2094 /* Otherwise: */
2095 /* I.B.2: Appearing Minutia */
2096 /* Ex. 0 0 ? */
2097 /* 0 1 ? */
2098 /* 0 0 */
2099 /* Ridge flow is up and to the right, which */
2100 /* should be SAME direction the ridge is */
2101 /* running. */
2102 /* Thus: VERTICAL : appearing : should be */
2103 /* be the same as ridge flow direction. */
2104 } /* End else VERTICAL scan */
2105 } /* End if Quadrant I */
2106
2107 /* Otherwise: */
2108 /* CASE II : Ridge flow in Quadrant II; directions [9..15] */
2109 else{
2110 /* II.A: HORIZONTAL scan */
2111
2/2
✓ Branch 0 taken 11314 times.
✓ Branch 1 taken 8871 times.
 20185 if(scan_dir == SCAN_HORIZONTAL){
2112 /* II.A.1: Disappearing Minutia */
2113
2/2
✓ Branch 0 taken 5619 times.
✓ Branch 1 taken 5695 times.
 11314 if(!appearing){
2114 /* Ex. ? ? */
2115 /* 0 1 0 */
2116 /* 0 0 0 */
2117 /* Ridge flow is down and to the right, */
2118 /* whereas actual ridge is running up and to */
2119 /* the left. */
2120 /* Thus: HORIZONTAL : disappearing : should */
2121 /* be OPPOSITE the ridge flow direction.*/
2122 5619 idir += ndirs;
2123 }
2124 /* Otherwise: */
2125 /* II.A.2: Appearing Minutia */
2126 /* Ex. 0 0 0 */
2127 /* 0 1 0 */
2128 /* ? ? */
2129 /* Ridge flow is down and to the right, which */
2130 /* should be same direction from which ridge */
2131 /* is projecting. */
2132 /* Thus: HORIZONTAL : appearing : should be */
2133 /* the SAME as ridge flow direction. */
2134 } /* End if HORIZONTAL scan */
2135 /* Otherwise: */
2136 /* II.B: VERTICAL scan */
2137 else{
2138 /* II.B.1: Disappearing Minutia */
2139
2/2
✓ Branch 0 taken 4502 times.
✓ Branch 1 taken 4369 times.
 8871 if(!appearing){
2140 /* Ex. ? 0 0 */
2141 /* ? 1 0 */
2142 /* 0 0 */
2143 /* Ridge flow is down and to the right, */
2144 /* whereas actual ridge is running up and to */
2145 /* the left. */
2146 /* Thus: VERTICAL : disappearing : should be */
2147 /* OPPOSITE the ridge flow direction. */
2148 4502 idir += ndirs;
2149 }
2150 /* Otherwise: */
2151 /* II.B.2: Appearing Minutia */
2152 /* Ex. 0 0 */
2153 /* 0 1 ? */
2154 /* 0 0 ? */
2155 /* Ridge flow is down and to the right, which */
2156 /* should be same direction the ridge is */
2157 /* projecting. */
2158 /* Thus: VERTICAL : appearing : should be */
2159 /* be the SAME as ridge flow direction. */
2160 } /* End else VERTICAL scan */
2161 } /* End else Quadrant II */
2162
2163 /* Return resulting direction on range [0..31]. */
2164 47942 return(idir);
2165 }
2166
2167