컴퓨터 비전에서 직선 검출을 위해 주로 사용하는 허프 변환 기법을 알아보고, 허프 그래디언트 방법을 통해 원을 검출하는 방법을 알아본다.
허프 변환 직선 검출
허프 변환과 직선의 방정식
허프 변환(hough transform) 기법은 2차원 xy좌표에서 직선의 방정식을 파라미터 공간으로 변환하여 직선을 찾는 알고리즘이다.
2차원 평면의 직선은 다음과 같이 나타낼 수 있다.
y=ax+b 이러한 기울기 a, 절편 b라는 파라미터로 결정되는 직선을 바꿔써보면
b = -xa+y 로 쓸 수 있다. 이는 ab공간에서의 -x기울기, y절편인 직선이다.
즉, xy 공간의 직선은 ab 공간에서 한 점으로 표현 가능하고, xy 공간에서 한 점은 ab 공간에서 직선의 형태로 나타난다.
이를 이용한다면 한 직선 위의 두 점 p, q를 통해 ab 공간에서 두 개의 직선을 그을 수 있고, 두 직선이 겹치는 한 점을 통해 xy 공간에서의 직선을 구할 수 있게 된다. 이렇게 구한 직선은 첫 직선(p, q가 지나는)과 동일한 직선이 된다.
허프 변환에서는 직선의 방정식을 찾기 위해 에지로 판별된 모든 점을 이용하여 ab 공간에 직선으로 표현한다. 그리고 직선이 많이 교차하는 좌표를 모두 찾는다.
이 때 교차하는 점을 찾기 위해 축적 배열을 사용한다. 축적배열이란 0으로 초기화된 2차원 배열에서 직선이 지나는 위치를 1씩 증가시켜 생성한 배열을 의미한다.
극좌표계 형식의 직선의 방정식
기존의 y=ax+b 형태의 직선으로는 모든 형태의 직선을 표현하기 어렵다는 단점이 있다.
대표적으로 y축과 평행한 수직선을 표현할 수 없다. (a가 무한대가 되어야 하기 때문에)
따라서 다음과 같은 극좌표계 형식의 직선의 방정식을 사용한다.
xcos(**Θ)+ysin(Θ) = ρ**
ρ 는 직선까지의 수직 거리, Θ 는 원점에서 직선에 수직선을 내렸을 때 x축과 이루는 각도이다.
이때 ρ, Θ가 파라미터로 해당 파라미터 공간에서의 한 점으로 xy공간의 직선을 나타낼 수 있게 된다.
이렇게 구하는 경우에도 축적 배열을 사용하여 국지적 최대값이 발생하는 위치의 파라미터를 구하여 사용한다.
OpenCV HoughLines()
void HoughLines(InputArray image, OutputArray lines,
double rho, double theta, int threshold,
double srn = 0, double srn = 0,
double min_theta = 0, double mx_theta = CV_PI);image는 Canny() 등으로 구한 에지 영상이다.
rho, theta는 축적 배열에서 로와 세타의 해상도값이다. 각각 픽셀과 라디안 단위
threshold는 축적 배열에서 직선으로 판단할 임계값
srm, stn은 멀티스케일 허프 변환에서 각각 rho와 theta의 해상도를 나누는 값이다. 둘 다 0이면 일반 허프 변환을 수행한다.
min_theta, mx_theta는 검출할 직선의 최소, 최대 세타값이다.
확률적 허프 변환
확률적 허프 변환 방법은 직선의 방정식 파라미터인 로와 세타를 반환하는 것이 아니라 직선의 시작점과 끝점 좌표를 반환한다. 즉 선분을 찾는다.
기존의 허프 변환은 직선의 방정식을 알아내는 형태이기에 말 그대로 해당 라인을 포함하는 직선을 구하게 되지만, 확률적 허프 변환은 시작점과 끝점을 통해 선분을 구해내기에 이를 이용하면 실제 직선이 존재하는 위치만을 알아낼 수 있다.
OpenCV에서는 다음으로 구현되어 있다.
void HoughLinesP(InputArray image, OutputArray lines,
double rho, double theta, int threshold,
double minLineLength = 0, double maxLineGap = 0);허프 변환 원 검출
허프 변환을 이용하여 원도 검출할 수 있다. 원의 방정식은 다음과 같이 표현할 수 있다.
(x-a)^2 + (y-b)^2 = r^2
세 개의 파라미터를 가지므로 3차원 파라미터 공간에서 축적 배열을 정의하고 가장 누적이 많은 위치를 찾으면 구할 수 있다.
하지만 이러한 방법은 너무 많은 메모리와 연산을 필요로 한다.
따라서 허프 그래디언트 방법(hough gradient method)를 이용하여 원을 검출해는데, 허프 그래디언트 방법은 파라미터를 두 단계로 나누어 구해낸다.
원의 중심 찾기
파라미터 공간이 아닌 xy 좌표 공간에서 2차원 축적 배열을 만드는데, 영상의 모든 에지 픽셀에서 그래디언트를 구하고 그래디언트 방향을 따르는 직선들로 축적배열을 만든다.
이렇게 하면 원의 방정식 위의 점들(에지 픽셀)로부터 원의 중심방향으로 직선이 그어지게 되고, 축적배열의 값이 큰 부분이 원의 중심이 된다.
원의 반지름 구하기
다양한 반지름의 원에 대해 원주상에 충분히 많은 에지 픽셀이 존재하는지 확인하여 적절한 반지름을 찾는다.
OpenCV HoughCircles()
void HoughCircles(InputArray image, OutputArray circles,
int method, double dp, double minDist,
double param1 = 100, double param2 = 100,
int minRadius = 0, int maxRadius = 0);image는 원본 그레이스케일 영상이다.
method 는 HOUGH_GRADIENT만 지정 가능하다.
dp는 입력 영상과 축적 배열의 크기 비율을 의미한다.
minDist는 인접한 원 중심의 최소 거리
param1, 2 는 각각 Canny에지 검출기의 높은 임계값, 축적 배열에서 원 검출을 위한 임계값을 의미한다.
minRadius, maxRadius는 검출할 원의 최소, 최대 반지름
해당 함수를 실행하면 원본 그레이스케일을 전달받아 내부에서 Sobel() 과 Canny() 를 이용하여 그래디언트와 에지 영상을 계산하고, 허프 그래디언트 방법으로 원을 검출한다.
