| 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: CHAINCODE.C | ||
| 49 | AUTHOR: Michael D. Garris | ||
| 50 | DATE: 05/11/1999 | ||
| 51 | |||
| 52 | Contains routines responsible for generating and manipulating | ||
| 53 | chain codes as part of the NIST Latent Fingerprint System (LFS). | ||
| 54 | |||
| 55 | *********************************************************************** | ||
| 56 | ROUTINES: | ||
| 57 | chain_code_loop() | ||
| 58 | is_chain_clockwise() | ||
| 59 | ***********************************************************************/ | ||
| 60 | |||
| 61 | #include <stdio.h> | ||
| 62 | #include <lfs.h> | ||
| 63 | |||
| 64 | /************************************************************************* | ||
| 65 | ************************************************************************** | ||
| 66 | #cat: chain_code_loop - Converts a feature's contour points into an | ||
| 67 | #cat: 8-connected chain code vector. This encoding represents | ||
| 68 | #cat: the direction taken between each adjacent point in the | ||
| 69 | #cat: contour. Chain codes may be used for many purposes, such | ||
| 70 | #cat: as computing the perimeter or area of an object, and they | ||
| 71 | #cat: may be used in object detection and recognition. | ||
| 72 | |||
| 73 | Input: | ||
| 74 | contour_x - x-coord list for feature's contour points | ||
| 75 | contour_y - y-coord list for feature's contour points | ||
| 76 | ncontour - number of points in contour | ||
| 77 | Output: | ||
| 78 | ochain - resulting vector of chain codes | ||
| 79 | onchain - number of codes in chain | ||
| 80 | (same as number of points in contour) | ||
| 81 | Return Code: | ||
| 82 | Zero - chain code successful derived | ||
| 83 | Negative - system error | ||
| 84 | **************************************************************************/ | ||
| 85 | 167 | int chain_code_loop(int **ochain, int *onchain, | |
| 86 | const int *contour_x, const int *contour_y, const int ncontour) | ||
| 87 | { | ||
| 88 | 167 | int *chain; | |
| 89 | 167 | int i, j, dx, dy; | |
| 90 | |||
| 91 | /* If we don't have at least 3 points in the contour ... */ | ||
| 92 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 167 times.
|
167 | if(ncontour <= 3){ |
| 93 | /* Then we don't have a loop, so set chain length to 0 */ | ||
| 94 | /* and return without any allocations. */ | ||
| 95 | ✗ | *onchain = 0; | |
| 96 | ✗ | return(0); | |
| 97 | } | ||
| 98 | |||
| 99 | /* Allocate chain code vector. It will be the same length as the */ | ||
| 100 | /* number of points in the contour. There will be one chain code */ | ||
| 101 | /* between each point on the contour including a code between the */ | ||
| 102 | /* last to the first point on the contour (completing the loop). */ | ||
| 103 | 167 | chain = (int *)g_malloc(ncontour * sizeof(int)); | |
| 104 | |||
| 105 | /* For each neighboring point in the list (with "i" pointing to the */ | ||
| 106 | /* previous neighbor and "j" pointing to the next neighbor... */ | ||
| 107 |
2/2✓ Branch 1 taken 1180 times.
✓ Branch 2 taken 167 times.
|
1514 | for(i = 0, j=1; i < ncontour-1; i++, j++){ |
| 108 | /* Compute delta in X between neighbors. */ | ||
| 109 | 1180 | dx = contour_x[j] - contour_x[i]; | |
| 110 | /* Compute delta in Y between neighbors. */ | ||
| 111 | 1180 | dy = contour_y[j] - contour_y[i]; | |
| 112 | /* Derive chain code index from neighbor deltas. */ | ||
| 113 | /* The deltas are on the range [-1..1], so to use them as indices */ | ||
| 114 | /* into the code list, they must first be incremented by one. */ | ||
| 115 | 1180 | chain[i] = *(g_chaincodes_nbr8+((dy+1)*NBR8_DIM)+dx+1); | |
| 116 | } | ||
| 117 | |||
| 118 | /* Now derive chain code between last and first points in the */ | ||
| 119 | /* contour list. */ | ||
| 120 | 167 | dx = contour_x[0] - contour_x[i]; | |
| 121 | 167 | dy = contour_y[0] - contour_y[i]; | |
| 122 | 167 | chain[i] = *(g_chaincodes_nbr8+((dy+1)*NBR8_DIM)+dx+1); | |
| 123 | |||
| 124 | /* Store results to the output pointers. */ | ||
| 125 | 167 | *ochain = chain; | |
| 126 | 167 | *onchain = ncontour; | |
| 127 | |||
| 128 | /* Return normally. */ | ||
| 129 | 167 | return(0); | |
| 130 | } | ||
| 131 | |||
| 132 | /************************************************************************* | ||
| 133 | ************************************************************************** | ||
| 134 | #cat: is_chain_clockwise - Takes an 8-connected chain code vector and | ||
| 135 | #cat: determines if the codes are ordered clockwise or | ||
| 136 | #cat: counter-clockwise. | ||
| 137 | #cat: The routine also requires a default return value be | ||
| 138 | #cat: specified in the case the the routine is not able to | ||
| 139 | #cat: definitively determine the chains direction. This allows | ||
| 140 | #cat: the default response to be application-specific. | ||
| 141 | |||
| 142 | Input: | ||
| 143 | chain - chain code vector | ||
| 144 | nchain - number of codes in chain | ||
| 145 | default_ret - default return code (used when we can't tell the order) | ||
| 146 | Return Code: | ||
| 147 | TRUE - chain determined to be ordered clockwise | ||
| 148 | FALSE - chain determined to be ordered counter-clockwise | ||
| 149 | Default - could not determine the order of the chain | ||
| 150 | **************************************************************************/ | ||
| 151 | 167 | int is_chain_clockwise(const int *chain, const int nchain, | |
| 152 | const int default_ret) | ||
| 153 | { | ||
| 154 | 167 | int i, j, d, sum; | |
| 155 | |||
| 156 | /* Initialize turn-accumulator to 0. */ | ||
| 157 | 167 | sum = 0; | |
| 158 | |||
| 159 | /* Foreach neighboring code in chain, compute the difference in */ | ||
| 160 | /* direction and accumulate. Left-hand turns increment, whereas */ | ||
| 161 | /* right-hand decrement. */ | ||
| 162 |
2/2✓ Branch 0 taken 1180 times.
✓ Branch 1 taken 167 times.
|
1347 | for(i = 0, j =1; i < nchain-1; i++, j++){ |
| 163 | /* Compute delta in neighbor direction. */ | ||
| 164 | 1180 | d = chain[j] - chain[i]; | |
| 165 | /* Make the delta the "inner" distance. */ | ||
| 166 | /* If delta >= 4, for example if chain_i==2 and chain_j==7 (which */ | ||
| 167 | /* means the contour went from a step up to step down-to-the-right) */ | ||
| 168 | /* then 5=(7-2) which is >=4, so -3=(5-8) which means that the */ | ||
| 169 | /* change in direction is a righ-hand turn of 3 units). */ | ||
| 170 |
2/2✓ Branch 0 taken 3 times.
✓ Branch 1 taken 1177 times.
|
1180 | if(d >= 4) |
| 171 | 3 | d -= 8; | |
| 172 | /* If delta <= -4, for example if chain_i==7 and chain_j==2 (which */ | ||
| 173 | /* means the contour went from a step down-to-the-right to step up) */ | ||
| 174 | /* then -5=(2-7) which is <=-4, so 3=(-5+8) which means that the */ | ||
| 175 | /* change in direction is a left-hand turn of 3 units). */ | ||
| 176 |
2/2✓ Branch 0 taken 169 times.
✓ Branch 1 taken 1008 times.
|
1177 | else if (d <= -4) |
| 177 | 169 | d += 8; | |
| 178 | |||
| 179 | /* The delta direction is then accumulated. */ | ||
| 180 | 1180 | sum += d; | |
| 181 | } | ||
| 182 | |||
| 183 | /* Now we need to add in the final delta direction between the last */ | ||
| 184 | /* and first codes in the chain. */ | ||
| 185 | 167 | d = chain[0] - chain[i]; | |
| 186 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 167 times.
|
167 | if(d >= 4) |
| 187 | ✗ | d -= 8; | |
| 188 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 166 times.
|
167 | else if (d <= -4) |
| 189 | 1 | d += 8; | |
| 190 | 167 | sum += d; | |
| 191 | |||
| 192 | /* If the final turn_accumulator == 0, then we CAN'T TELL the */ | ||
| 193 | /* direction of the chain code, so return the default return value. */ | ||
| 194 |
1/2✓ Branch 0 taken 167 times.
✗ Branch 1 not taken.
|
167 | if(sum == 0) |
| 195 | return(default_ret); | ||
| 196 | /* Otherwise, if the final turn-accumulator is positive ... */ | ||
| 197 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 167 times.
|
167 | else if(sum > 0) |
| 198 | /* Then we had a greater amount of left-hand turns than right-hand */ | ||
| 199 | /* turns, so the chain is in COUNTER-CLOCKWISE order, so return FALSE. */ | ||
| 200 | return(FALSE); | ||
| 201 | /* Otherwise, the final turn-accumulator is negative ... */ | ||
| 202 | else | ||
| 203 | /* So we had a greater amount of right-hand turns than left-hand */ | ||
| 204 | /* turns, so the chain is in CLOCKWISE order, so return TRUE. */ | ||
| 205 | ✗ | return(TRUE); | |
| 206 | } | ||
| 207 |