OpenCV로 배우는 영상 처리 및 응용/ 영상 분할 및 특징 처리

허프 변환

직선 검출 방법 중 가장 널리 사용되는 것은 허프 변환(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}$ 곡선을 이룬다.

허프 변환은 다음과 같은 세부적인 과정을 거쳐서 수행된다.
- 허프 변환 좌표계에서 행렬 구성
- 영상 내 모든 화소의 직선 여부 검사
- 직선 인지 좌표에 대한 허프 변환 누적 행렬 구성
- 허프 누적 행렬의 지역 최대값 선정
- 임계값 이상인 누적값(직선) 선별
- 직선 $(\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보다 큰 화소를 직선으로 간주한다.