libfprint/nbis/mindtct/contour.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: CONTOUR.C | ||
| 49 | AUTHOR: Michael D. Garris | ||
| 50 | DATE: 05/11/1999 | ||
| 51 | UPDATED: 10/04/1999 Version 2 by MDG | ||
| 52 | UPDATED: 03/16/2005 by MDG | ||
| 53 | |||
| 54 | Contains routines responsible for extracting and analyzing | ||
| 55 | minutia feature contour lists as part of the NIST Latent | ||
| 56 | Fingerprint System (LFS). | ||
| 57 | |||
| 58 | *********************************************************************** | ||
| 59 | ROUTINES: | ||
| 60 | allocate_contour() | ||
| 61 | free_contour() | ||
| 62 | get_high_curvature_contour() | ||
| 63 | get_centered_contour() | ||
| 64 | trace_contour() | ||
| 65 | search_contour() | ||
| 66 | next_contour_pixel() | ||
| 67 | start_scan_nbr() | ||
| 68 | next_scan_nbr() | ||
| 69 | min_contour_theta() | ||
| 70 | contour_limits() | ||
| 71 | ***********************************************************************/ | ||
| 72 | |||
| 73 | #include <stdio.h> | ||
| 74 | #include <lfs.h> | ||
| 75 | |||
| 76 | /************************************************************************* | ||
| 77 | ************************************************************************** | ||
| 78 | #cat: allocate_contour - Allocates the lists needed to represent the | ||
| 79 | #cat: contour of a minutia feature (a ridge or valley-ending). | ||
| 80 | #cat: This includes two lists of coordinate pairs. The first is | ||
| 81 | #cat: the 8-connected chain of points interior to the feature | ||
| 82 | #cat: and are called the feature's "contour points". | ||
| 83 | #cat: The second is a list or corresponding points each | ||
| 84 | #cat: adjacent to its respective feature contour point in the first | ||
| 85 | #cat: list and on the exterior of the feature. These second points | ||
| 86 | #cat: are called the feature's "edge points". Don't be confused, | ||
| 87 | #cat: both lists of points are on the "edge". The first set is | ||
| 88 | #cat: guaranteed 8-connected and the color of the feature. The | ||
| 89 | #cat: second set is NOT guaranteed to be 8-connected and its points | ||
| 90 | #cat: are opposite the color of the feature. Remeber that "feature" | ||
| 91 | #cat: means either ridge-ending (black pixels) or valley-ending | ||
| 92 | #cat: (white pixels). | ||
| 93 | |||
| 94 | Input: | ||
| 95 | ncontour - number of items in each coordinate list to be allocated | ||
| 96 | Output: | ||
| 97 | ocontour_x - allocated x-coord list for feature's contour points | ||
| 98 | ocontour_y - allocated y-coord list for feature's contour points | ||
| 99 | ocontour_ex - allocated x-coord list for feature's edge points | ||
| 100 | ocontour_ey - allocated y-coord list for feature's edge points | ||
| 101 | Return Code: | ||
| 102 | Zero - lists were successfully allocated | ||
| 103 | Negative - system (allocation) error | ||
| 104 | **************************************************************************/ | ||
| 105 | 284094 | int allocate_contour(int **ocontour_x, int **ocontour_y, | |
| 106 | int **ocontour_ex, int **ocontour_ey, const int ncontour) | ||
| 107 | { | ||
| 108 | 284094 | int *contour_x, *contour_y, *contour_ex, *contour_ey; | |
| 109 | |||
| 110 |
1/2✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 284094 times.
|
284094 | ASSERT_SIZE_MUL(ncontour, sizeof(int)); |
| 111 | |||
| 112 | /* Allocate contour's x-coord list. */ | ||
| 113 | 284094 | contour_x = (int *)g_malloc(ncontour * sizeof(int)); | |
| 114 | |||
| 115 | /* Allocate contour's y-coord list. */ | ||
| 116 | 284094 | contour_y = (int *)g_malloc(ncontour * sizeof(int)); | |
| 117 | |||
| 118 | /* Allocate contour's edge x-coord list. */ | ||
| 119 | 284094 | contour_ex = (int *)g_malloc(ncontour * sizeof(int)); | |
| 120 | |||
| 121 | /* Allocate contour's edge y-coord list. */ | ||
| 122 | 284094 | contour_ey = (int *)g_malloc(ncontour * sizeof(int)); | |
| 123 | |||
| 124 | /* Otherwise, allocations successful, so assign output pointers. */ | ||
| 125 | 284094 | *ocontour_x = contour_x; | |
| 126 | 284094 | *ocontour_y = contour_y; | |
| 127 | 284094 | *ocontour_ex = contour_ex; | |
| 128 | 284094 | *ocontour_ey = contour_ey; | |
| 129 | |||
| 130 | /* Return normally. */ | ||
| 131 | 284094 | return(0); | |
| 132 | } | ||
| 133 | |||
| 134 | /************************************************************************* | ||
| 135 | ************************************************************************** | ||
| 136 | #cat: free_contour - Deallocates the lists used to represent the | ||
| 137 | #cat: contour of a minutia feature (a ridge or valley-ending). | ||
| 138 | #cat: This includes two lists of coordinate pairs. The first is | ||
| 139 | #cat: the 8-connected chain of points interior to the feature | ||
| 140 | #cat: and are called the feature's "contour points". | ||
| 141 | #cat: The second is a list or corresponding points each | ||
| 142 | #cat: adjacent to its respective feature contour point in the first | ||
| 143 | #cat: list and on the exterior of the feature. These second points | ||
| 144 | #cat: are called the feature's "edge points". | ||
| 145 | |||
| 146 | Input: | ||
| 147 | contour_x - x-coord list for feature's contour points | ||
| 148 | contour_y - y-coord list for feature's contour points | ||
| 149 | contour_ex - x-coord list for feature's edge points | ||
| 150 | contour_ey - y-coord list for feature's edge points | ||
| 151 | **************************************************************************/ | ||
| 152 | 284094 | void free_contour(int *contour_x, int *contour_y, | |
| 153 | int *contour_ex, int *contour_ey) | ||
| 154 | { | ||
| 155 | 284094 | g_free(contour_x); | |
| 156 | 284094 | g_free(contour_y); | |
| 157 | 284094 | g_free(contour_ex); | |
| 158 | 284094 | g_free(contour_ey); | |
| 159 | 284094 | } | |
| 160 | |||
| 161 | /************************************************************************* | ||
| 162 | ************************************************************************** | ||
| 163 | #cat: get_high_curvature_contour - Takes the pixel coordinate of a detected | ||
| 164 | #cat: minutia feature point and its corresponding/adjacent edge | ||
| 165 | #cat: pixel and attempts to extract a contour of specified length | ||
| 166 | #cat: of the feature's edge. The contour is extracted by walking | ||
| 167 | #cat: the feature's edge a specified number of steps clockwise and | ||
| 168 | #cat: then counter-clockwise. If a loop is detected while | ||
| 169 | #cat: extracting the contour, the contour of the loop is returned | ||
| 170 | #cat: with a return code of (LOOP_FOUND). If the process fails | ||
| 171 | #cat: to extract a contour of total specified length, then | ||
| 172 | #cat: the returned contour length is set to Zero, NO allocated | ||
| 173 | #cat: memory is returned in this case, and the return code is set | ||
| 174 | #cat: to Zero. An alternative implementation would be to return | ||
| 175 | #cat: the incomplete contour with a return code of (INCOMPLETE). | ||
| 176 | #cat: For now, NO allocated contour is returned in this case. | ||
| 177 | |||
| 178 | Input: | ||
| 179 | half_contour - half the length of the extracted contour | ||
| 180 | (full-length non-loop contour = (half_contourX2)+1) | ||
| 181 | x_loc - starting x-pixel coord of feature (interior to feature) | ||
| 182 | y_loc - starting y-pixel coord of feature (interior to feature) | ||
| 183 | x_edge - x-pixel coord of corresponding edge pixel | ||
| 184 | (exterior to feature) | ||
| 185 | y_edge - y-pixel coord of corresponding edge pixel | ||
| 186 | (exterior to feature) | ||
| 187 | bdata - binary image data (0==while & 1==black) | ||
| 188 | iw - width (in pixels) of image | ||
| 189 | ih - height (in pixels) of image | ||
| 190 | Output: | ||
| 191 | ocontour_x - x-pixel coords of contour (interior to feature) | ||
| 192 | ocontour_y - y-pixel coords of contour (interior to feature) | ||
| 193 | ocontour_ex - x-pixel coords of corresponding edge (exterior to feature) | ||
| 194 | ocontour_ey - y-pixel coords of corresponding edge (exterior to feature) | ||
| 195 | oncontour - number of contour points returned | ||
| 196 | Return Code: | ||
| 197 | Zero - resulting contour was successfully extracted or is empty | ||
| 198 | LOOP_FOUND - resulting contour forms a complete loop | ||
| 199 | Negative - system error | ||
| 200 | **************************************************************************/ | ||
| 201 | 3906 | int get_high_curvature_contour(int **ocontour_x, int **ocontour_y, | |
| 202 | int **ocontour_ex, int **ocontour_ey, int *oncontour, | ||
| 203 | const int half_contour, | ||
| 204 | const int x_loc, const int y_loc, | ||
| 205 | const int x_edge, const int y_edge, | ||
| 206 | unsigned char *bdata, const int iw, const int ih) | ||
| 207 | { | ||
| 208 | 3906 | int max_contour; | |
| 209 | 3906 | int *half1_x, *half1_y, *half1_ex, *half1_ey, nhalf1; | |
| 210 | 3906 | int *half2_x, *half2_y, *half2_ex, *half2_ey, nhalf2; | |
| 211 | 3906 | int *contour_x, *contour_y, *contour_ex, *contour_ey, ncontour; | |
| 212 | 3906 | int i, j, ret; | |
| 213 | |||
| 214 | /* Compute maximum length of complete contour */ | ||
| 215 | /* (2 half contours + feature point). */ | ||
| 216 | 3906 | max_contour = (half_contour<<1) + 1; | |
| 217 | |||
| 218 | /* Initialize output contour length to 0. */ | ||
| 219 | 3906 | *oncontour = 0; | |
| 220 | |||
| 221 | /* Get 1st half contour with clockwise neighbor trace. */ | ||
| 222 |
2/2✓ Branch 3 → 4 taken 183 times.
✓ Branch 3 → 15 taken 3723 times.
|
3906 | if((ret = trace_contour(&half1_x, &half1_y, &half1_ex, &half1_ey, &nhalf1, |
| 223 | half_contour, x_loc, y_loc, x_loc, y_loc, x_edge, y_edge, | ||
| 224 | SCAN_CLOCKWISE, bdata, iw, ih))){ | ||
| 225 | |||
| 226 | /* If trace was not possible ... */ | ||
| 227 |
1/2✓ Branch 4 → 5 taken 183 times.
✗ Branch 4 → 44 not taken.
|
183 | if(ret == IGNORE) |
| 228 | /* Return, with nothing allocated and contour length equal to 0. */ | ||
| 229 | return(0); | ||
| 230 | |||
| 231 | /* If 1st half contour forms a loop ... */ | ||
| 232 |
1/2✓ Branch 5 → 6 taken 183 times.
✗ Branch 5 → 44 not taken.
|
183 | if(ret == LOOP_FOUND){ |
| 233 | /* Need to reverse the 1st half contour so that the points are */ | ||
| 234 | /* in consistent order. */ | ||
| 235 | /* We need to add the original feature point to the list, so */ | ||
| 236 | /* set new contour length to one plus length of 1st half contour. */ | ||
| 237 | 183 | ncontour = nhalf1+1; | |
| 238 | /* Allocate new contour list. */ | ||
| 239 |
1/2✗ Branch 7 → 8 not taken.
✓ Branch 7 → 10 taken 183 times.
|
183 | if((ret = allocate_contour(&contour_x, &contour_y, |
| 240 | &contour_ex, &contour_ey, ncontour))){ | ||
| 241 | /* If allcation error, then deallocate memory allocated to */ | ||
| 242 | /* this point in this routine. */ | ||
| 243 | ✗ | free_contour(half1_x, half1_y, half1_ex, half1_ey); | |
| 244 | /* Return error code. */ | ||
| 245 | ✗ | return(ret); | |
| 246 | } | ||
| 247 | |||
| 248 | /* Otherwise, we have the new contour allocated, so store the */ | ||
| 249 | /* original feature point. */ | ||
| 250 | 183 | contour_x[0] = x_loc; | |
| 251 | 183 | contour_y[0] = y_loc; | |
| 252 | 183 | contour_ex[0] = x_edge; | |
| 253 | 183 | contour_ey[0] = y_edge; | |
| 254 | |||
| 255 | /* Now store the first half contour in reverse order. */ | ||
| 256 |
2/2✓ Branch 12 → 11 taken 1280 times.
✓ Branch 12 → 13 taken 183 times.
|
1463 | for(i = 1, j = nhalf1-1; i < ncontour; i++, j--){ |
| 257 | 1280 | contour_x[i] = half1_x[j]; | |
| 258 | 1280 | contour_y[i] = half1_y[j]; | |
| 259 | 1280 | contour_ex[i] = half1_ex[j]; | |
| 260 | 1280 | contour_ey[i] = half1_ey[j]; | |
| 261 | } | ||
| 262 | |||
| 263 | /* Deallocate the first half contour. */ | ||
| 264 | 183 | free_contour(half1_x, half1_y, half1_ex, half1_ey); | |
| 265 | |||
| 266 | /* Assign the output pointers. */ | ||
| 267 | 183 | *ocontour_x = contour_x; | |
| 268 | 183 | *ocontour_y = contour_y; | |
| 269 | 183 | *ocontour_ex = contour_ex; | |
| 270 | 183 | *ocontour_ey = contour_ey; | |
| 271 | 183 | *oncontour = ncontour; | |
| 272 | |||
| 273 | /* Return LOOP_FOUND for further processing. */ | ||
| 274 | 183 | return(LOOP_FOUND); | |
| 275 | } | ||
| 276 | |||
| 277 | /* Otherwise, return the system error code from the first */ | ||
| 278 | /* call to trace_contour. */ | ||
| 279 | return(ret); | ||
| 280 | } | ||
| 281 | |||
| 282 | /* If 1st half contour not complete ... */ | ||
| 283 |
1/2✗ Branch 15 → 16 not taken.
✓ Branch 15 → 18 taken 3723 times.
|
3723 | if(nhalf1 < half_contour){ |
| 284 | /* Deallocate the partial contour. */ | ||
| 285 | ✗ | free_contour(half1_x, half1_y, half1_ex, half1_ey); | |
| 286 | /* Return, with nothing allocated and contour length equal to 0. */ | ||
| 287 | ✗ | return(0); | |
| 288 | } | ||
| 289 | |||
| 290 | /* Otherwise, we have a complete 1st half contour... */ | ||
| 291 | /* Get 2nd half contour with counter-clockwise neighbor trace. */ | ||
| 292 | /* Use the last point from the first contour trace as the */ | ||
| 293 | /* point to test for a loop when tracing the second contour. */ | ||
| 294 |
2/2✓ Branch 19 → 20 taken 265 times.
✓ Branch 19 → 26 taken 3458 times.
|
3723 | if((ret = trace_contour(&half2_x, &half2_y, &half2_ex, &half2_ey, &nhalf2, |
| 295 | 3723 | half_contour, half1_x[nhalf1-1], half1_y[nhalf1-1], | |
| 296 | x_loc, y_loc, x_edge, y_edge, | ||
| 297 | SCAN_COUNTER_CLOCKWISE, bdata, iw, ih))){ | ||
| 298 | |||
| 299 | /* If 2nd trace was not possible ... */ | ||
| 300 |
1/2✗ Branch 20 → 21 not taken.
✓ Branch 20 → 23 taken 265 times.
|
265 | if(ret == IGNORE){ |
| 301 | /* Deallocate the 1st half contour. */ | ||
| 302 | ✗ | free_contour(half1_x, half1_y, half1_ex, half1_ey); | |
| 303 | /* Return, with nothing allocated and contour length equal to 0. */ | ||
| 304 | ✗ | return(0); | |
| 305 | } | ||
| 306 | |||
| 307 | /* If non-zero return code is NOT LOOP_FOUND, then system error ... */ | ||
| 308 |
1/2✗ Branch 23 → 24 not taken.
✓ Branch 23 → 30 taken 265 times.
|
265 | if(ret != LOOP_FOUND){ |
| 309 | /* Deallocate the 1st half contour. */ | ||
| 310 | ✗ | free_contour(half1_x, half1_y, half1_ex, half1_ey); | |
| 311 | /* Return system error. */ | ||
| 312 | ✗ | return(ret); | |
| 313 | } | ||
| 314 | } | ||
| 315 | |||
| 316 | /* If 2nd half NOT a loop AND not complete ... */ | ||
| 317 |
1/2✗ Branch 26 → 27 not taken.
✓ Branch 26 → 30 taken 3458 times.
|
3458 | if((ret != LOOP_FOUND) && (nhalf2 < half_contour)){ |
| 318 | /* Deallocate both half contours. */ | ||
| 319 | ✗ | free_contour(half1_x, half1_y, half1_ex, half1_ey); | |
| 320 | ✗ | free_contour(half2_x, half2_y, half2_ex, half2_ey); | |
| 321 | /* Return, with nothing allocated and contour length equal to 0. */ | ||
| 322 | ✗ | return(0); | |
| 323 | } | ||
| 324 | |||
| 325 | /* Otherwise we have a full 1st half contour and a 2nd half contour */ | ||
| 326 | /* that is either a loop or complete. In either case we need to */ | ||
| 327 | /* concatenate the two half contours into one longer contour. */ | ||
| 328 | |||
| 329 | /* Allocate output contour list. Go ahead and allocate the */ | ||
| 330 | /* "max_contour" amount even though the resulting contour will */ | ||
| 331 | /* likely be shorter if it forms a loop. */ | ||
| 332 |
1/2✗ Branch 31 → 32 not taken.
✓ Branch 31 → 35 taken 3723 times.
|
3723 | if((ret = allocate_contour(&contour_x, &contour_y, |
| 333 | &contour_ex, &contour_ey, max_contour))){ | ||
| 334 | /* If allcation error, then deallocate memory allocated to */ | ||
| 335 | /* this point in this routine. */ | ||
| 336 | ✗ | free_contour(half1_x, half1_y, half1_ex, half1_ey); | |
| 337 | ✗ | free_contour(half2_x, half2_y, half2_ex, half2_ey); | |
| 338 | /* Return error code. */ | ||
| 339 | ✗ | return(ret); | |
| 340 | } | ||
| 341 | |||
| 342 | /* Set the current contour point counter to 0 */ | ||
| 343 | 3723 | ncontour = 0; | |
| 344 | |||
| 345 | /* Copy 1st half contour into output contour buffers. */ | ||
| 346 | /* This contour was collected clockwise, so it's points */ | ||
| 347 | /* are entered in reverse order of the trace. The result */ | ||
| 348 | /* is the first point in the output contour if farthest */ | ||
| 349 | /* from the starting feature point. */ | ||
| 350 |
2/2✓ Branch 37 → 36 taken 52122 times.
✓ Branch 37 → 38 taken 3723 times.
|
55845 | for(i = 0, j = nhalf1-1; i < nhalf1; i++, j--){ |
| 351 | 52122 | contour_x[i] = half1_x[j]; | |
| 352 | 52122 | contour_y[i] = half1_y[j]; | |
| 353 | 52122 | contour_ex[i] = half1_ex[j]; | |
| 354 | 52122 | contour_ey[i] = half1_ey[j]; | |
| 355 | 52122 | ncontour++; | |
| 356 | } | ||
| 357 | |||
| 358 | /* Deallocate 1st half contour. */ | ||
| 359 | 3723 | free_contour(half1_x, half1_y, half1_ex, half1_ey); | |
| 360 | |||
| 361 | /* Next, store starting feature point into output contour buffers. */ | ||
| 362 | 3723 | contour_x[nhalf1] = x_loc; | |
| 363 | 3723 | contour_y[nhalf1] = y_loc; | |
| 364 | 3723 | contour_ex[nhalf1] = x_edge; | |
| 365 | 3723 | contour_ey[nhalf1] = y_edge; | |
| 366 | 3723 | ncontour++; | |
| 367 | |||
| 368 | /* Now, append 2nd half contour to permanent contour buffers. */ | ||
| 369 |
2/2✓ Branch 41 → 40 taken 50120 times.
✓ Branch 41 → 42 taken 3723 times.
|
53843 | for(i = 0, j = nhalf1+1; i < nhalf2; i++, j++){ |
| 370 | 50120 | contour_x[j] = half2_x[i]; | |
| 371 | 50120 | contour_y[j] = half2_y[i]; | |
| 372 | 50120 | contour_ex[j] = half2_ex[i]; | |
| 373 | 50120 | contour_ey[j] = half2_ey[i]; | |
| 374 | 50120 | ncontour++; | |
| 375 | } | ||
| 376 | |||
| 377 | /* Deallocate 2nd half contour. */ | ||
| 378 | 3723 | free_contour(half2_x, half2_y, half2_ex, half2_ey); | |
| 379 | |||
| 380 | /* Assign outputs contour to output ponters. */ | ||
| 381 | 3723 | *ocontour_x = contour_x; | |
| 382 | 3723 | *ocontour_y = contour_y; | |
| 383 | 3723 | *ocontour_ex = contour_ex; | |
| 384 | 3723 | *ocontour_ey = contour_ey; | |
| 385 | 3723 | *oncontour = ncontour; | |
| 386 | |||
| 387 | /* Return the resulting return code form the 2nd call to trace_contour */ | ||
| 388 | /* (the value will either be 0 or LOOP_FOUND). */ | ||
| 389 | 3723 | return(ret); | |
| 390 | } | ||
| 391 | |||
| 392 | /************************************************************************* | ||
| 393 | ************************************************************************** | ||
| 394 | #cat: get_centered_contour - Takes the pixel coordinate of a detected | ||
| 395 | #cat: minutia feature point and its corresponding/adjacent edge | ||
| 396 | #cat: pixel and attempts to extract a contour of specified length | ||
| 397 | #cat: of the feature's edge. The contour is extracted by walking | ||
| 398 | #cat: the feature's edge a specified number of steps clockwise and | ||
| 399 | #cat: then counter-clockwise. If a loop is detected while | ||
| 400 | #cat: extracting the contour, no contour is returned with a return | ||
| 401 | #cat: code of (LOOP_FOUND). If the process fails to extract a | ||
| 402 | #cat: a complete contour, a code of INCOMPLETE is returned. | ||
| 403 | |||
| 404 | Input: | ||
| 405 | half_contour - half the length of the extracted contour | ||
| 406 | (full-length non-loop contour = (half_contourX2)+1) | ||
| 407 | x_loc - starting x-pixel coord of feature (interior to feature) | ||
| 408 | y_loc - starting y-pixel coord of feature (interior to feature) | ||
| 409 | x_edge - x-pixel coord of corresponding edge pixel | ||
| 410 | (exterior to feature) | ||
| 411 | y_edge - y-pixel coord of corresponding edge pixel | ||
| 412 | (exterior to feature) | ||
| 413 | bdata - binary image data (0==while & 1==black) | ||
| 414 | iw - width (in pixels) of image | ||
| 415 | ih - height (in pixels) of image | ||
| 416 | Output: | ||
| 417 | ocontour_x - x-pixel coords of contour (interior to feature) | ||
| 418 | ocontour_y - y-pixel coords of contour (interior to feature) | ||
| 419 | ocontour_ex - x-pixel coords of corresponding edge (exterior to feature) | ||
| 420 | ocontour_ey - y-pixel coords of corresponding edge (exterior to feature) | ||
| 421 | oncontour - number of contour points returned | ||
| 422 | Return Code: | ||
| 423 | Zero - resulting contour was successfully extracted or is empty | ||
| 424 | LOOP_FOUND - resulting contour forms a complete loop | ||
| 425 | IGNORE - contour could not be traced due to problem starting | ||
| 426 | conditions | ||
| 427 | INCOMPLETE - resulting contour was not long enough | ||
| 428 | Negative - system error | ||
| 429 | **************************************************************************/ | ||
| 430 | 23774 | int get_centered_contour(int **ocontour_x, int **ocontour_y, | |
| 431 | int **ocontour_ex, int **ocontour_ey, int *oncontour, | ||
| 432 | const int half_contour, | ||
| 433 | const int x_loc, const int y_loc, | ||
| 434 | const int x_edge, const int y_edge, | ||
| 435 | unsigned char *bdata, const int iw, const int ih) | ||
| 436 | { | ||
| 437 | 23774 | int max_contour; | |
| 438 | 23774 | int *half1_x, *half1_y, *half1_ex, *half1_ey, nhalf1; | |
| 439 | 23774 | int *half2_x, *half2_y, *half2_ex, *half2_ey, nhalf2; | |
| 440 | 23774 | int *contour_x, *contour_y, *contour_ex, *contour_ey, ncontour; | |
| 441 | 23774 | int i, j, ret; | |
| 442 | |||
| 443 |
1/2✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 23774 times.
|
23774 | g_assert (half_contour > 0); |
| 444 | |||
| 445 | /* Compute maximum length of complete contour */ | ||
| 446 | /* (2 half contours + feature point). */ | ||
| 447 | 23774 | max_contour = (half_contour<<1) + 1; | |
| 448 | |||
| 449 | /* Initialize output contour length to 0. */ | ||
| 450 | 23774 | *oncontour = 0; | |
| 451 | |||
| 452 | /* Get 1st half contour with clockwise neighbor trace. */ | ||
| 453 | 23774 | ret = trace_contour(&half1_x, &half1_y, &half1_ex, &half1_ey, &nhalf1, | |
| 454 | half_contour, x_loc, y_loc, x_loc, y_loc, x_edge, y_edge, | ||
| 455 | SCAN_CLOCKWISE, bdata, iw, ih); | ||
| 456 | |||
| 457 | /* If system error occurred ... */ | ||
| 458 |
1/2✓ Branch 5 → 6 taken 23774 times.
✗ Branch 5 → 42 not taken.
|
23774 | if(ret < 0){ |
| 459 | /* Return error code. */ | ||
| 460 | return(ret); | ||
| 461 | } | ||
| 462 | |||
| 463 | /* If trace was not possible ... */ | ||
| 464 |
2/2✓ Branch 6 → 7 taken 23728 times.
✓ Branch 6 → 42 taken 46 times.
|
23774 | if(ret == IGNORE) |
| 465 | /* Return IGNORE, with nothing allocated. */ | ||
| 466 | return(IGNORE); | ||
| 467 | |||
| 468 | /* If 1st half contour forms a loop ... */ | ||
| 469 |
2/2✓ Branch 7 → 8 taken 12 times.
✓ Branch 7 → 10 taken 23716 times.
|
23728 | if(ret == LOOP_FOUND){ |
| 470 | /* Deallocate loop's contour. */ | ||
| 471 | 12 | free_contour(half1_x, half1_y, half1_ex, half1_ey); | |
| 472 | /* Return LOOP_FOUND, with nothing allocated. */ | ||
| 473 | 12 | return(LOOP_FOUND); | |
| 474 | } | ||
| 475 | |||
| 476 | /* If 1st half contour not complete ... */ | ||
| 477 |
1/2✗ Branch 10 → 11 not taken.
✓ Branch 10 → 13 taken 23716 times.
|
23716 | if(nhalf1 < half_contour){ |
| 478 | /* Deallocate the partial contour. */ | ||
| 479 | ✗ | free_contour(half1_x, half1_y, half1_ex, half1_ey); | |
| 480 | /* Return, with nothing allocated and contour length equal to 0. */ | ||
| 481 | ✗ | return(INCOMPLETE); | |
| 482 | } | ||
| 483 | |||
| 484 | /* Otherwise, we have a complete 1st half contour... */ | ||
| 485 | /* Get 2nd half contour with counter-clockwise neighbor trace. */ | ||
| 486 | /* Use the last point from the first contour trace as the */ | ||
| 487 | /* point to test for a loop when tracing the second contour. */ | ||
| 488 | 47432 | ret = trace_contour(&half2_x, &half2_y, &half2_ex, &half2_ey, &nhalf2, | |
| 489 | 23716 | half_contour, half1_x[nhalf1-1], half1_y[nhalf1-1], | |
| 490 | x_loc, y_loc, x_edge, y_edge, | ||
| 491 | SCAN_COUNTER_CLOCKWISE, bdata, iw, ih); | ||
| 492 | |||
| 493 | /* If system error occurred on 2nd trace ... */ | ||
| 494 |
1/2✗ Branch 14 → 15 not taken.
✓ Branch 14 → 17 taken 23716 times.
|
23716 | if(ret < 0){ |
| 495 | /* Deallocate loop's contour. */ | ||
| 496 | ✗ | free_contour(half1_x, half1_y, half1_ex, half1_ey); | |
| 497 | /* Return error code. */ | ||
| 498 | ✗ | return(ret); | |
| 499 | } | ||
| 500 | |||
| 501 | /* If 2nd trace was not possible ... */ | ||
| 502 |
1/2✗ Branch 17 → 18 not taken.
✓ Branch 17 → 20 taken 23716 times.
|
23716 | if(ret == IGNORE){ |
| 503 | /* Deallocate the 1st half contour. */ | ||
| 504 | ✗ | free_contour(half1_x, half1_y, half1_ex, half1_ey); | |
| 505 | /* Return, with nothing allocated and contour length equal to 0. */ | ||
| 506 | ✗ | return(IGNORE); | |
| 507 | } | ||
| 508 | |||
| 509 | /* If 2nd trace forms a loop ... */ | ||
| 510 |
2/2✓ Branch 20 → 21 taken 24 times.
✓ Branch 20 → 24 taken 23692 times.
|
23716 | if(ret == LOOP_FOUND){ |
| 511 | /* Deallocate 1st and 2nd half contours. */ | ||
| 512 | 24 | free_contour(half1_x, half1_y, half1_ex, half1_ey); | |
| 513 | 24 | free_contour(half2_x, half2_y, half2_ex, half2_ey); | |
| 514 | /* Return LOOP_FOUND, with nothing allocated. */ | ||
| 515 | 24 | return(LOOP_FOUND); | |
| 516 | } | ||
| 517 | |||
| 518 | /* If 2nd half contour not complete ... */ | ||
| 519 |
1/2✗ Branch 24 → 25 not taken.
✓ Branch 24 → 28 taken 23692 times.
|
23692 | if(nhalf2 < half_contour){ |
| 520 | /* Deallocate 1st and 2nd half contours. */ | ||
| 521 | ✗ | free_contour(half1_x, half1_y, half1_ex, half1_ey); | |
| 522 | ✗ | free_contour(half2_x, half2_y, half2_ex, half2_ey); | |
| 523 | /* Return, with nothing allocated and contour length equal to 0. */ | ||
| 524 | ✗ | return(INCOMPLETE); | |
| 525 | } | ||
| 526 | |||
| 527 | /* Otherwise we have a full 1st half contour and a 2nd half contour */ | ||
| 528 | /* that do not form a loop and are complete. We now need to */ | ||
| 529 | /* concatenate the two half contours into one longer contour. */ | ||
| 530 | |||
| 531 | /* Allocate output contour list. */ | ||
| 532 |
1/2✗ Branch 29 → 30 not taken.
✓ Branch 29 → 33 taken 23692 times.
|
23692 | if((ret = allocate_contour(&contour_x, &contour_y, |
| 533 | &contour_ex, &contour_ey, max_contour))){ | ||
| 534 | /* If allcation error, then deallocate memory allocated to */ | ||
| 535 | /* this point in this routine. */ | ||
| 536 | ✗ | free_contour(half1_x, half1_y, half1_ex, half1_ey); | |
| 537 | ✗ | free_contour(half2_x, half2_y, half2_ex, half2_ey); | |
| 538 | /* Return error code. */ | ||
| 539 | ✗ | return(ret); | |
| 540 | } | ||
| 541 | |||
| 542 | /* Set the current contour point counter to 0 */ | ||
| 543 | 23692 | ncontour = 0; | |
| 544 | |||
| 545 | /* Copy 1st half contour into output contour buffers. */ | ||
| 546 | /* This contour was collected clockwise, so it's points */ | ||
| 547 | /* are entered in reverse order of the trace. The result */ | ||
| 548 | /* is the first point in the output contour if farthest */ | ||
| 549 | /* from the starting feature point. */ | ||
| 550 |
2/2✓ Branch 35 → 34 taken 165844 times.
✓ Branch 35 → 36 taken 23692 times.
|
189536 | for(i = 0, j = nhalf1-1; i < nhalf1; i++, j--){ |
| 551 | 165844 | contour_x[i] = half1_x[j]; | |
| 552 | 165844 | contour_y[i] = half1_y[j]; | |
| 553 | 165844 | contour_ex[i] = half1_ex[j]; | |
| 554 | 165844 | contour_ey[i] = half1_ey[j]; | |
| 555 | 165844 | ncontour++; | |
| 556 | } | ||
| 557 | |||
| 558 | /* Deallocate 1st half contour. */ | ||
| 559 | 23692 | free_contour(half1_x, half1_y, half1_ex, half1_ey); | |
| 560 | |||
| 561 | /* Next, store starting feature point into output contour buffers. */ | ||
| 562 | 23692 | contour_x[nhalf1] = x_loc; | |
| 563 | 23692 | contour_y[nhalf1] = y_loc; | |
| 564 | 23692 | contour_ex[nhalf1] = x_edge; | |
| 565 | 23692 | contour_ey[nhalf1] = y_edge; | |
| 566 | 23692 | ncontour++; | |
| 567 | |||
| 568 | /* Now, append 2nd half contour to permanent contour buffers. */ | ||
| 569 |
2/2✓ Branch 39 → 38 taken 165844 times.
✓ Branch 39 → 40 taken 23692 times.
|
189536 | for(i = 0, j = nhalf1+1; i < nhalf2; i++, j++){ |
| 570 | 165844 | contour_x[j] = half2_x[i]; | |
| 571 | 165844 | contour_y[j] = half2_y[i]; | |
| 572 | 165844 | contour_ex[j] = half2_ex[i]; | |
| 573 | 165844 | contour_ey[j] = half2_ey[i]; | |
| 574 | 165844 | ncontour++; | |
| 575 | } | ||
| 576 | |||
| 577 | /* Deallocate 2nd half contour. */ | ||
| 578 | 23692 | free_contour(half2_x, half2_y, half2_ex, half2_ey); | |
| 579 | |||
| 580 | /* Assign outputs contour to output ponters. */ | ||
| 581 | 23692 | *ocontour_x = contour_x; | |
| 582 | 23692 | *ocontour_y = contour_y; | |
| 583 | 23692 | *ocontour_ex = contour_ex; | |
| 584 | 23692 | *ocontour_ey = contour_ey; | |
| 585 | 23692 | *oncontour = ncontour; | |
| 586 | |||
| 587 | /* Return normally. */ | ||
| 588 | 23692 | return(0); | |
| 589 | } | ||
| 590 | |||
| 591 | /************************************************************************* | ||
| 592 | ************************************************************************** | ||
| 593 | #cat: trace_contour - Takes the pixel coordinate of a detected minutia | ||
| 594 | #cat: feature point and its corresponding/adjacent edge pixel | ||
| 595 | #cat: and extracts a contour (up to a specified maximum length) | ||
| 596 | #cat: of the feature's edge in either a clockwise or counter- | ||
| 597 | #cat: clockwise direction. A second point is specified, such that | ||
| 598 | #cat: if this point is encounted while extracting the contour, | ||
| 599 | #cat: it is to be assumed that a loop has been found and a code | ||
| 600 | #cat: of (LOOP_FOUND) is returned with the contour. By independently | ||
| 601 | #cat: specifying this point, successive calls can be made to | ||
| 602 | #cat: this routine from the same starting point, and loops across | ||
| 603 | #cat: successive calls can be detected. | ||
| 604 | |||
| 605 | Input: | ||
| 606 | max_len - maximum length of contour to be extracted | ||
| 607 | x_loop - x-pixel coord of point, if encountered, triggers LOOP_FOUND | ||
| 608 | y_loop - y-pixel coord of point, if encountered, triggers LOOP_FOUND | ||
| 609 | x_loc - starting x-pixel coord of feature (interior to feature) | ||
| 610 | y_loc - starting y-pixel coord of feature (interior to feature) | ||
| 611 | x_edge - x-pixel coord of corresponding edge pixel (exterior to feature) | ||
| 612 | y_edge - y-pixel coord of corresponding edge pixel (exterior to feature) | ||
| 613 | scan_clock - direction in which neighboring pixels are to be scanned | ||
| 614 | for the next contour pixel | ||
| 615 | bdata - binary image data (0==while & 1==black) | ||
| 616 | iw - width (in pixels) of image | ||
| 617 | ih - height (in pixels) of image | ||
| 618 | Output: | ||
| 619 | ocontour_x - x-pixel coords of contour (interior to feature) | ||
| 620 | ocontour_y - y-pixel coords of contour (interior to feature) | ||
| 621 | ocontour_ex - x-pixel coords of corresponding edge (exterior to feature) | ||
| 622 | ocontour_ey - y-pixel coords of corresponding edge (exterior to feature) | ||
| 623 | oncontour - number of contour points returned | ||
| 624 | Return Code: | ||
| 625 | Zero - resulting contour was successfully allocated and extracted | ||
| 626 | LOOP_FOUND - resulting contour forms a complete loop | ||
| 627 | IGNORE - trace is not possible due to state of inputs | ||
| 628 | Negative - system error | ||
| 629 | **************************************************************************/ | ||
| 630 | 253933 | int trace_contour(int **ocontour_x, int **ocontour_y, | |
| 631 | int **ocontour_ex, int **ocontour_ey, int *oncontour, | ||
| 632 | const int max_len, const int x_loop, const int y_loop, | ||
| 633 | const int x_loc, const int y_loc, | ||
| 634 | const int x_edge, const int y_edge, | ||
| 635 | const int scan_clock, | ||
| 636 | unsigned char *bdata, const int iw, const int ih) | ||
| 637 | { | ||
| 638 | 253933 | int *contour_x, *contour_y, *contour_ex, *contour_ey, ncontour; | |
| 639 | 253933 | int cur_x_loc, cur_y_loc; | |
| 640 | 253933 | int cur_x_edge, cur_y_edge; | |
| 641 | 253933 | int next_x_loc, next_y_loc; | |
| 642 | 253933 | int next_x_edge, next_y_edge; | |
| 643 | 253933 | int i, ret; | |
| 644 | |||
| 645 | /* Check to make sure that the feature and edge values are opposite. */ | ||
| 646 | 253933 | if(*(bdata+(y_loc*iw)+x_loc) == | |
| 647 |
2/2✓ Branch 2 → 3 taken 253601 times.
✓ Branch 2 → 14 taken 332 times.
|
253933 | *(bdata+(y_edge*iw)+x_edge)) |
| 648 | /* If not opposite, then the trace will not work, so return IGNORE. */ | ||
| 649 | return(IGNORE); | ||
| 650 | |||
| 651 | /* Allocate contour buffers. */ | ||
| 652 |
1/2✓ Branch 4 → 12 taken 253601 times.
✗ Branch 4 → 14 not taken.
|
253601 | if((ret = allocate_contour(&contour_x, &contour_y, |
| 653 | &contour_ex, &contour_ey, max_len))){ | ||
| 654 | /* If allocation error, return code. */ | ||
| 655 | return(ret); | ||
| 656 | } | ||
| 657 | |||
| 658 | /* Set pixel counter to 0. */ | ||
| 659 | ncontour = 0; | ||
| 660 | |||
| 661 | /* Set up for finding first contour pixel. */ | ||
| 662 | cur_x_loc = x_loc; | ||
| 663 | cur_y_loc = y_loc; | ||
| 664 | cur_x_edge = x_edge; | ||
| 665 | cur_y_edge = y_edge; | ||
| 666 | |||
| 667 | /* Foreach pixel to be collected on the feature's contour... */ | ||
| 668 |
2/2✓ Branch 12 → 5 taken 3555368 times.
✓ Branch 12 → 13 taken 235684 times.
|
3791052 | for(i = 0; i < max_len; i++){ |
| 669 | /* Find the next contour pixel. */ | ||
| 670 |
1/2✓ Branch 6 → 7 taken 3555368 times.
✗ Branch 6 → 11 not taken.
|
3555368 | if(next_contour_pixel(&next_x_loc, &next_y_loc, |
| 671 | &next_x_edge, &next_y_edge, | ||
| 672 | cur_x_loc, cur_y_loc, | ||
| 673 | cur_x_edge, cur_y_edge, | ||
| 674 | scan_clock, bdata, iw, ih)){ | ||
| 675 | |||
| 676 | /* If we trace back around to the specified starting */ | ||
| 677 | /* feature location... */ | ||
| 678 |
4/4✓ Branch 7 → 8 taken 183880 times.
✓ Branch 7 → 10 taken 3371488 times.
✓ Branch 8 → 9 taken 17917 times.
✓ Branch 8 → 10 taken 165963 times.
|
3555368 | if((next_x_loc == x_loop) && (next_y_loc == y_loop)){ |
| 679 | /* Then we have found a loop, so return what we */ | ||
| 680 | /* have traced to this point. */ | ||
| 681 | 17917 | *ocontour_x = contour_x; | |
| 682 | 17917 | *ocontour_y = contour_y; | |
| 683 | 17917 | *ocontour_ex = contour_ex; | |
| 684 | 17917 | *ocontour_ey = contour_ey; | |
| 685 | 17917 | *oncontour = ncontour; | |
| 686 | 17917 | return(LOOP_FOUND); | |
| 687 | } | ||
| 688 | |||
| 689 | /* Otherwise, we found another point on our feature's contour, */ | ||
| 690 | /* so store the new contour point. */ | ||
| 691 | 3537451 | contour_x[i] = next_x_loc; | |
| 692 | 3537451 | contour_y[i] = next_y_loc; | |
| 693 | 3537451 | contour_ex[i] = next_x_edge; | |
| 694 | 3537451 | contour_ey[i] = next_y_edge; | |
| 695 | /* Bump the number of points stored. */ | ||
| 696 | 3537451 | ncontour++; | |
| 697 | |||
| 698 | /* Set up for finding next contour pixel. */ | ||
| 699 | 3537451 | cur_x_loc = next_x_loc; | |
| 700 | 3537451 | cur_y_loc = next_y_loc; | |
| 701 | 3537451 | cur_x_edge = next_x_edge; | |
| 702 | 3537451 | cur_y_edge = next_y_edge; | |
| 703 | } | ||
| 704 | /* Otherwise, no new contour point found ... */ | ||
| 705 | else{ | ||
| 706 | /* So, stop short and return the number of pixels found */ | ||
| 707 | /* on the contour to this point. */ | ||
| 708 | ✗ | *ocontour_x = contour_x; | |
| 709 | ✗ | *ocontour_y = contour_y; | |
| 710 | ✗ | *ocontour_ex = contour_ex; | |
| 711 | ✗ | *ocontour_ey = contour_ey; | |
| 712 | ✗ | *oncontour = ncontour; | |
| 713 | |||
| 714 | /* Return normally. */ | ||
| 715 | ✗ | return(0); | |
| 716 | } | ||
| 717 | } | ||
| 718 | |||
| 719 | /* If we get here, we successfully found the maximum points we */ | ||
| 720 | /* were looking for on the feature contour, so assign the contour */ | ||
| 721 | /* buffers to the output pointers and return. */ | ||
| 722 | 235684 | *ocontour_x = contour_x; | |
| 723 | 235684 | *ocontour_y = contour_y; | |
| 724 | 235684 | *ocontour_ex = contour_ex; | |
| 725 | 235684 | *ocontour_ey = contour_ey; | |
| 726 | 235684 | *oncontour = ncontour; | |
| 727 | |||
| 728 | /* Return normally. */ | ||
| 729 | 235684 | return(0); | |
| 730 | } | ||
| 731 | |||
| 732 | /************************************************************************* | ||
| 733 | ************************************************************************** | ||
| 734 | #cat: search_contour - Walk the contour of a minutia feature starting at a | ||
| 735 | #cat: specified point on the feature and walking N steps in the | ||
| 736 | #cat: specified direction (clockwise or counter-clockwise), looking | ||
| 737 | #cat: for a second specified point. In this code, "feature" is | ||
| 738 | #cat: consistently referring to either the black interior edge of | ||
| 739 | #cat: a ridge-ending or the white interior edge of a valley-ending | ||
| 740 | #cat: (bifurcation). The term "edge of the feature" refers to | ||
| 741 | #cat: neighboring pixels on the "exterior" edge of the feature. | ||
| 742 | #cat: So "edge" pixels are opposite in color from the interior | ||
| 743 | #cat: feature pixels. | ||
| 744 | |||
| 745 | Input: | ||
| 746 | x_search - x-pixel coord of point being searched for | ||
| 747 | y_search - y-pixel coord of point being searched for | ||
| 748 | search_len - number of step to walk contour in search | ||
| 749 | x_loc - starting x-pixel coord of feature (interior to feature) | ||
| 750 | y_loc - starting y-pixel coord of feature (interior to feature) | ||
| 751 | x_edge - x-pixel coord of corresponding edge pixel | ||
| 752 | (exterior to feature) | ||
| 753 | y_edge - y-pixel coord of corresponding edge pixel | ||
| 754 | (exterior to feature) | ||
| 755 | scan_clock - direction in which neighbor pixels are to be scanned | ||
| 756 | (clockwise or counter-clockwise) | ||
| 757 | bdata - binary image data (0==while & 1==black) | ||
| 758 | iw - width (in pixels) of image | ||
| 759 | ih - height (in pixels) of image | ||
| 760 | Return Code: | ||
| 761 | NOT_FOUND - desired pixel not found along N steps of feature's contour | ||
| 762 | FOUND - desired pixel WAS found along N steps of feature's contour | ||
| 763 | **************************************************************************/ | ||
| 764 | 106850 | int search_contour(const int x_search, const int y_search, | |
| 765 | const int search_len, | ||
| 766 | const int x_loc, const int y_loc, | ||
| 767 | const int x_edge, const int y_edge, | ||
| 768 | const int scan_clock, | ||
| 769 | unsigned char *bdata, const int iw, const int ih) | ||
| 770 | { | ||
| 771 | 106850 | int cur_x_loc, cur_y_loc; | |
| 772 | 106850 | int cur_x_edge, cur_y_edge; | |
| 773 | 106850 | int next_x_loc, next_y_loc; | |
| 774 | 106850 | int next_x_edge, next_y_edge; | |
| 775 | 106850 | int i; | |
| 776 | |||
| 777 | /* Set up for finding first contour pixel. */ | ||
| 778 | 106850 | cur_x_loc = x_loc; | |
| 779 | 106850 | cur_y_loc = y_loc; | |
| 780 | 106850 | cur_x_edge = x_edge; | |
| 781 | 106850 | cur_y_edge = y_edge; | |
| 782 | |||
| 783 | /* Foreach point to be collected on the feature's contour... */ | ||
| 784 |
2/2✓ Branch 8 → 3 taken 957076 times.
✓ Branch 8 → 9 taken 90208 times.
|
1047284 | for(i = 0; i < search_len; i++){ |
| 785 | /* Find the next contour pixel. */ | ||
| 786 |
1/2✓ Branch 4 → 5 taken 957076 times.
✗ Branch 4 → 9 not taken.
|
957076 | if(next_contour_pixel(&next_x_loc, &next_y_loc, |
| 787 | &next_x_edge, &next_y_edge, | ||
| 788 | cur_x_loc, cur_y_loc, | ||
| 789 | cur_x_edge, cur_y_edge, | ||
| 790 | scan_clock, bdata, iw, ih)){ | ||
| 791 | |||
| 792 | /* If we find the point we are looking for on the contour... */ | ||
| 793 |
4/4✓ Branch 5 → 6 taken 66129 times.
✓ Branch 5 → 7 taken 890947 times.
✓ Branch 6 → 7 taken 49487 times.
✓ Branch 6 → 9 taken 16642 times.
|
957076 | if((next_x_loc == x_search) && (next_y_loc == y_search)){ |
| 794 | /* Then return FOUND. */ | ||
| 795 | return(FOUND); | ||
| 796 | } | ||
| 797 | |||
| 798 | /* Otherwise, set up for finding next contour pixel. */ | ||
| 799 | 940434 | cur_x_loc = next_x_loc; | |
| 800 | 940434 | cur_y_loc = next_y_loc; | |
| 801 | 940434 | cur_x_edge = next_x_edge; | |
| 802 | 940434 | cur_y_edge = next_y_edge; | |
| 803 | } | ||
| 804 | /* Otherwise, no new contour point found ... */ | ||
| 805 | else{ | ||
| 806 | /* So, stop searching, and return NOT_FOUND. */ | ||
| 807 | return(NOT_FOUND); | ||
| 808 | } | ||
| 809 | } | ||
| 810 | |||
| 811 | /* If we get here, we successfully searched the maximum points */ | ||
| 812 | /* without finding our desired point, so return NOT_FOUND. */ | ||
| 813 | return(NOT_FOUND); | ||
| 814 | } | ||
| 815 | |||
| 816 | /************************************************************************* | ||
| 817 | ************************************************************************** | ||
| 818 | #cat: next_contour_pixel - Takes a pixel coordinate of a point determined | ||
| 819 | #cat: to be on the interior edge of a feature (ridge or valley- | ||
| 820 | #cat: ending), and attempts to locate a neighboring pixel on the | ||
| 821 | #cat: feature's contour. Neighbors of the current feature pixel | ||
| 822 | #cat: are searched in a specified direction (clockwise or counter- | ||
| 823 | #cat: clockwise) and the first pair of adjacent/neigboring pixels | ||
| 824 | #cat: found with the first pixel having the color of the feature | ||
| 825 | #cat: and the second the opposite color are returned as the next | ||
| 826 | #cat: point on the contour. One exception happens when the new | ||
| 827 | #cat: point is on an "exposed" corner. | ||
| 828 | |||
| 829 | Input: | ||
| 830 | cur_x_loc - x-pixel coord of current point on feature's | ||
| 831 | interior contour | ||
| 832 | cur_y_loc - y-pixel coord of current point on feature's | ||
| 833 | interior contour | ||
| 834 | cur_x_edge - x-pixel coord of corresponding edge pixel | ||
| 835 | (exterior to feature) | ||
| 836 | cur_y_edge - y-pixel coord of corresponding edge pixel | ||
| 837 | (exterior to feature) | ||
| 838 | scan_clock - direction in which neighboring pixels are to be scanned | ||
| 839 | for the next contour pixel | ||
| 840 | bdata - binary image data (0==while & 1==black) | ||
| 841 | iw - width (in pixels) of image | ||
| 842 | ih - height (in pixels) of image | ||
| 843 | Output: | ||
| 844 | next_x_loc - x-pixel coord of next point on feature's interior contour | ||
| 845 | next_y_loc - y-pixel coord of next point on feature's interior contour | ||
| 846 | next_x_edge - x-pixel coord of corresponding edge (exterior to feature) | ||
| 847 | next_y_edge - y-pixel coord of corresponding edge (exterior to feature) | ||
| 848 | Return Code: | ||
| 849 | TRUE - next contour point found and returned | ||
| 850 | FALSE - next contour point NOT found | ||
| 851 | **************************************************************************/ | ||
| 852 | /*************************************************************************/ | ||
| 853 | 4512444 | int next_contour_pixel(int *next_x_loc, int *next_y_loc, | |
| 854 | int *next_x_edge, int *next_y_edge, | ||
| 855 | const int cur_x_loc, const int cur_y_loc, | ||
| 856 | const int cur_x_edge, const int cur_y_edge, | ||
| 857 | const int scan_clock, | ||
| 858 | unsigned char *bdata, const int iw, const int ih) | ||
| 859 | { | ||
| 860 | 4512444 | int feature_pix, edge_pix; | |
| 861 | 4512444 | int prev_nbr_pix, prev_nbr_x, prev_nbr_y; | |
| 862 | 4512444 | int cur_nbr_pix, cur_nbr_x, cur_nbr_y; | |
| 863 | 4512444 | int ni, nx, ny, npix; | |
| 864 | 4512444 | int nbr_i, i; | |
| 865 | |||
| 866 | /* Get the feature's pixel value. */ | ||
| 867 | 4512444 | feature_pix = *(bdata + (cur_y_loc * iw) + cur_x_loc); | |
| 868 | /* Get the feature's edge pixel value. */ | ||
| 869 | 4512444 | edge_pix = *(bdata + (cur_y_edge * iw) + cur_x_edge); | |
| 870 | |||
| 871 | /* Get the nieghbor position of the feature's edge pixel in relationship */ | ||
| 872 | /* to the feature's actual position. */ | ||
| 873 | /* REMEBER: The feature's position is always interior and on a ridge */ | ||
| 874 | /* ending (black pixel) or (for bifurcations) on a valley ending (white */ | ||
| 875 | /* pixel). The feature's edge pixel is an adjacent pixel to the feature */ | ||
| 876 | /* pixel that is exterior to the ridge or valley ending and opposite in */ | ||
| 877 | /* pixel value. */ | ||
| 878 | 4512444 | nbr_i = start_scan_nbr(cur_x_loc, cur_y_loc, cur_x_edge, cur_y_edge); | |
| 879 | |||
| 880 | /* Set current neighbor scan pixel to the feature's edge pixel. */ | ||
| 881 | 4512444 | cur_nbr_x = cur_x_edge; | |
| 882 | 4512444 | cur_nbr_y = cur_y_edge; | |
| 883 | 4512444 | cur_nbr_pix = edge_pix; | |
| 884 | |||
| 885 | /* Foreach pixel neighboring the feature pixel ... */ | ||
| 886 |
1/2✓ Branch 17 → 4 taken 10859530 times.
✗ Branch 17 → 18 not taken.
|
15371974 | for(i = 0; i < 8; i++){ |
| 887 | |||
| 888 | /* Set current neighbor scan pixel to previous scan pixel. */ | ||
| 889 | 10859530 | prev_nbr_x = cur_nbr_x; | |
| 890 | 10859530 | prev_nbr_y = cur_nbr_y; | |
| 891 | 10859530 | prev_nbr_pix = cur_nbr_pix; | |
| 892 | |||
| 893 | /* Bump pixel neighbor index clockwise or counter-clockwise. */ | ||
| 894 | 10859530 | nbr_i = next_scan_nbr(nbr_i, scan_clock); | |
| 895 | |||
| 896 | /* Set current scan pixel to the new neighbor. */ | ||
| 897 | /* REMEMBER: the neighbors are being scanned around the original */ | ||
| 898 | /* feature point. */ | ||
| 899 | 10859530 | cur_nbr_x = cur_x_loc + g_nbr8_dx[nbr_i]; | |
| 900 | 10859530 | cur_nbr_y = cur_y_loc + g_nbr8_dy[nbr_i]; | |
| 901 | |||
| 902 | /* If new neighbor is not within image boundaries... */ | ||
| 903 |
1/2✓ Branch 5 → 6 taken 10859530 times.
✗ Branch 5 → 18 not taken.
|
10859530 | if((cur_nbr_x < 0) || (cur_nbr_x >= iw) || |
| 904 |
1/2✓ Branch 6 → 7 taken 10859530 times.
✗ Branch 6 → 18 not taken.
|
10859530 | (cur_nbr_y < 0) || (cur_nbr_y >= ih)) |
| 905 | /* Return (FALSE==>Failure) if neighbor out of bounds. */ | ||
| 906 | return(FALSE); | ||
| 907 | |||
| 908 | /* Get the new neighbor's pixel value. */ | ||
| 909 | 10859530 | cur_nbr_pix = *(bdata + (cur_nbr_y * iw) + cur_nbr_x); | |
| 910 | |||
| 911 | /* If the new neighbor's pixel value is the same as the feature's */ | ||
| 912 | /* pixel value AND the previous neighbor's pixel value is the same */ | ||
| 913 | /* as the features's edge, then we have "likely" found our next */ | ||
| 914 | /* contour pixel. */ | ||
| 915 |
2/2✓ Branch 7 → 8 taken 4516761 times.
✓ Branch 7 → 16 taken 6342769 times.
|
10859530 | if((cur_nbr_pix == feature_pix) && (prev_nbr_pix == edge_pix)){ |
| 916 | |||
| 917 | /* Check to see if current neighbor is on the corner of the */ | ||
| 918 | /* neighborhood, and if so, test to see if it is "exposed". */ | ||
| 919 | /* The neighborhood corners have odd neighbor indicies. */ | ||
| 920 |
2/2✓ Branch 8 → 9 taken 1499334 times.
✓ Branch 8 → 15 taken 3017427 times.
|
4516761 | if(nbr_i % 2){ |
| 921 | /* To do this, look ahead one more neighbor pixel. */ | ||
| 922 | 1499334 | ni = next_scan_nbr(nbr_i, scan_clock); | |
| 923 | 1499334 | nx = cur_x_loc + g_nbr8_dx[ni]; | |
| 924 | 1499334 | ny = cur_y_loc + g_nbr8_dy[ni]; | |
| 925 | /* If new neighbor is not within image boundaries... */ | ||
| 926 |
1/2✓ Branch 10 → 11 taken 1499334 times.
✗ Branch 10 → 18 not taken.
|
1499334 | if((nx < 0) || (nx >= iw) || |
| 927 |
1/2✓ Branch 11 → 12 taken 1499334 times.
✗ Branch 11 → 18 not taken.
|
1499334 | (ny < 0) || (ny >= ih)) |
| 928 | /* Return (FALSE==>Failure) if neighbor out of bounds. */ | ||
| 929 | return(FALSE); | ||
| 930 | 1499334 | npix = *(bdata + (ny * iw) + nx); | |
| 931 | |||
| 932 | /* If the next neighbor's value is also the same as the */ | ||
| 933 | /* feature's pixel, then corner is NOT exposed... */ | ||
| 934 |
2/2✓ Branch 12 → 13 taken 1495017 times.
✓ Branch 12 → 14 taken 4317 times.
|
1499334 | if(npix == feature_pix){ |
| 935 | /* Assign the current neighbor pair to the output pointers. */ | ||
| 936 | 1495017 | *next_x_loc = cur_nbr_x; | |
| 937 | 1495017 | *next_y_loc = cur_nbr_y; | |
| 938 | 1495017 | *next_x_edge = prev_nbr_x; | |
| 939 | 1495017 | *next_y_edge = prev_nbr_y; | |
| 940 | /* Return TRUE==>Success. */ | ||
| 941 | 1495017 | return(TRUE); | |
| 942 | } | ||
| 943 | /* Otherwise, corner pixel is "exposed" so skip it. */ | ||
| 944 | else{ | ||
| 945 | /* Skip current corner neighbor by resetting it to the */ | ||
| 946 | /* next neighbor, which upon the iteration will immediately */ | ||
| 947 | /* become the previous neighbor. */ | ||
| 948 | 4317 | cur_nbr_x = nx; | |
| 949 | 4317 | cur_nbr_y = ny; | |
| 950 | 4317 | cur_nbr_pix = npix; | |
| 951 | /* Advance neighbor index. */ | ||
| 952 | 4317 | nbr_i = ni; | |
| 953 | /* Advance neighbor count. */ | ||
| 954 | 4317 | i++; | |
| 955 | } | ||
| 956 | } | ||
| 957 | /* Otherwise, current neighbor is not a corner ... */ | ||
| 958 | else{ | ||
| 959 | /* Assign the current neighbor pair to the output pointers. */ | ||
| 960 | 3017427 | *next_x_loc = cur_nbr_x; | |
| 961 | 3017427 | *next_y_loc = cur_nbr_y; | |
| 962 | 3017427 | *next_x_edge = prev_nbr_x; | |
| 963 | 3017427 | *next_y_edge = prev_nbr_y; | |
| 964 | /* Return TRUE==>Success. */ | ||
| 965 | 3017427 | return(TRUE); | |
| 966 | } | ||
| 967 | } | ||
| 968 | } | ||
| 969 | |||
| 970 | /* If we get here, then we did not find the next contour pixel */ | ||
| 971 | /* within the 8 neighbors of the current feature pixel so */ | ||
| 972 | /* return (FALSE==>Failure). */ | ||
| 973 | /* NOTE: This must mean we found a single isolated pixel. */ | ||
| 974 | /* Perhaps this should be filled? */ | ||
| 975 | return(FALSE); | ||
| 976 | } | ||
| 977 | |||
| 978 | /************************************************************************* | ||
| 979 | ************************************************************************** | ||
| 980 | #cat: start_scan_nbr - Takes a two pixel coordinates that are either | ||
| 981 | #cat: aligned north-to-south or east-to-west, and returns the | ||
| 982 | #cat: position the second pixel is in realtionship to the first. | ||
| 983 | #cat: The positions returned are based on 8-connectedness. | ||
| 984 | #cat: NOTE, this routine does NOT account for diagonal positions. | ||
| 985 | |||
| 986 | Input: | ||
| 987 | x_prev - x-coord of first point | ||
| 988 | y_prev - y-coord of first point | ||
| 989 | x_next - x-coord of second point | ||
| 990 | y_next - y-coord of second point | ||
| 991 | Return Code: | ||
| 992 | NORTH - second pixel above first | ||
| 993 | SOUTH - second pixel below first | ||
| 994 | EAST - second pixel right of first | ||
| 995 | WEST - second pixel left of first | ||
| 996 | **************************************************************************/ | ||
| 997 | 4512444 | int start_scan_nbr(const int x_prev, const int y_prev, | |
| 998 | const int x_next, const int y_next) | ||
| 999 | { | ||
| 1000 |
2/2✓ Branch 2 → 3 taken 3115240 times.
✓ Branch 2 → 7 taken 1397204 times.
|
4512444 | if((x_prev==x_next) && (y_next > y_prev)) |
| 1001 | return(SOUTH); | ||
| 1002 |
2/2✓ Branch 3 → 4 taken 1766631 times.
✓ Branch 3 → 7 taken 1348609 times.
|
3115240 | else if ((x_prev==x_next) && (y_next < y_prev)) |
| 1003 | return(NORTH); | ||
| 1004 |
2/2✓ Branch 4 → 5 taken 991619 times.
✓ Branch 4 → 7 taken 775012 times.
|
1766631 | else if ((x_next > x_prev) && (y_prev==y_next)) |
| 1005 | return(EAST); | ||
| 1006 |
1/2✓ Branch 5 → 6 taken 991619 times.
✗ Branch 5 → 7 not taken.
|
991619 | else if ((x_next < x_prev) && (y_prev==y_next)) |
| 1007 | 991619 | return(WEST); | |
| 1008 | |||
| 1009 | /* Added by MDG on 03-16-05 */ | ||
| 1010 | /* Should never reach here. Added to remove compiler warning. */ | ||
| 1011 | return(INVALID_DIR); /* -1 */ | ||
| 1012 | } | ||
| 1013 | |||
| 1014 | /************************************************************************* | ||
| 1015 | ************************************************************************** | ||
| 1016 | #cat: next_scan_nbr - Advances the given 8-connected neighbor index | ||
| 1017 | #cat: on location in the specifiec direction (clockwise or | ||
| 1018 | #cat: counter-clockwise). | ||
| 1019 | |||
| 1020 | Input: | ||
| 1021 | nbr_i - current 8-connected neighbor index | ||
| 1022 | scan_clock - direction in which the neighbor index is to be advanced | ||
| 1023 | Return Code: | ||
| 1024 | Next neighbor - 8-connected index of next neighbor | ||
| 1025 | **************************************************************************/ | ||
| 1026 | 12358864 | int next_scan_nbr(const int nbr_i, const int scan_clock) | |
| 1027 | { | ||
| 1028 | 12358864 | int new_i; | |
| 1029 | |||
| 1030 | /* If scanning neighbors clockwise ... */ | ||
| 1031 |
2/2✓ Branch 2 → 3 taken 8544904 times.
✓ Branch 2 → 4 taken 3813960 times.
|
12358864 | if(scan_clock == SCAN_CLOCKWISE) |
| 1032 | /* Advance one neighbor clockwise. */ | ||
| 1033 | 8544904 | new_i = (nbr_i+1)%8; | |
| 1034 | /* Otherwise, scanning neighbors counter-clockwise ... */ | ||
| 1035 | else | ||
| 1036 | /* Advance one neighbor counter-clockwise. */ | ||
| 1037 | /* There are 8 pixels in the neighborhood, so to */ | ||
| 1038 | /* decrement with wrapping from 0 around to 7, add */ | ||
| 1039 | /* the nieghbor index by 7 and mod with 8. */ | ||
| 1040 | 3813960 | new_i = (nbr_i+7)%8; | |
| 1041 | |||
| 1042 | /* Return the new neighbor index. */ | ||
| 1043 | 12358864 | return(new_i); | |
| 1044 | } | ||
| 1045 | |||
| 1046 | /************************************************************************* | ||
| 1047 | ************************************************************************** | ||
| 1048 | #cat: min_contour_theta - Takes a contour list and analyzes it locating the | ||
| 1049 | #cat: point at which the contour has highest curvature | ||
| 1050 | #cat: (or minimum interior angle). The angle of curvature is | ||
| 1051 | #cat: computed by searching a majority of points on the contour. | ||
| 1052 | #cat: At each of these points, a left and right segment (or edge) | ||
| 1053 | #cat: are extended out N number of pixels from the center point | ||
| 1054 | #cat: on the contour. The angle is formed between the straight line | ||
| 1055 | #cat: connecting the center point to the end point on the left edge | ||
| 1056 | #cat: and the line connecting the center point to the end of the | ||
| 1057 | #cat: right edge. The point of highest curvature is determined | ||
| 1058 | #cat: by locating the where the minimum of these angles occurs. | ||
| 1059 | |||
| 1060 | Input: | ||
| 1061 | angle_edge - length of the left and right edges extending from a | ||
| 1062 | common/centered pixel on the contour | ||
| 1063 | contour_x - x-coord list for contour points | ||
| 1064 | contour_y - y-coord list for contour points | ||
| 1065 | ncontour - number of points in contour | ||
| 1066 | Output: | ||
| 1067 | omin_i - index of contour point where minimum occurred | ||
| 1068 | omin_theta - minimum angle found along the contour | ||
| 1069 | Return Code: | ||
| 1070 | Zero - minimum angle successfully located | ||
| 1071 | IGNORE - ignore the contour | ||
| 1072 | Negative - system error | ||
| 1073 | **************************************************************************/ | ||
| 1074 | 3723 | int min_contour_theta(int *omin_i, double *omin_theta, | |
| 1075 | const int angle_edge, const int *contour_x, | ||
| 1076 | const int *contour_y, const int ncontour) | ||
| 1077 | { | ||
| 1078 | 3723 | int pleft, pcenter, pright; | |
| 1079 | 3723 | double theta1, theta2, dtheta; | |
| 1080 | 3723 | int min_i; | |
| 1081 | 3723 | double min_theta; | |
| 1082 | |||
| 1083 | /* If the contour length is too short for processing... */ | ||
| 1084 |
1/2✓ Branch 2 → 3 taken 3723 times.
✗ Branch 2 → 17 not taken.
|
3723 | if(ncontour < (angle_edge<<1)+1) |
| 1085 | /* Return IGNORE. */ | ||
| 1086 | return(IGNORE); | ||
| 1087 | |||
| 1088 | /* Intialize running minimum values. */ | ||
| 1089 | 3723 | min_theta = M_PI; | |
| 1090 | /* Need to truncate precision so that answers are consistent */ | ||
| 1091 | /* on different computer architectures when comparing doubles. */ | ||
| 1092 | 3723 | min_theta = trunc_dbl_precision(min_theta, TRUNC_SCALE); | |
| 1093 | 3723 | min_i = -1; | |
| 1094 | |||
| 1095 | /* Set left angle point to first contour point. */ | ||
| 1096 | 3723 | pleft = 0; | |
| 1097 | /* Set center angle point to "angle_edge" points into contour. */ | ||
| 1098 | 3723 | pcenter = angle_edge; | |
| 1099 | /* Set right angle point to "angle_edge" points from pcenter. */ | ||
| 1100 | 3723 | pright = pcenter + angle_edge; | |
| 1101 | |||
| 1102 | /* Loop until the right angle point exceeds the contour list. */ | ||
| 1103 |
2/2✓ Branch 13 → 4 taken 53843 times.
✓ Branch 13 → 14 taken 3723 times.
|
57566 | while(pright < ncontour){ |
| 1104 | /* Compute angle to first edge line (connecting pcenter to pleft). */ | ||
| 1105 | 107686 | theta1 = angle2line(contour_x[pcenter],contour_y[pcenter], | |
| 1106 | 53843 | contour_x[pleft],contour_y[pleft]); | |
| 1107 | /* Compute angle to second edge line (connecting pcenter to pright). */ | ||
| 1108 | 107686 | theta2 = angle2line(contour_x[pcenter],contour_y[pcenter], | |
| 1109 | 53843 | contour_x[pright],contour_y[pright]); | |
| 1110 | |||
| 1111 | /* Compute delta between angles accounting for an inner */ | ||
| 1112 | /* and outer distance between the angles. */ | ||
| 1113 | 53843 | dtheta = fabs(theta2 - theta1); | |
| 1114 |
2/2✓ Branch 6 → 7 taken 17423 times.
✓ Branch 6 → 9 taken 36420 times.
|
53843 | dtheta = min(dtheta, (M_PI*2.0)-dtheta); |
| 1115 | /* Need to truncate precision so that answers are consistent */ | ||
| 1116 | /* on different computer architectures when comparing doubles. */ | ||
| 1117 |
1/2✗ Branch 7 → 8 not taken.
✓ Branch 7 → 9 taken 17423 times.
|
53843 | dtheta = trunc_dbl_precision(dtheta, TRUNC_SCALE); |
| 1118 | |||
| 1119 | /* Keep track of running minimum theta. */ | ||
| 1120 |
2/2✓ Branch 10 → 11 taken 18401 times.
✓ Branch 10 → 12 taken 35442 times.
|
53843 | if(dtheta < min_theta){ |
| 1121 | 18401 | min_i = pcenter; | |
| 1122 | 18401 | min_theta = dtheta; | |
| 1123 | } | ||
| 1124 | |||
| 1125 | /* Bump to next points on contour. */ | ||
| 1126 | 53843 | pleft++; | |
| 1127 | 53843 | pcenter++; | |
| 1128 | 53843 | pright++; | |
| 1129 | } | ||
| 1130 | |||
| 1131 | /* If no minimum found (then contour is perfectly flat) so minimum */ | ||
| 1132 | /* to center point on contour. */ | ||
| 1133 |
2/2✓ Branch 14 → 15 taken 8 times.
✓ Branch 14 → 16 taken 3715 times.
|
3723 | if(min_i == -1){ |
| 1134 | 8 | *omin_i = ncontour>>1; | |
| 1135 | 8 | *omin_theta = min_theta; | |
| 1136 | } | ||
| 1137 | else{ | ||
| 1138 | /* Assign minimum theta information to output pointers. */ | ||
| 1139 | 3715 | *omin_i = min_i; | |
| 1140 | 3715 | *omin_theta = min_theta; | |
| 1141 | } | ||
| 1142 | |||
| 1143 | /* Return successfully. */ | ||
| 1144 | return(0); | ||
| 1145 | } | ||
| 1146 | |||
| 1147 | /************************************************************************* | ||
| 1148 | ************************************************************************** | ||
| 1149 | #cat: contour_limits - Determines the X and Y coordinate limits of the | ||
| 1150 | #cat: given contour list. | ||
| 1151 | |||
| 1152 | Input: | ||
| 1153 | contour_x - x-coord list for contour points | ||
| 1154 | contour_y - y-coord list for contour points | ||
| 1155 | ncontour - number of points in contour | ||
| 1156 | Output: | ||
| 1157 | xmin - left-most x-coord in contour | ||
| 1158 | ymin - top-most y-coord in contour | ||
| 1159 | xmax - right-most x-coord in contour | ||
| 1160 | ymax - bottom-most y-coord in contour | ||
| 1161 | **************************************************************************/ | ||
| 1162 | 3078 | void contour_limits(int *xmin, int *ymin, int *xmax, int *ymax, | |
| 1163 | const int *contour_x, const int *contour_y, const int ncontour) | ||
| 1164 | { | ||
| 1165 | /* Find the minimum x-coord from the list of contour points. */ | ||
| 1166 | 3078 | *xmin = minv(contour_x, ncontour); | |
| 1167 | /* Find the minimum y-coord from the list of contour points. */ | ||
| 1168 | 3078 | *ymin = minv(contour_y, ncontour); | |
| 1169 | /* Find the maximum x-coord from the list of contour points. */ | ||
| 1170 | 3078 | *xmax = maxv(contour_x, ncontour); | |
| 1171 | /* Find the maximum y-coord from the list of contour points. */ | ||
| 1172 | 3078 | *ymax = maxv(contour_y, ncontour); | |
| 1173 | 3078 | } | |
| 1174 | |||
| 1175 | /************************************************************************* | ||
| 1176 | ************************************************************************** | ||
| 1177 | #cat: fix_edge_pixel_pair - Takes a pair of pixel points with the first | ||
| 1178 | #cat: pixel on a feature and the second adjacent and off the feature, | ||
| 1179 | #cat: determines if the pair neighbor diagonally. If they do, their | ||
| 1180 | #cat: locations are adjusted so that the resulting pair retains the | ||
| 1181 | #cat: same pixel values, but are neighboring either to the N,S,E or W. | ||
| 1182 | #cat: This routine is needed in order to prepare the pixel pair for | ||
| 1183 | #cat: contour tracing. | ||
| 1184 | |||
| 1185 | Input: | ||
| 1186 | feat_x - pointer to x-pixel coord on feature | ||
| 1187 | feat_y - pointer to y-pixel coord on feature | ||
| 1188 | edge_x - pointer to x-pixel coord on edge of feature | ||
| 1189 | edge_y - pointer to y-pixel coord on edge of feature | ||
| 1190 | bdata - binary image data (0==while & 1==black) | ||
| 1191 | iw - width (in pixels) of image | ||
| 1192 | ih - height (in pixels) of image | ||
| 1193 | Output: | ||
| 1194 | feat_x - pointer to resulting x-pixel coord on feature | ||
| 1195 | feat_y - pointer to resulting y-pixel coord on feature | ||
| 1196 | edge_x - pointer to resulting x-pixel coord on edge of feature | ||
| 1197 | edge_y - pointer to resulting y-pixel coord on edge of feature | ||
| 1198 | **************************************************************************/ | ||
| 1199 | 58877 | void fix_edge_pixel_pair(int *feat_x, int *feat_y, int *edge_x, int *edge_y, | |
| 1200 | unsigned char *bdata, const int iw, const int ih) | ||
| 1201 | { | ||
| 1202 | 58877 | int dx, dy; | |
| 1203 | 58877 | int px, py, cx, cy; | |
| 1204 | 58877 | int feature_pix; | |
| 1205 | |||
| 1206 | /* Get the pixel value of the feature. */ | ||
| 1207 | 58877 | feature_pix = *(bdata + ((*feat_y) * iw) + (*feat_x)); | |
| 1208 | |||
| 1209 | /* Store the input points to current and previous points. */ | ||
| 1210 | 58877 | cx = *feat_x; | |
| 1211 | 58877 | cy = *feat_y; | |
| 1212 | 58877 | px = *edge_x; | |
| 1213 | 58877 | py = *edge_y; | |
| 1214 | |||
| 1215 | /* Compute detlas between current and previous point. */ | ||
| 1216 | 58877 | dx = px - cx; | |
| 1217 | 58877 | dy = py - cy; | |
| 1218 | |||
| 1219 | /* If previous point (P) is diagonal neighbor of */ | ||
| 1220 | /* current point (C)... This is a problem because */ | ||
| 1221 | /* the contour tracing routine requires that the */ | ||
| 1222 | /* "edge" pixel be north, south, east, or west of */ | ||
| 1223 | /* of the feature point. If the previous pixel is */ | ||
| 1224 | /* diagonal neighbor, then we need to adjust either */ | ||
| 1225 | /* the positon of te previous or current pixel. */ | ||
| 1226 |
4/4✓ Branch 2 → 3 taken 35015 times.
✓ Branch 2 → 8 taken 23862 times.
✓ Branch 3 → 4 taken 25418 times.
✓ Branch 3 → 8 taken 9597 times.
|
58877 | if((abs(dx)==1) && (abs(dy)==1)){ |
| 1227 | /* Then we have one of the 4 following conditions: */ | ||
| 1228 | /* */ | ||
| 1229 | /* *C C* */ | ||
| 1230 | /* 1. P* 2. P* 3. *P 4. *P */ | ||
| 1231 | /* *C C* */ | ||
| 1232 | /* */ | ||
| 1233 | /* dx = -1 -1 1 1 */ | ||
| 1234 | /* dy = 1 -1 -1 1 */ | ||
| 1235 | /* */ | ||
| 1236 | /* Want to test values in positions of '*': */ | ||
| 1237 | /* Let point P == (px, py) */ | ||
| 1238 | /* p1 == '*' positon where x changes */ | ||
| 1239 | /* p2 == '*' positon where y changes */ | ||
| 1240 | /* */ | ||
| 1241 | /* p1 = px+1,py px+1,py px-1,py px-1,py */ | ||
| 1242 | /* p2 = px,py-1 px,py+1 px,py+1 px,py-1 */ | ||
| 1243 | /* */ | ||
| 1244 | /* These can all be rewritten: */ | ||
| 1245 | /* p1 = px-dx,py */ | ||
| 1246 | /* p2 = px,py-dy */ | ||
| 1247 | |||
| 1248 | /* Check if 'p1' is NOT the value we are searching for... */ | ||
| 1249 |
2/2✓ Branch 4 → 5 taken 10158 times.
✓ Branch 4 → 7 taken 15260 times.
|
25418 | if(*(bdata+(py*iw)+(px-dx)) != feature_pix) |
| 1250 | /* Then set x-coord of edge pixel to p1. */ | ||
| 1251 | px -= dx; | ||
| 1252 | /* Check if 'p2' is NOT the value we are searching for... */ | ||
| 1253 |
2/2✓ Branch 5 → 6 taken 4552 times.
✓ Branch 5 → 7 taken 5606 times.
|
10158 | else if(*(bdata+((py-dy)*iw)+px) != feature_pix) |
| 1254 | /* Then set y-coord of edge pixel to p2. */ | ||
| 1255 | py -= dy; | ||
| 1256 | /* Otherwise, the current pixel 'C' is exposed on a corner ... */ | ||
| 1257 | else{ | ||
| 1258 | /* Set pixel 'C' to 'p1', which also has the pixel */ | ||
| 1259 | /* value we are searching for. */ | ||
| 1260 | 4552 | cy += dy; | |
| 1261 | } | ||
| 1262 | |||
| 1263 | /* Set the pointers to the resulting values. */ | ||
| 1264 | 25418 | *feat_x = cx; | |
| 1265 | 25418 | *feat_y = cy; | |
| 1266 | 25418 | *edge_x = px; | |
| 1267 | 25418 | *edge_y = py; | |
| 1268 | } | ||
| 1269 | |||
| 1270 | /* Otherwise, nothing has changed. */ | ||
| 1271 | 58877 | } | |
| 1272 |