Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Two sided Hausdorff distance is calculated as

$$H(r_1,r_2)=\max\{h(r_1,r_2),h(r_2,r_1)\}$$

where

$$h(r_1,r_2)=\max_{a \in r_1}\min_{b\in r_2}\|r_1-r_2\|$$ and vice-verse

$r_1$ and $r_2$ are two non empty, finite sets

This when programmed will take $O(n^2)$ time

Is there a better algorithm so that the time complexity is reduced? I need this to use in my project for finding the diffence between two images

share|improve this question
    
What is the norm here? are the objects in $r$ vectors? in what space? what dimension? –  Bitwise Oct 19 '12 at 18:52
    
r is a 2D array or a 2D matrix of binary image, hence i will be calculating the Hausdorff Distance using the position of the pixels rather than the value of the pixels. –  Yash Oct 19 '12 at 18:59
add comment

2 Answers

up vote 2 down vote accepted

Suppose you know both sets are in, say, a square of side $L$. I'm assuming you're using Euclidean distance, but other metrics will be similar. Break up the square into $m^2$ small squares of side $L/m$ and see which small squares contain members of each set. If for every small square that contains members of one set, that square or one of its 8 neighbours contains a member if the other set, you know the Hausdorff distance is at most $2 \sqrt{2} L/m$. On the other hand, if there is a small square that contains members of $r_1$ and neither it nor any of its neighbours contains members of $r_2$, you know that the Hausdorff distance is at least the distance from the square to the closest other small square that contains members of $r_2$. These estimates can then be refined by subdividing the relevant small squares.

share|improve this answer
    
Thank you very much. I will apply this. And I will be using Taxi Cab distance instead of Euclidean distance but as you stated, it will be similar. –  Yash Oct 19 '12 at 19:31
add comment

This answer is biased towards computer programming than mathematics but I could achieve my intended goal: "Reduction in computation time for Hausdorff Distance"

The answer is SIMD technology. I coded this problem using OpenCL on Python by following all your advices. Thank you all for helping me. The complexity is unaltered but the execution time is significantly reduced due to massive parallelism.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.