computing star: One dimension minimum Hausdorff distance

Hausdorff distance可以用來量測兩個sets之間的距離，如果將其中一個set的元素全部加(減)上t個單位，則兩個sets之間的Hausdorff distance可能會變小或變大。實際的應用，假設我們要做影像的比對，有一張影像為template，而另一張影像是準備要和template比對的圖片，若能夠讓兩張圖片儘量對齊，則能夠提高辨識的淮確度。

my meeting report

我在IPL Vol 106(2008)第一次看到這一篇A new algorithm for computing the minimum Hausdorff distance between two point sets on a line under translation時，看了很久還是不懂演算法實際上是如何運作的，於是追蹤下去追到了源頭的兩篇論文。

源頭是Huttenlocher在1990年發表的Computing the Mimimum Hausdorff Distance for Point Sets Under Translation，這一篇提出的算法提供最初的想法，把sets中每一個元素移動t單位的軌跡的圖形找出來，再找出所有軌跡極大值中的最小值即為所求，時間複雜度是O(mnlog(mn))。

第二篇論文是Rote在1991年發表的Computing the mimimum Hausdorff distance between two point sets on a line under translation也是沿用了Huttenlocker的概念，只是他使用了一個lower bound來減少搜尋解答時所要檢查的解答數量，這個演算法的時間複雜度已經是Optimal (O(m+n)log(m+n))，所以一直以來大家都使用這個算法。

2008年的這一篇論文也是Optimal algorithm，但是所需要檢查的解答數量又更少了，時間複雜度仍然是O((m+n)log(m+n))，但實驗的結果比Rote’s algorithm快了將近15倍。

以下是我用來畫軌跡圖的Scilab script：

//one dimensional Hausdorff distance
clear;
function [dist] = hausdorff(A, B)
if(size(A, 'r') ~= 1 | size(B, 'r') ~= 1)
warning("must be one dimension array");
dist = [];
return;
end
dist = max(compute_dist(A, B), compute_dist(B, A));
endfunction
//compute distance from point to set
function [dist] = compute_dist(A, B)
m = size(A, 'c');
n = size(B, 'c');
for k=1:m
D = abs(B - A(k));
dist(k) = min(D);
end
dist = max(dist);
endfunction
function [dist,dist2] = minHausdorff(A, B, t)
if (size(A, 'r') ~=1 | size(B, 'r') ~= 1 | size(t, 'r') ~=1)
warning("must be one dimension array");
dist=[];
return;
end
m = size(A,'c');
n = size(B,'c');
len = size(t,'c');
for i=1:m
for j=1:len
dist(i, j) = compute_dist(A(i)+t(j), B);
end
end
subplot(1, 2, 1);
xlabel("t");
plot(t, dist);
for i=1:n
for j=1:len
dist2(i, j) = compute_dist(B(i), A+t(j));
end
end
subplot(1, 2, 2);
xlabel("t");
plot(t, dist2);
endfunction
A=[0, 0.5, 2, 3];
B=[0 0.3 1];
t=linspace(-3, 3, 500);
minHausdorff(A, B, t);

2009年2月7日

One dimension minimum Hausdorff distance