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
43typedef struct _PointInfo
44{
45    CvPoint pt;
46    int left_neigh;
47    int right_neigh;
48
49}
50icvPointInfo;
51
52
53static CvStatus
54icvFindDominantPointsIPAN( 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*/
358CV_IMPL CvSeq*
359cvFindDominantPoints( 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