1 /*******************************************************************************
2
3 License:
4 This software was developed at the National Institute of Standards and
5 Technology (NIST) by employees of the Federal Government in the course
6 of their official duties. Pursuant to title 17 Section 105 of the
7 United States Code, this software is not subject to copyright protection
8 and is in the public domain. NIST assumes no responsibility whatsoever for
9 its use by other parties, and makes no guarantees, expressed or implied,
10 about its quality, reliability, or any other characteristic.
11
12 Disclaimer:
13 This software was developed to promote biometric standards and biometric
14 technology testing for the Federal Government in accordance with the USA
15 PATRIOT Act and the Enhanced Border Security and Visa Entry Reform Act.
16 Specific hardware and software products identified in this software were used
17 in order to perform the software development. In no case does such
18 identification imply recommendation or endorsement by the National Institute
19 of Standards and Technology, nor does it imply that the products and equipment
20 identified are necessarily the best available for the purpose.
21
22 *******************************************************************************/
23
24 /***********************************************************************
25 LIBRARY: LFS - NIST Latent Fingerprint System
26
27 FILE: MINUTIA.C
28 AUTHOR: Michael D. Garris
29 DATE: 05/11/1999
30 UPDATED: 10/04/1999 Version 2 by MDG
31 UPDATED: 09/13/2004
32
33 Contains routines responsible for detecting initial minutia
34 points as part of the NIST Latent Fingerprint System (LFS).
35
36 ***********************************************************************
37 ROUTINES:
38 alloc_minutiae()
39 realloc_minutiae()
40 detect_minutiae_V2()
41 update_minutiae()
42 update_minutiae_V2()
43 sort_minutiae_y_x()
44 sort_minutiae_x_y()
45 rm_dup_minutiae()
46 dump_minutiae()
47 dump_minutiae_pts()
48 dump_reliable_minutiae_pts()
49 create_minutia()
50 free_minutiae()
51 free_minutia()
52 remove_minutia()
53 join_minutia()
54 minutia_type()
55 is_minutia_appearing()
56 choose_scan_direction()
57 scan4minutiae()
58 scan4minutiae_horizontally()
59 scan4minutiae_horizontally_V2()
60 scan4minutiae_vertically()
61 scan4minutiae_vertically_V2()
62 rescan4minutiae_horizontally()
63 rescan4minutiae_vertically()
64 rescan_partial_horizontally()
65 rescan_partial_vertically()
66 get_nbr_block_index()
67 adjust_horizontal_rescan()
68 adjust_vertical_rescan()
69 process_horizontal_scan_minutia()
70 process_horizontal_scan_minutia_V2()
71 process_vertical_scan_minutia()
72 process_vertical_scan_minutia_V2()
73 adjust_high_curvature_minutia()
74 adjust_high_curvature_minutia_V2()
75 get_low_curvature_direction()
76 lfs2nist_minutia_XYT()
77
78 ***********************************************************************/
79
80 #include <stdio.h>
81 #include <stdlib.h>
82 #include <lfs.h>
83
84
85
86 /*************************************************************************
87 **************************************************************************
88 #cat: alloc_minutiae - Allocates and initializes a minutia list based on the
89 #cat: specified maximum number of minutiae to be detected.
90
91 Input:
92 max_minutiae - number of minutia to be allocated in list
93 Output:
94 ominutiae - points to the allocated minutiae list
95 Return Code:
96 Zero - successful completion
97 Negative - system error
98 **************************************************************************/
alloc_minutiae(MINUTIAE ** ominutiae,const int max_minutiae)99 int alloc_minutiae(MINUTIAE **ominutiae, const int max_minutiae)
100 {
101 MINUTIAE *minutiae;
102
103 minutiae = (MINUTIAE *)malloc(sizeof(MINUTIAE));
104 if(minutiae == (MINUTIAE *)NULL){
105 fprintf(stderr, "ERROR : alloc_minutiae : malloc : minutiae\n");
106 exit(-430);
107 }
108 minutiae->list = (MINUTIA **)malloc(max_minutiae * sizeof(MINUTIA *));
109 if(minutiae->list == (MINUTIA **)NULL){
110 fprintf(stderr, "ERROR : alloc_minutiae : malloc : minutiae->list\n");
111 exit(-431);
112 }
113
114 minutiae->alloc = max_minutiae;
115 minutiae->num = 0;
116
117 *ominutiae = minutiae;
118 return(0);
119 }
120
121 /*************************************************************************
122 **************************************************************************
123 #cat: realloc_minutiae - Reallocates a previously allocated minutia list
124 #cat: extending its allocated length based on the specified
125 #cat: increment.
126
127 Input:
128 minutiae - previously allocated list of minutiae points
129 max_minutiae - number of minutia to be allocated in list
130 Output:
131 minutiae - extended list of minutiae points
132 Return Code:
133 Zero - successful completion
134 Negative - system error
135 **************************************************************************/
realloc_minutiae(MINUTIAE * minutiae,const int incr_minutiae)136 int realloc_minutiae(MINUTIAE *minutiae, const int incr_minutiae)
137 {
138 minutiae->alloc += incr_minutiae;
139 minutiae->list = (MINUTIA **)realloc(minutiae->list,
140 minutiae->alloc * sizeof(MINUTIA *));
141 if(minutiae->list == (MINUTIA **)NULL){
142 fprintf(stderr, "ERROR : realloc_minutiae : realloc : minutiae->list\n");
143 exit(-432);
144 }
145
146 return(0);
147 }
148
149 /*************************************************************************
150 **************************************************************************
151 #cat: detect_minutiae_V2 - Takes a binary image and its associated
152 #cat: Direction and Low Flow Maps and scans each image block
153 #cat: with valid direction for minutia points. Minutia points
154 #cat: detected in LOW FLOW blocks are set with lower reliability.
155
156 Input:
157 bdata - binary image data (0==while & 1==black)
158 iw - width (in pixels) of image
159 ih - height (in pixels) of image
160 direction_map - map of image blocks containing directional ridge flow
161 low_flow_map - map of image blocks flagged as LOW RIDGE FLOW
162 high_curve_map - map of image blocks flagged as HIGH CURVATURE
163 mw - width (in blocks) of the maps
164 mh - height (in blocks) of the maps
165 lfsparms - parameters and thresholds for controlling LFS
166 Output:
167 minutiae - points to a list of detected minutia structures
168 Return Code:
169 Zero - successful completion
170 Negative - system error
171 **************************************************************************/
detect_minutiae_V2(MINUTIAE * minutiae,unsigned char * bdata,const int iw,const int ih,int * direction_map,int * low_flow_map,int * high_curve_map,const int mw,const int mh,const LFSPARMS * lfsparms)172 int detect_minutiae_V2(MINUTIAE *minutiae,
173 unsigned char *bdata, const int iw, const int ih,
174 int *direction_map, int *low_flow_map, int *high_curve_map,
175 const int mw, const int mh,
176 const LFSPARMS *lfsparms)
177 {
178 int ret;
179 int *pdirection_map, *plow_flow_map, *phigh_curve_map;
180
181 /* Pixelize the maps by assigning block values to individual pixels. */
182 if((ret = pixelize_map(&pdirection_map, iw, ih, direction_map, mw, mh,
183 lfsparms->blocksize))){
184 return(ret);
185 }
186
187 if((ret = pixelize_map(&plow_flow_map, iw, ih, low_flow_map, mw, mh,
188 lfsparms->blocksize))){
189 free(pdirection_map);
190 return(ret);
191 }
192
193 if((ret = pixelize_map(&phigh_curve_map, iw, ih, high_curve_map, mw, mh,
194 lfsparms->blocksize))){
195 free(pdirection_map);
196 free(plow_flow_map);
197 return(ret);
198 }
199
200 if((ret = scan4minutiae_horizontally_V2(minutiae, bdata, iw, ih,
201 pdirection_map, plow_flow_map, phigh_curve_map, lfsparms))){
202 free(pdirection_map);
203 free(plow_flow_map);
204 free(phigh_curve_map);
205 return(ret);
206 }
207
208 if((ret = scan4minutiae_vertically_V2(minutiae, bdata, iw, ih,
209 pdirection_map, plow_flow_map, phigh_curve_map, lfsparms))){
210 free(pdirection_map);
211 free(plow_flow_map);
212 free(phigh_curve_map);
213 return(ret);
214 }
215
216 /* Deallocate working memories. */
217 free(pdirection_map);
218 free(plow_flow_map);
219 free(phigh_curve_map);
220
221 /* Return normally. */
222 return(0);
223 }
224
225 /*************************************************************************
226 **************************************************************************
227 #cat: update_minutiae - Takes a detected minutia point and (if it is not
228 #cat: determined to already be in the minutiae list) adds it to
229 #cat: the list.
230
231 Input:
232 minutia - minutia structure for detected point
233 bdata - binary image data (0==while & 1==black)
234 iw - width (in pixels) of image
235 ih - height (in pixels) of image
236 lfsparms - parameters and thresholds for controlling LFS
237 Output:
238 minutiae - points to a list of detected minutia structures
239 Return Code:
240 Zero - minutia added to successfully added to minutiae list
241 IGNORE - minutia is to be ignored (already in the minutiae list)
242 Negative - system error
243 **************************************************************************/
update_minutiae(MINUTIAE * minutiae,MINUTIA * minutia,unsigned char * bdata,const int iw,const int ih,const LFSPARMS * lfsparms)244 int update_minutiae(MINUTIAE *minutiae, MINUTIA *minutia,
245 unsigned char *bdata, const int iw, const int ih,
246 const LFSPARMS *lfsparms)
247 {
248 int i, ret, dy, dx, delta_dir;
249 int qtr_ndirs, full_ndirs;
250
251 /* Check to see if minutiae list is full ... if so, then extend */
252 /* the length of the allocated list of minutia points. */
253 if(minutiae->num >= minutiae->alloc){
254 if((ret = realloc_minutiae(minutiae, MAX_MINUTIAE)))
255 return(ret);
256 }
257
258 /* Otherwise, there is still room for more minutia. */
259
260 /* Compute quarter of possible directions in a semi-circle */
261 /* (ie. 45 degrees). */
262 qtr_ndirs = lfsparms->num_directions>>2;
263
264 /* Compute number of directions in full circle. */
265 full_ndirs = lfsparms->num_directions<<1;
266
267 /* Is the minutiae list empty? */
268 if(minutiae->num > 0){
269 /* Foreach minutia stored in the list... */
270 for(i = 0; i < minutiae->num; i++){
271 /* If x distance between new minutia and current list minutia */
272 /* are sufficiently close... */
273 dx = abs(minutiae->list[i]->x - minutia->x);
274 if(dx < lfsparms->max_minutia_delta){
275 /* If y distance between new minutia and current list minutia */
276 /* are sufficiently close... */
277 dy = abs(minutiae->list[i]->y - minutia->y);
278 if(dy < lfsparms->max_minutia_delta){
279 /* If new minutia and current list minutia are same type... */
280 if(minutiae->list[i]->type == minutia->type){
281 /* Test to see if minutiae have similar directions. */
282 /* Take minimum of computed inner and outer */
283 /* direction differences. */
284 delta_dir = abs(minutiae->list[i]->direction -
285 minutia->direction);
286 delta_dir = min(delta_dir, full_ndirs-delta_dir);
287 /* If directional difference is <= 45 degrees... */
288 if(delta_dir <= qtr_ndirs){
289 /* If new minutia and current list minutia share */
290 /* the same point... */
291 if((dx==0) && (dy==0)){
292 /* Then the minutiae match, so don't add the new one */
293 /* to the list. */
294 return(IGNORE);
295 }
296 /* Othewise, check if they share the same contour. */
297 /* Start by searching "max_minutia_delta" steps */
298 /* clockwise. */
299 /* If new minutia point found on contour... */
300 if(search_contour(minutia->x, minutia->y,
301 lfsparms->max_minutia_delta,
302 minutiae->list[i]->x, minutiae->list[i]->y,
303 minutiae->list[i]->ex, minutiae->list[i]->ey,
304 SCAN_CLOCKWISE, bdata, iw, ih)){
305 /* Consider the new minutia to be the same as the */
306 /* current list minutia, so don't add the new one */
307 /* to the list. */
308 return(IGNORE);
309 }
310 /* Now search "max_minutia_delta" steps counter- */
311 /* clockwise along contour. */
312 /* If new minutia point found on contour... */
313 if(search_contour(minutia->x, minutia->y,
314 lfsparms->max_minutia_delta,
315 minutiae->list[i]->x, minutiae->list[i]->y,
316 minutiae->list[i]->ex, minutiae->list[i]->ey,
317 SCAN_COUNTER_CLOCKWISE, bdata, iw, ih)){
318 /* Consider the new minutia to be the same as the */
319 /* current list minutia, so don't add the new one */
320 /* to the list. */
321 return(IGNORE);
322 }
323
324 /* Otherwise, new minutia and current list minutia do */
325 /* not share the same contour, so although they are */
326 /* similar in type and location, treat them as 2 */
327 /* different minutia. */
328
329 } /* Otherwise, directions are too different. */
330 } /* Otherwise, minutiae are different type. */
331 } /* Otherwise, minutiae too far apart in Y. */
332 } /* Otherwise, minutiae too far apart in X. */
333 } /* End FOR minutia in list. */
334 } /* Otherwise, minutiae list is empty. */
335
336 /* Otherwise, assume new minutia is not in the list, so add it. */
337 minutiae->list[minutiae->num] = minutia;
338 (minutiae->num)++;
339
340 /* New minutia was successfully added to the list. */
341 /* Return normally. */
342 return(0);
343 }
344
345 /*************************************************************************
346 **************************************************************************
347 #cat: update_minutiae_V2 - Takes a detected minutia point and (if it is not
348 #cat: determined to already be in the minutiae list or the
349 #cat: new point is determined to be "more compatible") adds
350 #cat: it to the list.
351
352 Input:
353 minutia - minutia structure for detected point
354 scan_dir - orientation of scan when minutia was detected
355 dmapval - directional ridge flow of block minutia is in
356 bdata - binary image data (0==while & 1==black)
357 iw - width (in pixels) of image
358 ih - height (in pixels) of image
359 lfsparms - parameters and thresholds for controlling LFS
360 Output:
361 minutiae - points to a list of detected minutia structures
362 Return Code:
363 Zero - minutia added to successfully added to minutiae list
364 IGNORE - minutia is to be ignored (already in the minutiae list)
365 Negative - system error
366 **************************************************************************/
update_minutiae_V2(MINUTIAE * minutiae,MINUTIA * minutia,const int scan_dir,const int dmapval,unsigned char * bdata,const int iw,const int ih,const LFSPARMS * lfsparms)367 int update_minutiae_V2(MINUTIAE *minutiae, MINUTIA *minutia,
368 const int scan_dir, const int dmapval,
369 unsigned char *bdata, const int iw, const int ih,
370 const LFSPARMS *lfsparms)
371 {
372 int i, ret, dy, dx, delta_dir;
373 int qtr_ndirs, full_ndirs;
374 int map_scan_dir;
375
376 /* Check to see if minutiae list is full ... if so, then extend */
377 /* the length of the allocated list of minutia points. */
378 if(minutiae->num >= minutiae->alloc){
379 if((ret = realloc_minutiae(minutiae, MAX_MINUTIAE)))
380 return(ret);
381 }
382
383 /* Otherwise, there is still room for more minutia. */
384
385 /* Compute quarter of possible directions in a semi-circle */
386 /* (ie. 45 degrees). */
387 qtr_ndirs = lfsparms->num_directions>>2;
388
389 /* Compute number of directions in full circle. */
390 full_ndirs = lfsparms->num_directions<<1;
391
392 /* Is the minutiae list empty? */
393 if(minutiae->num > 0){
394 /* Foreach minutia stored in the list (in reverse order) ... */
395 for(i = minutiae->num-1; i >= 0; i--){
396 /* If x distance between new minutia and current list minutia */
397 /* are sufficiently close... */
398 dx = abs(minutiae->list[i]->x - minutia->x);
399 if(dx < lfsparms->max_minutia_delta){
400 /* If y distance between new minutia and current list minutia */
401 /* are sufficiently close... */
402 dy = abs(minutiae->list[i]->y - minutia->y);
403 if(dy < lfsparms->max_minutia_delta){
404 /* If new minutia and current list minutia are same type... */
405 if(minutiae->list[i]->type == minutia->type){
406 /* Test to see if minutiae have similar directions. */
407 /* Take minimum of computed inner and outer */
408 /* direction differences. */
409 delta_dir = abs(minutiae->list[i]->direction -
410 minutia->direction);
411 delta_dir = min(delta_dir, full_ndirs-delta_dir);
412 /* If directional difference is <= 45 degrees... */
413 if(delta_dir <= qtr_ndirs){
414 /* If new minutia and current list minutia share */
415 /* the same point... */
416 if((dx==0) && (dy==0)){
417 /* Then the minutiae match, so don't add the new one */
418 /* to the list. */
419 return(IGNORE);
420 }
421 /* Othewise, check if they share the same contour. */
422 /* Start by searching "max_minutia_delta" steps */
423 /* clockwise. */
424 /* If new minutia point found on contour... */
425 if(search_contour(minutia->x, minutia->y,
426 lfsparms->max_minutia_delta,
427 minutiae->list[i]->x, minutiae->list[i]->y,
428 minutiae->list[i]->ex, minutiae->list[i]->ey,
429 SCAN_CLOCKWISE, bdata, iw, ih) ||
430 search_contour(minutia->x, minutia->y,
431 lfsparms->max_minutia_delta,
432 minutiae->list[i]->x, minutiae->list[i]->y,
433 minutiae->list[i]->ex, minutiae->list[i]->ey,
434 SCAN_COUNTER_CLOCKWISE, bdata, iw, ih)){
435 /* If new minutia has VALID block direction ... */
436 if(dmapval >= 0){
437 /* Derive feature scan direction compatible */
438 /* with VALID direction. */
439 map_scan_dir = choose_scan_direction(dmapval,
440 lfsparms->num_directions);
441 /* If map scan direction compatible with scan */
442 /* direction in which new minutia was found ... */
443 if(map_scan_dir == scan_dir){
444 /* Then choose the new minutia over the one */
445 /* currently in the list. */
446 if((ret = remove_minutia(i, minutiae))){
447 return(ret);
448 }
449 /* Continue on ... */
450 }
451 else
452 /* Othersize, scan directions not compatible...*/
453 /* so choose to keep the current minutia in */
454 /* the list and ignore the new one. */
455 return(IGNORE);
456 }
457 else{
458 /* Otherwise, no reason to believe new minutia */
459 /* is any better than the current one in the list,*/
460 /* so consider the new minutia to be the same as */
461 /* the current list minutia, and don't add the new*/
462 /* one to the list. */
463 return(IGNORE);
464 }
465 }
466
467 /* Otherwise, new minutia and current list minutia do */
468 /* not share the same contour, so although they are */
469 /* similar in type and location, treat them as 2 */
470 /* different minutia. */
471
472 } /* Otherwise, directions are too different. */
473 } /* Otherwise, minutiae are different type. */
474 } /* Otherwise, minutiae too far apart in Y. */
475 } /* Otherwise, minutiae too far apart in X. */
476 } /* End FOR minutia in list. */
477 } /* Otherwise, minutiae list is empty. */
478
479 /* Otherwise, assume new minutia is not in the list, or those that */
480 /* were close neighbors were selectively removed, so add it. */
481 minutiae->list[minutiae->num] = minutia;
482 (minutiae->num)++;
483
484 /* New minutia was successfully added to the list. */
485 /* Return normally. */
486 return(0);
487 }
488
489 /*************************************************************************
490 **************************************************************************
491 #cat: sort_minutiae_y_x - Takes a list of minutia points and sorts them
492 #cat: top-to-bottom and then left-to-right.
493
494 Input:
495 minutiae - list of minutiae
496 iw - width (in pixels) of image
497 ih - height (in pixels) of image
498 Output:
499 minutiae - list of sorted minutiae
500 Return Code:
501 Zero - successful completion
502 Negative - system error
503 **************************************************************************/
sort_minutiae_y_x(MINUTIAE * minutiae,const int iw,const int ih)504 int sort_minutiae_y_x(MINUTIAE *minutiae, const int iw, const int ih)
505 {
506 int *ranks, *order;
507 int i, ret;
508 MINUTIA **newlist;
509
510 /* Allocate a list of integers to hold 1-D image pixel offsets */
511 /* for each of the 2-D minutia coordinate points. */
512 ranks = (int *)malloc(minutiae->num * sizeof(int));
513 if(ranks == (int *)NULL){
514 fprintf(stderr, "ERROR : sort_minutiae_y_x : malloc : ranks\n");
515 return(-310);
516 }
517
518 /* Compute 1-D image pixel offsets form 2-D minutia coordinate points. */
519 for(i = 0; i < minutiae->num; i++)
520 ranks[i] = (minutiae->list[i]->y * iw) + minutiae->list[i]->x;
521
522 /* Get sorted order of minutiae. */
523 if((ret = sort_indices_int_inc(&order, ranks, minutiae->num))){
524 free(ranks);
525 return(ret);
526 }
527
528 /* Allocate new MINUTIA list to hold sorted minutiae. */
529 newlist = (MINUTIA **)malloc(minutiae->num * sizeof(MINUTIA *));
530 if(newlist == (MINUTIA **)NULL){
531 free(ranks);
532 free(order);
533 fprintf(stderr, "ERROR : sort_minutiae_y_x : malloc : newlist\n");
534 return(-311);
535 }
536
537 /* Put minutia into sorted order in new list. */
538 for(i = 0; i < minutiae->num; i++)
539 newlist[i] = minutiae->list[order[i]];
540
541 /* Deallocate non-sorted list of minutia pointers. */
542 free(minutiae->list);
543 /* Assign new sorted list of minutia to minutiae list. */
544 minutiae->list = newlist;
545
546 /* Free the working memories supporting the sort. */
547 free(order);
548 free(ranks);
549
550 /* Return normally. */
551 return(0);
552 }
553
554 /*************************************************************************
555 **************************************************************************
556 #cat: sort_minutiae_x_y - Takes a list of minutia points and sorts them
557 #cat: left-to-right and then top-to-bottom.
558
559 Input:
560 minutiae - list of minutiae
561 iw - width (in pixels) of image
562 ih - height (in pixels) of image
563 Output:
564 minutiae - list of sorted minutiae
565 Return Code:
566 Zero - successful completion
567 Negative - system error
568 **************************************************************************/
sort_minutiae_x_y(MINUTIAE * minutiae,const int iw,const int ih)569 int sort_minutiae_x_y(MINUTIAE *minutiae, const int iw, const int ih)
570 {
571 int *ranks, *order;
572 int i, ret;
573 MINUTIA **newlist;
574
575 /* Allocate a list of integers to hold 1-D image pixel offsets */
576 /* for each of the 2-D minutia coordinate points. */
577 ranks = (int *)malloc(minutiae->num * sizeof(int));
578 if(ranks == (int *)NULL){
579 fprintf(stderr, "ERROR : sort_minutiae_x_y : malloc : ranks\n");
580 return(-440);
581 }
582
583 /* Compute 1-D image pixel offsets form 2-D minutia coordinate points. */
584 for(i = 0; i < minutiae->num; i++)
585 ranks[i] = (minutiae->list[i]->x * iw) + minutiae->list[i]->y;
586
587 /* Get sorted order of minutiae. */
588 if((ret = sort_indices_int_inc(&order, ranks, minutiae->num))){
589 free(ranks);
590 return(ret);
591 }
592
593 /* Allocate new MINUTIA list to hold sorted minutiae. */
594 newlist = (MINUTIA **)malloc(minutiae->num * sizeof(MINUTIA *));
595 if(newlist == (MINUTIA **)NULL){
596 free(ranks);
597 free(order);
598 fprintf(stderr, "ERROR : sort_minutiae_x_y : malloc : newlist\n");
599 return(-441);
600 }
601
602 /* Put minutia into sorted order in new list. */
603 for(i = 0; i < minutiae->num; i++)
604 newlist[i] = minutiae->list[order[i]];
605
606 /* Deallocate non-sorted list of minutia pointers. */
607 free(minutiae->list);
608 /* Assign new sorted list of minutia to minutiae list. */
609 minutiae->list = newlist;
610
611 /* Free the working memories supporting the sort. */
612 free(order);
613 free(ranks);
614
615 /* Return normally. */
616 return(0);
617 }
618
619 /*************************************************************************
620 **************************************************************************
621 #cat: rm_dup_minutiae - Takes a list of minutiae sorted in some adjacent order
622 #cat: and detects and removes redundant minutia that have the
623 #cat: same exact pixel coordinate locations (even if other
624 #cat: attributes may differ).
625
626 Input:
627 mintuiae - list of sorted minutiae
628 Output:
629 mintuiae - list of sorted minutiae with duplicates removed
630 Return Code:
631 Zero - successful completion
632 Negative - system error
633 **************************************************************************/
rm_dup_minutiae(MINUTIAE * minutiae)634 int rm_dup_minutiae(MINUTIAE *minutiae)
635 {
636 int i, ret;
637 MINUTIA *minutia1, *minutia2;
638
639 /* Work backward from the end of the list of minutiae. This way */
640 /* we can selectively remove minutia from the list and not cause */
641 /* problems with keeping track of current indices. */
642 for(i = minutiae->num-1; i > 0; i--){
643 minutia1 = minutiae->list[i];
644 minutia2 = minutiae->list[i-1];
645 /* If minutia pair has identical coordinates ... */
646 if((minutia1->x == minutia2->x) &&
647 (minutia1->y == minutia2->y)){
648 /* Remove the 2nd minutia from the minutiae list. */
649 if((ret = remove_minutia(i-1, minutiae)))
650 return(ret);
651 /* The first minutia slides into the position of the 2nd. */
652 }
653 }
654
655 /* Return successfully. */
656 return(0);
657 }
658
659 /*************************************************************************
660 **************************************************************************
661 #cat: dump_minutiae - Given a minutiae list, writes a formatted text report of
662 #cat: the list's contents to the specified open file pointer.
663
664 Input:
665 minutiae - list of minutia structures
666 Output:
667 fpout - open file pointer
668 **************************************************************************/
dump_minutiae(FILE * fpout,const MINUTIAE * minutiae)669 void dump_minutiae(FILE *fpout, const MINUTIAE *minutiae)
670 {
671 int i, j;
672
673 fprintf(fpout, "\n%d Minutiae Detected\n\n", minutiae->num);
674
675 for(i = 0; i < minutiae->num; i++){
676 /* Precision of reliablity added one decimal position */
677 /* on 09-13-04 */
678 fprintf(fpout, "%4d : %4d, %4d : %2d : %6.3f :", i,
679 minutiae->list[i]->x, minutiae->list[i]->y,
680 minutiae->list[i]->direction, minutiae->list[i]->reliability);
681 if(minutiae->list[i]->type == RIDGE_ENDING)
682 fprintf(fpout, "RIG : ");
683 else
684 fprintf(fpout, "BIF : ");
685
686 if(minutiae->list[i]->appearing)
687 fprintf(fpout, "APP : ");
688 else
689 fprintf(fpout, "DIS : ");
690
691 fprintf(fpout, "%2d ", minutiae->list[i]->feature_id);
692
693 for(j = 0; j < minutiae->list[i]->num_nbrs; j++){
694 fprintf(fpout, ": %4d,%4d; %2d ",
695 minutiae->list[minutiae->list[i]->nbrs[j]]->x,
696 minutiae->list[minutiae->list[i]->nbrs[j]]->y,
697 minutiae->list[i]->ridge_counts[j]);
698 }
699
700 fprintf(fpout, "\n");
701 }
702 }
703
704 /*************************************************************************
705 **************************************************************************
706 #cat: dump_minutiae_pts - Given a minutiae list, writes the coordinate point
707 #cat: for each minutia in the list to the specified open
708 #cat: file pointer.
709
710 Input:
711 minutiae - list of minutia structures
712 Output:
713 fpout - open file pointer
714 **************************************************************************/
dump_minutiae_pts(FILE * fpout,const MINUTIAE * minutiae)715 void dump_minutiae_pts(FILE *fpout, const MINUTIAE *minutiae)
716 {
717 int i;
718
719 /* First line in the output file contians the number of minutia */
720 /* points to be written to the file. */
721 fprintf(fpout, "%d\n", minutiae->num);
722
723 /* Foreach minutia in list... */
724 for(i = 0; i < minutiae->num; i++){
725 /* Write the minutia's coordinate point to the file pointer. */
726 fprintf(fpout, "%4d %4d\n", minutiae->list[i]->x, minutiae->list[i]->y);
727 }
728 }
729
730
731 /*************************************************************************
732 **************************************************************************
733 #cat: dump_reliable_minutiae_pts - Given a minutiae list, writes the
734 #cat: coordinate point for each minutia in the list that has
735 #cat: the specified reliability to the specified open
736 #cat: file pointer.
737
738 Input:
739 minutiae - list of minutia structures
740 reliability - desired reliability level for minutiae to be reported
741 Output:
742 fpout - open file pointer
743 **************************************************************************/
dump_reliable_minutiae_pts(FILE * fpout,const MINUTIAE * minutiae,const double reliability)744 void dump_reliable_minutiae_pts(FILE *fpout, const MINUTIAE *minutiae,
745 const double reliability)
746 {
747 int i, count;
748
749 /* First count the number of qualifying minutiae so that the */
750 /* MFS header may be written. */
751 count = 0;
752 /* Foreach minutia in list... */
753 for(i = 0; i < minutiae->num; i++){
754 if(minutiae->list[i]->reliability == reliability)
755 count++;
756 }
757
758 /* First line in the output file contians the number of minutia */
759 /* points to be written to the file. */
760 fprintf(fpout, "%d\n", count);
761
762 /* Foreach minutia in list... */
763 for(i = 0; i < minutiae->num; i++){
764 if(minutiae->list[i]->reliability == reliability)
765 /* Write the minutia's coordinate point to the file pointer. */
766 fprintf(fpout, "%4d %4d\n",
767 minutiae->list[i]->x, minutiae->list[i]->y);
768 }
769 }
770
771 /*************************************************************************
772 **************************************************************************
773 #cat: create_minutia - Takes attributes associated with a detected minutia
774 #cat: point and allocates and initializes a minutia structure.
775
776 Input:
777 x_loc - x-pixel coord of minutia (interior to feature)
778 y_loc - y-pixel coord of minutia (interior to feature)
779 x_edge - x-pixel coord of corresponding edge pixel (exterior to feature)
780 y_edge - y-pixel coord of corresponding edge pixel (exterior to feature)
781 idir - integer direction of the minutia
782 reliability - floating point measure of minutia's reliability
783 type - type of the minutia (ridge-ending or bifurcation)
784 appearing - designates the minutia as appearing or disappearing
785 feature_id - index of minutia's matching feature_patterns[]
786 Output:
787 ominutia - ponter to an allocated and initialized minutia structure
788 Return Code:
789 Zero - minutia structure successfully allocated and initialized
790 Negative - system error
791 *************************************************************************/
create_minutia(MINUTIA ** ominutia,const int x_loc,const int y_loc,const int x_edge,const int y_edge,const int idir,const double reliability,const int type,const int appearing,const int feature_id)792 int create_minutia(MINUTIA **ominutia, const int x_loc, const int y_loc,
793 const int x_edge, const int y_edge, const int idir,
794 const double reliability,
795 const int type, const int appearing, const int feature_id)
796 {
797 MINUTIA *minutia;
798
799 /* Allocate a minutia structure. */
800 minutia = (MINUTIA *)malloc(sizeof(MINUTIA));
801 /* If allocation error... */
802 if(minutia == (MINUTIA *)NULL){
803 fprintf(stderr, "ERROR : create_minutia : malloc : minutia\n");
804 return(-230);
805 }
806
807 /* Assign minutia structure attributes. */
808 minutia->x = x_loc;
809 minutia->y = y_loc;
810 minutia->ex = x_edge;
811 minutia->ey = y_edge;
812 minutia->direction = idir;
813 minutia->reliability = reliability;
814 minutia->type = type;
815 minutia->appearing = appearing;
816 minutia->feature_id = feature_id;
817 minutia->nbrs = (int *)NULL;
818 minutia->ridge_counts = (int *)NULL;
819 minutia->num_nbrs = 0;
820
821 /* Set minutia object to output pointer. */
822 *ominutia = minutia;
823 /* Return normally. */
824 return(0);
825 }
826
827 /*************************************************************************
828 **************************************************************************
829 #cat: free_minutiae - Takes a minutiae list and deallocates all memory
830 #cat: associated with it.
831
832 Input:
833 minutiae - pointer to allocated list of minutia structures
834 *************************************************************************/
free_minutiae(MINUTIAE * minutiae)835 void free_minutiae(MINUTIAE *minutiae)
836 {
837 int i;
838
839 /* Deallocate minutia structures in the list. */
840 for(i = 0; i < minutiae->num; i++)
841 free_minutia(minutiae->list[i]);
842 /* Deallocate list of minutia pointers. */
843 free(minutiae->list);
844
845 /* Deallocate the list structure. */
846 free(minutiae);
847 }
848
849 /*************************************************************************
850 **************************************************************************
851 #cat: free_minutia - Takes a minutia pointer and deallocates all memory
852 #cat: associated with it.
853
854 Input:
855 minutia - pointer to allocated minutia structure
856 *************************************************************************/
free_minutia(MINUTIA * minutia)857 void free_minutia(MINUTIA *minutia)
858 {
859 /* Deallocate sublists. */
860 if(minutia->nbrs != (int *)NULL)
861 free(minutia->nbrs);
862 if(minutia->ridge_counts != (int *)NULL)
863 free(minutia->ridge_counts);
864
865 /* Deallocate the minutia structure. */
866 free(minutia);
867 }
868
869 /*************************************************************************
870 **************************************************************************
871 #cat: remove_minutia - Removes the specified minutia point from the input
872 #cat: list of minutiae.
873
874 Input:
875 index - position of minutia to be removed from list
876 minutiae - input list of minutiae
877 Output:
878 minutiae - list with minutia removed
879 Return Code:
880 Zero - successful completion
881 Negative - system error
882 **************************************************************************/
remove_minutia(const int index,MINUTIAE * minutiae)883 int remove_minutia(const int index, MINUTIAE *minutiae)
884 {
885 int fr, to;
886
887 /* Make sure the requested index is within range. */
888 if((index < 0) && (index >= minutiae->num)){
889 fprintf(stderr, "ERROR : remove_minutia : index out of range\n");
890 return(-380);
891 }
892
893 /* Deallocate the minutia structure to be removed. */
894 free_minutia(minutiae->list[index]);
895
896 /* Slide the remaining list of minutiae up over top of the */
897 /* position of the minutia being removed. */
898 for(to = index, fr = index+1; fr < minutiae->num; to++, fr++)
899 minutiae->list[to] = minutiae->list[fr];
900
901 /* Decrement the number of minutiae remaining in the list. */
902 minutiae->num--;
903
904 /* Return normally. */
905 return(0);
906 }
907
908 /*************************************************************************
909 **************************************************************************
910 #cat: join_minutia - Takes 2 minutia points and connectes their features in
911 #cat: the input binary image. A line is drawn in the image
912 #cat: between the 2 minutia with a specified line-width radius
913 #cat: and a conditional border of pixels opposite in color
914 #cat: from the interior line.
915
916 Input:
917 minutia1 - first minutia point to be joined
918 minutia2 - second minutia point to be joined
919 bdata - binary image data (0==while & 1==black)
920 iw - width (in pixels) of image
921 ih - height (in pixels) of image
922 with_boundary - signifies the inclusion of border pixels
923 line_radius - line-width radius of join line
924 Output:
925 bdata - edited image with minutia features joined
926 Return Code:
927 Zero - successful completion
928 Negative - system error
929 **************************************************************************/
join_minutia(const MINUTIA * minutia1,const MINUTIA * minutia2,unsigned char * bdata,const int iw,const int ih,const int with_boundary,const int line_radius)930 int join_minutia(const MINUTIA *minutia1, const MINUTIA *minutia2,
931 unsigned char *bdata, const int iw, const int ih,
932 const int with_boundary, const int line_radius)
933 {
934 int dx_gte_dy, delta_x, delta_y;
935 int *x_list, *y_list, num;
936 int minutia_pix, boundary_pix;
937 int i, j, ret;
938 int x1, y1, x2, y2;
939
940 /* Compute X and Y deltas between minutia points. */
941 delta_x = abs(minutia1->x - minutia2->x);
942 delta_y = abs(minutia1->y - minutia2->y);
943
944 /* Set flag based on |DX| >= |DY|. */
945 /* If flag is true then add additional pixel width to the join line */
946 /* by adding pixels neighboring top and bottom. */
947 /* If flag is false then add additional pixel width to the join line */
948 /* by adding pixels neighboring left and right. */
949 if(delta_x >= delta_y)
950 dx_gte_dy = 1;
951 else
952 dx_gte_dy = 0;
953
954 /* Compute points along line segment between the two minutia points. */
955 if((ret = line_points(&x_list, &y_list, &num,
956 minutia1->x, minutia1->y, minutia2->x, minutia2->y)))
957 /* If error with line routine, return error code. */
958 return(ret);
959
960 /* Determine pixel color of minutia and boundary. */
961 if(minutia1->type == RIDGE_ENDING){
962 /* To connect 2 ridge-endings, draw black. */
963 minutia_pix = 1;
964 boundary_pix = 0;
965 }
966 else{
967 /* To connect 2 bifurcations, draw white. */
968 minutia_pix = 0;
969 boundary_pix = 1;
970 }
971
972 /* Foreach point on line connecting the minutiae points ... */
973 for(i = 1; i < num-1; i++){
974 /* Draw minutia pixel at current point on line. */
975 *(bdata+(y_list[i]*iw)+x_list[i]) = minutia_pix;
976
977 /* Initialize starting corrdinates for adding width to the */
978 /* join line to the current point on the line. */
979 x1 = x_list[i];
980 y1 = y_list[i];
981 x2 = x1;
982 y2 = y1;
983 /* Foreach pixel of added radial width ... */
984 for(j = 0; j < line_radius; j++){
985
986 /* If |DX|>=|DY|, we want to add width to line by writing */
987 /* to pixels neighboring above and below. */
988 /* x1 -= (0=(1-1)); y1 -= 1 ==> ABOVE */
989 /* x2 += (0=(1-1)); y2 += 1 ==> BELOW */
990 /* If |DX|<|DY|, we want to add width to line by writing */
991 /* to pixels neighboring left and right. */
992 /* x1 -= (1=(1-0)); y1 -= 0 ==> LEFT */
993 /* x2 += (1=(1-0)); y2 += 0 ==> RIGHT */
994
995 /* Advance 1st point along width dimension. */
996 x1 -= (1 - dx_gte_dy);
997 y1 -= dx_gte_dy;
998 /* If pixel 1st point is within image boundaries ... */
999 if((x1 >= 0) && (x1 < iw) &&
1000 (y1 >= 0) && (y1 < ih))
1001 /* Write the pixel ABOVE or LEFT. */
1002 *(bdata+(y1*iw)+x1) = minutia_pix;
1003
1004 /* Advance 2nd point along width dimension. */
1005 x2 += (1 - dx_gte_dy);
1006 y2 += dx_gte_dy;
1007 /* If pixel 2nd point is within image boundaries ... */
1008 if((x2 >= 0) && (x2 < iw) &&
1009 /* Write the pixel BELOW or RIGHT. */
1010 (y2 >= 0) && (y2 < ih))
1011 *(bdata+(y2*iw)+x2) = minutia_pix;
1012 }
1013
1014 /* If boundary flag is set ... draw the boundary pixels.*/
1015 if(with_boundary){
1016 /* Advance 1st point along width dimension. */
1017 x1 -= (1 - dx_gte_dy);
1018 y1 -= dx_gte_dy;
1019 /* If pixel 1st point is within image boundaries ... */
1020 if((x1 >= 0) && (x1 < iw) &&
1021 (y1 >= 0) && (y1 < ih))
1022 /* Write the pixel ABOVE or LEFT of opposite color. */
1023 *(bdata+(y1*iw)+x1) = boundary_pix;
1024
1025 /* Advance 2nd point along width dimension. */
1026 x2 += (1 - dx_gte_dy);
1027 y2 += dx_gte_dy;
1028 /* If pixel 2nd point is within image boundaries ... */
1029 if((x2 >= 0) && (x2 < iw) &&
1030 (y2 >= 0) && (y2 < ih))
1031 /* Write the pixel BELOW or RIGHT of opposite color. */
1032 *(bdata+(y2*iw)+x2) = boundary_pix;
1033 }
1034 }
1035
1036 /* Deallocate points along connecting line. */
1037 free(x_list);
1038 free(y_list);
1039
1040 /* Return normally. */
1041 return(0);
1042 }
1043
1044 /*************************************************************************
1045 **************************************************************************
1046 #cat: minutia_type - Given the pixel color of the detected feature, returns
1047 #cat: whether the minutia is a ridge-ending (black pixel) or
1048 #cat: bifurcation (white pixel).
1049
1050 Input:
1051 feature_pix - pixel color of the feature's interior
1052 Return Code:
1053 RIDGE_ENDING - minutia is a ridge-ending
1054 BIFURCATION - minutia is a bifurcation (valley-ending)
1055 **************************************************************************/
minutia_type(const int feature_pix)1056 int minutia_type(const int feature_pix)
1057 {
1058 int type;
1059
1060 /* If feature pixel is white ... */
1061 if(feature_pix == 0)
1062 /* Then the feature is a valley-ending, so BIFURCATION. */
1063 type = BIFURCATION;
1064 /* Otherwise, the feature pixel is black ... */
1065 else
1066 /* So the feature is a RIDGE-ENDING. */
1067 type = RIDGE_ENDING;
1068
1069 /* Return the type. */
1070 return(type);
1071 }
1072
1073 /*************************************************************************
1074 **************************************************************************
1075 #cat: is_minutia_appearing - Given the pixel location of a minutia feature
1076 #cat: and its corresponding adjacent edge pixel, returns whether
1077 #cat: the minutia is appearing or disappearing. Remeber, that
1078 #cat: "feature" refers to either a ridge or valley-ending.
1079
1080 Input:
1081 x_loc - x-pixel coord of feature (interior to feature)
1082 y_loc - y-pixel coord of feature (interior to feature)
1083 x_edge - x-pixel coord of corresponding edge pixel
1084 (exterior to feature)
1085 y_edge - y-pixel coord of corresponding edge pixel
1086 (exterior to feature)
1087 Return Code:
1088 APPEARING - minutia is appearing (TRUE==1)
1089 DISAPPEARING - minutia is disappearing (FALSE==0)
1090 Negative - system error
1091 **************************************************************************/
is_minutia_appearing(const int x_loc,const int y_loc,const int x_edge,const int y_edge)1092 int is_minutia_appearing(const int x_loc, const int y_loc,
1093 const int x_edge, const int y_edge)
1094 {
1095 /* Edge pixels will always be N,S,E,W of feature pixel. */
1096
1097 /* 1. When scanning for feature's HORIZONTALLY... */
1098 /* If the edge is above the feature, then appearing. */
1099 if(x_edge < x_loc)
1100 return(APPEARING);
1101 /* If the edge is below the feature, then disappearing. */
1102 if(x_edge > x_loc)
1103 return(DISAPPEARING);
1104
1105 /* 1. When scanning for feature's VERTICALLY... */
1106 /* If the edge is left of feature, then appearing. */
1107 if(y_edge < y_loc)
1108 return(APPEARING);
1109 /* If the edge is right of feature, then disappearing. */
1110 if(y_edge > y_loc)
1111 return(DISAPPEARING);
1112
1113 /* Should never get here, but just in case. */
1114 fprintf(stderr,
1115 "ERROR : is_minutia_appearing : bad configuration of pixels\n");
1116 return(-240);
1117 }
1118
1119 /*************************************************************************
1120 **************************************************************************
1121 #cat: choose_scan_direction - Determines the orientation (horizontal or
1122 #cat: vertical) in which a block is to be scanned for minutiae.
1123 #cat: The orientation is based on the blocks corresponding IMAP
1124 #cat: direction.
1125
1126 Input:
1127 imapval - Block's IMAP direction
1128 ndirs - number of possible IMAP directions (within semicircle)
1129 Return Code:
1130 SCAN_HORIZONTAL - horizontal orientation
1131 SCAN_VERTICAL - vertical orientation
1132 **************************************************************************/
choose_scan_direction(const int imapval,const int ndirs)1133 int choose_scan_direction(const int imapval, const int ndirs)
1134 {
1135 int qtr_ndirs;
1136
1137 /* Compute quarter of directions in semi-circle. */
1138 qtr_ndirs = ndirs>>2;
1139
1140 /* If ridge flow in block is relatively vertical, then we want */
1141 /* to scan for minutia features in the opposite direction */
1142 /* (ie. HORIZONTALLY). */
1143 if((imapval <= qtr_ndirs) || (imapval > (qtr_ndirs*3)))
1144 return(SCAN_HORIZONTAL);
1145 /* Otherwise, ridge flow is realtively horizontal, and we want */
1146 /* to scan for minutia features in the opposite direction */
1147 /* (ie. VERTICALLY). */
1148 else
1149 return(SCAN_VERTICAL);
1150
1151 }
1152
1153 /*************************************************************************
1154 **************************************************************************
1155 #cat: scan4minutiae - Scans a block of binary image data detecting potential
1156 #cat: minutiae points.
1157
1158 Input:
1159 bdata - binary image data (0==while & 1==black)
1160 iw - width (in pixels) of image
1161 ih - height (in pixels) of image
1162 imap - matrix of ridge flow directions
1163 nmap - IMAP augmented with blocks of HIGH-CURVATURE and
1164 blocks which have no neighboring valid directions.
1165 blk_x - x-block coord to be scanned
1166 blk_y - y-block coord to be scanned
1167 mw - width (in blocks) of IMAP and NMAP matrices.
1168 mh - height (in blocks) of IMAP and NMAP matrices.
1169 scan_x - x-pixel coord of origin of region to be scanned
1170 scan_y - y-pixel coord of origin of region to be scanned
1171 scan_w - width (in pixels) of region to be scanned
1172 scan_h - height (in pixels) of region to be scanned
1173 scan_dir - the scan orientation (horizontal or vertical)
1174 lfsparms - parameters and thresholds for controlling LFS
1175 Output:
1176 minutiae - points to a list of detected minutia structures
1177 Return Code:
1178 Zero - successful completion
1179 Negative - system error
1180 **************************************************************************/
scan4minutiae(MINUTIAE * minutiae,unsigned char * bdata,const int iw,const int ih,const int * imap,const int * nmap,const int blk_x,const int blk_y,const int mw,const int mh,const int scan_x,const int scan_y,const int scan_w,const int scan_h,const int scan_dir,const LFSPARMS * lfsparms)1181 int scan4minutiae(MINUTIAE *minutiae,
1182 unsigned char *bdata, const int iw, const int ih,
1183 const int *imap, const int *nmap,
1184 const int blk_x, const int blk_y, const int mw, const int mh,
1185 const int scan_x, const int scan_y,
1186 const int scan_w, const int scan_h, const int scan_dir,
1187 const LFSPARMS *lfsparms)
1188 {
1189 int blk_i, ret;
1190
1191 /* Compute block index from block coordinates. */
1192 blk_i = (blk_y*mw) + blk_x;
1193
1194 /* Conduct primary scan for minutiae horizontally. */
1195 if(scan_dir == SCAN_HORIZONTAL){
1196
1197 if((ret = scan4minutiae_horizontally(minutiae, bdata, iw, ih,
1198 imap[blk_i], nmap[blk_i],
1199 scan_x, scan_y, scan_w, scan_h, lfsparms))){
1200 /* Return code may be: */
1201 /* 1. ret<0 (implying system error) */
1202 return(ret);
1203 }
1204
1205 /* Rescan block vertically. */
1206 if((ret = rescan4minutiae_vertically(minutiae, bdata, iw, ih,
1207 imap, nmap, blk_x, blk_y, mw, mh,
1208 scan_x, scan_y, scan_w, scan_h, lfsparms))){
1209 /* Return code may be: */
1210 /* 1. ret<0 (implying system error) */
1211 return(ret);
1212 }
1213 }
1214
1215 /* Otherwise, conduct primary scan for minutiae vertically. */
1216 else{
1217 if((ret = scan4minutiae_vertically(minutiae, bdata, iw, ih,
1218 imap[blk_i], nmap[blk_i],
1219 scan_x, scan_y, scan_w, scan_h, lfsparms))){
1220 /* Return resulting code. */
1221 return(ret);
1222 }
1223
1224 /* Rescan block horizontally. */
1225 if((ret = rescan4minutiae_horizontally(minutiae, bdata, iw, ih,
1226 imap, nmap, blk_x, blk_y, mw, mh,
1227 scan_x, scan_y, scan_w, scan_h, lfsparms))){
1228 /* Return resulting code. */
1229 return(ret);
1230 }
1231 }
1232
1233 /* Return normally. */
1234 return(0);
1235 }
1236
1237 /*************************************************************************
1238 **************************************************************************
1239 #cat: scan4minutiae_horizontally - Scans a specified region of binary image
1240 #cat: data horizontally, detecting potential minutiae points.
1241 #cat: Minutia detected via the horizontal scan process are
1242 #cat: by nature vertically oriented (orthogonal to the scan).
1243 #cat: The region actually scanned is slightly larger than that
1244 #cat: specified. This overlap attempts to minimize the number
1245 #cat: of minutiae missed at the region boundaries.
1246 #cat: HOWEVER, some minutiae will still be missed!
1247
1248 Input:
1249 bdata - binary image data (0==while & 1==black)
1250 iw - width (in pixels) of image
1251 ih - height (in pixels) of image
1252 imapval - IMAP value associated with this image region
1253 nmapval - NMAP value associated with this image region
1254 scan_x - x-pixel coord of origin of region to be scanned
1255 scan_y - y-pixel coord of origin of region to be scanned
1256 scan_w - width (in pixels) of region to be scanned
1257 scan_h - height (in pixels) of region to be scanned
1258 lfsparms - parameters and thresholds for controlling LFS
1259 Output:
1260 minutiae - points to a list of detected minutia structures
1261 Return Code:
1262 Zero - successful completion
1263 Negative - system error
1264 **************************************************************************/
scan4minutiae_horizontally(MINUTIAE * minutiae,unsigned char * bdata,const int iw,const int ih,const int imapval,const int nmapval,const int scan_x,const int scan_y,const int scan_w,const int scan_h,const LFSPARMS * lfsparms)1265 int scan4minutiae_horizontally(MINUTIAE *minutiae,
1266 unsigned char *bdata, const int iw, const int ih,
1267 const int imapval, const int nmapval,
1268 const int scan_x, const int scan_y,
1269 const int scan_w, const int scan_h,
1270 const LFSPARMS *lfsparms)
1271 {
1272 int sx, sy, ex, ey, cx, cy, x2;
1273 unsigned char *p1ptr, *p2ptr;
1274 int possible[NFEATURES], nposs;
1275 int ret;
1276
1277 /* NOTE!!! Minutia that "straddle" region boundaries may be missed! */
1278
1279 /* If possible, overlap left and right of current scan region */
1280 /* by 2 pixel columns to help catch some minutia that straddle the */
1281 /* the scan region boundaries. */
1282 sx = max(0, scan_x-2);
1283 ex = min(iw, scan_x+scan_w+2);
1284
1285 /* If possible, overlap the scan region below by 1 pixel row. */
1286 sy = scan_y;
1287 ey = min(ih, scan_y+scan_h+1);
1288
1289 /* For now, we will not adjust for IMAP edge, as the binary image */
1290 /* was properly padded at its edges so as not to cause anomallies. */
1291
1292 /* Start at first row in region. */
1293 cy = sy;
1294 /* While second scan row not outside the bottom of the scan region... */
1295 while(cy+1 < ey){
1296 /* Start at beginning of new scan row in region. */
1297 cx = sx;
1298 /* While not at end of region's current scan row. */
1299 while(cx < ex){
1300 /* Get pixel pair from current x position in current and next */
1301 /* scan rows. */
1302 p1ptr = bdata+(cy*iw)+cx;
1303 p2ptr = bdata+((cy+1)*iw)+cx;
1304 /* If scan pixel pair matches first pixel pair of */
1305 /* 1 or more features... */
1306 if(match_1st_pair(*p1ptr, *p2ptr, possible, &nposs)){
1307 /* Bump forward to next scan pixel pair. */
1308 cx++;
1309 p1ptr++;
1310 p2ptr++;
1311 /* If not at end of region's current scan row... */
1312 if(cx < ex){
1313 /* If scan pixel pair matches second pixel pair of */
1314 /* 1 or more features... */
1315 if(match_2nd_pair(*p1ptr, *p2ptr, possible, &nposs)){
1316 /* Store current x location. */
1317 x2 = cx;
1318 /* Skip repeated pixel pairs. */
1319 skip_repeated_horizontal_pair(&cx, ex, &p1ptr, &p2ptr,
1320 iw, ih);
1321 /* If not at end of region's current scan row... */
1322 if(cx < ex){
1323 /* If scan pixel pair matches third pixel pair of */
1324 /* a single feature... */
1325 if(match_3rd_pair(*p1ptr, *p2ptr, possible, &nposs)){
1326 /* Process detected minutia point. */
1327 if((ret = process_horizontal_scan_minutia(minutiae,
1328 cx, cy, x2, possible[0],
1329 bdata, iw, ih,
1330 imapval, nmapval, lfsparms))){
1331 /* Return code may be: */
1332 /* 1. ret< 0 (implying system error) */
1333 /* 2. ret==IGNORE (ignore current feature) */
1334 if(ret < 0)
1335 return(ret);
1336 /* Otherwise, IGNORE and continue. */
1337 }
1338 }
1339
1340 /* Set up to resume scan. */
1341 /* Test to see if 3rd pair can slide into 2nd pair. */
1342 /* The values of the 2nd pair MUST be different. */
1343 /* If 3rd pair values are different ... */
1344 if(*p1ptr != *p2ptr){
1345 /* Set next first pair to last of repeated */
1346 /* 2nd pairs, ie. back up one pair. */
1347 cx--;
1348 }
1349
1350 /* Otherwise, 3rd pair can't be a 2nd pair, so */
1351 /* keep pointing to 3rd pair so that it is used */
1352 /* in the next first pair test. */
1353
1354 } /* Else, at end of current scan row. */
1355 }
1356
1357 /* Otherwise, 2nd pair failed, so keep pointing to it */
1358 /* so that it is used in the next first pair test. */
1359
1360 } /* Else, at end of current scan row. */
1361 }
1362 /* Otherwise, 1st pair failed... */
1363 else{
1364 /* Bump forward to next pixel pair. */
1365 cx++;
1366 }
1367 } /* While not at end of current scan row. */
1368 /* Bump forward to next scan row. */
1369 cy++;
1370 } /* While not out of scan rows. */
1371
1372 /* Return normally. */
1373 return(0);
1374 }
1375
1376 /*************************************************************************
1377 **************************************************************************
1378 #cat: scan4minutiae_horizontally_V2 - Scans an entire binary image
1379 #cat: horizontally, detecting potential minutiae points.
1380 #cat: Minutia detected via the horizontal scan process are
1381 #cat: by nature vertically oriented (orthogonal to the scan).
1382
1383 Input:
1384 bdata - binary image data (0==while & 1==black)
1385 iw - width (in pixels) of image
1386 ih - height (in pixels) of image
1387 pdirection_map - pixelized Direction Map
1388 plow_flow_map - pixelized Low Ridge Flow Map
1389 phigh_curve_map - pixelized High Curvature Map
1390 lfsparms - parameters and thresholds for controlling LFS
1391 Output:
1392 minutiae - points to a list of detected minutia structures
1393 Return Code:
1394 Zero - successful completion
1395 Negative - system error
1396 **************************************************************************/
scan4minutiae_horizontally_V2(MINUTIAE * minutiae,unsigned char * bdata,const int iw,const int ih,int * pdirection_map,int * plow_flow_map,int * phigh_curve_map,const LFSPARMS * lfsparms)1397 int scan4minutiae_horizontally_V2(MINUTIAE *minutiae,
1398 unsigned char *bdata, const int iw, const int ih,
1399 int *pdirection_map, int *plow_flow_map, int *phigh_curve_map,
1400 const LFSPARMS *lfsparms)
1401 {
1402 int sx, sy, ex, ey, cx, cy, x2;
1403 unsigned char *p1ptr, *p2ptr;
1404 int possible[NFEATURES], nposs;
1405 int ret;
1406
1407 /* Set scan region to entire image. */
1408 sx = 0;
1409 ex = iw;
1410 sy = 0;
1411 ey = ih;
1412
1413 /* Start at first row in region. */
1414 cy = sy;
1415 /* While second scan row not outside the bottom of the scan region... */
1416 while(cy+1 < ey){
1417 /* Start at beginning of new scan row in region. */
1418 cx = sx;
1419 /* While not at end of region's current scan row. */
1420 while(cx < ex){
1421 /* Get pixel pair from current x position in current and next */
1422 /* scan rows. */
1423 p1ptr = bdata+(cy*iw)+cx;
1424 p2ptr = bdata+((cy+1)*iw)+cx;
1425 /* If scan pixel pair matches first pixel pair of */
1426 /* 1 or more features... */
1427 if(match_1st_pair(*p1ptr, *p2ptr, possible, &nposs)){
1428 /* Bump forward to next scan pixel pair. */
1429 cx++;
1430 p1ptr++;
1431 p2ptr++;
1432 /* If not at end of region's current scan row... */
1433 if(cx < ex){
1434 /* If scan pixel pair matches second pixel pair of */
1435 /* 1 or more features... */
1436 if(match_2nd_pair(*p1ptr, *p2ptr, possible, &nposs)){
1437 /* Store current x location. */
1438 x2 = cx;
1439 /* Skip repeated pixel pairs. */
1440 skip_repeated_horizontal_pair(&cx, ex, &p1ptr, &p2ptr,
1441 iw, ih);
1442 /* If not at end of region's current scan row... */
1443 if(cx < ex){
1444 /* If scan pixel pair matches third pixel pair of */
1445 /* a single feature... */
1446 if(match_3rd_pair(*p1ptr, *p2ptr, possible, &nposs)){
1447 /* Process detected minutia point. */
1448 if((ret = process_horizontal_scan_minutia_V2(minutiae,
1449 cx, cy, x2, possible[0],
1450 bdata, iw, ih, pdirection_map,
1451 plow_flow_map, phigh_curve_map,
1452 lfsparms))){
1453 /* Return code may be: */
1454 /* 1. ret< 0 (implying system error) */
1455 /* 2. ret==IGNORE (ignore current feature) */
1456 if(ret < 0)
1457 return(ret);
1458 /* Otherwise, IGNORE and continue. */
1459 }
1460 }
1461
1462 /* Set up to resume scan. */
1463 /* Test to see if 3rd pair can slide into 2nd pair. */
1464 /* The values of the 2nd pair MUST be different. */
1465 /* If 3rd pair values are different ... */
1466 if(*p1ptr != *p2ptr){
1467 /* Set next first pair to last of repeated */
1468 /* 2nd pairs, ie. back up one pair. */
1469 cx--;
1470 }
1471
1472 /* Otherwise, 3rd pair can't be a 2nd pair, so */
1473 /* keep pointing to 3rd pair so that it is used */
1474 /* in the next first pair test. */
1475
1476 } /* Else, at end of current scan row. */
1477 }
1478
1479 /* Otherwise, 2nd pair failed, so keep pointing to it */
1480 /* so that it is used in the next first pair test. */
1481
1482 } /* Else, at end of current scan row. */
1483 }
1484 /* Otherwise, 1st pair failed... */
1485 else{
1486 /* Bump forward to next pixel pair. */
1487 cx++;
1488 }
1489 } /* While not at end of current scan row. */
1490 /* Bump forward to next scan row. */
1491 cy++;
1492 } /* While not out of scan rows. */
1493
1494 /* Return normally. */
1495 return(0);
1496 }
1497
1498 /*************************************************************************
1499 **************************************************************************
1500 #cat: scan4minutiae_vertically - Scans a specified region of binary image data
1501 #cat: vertically, detecting potential minutiae points.
1502 #cat: Minutia detected via the vetical scan process are
1503 #cat: by nature horizontally oriented (orthogonal to the scan).
1504 #cat: The region actually scanned is slightly larger than that
1505 #cat: specified. This overlap attempts to minimize the number
1506 #cat: of minutiae missed at the region boundaries.
1507 #cat: HOWEVER, some minutiae will still be missed!
1508
1509 Input:
1510 bdata - binary image data (0==while & 1==black)
1511 iw - width (in pixels) of image
1512 ih - height (in pixels) of image
1513 imapval - IMAP value associated with this image region
1514 nmapval - NMAP value associated with this image region
1515 scan_x - x-pixel coord of origin of region to be scanned
1516 scan_y - y-pixel coord of origin of region to be scanned
1517 scan_w - width (in pixels) of region to be scanned
1518 scan_h - height (in pixels) of region to be scanned
1519 lfsparms - parameters and thresholds for controlling LFS
1520 Output:
1521 minutiae - points to a list of detected minutia structures
1522 Return Code:
1523 Zero - successful completion
1524 Negative - system error
1525 **************************************************************************/
scan4minutiae_vertically(MINUTIAE * minutiae,unsigned char * bdata,const int iw,const int ih,const int imapval,const int nmapval,const int scan_x,const int scan_y,const int scan_w,const int scan_h,const LFSPARMS * lfsparms)1526 int scan4minutiae_vertically(MINUTIAE *minutiae,
1527 unsigned char *bdata, const int iw, const int ih,
1528 const int imapval, const int nmapval,
1529 const int scan_x, const int scan_y,
1530 const int scan_w, const int scan_h,
1531 const LFSPARMS *lfsparms)
1532 {
1533 int sx, sy, ex, ey, cx, cy, y2;
1534 unsigned char *p1ptr, *p2ptr;
1535 int possible[NFEATURES], nposs;
1536 int ret;
1537
1538 /* NOTE!!! Minutia that "straddle" region boundaries may be missed! */
1539
1540 /* If possible, overlap scan region to the right by 1 pixel column. */
1541 sx = scan_x;
1542 ex = min(iw, scan_x+scan_w+1);
1543
1544 /* If possible, overlap top and bottom of current scan region */
1545 /* by 2 pixel rows to help catch some minutia that straddle the */
1546 /* the scan region boundaries. */
1547 sy = max(0, scan_y-2);
1548 ey = min(ih, scan_y+scan_h+2);
1549
1550 /* For now, we will not adjust for IMAP edge, as the binary image */
1551 /* was properly padded at its edges so as not to cause anomalies. */
1552
1553 /* Start at first column in region. */
1554 cx = sx;
1555 /* While second scan column not outside the right of the region ... */
1556 while(cx+1 < ex){
1557 /* Start at beginning of new scan column in region. */
1558 cy = sy;
1559 /* While not at end of region's current scan column. */
1560 while(cy < ey){
1561 /* Get pixel pair from current y position in current and next */
1562 /* scan columns. */
1563 p1ptr = bdata+(cy*iw)+cx;
1564 p2ptr = p1ptr+1;
1565 /* If scan pixel pair matches first pixel pair of */
1566 /* 1 or more features... */
1567 if(match_1st_pair(*p1ptr, *p2ptr, possible, &nposs)){
1568 /* Bump forward to next scan pixel pair. */
1569 cy++;
1570 p1ptr+=iw;
1571 p2ptr+=iw;
1572 /* If not at end of region's current scan column... */
1573 if(cy < ey){
1574 /* If scan pixel pair matches second pixel pair of */
1575 /* 1 or more features... */
1576 if(match_2nd_pair(*p1ptr, *p2ptr, possible, &nposs)){
1577 /* Store current y location. */
1578 y2 = cy;
1579 /* Skip repeated pixel pairs. */
1580 skip_repeated_vertical_pair(&cy, ey, &p1ptr, &p2ptr,
1581 iw, ih);
1582 /* If not at end of region's current scan column... */
1583 if(cy < ey){
1584 /* If scan pixel pair matches third pixel pair of */
1585 /* a single feature... */
1586 if(match_3rd_pair(*p1ptr, *p2ptr, possible, &nposs)){
1587 /* Process detected minutia point. */
1588 if((ret = process_vertical_scan_minutia(minutiae,
1589 cx, cy, y2, possible[0],
1590 bdata, iw, ih,
1591 imapval, nmapval, lfsparms))){
1592 /* Return code may be: */
1593 /* 1. ret< 0 (implying system error) */
1594 /* 2. ret==IGNORE (ignore current feature) */
1595 if(ret < 0)
1596 return(ret);
1597 /* Otherwise, IGNORE and continue. */
1598 }
1599 }
1600
1601 /* Set up to resume scan. */
1602 /* Test to see if 3rd pair can slide into 2nd pair. */
1603 /* The values of the 2nd pair MUST be different. */
1604 /* If 3rd pair values are different ... */
1605 if(*p1ptr != *p2ptr){
1606 /* Set next first pair to last of repeated */
1607 /* 2nd pairs, ie. back up one pair. */
1608 cy--;
1609 }
1610
1611 /* Otherwise, 3rd pair can't be a 2nd pair, so */
1612 /* keep pointing to 3rd pair so that it is used */
1613 /* in the next first pair test. */
1614
1615 } /* Else, at end of current scan row. */
1616 }
1617
1618 /* Otherwise, 2nd pair failed, so keep pointing to it */
1619 /* so that it is used in the next first pair test. */
1620
1621 } /* Else, at end of current scan column. */
1622 }
1623 /* Otherwise, 1st pair failed... */
1624 else{
1625 /* Bump forward to next pixel pair. */
1626 cy++;
1627 }
1628 } /* While not at end of current scan column. */
1629 /* Bump forward to next scan column. */
1630 cx++;
1631 } /* While not out of scan columns. */
1632
1633 /* Return normally. */
1634 return(0);
1635 }
1636
1637 /*************************************************************************
1638 **************************************************************************
1639 #cat: scan4minutiae_vertically_V2 - Scans an entire binary image
1640 #cat: vertically, detecting potential minutiae points.
1641 #cat: Minutia detected via the vetical scan process are
1642 #cat: by nature horizontally oriented (orthogonal to the scan).
1643
1644 Input:
1645 bdata - binary image data (0==while & 1==black)
1646 iw - width (in pixels) of image
1647 ih - height (in pixels) of image
1648 pdirection_map - pixelized Direction Map
1649 plow_flow_map - pixelized Low Ridge Flow Map
1650 phigh_curve_map - pixelized High Curvature Map
1651 lfsparms - parameters and thresholds for controlling LFS
1652 Output:
1653 minutiae - points to a list of detected minutia structures
1654 Return Code:
1655 Zero - successful completion
1656 Negative - system error
1657 **************************************************************************/
scan4minutiae_vertically_V2(MINUTIAE * minutiae,unsigned char * bdata,const int iw,const int ih,int * pdirection_map,int * plow_flow_map,int * phigh_curve_map,const LFSPARMS * lfsparms)1658 int scan4minutiae_vertically_V2(MINUTIAE *minutiae,
1659 unsigned char *bdata, const int iw, const int ih,
1660 int *pdirection_map, int *plow_flow_map, int *phigh_curve_map,
1661 const LFSPARMS *lfsparms)
1662 {
1663 int sx, sy, ex, ey, cx, cy, y2;
1664 unsigned char *p1ptr, *p2ptr;
1665 int possible[NFEATURES], nposs;
1666 int ret;
1667
1668 /* Set scan region to entire image. */
1669 sx = 0;
1670 ex = iw;
1671 sy = 0;
1672 ey = ih;
1673
1674 /* Start at first column in region. */
1675 cx = sx;
1676 /* While second scan column not outside the right of the region ... */
1677 while(cx+1 < ex){
1678 /* Start at beginning of new scan column in region. */
1679 cy = sy;
1680 /* While not at end of region's current scan column. */
1681 while(cy < ey){
1682 /* Get pixel pair from current y position in current and next */
1683 /* scan columns. */
1684 p1ptr = bdata+(cy*iw)+cx;
1685 p2ptr = p1ptr+1;
1686 /* If scan pixel pair matches first pixel pair of */
1687 /* 1 or more features... */
1688 if(match_1st_pair(*p1ptr, *p2ptr, possible, &nposs)){
1689 /* Bump forward to next scan pixel pair. */
1690 cy++;
1691 p1ptr+=iw;
1692 p2ptr+=iw;
1693 /* If not at end of region's current scan column... */
1694 if(cy < ey){
1695 /* If scan pixel pair matches second pixel pair of */
1696 /* 1 or more features... */
1697 if(match_2nd_pair(*p1ptr, *p2ptr, possible, &nposs)){
1698 /* Store current y location. */
1699 y2 = cy;
1700 /* Skip repeated pixel pairs. */
1701 skip_repeated_vertical_pair(&cy, ey, &p1ptr, &p2ptr,
1702 iw, ih);
1703 /* If not at end of region's current scan column... */
1704 if(cy < ey){
1705 /* If scan pixel pair matches third pixel pair of */
1706 /* a single feature... */
1707 if(match_3rd_pair(*p1ptr, *p2ptr, possible, &nposs)){
1708 /* Process detected minutia point. */
1709 if((ret = process_vertical_scan_minutia_V2(minutiae,
1710 cx, cy, y2, possible[0],
1711 bdata, iw, ih, pdirection_map,
1712 plow_flow_map, phigh_curve_map,
1713 lfsparms))){
1714 /* Return code may be: */
1715 /* 1. ret< 0 (implying system error) */
1716 /* 2. ret==IGNORE (ignore current feature) */
1717 if(ret < 0)
1718 return(ret);
1719 /* Otherwise, IGNORE and continue. */
1720 }
1721 }
1722
1723 /* Set up to resume scan. */
1724 /* Test to see if 3rd pair can slide into 2nd pair. */
1725 /* The values of the 2nd pair MUST be different. */
1726 /* If 3rd pair values are different ... */
1727 if(*p1ptr != *p2ptr){
1728 /* Set next first pair to last of repeated */
1729 /* 2nd pairs, ie. back up one pair. */
1730 cy--;
1731 }
1732
1733 /* Otherwise, 3rd pair can't be a 2nd pair, so */
1734 /* keep pointing to 3rd pair so that it is used */
1735 /* in the next first pair test. */
1736
1737 } /* Else, at end of current scan row. */
1738 }
1739
1740 /* Otherwise, 2nd pair failed, so keep pointing to it */
1741 /* so that it is used in the next first pair test. */
1742
1743 } /* Else, at end of current scan column. */
1744 }
1745 /* Otherwise, 1st pair failed... */
1746 else{
1747 /* Bump forward to next pixel pair. */
1748 cy++;
1749 }
1750 } /* While not at end of current scan column. */
1751 /* Bump forward to next scan column. */
1752 cx++;
1753 } /* While not out of scan columns. */
1754
1755 /* Return normally. */
1756 return(0);
1757 }
1758
1759 /*************************************************************************
1760 **************************************************************************
1761 #cat: rescan4minutiae_horizontally - Rescans portions of a block of binary
1762 #cat: image data horizontally for potential minutiae. The areas
1763 #cat: rescanned within the block are based on the current
1764 #cat: block's neighboring blocks' IMAP and NMAP values.
1765
1766 Input:
1767 bdata - binary image data (0==while & 1==black)
1768 iw - width (in pixels) of image
1769 ih - height (in pixels) of image
1770 imap - matrix of ridge flow directions
1771 nmap - IMAP augmented with blocks of HIGH-CURVATURE and
1772 blocks which have no neighboring valid directions.
1773 blk_x - x-block coord to be rescanned
1774 blk_y - y-block coord to be rescanned
1775 mw - width (in blocks) of IMAP and NMAP matrices.
1776 mh - height (in blocks) of IMAP and NMAP matrices.
1777 scan_x - x-pixel coord of origin of region to be rescanned
1778 scan_y - y-pixel coord of origin of region to be rescanned
1779 scan_w - width (in pixels) of region to be rescanned
1780 scan_h - height (in pixels) of region to be rescanned
1781 lfsparms - parameters and thresholds for controlling LFS
1782 Output:
1783 minutiae - points to a list of detected minutia structures
1784 Return Code:
1785 Zero - successful completion
1786 Negative - system error
1787 **************************************************************************/
rescan4minutiae_horizontally(MINUTIAE * minutiae,unsigned char * bdata,const int iw,const int ih,const int * imap,const int * nmap,const int blk_x,const int blk_y,const int mw,const int mh,const int scan_x,const int scan_y,const int scan_w,const int scan_h,const LFSPARMS * lfsparms)1788 int rescan4minutiae_horizontally(MINUTIAE *minutiae,
1789 unsigned char *bdata, const int iw, const int ih,
1790 const int *imap, const int *nmap,
1791 const int blk_x, const int blk_y,
1792 const int mw, const int mh,
1793 const int scan_x, const int scan_y,
1794 const int scan_w, const int scan_h,
1795 const LFSPARMS *lfsparms)
1796 {
1797 int blk_i, ret;
1798
1799 /* Compute block index from block coordinates. */
1800 blk_i = (blk_y*mw)+blk_x;
1801
1802 /* If high-curve block... */
1803 if(nmap[blk_i] == HIGH_CURVATURE){
1804 /* Rescan entire block in orthogonal direction. */
1805 if((ret = scan4minutiae_horizontally(minutiae, bdata, iw, ih,
1806 imap[blk_i], nmap[blk_i],
1807 scan_x, scan_y, scan_w, scan_h, lfsparms)))
1808 /* Return code may be: */
1809 /* 1. ret<0 (implying system error) */
1810 return(ret);
1811 }
1812 /* Otherwise, block is low-curvature. */
1813 else{
1814 /* 1. Rescan horizontally to the North. */
1815 if((ret = rescan_partial_horizontally(NORTH, minutiae, bdata, iw, ih,
1816 imap, nmap, blk_x, blk_y, mw, mh,
1817 scan_x, scan_y, scan_w, scan_h, lfsparms)))
1818 /* Return code may be: */
1819 /* 1. ret<0 (implying system error) */
1820 return(ret);
1821
1822 /* 2. Rescan horizontally to the East. */
1823 if((ret = rescan_partial_horizontally(EAST, minutiae, bdata, iw, ih,
1824 imap, nmap, blk_x, blk_y, mw, mh,
1825 scan_x, scan_y, scan_w, scan_h, lfsparms)))
1826 return(ret);
1827
1828 /* 3. Rescan horizontally to the South. */
1829 if((ret = rescan_partial_horizontally(SOUTH, minutiae, bdata, iw, ih,
1830 imap, nmap, blk_x, blk_y, mw, mh,
1831 scan_x, scan_y, scan_w, scan_h, lfsparms)))
1832 return(ret);
1833
1834 /* 4. Rescan horizontally to the West. */
1835 if((ret = rescan_partial_horizontally(WEST, minutiae, bdata, iw, ih,
1836 imap, nmap, blk_x, blk_y, mw, mh,
1837 scan_x, scan_y, scan_w, scan_h, lfsparms)))
1838 return(ret);
1839 } /* End low-curvature rescan. */
1840
1841 /* Return normally. */
1842 return(0);
1843 }
1844
1845 /*************************************************************************
1846 **************************************************************************
1847 #cat: rescan4minutiae_vertically - Rescans portions of a block of binary
1848 #cat: image data vertically for potential minutiae. The areas
1849 #cat: rescanned within the block are based on the current
1850 #cat: block's neighboring blocks' IMAP and NMAP values.
1851
1852 Input:
1853 bdata - binary image data (0==while & 1==black)
1854 iw - width (in pixels) of image
1855 ih - height (in pixels) of image
1856 imap - matrix of ridge flow directions
1857 nmap - IMAP augmented with blocks of HIGH-CURVATURE and
1858 blocks which have no neighboring valid directions.
1859 blk_x - x-block coord to be rescanned
1860 blk_y - y-block coord to be rescanned
1861 mw - width (in blocks) of IMAP and NMAP matrices.
1862 mh - height (in blocks) of IMAP and NMAP matrices.
1863 scan_x - x-pixel coord of origin of region to be rescanned
1864 scan_y - y-pixel coord of origin of region to be rescanned
1865 scan_w - width (in pixels) of region to be rescanned
1866 scan_h - height (in pixels) of region to be rescanned
1867 lfsparms - parameters and thresholds for controlling LFS
1868 Output:
1869 minutiae - points to a list of detected minutia structures
1870 Return Code:
1871 Zero - successful completion
1872 Negative - system error
1873 **************************************************************************/
rescan4minutiae_vertically(MINUTIAE * minutiae,unsigned char * bdata,const int iw,const int ih,const int * imap,const int * nmap,const int blk_x,const int blk_y,const int mw,const int mh,const int scan_x,const int scan_y,const int scan_w,const int scan_h,const LFSPARMS * lfsparms)1874 int rescan4minutiae_vertically(MINUTIAE *minutiae,
1875 unsigned char *bdata, const int iw, const int ih,
1876 const int *imap, const int *nmap,
1877 const int blk_x, const int blk_y,
1878 const int mw, const int mh,
1879 const int scan_x, const int scan_y,
1880 const int scan_w, const int scan_h,
1881 const LFSPARMS *lfsparms)
1882 {
1883 int blk_i, ret;
1884
1885 /* Compute block index from block coordinates. */
1886 blk_i = (blk_y*mw)+blk_x;
1887
1888 /* If high-curve block... */
1889 if(nmap[blk_i] == HIGH_CURVATURE){
1890 /* Rescan entire block in orthogonal direction. */
1891 if((ret = scan4minutiae_vertically(minutiae, bdata, iw, ih,
1892 imap[blk_i], nmap[blk_i],
1893 scan_x, scan_y, scan_w, scan_h, lfsparms)))
1894 /* Return code may be: */
1895 /* 1. ret<0 (implying system error) */
1896 return(ret);
1897 }
1898 /* Otherwise, block is low-curvature. */
1899 else{
1900 /* 1. Rescan vertically to the North. */
1901 if((ret = rescan_partial_vertically(NORTH, minutiae, bdata, iw, ih,
1902 imap, nmap, blk_x, blk_y, mw, mh,
1903 scan_x, scan_y, scan_w, scan_h, lfsparms)))
1904 /* Return code may be: */
1905 /* 1. ret<0 (implying system error) */
1906 return(ret);
1907
1908 /* 2. Rescan vertically to the East. */
1909 if((ret = rescan_partial_vertically(EAST, minutiae, bdata, iw, ih,
1910 imap, nmap, blk_x, blk_y, mw, mh,
1911 scan_x, scan_y, scan_w, scan_h, lfsparms)))
1912 return(ret);
1913
1914 /* 3. Rescan vertically to the South. */
1915 if((ret = rescan_partial_vertically(SOUTH, minutiae, bdata, iw, ih,
1916 imap, nmap, blk_x, blk_y, mw, mh,
1917 scan_x, scan_y, scan_w, scan_h, lfsparms)))
1918 return(ret);
1919
1920 /* 4. Rescan vertically to the West. */
1921 if((ret = rescan_partial_vertically(WEST, minutiae, bdata, iw, ih,
1922 imap, nmap, blk_x, blk_y, mw, mh,
1923 scan_x, scan_y, scan_w, scan_h, lfsparms)))
1924 return(ret);
1925 } /* End low-curvature rescan. */
1926
1927 /* Return normally. */
1928 return(0);
1929 }
1930
1931 /*************************************************************************
1932 **************************************************************************
1933 #cat: rescan_partial_horizontally - Rescans a portion of a block of binary
1934 #cat: image data horizontally based on the IMAP and NMAP values
1935 #cat: of a specified neighboring block.
1936
1937 Input:
1938 nbr_dir - specifies which block neighbor {NORTH, SOUTH, EAST, WEST}
1939 bdata - binary image data (0==while & 1==black)
1940 iw - width (in pixels) of image
1941 ih - height (in pixels) of image
1942 imap - matrix of ridge flow directions
1943 nmap - IMAP augmented with blocks of HIGH-CURVATURE and
1944 blocks which have no neighboring valid directions.
1945 blk_x - x-block coord to be rescanned
1946 blk_y - y-block coord to be rescanned
1947 mw - width (in blocks) of IMAP and NMAP matrices.
1948 mh - height (in blocks) of IMAP and NMAP matrices.
1949 scan_x - x-pixel coord of origin of image region
1950 scan_y - y-pixel coord of origin of image region
1951 scan_w - width (in pixels) of image region
1952 scan_h - height (in pixels) of image region
1953 lfsparms - parameters and thresholds for controlling LFS
1954 Output:
1955 minutiae - points to a list of detected minutia structures
1956 Return Code:
1957 Zero - successful completion
1958 Negative - system error
1959 **************************************************************************/
rescan_partial_horizontally(const int nbr_dir,MINUTIAE * minutiae,unsigned char * bdata,const int iw,const int ih,const int * imap,const int * nmap,const int blk_x,const int blk_y,const int mw,const int mh,const int scan_x,const int scan_y,const int scan_w,const int scan_h,const LFSPARMS * lfsparms)1960 int rescan_partial_horizontally(const int nbr_dir, MINUTIAE *minutiae,
1961 unsigned char *bdata, const int iw, const int ih,
1962 const int *imap, const int *nmap,
1963 const int blk_x, const int blk_y,
1964 const int mw, const int mh,
1965 const int scan_x, const int scan_y,
1966 const int scan_w, const int scan_h,
1967 const LFSPARMS *lfsparms)
1968 {
1969 int nblk_i, blk_i;
1970 int rescan_dir;
1971 int rescan_x, rescan_y, rescan_w, rescan_h;
1972 int ret;
1973
1974 /* Neighbor will either be NORTH, SOUTH, EAST, OR WEST. */
1975 ret = get_nbr_block_index(&nblk_i, nbr_dir, blk_x, blk_y, mw, mh);
1976 /* Will return: */
1977 /* 1. Neighbor index found == FOUND */
1978 /* 2. Neighbor not found == NOT_FOUND */
1979 /* 3. System error < 0 */
1980
1981 /* If system error ... */
1982 if(ret < 0)
1983 /* Return the error code. */
1984 return(ret);
1985
1986 /* If neighbor not found ... */
1987 if(ret == NOT_FOUND)
1988 /* Nothing to do, so return normally. */
1989 return(0);
1990
1991 /* Otherwise, neighboring block found ... */
1992
1993 /* If neighbor block is VALID... */
1994 if(imap[nblk_i] != INVALID_DIR){
1995
1996 /* Compute block index from current (not neighbor) block coordinates. */
1997 blk_i = (blk_y*mw)+blk_x;
1998
1999 /* Select feature scan direction based on neighbor IMAP. */
2000 rescan_dir = choose_scan_direction(imap[nblk_i],
2001 lfsparms->num_directions);
2002 /* If new scan direction is HORIZONTAL... */
2003 if(rescan_dir == SCAN_HORIZONTAL){
2004 /* Adjust scan_x, scan_y, scan_w, scan_h for rescan. */
2005 if((ret = adjust_horizontal_rescan(nbr_dir, &rescan_x, &rescan_y,
2006 &rescan_w, &rescan_h,
2007 scan_x, scan_y, scan_w, scan_h, lfsparms->blocksize)))
2008 /* Return system error code. */
2009 return(ret);
2010 /* Rescan specified region in block vertically. */
2011 /* Pass IMAP direction for the block, NOT its neighbor. */
2012 if((ret = scan4minutiae_horizontally(minutiae, bdata, iw, ih,
2013 imap[blk_i], nmap[blk_i],
2014 rescan_x, rescan_y, rescan_w, rescan_h, lfsparms)))
2015 /* Return code may be: */
2016 /* 1. ret<0 (implying system error) */
2017 return(ret);
2018 } /* Otherwise, block has already been scanned vertically. */
2019 } /* Otherwise, neighbor has INVALID IMAP, so ignore rescan. */
2020
2021 /* Return normally. */
2022 return(0);
2023 }
2024
2025 /*************************************************************************
2026 **************************************************************************
2027 #cat: rescan_partial_vertically - Rescans a portion of a block of binary
2028 #cat: image data vertically based on the IMAP and NMAP values
2029 #cat: of a specified neighboring block.
2030
2031 Input:
2032 nbr_dir - specifies which block neighbor {NORTH, SOUTH, EAST, WEST}
2033 bdata - binary image data (0==while & 1==black)
2034 iw - width (in pixels) of image
2035 ih - height (in pixels) of image
2036 imap - matrix of ridge flow directions
2037 nmap - IMAP augmented with blocks of HIGH-CURVATURE and
2038 blocks which have no neighboring valid directions.
2039 blk_x - x-block coord to be rescanned
2040 blk_y - y-block coord to be rescanned
2041 mw - width (in blocks) of IMAP and NMAP matrices.
2042 mh - height (in blocks) of IMAP and NMAP matrices.
2043 scan_x - x-pixel coord of origin of image region
2044 scan_y - y-pixel coord of origin of image region
2045 scan_w - width (in pixels) of image region
2046 scan_h - height (in pixels) of image region
2047 lfsparms - parameters and thresholds for controlling LFS
2048 Output:
2049 minutiae - points to a list of detected minutia structures
2050 Return Code:
2051 Zero - successful completion
2052 Negative - system error
2053 **************************************************************************/
rescan_partial_vertically(const int nbr_dir,MINUTIAE * minutiae,unsigned char * bdata,const int iw,const int ih,const int * imap,const int * nmap,const int blk_x,const int blk_y,const int mw,const int mh,const int scan_x,const int scan_y,const int scan_w,const int scan_h,const LFSPARMS * lfsparms)2054 int rescan_partial_vertically(const int nbr_dir, MINUTIAE *minutiae,
2055 unsigned char *bdata, const int iw, const int ih,
2056 const int *imap, const int *nmap,
2057 const int blk_x, const int blk_y,
2058 const int mw, const int mh,
2059 const int scan_x, const int scan_y,
2060 const int scan_w, const int scan_h,
2061 const LFSPARMS *lfsparms)
2062 {
2063 int nblk_i, blk_i;
2064 int rescan_dir;
2065 int rescan_x, rescan_y, rescan_w, rescan_h;
2066 int ret;
2067
2068 /* Neighbor will either be NORTH, SOUTH, EAST, OR WEST. */
2069 ret = get_nbr_block_index(&nblk_i, nbr_dir, blk_x, blk_y, mw, mh);
2070 /* Will return: */
2071 /* 1. Neighbor index found == FOUND */
2072 /* 2. Neighbor not found == NOT_FOUND */
2073 /* 3. System error < 0 */
2074
2075 /* If system error ... */
2076 if(ret < 0)
2077 /* Return the error code. */
2078 return(ret);
2079
2080 /* If neighbor not found ... */
2081 if(ret == NOT_FOUND)
2082 /* Nothing to do, so return normally. */
2083 return(0);
2084
2085 /* Otherwise, neighboring block found ... */
2086
2087 /* If neighbor block is VALID... */
2088 if(imap[nblk_i] != INVALID_DIR){
2089
2090 /* Compute block index from current (not neighbor) block coordinates. */
2091 blk_i = (blk_y*mw)+blk_x;
2092
2093 /* Select feature scan direction based on neighbor IMAP. */
2094 rescan_dir = choose_scan_direction(imap[nblk_i],
2095 lfsparms->num_directions);
2096 /* If new scan direction is VERTICAL... */
2097 if(rescan_dir == SCAN_VERTICAL){
2098 /* Adjust scan_x, scan_y, scan_w, scan_h for rescan. */
2099 if((ret = adjust_vertical_rescan(nbr_dir, &rescan_x, &rescan_y,
2100 &rescan_w, &rescan_h,
2101 scan_x, scan_y, scan_w, scan_h, lfsparms->blocksize)))
2102 /* Return system error code. */
2103 return(ret);
2104 /* Rescan specified region in block vertically. */
2105 /* Pass IMAP direction for the block, NOT its neighbor. */
2106 if((ret = scan4minutiae_vertically(minutiae, bdata, iw, ih,
2107 imap[blk_i], nmap[blk_i],
2108 rescan_x, rescan_y, rescan_w, rescan_h, lfsparms)))
2109 /* Return code may be: */
2110 /* 1. ret<0 (implying system error) */
2111 return(ret);
2112 } /* Otherwise, block has already been scanned horizontally. */
2113 } /* Otherwise, neighbor has INVALID IMAP, so ignore rescan. */
2114
2115 /* Return normally. */
2116 return(0);
2117 }
2118
2119 /*************************************************************************
2120 **************************************************************************
2121 #cat: get_nbr_block_index - Determines the block index (if one exists)
2122 #cat: for a specified neighbor of a block in the image.
2123
2124 Input:
2125 nbr_dir - specifies which block neighbor {NORTH, SOUTH, EAST, WEST}
2126 blk_x - x-block coord to find neighbor of
2127 blk_y - y-block coord to find neighbor of
2128 mw - width (in blocks) of IMAP and NMAP matrices.
2129 mh - height (in blocks) of IMAP and NMAP matrices.
2130 Output:
2131 oblk_i - points to neighbor's block index
2132 Return Code:
2133 NOT_FOUND - neighbor index does not exist
2134 FOUND - neighbor index exists and returned
2135 Negative - system error
2136 **************************************************************************/
get_nbr_block_index(int * oblk_i,const int nbr_dir,const int blk_x,const int blk_y,const int mw,const int mh)2137 int get_nbr_block_index(int *oblk_i, const int nbr_dir,
2138 const int blk_x, const int blk_y, const int mw, const int mh)
2139 {
2140 int nx, ny, ni;
2141
2142 switch(nbr_dir){
2143 case NORTH:
2144 /* If neighbor doesn't exist above... */
2145 if((ny = blk_y-1) < 0)
2146 /* Done, so return normally. */
2147 return(NOT_FOUND);
2148 /* Get neighbor's block index. */
2149 ni = (ny*mw)+blk_x;
2150 break;
2151 case EAST:
2152 /* If neighbor doesn't exist to the right... */
2153 if((nx = blk_x+1) >= mw)
2154 /* Done, so return normally. */
2155 return(NOT_FOUND);
2156 /* Get neighbor's block index. */
2157 ni = (blk_y*mw)+nx;
2158 break;
2159 case SOUTH:
2160 /* If neighbor doesn't exist below... */
2161 if((ny = blk_y+1) >= mh)
2162 /* Return normally. */
2163 return(NOT_FOUND);
2164 /* Get neighbor's block index. */
2165 ni = (ny*mw)+blk_x;
2166 break;
2167 case WEST:
2168 /* If neighbor doesn't exist to the left... */
2169 if((nx = blk_x-1) < 0)
2170 /* Return normally. */
2171 return(NOT_FOUND);
2172 /* Get neighbor's block index. */
2173 ni = (blk_y*mw)+nx;
2174 break;
2175 default:
2176 fprintf(stderr,
2177 "ERROR : get_nbr_block_index : illegal neighbor direction\n");
2178 return(-200);
2179 }
2180
2181 /* Assign output pointer. */
2182 *oblk_i = ni;
2183
2184 /* Return neighbor FOUND. */
2185 return(FOUND);
2186 }
2187
2188 /*************************************************************************
2189 **************************************************************************
2190 #cat: adjust_horizontal_rescan - Determines the portion of an image block to
2191 #cat: be rescanned horizontally based on a specified neighbor.
2192
2193 Input:
2194 nbr_dir - specifies which block neighbor {NORTH, SOUTH, EAST, WEST}
2195 scan_x - x-pixel coord of origin of image region
2196 scan_y - y-pixel coord of origin of image region
2197 scan_w - width (in pixels) of image region
2198 scan_h - height (in pixels) of image region
2199 blocksize - dimension of image blocks (in pixels)
2200 Output:
2201 rescan_x - x-pixel coord of origin of region to be rescanned
2202 rescan_y - y-pixel coord of origin of region to be rescanned
2203 rescan_w - width (in pixels) of region to be rescanned
2204 rescan_h - height (in pixels) of region to be rescanned
2205 Return Code:
2206 Zero - successful completion
2207 Negative - system error
2208 **************************************************************************/
adjust_horizontal_rescan(const int nbr_dir,int * rescan_x,int * rescan_y,int * rescan_w,int * rescan_h,const int scan_x,const int scan_y,const int scan_w,const int scan_h,const int blocksize)2209 int adjust_horizontal_rescan(const int nbr_dir, int *rescan_x, int *rescan_y,
2210 int *rescan_w, int *rescan_h, const int scan_x, const int scan_y,
2211 const int scan_w, const int scan_h, const int blocksize)
2212 {
2213 int half_blocksize, qtr_blocksize;
2214
2215 /* Compute half of blocksize. */
2216 half_blocksize = blocksize>>1;
2217 /* Compute quarter of blocksize. */
2218 qtr_blocksize = blocksize>>2;
2219
2220 /* Neighbor will either be NORTH, SOUTH, EAST, OR WEST. */
2221 switch(nbr_dir){
2222 case NORTH:
2223 /*
2224 *************************
2225 * RESCAN NORTH *
2226 * AREA *
2227 *************************
2228 | |
2229 | |
2230 | |
2231 | |
2232 | |
2233 | |
2234 -------------------------
2235 */
2236 /* Rescan origin stays the same. */
2237 *rescan_x = scan_x;
2238 *rescan_y = scan_y;
2239 /* Rescan width stays the same. */
2240 *rescan_w = scan_w;
2241 /* Rescan height is reduced to "qtr_blocksize" */
2242 /* if scan_h is larger. */
2243 *rescan_h = min(qtr_blocksize, scan_h);
2244 break;
2245 case EAST:
2246 /*
2247 ------------*************
2248 | * *
2249 | * *
2250 | * E R *
2251 | * A E *
2252 | * S S *
2253 | * T C *
2254 | * A *
2255 | * N *
2256 | * *
2257 | * *
2258 ------------*************
2259 */
2260 /* Rescan x-orign is set to half_blocksize from right edge of */
2261 /* block if scan width is larger. */
2262 *rescan_x = max(scan_x+scan_w-half_blocksize, scan_x);
2263 /* Rescan y-origin stays the same. */
2264 *rescan_y = scan_y;
2265 /* Rescan width is reduced to "half_blocksize" */
2266 /* if scan width is larger. */
2267 *rescan_w = min(half_blocksize, scan_w);
2268 /* Rescan height stays the same. */
2269 *rescan_h = scan_h;
2270 break;
2271 case SOUTH:
2272 /*
2273 -------------------------
2274 | |
2275 | |
2276 | |
2277 | |
2278 | |
2279 | |
2280 *************************
2281 * RESCAN SOUTH *
2282 * AREA *
2283 *************************
2284 */
2285 /* Rescan x-origin stays the same. */
2286 *rescan_x = scan_x;
2287 /* Rescan y-orign is set to qtr_blocksize from bottom edge of */
2288 /* block if scan height is larger. */
2289 *rescan_y = max(scan_y+scan_h-qtr_blocksize, scan_y);
2290 /* Rescan width stays the same. */
2291 *rescan_w = scan_w;
2292 /* Rescan height is reduced to "qtr_blocksize" */
2293 /* if scan height is larger. */
2294 *rescan_h = min(qtr_blocksize, scan_h);
2295 break;
2296 case WEST:
2297 /*
2298 *************------------
2299 * * |
2300 * * |
2301 * W R * |
2302 * E E * |
2303 * S S * |
2304 * T C * |
2305 * A * |
2306 * N * |
2307 * * |
2308 * * |
2309 *************------------
2310 */
2311 /* Rescan origin stays the same. */
2312 *rescan_x = scan_x;
2313 *rescan_y = scan_y;
2314 /* Rescan width is reduced to "half_blocksize" */
2315 /* if scan width is larger. */
2316 *rescan_w = min(half_blocksize, scan_w);
2317 /* Rescan height stays the same. */
2318 *rescan_h = scan_h;
2319 break;
2320 default:
2321 fprintf(stderr,
2322 "ERROR : adjust_horizontal_rescan : illegal neighbor direction\n");
2323 return(-210);
2324 }
2325
2326 /* Return normally. */
2327 return(0);
2328 }
2329
2330 /*************************************************************************
2331 **************************************************************************
2332 #cat: adjust_vertical_rescan - Determines the portion of an image block to
2333 #cat: be rescanned vertically based on a specified neighbor.
2334
2335 Input:
2336 nbr_dir - specifies which block neighbor {NORTH, SOUTH, EAST, WEST}
2337 scan_x - x-pixel coord of origin of image region
2338 scan_y - y-pixel coord of origin of image region
2339 scan_w - width (in pixels) of image region
2340 scan_h - height (in pixels) of image region
2341 blocksize - dimension of image blocks (in pixels)
2342 Output:
2343 rescan_x - x-pixel coord of origin of region to be rescanned
2344 rescan_y - y-pixel coord of origin of region to be rescanned
2345 rescan_w - width (in pixels) of region to be rescanned
2346 rescan_h - height (in pixels) of region to be rescanned
2347 Return Code:
2348 Zero - successful completion
2349 Negative - system error
2350 **************************************************************************/
adjust_vertical_rescan(const int nbr_dir,int * rescan_x,int * rescan_y,int * rescan_w,int * rescan_h,const int scan_x,const int scan_y,const int scan_w,const int scan_h,const int blocksize)2351 int adjust_vertical_rescan(const int nbr_dir, int *rescan_x, int *rescan_y,
2352 int *rescan_w, int *rescan_h, const int scan_x, const int scan_y,
2353 const int scan_w, const int scan_h, const int blocksize)
2354 {
2355 int half_blocksize, qtr_blocksize;
2356
2357 /* Compute half of blocksize. */
2358 half_blocksize = blocksize>>1;
2359 /* Compute quarter of blocksize. */
2360 qtr_blocksize = blocksize>>2;
2361
2362 /* Neighbor will either be NORTH, SOUTH, EAST, OR WEST. */
2363 switch(nbr_dir){
2364 case NORTH:
2365 /*
2366 *************************
2367 * *
2368 * RESCAN NORTH *
2369 * AREA *
2370 * *
2371 *************************
2372 | |
2373 | |
2374 | |
2375 | |
2376 | |
2377 -------------------------
2378 */
2379 /* Rescan origin stays the same. */
2380 *rescan_x = scan_x;
2381 *rescan_y = scan_y;
2382 /* Rescan width stays the same. */
2383 *rescan_w = scan_w;
2384 /* Rescan height is reduced to "half_blocksize" */
2385 /* if scan_h is larger. */
2386 *rescan_h = min(half_blocksize, scan_h);
2387 break;
2388 case EAST:
2389 /*
2390 ------------------*******
2391 | * *
2392 | * *
2393 | * E R *
2394 | * A E *
2395 | * S S *
2396 | * T C *
2397 | * A *
2398 | * N *
2399 | * *
2400 | * *
2401 ------------------*******
2402 */
2403 /* Rescan x-orign is set to qtr_blocksize from right edge of */
2404 /* block if scan width is larger. */
2405 *rescan_x = max(scan_x+scan_w-qtr_blocksize, scan_x);
2406 /* Rescan y-origin stays the same. */
2407 *rescan_y = scan_y;
2408 /* Rescan width is reduced to "qtr_blocksize" */
2409 /* if scan width is larger. */
2410 *rescan_w = min(qtr_blocksize, scan_w);
2411 /* Rescan height stays the same. */
2412 *rescan_h = scan_h;
2413 break;
2414 case SOUTH:
2415 /*
2416 -------------------------
2417 | |
2418 | |
2419 | |
2420 | |
2421 | |
2422 *************************
2423 * *
2424 * RESCAN SOUTH *
2425 * AREA *
2426 * *
2427 *************************
2428 */
2429 /* Rescan x-origin stays the same. */
2430 *rescan_x = scan_x;
2431 /* Rescan y-orign is set to half_blocksize from bottom edge of */
2432 /* block if scan height is larger. */
2433 *rescan_y = max(scan_y+scan_h-half_blocksize, scan_y);
2434 /* Rescan width stays the same. */
2435 *rescan_w = scan_w;
2436 /* Rescan height is reduced to "half_blocksize" */
2437 /* if scan height is larger. */
2438 *rescan_h = min(half_blocksize, scan_h);
2439 break;
2440 case WEST:
2441 /*
2442 *******------------------
2443 * * |
2444 * * |
2445 * W R * |
2446 * E E * |
2447 * S S * |
2448 * T C * |
2449 * A * |
2450 * N * |
2451 * * |
2452 * * |
2453 *******------------------
2454 */
2455 /* Rescan origin stays the same. */
2456 *rescan_x = scan_x;
2457 *rescan_y = scan_y;
2458 /* Rescan width is reduced to "qtr_blocksize" */
2459 /* if scan width is larger. */
2460 *rescan_w = min(qtr_blocksize, scan_w);
2461 /* Rescan height stays the same. */
2462 *rescan_h = scan_h;
2463 break;
2464 default:
2465 fprintf(stderr,
2466 "ERROR : adjust_vertical_rescan : illegal neighbor direction\n");
2467 return(-220);
2468 }
2469
2470 /* Return normally. */
2471 return(0);
2472 }
2473
2474 /*************************************************************************
2475 **************************************************************************
2476 #cat: process_horizontal_scan_minutia - Takes a minutia point that was
2477 #cat: detected via the horizontal scan process and
2478 #cat: adjusts its location (if necessary), determines its
2479 #cat: direction, and (if it is not already in the minutiae
2480 #cat: list) adds it to the list. These minutia are by nature
2481 #cat: vertical in orientation (orthogonal to the scan).
2482
2483 Input:
2484 cx - x-pixel coord where 3rd pattern pair of mintuia was detected
2485 cy - y-pixel coord where 3rd pattern pair of mintuia was detected
2486 y2 - y-pixel coord where 2nd pattern pair of mintuia was detected
2487 feature_id - type of minutia (ex. index into feature_patterns[] list)
2488 bdata - binary image data (0==while & 1==black)
2489 iw - width (in pixels) of image
2490 ih - height (in pixels) of image
2491 imapval - IMAP value associated with this image region
2492 nmapval - NMAP value associated with this image region
2493 lfsparms - parameters and thresholds for controlling LFS
2494 Output:
2495 minutiae - points to a list of detected minutia structures
2496 Return Code:
2497 Zero - successful completion
2498 IGNORE - minutia is to be ignored
2499 Negative - system error
2500 **************************************************************************/
process_horizontal_scan_minutia(MINUTIAE * minutiae,const int cx,const int cy,const int x2,const int feature_id,unsigned char * bdata,const int iw,const int ih,const int imapval,const int nmapval,const LFSPARMS * lfsparms)2501 int process_horizontal_scan_minutia(MINUTIAE *minutiae,
2502 const int cx, const int cy,
2503 const int x2, const int feature_id,
2504 unsigned char *bdata, const int iw, const int ih,
2505 const int imapval, const int nmapval,
2506 const LFSPARMS *lfsparms)
2507 {
2508 MINUTIA *minutia;
2509 int x_loc, y_loc;
2510 int x_edge, y_edge;
2511 int idir, ret;
2512
2513 /* Set x location of minutia point to be half way between */
2514 /* first position of second feature pair and position of */
2515 /* third feature pair. */
2516 x_loc = (cx + x2)>>1;
2517
2518 /* Set same x location to neighboring edge pixel. */
2519 x_edge = x_loc;
2520
2521 /* Feature location should always point to either ending */
2522 /* of ridge or (for bifurcations) ending of valley. */
2523 /* So, if detected feature is APPEARING... */
2524 if(g_feature_patterns[feature_id].appearing){
2525 /* Set y location to second scan row. */
2526 y_loc = cy+1;
2527 /* Set y location of neighboring edge pixel to the first scan row. */
2528 y_edge = cy;
2529 }
2530 /* Otherwise, feature is DISAPPEARING... */
2531 else{
2532 /* Set y location to first scan row. */
2533 y_loc = cy;
2534 /* Set y location of neighboring edge pixel to the second scan row. */
2535 y_edge = cy+1;
2536 }
2537
2538 /* If current minutia is in a high-curvature block... */
2539 if(nmapval == HIGH_CURVATURE){
2540 /* Adjust location and direction locally. */
2541 if((ret = adjust_high_curvature_minutia(&idir, &x_loc, &y_loc,
2542 &x_edge, &y_edge, x_loc, y_loc, x_edge, y_edge,
2543 bdata, iw, ih, minutiae, lfsparms))){
2544 /* Could be a system error or IGNORE minutia. */
2545 return(ret);
2546 }
2547 /* Otherwise, we have our high-curvature minutia attributes. */
2548 }
2549 /* Otherwise, minutia is in fairly low-curvature block... */
2550 else{
2551 /* Get minutia direction based on current IMAP value. */
2552 idir = get_low_curvature_direction(SCAN_HORIZONTAL,
2553 g_feature_patterns[feature_id].appearing,
2554 imapval, lfsparms->num_directions);
2555 }
2556
2557 /* Create a minutia object based on derived attributes. */
2558 if((ret = create_minutia(&minutia, x_loc, y_loc, x_edge, y_edge, idir,
2559 DEFAULT_RELIABILITY,
2560 g_feature_patterns[feature_id].type,
2561 g_feature_patterns[feature_id].appearing, feature_id)))
2562 /* Return system error. */
2563 return(ret);
2564
2565 /* Update the minutiae list with potential new minutia. */
2566 ret = update_minutiae(minutiae, minutia, bdata, iw, ih, lfsparms);
2567
2568 /* If minuitia IGNORED and not added to the minutia list ... */
2569 if(ret == IGNORE)
2570 /* Deallocate the minutia. */
2571 free_minutia(minutia);
2572
2573 /* Otherwise, return normally. */
2574 return(0);
2575 }
2576
2577 /*************************************************************************
2578 **************************************************************************
2579 #cat: process_horizontal_scan_minutia_V2 - Takes a minutia point that was
2580 #cat: detected via the horizontal scan process and
2581 #cat: adjusts its location (if necessary), determines its
2582 #cat: direction, and (if it is not already in the minutiae
2583 #cat: list) adds it to the list. These minutia are by nature
2584 #cat: vertical in orientation (orthogonal to the scan).
2585
2586 Input:
2587 cx - x-pixel coord where 3rd pattern pair of mintuia was detected
2588 cy - y-pixel coord where 3rd pattern pair of mintuia was detected
2589 y2 - y-pixel coord where 2nd pattern pair of mintuia was detected
2590 feature_id - type of minutia (ex. index into feature_patterns[] list)
2591 bdata - binary image data (0==while & 1==black)
2592 iw - width (in pixels) of image
2593 ih - height (in pixels) of image
2594 pdirection_map - pixelized Direction Map
2595 plow_flow_map - pixelized Low Ridge Flow Map
2596 phigh_curve_map - pixelized High Curvature Map
2597 lfsparms - parameters and thresholds for controlling LFS
2598 Output:
2599 minutiae - points to a list of detected minutia structures
2600 Return Code:
2601 Zero - successful completion
2602 IGNORE - minutia is to be ignored
2603 Negative - system error
2604 **************************************************************************/
process_horizontal_scan_minutia_V2(MINUTIAE * minutiae,const int cx,const int cy,const int x2,const int feature_id,unsigned char * bdata,const int iw,const int ih,int * pdirection_map,int * plow_flow_map,int * phigh_curve_map,const LFSPARMS * lfsparms)2605 int process_horizontal_scan_minutia_V2(MINUTIAE *minutiae,
2606 const int cx, const int cy,
2607 const int x2, const int feature_id,
2608 unsigned char *bdata, const int iw, const int ih,
2609 int *pdirection_map, int *plow_flow_map, int *phigh_curve_map,
2610 const LFSPARMS *lfsparms)
2611 {
2612 MINUTIA *minutia;
2613 int x_loc, y_loc;
2614 int x_edge, y_edge;
2615 int idir, ret;
2616 int dmapval, fmapval, cmapval;
2617 double reliability;
2618
2619 /* Set x location of minutia point to be half way between */
2620 /* first position of second feature pair and position of */
2621 /* third feature pair. */
2622 x_loc = (cx + x2)>>1;
2623
2624 /* Set same x location to neighboring edge pixel. */
2625 x_edge = x_loc;
2626
2627 /* Feature location should always point to either ending */
2628 /* of ridge or (for bifurcations) ending of valley. */
2629 /* So, if detected feature is APPEARING... */
2630 if(g_feature_patterns[feature_id].appearing){
2631 /* Set y location to second scan row. */
2632 y_loc = cy+1;
2633 /* Set y location of neighboring edge pixel to the first scan row. */
2634 y_edge = cy;
2635 }
2636 /* Otherwise, feature is DISAPPEARING... */
2637 else{
2638 /* Set y location to first scan row. */
2639 y_loc = cy;
2640 /* Set y location of neighboring edge pixel to the second scan row. */
2641 y_edge = cy+1;
2642 }
2643
2644 dmapval = *(pdirection_map+(y_loc*iw)+x_loc);
2645 fmapval = *(plow_flow_map+(y_loc*iw)+x_loc);
2646 cmapval = *(phigh_curve_map+(y_loc*iw)+x_loc);
2647
2648 /* If the minutia point is in a block with INVALID direction ... */
2649 if(dmapval == INVALID_DIR)
2650 /* Then, IGNORE the point. */
2651 return(IGNORE);
2652
2653 /* If current minutia is in a HIGH CURVATURE block ... */
2654 if(cmapval){
2655 /* Adjust location and direction locally. */
2656 if((ret = adjust_high_curvature_minutia_V2(&idir, &x_loc, &y_loc,
2657 &x_edge, &y_edge, x_loc, y_loc, x_edge, y_edge,
2658 bdata, iw, ih, plow_flow_map, minutiae, lfsparms))){
2659 /* Could be a system error or IGNORE minutia. */
2660 return(ret);
2661 }
2662 /* Otherwise, we have our high-curvature minutia attributes. */
2663 }
2664 /* Otherwise, minutia is in fairly low-curvature block... */
2665 else{
2666 /* Get minutia direction based on current block's direction. */
2667 idir = get_low_curvature_direction(SCAN_HORIZONTAL,
2668 g_feature_patterns[feature_id].appearing, dmapval,
2669 lfsparms->num_directions);
2670 }
2671
2672 /* If current minutia is in a LOW RIDGE FLOW block ... */
2673 if(fmapval)
2674 reliability = MEDIUM_RELIABILITY;
2675 else
2676 /* Otherwise, minutia is in a block with reliable direction and */
2677 /* binarization. */
2678 reliability = HIGH_RELIABILITY;
2679
2680 /* Create a minutia object based on derived attributes. */
2681 if((ret = create_minutia(&minutia, x_loc, y_loc, x_edge, y_edge, idir,
2682 reliability,
2683 g_feature_patterns[feature_id].type,
2684 g_feature_patterns[feature_id].appearing, feature_id)))
2685 /* Return system error. */
2686 return(ret);
2687
2688 /* Update the minutiae list with potential new minutia. */
2689 ret = update_minutiae_V2(minutiae, minutia, SCAN_HORIZONTAL,
2690 dmapval, bdata, iw, ih, lfsparms);
2691
2692 /* If minuitia IGNORED and not added to the minutia list ... */
2693 if(ret == IGNORE)
2694 /* Deallocate the minutia. */
2695 free_minutia(minutia);
2696
2697 /* Otherwise, return normally. */
2698 return(0);
2699 }
2700
2701 /*************************************************************************
2702 **************************************************************************
2703 #cat: process_vertical_scan_minutia - Takes a minutia point that was
2704 #cat: detected in via the vertical scan process and
2705 #cat: adjusts its location (if necessary), determines its
2706 #cat: direction, and (if it is not already in the minutiae
2707 #cat: list) adds it to the list. These minutia are by nature
2708 #cat: horizontal in orientation (orthogonal to the scan).
2709
2710 Input:
2711 cx - x-pixel coord where 3rd pattern pair of mintuia was detected
2712 cy - y-pixel coord where 3rd pattern pair of mintuia was detected
2713 x2 - x-pixel coord where 2nd pattern pair of mintuia was detected
2714 feature_id - type of minutia (ex. index into feature_patterns[] list)
2715 bdata - binary image data (0==while & 1==black)
2716 iw - width (in pixels) of image
2717 ih - height (in pixels) of image
2718 imapval - IMAP value associated with this image region
2719 nmapval - NMAP value associated with this image region
2720 lfsparms - parameters and thresholds for controlling LFS
2721 Output:
2722 minutiae - points to a list of detected minutia structures
2723 Return Code:
2724 Zero - successful completion
2725 IGNORE - minutia is to be ignored
2726 Negative - system error
2727 **************************************************************************/
process_vertical_scan_minutia(MINUTIAE * minutiae,const int cx,const int cy,const int y2,const int feature_id,unsigned char * bdata,const int iw,const int ih,const int imapval,const int nmapval,const LFSPARMS * lfsparms)2728 int process_vertical_scan_minutia(MINUTIAE *minutiae,
2729 const int cx, const int cy,
2730 const int y2, const int feature_id,
2731 unsigned char *bdata, const int iw, const int ih,
2732 const int imapval, const int nmapval,
2733 const LFSPARMS *lfsparms)
2734 {
2735 MINUTIA *minutia;
2736 int x_loc, y_loc;
2737 int x_edge, y_edge;
2738 int idir, ret;
2739
2740 /* Feature location should always point to either ending */
2741 /* of ridge or (for bifurcations) ending of valley. */
2742 /* So, if detected feature is APPEARING... */
2743 if(g_feature_patterns[feature_id].appearing){
2744 /* Set x location to second scan column. */
2745 x_loc = cx+1;
2746 /* Set x location of neighboring edge pixel to the first scan column. */
2747 x_edge = cx;
2748 }
2749 /* Otherwise, feature is DISAPPEARING... */
2750 else{
2751 /* Set x location to first scan column. */
2752 x_loc = cx;
2753 /* Set x location of neighboring edge pixel to the second scan column. */
2754 x_edge = cx+1;
2755 }
2756
2757 /* Set y location of minutia point to be half way between */
2758 /* first position of second feature pair and position of */
2759 /* third feature pair. */
2760 y_loc = (cy + y2)>>1;
2761 /* Set same y location to neighboring edge pixel. */
2762 y_edge = y_loc;
2763
2764 /* If current minutia is in a high-curvature block... */
2765 if(nmapval == HIGH_CURVATURE){
2766 /* Adjust location and direction locally. */
2767 if((ret = adjust_high_curvature_minutia(&idir, &x_loc, &y_loc,
2768 &x_edge, &y_edge, x_loc, y_loc, x_edge, y_edge,
2769 bdata, iw, ih, minutiae, lfsparms))){
2770 /* Could be a system error or IGNORE minutia. */
2771 return(ret);
2772 }
2773 /* Otherwise, we have our high-curvature minutia attributes. */
2774 }
2775 /* Otherwise, minutia is in fairly low-curvature block... */
2776 else{
2777 /* Get minutia direction based on current IMAP value. */
2778 idir = get_low_curvature_direction(SCAN_VERTICAL,
2779 g_feature_patterns[feature_id].appearing,
2780 imapval, lfsparms->num_directions);
2781 }
2782
2783 /* Create a minutia object based on derived attributes. */
2784 if((ret = create_minutia(&minutia, x_loc, y_loc, x_edge, y_edge, idir,
2785 DEFAULT_RELIABILITY,
2786 g_feature_patterns[feature_id].type,
2787 g_feature_patterns[feature_id].appearing, feature_id)))
2788 /* Return system error. */
2789 return(ret);
2790
2791 /* Update the minutiae list with potential new minutia. */
2792 ret = update_minutiae(minutiae, minutia, bdata, iw, ih, lfsparms);
2793
2794 /* If minuitia IGNORED and not added to the minutia list ... */
2795 if(ret == IGNORE)
2796 /* Deallocate the minutia. */
2797 free_minutia(minutia);
2798
2799 /* Otherwise, return normally. */
2800 return(0);
2801 }
2802
2803 /*************************************************************************
2804 **************************************************************************
2805 #cat: process_vertical_scan_minutia_V2 - Takes a minutia point that was
2806 #cat: detected in via the vertical scan process and
2807 #cat: adjusts its location (if necessary), determines its
2808 #cat: direction, and (if it is not already in the minutiae
2809 #cat: list) adds it to the list. These minutia are by nature
2810 #cat: horizontal in orientation (orthogonal to the scan).
2811
2812 Input:
2813 cx - x-pixel coord where 3rd pattern pair of mintuia was detected
2814 cy - y-pixel coord where 3rd pattern pair of mintuia was detected
2815 x2 - x-pixel coord where 2nd pattern pair of mintuia was detected
2816 feature_id - type of minutia (ex. index into feature_patterns[] list)
2817 bdata - binary image data (0==while & 1==black)
2818 iw - width (in pixels) of image
2819 ih - height (in pixels) of image
2820 pdirection_map - pixelized Direction Map
2821 plow_flow_map - pixelized Low Ridge Flow Map
2822 phigh_curve_map - pixelized High Curvature Map
2823 lfsparms - parameters and thresholds for controlling LFS
2824 Output:
2825 minutiae - points to a list of detected minutia structures
2826 Return Code:
2827 Zero - successful completion
2828 IGNORE - minutia is to be ignored
2829 Negative - system error
2830 **************************************************************************/
process_vertical_scan_minutia_V2(MINUTIAE * minutiae,const int cx,const int cy,const int y2,const int feature_id,unsigned char * bdata,const int iw,const int ih,int * pdirection_map,int * plow_flow_map,int * phigh_curve_map,const LFSPARMS * lfsparms)2831 int process_vertical_scan_minutia_V2(MINUTIAE *minutiae,
2832 const int cx, const int cy,
2833 const int y2, const int feature_id,
2834 unsigned char *bdata, const int iw, const int ih,
2835 int *pdirection_map, int *plow_flow_map, int *phigh_curve_map,
2836 const LFSPARMS *lfsparms)
2837 {
2838 MINUTIA *minutia;
2839 int x_loc, y_loc;
2840 int x_edge, y_edge;
2841 int idir, ret;
2842 int dmapval, fmapval, cmapval;
2843 double reliability;
2844
2845 /* Feature location should always point to either ending */
2846 /* of ridge or (for bifurcations) ending of valley. */
2847 /* So, if detected feature is APPEARING... */
2848 if(g_feature_patterns[feature_id].appearing){
2849 /* Set x location to second scan column. */
2850 x_loc = cx+1;
2851 /* Set x location of neighboring edge pixel to the first scan column. */
2852 x_edge = cx;
2853 }
2854 /* Otherwise, feature is DISAPPEARING... */
2855 else{
2856 /* Set x location to first scan column. */
2857 x_loc = cx;
2858 /* Set x location of neighboring edge pixel to the second scan column. */
2859 x_edge = cx+1;
2860 }
2861
2862 /* Set y location of minutia point to be half way between */
2863 /* first position of second feature pair and position of */
2864 /* third feature pair. */
2865 y_loc = (cy + y2)>>1;
2866 /* Set same y location to neighboring edge pixel. */
2867 y_edge = y_loc;
2868
2869 dmapval = *(pdirection_map+(y_loc*iw)+x_loc);
2870 fmapval = *(plow_flow_map+(y_loc*iw)+x_loc);
2871 cmapval = *(phigh_curve_map+(y_loc*iw)+x_loc);
2872
2873 /* If the minutia point is in a block with INVALID direction ... */
2874 if(dmapval == INVALID_DIR)
2875 /* Then, IGNORE the point. */
2876 return(IGNORE);
2877
2878 /* If current minutia is in a HIGH CURVATURE block... */
2879 if(cmapval){
2880 /* Adjust location and direction locally. */
2881 if((ret = adjust_high_curvature_minutia_V2(&idir, &x_loc, &y_loc,
2882 &x_edge, &y_edge, x_loc, y_loc, x_edge, y_edge,
2883 bdata, iw, ih, plow_flow_map, minutiae, lfsparms))){
2884 /* Could be a system error or IGNORE minutia. */
2885 return(ret);
2886 }
2887 /* Otherwise, we have our high-curvature minutia attributes. */
2888 }
2889 /* Otherwise, minutia is in fairly low-curvature block... */
2890 else{
2891 /* Get minutia direction based on current block's direction. */
2892 idir = get_low_curvature_direction(SCAN_VERTICAL,
2893 g_feature_patterns[feature_id].appearing, dmapval,
2894 lfsparms->num_directions);
2895 }
2896
2897 /* If current minutia is in a LOW RIDGE FLOW block ... */
2898 if(fmapval)
2899 reliability = MEDIUM_RELIABILITY;
2900 else
2901 /* Otherwise, minutia is in a block with reliable direction and */
2902 /* binarization. */
2903 reliability = HIGH_RELIABILITY;
2904
2905 /* Create a minutia object based on derived attributes. */
2906 if((ret = create_minutia(&minutia, x_loc, y_loc, x_edge, y_edge, idir,
2907 reliability,
2908 g_feature_patterns[feature_id].type,
2909 g_feature_patterns[feature_id].appearing, feature_id)))
2910 /* Return system error. */
2911 return(ret);
2912
2913 /* Update the minutiae list with potential new minutia. */
2914 ret = update_minutiae_V2(minutiae, minutia, SCAN_VERTICAL,
2915 dmapval, bdata, iw, ih, lfsparms);
2916
2917 /* If minuitia IGNORED and not added to the minutia list ... */
2918 if(ret == IGNORE)
2919 /* Deallocate the minutia. */
2920 free_minutia(minutia);
2921
2922 /* Otherwise, return normally. */
2923 return(0);
2924 }
2925
2926 /*************************************************************************
2927 **************************************************************************
2928 #cat: adjust_high_curvature_minutia - Takes an initial minutia point detected
2929 #cat: in a high-curvature area and adjusts its location and
2930 #cat: direction. First, it walks and extracts the contour
2931 #cat: of the detected feature looking for and processing any loop
2932 #cat: discovered along the way. Once the contour is extracted,
2933 #cat: the point of highest-curvature is determined and used to
2934 #cat: adjust the location of the minutia point. The angle of
2935 #cat: the line perpendicular to the tangent on the high-curvature
2936 #cat: contour at the minutia point is used as the mintutia's
2937 #cat: direction.
2938
2939 Input:
2940 x_loc - starting x-pixel coord of feature (interior to feature)
2941 y_loc - starting y-pixel coord of feature (interior to feature)
2942 x_edge - x-pixel coord of corresponding edge pixel
2943 (exterior to feature)
2944 y_edge - y-pixel coord of corresponding edge pixel
2945 (exterior to feature)
2946 bdata - binary image data (0==while & 1==black)
2947 iw - width (in pixels) of image
2948 ih - height (in pixels) of image
2949 lfsparms - parameters and thresholds for controlling LFS
2950 Output:
2951 oidir - direction of adjusted minutia point
2952 ox_loc - adjusted x-pixel coord of feature
2953 oy_loc - adjusted y-pixel coord of feature
2954 ox_edge - adjusted x-pixel coord of corresponding edge pixel
2955 oy_edge - adjusted y-pixel coord of corresponding edge pixel
2956 minutiae - points to a list of detected minutia structures
2957 Return Code:
2958 Zero - minutia point processed successfully
2959 IGNORE - minutia point is to be ignored
2960 Negative - system error
2961 **************************************************************************/
adjust_high_curvature_minutia(int * oidir,int * ox_loc,int * oy_loc,int * ox_edge,int * oy_edge,const int x_loc,const int y_loc,const int x_edge,const int y_edge,unsigned char * bdata,const int iw,const int ih,MINUTIAE * minutiae,const LFSPARMS * lfsparms)2962 int adjust_high_curvature_minutia(int *oidir, int *ox_loc, int *oy_loc,
2963 int *ox_edge, int *oy_edge,
2964 const int x_loc, const int y_loc,
2965 const int x_edge, const int y_edge,
2966 unsigned char *bdata, const int iw, const int ih,
2967 MINUTIAE *minutiae, const LFSPARMS *lfsparms)
2968 {
2969 int ret;
2970 int *contour_x, *contour_y, *contour_ex, *contour_ey, ncontour;
2971 int min_i;
2972 double min_theta;
2973 int feature_pix;
2974 int mid_x, mid_y, mid_pix;
2975 int idir;
2976 int half_contour, angle_edge;
2977
2978 /* Set variable from parameter structure. */
2979 half_contour = lfsparms->high_curve_half_contour;
2980
2981 /* Set edge length for computing contour's angle of curvature */
2982 /* to one quarter of desired pixel length of entire contour. */
2983 /* Ex. If half_contour==14, then contour length==29=(2X14)+1 */
2984 /* and angle_edge==7=(14/2). */
2985 angle_edge = half_contour>>1;
2986
2987 /* Get the pixel value of current feature. */
2988 feature_pix = *(bdata + (y_loc * iw) + x_loc);
2989
2990 /* Extract feature's contour. */
2991 if((ret = get_high_curvature_contour(&contour_x, &contour_y,
2992 &contour_ex, &contour_ey, &ncontour, half_contour,
2993 x_loc, y_loc, x_edge, y_edge, bdata, iw, ih))){
2994 /* Returns with: */
2995 /* 1. Successful or empty contour == 0 */
2996 /* If contour is empty, then contour lists are not allocated. */
2997 /* 2. Contour forms loop == LOOP_FOUND */
2998 /* 3. Sysetm error < 0 */
2999
3000 /* If the contour forms a loop... */
3001 if(ret == LOOP_FOUND){
3002
3003 /* If the order of the contour is clockwise, then the loops's */
3004 /* contour pixels are outside the corresponding edge pixels. We */
3005 /* definitely do NOT want to fill based on the feature pixel in */
3006 /* this case, because it is OUTSIDE the loop. For now we will */
3007 /* ignore the loop and the minutia that triggered its tracing. */
3008 /* It is likely that other minutia on the loop will be */
3009 /* detected that create a contour on the "inside" of the loop. */
3010 /* There is another issue here that could be addressed ... */
3011 /* It seems that many/multiple minutia are often detected within */
3012 /* the same loop, which currently requires retracing the loop, */
3013 /* locating minutia on opposite ends of the major axis of the */
3014 /* loop, and then determining that the minutia have already been */
3015 /* entered into the minutiae list upon processing the very first */
3016 /* minutia detected in the loop. There is a lot of redundant */
3017 /* work being done here! */
3018 /* Is_loop_clockwise takes a default value to be returned if the */
3019 /* routine is unable to determine the direction of the contour. */
3020 /* In this case, we want to IGNORE the loop if we can't tell its */
3021 /* direction so that we do not inappropriately fill the loop, so */
3022 /* we are passing the default value TRUE. */
3023 if((ret = is_loop_clockwise(contour_x, contour_y, ncontour, TRUE))){
3024 /* Deallocate contour lists. */
3025 free_contour(contour_x, contour_y, contour_ex, contour_ey);
3026 /* If we had a system error... */
3027 if(ret < 0)
3028 /* Return the error code. */
3029 return(ret);
3030 /* Otherwise, loop is clockwise, so return IGNORE. */
3031 return(IGNORE);
3032 }
3033
3034 /* Otherwise, process the clockwise-ordered contour of the loop */
3035 /* as it may contain minutia. If no minutia found, then it is */
3036 /* filled in. */
3037 ret = process_loop(minutiae, contour_x, contour_y,
3038 contour_ex, contour_ey, ncontour,
3039 bdata, iw, ih, lfsparms);
3040 /* Returns with: */
3041 /* 1. Successful processing of loop == 0 */
3042 /* 2. System error < 0 */
3043
3044 /* Deallocate contour lists. */
3045 free_contour(contour_x, contour_y, contour_ex, contour_ey);
3046
3047 /* If loop processed successfully ... */
3048 if(ret == 0)
3049 /* Then either a minutia pair was extracted or the loop was */
3050 /* filled. Either way we want to IGNORE the minutia that */
3051 /* started the whole loop processing in the beginning. */
3052 return(IGNORE);
3053
3054 /* Otherwise, there was a system error. */
3055 /* Return the resulting code. */
3056 return(ret);
3057 }
3058
3059 /* Otherwise not a loop, so get_high_curvature_contour incurred */
3060 /* a system error. Return the error code. */
3061 return(ret);
3062 }
3063
3064 /* If contour is empty ... then contour lists were not allocated, so */
3065 /* simply return IGNORE. The contour comes back empty when there */
3066 /* were not a sufficient number of points found on the contour. */
3067 if(ncontour == 0)
3068 return(IGNORE);
3069
3070 /* Otherwise, there are contour points to process. */
3071
3072 /* Given the contour, determine the point of highest curvature */
3073 /* (ie. forming the minimum angle between contour walls). */
3074 if((ret = min_contour_theta(&min_i, &min_theta, angle_edge,
3075 contour_x, contour_y, ncontour))){
3076 /* Deallocate contour lists. */
3077 free_contour(contour_x, contour_y, contour_ex, contour_ey);
3078 /* Returns IGNORE or system error. Either way */
3079 /* free the contour and return the code. */
3080 return(ret);
3081 }
3082
3083 /* If the minimum theta found along the contour is too large... */
3084 if(min_theta >= lfsparms->max_high_curve_theta){
3085 /* Deallocate contour lists. */
3086 free_contour(contour_x, contour_y, contour_ex, contour_ey);
3087 /* Reject the high-curvature minutia, and return IGNORE. */
3088 return(IGNORE);
3089 }
3090
3091 /* Test to see if interior of curvature is OK. Compute midpoint */
3092 /* between left and right points symmetrically distant (angle_edge */
3093 /* pixels) from the contour's point of minimum theta. */
3094 mid_x = (contour_x[min_i-angle_edge] + contour_x[min_i+angle_edge])>>1;
3095 mid_y = (contour_y[min_i-angle_edge] + contour_y[min_i+angle_edge])>>1;
3096 mid_pix = *(bdata + (mid_y * iw) + mid_x);
3097 /* If the interior pixel value is not the same as the feature's... */
3098 if(mid_pix != feature_pix){
3099 /* Deallocate contour lists. */
3100 free_contour(contour_x, contour_y, contour_ex, contour_ey);
3101 /* Reject the high-curvature minutia and return IGNORE. */
3102 return(IGNORE);
3103 }
3104
3105 /* Compute new direction based on line connecting adjusted feature */
3106 /* location and the midpoint in the feature's interior. */
3107 idir = line2direction(contour_x[min_i], contour_y[min_i],
3108 mid_x, mid_y, lfsparms->num_directions);
3109
3110 /* Set minutia location to minimum theta position on the contour. */
3111 *oidir = idir;
3112 *ox_loc = contour_x[min_i];
3113 *oy_loc = contour_y[min_i];
3114 *ox_edge = contour_ex[min_i];
3115 *oy_edge = contour_ey[min_i];
3116
3117 /* Deallocate contour buffers. */
3118 free_contour(contour_x, contour_y, contour_ex, contour_ey);
3119
3120 /*Return normally. */
3121 return(0);
3122 }
3123
3124 /*************************************************************************
3125 **************************************************************************
3126 #cat: adjust_high_curvature_minutia_V2 - Takes an initial minutia point
3127 #cat: in a high-curvature area and adjusts its location and
3128 #cat: direction. First, it walks and extracts the contour
3129 #cat: of the detected feature looking for and processing any loop
3130 #cat: discovered along the way. Once the contour is extracted,
3131 #cat: the point of highest-curvature is determined and used to
3132 #cat: adjust the location of the minutia point. The angle of
3133 #cat: the line perpendicular to the tangent on the high-curvature
3134 #cat: contour at the minutia point is used as the mintutia's
3135 #cat: direction.
3136
3137 Input:
3138 x_loc - starting x-pixel coord of feature (interior to feature)
3139 y_loc - starting y-pixel coord of feature (interior to feature)
3140 x_edge - x-pixel coord of corresponding edge pixel
3141 (exterior to feature)
3142 y_edge - y-pixel coord of corresponding edge pixel
3143 (exterior to feature)
3144 bdata - binary image data (0==while & 1==black)
3145 iw - width (in pixels) of image
3146 ih - height (in pixels) of image
3147 plow_flow_map - pixelized Low Ridge Flow Map
3148 lfsparms - parameters and thresholds for controlling LFS
3149 Output:
3150 oidir - direction of adjusted minutia point
3151 ox_loc - adjusted x-pixel coord of feature
3152 oy_loc - adjusted y-pixel coord of feature
3153 ox_edge - adjusted x-pixel coord of corresponding edge pixel
3154 oy_edge - adjusted y-pixel coord of corresponding edge pixel
3155 minutiae - points to a list of detected minutia structures
3156 Return Code:
3157 Zero - minutia point processed successfully
3158 IGNORE - minutia point is to be ignored
3159 Negative - system error
3160 **************************************************************************/
adjust_high_curvature_minutia_V2(int * oidir,int * ox_loc,int * oy_loc,int * ox_edge,int * oy_edge,const int x_loc,const int y_loc,const int x_edge,const int y_edge,unsigned char * bdata,const int iw,const int ih,int * plow_flow_map,MINUTIAE * minutiae,const LFSPARMS * lfsparms)3161 int adjust_high_curvature_minutia_V2(int *oidir, int *ox_loc, int *oy_loc,
3162 int *ox_edge, int *oy_edge,
3163 const int x_loc, const int y_loc,
3164 const int x_edge, const int y_edge,
3165 unsigned char *bdata, const int iw, const int ih,
3166 int *plow_flow_map, MINUTIAE *minutiae, const LFSPARMS *lfsparms)
3167 {
3168 int ret;
3169 int *contour_x, *contour_y, *contour_ex, *contour_ey, ncontour;
3170 int min_i;
3171 double min_theta;
3172 int feature_pix;
3173 int mid_x, mid_y, mid_pix;
3174 int idir;
3175 int half_contour, angle_edge;
3176
3177 /* Set variable from parameter structure. */
3178 half_contour = lfsparms->high_curve_half_contour;
3179
3180 /* Set edge length for computing contour's angle of curvature */
3181 /* to one quarter of desired pixel length of entire contour. */
3182 /* Ex. If half_contour==14, then contour length==29=(2X14)+1 */
3183 /* and angle_edge==7=(14/2). */
3184 angle_edge = half_contour>>1;
3185
3186 /* Get the pixel value of current feature. */
3187 feature_pix = *(bdata + (y_loc * iw) + x_loc);
3188
3189 /* Extract feature's contour. */
3190 if((ret = get_high_curvature_contour(&contour_x, &contour_y,
3191 &contour_ex, &contour_ey, &ncontour, half_contour,
3192 x_loc, y_loc, x_edge, y_edge, bdata, iw, ih))){
3193 /* Returns with: */
3194 /* 1. Successful or empty contour == 0 */
3195 /* If contour is empty, then contour lists are not allocated. */
3196 /* 2. Contour forms loop == LOOP_FOUND */
3197 /* 3. Sysetm error < 0 */
3198
3199 /* If the contour forms a loop... */
3200 if(ret == LOOP_FOUND){
3201
3202 /* If the order of the contour is clockwise, then the loops's */
3203 /* contour pixels are outside the corresponding edge pixels. We */
3204 /* definitely do NOT want to fill based on the feature pixel in */
3205 /* this case, because it is OUTSIDE the loop. For now we will */
3206 /* ignore the loop and the minutia that triggered its tracing. */
3207 /* It is likely that other minutia on the loop will be */
3208 /* detected that create a contour on the "inside" of the loop. */
3209 /* There is another issue here that could be addressed ... */
3210 /* It seems that many/multiple minutia are often detected within */
3211 /* the same loop, which currently requires retracing the loop, */
3212 /* locating minutia on opposite ends of the major axis of the */
3213 /* loop, and then determining that the minutia have already been */
3214 /* entered into the minutiae list upon processing the very first */
3215 /* minutia detected in the loop. There is a lot of redundant */
3216 /* work being done here! */
3217 /* Is_loop_clockwise takes a default value to be returned if the */
3218 /* routine is unable to determine the direction of the contour. */
3219 /* In this case, we want to IGNORE the loop if we can't tell its */
3220 /* direction so that we do not inappropriately fill the loop, so */
3221 /* we are passing the default value TRUE. */
3222 if((ret = is_loop_clockwise(contour_x, contour_y, ncontour, TRUE))){
3223 /* Deallocate contour lists. */
3224 free_contour(contour_x, contour_y, contour_ex, contour_ey);
3225 /* If we had a system error... */
3226 if(ret < 0)
3227 /* Return the error code. */
3228 return(ret);
3229 /* Otherwise, loop is clockwise, so return IGNORE. */
3230 return(IGNORE);
3231 }
3232
3233 /* Otherwise, process the clockwise-ordered contour of the loop */
3234 /* as it may contain minutia. If no minutia found, then it is */
3235 /* filled in. */
3236 ret = process_loop_V2(minutiae, contour_x, contour_y,
3237 contour_ex, contour_ey, ncontour,
3238 bdata, iw, ih, plow_flow_map, lfsparms);
3239 /* Returns with: */
3240 /* 1. Successful processing of loop == 0 */
3241 /* 2. System error < 0 */
3242
3243 /* Deallocate contour lists. */
3244 free_contour(contour_x, contour_y, contour_ex, contour_ey);
3245
3246 /* If loop processed successfully ... */
3247 if(ret == 0)
3248 /* Then either a minutia pair was extracted or the loop was */
3249 /* filled. Either way we want to IGNORE the minutia that */
3250 /* started the whole loop processing in the beginning. */
3251 return(IGNORE);
3252
3253 /* Otherwise, there was a system error. */
3254 /* Return the resulting code. */
3255 return(ret);
3256 }
3257
3258 /* Otherwise not a loop, so get_high_curvature_contour incurred */
3259 /* a system error. Return the error code. */
3260 return(ret);
3261 }
3262
3263 /* If contour is empty ... then contour lists were not allocated, so */
3264 /* simply return IGNORE. The contour comes back empty when there */
3265 /* were not a sufficient number of points found on the contour. */
3266 if(ncontour == 0)
3267 return(IGNORE);
3268
3269 /* Otherwise, there are contour points to process. */
3270
3271 /* Given the contour, determine the point of highest curvature */
3272 /* (ie. forming the minimum angle between contour walls). */
3273 if((ret = min_contour_theta(&min_i, &min_theta, angle_edge,
3274 contour_x, contour_y, ncontour))){
3275 /* Deallocate contour lists. */
3276 free_contour(contour_x, contour_y, contour_ex, contour_ey);
3277 /* Returns IGNORE or system error. Either way */
3278 /* free the contour and return the code. */
3279 return(ret);
3280 }
3281
3282 /* If the minimum theta found along the contour is too large... */
3283 if(min_theta >= lfsparms->max_high_curve_theta){
3284 /* Deallocate contour lists. */
3285 free_contour(contour_x, contour_y, contour_ex, contour_ey);
3286 /* Reject the high-curvature minutia, and return IGNORE. */
3287 return(IGNORE);
3288 }
3289
3290 /* Test to see if interior of curvature is OK. Compute midpoint */
3291 /* between left and right points symmetrically distant (angle_edge */
3292 /* pixels) from the contour's point of minimum theta. */
3293 mid_x = (contour_x[min_i-angle_edge] + contour_x[min_i+angle_edge])>>1;
3294 mid_y = (contour_y[min_i-angle_edge] + contour_y[min_i+angle_edge])>>1;
3295 mid_pix = *(bdata + (mid_y * iw) + mid_x);
3296 /* If the interior pixel value is not the same as the feature's... */
3297 if(mid_pix != feature_pix){
3298 /* Deallocate contour lists. */
3299 free_contour(contour_x, contour_y, contour_ex, contour_ey);
3300 /* Reject the high-curvature minutia and return IGNORE. */
3301 return(IGNORE);
3302 }
3303
3304 /* Compute new direction based on line connecting adjusted feature */
3305 /* location and the midpoint in the feature's interior. */
3306 idir = line2direction(contour_x[min_i], contour_y[min_i],
3307 mid_x, mid_y, lfsparms->num_directions);
3308
3309 /* Set minutia location to minimum theta position on the contour. */
3310 *oidir = idir;
3311 *ox_loc = contour_x[min_i];
3312 *oy_loc = contour_y[min_i];
3313 *ox_edge = contour_ex[min_i];
3314 *oy_edge = contour_ey[min_i];
3315
3316 /* Deallocate contour buffers. */
3317 free_contour(contour_x, contour_y, contour_ex, contour_ey);
3318
3319 /*Return normally. */
3320 return(0);
3321 }
3322
3323 /*************************************************************************
3324 **************************************************************************
3325 #cat: get_low_curvature_direction - Converts a bi-direcitonal IMAP direction
3326 #cat: (based on a semi-circle) to a uni-directional value covering
3327 #cat: a full circle based on the scan orientation used to detect
3328 #cat: a minutia feature (horizontal or vertical) and whether the
3329 #cat: detected minutia is appearing or disappearing.
3330
3331 Input:
3332 scan_dir - designates the feature scan orientation
3333 appearing - designates the minutia as appearing or disappearing
3334 imapval - IMAP block direction
3335 ndirs - number of IMAP directions (in semicircle)
3336 Return Code:
3337 New direction - bi-directonal integer direction on full circle
3338 *************************************************************************/
get_low_curvature_direction(const int scan_dir,const int appearing,const int imapval,const int ndirs)3339 int get_low_curvature_direction(const int scan_dir, const int appearing,
3340 const int imapval, const int ndirs)
3341 {
3342 int idir;
3343
3344 /* Start direction out with IMAP value. */
3345 idir = imapval;
3346
3347 /* NOTE! */
3348 /* The logic in this routine should hold whether for ridge endings */
3349 /* or for bifurcations. The examples in the comments show ridge */
3350 /* ending conditions only. */
3351
3352 /* CASE I : Ridge flow in Quadrant I; directions [0..8] */
3353 if(imapval <= (ndirs>>1)){
3354 /* I.A: HORIZONTAL scan */
3355 if(scan_dir == SCAN_HORIZONTAL){
3356 /* I.A.1: Appearing Minutia */
3357 if(appearing){
3358 /* Ex. 0 0 0 */
3359 /* 0 1 0 */
3360 /* ? ? */
3361 /* Ridge flow is up and to the right, whereas */
3362 /* actual ridge is running down and to the */
3363 /* left. */
3364 /* Thus: HORIZONTAL : appearing : should be */
3365 /* OPPOSITE the ridge flow direction. */
3366 idir += ndirs;
3367 }
3368 /* Otherwise: */
3369 /* I.A.2: Disappearing Minutia */
3370 /* Ex. ? ? */
3371 /* 0 1 0 */
3372 /* 0 0 0 */
3373 /* Ridge flow is up and to the right, which */
3374 /* should be SAME direction from which ridge */
3375 /* is projecting. */
3376 /* Thus: HORIZONTAL : disappearing : should */
3377 /* be the same as ridge flow direction. */
3378 } /* End if HORIZONTAL scan */
3379 /* Otherwise: */
3380 /* I.B: VERTICAL scan */
3381 else{
3382 /* I.B.1: Disappearing Minutia */
3383 if(!appearing){
3384 /* Ex. 0 0 */
3385 /* ? 1 0 */
3386 /* ? 0 0 */
3387 /* Ridge flow is up and to the right, whereas */
3388 /* actual ridge is projecting down and to the */
3389 /* left. */
3390 /* Thus: VERTICAL : disappearing : should be */
3391 /* OPPOSITE the ridge flow direction. */
3392 idir += ndirs;
3393 }
3394 /* Otherwise: */
3395 /* I.B.2: Appearing Minutia */
3396 /* Ex. 0 0 ? */
3397 /* 0 1 ? */
3398 /* 0 0 */
3399 /* Ridge flow is up and to the right, which */
3400 /* should be SAME direction the ridge is */
3401 /* running. */
3402 /* Thus: VERTICAL : appearing : should be */
3403 /* be the same as ridge flow direction. */
3404 } /* End else VERTICAL scan */
3405 } /* End if Quadrant I */
3406
3407 /* Otherwise: */
3408 /* CASE II : Ridge flow in Quadrant II; directions [9..15] */
3409 else{
3410 /* II.A: HORIZONTAL scan */
3411 if(scan_dir == SCAN_HORIZONTAL){
3412 /* II.A.1: Disappearing Minutia */
3413 if(!appearing){
3414 /* Ex. ? ? */
3415 /* 0 1 0 */
3416 /* 0 0 0 */
3417 /* Ridge flow is down and to the right, */
3418 /* whereas actual ridge is running up and to */
3419 /* the left. */
3420 /* Thus: HORIZONTAL : disappearing : should */
3421 /* be OPPOSITE the ridge flow direction.*/
3422 idir += ndirs;
3423 }
3424 /* Otherwise: */
3425 /* II.A.2: Appearing Minutia */
3426 /* Ex. 0 0 0 */
3427 /* 0 1 0 */
3428 /* ? ? */
3429 /* Ridge flow is down and to the right, which */
3430 /* should be same direction from which ridge */
3431 /* is projecting. */
3432 /* Thus: HORIZONTAL : appearing : should be */
3433 /* the SAME as ridge flow direction. */
3434 } /* End if HORIZONTAL scan */
3435 /* Otherwise: */
3436 /* II.B: VERTICAL scan */
3437 else{
3438 /* II.B.1: Disappearing Minutia */
3439 if(!appearing){
3440 /* Ex. ? 0 0 */
3441 /* ? 1 0 */
3442 /* 0 0 */
3443 /* Ridge flow is down and to the right, */
3444 /* whereas actual ridge is running up and to */
3445 /* the left. */
3446 /* Thus: VERTICAL : disappearing : should be */
3447 /* OPPOSITE the ridge flow direction. */
3448 idir += ndirs;
3449 }
3450 /* Otherwise: */
3451 /* II.B.2: Appearing Minutia */
3452 /* Ex. 0 0 */
3453 /* 0 1 ? */
3454 /* 0 0 ? */
3455 /* Ridge flow is down and to the right, which */
3456 /* should be same direction the ridge is */
3457 /* projecting. */
3458 /* Thus: VERTICAL : appearing : should be */
3459 /* be the SAME as ridge flow direction. */
3460 } /* End else VERTICAL scan */
3461 } /* End else Quadrant II */
3462
3463 /* Return resulting direction on range [0..31]. */
3464 return(idir);
3465 }
3466
3467 /*************************************************************************
3468 **************************************************************************
3469 #cat: lfs2nist_minutia_XYT - Converts XYT minutiae attributes in LFS native
3470 #cat: representation to NIST internal representation
3471
3472 Input:
3473 minutia - LFS minutia structure containing attributes to be converted
3474 Output:
3475 ox - NIST internal based x-pixel coordinate
3476 oy - NIST internal based y-pixel coordinate
3477 ot - NIST internal based minutia direction/orientation
3478 Return Code:
3479 Zero - successful completion
3480 Negative - system error
3481 **************************************************************************/
lfs2nist_minutia_XYT(int * ox,int * oy,int * ot,const MINUTIA * minutia,const int iw,const int ih)3482 void lfs2nist_minutia_XYT(int *ox, int *oy, int *ot,
3483 const MINUTIA *minutia, const int iw, const int ih)
3484 {
3485 int x, y, t;
3486 float degrees_per_unit;
3487
3488 /* XYT's according to NIST internal rep: */
3489 /* 1. pixel coordinates with origin bottom-left */
3490 /* 2. orientation in degrees on range [0..360] */
3491 /* with 0 pointing east and increasing counter */
3492 /* clockwise (same as M1) */
3493 /* 3. direction pointing out and away from the */
3494 /* ridge ending or bifurcation valley */
3495 /* (opposite direction from M1) */
3496
3497 x = minutia->x;
3498 y = ih - minutia->y;
3499
3500 degrees_per_unit = 180 / (float)NUM_DIRECTIONS;
3501
3502 t = (270 - sround(minutia->direction * degrees_per_unit)) % 360;
3503 if(t < 0){
3504 t += 360;
3505 }
3506
3507 *ox = x;
3508 *oy = y;
3509 *ot = t;
3510 }
3511
3512