1 /*M///////////////////////////////////////////////////////////////////////////////////////
3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
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.
10 // Intel License Agreement
11 // For Open Source Computer Vision Library
13 // Copyright (C) 2000, Intel Corporation, all rights reserved.
14 // Third party copyrights are property of their respective owners.
16 // Redistribution and use in source and binary forms, with or without modification,
17 // are permitted provided that the following conditions are met:
19 // * Redistribution's of source code must retain the above copyright notice,
20 // this list of conditions and the following disclaimer.
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.
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.
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.
43 #define _CV_ACOS_TABLE_SIZE 513
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
135 /*F///////////////////////////////////////////////////////////////////////////////////////
138 // Calculates PGH(pairwise geometric histogram) for contour given.
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)
146 // CV_OK or error code
150 icvCalcPGH( const CvSeq * contour, float *pgh, int angle_dim, int dist_dim )
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;
159 int *pghi = (int *) pgh;
160 int hist_size = angle_dim * dist_dim;
161 CvSeqReader reader1, reader2; /* external and internal readers */
163 if( !contour || !pgh )
164 return CV_NULLPTR_ERR;
166 if( angle_dim <= 0 || angle_dim > 180 || dist_dim <= 0 )
167 return CV_BADRANGE_ERR;
169 if( !CV_IS_SEQ_POLYGON( contour ))
170 return CV_BADFLAG_ERR;
172 memset( pgh, 0, hist_size * sizeof( pgh[0] ));
174 count = contour->total;
176 /* allocate buffer for distances */
177 buffer_size = count * sizeof( float );
179 if( buffer_size > (int)sizeof(local_buffer) - 32 )
181 buffer = (float *) cvAlloc( buffer_size );
183 return CV_OUTOFMEM_ERR;
186 cvStartReadSeq( contour, &reader1, 0 );
187 cvStartReadSeq( contour, &reader2, 0 );
189 /* calc & store squared edge lengths, calculate maximal distance between edges */
190 for( i = 0; i < count; i++ )
195 CV_READ_EDGE( pt1, pt2, reader1 );
199 buffer[i] = (float)(1./sqrt(dx * dx + dy * dy));
204 First calculates maximal distance.
205 Second calculates histogram itself.
207 for( pass = 1; pass <= 2; pass++ )
209 double dist_coeff = 0, angle_coeff = 0;
211 /* run external loop */
212 for( i = 0; i < count; i++ )
218 CV_READ_EDGE( pt1, pt2, reader1 );
229 dist_coeff = buffer[i] * dist_scale;
230 angle_coeff = buffer[i] * (_CV_ACOS_TABLE_SIZE / 2);
233 /* run internal loop (for current edge) */
234 for( j = 0; j < count; j++ )
238 CV_READ_EDGE( pt3, pt4, reader2 );
240 if( i != j ) /* process edge pair */
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;
249 int dp = (pt4.x - pt3.x) * dx + (pt4.y - pt3.y) * dy;
251 dp = cvRound( dp * angle_coeff * buffer[j] ) +
252 (_CV_ACOS_TABLE_SIZE / 2);
254 dp = MIN( dp, _CV_ACOS_TABLE_SIZE - 1 );
255 hist_row = pghi + dist_dim *
256 cvRound( icv_acos_table[dp] * angle_scale );
258 d1 = cvRound( d1 * dist_coeff );
259 d2 = cvRound( d2 * dist_coeff );
262 cross_flag = (d1 ^ d2) < 0;
276 if( d1 > d2 ) /* make d1 <= d2 */
283 for( ; d1 <= d2; d1++ )
288 for( ; d1 >= 0; d1-- )
290 for( ; d2 >= 0; d2-- )
296 d1 = CV_IMAX( d1, d2 );
297 dist = CV_IMAX( dist, d1 );
299 } /* end of processing of edge pair */
301 } /* end of internal loop */
305 double scale = dist * buffer[i];
307 dist_scale = MAX( dist_scale, scale );
310 } /* end of external loop */
314 dist_scale = (dist_dim - 0.51) / dist_scale;
317 } /* end of pass on loops */
320 /* convert hist to floats */
321 for( i = 0; i < hist_size; i++ )
323 ((float *) pghi)[i] = (float) pghi[i];
326 if( buffer != local_buffer_ptr )
334 cvCalcPGH( const CvSeq * contour, CvHistogram * hist )
336 CV_FUNCNAME( "cvCalcPGH" );
340 int size[CV_MAX_DIM];
343 if( !CV_IS_HIST(hist))
344 CV_ERROR( CV_StsBadArg, "The histogram header is invalid " );
346 if( CV_IS_SPARSE_HIST( hist ))
347 CV_ERROR( CV_StsUnsupportedFormat, "Sparse histogram are not supported" );
349 dims = cvGetDims( hist->bins, size );
352 CV_ERROR( CV_StsBadSize, "The histogram must be two-dimensional" );
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" );
357 IPPI_CALL( icvCalcPGH( contour, ((CvMatND*)(hist->bins))->data.fl, size[0], size[1] ));