# 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;
}

edit retag close merge delete

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() ?

( 2017-10-09 00:59:47 -0500 )edit

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?

( 2017-10-09 03:06:04 -0500 )edit

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.

( 2017-10-09 03:09:16 -0500 )edit

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?

( 2017-10-09 03:18:26 -0500 )edit

oh, wait, ignore, what i said, it's probably all wrong.

(needs some more thinking..:)

( 2017-10-09 03:34:30 -0500 )edit

@StevenPuttemans what's your take on this?

( 2017-10-11 07:53:27 -0500 )edit

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.

( 2017-10-11 08:32:54 -0500 )edit

@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

( 2017-10-19 09:04:23 -0500 )edit
1

@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           B  C


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 :)

( 2017-10-19 09:40:23 -0500 )edit

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?

( 2017-10-19 10:30:53 -0500 )edit

Sort by ยป oldest newest most voted

I finally managed to solve this problem and this is how I went about doing it.

1. I translated my contours back to the origin.
2. Then I rotated them about the origin to match the alignment of my template image.
3. Implemented the brute-force Hausdorff distance as illustrated here and allowed contours which passed my set threshold.

My new Hausdorff distance implementation looked like this:

int distance(vector<Point>const& image, vector<Point>const& tempImage)
{
int totalDistance = 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;
}

if(minDistance > totalDistance) totalDistance = minDistance;
}
}


With regards to scale, that's where the image pyramids came into play. Turned out the slidingWindows were entirely useless.

Aside from the first two steps, the previous Hausdorff Distance implementation was not working for me at all. Why you might ask?

1. The maxDistance += minDistance part was just killing me. I was getting huge values as my distance even though my frame size was nowhere close to being that huge. Distances north of 3k were the norm.
2. When comparing two equal images, granted it gave me a 0 for the one contour that matched perfectly but the next closest contour had a value of 28.5657 followed by 358.049. With the revised version, the perfect match had a 0, then followed by 4.12311 then 50.04.
3. The revised version made it easier and sensible to even set a threshold for qualifying contours.

With that said, I am still learning so before down voting, please point out my mistake so I can learn from it.

EDIT I

After performing multiple tests, I observed two things

1. Without +=, the detection work just fine when the camera is pointed directly at the object.
2. += worked best even with weird camera angles but the thresholding is still tricky.

Thanks to @berak, I finally caved in to +=

more

so, youre only retaining the best distance between 2 single points from A and B.

that's not, what the spec says (imho).

(don't get me wrong, improvements can only happen, if you're bold enough to leave the trodden path)

((just double-check with some entirely unrelated images/samples, make sure you're not cheating yourself with something, that only works with your current data))

( 2017-10-23 14:09:05 -0500 )edit

@berak Sorry for the delay in getting back.. I real-timed it and actually with the +=, it works way better especially at weird angles. I'll update my answer to reflect this. Thanks a lot buddy!!!!

( 2017-10-26 11:23:13 -0500 )edit
1

apart from hausdorff, see also: shapecontexts, fourier descriptors, sampsonDistance, 1$shape reco ( 2017-10-26 12:06:21 -0500 )edit What is 1$ shape reco? Was it a typo? Or is there a method out there literally called 1 dollar shape reco?

( 2017-10-26 14:12:10 -0500 )edit

the latter, 1 dollar shape recognition (as in : being cheap)

( 2017-10-26 14:14:27 -0500 )edit

Official site

GitHub

Wiki

Documentation