1. 허프 변환이란?
허프변환은 이미지에서 모양(직선)을 찾는 가장 유명한 방법으로
서로 직선 관계를 갖는 픽셀들만 골라내는 것이 핵심이다.
직선만 찾는 것이 아닌 원과 같은 수식으로 표현할 수 있는 모든 도형을 인식할 수 있다.
자율주행차에서 도로의 차선을 검출할 때 쓰는 알고리즘으로
도로의 차선(직선)을 받아서 그 정보를 사용할 수 있도록 한다.
2. 허프 선 변환
허프 선 변환(Hough line transform)의 기본 개념은 2차원 이미지 상의 어떠한 점은 선의 일부라는 사실을 기초로 한다.
2-1. 원리
허프변환은 직선의 방정식을 이용하는데
하나의 점을 지나는 무수한 직선의 방정식은 y=ax+b 로 표현할 수 있으며, 이를 극좌표 방정식으로 변환해서 아래의 식으로 사용한다.
ρ(rho) = xcos𝜃 + ysin𝜃
(사진 출처: https://en.wikipedia.org/wiki/Hough_transform)
위 식에서 ρ는 직선과 원점의 거리이고, 𝜃는 직선과 x축이 이루는 각도이다.
점 (x, y)를 지나는 직선은 무수히 많이 존재한다. 따라서 점 (x, y)를 지나는 각각의 직선들은 (ρ, 𝜃)값이 고유하게 존재하게 된다.
예로 들어 아래 그림과 같이 (a1, b1), (a2, b2) 두 점이 있을 때,
a1, b1)을 지나는 직선은 무수히 많다.
(a1, b1)을 중심으로 직선을 반시계 방향으로 돌리면서 (ρ, 𝜃)값을 기록하다가 (a2, b2)를 지날 때의 (ρ, 𝜃)를 (ρ1, 𝜃1)이라고 하자.
마찬가지로 (a2, b2)를 지나는 직선도 반시계 방향으로 돌리면서 (ρ, 𝜃)값을 기록하다가 (a1, b1)를 지날 때의 (ρ, 𝜃)값을 기록하면 (ρ1, 𝜃1)일 것이다.
만약 평면상에 (a1, b1), (a2, b2) 두 점만 존재하고 각각의 점을 지나는 직선에 대해 (ρ, 𝜃)의 값을 카운팅하면 (ρ1, 𝜃1)만 2가 되고, 나머지는 1이 될 것이다.
이것이 바로 허프변환을 이용한 이미지에서 직선을 찾는 핵심적 원리이다.
실제 이미지에 허프변환을 바로 적용하기에는 계산량이 많기에 엣지 검출 알고리즘인 Canny Edge Detection 알고리즘과 같이 쓰인다.
3. 허프 변환을 이용한 선분 검출
OpenCV에서 허프 변환을 이용해 선분을 검출할 수 있는 함수
Imgproc.HoughLines(
Mat image, Mat lines, double rho, double theta, int threshold,
double srn, double stn, double min_theta, double max_theta
)3-1. parameter
- image : 입력 영상
- lines : 검출한 선분, rho와 theta정보를 담고 있다.
- rho : 누적 배열에서 rho 값의 간격.
ex) 1.0 -> 1픽셀 간격 - theta : 누적 배열에서 theta 값의 간격.
ex) Math.PI / 180 -> 1도 간격
(theta값을 촘촘히 나누면 연산에 오랜 시간을 소비하지만 정밀한 검출이 가능하다) - threshold : 누적 배열에서 직선으로 판단할 임계값(검출량을 조절할 수 있음)
- srn, stn : 멀티 스케일 허프 변환에서 rho 해상도, theta 해상도를 나누는 값.
(기본값은 0이고, 이 경우 일반 허프 변환 수행) - min_theta, max_theta : 검출할 선분의 최소, 최대 theta 값
HoughLines 함수를 사용하려면 Edge detection된 이미지를 사용해야하므로 Canny Edge Dectection과 같은 필터를 먼저 수행해야 한다.
허프변환은 모든 점에 대해서 계산을 하기 때문에 시간이 많이 소요되는데 이를 개선한 것이 확률적 허프 변환에 의한 선분 검출이다.
4. 확률 허프 변환
허프 변환과의 차이점은 결과값 lies의 파라미터가 다르다는 것이다.
허프 변환 함수는 ρ와 𝜃 값으로 직선의 파라미터 정보를 제공했지만, 확률적 허프 변환 함수는 직선의 시작과 끝 정보를 제공한다.
확률 허프 변환은 직선일 수 있는 픽셀들의 좌표만 연산하기에 연산량이 줄어들어 속도가 빠르다.
