git.maemo.org Git - opencv/blob - cv/src/cvdominants.cpp

   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. */