1 /*M/////////////////////////////////////////////////////////////////////////////////////// 2 // 3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. 4 // 5 // By downloading, copying, installing or using the software you agree to this license. 6 // If you do not agree to this license, do not download, install, 7 // copy or use the software. 8 // 9 // 10 // Intel License Agreement 11 // For Open Source Computer Vision Library 12 // 13 // Copyright (C) 2000, Intel Corporation, all rights reserved. 14 // Third party copyrights are property of their respective owners. 15 // 16 // Redistribution and use in source and binary forms, with or without modification, 17 // are permitted provided that the following conditions are met: 18 // 19 // * Redistribution's of source code must retain the above copyright notice, 20 // this list of conditions and the following disclaimer. 21 // 22 // * Redistribution's in binary form must reproduce the above copyright notice, 23 // this list of conditions and the following disclaimer in the documentation 24 // and/or other materials provided with the distribution. 25 // 26 // * The name of Intel Corporation may not be used to endorse or promote products 27 // derived from this software without specific prior written permission. 28 // 29 // This software is provided by the copyright holders and contributors "as is" and 30 // any express or implied warranties, including, but not limited to, the implied 31 // warranties of merchantability and fitness for a particular purpose are disclaimed. 32 // In no event shall the Intel Corporation or contributors be liable for any direct, 33 // indirect, incidental, special, exemplary, or consequential damages 34 // (including, but not limited to, procurement of substitute goods or services; 35 // loss of use, data, or profits; or business interruption) however caused 36 // and on any theory of liability, whether in contract, strict liability, 37 // or tort (including negligence or otherwise) arising in any way out of 38 // the use of this software, even if advised of the possibility of such damage. 39 // 40 //M*/ 41 #include "_cv.h" 42 43 typedef struct _PointInfo 44 { 45 CvPoint pt; 46 int left_neigh; 47 int right_neigh; 48 49 } 50 icvPointInfo; 51 52 53 static CvStatus 54 icvFindDominantPointsIPAN( CvSeq * contour, 55 CvMemStorage * storage, 56 CvSeq ** corners, int dmin2, int dmax2, int dneigh2, float amax ) 57 { 58 CvStatus status = CV_OK; 59 60 /* variables */ 61 int n = contour->total; 62 63 float *sharpness; 64 float *distance; 65 icvPointInfo *ptInf; 66 67 int i, j, k; 68 69 CvSeqWriter writer; 70 71 float mincos = (float) cos( 3.14159265359 * amax / 180 ); 72 73 /* check bad arguments */ 74 if( contour == NULL ) 75 return CV_NULLPTR_ERR; 76 if( storage == NULL ) 77 return CV_NULLPTR_ERR; 78 if( corners == NULL ) 79 return CV_NULLPTR_ERR; 80 if( dmin2 < 0 ) 81 return CV_BADSIZE_ERR; 82 if( dmax2 < dmin2 ) 83 return CV_BADSIZE_ERR; 84 if( (dneigh2 > dmax2) || (dneigh2 < 0) ) 85 return CV_BADSIZE_ERR; 86 if( (amax < 0) || (amax > 180) ) 87 return CV_BADSIZE_ERR; 88 89 sharpness = (float *) cvAlloc( n * sizeof( float )); 90 distance = (float *) cvAlloc( n * sizeof( float )); 91 92 ptInf = (icvPointInfo *) cvAlloc( n * sizeof( icvPointInfo )); 93 94 /*****************************************************************************************/ 95 /* First pass */ 96 /*****************************************************************************************/ 97 98 if( CV_IS_SEQ_CHAIN_CONTOUR( contour )) 99 { 100 CvChainPtReader reader; 101 102 cvStartReadChainPoints( (CvChain *) contour, &reader ); 103 104 for( i = 0; i < n; i++ ) 105 { 106 CV_READ_CHAIN_POINT( ptInf[i].pt, reader ); 107 } 108 } 109 else if( CV_IS_SEQ_POLYGON( contour )) 110 { 111 CvSeqReader reader; 112 113 cvStartReadSeq( contour, &reader, 0 ); 114 115 for( i = 0; i < n; i++ ) 116 { 117 CV_READ_SEQ_ELEM( ptInf[i].pt, reader ); 118 } 119 } 120 else 121 { 122 return CV_BADFLAG_ERR; 123 } 124 125 for( i = 0; i < n; i++ ) 126 { 127 /* find nearest suitable points 128 which satisfy distance constraint >dmin */ 129 int left_near = 0; 130 int right_near = 0; 131 int left_far, right_far; 132 133 float dist_l = 0; 134 float dist_r = 0; 135 136 int i_plus = 0; 137 int i_minus = 0; 138 139 float max_cos_alpha; 140 141 /* find right minimum */ 142 while( dist_r < dmin2 ) 143 { 144 float dx, dy; 145 int ind; 146 147 if( i_plus >= n ) 148 goto error; 149 150 right_near = i_plus; 151 152 if( dist_r < dneigh2 ) 153 ptInf[i].right_neigh = i_plus; 154 155 i_plus++; 156 157 ind = (i + i_plus) % n; 158 dx = (float) (ptInf[i].pt.x - ptInf[ind].pt.x); 159 dy = (float) (ptInf[i].pt.y - ptInf[ind].pt.y); 160 dist_r = dx * dx + dy * dy; 161 } 162 /* find right maximum */ 163 while( dist_r <= dmax2 ) 164 { 165 float dx, dy; 166 int ind; 167 168 if( i_plus >= n ) 169 goto error; 170 171 distance[(i + i_plus) % n] = cvSqrt( dist_r ); 172 173 if( dist_r < dneigh2 ) 174 ptInf[i].right_neigh = i_plus; 175 176 i_plus++; 177 178 right_far = i_plus; 179 180 ind = (i + i_plus) % n; 181 182 dx = (float) (ptInf[i].pt.x - ptInf[ind].pt.x); 183 dy = (float) (ptInf[i].pt.y - ptInf[ind].pt.y); 184 dist_r = dx * dx + dy * dy; 185 } 186 right_far = i_plus; 187 188 /* left minimum */ 189 while( dist_l < dmin2 ) 190 { 191 float dx, dy; 192 int ind; 193 194 if( i_minus <= -n ) 195 goto error; 196 197 left_near = i_minus; 198 199 if( dist_l < dneigh2 ) 200 ptInf[i].left_neigh = i_minus; 201 202 i_minus--; 203 204 ind = i + i_minus; 205 ind = (ind < 0) ? (n + ind) : ind; 206 207 dx = (float) (ptInf[i].pt.x - ptInf[ind].pt.x); 208 dy = (float) (ptInf[i].pt.y - ptInf[ind].pt.y); 209 dist_l = dx * dx + dy * dy; 210 } 211 212 /* find left maximum */ 213 while( dist_l <= dmax2 ) 214 { 215 float dx, dy; 216 int ind; 217 218 if( i_minus <= -n ) 219 goto error; 220 221 ind = i + i_minus; 222 ind = (ind < 0) ? (n + ind) : ind; 223 224 distance[ind] = cvSqrt( dist_l ); 225 226 if( dist_l < dneigh2 ) 227 ptInf[i].left_neigh = i_minus; 228 229 i_minus--; 230 231 left_far = i_minus; 232 233 ind = i + i_minus; 234 ind = (ind < 0) ? (n + ind) : ind; 235 236 dx = (float) (ptInf[i].pt.x - ptInf[ind].pt.x); 237 dy = (float) (ptInf[i].pt.y - ptInf[ind].pt.y); 238 dist_l = dx * dx + dy * dy; 239 } 240 left_far = i_minus; 241 242 if( (i_plus - i_minus) > n + 2 ) 243 goto error; 244 245 max_cos_alpha = -1; 246 for( j = left_far + 1; j < left_near; j++ ) 247 { 248 float dx, dy; 249 float a, a2; 250 int leftind = i + j; 251 252 leftind = (leftind < 0) ? (n + leftind) : leftind; 253 254 a = distance[leftind]; 255 a2 = a * a; 256 257 for( k = right_near + 1; k < right_far; k++ ) 258 { 259 int ind = (i + k) % n; 260 float c2, cosalpha; 261 float b = distance[ind]; 262 float b2 = b * b; 263 264 /* compute cosinus */ 265 dx = (float) (ptInf[leftind].pt.x - ptInf[ind].pt.x); 266 dy = (float) (ptInf[leftind].pt.y - ptInf[ind].pt.y); 267 268 c2 = dx * dx + dy * dy; 269 cosalpha = (a2 + b2 - c2) / (2 * a * b); 270 271 max_cos_alpha = MAX( max_cos_alpha, cosalpha ); 272 273 if( max_cos_alpha < mincos ) 274 max_cos_alpha = -1; 275 276 sharpness[i] = max_cos_alpha; 277 } 278 } 279 } 280 /*****************************************************************************************/ 281 /* Second pass */ 282 /*****************************************************************************************/ 283 284 cvStartWriteSeq( (contour->flags & ~CV_SEQ_ELTYPE_MASK) | CV_SEQ_ELTYPE_INDEX, 285 sizeof( CvSeq ), sizeof( int ), storage, &writer ); 286 287 /* second pass - nonmaxima suppression */ 288 /* neighborhood of point < dneigh2 */ 289 for( i = 0; i < n; i++ ) 290 { 291 int suppressed = 0; 292 if( sharpness[i] == -1 ) 293 continue; 294 295 for( j = 1; (j <= ptInf[i].right_neigh) && (suppressed == 0); j++ ) 296 { 297 if( sharpness[i] < sharpness[(i + j) % n] ) 298 suppressed = 1; 299 } 300 301 for( j = -1; (j >= ptInf[i].left_neigh) && (suppressed == 0); j-- ) 302 { 303 int ind = i + j; 304 305 ind = (ind < 0) ? (n + ind) : ind; 306 if( sharpness[i] < sharpness[ind] ) 307 suppressed = 1; 308 } 309 310 if( !suppressed ) 311 CV_WRITE_SEQ_ELEM( i, writer ); 312 } 313 314 *corners = cvEndWriteSeq( &writer ); 315 316 cvFree( &sharpness ); 317 cvFree( &distance ); 318 cvFree( &ptInf ); 319 320 return status; 321 322 error: 323 /* dmax is so big (more than contour diameter) 324 that algorithm could become infinite cycle */ 325 cvFree( &sharpness ); 326 cvFree( &distance ); 327 cvFree( &ptInf ); 328 329 return CV_BADRANGE_ERR; 330 } 331 332 333 /*F/////////////////////////////////////////////////////////////////////////////////////// 334 // Name: icvFindDominantPoints 335 // Purpose: 336 // Applies some algorithm to find dominant points ( corners ) of contour 337 // 338 // Context: 339 // Parameters: 340 // contours - pointer to input contour object. 341 // out_numbers - array of dominant points indices 342 // count - length of out_numbers array on input 343 // and numbers of founded dominant points on output 344 // 345 // method - only CV_DOMINANT_IPAN now 346 // parameters - array of parameters 347 // for IPAN algorithm 348 // [0] - minimal distance 349 // [1] - maximal distance 350 // [2] - neighborhood distance (must be not greater than dmaximal distance) 351 // [3] - maximal possible angle of curvature 352 // Returns: 353 // CV_OK or error code 354 // Notes: 355 // User must allocate out_numbers array. If it is small - function fills array 356 // with part of points and returns error 357 //F*/ 358 CV_IMPL CvSeq* 359 cvFindDominantPoints( CvSeq * contour, CvMemStorage * storage, int method, 360 double parameter1, double parameter2, double parameter3, double parameter4 ) 361 { 362 CvSeq* corners = 0; 363 364 CV_FUNCNAME( "cvFindDominantPoints" ); 365 __BEGIN__; 366 367 if( !contour ) 368 CV_ERROR( CV_StsNullPtr, "" ); 369 370 if( !storage ) 371 storage = contour->storage; 372 373 if( !storage ) 374 CV_ERROR( CV_StsNullPtr, "" ); 375 376 switch (method) 377 { 378 case CV_DOMINANT_IPAN: 379 { 380 int dmin = cvRound(parameter1); 381 int dmax = cvRound(parameter2); 382 int dneigh = cvRound(parameter3); 383 int amax = cvRound(parameter4); 384 385 if( amax == 0 ) 386 amax = 150; 387 if( dmin == 0 ) 388 dmin = 7; 389 if( dmax == 0 ) 390 dmax = dmin + 2; 391 if( dneigh == 0 ) 392 dneigh = dmin; 393 394 IPPI_CALL( icvFindDominantPointsIPAN( contour, storage, &corners, 395 dmin*dmin, dmax*dmax, dneigh*dneigh, (float)amax )); 396 } 397 break; 398 default: 399 CV_ERROR_FROM_STATUS( CV_BADFLAG_ERR ); 400 } 401 402 __END__; 403 404 return corners; 405 } 406 407 /* End of file. */ 408
