| 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: SHAPE.C | ||
| 49 | AUTHOR: Michael D. Garris | ||
| 50 | DATE: 05/11/1999 | ||
| 51 | UPDATED: 03/16/2005 by MDG | ||
| 52 | |||
| 53 | Contains routines responsible for creating and manipulating | ||
| 54 | shape stuctures as part of the NIST Latent Fingerprint System (LFS). | ||
| 55 | |||
| 56 | *********************************************************************** | ||
| 57 | ROUTINES: | ||
| 58 | alloc_shape() | ||
| 59 | free_shape() | ||
| 60 | dump_shape() | ||
| 61 | shape_from_contour() | ||
| 62 | sort_row_on_x() | ||
| 63 | ***********************************************************************/ | ||
| 64 | |||
| 65 | #include <stdio.h> | ||
| 66 | #include <lfs.h> | ||
| 67 | |||
| 68 | /************************************************************************* | ||
| 69 | ************************************************************************** | ||
| 70 | #cat: alloc_shape - Allocates and initializes a shape structure given the | ||
| 71 | #cat: the X and Y limits of the shape. | ||
| 72 | |||
| 73 | Input: | ||
| 74 | xmin - left-most x-coord in shape | ||
| 75 | ymin - top-most y-coord in shape | ||
| 76 | xmax - right-most x-coord in shape | ||
| 77 | ymax - bottom-most y-coord in shape | ||
| 78 | Output: | ||
| 79 | oshape - pointer to the allocated & initialized shape structure | ||
| 80 | Return Code: | ||
| 81 | Zero - Shape successfully allocated and initialized | ||
| 82 | Negative - System error | ||
| 83 | **************************************************************************/ | ||
| 84 | 2980 | int alloc_shape(SHAPE **oshape, const int xmin, const int ymin, | |
| 85 | const int xmax, const int ymax) | ||
| 86 | { | ||
| 87 | 2980 | SHAPE *shape; | |
| 88 | 2980 | int alloc_rows, alloc_pts; | |
| 89 | 2980 | int i, y; | |
| 90 | |||
| 91 | /* Compute allocation parameters. */ | ||
| 92 | /* First, compute the number of scanlines spanned by the shape. */ | ||
| 93 | 2980 | alloc_rows = ymax - ymin + 1; | |
| 94 | /* Second, compute the "maximum" number of contour points possible */ | ||
| 95 | /* on a row. Here we are allocating the maximum number of contiguous */ | ||
| 96 | /* pixels on each row which will be sufficiently larger than the */ | ||
| 97 | /* number of actual contour points. */ | ||
| 98 | 2980 | alloc_pts = xmax - xmin + 1; | |
| 99 | |||
| 100 | /* Allocate the shape structure. */ | ||
| 101 | 2980 | shape = (SHAPE *)g_malloc(sizeof(SHAPE)); | |
| 102 | |||
| 103 | /* Allocate the list of row pointers. We now this number will fit */ | ||
| 104 | /* the shape exactly. */ | ||
| 105 | 2980 | shape->rows = (ROW **)g_malloc(alloc_rows * sizeof(ROW *)); | |
| 106 | |||
| 107 | /* Initialize the shape structure's attributes. */ | ||
| 108 | 2980 | shape->ymin = ymin; | |
| 109 | 2980 | shape->ymax = ymax; | |
| 110 | /* The number of allocated rows will be exactly the number of */ | ||
| 111 | /* assigned rows for the shape. */ | ||
| 112 | 2980 | shape->alloc = alloc_rows; | |
| 113 | 2980 | shape->nrows = alloc_rows; | |
| 114 | |||
| 115 | /* Foreach row in the shape... */ | ||
| 116 |
2/2✓ Branch 0 (8→5) taken 14050 times.
✓ Branch 1 (8→9) taken 2980 times.
|
17030 | for(i = 0, y = ymin; i < alloc_rows; i++, y++){ |
| 117 | /* Allocate a row structure and store it in its respective position */ | ||
| 118 | /* in the shape structure's list of row pointers. */ | ||
| 119 | 14050 | shape->rows[i] = (ROW *)g_malloc(sizeof(ROW)); | |
| 120 | |||
| 121 | /* Allocate the current rows list of x-coords. */ | ||
| 122 | 14050 | shape->rows[i]->xs = (int *)g_malloc(alloc_pts * sizeof(int)); | |
| 123 | |||
| 124 | /* Initialize the current row structure's attributes. */ | ||
| 125 | 14050 | shape->rows[i]->y = y; | |
| 126 | 14050 | shape->rows[i]->alloc = alloc_pts; | |
| 127 | /* There are initially ZERO points assigned to the row. */ | ||
| 128 | 14050 | shape->rows[i]->npts = 0; | |
| 129 | } | ||
| 130 | |||
| 131 | /* Assign structure to output pointer. */ | ||
| 132 | 2980 | *oshape = shape; | |
| 133 | |||
| 134 | /* Return normally. */ | ||
| 135 | 2980 | return(0); | |
| 136 | } | ||
| 137 | |||
| 138 | /************************************************************************* | ||
| 139 | ************************************************************************** | ||
| 140 | #cat: free_shape - Deallocates a shape structure and all its allocated | ||
| 141 | #cat: attributes. | ||
| 142 | |||
| 143 | Input: | ||
| 144 | shape - pointer to the shape structure to be deallocated | ||
| 145 | **************************************************************************/ | ||
| 146 | 2980 | void free_shape(SHAPE *shape) | |
| 147 | { | ||
| 148 | 2980 | int i; | |
| 149 | |||
| 150 | /* Foreach allocated row in the shape ... */ | ||
| 151 |
2/2✓ Branch 0 (6→3) taken 14050 times.
✓ Branch 1 (6→7) taken 2980 times.
|
17030 | for(i = 0; i < shape->alloc; i++){ |
| 152 | /* Deallocate the current row's list of x-coords. */ | ||
| 153 | 14050 | g_free(shape->rows[i]->xs); | |
| 154 | /* Deallocate the current row structure. */ | ||
| 155 | 14050 | g_free(shape->rows[i]); | |
| 156 | } | ||
| 157 | |||
| 158 | /* Deallocate the list of row pointers. */ | ||
| 159 | 2980 | g_free(shape->rows); | |
| 160 | /* Deallocate the shape structure. */ | ||
| 161 | 2980 | g_free(shape); | |
| 162 | 2980 | } | |
| 163 | |||
| 164 | /************************************************************************* | ||
| 165 | ************************************************************************** | ||
| 166 | #cat: dump_shape - Takes an initialized shape structure and dumps its contents | ||
| 167 | #cat: as formatted text to the specified open file pointer. | ||
| 168 | |||
| 169 | Input: | ||
| 170 | shape - shape structure to be dumped | ||
| 171 | Output: | ||
| 172 | fpout - open file pointer to be written to | ||
| 173 | **************************************************************************/ | ||
| 174 | |||
| 175 | /************************************************************************* | ||
| 176 | ************************************************************************** | ||
| 177 | #cat: shape_from_contour - Converts a contour list that has been determined | ||
| 178 | #cat: to form a complete loop into a shape representation where | ||
| 179 | #cat: the contour points on each contiguous scanline of the shape | ||
| 180 | #cat: are stored in left-to-right order. | ||
| 181 | |||
| 182 | Input: | ||
| 183 | contour_x - x-coord list for loop's contour points | ||
| 184 | contour_y - y-coord list for loop's contour points | ||
| 185 | ncontour - number of points in contour | ||
| 186 | Output: | ||
| 187 | oshape - points to the resulting shape structure | ||
| 188 | Return Code: | ||
| 189 | Zero - shape successfully derived | ||
| 190 | Negative - system error | ||
| 191 | **************************************************************************/ | ||
| 192 | 2980 | int shape_from_contour(SHAPE **oshape, const int *contour_x, | |
| 193 | const int *contour_y, const int ncontour) | ||
| 194 | { | ||
| 195 | 2980 | SHAPE *shape; | |
| 196 | 2980 | ROW *row; | |
| 197 | 2980 | int ret, i, xmin, ymin, xmax, ymax; | |
| 198 | |||
| 199 | /* Find xmin, ymin, xmax, ymax on contour. */ | ||
| 200 | 2980 | contour_limits(&xmin, &ymin, &xmax, &ymax, | |
| 201 | contour_x, contour_y, ncontour); | ||
| 202 | |||
| 203 | /* Allocate and initialize a shape structure. */ | ||
| 204 |
1/2✓ Branch 0 (4→13) taken 2980 times.
✗ Branch 1 (4→18) not taken.
|
2980 | if((ret = alloc_shape(&shape, xmin, ymin, xmax, ymax))) |
| 205 | /* If system error, then return error code. */ | ||
| 206 | return(ret); | ||
| 207 | |||
| 208 | /* Foreach point on contour ... */ | ||
| 209 |
2/2✓ Branch 0 (13→5) taken 41640 times.
✓ Branch 1 (13→16) taken 2980 times.
|
44620 | for(i = 0; i < ncontour; i++){ |
| 210 | /* Add point to corresponding row. */ | ||
| 211 | /* First set a pointer to the current row. We need to subtract */ | ||
| 212 | /* ymin because the rows are indexed relative to the top-most */ | ||
| 213 | /* scanline in the shape. */ | ||
| 214 | 41640 | row = shape->rows[contour_y[i]-ymin]; | |
| 215 | |||
| 216 | /* It is possible with complex shapes to reencounter points */ | ||
| 217 | /* already visited on a contour, especially at "pinching" points */ | ||
| 218 | /* along the contour. So we need to test to see if a point has */ | ||
| 219 | /* already been stored in the row. If not in row list already ... */ | ||
| 220 |
2/2✓ Branch 0 (6→7) taken 41614 times.
✓ Branch 1 (6→12) taken 26 times.
|
41640 | if(in_int_list(contour_x[i], row->xs, row->npts) < 0){ |
| 221 | /* If row is full ... */ | ||
| 222 |
1/2✗ Branch 0 (7→8) not taken.
✓ Branch 1 (7→11) taken 41614 times.
|
41614 | if(row->npts >= row->alloc){ |
| 223 | /* This should never happen becuase we have allocated */ | ||
| 224 | /* based on shape bounding limits. */ | ||
| 225 | ✗ | g_free(shape); | |
| 226 | ✗ | fprintf(stderr, | |
| 227 | "ERROR : shape_from_contour : row overflow\n"); | ||
| 228 | ✗ | return(-260); | |
| 229 | } | ||
| 230 | /* Assign the x-coord of the current contour point to the row */ | ||
| 231 | /* and bump the row's point counter. All the contour points */ | ||
| 232 | /* on the same row share the same y-coord. */ | ||
| 233 | 41614 | row->xs[row->npts++] = contour_x[i]; | |
| 234 | } | ||
| 235 | /* Otherwise, point is already stored in row, so ignore. */ | ||
| 236 | } | ||
| 237 | |||
| 238 | /* Foreach row in the shape. */ | ||
| 239 |
2/2✓ Branch 0 (16→14) taken 14050 times.
✓ Branch 1 (16→17) taken 2980 times.
|
17030 | for(i = 0; i < shape->nrows; i++) |
| 240 | /* Sort row points increasing on their x-coord. */ | ||
| 241 | 14050 | sort_row_on_x(shape->rows[i]); | |
| 242 | |||
| 243 | /* Assign shape structure to output pointer. */ | ||
| 244 | 2980 | *oshape = shape; | |
| 245 | |||
| 246 | /* Return normally. */ | ||
| 247 | 2980 | return(0); | |
| 248 | } | ||
| 249 | |||
| 250 | /************************************************************************* | ||
| 251 | ************************************************************************** | ||
| 252 | #cat: sort_row_on_x - Takes a row structure and sorts its points left-to- | ||
| 253 | #cat: right on X. | ||
| 254 | |||
| 255 | Input: | ||
| 256 | row - row structure to be sorted | ||
| 257 | Output: | ||
| 258 | row - row structure with points in sorted order | ||
| 259 | **************************************************************************/ | ||
| 260 | 14050 | void sort_row_on_x(ROW *row) | |
| 261 | { | ||
| 262 | /* Conduct a simple increasing bubble sort on the x-coords */ | ||
| 263 | /* in the given row. A bubble sort is satisfactory as the */ | ||
| 264 | /* number of points will be relatively small. */ | ||
| 265 | 14050 | bubble_sort_int_inc(row->xs, row->npts); | |
| 266 | 14050 | } | |
| 267 | |||
| 268 |