2D curve matching in OpenCV [w/ code]

Just sharing some code and ideas for matching 2D curves. I was working for a while on matching 2D curves to discover shapes in images, but it didn’t work out, what did succeed is this 2D curve matcher that seems to be very robust for certain applications. It’s based on ideas from the Heat Kernel Signature and the CSS Image (that I introduced in my latest post), all around inspecting curves under different level of smoothing.

Principle

The idea is simple, take the curve and build a “Signature Database” for it, which then you compare to another DB.
The database is essentially every possible sub-curve of the curve, under every possible offset, all normalized to the same length.
This also makes this method quite robust to occlusions! (where only part of the target curve is available)

The matching is done over the curvature of (a smoothed version of) the curve, the 2nd derivative, which was nicely explained in this paper by Mokhtarian in 2002.

Working with the functions

I created a sample app that takes in a curve (binary image with contour extracted), transforms it and then tries to find a match with the original.
But the central function is

template
void CompareCurvesUsingSignatureDB(const vector<Point_ >& a,
								   const vector<Point_ >& b,
								   int& a_len,
								   int& a_off,
								   int& b_len,
								   int& b_off,
								   double& score
								   );

It takes in any type of curve (Point, Point2f, Point2d) and returns the length and offset inside each curve of the sub-curves that best match.
You can then find a rigid transformation easily by

//assume you have vector a,b; from before
//Get matched subsets of curves
vector a_subset(a.begin() + a_off, a.begin() + a_off + a_len);
vector b_subset(b.begin() + b_off, b.begin() + b_off + b_len);
//Normalize to equal length
ResampleCurve(a_subset, a_subset, 200, true);
ResampleCurve(b_subset, b_subset, 200, true);
//Find rigid transformation
Mat trans = Find2DRigidTransform(a_subset, b_subset);
vector a_trans;
cv::transform(a_subset,a_trans,trans);

Code and salutations

Get the code at the github repo
Enjoy!
Roy.