허프 원 변환(Hough Circle Transform;CHT)

지난 포스팅에서 직선을 검출하는 허프 선 변환에 대해서 알아보았다. 이번 포스팅에서는 허프 변환을 통해 원을 검출하는 방법에 대해서 알아본다.

우선 우리가 알고 있는 원을 표현하는 표준 원 방정식은 다음과 같다.

(x-a)2 + (y-b)2 = r2

r은 반지름(radius)을 의미하고, (a,b)은 원의 중심을 의미 한다. 이 방정식에서 원을 표현하기 위해 우리는 3개의 파라미터(a,b,r)를 필요로 하고 있다.

이전에 허프 선 변환에서는 두개의 파라미터 (ρ, θ) 사용 했기 때문에, 2차원 누적 배열을 통해 선을 검출 할 수 있었다. 하지만, 원을 찾기 위한 허프 원 변환은 3개의 파라미터를 필요로 하기 때문에, 3차원 누적배열이 필요하다. 이것은 많은 용량의 메모리를 요구하고, 연산 속도 또한 느리게 만든다. 

반지름을 알고 원을 찾기

만약 이미지내에서 반지름의 길이를 알고 있다면, 누적배열을 2차원 평면으로 다시 바꿀수 있게 된다. 원의 중심인 (a, b)만 찾으면 되기 때문이다.

수정된 방정식은 다음과 같다

x = a + r * cos(θ)
y = b + r * sin(θ)

파라미터 공간 상에서 (a, b) 점의 궤적은 (x, y)를 중심으로하는 반경 r의 원에 속하게 된다. 

다음의 이미지를 참고하자.

위 이미지에서 왼쪽의 그래프는 기하학 공간상의 그래프이고, 오른쪽의 그래프는 파라미터 공간상의 그래프이다.

왼쪽에서 실제 원이 포함하고 있는 각 점들이 오른쪽의 파라미터 공간상에서 새로운 원을 생성하고 있다. 이렇게 파라미터 공간상에서 원을 누적시켜서 그려보면 가장 많이 누적되는 값(빨간점)이 실제 원의 중심값임을 알수 있게 된다.

이 부분은 다음의 영상을 보면 조금 더 이해하기 쉬울 것 같다. (3분 30초쯤 에서 잘 설명 되어있다. )

반지름을 알고 여러 원을 찾기

동일한 반지름을 가진 여러 원을 동일한 방법으로 찾을 수 있다. 왼쪽 실제 원의 중심점은 오른쪽 그림의 파라미터 공간 그래프에서 빨간색 점으로 표현된다. 원이 여러개 겹치다보면 파란색 점과 같은 가짜 중심점도 발견 될 수 있다. 이럴 때는 원본 이미지의 원과 대조하여 가짜 원을 제거 할 수 있다.

반지름을 모르고 원을 찾기

반지름을 알 수 없는 경우에는 r을 고정할 수 없으므로 3개의 변수가 필요하며, 파라미터 공간이 3차원으로 바뀐다. 허프 변환 방식으로 동일하게 원을 찾으려고 하면 원을 구성하는 점의 궤적이 파라미터 공간에서 원뿔형태로 나타난다.

원뿔 표면을가장 많이 교차하는 부분이 반지름이 된다. 이런식으로 반지름을 몰라도 원을 찾을 수는 있지만 많은 메모리와 연산량을 요구하게 되므로 보통은 계산을 줄이기 위해 그래디언트(방향)를 이용하여 계산을 하게 된다.

Hough Gradient Method

이름에서 알 수 있듯이 이 방법은 그래디언트를 고려한다. 위의 방법들은 각 엣지 포인트에 대해 파라미터 공간에 해당 원을 그려서 누적되는 것으로 원을 유추 했다. 그러나 이제는 전체 원을 그리는 대신 엣지 픽셀의 그래디언트 방향으로 직선을 그리면서 값을 누적시킨다.

엣지를 순회하며 직선을 그린 결과 가장 많이 누적된 픽셀이 원의 중심점이 되는 것이다.

이렇게 하면 원의 중심점 (a, b) 를 찾았기 때문에 반지름(r)만 찾으면 된다. 반지름에 대한 적절한 임계값(threshold)을 설정하고, 원의 중심으로 부터 원을 조금씩 크게 그려 나가면서 원이 될만한 후보군을 선별한다.

허프 원 변환 검출 함수

OpenCV에서 제공하는 허프 원 변환 검출 함수는 다음과 같다.

Imgproc.HoughCircles(
    Mat image, Mat circles, int method, double dp, 
    double minDist, double param1, double param2, 
    int minRadius, int maxRadius
) 

image : 회색조 입력영상(내부에서 Canny를 적용하므로 엣지영상 X)
circles : (cx, cy, r) 정보를 담고 있는 Mat
method : OpenCV4.2 이하에서는 HOUGH_GRADIENT만 지정가능. 
         이 포스팅에서도 HOUGH GRADIENT METHOD에서만 설명했다.
dp : 입력 영상과 누적 배열의 크기 비율. 1이면 동일크기. 2이면 축적배열의 가로, 세로 크기가 입력영상의 반
minDist : 검출된 원 중심점들의 최소 거리
param1 : Canny 엣지 검출기의 높은 임계값
param2 : 누적 배열에서 원 검출을 위한 임계값
minRadius, maxRadius : 검출할 원의 최소, 최대 반지름

이미지 속 동전 검출 예제

실제 위와 같은 이미지가 있고 이미지 내의 동전을 검출하는 예제를 살펴보자

// grayscale로 변환
val graySrc = Mat()
Imgproc.cvtColor(src, graySrc, Imgproc.COLOR_BGR2GRAY)
// 좀 더 정확한 검출을 위해 잡음 제거를 위한 가우시안 블러처리
val blurred = Mat()
Imgproc.GaussianBlur(graySrc, blurred, Size(0.0, 0.0), 1.0)
// 허프 원 변환을 통한 원 검출
val circles = Mat()
Imgproc.HoughCircles(
    blurred,
    circles,
    Imgproc.HOUGH_GRADIENT,
    1.0, // 입력 영상과 누적배열 비율
    50.0, // 검출된 원 중심점들의 최소 거리
    150.0, // Canny 에지 검출기의 높은 임계값
    40.0, // 누적 배열에서 원 검출을 위한 임계값
    50, // 원의 최소 반지름
    150 // 원의 최대 반지름
)
// 검출한 원에 덧그리기
for (i in 0 until circles.cols()) {
    val circle = circles.get(0, i) // 검출된 원
    val centerX = circle[0] // 원의 중심점 X좌표
    val centerY = circle[1] //원의 중심점 Y좌표
    val radius = Math.round(circle[2]).toInt() // 원의 반지름
    val center = Point(
        Math.round(centerX).toDouble(),
        Math.round(centerY).toDouble()
    )
    val centerColor = Scalar(0.0, 0.0, 255.0)
    Imgproc.circle(src, center, 3, centerColor, 3)
    val circleColor = Scalar(255.0, 0.0, 255.0)
    Imgproc.circle(src, center, radius, circleColor, 3)
}

//src 나타내기

원을 검출한 결과는 다음과 같다.

후원하기