Hough Transform (허프 변환)으로 직선 찾기

데이빗 2016-02-29 (월) 14:12 8년전 39357  

이미지 혹은 영상에서 직선을 찾기 위해서 다양한 방법을 사용할 수 있겠다. 대략 세가지 방식을 생각할 수 있는데, 1) curve fitting, 2) RANSAC, 3) Hough Transform을 이야기 할 수 있다. curve fitting은 많은 점들을 가지고 최적의 라인을 찾는 것으로 다수의 점을 가지고 직선을 찾는 개념이고 RANSAC은 (Random Sample Consensus)의 약자로 두 점을 가지고 랜덤하게 추출한 후, 최적의 직선을 구하거나 아웃라이어 혹은 특이점을 제거하는 알고리즘이다. 

오늘 다루게 될 허프 변환은 실시간으로 사용할 수 있을 정도로 빠른 직선 처리와 간단한 알고리즘으로 이미 많이 사용되는 알고리즘으로 OpenCV 라이브러리에 내장되어 있기도 하다. 

허프 변환 (Hough Transform)은 논문으로 나와있는 구체적인 설명은 없고 특허로 지정이 되어 있다. 허프 변환을 간단하게 설명하면, 수식으로 표현할 수 있는 도형 (직선, 원, 타원, 쌍곡선 등등)이라면 검출할 수 있다는 것이다. 
가장 널리 사용하고 있다고 하면, 무인자동차의 차선을 검출과 같이 직선을 검출하는 것인데, 다음과 같은 원리로 사용할 수 있다. 
cba7d75088069cd02a9535379e0eb2c0_1456722


x-y 평면은 이미지라고 생각할 수 있다. 그리고, 이미지 안에 있는 빨간 직선을 찾는 알고리즘을 허프 변환을 통해 찾을 수 있는데, 쎄타와 r (혹은 rho)라는 두 개의 파라미터를 가지고 구할 수 있다. 
즉, 빨간 직선에 수직인 선분 r은 cba7d75088069cd02a9535379e0eb2c0_1456722으로 표현할 수 있다. 
실제 이미지에 허프 변환을 바로 적용하기에는 계산량이 많기 때문에 엣지 검출 알고리즘인 Canny Edge Detection 알고리즘들과 같이 쓰이며, 검출된 엣지들에 있는 점을 적용하여 직선을 찾을 수 있다. 

예를 들어 다음과 같이 세 개의 점이 있다고 가정하자. 우리 눈에 보이기에는 핑크색 선이 세 개의 점을 연결하는 직선이고 우리가 관심있는 직선이다. 표에서 Angle은 쎄타고, Dist.는 거리 r을 의미한다. 
(하단의 왼쪽에 있는 그래프와 표는 세개의 점 중 왼쪽 상단의 첫번째 점까지의 거리와 각도를 나타낸 것이고, 중앙의 그래프와 표는 중앙 점에 대한 거리와 각도, 오른쪽의 그래프와 표는 오른족 하단의 점까지의 거리와 각도를 표현)

cba7d75088069cd02a9535379e0eb2c0_1456722


위에서 얻은 각도와 거리를 다시 그래프로 표현하면 다음과 같이 사인파의 그래프로 표현이 될 수 있다. 
cba7d75088069cd02a9535379e0eb2c0_1456722

그리고, 약 60도에서 검출된 교점이 우리가 찾는 핑크색 직선이다. 
만약, 위의 r-쎄타 평면 (혹은 Distance-Angle 평면)에서 많은 수의 점들이 한곳에서 만난다면 그 점은 쎄타와 r로 표현할 수 있는 직선일 가능성이 매우 크다.

실제로 코딩을 통해 배워보도록 한다. 

다음의 코딩을 보도록 하자. 
import numpy as np
import cv2

img = cv2.imread('road.jpg',1)
cv2.imshow('Original',img)
gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
cv2.imshow('Gray',gray)
edges = cv2.Canny(gray,250,500,apertureSize = 3)
cv2.imshow('Edges',edges)
lines = cv2.HoughLines(edges,1,np.pi/180,170)

for rho,theta in lines[0]:
    a = np.cos(theta)
    b = np.sin(theta)
    x0 = a*rho
    y0 = b*rho
    x1 = int(x0 + 1000*(-b))
    y1 = int(y0 + 1000*(a))
    x2 = int(x0 - 1000*(-b))
    y2 = int(y0 - 1000*(a))

    cv2.line(img,(x1,y1),(x2,y2),(0,0,255),2)

cv2.imshow('Lines',img)

k = cv2.waitKey(0)
if k == 27:         # wait for ESC key to exit
    cv2.destroyAllWindows()

중간중간에 보이는 cv2.imshow는 알고리즘의 중간단계에서 보이는 이미지들을 보기 위함이다. 
실행하면 다음과 같은 결과를 확인할 수 있다. 

cba7d75088069cd02a9535379e0eb2c0_1456722

cba7d75088069cd02a9535379e0eb2c0_1456722

cba7d75088069cd02a9535379e0eb2c0_1456722

cba7d75088069cd02a9535379e0eb2c0_1456722


엣지를 검출하기 위한 알고리즘 중 가장 유명한 것은 캐니 알고리즘이며 (Canny Edge Detector) OpenCV에서는 Canny라는 함수로 사용할 수 있다. 
edges = cv2.Canny(gray,250,500,apertureSize = 3)

위에서 첫번째 Thresdhold와 두번째 Threshold인 250과 500을 각각 변경하면 다음과 같이 엣지가 다르게 나온다. 

cba7d75088069cd02a9535379e0eb2c0_1456722

edges = cv2.Canny(gray,150,300,apertureSize = 3)일 경우

cba7d75088069cd02a9535379e0eb2c0_1456722

edges = cv2.Canny(gray,50,150,apertureSize = 3)일 경우

즉, 처음에 엣지 검출을 통해서 상당한 수의 자잘한 세그먼트들을 필터링한다면 이후에 이루어질 허프 변환 처리 속도가 빨라질 수 있다. 

그리고, lines = cv2.HoughLines(edges,1,np.pi/180,170)가 허프변환을 통해 라인을 검출하는 알고리즘이며, 170이라는 숫자가 올라갈 수록 많은 교점이 있는 직선을 검출한다. 즉, 170을 70으로 바꾸면 다음과 같이 검출하게 된다. 
cba7d75088069cd02a9535379e0eb2c0_1456722


허프 변환은 이렇듯 직선을 검출하는데 유용하게 사용하며 다음 시간에는 허프 변환을 사용하여 원을 검출하는 알고리즘에 대해서 적용해보도록 하겠다. 

메카리워즈 Image Map


모바일 버전으로 보기