OpenCV Tutorials —— Introduction to Support Vector Machines

支持向量机 ~~

How is the optimal hyperplane computed?

Let’s introduce the notation used to define formally a hyperplane:

where is known as the weight vector and as the bias.

 

The optimal hyperplane can be represented in an infinite number of different ways by scaling of and . As a matter of convention, among all the possible representations of the hyperplane, the one chosen is

where symbolizes the training examples closest to the hyperplane. In general, the training examples that are closest to the hyperplane are called support vectors. This representation is known as the canonical hyperplane.

Now, we use the result of geometry that gives the distance between a point and a hyperplane :

In particular, for the canonical hyperplane, the numerator is equal to one and the distance to the support vectors is

Recall that the margin introduced in the previous section, here denoted as , is twice the distance to the closest examples:

Finally, the problem of maximizing is equivalent to the problem of minimizing a function subject to some constraints. The constraints model the requirement for the hyperplane to classify correctly all the training examples . Formally,

where represents each of the labels of the training examples.

This is a problem of Lagrangian optimization that can be solved using Lagrange multipliers to obtain the weight vector and the bias of the optimal hyperplane.

float labels[4] = {1.0, -1.0, -1.0, -1.0};
float trainingData[4][2] = {{501, 10}, {255, 10}, {501, 255}, {10, 501}};
Mat trainingDataMat(3, 2, CV_32FC1, trainingData);
Mat labelsMat      (3, 1, CV_32FC1, labels);

The function CvSVM::train that will be used afterwards requires the training data to be stored as Mat objects of floats.  数组转Mat

CvSVMParams params;
params.svm_type    = CvSVM::C_SVC;
params.kernel_type = CvSVM::LINEAR;
params.term_crit   = cvTermCriteria(CV_TERMCRIT_ITER, 100, 1e-6);

The methodCvSVM::get_support_vector_count outputs the total number of support vectors used in the problem and with the method CvSVM::get_support_vector we obtain each of the support vectors using an index.

Code

#include "stdafx.h"

#include <opencv2/core/core.hpp>
#include <opencv2/highgui/highgui.hpp>
#include <opencv2/ml/ml.hpp>

using namespace cv;

int main()
{
	// Data for visual representation
	int width = 512, height = 512;
	Mat image = Mat::zeros(height, width, CV_8UC3);

	// Set up training data
	float labels[4] = {1.0, -1.0, -1.0, -1.0};
	Mat labelsMat(4, 1, CV_32FC1, labels);

	float trainingData[4][2] = { {501, 10}, {255, 10}, {501, 255}, {10, 501} };
	Mat trainingDataMat(4, 2, CV_32FC1, trainingData);

	// Set up SVM‘s parameters
	CvSVMParams params;
	params.svm_type    = CvSVM::C_SVC;
	params.kernel_type = CvSVM::LINEAR;	// 不对训练数据进行映射
	params.term_crit   = cvTermCriteria(CV_TERMCRIT_ITER, 100, 1e-6);	// 迭代终止条件，在迭代中完成二次优化

	// Train the SVM
	CvSVM SVM;
	SVM.train(trainingDataMat, labelsMat, Mat(), Mat(), params);

	Vec3b green(0,255,0), blue (255,0,0);
	// Show the decision regions given by the SVM
	for (int i = 0; i < image.rows; ++i)
		for (int j = 0; j < image.cols; ++j)
		{
			Mat sampleMat = (Mat_<float>(1,2) << j,i);	// 每个像素点都进行predict
			float response = SVM.predict(sampleMat);

			if (response == 1)
				image.at<Vec3b>(i,j)  = green;
			else if (response == -1)
				image.at<Vec3b>(i,j)  = blue;
		}

		// Show the training data
		int thickness = -1;
		int lineType = 8;
		circle( image, Point(501,  10), 5, Scalar(  0,   0,   0), thickness, lineType);
		circle( image, Point(255,  10), 5, Scalar(255, 255, 255), thickness, lineType);
		circle( image, Point(501, 255), 5, Scalar(255, 255, 255), thickness, lineType);
		circle( image, Point( 10, 501), 5, Scalar(255, 255, 255), thickness, lineType);

		// Show support vectors
		thickness = 2;
		lineType  = 8;
		int c     = SVM.get_support_vector_count();

		for (int i = 0; i < c; ++i)
		{
			const float* v = SVM.get_support_vector(i);
			circle( image,  Point( (int) v[0], (int) v[1]),   6,  Scalar(128, 128, 128), thickness, lineType);
		}

		imwrite("result.png", image);        // save the image

		imshow("SVM Simple Example", image); // show it to the user
		waitKey(0);

}