K-nearest neighbors (KNN) is one of the simplest classifiers. It is a supervised classification method, which learns from available cases and classifies new cases by a minimum distance. K is the number of neighbors to be analyzed in the decision. The new data point to classify (the query) is projected to the same space as the learning points, and its class is given by the most frequent class among its KNN from the training set.
The following KNNClassifier code is an example of using the KNN algorithm to classify each image pixel to the nearest color: black (0, 0, 0), white (255, 255, 255), blue (255, 0, 0), green (0, 255, 0), or red (0, 0, 255):
#include <iostream> #include <opencv2/core/core.hpp> #include <opencv2/highgui/highgui.hpp> #include <opencv2/ml/ml.hpp> using namespace std; using namespace cv; int main(int argc, char *argv[]){ //Create Mat for the training set and classes Mat classes(5, 1, CV_32FC1); Mat colors(5, 3, CV_32FC1); //Training set (primary colors) colors.at<float>(0,0)=0, colors.at<float>(0,1)=0, colors.at<float>(0,2)=0; colors.at<float>(1,0)=255, colors.at<float>(1,1)=255, colors.at<float>(1,2)=255; colors.at<float>(2,0)=255, colors.at<float>(2,1)=0, colors.at<float>(2,2)=0; colors.at<float>(3,0)=0, colors.at<float>(3,1)=255, colors.at<float>(3,2)=0; colors.at<float>(4,0)=0, colors.at<float>(4,1)=0, colors.at<float>(4,2)=255; //Set classes to each training sample classes.at<float>(0,0)=1; classes.at<float>(1,0)=2; classes.at<float>(2,0)=3; classes.at<float>(3,0)=4; classes.at<float>(4,0)=5; //KNN classifier (k=1) CvKNearest classifier; classifier.train(colors,classes,Mat(),false,1,false); //Load original image Mat src=imread("baboon.jpg",1); imshow("baboon",src); //Create result image Mat dst(src.rows , src.cols, CV_8UC3); Mat results; Mat newPoint(1,3,CV_32FC1); //Response for each pixel and store the result in the result image float prediction=0; for(int y = 0; y < src.rows; ++y){ for(int x = 0; x < src.cols; ++x){ newPoint.at<float>(0,0)= src.at<Vec3b>(y, x)[0]; newPoint.at<float>(0,1) = src.at<Vec3b>(y, x)[1]; newPoint.at<float>(0,2) = src.at<Vec3b>(y, x)[2]; prediction=classifier.find_nearest(newPoint,1,&results, 0, 0); dst.at<Vec3b>(y, x)[0]= colors.at<float>(prediction-1,0); dst.at<Vec3b>(y, x)[1]= colors.at<float>(prediction-1,1); dst.at<Vec3b>(y, x)[2]= colors.at<float>(prediction-1,2); } } //Show result image cv::imshow("result KNN",dst); cv::waitKey(0); return 0; }
OpenCV provides the KNN algorithm through the CvKNearest class. The training information is added to the KNN classifier through the bool CvKNearest::train(const Mat& trainData, const Mat& responses, const Mat& sampleIdx, bool isRegression, int maxK, bool updateBase) function. The example creates a training set with five samples, (Mat colors(5, 3, CV_32FC1)), which represent each class (color) (Mat classes(5, 1, CV_32FC1)); these are the first two input parameters. The isRegression is parameter is a Boolean value that defines whether we want to perform a classification or a regression. The maxK value indicates the maximum number of neighbors that will be used in the test phase.
Finally, updateBaseparameter allows us to indicate whether we want to train a new classifier with the data or use it to update the previous training data. Then, the code sample performs the test phase with each pixel of the original image using the float CvKNearest::find_nearest(const Mat& samples, int k, Mat* results=0, const float** neighbors=0, Mat* neighborResponses=0, Mat* dist=0) function. The function tests the input sample, selecting the KNN, and finally predicts the class value for this sample.
In the following screenshot, we can see the code output and the difference between the original and the result images after this KNN classification:
KNN classification using the primary colors as classes (left: the original image, right: the result image)