728x90

주어진 영상에서 선분을 찾고자 하면 어떻게 해야 할까. 우선 에지 영상을 만들어 선분을 강조하고, 선분이 하나만 있는 경우에는 에지 데이터를 가지고 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$ 인 직선 위의 점들이었다는 것을 추정할 수 있다.

 

사용자 삽입 이미지

 

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 int;
                    // 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 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 );
            }
        }
    }
    free(accum);
    return TRUE;
}

아래 그림에서 첫 번째는 소스 이미지이고, 이 이미지에서 $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
*/

 

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

Bright Preserving Histogram Equalization with Maximum Entropy  (0) 2008.07.31
Adaptive Binarization  (2) 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

댓글을 달아 주세요

  1. 화이링 2010.04.11 09:44  댓글주소  수정/삭제  댓글쓰기

    안녕하세요.. 이번에 학교에서 과제로 이쪽분야를 선택하게 되었습니다..많이좀 도와주세요..
    다름이 아니라 이번에 허프 변환 프로그램을 돌려봐야 하는데 여기있는 코드로 돌려보고 싶습니다..
    어떻게 돌려야 되는지 정확히좀 알려주세요..
    코딩방법이랑 영상불러오는것 까지 좀 초보자라 생각하시고 자세히좀 알려주세요.. 참 그리고 이코드는 c인가요??
    rmw0709@nate.com 좀 보내주심 정말정말 복받으실껍니다.

  2. helloktk 2010.04.11 17:24 신고  댓글주소  수정/삭제  댓글쓰기

    c++ code 입니다. c에서는 vector container를 지원하지 않습니다. 이것을 사용하는 것보다는 아마 opencv(그곳의 Hough 알고리즘을 좀 변형한 것입니다)를 사용하는 것이 더 낳을 것입니다. 실제로 알고리즘을 돌려서 직선을 검출하려면 좀더 많은 부분이 필요합니다. 이 코드로 다 되는 것이 아니지요.