Hough Line Transform 구현

직선 y = mx + b을 매개변수식으로 바꾸면 r = xcosθ + ysinθ이다. 여기서 r은 원점으로부터 직선까지의 수직거리이며 θ는 이 직선과 수직인 직선과 x축 사이의 각도를 시계 반대방향으로 측정한 값이다.

좌표 (300,300)을 지나는 모든 직선에 대한 r과 θ를 구해서 극좌표계에 그려보면 사인곡선이 그려진다. 식 r = xcosθ + ysinθ에 좌표 (300,300)을 대입하고 θ를 0에서 180까지 증가시키면서 r값을 구한 결과이다.

좌표(100,100), (200,200), (300,300) 세 점을 지나는 모든 직선에 대한 r과 θ를 구하여 극좌표계에 그려보면 세 개의 사인곡선이 그려지는데 한 점에서 만나는 것을 확인할 수 있다.

교차점의 r,θ 값을 구하여 직선의 방정식으로 변환 후, 그려보면 세 점 (100,100), (200,200), (300,300)을 지나는 직선임을 확인 할 수 있다.

다음은 hough line transform 구현 과정이다.

1.입력 영상을 그레이스케일 영상으로 변환한다.

2. 에지를 검출한다. sobel 또는 canny를 사용하면 된다.

3. 에지에 속하는 모든 점에 대해 다음을 수행한다.  

해당 점을 지나는 모든 직선에 대한 r, θ를 구하여 accumulator의 (r,θ) 위치값을 1씩 증가시킨다. accumulator는 2차원 배열로 구현된다.

    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            if ( img_edge.at<uchar>(y,x) > 0 )
                for (int angle = 0; angle < 180; angle++)
                {
                    int r = (x-centerX)*table_cos[angle] + (y-centerY)*table_sin[angle];
 
                    r = r + hough_height;//r이 음수인 경우 때문 -r ~ r 범위를 0 ~ 2r 범위로 변경
                    accumulator[r*accumulator_width + angle] += 1;
                }
        }
    }

4. accumulator를 이미지화 해보면 수많은 곡선들이 그려진다. 하나의 곡선은 하나의 점을 지나는 모든 직선들이다. 곡선들의 교점이 직선일 가능성이 있는 후보점인데 많은 곡선이 겹쳐질수록 실제 에지 위를 지나는 직선일 가능성이 높아진다.

일정 threshold값 이상이면서 local maxima인 경우를 찾아 파란색 원을 그려보면 4개의 위치가 찾아진다. 

5. 찾은 r,θ값을 직선으로 변환한다. 입력영상에 직선을 그리기 위해서 직선의 양끝점을 구해야 한다.

식 r = xcosθ + ysinθ은  다음 두 식으로 변환할 수 있다.

45 <= θ <= 135 인 경우 ( 수평선에 가까운 경우 )         

y = (r- xcosθ)/ sinθ

45 > θ 또는 135 < θ 경우 ( 수직선에 가까운 경우 )

x = (r- ysinθ)/ cosθ

6. 입력 영상에 직선을 그린다. 정사각형 주위로 4개의 파란색 직선들이 그려졌다.

 

다른 실행 결과들

전체 소스코드이다.

#include <opencv2/highgui.hpp>  
#include <opencv2/imgproc.hpp>  
#include <iostream>
#include <stdio.h>
 
using namespace cv;
using namespace std;
 
 
int main(int argc, char** argv)
{
 
    Mat img_original, img_gray, img_edge;
 
    //이미지파일 로드 
    img_original = imread("test2.jpg", IMREAD_COLOR);
    //img_original = imread("test2.png", IMREAD_COLOR);
    //img_original = imread("test.jpg", IMREAD_COLOR);
    if (img_original.empty())
    {
        cout << "Could not open or find the image" << std::endl;
        return -1;
    }
 
 
    //그레이스케일 이미지로 변환  
    cvtColor(img_original, img_gray, COLOR_BGR2GRAY);
 
    //에지 검출
    GaussianBlur(img_gray, img_edge, cvSize(5, 5),0,0);
    Canny(img_edge, img_edge, 50, 150, 3);
 
 
    int height = img_edge.rows;
    int width = img_edge.cols;
 
    double hough_height = ((sqrt(2.0) * (double)(height>width ? height:width)) / 2.0);
    int centerX = width / 2.0;
    int centerY = height / 2.0;
 
 
    int accumulator_width = 180;
    int accumulator_height = hough_height * 2;
    int accumulator_size = accumulator_height * accumulator_width;
    
    int *accumulator = (int*)malloc(sizeof(int)*accumulator_size);
    memset(accumulator, 0, sizeof(int)*accumulator_size);
 
 
    double table_sin[180], table_cos[180];
    double DEG2RAD = CV_PI / 180;
    for (int angle = 0; angle < 180; angle++)
    {
        table_sin[angle] = sin(angle*DEG2RAD);
        table_cos[angle] = cos(angle*DEG2RAD);
    }
 
 
    
 
    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            if ( img_edge.at<uchar>(y,x) > 0 )
                for (int angle = 0; angle < 180; angle++)
                {
                    int r = (x-centerX)*table_cos[angle] + (y-centerY)*table_sin[angle];
 
                    r = r + hough_height;//r이 음수인 경우 때문 -r ~ r 범위를 0 ~ 2r 범위로 변경
                    accumulator[r*accumulator_width + angle] += 1;
                }
        }
    }
        
 
    //accumulator에서 MAX값 찾기
    int max = -1;
    for (int y = 0; y < accumulator_height; y++)
    for (int x = 0; x < accumulator_width; x++)
    {
        if (accumulator[y*accumulator_width + x] > max)
            max = accumulator[y*accumulator_width + x];
    }
    
 
 
    //accumulator를 이미지화
    Mat img_accumulator = Mat(accumulator_height, accumulator_width, CV_8UC3);
 
    for (int y = 0; y < accumulator_height; y++)
    for (int x = 0; x < accumulator_width; x++)
    {
        int value = 255 * ((double)accumulator[y*accumulator_width + x]) / max;
        
        img_accumulator.at<Vec3b>(y, x)[0] = 255-value;
        img_accumulator.at<Vec3b>(y, x)[1] = 255-value;
        img_accumulator.at<Vec3b>(y, x)[2] = 255-value;
 
    }
 
 
 
    
    int count = 0;
    for (int r = 0; r < accumulator_height; r++)
    for (int angle = 0; angle < 180; angle++)
    {
 
        if (accumulator[r * accumulator_width + angle] > 50)
        {
 
            // 11 x 11 영역내에서 현재 위치가 local maxima 인지 검사
            int max = accumulator[r * accumulator_width + angle];
            for (int y = -5; y <= 5; y++)
            {
                for (int x = -5; x <= 5; x++)
                {
                    int new_r = r + y;
                    int new_angle = angle + x;
 
                    if ( new_angle  < 0 )
                    {
                        new_angle = 180 + new_angle;
                    }
                    else if (new_angle >= 180) {
                        new_angle = new_angle - 180;
                    }
                    
                    
                    if ( new_r >= 0 && new_r < accumulator_height) 
                    {
                        if (accumulator[ new_r * accumulator_width + new_angle] > max)
                        {
                            max = accumulator[ new_r * accumulator_width + new_angle];
                            x = y = 6;//loop 종료
                        }
                    }
                }
            }
 
            if (max > accumulator[r * accumulator_width + angle])
            {
                continue; //현재 위치는 local maxima가 아님
            }
 
 
            // r = x*cos(theta) + y*sin(theta)
            // y = (r- x*cos(theta))/ sin(theta) 수평선인 경우
            // x = (r- y*sin(theta))/ cos(theta) 수직선인 경우
 
            int x1, x2, y1, y2;
 
            if (angle >= 45 && angle <= 135) //수평선
            {
                x1 = 0;
                x2 = width;
                y1 = ((r - hough_height) - (x1 - centerX)*table_cos[angle]) / table_sin[angle] + centerY;
                y2 = ((r - hough_height) - (x2 - centerX)*table_cos[angle]) / table_sin[angle] + centerY;
            }
            else //수직선
            {
                y1 = 0;
                y2 = height;
                x1 = ((r - hough_height) - (y1 - centerY)*table_sin[angle]) / table_cos[angle] + centerX;
                x2 = ((r - hough_height) - (y2 - centerY)*table_sin[angle]) / table_cos[angle] + centerX;
 
            }
 
            circle(img_accumulator, cvPoint(angle, r), 3, Scalar(255, 0, 0));
            line(img_original, cvPoint(x1, y1), cvPoint(x2, y2), Scalar(255, 0, 0), 1);
            count++;
 
            cout << count << " (" << x1 << "," << y1 << ") (" << x2 << "," << y2 << ")  angle=" << angle<<" r="<<r<< " accumulator값="<< accumulator[r * accumulator_width + angle]<<endl;
        }
 
    }
 
    
 
    imshow("img_result", img_original);
    imshow("img_gray", img_gray);
    imshow("img_edge", img_edge);
    imshow("img_accumulator", img_accumulator);
 
    imwrite("img_gray.jpg", img_gray);
    imwrite("img_edge.jpg", img_edge);
    imwrite("img_accumulator.jpg", img_accumulator);
    imwrite("img_result.jpg", img_original);
 
 
    //키보드 입력이 될때까지 대기  
    waitKey(0);
 
 
    return 0;
}