Jump to content
  • Advertisement
Sign in to follow this  
dnaxx

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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by Veladon Fireheart
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.


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

Quote:
Original post by Veladon Fireheart
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).


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 this post


Link to post
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 this post


Link to post
Share on other sites
thanks for your suggestions.
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!