허프 변환(Hough Transform)

허프 변환은 이미지에서 선과 원 같은 단순한 형태를 찾는 방식이다. 이진화 된 이미지에서 직선을 찾을 때 상대적으로 빠른 검출을 보여준다.

허프 선 변환(Hough line transform)

허프 선 변환의 기본 개념은 2차원 이미지 상의 어떠한 점은 선의 일부라는 사실을 기초로 한다. 선분의 기울기를 a라고 가정하고 y절편을 b라고 할 때 다음과 같은 방정식을 세우고, 그래프로 표현할 수 있다.

y = ax+b 

[그림1]

이 직선의 방정식을 (x, y) 공간이 아닌 (a, b)의 파라미터 공간으로 변환하면 다음과 같다.

b = -xa+y

[그림2]

원본 이미지에서 한 점은 (a, b) 파라미터 공간상에서는 직선이 된다. 그렇기 때문에 원본 이미지 내의 직선 성분과 관련된 원소 값을 일정량 증가시키면서 (a, b) 파라미터 공간상에 직선을 계속 그리다 보면, [그림2]처럼 (a, b) 파라미터 공간상에서 직선들이 겹쳐지는 부분을 확인할 수 있다. 이 겹쳐진 한 점(a, b)이 (x, y) 상에서의 직선 방정식에 대한 기울기와 절편이 되는데, 이 때 겹쳐지는 직선들을 구하기 위해 사용되는 평면 또는 배열을 누적 평면(accumulation plane)  또는 누적 배열(accumulation array)이라고 한다.

이런식으로 (a, b) 공간에서 겹쳐지는 직선에 대한 점을 찾아 원본이미지 (x, y) 공간에서 기울기(a)와 절편(b)을 통해 직선을 찾고자 하는 것이 허프 선 변환의 핵심 내용이다.

직선 검출의 한계와 극좌표계 사용

문제가 하나 있다. y = ax + b 방정식에서 축과 평행한 수직선의 경우 기울기-절편으로는 표현할 수가 없다. 그렇기 때문에 ρ와 θ를 사용하는 극좌표계 직선의 방정식을 사용한다. ρ는 로(rho), θ는 쎄타(theta)라고 읽는다.

ρ와 θ를 이용하면 축에 수직으로 존재하는 직선도 표현할 수 있게 된다.

이제 기울기와 y절편으로 이루어진 파라미터 공간으로 변환해야한다. 삼각함수를 사용하여 변환 할 수 있다. 풀이과정을 잠시 살펴보자.

직선과 축의 교점을 통해 a, b, c 변을 갖는 삼각형을 찾을 수 있다.

이 때 직선의 방정식은 y = -bx/a + b 이다. 기울기는 -b/a, y절편은 b가 된다. 이 수식에서 a와 b를 ρ와 θ 파라미터로 치환해야 한다.

기울기 구하기

a/c = sinθ
b/c = cosθ

기울기 = -(b/a) = -(cosθ * c / sinθ *c) = -(cosθ / sinθ)

y절편 구하기

ρ / b = sinθ

y절편 = b = ρ / sinθ 

ρ와 θ를 매개변수로 갖는 최종적인 직선 방정식

y = -bx/a + b
y = -x(cosθ / sinθ) + ρ / sinθ 
ρ = x(cosθ) + y(sinθ)

최종적으로 구한 방정식 xcosθ + ysinθ = ρ 를 (ρ,θ) 파라미터 공간상에서 보면 다음과 같다.

OpenCV에서는 허프 선 변환을 위한 함수 2가지를 제공한다.

• HoughLines
• HoughLinesP

허프 변환에 의한 선분 검출

OpenCV에서 허프 선 변환을 통해 선분을 검출 할 수 있는 함수는 다음과 같다.

Imgproc.HoughLines(
    Mat image, Mat lines, double rho, double theta, int threshold, 
    double srn, double stn, double min_theta, double max_theta
)

image : 입력 영상
lines : 검출한 선분, rho와 theta정보를 담고 있다.
rho : 누적 배열에서 rho 값의 간격. ex) 1.0 -> 1픽셀 간격
theta : 누적 배열에서 theta 값의 간격. ex) Math.PI / 180 -> 1도 간격
threshold : 누적 배열에서 직선으로 판단할 임계값
srn, stn : 멀티 스케일 허프 변환에서 rho 해상도, theta 해상도를 나누는 값. 
           기본값 0이고, 이 경우 일반 허프 변환 수행
min_theta, max_theta : 검출할 선분의 최소, 최대 theta 값

이 함수를 사용하려면 입력 영상이 이진화 된 영상이여야 하므로, Canny와 같은 필터를 먼저 수행하는 것을 권장한다. 

다음 건물 사진에서 HoughLines 함수를 통해 선분을 검출해보자.

예제코드는 다음과 같다.

// grayscale로 변환
val graySrc = Mat()
Imgproc.cvtColor(src, graySrc, Imgproc.COLOR_BGR2GRAY)

// 캐니 엣지 검출
val edge = Mat()
Imgproc.Canny(graySrc, edge, 50.0, 100.0)

// 허프 선 변환 함수로 선 검출하기
val lines = Mat()
Imgproc.HoughLines(
    edge,
    lines,
    1.0, // 1픽셀 간격
    Math.PI / 180.0, // 1도 간격
    300
)

// 엣지 영상을 컬러 영상으로 변환
Imgproc.cvtColor(edge, edge, Imgproc.COLOR_GRAY2BGR)

// 검출한 선 그리기
for (x in 0 until lines.rows()) {
    val rho = lines.get(x, 0)[0]
    val theta = lines.get(x, 0)[1]
    val a = cos(theta)
    val b = sin(theta)
    val x0 = a * rho
    val y0 = b * rho
    val pt1 = Point(round(x0 + 5000*(-b)), round(y0 + 5000*(a)))
    val pt2 = Point(round(x0 - 5000*(-b)), round(y0 - 5000*(a)))
    Imgproc.line(edge, pt1, pt2, Scalar(0.0,0.0,255.0), 3)
}
// 결과 엣지 영상 출력

코드를 실행한 결과는 다음과 같다.

검출한 선분에 대한 정보는 rho와 theta 뿐이기 때문에 이를 선분으로 그리기 위해 직선 그래프 상의 임의 점 두개를 선택해 직선으로 그렸다. 그래서 영상 내에 직선과 관계 없는 객체에도 빨간선이 덧 그려지는 것을 확인할 수 있다.

확률적 허프 변환에 의한 선분 검출

확률적 허프 변환은 허프 변환 알고리즘 일부를 수정한 알고리즘이다. 모든 점을 고려하지 않는 대신에 선분이라 판단되는 임의의 정점셋트만 검출한다. 

선분을 더 잘 판단하기 위해 확률적 허프 변환 알고리즘은 다음의 두 가지 내용을 개선한다.

• 검출할 선분의 최소 길이 : 직선을 형성하기 하기 위한 임계 값보다 많은 픽셀이 있지만 직선의 길이가 매우 짧다면 직선으로 받아들여지지 않는다.
• 직선으로 간주할 최대 간격 : 직선을 형성할 픽셀 그룹과 그룹사이의 거리가 매우 먼 경우 직선으로 인정되지 않는다.

OpenCV에서 제공하는 확률적 허프 변환 함수, HoughLinesP 에 대해서 살펴보자.

Imgproc.HoughLinesP(
    Mat image, Mat lines, double rho, double theta, 
    int threshold, double minLineLength, double maxLineGap
)

image : 입력 영상 
lines : 선분의 시작과 끝 좌표를 담고 있는 배열
rho : 누적 배열에서 rho 값의 간격. ex) 1.0 -> 1픽셀 간격 
theta : 누적 배열에서 theta 값의 간격. ex) Math.PI / 180 -> 1도 간격 
threshold : 누적 배열에서 직선으로 판단할 임계값 
minLineLength : 검출할 선분의 최소 길이
maxLineGap : 직선으로 간주할 최대 간격

예제코드는 다음과 같다.

// grayscale로 변환
val graySrc = Mat()
Imgproc.cvtColor(src, graySrc, Imgproc.COLOR_BGR2GRAY)

// 캐니 엣지 검출
val edge = Mat()
Imgproc.Canny(graySrc, edge, 50.0, 100.0)

// 허프 선 변환 함수로 선 검출하기
val lines = Mat()
Imgproc.HoughLinesP(
    edge,
    lines,
    1.0, // 1픽셀 간격
    Math.PI / 180.0, // 1도 간격
    100,
    150.0,
    25.0
)

// 엣지 영상을 컬러 영상으로 변환
Imgproc.cvtColor(edge, edge, Imgproc.COLOR_GRAY2BGR)

// 검출한 선 그리기
for (x in 0 until lines.rows()) {
    val l: DoubleArray = lines.get(x, 0)
    Imgproc.line(
        edge,
        Point(l[0], l[1]), // 시작점 좌표
        Point(l[2], l[3]), // 끝점 좌표
        Scalar(0.0, 0.0, 255.0),
        3
    )
}
//edge 출력

코드를 실행한 결과는 다음과 같다.

마치며 

상황에 따라 HoughLines 또는 HoughLinesP 함수를 통해 직선을 검출 할 수 있다. 함수의 파라미터를 적절히 조절하여 원하는 직선 성분을 검출 하자. 허프 선 변환은 퍼포먼스가 빠른 알고리즘은 아니기 때문에, 이러한 부분을 유의하여 사용해야 한다.

후원하기