| 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: LOOP.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 analyzing and filling | ||
| 55 | lakes and islands within a binary image as part of the | ||
| 56 | NIST Latent Fingerprint System (LFS). | ||
| 57 | |||
| 58 | *********************************************************************** | ||
| 59 | ROUTINES: | ||
| 60 | get_loop_list() | ||
| 61 | on_loop() | ||
| 62 | on_island_lake() | ||
| 63 | on_hook() | ||
| 64 | is_loop_clockwise() | ||
| 65 | process_loop() | ||
| 66 | process_loop_V2() | ||
| 67 | get_loop_aspect() | ||
| 68 | fill_loop() | ||
| 69 | fill_partial_row() | ||
| 70 | flood_loop() | ||
| 71 | flood_fill4() | ||
| 72 | ***********************************************************************/ | ||
| 73 | |||
| 74 | #include <stdio.h> | ||
| 75 | #include <lfs.h> | ||
| 76 | |||
| 77 | /************************************************************************* | ||
| 78 | ************************************************************************** | ||
| 79 | #cat: get_loop_list - Takes a list of minutia points and determines which | ||
| 80 | #cat: ones lie on loops around valleys (lakes) of a specified | ||
| 81 | #cat: maximum circumference. The routine returns a list of | ||
| 82 | #cat: flags, one for each minutia in the input list, and if | ||
| 83 | #cat: the minutia is on a qualifying loop, the corresponding | ||
| 84 | #cat: flag is set to TRUE, otherwise it is set to FALSE. | ||
| 85 | #cat: If for some reason it was not possible to trace the | ||
| 86 | #cat: minutia's contour, then it is removed from the list. | ||
| 87 | #cat: This can occur due to edits dynamically taking place | ||
| 88 | #cat: in the image by other routines. | ||
| 89 | |||
| 90 | Input: | ||
| 91 | minutiae - list of true and false minutiae | ||
| 92 | loop_len - maximum size of loop searched for | ||
| 93 | bdata - binary image data (0==while & 1==black) | ||
| 94 | iw - width (in pixels) of image | ||
| 95 | ih - height (in pixels) of image | ||
| 96 | Output: | ||
| 97 | oonloop - loop flags: TRUE == loop, FALSE == no loop | ||
| 98 | Return Code: | ||
| 99 | Zero - successful completion | ||
| 100 | Negative - system error | ||
| 101 | **************************************************************************/ | ||
| 102 | |||
| 103 | /************************************************************************* | ||
| 104 | ************************************************************************** | ||
| 105 | #cat: on_loop - Determines if a minutia point lies on a loop (island or lake) | ||
| 106 | #cat: of specified maximum circumference. | ||
| 107 | |||
| 108 | Input: | ||
| 109 | minutiae - list of true and false minutiae | ||
| 110 | max_loop_len - maximum size of loop searched for | ||
| 111 | bdata - binary image data (0==while & 1==black) | ||
| 112 | iw - width (in pixels) of image | ||
| 113 | ih - height (in pixels) of image | ||
| 114 | Return Code: | ||
| 115 | IGNORE - minutia contour could not be traced | ||
| 116 | LOOP_FOUND - minutia determined to lie on qualifying loop | ||
| 117 | FALSE - minutia determined not to lie on qualifying loop | ||
| 118 | Negative - system error | ||
| 119 | **************************************************************************/ | ||
| 120 | 12464 | int on_loop(const MINUTIA *minutia, const int max_loop_len, | |
| 121 | unsigned char *bdata, const int iw, const int ih) | ||
| 122 | { | ||
| 123 | 12464 | int ret; | |
| 124 | 12464 | int *contour_x, *contour_y, *contour_ex, *contour_ey, ncontour; | |
| 125 | |||
| 126 | /* Trace the contour of the feature starting at the minutia point */ | ||
| 127 | /* and stepping along up to the specified maximum number of steps. */ | ||
| 128 | 24928 | ret = trace_contour(&contour_x, &contour_y, | |
| 129 | &contour_ex, &contour_ey, &ncontour, max_loop_len, | ||
| 130 | 12464 | minutia->x, minutia->y, minutia->x, minutia->y, | |
| 131 | 12464 | minutia->ex, minutia->ey, | |
| 132 | SCAN_CLOCKWISE, bdata, iw, ih); | ||
| 133 | |||
| 134 | /* If trace was not possible ... */ | ||
| 135 |
2/2✓ Branch 0 taken 12344 times.
✓ Branch 1 taken 120 times.
|
12464 | if(ret == IGNORE) |
| 136 | return(ret); | ||
| 137 | |||
| 138 | /* If the trace completed a loop ... */ | ||
| 139 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 12344 times.
|
12344 | if(ret == LOOP_FOUND){ |
| 140 | ✗ | free_contour(contour_x, contour_y, contour_ex, contour_ey); | |
| 141 | ✗ | return(LOOP_FOUND); | |
| 142 | } | ||
| 143 | |||
| 144 | /* If the trace successfully followed the minutia's contour, but did */ | ||
| 145 | /* not complete a loop within the specified number of steps ... */ | ||
| 146 |
1/2✓ Branch 0 taken 12344 times.
✗ Branch 1 not taken.
|
12344 | if(ret == 0){ |
| 147 | 12344 | free_contour(contour_x, contour_y, contour_ex, contour_ey); | |
| 148 | 12344 | return(FALSE); | |
| 149 | } | ||
| 150 | |||
| 151 | /* Otherwise, the trace had an error in following the contour ... */ | ||
| 152 | return(ret); | ||
| 153 | } | ||
| 154 | |||
| 155 | /************************************************************************* | ||
| 156 | ************************************************************************** | ||
| 157 | #cat: on_island_lake - Determines if two minutia points lie on the same loop | ||
| 158 | #cat: (island or lake). If a loop is detected, the contour | ||
| 159 | #cat: points of the loop are returned. | ||
| 160 | |||
| 161 | Input: | ||
| 162 | minutia1 - first minutia point | ||
| 163 | minutia2 - second minutia point | ||
| 164 | max_half_loop - maximum size of half the loop circumference searched for | ||
| 165 | bdata - binary image data (0==while & 1==black) | ||
| 166 | iw - width (in pixels) of image | ||
| 167 | ih - height (in pixels) of image | ||
| 168 | Output: | ||
| 169 | ocontour_x - x-pixel coords of loop contour | ||
| 170 | ocontour_y - y-pixel coords of loop contour | ||
| 171 | ocontour_x - x coord of each contour point's edge pixel | ||
| 172 | ocontour_y - y coord of each contour point's edge pixel | ||
| 173 | oncontour - number of points in the contour. | ||
| 174 | Return Code: | ||
| 175 | IGNORE - contour could not be traced | ||
| 176 | LOOP_FOUND - minutiae determined to lie on same qualifying loop | ||
| 177 | FALSE - minutiae determined not to lie on same qualifying loop | ||
| 178 | Negative - system error | ||
| 179 | **************************************************************************/ | ||
| 180 | 43860 | int on_island_lake(int **ocontour_x, int **ocontour_y, | |
| 181 | int **ocontour_ex, int **ocontour_ey, int *oncontour, | ||
| 182 | const MINUTIA *minutia1, const MINUTIA *minutia2, | ||
| 183 | const int max_half_loop, | ||
| 184 | unsigned char *bdata, const int iw, const int ih) | ||
| 185 | { | ||
| 186 | 43860 | int i, l, ret; | |
| 187 | 43860 | int *contour1_x, *contour1_y, *contour1_ex, *contour1_ey, ncontour1; | |
| 188 | 43860 | int *contour2_x, *contour2_y, *contour2_ex, *contour2_ey, ncontour2; | |
| 189 | 43860 | int *loop_x, *loop_y, *loop_ex, *loop_ey, nloop; | |
| 190 | |||
| 191 | /* Trace the contour of the feature starting at the 1st minutia point */ | ||
| 192 | /* and stepping along up to the specified maximum number of steps or */ | ||
| 193 | /* until 2nd mintuia point is encountered. */ | ||
| 194 | 87720 | ret = trace_contour(&contour1_x, &contour1_y, | |
| 195 | &contour1_ex, &contour1_ey, &ncontour1, max_half_loop, | ||
| 196 | 43860 | minutia2->x, minutia2->y, minutia1->x, minutia1->y, | |
| 197 | 43860 | minutia1->ex, minutia1->ey, | |
| 198 | SCAN_CLOCKWISE, bdata, iw, ih); | ||
| 199 | |||
| 200 | /* If trace was not possible, return IGNORE. */ | ||
| 201 |
2/2✓ Branch 0 taken 43735 times.
✓ Branch 1 taken 125 times.
|
43860 | if(ret == IGNORE) |
| 202 | return(ret); | ||
| 203 | |||
| 204 | /* If the trace encounters 2nd minutia point ... */ | ||
| 205 |
2/2✓ Branch 0 taken 5406 times.
✓ Branch 1 taken 38329 times.
|
43735 | if(ret == LOOP_FOUND){ |
| 206 | |||
| 207 | /* Now, trace the contour of the feature starting at the 2nd minutia, */ | ||
| 208 | /* continuing to search for edge neighbors clockwise, and stepping */ | ||
| 209 | /* along up to the specified maximum number of steps or until 1st */ | ||
| 210 | /* mintuia point is encountered. */ | ||
| 211 | 10812 | ret = trace_contour(&contour2_x, &contour2_y, | |
| 212 | &contour2_ex, &contour2_ey, &ncontour2, max_half_loop, | ||
| 213 | 5406 | minutia1->x, minutia1->y, minutia2->x, minutia2->y, | |
| 214 | 5406 | minutia2->ex, minutia2->ey, | |
| 215 | SCAN_CLOCKWISE, bdata, iw, ih); | ||
| 216 | |||
| 217 | /* If trace was not possible, return IGNORE. */ | ||
| 218 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 5406 times.
|
5406 | if(ret == IGNORE){ |
| 219 | ✗ | free_contour(contour1_x, contour1_y, contour1_ex, contour1_ey); | |
| 220 | ✗ | return(ret); | |
| 221 | } | ||
| 222 | |||
| 223 | /* If the 2nd trace encounters 1st minutia point ... */ | ||
| 224 |
2/2✓ Branch 0 taken 2813 times.
✓ Branch 1 taken 2593 times.
|
5406 | if(ret == LOOP_FOUND){ |
| 225 | /* Combine the 2 half loop contours into one full loop. */ | ||
| 226 | |||
| 227 | /* Compute loop length (including the minutia pair). */ | ||
| 228 | 2813 | nloop = ncontour1 + ncontour2 + 2; | |
| 229 | |||
| 230 | /* Allocate loop contour. */ | ||
| 231 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 2813 times.
|
2813 | if((ret = allocate_contour(&loop_x, &loop_y, &loop_ex, &loop_ey, |
| 232 | nloop))){ | ||
| 233 | ✗ | free_contour(contour1_x, contour1_y, contour1_ex, contour1_ey); | |
| 234 | ✗ | free_contour(contour2_x, contour2_y, contour2_ex, contour2_ey); | |
| 235 | ✗ | return(ret); | |
| 236 | } | ||
| 237 | |||
| 238 | /* Store 1st minutia. */ | ||
| 239 | 2813 | l = 0; | |
| 240 | 2813 | loop_x[l] = minutia1->x; | |
| 241 | 2813 | loop_y[l] = minutia1->y; | |
| 242 | 2813 | loop_ex[l] = minutia1->ex; | |
| 243 | 2813 | loop_ey[l++] = minutia1->ey; | |
| 244 | /* Store first contour. */ | ||
| 245 |
2/2✓ Branch 0 taken 17710 times.
✓ Branch 1 taken 2813 times.
|
20523 | for(i = 0; i < ncontour1; i++){ |
| 246 | 17710 | loop_x[l] = contour1_x[i]; | |
| 247 | 17710 | loop_y[l] = contour1_y[i]; | |
| 248 | 17710 | loop_ex[l] = contour1_ex[i]; | |
| 249 | 17710 | loop_ey[l++] = contour1_ey[i]; | |
| 250 | } | ||
| 251 | /* Store 2nd minutia. */ | ||
| 252 | 2813 | loop_x[l] = minutia2->x; | |
| 253 | 2813 | loop_y[l] = minutia2->y; | |
| 254 | 2813 | loop_ex[l] = minutia2->ex; | |
| 255 | 2813 | loop_ey[l++] = minutia2->ey; | |
| 256 | /* Store 2nd contour. */ | ||
| 257 |
2/2✓ Branch 0 taken 16957 times.
✓ Branch 1 taken 2813 times.
|
19770 | for(i = 0; i < ncontour2; i++){ |
| 258 | 16957 | loop_x[l] = contour2_x[i]; | |
| 259 | 16957 | loop_y[l] = contour2_y[i]; | |
| 260 | 16957 | loop_ex[l] = contour2_ex[i]; | |
| 261 | 16957 | loop_ey[l++] = contour2_ey[i]; | |
| 262 | } | ||
| 263 | |||
| 264 | /* Deallocate the half loop contours. */ | ||
| 265 | 2813 | free_contour(contour1_x, contour1_y, contour1_ex, contour1_ey); | |
| 266 | 2813 | free_contour(contour2_x, contour2_y, contour2_ex, contour2_ey); | |
| 267 | |||
| 268 | /* Assign loop contour to return pointers. */ | ||
| 269 | 2813 | *ocontour_x = loop_x; | |
| 270 | 2813 | *ocontour_y = loop_y; | |
| 271 | 2813 | *ocontour_ex = loop_ex; | |
| 272 | 2813 | *ocontour_ey = loop_ey; | |
| 273 | 2813 | *oncontour = nloop; | |
| 274 | |||
| 275 | /* Then return that an island/lake WAS found (LOOP_FOUND). */ | ||
| 276 | 2813 | return(LOOP_FOUND); | |
| 277 | } | ||
| 278 | |||
| 279 | /* If the trace successfully followed 2nd minutia's contour, but */ | ||
| 280 | /* did not encounter 1st minutia point within the specified number */ | ||
| 281 | /* of steps ... */ | ||
| 282 |
1/2✓ Branch 0 taken 2593 times.
✗ Branch 1 not taken.
|
2593 | if(ret == 0){ |
| 283 | /* Deallocate the two contours. */ | ||
| 284 | 2593 | free_contour(contour1_x, contour1_y, contour1_ex, contour1_ey); | |
| 285 | 2593 | free_contour(contour2_x, contour2_y, contour2_ex, contour2_ey); | |
| 286 | /* Then return that an island/lake was NOT found (FALSE). */ | ||
| 287 | 2593 | return(FALSE); | |
| 288 | } | ||
| 289 | |||
| 290 | /* Otherwise, the 2nd trace had an error in following the contour ... */ | ||
| 291 | ✗ | free_contour(contour1_x, contour1_y, contour1_ex, contour1_ey); | |
| 292 | ✗ | return(ret); | |
| 293 | } | ||
| 294 | |||
| 295 | /* If the 1st trace successfully followed 1st minutia's contour, but */ | ||
| 296 | /* did not encounter the 2nd minutia point within the specified number */ | ||
| 297 | /* of steps ... */ | ||
| 298 |
1/2✓ Branch 0 taken 38329 times.
✗ Branch 1 not taken.
|
38329 | if(ret == 0){ |
| 299 | 38329 | free_contour(contour1_x, contour1_y, contour1_ex, contour1_ey); | |
| 300 | /* Then return that an island/lake was NOT found (FALSE). */ | ||
| 301 | 38329 | return(FALSE); | |
| 302 | } | ||
| 303 | |||
| 304 | /* Otherwise, the 1st trace had an error in following the contour ... */ | ||
| 305 | return(ret); | ||
| 306 | } | ||
| 307 | |||
| 308 | /************************************************************************* | ||
| 309 | ************************************************************************** | ||
| 310 | #cat: on_hook - Determines if two minutia points lie on a hook on the side | ||
| 311 | #cat: of a ridge or valley. | ||
| 312 | |||
| 313 | Input: | ||
| 314 | minutia1 - first minutia point | ||
| 315 | minutia2 - second minutia point | ||
| 316 | max_hook_len - maximum length of contour searched along for a hook | ||
| 317 | bdata - binary image data (0==while & 1==black) | ||
| 318 | iw - width (in pixels) of image | ||
| 319 | ih - height (in pixels) of image | ||
| 320 | Return Code: | ||
| 321 | IGNORE - contour could not be traced | ||
| 322 | HOOK_FOUND - minutiae determined to lie on same qualifying hook | ||
| 323 | FALSE - minutiae determined not to lie on same qualifying hook | ||
| 324 | Negative - system error | ||
| 325 | **************************************************************************/ | ||
| 326 | 2909 | int on_hook(const MINUTIA *minutia1, const MINUTIA *minutia2, | |
| 327 | const int max_hook_len, | ||
| 328 | unsigned char *bdata, const int iw, const int ih) | ||
| 329 | { | ||
| 330 | 2909 | int ret; | |
| 331 | 2909 | int *contour_x, *contour_y, *contour_ex, *contour_ey, ncontour; | |
| 332 | |||
| 333 | /* NOTE: This routine should only be called when the 2 minutia points */ | ||
| 334 | /* are of "opposite" type. */ | ||
| 335 | |||
| 336 | /* Trace the contour of the feature starting at the 1st minutia's */ | ||
| 337 | /* "edge" point and stepping along up to the specified maximum number */ | ||
| 338 | /* of steps or until the 2nd minutia point is encountered. */ | ||
| 339 | /* First search for edge neighbors clockwise. */ | ||
| 340 | |||
| 341 | 5818 | ret = trace_contour(&contour_x, &contour_y, | |
| 342 | &contour_ex, &contour_ey, &ncontour, max_hook_len, | ||
| 343 | 2909 | minutia2->x, minutia2->y, minutia1->ex, minutia1->ey, | |
| 344 | 2909 | minutia1->x, minutia1->y, | |
| 345 | SCAN_CLOCKWISE, bdata, iw, ih); | ||
| 346 | |||
| 347 | /* If trace was not possible, return IGNORE. */ | ||
| 348 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 2909 times.
|
2909 | if(ret == IGNORE) |
| 349 | return(ret); | ||
| 350 | |||
| 351 | /* If the trace encountered the second minutia point ... */ | ||
| 352 |
2/2✓ Branch 0 taken 543 times.
✓ Branch 1 taken 2366 times.
|
2909 | if(ret == LOOP_FOUND){ |
| 353 | 543 | free_contour(contour_x, contour_y, contour_ex, contour_ey); | |
| 354 | 543 | return(HOOK_FOUND); | |
| 355 | } | ||
| 356 | |||
| 357 | /* If trace had an error in following the contour ... */ | ||
| 358 |
1/2✓ Branch 0 taken 2366 times.
✗ Branch 1 not taken.
|
2366 | if(ret != 0) |
| 359 | return(ret); | ||
| 360 | |||
| 361 | |||
| 362 | /* Otherwise, the trace successfully followed the contour, but did */ | ||
| 363 | /* not encounter the 2nd minutia point within the specified number */ | ||
| 364 | /* of steps. */ | ||
| 365 | |||
| 366 | /* Deallocate previously extracted contour. */ | ||
| 367 | 2366 | free_contour(contour_x, contour_y, contour_ex, contour_ey); | |
| 368 | |||
| 369 | /* Try searching contour from 1st minutia "edge" searching for */ | ||
| 370 | /* edge neighbors counter-clockwise. */ | ||
| 371 | 4732 | ret = trace_contour(&contour_x, &contour_y, | |
| 372 | &contour_ex, &contour_ey, &ncontour, max_hook_len, | ||
| 373 | 2366 | minutia2->x, minutia2->y, minutia1->ex, minutia1->ey, | |
| 374 | 2366 | minutia1->x, minutia1->y, | |
| 375 | SCAN_COUNTER_CLOCKWISE, bdata, iw, ih); | ||
| 376 | |||
| 377 | /* If trace was not possible, return IGNORE. */ | ||
| 378 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 2366 times.
|
2366 | if(ret == IGNORE) |
| 379 | return(ret); | ||
| 380 | |||
| 381 | /* If the trace encountered the second minutia point ... */ | ||
| 382 |
2/2✓ Branch 0 taken 462 times.
✓ Branch 1 taken 1904 times.
|
2366 | if(ret == LOOP_FOUND){ |
| 383 | 462 | free_contour(contour_x, contour_y, contour_ex, contour_ey); | |
| 384 | 462 | return(HOOK_FOUND); | |
| 385 | } | ||
| 386 | |||
| 387 | /* If the trace successfully followed the 1st minutia's contour, but */ | ||
| 388 | /* did not encounter the 2nd minutia point within the specified number */ | ||
| 389 | /* of steps ... */ | ||
| 390 |
1/2✓ Branch 0 taken 1904 times.
✗ Branch 1 not taken.
|
1904 | if(ret == 0){ |
| 391 | 1904 | free_contour(contour_x, contour_y, contour_ex, contour_ey); | |
| 392 | /* Then return hook NOT found (FALSE). */ | ||
| 393 | 1904 | return(FALSE); | |
| 394 | } | ||
| 395 | |||
| 396 | /* Otherwise, the 2nd trace had an error in following the contour ... */ | ||
| 397 | return(ret); | ||
| 398 | } | ||
| 399 | |||
| 400 | /************************************************************************* | ||
| 401 | ************************************************************************** | ||
| 402 | #cat: is_loop_clockwise - Takes a feature's contour points and determines if | ||
| 403 | #cat: the points are ordered clockwise or counter-clockwise about | ||
| 404 | #cat: the feature. The routine also requires a default return | ||
| 405 | #cat: value be specified in the case the the routine is not able | ||
| 406 | #cat: to definitively determine the contour's order. This allows | ||
| 407 | #cat: the default response to be application-specific. | ||
| 408 | |||
| 409 | Input: | ||
| 410 | contour_x - x-coord list for feature's contour points | ||
| 411 | contour_y - y-coord list for feature's contour points | ||
| 412 | ncontour - number of points in contour | ||
| 413 | default_ret - default return code (used when we can't tell the order) | ||
| 414 | Return Code: | ||
| 415 | TRUE - contour determined to be ordered clockwise | ||
| 416 | FALSE - contour determined to be ordered counter-clockwise | ||
| 417 | Default - could not determine the order of the contour | ||
| 418 | Negative - system error | ||
| 419 | **************************************************************************/ | ||
| 420 | 167 | int is_loop_clockwise(const int *contour_x, const int *contour_y, | |
| 421 | const int ncontour, const int default_ret) | ||
| 422 | { | ||
| 423 | 167 | int ret; | |
| 424 | 167 | int *chain, nchain; | |
| 425 | |||
| 426 | /* Derive chain code from contour points. */ | ||
| 427 |
1/2✓ Branch 1 taken 167 times.
✗ Branch 2 not taken.
|
167 | if((ret = chain_code_loop(&chain, &nchain, |
| 428 | contour_x, contour_y, ncontour))) | ||
| 429 | /* If there is a system error, return the error code. */ | ||
| 430 | return(ret); | ||
| 431 | |||
| 432 | /* If chain is empty... */ | ||
| 433 |
1/2✓ Branch 0 taken 167 times.
✗ Branch 1 not taken.
|
167 | if(nchain == 0){ |
| 434 | /* There wasn't enough contour points to tell, so return the */ | ||
| 435 | /* the default return value. No chain needs to be deallocated */ | ||
| 436 | /* in this case. */ | ||
| 437 | return(default_ret); | ||
| 438 | } | ||
| 439 | |||
| 440 | /* If the chain code for contour is clockwise ... pass default return */ | ||
| 441 | /* value on to this routine to correctly handle the case where we can't */ | ||
| 442 | /* tell the direction of the chain code. */ | ||
| 443 | 167 | ret = is_chain_clockwise(chain, nchain, default_ret); | |
| 444 | |||
| 445 | /* Free the chain code and return result. */ | ||
| 446 | 167 | g_free(chain); | |
| 447 | 167 | return(ret); | |
| 448 | } | ||
| 449 | |||
| 450 | /************************************************************************* | ||
| 451 | ************************************************************************** | ||
| 452 | #cat: process_loop - Takes a contour list that has been determined to form | ||
| 453 | #cat: a complete loop, and processes it. If the loop is sufficiently | ||
| 454 | #cat: large and elongated, then two minutia points are calculated | ||
| 455 | #cat: along the loop's longest aspect axis. If it is determined | ||
| 456 | #cat: that the loop does not contain minutiae, it is filled in the | ||
| 457 | #cat: binary image. | ||
| 458 | |||
| 459 | Input: | ||
| 460 | contour_x - x-coord list for loop's contour points | ||
| 461 | contour_y - y-coord list for loop's contour points | ||
| 462 | contour_ex - x-coord list for loop's edge points | ||
| 463 | contour_ey - y-coord list for loop's edge points | ||
| 464 | ncontour - number of points in contour | ||
| 465 | bdata - binary image data (0==while & 1==black) | ||
| 466 | iw - width (in pixels) of image | ||
| 467 | ih - height (in pixels) of image | ||
| 468 | lfsparms - parameters and thresholds for controlling LFS | ||
| 469 | Output: | ||
| 470 | minutiae - points to a list of detected minutia structures | ||
| 471 | OR | ||
| 472 | bdata - binary image data with loop filled | ||
| 473 | Return Code: | ||
| 474 | Zero - loop processed successfully | ||
| 475 | Negative - system error | ||
| 476 | **************************************************************************/ | ||
| 477 | |||
| 478 | /************************************************************************* | ||
| 479 | ************************************************************************** | ||
| 480 | #cat: process_loop_V2 - Takes a contour list that has been determined to form | ||
| 481 | #cat: a complete loop, and processes it. If the loop is sufficiently | ||
| 482 | #cat: large and elongated, then two minutia points are calculated | ||
| 483 | #cat: along the loop's longest aspect axis. If it is determined | ||
| 484 | #cat: that the loop does not contain minutiae, it is filled in the | ||
| 485 | #cat: binary image. | ||
| 486 | |||
| 487 | Input: | ||
| 488 | contour_x - x-coord list for loop's contour points | ||
| 489 | contour_y - y-coord list for loop's contour points | ||
| 490 | contour_ex - x-coord list for loop's edge points | ||
| 491 | contour_ey - y-coord list for loop's edge points | ||
| 492 | ncontour - number of points in contour | ||
| 493 | bdata - binary image data (0==while & 1==black) | ||
| 494 | iw - width (in pixels) of image | ||
| 495 | ih - height (in pixels) of image | ||
| 496 | plow_flow_map - pixelized Low Ridge Flow Map | ||
| 497 | lfsparms - parameters and thresholds for controlling LFS | ||
| 498 | Output: | ||
| 499 | minutiae - points to a list of detected minutia structures | ||
| 500 | OR | ||
| 501 | bdata - binary image data with loop filled | ||
| 502 | Return Code: | ||
| 503 | Zero - loop processed successfully | ||
| 504 | Negative - system error | ||
| 505 | **************************************************************************/ | ||
| 506 | 167 | int process_loop_V2(MINUTIAE *minutiae, | |
| 507 | const int *contour_x, const int *contour_y, | ||
| 508 | const int *contour_ex, const int *contour_ey, const int ncontour, | ||
| 509 | unsigned char *bdata, const int iw, const int ih, | ||
| 510 | int *plow_flow_map, const LFSPARMS *lfsparms) | ||
| 511 | { | ||
| 512 | 167 | int idir, type, appearing; | |
| 513 | 167 | double min_dist, max_dist; | |
| 514 | 167 | int min_fr, max_fr, min_to, max_to; | |
| 515 | 167 | int mid_x, mid_y, mid_pix; | |
| 516 | 167 | int feature_pix; | |
| 517 | 167 | int ret; | |
| 518 | 167 | MINUTIA *minutia; | |
| 519 | 167 | int fmapval; | |
| 520 | 167 | double reliability; | |
| 521 | |||
| 522 | /* If contour is empty, then just return. */ | ||
| 523 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 167 times.
|
167 | if(ncontour <= 0) |
| 524 | return(0); | ||
| 525 | |||
| 526 | /* If loop is large enough ... */ | ||
| 527 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 167 times.
|
167 | if(ncontour > lfsparms->min_loop_len){ |
| 528 | /* Get pixel value of feature's interior. */ | ||
| 529 | ✗ | feature_pix = *(bdata + (contour_y[0] * iw) + contour_x[0]); | |
| 530 | |||
| 531 | /* Get the aspect dimensions of the loop in units of */ | ||
| 532 | /* squared distance. */ | ||
| 533 | ✗ | get_loop_aspect(&min_fr, &min_to, &min_dist, | |
| 534 | &max_fr, &max_to, &max_dist, | ||
| 535 | contour_x, contour_y, ncontour); | ||
| 536 | |||
| 537 | /* If loop passes aspect ratio tests ... loop is sufficiently */ | ||
| 538 | /* narrow or elongated ... */ | ||
| 539 | ✗ | if((min_dist < lfsparms->min_loop_aspect_dist) || | |
| 540 | ✗ | ((max_dist/min_dist) >= lfsparms->min_loop_aspect_ratio)){ | |
| 541 | |||
| 542 | /* Update minutiae list with opposite points of max distance */ | ||
| 543 | /* on the loop. */ | ||
| 544 | |||
| 545 | /* First, check if interior point has proper pixel value. */ | ||
| 546 | ✗ | mid_x = (contour_x[max_fr]+contour_x[max_to])>>1; | |
| 547 | ✗ | mid_y = (contour_y[max_fr]+contour_y[max_to])>>1; | |
| 548 | ✗ | mid_pix = *(bdata + (mid_y * iw) + mid_x); | |
| 549 | /* If interior point is the same as the feature... */ | ||
| 550 | ✗ | if(mid_pix == feature_pix){ | |
| 551 | |||
| 552 | /* 1. Treat maximum distance point as a potential minutia. */ | ||
| 553 | |||
| 554 | /* Compute direction from maximum loop point to its */ | ||
| 555 | /* opposite point. */ | ||
| 556 | ✗ | idir = line2direction(contour_x[max_fr], contour_y[max_fr], | |
| 557 | contour_x[max_to], contour_y[max_to], | ||
| 558 | ✗ | lfsparms->num_directions); | |
| 559 | /* Get type of minutia: BIFURCATION or RIDGE_ENDING. */ | ||
| 560 | ✗ | type = minutia_type(feature_pix); | |
| 561 | /* Determine if minutia is appearing or disappearing. */ | ||
| 562 | ✗ | if((appearing = is_minutia_appearing( | |
| 563 | ✗ | contour_x[max_fr], contour_y[max_fr], | |
| 564 | ✗ | contour_ex[max_fr], contour_ey[max_fr])) < 0){ | |
| 565 | /* Return system error code. */ | ||
| 566 | return(appearing); | ||
| 567 | } | ||
| 568 | |||
| 569 | /* Is the new point in a LOW RIDGE FLOW block? */ | ||
| 570 | ✗ | fmapval = *(plow_flow_map+(contour_y[max_fr]*iw)+ | |
| 571 | ✗ | contour_x[max_fr]); | |
| 572 | |||
| 573 | /* If current minutia is in a LOW RIDGE FLOW block ... */ | ||
| 574 | ✗ | if(fmapval) | |
| 575 | reliability = MEDIUM_RELIABILITY; | ||
| 576 | else | ||
| 577 | /* Otherwise, minutia is in a reliable block. */ | ||
| 578 | ✗ | reliability = HIGH_RELIABILITY; | |
| 579 | |||
| 580 | /* Create new minutia object. */ | ||
| 581 | ✗ | if((ret = create_minutia(&minutia, | |
| 582 | contour_x[max_fr], contour_y[max_fr], | ||
| 583 | ✗ | contour_ex[max_fr], contour_ey[max_fr], | |
| 584 | idir, reliability, | ||
| 585 | type, appearing, LOOP_ID))){ | ||
| 586 | /* Return system error code. */ | ||
| 587 | return(ret); | ||
| 588 | } | ||
| 589 | /* Update the minutiae list with potential new minutia. */ | ||
| 590 | /* NOTE: Deliberately using version one of this routine. */ | ||
| 591 | ✗ | ret = update_minutiae(minutiae, minutia, bdata, iw, ih, lfsparms); | |
| 592 | |||
| 593 | /* If minuitia IGNORED and not added to the minutia list ... */ | ||
| 594 | ✗ | if(ret == IGNORE) | |
| 595 | /* Deallocate the minutia. */ | ||
| 596 | ✗ | free_minutia(minutia); | |
| 597 | |||
| 598 | /* 2. Treat point opposite of maximum distance point as */ | ||
| 599 | /* a potential minutia. */ | ||
| 600 | |||
| 601 | /* Flip the direction 180 degrees. Make sure new direction */ | ||
| 602 | /* is on the range [0..(ndirsX2)]. */ | ||
| 603 | ✗ | idir += lfsparms->num_directions; | |
| 604 | ✗ | idir %= (lfsparms->num_directions<<1); | |
| 605 | |||
| 606 | /* The type of minutia will stay the same. */ | ||
| 607 | |||
| 608 | /* Determine if minutia is appearing or disappearing. */ | ||
| 609 | ✗ | if((appearing = is_minutia_appearing( | |
| 610 | ✗ | contour_x[max_to], contour_y[max_to], | |
| 611 | ✗ | contour_ex[max_to], contour_ey[max_to])) < 0){ | |
| 612 | /* Return system error code. */ | ||
| 613 | return(appearing); | ||
| 614 | } | ||
| 615 | |||
| 616 | /* Is the new point in a LOW RIDGE FLOW block? */ | ||
| 617 | ✗ | fmapval = *(plow_flow_map+(contour_y[max_to]*iw)+ | |
| 618 | ✗ | contour_x[max_to]); | |
| 619 | |||
| 620 | /* If current minutia is in a LOW RIDGE FLOW block ... */ | ||
| 621 | ✗ | if(fmapval) | |
| 622 | reliability = MEDIUM_RELIABILITY; | ||
| 623 | else | ||
| 624 | /* Otherwise, minutia is in a reliable block. */ | ||
| 625 | ✗ | reliability = HIGH_RELIABILITY; | |
| 626 | |||
| 627 | /* Create new minutia object. */ | ||
| 628 | ✗ | if((ret = create_minutia(&minutia, | |
| 629 | contour_x[max_to], contour_y[max_to], | ||
| 630 | ✗ | contour_ex[max_to], contour_ey[max_to], | |
| 631 | idir, reliability, | ||
| 632 | type, appearing, LOOP_ID))){ | ||
| 633 | /* Return system error code. */ | ||
| 634 | return(ret); | ||
| 635 | } | ||
| 636 | |||
| 637 | /* Update the minutiae list with potential new minutia. */ | ||
| 638 | /* NOTE: Deliberately using version one of this routine. */ | ||
| 639 | ✗ | ret = update_minutiae(minutiae, minutia, bdata, iw, ih, lfsparms); | |
| 640 | |||
| 641 | /* If minuitia IGNORED and not added to the minutia list ... */ | ||
| 642 | ✗ | if(ret == IGNORE) | |
| 643 | /* Deallocate the minutia. */ | ||
| 644 | ✗ | free_minutia(minutia); | |
| 645 | |||
| 646 | /* Done successfully processing this loop, so return normally. */ | ||
| 647 | ✗ | return(0); | |
| 648 | |||
| 649 | } /* Otherwise, loop interior has problems. */ | ||
| 650 | } /* Otherwise, loop is not the right shape for minutiae. */ | ||
| 651 | } /* Otherwise, loop's perimeter is too small for minutiae. */ | ||
| 652 | |||
| 653 | /* If we get here, we have a loop that is assumed to not contain */ | ||
| 654 | /* minutiae, so remove the loop from the image. */ | ||
| 655 | 167 | ret = fill_loop(contour_x, contour_y, ncontour, bdata, iw, ih); | |
| 656 | |||
| 657 | /* Return either an error code from fill_loop or return normally. */ | ||
| 658 | 167 | return(ret); | |
| 659 | } | ||
| 660 | |||
| 661 | /************************************************************************* | ||
| 662 | ************************************************************************** | ||
| 663 | #cat: get_loop_aspect - Takes a contour list (determined to form a complete | ||
| 664 | #cat: loop) and measures the loop's aspect (the largest and smallest | ||
| 665 | #cat: distances across the loop) and returns the points on the | ||
| 666 | #cat: loop where these distances occur. | ||
| 667 | |||
| 668 | Input: | ||
| 669 | contour_x - x-coord list for loop's contour points | ||
| 670 | contour_y - y-coord list for loop's contour points | ||
| 671 | ncontour - number of points in contour | ||
| 672 | Output: | ||
| 673 | omin_fr - contour point index where minimum aspect occurs | ||
| 674 | omin_to - opposite contour point index where minimum aspect occurs | ||
| 675 | omin_dist - the minimum distance across the loop | ||
| 676 | omax_fr - contour point index where maximum aspect occurs | ||
| 677 | omax_to - contour point index where maximum aspect occurs | ||
| 678 | omax_dist - the maximum distance across the loop | ||
| 679 | **************************************************************************/ | ||
| 680 | ✗ | void get_loop_aspect(int *omin_fr, int *omin_to, double *omin_dist, | |
| 681 | int *omax_fr, int *omax_to, double *omax_dist, | ||
| 682 | const int *contour_x, const int *contour_y, const int ncontour) | ||
| 683 | { | ||
| 684 | ✗ | int halfway, limit; | |
| 685 | ✗ | int i, j; | |
| 686 | ✗ | double dist; | |
| 687 | ✗ | double min_dist, max_dist; | |
| 688 | ✗ | int min_i, max_i, min_j, max_j; | |
| 689 | |||
| 690 | /* Compute half the perimeter of the loop. */ | ||
| 691 | ✗ | halfway = ncontour>>1; | |
| 692 | |||
| 693 | /* Take opposite points on the contour and walk half way */ | ||
| 694 | /* around the loop. */ | ||
| 695 | ✗ | i = 0; | |
| 696 | ✗ | j = halfway; | |
| 697 | /* Compute squared distance between opposite points on loop. */ | ||
| 698 | ✗ | dist = squared_distance(contour_x[i], contour_y[i], | |
| 699 | ✗ | contour_x[j], contour_y[j]); | |
| 700 | |||
| 701 | /* Initialize running minimum and maximum distances along loop. */ | ||
| 702 | ✗ | min_dist = dist; | |
| 703 | ✗ | min_i = i; | |
| 704 | ✗ | min_j = j; | |
| 705 | ✗ | max_dist = dist; | |
| 706 | ✗ | max_i = i; | |
| 707 | ✗ | max_j = j; | |
| 708 | /* Bump to next pair of opposite points. */ | ||
| 709 | ✗ | i++; | |
| 710 | /* Make sure j wraps around end of list. */ | ||
| 711 | ✗ | j++; | |
| 712 | ✗ | j %= ncontour; | |
| 713 | |||
| 714 | /* If the loop is of even length, then we only need to walk half */ | ||
| 715 | /* way around as the other half will be exactly redundant. If */ | ||
| 716 | /* the loop is of odd length, then the second half will not be */ | ||
| 717 | /* be exactly redundant and the difference "may" be meaningful. */ | ||
| 718 | /* If execution speed is an issue, then probably get away with */ | ||
| 719 | /* walking only the fist half of the loop under ALL conditions. */ | ||
| 720 | |||
| 721 | /* If loop has odd length ... */ | ||
| 722 | ✗ | if(ncontour % 2) | |
| 723 | /* Walk the loop's entire perimeter. */ | ||
| 724 | ✗ | limit = ncontour; | |
| 725 | /* Otherwise the loop has even length ... */ | ||
| 726 | else | ||
| 727 | /* Only walk half the perimeter. */ | ||
| 728 | ✗ | limit = halfway; | |
| 729 | |||
| 730 | /* While we have not reached our perimeter limit ... */ | ||
| 731 | ✗ | while(i < limit){ | |
| 732 | /* Compute squared distance between opposite points on loop. */ | ||
| 733 | ✗ | dist = squared_distance(contour_x[i], contour_y[i], | |
| 734 | ✗ | contour_x[j], contour_y[j]); | |
| 735 | /* Check the running minimum and maximum distances. */ | ||
| 736 | ✗ | if(dist < min_dist){ | |
| 737 | ✗ | min_dist = dist; | |
| 738 | ✗ | min_i = i; | |
| 739 | ✗ | min_j = j; | |
| 740 | } | ||
| 741 | ✗ | if(dist > max_dist){ | |
| 742 | ✗ | max_dist = dist; | |
| 743 | ✗ | max_i = i; | |
| 744 | ✗ | max_j = j; | |
| 745 | } | ||
| 746 | /* Bump to next pair of opposite points. */ | ||
| 747 | ✗ | i++; | |
| 748 | /* Make sure j wraps around end of list. */ | ||
| 749 | ✗ | j++; | |
| 750 | ✗ | j %= ncontour; | |
| 751 | } | ||
| 752 | |||
| 753 | /* Assign minimum and maximum distances to output pointers. */ | ||
| 754 | ✗ | *omin_fr = min_i; | |
| 755 | ✗ | *omin_to = min_j; | |
| 756 | ✗ | *omin_dist = min_dist; | |
| 757 | ✗ | *omax_fr = max_i; | |
| 758 | ✗ | *omax_to = max_j; | |
| 759 | ✗ | *omax_dist = max_dist; | |
| 760 | ✗ | } | |
| 761 | |||
| 762 | /************************************************************************* | ||
| 763 | ************************************************************************** | ||
| 764 | #cat: fill_loop - Takes a contour list that has been determined to form | ||
| 765 | #cat: a complete loop, and fills the loop accounting for | ||
| 766 | #cat: complex/concaved shapes. | ||
| 767 | #cat: NOTE, I tried using a flood-fill in place of this routine, | ||
| 768 | #cat: but the contour (although 8-connected) is NOT guaranteed to | ||
| 769 | #cat: be "complete" surrounded (in an 8-connected sense) by pixels | ||
| 770 | #cat: of opposite color. Therefore, the flood would occasionally | ||
| 771 | #cat: escape the loop and corrupt the binary image! | ||
| 772 | |||
| 773 | Input: | ||
| 774 | contour_x - x-coord list for loop's contour points | ||
| 775 | contour_y - y-coord list for loop's contour points | ||
| 776 | ncontour - number of points in contour | ||
| 777 | bdata - binary image data (0==while & 1==black) | ||
| 778 | iw - width (in pixels) of image | ||
| 779 | ih - height (in pixels) of image | ||
| 780 | Output: | ||
| 781 | bdata - binary image data with loop filled | ||
| 782 | Return Code: | ||
| 783 | Zero - loop filled successfully | ||
| 784 | Negative - system error | ||
| 785 | **************************************************************************/ | ||
| 786 | 2980 | int fill_loop(const int *contour_x, const int *contour_y, | |
| 787 | const int ncontour, unsigned char *bdata, | ||
| 788 | const int iw, const int ih) | ||
| 789 | { | ||
| 790 | 2980 | SHAPE *shape; | |
| 791 | 2980 | int ret, i, j, x, nx, y; | |
| 792 | 2980 | int lastj; | |
| 793 | 2980 | int next_pix, feature_pix, edge_pix; | |
| 794 | |||
| 795 | /* Create a shape structure from loop's contour. */ | ||
| 796 |
1/2✓ Branch 1 taken 2980 times.
✗ Branch 2 not taken.
|
2980 | if((ret = shape_from_contour(&shape, contour_x, contour_y, ncontour))) |
| 797 | /* If system error, then return error code. */ | ||
| 798 | return(ret); | ||
| 799 | |||
| 800 | /* Get feature pixel value (the value on the interior of the loop */ | ||
| 801 | /* to be filled). */ | ||
| 802 | 2980 | feature_pix = *(bdata+(contour_y[0]*iw)+contour_x[0]); | |
| 803 | /* Now get edge pixel value (the value on the exterior of the loop */ | ||
| 804 | /* to be used to filled the loop). We can get this value by flipping */ | ||
| 805 | /* the feature pixel value. */ | ||
| 806 |
2/2✓ Branch 0 taken 1617 times.
✓ Branch 1 taken 1363 times.
|
2980 | if(feature_pix) |
| 807 | edge_pix = 0; | ||
| 808 | else | ||
| 809 | 1617 | edge_pix = 1; | |
| 810 | |||
| 811 | /* Foreach row in shape... */ | ||
| 812 |
2/2✓ Branch 0 taken 14050 times.
✓ Branch 1 taken 2980 times.
|
17030 | for(i = 0; i < shape->nrows; i++){ |
| 813 | /* Get y-coord of current row in shape. */ | ||
| 814 | 14050 | y = shape->rows[i]->y; | |
| 815 | |||
| 816 | /* There should always be at least 1 contour points in the row. */ | ||
| 817 | /* If there isn't, then something is wrong, so post a warning and */ | ||
| 818 | /* just return. This is mostly for debug purposes. */ | ||
| 819 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 14050 times.
|
14050 | if(shape->rows[i]->npts < 1){ |
| 820 | /* Deallocate the shape. */ | ||
| 821 | ✗ | free_shape(shape); | |
| 822 | ✗ | fprintf(stderr, | |
| 823 | "WARNING : fill_loop : unexpected shape, preempting loop fill\n"); | ||
| 824 | /* This is unexpected, but not fatal, so return normally. */ | ||
| 825 | ✗ | return(0); | |
| 826 | } | ||
| 827 | |||
| 828 | /* Reset x index on row to the left-most contour point in the row. */ | ||
| 829 | 14050 | j = 0; | |
| 830 | /* Get first x-coord corresponding to the first contour point on row. */ | ||
| 831 | 14050 | x = shape->rows[i]->xs[j]; | |
| 832 | /* Fill the first contour point on the row. */ | ||
| 833 | 14050 | *(bdata+(y*iw)+x) = edge_pix; | |
| 834 | /* Set the index of last contour point on row. */ | ||
| 835 | 14050 | lastj = shape->rows[i]->npts - 1; | |
| 836 | /* While last contour point on row has not been processed... */ | ||
| 837 |
2/2✓ Branch 0 taken 27564 times.
✓ Branch 1 taken 14050 times.
|
41614 | while(j < lastj){ |
| 838 | |||
| 839 | /* On each interation, we have filled up to the current */ | ||
| 840 | /* contour point on the row pointed to by "j", and now we */ | ||
| 841 | /* need to determine if we need to skip some edge pixels */ | ||
| 842 | /* caused by a concavity in the shape or not. */ | ||
| 843 | |||
| 844 | /* Get the next pixel value on the row just right of the */ | ||
| 845 | /* last contour point filled. We know there are more points */ | ||
| 846 | /* on the row because we haven't processed the last contour */ | ||
| 847 | /* point on the row yet. */ | ||
| 848 | 27564 | x++; | |
| 849 | 27564 | next_pix = *(bdata+(y*iw)+x); | |
| 850 | |||
| 851 | /* If the next pixel is the same value as loop's edge pixels ... */ | ||
| 852 |
2/2✓ Branch 0 taken 1406 times.
✓ Branch 1 taken 26158 times.
|
27564 | if(next_pix == edge_pix){ |
| 853 | /* Then assume we have found a concavity and skip to next */ | ||
| 854 | /* contour point on row. */ | ||
| 855 | 1406 | j++; | |
| 856 | /* Fill the new contour point because we know it is on the */ | ||
| 857 | /* feature's contour. */ | ||
| 858 | 1406 | x = shape->rows[i]->xs[j]; | |
| 859 | 1406 | *(bdata+(y*iw)+x) = edge_pix; | |
| 860 | |||
| 861 | /* Now we are ready to loop again. */ | ||
| 862 | } | ||
| 863 | |||
| 864 | /* Otherwise, fill from current pixel up through the next contour */ | ||
| 865 | /* point to the right on the row. */ | ||
| 866 | else{ | ||
| 867 | /* Bump to the next contour point to the right on row. */ | ||
| 868 | 26158 | j++; | |
| 869 | /* Set the destination x-coord to the next contour point */ | ||
| 870 | /* to the right on row. Realize that this could be the */ | ||
| 871 | /* same pixel as the current x-coord if contour points are */ | ||
| 872 | /* adjacent. */ | ||
| 873 | 26158 | nx = shape->rows[i]->xs[j]; | |
| 874 | |||
| 875 | /* Fill between current x-coord and next contour point to the */ | ||
| 876 | /* right on the row (including the new contour point).*/ | ||
| 877 | 26158 | fill_partial_row(edge_pix, x, nx, y, bdata, iw, ih); | |
| 878 | } | ||
| 879 | |||
| 880 | /* Once we are here we have filled the row up to (and including) */ | ||
| 881 | /* the contour point currently pointed to by "j". */ | ||
| 882 | /* We are now ready to loop again. */ | ||
| 883 | |||
| 884 | } /* End WHILE */ | ||
| 885 | } /* End FOR */ | ||
| 886 | |||
| 887 | 2980 | free_shape(shape); | |
| 888 | |||
| 889 | /* Return normally. */ | ||
| 890 | 2980 | return(0); | |
| 891 | } | ||
| 892 | |||
| 893 | /************************************************************************* | ||
| 894 | ************************************************************************** | ||
| 895 | #cat: fill_partial_row - Fills a specified range of contiguous pixels on | ||
| 896 | #cat: a specified row of an 8-bit pixel image with a specified | ||
| 897 | #cat: pixel value. NOTE, the pixel coordinates are assumed to | ||
| 898 | #cat: be within the image boundaries. | ||
| 899 | |||
| 900 | Input: | ||
| 901 | fill_pix - pixel value to fill with (should be on range [0..255] | ||
| 902 | frx - x-pixel coord where fill should begin | ||
| 903 | tox - x-pixel coord where fill should end (inclusive) | ||
| 904 | y - y-pixel coord of current row being filled | ||
| 905 | bdata - 8-bit image data | ||
| 906 | iw - width (in pixels) of image | ||
| 907 | ih - height (in pixels) of image | ||
| 908 | Output: | ||
| 909 | bdata - 8-bit image data with partial row filled. | ||
| 910 | **************************************************************************/ | ||
| 911 | 26158 | void fill_partial_row(const int fill_pix, const int frx, const int tox, | |
| 912 | const int y, unsigned char *bdata, const int iw, const int ih) | ||
| 913 | { | ||
| 914 | 26158 | int x; | |
| 915 | 26158 | unsigned char *bptr; | |
| 916 | |||
| 917 | /* Set pixel pointer to starting x-coord on current row. */ | ||
| 918 | 26158 | bptr = bdata+(y*iw)+frx; | |
| 919 | |||
| 920 | /* Foreach pixel between starting and ending x-coord on row */ | ||
| 921 | /* (including the end points) ... */ | ||
| 922 |
2/2✓ Branch 0 taken 37509 times.
✓ Branch 1 taken 26158 times.
|
63667 | for(x = frx; x <= tox; x++){ |
| 923 | /* Set current pixel with fill pixel value. */ | ||
| 924 | 37509 | *bptr = fill_pix; | |
| 925 | /* Bump to next pixel in the row. */ | ||
| 926 | 37509 | bptr++; | |
| 927 | } | ||
| 928 | 26158 | } | |
| 929 | |||
| 930 | /************************************************************************* | ||
| 931 | ************************************************************************** | ||
| 932 | #cat: flood_loop - Fills a given contour (determined to form a complete loop) | ||
| 933 | #cat: with a specified pixel value using a recursive flood-fill | ||
| 934 | #cat: technique. | ||
| 935 | #cat: NOTE, this fill approach will NOT always work with the | ||
| 936 | #cat: contours generated in this application because they | ||
| 937 | #cat: are NOT guaranteed to be ENTIRELY surrounded by 8-connected | ||
| 938 | #cat: pixels not equal to the fill pixel value. This is unfortunate | ||
| 939 | #cat: because the flood-fill is a simple algorithm that will handle | ||
| 940 | #cat: complex/concaved shapes. | ||
| 941 | |||
| 942 | Input: | ||
| 943 | contour_x - x-coord list for loop's contour points | ||
| 944 | contour_y - y-coord list for loop's contour points | ||
| 945 | ncontour - number of points in contour | ||
| 946 | bdata - binary image data (0==while & 1==black) | ||
| 947 | iw - width (in pixels) of image | ||
| 948 | ih - height (in pixels) of image | ||
| 949 | Output: | ||
| 950 | bdata - binary image data with loop filled | ||
| 951 | **************************************************************************/ | ||
| 952 | |||
| 953 | /************************************************************************* | ||
| 954 | ************************************************************************** | ||
| 955 | #cat: flood_fill4 - Recursively floods a region of an 8-bit pixel image with a | ||
| 956 | #cat: specified pixel value given a starting (seed) point. The | ||
| 957 | #cat: recursion is based neighbors being 4-connected. | ||
| 958 | |||
| 959 | Input: | ||
| 960 | fill_pix - 8-bit pixel value to be filled with (on range [0..255] | ||
| 961 | x - starting x-pixel coord | ||
| 962 | y - starting y-pixel coord | ||
| 963 | bdata - 8-bit pixel image data | ||
| 964 | iw - width (in pixels) of image | ||
| 965 | ih - height (in pixels) of image | ||
| 966 | Output: | ||
| 967 | bdata - 8-bit pixel image data with region filled | ||
| 968 | **************************************************************************/ | ||
| 969 | ✗ | void flood_fill4(const int fill_pix, const int x, const int y, | |
| 970 | unsigned char *bdata, const int iw, const int ih) | ||
| 971 | { | ||
| 972 | ✗ | unsigned char *pptr; | |
| 973 | ✗ | int y_north, y_south, x_east, x_west; | |
| 974 | |||
| 975 | /* Get address of current pixel. */ | ||
| 976 | ✗ | pptr = bdata + (y*iw) + x; | |
| 977 | /* If pixel needs to be filled ... */ | ||
| 978 | ✗ | if(*pptr != fill_pix){ | |
| 979 | /* Fill the current pixel. */ | ||
| 980 | ✗ | *pptr = fill_pix; | |
| 981 | |||
| 982 | /* Recursively invoke flood on the pixel's 4 neighbors. */ | ||
| 983 | /* Test to make sure neighbors are within image boudaries */ | ||
| 984 | /* before invoking each flood. */ | ||
| 985 | ✗ | y_north = y-1; | |
| 986 | ✗ | y_south = y+1; | |
| 987 | ✗ | x_west = x-1; | |
| 988 | ✗ | x_east = x+1; | |
| 989 | |||
| 990 | /* Invoke North */ | ||
| 991 | ✗ | if(y_north >= 0) | |
| 992 | ✗ | flood_fill4(fill_pix, x, y_north, bdata, iw, ih); | |
| 993 | |||
| 994 | /* Invoke East */ | ||
| 995 | ✗ | if(x_east < iw) | |
| 996 | ✗ | flood_fill4(fill_pix, x_east, y, bdata, iw, ih); | |
| 997 | |||
| 998 | /* Invoke South */ | ||
| 999 | ✗ | if(y_south < ih) | |
| 1000 | ✗ | flood_fill4(fill_pix, x, y_south, bdata, iw, ih); | |
| 1001 | |||
| 1002 | /* Invoke West */ | ||
| 1003 | ✗ | if(x_west >= 0) | |
| 1004 | flood_fill4(fill_pix, x_west, y, bdata, iw, ih); | ||
| 1005 | } | ||
| 1006 | |||
| 1007 | /* Otherwise, there is nothing to be done. */ | ||
| 1008 | ✗ | } | |
| 1009 |