728x90

Distance Transform은 이미지 상의 각 픽셀에서 가장 가까이 놓인 물체(전경)의 경계까지 거리를 구하는 연산이다. 보통의 경우에 이진 영상에만 적용이 된다. 구해진 거리의 정보를 이용해서 영상에 놓인 전경 물체의 skeleton을 구하거나 (OCR), 로봇의 팔 등을 자동 제어하는 데 있어서 움직이는 경로에 놓인 방해물의 위치를 예측할 수 있으며, 또한 물체까지의 경로 찾기(path finding) 등에 이용이 된다. distance transform은 사용되는 거리 측도(measure)에 따라 그 특성이 달라진다. 우선 가장 단순한 Euclidean 측도를 이용하도록 하자.

 

distance transform은 전경의 경계선을 모두 찾아서 배경의 각 픽셀에서 거리의 최솟값을 할당하면 된다. 그러나 경계가 많은 픽셀로 구성이 되는 이미지에서는 연산 비용이 매우 커지게 된다. 여기서는 이미지의 크기에 선형으로 비례하는 알고리즘에 대해서 살펴보도록 하겠다. 픽셀 수에 선형이기 위해서는 알고리즘이 raster 스캔 방식을 따라야 한다.

 

Euclidean 측도를 사용하는 distance transform은 한 점 $(x, y)$에서 전경 픽셀 $(i, j)$까지 거리의 제곱이 $z = (x-i)^2 + (y-j)^2$로 표현된다. 이미지 상의 각 전경 픽셀 꼭짓점으로 하는 paraboloid를 생각하면 distance transform은 한 픽셀에서 가장 밑에 위치한 paraboloid를 찾는 문제로 환원된다. 그러나 이차원 영역에서 이를 찾기는 쉽지 않은 작업이므로 이를 수평과 수직 방향으로 분리가 가능한지를 찾아보아야 한다. 우선 $x$-방향으로 스캔하면서 $x$-축으로 사영된 거리를 저장하면서 다시 $y$-축 방향으로 스캔하면서 저장된 $x$-방향의 거리의 제곱의 정보를 이용하면 된다. 이것은  $x$-방향으로 스캔할 때 거리의 제곱 값을 이미지의 그레이 값으로 저장하면 보다 쉽게 해결이 된다. 그러면 $y$-방향으로 스캔할 때는 꼭짓점이 이전에 $x$-방향 스캔 시 저장된 거리의 제곱만큼 이동이 된 이차곡선들 중에서 맨 아래에 놓인 것을 찾으면 된다.  따라서 2차원 distance transform은 1차원의 distance transform을 행방향 그리고 열방향으로 2번 시행을 하면 얻을 수 있다.

 

1차원의 distance transform은 일직선에 놓인 각 픽셀 위치를 꼭짓점으로 하는 이차 곡선들 중에서 가장 아래에 놓인 곡선을 선택하여 그 값을 취하면 된다. 거리의 최솟값을 구할 때 배경에 해당되는 픽셀은 선택되지 않기 위해서 배경 위치에서 이차곡선에 매우 큰 (수학적으로는 무한대) offset을 준다:

$$\text {1-dim distance transform}(p)=\underset {q\in\text {pixels}}{\text {min}}  \left( (q-p)^2+ F(q) \right)$$

초기 offset $F(q)$ 값은 전경 픽셀에서는 0, 배경 픽셀에서는 +INFINITY로 설정한다.  전경의 경계에서 형성이 된 2차 곡선 가장 낮게 놓이므로 그것에 의해서 거리가 결정이 된다.

일반적인 F(q)의 값이 주어지는 경우에는 문제는 각 픽셀점에서 보는 가장 낮게 놓인 이차곡선이 어느 것이고, 그것이 성립이 되는 영역을 찾는 문제로 귀결이 된다. 위치 $p$, $q$에 꼭짓점이 있는 이차곡선의 교차점이

$$s=\frac { (F(p) + p^2)-(F(q) + q^2) }{ 2(p-q)}$$ 표현되므로 쉽게 가장 낮은 2차 곡선의 영역을 찾을 수 있다.

 

아래 그림은 일차원 이미지의 distance transform의 결과이다: 붉은 선은 이미지(0:전경, 255:배경)이고, 녹색 선은 거리 값을 나타내는데 직관적으로 맞음을 확인할 수 있다.

네이버 블로그 이전

이 일차원 distance transform을 각각의 행에 대해서 한 후에, 그 결과를 다시 각각의 열에 또다시 적용하면 원하는 결과를 얻는다. 아래의 그림은 글씨에 대해서 skeleton을 구하기 위해서 distance transform을 적용하였다(skeleton을 얻기 위해서 반대로 함: 흰색=배경, 검은색=전경)

** 참고: en.wikipedia.org/wiki/Distance_transform

** cs.brown.edu/people/pfelzens/dt/에서 관련 논문과 원 코드를 찾을 수 있다;

#define INF     (1E+20)
#define SQR(a)	((a) * (a))
/* distanceTransform of 1d function using the Euclidean distance */
struct para_envelop {
    int x;		   // x-coord of the vertex of parabolar;
    double start;  // 현재 parabola가 가장 아래 높인 구간의 시작;
};
double para_intersection(int q, int p, double *dblimg) {
    return ((dblimg[q] + SQR(q)) - (dblimg[p] + SQR(p))) / (2. * q - 2. * p);
}
void DistanceTransform_1D(double *dblimg, int n, double* dist) {
    para_envelop *env = new para_envelop [n + 1] ;
    int k = 0;				// index of right_most parabola lower envelop;
    env[k].x = 0; env[k].start = -INF;
    env[k + 1].start = +INF;
    for (int q = 1; q < n; ++q) {
        double s = para_intersection(q, env[k].x, dblimg);
        // q에 꼭지점이 있는 parabola가 가장 밑에 있는 영역의 시작 위치(start)를 찾음;
        while (s <= env[k].start) s = para_intersection(q, env[--k].x, dblimg);
        env[++k].x = q ;    // 가장 아래에 있는 parabola 갱신;
        env[k].start = s ;
        env[k + 1].start = +INF;
    }
    k = 0;
    for (int q = 0; q < n; ++q) {
        while (env[k + 1].start < q) k++;//현재 위치에서 가장 낮은 parabola를 찾음;
        // Euclidean 거리 정보를 기록;
        dist[q] = SQR(q - env[k].x) + dblimg[env[k].x];
    }
    delete[] env;
}

'Image Recognition' 카테고리의 다른 글

Contrast Limited Adaptive Histogram Equalization (CLAHE)  (0) 2021.02.15
Fixed-Point Bicubic Interpolation  (0) 2021.01.19
Distance Transform  (0) 2021.01.16
FFT 알고리즘의 재귀적 구현  (0) 2021.01.14
Edge-Preserving Smoothing  (0) 2021.01.12
Octree Quantization  (0) 2021.01.12
Posted by helloktk

댓글을 달아 주세요