Simple Shape Matching with kNearest and OpenCV

May 27th, 2013

Here is a short demo of how to do a simple shape matching using the “K Nearest Neighbors” algorithm implementation that comes with OpenCV 2.4.

The process of recognition is very simple, first you need to convert some shapes to a sets of points. Then you must train and label the kNearest class with the point sets. Then you could draw some points to the screen and use the find_nearest() function to see which label does the drawn point set will match best.

Here are some code snippets for every task above:

Convert image to a point set

vector<cv::Point> points;
ofImage im;


cv::Mat original;
original = ofxCv::toCv(im).clone();

// 1-channel convert
if(original.channels() == 3) {
	cv::cvtColor(original, original, CV_RGB2GRAY);
} else if(original.channels() == 4) {
	cv::cvtColor(original, original, CV_RGBA2GRAY);

cv::Canny(original, original, 0, 100.0);

cv::Mat dilateKernel(cv::Size(3,3), CV_8UC1, cv::Scalar(1));
cv::dilate(original, original, dilateKernel);
vector<vector<cv::Point> > foundc;
cv::findContours(original, foundc,CV_RETR_EXTERNAL, CV_CHAIN_APPROX_NONE, cv::Point(0,0));
if(foundc.size() >0) {
	points = foundc[0];

Training kNearest

cv::KNearest *knn;

cv::Mat trainingData(points.size(), 2, CV_32FC1);
cv::Mat trainingClasses(points.size(), 1, CV_32FC1);

// we fill the training data with the points set
// if we have couple of shapes, we must fill all points into one trainingData set
// and label accordingly

for(int i=0;i<points.size();i++) {<float>(i,0) = points[i].x;<float>(i,1) = points[i].y;<float>(i,0) = 1; // we label the shape as "1", the next added shape point set should be labeled as "2" and etc.
// train the algorithm
knn = new kNearest(trainingData, trainingClasses);

Find Matches

// points that are drawn on screen
vector<cv::Point> drawnPoints;

cv::Mat testData(drawnPoints.size(),2,CV_32FC1);
for(int i=0;i<drawnPoints.size();i++) {<float>(i,0) = drawnPoints[i].x;<float>(i,0) = drawnPoints[i].y;

// found will return the label that is closer to the drawn points
int found = knn->find_nearest(testData,1);

You could check out a working example at: