X-Git-Url: https://vcs.maemo.org/git/?a=blobdiff_plain;f=ml%2Fsrc%2Fmlsvm.cpp;fp=ml%2Fsrc%2Fmlsvm.cpp;h=0000000000000000000000000000000000000000;hb=e4c14cdbdf2fe805e79cd96ded236f57e7b89060;hp=fc1794f0cbedd116171193a310e5bfc7306d43b5;hpb=454138ff8a20f6edb9b65a910101403d8b520643;p=opencv diff --git a/ml/src/mlsvm.cpp b/ml/src/mlsvm.cpp deleted file mode 100644 index fc1794f..0000000 --- a/ml/src/mlsvm.cpp +++ /dev/null @@ -1,2689 +0,0 @@ -/*M/////////////////////////////////////////////////////////////////////////////////////// -// -// IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. -// -// By downloading, copying, installing or using the software you agree to this license. -// If you do not agree to this license, do not download, install, -// copy or use the software. -// -// -// Intel License Agreement -// -// Copyright (C) 2000, Intel Corporation, all rights reserved. -// Third party copyrights are property of their respective owners. -// -// Redistribution and use in source and binary forms, with or without modification, -// are permitted provided that the following conditions are met: -// -// * Redistribution's of source code must retain the above copyright notice, -// this list of conditions and the following disclaimer. -// -// * Redistribution's in binary form must reproduce the above copyright notice, -// this list of conditions and the following disclaimer in the documentation -// and/or other materials provided with the distribution. -// -// * The name of Intel Corporation may not be used to endorse or promote products -// derived from this software without specific prior written permission. -// -// This software is provided by the copyright holders and contributors "as is" and -// any express or implied warranties, including, but not limited to, the implied -// warranties of merchantability and fitness for a particular purpose are disclaimed. -// In no event shall the Intel Corporation or contributors be liable for any direct, -// indirect, incidental, special, exemplary, or consequential damages -// (including, but not limited to, procurement of substitute goods or services; -// loss of use, data, or profits; or business interruption) however caused -// and on any theory of liability, whether in contract, strict liability, -// or tort (including negligence or otherwise) arising in any way out of -// the use of this software, even if advised of the possibility of such damage. -// -//M*/ - -#include "_ml.h" - -/****************************************************************************************\ - COPYRIGHT NOTICE - ---------------- - - The code has been derived from libsvm library (version 2.6) - (http://www.csie.ntu.edu.tw/~cjlin/libsvm). - - Here is the orignal copyright: ------------------------------------------------------------------------------------------- - Copyright (c) 2000-2003 Chih-Chung Chang and Chih-Jen Lin - All rights reserved. - - Redistribution and use in source and binary forms, with or without - modification, are permitted provided that the following conditions - are met: - - 1. Redistributions of source code must retain the above copyright - notice, this list of conditions and the following disclaimer. - - 2. Redistributions in binary form must reproduce the above copyright - notice, this list of conditions and the following disclaimer in the - documentation and/or other materials provided with the distribution. - - 3. Neither name of copyright holders nor the names of its contributors - may be used to endorse or promote products derived from this software - without specific prior written permission. - - - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF - LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. -\****************************************************************************************/ - -#define CV_SVM_MIN_CACHE_SIZE (40 << 20) /* 40Mb */ - -#include -#include - -#if _MSC_VER >= 1200 -#pragma warning( disable: 4514 ) /* unreferenced inline functions */ -#endif - -#if 1 -typedef float Qfloat; -#define QFLOAT_TYPE CV_32F -#else -typedef double Qfloat; -#define QFLOAT_TYPE CV_64F -#endif - -// Param Grid -bool CvParamGrid::check() const -{ - bool ok = false; - - CV_FUNCNAME( "CvParamGrid::check" ); - __BEGIN__; - - if( min_val > max_val ) - CV_ERROR( CV_StsBadArg, "Lower bound of the grid must be less then the upper one" ); - if( min_val < DBL_EPSILON ) - CV_ERROR( CV_StsBadArg, "Lower bound of the grid must be positive" ); - if( step < 1. + FLT_EPSILON ) - CV_ERROR( CV_StsBadArg, "Grid step must greater then 1" ); - - ok = true; - - __END__; - - return ok; -} - -CvParamGrid CvSVM::get_default_grid( int param_id ) -{ - CvParamGrid grid; - if( param_id == CvSVM::C ) - { - grid.min_val = 0.1; - grid.max_val = 500; - grid.step = 5; // total iterations = 5 - } - else if( param_id == CvSVM::GAMMA ) - { - grid.min_val = 1e-5; - grid.max_val = 0.6; - grid.step = 15; // total iterations = 4 - } - else if( param_id == CvSVM::P ) - { - grid.min_val = 0.01; - grid.max_val = 100; - grid.step = 7; // total iterations = 4 - } - else if( param_id == CvSVM::NU ) - { - grid.min_val = 0.01; - grid.max_val = 0.2; - grid.step = 3; // total iterations = 3 - } - else if( param_id == CvSVM::COEF ) - { - grid.min_val = 0.1; - grid.max_val = 300; - grid.step = 14; // total iterations = 3 - } - else if( param_id == CvSVM::DEGREE ) - { - grid.min_val = 0.01; - grid.max_val = 4; - grid.step = 7; // total iterations = 3 - } - else - cvError( CV_StsBadArg, "CvSVM::get_default_grid", "Invalid type of parameter " - "(use one of CvSVM::C, CvSVM::GAMMA et al.)", __FILE__, __LINE__ ); - return grid; -} - -// SVM training parameters -CvSVMParams::CvSVMParams() : - svm_type(CvSVM::C_SVC), kernel_type(CvSVM::RBF), degree(0), - gamma(1), coef0(0), C(1), nu(0), p(0), class_weights(0) -{ - term_crit = cvTermCriteria( CV_TERMCRIT_ITER+CV_TERMCRIT_EPS, 1000, FLT_EPSILON ); -} - - -CvSVMParams::CvSVMParams( int _svm_type, int _kernel_type, - double _degree, double _gamma, double _coef0, - double _Con, double _nu, double _p, - CvMat* _class_weights, CvTermCriteria _term_crit ) : - svm_type(_svm_type), kernel_type(_kernel_type), - degree(_degree), gamma(_gamma), coef0(_coef0), - C(_Con), nu(_nu), p(_p), class_weights(_class_weights), term_crit(_term_crit) -{ -} - - -/////////////////////////////////////// SVM kernel /////////////////////////////////////// - -CvSVMKernel::CvSVMKernel() -{ - clear(); -} - - -void CvSVMKernel::clear() -{ - params = 0; - calc_func = 0; -} - - -CvSVMKernel::~CvSVMKernel() -{ -} - - -CvSVMKernel::CvSVMKernel( const CvSVMParams* _params, Calc _calc_func ) -{ - clear(); - create( _params, _calc_func ); -} - - -bool CvSVMKernel::create( const CvSVMParams* _params, Calc _calc_func ) -{ - clear(); - params = _params; - calc_func = _calc_func; - - if( !calc_func ) - calc_func = params->kernel_type == CvSVM::RBF ? &CvSVMKernel::calc_rbf : - params->kernel_type == CvSVM::POLY ? &CvSVMKernel::calc_poly : - params->kernel_type == CvSVM::SIGMOID ? &CvSVMKernel::calc_sigmoid : - &CvSVMKernel::calc_linear; - - return true; -} - - -void CvSVMKernel::calc_non_rbf_base( int vcount, int var_count, const float** vecs, - const float* another, Qfloat* results, - double alpha, double beta ) -{ - int j, k; - for( j = 0; j < vcount; j++ ) - { - const float* sample = vecs[j]; - double s = 0; - for( k = 0; k <= var_count - 4; k += 4 ) - s += sample[k]*another[k] + sample[k+1]*another[k+1] + - sample[k+2]*another[k+2] + sample[k+3]*another[k+3]; - for( ; k < var_count; k++ ) - s += sample[k]*another[k]; - results[j] = (Qfloat)(s*alpha + beta); - } -} - - -void CvSVMKernel::calc_linear( int vcount, int var_count, const float** vecs, - const float* another, Qfloat* results ) -{ - calc_non_rbf_base( vcount, var_count, vecs, another, results, 1, 0 ); -} - - -void CvSVMKernel::calc_poly( int vcount, int var_count, const float** vecs, - const float* another, Qfloat* results ) -{ - CvMat R = cvMat( 1, vcount, QFLOAT_TYPE, results ); - calc_non_rbf_base( vcount, var_count, vecs, another, results, params->gamma, params->coef0 ); - cvPow( &R, &R, params->degree ); -} - - -void CvSVMKernel::calc_sigmoid( int vcount, int var_count, const float** vecs, - const float* another, Qfloat* results ) -{ - int j; - calc_non_rbf_base( vcount, var_count, vecs, another, results, - -2*params->gamma, -2*params->coef0 ); - // TODO: speedup this - for( j = 0; j < vcount; j++ ) - { - Qfloat t = results[j]; - double e = exp(-fabs(t)); - if( t > 0 ) - results[j] = (Qfloat)((1. - e)/(1. + e)); - else - results[j] = (Qfloat)((e - 1.)/(e + 1.)); - } -} - - -void CvSVMKernel::calc_rbf( int vcount, int var_count, const float** vecs, - const float* another, Qfloat* results ) -{ - CvMat R = cvMat( 1, vcount, QFLOAT_TYPE, results ); - double gamma = -params->gamma; - int j, k; - - for( j = 0; j < vcount; j++ ) - { - const float* sample = vecs[j]; - double s = 0; - - for( k = 0; k <= var_count - 4; k += 4 ) - { - double t0 = sample[k] - another[k]; - double t1 = sample[k+1] - another[k+1]; - - s += t0*t0 + t1*t1; - - t0 = sample[k+2] - another[k+2]; - t1 = sample[k+3] - another[k+3]; - - s += t0*t0 + t1*t1; - } - - for( ; k < var_count; k++ ) - { - double t0 = sample[k] - another[k]; - s += t0*t0; - } - results[j] = (Qfloat)(s*gamma); - } - - cvExp( &R, &R ); -} - - -void CvSVMKernel::calc( int vcount, int var_count, const float** vecs, - const float* another, Qfloat* results ) -{ - const Qfloat max_val = (Qfloat)(FLT_MAX*1e-3); - int j; - (this->*calc_func)( vcount, var_count, vecs, another, results ); - for( j = 0; j < vcount; j++ ) - { - if( results[j] > max_val ) - results[j] = max_val; - } -} - - -// Generalized SMO+SVMlight algorithm -// Solves: -// -// min [0.5(\alpha^T Q \alpha) + b^T \alpha] -// -// y^T \alpha = \delta -// y_i = +1 or -1 -// 0 <= alpha_i <= Cp for y_i = 1 -// 0 <= alpha_i <= Cn for y_i = -1 -// -// Given: -// -// Q, b, y, Cp, Cn, and an initial feasible point \alpha -// l is the size of vectors and matrices -// eps is the stopping criterion -// -// solution will be put in \alpha, objective value will be put in obj -// - -void CvSVMSolver::clear() -{ - G = 0; - alpha = 0; - y = 0; - b = 0; - buf[0] = buf[1] = 0; - cvReleaseMemStorage( &storage ); - kernel = 0; - select_working_set_func = 0; - calc_rho_func = 0; - - rows = 0; - samples = 0; - get_row_func = 0; -} - - -CvSVMSolver::CvSVMSolver() -{ - storage = 0; - clear(); -} - - -CvSVMSolver::~CvSVMSolver() -{ - clear(); -} - - -CvSVMSolver::CvSVMSolver( int _sample_count, int _var_count, const float** _samples, schar* _y, - int _alpha_count, double* _alpha, double _Cp, double _Cn, - CvMemStorage* _storage, CvSVMKernel* _kernel, GetRow _get_row, - SelectWorkingSet _select_working_set, CalcRho _calc_rho ) -{ - storage = 0; - create( _sample_count, _var_count, _samples, _y, _alpha_count, _alpha, _Cp, _Cn, - _storage, _kernel, _get_row, _select_working_set, _calc_rho ); -} - - -bool CvSVMSolver::create( int _sample_count, int _var_count, const float** _samples, schar* _y, - int _alpha_count, double* _alpha, double _Cp, double _Cn, - CvMemStorage* _storage, CvSVMKernel* _kernel, GetRow _get_row, - SelectWorkingSet _select_working_set, CalcRho _calc_rho ) -{ - bool ok = false; - int i, svm_type; - - CV_FUNCNAME( "CvSVMSolver::create" ); - - __BEGIN__; - - int rows_hdr_size; - - clear(); - - sample_count = _sample_count; - var_count = _var_count; - samples = _samples; - y = _y; - alpha_count = _alpha_count; - alpha = _alpha; - kernel = _kernel; - - C[0] = _Cn; - C[1] = _Cp; - eps = kernel->params->term_crit.epsilon; - max_iter = kernel->params->term_crit.max_iter; - storage = cvCreateChildMemStorage( _storage ); - - b = (double*)cvMemStorageAlloc( storage, alpha_count*sizeof(b[0])); - alpha_status = (schar*)cvMemStorageAlloc( storage, alpha_count*sizeof(alpha_status[0])); - G = (double*)cvMemStorageAlloc( storage, alpha_count*sizeof(G[0])); - for( i = 0; i < 2; i++ ) - buf[i] = (Qfloat*)cvMemStorageAlloc( storage, sample_count*2*sizeof(buf[i][0]) ); - svm_type = kernel->params->svm_type; - - select_working_set_func = _select_working_set; - if( !select_working_set_func ) - select_working_set_func = svm_type == CvSVM::NU_SVC || svm_type == CvSVM::NU_SVR ? - &CvSVMSolver::select_working_set_nu_svm : &CvSVMSolver::select_working_set; - - calc_rho_func = _calc_rho; - if( !calc_rho_func ) - calc_rho_func = svm_type == CvSVM::NU_SVC || svm_type == CvSVM::NU_SVR ? - &CvSVMSolver::calc_rho_nu_svm : &CvSVMSolver::calc_rho; - - get_row_func = _get_row; - if( !get_row_func ) - get_row_func = params->svm_type == CvSVM::EPS_SVR || - params->svm_type == CvSVM::NU_SVR ? &CvSVMSolver::get_row_svr : - params->svm_type == CvSVM::C_SVC || - params->svm_type == CvSVM::NU_SVC ? &CvSVMSolver::get_row_svc : - &CvSVMSolver::get_row_one_class; - - cache_line_size = sample_count*sizeof(Qfloat); - // cache size = max(num_of_samples^2*sizeof(Qfloat)*0.25, 64Kb) - // (assuming that for large training sets ~25% of Q matrix is used) - cache_size = MAX( cache_line_size*sample_count/4, CV_SVM_MIN_CACHE_SIZE ); - - // the size of Q matrix row headers - rows_hdr_size = sample_count*sizeof(rows[0]); - if( rows_hdr_size > storage->block_size ) - CV_ERROR( CV_StsOutOfRange, "Too small storage block size" ); - - lru_list.prev = lru_list.next = &lru_list; - rows = (CvSVMKernelRow*)cvMemStorageAlloc( storage, rows_hdr_size ); - memset( rows, 0, rows_hdr_size ); - - ok = true; - - __END__; - - return ok; -} - - -float* CvSVMSolver::get_row_base( int i, bool* _existed ) -{ - int i1 = i < sample_count ? i : i - sample_count; - CvSVMKernelRow* row = rows + i1; - bool existed = row->data != 0; - Qfloat* data; - - if( existed || cache_size <= 0 ) - { - CvSVMKernelRow* del_row = existed ? row : lru_list.prev; - data = del_row->data; - assert( data != 0 ); - - // delete row from the LRU list - del_row->data = 0; - del_row->prev->next = del_row->next; - del_row->next->prev = del_row->prev; - } - else - { - data = (Qfloat*)cvMemStorageAlloc( storage, cache_line_size ); - cache_size -= cache_line_size; - } - - // insert row into the LRU list - row->data = data; - row->prev = &lru_list; - row->next = lru_list.next; - row->prev->next = row->next->prev = row; - - if( !existed ) - { - kernel->calc( sample_count, var_count, samples, samples[i1], row->data ); - } - - if( _existed ) - *_existed = existed; - - return row->data; -} - - -float* CvSVMSolver::get_row_svc( int i, float* row, float*, bool existed ) -{ - if( !existed ) - { - const schar* _y = y; - int j, len = sample_count; - assert( _y && i < sample_count ); - - if( _y[i] > 0 ) - { - for( j = 0; j < len; j++ ) - row[j] = _y[j]*row[j]; - } - else - { - for( j = 0; j < len; j++ ) - row[j] = -_y[j]*row[j]; - } - } - return row; -} - - -float* CvSVMSolver::get_row_one_class( int, float* row, float*, bool ) -{ - return row; -} - - -float* CvSVMSolver::get_row_svr( int i, float* row, float* dst, bool ) -{ - int j, len = sample_count; - Qfloat* dst_pos = dst; - Qfloat* dst_neg = dst + len; - if( i >= len ) - { - Qfloat* temp; - CV_SWAP( dst_pos, dst_neg, temp ); - } - - for( j = 0; j < len; j++ ) - { - Qfloat t = row[j]; - dst_pos[j] = t; - dst_neg[j] = -t; - } - return dst; -} - - - -float* CvSVMSolver::get_row( int i, float* dst ) -{ - bool existed = false; - float* row = get_row_base( i, &existed ); - return (this->*get_row_func)( i, row, dst, existed ); -} - - -#undef is_upper_bound -#define is_upper_bound(i) (alpha_status[i] > 0) - -#undef is_lower_bound -#define is_lower_bound(i) (alpha_status[i] < 0) - -#undef is_free -#define is_free(i) (alpha_status[i] == 0) - -#undef get_C -#define get_C(i) (C[y[i]>0]) - -#undef update_alpha_status -#define update_alpha_status(i) \ - alpha_status[i] = (schar)(alpha[i] >= get_C(i) ? 1 : alpha[i] <= 0 ? -1 : 0) - -#undef reconstruct_gradient -#define reconstruct_gradient() /* empty for now */ - - -bool CvSVMSolver::solve_generic( CvSVMSolutionInfo& si ) -{ - int iter = 0; - int i, j, k; - - // 1. initialize gradient and alpha status - for( i = 0; i < alpha_count; i++ ) - { - update_alpha_status(i); - G[i] = b[i]; - if( fabs(G[i]) > 1e200 ) - return false; - } - - for( i = 0; i < alpha_count; i++ ) - { - if( !is_lower_bound(i) ) - { - const Qfloat *Q_i = get_row( i, buf[0] ); - double alpha_i = alpha[i]; - - for( j = 0; j < alpha_count; j++ ) - G[j] += alpha_i*Q_i[j]; - } - } - - // 2. optimization loop - for(;;) - { - const Qfloat *Q_i, *Q_j; - double C_i, C_j; - double old_alpha_i, old_alpha_j, alpha_i, alpha_j; - double delta_alpha_i, delta_alpha_j; - -#ifdef _DEBUG - for( i = 0; i < alpha_count; i++ ) - { - if( fabs(G[i]) > 1e+300 ) - return false; - - if( fabs(alpha[i]) > 1e16 ) - return false; - } -#endif - - if( (this->*select_working_set_func)( i, j ) != 0 || iter++ >= max_iter ) - break; - - Q_i = get_row( i, buf[0] ); - Q_j = get_row( j, buf[1] ); - - C_i = get_C(i); - C_j = get_C(j); - - alpha_i = old_alpha_i = alpha[i]; - alpha_j = old_alpha_j = alpha[j]; - - if( y[i] != y[j] ) - { - double denom = Q_i[i]+Q_j[j]+2*Q_i[j]; - double delta = (-G[i]-G[j])/MAX(fabs(denom),FLT_EPSILON); - double diff = alpha_i - alpha_j; - alpha_i += delta; - alpha_j += delta; - - if( diff > 0 && alpha_j < 0 ) - { - alpha_j = 0; - alpha_i = diff; - } - else if( diff <= 0 && alpha_i < 0 ) - { - alpha_i = 0; - alpha_j = -diff; - } - - if( diff > C_i - C_j && alpha_i > C_i ) - { - alpha_i = C_i; - alpha_j = C_i - diff; - } - else if( diff <= C_i - C_j && alpha_j > C_j ) - { - alpha_j = C_j; - alpha_i = C_j + diff; - } - } - else - { - double denom = Q_i[i]+Q_j[j]-2*Q_i[j]; - double delta = (G[i]-G[j])/MAX(fabs(denom),FLT_EPSILON); - double sum = alpha_i + alpha_j; - alpha_i -= delta; - alpha_j += delta; - - if( sum > C_i && alpha_i > C_i ) - { - alpha_i = C_i; - alpha_j = sum - C_i; - } - else if( sum <= C_i && alpha_j < 0) - { - alpha_j = 0; - alpha_i = sum; - } - - if( sum > C_j && alpha_j > C_j ) - { - alpha_j = C_j; - alpha_i = sum - C_j; - } - else if( sum <= C_j && alpha_i < 0 ) - { - alpha_i = 0; - alpha_j = sum; - } - } - - // update alpha - alpha[i] = alpha_i; - alpha[j] = alpha_j; - update_alpha_status(i); - update_alpha_status(j); - - // update G - delta_alpha_i = alpha_i - old_alpha_i; - delta_alpha_j = alpha_j - old_alpha_j; - - for( k = 0; k < alpha_count; k++ ) - G[k] += Q_i[k]*delta_alpha_i + Q_j[k]*delta_alpha_j; - } - - // calculate rho - (this->*calc_rho_func)( si.rho, si.r ); - - // calculate objective value - for( i = 0, si.obj = 0; i < alpha_count; i++ ) - si.obj += alpha[i] * (G[i] + b[i]); - - si.obj *= 0.5; - - si.upper_bound_p = C[1]; - si.upper_bound_n = C[0]; - - return true; -} - - -// return 1 if already optimal, return 0 otherwise -bool -CvSVMSolver::select_working_set( int& out_i, int& out_j ) -{ - // return i,j which maximize -grad(f)^T d , under constraint - // if alpha_i == C, d != +1 - // if alpha_i == 0, d != -1 - double Gmax1 = -DBL_MAX; // max { -grad(f)_i * d | y_i*d = +1 } - int Gmax1_idx = -1; - - double Gmax2 = -DBL_MAX; // max { -grad(f)_i * d | y_i*d = -1 } - int Gmax2_idx = -1; - - int i; - - for( i = 0; i < alpha_count; i++ ) - { - double t; - - if( y[i] > 0 ) // y = +1 - { - if( !is_upper_bound(i) && (t = -G[i]) > Gmax1 ) // d = +1 - { - Gmax1 = t; - Gmax1_idx = i; - } - if( !is_lower_bound(i) && (t = G[i]) > Gmax2 ) // d = -1 - { - Gmax2 = t; - Gmax2_idx = i; - } - } - else // y = -1 - { - if( !is_upper_bound(i) && (t = -G[i]) > Gmax2 ) // d = +1 - { - Gmax2 = t; - Gmax2_idx = i; - } - if( !is_lower_bound(i) && (t = G[i]) > Gmax1 ) // d = -1 - { - Gmax1 = t; - Gmax1_idx = i; - } - } - } - - out_i = Gmax1_idx; - out_j = Gmax2_idx; - - return Gmax1 + Gmax2 < eps; -} - - -void -CvSVMSolver::calc_rho( double& rho, double& r ) -{ - int i, nr_free = 0; - double ub = DBL_MAX, lb = -DBL_MAX, sum_free = 0; - - for( i = 0; i < alpha_count; i++ ) - { - double yG = y[i]*G[i]; - - if( is_lower_bound(i) ) - { - if( y[i] > 0 ) - ub = MIN(ub,yG); - else - lb = MAX(lb,yG); - } - else if( is_upper_bound(i) ) - { - if( y[i] < 0) - ub = MIN(ub,yG); - else - lb = MAX(lb,yG); - } - else - { - ++nr_free; - sum_free += yG; - } - } - - rho = nr_free > 0 ? sum_free/nr_free : (ub + lb)*0.5; - r = 0; -} - - -bool -CvSVMSolver::select_working_set_nu_svm( int& out_i, int& out_j ) -{ - // return i,j which maximize -grad(f)^T d , under constraint - // if alpha_i == C, d != +1 - // if alpha_i == 0, d != -1 - double Gmax1 = -DBL_MAX; // max { -grad(f)_i * d | y_i = +1, d = +1 } - int Gmax1_idx = -1; - - double Gmax2 = -DBL_MAX; // max { -grad(f)_i * d | y_i = +1, d = -1 } - int Gmax2_idx = -1; - - double Gmax3 = -DBL_MAX; // max { -grad(f)_i * d | y_i = -1, d = +1 } - int Gmax3_idx = -1; - - double Gmax4 = -DBL_MAX; // max { -grad(f)_i * d | y_i = -1, d = -1 } - int Gmax4_idx = -1; - - int i; - - for( i = 0; i < alpha_count; i++ ) - { - double t; - - if( y[i] > 0 ) // y == +1 - { - if( !is_upper_bound(i) && (t = -G[i]) > Gmax1 ) // d = +1 - { - Gmax1 = t; - Gmax1_idx = i; - } - if( !is_lower_bound(i) && (t = G[i]) > Gmax2 ) // d = -1 - { - Gmax2 = t; - Gmax2_idx = i; - } - } - else // y == -1 - { - if( !is_upper_bound(i) && (t = -G[i]) > Gmax3 ) // d = +1 - { - Gmax3 = t; - Gmax3_idx = i; - } - if( !is_lower_bound(i) && (t = G[i]) > Gmax4 ) // d = -1 - { - Gmax4 = t; - Gmax4_idx = i; - } - } - } - - if( MAX(Gmax1 + Gmax2, Gmax3 + Gmax4) < eps ) - return 1; - - if( Gmax1 + Gmax2 > Gmax3 + Gmax4 ) - { - out_i = Gmax1_idx; - out_j = Gmax2_idx; - } - else - { - out_i = Gmax3_idx; - out_j = Gmax4_idx; - } - return 0; -} - - -void -CvSVMSolver::calc_rho_nu_svm( double& rho, double& r ) -{ - int nr_free1 = 0, nr_free2 = 0; - double ub1 = DBL_MAX, ub2 = DBL_MAX; - double lb1 = -DBL_MAX, lb2 = -DBL_MAX; - double sum_free1 = 0, sum_free2 = 0; - double r1, r2; - - int i; - - for( i = 0; i < alpha_count; i++ ) - { - double G_i = G[i]; - if( y[i] > 0 ) - { - if( is_lower_bound(i) ) - ub1 = MIN( ub1, G_i ); - else if( is_upper_bound(i) ) - lb1 = MAX( lb1, G_i ); - else - { - ++nr_free1; - sum_free1 += G_i; - } - } - else - { - if( is_lower_bound(i) ) - ub2 = MIN( ub2, G_i ); - else if( is_upper_bound(i) ) - lb2 = MAX( lb2, G_i ); - else - { - ++nr_free2; - sum_free2 += G_i; - } - } - } - - r1 = nr_free1 > 0 ? sum_free1/nr_free1 : (ub1 + lb1)*0.5; - r2 = nr_free2 > 0 ? sum_free2/nr_free2 : (ub2 + lb2)*0.5; - - rho = (r1 - r2)*0.5; - r = (r1 + r2)*0.5; -} - - -/* -///////////////////////// construct and solve various formulations /////////////////////// -*/ - -bool CvSVMSolver::solve_c_svc( int _sample_count, int _var_count, const float** _samples, schar* _y, - double _Cp, double _Cn, CvMemStorage* _storage, - CvSVMKernel* _kernel, double* _alpha, CvSVMSolutionInfo& _si ) -{ - int i; - - if( !create( _sample_count, _var_count, _samples, _y, _sample_count, - _alpha, _Cp, _Cn, _storage, _kernel, &CvSVMSolver::get_row_svc, - &CvSVMSolver::select_working_set, &CvSVMSolver::calc_rho )) - return false; - - for( i = 0; i < sample_count; i++ ) - { - alpha[i] = 0; - b[i] = -1; - } - - if( !solve_generic( _si )) - return false; - - for( i = 0; i < sample_count; i++ ) - alpha[i] *= y[i]; - - return true; -} - - -bool CvSVMSolver::solve_nu_svc( int _sample_count, int _var_count, const float** _samples, schar* _y, - CvMemStorage* _storage, CvSVMKernel* _kernel, - double* _alpha, CvSVMSolutionInfo& _si ) -{ - int i; - double sum_pos, sum_neg, inv_r; - - if( !create( _sample_count, _var_count, _samples, _y, _sample_count, - _alpha, 1., 1., _storage, _kernel, &CvSVMSolver::get_row_svc, - &CvSVMSolver::select_working_set_nu_svm, &CvSVMSolver::calc_rho_nu_svm )) - return false; - - sum_pos = kernel->params->nu * sample_count * 0.5; - sum_neg = kernel->params->nu * sample_count * 0.5; - - for( i = 0; i < sample_count; i++ ) - { - if( y[i] > 0 ) - { - alpha[i] = MIN(1.0, sum_pos); - sum_pos -= alpha[i]; - } - else - { - alpha[i] = MIN(1.0, sum_neg); - sum_neg -= alpha[i]; - } - b[i] = 0; - } - - if( !solve_generic( _si )) - return false; - - inv_r = 1./_si.r; - - for( i = 0; i < sample_count; i++ ) - alpha[i] *= y[i]*inv_r; - - _si.rho *= inv_r; - _si.obj *= (inv_r*inv_r); - _si.upper_bound_p = inv_r; - _si.upper_bound_n = inv_r; - - return true; -} - - -bool CvSVMSolver::solve_one_class( int _sample_count, int _var_count, const float** _samples, - CvMemStorage* _storage, CvSVMKernel* _kernel, - double* _alpha, CvSVMSolutionInfo& _si ) -{ - int i, n; - double nu = _kernel->params->nu; - - if( !create( _sample_count, _var_count, _samples, 0, _sample_count, - _alpha, 1., 1., _storage, _kernel, &CvSVMSolver::get_row_one_class, - &CvSVMSolver::select_working_set, &CvSVMSolver::calc_rho )) - return false; - - y = (schar*)cvMemStorageAlloc( storage, sample_count*sizeof(y[0]) ); - n = cvRound( nu*sample_count ); - - for( i = 0; i < sample_count; i++ ) - { - y[i] = 1; - b[i] = 0; - alpha[i] = i < n ? 1 : 0; - } - - if( n < sample_count ) - alpha[n] = nu * sample_count - n; - else - alpha[n-1] = nu * sample_count - (n-1); - - return solve_generic(_si); -} - - -bool CvSVMSolver::solve_eps_svr( int _sample_count, int _var_count, const float** _samples, - const float* _y, CvMemStorage* _storage, - CvSVMKernel* _kernel, double* _alpha, CvSVMSolutionInfo& _si ) -{ - int i; - double p = _kernel->params->p, C = _kernel->params->C; - - if( !create( _sample_count, _var_count, _samples, 0, - _sample_count*2, 0, C, C, _storage, _kernel, &CvSVMSolver::get_row_svr, - &CvSVMSolver::select_working_set, &CvSVMSolver::calc_rho )) - return false; - - y = (schar*)cvMemStorageAlloc( storage, sample_count*2*sizeof(y[0]) ); - alpha = (double*)cvMemStorageAlloc( storage, alpha_count*sizeof(alpha[0]) ); - - for( i = 0; i < sample_count; i++ ) - { - alpha[i] = 0; - b[i] = p - _y[i]; - y[i] = 1; - - alpha[i+sample_count] = 0; - b[i+sample_count] = p + _y[i]; - y[i+sample_count] = -1; - } - - if( !solve_generic( _si )) - return false; - - for( i = 0; i < sample_count; i++ ) - _alpha[i] = alpha[i] - alpha[i+sample_count]; - - return true; -} - - -bool CvSVMSolver::solve_nu_svr( int _sample_count, int _var_count, const float** _samples, - const float* _y, CvMemStorage* _storage, - CvSVMKernel* _kernel, double* _alpha, CvSVMSolutionInfo& _si ) -{ - int i; - double C = _kernel->params->C, sum; - - if( !create( _sample_count, _var_count, _samples, 0, - _sample_count*2, 0, 1., 1., _storage, _kernel, &CvSVMSolver::get_row_svr, - &CvSVMSolver::select_working_set_nu_svm, &CvSVMSolver::calc_rho_nu_svm )) - return false; - - y = (schar*)cvMemStorageAlloc( storage, sample_count*2*sizeof(y[0]) ); - alpha = (double*)cvMemStorageAlloc( storage, alpha_count*sizeof(alpha[0]) ); - sum = C * _kernel->params->nu * sample_count * 0.5; - - for( i = 0; i < sample_count; i++ ) - { - alpha[i] = alpha[i + sample_count] = MIN(sum, C); - sum -= alpha[i]; - - b[i] = -_y[i]; - y[i] = 1; - - b[i + sample_count] = _y[i]; - y[i + sample_count] = -1; - } - - if( !solve_generic( _si )) - return false; - - for( i = 0; i < sample_count; i++ ) - _alpha[i] = alpha[i] - alpha[i+sample_count]; - - return true; -} - - -////////////////////////////////////////////////////////////////////////////////////////// - -CvSVM::CvSVM() -{ - decision_func = 0; - class_labels = 0; - class_weights = 0; - storage = 0; - var_idx = 0; - kernel = 0; - solver = 0; - default_model_name = "my_svm"; - - clear(); -} - - -CvSVM::~CvSVM() -{ - clear(); -} - - -void CvSVM::clear() -{ - cvFree( &decision_func ); - cvReleaseMat( &class_labels ); - cvReleaseMat( &class_weights ); - cvReleaseMemStorage( &storage ); - cvReleaseMat( &var_idx ); - delete kernel; - delete solver; - kernel = 0; - solver = 0; - var_all = 0; - sv = 0; - sv_total = 0; -} - - -CvSVM::CvSVM( const CvMat* _train_data, const CvMat* _responses, - const CvMat* _var_idx, const CvMat* _sample_idx, CvSVMParams _params ) -{ - decision_func = 0; - class_labels = 0; - class_weights = 0; - storage = 0; - var_idx = 0; - kernel = 0; - solver = 0; - default_model_name = "my_svm"; - - train( _train_data, _responses, _var_idx, _sample_idx, _params ); -} - - -int CvSVM::get_support_vector_count() const -{ - return sv_total; -} - - -const float* CvSVM::get_support_vector(int i) const -{ - return sv && (unsigned)i < (unsigned)sv_total ? sv[i] : 0; -} - - -bool CvSVM::set_params( const CvSVMParams& _params ) -{ - bool ok = false; - - CV_FUNCNAME( "CvSVM::set_params" ); - - __BEGIN__; - - int kernel_type, svm_type; - - params = _params; - - kernel_type = params.kernel_type; - svm_type = params.svm_type; - - if( kernel_type != LINEAR && kernel_type != POLY && - kernel_type != SIGMOID && kernel_type != RBF ) - CV_ERROR( CV_StsBadArg, "Unknown/unsupported kernel type" ); - - if( kernel_type == LINEAR ) - params.gamma = 1; - else if( params.gamma <= 0 ) - CV_ERROR( CV_StsOutOfRange, "gamma parameter of the kernel must be positive" ); - - if( kernel_type != SIGMOID && kernel_type != POLY ) - params.coef0 = 0; - else if( params.coef0 < 0 ) - CV_ERROR( CV_StsOutOfRange, "The kernel parameter must be positive or zero" ); - - if( kernel_type != POLY ) - params.degree = 0; - else if( params.degree <= 0 ) - CV_ERROR( CV_StsOutOfRange, "The kernel parameter must be positive" ); - - if( svm_type != C_SVC && svm_type != NU_SVC && - svm_type != ONE_CLASS && svm_type != EPS_SVR && - svm_type != NU_SVR ) - CV_ERROR( CV_StsBadArg, "Unknown/unsupported SVM type" ); - - if( svm_type == ONE_CLASS || svm_type == NU_SVC ) - params.C = 0; - else if( params.C <= 0 ) - CV_ERROR( CV_StsOutOfRange, "The parameter C must be positive" ); - - if( svm_type == C_SVC || svm_type == EPS_SVR ) - params.nu = 0; - else if( params.nu <= 0 || params.nu >= 1 ) - CV_ERROR( CV_StsOutOfRange, "The parameter nu must be between 0 and 1" ); - - if( svm_type != EPS_SVR ) - params.p = 0; - else if( params.p <= 0 ) - CV_ERROR( CV_StsOutOfRange, "The parameter p must be positive" ); - - if( svm_type != C_SVC ) - params.class_weights = 0; - - params.term_crit = cvCheckTermCriteria( params.term_crit, DBL_EPSILON, INT_MAX ); - params.term_crit.epsilon = MAX( params.term_crit.epsilon, DBL_EPSILON ); - ok = true; - - __END__; - - return ok; -} - - - -void CvSVM::create_kernel() -{ - kernel = new CvSVMKernel(¶ms,0); -} - - -void CvSVM::create_solver( ) -{ - solver = new CvSVMSolver; -} - - -// switching function -bool CvSVM::train1( int sample_count, int var_count, const float** samples, - const void* _responses, double Cp, double Cn, - CvMemStorage* _storage, double* alpha, double& rho ) -{ - bool ok = false; - - //CV_FUNCNAME( "CvSVM::train1" ); - - __BEGIN__; - - CvSVMSolutionInfo si; - int svm_type = params.svm_type; - - si.rho = 0; - - ok = svm_type == C_SVC ? solver->solve_c_svc( sample_count, var_count, samples, (schar*)_responses, - Cp, Cn, _storage, kernel, alpha, si ) : - svm_type == NU_SVC ? solver->solve_nu_svc( sample_count, var_count, samples, (schar*)_responses, - _storage, kernel, alpha, si ) : - svm_type == ONE_CLASS ? solver->solve_one_class( sample_count, var_count, samples, - _storage, kernel, alpha, si ) : - svm_type == EPS_SVR ? solver->solve_eps_svr( sample_count, var_count, samples, (float*)_responses, - _storage, kernel, alpha, si ) : - svm_type == NU_SVR ? solver->solve_nu_svr( sample_count, var_count, samples, (float*)_responses, - _storage, kernel, alpha, si ) : false; - - rho = si.rho; - - __END__; - - return ok; -} - - -bool CvSVM::do_train( int svm_type, int sample_count, int var_count, const float** samples, - const CvMat* responses, CvMemStorage* temp_storage, double* alpha ) -{ - bool ok = false; - - CV_FUNCNAME( "CvSVM::do_train" ); - - __BEGIN__; - - CvSVMDecisionFunc* df = 0; - const int sample_size = var_count*sizeof(samples[0][0]); - int i, j, k; - - if( svm_type == ONE_CLASS || svm_type == EPS_SVR || svm_type == NU_SVR ) - { - int sv_count = 0; - - CV_CALL( decision_func = df = - (CvSVMDecisionFunc*)cvAlloc( sizeof(df[0]) )); - - df->rho = 0; - if( !train1( sample_count, var_count, samples, svm_type == ONE_CLASS ? 0 : - responses->data.i, 0, 0, temp_storage, alpha, df->rho )) - EXIT; - - for( i = 0; i < sample_count; i++ ) - sv_count += fabs(alpha[i]) > 0; - - sv_total = df->sv_count = sv_count; - CV_CALL( df->alpha = (double*)cvMemStorageAlloc( storage, sv_count*sizeof(df->alpha[0])) ); - CV_CALL( sv = (float**)cvMemStorageAlloc( storage, sv_count*sizeof(sv[0]))); - - for( i = k = 0; i < sample_count; i++ ) - { - if( fabs(alpha[i]) > 0 ) - { - CV_CALL( sv[k] = (float*)cvMemStorageAlloc( storage, sample_size )); - memcpy( sv[k], samples[i], sample_size ); - df->alpha[k++] = alpha[i]; - } - } - } - else - { - int class_count = class_labels->cols; - int* sv_tab = 0; - const float** temp_samples = 0; - int* class_ranges = 0; - schar* temp_y = 0; - assert( svm_type == CvSVM::C_SVC || svm_type == CvSVM::NU_SVC ); - - if( svm_type == CvSVM::C_SVC && params.class_weights ) - { - const CvMat* cw = params.class_weights; - - if( !CV_IS_MAT(cw) || cw->cols != 1 && cw->rows != 1 || - cw->rows + cw->cols - 1 != class_count || - CV_MAT_TYPE(cw->type) != CV_32FC1 && CV_MAT_TYPE(cw->type) != CV_64FC1 ) - CV_ERROR( CV_StsBadArg, "params.class_weights must be 1d floating-point vector " - "containing as many elements as the number of classes" ); - - CV_CALL( class_weights = cvCreateMat( cw->rows, cw->cols, CV_64F )); - CV_CALL( cvConvert( cw, class_weights )); - CV_CALL( cvScale( class_weights, class_weights, params.C )); - } - - CV_CALL( decision_func = df = (CvSVMDecisionFunc*)cvAlloc( - (class_count*(class_count-1)/2)*sizeof(df[0]))); - - CV_CALL( sv_tab = (int*)cvMemStorageAlloc( temp_storage, sample_count*sizeof(sv_tab[0]) )); - memset( sv_tab, 0, sample_count*sizeof(sv_tab[0]) ); - CV_CALL( class_ranges = (int*)cvMemStorageAlloc( temp_storage, - (class_count + 1)*sizeof(class_ranges[0]))); - CV_CALL( temp_samples = (const float**)cvMemStorageAlloc( temp_storage, - sample_count*sizeof(temp_samples[0]))); - CV_CALL( temp_y = (schar*)cvMemStorageAlloc( temp_storage, sample_count)); - - class_ranges[class_count] = 0; - cvSortSamplesByClasses( samples, responses, class_ranges, 0 ); - //check that while cross-validation there were the samples from all the classes - if( class_ranges[class_count] <= 0 ) - CV_ERROR( CV_StsBadArg, "While cross-validation one or more of the classes have " - "been fell out of the sample. Try to enlarge " ); - - if( svm_type == NU_SVC ) - { - // check if nu is feasible - for(i = 0; i < class_count; i++ ) - { - int ci = class_ranges[i+1] - class_ranges[i]; - for( j = i+1; j< class_count; j++ ) - { - int cj = class_ranges[j+1] - class_ranges[j]; - if( params.nu*(ci + cj)*0.5 > MIN( ci, cj ) ) - { - // !!!TODO!!! add some diagnostic - EXIT; // exit immediately; will release the model and return NULL pointer - } - } - } - } - - // train n*(n-1)/2 classifiers - for( i = 0; i < class_count; i++ ) - { - for( j = i+1; j < class_count; j++, df++ ) - { - int si = class_ranges[i], ci = class_ranges[i+1] - si; - int sj = class_ranges[j], cj = class_ranges[j+1] - sj; - double Cp = params.C, Cn = Cp; - int k1 = 0, sv_count = 0; - - for( k = 0; k < ci; k++ ) - { - temp_samples[k] = samples[si + k]; - temp_y[k] = 1; - } - - for( k = 0; k < cj; k++ ) - { - temp_samples[ci + k] = samples[sj + k]; - temp_y[ci + k] = -1; - } - - if( class_weights ) - { - Cp = class_weights->data.db[i]; - Cn = class_weights->data.db[j]; - } - - if( !train1( ci + cj, var_count, temp_samples, temp_y, - Cp, Cn, temp_storage, alpha, df->rho )) - EXIT; - - for( k = 0; k < ci + cj; k++ ) - sv_count += fabs(alpha[k]) > 0; - - df->sv_count = sv_count; - - CV_CALL( df->alpha = (double*)cvMemStorageAlloc( temp_storage, - sv_count*sizeof(df->alpha[0]))); - CV_CALL( df->sv_index = (int*)cvMemStorageAlloc( temp_storage, - sv_count*sizeof(df->sv_index[0]))); - - for( k = 0; k < ci; k++ ) - { - if( fabs(alpha[k]) > 0 ) - { - sv_tab[si + k] = 1; - df->sv_index[k1] = si + k; - df->alpha[k1++] = alpha[k]; - } - } - - for( k = 0; k < cj; k++ ) - { - if( fabs(alpha[ci + k]) > 0 ) - { - sv_tab[sj + k] = 1; - df->sv_index[k1] = sj + k; - df->alpha[k1++] = alpha[ci + k]; - } - } - } - } - - // allocate support vectors and initialize sv_tab - for( i = 0, k = 0; i < sample_count; i++ ) - { - if( sv_tab[i] ) - sv_tab[i] = ++k; - } - - sv_total = k; - CV_CALL( sv = (float**)cvMemStorageAlloc( storage, sv_total*sizeof(sv[0]))); - - for( i = 0, k = 0; i < sample_count; i++ ) - { - if( sv_tab[i] ) - { - CV_CALL( sv[k] = (float*)cvMemStorageAlloc( storage, sample_size )); - memcpy( sv[k], samples[i], sample_size ); - k++; - } - } - - df = (CvSVMDecisionFunc*)decision_func; - - // set sv pointers - for( i = 0; i < class_count; i++ ) - { - for( j = i+1; j < class_count; j++, df++ ) - { - for( k = 0; k < df->sv_count; k++ ) - { - df->sv_index[k] = sv_tab[df->sv_index[k]]-1; - assert( (unsigned)df->sv_index[k] < (unsigned)sv_total ); - } - } - } - } - - ok = true; - - __END__; - - return ok; -} - -bool CvSVM::train( const CvMat* _train_data, const CvMat* _responses, - const CvMat* _var_idx, const CvMat* _sample_idx, CvSVMParams _params ) -{ - bool ok = false; - CvMat* responses = 0; - CvMemStorage* temp_storage = 0; - const float** samples = 0; - - CV_FUNCNAME( "CvSVM::train" ); - - __BEGIN__; - - int svm_type, sample_count, var_count, sample_size; - int block_size = 1 << 16; - double* alpha; - - clear(); - CV_CALL( set_params( _params )); - - svm_type = _params.svm_type; - - /* Prepare training data and related parameters */ - CV_CALL( cvPrepareTrainData( "CvSVM::train", _train_data, CV_ROW_SAMPLE, - svm_type != CvSVM::ONE_CLASS ? _responses : 0, - svm_type == CvSVM::C_SVC || - svm_type == CvSVM::NU_SVC ? CV_VAR_CATEGORICAL : - CV_VAR_ORDERED, _var_idx, _sample_idx, - false, &samples, &sample_count, &var_count, &var_all, - &responses, &class_labels, &var_idx )); - - - sample_size = var_count*sizeof(samples[0][0]); - - // make the storage block size large enough to fit all - // the temporary vectors and output support vectors. - block_size = MAX( block_size, sample_count*(int)sizeof(CvSVMKernelRow)); - block_size = MAX( block_size, sample_count*2*(int)sizeof(double) + 1024 ); - block_size = MAX( block_size, sample_size*2 + 1024 ); - - CV_CALL( storage = cvCreateMemStorage(block_size)); - CV_CALL( temp_storage = cvCreateChildMemStorage(storage)); - CV_CALL( alpha = (double*)cvMemStorageAlloc(temp_storage, sample_count*sizeof(double))); - - create_kernel(); - create_solver(); - - if( !do_train( svm_type, sample_count, var_count, samples, responses, temp_storage, alpha )) - EXIT; - - ok = true; // model has been trained succesfully - - __END__; - - delete solver; - solver = 0; - cvReleaseMemStorage( &temp_storage ); - cvReleaseMat( &responses ); - cvFree( &samples ); - - if( cvGetErrStatus() < 0 || !ok ) - clear(); - - return ok; -} - -bool CvSVM::train_auto( const CvMat* _train_data, const CvMat* _responses, - const CvMat* _var_idx, const CvMat* _sample_idx, CvSVMParams _params, int k_fold, - CvParamGrid C_grid, CvParamGrid gamma_grid, CvParamGrid p_grid, - CvParamGrid nu_grid, CvParamGrid coef_grid, CvParamGrid degree_grid ) -{ - bool ok = false; - CvMat* responses = 0; - CvMat* responses_local = 0; - CvMemStorage* temp_storage = 0; - const float** samples = 0; - const float** samples_local = 0; - - CV_FUNCNAME( "CvSVM::train_auto" ); - __BEGIN__; - - int svm_type, sample_count, var_count, sample_size; - int block_size = 1 << 16; - double* alpha; - int i, k; - CvRNG rng = cvRNG(-1); - - // all steps are logarithmic and must be > 1 - double degree_step = 10, g_step = 10, coef_step = 10, C_step = 10, nu_step = 10, p_step = 10; - double gamma = 0, C = 0, degree = 0, coef = 0, p = 0, nu = 0; - double best_degree = 0, best_gamma = 0, best_coef = 0, best_C = 0, best_nu = 0, best_p = 0; - float min_error = FLT_MAX, error; - - if( _params.svm_type == CvSVM::ONE_CLASS ) - { - if(!train( _train_data, _responses, _var_idx, _sample_idx, _params )) - EXIT; - return true; - } - - clear(); - - if( k_fold < 2 ) - CV_ERROR( CV_StsBadArg, "Parameter must be > 1" ); - - CV_CALL(set_params( _params )); - svm_type = _params.svm_type; - - // All the parameters except, possibly, are positive. - // is nonnegative - if( C_grid.step <= 1 ) - { - C_grid.min_val = C_grid.max_val = params.C; - C_grid.step = 10; - } - else - CV_CALL(C_grid.check()); - - if( gamma_grid.step <= 1 ) - { - gamma_grid.min_val = gamma_grid.max_val = params.gamma; - gamma_grid.step = 10; - } - else - CV_CALL(gamma_grid.check()); - - if( p_grid.step <= 1 ) - { - p_grid.min_val = p_grid.max_val = params.p; - p_grid.step = 10; - } - else - CV_CALL(p_grid.check()); - - if( nu_grid.step <= 1 ) - { - nu_grid.min_val = nu_grid.max_val = params.nu; - nu_grid.step = 10; - } - else - CV_CALL(nu_grid.check()); - - if( coef_grid.step <= 1 ) - { - coef_grid.min_val = coef_grid.max_val = params.coef0; - coef_grid.step = 10; - } - else - CV_CALL(coef_grid.check()); - - if( degree_grid.step <= 1 ) - { - degree_grid.min_val = degree_grid.max_val = params.degree; - degree_grid.step = 10; - } - else - CV_CALL(degree_grid.check()); - - // these parameters are not used: - if( params.kernel_type != CvSVM::POLY ) - degree_grid.min_val = degree_grid.max_val = params.degree; - if( params.kernel_type == CvSVM::LINEAR ) - gamma_grid.min_val = gamma_grid.max_val = params.gamma; - if( params.kernel_type != CvSVM::POLY && params.kernel_type != CvSVM::SIGMOID ) - coef_grid.min_val = coef_grid.max_val = params.coef0; - if( svm_type == CvSVM::NU_SVC || svm_type == CvSVM::ONE_CLASS ) - C_grid.min_val = C_grid.max_val = params.C; - if( svm_type == CvSVM::C_SVC || svm_type == CvSVM::EPS_SVR ) - nu_grid.min_val = nu_grid.max_val = params.nu; - if( svm_type != CvSVM::EPS_SVR ) - p_grid.min_val = p_grid.max_val = params.p; - - CV_ASSERT( g_step > 1 && degree_step > 1 && coef_step > 1); - CV_ASSERT( p_step > 1 && C_step > 1 && nu_step > 1 ); - - /* Prepare training data and related parameters */ - CV_CALL(cvPrepareTrainData( "CvSVM::train_auto", _train_data, CV_ROW_SAMPLE, - svm_type != CvSVM::ONE_CLASS ? _responses : 0, - svm_type == CvSVM::C_SVC || - svm_type == CvSVM::NU_SVC ? CV_VAR_CATEGORICAL : - CV_VAR_ORDERED, _var_idx, _sample_idx, - false, &samples, &sample_count, &var_count, &var_all, - &responses, &class_labels, &var_idx )); - - sample_size = var_count*sizeof(samples[0][0]); - - // make the storage block size large enough to fit all - // the temporary vectors and output support vectors. - block_size = MAX( block_size, sample_count*(int)sizeof(CvSVMKernelRow)); - block_size = MAX( block_size, sample_count*2*(int)sizeof(double) + 1024 ); - block_size = MAX( block_size, sample_size*2 + 1024 ); - - CV_CALL(storage = cvCreateMemStorage(block_size)); - CV_CALL(temp_storage = cvCreateChildMemStorage(storage)); - CV_CALL(alpha = (double*)cvMemStorageAlloc(temp_storage, sample_count*sizeof(double))); - - create_kernel(); - create_solver(); - - { - const int testset_size = sample_count/k_fold; - const int trainset_size = sample_count - testset_size; - const int last_testset_size = sample_count - testset_size*(k_fold-1); - const int last_trainset_size = sample_count - last_testset_size; - const bool is_regression = (svm_type == EPS_SVR) || (svm_type == NU_SVR); - - size_t resp_elem_size = CV_ELEM_SIZE(responses->type); - size_t size = 2*last_trainset_size*sizeof(samples[0]); - - samples_local = (const float**) cvAlloc( size ); - memset( samples_local, 0, size ); - - responses_local = cvCreateMat( 1, trainset_size, CV_MAT_TYPE(responses->type) ); - cvZero( responses_local ); - - // randomly permute samples and responses - for( i = 0; i < sample_count; i++ ) - { - int i1 = cvRandInt( &rng ) % sample_count; - int i2 = cvRandInt( &rng ) % sample_count; - const float* temp; - float t; - int y; - - CV_SWAP( samples[i1], samples[i2], temp ); - if( is_regression ) - CV_SWAP( responses->data.fl[i1], responses->data.fl[i2], t ); - else - CV_SWAP( responses->data.i[i1], responses->data.i[i2], y ); - } - - C = C_grid.min_val; - do - { - params.C = C; - gamma = gamma_grid.min_val; - do - { - params.gamma = gamma; - p = p_grid.min_val; - do - { - params.p = p; - nu = nu_grid.min_val; - do - { - params.nu = nu; - coef = coef_grid.min_val; - do - { - params.coef0 = coef; - degree = degree_grid.min_val; - do - { - params.degree = degree; - - float** test_samples_ptr = (float**)samples; - uchar* true_resp = responses->data.ptr; - int test_size = testset_size; - int train_size = trainset_size; - - error = 0; - for( k = 0; k < k_fold; k++ ) - { - memcpy( samples_local, samples, sizeof(samples[0])*test_size*k ); - memcpy( samples_local + test_size*k, test_samples_ptr + test_size, - sizeof(samples[0])*(sample_count - testset_size*(k+1)) ); - - memcpy( responses_local->data.ptr, responses->data.ptr, resp_elem_size*test_size*k ); - memcpy( responses_local->data.ptr + resp_elem_size*test_size*k, - true_resp + resp_elem_size*test_size, - sizeof(samples[0])*(sample_count - testset_size*(k+1)) ); - - if( k == k_fold - 1 ) - { - test_size = last_testset_size; - train_size = last_trainset_size; - responses_local->cols = last_trainset_size; - } - - // Train SVM on samples - if( !do_train( svm_type, train_size, var_count, - (const float**)samples_local, responses_local, temp_storage, alpha ) ) - EXIT; - - // Compute test set error on samples - CvMat s = cvMat( 1, var_count, CV_32FC1 ); - for( i = 0; i < test_size; i++, true_resp += resp_elem_size, test_samples_ptr++ ) - { - float resp; - s.data.fl = *test_samples_ptr; - resp = predict( &s ); - error += is_regression ? powf( resp - *(float*)true_resp, 2 ) - : ((int)resp != *(int*)true_resp); - } - } - if( min_error > error ) - { - min_error = error; - best_degree = degree; - best_gamma = gamma; - best_coef = coef; - best_C = C; - best_nu = nu; - best_p = p; - } - degree *= degree_grid.step; - } - while( degree < degree_grid.max_val ); - coef *= coef_grid.step; - } - while( coef < coef_grid.max_val ); - nu *= nu_grid.step; - } - while( nu < nu_grid.max_val ); - p *= p_grid.step; - } - while( p < p_grid.max_val ); - gamma *= gamma_grid.step; - } - while( gamma < gamma_grid.max_val ); - C *= C_grid.step; - } - while( C < C_grid.max_val ); - } - - min_error /= (float) sample_count; - - params.C = best_C; - params.nu = best_nu; - params.p = best_p; - params.gamma = best_gamma; - params.degree = best_degree; - params.coef0 = best_coef; - - CV_CALL(ok = do_train( svm_type, sample_count, var_count, samples, responses, temp_storage, alpha )); - - __END__; - - delete solver; - solver = 0; - cvReleaseMemStorage( &temp_storage ); - cvReleaseMat( &responses ); - cvReleaseMat( &responses_local ); - cvFree( &samples ); - cvFree( &samples_local ); - - if( cvGetErrStatus() < 0 || !ok ) - clear(); - - return ok; -} - -float CvSVM::predict( const CvMat* sample ) const -{ - bool local_alloc = 0; - float result = 0; - float* row_sample = 0; - Qfloat* buffer = 0; - - CV_FUNCNAME( "CvSVM::predict" ); - - __BEGIN__; - - int class_count; - int var_count, buf_sz; - - if( !kernel ) - CV_ERROR( CV_StsBadArg, "The SVM should be trained first" ); - - class_count = class_labels ? class_labels->cols : - params.svm_type == ONE_CLASS ? 1 : 0; - - CV_CALL( cvPreparePredictData( sample, var_all, var_idx, - class_count, 0, &row_sample )); - - var_count = get_var_count(); - - buf_sz = sv_total*sizeof(buffer[0]) + (class_count+1)*sizeof(int); - if( buf_sz <= CV_MAX_LOCAL_SIZE ) - { - CV_CALL( buffer = (Qfloat*)cvStackAlloc( buf_sz )); - local_alloc = 1; - } - else - CV_CALL( buffer = (Qfloat*)cvAlloc( buf_sz )); - - if( params.svm_type == EPS_SVR || - params.svm_type == NU_SVR || - params.svm_type == ONE_CLASS ) - { - CvSVMDecisionFunc* df = (CvSVMDecisionFunc*)decision_func; - int i, sv_count = df->sv_count; - double sum = -df->rho; - - kernel->calc( sv_count, var_count, (const float**)sv, row_sample, buffer ); - for( i = 0; i < sv_count; i++ ) - sum += buffer[i]*df->alpha[i]; - - result = params.svm_type == ONE_CLASS ? (float)(sum > 0) : (float)sum; - } - else if( params.svm_type == C_SVC || - params.svm_type == NU_SVC ) - { - CvSVMDecisionFunc* df = (CvSVMDecisionFunc*)decision_func; - int* vote = (int*)(buffer + sv_total); - int i, j, k; - - memset( vote, 0, class_count*sizeof(vote[0])); - kernel->calc( sv_total, var_count, (const float**)sv, row_sample, buffer ); - - for( i = 0; i < class_count; i++ ) - { - for( j = i+1; j < class_count; j++, df++ ) - { - double sum = -df->rho; - int sv_count = df->sv_count; - for( k = 0; k < sv_count; k++ ) - sum += df->alpha[k]*buffer[df->sv_index[k]]; - - vote[sum > 0 ? i : j]++; - } - } - - for( i = 1, k = 0; i < class_count; i++ ) - { - if( vote[i] > vote[k] ) - k = i; - } - - result = (float)(class_labels->data.i[k]); - } - else - CV_ERROR( CV_StsBadArg, "INTERNAL ERROR: Unknown SVM type, " - "the SVM structure is probably corrupted" ); - - __END__; - - if( sample && (!CV_IS_MAT(sample) || sample->data.fl != row_sample) ) - cvFree( &row_sample ); - - if( !local_alloc ) - cvFree( &buffer ); - - return result; -} - - -void CvSVM::write_params( CvFileStorage* fs ) -{ - //CV_FUNCNAME( "CvSVM::write_params" ); - - __BEGIN__; - - int svm_type = params.svm_type; - int kernel_type = params.kernel_type; - - const char* svm_type_str = - svm_type == CvSVM::C_SVC ? "C_SVC" : - svm_type == CvSVM::NU_SVC ? "NU_SVC" : - svm_type == CvSVM::ONE_CLASS ? "ONE_CLASS" : - svm_type == CvSVM::EPS_SVR ? "EPS_SVR" : - svm_type == CvSVM::NU_SVR ? "NU_SVR" : 0; - const char* kernel_type_str = - kernel_type == CvSVM::LINEAR ? "LINEAR" : - kernel_type == CvSVM::POLY ? "POLY" : - kernel_type == CvSVM::RBF ? "RBF" : - kernel_type == CvSVM::SIGMOID ? "SIGMOID" : 0; - - if( svm_type_str ) - cvWriteString( fs, "svm_type", svm_type_str ); - else - cvWriteInt( fs, "svm_type", svm_type ); - - // save kernel - cvStartWriteStruct( fs, "kernel", CV_NODE_MAP + CV_NODE_FLOW ); - - if( kernel_type_str ) - cvWriteString( fs, "type", kernel_type_str ); - else - cvWriteInt( fs, "type", kernel_type ); - - if( kernel_type == CvSVM::POLY || !kernel_type_str ) - cvWriteReal( fs, "degree", params.degree ); - - if( kernel_type != CvSVM::LINEAR || !kernel_type_str ) - cvWriteReal( fs, "gamma", params.gamma ); - - if( kernel_type == CvSVM::POLY || kernel_type == CvSVM::SIGMOID || !kernel_type_str ) - cvWriteReal( fs, "coef0", params.coef0 ); - - cvEndWriteStruct(fs); - - if( svm_type == CvSVM::C_SVC || svm_type == CvSVM::EPS_SVR || - svm_type == CvSVM::NU_SVR || !svm_type_str ) - cvWriteReal( fs, "C", params.C ); - - if( svm_type == CvSVM::NU_SVC || svm_type == CvSVM::ONE_CLASS || - svm_type == CvSVM::NU_SVR || !svm_type_str ) - cvWriteReal( fs, "nu", params.nu ); - - if( svm_type == CvSVM::EPS_SVR || !svm_type_str ) - cvWriteReal( fs, "p", params.p ); - - cvStartWriteStruct( fs, "term_criteria", CV_NODE_MAP + CV_NODE_FLOW ); - if( params.term_crit.type & CV_TERMCRIT_EPS ) - cvWriteReal( fs, "epsilon", params.term_crit.epsilon ); - if( params.term_crit.type & CV_TERMCRIT_ITER ) - cvWriteInt( fs, "iterations", params.term_crit.max_iter ); - cvEndWriteStruct( fs ); - - __END__; -} - - -void CvSVM::write( CvFileStorage* fs, const char* name ) -{ - CV_FUNCNAME( "CvSVM::write" ); - - __BEGIN__; - - int i, var_count = get_var_count(), df_count, class_count; - const CvSVMDecisionFunc* df = decision_func; - - cvStartWriteStruct( fs, name, CV_NODE_MAP, CV_TYPE_NAME_ML_SVM ); - - write_params( fs ); - - cvWriteInt( fs, "var_all", var_all ); - cvWriteInt( fs, "var_count", var_count ); - - class_count = class_labels ? class_labels->cols : - params.svm_type == CvSVM::ONE_CLASS ? 1 : 0; - - if( class_count ) - { - cvWriteInt( fs, "class_count", class_count ); - - if( class_labels ) - cvWrite( fs, "class_labels", class_labels ); - - if( class_weights ) - cvWrite( fs, "class_weights", class_weights ); - } - - if( var_idx ) - cvWrite( fs, "var_idx", var_idx ); - - // write the joint collection of support vectors - cvWriteInt( fs, "sv_total", sv_total ); - cvStartWriteStruct( fs, "support_vectors", CV_NODE_SEQ ); - for( i = 0; i < sv_total; i++ ) - { - cvStartWriteStruct( fs, 0, CV_NODE_SEQ + CV_NODE_FLOW ); - cvWriteRawData( fs, sv[i], var_count, "f" ); - cvEndWriteStruct( fs ); - } - - cvEndWriteStruct( fs ); - - // write decision functions - df_count = class_count > 1 ? class_count*(class_count-1)/2 : 1; - df = decision_func; - - cvStartWriteStruct( fs, "decision_functions", CV_NODE_SEQ ); - for( i = 0; i < df_count; i++ ) - { - int sv_count = df[i].sv_count; - cvStartWriteStruct( fs, 0, CV_NODE_MAP ); - cvWriteInt( fs, "sv_count", sv_count ); - cvWriteReal( fs, "rho", df[i].rho ); - cvStartWriteStruct( fs, "alpha", CV_NODE_SEQ+CV_NODE_FLOW ); - cvWriteRawData( fs, df[i].alpha, df[i].sv_count, "d" ); - cvEndWriteStruct( fs ); - if( class_count > 1 ) - { - cvStartWriteStruct( fs, "index", CV_NODE_SEQ+CV_NODE_FLOW ); - cvWriteRawData( fs, df[i].sv_index, df[i].sv_count, "i" ); - cvEndWriteStruct( fs ); - } - else - CV_ASSERT( sv_count == sv_total ); - cvEndWriteStruct( fs ); - } - cvEndWriteStruct( fs ); - cvEndWriteStruct( fs ); - - __END__; -} - - -void CvSVM::read_params( CvFileStorage* fs, CvFileNode* svm_node ) -{ - CV_FUNCNAME( "CvSVM::read_params" ); - - __BEGIN__; - - int svm_type, kernel_type; - CvSVMParams _params; - - CvFileNode* tmp_node = cvGetFileNodeByName( fs, svm_node, "svm_type" ); - CvFileNode* kernel_node; - if( !tmp_node ) - CV_ERROR( CV_StsBadArg, "svm_type tag is not found" ); - - if( CV_NODE_TYPE(tmp_node->tag) == CV_NODE_INT ) - svm_type = cvReadInt( tmp_node, -1 ); - else - { - const char* svm_type_str = cvReadString( tmp_node, "" ); - svm_type = - strcmp( svm_type_str, "C_SVC" ) == 0 ? CvSVM::C_SVC : - strcmp( svm_type_str, "NU_SVC" ) == 0 ? CvSVM::NU_SVC : - strcmp( svm_type_str, "ONE_CLASS" ) == 0 ? CvSVM::ONE_CLASS : - strcmp( svm_type_str, "EPS_SVR" ) == 0 ? CvSVM::EPS_SVR : - strcmp( svm_type_str, "NU_SVR" ) == 0 ? CvSVM::NU_SVR : -1; - - if( svm_type < 0 ) - CV_ERROR( CV_StsParseError, "Missing of invalid SVM type" ); - } - - kernel_node = cvGetFileNodeByName( fs, svm_node, "kernel" ); - if( !kernel_node ) - CV_ERROR( CV_StsParseError, "SVM kernel tag is not found" ); - - tmp_node = cvGetFileNodeByName( fs, kernel_node, "type" ); - if( !tmp_node ) - CV_ERROR( CV_StsParseError, "SVM kernel type tag is not found" ); - - if( CV_NODE_TYPE(tmp_node->tag) == CV_NODE_INT ) - kernel_type = cvReadInt( tmp_node, -1 ); - else - { - const char* kernel_type_str = cvReadString( tmp_node, "" ); - kernel_type = - strcmp( kernel_type_str, "LINEAR" ) == 0 ? CvSVM::LINEAR : - strcmp( kernel_type_str, "POLY" ) == 0 ? CvSVM::POLY : - strcmp( kernel_type_str, "RBF" ) == 0 ? CvSVM::RBF : - strcmp( kernel_type_str, "SIGMOID" ) == 0 ? CvSVM::SIGMOID : -1; - - if( kernel_type < 0 ) - CV_ERROR( CV_StsParseError, "Missing of invalid SVM kernel type" ); - } - - _params.svm_type = svm_type; - _params.kernel_type = kernel_type; - _params.degree = cvReadRealByName( fs, kernel_node, "degree", 0 ); - _params.gamma = cvReadRealByName( fs, kernel_node, "gamma", 0 ); - _params.coef0 = cvReadRealByName( fs, kernel_node, "coef0", 0 ); - - _params.C = cvReadRealByName( fs, svm_node, "C", 0 ); - _params.nu = cvReadRealByName( fs, svm_node, "nu", 0 ); - _params.p = cvReadRealByName( fs, svm_node, "p", 0 ); - _params.class_weights = 0; - - tmp_node = cvGetFileNodeByName( fs, svm_node, "term_criteria" ); - if( tmp_node ) - { - _params.term_crit.epsilon = cvReadRealByName( fs, tmp_node, "epsilon", -1. ); - _params.term_crit.max_iter = cvReadIntByName( fs, tmp_node, "iterations", -1 ); - _params.term_crit.type = (_params.term_crit.epsilon >= 0 ? CV_TERMCRIT_EPS : 0) + - (_params.term_crit.max_iter >= 0 ? CV_TERMCRIT_ITER : 0); - } - else - _params.term_crit = cvTermCriteria( CV_TERMCRIT_EPS + CV_TERMCRIT_ITER, 1000, FLT_EPSILON ); - - set_params( _params ); - - __END__; -} - - -void CvSVM::read( CvFileStorage* fs, CvFileNode* svm_node ) -{ - const double not_found_dbl = DBL_MAX; - - CV_FUNCNAME( "CvSVM::read" ); - - __BEGIN__; - - int i, var_count, df_count, class_count; - int block_size = 1 << 16, sv_size; - CvFileNode *sv_node, *df_node; - CvSVMDecisionFunc* df; - CvSeqReader reader; - - if( !svm_node ) - CV_ERROR( CV_StsParseError, "The requested element is not found" ); - - clear(); - - // read SVM parameters - read_params( fs, svm_node ); - - // and top-level data - sv_total = cvReadIntByName( fs, svm_node, "sv_total", -1 ); - var_all = cvReadIntByName( fs, svm_node, "var_all", -1 ); - var_count = cvReadIntByName( fs, svm_node, "var_count", var_all ); - class_count = cvReadIntByName( fs, svm_node, "class_count", 0 ); - - if( sv_total <= 0 || var_all <= 0 || var_count <= 0 || var_count > var_all || class_count < 0 ) - CV_ERROR( CV_StsParseError, "SVM model data is invalid, check sv_count, var_* and class_count tags" ); - - CV_CALL( class_labels = (CvMat*)cvReadByName( fs, svm_node, "class_labels" )); - CV_CALL( class_weights = (CvMat*)cvReadByName( fs, svm_node, "class_weights" )); - CV_CALL( var_idx = (CvMat*)cvReadByName( fs, svm_node, "comp_idx" )); - - if( class_count > 1 && (!class_labels || - !CV_IS_MAT(class_labels) || class_labels->cols != class_count)) - CV_ERROR( CV_StsParseError, "Array of class labels is missing or invalid" ); - - if( var_count < var_all && (!var_idx || !CV_IS_MAT(var_idx) || var_idx->cols != var_count) ) - CV_ERROR( CV_StsParseError, "var_idx array is missing or invalid" ); - - // read support vectors - sv_node = cvGetFileNodeByName( fs, svm_node, "support_vectors" ); - if( !sv_node || !CV_NODE_IS_SEQ(sv_node->tag)) - CV_ERROR( CV_StsParseError, "Missing or invalid sequence of support vectors" ); - - block_size = MAX( block_size, sv_total*(int)sizeof(CvSVMKernelRow)); - block_size = MAX( block_size, sv_total*2*(int)sizeof(double)); - block_size = MAX( block_size, var_all*(int)sizeof(double)); - CV_CALL( storage = cvCreateMemStorage( block_size )); - CV_CALL( sv = (float**)cvMemStorageAlloc( storage, - sv_total*sizeof(sv[0]) )); - - CV_CALL( cvStartReadSeq( sv_node->data.seq, &reader, 0 )); - sv_size = var_count*sizeof(sv[0][0]); - - for( i = 0; i < sv_total; i++ ) - { - CvFileNode* sv_elem = (CvFileNode*)reader.ptr; - CV_ASSERT( var_count == 1 || (CV_NODE_IS_SEQ(sv_elem->tag) && - sv_elem->data.seq->total == var_count) ); - - CV_CALL( sv[i] = (float*)cvMemStorageAlloc( storage, sv_size )); - CV_CALL( cvReadRawData( fs, sv_elem, sv[i], "f" )); - CV_NEXT_SEQ_ELEM( sv_node->data.seq->elem_size, reader ); - } - - // read decision functions - df_count = class_count > 1 ? class_count*(class_count-1)/2 : 1; - df_node = cvGetFileNodeByName( fs, svm_node, "decision_functions" ); - if( !df_node || !CV_NODE_IS_SEQ(df_node->tag) || - df_node->data.seq->total != df_count ) - CV_ERROR( CV_StsParseError, "decision_functions is missing or is not a collection " - "or has a wrong number of elements" ); - - CV_CALL( df = decision_func = (CvSVMDecisionFunc*)cvAlloc( df_count*sizeof(df[0]) )); - cvStartReadSeq( df_node->data.seq, &reader, 0 ); - - for( i = 0; i < df_count; i++ ) - { - CvFileNode* df_elem = (CvFileNode*)reader.ptr; - CvFileNode* alpha_node = cvGetFileNodeByName( fs, df_elem, "alpha" ); - - int sv_count = cvReadIntByName( fs, df_elem, "sv_count", -1 ); - if( sv_count <= 0 ) - CV_ERROR( CV_StsParseError, "sv_count is missing or non-positive" ); - df[i].sv_count = sv_count; - - df[i].rho = cvReadRealByName( fs, df_elem, "rho", not_found_dbl ); - if( fabs(df[i].rho - not_found_dbl) < DBL_EPSILON ) - CV_ERROR( CV_StsParseError, "rho is missing" ); - - if( !alpha_node ) - CV_ERROR( CV_StsParseError, "alpha is missing in the decision function" ); - - CV_CALL( df[i].alpha = (double*)cvMemStorageAlloc( storage, - sv_count*sizeof(df[i].alpha[0]))); - CV_ASSERT( sv_count == 1 || CV_NODE_IS_SEQ(alpha_node->tag) && - alpha_node->data.seq->total == sv_count ); - CV_CALL( cvReadRawData( fs, alpha_node, df[i].alpha, "d" )); - - if( class_count > 1 ) - { - CvFileNode* index_node = cvGetFileNodeByName( fs, df_elem, "index" ); - if( !index_node ) - CV_ERROR( CV_StsParseError, "index is missing in the decision function" ); - CV_CALL( df[i].sv_index = (int*)cvMemStorageAlloc( storage, - sv_count*sizeof(df[i].sv_index[0]))); - CV_ASSERT( sv_count == 1 || CV_NODE_IS_SEQ(index_node->tag) && - index_node->data.seq->total == sv_count ); - CV_CALL( cvReadRawData( fs, index_node, df[i].sv_index, "i" )); - } - else - df[i].sv_index = 0; - - CV_NEXT_SEQ_ELEM( df_node->data.seq->elem_size, reader ); - } - - create_kernel(); - - __END__; -} - -#if 0 - -static void* -icvCloneSVM( const void* _src ) -{ - CvSVMModel* dst = 0; - - CV_FUNCNAME( "icvCloneSVM" ); - - __BEGIN__; - - const CvSVMModel* src = (const CvSVMModel*)_src; - int var_count, class_count; - int i, sv_total, df_count; - int sv_size; - - if( !CV_IS_SVM(src) ) - CV_ERROR( !src ? CV_StsNullPtr : CV_StsBadArg, "Input pointer is NULL or invalid" ); - - // 0. create initial CvSVMModel structure - CV_CALL( dst = icvCreateSVM() ); - dst->params = src->params; - dst->params.weight_labels = 0; - dst->params.weights = 0; - - dst->var_all = src->var_all; - if( src->class_labels ) - dst->class_labels = cvCloneMat( src->class_labels ); - if( src->class_weights ) - dst->class_weights = cvCloneMat( src->class_weights ); - if( src->comp_idx ) - dst->comp_idx = cvCloneMat( src->comp_idx ); - - var_count = src->comp_idx ? src->comp_idx->cols : src->var_all; - class_count = src->class_labels ? src->class_labels->cols : - src->params.svm_type == CvSVM::ONE_CLASS ? 1 : 0; - sv_total = dst->sv_total = src->sv_total; - CV_CALL( dst->storage = cvCreateMemStorage( src->storage->block_size )); - CV_CALL( dst->sv = (float**)cvMemStorageAlloc( dst->storage, - sv_total*sizeof(dst->sv[0]) )); - - sv_size = var_count*sizeof(dst->sv[0][0]); - - for( i = 0; i < sv_total; i++ ) - { - CV_CALL( dst->sv[i] = (float*)cvMemStorageAlloc( dst->storage, sv_size )); - memcpy( dst->sv[i], src->sv[i], sv_size ); - } - - df_count = class_count > 1 ? class_count*(class_count-1)/2 : 1; - - CV_CALL( dst->decision_func = cvAlloc( df_count*sizeof(CvSVMDecisionFunc) )); - - for( i = 0; i < df_count; i++ ) - { - const CvSVMDecisionFunc *sdf = - (const CvSVMDecisionFunc*)src->decision_func+i; - CvSVMDecisionFunc *ddf = - (CvSVMDecisionFunc*)dst->decision_func+i; - int sv_count = sdf->sv_count; - ddf->sv_count = sv_count; - ddf->rho = sdf->rho; - CV_CALL( ddf->alpha = (double*)cvMemStorageAlloc( dst->storage, - sv_count*sizeof(ddf->alpha[0]))); - memcpy( ddf->alpha, sdf->alpha, sv_count*sizeof(ddf->alpha[0])); - - if( class_count > 1 ) - { - CV_CALL( ddf->sv_index = (int*)cvMemStorageAlloc( dst->storage, - sv_count*sizeof(ddf->sv_index[0]))); - memcpy( ddf->sv_index, sdf->sv_index, sv_count*sizeof(ddf->sv_index[0])); - } - else - ddf->sv_index = 0; - } - - __END__; - - if( cvGetErrStatus() < 0 && dst ) - icvReleaseSVM( &dst ); - - return dst; -} - -static int icvRegisterSVMType() -{ - CvTypeInfo info; - memset( &info, 0, sizeof(info) ); - - info.flags = 0; - info.header_size = sizeof( info ); - info.is_instance = icvIsSVM; - info.release = (CvReleaseFunc)icvReleaseSVM; - info.read = icvReadSVM; - info.write = icvWriteSVM; - info.clone = icvCloneSVM; - info.type_name = CV_TYPE_NAME_ML_SVM; - cvRegisterType( &info ); - - return 1; -} - - -static int svm = icvRegisterSVMType(); - -/* The function trains SVM model with optimal parameters, obtained by using cross-validation. -The parameters to be estimated should be indicated by setting theirs values to FLT_MAX. -The optimal parameters are saved in */ -CV_IMPL CvStatModel* -cvTrainSVM_CrossValidation( const CvMat* train_data, int tflag, - const CvMat* responses, - CvStatModelParams* model_params, - const CvStatModelParams* cross_valid_params, - const CvMat* comp_idx, - const CvMat* sample_idx, - const CvParamGrid* degree_grid, - const CvParamGrid* gamma_grid, - const CvParamGrid* coef_grid, - const CvParamGrid* C_grid, - const CvParamGrid* nu_grid, - const CvParamGrid* p_grid ) -{ - CvStatModel* svm = 0; - - CV_FUNCNAME("cvTainSVMCrossValidation"); - __BEGIN__; - - double degree_step = 7, - g_step = 15, - coef_step = 14, - C_step = 20, - nu_step = 5, - p_step = 7; // all steps must be > 1 - double degree_begin = 0.01, degree_end = 2; - double g_begin = 1e-5, g_end = 0.5; - double coef_begin = 0.1, coef_end = 300; - double C_begin = 0.1, C_end = 6000; - double nu_begin = 0.01, nu_end = 0.4; - double p_begin = 0.01, p_end = 100; - - double rate = 0, gamma = 0, C = 0, degree = 0, coef = 0, p = 0, nu = 0; - - double best_rate = 0; - double best_degree = degree_begin; - double best_gamma = g_begin; - double best_coef = coef_begin; - double best_C = C_begin; - double best_nu = nu_begin; - double best_p = p_begin; - - CvSVMModelParams svm_params, *psvm_params; - CvCrossValidationParams* cv_params = (CvCrossValidationParams*)cross_valid_params; - int svm_type, kernel; - int is_regression; - - if( !model_params ) - CV_ERROR( CV_StsBadArg, "" ); - if( !cv_params ) - CV_ERROR( CV_StsBadArg, "" ); - - svm_params = *(CvSVMModelParams*)model_params; - psvm_params = (CvSVMModelParams*)model_params; - svm_type = svm_params.svm_type; - kernel = svm_params.kernel_type; - - svm_params.degree = svm_params.degree > 0 ? svm_params.degree : 1; - svm_params.gamma = svm_params.gamma > 0 ? svm_params.gamma : 1; - svm_params.coef0 = svm_params.coef0 > 0 ? svm_params.coef0 : 1e-6; - svm_params.C = svm_params.C > 0 ? svm_params.C : 1; - svm_params.nu = svm_params.nu > 0 ? svm_params.nu : 1; - svm_params.p = svm_params.p > 0 ? svm_params.p : 1; - - if( degree_grid ) - { - if( !(degree_grid->max_val == 0 && degree_grid->min_val == 0 && - degree_grid->step == 0) ) - { - if( degree_grid->min_val > degree_grid->max_val ) - CV_ERROR( CV_StsBadArg, - "low bound of grid should be less then the upper one"); - if( degree_grid->step <= 1 ) - CV_ERROR( CV_StsBadArg, "grid step should be greater 1" ); - degree_begin = degree_grid->min_val; - degree_end = degree_grid->max_val; - degree_step = degree_grid->step; - } - } - else - degree_begin = degree_end = svm_params.degree; - - if( gamma_grid ) - { - if( !(gamma_grid->max_val == 0 && gamma_grid->min_val == 0 && - gamma_grid->step == 0) ) - { - if( gamma_grid->min_val > gamma_grid->max_val ) - CV_ERROR( CV_StsBadArg, - "low bound of grid should be less then the upper one"); - if( gamma_grid->step <= 1 ) - CV_ERROR( CV_StsBadArg, "grid step should be greater 1" ); - g_begin = gamma_grid->min_val; - g_end = gamma_grid->max_val; - g_step = gamma_grid->step; - } - } - else - g_begin = g_end = svm_params.gamma; - - if( coef_grid ) - { - if( !(coef_grid->max_val == 0 && coef_grid->min_val == 0 && - coef_grid->step == 0) ) - { - if( coef_grid->min_val > coef_grid->max_val ) - CV_ERROR( CV_StsBadArg, - "low bound of grid should be less then the upper one"); - if( coef_grid->step <= 1 ) - CV_ERROR( CV_StsBadArg, "grid step should be greater 1" ); - coef_begin = coef_grid->min_val; - coef_end = coef_grid->max_val; - coef_step = coef_grid->step; - } - } - else - coef_begin = coef_end = svm_params.coef0; - - if( C_grid ) - { - if( !(C_grid->max_val == 0 && C_grid->min_val == 0 && C_grid->step == 0)) - { - if( C_grid->min_val > C_grid->max_val ) - CV_ERROR( CV_StsBadArg, - "low bound of grid should be less then the upper one"); - if( C_grid->step <= 1 ) - CV_ERROR( CV_StsBadArg, "grid step should be greater 1" ); - C_begin = C_grid->min_val; - C_end = C_grid->max_val; - C_step = C_grid->step; - } - } - else - C_begin = C_end = svm_params.C; - - if( nu_grid ) - { - if(!(nu_grid->max_val == 0 && nu_grid->min_val == 0 && nu_grid->step==0)) - { - if( nu_grid->min_val > nu_grid->max_val ) - CV_ERROR( CV_StsBadArg, - "low bound of grid should be less then the upper one"); - if( nu_grid->step <= 1 ) - CV_ERROR( CV_StsBadArg, "grid step should be greater 1" ); - nu_begin = nu_grid->min_val; - nu_end = nu_grid->max_val; - nu_step = nu_grid->step; - } - } - else - nu_begin = nu_end = svm_params.nu; - - if( p_grid ) - { - if( !(p_grid->max_val == 0 && p_grid->min_val == 0 && p_grid->step == 0)) - { - if( p_grid->min_val > p_grid->max_val ) - CV_ERROR( CV_StsBadArg, - "low bound of grid should be less then the upper one"); - if( p_grid->step <= 1 ) - CV_ERROR( CV_StsBadArg, "grid step should be greater 1" ); - p_begin = p_grid->min_val; - p_end = p_grid->max_val; - p_step = p_grid->step; - } - } - else - p_begin = p_end = svm_params.p; - - // these parameters are not used: - if( kernel != CvSVM::POLY ) - degree_begin = degree_end = svm_params.degree; - - if( kernel == CvSVM::LINEAR ) - g_begin = g_end = svm_params.gamma; - - if( kernel != CvSVM::POLY && kernel != CvSVM::SIGMOID ) - coef_begin = coef_end = svm_params.coef0; - - if( svm_type == CvSVM::NU_SVC || svm_type == CvSVM::ONE_CLASS ) - C_begin = C_end = svm_params.C; - - if( svm_type == CvSVM::C_SVC || svm_type == CvSVM::EPS_SVR ) - nu_begin = nu_end = svm_params.nu; - - if( svm_type != CvSVM::EPS_SVR ) - p_begin = p_end = svm_params.p; - - is_regression = cv_params->is_regression; - best_rate = is_regression ? FLT_MAX : 0; - - assert( g_step > 1 && degree_step > 1 && coef_step > 1); - assert( p_step > 1 && C_step > 1 && nu_step > 1 ); - - for( degree = degree_begin; degree <= degree_end; degree *= degree_step ) - { - svm_params.degree = degree; - //printf("degree = %.3f\n", degree ); - for( gamma= g_begin; gamma <= g_end; gamma *= g_step ) - { - svm_params.gamma = gamma; - //printf(" gamma = %.3f\n", gamma ); - for( coef = coef_begin; coef <= coef_end; coef *= coef_step ) - { - svm_params.coef0 = coef; - //printf(" coef = %.3f\n", coef ); - for( C = C_begin; C <= C_end; C *= C_step ) - { - svm_params.C = C; - //printf(" C = %.3f\n", C ); - for( nu = nu_begin; nu <= nu_end; nu *= nu_step ) - { - svm_params.nu = nu; - //printf(" nu = %.3f\n", nu ); - for( p = p_begin; p <= p_end; p *= p_step ) - { - int well; - svm_params.p = p; - //printf(" p = %.3f\n", p ); - - CV_CALL(rate = cvCrossValidation( train_data, tflag, responses, &cvTrainSVM, - cross_valid_params, (CvStatModelParams*)&svm_params, comp_idx, sample_idx )); - - well = rate > best_rate && !is_regression || rate < best_rate && is_regression; - if( well || (rate == best_rate && C < best_C) ) - { - best_rate = rate; - best_degree = degree; - best_gamma = gamma; - best_coef = coef; - best_C = C; - best_nu = nu; - best_p = p; - } - //printf(" rate = %.2f\n", rate ); - } - } - } - } - } - } - //printf("The best:\nrate = %.2f%% degree = %f gamma = %f coef = %f c = %f nu = %f p = %f\n", - // best_rate, best_degree, best_gamma, best_coef, best_C, best_nu, best_p ); - - psvm_params->C = best_C; - psvm_params->nu = best_nu; - psvm_params->p = best_p; - psvm_params->gamma = best_gamma; - psvm_params->degree = best_degree; - psvm_params->coef0 = best_coef; - - CV_CALL(svm = cvTrainSVM( train_data, tflag, responses, model_params, comp_idx, sample_idx )); - - __END__; - - return svm; -} - -#endif - -/* End of file. */ -