| 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: DFT.C | ||
| 49 | AUTHOR: Michael D. Garris | ||
| 50 | DATE: 03/16/1999 | ||
| 51 | UPDATED: 03/16/2005 by MDG | ||
| 52 | |||
| 53 | Contains routines responsible for conducting Discrete Fourier | ||
| 54 | Transforms (DFT) analysis on a block of image data as part of | ||
| 55 | the NIST Latent Fingerprint System (LFS). | ||
| 56 | |||
| 57 | *********************************************************************** | ||
| 58 | ROUTINES: | ||
| 59 | dft_dir_powers() | ||
| 60 | sum_rot_block_rows() | ||
| 61 | dft_power() | ||
| 62 | dft_power_stats() | ||
| 63 | get_max_norm() | ||
| 64 | sort_dft_waves() | ||
| 65 | ***********************************************************************/ | ||
| 66 | |||
| 67 | #include <stdio.h> | ||
| 68 | #include <lfs.h> | ||
| 69 | |||
| 70 | /************************************************************************* | ||
| 71 | ************************************************************************** | ||
| 72 | #cat: dft_dir_powers - Conducts the DFT analysis on a block of image data. | ||
| 73 | #cat: The image block is sampled across a range of orientations | ||
| 74 | #cat: (directions) and multiple wave forms of varying frequency are | ||
| 75 | #cat: applied at each orientation. At each orentation, pixels are | ||
| 76 | #cat: accumulated along each rotated pixel row, creating a vector | ||
| 77 | #cat: of pixel row sums. Each DFT wave form is then applied | ||
| 78 | #cat: individually to this vector of pixel row sums. A DFT power | ||
| 79 | #cat: value is computed for each wave form (frequency0 at each | ||
| 80 | #cat: orientaion within the image block. Therefore, the resulting DFT | ||
| 81 | #cat: power vectors are of dimension (N Waves X M Directions). | ||
| 82 | #cat: The power signatures derived form this process are used to | ||
| 83 | #cat: determine dominant direction flow within the image block. | ||
| 84 | |||
| 85 | Input: | ||
| 86 | pdata - the padded input image. It is important that the image | ||
| 87 | be properly padded, or else the sampling at various block | ||
| 88 | orientations may result in accessing unkown memory. | ||
| 89 | blkoffset - the pixel offset form the origin of the padded image to | ||
| 90 | the origin of the current block in the image | ||
| 91 | pw - the width (in pixels) of the padded input image | ||
| 92 | ph - the height (in pixels) of the padded input image | ||
| 93 | dftwaves - structure containing the DFT wave forms | ||
| 94 | dftgrids - structure containing the rotated pixel grid offsets | ||
| 95 | Output: | ||
| 96 | powers - DFT power computed from each wave form frequencies at each | ||
| 97 | orientation (direction) in the current image block | ||
| 98 | Return Code: | ||
| 99 | Zero - successful completion | ||
| 100 | Negative - system error | ||
| 101 | **************************************************************************/ | ||
| 102 | 46139 | int dft_dir_powers(double **powers, unsigned char *pdata, | |
| 103 | const int blkoffset, const int pw, const int ph, | ||
| 104 | const DFTWAVES *dftwaves, const ROTGRIDS *dftgrids) | ||
| 105 | { | ||
| 106 | 46139 | int w, dir; | |
| 107 | 46139 | int *rowsums; | |
| 108 | 46139 | unsigned char *blkptr; | |
| 109 | |||
| 110 | /* Allocate line sum vector, and initialize to zeros */ | ||
| 111 | /* This routine requires square block (grid), so ERROR otherwise. */ | ||
| 112 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 46139 times.
|
46139 | if(dftgrids->grid_w != dftgrids->grid_h){ |
| 113 | ✗ | fprintf(stderr, "ERROR : dft_dir_powers : DFT grids must be square\n"); | |
| 114 | ✗ | return(-90); | |
| 115 | } | ||
| 116 | 46139 | rowsums = (int *)g_malloc(dftgrids->grid_w * sizeof(int)); | |
| 117 | 46139 | memset(rowsums, 0, dftgrids->grid_w * sizeof(int)); | |
| 118 | |||
| 119 | /* Foreach direction ... */ | ||
| 120 |
2/2✓ Branch 0 taken 738224 times.
✓ Branch 1 taken 46139 times.
|
784363 | for(dir = 0; dir < dftgrids->ngrids; dir++){ |
| 121 | /* Compute vector of line sums from rotated grid */ | ||
| 122 | 738224 | blkptr = pdata + blkoffset; | |
| 123 | 738224 | sum_rot_block_rows(rowsums, blkptr, | |
| 124 | 738224 | dftgrids->grids[dir], dftgrids->grid_w); | |
| 125 | |||
| 126 | /* Foreach DFT wave ... */ | ||
| 127 |
2/2✓ Branch 1 taken 2952896 times.
✓ Branch 2 taken 738224 times.
|
4429344 | for(w = 0; w < dftwaves->nwaves; w++){ |
| 128 | 2952896 | dft_power(&(powers[w][dir]), rowsums, | |
| 129 | 2952896 | dftwaves->waves[w], dftwaves->wavelen); | |
| 130 | } | ||
| 131 | } | ||
| 132 | |||
| 133 | /* Deallocate working memory. */ | ||
| 134 | 46139 | g_free(rowsums); | |
| 135 | |||
| 136 | 46139 | return(0); | |
| 137 | } | ||
| 138 | |||
| 139 | /************************************************************************* | ||
| 140 | ************************************************************************** | ||
| 141 | #cat: sum_rot_block_rows - Computes a vector or pixel row sums by sampling | ||
| 142 | #cat: the current image block at a given orientation. The | ||
| 143 | #cat: sampling is conducted using a precomputed set of rotated | ||
| 144 | #cat: pixel offsets (called a grid) relative to the orgin of | ||
| 145 | #cat: the image block. | ||
| 146 | |||
| 147 | Input: | ||
| 148 | blkptr - the pixel address of the origin of the current image block | ||
| 149 | grid_offsets - the rotated pixel offsets for a block-sized grid | ||
| 150 | rotated according to a specific orientation | ||
| 151 | blocksize - the width and height of the image block and thus the size | ||
| 152 | of the rotated grid | ||
| 153 | Output: | ||
| 154 | rowsums - the resulting vector of pixel row sums | ||
| 155 | **************************************************************************/ | ||
| 156 | 738224 | void sum_rot_block_rows(int *rowsums, const unsigned char *blkptr, | |
| 157 | const int *grid_offsets, const int blocksize) | ||
| 158 | { | ||
| 159 | 738224 | int ix, iy, gi; | |
| 160 | |||
| 161 | /* Initialize rotation offset index. */ | ||
| 162 | 738224 | gi = 0; | |
| 163 | |||
| 164 | /* For each row in block ... */ | ||
| 165 |
2/2✓ Branch 0 taken 17717376 times.
✓ Branch 1 taken 738224 times.
|
18455600 | for(iy = 0; iy < blocksize; iy++){ |
| 166 | /* The sums are accumlated along the rotated rows of the grid, */ | ||
| 167 | /* so initialize row sum to 0. */ | ||
| 168 | 17717376 | rowsums[iy] = 0; | |
| 169 | /* Foreach column in block ... */ | ||
| 170 |
2/2✓ Branch 0 taken 425217024 times.
✓ Branch 1 taken 17717376 times.
|
442934400 | for(ix = 0; ix < blocksize; ix++){ |
| 171 | /* Accumulate pixel value at rotated grid position in image */ | ||
| 172 | 425217024 | rowsums[iy] += *(blkptr + grid_offsets[gi]); | |
| 173 | 425217024 | gi++; | |
| 174 | } | ||
| 175 | } | ||
| 176 | 738224 | } | |
| 177 | |||
| 178 | /************************************************************************* | ||
| 179 | ************************************************************************** | ||
| 180 | #cat: dft_power - Computes the DFT power by applying a specific wave form | ||
| 181 | #cat: frequency to a vector of pixel row sums computed from a | ||
| 182 | #cat: specific orientation of the block image | ||
| 183 | |||
| 184 | Input: | ||
| 185 | rowsums - accumulated rows of pixels from within a rotated grid | ||
| 186 | overlaying an input image block | ||
| 187 | wave - the wave form (cosine and sine components) at a specific | ||
| 188 | frequency | ||
| 189 | wavelen - the length of the wave form (must match the height of the | ||
| 190 | image block which is the length of the rowsum vector) | ||
| 191 | Output: | ||
| 192 | power - the computed DFT power for the given wave form at the | ||
| 193 | given orientation within the image block | ||
| 194 | **************************************************************************/ | ||
| 195 | 2952896 | void dft_power(double *power, const int *rowsums, | |
| 196 | const DFTWAVE *wave, const int wavelen) | ||
| 197 | { | ||
| 198 | 2952896 | int i; | |
| 199 | 2952896 | double cospart, sinpart; | |
| 200 | |||
| 201 | /* Initialize accumulators */ | ||
| 202 | 2952896 | cospart = 0.0; | |
| 203 | 2952896 | sinpart = 0.0; | |
| 204 | |||
| 205 | /* Accumulate cos and sin components of DFT. */ | ||
| 206 |
2/2✓ Branch 0 taken 70869504 times.
✓ Branch 1 taken 2952896 times.
|
73822400 | for(i = 0; i < wavelen; i++){ |
| 207 | /* Multiply each rotated row sum by its */ | ||
| 208 | /* corresponding cos or sin point in DFT wave. */ | ||
| 209 | 70869504 | cospart += (rowsums[i] * wave->cos[i]); | |
| 210 | 70869504 | sinpart += (rowsums[i] * wave->sin[i]); | |
| 211 | } | ||
| 212 | |||
| 213 | /* Power is the sum of the squared cos and sin components */ | ||
| 214 | 2952896 | *power = (cospart * cospart) + (sinpart * sinpart); | |
| 215 | 2952896 | } | |
| 216 | |||
| 217 | /************************************************************************* | ||
| 218 | ************************************************************************** | ||
| 219 | #cat: dft_power_stats - Derives statistics from a set of DFT power vectors. | ||
| 220 | #cat: Statistics are computed for all but the lowest frequency | ||
| 221 | #cat: wave form, including the Maximum power for each wave form, | ||
| 222 | #cat: the direction at which the maximum power occured, and a | ||
| 223 | #cat: normalized value for the maximum power. In addition, the | ||
| 224 | #cat: statistics are ranked in descending order based on normalized | ||
| 225 | #cat: squared maximum power. These statistics are fundamental | ||
| 226 | #cat: to selecting a dominant direction flow for the current | ||
| 227 | #cat: input image block. | ||
| 228 | |||
| 229 | Input: | ||
| 230 | powers - DFT power vectors (N Waves X M Directions) computed for | ||
| 231 | the current image block from which the values in the | ||
| 232 | statistics arrays are derived | ||
| 233 | fw - the beginning of the range of wave form indices from which | ||
| 234 | the statistcs are to derived | ||
| 235 | tw - the ending of the range of wave form indices from which | ||
| 236 | the statistcs are to derived (last index is tw-1) | ||
| 237 | ndirs - number of orientations (directions) at which the DFT | ||
| 238 | analysis was conducted | ||
| 239 | Output: | ||
| 240 | wis - list of ranked wave form indicies of the corresponding | ||
| 241 | statistics based on normalized squared maximum power. These | ||
| 242 | indices will be used as indirect addresses when processing | ||
| 243 | the power statistics in descending order of "dominance" | ||
| 244 | powmaxs - array holding the maximum DFT power for each wave form | ||
| 245 | (other than the lowest frequecy) | ||
| 246 | powmax_dirs - array to holding the direction corresponding to | ||
| 247 | each maximum power value in powmaxs | ||
| 248 | pownorms - array to holding the normalized maximum powers corresponding | ||
| 249 | to each value in powmaxs | ||
| 250 | Return Code: | ||
| 251 | Zero - successful completion | ||
| 252 | Negative - system error | ||
| 253 | **************************************************************************/ | ||
| 254 | 46139 | int dft_power_stats(int *wis, double *powmaxs, int *powmax_dirs, | |
| 255 | double *pownorms, double **powers, | ||
| 256 | const int fw, const int tw, const int ndirs) | ||
| 257 | { | ||
| 258 | 46139 | int w, i; | |
| 259 | 46139 | int ret; /* return code */ | |
| 260 | |||
| 261 |
2/2✓ Branch 0 taken 138417 times.
✓ Branch 1 taken 46139 times.
|
184556 | for(w = fw, i = 0; w < tw; w++, i++){ |
| 262 | 138417 | get_max_norm(&(powmaxs[i]), &(powmax_dirs[i]), | |
| 263 | 138417 | &(pownorms[i]), powers[w], ndirs); | |
| 264 | } | ||
| 265 | |||
| 266 | /* Get sorted order of applied DFT waves based on normalized power */ | ||
| 267 | 46139 | if((ret = sort_dft_waves(wis, powmaxs, pownorms, tw-fw))) | |
| 268 | return(ret); | ||
| 269 | |||
| 270 | return(0); | ||
| 271 | } | ||
| 272 | |||
| 273 | /************************************************************************* | ||
| 274 | ************************************************************************** | ||
| 275 | #cat: get_max_norm - Analyses a DFT power vector for a specific wave form | ||
| 276 | #cat: applied at different orientations (directions) to the | ||
| 277 | #cat: current image block. The routine retuns the maximum | ||
| 278 | #cat: power value in the vector, the direction at which the | ||
| 279 | #cat: maximum occurs, and a normalized power value. The | ||
| 280 | #cat: normalized power is computed as the maximum power divided | ||
| 281 | #cat: by the average power across all the directions. These | ||
| 282 | #cat: simple statistics are fundamental to the selection of | ||
| 283 | #cat: a dominant direction flow for the image block. | ||
| 284 | |||
| 285 | Input: | ||
| 286 | power_vector - the DFT power values derived form a specific wave form | ||
| 287 | applied at different directions | ||
| 288 | ndirs - the number of directions to which the wave form was applied | ||
| 289 | Output: | ||
| 290 | powmax - the maximum power value in the DFT power vector | ||
| 291 | powmax_dir - the direciton at which the maximum power value occured | ||
| 292 | pownorm - the normalized power corresponding to the maximum power | ||
| 293 | **************************************************************************/ | ||
| 294 | 138417 | void get_max_norm(double *powmax, int *powmax_dir, | |
| 295 | double *pownorm, const double *power_vector, const int ndirs) | ||
| 296 | { | ||
| 297 | 138417 | int dir; | |
| 298 | 138417 | double max_v, powsum; | |
| 299 | 138417 | int max_i; | |
| 300 | 138417 | double powmean; | |
| 301 | |||
| 302 | /* Find max power value and store corresponding direction */ | ||
| 303 | 138417 | max_v = power_vector[0]; | |
| 304 | 138417 | max_i = 0; | |
| 305 | |||
| 306 | /* Sum the total power in a block at a given direction */ | ||
| 307 | 138417 | powsum = power_vector[0]; | |
| 308 | |||
| 309 | /* For each direction ... */ | ||
| 310 |
2/2✓ Branch 0 taken 2076255 times.
✓ Branch 1 taken 138417 times.
|
2214672 | for(dir = 1; dir < ndirs; dir++){ |
| 311 | 2076255 | powsum += power_vector[dir]; | |
| 312 |
2/2✓ Branch 0 taken 405763 times.
✓ Branch 1 taken 1670492 times.
|
2076255 | if(power_vector[dir] > max_v){ |
| 313 | 405763 | max_v = power_vector[dir]; | |
| 314 | 405763 | max_i = dir; | |
| 315 | } | ||
| 316 | } | ||
| 317 | |||
| 318 | 138417 | *powmax = max_v; | |
| 319 | 138417 | *powmax_dir = max_i; | |
| 320 | |||
| 321 | /* Powmean is used as denominator for pownorm, so setting */ | ||
| 322 | /* a non-zero minimum avoids possible division by zero. */ | ||
| 323 |
1/2✓ Branch 0 taken 138417 times.
✗ Branch 1 not taken.
|
138417 | powmean = max(powsum, MIN_POWER_SUM)/(double)ndirs; |
| 324 | |||
| 325 | 138417 | *pownorm = *powmax / powmean; | |
| 326 | 138417 | } | |
| 327 | |||
| 328 | /************************************************************************* | ||
| 329 | ************************************************************************** | ||
| 330 | #cat: sort_dft_waves - Creates a ranked list of DFT wave form statistics | ||
| 331 | #cat: by sorting on the normalized squared maximum power. | ||
| 332 | |||
| 333 | Input: | ||
| 334 | powmaxs - maximum DFT power for each wave form used to derive | ||
| 335 | statistics | ||
| 336 | pownorms - normalized maximum power corresponding to values in powmaxs | ||
| 337 | nstats - number of wave forms used to derive statistics (N Wave - 1) | ||
| 338 | Output: | ||
| 339 | wis - sorted list of indices corresponding to the ranked set of | ||
| 340 | wave form statistics. These indices will be used as | ||
| 341 | indirect addresses when processing the power statistics | ||
| 342 | in descending order of "dominance" | ||
| 343 | Return Code: | ||
| 344 | Zero - successful completion | ||
| 345 | Negative - system error | ||
| 346 | **************************************************************************/ | ||
| 347 | 46139 | int sort_dft_waves(int *wis, const double *powmaxs, const double *pownorms, | |
| 348 | const int nstats) | ||
| 349 | { | ||
| 350 | 46139 | int i; | |
| 351 | 46139 | double *pownorms2; | |
| 352 | |||
| 353 | /* Allocate normalized power^2 array */ | ||
| 354 | 46139 | pownorms2 = (double *)g_malloc(nstats * sizeof(double)); | |
| 355 | |||
| 356 |
2/2✓ Branch 1 taken 138417 times.
✓ Branch 2 taken 46139 times.
|
230695 | for(i = 0; i < nstats; i++){ |
| 357 | /* Wis will hold the sorted statistic indices when all is done. */ | ||
| 358 | 138417 | wis[i] = i; | |
| 359 | /* This is normalized squared max power. */ | ||
| 360 | 138417 | pownorms2[i] = powmaxs[i] * pownorms[i]; | |
| 361 | } | ||
| 362 | |||
| 363 | /* Sort the statistic indices on the normalized squared power. */ | ||
| 364 | 46139 | bubble_sort_double_dec_2(pownorms2, wis, nstats); | |
| 365 | |||
| 366 | /* Deallocate the working memory. */ | ||
| 367 | 46139 | g_free(pownorms2); | |
| 368 | |||
| 369 | 46139 | return(0); | |
| 370 | } | ||
| 371 | |||
| 372 |