vcs.maemo.org Git - opencv/blob - tests/cv/src/akmeans.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
  42 #include "cvtest.h"
  43
  44 #if 0
  45
  46 /* Testing parameters */
  47 static char test_desc[] = "KMeans clustering";
  48 static char* func_name[] =
  49 {
  50     "cvKMeans"
  51 };
  52
  53 //based on Ara Nefian's implementation
  54 float distance(float* vector_1, float *vector_2, int VecSize)
  55 {
  56   int i;
  57   float dist;
  58
  59   dist = 0.0;
  60   for (i = 0; i < VecSize; i++)
  61   {
  62       //printf ("%f, %f\n", vector_1[i], vector_2[i]);
  63       dist = dist + (vector_1[i] - vector_2[i])*(vector_1[i] - vector_2[i]);
  64   }
  65   return dist;
  66 }
  67
  68 //returns number of made iterations
  69 int _real_kmeans( int numClusters, float **sample, int numSamples,
  70                    int VecSize, int* a_class, double eps, int iter )
  71
  72 {
  73   int     i, k, n;
  74   int     *counter;
  75   float   minDist;
  76   float   *dist;
  77   float   **curr_cluster;
  78   float   **prev_cluster;
  79
  80   float   error;
  81
  82   //printf("* numSamples = %d, numClusters = %d, VecSize = %d\n", numSamples, numClusters, VecSize);
  83
  84   //memory allocation
  85   dist = new float[numClusters];
  86   counter = new int[numClusters];
  87
  88   //allocate memory for curr_cluster and prev_cluster
  89   curr_cluster = new float*[numClusters];
  90   prev_cluster = new float*[numClusters];
  91   for (k = 0; k < numClusters; k++){
  92       curr_cluster[k] = new float[VecSize];
  93       prev_cluster[k] = new float[VecSize];
  94   }
  95
  96   //pick initial cluster centers
  97   for (k = 0; k < numClusters; k++)
  98   {
  99     for (n = 0; n < VecSize; n++)
 100     {
 101        curr_cluster[k][n] = sample[k*(numSamples/numClusters)][n];
 102        prev_cluster[k][n] = sample[k*(numSamples/numClusters)][n];
 103     }
 104   }
 105
 106
 107   int NumIter = 0;
 108   error = FLT_MAX;
 109   while ((error > eps) && (NumIter < iter))
 110   {
 111     NumIter++;
 112     //printf("NumIter = %d, error = %lf, \n", NumIter, error);
 113
 114     //assign samples to clusters
 115     for (i = 0; i < numSamples; i++)
 116     {
 117       for (k = 0; k < numClusters; k++)
 118       {
 119           dist[k] = distance(sample[i], curr_cluster[k], VecSize);
 120       }
 121       minDist = dist[0];
 122       a_class[i] = 0;
 123       for (k = 1; k < numClusters; k++)
 124       {
 125         if (dist[k] < minDist)
 126         {
 127            minDist = dist[k];
 128            a_class[i] = k;
 129         }
 130       }
 131     }
 132
 133    //reset clusters and counters
 134    for (k = 0; k < numClusters; k++){
 135      counter[k] = 0;
 136      for (n = 0; n < VecSize; n++){
 137         curr_cluster[k][n] = 0.0;
 138      }
 139    }
 140     for (i = 0; i < numSamples; i++){
 141       for (n = 0; n < VecSize; n++){
 142           curr_cluster[a_class[i]][n] = curr_cluster[a_class[i]][n] + sample[i][n];
 143       }
 144       counter[a_class[i]]++;
 145     }
 146
 147    for (k = 0; k < numClusters; k++){
 148       for (n = 0; n < VecSize; n++){
 149          curr_cluster[k][n] = curr_cluster[k][n]/(float)counter[k];
 150       }
 151     }
 152
 153     error = 0.0;
 154     for (k = 0; k < numClusters; k++){
 155       for (n = 0; n < VecSize; n++){
 156         error = error + (curr_cluster[k][n] - prev_cluster[k][n])*(curr_cluster[k][n] - prev_cluster[k][n]);
 157       }
 158     }
 159     //error = error/(double)(numClusters*VecSize);
 160
 161     //copy curr_clusters to prev_clusters
 162     for (k = 0; k < numClusters; k++){
 163       for (n =0; n < VecSize; n++){
 164         prev_cluster[k][n] = curr_cluster[k][n];
 165       }
 166     }
 167
 168   }
 169
 170   //deallocate memory for curr_cluster and prev_cluster
 171   for (k = 0; k < numClusters; k++){
 172       delete curr_cluster[k];
 173       delete prev_cluster[k];
 174   }
 175   delete curr_cluster;
 176   delete prev_cluster;
 177
 178   delete counter;
 179   delete dist;
 180   return NumIter;
 181
 182 }
 183
 184 static int fmaKMeans(void)
 185 {
 186     CvTermCriteria crit;
 187     float** vectors;
 188     int*    output;
 189     int*    etalon_output;
 190
 191     int lErrors = 0;
 192     int lNumVect = 0;
 193     int lVectSize = 0;
 194     int lNumClust = 0;
 195     int lMaxNumIter = 0;
 196     float flEpsilon = 0;
 197
 198     int i,j;
 199     static int  read_param = 0;
 200
 201     /* Initialization global parameters */
 202     if( !read_param )
 203     {
 204         read_param = 1;
 205         /* Read test-parameters */
 206         trsiRead( &lNumVect, "1000", "Number of vectors" );
 207         trsiRead( &lVectSize, "10", "Number of vectors" );
 208         trsiRead( &lNumClust, "20", "Number of clusters" );
 209         trsiRead( &lMaxNumIter,"100","Maximal number of iterations");
 210         trssRead( &flEpsilon, "0.5", "Accuracy" );
 211     }
 212
 213     crit = cvTermCriteria( CV_TERMCRIT_EPS|CV_TERMCRIT_ITER, lMaxNumIter, flEpsilon );
 214
 215     //allocate vectors
 216     vectors = (float**)cvAlloc( lNumVect * sizeof(float*) );
 217     for( i = 0; i < lNumVect; i++ )
 218     {
 219         vectors[i] = (float*)cvAlloc( lVectSize * sizeof( float ) );
 220     }
 221
 222     output = (int*)cvAlloc( lNumVect * sizeof(int) );
 223     etalon_output = (int*)cvAlloc( lNumVect * sizeof(int) );
 224
 225     //fill input vectors
 226     for( i = 0; i < lNumVect; i++ )
 227     {
 228         ats1flInitRandom( -2000, 2000, vectors[i], lVectSize );
 229     }
 230
 231     /* run etalon kmeans */
 232     /* actually it is the simpliest realization of kmeans */
 233
 234     int ni = _real_kmeans( lNumClust, vectors, lNumVect, lVectSize, etalon_output, crit.epsilon, crit.max_iter );
 235
 236     trsWrite(  ATS_CON, "%d iterations done\n",  ni );
 237
 238     /* Run OpenCV function */
 239 #define _KMEANS_TIME 0
 240
 241 #if _KMEANS_TIME
 242     //timing section
 243     trsTimerStart(0);
 244     __int64 tics = atsGetTickCount();
 245 #endif
 246
 247     cvKMeans( lNumClust, vectors, lNumVect, lVectSize,
 248               crit, output );
 249
 250 #if _KMEANS_TIME
 251     tics = atsGetTickCount() - tics;
 252     trsTimerStop(0);
 253     //output result
 254     //double dbUsecs =ATS_TICS_TO_USECS((double)tics);
 255     trsWrite( ATS_CON, "Tics per iteration %d\n", tics/ni );
 256
 257 #endif
 258
 259     //compare results
 260     for( j = 0; j < lNumVect; j++ )
 261     {
 262         if ( output[j] != etalon_output[j] )
 263         {
 264             lErrors++;
 265         }
 266     }
 267
 268     //free memory
 269     for( i = 0; i < lNumVect; i++ )
 270     {
 271         cvFree( &(vectors[i]) );
 272     }
 273     cvFree(&vectors);
 274     cvFree(&output);
 275     cvFree(&etalon_output);
 276
 277    if( lErrors == 0 ) return trsResult( TRS_OK, "No errors fixed for this text" );
 278     else return trsResult( TRS_FAIL, "Detected %d errors", lErrors );
 279
 280 }
 281
 282
 283
 284 void InitAKMeans()
 285 {
 286     /* Register test function */
 287     trsReg( func_name[0], test_desc, atsAlgoClass, fmaKMeans );
 288
 289 } /* InitAKMeans */
 290
 291 #endif