git.maemo.org Git - opencv/blob - ml/src/mlknearest.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 //
  12 // Copyright (C) 2000, Intel Corporation, all rights reserved.
  13 // Third party copyrights are property of their respective owners.
  14 //
  15 // Redistribution and use in source and binary forms, with or without modification,
  16 // are permitted provided that the following conditions are met:
  17 //
  18 //   * Redistribution's of source code must retain the above copyright notice,
  19 //     this list of conditions and the following disclaimer.
  20 //
  21 //   * Redistribution's in binary form must reproduce the above copyright notice,
  22 //     this list of conditions and the following disclaimer in the documentation
  23 //     and/or other materials provided with the distribution.
  24 //
  25 //   * The name of Intel Corporation may not be used to endorse or promote products
  26 //     derived from this software without specific prior written permission.
  27 //
  28 // This software is provided by the copyright holders and contributors "as is" and
  29 // any express or implied warranties, including, but not limited to, the implied
  30 // warranties of merchantability and fitness for a particular purpose are disclaimed.
  31 // In no event shall the Intel Corporation or contributors be liable for any direct,
  32 // indirect, incidental, special, exemplary, or consequential damages
  33 // (including, but not limited to, procurement of substitute goods or services;
  34 // loss of use, data, or profits; or business interruption) however caused
  35 // and on any theory of liability, whether in contract, strict liability,
  36 // or tort (including negligence or otherwise) arising in any way out of
  37 // the use of this software, even if advised of the possibility of such damage.
  38 //
  39 //M*/
  40
  41 #include "_ml.h"
  42
  43 /****************************************************************************************\
  44 *                          K-Nearest Neighbors Classifier                                *
  45 \****************************************************************************************/
  46
  47 // k Nearest Neighbors
  48 CvKNearest::CvKNearest()
  49 {
  50     samples = 0;
  51     clear();
  52 }
  53
  54
  55 CvKNearest::~CvKNearest()
  56 {
  57     clear();
  58 }
  59
  60
  61 CvKNearest::CvKNearest( const CvMat* _train_data, const CvMat* _responses,
  62                         const CvMat* _sample_idx, bool _is_regression, int _max_k )
  63 {
  64     samples = 0;
  65     train( _train_data, _responses, _sample_idx, _is_regression, _max_k, false );
  66 }
  67
  68
  69 void CvKNearest::clear()
  70 {
  71     while( samples )
  72     {
  73         CvVectors* next_samples = samples->next;
  74         cvFree( &samples->data.fl );
  75         cvFree( &samples );
  76         samples = next_samples;
  77     }
  78     var_count = 0;
  79     total = 0;
  80     max_k = 0;
  81 }
  82
  83
  84 int CvKNearest::get_max_k() const { return max_k; }
  85
  86 int CvKNearest::get_var_count() const { return var_count; }
  87
  88 bool CvKNearest::is_regression() const { return regression; }
  89
  90 int CvKNearest::get_sample_count() const { return total; }
  91
  92 bool CvKNearest::train( const CvMat* _train_data, const CvMat* _responses,
  93                         const CvMat* _sample_idx, bool _is_regression,
  94                         int _max_k, bool _update_base )
  95 {
  96     bool ok = false;
  97     CvMat* responses = 0;
  98
  99     CV_FUNCNAME( "CvKNearest::train" );
 100
 101     __BEGIN__;
 102
 103     CvVectors* _samples;
 104     float** _data;
 105     int _count, _dims, _dims_all, _rsize;
 106
 107     if( !_update_base )
 108         clear();
 109
 110     // Prepare training data and related parameters.
 111     // Treat categorical responses as ordered - to prevent class label compression and
 112     // to enable entering new classes in the updates
 113     CV_CALL( cvPrepareTrainData( "CvKNearest::train", _train_data, CV_ROW_SAMPLE,
 114         _responses, CV_VAR_ORDERED, 0, _sample_idx, true, (const float***)&_data,
 115         &_count, &_dims, &_dims_all, &responses, 0, 0 ));
 116
 117     if( _update_base && _dims != var_count )
 118         CV_ERROR( CV_StsBadArg, "The newly added data have different dimensionality" );
 119
 120     if( !_update_base )
 121     {
 122         if( _max_k < 1 )
 123             CV_ERROR( CV_StsOutOfRange, "max_k must be a positive number" );
 124
 125         regression = _is_regression;
 126         var_count = _dims;
 127         max_k = _max_k;
 128     }
 129
 130     _rsize = _count*sizeof(float);
 131     CV_CALL( _samples = (CvVectors*)cvAlloc( sizeof(*_samples) + _rsize ));
 132     _samples->next = samples;
 133     _samples->type = CV_32F;
 134     _samples->data.fl = _data;
 135     _samples->count = _count;
 136     total += _count;
 137
 138     samples = _samples;
 139     memcpy( _samples + 1, responses->data.fl, _rsize );
 140
 141     ok = true;
 142
 143     __END__;
 144
 145     return ok;
 146 }
 147
 148
 149
 150 void CvKNearest::find_neighbors_direct( const CvMat* _samples, int k, int start, int end,
 151                     float* neighbor_responses, const float** neighbors, float* dist ) const
 152 {
 153     int i, j, count = end - start, k1 = 0, k2 = 0, d = var_count;
 154     CvVectors* s = samples;
 155
 156     for( ; s != 0; s = s->next )
 157     {
 158         int n = s->count;
 159         for( j = 0; j < n; j++ )
 160         {
 161             for( i = 0; i < count; i++ )
 162             {
 163                 double sum = 0;
 164                 Cv32suf si;
 165                 const float* v = s->data.fl[j];
 166                 const float* u = (float*)(_samples->data.ptr + _samples->step*(start + i));
 167                 Cv32suf* dd = (Cv32suf*)(dist + i*k);
 168                 float* nr;
 169                 const float** nn;
 170                 int t, ii, ii1;
 171
 172                 for( t = 0; t <= d - 4; t += 4 )
 173                 {
 174                     double t0 = u[t] - v[t], t1 = u[t+1] - v[t+1];
 175                     double t2 = u[t+2] - v[t+2], t3 = u[t+3] - v[t+3];
 176                     sum += t0*t0 + t1*t1 + t2*t2 + t3*t3;
 177                 }
 178
 179                 for( ; t < d; t++ )
 180                 {
 181                     double t0 = u[t] - v[t];
 182                     sum += t0*t0;
 183                 }
 184
 185                 si.f = (float)sum;
 186                 for( ii = k1-1; ii >= 0; ii-- )
 187                     if( si.i > dd[ii].i )
 188                         break;
 189                 if( ii >= k-1 )
 190                     continue;
 191
 192                 nr = neighbor_responses + i*k;
 193                 nn = neighbors ? neighbors + (start + i)*k : 0;
 194                 for( ii1 = k2 - 1; ii1 > ii; ii1-- )
 195                 {
 196                     dd[ii1+1].i = dd[ii1].i;
 197                     nr[ii1+1] = nr[ii1];
 198                     if( nn ) nn[ii1+1] = nn[ii1];
 199                 }
 200                 dd[ii+1].i = si.i;
 201                 nr[ii+1] = ((float*)(s + 1))[j];
 202                 if( nn )
 203                     nn[ii+1] = v;
 204             }
 205             k1 = MIN( k1+1, k );
 206             k2 = MIN( k1, k-1 );
 207         }
 208     }
 209 }
 210
 211
 212 float CvKNearest::write_results( int k, int k1, int start, int end,
 213     const float* neighbor_responses, const float* dist,
 214     CvMat* _results, CvMat* _neighbor_responses,
 215     CvMat* _dist, Cv32suf* sort_buf ) const
 216 {
 217     float result = 0.f;
 218     int i, j, j1, count = end - start;
 219     double inv_scale = 1./k1;
 220     int rstep = _results && !CV_IS_MAT_CONT(_results->type) ? _results->step/sizeof(result) : 1;
 221
 222     for( i = 0; i < count; i++ )
 223     {
 224         const Cv32suf* nr = (const Cv32suf*)(neighbor_responses + i*k);
 225         float* dst;
 226         float r;
 227         if( _results || start+i == 0 )
 228         {
 229             if( regression )
 230             {
 231                 double s = 0;
 232                 for( j = 0; j < k1; j++ )
 233                     s += nr[j].f;
 234                 r = (float)(s*inv_scale);
 235             }
 236             else
 237             {
 238                 int prev_start = 0, best_count = 0, cur_count;
 239                 Cv32suf best_val;
 240
 241                 for( j = 0; j < k1; j++ )
 242                     sort_buf[j].i = nr[j].i;
 243
 244                 for( j = k1-1; j > 0; j-- )
 245                 {
 246                     bool swap_fl = false;
 247                     for( j1 = 0; j1 < j; j1++ )
 248                         if( sort_buf[j1].i > sort_buf[j1+1].i )
 249                         {
 250                             int t;
 251                             CV_SWAP( sort_buf[j1].i, sort_buf[j1+1].i, t );
 252                             swap_fl = true;
 253                         }
 254                     if( !swap_fl )
 255                         break;
 256                 }
 257
 258                 best_val.i = 0;
 259                 for( j = 1; j <= k1; j++ )
 260                     if( j == k1 || sort_buf[j].i != sort_buf[j-1].i )
 261                     {
 262                         cur_count = j - prev_start;
 263                         if( best_count < cur_count )
 264                         {
 265                             best_count = cur_count;
 266                             best_val.i = sort_buf[j-1].i;
 267                         }
 268                         prev_start = j;
 269                     }
 270                 r = best_val.f;
 271             }
 272
 273             if( start+i == 0 )
 274                 result = r;
 275
 276             if( _results )
 277                 _results->data.fl[(start + i)*rstep] = r;
 278         }
 279
 280         if( _neighbor_responses )
 281         {
 282             dst = (float*)(_neighbor_responses->data.ptr +
 283                 (start + i)*_neighbor_responses->step);
 284             for( j = 0; j < k1; j++ )
 285                 dst[j] = nr[j].f;
 286             for( ; j < k; j++ )
 287                 dst[j] = 0.f;
 288         }
 289
 290         if( _dist )
 291         {
 292             dst = (float*)(_dist->data.ptr + (start + i)*_dist->step);
 293             for( j = 0; j < k1; j++ )
 294                 dst[j] = dist[j + i*k];
 295             for( ; j < k; j++ )
 296                 dst[j] = 0.f;
 297         }
 298     }
 299
 300     return result;
 301 }
 302
 303
 304
 305 float CvKNearest::find_nearest( const CvMat* _samples, int k, CvMat* _results,
 306     const float** _neighbors, CvMat* _neighbor_responses, CvMat* _dist ) const
 307 {
 308     float result = 0.f;
 309     bool local_alloc = false;
 310     float* buf = 0;
 311     const int max_blk_count = 128, max_buf_sz = 1 << 12;
 312
 313     CV_FUNCNAME( "CvKNearest::find_nearest" );
 314
 315     __BEGIN__;
 316
 317     int i, count, count_scale, blk_count0, blk_count = 0, buf_sz, k1;
 318
 319     if( !samples )
 320         CV_ERROR( CV_StsError, "The search tree must be constructed first using train method" );
 321
 322     if( !CV_IS_MAT(_samples) ||
 323         CV_MAT_TYPE(_samples->type) != CV_32FC1 ||
 324         _samples->cols != var_count )
 325         CV_ERROR( CV_StsBadArg, "Input samples must be floating-point matrix (<num_samples>x<var_count>)" );
 326
 327     if( _results && (!CV_IS_MAT(_results) ||
 328         _results->cols != 1 && _results->rows != 1 ||
 329         _results->cols + _results->rows - 1 != _samples->rows) )
 330         CV_ERROR( CV_StsBadArg,
 331         "The results must be 1d vector containing as much elements as the number of samples" );
 332
 333     if( _results && CV_MAT_TYPE(_results->type) != CV_32FC1 &&
 334         (CV_MAT_TYPE(_results->type) != CV_32SC1 || regression))
 335         CV_ERROR( CV_StsUnsupportedFormat,
 336         "The results must be floating-point or integer (in case of classification) vector" );
 337
 338     if( k < 1 || k > max_k )
 339         CV_ERROR( CV_StsOutOfRange, "k must be within 1..max_k range" );
 340
 341     if( _neighbor_responses )
 342     {
 343         if( !CV_IS_MAT(_neighbor_responses) || CV_MAT_TYPE(_neighbor_responses->type) != CV_32FC1 ||
 344             _neighbor_responses->rows != _samples->rows || _neighbor_responses->cols != k )
 345             CV_ERROR( CV_StsBadArg,
 346             "The neighbor responses (if present) must be floating-point matrix of <num_samples> x <k> size" );
 347     }
 348
 349     if( _dist )
 350     {
 351         if( !CV_IS_MAT(_dist) || CV_MAT_TYPE(_dist->type) != CV_32FC1 ||
 352             _dist->rows != _samples->rows || _dist->cols != k )
 353             CV_ERROR( CV_StsBadArg,
 354             "The distances from the neighbors (if present) must be floating-point matrix of <num_samples> x <k> size" );
 355     }
 356
 357     count = _samples->rows;
 358     count_scale = k*2*sizeof(float);
 359     blk_count0 = MIN( count, max_blk_count );
 360     buf_sz = MIN( blk_count0 * count_scale, max_buf_sz );
 361     blk_count0 = MAX( buf_sz/count_scale, 1 );
 362     blk_count0 += blk_count0 % 2;
 363     blk_count0 = MIN( blk_count0, count );
 364     buf_sz = blk_count0 * count_scale + k*sizeof(float);
 365     k1 = get_sample_count();
 366     k1 = MIN( k1, k );
 367
 368     if( buf_sz <= CV_MAX_LOCAL_SIZE )
 369     {
 370         buf = (float*)cvStackAlloc( buf_sz );
 371         local_alloc = true;
 372     }
 373     else
 374         CV_CALL( buf = (float*)cvAlloc( buf_sz ));
 375
 376     for( i = 0; i < count; i += blk_count )
 377     {
 378         blk_count = MIN( count - i, blk_count0 );
 379         float* neighbor_responses = buf;
 380         float* dist = buf + blk_count*k;
 381         Cv32suf* sort_buf = (Cv32suf*)(dist + blk_count*k);
 382
 383         find_neighbors_direct( _samples, k, i, i + blk_count,
 384                     neighbor_responses, _neighbors, dist );
 385
 386         float r = write_results( k, k1, i, i + blk_count, neighbor_responses, dist,
 387                                  _results, _neighbor_responses, _dist, sort_buf );
 388         if( i == 0 )
 389             result = r;
 390     }
 391
 392     __END__;
 393
 394     if( !local_alloc )
 395         cvFree( &buf );
 396
 397     return result;
 398 }
 399
 400 /* End of file */
 401