libfprint/nbis/mindtct/matchpat.c
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /******************************************************************************* | ||
| 2 | |||
| 3 | License: | ||
| 4 | This software and/or related materials was developed at the National Institute | ||
| 5 | of Standards and Technology (NIST) by employees of the Federal Government | ||
| 6 | in the course of their official duties. Pursuant to title 17 Section 105 | ||
| 7 | of the United States Code, this software is not subject to copyright | ||
| 8 | protection and is in the public domain. | ||
| 9 | |||
| 10 | This software and/or related materials have been determined to be not subject | ||
| 11 | to the EAR (see Part 734.3 of the EAR for exact details) because it is | ||
| 12 | a publicly available technology and software, and is freely distributed | ||
| 13 | to any interested party with no licensing requirements. Therefore, it is | ||
| 14 | permissible to distribute this software as a free download from the internet. | ||
| 15 | |||
| 16 | Disclaimer: | ||
| 17 | This software and/or related materials was developed to promote biometric | ||
| 18 | standards and biometric technology testing for the Federal Government | ||
| 19 | in accordance with the USA PATRIOT Act and the Enhanced Border Security | ||
| 20 | and Visa Entry Reform Act. Specific hardware and software products identified | ||
| 21 | in this software were used in order to perform the software development. | ||
| 22 | In no case does such identification imply recommendation or endorsement | ||
| 23 | by the National Institute of Standards and Technology, nor does it imply that | ||
| 24 | the products and equipment identified are necessarily the best available | ||
| 25 | for the purpose. | ||
| 26 | |||
| 27 | This software and/or related materials are provided "AS-IS" without warranty | ||
| 28 | of any kind including NO WARRANTY OF PERFORMANCE, MERCHANTABILITY, | ||
| 29 | NO WARRANTY OF NON-INFRINGEMENT OF ANY 3RD PARTY INTELLECTUAL PROPERTY | ||
| 30 | or FITNESS FOR A PARTICULAR PURPOSE or for any purpose whatsoever, for the | ||
| 31 | licensed product, however used. In no event shall NIST be liable for any | ||
| 32 | damages and/or costs, including but not limited to incidental or consequential | ||
| 33 | damages of any kind, including economic damage or injury to property and lost | ||
| 34 | profits, regardless of whether NIST shall be advised, have reason to know, | ||
| 35 | or in fact shall know of the possibility. | ||
| 36 | |||
| 37 | By using this software, you agree to bear all risk relating to quality, | ||
| 38 | use and performance of the software and/or related materials. You agree | ||
| 39 | to hold the Government harmless from any claim arising from your use | ||
| 40 | of the software. | ||
| 41 | |||
| 42 | *******************************************************************************/ | ||
| 43 | |||
| 44 | |||
| 45 | /*********************************************************************** | ||
| 46 | LIBRARY: LFS - NIST Latent Fingerprint System | ||
| 47 | |||
| 48 | FILE: MATCHPAT.C | ||
| 49 | AUTHOR: Michael D. Garris | ||
| 50 | DATE: 05/11/1999 | ||
| 51 | UPDATED: 03/16/2005 by MDG | ||
| 52 | |||
| 53 | Contains routines responsible for matching minutia feature | ||
| 54 | patterns as part of the NIST Latent Fingerprint System (LFS). | ||
| 55 | |||
| 56 | *********************************************************************** | ||
| 57 | ROUTINES: | ||
| 58 | match_1st_pair() | ||
| 59 | match_2nd_pair() | ||
| 60 | match_3rd_pair() | ||
| 61 | skip_repeated_horizontal_pair() | ||
| 62 | skip_repeated_vertical_pair() | ||
| 63 | ***********************************************************************/ | ||
| 64 | |||
| 65 | #include <stdio.h> | ||
| 66 | #include <lfs.h> | ||
| 67 | |||
| 68 | /************************************************************************* | ||
| 69 | ************************************************************************** | ||
| 70 | #cat: match_1st_pair - Determines which of the g_feature_patterns[] have their | ||
| 71 | #cat: first pixel pair match the specified pixel pair. | ||
| 72 | |||
| 73 | Input: | ||
| 74 | p1 - first pixel value of pair | ||
| 75 | p2 - second pixel value of pair | ||
| 76 | Output: | ||
| 77 | possible - list of matching g_feature_patterns[] indices | ||
| 78 | nposs - number of matches | ||
| 79 | Return Code: | ||
| 80 | nposs - number of matches | ||
| 81 | *************************************************************************/ | ||
| 82 | 5608781 | int match_1st_pair(unsigned char p1, unsigned char p2, | |
| 83 | int *possible, int *nposs) | ||
| 84 | { | ||
| 85 | 5608781 | int i; | |
| 86 | |||
| 87 | /* Set possibilities to 0 */ | ||
| 88 | 5608781 | *nposs = 0; | |
| 89 | |||
| 90 | /* Foreach set of feature pairs ... */ | ||
| 91 |
2/2✓ Branch 7 → 3 taken 56087810 times.
✓ Branch 7 → 8 taken 5608781 times.
|
61696591 | for(i = 0; i < NFEATURES; i++){ |
| 92 | /* If current scan pair matches first pair for feature ... */ | ||
| 93 |
2/2✓ Branch 3 → 4 taken 26667060 times.
✓ Branch 3 → 6 taken 29420750 times.
|
56087810 | if((p1==g_feature_patterns[i].first[0]) && |
| 94 |
2/2✓ Branch 4 → 5 taken 15449104 times.
✓ Branch 4 → 6 taken 11217956 times.
|
26667060 | (p2==g_feature_patterns[i].first[1])){ |
| 95 | /* Store feature as a possible match. */ | ||
| 96 | 15449104 | possible[*nposs] = i; | |
| 97 | /* Bump number of stored possibilities. */ | ||
| 98 | 15449104 | (*nposs)++; | |
| 99 | } | ||
| 100 | } | ||
| 101 | |||
| 102 | /* Return number of stored possibilities. */ | ||
| 103 | 5608781 | return(*nposs); | |
| 104 | } | ||
| 105 | |||
| 106 | /************************************************************************* | ||
| 107 | ************************************************************************** | ||
| 108 | #cat: match_2nd_pair - Determines which of the passed g_feature_patterns[] have | ||
| 109 | #cat: their second pixel pair match the specified pixel pair. | ||
| 110 | |||
| 111 | Input: | ||
| 112 | p1 - first pixel value of pair | ||
| 113 | p2 - second pixel value of pair | ||
| 114 | possible - list of potentially-matching g_feature_patterns[] indices | ||
| 115 | nposs - number of potential matches | ||
| 116 | Output: | ||
| 117 | possible - list of matching g_feature_patterns[] indices | ||
| 118 | nposs - number of matches | ||
| 119 | Return Code: | ||
| 120 | nposs - number of matches | ||
| 121 | *************************************************************************/ | ||
| 122 | 5582934 | int match_2nd_pair(unsigned char p1, unsigned char p2, | |
| 123 | int *possible, int *nposs) | ||
| 124 | { | ||
| 125 | 5582934 | int i; | |
| 126 | 5582934 | int tnposs; | |
| 127 | |||
| 128 | /* Store input possibilities. */ | ||
| 129 | 5582934 | tnposs = *nposs; | |
| 130 | /* Reset output possibilities to 0. */ | ||
| 131 | 5582934 | *nposs = 0; | |
| 132 | |||
| 133 | /* If current scan pair values are the same ... */ | ||
| 134 |
2/2✓ Branch 2 → 7 taken 538186 times.
✓ Branch 2 → 9 taken 5044748 times.
|
5582934 | if(p1 == p2) |
| 135 | /* Simply return because pair can't be a second feature pair. */ | ||
| 136 | return(*nposs); | ||
| 137 | |||
| 138 | /* Foreach possible match based on first pair ... */ | ||
| 139 |
2/2✓ Branch 7 → 3 taken 1609978 times.
✓ Branch 7 → 8 taken 538186 times.
|
2148164 | for(i = 0; i < tnposs; i++){ |
| 140 | /* If current scan pair matches second pair for feature ... */ | ||
| 141 |
2/2✓ Branch 3 → 4 taken 805344 times.
✓ Branch 3 → 6 taken 804634 times.
|
1609978 | if((p1==g_feature_patterns[possible[i]].second[0]) && |
| 142 |
1/2✓ Branch 4 → 5 taken 805344 times.
✗ Branch 4 → 6 not taken.
|
805344 | (p2==g_feature_patterns[possible[i]].second[1])){ |
| 143 | /* Store feature as a possible match. */ | ||
| 144 | 805344 | possible[*nposs] = possible[i]; | |
| 145 | /* Bump number of stored possibilities. */ | ||
| 146 | 805344 | (*nposs)++; | |
| 147 | } | ||
| 148 | } | ||
| 149 | |||
| 150 | /* Return number of stored possibilities. */ | ||
| 151 | 538186 | return(*nposs); | |
| 152 | } | ||
| 153 | |||
| 154 | /************************************************************************* | ||
| 155 | ************************************************************************** | ||
| 156 | #cat: match_3rd_pair - Determines which of the passed g_feature_patterns[] have | ||
| 157 | #cat: their third pixel pair match the specified pixel pair. | ||
| 158 | |||
| 159 | Input: | ||
| 160 | p1 - first pixel value of pair | ||
| 161 | p2 - second pixel value of pair | ||
| 162 | possible - list of potentially-matching g_feature_patterns[] indices | ||
| 163 | nposs - number of potential matches | ||
| 164 | Output: | ||
| 165 | possible - list of matching g_feature_patterns[] indices | ||
| 166 | nposs - number of matches | ||
| 167 | Return Code: | ||
| 168 | nposs - number of matches | ||
| 169 | *************************************************************************/ | ||
| 170 | 538186 | int match_3rd_pair(unsigned char p1, unsigned char p2, | |
| 171 | int *possible, int *nposs) | ||
| 172 | { | ||
| 173 | 538186 | int i; | |
| 174 | 538186 | int tnposs; | |
| 175 | |||
| 176 | /* Store input possibilities. */ | ||
| 177 | 538186 | tnposs = *nposs; | |
| 178 | /* Reset output possibilities to 0. */ | ||
| 179 | 538186 | *nposs = 0; | |
| 180 | |||
| 181 | /* Foreach possible match based on first and second pairs ... */ | ||
| 182 |
2/2✓ Branch 7 → 3 taken 805344 times.
✓ Branch 7 → 8 taken 538186 times.
|
1343530 | for(i = 0; i < tnposs; i++){ |
| 183 | /* If current scan pair matches third pair for feature ... */ | ||
| 184 |
2/2✓ Branch 3 → 4 taken 181741 times.
✓ Branch 3 → 6 taken 623603 times.
|
805344 | if((p1==g_feature_patterns[possible[i]].third[0]) && |
| 185 |
2/2✓ Branch 4 → 5 taken 56077 times.
✓ Branch 4 → 6 taken 125664 times.
|
181741 | (p2==g_feature_patterns[possible[i]].third[1])){ |
| 186 | /* Store feature as a possible match. */ | ||
| 187 | 56077 | possible[*nposs] = possible[i]; | |
| 188 | /* Bump number of stored possibilities. */ | ||
| 189 | 56077 | (*nposs)++; | |
| 190 | } | ||
| 191 | } | ||
| 192 | |||
| 193 | /* Return number of stored possibilities. */ | ||
| 194 | 538186 | return(*nposs); | |
| 195 | } | ||
| 196 | |||
| 197 | /************************************************************************* | ||
| 198 | ************************************************************************** | ||
| 199 | #cat: skip_repeated_horizontal_pair - Takes the location of two pixel in | ||
| 200 | #cat: adjacent pixel rows within an image region and skips | ||
| 201 | #cat: rightward until the either the pixel pair no longer repeats | ||
| 202 | #cat: itself or the image region is exhausted. | ||
| 203 | |||
| 204 | Input: | ||
| 205 | cx - current x-coord of starting pixel pair | ||
| 206 | ex - right edge of the image region | ||
| 207 | p1ptr - pointer to current top pixel in pair | ||
| 208 | p2ptr - pointer to current bottom pixel in pair | ||
| 209 | iw - width (in pixels) of image | ||
| 210 | ih - height (in pixels) of image | ||
| 211 | Output: | ||
| 212 | cx - x-coord of where rightward skip terminated | ||
| 213 | p1ptr - points to top pixel where rightward skip terminated | ||
| 214 | p2ptr - points to bottom pixel where rightward skip terminated | ||
| 215 | *************************************************************************/ | ||
| 216 | 269201 | void skip_repeated_horizontal_pair(int *cx, const int ex, | |
| 217 | unsigned char **p1ptr, unsigned char **p2ptr, | ||
| 218 | const int iw, const int ih) | ||
| 219 | { | ||
| 220 | 269201 | int old1, old2; | |
| 221 | |||
| 222 | /* Store starting pixel pair. */ | ||
| 223 | 269201 | old1 = **p1ptr; | |
| 224 | 269201 | old2 = **p2ptr; | |
| 225 | |||
| 226 | /* Bump horizontally to next pixel pair. */ | ||
| 227 | 269201 | (*cx)++; | |
| 228 | 269201 | (*p1ptr)++; | |
| 229 | 269201 | (*p2ptr)++; | |
| 230 | |||
| 231 | /* While not at right of scan region... */ | ||
| 232 |
1/2✓ Branch 6 → 3 taken 548272 times.
✗ Branch 6 → 7 not taken.
|
548272 | while(*cx < ex){ |
| 233 | /* If one or the other pixels in the new pair are different */ | ||
| 234 | /* from the starting pixel pair... */ | ||
| 235 |
4/4✓ Branch 3 → 4 taken 421151 times.
✓ Branch 3 → 7 taken 127121 times.
✓ Branch 4 → 5 taken 279071 times.
✓ Branch 4 → 7 taken 142080 times.
|
548272 | if((**p1ptr != old1) || (**p2ptr != old2)) |
| 236 | /* Done skipping repreated pixel pairs. */ | ||
| 237 | return; | ||
| 238 | /* Otherwise, bump horizontally to next pixel pair. */ | ||
| 239 | 279071 | (*cx)++; | |
| 240 | 279071 | (*p1ptr)++; | |
| 241 | 279071 | (*p2ptr)++; | |
| 242 | } | ||
| 243 | } | ||
| 244 | |||
| 245 | /************************************************************************* | ||
| 246 | ************************************************************************** | ||
| 247 | #cat: skip_repeated_vertical_pair - Takes the location of two pixel in | ||
| 248 | #cat: adjacent pixel columns within an image region and skips | ||
| 249 | #cat: downward until the either the pixel pair no longer repeats | ||
| 250 | #cat: itself or the image region is exhausted. | ||
| 251 | |||
| 252 | Input: | ||
| 253 | cy - current y-coord of starting pixel pair | ||
| 254 | ey - bottom of the image region | ||
| 255 | p1ptr - pointer to current left pixel in pair | ||
| 256 | p2ptr - pointer to current right pixel in pair | ||
| 257 | iw - width (in pixels) of image | ||
| 258 | ih - height (in pixels) of image | ||
| 259 | Output: | ||
| 260 | cy - y-coord of where downward skip terminated | ||
| 261 | p1ptr - points to left pixel where downward skip terminated | ||
| 262 | p2ptr - points to right pixel where donward skip terminated | ||
| 263 | *************************************************************************/ | ||
| 264 | 268985 | void skip_repeated_vertical_pair(int *cy, const int ey, | |
| 265 | unsigned char **p1ptr, unsigned char **p2ptr, | ||
| 266 | const int iw, const int ih) | ||
| 267 | { | ||
| 268 | 268985 | int old1, old2; | |
| 269 | |||
| 270 | /* Store starting pixel pair. */ | ||
| 271 | 268985 | old1 = **p1ptr; | |
| 272 | 268985 | old2 = **p2ptr; | |
| 273 | |||
| 274 | /* Bump vertically to next pixel pair. */ | ||
| 275 | 268985 | (*cy)++; | |
| 276 | 268985 | (*p1ptr)+=iw; | |
| 277 | 268985 | (*p2ptr)+=iw; | |
| 278 | |||
| 279 | /* While not at bottom of scan region... */ | ||
| 280 |
1/2✓ Branch 6 → 3 taken 440549 times.
✗ Branch 6 → 7 not taken.
|
440549 | while(*cy < ey){ |
| 281 | /* If one or the other pixels in the new pair are different */ | ||
| 282 | /* from the starting pixel pair... */ | ||
| 283 |
4/4✓ Branch 3 → 4 taken 313454 times.
✓ Branch 3 → 7 taken 127095 times.
✓ Branch 4 → 5 taken 171564 times.
✓ Branch 4 → 7 taken 141890 times.
|
440549 | if((**p1ptr != old1) || (**p2ptr != old2)) |
| 284 | /* Done skipping repreated pixel pairs. */ | ||
| 285 | return; | ||
| 286 | /* Otherwise, bump vertically to next pixel pair. */ | ||
| 287 | 171564 | (*cy)++; | |
| 288 | 171564 | (*p1ptr)+=iw; | |
| 289 | 171564 | (*p2ptr)+=iw; | |
| 290 | } | ||
| 291 | } | ||
| 292 | |||
| 293 |