Code covered by the BSD License

### Highlights from Hausdorff Distance

4.61538
4.6 | 13 ratings Rate this file 81 Downloads (last 30 days) File Size: 4.22 KB File ID: #26738 Version: 1.6

# Hausdorff Distance

### Zachary Danziger (view profile)

19 Feb 2010 (Updated )

Calculates the Hausdorff Distance between two sets of points in a Euclidean metric space.

File Information
Description

The Hausdorff Distance is a mathematical construct to measure the "closeness" of two sets of points that are subsets of a metric space.

Such a measure may be used to assign a scalar score to the similarity between two trajectories, data clouds or any sets of points.

This function will return the Hausdorff Distance between two sets of points.

Acknowledgements

Hausdorff Distance inspired this file.

This file inspired Modified Hausdorff Distance and *Mex* Modified Hausdorff Distance For 2 D Point Sets.

MATLAB release MATLAB 7.8 (R2009a)
11 Jul 2016 ggyyree

### ggyyree (view profile)

Hi Zachary，

Just a couple of quick questions:

1. Will your implementation OK with 3D data points? For example, I have got two sets of 3D data points represented by vertices (x, y, z) and (x', y', z'). Will this implementation be able to handle this?

2. I found another implementation at
http://uk.mathworks.com/matlabcentral/fileexchange/29968-modified-hausdorff-distance

However, the results given by this one are different from your implementation. Could you please comment on this?

Thanks so much for your fantastic work.

09 Jun 2016 Son Nguyen

### Son Nguyen (view profile)

Hi Zachary.

What I mean is that one can use the coordinate of a point to be the set. For instance, the point (1,2,3) will turn into the set {1,2,3} -- the set consisting of the coordinates.

So using that idea, I would like to see which set is a distance of d away from a point P = (a,b,c) that I input. [I only want to take points in space.]

Comment only
07 Jun 2016 Zachary Danziger

### Zachary Danziger (view profile)

@Son: The Hausdorff distance between two points will be the the same as the "regular" Euclidean distance. The Hausdorff distance becomes useful when you compare two sets of points.

Comment only
07 Jun 2016 Son Nguyen

### Son Nguyen (view profile)

Hi.

I am new to Matlab. Can someone assist me on how to use this program?

Basically what I would like to do is I want to put in a point in space, say (0,0,0), and specify the maximum distance, say 5. I would like to find all points in space whose Hausdorff distance to the origin is at most 5.

Comment only

All the warnings could be avoided by adding comma between the output arguments. [a b] --> [a,b].

09 Dec 2015 Zachary Danziger

### Zachary Danziger (view profile)

@Duc Fehr Thanks for the input, this could be really useful. I haven't worked with with parallelizing MATLAB computations very much.

Comment only
08 Dec 2015 Duc Fehr

### Duc Fehr (view profile)

Very nice piece of code. I am wondering if this change is possible: l91-l110, making use of the parallel computation. I realize that sometimes a vector of length sP(1) or sQ(1) might still be too big too save, but there is a big difference between a matrix of size sP(1)*sQ(1) and a vector those individual length.

minP = zeros(1,sP(1));
parfor p = 1:sP(1)
% calculate the minimum distance from points in P to Q
minP(p) = min(sum( bsxfun(@minus,P(p,:),Q).^2, 2));
end
maxP = max(minP);

% repeat for points in Q
minQ = zeros(1,sQ(1));
parfor q = 1:sQ(1)
minQ(q) = min(sum( bsxfun(@minus,Q(q,:),P).^2, 2));
end
maxQ = max(minQ);

21 Nov 2015 wang

### wang (view profile)

i want calculate Hausdorff distance between two index images!!!

07 Sep 2015 siwar chniti

### siwar chniti (view profile)

please I need a code to calculate Hausdorff distance between two binary images!!!

Comment only
29 Jan 2015 Zachary Danziger

### Zachary Danziger (view profile)

@Yunus, Your question is a bit ambiguous. As written, the code will interpret your input sets as having one 2-dimensional point each, in which case we do expect a non-zero HD because the points are different, and in fact, are different precisely by their Euclidean distance. If you are interested in comparing sets with two 1-dimensional points each you need to transpose your inputs. Rows are treated as observations and columns as dimensions.

hd = HausdorffDist([1 2],[2 1]) -> 1.41
hd = HausdorffDist([1 2]',[2 1]') -> 0

Comment only
29 Jan 2015 Yunus Emre

### Yunus Emre (view profile)

Very useful code indeed. I have a question :

Assume that we have two sets, i.e {1,2} and {2,1}. The Hausdorff distance between these two sets are zero. However, in the code we got the value of Euclidean distance between points. Am I wrong?

06 Nov 2014 Zachary Danziger

### Zachary Danziger (view profile)

@Shaan, One way would be to treat those images as vectors of pixels, and use the code on those vectors, however, many more nuanced implementations of HD for image comparison have been developed.

Comment only
06 Nov 2014 Shaan

### Shaan (view profile)

How do you use this code to calculate Hausdorff distance between two binary images?

Comment only

It is great code, but you need to fix your bugs: in order to achieve the same column for your both images, you can fix number of columns with the following codes:

nrows = max(size(I1,1), size(I2,1));
ncols = max(size(I1,2), size(I2,2));
nchannels = size(I1,3);

extendedI1 = [ I1, zeros(size(I1,1), ncols-size(I1,2), nchannels); ...
zeros(nrows-size(I1,1), ncols, nchannels)];

extendedI2 = [ I2, zeros(size(I2,1), ncols-size(I2,2), nchannels); ...
zeros(nrows-size(I2,1), ncols, nchannels)];

I1=extendedI1;
I2=extendedI2;

Also, Binary images don't give us the minimum numbers for Hausdorff Distance. I checked your codes with several binary images and all of the times the max Hausdorff Distance numbers were the correct answer, not the minimum number.

08 Feb 2014 Venkat R

### Venkat R (view profile)

Very fast and useful submission.
Works well for me. Thank you

09 Jan 2014 Pramit Mazumdar

### Pramit Mazumdar (view profile)

Hi,
I am having two vectors consisting of sequential locations visited by person-X and Y like:

X = [ (lat1,long1), (lat2,long2), (lat3,long3) ];

Y = [ (lat4,long4), (lat2,long2), (lat3,long3) ];

I need to find similarity between these two vectors. Can this Hausdorff distance help me in any way??

07 Aug 2013 Nejc Ilc

### Nejc Ilc (view profile)

03 Oct 2012 Zachary Danziger

### Zachary Danziger (view profile)

Roel H,
Agreed on both counts. The code has been updated and re-posted. Doing some quick testing, the updates you recommended significantly improve speed for very large matrices, thank you.

Comment only
25 Sep 2012 Roel H

### Roel H (view profile)

Nice code, thanks for writing this function!

Though I have a few remarks. For the largeMat case, it is better to use bsxfun instead of repmat, as it is more efficient(faster) for large matrices which obviously is the case. Also it may be an idea to postpone the "sqrt" call untill a maximum is found. This won't change the outcome, but should require less computations

%existing code:
minP = min(sqrt(sum((repmat(P(p,:),[sQ(1) 1]) - Q).^2,2)));
%sugestion:
minP = min(sum((bsxfun(@minus,P(p,:),Q)).^2,2));

30 Apr 2012 Zachary Danziger

### Zachary Danziger (view profile)

It was brought to my attention by Roey Baror of Tel-Aviv University that creating/outputting a matrix of distances between all points could quickly tax the system's memory for large matrices, such as high resolution images. The update provides a secondary algorithm to calculate the Hausdorff Distance without storing the large matrix in memory, and detects automatically when this secondary algorithm is necessary.

Comment only
24 Mar 2012 s_ppu

### s_ppu (view profile)

12 Jul 2011 longan

### longan (view profile)

07 Jan 2011 SasiKanth

### SasiKanth (view profile)

Nice code and well commented to!

28 May 2010 1.1

Edits Added the matrix of distances as an output option. Fixed a bug that would cause an error if one of the sets was a single point. Removed excess calls to "size" and "length". - May 2010

15 Jun 2010 1.2

Generalizes the code to allow N-dimensional point sets. This update is inspired by file 27905, which has a good implementation of HD beyond 2-D sets of points.

30 Apr 2012 1.3

The code now automatically switches to a secondary algorithm when there is insufficient memory to compute and store a matrix containing distances between all constituent points. It also allows the user to manually choose the desired algorithm.

04 Oct 2012 1.4

Based on user comments, the algorithm for large data sets was updated for performance.

03 Apr 2013 1.6

An option for data visualization is now included.