Hausdorff Distance Object Detection
I have been struggling trying to implement the outlining algorithm described here and here.
The general idea of the paper is determining the Hausdorff distance of binary images and using it to find the template image from a test image.
For template matching, it is recommended to construct image pyramids along with sliding windows which you'll use to slide over your test image for detection. I was able to do both of these as well.
I am stuck on how to move forward from here on. Do I slide my template over the test image from different pyramid layers? Or is it the test image over the template? And with regards to the sliding window, is/are they meant to be a ROI of the test or template image?
In a nutshell, I have pieces to the puzzle but no idea of which direction to take to solve the puzzle
int distance(vector<Point>const& image, vector<Point>const& tempImage)
{
int maxDistance = 0;
for(Point imagePoint: image)
{
int minDistance = numeric_limits<int>::max();
for(Point tempPoint: tempImage)
{
Point diff = imagePoint - tempPoint;
int length = (diff.x * diff.x) + (diff.y * diff.y);
if(length < minDistance) minDistance = length;
if(length == 0) break;
}
maxDistance += minDistance;
}
return maxDistance;
}
double hausdorffDistance(vector<Point>const& image, vector<Point>const& tempImage)
{
double maxDistImage = distance(image, tempImage);
double maxDistTemp = distance(tempImage, image);
return sqrt(max(maxDistImage, maxDistTemp));
}
vector<Mat> buildPyramids(Mat& frame)
{
vector<Mat> pyramids;
int count = 6;
Mat prevFrame = frame, nextFrame;
while(count > 0)
{
resize(prevFrame, nextFrame, Size(), .85, .85);
prevFrame = nextFrame;
pyramids.push_back(nextFrame);
--count;
}
return pyramids;
}
vector<Rect> slidingWindows(Mat& image, int stepSize, int width, int height)
{
vector<Rect> windows;
for(size_t row = 0; row < image.rows; row += stepSize)
{
if((row + height) > image.rows) break;
for(size_t col = 0; col < image.cols; col += stepSize)
{
if((col + width) > image.cols) break;
windows.push_back(Rect(col, row, width, height));
}
}
return windows;
}
it's all about comparing contours, right ?
so i don't think, you need image pyramids, far too expensive, and you'd also have to re-sample the contours from that.
just scale the template contour, instead.
how do you sample your Points ? findContours() ?
Yes. Its about contours comparison. I just didn't put it here but I do find and save the template contours. What do you mean by scale the template contour?
multiply the points by a scale factor (shrink the contour) instead of resizing the image, and finding new points.
" Do I slide my template over the test image from different pyramid layers?" -- i think, that is meant in the links you gave.
Just to make sure I understood you, I should just iterate over the template contours through different scale factors (say diving them in quarters up to 6 times) then just comparing them with the test image contours and finding the best match after the 6 iterations?
oh, wait, ignore, what i said, it's probably all wrong.
(needs some more thinking..:)
@StevenPuttemans what's your take on this?
I am not sure, that is why I did not reply yet. Also never heared of the approach and not in the possibility of putting time into reading the publication now.
@berak I looked at your implementation of Hausdorff distance and was wondering why you were adding the minimum distances. Arean't you just supposed to compute and assign them? At least according to this
@eshirima, what about (eq. 2/3) ?
"why you were adding the minimum distances" -- that's the computation of the (L2) vector distance, right ? sum over the square of the (minimum) components. for each point in A, find the closest in B. then sum that up, resulting in a single number for a (directed) comparison between A and B.
and "maxDistAB" is indeed a misnomer, should be "minDistAB"
hausdorff is simply: take minimum distance from a to b, and from b to a, and use the max of the two. it solves this problem:
A's closest neighbour is B, but B's closest neighbour is C, not A, it's not reciprocal, that's why we have to look at it from both directions, and the hausdorff distance is using the "worst case assumption" as measure. (minimizing the pessimism - pure genius :)
Hahahaha... I totally agree with you. But with that in mind, doesn't it mean that if you take an exact copy of the same template image and compare their edges then you should get a Hausdorff distance of 0?