Approximate Distance Transform

Approximate Distance Transform은 이진 영상에서 각 화소가 가장 가까운 객체(또는 배경)까지의 거리를 정확하게 계산하지 않고, 빠른 계산을 위해 근사적으로 구하는 알고리즘이다.

기본 아이디어는 영상을 한두 번 스캔하면서 이미 계산된 이웃 화소의 거리 정보를 현재 화소로 전달(propagation)하는 것이다. 예를 들어, forward pass에서는 왼쪽과 위쪽 이웃을, backward pass에서는 오른쪽과 아래쪽 이웃을 이용하여 현재 화소의 거리를 반복적으로 갱신한다. 이때 수평 및 수직 이동에는 비용 \(1\), 대각선 이동에는 \(1.4\approx \sqrt{2}\) (또는 \(3\)과 \(4\) 같은 정수 가중치)를 사용하여 유클리드 거리를 근사한다.

대표적인 갱신식은 다음과 같다.

\begin{gather}D(x,y)=\\ \min\left[D(x,y),D(x-1,y)+1,D(x,y-1)+1,D(x-1,y-1)+\sqrt{2},D(x+1,y-1)+\sqrt{2}\right]\end{gather}

이며, backward pass에서는 반대 방향의 이웃에 대해서도 동일한 연산을 수행한다.

Approximate Distance Transform의 장점은 계산량이 영상의 크기에 비례하는 \(O(N)\)으로 매우 빠르며 구현이 간단하다는 점이다. 반면, 대각선 방향의 거리 등을 근사하기 때문에 정확한 유클리드 거리와는 약간의 오차가 발생한다. 이러한 이유로 ADT는 실시간 영상처리나 초기 거리 추정에 널리 사용되며, 높은 정확도가 필요한 경우에는 Exact Euclidean Distance Transform (EDT)이 사용된다.

 

아래 구현은 배경의 각 픽셀에서 객체 픽셀까지의 수평/수직 방향의 Euclidean distance가 1, 대각선 방향으로는 $\sqrt{2}$이지만, 이 거리에 $\sqrt{8}\approx 2.83\approx 3$을 곱하여 각각 $3$과 $4$로 근사값 거리를 이용한다. 이 경우 정수 연산만으로 distance transform을 구할 수 있다.

approximate distance transform

exact Euclidean distance transform

 

#define BACKGROUND (0)
void distanceTransform_approx(BYTE **image, int w, int h, int **map) {
    // initialization;
    for (int y = h; y-->0;)
        for (int x = w; x-->0;) map[y][x] = 0;
    // forward_pass
    // y=x=0;
    if (image[0][0] == BACKGROUND) map[0][0] = 0xFFFF;//  INFINITY;
    // y=0;
    for (int x=1; x<w; x++)
        if (image[0][x] == BACKGROUND) map[0][x] = 3 + map[0][x-1];
    for (int y=1; y<h; y++) {
        // x=0;
        if (image[y][0] == BACKGROUND) 
            map[y][0] = min(3 + map[y-1][0], 4 + map[y-1][1]);
        for (int x=1; x<w-1; x++) 
            if (image[y][x] == BACKGROUND)
                map[y][x] = min(4 + map[y-1][x-1], min(3 + map[y-1][x], 
                           min(4 + map[y-1][x+1], 3 + map[y][x-1])));
        // x=w-1;
        if (image[y][w-1] == BACKGROUND) 
            map[y][w-1] = min(4 + map[y-1][w-2], min(3 + map[y-1][w-1], 3 + map[y][w-2]));
    }
    // backward_pass
    // y=h-1;
    for (int x = w-1; x-->0;)
        if (image[h-1][x] == BACKGROUND) 
            map[h-1][x] = min(map[h-1][x], 3 + map[h-1][x+1]);

    for (int y = h-1; y-->0;) {
        // x=w-1;
        if (image[y][w-1] == BACKGROUND)
            map[y][w-1] = min(map[y][w-1], min(3 + map[y+1][w-1], 4 + map[y+1][w-2]));
        for (int x=w-1; x-->1;) 
            if (image[y][x] == BACKGROUND)
                map[y][x] = min(map[y][x], min(4 + map[y+1][x+1], 
                           min(3 + map[y+1][x], min(4 + map[y+1][x-1], 3 + map[y][x+1]))));
        // x=0;
        if (image[y][0] == BACKGROUND)
            map[y][0] = min(map[y][0], min(4 + map[y+1][1], 
                            min(3 + map[y+1][0], 3 + map[y][1])));
    }
};