From a06af5ca250e31840a3e8b86f8d1de3500585137 Mon Sep 17 00:00:00 2001
From: Vadim Pisarevsky <vadim.pisarevsky@gmail.com>
Date: Tue, 19 Mar 2013 18:28:17 +0400
Subject: [PATCH] dramatic speedup of SVM::predict in the case of linear SVM

---
 modules/ml/include/opencv2/ml/ml.hpp |  2 ++
 modules/ml/src/svm.cpp               | 55 ++++++++++++++++++++++++++++++++++++
 samples/cpp/letter_recog.cpp         |  3 ++
 3 files changed, 60 insertions(+)

diff --git a/modules/ml/include/opencv2/ml/ml.hpp b/modules/ml/include/opencv2/ml/ml.hpp
index dc7a404..6612d2e 100644
--- a/modules/ml/include/opencv2/ml/ml.hpp
+++ b/modules/ml/include/opencv2/ml/ml.hpp
@@ -534,6 +534,8 @@ protected:
     virtual void write_params( CvFileStorage* fs ) const;
     virtual void read_params( CvFileStorage* fs, CvFileNode* node );
 
+    void optimize_linear_svm();
+
     CvSVMParams params;
     CvMat* class_labels;
     int var_all;
diff --git a/modules/ml/src/svm.cpp b/modules/ml/src/svm.cpp
index 9cbc46b..3c970f2 100644
--- a/modules/ml/src/svm.cpp
+++ b/modules/ml/src/svm.cpp
@@ -1517,6 +1517,7 @@ bool CvSVM::do_train( int svm_type, int sample_count, int var_count, const float
         }
     }
 
+    optimize_linear_svm();
     ok = true;
 
     __END__;
@@ -1524,6 +1525,59 @@ bool CvSVM::do_train( int svm_type, int sample_count, int var_count, const float
     return ok;
 }
 
+
+void CvSVM::optimize_linear_svm()
+{
+    // we optimize only linear SVM: compress all the support vectors into one.
+    if( params.kernel_type != LINEAR )
+        return;
+
+    int class_count = class_labels ? class_labels->cols :
+            params.svm_type == CvSVM::ONE_CLASS ? 1 : 0;
+
+    int i, df_count = class_count > 1 ? class_count*(class_count-1)/2 : 1;
+    CvSVMDecisionFunc* df = decision_func;
+
+    for( i = 0; i < df_count; i++ )
+    {
+        int sv_count = df[i].sv_count;
+        if( sv_count != 1 )
+            break;
+    }
+
+    // if every decision functions uses a single support vector;
+    // it's already compressed. skip it then.
+    if( i == df_count )
+        return;
+
+    int var_count = get_var_count();
+    int sample_size = (int)(var_count*sizeof(sv[0][0]));
+    float** new_sv = (float**)cvMemStorageAlloc(storage, df_count*sizeof(new_sv[0]));
+
+    for( i = 0; i < df_count; i++ )
+    {
+        new_sv[i] = (float*)cvMemStorageAlloc(storage, sample_size);
+        float* dst = new_sv[i];
+        memset(dst, 0, sample_size);
+        int j, k, sv_count = df[i].sv_count;
+        for( j = 0; j < sv_count; j++ )
+        {
+            const float* src = class_count > 1 ? sv[df[i].sv_index[j]] : sv[j];
+            double a = df[i].alpha[j];
+            for( k = 0; k < var_count; k++ )
+                dst[k] = (float)(dst[k] + src[k]*a);
+        }
+        df[i].sv_count = 1;
+        df[i].alpha[0] = 1.;
+        if( class_count > 1 )
+            df[i].sv_index[0] = i;
+    }
+
+    sv = new_sv;
+    sv_total = df_count;
+}
+
+
 bool CvSVM::train( const CvMat* _train_data, const CvMat* _responses,
     const CvMat* _var_idx, const CvMat* _sample_idx, CvSVMParams _params )
 {
@@ -2516,6 +2570,7 @@ void CvSVM::read( CvFileStorage* fs, CvFileNode* svm_node )
         CV_NEXT_SEQ_ELEM( df_node->data.seq->elem_size, reader );
     }
 
+    optimize_linear_svm();
     create_kernel();
 
     __END__;
diff --git a/samples/cpp/letter_recog.cpp b/samples/cpp/letter_recog.cpp
index 49a55fc..144dbe8 100644
--- a/samples/cpp/letter_recog.cpp
+++ b/samples/cpp/letter_recog.cpp
@@ -691,7 +691,10 @@ int build_svm_classifier( char* data_filename )
     CvMat *result = cvCreateMat(1, nsamples_all - ntrain_samples, CV_32FC1);
 
     printf("Classification (may take a few minutes)...\n");
+    double t = (double)cvGetTickCount();
     svm.predict(&sample, result);
+    t = (double)cvGetTickCount() - t;
+    printf("Prediction type: %gms\n", t/(cvGetTickFrequency()*1000.));
 
     int true_resp = 0;
     for (int i = 0; i < nsamples_all - ntrain_samples; i++)
-- 
2.7.4