| 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: BLOCK.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 partitioning arbitrarily- | ||
| 55 | sized images into equally-sized blocks as part of the NIST | ||
| 56 | Latent Fingerprint System (LFS). | ||
| 57 | |||
| 58 | *********************************************************************** | ||
| 59 | ROUTINES: | ||
| 60 | block_offsets() | ||
| 61 | low_contrast_block() | ||
| 62 | find_valid_block() | ||
| 63 | set_margin_blocks() | ||
| 64 | |||
| 65 | ***********************************************************************/ | ||
| 66 | |||
| 67 | #include <stdio.h> | ||
| 68 | #include <lfs.h> | ||
| 69 | |||
| 70 | /************************************************************************* | ||
| 71 | ************************************************************************** | ||
| 72 | #cat: block_offsets - Divides an image into mw X mh equally sized blocks, | ||
| 73 | #cat: returning a list of offsets to the top left corner of each block. | ||
| 74 | #cat: For images that are even multiples of BLOCKSIZE, blocks do not | ||
| 75 | #cat: not overlap and are immediately adjacent to each other. For image | ||
| 76 | #cat: that are NOT even multiples of BLOCKSIZE, blocks continue to be | ||
| 77 | #cat: non-overlapping up to the last column and/or last row of blocks. | ||
| 78 | #cat: In these cases the blocks are adjacent to the edge of the image and | ||
| 79 | #cat: extend inwards BLOCKSIZE units, overlapping the neighboring column | ||
| 80 | #cat: or row of blocks. This routine also accounts for image padding | ||
| 81 | #cat: which makes things a little more "messy". This routine is primarily | ||
| 82 | #cat: responsible providing the ability to processs arbitrarily-sized | ||
| 83 | #cat: images. The strategy used here is simple, but others are possible. | ||
| 84 | |||
| 85 | Input: | ||
| 86 | iw - width (in pixels) of the orginal input image | ||
| 87 | ih - height (in pixels) of the orginal input image | ||
| 88 | pad - the padding (in pixels) required to support the desired | ||
| 89 | range of block orientations for DFT analysis. This padding | ||
| 90 | is required along the entire perimeter of the input image. | ||
| 91 | For certain applications, the pad may be zero. | ||
| 92 | blocksize - the width and height (in pixels) of each image block | ||
| 93 | Output: | ||
| 94 | optr - points to the list of pixel offsets to the origin of | ||
| 95 | each block in the "padded" input image | ||
| 96 | ow - the number of horizontal blocks in the input image | ||
| 97 | oh - the number of vertical blocks in the input image | ||
| 98 | Return Code: | ||
| 99 | Zero - successful completion | ||
| 100 | Negative - system error | ||
| 101 | **************************************************************************/ | ||
| 102 | 240 | int block_offsets(int **optr, int *ow, int *oh, | |
| 103 | const int iw, const int ih, const int pad, const int blocksize) | ||
| 104 | { | ||
| 105 | 240 | int *blkoffs, bx, by, bw, bh, bi, bsize; | |
| 106 | 240 | int blkrow_start, blkrow_size, offset; | |
| 107 | 240 | int lastbw, lastbh; | |
| 108 | 240 | int pad2, pw; | |
| 109 | |||
| 110 | /* Test if unpadded image is smaller than a single block */ | ||
| 111 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 240 times.
|
240 | if((iw < blocksize) || (ih < blocksize)){ |
| 112 | ✗ | fprintf(stderr, | |
| 113 | "ERROR : block_offsets : image must be at least %d by %d in size\n", | ||
| 114 | blocksize, blocksize); | ||
| 115 | ✗ | return(-80); | |
| 116 | } | ||
| 117 | |||
| 118 | /* Compute padded width of image */ | ||
| 119 | 240 | pad2 = pad<<1; | |
| 120 | 240 | pw = iw + pad2; | |
| 121 | |||
| 122 | /* Compute the number of columns and rows of blocks in the image. */ | ||
| 123 | /* Take the ceiling to account for "leftovers" at the right and */ | ||
| 124 | /* bottom of the unpadded image */ | ||
| 125 | 240 | bw = (int)ceil(iw / (double)blocksize); | |
| 126 | 240 | bh = (int)ceil(ih / (double)blocksize); | |
| 127 | |||
| 128 | /* Total number of blocks in the image */ | ||
| 129 | 240 | bsize = bw*bh; | |
| 130 | |||
| 131 | /* The index of the last column */ | ||
| 132 | 240 | lastbw = bw - 1; | |
| 133 | /* The index of the last row */ | ||
| 134 | 240 | lastbh = bh - 1; | |
| 135 | |||
| 136 | /* Allocate list of block offsets */ | ||
| 137 | 240 | blkoffs = (int *)g_malloc(bsize * sizeof(int)); | |
| 138 | |||
| 139 | /* Current block index */ | ||
| 140 | 240 | bi = 0; | |
| 141 | |||
| 142 | /* Current offset from top of padded image to start of new row of */ | ||
| 143 | /* unpadded image blocks. It is initialize to account for the */ | ||
| 144 | /* padding and will always be indented the size of the padding */ | ||
| 145 | /* from the left edge of the padded image. */ | ||
| 146 | 240 | blkrow_start = (pad * pw) + pad; | |
| 147 | |||
| 148 | /* Number of pixels in a row of blocks in the padded image */ | ||
| 149 | 240 | blkrow_size = pw * blocksize; /* row width X block height */ | |
| 150 | |||
| 151 | /* Foreach non-overlapping row of blocks in the image */ | ||
| 152 |
2/2✓ Branch 0 taken 8125 times.
✓ Branch 1 taken 240 times.
|
8365 | for(by = 0; by < lastbh; by++){ |
| 153 | /* Current offset from top of padded image to beginning of */ | ||
| 154 | /* the next block */ | ||
| 155 | offset = blkrow_start; | ||
| 156 | /* Foreach non-overlapping column of blocks in the image */ | ||
| 157 |
2/2✓ Branch 0 taken 237985 times.
✓ Branch 1 taken 8125 times.
|
246110 | for(bx = 0; bx < lastbw; bx++){ |
| 158 | /* Store current block offset */ | ||
| 159 | 237985 | blkoffs[bi++] = offset; | |
| 160 | /* Bump to the beginning of the next block */ | ||
| 161 | 237985 | offset += blocksize; | |
| 162 | } | ||
| 163 | |||
| 164 | /* Compute and store "left-over" block in row. */ | ||
| 165 | /* This is the block in the last column of row. */ | ||
| 166 | /* Start at far right edge of unpadded image data */ | ||
| 167 | /* and come in BLOCKSIZE pixels. */ | ||
| 168 | 8125 | blkoffs[bi++] = blkrow_start + iw - blocksize; | |
| 169 | /* Bump to beginning of next row of blocks */ | ||
| 170 | 8125 | blkrow_start += blkrow_size; | |
| 171 | } | ||
| 172 | |||
| 173 | /* Compute and store "left-over" row of blocks at bottom of image */ | ||
| 174 | /* Start at bottom edge of unpadded image data and come up */ | ||
| 175 | /* BLOCKSIZE pixels. This too must account for padding. */ | ||
| 176 | 240 | blkrow_start = ((pad + ih - blocksize) * pw) + pad; | |
| 177 | /* Start the block offset for the last row at this point */ | ||
| 178 | 240 | offset = blkrow_start; | |
| 179 | /* Foreach non-overlapping column of blocks in last row of the image */ | ||
| 180 |
2/2✓ Branch 0 taken 7300 times.
✓ Branch 1 taken 240 times.
|
7540 | for(bx = 0; bx < lastbw; bx++){ |
| 181 | /* Store current block offset */ | ||
| 182 | 7300 | blkoffs[bi++] = offset; | |
| 183 | /* Bump to the beginning of the next block */ | ||
| 184 | 7300 | offset += blocksize; | |
| 185 | } | ||
| 186 | |||
| 187 | /* Compute and store last "left-over" block in last row. */ | ||
| 188 | /* Start at right edge of unpadded image data and come in */ | ||
| 189 | /* BLOCKSIZE pixels. */ | ||
| 190 | 240 | blkoffs[bi++] = blkrow_start + iw - blocksize; | |
| 191 | |||
| 192 | 240 | *optr = blkoffs; | |
| 193 | 240 | *ow = bw; | |
| 194 | 240 | *oh = bh; | |
| 195 | 240 | return(0); | |
| 196 | } | ||
| 197 | |||
| 198 | /************************************************************************* | ||
| 199 | #cat: low_contrast_block - Takes the offset to an image block of specified | ||
| 200 | #cat: dimension, and analyzes the pixel intensities in the block | ||
| 201 | #cat: to determine if there is sufficient contrast for further | ||
| 202 | #cat: processing. | ||
| 203 | |||
| 204 | Input: | ||
| 205 | blkoffset - byte offset into the padded input image to the origin of | ||
| 206 | the block to be analyzed | ||
| 207 | blocksize - dimension (in pixels) of the width and height of the block | ||
| 208 | (passing separate blocksize from LFSPARMS on purpose) | ||
| 209 | pdata - padded input image data (8 bits [0..256) grayscale) | ||
| 210 | pw - width (in pixels) of the padded input image | ||
| 211 | ph - height (in pixels) of the padded input image | ||
| 212 | lfsparms - parameters and thresholds for controlling LFS | ||
| 213 | Return Code: | ||
| 214 | TRUE - block has sufficiently low contrast | ||
| 215 | FALSE - block has sufficiently hight contrast | ||
| 216 | Negative - system error | ||
| 217 | ************************************************************************** | ||
| 218 | **************************************************************************/ | ||
| 219 | 50730 | int low_contrast_block(const int blkoffset, const int blocksize, | |
| 220 | unsigned char *pdata, const int pw, const int ph, | ||
| 221 | const LFSPARMS *lfsparms) | ||
| 222 | { | ||
| 223 | 50730 | int pixtable[IMG_6BIT_PIX_LIMIT], numpix; | |
| 224 | 50730 | int px, py, pi; | |
| 225 | 50730 | unsigned char *sptr, *pptr; | |
| 226 | 50730 | int delta; | |
| 227 | 50730 | double tdbl; | |
| 228 | 50730 | int prctmin = 0, prctmax = 0, prctthresh; | |
| 229 | 50730 | int pixsum, found; | |
| 230 | |||
| 231 | 50730 | numpix = blocksize*blocksize; | |
| 232 | 50730 | memset(pixtable, 0, IMG_6BIT_PIX_LIMIT*sizeof(int)); | |
| 233 | |||
| 234 | 50730 | tdbl = (lfsparms->percentile_min_max/100.0) * (double)(numpix-1); | |
| 235 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 50730 times.
|
50730 | tdbl = trunc_dbl_precision(tdbl, TRUNC_SCALE); |
| 236 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 50730 times.
|
50730 | prctthresh = sround(tdbl); |
| 237 | |||
| 238 | 50730 | sptr = pdata+blkoffset; | |
| 239 |
2/2✓ Branch 0 taken 1217520 times.
✓ Branch 1 taken 50730 times.
|
1268250 | for(py = 0; py < blocksize; py++){ |
| 240 | pptr = sptr; | ||
| 241 |
2/2✓ Branch 0 taken 29220480 times.
✓ Branch 1 taken 1217520 times.
|
30438000 | for(px = 0; px < blocksize; px++){ |
| 242 | 29220480 | pixtable[*pptr]++; | |
| 243 | 29220480 | pptr++; | |
| 244 | } | ||
| 245 | 1217520 | sptr += pw; | |
| 246 | } | ||
| 247 | |||
| 248 | pi = 0; | ||
| 249 | pixsum = 0; | ||
| 250 | 1190583 | found = FALSE; | |
| 251 |
1/2✓ Branch 0 taken 1190583 times.
✗ Branch 1 not taken.
|
1190583 | while(pi < IMG_6BIT_PIX_LIMIT){ |
| 252 | 1190583 | pixsum += pixtable[pi]; | |
| 253 |
2/2✓ Branch 0 taken 1139853 times.
✓ Branch 1 taken 50730 times.
|
1190583 | if(pixsum >= prctthresh){ |
| 254 | prctmin = pi; | ||
| 255 | found = TRUE; | ||
| 256 | break; | ||
| 257 | } | ||
| 258 | 1139853 | pi++; | |
| 259 | } | ||
| 260 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 50730 times.
|
50730 | if(!found){ |
| 261 | ✗ | fprintf(stderr, | |
| 262 | "ERROR : low_contrast_block : min percentile pixel not found\n"); | ||
| 263 | ✗ | return(-510); | |
| 264 | } | ||
| 265 | |||
| 266 | pi = IMG_6BIT_PIX_LIMIT-1; | ||
| 267 | pixsum = 0; | ||
| 268 | 1091931 | found = FALSE; | |
| 269 |
1/2✓ Branch 0 taken 1091931 times.
✗ Branch 1 not taken.
|
1091931 | while(pi >= 0){ |
| 270 | 1091931 | pixsum += pixtable[pi]; | |
| 271 |
2/2✓ Branch 0 taken 1041201 times.
✓ Branch 1 taken 50730 times.
|
1091931 | if(pixsum >= prctthresh){ |
| 272 | prctmax = pi; | ||
| 273 | found = TRUE; | ||
| 274 | break; | ||
| 275 | } | ||
| 276 | 1041201 | pi--; | |
| 277 | } | ||
| 278 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 50730 times.
|
50730 | if(!found){ |
| 279 | ✗ | fprintf(stderr, | |
| 280 | "ERROR : low_contrast_block : max percentile pixel not found\n"); | ||
| 281 | ✗ | return(-511); | |
| 282 | } | ||
| 283 | |||
| 284 | 50730 | delta = prctmax - prctmin; | |
| 285 | |||
| 286 |
2/2✓ Branch 0 taken 46139 times.
✓ Branch 1 taken 4591 times.
|
50730 | if(delta < lfsparms->min_contrast_delta) |
| 287 | return(TRUE); | ||
| 288 | else | ||
| 289 | 46139 | return(FALSE); | |
| 290 | } | ||
| 291 | |||
| 292 | /************************************************************************* | ||
| 293 | ************************************************************************** | ||
| 294 | #cat: find_valid_block - Take a Direction Map, Low Contrast Map, | ||
| 295 | #cat: Starting block address, a direction and searches the | ||
| 296 | #cat: maps in the specified direction until either a block valid | ||
| 297 | #cat: direction is encountered or a block flagged as LOW CONTRAST | ||
| 298 | #cat: is encountered. If a valid direction is located, it and the | ||
| 299 | #cat: address of the corresponding block are returned with a | ||
| 300 | #cat: code of FOUND. Otherwise, a code of NOT_FOUND is returned. | ||
| 301 | |||
| 302 | Input: | ||
| 303 | direction_map - map of blocks containing directional ridge flows | ||
| 304 | low_contrast_map - map of blocks flagged as LOW CONTRAST | ||
| 305 | sx - X-block coord where search starts in maps | ||
| 306 | sy - Y-block coord where search starts in maps | ||
| 307 | mw - number of blocks horizontally in the maps | ||
| 308 | mh - number of blocks vertically in the maps | ||
| 309 | x_incr - X-block increment to direct search | ||
| 310 | y_incr - Y-block increment to direct search | ||
| 311 | Output: | ||
| 312 | nbr_dir - valid direction found | ||
| 313 | nbr_x - X-block coord where valid direction found | ||
| 314 | nbr_y - Y-block coord where valid direction found | ||
| 315 | Return Code: | ||
| 316 | FOUND - neighboring block with valid direction found | ||
| 317 | NOT_FOUND - neighboring block with valid direction NOT found | ||
| 318 | **************************************************************************/ | ||
| 319 | 50952 | int find_valid_block(int *nbr_dir, int *nbr_x, int *nbr_y, | |
| 320 | int *direction_map, int *low_contrast_map, | ||
| 321 | const int sx, const int sy, | ||
| 322 | const int mw, const int mh, | ||
| 323 | const int x_incr, const int y_incr) | ||
| 324 | { | ||
| 325 | 50952 | int x, y, dir; | |
| 326 | |||
| 327 | /* Initialize starting block coords. */ | ||
| 328 | 50952 | x = sx + x_incr; | |
| 329 | 50952 | y = sy + y_incr; | |
| 330 | |||
| 331 | /* While we are not outside the boundaries of the map ... */ | ||
| 332 |
4/4✓ Branch 0 taken 239723 times.
✓ Branch 1 taken 2747 times.
✓ Branch 2 taken 234959 times.
✓ Branch 3 taken 4764 times.
|
242470 | while((x >= 0) && (x < mw) && (y >= 0) && (y < mh)){ |
| 333 | /* Stop unsuccessfully if we encounter a LOW CONTRAST block. */ | ||
| 334 |
2/2✓ Branch 0 taken 226836 times.
✓ Branch 1 taken 8123 times.
|
234959 | if(*(low_contrast_map+(y*mw)+x)) |
| 335 | return(NOT_FOUND); | ||
| 336 | |||
| 337 | /* Stop successfully if we encounter a block with valid direction. */ | ||
| 338 |
2/2✓ Branch 0 taken 35318 times.
✓ Branch 1 taken 191518 times.
|
226836 | if((dir = *(direction_map+(y*mw)+x)) >= 0){ |
| 339 | 35318 | *nbr_dir = dir; | |
| 340 | 35318 | *nbr_x = x; | |
| 341 | 35318 | *nbr_y = y; | |
| 342 | 35318 | return(FOUND); | |
| 343 | } | ||
| 344 | |||
| 345 | /* Otherwise, advance to the next block in the map. */ | ||
| 346 | 191518 | x += x_incr; | |
| 347 | 191518 | y += y_incr; | |
| 348 | } | ||
| 349 | |||
| 350 | /* If we get here, then we did not find a valid block in the given */ | ||
| 351 | /* direction in the map. */ | ||
| 352 | return(NOT_FOUND); | ||
| 353 | } | ||
| 354 | |||
| 355 | /************************************************************************* | ||
| 356 | ************************************************************************** | ||
| 357 | #cat: set_margin_blocks - Take an image map and sets its perimeter values to | ||
| 358 | #cat: the specified value. | ||
| 359 | |||
| 360 | Input: | ||
| 361 | map - map of blocks to be modified | ||
| 362 | mw - number of blocks horizontally in the map | ||
| 363 | mh - number of blocks vertically in the map | ||
| 364 | margin_value - value to be assigned to the perimeter blocks | ||
| 365 | Output: | ||
| 366 | map - resulting map | ||
| 367 | **************************************************************************/ | ||
| 368 | 48 | void set_margin_blocks(int *map, const int mw, const int mh, | |
| 369 | const int margin_value) | ||
| 370 | { | ||
| 371 | 48 | int x, y; | |
| 372 | 48 | int *ptr1, *ptr2; | |
| 373 | |||
| 374 | 48 | ptr1 = map; | |
| 375 | 48 | ptr2 = map+((mh-1)*mw); | |
| 376 |
2/2✓ Branch 0 taken 1508 times.
✓ Branch 1 taken 48 times.
|
1556 | for(x = 0; x < mw; x++){ |
| 377 | 1508 | *ptr1++ = margin_value; | |
| 378 | 1508 | *ptr2++ = margin_value; | |
| 379 | } | ||
| 380 | |||
| 381 | 48 | ptr1 = map + mw; | |
| 382 | 48 | ptr2 = map + mw + mw - 1; | |
| 383 |
2/2✓ Branch 0 taken 1577 times.
✓ Branch 1 taken 48 times.
|
1625 | for(y = 1; y < mh-1; y++){ |
| 384 | 1577 | *ptr1 = margin_value; | |
| 385 | 1577 | *ptr2 = margin_value; | |
| 386 | 1577 | ptr1 += mw; | |
| 387 | 1577 | ptr2 += mw; | |
| 388 | } | ||
| 389 | |||
| 390 | 48 | } | |
| 391 | |||
| 392 |