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

                          r = cosθ * x + sinθ * y;

의 형태로 주어진다. 즉, (r,θ) 한쌍이 주어지면 (x,y)평면에서 직선이 하나가 정의된다 (하나의 (r, θ) 값이 주어지는 경우, 만들어지는 직선을 a * x + b * y = c  꼴로 쓰면, 계수들은 a = cosθ, b = sinθ, c = r 로 주어진다).

이 직선의 방정식은 rθ-평면의 stripe을  xy-평면으로 보내는 변환으로도 생각할 수있다. 이 변환은 rθ-평면의 한점을 xy-평면의 직선으로 보낸다. 그럼 역으로 xy-평면의 한점은 rθ-평면의 곡선으로 변환이 된다. xy-평면상의 각각의 점들은 rθ-평면의 곡선을 하나씩 만드는데 이 곡선들이 공통으로 만나는 교점이 생기게 된다. rθ-평면에서의 이 교점의 좌표가 바로 xy-평면에서의 직선을 기술한다.

Hough Transform은 이 변환의 특성을 이용한 것이다. 이미지에서 에지에 해당하는 점들을 위의 변환에 의해서 rθ-평면의 곡선으로 보내는 것이다 (프로그램적으로는, 에지점 좌표 (x,y)가 주어지면 θ=0, π까지 일정 간격으로 증가시키면서 곡선 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 인 직선 위의 점들이었다는 것을 추정할 수 있다.

사용자 삽입 이미지

BOOL HoughTransformLine(BYTE* image, int width, int height, /*background=0*/
                                       double rho/*=2*/,
                                       double theta/*=Pi/180.*/,
                                       int threshold/*=20*/,
                                       std::vector<Line>& vecLine) {
    /* use cosine and sine look-up tables*/
    double irho = 1 / rho;
    int numangle = (int) (Pi / theta);
    int numrho = (int) (((width + height) * 2 + 1) / rho);
    int *accum = (int*)malloc( sizeof(accum[0]) * (numangle+2) * (numrho+2) );
    memset( accum, 0, sizeof(accum[0]) * (numangle+2) * (numrho+2) );
    double ang;
    int n, rwidth=(numrho+2);
    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 integer;
                    //accum을 이차원배열로 생각하고, 1픽셀의 border를 두는 형태로 한다.
                    //이는 아래의 local-maxima를 찾을때 경계를 고려할 필요가 없어서 유리하다.
                    r += (numrho - 1) / 2;
                    accum[(n+1) * rwidth + r+1]++;
                }
            }
        }
    }
    //find local maxima;
    for(int  r = 0; r < numrho; r++ ){
        for(int  n = 0; n < numangle; n++ ){
            int base = (n+1) * rwidth + r+1;
            //test if 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 );
            }
        }
    }
    free(accum);
    return TRUE;
}

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

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

사용자 삽입 이미지

사용자 삽입 이미지


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

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

Bright Preserving Histogram Equalization with Maximum Entropy  (0) 2008.07.31
Adaptive Binarization  (1) 2008.07.14
Histogram Equalization  (0) 2008.06.22
FFT2D  (0) 2008.06.10
Otsu Algorithm  (6) 2008.05.30
Hough Transform  (2) 2008.05.22
Posted by helloktk