Hough Tranform 은 직선을 표현하는 방법으로, 그림에서 직선(혹은 선분)을 검출하는 알고리즘을 지칭하기도 한다.
Hough Tranform에 대한 간단한 설명과 Python으로 구현한 코드, 그리고 CV2 library에서 제공하는 함수에 대해 알아보자.
1. Parametrization of Line
2차원 공간에서 직선을 나타내는(정의하는) 방법에 대해 생각해보자.
- 기울기(a)와 절편(b) 을 사용해 직선을 정의할 수 있다. (그림 왼쪽) 이 때, 두 parameter 값의 범위는 a, b ∈ (-∞,∞) 이다.
- 어떤 두 점을 지나는 직선은 유일하게 존재한다. 따라서 두 점 $(x_1, y_1)$, $(x2,y2)$을 사용해 유일한 직선을 정의할 수 있다. (중간 그림). 주어진 image의 크가가 유한하다면, image에 존재하는 한 점 $x_i$, $y_i$ 값의 범위 역시 유한한 실수 공간에 포함된다.
- 직선을 정의하는 세 번째 방법은 (1) 원점을 지나면서 (2) 대상 직선과 직교로 만나는 선분을 사용하는 것이다. 이 선분의 길이 ρ와 원점에서의 각도 θ가 주어지면, 이 선분과 직교하면서 선분의 끝 점에서 교차하는 직선을 유일하게 정의할 수 있다. 또한, 주어진 image의 크기가 유한하다면, 두 parameter의 범위는 $ρ^2$ ∈ [0, max( $x^2$ + $y^2$) ], θ ∈ [0, π] 가 된다.
직선을 검출할때 어떤 방법이 더 효율적일까? 극단적인 예로, 직선 y=0을 위의 3가지 방법으로 나타내보자. 기울기가 무한대이기 때문에,
- a = ∞, b=0
- (0,0), (0,1)
- ρ=0, θ=0
이 된다. 알고리즘에서 무한대를 다루기 힘들기 때문에, 2번이나 3번 방법으로 직선을 parametrization 하는것이 더 효율적이다.
2. Line detection algorithm
image에서 직선의 존재를 어떻게 찾을 수 있을까? Hough(1959)가 제시한 방법은 (1) 임의의 두 점을 지나는 직선을 정하고, (2) 그 직선 위에 있는 점이 (많이) 있다면, image에 직선이 존재한다고 하는 것이다. (1번 or 2번 방법) 이후, Richard et al.(1972) 에서 기울기와 절편 대신, 직교 선분의 (ρ, θ)을 사용한 algorithm을 제안했다. 구체적인 algorithm을 알아보자.
먼저, Cartesian 좌표로 주어진 점을 지나는 모든 직선들을 (그 직선과 직교하는 선분의) hough 공간의 parameter인 ρ, θ로 변환해야 한다. 이를위해, 점의 좌표 (x,y)와 (ρ, θ)의 관계식을 정리하면 다음과 같다.
$ \cfrac{x}{\rho} = cos(\theta) $, $ \cfrac{y}{\rho} = sin(\theta) $, $ \rho^2 = x^2 + y^2 $
따라서, $\theta$ 탐색 단위를 △$\theta$ 라고 한다면, 점 (x,y)를 지나는 모든 직선의 ($\rho, \theta$)는
$ \rho = x cos(\theta) + y sin(\theta) $,
for $\theta = 0$, △$\theta$, 2△$\theta$, ..., $\pi$
로 나타낼 수 있다.
이제, image에 존재하는 모든 점들에 대해, 각 점은 지나는 직선들을 hough space에 기록한다. 아래 그림 왼쪽은 4개의 점과, 그 점들을 지나는 1개의 직선이 존재하는 image이고, 오른쪽 그림은 이를 hough space로 변환한 것이다. (x축은 $\theta$, y축은 $\rho$). hough space에서 threshold를 넘는 지점을 "image에 존재하는 직선" 과 직교하는 선분과 대응되는 것이다.
원본 image에 존재하는 직선을 Hough Transform으로 변환하는 Python 코드는 아래와 같다.
import numpy as np
from PIL import Image
import cv2
filename = 'data/data1.jpg'
data = cv2.imread(filename)
data = cv2.cvtColor(data, cv2.COLOR_BGR2GRAY)
# parameter
unit_theta = np.pi/180
unit_rho = 3
max_rho = data.shape[0]**2 + data.shape[1]**2
grid_rho = max_rho // unit_rho
list_theta = np.arange(0, np.pi, unit_theta)
sin_data = [np.sin(x) for x in list_theta]
cos_data = [np.cos(x) for x in list_theta]
# set hough matrix
num_row = grid_rho * 2 + 1
hough_data = np.zeros((num_row, len(sin_data)))
for y in reversed(range(data.shape[0])):
for x in range(data.shape[1]):
if data[y][x] > 0:
for ind_theta in range(len(sin_data)):
rho = round(y * sin_data[ind_theta] + x * cos_data[ind_theta])
rho += grid_rho
hough_data[rho][ind_theta] += 1
hough_data = 255*hough_data/np.amax(hough_data)
pil_image=Image.fromarray(hough_data)
pil_image.show()
3. CV2 함수
CV2 library에서 제공하는 함수를 통해 Hough Transform으로 직선을 검출할 수 있다. HoughLines() 함수는 이미지에 존재하는 모든 점을 지나는 직선을 Hough space 로 변환하고, 주어진 threshold를 넘는 직선을 찾아낸다.
import cv2
cv2.HoughLines(image, rho, theta, threshold)
rho : real, [0,1] , $\rho$의 단위. 값이 1이면 1 pixel 단위로 $\rho$를 변화시키며 직선을 검출한다. 값이 작아질수록 더 세밀하게 직선을 검출한다.
theta : [0, 2$\pi$), $\theta$ 단위. 값이 $\cfrac{\pi}{180}$ 이면, $theta$의 탐색 grid를 1 radian 단위로 하여 직선을 검출한다. 따라서 theta 값이 작을수록 더 세밀하게 직선을 검출한다.
threshold : Hough space에서 직선이라고 정의할 값의 기준. threshold의 값이 작을수록 더 많은 직선을 검출한다.
