Geometry & Recognition

주어진 영상에서 선분을 찾고자 하면 어떻게 해야 할까. 우선 에지 영상을 만들어 선분을 강조하고, 선분이 하나만 있는 경우에는 에지 데이터를 가지고 line-fitting 알고리즘을 적용해서 해당 선분을 기술하는 파라미터를 추출할 수 있다. 그러나 영상이 선분을 여러 개 포함하는 경우에는 이 방법을 이용하기 어렵다(불가능한 것은 아니지만 노이즈 등에 의한 영향을 고려해야 하므로 복잡한 과정을 거쳐야 한다). 평면에서 선분은 원점까지 거리와 그것의 수직(수평)인 방향만 주어지면 결정이 된다. 직선에서 원점까지 거리를 $r$, 법선이 $x$-축과 이루는 각도가 $θ$면

$$r = \cos(θ)  x + \sin(θ)  y;$$

의 형태로 주어진다. 즉, $(r,θ)$ 한쌍이 주어지면 직선 한 개가 정의된다 (주어진 $(r,θ)$ 값이 만드는 직선을 $a  x + b  y = c$  꼴로 쓰면 계수는 $a = \cos θ$, $b = \sin θ$, $c = r$로 표현된다). 

이 직선 방정식은 $rθ$-평면의 stripe=$[0,∞) \times  [0,2π]$을 $xy$-평면으로 보내는 변환으로도 생각할 수 있다. 이 변환은 $rθ$-평면의 한 점을 $xy$-평면의 한 직선으로 보낸다. 역으로는 $xy$-평면의 한 점은 $rθ$-평면의 한 곡선으로 변환이 된다. 직선 상의 점들은 같은 원점 거리=$r$, 같은 기울기=$\theta$를 가지므로, 직선 위의 각 점들이 $rθ$-평면에 만드는 곡선들은 공통의 교점을 가지게 된다. 이 교점의 위치가 $xy$-평면에서 직선을 기술하는 파라미터를 준다.

Hough Transform은 이 변환의 특성을 이용한 것이다. 이미지에서 에지에 해당하는 점들을 위의 변환에 의해서 $rθ$-평면의 곡선으로 보내는 것이다 (프로그램적으로는, 에지점 좌표 $(x, y)$가 주어지면 $θ=0 \rightarrow π$까지 일정 간격으로 증가시키면서 곡선 $r=x \cos(θ) + y\sin(θ)$의 값을 구해서 메모리 상의  $[r,θ]$ 지점의 도수를 1씩 증가시킨다). 만약 에지에 해당되는 점들이 직선의 관계를 가지게 되면, 각 점들에 해당하는 $rθ$-평면에서 곡선들은 한 교점을 형성하게 될 것이다. 긴 선분은 $rθ$-평면의 한 점에서 더 많은 곡선들의 교점을 형성하게 된다. 따라서, $rθ$-평면에서 이러한 교점의 히스토그램을 구하여, 교점 수가 일정 이상 누적이 된 경우를 취하면, $xy$-이미지 평면에서 일정한 길이 이상을 갖는 선분을 골라낼 수 있다.

그러면 왜 $rθ$-평면으로 변환을 생각하는 것일까? 직선이 $y= a x+b$의 형태로 표시되므로 기울기와 $y$축과의 교점을 기술하는 $ab$-공간을 이용할 수도 있지만, 이 경우에 $y$-축에 평행인 직선의 경우에 기울기 $a$ 값이 무한히 커지는 경우가 발생하여 저장공간 할당에 문제가 생긴다. 실제적인 문제에서 되도록이면 compact 한 공간으로 변환을 고려해야 하는 것이다. $rθ$-공간으로의 변환은 유한한 이미지의 경우 항상 유한한 $rθ$-공간의 영역으로 변환된다.

아래의 그림은 $x-y=-5$인 직선상의 세 점 $(5,10)$, $(10,15)$, $(15,20)$에 해당하는 $rθ$-평면상의 세 곡선을 보인 것이다: $r = 5 \cos(θ) + 10\sin(θ)$, $r = 10 \cos(θ) + 15  \sin(θ)$, $r = 15 \cos(θ) + 20 \sin(θ)$. 이 세 곡선은 $(r,θ) = (5/\sqrt{2}, 3 \pi /4)$ 지점에서 만남을 알 수 있다. 이 만나는 지점을 구하면, 거꾸로 세 점이  $x-y=-5$ 인 직선 위의 점들이었다는 것을 추정할 수 있다.

std::vector<Line> HoughTransformLine(BYTE* image, int width, int height, /*background=0*/
                                     double rho/*=2*/, 
                                     double theta/*=Pi/180.*/,
                                     int threshold/*=20*/) 
{
    /* use cosine and sine look-up tables*/
    const double irho = 1 / rho;
    const int numangle = (int) (Pi / theta);
    const int numrho = (int) (((width + height) * 2 + 1) / rho);
    const int rwidth = (numrho + 2);
    std::vector<int> accum((numangle + 2) * (numrho + 2), 0);
    double ang; int n;
    for (int  y = 0; y < height; y++ ){
        for (int x = 0; x < width; x++ ){
            if ( image[y * width + x] != 0 ){ // only for foreground pixels;
                for (ang = 0, n = 0; n < numangle; ang += theta, n++ ) {
                    double rho = (x * cos(ang) + y * sin(ang)) * irho ;
                    int r = rho >= 0 ? int(rho + .5) : (-int(-rho + .5));//round to nearest int;
                    // accum을 이차원배열로 생각하고, 1 픽셀의 border를 두는 형태로 한다.
                    // 이는 아래의 local-maxima를 찾을때 경계를 고려할 필요가 없어서 유리하다.
                    r += (numrho - 1) / 2;
                    accum[(n + 1) * rwidth + r + 1]++;
                }
            }
        }
    }
    //find local maxima;
    std::vector<Line> vecLine;
    for (int  r = 0; r < numrho; r++ ) {
        for (int  n = 0; n < numangle; n++ ) {
            int base = (n + 1) * rwidth + r + 1;
            //test whether it is local-maximum(4-way);
            if ( accum[base] > threshold &&
                 accum[base] > accum[base - 1] && accum[base] > accum[base + 1] &&
                 accum[base] > accum[base - rwidth] && accum[base] > accum[base + rwidth] )
            {               
                Line line;
                line.rho = (r - (numrho - 1) * .5) * rho;
                line.angle = n * theta;
                vecLine.push_back( line );
            }
        }
    }
    return vecLine;
}

아래 그림에서 첫 번째는 소스 이미지이고, 이 이미지에서 $rθ$-평면으로 Hough Transform 한 것이 두 번째 것이다(rho=2, theta=Pi/360). 원본 이미지에는 8개의 선분이 있고, 4 개씩 같은 방향을 갖고 있다. Hough Transform 된 이미지에서 이러한 특징을 볼 수 있다(가로축이 $θ$이고 세로축이 $r$이다. $r$ 축은 가운데가 $r=0$이다). 누적이 많이 된 부분이 두 군데의 동일한 θ에서 나타나고 있다. 그러나 결과에서 8개의 피크를 분리하기는 쉽지 않다. 위의 코드는 각각의 점에서 4방향으로 체크하여 극대 값을 찾고 있으나, 항상 잘 동작하는 것은 아니다.

local-maxima를 좀 더 잘 잡고 싶으면, 위처럼 주변의 4점만 체크할 것이 아니라, 윈도를 좀 더 크게 잡고, 그 윈도 내에서 최댓값을 찾아보는 것도 한 방법이 된다.

/**
** http://blog.naver.com/helloktk/80051779331
*/

주어진 이미지의 gaussian scale space의 표현은 이미지와 gaussian kernel의  convolution 결과로 주어진다.
$$L(x, y; σ)= G(x, y; σ) * I(x, y);$$

이 표현은 임의의 $σ$에 대해서 정의되나 실제적으로는 유한한 구간의 값들만 취급한다. 그리고 스케일 값이 한 옥타브를 넘어서는 경우에는 원본 이미지의 크기를 유지할 필요가 없다. 주어진 스케일보다 작은 특징들은 고려 대상이 되지 않는다는 점을 인식하면, 스케일이 두 배로 커지는 경우에는 원본 이미지를 반으로 줄이고 스케일은 동일하게 유지하는 것이 훨씬 더 이득이다. 따라서 scale space를 이미지 pyramid로 표현하는 것이 자연스럽다.
아래 예는 3 옥타브까지 scale space를 표현한 것이다. 각 옥타브에서 3 개의 구간(수직 방향)을 갖는다(각 옥타브에서 마지막 이미지는 비교를 위해 넣은 것이다). 한 단계 위 옥타브의 이미지는 전 단계 옥타브의 동일한 레벨의 이미지를 1/2 다운 샘플링하면 바로 얻을 수 있다.

*** $L(x; σ) = G(x; σ) * I(x)$ 의 1/2 down-sampling 이미지 $L'(x;\sigma)$는 (1-dim만 고려해도 충분하다)
$$\begin{align} L'(x; σ)\equiv L(2x; σ)  &= \int \frac{1}{σ} \exp\Big[-\frac{(2x-x')^2}{2σ^2}\Big] I(x') dx',   \quad (x'\rightarrow 2x') \\&=\int \frac{1}{σ} \exp\Big[- \frac{(2x-2x')^2}{2σ^2} \Big] I(2x') d(2x')\\&= \int \frac{1}{\sigma/2} \exp \Big[ -\frac{(x-x')^2 }{2(σ/2)^2}\Big] I(2x') dx'   \\  &=G(x; σ/2) * I(2 x);\end{align}$$
임을 알 수 있다. 즉, 스케일 $σ$로 gaussian convolution 이미지를 1/2 다운샘플링한 것은 1/2 다운샘플링한 이미지를 $σ/2$ 스케일로 gaussian convolution 결과와 같다. 따라서 스케일이 2배인 이미지가 필요하면 현재의 스케일에서 이미지를 반으로 줄이면 된다.

(1) cell image : 원본 영상을 이진화(Otsu-알고리즘)시킨 결과다. 두 군데서 셀이 겹쳤다. 단순히 connected component labeling을 적용해서는 이를 분리할 수 없다.

(2) distance transform : distance 변환 결과에 blurring을 추가한 결과다. distance 변환은 셀 외부는 셀로부터의 거리를, 셀 내부는 배경으로부터의 거리의 음의 값을 취한 후 전체적으로 다시 리스케일한 것이다.  blurring은 watershed 알고리즘이 보다 정확히 동작하는데 필요하다.

(3) watershed segmentation: 분할된 영역의 label이 나온다(경계 label=0). 이 label을 가지고  false coloring을 한 결과다. 이 알고리즘은 논문 "The Watershed Transform: Definitions, Algorithms and Parallelization Strategies", Jos B.T.M. Roerdink and Arnold Meijster의 내용을 구현한 것이다. 8-방향 픽셀 연결성을 이용했다.

(4) final result; watershed 결과를  mask로 이용해서 이미지를 분할한 것이다. 겹친 cell이 분리되었다.

다른 예:

* http://blog.naver.com/helloktk/80051779331 에서 옮긴 자료.

* 구현: https://kipl.tistory.com/66

https://kipl.tistory.com/299