Hausdorff Distance

1. Hausdorff Distance 뜻

-  컴퓨터 비전 분야에서 주로 쓰이며, '매칭' 문제 해결을 위해 사용됩니다.

- X 와 Y가 비어 있지 않은 메트릭 공간(M, d)의 부분 집합(non-empty sets of points X, Y)이라고 하면,

 Hausdorff 공간 $d_{H}(X, Y)$는 다음과 같이 정의 합니다.

- X, Y 집합에 속한 점의 갯수는 다를 수 있습니다.

 

 

Hausdorff Distance 공식1(in Wikipedia)

 

이산화(discretized)와 경계 $\Omega$를 고려하였을 때(점이 이산적으로 분포함을 가정하면)

공식 1은 아래와 같이 표현할 수 있습니다.

※ 직관적으로 보면, 한쪽 점 집합을 기준으로 다른쪽 집합 상의 점까지의 가장 먼 거리를 구하는 것처럼 보입니다.  그리고 두 거리 중 더 큰 것(max)을 $d_{H}(X,Y)$ 로 정합니다. 

 

2 Hausdorff Distance 특징

 

3. Hausdorff Distance 수학적 정의

두개의 점 집합 $ A = {a_1, a_2, ..., a_n} $ , $ B = {b_1, b_2, ... , b_n} $ 이 주어 졌을 때,

한쪽 방면의 Hausdorff 거리는 다음과 같이 정의할 수 있습니다(From A to B)

 

그리고, AB 양 방향의 Hausdorff 거리는 다음과 같이 정의할 수 있습니다.

 

Hausdorff Distance 공식2(in 강의 노트)

 

※ 공식1과 공식2는 결국엔 같은 뜻입니다.

 

 

4. Hausdorff Distance 단점

- 아웃 라이어(outlier)에 취약합니다.

논문에서 따온 이미지를 가지고 설명하자면, 왼쪽과 오른쪽의 x, y 집합 간의 Hausdorff 거리는 아웃라이어(각각 x4, y4)를 제외하면, 왼쪽이 훨씬 작습니다. 두 점간이 서로 붙어 있기 때문에.

하지만, 아웃라이어(x4, y4)로 인해 왼쪽, 오른쪽 점 집합간의 Hausdorff거리는 (양방향 화살표가 나타내는 거리에 따르면) 동일하게 됩니다(단점).

 

5. Average Hausdorff distance

- Average Hausdorff distance는 위의 단점을 보완한 것입니다.

 

|X|, |Y|는 각각 X, Y 집합의 점의 갯수를 뜻합니다.

Maximum 값을 Average 값으로 대체합니다.

 

6. Code

def averaged_hausdorff_distance(set1, set2, max_ahd=np.inf):
    """
    Compute the Averaged Hausdorff Distance function
    between two unordered sets of points (the function is symmetric).
    Batches are not supported, so squeeze your inputs first!
    :param set1: Array/list where each row/element is an N-dimensional point.
    :param set2: Array/list where each row/element is an N-dimensional point.
    :param max_ahd: Maximum AHD possible to return if any set is empty. Default: inf.
    :return: The Averaged Hausdorff Distance between set1 and set2.
    """

    if len(set1) == 0 or len(set2) == 0:
        return max_ahd

    set1 = np.array(set1)
    set2 = np.array(set2)

    assert set1.ndim == 2, 'got %s' % set1.ndim
    assert set2.ndim == 2, 'got %s' % set2.ndim

    assert set1.shape[1] == set2.shape[1], \
        'The points in both sets must have the same number of dimensions, got %s and %s.'\
        % (set2.shape[1], set2.shape[1])

    d2_matrix = pairwise_distances(set1, set2, metric='euclidean')

    res = np.average(np.min(d2_matrix, axis=0)) + \
        np.average(np.min(d2_matrix, axis=1))

    return res

 

---

출처)

en.wikipedia.org/wiki/Hausdorff_distance

web.stanford.edu/class/cs273/scribing/2004/class8/scribe8.pdf

github.com/javiribera/locating-objects-without-bboxes/blob/master/object-locator/losses.py

Locating Object Without Bounding Boxes, CVPR2019, Oral.

H. Attouch, R. Lucchetti, and R. J. B.Wets. The topology of the $\rho$-Hausdorff distance. Annali di Matematica
Pura ed Applicata, 160(1):303–320, December 1991.