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 #define _CV_ACOS_TABLE_SIZE 513
44
45 static const float icv_acos_table[_CV_ACOS_TABLE_SIZE] = {
46 3.14159265f, 3.05317551f, 3.01651113f, 2.98834964f, 2.96458497f, 2.94362719f,
47 2.92466119f, 2.90720289f, 2.89093699f, 2.87564455f, 2.86116621f, 2.84738169f,
48 2.83419760f, 2.82153967f, 2.80934770f, 2.79757211f, 2.78617145f, 2.77511069f,
49 2.76435988f, 2.75389319f, 2.74368816f, 2.73372510f, 2.72398665f, 2.71445741f,
50 2.70512362f, 2.69597298f, 2.68699438f, 2.67817778f, 2.66951407f, 2.66099493f,
51 2.65261279f, 2.64436066f, 2.63623214f, 2.62822133f, 2.62032277f, 2.61253138f,
52 2.60484248f, 2.59725167f, 2.58975488f, 2.58234828f, 2.57502832f, 2.56779164f,
53 2.56063509f, 2.55355572f, 2.54655073f, 2.53961750f, 2.53275354f, 2.52595650f,
54 2.51922417f, 2.51255441f, 2.50594525f, 2.49939476f, 2.49290115f, 2.48646269f,
55 2.48007773f, 2.47374472f, 2.46746215f, 2.46122860f, 2.45504269f, 2.44890314f,
56 2.44280867f, 2.43675809f, 2.43075025f, 2.42478404f, 2.41885841f, 2.41297232f,
57 2.40712480f, 2.40131491f, 2.39554173f, 2.38980439f, 2.38410204f, 2.37843388f,
58 2.37279910f, 2.36719697f, 2.36162673f, 2.35608768f, 2.35057914f, 2.34510044f,
59 2.33965094f, 2.33423003f, 2.32883709f, 2.32347155f, 2.31813284f, 2.31282041f,
60 2.30753373f, 2.30227228f, 2.29703556f, 2.29182309f, 2.28663439f, 2.28146900f,
61 2.27632647f, 2.27120637f, 2.26610827f, 2.26103177f, 2.25597646f, 2.25094195f,
62 2.24592786f, 2.24093382f, 2.23595946f, 2.23100444f, 2.22606842f, 2.22115104f,
63 2.21625199f, 2.21137096f, 2.20650761f, 2.20166166f, 2.19683280f, 2.19202074f,
64 2.18722520f, 2.18244590f, 2.17768257f, 2.17293493f, 2.16820274f, 2.16348574f,
65 2.15878367f, 2.15409630f, 2.14942338f, 2.14476468f, 2.14011997f, 2.13548903f,
66 2.13087163f, 2.12626757f, 2.12167662f, 2.11709859f, 2.11253326f, 2.10798044f,
67 2.10343994f, 2.09891156f, 2.09439510f, 2.08989040f, 2.08539725f, 2.08091550f,
68 2.07644495f, 2.07198545f, 2.06753681f, 2.06309887f, 2.05867147f, 2.05425445f,
69 2.04984765f, 2.04545092f, 2.04106409f, 2.03668703f, 2.03231957f, 2.02796159f,
70 2.02361292f, 2.01927344f, 2.01494300f, 2.01062146f, 2.00630870f, 2.00200457f,
71 1.99770895f, 1.99342171f, 1.98914271f, 1.98487185f, 1.98060898f, 1.97635399f,
72 1.97210676f, 1.96786718f, 1.96363511f, 1.95941046f, 1.95519310f, 1.95098292f,
73 1.94677982f, 1.94258368f, 1.93839439f, 1.93421185f, 1.93003595f, 1.92586659f,
74 1.92170367f, 1.91754708f, 1.91339673f, 1.90925250f, 1.90511432f, 1.90098208f,
75 1.89685568f, 1.89273503f, 1.88862003f, 1.88451060f, 1.88040664f, 1.87630806f,
76 1.87221477f, 1.86812668f, 1.86404371f, 1.85996577f, 1.85589277f, 1.85182462f,
77 1.84776125f, 1.84370256f, 1.83964848f, 1.83559892f, 1.83155381f, 1.82751305f,
78 1.82347658f, 1.81944431f, 1.81541617f, 1.81139207f, 1.80737194f, 1.80335570f,
79 1.79934328f, 1.79533460f, 1.79132959f, 1.78732817f, 1.78333027f, 1.77933581f,
80 1.77534473f, 1.77135695f, 1.76737240f, 1.76339101f, 1.75941271f, 1.75543743f,
81 1.75146510f, 1.74749565f, 1.74352900f, 1.73956511f, 1.73560389f, 1.73164527f,
82 1.72768920f, 1.72373560f, 1.71978441f, 1.71583556f, 1.71188899f, 1.70794462f,
83 1.70400241f, 1.70006228f, 1.69612416f, 1.69218799f, 1.68825372f, 1.68432127f,
84 1.68039058f, 1.67646160f, 1.67253424f, 1.66860847f, 1.66468420f, 1.66076139f,
85 1.65683996f, 1.65291986f, 1.64900102f, 1.64508338f, 1.64116689f, 1.63725148f,
86 1.63333709f, 1.62942366f, 1.62551112f, 1.62159943f, 1.61768851f, 1.61377831f,
87 1.60986877f, 1.60595982f, 1.60205142f, 1.59814349f, 1.59423597f, 1.59032882f,
88 1.58642196f, 1.58251535f, 1.57860891f, 1.57470259f, 1.57079633f, 1.56689007f,
89 1.56298375f, 1.55907731f, 1.55517069f, 1.55126383f, 1.54735668f, 1.54344917f,
90 1.53954124f, 1.53563283f, 1.53172389f, 1.52781434f, 1.52390414f, 1.51999323f,
91 1.51608153f, 1.51216900f, 1.50825556f, 1.50434117f, 1.50042576f, 1.49650927f,
92 1.49259163f, 1.48867280f, 1.48475270f, 1.48083127f, 1.47690845f, 1.47298419f,
93 1.46905841f, 1.46513106f, 1.46120207f, 1.45727138f, 1.45333893f, 1.44940466f,
94 1.44546850f, 1.44153038f, 1.43759024f, 1.43364803f, 1.42970367f, 1.42575709f,
95 1.42180825f, 1.41785705f, 1.41390346f, 1.40994738f, 1.40598877f, 1.40202755f,
96 1.39806365f, 1.39409701f, 1.39012756f, 1.38615522f, 1.38217994f, 1.37820164f,
97 1.37422025f, 1.37023570f, 1.36624792f, 1.36225684f, 1.35826239f, 1.35426449f,
98 1.35026307f, 1.34625805f, 1.34224937f, 1.33823695f, 1.33422072f, 1.33020059f,
99 1.32617649f, 1.32214834f, 1.31811607f, 1.31407960f, 1.31003885f, 1.30599373f,
100 1.30194417f, 1.29789009f, 1.29383141f, 1.28976803f, 1.28569989f, 1.28162688f,
101 1.27754894f, 1.27346597f, 1.26937788f, 1.26528459f, 1.26118602f, 1.25708205f,
102 1.25297262f, 1.24885763f, 1.24473698f, 1.24061058f, 1.23647833f, 1.23234015f,
103 1.22819593f, 1.22404557f, 1.21988898f, 1.21572606f, 1.21155670f, 1.20738080f,
104 1.20319826f, 1.19900898f, 1.19481283f, 1.19060973f, 1.18639955f, 1.18218219f,
105 1.17795754f, 1.17372548f, 1.16948589f, 1.16523866f, 1.16098368f, 1.15672081f,
106 1.15244994f, 1.14817095f, 1.14388370f, 1.13958808f, 1.13528396f, 1.13097119f,
107 1.12664966f, 1.12231921f, 1.11797973f, 1.11363107f, 1.10927308f, 1.10490563f,
108 1.10052856f, 1.09614174f, 1.09174500f, 1.08733820f, 1.08292118f, 1.07849378f,
109 1.07405585f, 1.06960721f, 1.06514770f, 1.06067715f, 1.05619540f, 1.05170226f,
110 1.04719755f, 1.04268110f, 1.03815271f, 1.03361221f, 1.02905939f, 1.02449407f,
111 1.01991603f, 1.01532509f, 1.01072102f, 1.00610363f, 1.00147268f, 0.99682798f,
112 0.99216928f, 0.98749636f, 0.98280898f, 0.97810691f, 0.97338991f, 0.96865772f,
113 0.96391009f, 0.95914675f, 0.95436745f, 0.94957191f, 0.94475985f, 0.93993099f,
114 0.93508504f, 0.93022170f, 0.92534066f, 0.92044161f, 0.91552424f, 0.91058821f,
115 0.90563319f, 0.90065884f, 0.89566479f, 0.89065070f, 0.88561619f, 0.88056088f,
116 0.87548438f, 0.87038629f, 0.86526619f, 0.86012366f, 0.85495827f, 0.84976956f,
117 0.84455709f, 0.83932037f, 0.83405893f, 0.82877225f, 0.82345981f, 0.81812110f,
118 0.81275556f, 0.80736262f, 0.80194171f, 0.79649221f, 0.79101352f, 0.78550497f,
119 0.77996593f, 0.77439569f, 0.76879355f, 0.76315878f, 0.75749061f, 0.75178826f,
120 0.74605092f, 0.74027775f, 0.73446785f, 0.72862033f, 0.72273425f, 0.71680861f,
121 0.71084240f, 0.70483456f, 0.69878398f, 0.69268952f, 0.68654996f, 0.68036406f,
122 0.67413051f, 0.66784794f, 0.66151492f, 0.65512997f, 0.64869151f, 0.64219789f,
123 0.63564741f, 0.62903824f, 0.62236849f, 0.61563615f, 0.60883911f, 0.60197515f,
124 0.59504192f, 0.58803694f, 0.58095756f, 0.57380101f, 0.56656433f, 0.55924437f,
125 0.55183778f, 0.54434099f, 0.53675018f, 0.52906127f, 0.52126988f, 0.51337132f,
126 0.50536051f, 0.49723200f, 0.48897987f, 0.48059772f, 0.47207859f, 0.46341487f,
127 0.45459827f, 0.44561967f, 0.43646903f, 0.42713525f, 0.41760600f, 0.40786755f,
128 0.39790449f, 0.38769946f, 0.37723277f, 0.36648196f, 0.35542120f, 0.34402054f,
129 0.33224495f, 0.32005298f, 0.30739505f, 0.29421096f, 0.28042645f, 0.26594810f,
130 0.25065566f, 0.23438976f, 0.21693146f, 0.19796546f, 0.17700769f, 0.15324301f,
131 0.12508152f, 0.08841715f, 0.00000000f
132 };
133
134
135 /*F///////////////////////////////////////////////////////////////////////////////////////
136 // Name: icvCalcPGH
137 // Purpose:
138 // Calculates PGH(pairwise geometric histogram) for contour given.
139 // Context:
140 // Parameters:
141 // contour - pointer to input contour object.
142 // pgh - output histogram
143 // ang_dim - number of angle bins (vertical size of histogram)
144 // dist_dim - number of distance bins (horizontal size of histogram)
145 // Returns:
146 // CV_OK or error code
147 // Notes:
148 //F*/
149 static CvStatus
icvCalcPGH(const CvSeq * contour,float * pgh,int angle_dim,int dist_dim)150 icvCalcPGH( const CvSeq * contour, float *pgh, int angle_dim, int dist_dim )
151 {
152 char local_buffer[(1 << 14) + 32];
153 float *local_buffer_ptr = (float *)cvAlignPtr(local_buffer,32);
154 float *buffer = local_buffer_ptr;
155 double angle_scale = (angle_dim - 0.51) / icv_acos_table[0];
156 double dist_scale = DBL_EPSILON;
157 int buffer_size;
158 int i, count, pass;
159 int *pghi = (int *) pgh;
160 int hist_size = angle_dim * dist_dim;
161 CvSeqReader reader1, reader2; /* external and internal readers */
162
163 if( !contour || !pgh )
164 return CV_NULLPTR_ERR;
165
166 if( angle_dim <= 0 || angle_dim > 180 || dist_dim <= 0 )
167 return CV_BADRANGE_ERR;
168
169 if( !CV_IS_SEQ_POLYGON( contour ))
170 return CV_BADFLAG_ERR;
171
172 memset( pgh, 0, hist_size * sizeof( pgh[0] ));
173
174 count = contour->total;
175
176 /* allocate buffer for distances */
177 buffer_size = count * sizeof( float );
178
179 if( buffer_size > (int)sizeof(local_buffer) - 32 )
180 {
181 buffer = (float *) cvAlloc( buffer_size );
182 if( !buffer )
183 return CV_OUTOFMEM_ERR;
184 }
185
186 cvStartReadSeq( contour, &reader1, 0 );
187 cvStartReadSeq( contour, &reader2, 0 );
188
189 /* calc & store squared edge lengths, calculate maximal distance between edges */
190 for( i = 0; i < count; i++ )
191 {
192 CvPoint pt1, pt2;
193 double dx, dy;
194
195 CV_READ_EDGE( pt1, pt2, reader1 );
196
197 dx = pt2.x - pt1.x;
198 dy = pt2.y - pt1.y;
199 buffer[i] = (float)(1./sqrt(dx * dx + dy * dy));
200 }
201
202 /*
203 do 2 passes.
204 First calculates maximal distance.
205 Second calculates histogram itself.
206 */
207 for( pass = 1; pass <= 2; pass++ )
208 {
209 double dist_coeff = 0, angle_coeff = 0;
210
211 /* run external loop */
212 for( i = 0; i < count; i++ )
213 {
214 CvPoint pt1, pt2;
215 int dx, dy;
216 int dist = 0;
217
218 CV_READ_EDGE( pt1, pt2, reader1 );
219
220 dx = pt2.x - pt1.x;
221 dy = pt2.y - pt1.y;
222
223 if( (dx | dy) != 0 )
224 {
225 int j;
226
227 if( pass == 2 )
228 {
229 dist_coeff = buffer[i] * dist_scale;
230 angle_coeff = buffer[i] * (_CV_ACOS_TABLE_SIZE / 2);
231 }
232
233 /* run internal loop (for current edge) */
234 for( j = 0; j < count; j++ )
235 {
236 CvPoint pt3, pt4;
237
238 CV_READ_EDGE( pt3, pt4, reader2 );
239
240 if( i != j ) /* process edge pair */
241 {
242 int d1 = (pt3.y - pt1.y) * dx - (pt3.x - pt1.x) * dy;
243 int d2 = (pt4.y - pt1.y) * dx - (pt2.x - pt1.x) * dy;
244 int cross_flag;
245 int *hist_row = 0;
246
247 if( pass == 2 )
248 {
249 int dp = (pt4.x - pt3.x) * dx + (pt4.y - pt3.y) * dy;
250
251 dp = cvRound( dp * angle_coeff * buffer[j] ) +
252 (_CV_ACOS_TABLE_SIZE / 2);
253 dp = MAX( dp, 0 );
254 dp = MIN( dp, _CV_ACOS_TABLE_SIZE - 1 );
255 hist_row = pghi + dist_dim *
256 cvRound( icv_acos_table[dp] * angle_scale );
257
258 d1 = cvRound( d1 * dist_coeff );
259 d2 = cvRound( d2 * dist_coeff );
260 }
261
262 cross_flag = (d1 ^ d2) < 0;
263
264 d1 = CV_IABS( d1 );
265 d2 = CV_IABS( d2 );
266
267 if( pass == 2 )
268 {
269 if( d1 >= dist_dim )
270 d1 = dist_dim - 1;
271 if( d2 >= dist_dim )
272 d2 = dist_dim - 1;
273
274 if( !cross_flag )
275 {
276 if( d1 > d2 ) /* make d1 <= d2 */
277 {
278 d1 ^= d2;
279 d2 ^= d1;
280 d1 ^= d2;
281 }
282
283 for( ; d1 <= d2; d1++ )
284 hist_row[d1]++;
285 }
286 else
287 {
288 for( ; d1 >= 0; d1-- )
289 hist_row[d1]++;
290 for( ; d2 >= 0; d2-- )
291 hist_row[d2]++;
292 }
293 }
294 else /* 1st pass */
295 {
296 d1 = CV_IMAX( d1, d2 );
297 dist = CV_IMAX( dist, d1 );
298 }
299 } /* end of processing of edge pair */
300
301 } /* end of internal loop */
302
303 if( pass == 1 )
304 {
305 double scale = dist * buffer[i];
306
307 dist_scale = MAX( dist_scale, scale );
308 }
309 }
310 } /* end of external loop */
311
312 if( pass == 1 )
313 {
314 dist_scale = (dist_dim - 0.51) / dist_scale;
315 }
316
317 } /* end of pass on loops */
318
319
320 /* convert hist to floats */
321 for( i = 0; i < hist_size; i++ )
322 {
323 ((float *) pghi)[i] = (float) pghi[i];
324 }
325
326 if( buffer != local_buffer_ptr )
327 cvFree( &buffer );
328
329 return CV_OK;
330 }
331
332
333 CV_IMPL void
cvCalcPGH(const CvSeq * contour,CvHistogram * hist)334 cvCalcPGH( const CvSeq * contour, CvHistogram * hist )
335 {
336 CV_FUNCNAME( "cvCalcPGH" );
337
338 __BEGIN__;
339
340 int size[CV_MAX_DIM];
341 int dims;
342
343 if( !CV_IS_HIST(hist))
344 CV_ERROR( CV_StsBadArg, "The histogram header is invalid " );
345
346 if( CV_IS_SPARSE_HIST( hist ))
347 CV_ERROR( CV_StsUnsupportedFormat, "Sparse histogram are not supported" );
348
349 dims = cvGetDims( hist->bins, size );
350
351 if( dims != 2 )
352 CV_ERROR( CV_StsBadSize, "The histogram must be two-dimensional" );
353
354 if( !CV_IS_SEQ_POLYGON( contour ) || CV_SEQ_ELTYPE( contour ) != CV_32SC2 )
355 CV_ERROR( CV_StsUnsupportedFormat, "The contour is not valid or the point type is not supported" );
356
357 IPPI_CALL( icvCalcPGH( contour, ((CvMatND*)(hist->bins))->data.fl, size[0], size[1] ));
358
359 __END__;
360 }
361
362
363 /* End of file. */
364