허프 변환 (Hough Transformation)

✣

허프 변환의 동작을 요약하면 다음과 같다. 입력된 각각의 점 $(x_{i},y_{i})$ 에 대해 $(a,b)$ 공간에 직선 $b=-ax_{i}+y_{i}$를 그린 다음 이들 직선이 만나는 점 $(a,b)$를 찾아 $a$를 기울기, $b$를 $y$절편으로 취한다. 만나는 점은 투표로 알아낸다.

 

"투표"의 의미?

각각의 직선은 자신이 지나는 점에 1만큼씩 투표를 한다. 결국 직선이 지나지 않는 곳은 0, 직선이 지나는 곳은 1표, 두 직선이 만나는 곳은 2표를 받는다. 

허프 변환의 원리

앞서 설명한 허프 변환은 이상적인 상황을 가정했다. 실제 상황에서 구현하 때는 몇 가지 사항을 신중히 고려해야 한다. 

1) 위 그림에서는 두 점만 고려했는데 현실에서는 많은 점이 있고 점들이 완벽히 일직선을 이루지 못함
-> 이 문제는 (a,b)공간을 이산화하여 해결한다. 예를 들어 a와 b의 범위를 -1000~1000으로 설정하고 각각을 크기가 20인 구간 50개로 나누어 칸이 50x50=2500 개인 2차원 누적 배열 v를 만든다. v를 0으로 초기화한 다음 (a,b)공간에서 각각의 직선은 자신이 지나는 모든 칸에 1만큼씩 투표한다.

2) 투표가 이루어진 누적 배열에 잡음이 많다.

-> 이 문제는 비최대 억제를 사용한다. 지역 최대점(극점, extreme point)만 남기고 임계값을 설정하여 칸을 최종 선택한다. 

 

비최대 억제로 찾은 극점 2개. 그림에서 비최대 억제로 점이 3개 남았는데 임곗값을 5로 설정하면 노란색으로 칠한 점 2개만 최종 선택된다.

허프 변환은 직선 뿐 아니라 이론적으로는 어떤 도형이라도 검출할 수 있다. 예를 들어 원을 검출하려면 원의 방정식을 이용한다. 이 식은 a와 b,r을 포함하므로 (a,b,r) 3차원 누적 배열을 사용해야 한다. 

$$(x-a)^{2}+(y-b)^{2}=r^{2}$$

 

허프 변환 활용

 

원을 검출하는 허프 변환으로 사과 나무 영상에서 사과를 검출하는 프로그램을 만들어 보자. 

cv.HougCircles 함수는 명암 영상에서 원을 검출해 중심과 반지름을 저장한 리스트를 반환다. 

두 번째 인수는 여러 변형 알고리즘 중의 하나를 지정하는데 cv.HOUGH_GRADIENT는 에지 방향 정보를 추가로 사용하는 방법이다. 

세 번째 인수는 누적 배열의 크기를 지정하는데 1로 설정하면 입력 영상과 같은 크기를 사용한다. 

네 번째 인수는 원 사이의 최소 거리를 지정하는데 작을수록 많은 원이 검출된다. 다섯 번째 인수는 캐니 에지 알고리즘이 사용하는 $T_{high}$다. 여섯 번째 인수는 비최대 억제를 적용할 때 쓰는 임계값이다. 일곱번째와 여덟번째는 원의 최소와 최대 반지름을 지정한다. 

 

import cv2
import cv2 as cv

img = cv.imread('apples.jpg')
gray = cv.cvtColor(img, cv.COLOR_BGR2GRAY)


apples = cv.HoughCircles(gray, cv2.HOUGH_GRADIENT, 1, 100, param1=100, param2=40,
minRadius=15, maxRadius=60)

for i in apples[0]:
    cv.circle(img, (int(i[0]), int(i[1])), int(i[2]), (255, 0, 0), 2)
cv.imshow('Apple detection', img)

cv.waitKey()
cv.destroyAllWindows()

실행 결과 사과를 제대로 찾은 경우도 있지만, 없는 곳을 검출한 거짓 긍정과, 있는데 놓친 거짓 부정도 있다. 

또한 위치가 틀어진 경우도 있다. HoughCircles 함수의 인수값을 이리저리 변경하며 실험이 필요하다.