?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
NBIS cleanup
[libfprint.git] / libfprint / nbis / include / lfs.h
blobf260c48885c3b2c69e710e194f01b2b1f049794f
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 #ifndef _LFS_H
25 #define _LFS_H
26
27 /***********************************************************************
28 PACKAGE: NIST Latent Fingerprint System
29 AUTHOR: Michael D. Garris
30 DATE: 03/16/1999
31 UPDATED: 10/04/1999 Version 2 by MDG
32 UPDATED: 10/26/1999 by MDG
33 Comments added to guide changes to blocksize
34 or number of detected directions.
35 UPDATED: 03/11/2005 by MDG
36
37 FILE: LFS.H
38
39 Contains all custom structure definitions, constant definitions,
40 external function definitions, and external global variable
41 definitions required by the NIST Latent Fingerprint System (LFS).
42 ***********************************************************************/
43
44 #include <math.h>
45 #include <stdio.h>
46
47 /*************************************************************************/
48 /* OUTPUT FILE EXTENSIONS */
49 /*************************************************************************/
50 #define MIN_TXT_EXT "min"
51 #define LOW_CONTRAST_MAP_EXT "lcm"
52 #define HIGH_CURVE_MAP_EXT "hcm"
53 #define DIRECTION_MAP_EXT "dm"
54 #define LOW_FLOW_MAP_EXT "lfm"
55 #define QUALITY_MAP_EXT "qm"
56 #define AN2K_OUT_EXT "mdt"
57 #define BINARY_IMG_EXT "brw"
58 #define XYT_EXT "xyt"
59
60 /*************************************************************************/
61 /* MINUTIAE XYT REPRESENTATION SCHEMES */
62 /*************************************************************************/
63 #define NIST_INTERNAL_XYT_REP 0
64 #define M1_XYT_REP 1
65
66 /*************************************************************************/
67 /* MACRO DEFINITIONS */
68 /*************************************************************************/
69
70 #define max(a, b) ((a) > (b) ? (a) : (b))
71 #define min(a, b) ((a) < (b) ? (a) : (b))
72 #define sround(x) ((int) (((x)<0) ? (x)-0.5 : (x)+0.5))
73 #define trunc_dbl_precision(x, scale) ((double) (((x)<0.0) \
74 ? ((int)(((x)*(scale))-0.5))/(scale) \
75 : ((int)(((x)*(scale))+0.5))/(scale)))
76
77 #ifndef M_PI
78 #define M_PI 3.14159265358979323846 /* pi */
79 #endif
80
81 /*************************************************************************/
82 /* STRUCTURE DEFINITIONS */
83 /*************************************************************************/
84
85 /* Lookup tables for converting from integer directions */
86 /* to angles in radians. */
87 typedef struct dir2rad{
88 int ndirs;
89 double *cos;
90 double *sin;
91 } DIR2RAD;
92
93 /* DFT wave form structure containing both cosine and */
94 /* sine components for a specific frequency. */
95 typedef struct dftwave{
96 double *cos;
97 double *sin;
98 } DFTWAVE;
99
100 /* DFT wave forms structure containing all wave forms */
101 /* to be used in DFT analysis. */
102 typedef struct dftwaves{
103 int nwaves;
104 int wavelen;
105 DFTWAVE **waves;
106 }DFTWAVES;
107
108 /* Rotated pixel offsets for a grid of specified dimensions */
109 /* rotated at a specified number of different orientations */
110 /* (directions). This structure used by the DFT analysis */
111 /* when generating a Direction Map and also for conducting */
112 /* isotropic binarization. */
113 typedef struct rotgrids{
114 int pad;
115 int relative2;
116 double start_angle;
117 int ngrids;
118 int grid_w;
119 int grid_h;
120 int **grids;
121 } ROTGRIDS;
122
123 /*************************************************************************/
124 /* 10, 2X3 pixel pair feature patterns used to define ridge endings */
125 /* and bifurcations. */
126 /* 2nd pixel pair is permitted to repeat multiple times in match. */
127 #define NFEATURES 10
128 #define BIFURCATION 0
129 #define RIDGE_ENDING 1
130 #define DISAPPEARING 0
131 #define APPEARING 1
132
133 typedef struct minutia{
134 int x;
135 int y;
136 int ex;
137 int ey;
138 int direction;
139 double reliability;
140 int type;
141 int appearing;
142 int feature_id;
143 int *nbrs;
144 int *ridge_counts;
145 int num_nbrs;
146 } MINUTIA;
147
148 typedef struct minutiae{
149 int alloc;
150 int num;
151 MINUTIA **list;
152 } MINUTIAE;
153
154 typedef struct feature_pattern{
155 int type;
156 int appearing;
157 int first[2];
158 int second[2];
159 int third[2];
160 } FEATURE_PATTERN;
161
162 /* SHAPE structure definitions. */
163 typedef struct rows{
164 int y; /* Y-coord of current row in shape. */
165 int *xs; /* X-coords for shape contour points on current row. */
166 int alloc; /* Number of points allocate for x-coords on row. */
167 int npts; /* Number of points assigned for x-coords on row. */
168 } ROW;
169
170 typedef struct shape{
171 int ymin; /* Y-coord of top-most scanline in shape. */
172 int ymax; /* Y-coord of bottom-most scanline in shape. */
173 ROW **rows; /* List of row pointers comprising the shape. */
174 int alloc; /* Number of rows allocated for shape. */
175 int nrows; /* Number of rows assigned to shape. */
176 } SHAPE;
177
178 /* Parameters used by LFS for setting thresholds and */
179 /* defining testing criterion. */
180 typedef struct lfsparms{
181 /* Image Controls */
182 int pad_value;
183 int join_line_radius;
184
185 /* Map Controls */
186 int blocksize; /* Pixel dimension image block. */
187 int windowsize; /* Pixel dimension window surrounding block. */
188 int windowoffset; /* Offset in X & Y from block to window origin. */
189 int num_directions;
190 double start_dir_angle;
191 int rmv_valid_nbr_min;
192 double dir_strength_min;
193 int dir_distance_max;
194 int smth_valid_nbr_min;
195 int vort_valid_nbr_min;
196 int highcurv_vorticity_min;
197 int highcurv_curvature_min;
198 int min_interpolate_nbrs;
199 int percentile_min_max;
200 int min_contrast_delta;
201
202 /* DFT Controls */
203 int num_dft_waves;
204 double powmax_min;
205 double pownorm_min;
206 double powmax_max;
207 int fork_interval;
208 double fork_pct_powmax;
209 double fork_pct_pownorm;
210
211 /* Binarization Controls */
212 int dirbin_grid_w;
213 int dirbin_grid_h;
214 int isobin_grid_dim;
215 int num_fill_holes;
216
217 /* Minutiae Detection Controls */
218 int max_minutia_delta;
219 double max_high_curve_theta;
220 int high_curve_half_contour;
221 int min_loop_len;
222 double min_loop_aspect_dist;
223 double min_loop_aspect_ratio;
224
225 /* Minutiae Link Controls */
226 int link_table_dim;
227 int max_link_dist;
228 int min_theta_dist;
229 int maxtrans;
230 double score_theta_norm;
231 double score_dist_norm;
232 double score_dist_weight;
233 double score_numerator;
234
235 /* False Minutiae Removal Controls */
236 int max_rmtest_dist;
237 int max_hook_len;
238 int max_half_loop;
239 int trans_dir_pix;
240 int small_loop_len;
241 int side_half_contour;
242 int inv_block_margin;
243 int rm_valid_nbr_min;
244 int max_overlap_dist;
245 int max_overlap_join_dist;
246 int malformation_steps_1;
247 int malformation_steps_2;
248 double min_malformation_ratio;
249 int max_malformation_dist;
250 int pores_trans_r;
251 int pores_perp_steps;
252 int pores_steps_fwd;
253 int pores_steps_bwd;
254 double pores_min_dist2;
255 double pores_max_ratio;
256
257 /* Ridge Counting Controls */
258 int max_nbrs;
259 int max_ridge_steps;
260 } LFSPARMS;
261
262 /*************************************************************************/
263 /* LFS CONSTANT DEFINITIONS */
264 /*************************************************************************/
265
266 /***** IMAGE CONSTANTS *****/
267
268 #ifndef DEFAULT_PPI
269 #define DEFAULT_PPI 500
270 #endif
271
272 /* Intensity used to fill padded image area */
273 #define PAD_VALUE 128 /* medium gray @ 8 bits */
274
275 /* Intensity used to draw on grayscale images */
276 #define DRAW_PIXEL 255 /* white in 8 bits */
277
278 /* Definitions for 8-bit binary pixel intensities. */
279 #define WHITE_PIXEL 255
280 #define BLACK_PIXEL 0
281
282 /* Definitions for controlling join_miutia(). */
283 /* Draw without opposite perimeter pixels. */
284 #define NO_BOUNDARY 0
285
286 /* Draw with opposite perimeter pixels. */
287 #define WITH_BOUNDARY 1
288
289 /* Radial width added to join line (not including the boundary pixels). */
290 #define JOIN_LINE_RADIUS 1
291
292
293 /***** MAP CONSTANTS *****/
294
295 /* Map value for not well-defined directions */
296 #define INVALID_DIR -1
297
298 /* Map value assigned when the current block has no neighbors */
299 /* with valid direction. */
300 #define NO_VALID_NBRS -3
301
302 /* Map value designating a block is near a high-curvature */
303 /* area such as a core or delta. */
304 #define HIGH_CURVATURE -2
305
306 /* This specifies the pixel dimensions of each block in the IMAP */
307 #define IMAP_BLOCKSIZE 24
308
309 /* Pixel dimension of image blocks. The following three constants work */
310 /* together to define a system of 8X8 adjacent and non-overlapping */
311 /* blocks that are assigned results from analyzing a larger 24X24 */
312 /* window centered about each of the 8X8 blocks. */
313 /* CAUTION: If MAP_BLOCKSIZE_V2 is changed, then the following will */
314 /* likely need to be changed: MAP_WINDOWOFFSET_V2, */
315 /* TRANS_DIR_PIX_V2, */
316 /* INV_BLOCK_MARGIN_V2 */
317 #define MAP_BLOCKSIZE_V2 8
318
319 /* Pixel dimension of window that surrounds the block. The result from */
320 /* analyzing the content of the window is stored in the interior block. */
321 #define MAP_WINDOWSIZE_V2 24
322
323 /* Pixel offset in X & Y from the origin of the block to the origin of */
324 /* the surrounding window. */
325 #define MAP_WINDOWOFFSET_V2 8
326
327 /* This is the number of integer directions to be used in semicircle. */
328 /* CAUTION: If NUM_DIRECTIONS is changed, then the following will */
329 /* likely need to be changed: HIGHCURV_VORTICITY_MIN, */
330 /* HIGHCURV_CURVATURE_MIN, */
331 /* FORK_INTERVAL */
332 #define NUM_DIRECTIONS 16
333
334 /* This is the theta from which integer directions */
335 /* are to begin. */
336 #define START_DIR_ANGLE (double)(M_PI/2.0) /* 90 degrees */
337
338 /* Minimum number of valid neighbors required for a */
339 /* valid block value to keep from being removed. */
340 #define RMV_VALID_NBR_MIN 3
341
342 /* Minimum strength for a direction to be considered significant. */
343 #define DIR_STRENGTH_MIN 0.2
344
345 /* Maximum distance allowable between valid block direction */
346 /* and the average direction of its neighbors before the */
347 /* direction is removed. */
348 #define DIR_DISTANCE_MAX 3
349
350 /* Minimum number of valid neighbors required for an */
351 /* INVALID block direction to receive its direction from */
352 /* the average of its neighbors. */
353 #define SMTH_VALID_NBR_MIN 7
354
355 /* Minimum number of valid neighbors required for a block */
356 /* with an INVALID block direction to be measured for */
357 /* vorticity. */
358 #define VORT_VALID_NBR_MIN 7
359
360 /* The minimum vorticity value whereby an INVALID block */
361 /* is determined to be high-curvature based on the directions */
362 /* of it neighbors. */
363 #define HIGHCURV_VORTICITY_MIN 5
364
365 /* The minimum curvature value whereby a VALID direction block is */
366 /* determined to be high-curvature based on it value compared with */
367 /* its neighbors' directions. */
368 #define HIGHCURV_CURVATURE_MIN 5
369
370 /* Minimum number of neighbors with VALID direction for an INVALID */
371 /* directon block to have its direction interpolated from those neighbors. */
372 #define MIN_INTERPOLATE_NBRS 2
373
374 /* Definitions for creating a low contrast map. */
375 /* Percentile cut off for choosing min and max pixel intensities */
376 /* in a block. */
377 #define PERCENTILE_MIN_MAX 10
378
379 /* The minimum delta between min and max percentile pixel intensities */
380 /* in block for block NOT to be considered low contrast. (Note that */
381 /* this value is in terms of 6-bit pixels.) */
382 #define MIN_CONTRAST_DELTA 5
383
384
385 /***** DFT CONSTANTS *****/
386
387 /* This specifies the number of DFT wave forms to be applied */
388 #define NUM_DFT_WAVES 4
389
390 /* Minimum total DFT power for any given block */
391 /* which is used to compute an average power. */
392 /* By setting a non-zero minimum total,possible */
393 /* division by zero is avoided. This value was */
394 /* taken from HO39. */
395 #define MIN_POWER_SUM 10.0
396
397 /* Thresholds and factors used by HO39. Renamed */
398 /* here to give more meaning. */
399 /* HO39 Name=Value */
400 /* Minimum DFT power allowable in any one direction. */
401 #define POWMAX_MIN 100000.0 /* thrhf=1e5f */
402
403 /* Minimum normalized power allowable in any one */
404 /* direction. */
405 #define POWNORM_MIN 3.8 /* disc=3.8f */
406
407 /* Maximum power allowable at the lowest frequency */
408 /* DFT wave. */
409 #define POWMAX_MAX 50000000.0 /* thrlf=5e7f */
410
411 /* Check for a fork at +- this number of units from */
412 /* current integer direction. For example, */
413 /* 2 dir ==> 11.25 X 2 degrees. */
414 #define FORK_INTERVAL 2
415
416 /* Minimum DFT power allowable at fork angles is */
417 /* FORK_PCT_POWMAX X block's max directional power. */
418 #define FORK_PCT_POWMAX 0.7
419
420 /* Minimum normalized power allowable at fork angles */
421 /* is FORK_PCT_POWNORM X POWNORM_MIN */
422 #define FORK_PCT_POWNORM 0.75
423
424
425 /***** BINRAIZATION CONSTANTS *****/
426
427 /* Directional binarization grid dimensions. */
428 #define DIRBIN_GRID_W 7
429 #define DIRBIN_GRID_H 9
430
431 /* The pixel dimension (square) of the grid used in isotropic */
432 /* binarization. */
433 #define ISOBIN_GRID_DIM 11
434
435 /* Number of passes through the resulting binary image where holes */
436 /* of pixel length 1 in horizontal and vertical runs are filled. */
437 #define NUM_FILL_HOLES 3
438
439
440 /***** MINUTIAE DETECTION CONSTANTS *****/
441
442 /* The maximum pixel translation distance in X or Y within which */
443 /* two potential minutia points are to be considered similar. */
444 #define MAX_MINUTIA_DELTA 10
445
446 /* If the angle of a contour exceeds this angle, then it is NOT */
447 /* to be considered to contain minutiae. */
448 #define MAX_HIGH_CURVE_THETA (double)(M_PI/3.0)
449
450 /* Half the length in pixels to be extracted for a high-curvature contour. */
451 #define HIGH_CURVE_HALF_CONTOUR 14
452
453 /* Loop must be larger than this threshold (in pixels) to be considered */
454 /* to contain minutiae. */
455 #define MIN_LOOP_LEN 20
456
457 /* If loop's minimum distance half way across its contour is less than */
458 /* this threshold, then loop is tested for minutiae. */
459 #define MIN_LOOP_ASPECT_DIST 1.0
460
461 /* If ratio of loop's maximum/minimum distances half way across its */
462 /* contour is >= to this threshold, then loop is tested for minutiae. */
463 #define MIN_LOOP_ASPECT_RATIO 2.25
464
465 /* There are 10 unique feature patterns with ID = [0..9] , */
466 /* so set LOOP ID to 10 (one more than max pattern ID). */
467 #define LOOP_ID 10
468
469 /* Definitions for controlling the scanning of minutiae. */
470 #define SCAN_HORIZONTAL 0
471 #define SCAN_VERTICAL 1
472 #define SCAN_CLOCKWISE 0
473 #define SCAN_COUNTER_CLOCKWISE 1
474
475 /* The dimension of the chaincode loopkup matrix. */
476 #define NBR8_DIM 3
477
478 /* Default minutiae reliability. */
479 #define DEFAULT_RELIABILITY 0.99
480
481 /* Medium minutia reliability. */
482 #define MEDIUM_RELIABILITY 0.50
483
484 /* High minutia reliability. */
485 #define HIGH_RELIABILITY 0.99
486
487
488 /***** MINUTIAE LINKING CONSTANTS *****/
489
490 /* Definitions for controlling the linking of minutiae. */
491 /* Square dimensions of 2D table of potentially linked minutiae. */
492 #define LINK_TABLE_DIM 20
493
494 /* Distance (in pixels) used to determine if the orthogonal distance */
495 /* between the coordinates of 2 minutia points are sufficiently close */
496 /* to be considered for linking. */
497 #define MAX_LINK_DIST 20
498
499 /* Minimum distance (in pixels) between 2 minutia points that an angle */
500 /* computed between the points may be considered reliable. */
501 #define MIN_THETA_DIST 5
502
503 /* Maximum number of transitions along a contiguous pixel trajectory */
504 /* between 2 minutia points for that trajectory to be considered "free" */
505 /* of obstacles. */
506 #define MAXTRANS 2
507
508 /* Parameters used to compute a link score between 2 minutiae. */
509 #define SCORE_THETA_NORM 15.0
510 #define SCORE_DIST_NORM 10.0
511 #define SCORE_DIST_WEIGHT 4.0
512 #define SCORE_NUMERATOR 32000.0
513
514
515 /***** FALSE MINUTIAE REMOVAL CONSTANTS *****/
516
517 /* Definitions for removing hooks, islands, lakes, and overlaps. */
518 /* Distance (in pixels) used to determine if the orthogonal distance */
519 /* between the coordinates of 2 minutia points are sufficiently close */
520 /* to be considered for removal. */
521 #define MAX_RMTEST_DIST 8
522
523 #define MAX_RMTEST_DIST_V2 16
524
525 /* Length of pixel contours to be traced and analyzed for possible hooks. */
526 #define MAX_HOOK_LEN 15
527
528 #define MAX_HOOK_LEN_V2 30
529
530 /* Half the maximum length of pixel contours to be traced and analyzed */
531 /* for possible loops (islands/lakes). */
532 #define MAX_HALF_LOOP 15
533
534 #define MAX_HALF_LOOP_V2 30
535
536 /* Definitions for removing minutiae that are sufficiently close and */
537 /* point to a block with invalid ridge flow. */
538 /* Distance (in pixels) in direction opposite the minutia to be */
539 /* considered sufficiently close to an invalid block. */
540 #define TRANS_DIR_PIX 6
541
542 #define TRANS_DIR_PIX_V2 4
543
544 /* Definitions for removing small holes (islands/lakes). */
545 /* Maximum circumference (in pixels) of qualifying loops. */
546 #define SMALL_LOOP_LEN 15
547
548 /* Definitions for removing or adusting side minutiae. */
549 /* Half the number of pixels to be traced to form a complete contour. */
550 #define SIDE_HALF_CONTOUR 7
551
552 /* Definitions for removing minutiae near invalid blocks. */
553 /* Maximum orthogonal distance a minutia can be neighboring a block with */
554 /* invalid ridge flow in order to be removed. */
555 #define INV_BLOCK_MARGIN 6
556
557 #define INV_BLOCK_MARGIN_V2 4
558
559 /* Given a sufficiently close, neighboring invalid block, if that invalid */
560 /* block has a total number of neighboring blocks with valid ridge flow */
561 /* less than this threshold, then the minutia point is removed. */
562 #define RM_VALID_NBR_MIN 7
563
564 /* Definitions for removing overlaps. */
565 /* Maximum pixel distance between 2 points to be tested for overlapping */
566 /* conditions. */
567 #define MAX_OVERLAP_DIST 8
568
569 /* Maximum pixel distance between 2 points on opposite sides of an overlap */
570 /* will be joined. */
571 #define MAX_OVERLAP_JOIN_DIST 6
572
573 /* Definitions for removing "irregularly-shaped" minutiae. */
574 /* Contour steps to be traced to 1st measuring point. */
575 #define MALFORMATION_STEPS_1 10
576 /* Contour steps to be traced to 2nd measuring point. */
577 #define MALFORMATION_STEPS_2 20
578 /* Minimum ratio of distances across feature at the two point to be */
579 /* considered normal. */
580 #define MIN_MALFORMATION_RATIO 2.0
581 /* Maximum distance permitted across feature to be considered normal. */
582 #define MAX_MALFORMATION_DIST 20
583
584 /* Definitions for removing minutiae on pores. */
585 /* Translation distance (in pixels) from minutia point in opposite direction */
586 /* in order to get off a valley edge and into the neighboring ridge. */
587 #define PORES_TRANS_R 3
588
589 /* Number of steps (in pixels) to search for edge of current ridge. */
590 #define PORES_PERP_STEPS 12
591
592 /* Number of pixels to be traced to find forward contour points. */
593 #define PORES_STEPS_FWD 10
594
595 /* Number of pixels to be traced to find backward contour points. */
596 #define PORES_STEPS_BWD 8
597
598 /* Minimum squared distance between points before being considered zero. */
599 #define PORES_MIN_DIST2 0.5
600
601 /* Max ratio of computed distances between pairs of forward and backward */
602 /* contour points to be considered a pore. */
603 #define PORES_MAX_RATIO 2.25
604
605
606 /***** RIDGE COUNTING CONSTANTS *****/
607
608 /* Definitions for detecting nearest neighbors and counting ridges. */
609 /* Maximum number of nearest neighbors per minutia. */
610 #define MAX_NBRS 5
611
612 /* Maximum number of contour steps taken to validate a ridge crossing. */
613 #define MAX_RIDGE_STEPS 10
614
615 /*************************************************************************/
616 /* QUALITY/RELIABILITY DEFINITIONS */
617 /*************************************************************************/
618 /* Quality map levels */
619 #define QMAP_LEVELS 5
620
621 /* Neighborhood radius in millimeters computed from 11 pixles */
622 /* scanned at 19.69 pixels/mm. */
623 #define RADIUS_MM ((double)(11.0 / 19.69))
624
625 /* Ideal Standard Deviation of pixel values in a neighborhood. */
626 #define IDEALSTDEV 64
627 /* Ideal Mean of pixel values in a neighborhood. */
628 #define IDEALMEAN 127
629
630 /* Look for neighbors this many blocks away. */
631 #define NEIGHBOR_DELTA 2
632
633 /*************************************************************************/
634 /* GENERAL DEFINITIONS */
635 /*************************************************************************/
636 #define LFS_VERSION_STR "NIST_LFS_VER2"
637
638 /* This factor converts degrees to radians. */
639 #ifndef DEG2RAD
640 #define DEG2RAD (double)(M_PI/180.0)
641 #endif
642
643 #define NORTH 0
644 #define SOUTH 4
645 #define EAST 2
646 #define WEST 6
647
648 #ifndef TRUE
649 #define TRUE 1
650 #endif
651 #ifndef FALSE
652 #define FALSE 0
653 #endif
654
655 #ifndef FOUND
656 #define FOUND TRUE
657 #endif
658 #ifndef NOT_FOUND
659 #define NOT_FOUND FALSE
660 #endif
661
662 #define HOOK_FOUND 1
663 #define LOOP_FOUND 1
664 #define IGNORE 2
665 #define LIST_FULL 3
666 #define INCOMPLETE 3
667
668 /* Pixel value limit in 6-bit image. */
669 #define IMG_6BIT_PIX_LIMIT 64
670
671 /* Maximum number (or reallocated chunks) of minutia to be detected */
672 /* in an image. */
673 #define MAX_MINUTIAE 1000
674
675 /* If both deltas in X and Y for a line of specified slope is less than */
676 /* this threshold, then the angle for the line is set to 0 radians. */
677 #define MIN_SLOPE_DELTA 0.5
678
679 /* Designates that rotated grid offsets should be relative */
680 /* to the grid's center. */
681 #define RELATIVE2CENTER 0
682
683 /* Designates that rotated grid offsets should be relative */
684 /* to the grid's origin. */
685 #define RELATIVE2ORIGIN 1
686
687 /* Truncate floating point precision by multiply, rounding, and then */
688 /* dividing by this value. This enables consistant results across */
689 /* different computer architectures. */
690 #define TRUNC_SCALE 16384.0
691
692 /* Designates passed argument as undefined. */
693 #define UNDEFINED -1
694
695 /* Dummy values for unused LFS control parameters. */
696 #define UNUSED_INT 0
697 #define UNUSED_DBL 0.0
698
699 /*************************************************************************/
700 /* EXTERNAL FUNCTION DEFINITIONS */
701 /*************************************************************************/
702
703 /* binar.c */
704 extern int binarize_V2(unsigned char **, int *, int *,
705 unsigned char *, const int, const int,
706 int *, const int, const int,
707 const ROTGRIDS *, const LFSPARMS *);
708 extern int binarize_image_V2(unsigned char **, int *, int *,
709 unsigned char *, const int, const int,
710 const int *, const int, const int,
711 const int, const ROTGRIDS *);
712 extern int dirbinarize(const unsigned char *, const int, const ROTGRIDS *);
713
714 /* block.c */
715 extern int block_offsets(int **, int *, int *, const int, const int,
716 const int, const int);
717 extern int low_contrast_block(const int, const int,
718 unsigned char *, const int, const int, const LFSPARMS *);
719 extern int find_valid_block(int *, int *, int *, int *, int *,
720 const int, const int, const int, const int,
721 const int, const int);
722 extern void set_margin_blocks(int *, const int, const int, const int);
723
724 /* chaincod.c */
725 extern int chain_code_loop(int **, int *, const int *, const int *, const int);
726 extern int is_chain_clockwise(const int *, const int, const int);
727
728 /* contour.c */
729 extern int allocate_contour(int **, int **, int **, int **, const int);
730 extern void free_contour(int *, int *, int *, int *);
731 extern int get_high_curvature_contour(int **, int **, int **, int **, int *,
732 const int, const int, const int, const int, const int,
733 unsigned char *, const int, const int);
734 extern int get_centered_contour(int **, int **, int **, int **, int *,
735 const int, const int, const int, const int, const int,
736 unsigned char *, const int, const int);
737 extern int trace_contour(int **, int **, int **, int **, int *,
738 const int, const int, const int, const int, const int,
739 const int, const int, const int,
740 unsigned char *, const int, const int);
741 extern int search_contour(const int, const int, const int,
742 const int, const int, const int, const int, const int,
743 unsigned char *, const int, const int);
744 extern int next_contour_pixel(int *, int *, int *, int *,
745 const int, const int, const int, const int, const int,
746 unsigned char *, const int, const int);
747 extern int start_scan_nbr(const int, const int, const int, const int);
748 extern int next_scan_nbr(const int, const int);
749 extern int min_contour_theta(int *, double *, const int, const int *,
750 const int *, const int);
751 extern void contour_limits(int *, int *, int *, int *, const int *,
752 const int *, const int);
753 extern void fix_edge_pixel_pair(int *, int *, int *, int *,
754 unsigned char *, const int, const int);
755
756 /* detect.c */
757 extern int lfs_detect_minutiae_V2(MINUTIAE **,
758 int **, int **, int **, int **, int *, int *,
759 unsigned char **, int *, int *,
760 unsigned char *, const int, const int,
761 const LFSPARMS *);
762
763 /* dft.c */
764 extern int dft_dir_powers(double **, unsigned char *, const int,
765 const int, const int, const DFTWAVES *,
766 const ROTGRIDS *);
767 extern int dft_power_stats(int *, double *, int *, double *, double **,
768 const int, const int, const int);
769
770 /* free.c */
771 extern void free_dir2rad(DIR2RAD *);
772 extern void free_dftwaves(DFTWAVES *);
773 extern void free_rotgrids(ROTGRIDS *);
774 extern void free_dir_powers(double **, const int);
775
776 /* getmin.c */
777 extern int get_minutiae(MINUTIAE **, int **, int **, int **,
778 int **, int **, int *, int *,
779 unsigned char **, int *, int *, int *,
780 unsigned char *, const int, const int,
781 const int, const double, const LFSPARMS *);
782
783 /* imgutil.c */
784 extern void bits_6to8(unsigned char *, const int, const int);
785 extern void bits_8to6(unsigned char *, const int, const int);
786 extern void gray2bin(const int, const int, const int,
787 unsigned char *, const int, const int);
788 extern int pad_uchar_image(unsigned char **, int *, int *,
789 unsigned char *, const int, const int, const int,
790 const int);
791 extern void fill_holes(unsigned char *, const int, const int);
792 extern int free_path(const int, const int, const int, const int,
793 unsigned char *, const int, const int, const LFSPARMS *);
794 extern int search_in_direction(int *, int *, int *, int *, const int,
795 const int, const int, const double, const double,
796 const int, unsigned char *, const int, const int);
797
798 /* init.c */
799 extern int init_dir2rad(DIR2RAD **, const int);
800 extern int init_dftwaves(DFTWAVES **, const double *, const int, const int);
801 extern int get_max_padding_V2(const int, const int, const int, const int);
802 extern int init_rotgrids(ROTGRIDS **, const int, const int, const int,
803 const double, const int, const int, const int, const int);
804 extern int alloc_dir_powers(double ***, const int, const int);
805 extern int alloc_power_stats(int **, double **, int **, double **, const int);
806
807 /* isempty.c */
808 extern int is_image_empty(int *, const int, const int);
809 extern int is_qmap_empty(int *, const int, const int);
810
811
812 /* line.c */
813 extern int line_points(int **, int **, int *,
814 const int, const int, const int, const int);
815
816 /* link.c */
817 extern int link_minutiae(MINUTIAE *, unsigned char *, const int, const int,
818 int *, const int, const int, const LFSPARMS *);
819 extern int create_link_table(int **, int **, int **, int *, int *, int *,
820 const int, const int, const MINUTIAE *, const int *,
821 int *, const int, const int, unsigned char *,
822 const int, const int, const LFSPARMS *);
823 extern int update_link_table(int *, int *, int *, int *, int *, int *,
824 const int, int *, int *, int *, int *,
825 const int, const int, const int);
826 extern int order_link_table(int *, int *, int *, const int, const int,
827 const int, const int, const MINUTIAE *, const int);
828 extern int process_link_table(const int *, const int *, const int *,
829 const int, const int, const int, const int, MINUTIAE *,
830 int *, unsigned char *, const int, const int,
831 const LFSPARMS *);
832 extern double link_score(const double, const double, const LFSPARMS *);
833
834 /* loop.c */
835 extern int get_loop_list(int **, MINUTIAE *, const int, unsigned char *,
836 const int, const int);
837 extern int on_loop(const MINUTIA *, const int, unsigned char *, const int,
838 const int);
839 extern int on_island_lake(int **, int **, int **, int **, int *,
840 const MINUTIA *, const MINUTIA *, const int,
841 unsigned char *, const int, const int);
842 extern int on_hook(const MINUTIA *, const MINUTIA *, const int,
843 unsigned char *, const int, const int);
844 extern int is_loop_clockwise(const int *, const int *, const int, const int);
845 extern int process_loop(MINUTIAE *, const int *, const int *,
846 const int *, const int *, const int,
847 unsigned char *, const int, const int, const LFSPARMS *);
848 extern int process_loop_V2(MINUTIAE *, const int *, const int *,
849 const int *, const int *, const int,
850 unsigned char *, const int, const int,
851 int *, const LFSPARMS *);
852 extern int fill_loop(const int *, const int *, const int,
853 unsigned char *, const int, const int);
854
855 /* maps.c */
856 extern int gen_image_maps(int **, int **, int **, int **, int *, int *,
857 unsigned char *, const int, const int,
858 const DIR2RAD *, const DFTWAVES *,
859 const ROTGRIDS *, const LFSPARMS *);
860 extern int gen_initial_maps(int **, int **, int **,
861 int *, const int, const int,
862 unsigned char *, const int, const int,
863 const DFTWAVES *, const ROTGRIDS *, const LFSPARMS *);
864 extern int interpolate_direction_map(int *, int *, const int, const int,
865 const LFSPARMS *);
866 extern int morph_TF_map(int *, const int, const int, const LFSPARMS *);
867 extern int pixelize_map(int **, const int, const int,
868 int *, const int, const int, const int);
869 extern void smooth_direction_map(int *, int *, const int, const int,
870 const DIR2RAD *, const LFSPARMS *);
871 extern int gen_high_curve_map(int **, int *, const int, const int,
872 const LFSPARMS *);
873 extern int gen_initial_imap(int **, int *, const int, const int,
874 unsigned char *, const int, const int,
875 const DFTWAVES *, const ROTGRIDS *, const LFSPARMS *);
876 extern int primary_dir_test(double **, const int *, const double *,
877 const int *, const double *, const int,
878 const LFSPARMS *);
879 extern int secondary_fork_test(double **, const int *, const double *,
880 const int *, const double *, const int,
881 const LFSPARMS *);
882 extern void remove_incon_dirs(int *, const int, const int,
883 const DIR2RAD *, const LFSPARMS *);
884 extern int test_top_edge(const int, const int, const int, const int,
885 int *, const int, const int, const DIR2RAD *,
886 const LFSPARMS *);
887 extern int test_right_edge(const int, const int, const int, const int,
888 int *, const int, const int, const DIR2RAD *,
889 const LFSPARMS *);
890 extern int test_bottom_edge(const int, const int, const int, const int,
891 int *, const int, const int, const DIR2RAD *,
892 const LFSPARMS *);
893 extern int test_left_edge(const int, const int, const int, const int,
894 int *, const int, const int, const DIR2RAD *,
895 const LFSPARMS *);
896 extern int remove_dir(int *, const int, const int, const int, const int,
897 const DIR2RAD *, const LFSPARMS *);
898 extern void average_8nbr_dir(int *, double *, int *, int *, const int,
899 const int, const int, const int, const DIR2RAD *);
900 extern int num_valid_8nbrs(int *, const int, const int, const int, const int);
901 extern void smooth_imap(int *, const int, const int, const DIR2RAD *,
902 const LFSPARMS *);
903 extern int vorticity(int *, const int, const int, const int, const int,
904 const int);
905 extern void accum_nbr_vorticity(int *, const int, const int, const int);
906 extern int curvature(int *, const int, const int, const int, const int,
907 const int);
908
909 /* matchpat.c */
910 extern int match_1st_pair(unsigned char, unsigned char, int *, int *);
911 extern int match_2nd_pair(unsigned char, unsigned char, int *, int *);
912 extern int match_3rd_pair(unsigned char, unsigned char, int *, int *);
913 extern void skip_repeated_horizontal_pair(int *, const int,
914 unsigned char **, unsigned char **, const int, const int);
915 extern void skip_repeated_vertical_pair(int *, const int,
916 unsigned char **, unsigned char **, const int, const int);
917
918 /* minutia.c */
919 extern int alloc_minutiae(MINUTIAE **, const int);
920 extern int realloc_minutiae(MINUTIAE *, const int);
921 extern int detect_minutiae_V2(MINUTIAE *,
922 unsigned char *, const int, const int,
923 int *, int *, int *, const int, const int,
924 const LFSPARMS *);
925 extern int update_minutiae(MINUTIAE *, MINUTIA *, unsigned char *,
926 const int, const int, const LFSPARMS *);
927 extern int update_minutiae_V2(MINUTIAE *, MINUTIA *, const int, const int,
928 unsigned char *, const int, const int,
929 const LFSPARMS *);
930 extern int sort_minutiae(MINUTIAE *, const int, const int);
931 extern int sort_minutiae_y_x(MINUTIAE *, const int, const int);
932 extern int sort_minutiae_x_y(MINUTIAE *, const int, const int);
933 extern int rm_dup_minutiae(MINUTIAE *);
934 extern void dump_minutiae(FILE *, const MINUTIAE *);
935 extern void dump_minutiae_pts(FILE *, const MINUTIAE *);
936 extern void dump_reliable_minutiae_pts(FILE *, const MINUTIAE *, const double);
937 extern int create_minutia(MINUTIA **, const int, const int,
938 const int, const int, const int, const double,
939 const int, const int, const int);
940 extern void free_minutiae(MINUTIAE *);
941 extern void free_minutia(MINUTIA *);
942 extern int remove_minutia(const int, MINUTIAE *);
943 extern int join_minutia(const MINUTIA *, const MINUTIA *, unsigned char *,
944 const int, const int, const int, const int);
945 extern int minutia_type(const int);
946 extern int is_minutia_appearing(const int, const int, const int, const int);
947 extern int choose_scan_direction(const int, const int);
948 int scan4minutiae(MINUTIAE *, unsigned char *, const int, const int,
949 const int *, const int *, const int, const int,
950 const int, const int, const int, const int,
951 const int, const int, const int, const LFSPARMS *);
952 extern int scan4minutiae_horizontally(MINUTIAE *, unsigned char *,
953 const int, const int, const int, const int,
954 const int, const int, const int, const int,
955 const LFSPARMS *);
956 extern int scan4minutiae_horizontally_V2(MINUTIAE *,
957 unsigned char *, const int, const int,
958 int *, int *, int *,
959 const LFSPARMS *);
960 extern int scan4minutiae_vertically(MINUTIAE *, unsigned char *,
961 const int, const int, const int, const int,
962 const int, const int, const int, const int,
963 const LFSPARMS *);
964 extern int rescan4minutiae_horizontally(MINUTIAE *, unsigned char *bdata,
965 const int, const int, const int *, const int *,
966 const int, const int, const int, const int,
967 const int, const int, const int, const int,
968 const LFSPARMS *);
969 extern int scan4minutiae_vertically_V2(MINUTIAE *,
970 unsigned char *, const int, const int,
971 int *, int *, int *, const LFSPARMS *);
972 extern int rescan4minutiae_vertically(MINUTIAE *, unsigned char *,
973 const int, const int, const int *, const int *,
974 const int, const int, const int, const int,
975 const int, const int, const int, const int,
976 const LFSPARMS *);
977 extern int rescan_partial_horizontally(const int, MINUTIAE *,
978 unsigned char *, const int, const int,
979 const int *, const int *,
980 const int, const int, const int, const int,
981 const int, const int, const int, const int,
982 const LFSPARMS *);
983 extern int rescan_partial_vertically(const int, MINUTIAE *,
984 unsigned char *, const int, const int,
985 const int *, const int *,
986 const int, const int, const int, const int,
987 const int, const int, const int, const int,
988 const LFSPARMS *);
989 extern int get_nbr_block_index(int *, const int, const int, const int,
990 const int, const int);
991 extern int adjust_horizontal_rescan(const int, int *, int *, int *, int *,
992 const int, const int, const int, const int, const int);
993 extern int adjust_vertical_rescan(const int, int *, int *, int *, int *,
994 const int, const int, const int, const int, const int);
995 extern int process_horizontal_scan_minutia(MINUTIAE *, const int, const int,
996 const int, const int,
997 unsigned char *, const int, const int,
998 const int, const int, const LFSPARMS *);
999 extern int process_horizontal_scan_minutia_V2(MINUTIAE *,
1000 const int, const int, const int, const int,
1001 unsigned char *, const int, const int,
1002 int *, int *, int *, const LFSPARMS *);
1003 extern int process_vertical_scan_minutia(MINUTIAE *, const int, const int,
1004 const int, const int,
1005 unsigned char *, const int, const int,
1006 const int, const int, const LFSPARMS *);
1007 extern int process_vertical_scan_minutia_V2(MINUTIAE *, const int, const int,
1008 const int, const int,
1009 unsigned char *, const int, const int,
1010 int *, int *, int *, const LFSPARMS *);
1011 extern int update_minutiae_V2(MINUTIAE *, MINUTIA *, const int, const int,
1012 unsigned char *, const int, const int,
1013 const LFSPARMS *);
1014 extern int adjust_high_curvature_minutia(int *, int *, int *, int *, int *,
1015 const int, const int, const int, const int,
1016 unsigned char *, const int, const int,
1017 MINUTIAE *, const LFSPARMS *);
1018 extern int adjust_high_curvature_minutia_V2(int *, int *, int *,
1019 int *, int *, const int, const int,
1020 const int, const int,
1021 unsigned char *, const int, const int,
1022 int *, MINUTIAE *, const LFSPARMS *);
1023 extern int get_low_curvature_direction(const int, const int, const int,
1024 const int);
1025
1026 /* quality.c */
1027 extern int gen_quality_map(int **, int *, int *, int *, int *,
1028 const int, const int);
1029 extern int combined_minutia_quality(MINUTIAE *, int *, const int, const int,
1030 const int, unsigned char *, const int, const int,
1031 const int, const double);
1032 double grayscale_reliability(MINUTIA *, unsigned char *,
1033 const int, const int, const int);
1034 extern void get_neighborhood_stats(double *, double *, MINUTIA *,
1035 unsigned char *, const int, const int, const int);
1036 extern int reliability_fr_quality_map(MINUTIAE *, int *, const int,
1037 const int, const int, const int, const int);
1038
1039 /* remove.c */
1040 extern int remove_false_minutia(MINUTIAE *,
1041 unsigned char *, const int, const int,
1042 int *, const int, const int, const LFSPARMS *);
1043 extern int remove_false_minutia_V2(MINUTIAE *,
1044 unsigned char *, const int, const int,
1045 int *, int *, int *, const int, const int,
1046 const LFSPARMS *);
1047
1048 /* ridges.c */
1049 extern int count_minutiae_ridges(MINUTIAE *,
1050 unsigned char *, const int, const int,
1051 const LFSPARMS *);
1052 extern int count_minutia_ridges(const int, MINUTIAE *,
1053 unsigned char *, const int, const int,
1054 const LFSPARMS *);
1055 extern int find_neighbors(int **, int *, const int, const int, MINUTIAE *);
1056 extern int update_nbr_dists(int *, double *, int *, const int,
1057 const int, const int, MINUTIAE *);
1058 extern int insert_neighbor(const int, const int, const double,
1059 int *, double *, int *, const int);
1060 extern int sort_neighbors(int *, const int, const int, MINUTIAE *);
1061 extern int ridge_count(const int, const int, MINUTIAE *,
1062 unsigned char *, const int, const int, const LFSPARMS *);
1063 extern int find_transition(int *, const int, const int,
1064 const int *, const int *, const int,
1065 unsigned char *, const int, const int);
1066 extern int validate_ridge_crossing(const int, const int,
1067 const int *, const int *, const int,
1068 unsigned char *, const int, const int, const int);
1069
1070 /* shape.c */
1071 extern void free_shape(SHAPE *);
1072 extern int shape_from_contour(SHAPE **, const int *, const int *, const int);
1073
1074 /* sort.c */
1075 extern int sort_indices_int_inc(int **, int *, const int);
1076 extern int sort_indices_double_inc(int **, double *, const int);
1077 extern void bubble_sort_int_inc_2(int *, int *, const int);
1078 extern void bubble_sort_double_inc_2(double *, int *, const int);
1079 extern void bubble_sort_double_dec_2(double *, int *, const int);
1080 extern void bubble_sort_int_inc(int *, const int);
1081
1082 /* util.c */
1083 extern int maxv(const int *, const int);
1084 extern int minv(const int *, const int);
1085 extern int minmaxs(int **, int **, int **, int *, int *,
1086 const int *, const int);
1087 extern double distance(const int, const int, const int, const int);
1088 extern double squared_distance(const int, const int, const int, const int);
1089 extern int in_int_list(const int, const int *, const int);
1090 extern int remove_from_int_list(const int, int *, const int);
1091 extern int find_incr_position_dbl(const double, double *, const int);
1092 extern double angle2line(const int, const int, const int, const int);
1093 extern int line2direction(const int, const int, const int, const int,
1094 const int);
1095 extern int closest_dir_dist(const int, const int, const int);
1096
1097 /* xytreps.c */
1098 extern void lfs2nist_minutia_XYT(int *, int *, int *,
1099 const MINUTIA *, const int, const int);
1100 extern void lfs2m1_minutia_XYT(int *, int *, int *, const MINUTIA *);
1101
1102
1103 /*************************************************************************/
1104 /* EXTERNAL GLOBAL VARIABLE DEFINITIONS */
1105 /*************************************************************************/
1106 extern double dft_coefs[];
1107 extern LFSPARMS lfsparms;
1108 extern LFSPARMS lfsparms_V2;
1109 extern int nbr8_dx[];
1110 extern int nbr8_dy[];
1111 extern int chaincodes_nbr8[];
1112 extern FEATURE_PATTERN feature_patterns[];
1113
1114 #endif
Library for fingerprint scanning and recognition