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
icvFindDominantPointsIPAN(CvSeq * contour,CvMemStorage * storage,CvSeq ** corners,int dmin2,int dmax2,int dneigh2,float amax)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*
cvFindDominantPoints(CvSeq * contour,CvMemStorage * storage,int method,double parameter1,double parameter2,double parameter3,double parameter4)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