| 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 | 273597 | int allocate_contour(int **ocontour_x, int **ocontour_y, | |
| 106 | int **ocontour_ex, int **ocontour_ey, const int ncontour) | ||
| 107 | { | ||
| 108 | 273597 | int *contour_x, *contour_y, *contour_ex, *contour_ey; | |
| 109 | |||
| 110 |
1/2✗ Branch 0 (2→3) not taken.
✓ Branch 1 (2→4) taken 273597 times.
|
273597 | ASSERT_SIZE_MUL(ncontour, sizeof(int)); |
| 111 | |||
| 112 | /* Allocate contour's x-coord list. */ | ||
| 113 | 273597 | contour_x = (int *)g_malloc(ncontour * sizeof(int)); | |
| 114 | |||
| 115 | /* Allocate contour's y-coord list. */ | ||
| 116 | 273597 | contour_y = (int *)g_malloc(ncontour * sizeof(int)); | |
| 117 | |||
| 118 | /* Allocate contour's edge x-coord list. */ | ||
| 119 | 273597 | contour_ex = (int *)g_malloc(ncontour * sizeof(int)); | |
| 120 | |||
| 121 | /* Allocate contour's edge y-coord list. */ | ||
| 122 | 273597 | contour_ey = (int *)g_malloc(ncontour * sizeof(int)); | |
| 123 | |||
| 124 | /* Otherwise, allocations successful, so assign output pointers. */ | ||
| 125 | 273597 | *ocontour_x = contour_x; | |
| 126 | 273597 | *ocontour_y = contour_y; | |
| 127 | 273597 | *ocontour_ex = contour_ex; | |
| 128 | 273597 | *ocontour_ey = contour_ey; | |
| 129 | |||
| 130 | /* Return normally. */ | ||
| 131 | 273597 | 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 | 273597 | void free_contour(int *contour_x, int *contour_y, | |
| 153 | int *contour_ex, int *contour_ey) | ||
| 154 | { | ||
| 155 | 273597 | g_free(contour_x); | |
| 156 | 273597 | g_free(contour_y); | |
| 157 | 273597 | g_free(contour_ex); | |
| 158 | 273597 | g_free(contour_ey); | |
| 159 | 273597 | } | |
| 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 | 3716 | 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 | 3716 | int max_contour; | |
| 209 | 3716 | int *half1_x, *half1_y, *half1_ex, *half1_ey, nhalf1; | |
| 210 | 3716 | int *half2_x, *half2_y, *half2_ex, *half2_ey, nhalf2; | |
| 211 | 3716 | int *contour_x, *contour_y, *contour_ex, *contour_ey, ncontour; | |
| 212 | 3716 | int i, j, ret; | |
| 213 | |||
| 214 | /* Compute maximum length of complete contour */ | ||
| 215 | /* (2 half contours + feature point). */ | ||
| 216 | 3716 | max_contour = (half_contour<<1) + 1; | |
| 217 | |||
| 218 | /* Initialize output contour length to 0. */ | ||
| 219 | 3716 | *oncontour = 0; | |
| 220 | |||
| 221 | /* Get 1st half contour with clockwise neighbor trace. */ | ||
| 222 |
2/2✓ Branch 0 (3→4) taken 167 times.
✓ Branch 1 (3→15) taken 3549 times.
|
3716 | 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 0 (4→5) not taken.
✓ Branch 1 (4→6) taken 167 times.
|
167 | 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 0 (6→7) taken 167 times.
✗ Branch 1 (6→45) not taken.
|
167 | 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 | 167 | ncontour = nhalf1+1; | |
| 238 | /* Allocate new contour list. */ | ||
| 239 |
1/2✗ Branch 0 (8→9) not taken.
✓ Branch 1 (8→10) taken 167 times.
|
167 | 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 | 167 | contour_x[0] = x_loc; | |
| 251 | 167 | contour_y[0] = y_loc; | |
| 252 | 167 | contour_ex[0] = x_edge; | |
| 253 | 167 | contour_ey[0] = y_edge; | |
| 254 | |||
| 255 | /* Now store the first half contour in reverse order. */ | ||
| 256 |
2/2✓ Branch 0 (12→11) taken 1180 times.
✓ Branch 1 (12→13) taken 167 times.
|
1347 | for(i = 1, j = nhalf1-1; i < ncontour; i++, j--){ |
| 257 | 1180 | contour_x[i] = half1_x[j]; | |
| 258 | 1180 | contour_y[i] = half1_y[j]; | |
| 259 | 1180 | contour_ex[i] = half1_ex[j]; | |
| 260 | 1180 | contour_ey[i] = half1_ey[j]; | |
| 261 | } | ||
| 262 | |||
| 263 | /* Deallocate the first half contour. */ | ||
| 264 | 167 | free_contour(half1_x, half1_y, half1_ex, half1_ey); | |
| 265 | |||
| 266 | /* Assign the output pointers. */ | ||
| 267 | 167 | *ocontour_x = contour_x; | |
| 268 | 167 | *ocontour_y = contour_y; | |
| 269 | 167 | *ocontour_ex = contour_ex; | |
| 270 | 167 | *ocontour_ey = contour_ey; | |
| 271 | 167 | *oncontour = ncontour; | |
| 272 | |||
| 273 | /* Return LOOP_FOUND for further processing. */ | ||
| 274 | 167 | 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 0 (15→16) not taken.
✓ Branch 1 (15→18) taken 3549 times.
|
3549 | 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 0 (19→20) taken 217 times.
✓ Branch 1 (19→26) taken 3332 times.
|
3549 | if((ret = trace_contour(&half2_x, &half2_y, &half2_ex, &half2_ey, &nhalf2, |
| 295 | 3549 | 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 0 (20→21) not taken.
✓ Branch 1 (20→23) taken 217 times.
|
217 | 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 0 (23→24) not taken.
✓ Branch 1 (23→30) taken 217 times.
|
217 | 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 0 (26→27) not taken.
✓ Branch 1 (26→30) taken 3332 times.
|
3332 | 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 0 (31→32) not taken.
✓ Branch 1 (31→35) taken 3549 times.
|
3549 | 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 | 3549 | 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 0 (37→36) taken 49686 times.
✓ Branch 1 (37→38) taken 3549 times.
|
53235 | for(i = 0, j = nhalf1-1; i < nhalf1; i++, j--){ |
| 351 | 49686 | contour_x[i] = half1_x[j]; | |
| 352 | 49686 | contour_y[i] = half1_y[j]; | |
| 353 | 49686 | contour_ex[i] = half1_ex[j]; | |
| 354 | 49686 | contour_ey[i] = half1_ey[j]; | |
| 355 | 49686 | ncontour++; | |
| 356 | } | ||
| 357 | |||
| 358 | /* Deallocate 1st half contour. */ | ||
| 359 | 3549 | free_contour(half1_x, half1_y, half1_ex, half1_ey); | |
| 360 | |||
| 361 | /* Next, store starting feature point into output contour buffers. */ | ||
| 362 | 3549 | contour_x[nhalf1] = x_loc; | |
| 363 | 3549 | contour_y[nhalf1] = y_loc; | |
| 364 | 3549 | contour_ex[nhalf1] = x_edge; | |
| 365 | 3549 | contour_ey[nhalf1] = y_edge; | |
| 366 | 3549 | ncontour++; | |
| 367 | |||
| 368 | /* Now, append 2nd half contour to permanent contour buffers. */ | ||
| 369 |
2/2✓ Branch 0 (41→40) taken 48441 times.
✓ Branch 1 (41→42) taken 3549 times.
|
51990 | for(i = 0, j = nhalf1+1; i < nhalf2; i++, j++){ |
| 370 | 48441 | contour_x[j] = half2_x[i]; | |
| 371 | 48441 | contour_y[j] = half2_y[i]; | |
| 372 | 48441 | contour_ex[j] = half2_ex[i]; | |
| 373 | 48441 | contour_ey[j] = half2_ey[i]; | |
| 374 | 48441 | ncontour++; | |
| 375 | } | ||
| 376 | |||
| 377 | /* Deallocate 2nd half contour. */ | ||
| 378 | 3549 | free_contour(half2_x, half2_y, half2_ex, half2_ey); | |
| 379 | |||
| 380 | /* Assign outputs contour to output ponters. */ | ||
| 381 | 3549 | *ocontour_x = contour_x; | |
| 382 | 3549 | *ocontour_y = contour_y; | |
| 383 | 3549 | *ocontour_ex = contour_ex; | |
| 384 | 3549 | *ocontour_ey = contour_ey; | |
| 385 | 3549 | *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 | 3549 | 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 | 22446 | 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 | 22446 | int max_contour; | |
| 438 | 22446 | int *half1_x, *half1_y, *half1_ex, *half1_ey, nhalf1; | |
| 439 | 22446 | int *half2_x, *half2_y, *half2_ex, *half2_ey, nhalf2; | |
| 440 | 22446 | int *contour_x, *contour_y, *contour_ex, *contour_ey, ncontour; | |
| 441 | 22446 | int i, j, ret; | |
| 442 | |||
| 443 |
1/2✗ Branch 0 (2→3) not taken.
✓ Branch 1 (2→4) taken 22446 times.
|
22446 | g_assert (half_contour > 0); |
| 444 | |||
| 445 | /* Compute maximum length of complete contour */ | ||
| 446 | /* (2 half contours + feature point). */ | ||
| 447 | 22446 | max_contour = (half_contour<<1) + 1; | |
| 448 | |||
| 449 | /* Initialize output contour length to 0. */ | ||
| 450 | 22446 | *oncontour = 0; | |
| 451 | |||
| 452 | /* Get 1st half contour with clockwise neighbor trace. */ | ||
| 453 | 22446 | 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 0 (5→6) taken 22446 times.
✗ Branch 1 (5→45) not taken.
|
22446 | if(ret < 0){ |
| 459 | /* Return error code. */ | ||
| 460 | return(ret); | ||
| 461 | } | ||
| 462 | |||
| 463 | /* If trace was not possible ... */ | ||
| 464 |
2/2✓ Branch 0 (6→7) taken 21 times.
✓ Branch 1 (6→8) taken 22425 times.
|
22446 | 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 0 (8→9) taken 1 times.
✓ Branch 1 (8→12) taken 22424 times.
|
22425 | if(ret == LOOP_FOUND){ |
| 470 | /* Deallocate loop's contour. */ | ||
| 471 | 1 | free_contour(half1_x, half1_y, half1_ex, half1_ey); | |
| 472 | /* Return LOOP_FOUND, with nothing allocated. */ | ||
| 473 | 1 | return(LOOP_FOUND); | |
| 474 | } | ||
| 475 | |||
| 476 | /* If 1st half contour not complete ... */ | ||
| 477 |
1/2✗ Branch 0 (12→13) not taken.
✓ Branch 1 (12→16) taken 22424 times.
|
22424 | 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 | 44848 | ret = trace_contour(&half2_x, &half2_y, &half2_ex, &half2_ey, &nhalf2, | |
| 489 | 22424 | 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 0 (17→18) not taken.
✓ Branch 1 (17→20) taken 22424 times.
|
22424 | 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 0 (20→21) not taken.
✓ Branch 1 (20→23) taken 22424 times.
|
22424 | 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 0 (23→24) taken 24 times.
✓ Branch 1 (23→27) taken 22400 times.
|
22424 | 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 0 (27→28) not taken.
✓ Branch 1 (27→31) taken 22400 times.
|
22400 | 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 0 (32→33) not taken.
✓ Branch 1 (32→36) taken 22400 times.
|
22400 | 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 | 22400 | 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 0 (38→37) taken 156800 times.
✓ Branch 1 (38→39) taken 22400 times.
|
179200 | for(i = 0, j = nhalf1-1; i < nhalf1; i++, j--){ |
| 551 | 156800 | contour_x[i] = half1_x[j]; | |
| 552 | 156800 | contour_y[i] = half1_y[j]; | |
| 553 | 156800 | contour_ex[i] = half1_ex[j]; | |
| 554 | 156800 | contour_ey[i] = half1_ey[j]; | |
| 555 | 156800 | ncontour++; | |
| 556 | } | ||
| 557 | |||
| 558 | /* Deallocate 1st half contour. */ | ||
| 559 | 22400 | free_contour(half1_x, half1_y, half1_ex, half1_ey); | |
| 560 | |||
| 561 | /* Next, store starting feature point into output contour buffers. */ | ||
| 562 | 22400 | contour_x[nhalf1] = x_loc; | |
| 563 | 22400 | contour_y[nhalf1] = y_loc; | |
| 564 | 22400 | contour_ex[nhalf1] = x_edge; | |
| 565 | 22400 | contour_ey[nhalf1] = y_edge; | |
| 566 | 22400 | ncontour++; | |
| 567 | |||
| 568 | /* Now, append 2nd half contour to permanent contour buffers. */ | ||
| 569 |
2/2✓ Branch 0 (42→41) taken 156800 times.
✓ Branch 1 (42→43) taken 22400 times.
|
179200 | for(i = 0, j = nhalf1+1; i < nhalf2; i++, j++){ |
| 570 | 156800 | contour_x[j] = half2_x[i]; | |
| 571 | 156800 | contour_y[j] = half2_y[i]; | |
| 572 | 156800 | contour_ex[j] = half2_ex[i]; | |
| 573 | 156800 | contour_ey[j] = half2_ey[i]; | |
| 574 | 156800 | ncontour++; | |
| 575 | } | ||
| 576 | |||
| 577 | /* Deallocate 2nd half contour. */ | ||
| 578 | 22400 | free_contour(half2_x, half2_y, half2_ex, half2_ey); | |
| 579 | |||
| 580 | /* Assign outputs contour to output ponters. */ | ||
| 581 | 22400 | *ocontour_x = contour_x; | |
| 582 | 22400 | *ocontour_y = contour_y; | |
| 583 | 22400 | *ocontour_ex = contour_ex; | |
| 584 | 22400 | *ocontour_ey = contour_ey; | |
| 585 | 22400 | *oncontour = ncontour; | |
| 586 | |||
| 587 | /* Return normally. */ | ||
| 588 | 22400 | 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 | 244934 | 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 | 244934 | int *contour_x, *contour_y, *contour_ex, *contour_ey, ncontour; | |
| 639 | 244934 | int cur_x_loc, cur_y_loc; | |
| 640 | 244934 | int cur_x_edge, cur_y_edge; | |
| 641 | 244934 | int next_x_loc, next_y_loc; | |
| 642 | 244934 | int next_x_edge, next_y_edge; | |
| 643 | 244934 | int i, ret; | |
| 644 | |||
| 645 | /* Check to make sure that the feature and edge values are opposite. */ | ||
| 646 | 244934 | if(*(bdata+(y_loc*iw)+x_loc) == | |
| 647 |
2/2✓ Branch 0 (2→3) taken 244668 times.
✓ Branch 1 (2→15) taken 266 times.
|
244934 | *(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 0 (4→13) taken 244668 times.
✗ Branch 1 (4→15) not taken.
|
244668 | 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 0 (13→5) taken 3363262 times.
✓ Branch 1 (13→14) taken 228258 times.
|
3591520 | for(i = 0; i < max_len; i++){ |
| 669 | /* Find the next contour pixel. */ | ||
| 670 |
1/2✓ Branch 0 (6→7) taken 3363262 times.
✗ Branch 1 (6→11) not taken.
|
3363262 | 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 0 (7→8) taken 179237 times.
✓ Branch 1 (7→10) taken 3184025 times.
✓ Branch 2 (8→9) taken 16410 times.
✓ Branch 3 (8→10) taken 162827 times.
|
3363262 | 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 | 16410 | *ocontour_x = contour_x; | |
| 682 | 16410 | *ocontour_y = contour_y; | |
| 683 | 16410 | *ocontour_ex = contour_ex; | |
| 684 | 16410 | *ocontour_ey = contour_ey; | |
| 685 | 16410 | *oncontour = ncontour; | |
| 686 | 16410 | return(LOOP_FOUND); | |
| 687 | } | ||
| 688 | |||
| 689 | /* Otherwise, we found another point on our feature's contour, */ | ||
| 690 | /* so store the new contour point. */ | ||
| 691 | 3346852 | contour_x[i] = next_x_loc; | |
| 692 | 3346852 | contour_y[i] = next_y_loc; | |
| 693 | 3346852 | contour_ex[i] = next_x_edge; | |
| 694 | 3346852 | contour_ey[i] = next_y_edge; | |
| 695 | /* Bump the number of points stored. */ | ||
| 696 | 3346852 | ncontour++; | |
| 697 | |||
| 698 | /* Set up for finding next contour pixel. */ | ||
| 699 | 3346852 | cur_x_loc = next_x_loc; | |
| 700 | 3346852 | cur_y_loc = next_y_loc; | |
| 701 | 3346852 | cur_x_edge = next_x_edge; | |
| 702 | 3346852 | 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 | 228258 | *ocontour_x = contour_x; | |
| 723 | 228258 | *ocontour_y = contour_y; | |
| 724 | 228258 | *ocontour_ex = contour_ex; | |
| 725 | 228258 | *ocontour_ey = contour_ey; | |
| 726 | 228258 | *oncontour = ncontour; | |
| 727 | |||
| 728 | /* Return normally. */ | ||
| 729 | 228258 | 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 | 99699 | 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 | 99699 | int cur_x_loc, cur_y_loc; | |
| 772 | 99699 | int cur_x_edge, cur_y_edge; | |
| 773 | 99699 | int next_x_loc, next_y_loc; | |
| 774 | 99699 | int next_x_edge, next_y_edge; | |
| 775 | 99699 | int i; | |
| 776 | |||
| 777 | /* Set up for finding first contour pixel. */ | ||
| 778 | 99699 | cur_x_loc = x_loc; | |
| 779 | 99699 | cur_y_loc = y_loc; | |
| 780 | 99699 | cur_x_edge = x_edge; | |
| 781 | 99699 | cur_y_edge = y_edge; | |
| 782 | |||
| 783 | /* Foreach point to be collected on the feature's contour... */ | ||
| 784 |
2/2✓ Branch 0 (9→3) taken 889403 times.
✓ Branch 1 (9→8) taken 83678 times.
|
973081 | for(i = 0; i < search_len; i++){ |
| 785 | /* Find the next contour pixel. */ | ||
| 786 |
1/2✓ Branch 0 (4→5) taken 889403 times.
✗ Branch 1 (4→8) not taken.
|
889403 | 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 0 (5→6) taken 62384 times.
✓ Branch 1 (5→7) taken 827019 times.
✓ Branch 2 (6→7) taken 46363 times.
✓ Branch 3 (6→10) taken 16021 times.
|
889403 | 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 | 873382 | cur_x_loc = next_x_loc; | |
| 800 | 873382 | cur_y_loc = next_y_loc; | |
| 801 | 873382 | cur_x_edge = next_x_edge; | |
| 802 | 873382 | 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 | 4252665 | 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 | 4252665 | int feature_pix, edge_pix; | |
| 861 | 4252665 | int prev_nbr_pix, prev_nbr_x, prev_nbr_y; | |
| 862 | 4252665 | int cur_nbr_pix, cur_nbr_x, cur_nbr_y; | |
| 863 | 4252665 | int ni, nx, ny, npix; | |
| 864 | 4252665 | int nbr_i, i; | |
| 865 | |||
| 866 | /* Get the feature's pixel value. */ | ||
| 867 | 4252665 | feature_pix = *(bdata + (cur_y_loc * iw) + cur_x_loc); | |
| 868 | /* Get the feature's edge pixel value. */ | ||
| 869 | 4252665 | 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 | 4252665 | 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 | 4252665 | cur_nbr_x = cur_x_edge; | |
| 882 | 4252665 | cur_nbr_y = cur_y_edge; | |
| 883 | 4252665 | cur_nbr_pix = edge_pix; | |
| 884 | |||
| 885 | /* Foreach pixel neighboring the feature pixel ... */ | ||
| 886 |
1/2✓ Branch 0 (18→4) taken 10265901 times.
✗ Branch 1 (18→7) not taken.
|
14518566 | for(i = 0; i < 8; i++){ |
| 887 | |||
| 888 | /* Set current neighbor scan pixel to previous scan pixel. */ | ||
| 889 | 10265901 | prev_nbr_x = cur_nbr_x; | |
| 890 | 10265901 | prev_nbr_y = cur_nbr_y; | |
| 891 | 10265901 | prev_nbr_pix = cur_nbr_pix; | |
| 892 | |||
| 893 | /* Bump pixel neighbor index clockwise or counter-clockwise. */ | ||
| 894 | 10265901 | 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 | 10265901 | cur_nbr_x = cur_x_loc + g_nbr8_dx[nbr_i]; | |
| 900 | 10265901 | 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 0 (5→6) taken 10265901 times.
✗ Branch 1 (5→7) not taken.
|
10265901 | if((cur_nbr_x < 0) || (cur_nbr_x >= iw) || |
| 904 |
1/2✗ Branch 0 (6→7) not taken.
✓ Branch 1 (6→8) taken 10265901 times.
|
10265901 | (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 | 10265901 | 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 0 (8→9) taken 4256029 times.
✓ Branch 1 (8→17) taken 6009872 times.
|
10265901 | 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 0 (9→10) taken 1439387 times.
✓ Branch 1 (9→16) taken 2816642 times.
|
4256029 | if(nbr_i % 2){ |
| 921 | /* To do this, look ahead one more neighbor pixel. */ | ||
| 922 | 1439387 | ni = next_scan_nbr(nbr_i, scan_clock); | |
| 923 | 1439387 | nx = cur_x_loc + g_nbr8_dx[ni]; | |
| 924 | 1439387 | ny = cur_y_loc + g_nbr8_dy[ni]; | |
| 925 | /* If new neighbor is not within image boundaries... */ | ||
| 926 |
1/2✗ Branch 0 (11→7) not taken.
✓ Branch 1 (11→12) taken 1439387 times.
|
1439387 | if((nx < 0) || (nx >= iw) || |
| 927 |
1/2✗ Branch 0 (12→7) not taken.
✓ Branch 1 (12→13) taken 1439387 times.
|
1439387 | (ny < 0) || (ny >= ih)) |
| 928 | /* Return (FALSE==>Failure) if neighbor out of bounds. */ | ||
| 929 | return(FALSE); | ||
| 930 | 1439387 | 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 0 (13→14) taken 1436023 times.
✓ Branch 1 (13→15) taken 3364 times.
|
1439387 | if(npix == feature_pix){ |
| 935 | /* Assign the current neighbor pair to the output pointers. */ | ||
| 936 | 1436023 | *next_x_loc = cur_nbr_x; | |
| 937 | 1436023 | *next_y_loc = cur_nbr_y; | |
| 938 | 1436023 | *next_x_edge = prev_nbr_x; | |
| 939 | 1436023 | *next_y_edge = prev_nbr_y; | |
| 940 | /* Return TRUE==>Success. */ | ||
| 941 | 1436023 | 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 | 3364 | cur_nbr_x = nx; | |
| 949 | 3364 | cur_nbr_y = ny; | |
| 950 | 3364 | cur_nbr_pix = npix; | |
| 951 | /* Advance neighbor index. */ | ||
| 952 | 3364 | nbr_i = ni; | |
| 953 | /* Advance neighbor count. */ | ||
| 954 | 3364 | i++; | |
| 955 | } | ||
| 956 | } | ||
| 957 | /* Otherwise, current neighbor is not a corner ... */ | ||
| 958 | else{ | ||
| 959 | /* Assign the current neighbor pair to the output pointers. */ | ||
| 960 | 2816642 | *next_x_loc = cur_nbr_x; | |
| 961 | 2816642 | *next_y_loc = cur_nbr_y; | |
| 962 | 2816642 | *next_x_edge = prev_nbr_x; | |
| 963 | 2816642 | *next_y_edge = prev_nbr_y; | |
| 964 | /* Return TRUE==>Success. */ | ||
| 965 | 2816642 | 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 | 4252665 | 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 0 (2→3) taken 2928804 times.
✓ Branch 1 (2→7) taken 1323861 times.
|
4252665 | if((x_prev==x_next) && (y_next > y_prev)) |
| 1001 | return(SOUTH); | ||
| 1002 |
2/2✓ Branch 0 (3→4) taken 1710022 times.
✓ Branch 1 (3→7) taken 1218782 times.
|
2928804 | else if ((x_prev==x_next) && (y_next < y_prev)) |
| 1003 | return(NORTH); | ||
| 1004 |
2/2✓ Branch 0 (4→5) taken 977633 times.
✓ Branch 1 (4→7) taken 732389 times.
|
1710022 | else if ((x_next > x_prev) && (y_prev==y_next)) |
| 1005 | return(EAST); | ||
| 1006 |
1/2✓ Branch 0 (5→6) taken 977633 times.
✗ Branch 1 (5→7) not taken.
|
977633 | else if ((x_next < x_prev) && (y_prev==y_next)) |
| 1007 | 977633 | 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 | 11705288 | int next_scan_nbr(const int nbr_i, const int scan_clock) | |
| 1027 | { | ||
| 1028 | 11705288 | int new_i; | |
| 1029 | |||
| 1030 | /* If scanning neighbors clockwise ... */ | ||
| 1031 |
2/2✓ Branch 0 (2→3) taken 8011600 times.
✓ Branch 1 (2→4) taken 3693688 times.
|
11705288 | if(scan_clock == SCAN_CLOCKWISE) |
| 1032 | /* Advance one neighbor clockwise. */ | ||
| 1033 | 8011600 | 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 | 3693688 | new_i = (nbr_i+7)%8; | |
| 1041 | |||
| 1042 | /* Return the new neighbor index. */ | ||
| 1043 | 11705288 | 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 | 3549 | 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 | 3549 | int pleft, pcenter, pright; | |
| 1079 | 3549 | double theta1, theta2, dtheta; | |
| 1080 | 3549 | int min_i; | |
| 1081 | 3549 | double min_theta; | |
| 1082 | |||
| 1083 | /* If the contour length is too short for processing... */ | ||
| 1084 |
1/2✓ Branch 0 (2→3) taken 3549 times.
✗ Branch 1 (2→18) not taken.
|
3549 | if(ncontour < (angle_edge<<1)+1) |
| 1085 | /* Return IGNORE. */ | ||
| 1086 | return(IGNORE); | ||
| 1087 | |||
| 1088 | /* Intialize running minimum values. */ | ||
| 1089 | 3549 | min_theta = M_PI; | |
| 1090 | /* Need to truncate precision so that answers are consistent */ | ||
| 1091 | /* on different computer architectures when comparing doubles. */ | ||
| 1092 | 3549 | min_theta = trunc_dbl_precision(min_theta, TRUNC_SCALE); | |
| 1093 | 3549 | min_i = -1; | |
| 1094 | |||
| 1095 | /* Set left angle point to first contour point. */ | ||
| 1096 | 3549 | pleft = 0; | |
| 1097 | /* Set center angle point to "angle_edge" points into contour. */ | ||
| 1098 | 3549 | pcenter = angle_edge; | |
| 1099 | /* Set right angle point to "angle_edge" points from pcenter. */ | ||
| 1100 | 3549 | pright = pcenter + angle_edge; | |
| 1101 | |||
| 1102 | /* Loop until the right angle point exceeds the contour list. */ | ||
| 1103 |
2/2✓ Branch 0 (13→4) taken 51990 times.
✓ Branch 1 (13→14) taken 3549 times.
|
55539 | while(pright < ncontour){ |
| 1104 | /* Compute angle to first edge line (connecting pcenter to pleft). */ | ||
| 1105 | 103980 | theta1 = angle2line(contour_x[pcenter],contour_y[pcenter], | |
| 1106 | 51990 | contour_x[pleft],contour_y[pleft]); | |
| 1107 | /* Compute angle to second edge line (connecting pcenter to pright). */ | ||
| 1108 | 103980 | theta2 = angle2line(contour_x[pcenter],contour_y[pcenter], | |
| 1109 | 51990 | contour_x[pright],contour_y[pright]); | |
| 1110 | |||
| 1111 | /* Compute delta between angles accounting for an inner */ | ||
| 1112 | /* and outer distance between the angles. */ | ||
| 1113 | 51990 | dtheta = fabs(theta2 - theta1); | |
| 1114 |
2/2✓ Branch 0 (6→7) taken 16482 times.
✓ Branch 1 (6→9) taken 35508 times.
|
51990 | 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 0 (7→8) not taken.
✓ Branch 1 (7→9) taken 16482 times.
|
51990 | dtheta = trunc_dbl_precision(dtheta, TRUNC_SCALE); |
| 1118 | |||
| 1119 | /* Keep track of running minimum theta. */ | ||
| 1120 |
2/2✓ Branch 0 (10→11) taken 17274 times.
✓ Branch 1 (10→12) taken 34716 times.
|
51990 | if(dtheta < min_theta){ |
| 1121 | 17274 | min_i = pcenter; | |
| 1122 | 17274 | min_theta = dtheta; | |
| 1123 | } | ||
| 1124 | |||
| 1125 | /* Bump to next points on contour. */ | ||
| 1126 | 51990 | pleft++; | |
| 1127 | 51990 | pcenter++; | |
| 1128 | 51990 | 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 0 (14→15) taken 14 times.
✓ Branch 1 (14→16) taken 3535 times.
|
3549 | if(min_i == -1){ |
| 1134 | 14 | *omin_i = ncontour>>1; | |
| 1135 | 14 | *omin_theta = min_theta; | |
| 1136 | } | ||
| 1137 | else{ | ||
| 1138 | /* Assign minimum theta information to output pointers. */ | ||
| 1139 | 3535 | *omin_i = min_i; | |
| 1140 | 3535 | *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 | 2980 | 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 | 2980 | *xmin = minv(contour_x, ncontour); | |
| 1167 | /* Find the minimum y-coord from the list of contour points. */ | ||
| 1168 | 2980 | *ymin = minv(contour_y, ncontour); | |
| 1169 | /* Find the maximum x-coord from the list of contour points. */ | ||
| 1170 | 2980 | *xmax = maxv(contour_x, ncontour); | |
| 1171 | /* Find the maximum y-coord from the list of contour points. */ | ||
| 1172 | 2980 | *ymax = maxv(contour_y, ncontour); | |
| 1173 | 2980 | } | |
| 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 | 59166 | 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 | 59166 | int dx, dy; | |
| 1203 | 59166 | int px, py, cx, cy; | |
| 1204 | 59166 | int feature_pix; | |
| 1205 | |||
| 1206 | /* Get the pixel value of the feature. */ | ||
| 1207 | 59166 | feature_pix = *(bdata + ((*feat_y) * iw) + (*feat_x)); | |
| 1208 | |||
| 1209 | /* Store the input points to current and previous points. */ | ||
| 1210 | 59166 | cx = *feat_x; | |
| 1211 | 59166 | cy = *feat_y; | |
| 1212 | 59166 | px = *edge_x; | |
| 1213 | 59166 | py = *edge_y; | |
| 1214 | |||
| 1215 | /* Compute detlas between current and previous point. */ | ||
| 1216 | 59166 | dx = px - cx; | |
| 1217 | 59166 | 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 0 (2→3) taken 35774 times.
✓ Branch 1 (2→8) taken 23392 times.
✓ Branch 2 (3→4) taken 25691 times.
✓ Branch 3 (3→8) taken 10083 times.
|
59166 | 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 0 (4→5) taken 10471 times.
✓ Branch 1 (4→7) taken 15220 times.
|
25691 | 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 0 (5→6) taken 4811 times.
✓ Branch 1 (5→7) taken 5660 times.
|
10471 | 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 | 4811 | cy += dy; | |
| 1261 | } | ||
| 1262 | |||
| 1263 | /* Set the pointers to the resulting values. */ | ||
| 1264 | 25691 | *feat_x = cx; | |
| 1265 | 25691 | *feat_y = cy; | |
| 1266 | 25691 | *edge_x = px; | |
| 1267 | 25691 | *edge_y = py; | |
| 1268 | } | ||
| 1269 | |||
| 1270 | /* Otherwise, nothing has changed. */ | ||
| 1271 | 59166 | } | |
| 1272 |