| 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: BINAR.C | ||
| 49 | AUTHOR: Michael D. Garris | ||
| 50 | DATE: 03/16/1999 | ||
| 51 | UPDATED: 10/04/1999 Version 2 by MDG | ||
| 52 | UPDATED: 03/16/2005 by MDG | ||
| 53 | |||
| 54 | Contains routines responsible for binarizing a grayscale image based | ||
| 55 | on an arbitrarily-sized image and its precomputed direcitonal ridge | ||
| 56 | flow (IMAP) as part of the NIST Latent Fingerprint System (LFS). | ||
| 57 | |||
| 58 | *********************************************************************** | ||
| 59 | ROUTINES: | ||
| 60 | binarize() | ||
| 61 | binarize_V2() | ||
| 62 | binarize_image() | ||
| 63 | binarize_image_V2() | ||
| 64 | dirbinarize() | ||
| 65 | isobinarize() | ||
| 66 | |||
| 67 | ***********************************************************************/ | ||
| 68 | |||
| 69 | #include <stdio.h> | ||
| 70 | #include <lfs.h> | ||
| 71 | |||
| 72 | /************************************************************************* | ||
| 73 | ************************************************************************** | ||
| 74 | #cat: binarize - Takes a padded grayscale input image and its associated ridge | ||
| 75 | #cat: direction flow NMAP and produces a binarized version of the | ||
| 76 | #cat: image. It then fills horizontal and vertical "holes" in the | ||
| 77 | #cat: binary image results. | ||
| 78 | |||
| 79 | Input: | ||
| 80 | pdata - padded input grayscale image | ||
| 81 | pw - padded width (in pixels) of input image | ||
| 82 | ph - padded height (in pixels) of input image | ||
| 83 | nmap - 2-D vector of IMAP directions and other codes | ||
| 84 | mw - width (in blocks) of the NMAP | ||
| 85 | mh - height (in blocks) of the NMAP | ||
| 86 | dirbingrids - set of rotated grid offsets used for directional | ||
| 87 | binarization | ||
| 88 | lfsparms - parameters and thresholds for controlling LFS | ||
| 89 | Output: | ||
| 90 | optr - points to created (unpadded) binary image | ||
| 91 | ow - width of binary image | ||
| 92 | oh - height of binary image | ||
| 93 | Return Code: | ||
| 94 | Zero - successful completion | ||
| 95 | Negative - system error | ||
| 96 | **************************************************************************/ | ||
| 97 | |||
| 98 | /************************************************************************* | ||
| 99 | ************************************************************************** | ||
| 100 | #cat: binarize_V2 - Takes a padded grayscale input image and its associated | ||
| 101 | #cat: Direction Map and produces a binarized version of the | ||
| 102 | #cat: image. It then fills horizontal and vertical "holes" in | ||
| 103 | #cat: the binary image results. Note that the input image must | ||
| 104 | #cat: be padded sufficiently to contain in memory rotated | ||
| 105 | #cat: directional binarization grids applied to pixels along the | ||
| 106 | #cat: perimeter of the input image. | ||
| 107 | |||
| 108 | Input: | ||
| 109 | pdata - padded input grayscale image | ||
| 110 | pw - padded width (in pixels) of input image | ||
| 111 | ph - padded height (in pixels) of input image | ||
| 112 | direction_map - 2-D vector of discrete ridge flow directions | ||
| 113 | mw - width (in blocks) of the map | ||
| 114 | mh - height (in blocks) of the map | ||
| 115 | dirbingrids - set of rotated grid offsets used for directional | ||
| 116 | binarization | ||
| 117 | lfsparms - parameters and thresholds for controlling LFS | ||
| 118 | Output: | ||
| 119 | odata - points to created (unpadded) binary image | ||
| 120 | ow - width of binary image | ||
| 121 | oh - height of binary image | ||
| 122 | Return Code: | ||
| 123 | Zero - successful completion | ||
| 124 | Negative - system error | ||
| 125 | **************************************************************************/ | ||
| 126 | 48 | int binarize_V2(unsigned char **odata, int *ow, int *oh, | |
| 127 | unsigned char *pdata, const int pw, const int ph, | ||
| 128 | int *direction_map, const int mw, const int mh, | ||
| 129 | const ROTGRIDS *dirbingrids, const LFSPARMS *lfsparms) | ||
| 130 | { | ||
| 131 | 48 | unsigned char *bdata; | |
| 132 | 48 | int i, bw, bh, ret; /* return code */ | |
| 133 | |||
| 134 | /* 1. Binarize the padded input image using directional block info. */ | ||
| 135 |
1/2✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
|
48 | if((ret = binarize_image_V2(&bdata, &bw, &bh, pdata, pw, ph, |
| 136 | direction_map, mw, mh, | ||
| 137 | 48 | lfsparms->blocksize, dirbingrids))){ | |
| 138 | return(ret); | ||
| 139 | } | ||
| 140 | |||
| 141 | /* 2. Fill black and white holes in binary image. */ | ||
| 142 | /* LFS scans the binary image, filling holes, 3 times. */ | ||
| 143 |
2/2✓ Branch 0 taken 144 times.
✓ Branch 1 taken 48 times.
|
192 | for(i = 0; i < lfsparms->num_fill_holes; i++) |
| 144 | 144 | fill_holes(bdata, bw, bh); | |
| 145 | |||
| 146 | /* Return binarized input image. */ | ||
| 147 | 48 | *odata = bdata; | |
| 148 | 48 | *ow = bw; | |
| 149 | 48 | *oh = bh; | |
| 150 | 48 | return(0); | |
| 151 | } | ||
| 152 | |||
| 153 | /************************************************************************* | ||
| 154 | ************************************************************************** | ||
| 155 | #cat: binarize_image - Takes a grayscale input image and its associated | ||
| 156 | #cat: NMAP and generates a binarized version of the image. | ||
| 157 | |||
| 158 | Input: | ||
| 159 | pdata - padded input grayscale image | ||
| 160 | pw - padded width (in pixels) of input image | ||
| 161 | ph - padded height (in pixels) of input image | ||
| 162 | nmap - 2-D vector of IMAP directions and other codes | ||
| 163 | mw - width (in blocks) of the NMAP | ||
| 164 | mh - height (in blocks) of the NMAP | ||
| 165 | imap_blocksize - dimension (in pixels) of each NMAP block | ||
| 166 | dirbingrids - set of rotated grid offsets used for directional | ||
| 167 | binarization | ||
| 168 | isobin_grid_dim - dimension (in pixels) of grid used for isotropic | ||
| 169 | binarization | ||
| 170 | Output: | ||
| 171 | optr - points to binary image results | ||
| 172 | ow - points to binary image width | ||
| 173 | oh - points to binary image height | ||
| 174 | Return Code: | ||
| 175 | Zero - successful completion | ||
| 176 | Negative - system error | ||
| 177 | **************************************************************************/ | ||
| 178 | |||
| 179 | /************************************************************************* | ||
| 180 | ************************************************************************** | ||
| 181 | #cat: binarize_image_V2 - Takes a grayscale input image and its associated | ||
| 182 | #cat: Direction Map and generates a binarized version of the | ||
| 183 | #cat: image. Note that there is no "Isotropic" binarization | ||
| 184 | #cat: used in this version. | ||
| 185 | |||
| 186 | Input: | ||
| 187 | pdata - padded input grayscale image | ||
| 188 | pw - padded width (in pixels) of input image | ||
| 189 | ph - padded height (in pixels) of input image | ||
| 190 | direction_map - 2-D vector of discrete ridge flow directions | ||
| 191 | mw - width (in blocks) of the map | ||
| 192 | mh - height (in blocks) of the map | ||
| 193 | blocksize - dimension (in pixels) of each NMAP block | ||
| 194 | dirbingrids - set of rotated grid offsets used for directional | ||
| 195 | binarization | ||
| 196 | Output: | ||
| 197 | odata - points to binary image results | ||
| 198 | ow - points to binary image width | ||
| 199 | oh - points to binary image height | ||
| 200 | Return Code: | ||
| 201 | Zero - successful completion | ||
| 202 | Negative - system error | ||
| 203 | **************************************************************************/ | ||
| 204 | 48 | int binarize_image_V2(unsigned char **odata, int *ow, int *oh, | |
| 205 | unsigned char *pdata, const int pw, const int ph, | ||
| 206 | const int *direction_map, const int mw, const int mh, | ||
| 207 | const int blocksize, const ROTGRIDS *dirbingrids) | ||
| 208 | { | ||
| 209 | 48 | int ix, iy, bw, bh, bx, by, mapval; | |
| 210 | 48 | unsigned char *bdata, *bptr; | |
| 211 | 48 | unsigned char *pptr, *spptr; | |
| 212 | |||
| 213 | /* Compute dimensions of "unpadded" binary image results. */ | ||
| 214 | 48 | bw = pw - (dirbingrids->pad<<1); | |
| 215 | 48 | bh = ph - (dirbingrids->pad<<1); | |
| 216 | |||
| 217 | 48 | bdata = (unsigned char *)g_malloc(bw * bh * sizeof(unsigned char)); | |
| 218 | |||
| 219 | 48 | bptr = bdata; | |
| 220 | 48 | spptr = pdata + (dirbingrids->pad * pw) + dirbingrids->pad; | |
| 221 |
2/2✓ Branch 0 taken 13261 times.
✓ Branch 1 taken 48 times.
|
13309 | for(iy = 0; iy < bh; iy++){ |
| 222 | /* Set pixel pointer to start of next row in grid. */ | ||
| 223 | pptr = spptr; | ||
| 224 |
2/2✓ Branch 0 taken 3191596 times.
✓ Branch 1 taken 13261 times.
|
3204857 | for(ix = 0; ix < bw; ix++){ |
| 225 | |||
| 226 | /* Compute which block the current pixel is in. */ | ||
| 227 | 3191596 | bx = (int)(ix/blocksize); | |
| 228 | 3191596 | by = (int)(iy/blocksize); | |
| 229 | /* Get corresponding value in Direction Map. */ | ||
| 230 | 3191596 | mapval = *(direction_map + (by*mw) + bx); | |
| 231 | /* If current block has has INVALID direction ... */ | ||
| 232 |
2/2✓ Branch 0 taken 697516 times.
✓ Branch 1 taken 2494080 times.
|
3191596 | if(mapval == INVALID_DIR) |
| 233 | /* Set binary pixel to white (255). */ | ||
| 234 | 697516 | *bptr = WHITE_PIXEL; | |
| 235 | /* Otherwise, if block has a valid direction ... */ | ||
| 236 | else /*if(mapval >= 0)*/ | ||
| 237 | /* Use directional binarization based on block's direction. */ | ||
| 238 | 2494080 | *bptr = dirbinarize(pptr, mapval, dirbingrids); | |
| 239 | |||
| 240 | /* Bump input and output pixel pointers. */ | ||
| 241 | 3191596 | pptr++; | |
| 242 | 3191596 | bptr++; | |
| 243 | } | ||
| 244 | /* Bump pointer to the next row in padded input image. */ | ||
| 245 | 13261 | spptr += pw; | |
| 246 | } | ||
| 247 | |||
| 248 | 48 | *odata = bdata; | |
| 249 | 48 | *ow = bw; | |
| 250 | 48 | *oh = bh; | |
| 251 | 48 | return(0); | |
| 252 | } | ||
| 253 | |||
| 254 | /************************************************************************* | ||
| 255 | ************************************************************************** | ||
| 256 | #cat: dirbinarize - Determines the binary value of a grayscale pixel based | ||
| 257 | #cat: on a VALID IMAP ridge flow direction. | ||
| 258 | |||
| 259 | CAUTION: The image to which the input pixel points must be appropriately | ||
| 260 | padded to account for the radius of the rotated grid. Otherwise, | ||
| 261 | this routine may access "unkown" memory. | ||
| 262 | |||
| 263 | Input: | ||
| 264 | pptr - pointer to current grayscale pixel | ||
| 265 | idir - IMAP integer direction associated with the block the | ||
| 266 | current is in | ||
| 267 | dirbingrids - set of precomputed rotated grid offsets | ||
| 268 | Return Code: | ||
| 269 | BLACK_PIXEL - pixel intensity for BLACK | ||
| 270 | WHITE_PIXEL - pixel intensity of WHITE | ||
| 271 | **************************************************************************/ | ||
| 272 | 2494080 | int dirbinarize(const unsigned char *pptr, const int idir, | |
| 273 | const ROTGRIDS *dirbingrids) | ||
| 274 | { | ||
| 275 | 2494080 | int gx, gy, gi, cy; | |
| 276 | 2494080 | int rsum, gsum, csum = 0; | |
| 277 | 2494080 | int *grid; | |
| 278 | 2494080 | double dcy; | |
| 279 | |||
| 280 | /* Assign nickname pointer. */ | ||
| 281 | 2494080 | grid = dirbingrids->grids[idir]; | |
| 282 | /* Calculate center (0-oriented) row in grid. */ | ||
| 283 | 2494080 | dcy = (dirbingrids->grid_h-1)/(double)2.0; | |
| 284 | /* Need to truncate precision so that answers are consistent */ | ||
| 285 | /* on different computer architectures when rounding doubles. */ | ||
| 286 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 2494080 times.
|
2494080 | dcy = trunc_dbl_precision(dcy, TRUNC_SCALE); |
| 287 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 2494080 times.
|
2494080 | cy = sround(dcy); |
| 288 | /* Initialize grid's pixel offset index to zero. */ | ||
| 289 | 2494080 | gi = 0; | |
| 290 | /* Initialize grid's pixel accumulator to zero */ | ||
| 291 | 2494080 | gsum = 0; | |
| 292 | |||
| 293 | /* Foreach row in grid ... */ | ||
| 294 |
2/2✓ Branch 0 taken 22446720 times.
✓ Branch 1 taken 2494080 times.
|
24940800 | for(gy = 0; gy < dirbingrids->grid_h; gy++){ |
| 295 | /* Initialize row pixel sum to zero. */ | ||
| 296 | rsum = 0; | ||
| 297 | /* Foreach column in grid ... */ | ||
| 298 |
2/2✓ Branch 0 taken 157127040 times.
✓ Branch 1 taken 22446720 times.
|
179573760 | for(gx = 0; gx < dirbingrids->grid_w; gx++){ |
| 299 | /* Accumulate next pixel along rotated row in grid. */ | ||
| 300 | 157127040 | rsum += *(pptr+grid[gi]); | |
| 301 | /* Bump grid's pixel offset index. */ | ||
| 302 | 157127040 | gi++; | |
| 303 | } | ||
| 304 | /* Accumulate row sum into grid pixel sum. */ | ||
| 305 | 22446720 | gsum += rsum; | |
| 306 | /* If current row is center row, then save row sum separately. */ | ||
| 307 |
2/2✓ Branch 0 taken 2494080 times.
✓ Branch 1 taken 19952640 times.
|
22446720 | if(gy == cy) |
| 308 | 2494080 | csum = rsum; | |
| 309 | } | ||
| 310 | |||
| 311 | /* If the center row sum treated as an average is less than the */ | ||
| 312 | /* total pixel sum in the rotated grid ... */ | ||
| 313 |
2/2✓ Branch 0 taken 1199374 times.
✓ Branch 1 taken 1294706 times.
|
2494080 | if((csum * dirbingrids->grid_h) < gsum) |
| 314 | /* Set the binary pixel to BLACK. */ | ||
| 315 | return(BLACK_PIXEL); | ||
| 316 | else | ||
| 317 | /* Otherwise set the binary pixel to WHITE. */ | ||
| 318 | 1199374 | return(WHITE_PIXEL); | |
| 319 | } | ||
| 320 | |||
| 321 | /************************************************************************* | ||
| 322 | ************************************************************************** | ||
| 323 | #cat: isobinarize - Determines the binary value of a grayscale pixel based | ||
| 324 | #cat: on comparing the grayscale value with a surrounding | ||
| 325 | #cat: neighborhood grid of pixels. If the current pixel (treated | ||
| 326 | #cat: as an average) is less than the sum of the pixels in | ||
| 327 | #cat: the neighborhood, then the binary value is set to BLACK, | ||
| 328 | #cat: otherwise it is set to WHITE. This binarization technique | ||
| 329 | #cat: is used when there is no VALID IMAP direction for the | ||
| 330 | #cat: block in which the current pixel resides. | ||
| 331 | |||
| 332 | CAUTION: The image to which the input pixel points must be appropriately | ||
| 333 | padded to account for the radius of the neighborhood. Otherwise, | ||
| 334 | this routine may access "unkown" memory. | ||
| 335 | |||
| 336 | Input: | ||
| 337 | pptr - pointer to curent grayscale pixel | ||
| 338 | pw - padded width (in pixels) of the grayscale image | ||
| 339 | ph - padded height (in pixels) of the grayscale image | ||
| 340 | isobin_grid_dim - dimension (in pixels) of the neighborhood | ||
| 341 | Return Code: | ||
| 342 | BLACK_PIXEL - pixel intensity for BLACK | ||
| 343 | WHITE_PIXEL - pixel intensity of WHITE | ||
| 344 | **************************************************************************/ | ||
| 345 |