# Hausdorff Distance between images

This topic is 4404 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello, I want to match an image A and a template B. Therefore I compare a window from A with the template (both have same dimensions) and get the Hausdorff distance. The images are edge-images (binary); a 1 represents an edge. The number of "1" between the images can differ due to occlusions or noise. I thought about using the following algorithm (pseudocode), but it's extremely CPU-intensive:
// Dimensions of the two images
widthA = widthB;
heightA = heightB;

// Generate two arrays (P_A, P_B) containing coordinates of points
// where P_A[0][0] is the x-, and P_A[0][1] is the y-coordinate for instance.
for (i=0; i<widthA; i++)
{
for (j=0; j<heightA; j++)
{
if (A[j] != 0)
AddPoint(*P_A, i,j); // Function that adds a point to the array P_A
if (B[j] != 0)
AddPoint(*P_B, i,j); // Function that adds a point to the array P_B
}
}

// Number of found points in A, B
sizeA = length(P_A);
sizeB = length(P_B);

// Calculate Hausdorff distance d(A,B)
maxDistAB = 0;
for (i=0; i<sizeA; i++)
{
minB = 1000000; // Helpervariable holding current minimum B
for (j=0; j<sizeB; j++)
{
tmpDist = sqrt((P_A[0]-P_B[j][0])^2 + (P_A[1]-P_B[j][1])^2);

if (tmpDist < minB)
{
minB = tmpDist;
}
}

maxDistAB += minB;
}
maxDistAB *= 1/widthA*heightA;

// Calculate Hausdorff distance d(B,A)
maxDistBA = 0;
for (i=0; i<sizeB; i++)
{
minA = 100000; // Helpervariable holding current minimum A
for (j=0; j<sizeA; j++)
{
tmpDist = sqrt((P_B[j][0]-P_A[0])^2 + (P_B[j][1]-P_A[1])^2);

if (tmpDist < minA)
{
minA = tmpDist;
}
}

maxDistBA += minA;
}
maxDistBA *= 1/widthA*heightA;

HausdorffDist = max(maxDistAB,maxDistBA);


Formulas: Can this algorithm be made more reliable, or are there errors in it? Thank you, [Edited by - dnaxx on July 28, 2006 2:50:22 AM]

##### Share on other sites
One thing I see:

tmpDist = sqrt((P_A[0]-P_B[j][0])^2 + (P_A[1]-P_B[j][1])^2);

I don't think this does what you want. The ^ operator in C++/Java is exclusive or, not power.

##### Share on other sites
The code above is only pseudo-code. I implemented it in C and it works (also the Hausdorff distance is correct). But the speed is not the best.

##### Share on other sites
To find out where your program is slowest, put timers around each double for loop as this is where all your CPU will be going to.
maxDistAB *= 1/widthA*heightA
This line means
maxDistAB *= (1/widthA)*heightA
not
maxDistAB *= 1/(widthA*heightA)
which is what I think you want (and the same with maxDistBA).

##### Share on other sites
Unless I missed something from a brief glance - you can move the sqrts outside the loops. Also check that the compiler is inlining/optimising the (P_A[0]-P_B[j][0])^2 type lines - it might be better to write that as a single inline expression that definitely avoids temporaries.

##### Share on other sites
Yep, definately move that sqrt out of the inner loops, just find the min of the squared distances and do the sqrt once you have the min not only does this remove the expensive sqrt but it lets keep everything in the inner loop as integer math.

Also, how does AddPoint() work? Make sure you're not doing anything silly like dynamically resizing the array, just reserve the maximum possible size (ie. widthA*heightA) to begin with.

##### Share on other sites
Quote:
 Original post by Veladon FireheartTo find out where your program is slowest, put timers around each double for loop as this is where all your CPU will be going to.

Umm, it's fairly obvious the slowest part is the inner loops with the sqrt's.

Quote:
 Original post by Veladon FireheartmaxDistAB *= 1/widthA*heightAThis line meansmaxDistAB *= (1/widthA)*heightAnotmaxDistAB *= 1/(widthA*heightA)which is what I think you want (and the same with maxDistBA).

Since there's no way it would work either way with integer math he must be using floating point there, in which case I doubt the precision difference between the 2 would matter. And besides, its only pseudocode.

##### Share on other sites
@joanusdmentia,
The precision difference? Say widthA = heightA = 10, then (1/10)*10 = 1 whereas 1/(10*10) = 1/100. I'd call that quite a big difference.

##### Share on other sites
Quote:
 Original post by Veladon Fireheart@joanusdmentia, The precision difference? Say widthA = heightA = 10, then (1/10)*10 = 1 whereas 1/(10*10) = 1/100. I'd call that quite a big difference.

Ah crap, my bad [smile] No idea where my brain was on that one.....

##### Share on other sites
The most performance is used by this part:
helperX = (P_A[0]-P_B[j][0]);helperY = (P_A[1]-P_B[j][1]);tmpDist = helperX*helperX + helperY*helperY;//tmpDist = pow(helperX,2) + pow(helperY,2);

The pow-function* from "math.h" is even slower than "normal" multiplication.

1. 1
2. 2
JoeJ
20
3. 3
frob
18
4. 4
5. 5

• 10
• 11
• 12
• 13
• 9
• ### Forum Statistics

• Total Topics
632204
• Total Posts
3004755

×