허프 변환
- 직선 검출 방법 중 가장 널리 사용되는 것은 허프 변환(Hough transform)이다.
- 허프 변환은 영상 내의 선, 원 뿐만 아니라 임의의 형태를 지닌 물체를 감지해 내는 대표적인 기술로서 데이터 손실 및 왜곡이 포함된 영상에서도 직선을 잘 추출한다.
허프 변환의 좌표계
- 허프 변환은 아래의 수식과 같이 직교 좌표계로 표현되는 영상의 에지 점들을 오른쪽 식의 극좌표계로 옮겨 검출하고자 하는 물체의 파라미터$(\rho, \theta)$를 추출하는 방법이다.
$y = ax + b \leftrightarrow \rho = x \cdot cos \theta + y \cdot sin \theta$
- 직교 좌표계에서는 수직선일 경우 기울기가 무한대가 될 수 있으며, 검출되는 직선의 간격이 동일하지 않아서 검출 속도와 정밀도에서 문제가 될 수 있다.
- 반면 극좌표계를 사용하면 직선이 원점에서 떨어진 수직 거리$(\rho)$와 이 수직선이 x축과 이루는 각도$(\theta)$를 이용해서 직선을 표현할 수 있다.
- 또한 직선의 수직거리와 각도를 일정한 간격으로 검출함으로써 정밀한 직선 검출이 가능하다.
- 직교 좌표계에서 하나의 직선상에 놓인 좌표들을 허프 변환 좌표계로 표시하면 아래 그림과 같다.
- 직선 A 상에 검출된 3개의 지점 $a_{1}, a_{2}, a_{3}$가 있다고 가정하자.
- 먼저 직선 A는 $\rho_{1} = x \cdot cos \theta_{1} + y \cdot sin \theta_{1}$ 로 표현할 수 있다.
- 이 수식에 따라 직선 A는 허프 변환 좌표계에서 한 점 ($\rho_{1}, \theta_{1}$)의 좌표로 나타난다.
- 또한 영상 좌표에서 3개의 지점($a_{1}, a_{2}, a_{3}$)은 허프 변환 좌표($\rho_{1}, \theta_{1}$)를 같이 공유한다.
- 또한 직교 좌표계에서 한 점은 허프 변환 좌표계에서는 곡선으로 표현된다.
- 즉, $a_{1}$ 좌표에서 그려질 수 있는 수많은 직선이 존재하며, 많은 $(\rho_{i}, \theta_{i})$로 표현되어, 결과적으로 아래 그림의 b에서 $a_{1}$ 곡선을 이룬다.
https://drive.google.com/uc?id=11G-fhdj3OQxy_g2Tji09heRCcAKt0MN4
허프 변환의 전체 과정
- 허프 변환은 다음과 같은 세부적인 과정을 거쳐서 수행된다.
- 허프 변환 좌표계에서 행렬 구성
- 영상 내 모든 화소의 직선 여부 검사
- 직선 인지 좌표에 대한 허프 변환 누적 행렬 구성
- 허프 누적 행렬의 지역 최대값 선정
- 임계값 이상인 누적값(직선) 선별
- 직선 $(\rho_{i}, \theta_{i})$을 누적값 기준으로 내림차순 정렬
- 먼저 영상의 크기에 맞게 허프 변환 좌표계를 위한 행렬을 구성한다. 이 행렬은 검출된 직선을 좌표 $(\rho, \theta)$로 표시해서 값을 누적하기 위한 것이다.
- $\rho$는 $-\rho_{max}$에서 $+\rho_{max}$까지의 범위를 가지고, $\theta$는 $0 - \pi$까지의 범위를 가지며, 다음의 수식으로 계산된다.
- 여기서 height, width는 원본 영상의 크기이며, acc_h, acc_w는 허프 누적 행렬의 크기이다.
$-\rho_{max} \leq \rho \leq \rho_{max}, \rho_{max} = height + width$
$acc_h = {\rho_{max} \times 2 \over \Delta \rho}$
$0 \leq \theta \leq \theta_{max}, \theta_{max} = \pi$
$acc_w = {\pi \over \Delta \theta}$
- 따라서 허프 행렬의 크기는 거리 간격$(\Delta \rho)$과 각도 간격$(\Delta \theta)$에 따라 조절되며, 거리 간격과 각도 간격이 작을수록 행렬의 크기가 커져서 해상도가 높아진다.
- 예컨대 각도 간격을 2도로 하면 가로$(\theta)$ 방향으로 90개의 원소가 필요하며, 1도 간격으로 하면, 180개의 원소가 필요하다.
허프 누적 행렬 구성
- 다음으로 영상 내의 모든 좌표에서 직선인지 여부를 점검한다. 허프 변환에 입력되는 영상은 먼저 이진화나 모폴로지와 같은 다양한 전처리를 수행하여 잡음을 제거하고 직선 성분을 검출한다.
- 일반적으로 캐니 에지 검출과 같이 이진 영상을 허프 변환의 입력 영상으로 사용한다. 따라서 입력 영상에서 0보다 큰 화소를 직선으로 간주한다.