1. Introduction

이미지 프로세싱에서 circle detection은 원형 객체의 위치, 크기를 찾는 기법이다. 홍채 인식부터 농작물 분류 시 이물질 탐지, 자동차의 표지판 인식 등 광범위한 비전 분야에 활용되며 완벽하지 않은 형태 (일부 가려짐, 찌그러짐 등) 의 객체에 대해서도 어느 정도 검출이 가능하다. 대표적인 알고리즘으로 Hough transform을 이용한 Circle Hough transform이 있으며 특징점 기반 검출, 블롭 검출과 같은 방법들이 존재한다. 고전적인 circle detection은 주로 다음과 같은 단계를 거쳐 수행한다.

1. Preprocessing
   색상 공간 변환, 노이즈 제거 등을 수행하여 프로세싱에 알맞게 이미지를 조정한다.
2. Edge detection
   이미지의 엣지를 찾아낸다. 주로 Canny, Sobel 등의 알고리즘이 사용되며 이미지 특성에 따라 Thresholding 처리를 하기도 한다.
3. Circle detection
   검출된 엣지를 분석하여 $(x-a)^2 + (y-b)^2 = r^2$ 형태의 방정식을 충족하는 픽셀의 집합을 찾는다.

OpenCV에서는 circle detection을 수행할 수 있도록 Mat.HoughCircles(), Cv2.MinEnclosingCircle(), SimpleBlobDetector와 같은 기능을 제공한다. 이 문서에서는 해당 방법들을 이용하여 circle detection을 수행하는 예시와 함께 간략한 결과를 알아본다.

실습에 사용할 이미지는 다음과 같다.

2. HoughCircles

Circle hough transform은 Hough transform을 원 검출에 적용한 것으로, 픽셀을 3d parameter space 요소로 변환하여 검출을 수행한다. OpenCV에서 제공하는 Mat.HoughCircles() 메서드는 보통 HoughModes.Gradient를 파라미터로 사용하여 연산을 수행하는데, 이는 3d space를 이용한 검출의 과도한 리소스 사용을 개선하기 위함이다.

HoughModes.Gradient를 파라미터로 설정하는 경우 이미지의 edge와 gradient를 활용한 2단계 연산 방식을 사용하게 된다. 먼저 원 위에 존재하는 한 점의 gradient 방향은 원의 중심을 향하게 되는데, 이를 기반으로 중심 픽셀이 될 수 있는 후보 지점 $(x, y)$를 검출한다. 이후 $(x, y)$를 이용하여 원을 구성할 수 있는 $r$ 값들을 산출, 다시 이를 edge 픽셀과 비교하여 가장 많은 픽셀과 만나는 $r$을 최종 반지름으로 선택하여 원의 정보 $(x, y, r)$을 반환한다.

private void HoughCircles(Mat image)
{
    using var grayscale = image.CvtColor(ColorConversionCodes.BGR2GRAY);
 
    // Mat.HoughCircles(method, quantization interval, distance, ...)
    var circles = grayscale.HoughCircles(HoughModes.Gradient, 1, 20, 60, 30, 10, 20);
 
    if (circles is null || circles.Length == 0)
    {
        MessageBox.Show("Not found");
        return;
    }
 
    using var detected = image.Clone();
 
    foreach (var circle in circles)
    {
        detected.Circle((int)circle.Center.X, (int)circle.Center.Y, (int)circle.Radius, Scalar.Red, 2);
    }
 
    Cv2.ImShow("HoughCircles detected", detected);
}

Mat.HoughCircles() 메서드의 파라미터에 대한 정보는 다음 내용을 참조한다.

1. method
   HoughModes.Gradient, HoughModes.GradientAlt가 지원된다.

   • HoughModes.Gradient : Basically 21HT, described in A COMPARATIVE STUDY OF HOUGH TRANSFORM METHODS FOR CIRCLE FINDING
   • HoughModes.GradientAlt : Variation of HoughModes.Gradient to get better accuracy

2. dp (Quantization interval)
   원의 중심 후보를 찾을 때 사용하는 누적 배열 공간의 양자화 간격 (grid 크기) 에 해당한다. dp = 1을 기준으로 크기가 커질수록 연산 속도가 빨라지지만, 검출 정확도가 떨어지게 된다. (dp = 2이면 픽셀 수는 1/4가 된다)

3. minDist
   원 사이의 최소 중심 간격이다. 이 값보다 적은 간격을 가지는 원은 하나의 원으로 취급된다.

4. param1, param2
   지정된 method에 따라 다른 값을 의미한다.

   • HoughModes.Gradient
     • param1 : Canny edge detection의 high threshold value를 의미하며 내부 필터로 Sobel을 사용한다. low threshold value는 자동으로 high value의 절반이 된다.
     • param2 : 중심 픽셀 후보 지점 $(x, y)$의 threshold value를 의미한다. 설정된 값이 작을수록 더 관대하게 원을 검출한다.
   • HoughModes.GradientAlt
     • param1 : Canny edge detection의 high threshold value를 의미한다. 내부 필터로 Scharr를 사용하므로, HoughModes.Gradient의 high threshold value보다 높은 값을 설정한다. low threshold value는 자동으로 high value의 절반이 된다.
     • param2 : 검출할 원의 perfectness를 의미한다. 1에 가까울수록 완벽한 원에 가까운 객체만 검출된다.

5. minRadius
   검출할 원의 최소 반지름

6. maxRadius
   검출할 원의 최대 반지름

3. MinEnclosingCircle

Blur

MinEnclosingCircle detected

Cv2.MinEnclosingCircle() 메서드는 주로 contour detection 이후 호출하며, 주어진 점들을 포함하는 가장 작은 면적의 원 $(x, y, r)$ 을 반환한다. 수학적으로는 Welzl의 알고리즘을 사용하여 Smallest-circle problem을 풀어낸다. 이 알고리즘은 주어진 점을 random하게 섞은 후 재귀적으로 가장 작은 면적의 원을 찾게 된다. 이 때, 현재의 원 외부에 새로운 점이 나타나면 원을 다시 계산하여 최종적으로 주어진 모든 점을 포함하는 가장 작은 면적의 원을 반환하게 된다.

private void FindContours(Mat image)
{
    using var grayscale = image.CvtColor(ColorConversionCodes.BGR2GRAY);
    using var threshold = grayscale.Threshold(150, 255, ThresholdTypes.Binary);
    // Noise 제거
    using var blur = threshold.MedianBlur(3);
 
    blur.FindContours(out var contours, out var hierarchy, RetrievalModes.External, ContourApproximationModes.ApproxTC89KCOS);
 
    if (contours is null || contours.Length == 0)
    {
        MessageBox.Show("Not found");
        return;
    }
 
    using var detected = image.Clone();
 
    foreach (var contour in contours)
    {
        // 점 또는 선인 경우 length == 0
        double length = Cv2.ArcLength(contour, true);
        if (length == 0)
            continue;
 
        // 너무 작은 면적은 원이 아닐 수 있음
        double area = Cv2.ContourArea(contour);
        if (area < 50)
            continue;
 
        Cv2.MinEnclosingCircle(contour, out var center, out var radius);
 
        // 검출된 원에 대해 필터링이 필요한 경우 다음과 같이 구성할 수 있다.
        // 원형 지표 계산
        double circularity = 4 * Math.PI * area / Math.Pow(length, 2);
 
        double minCircleArea = Math.PI * Math.Pow(radius, 2);
 
        // 원형 지표와 contour/minCircleArea 비율이 60% 이상인 경우 원으로 취급
        // Thresholding 값은 환경에 따라 임의 설정
        if (circularity > 0.6 && area / minCircleArea > 0.6)
        {
            detected.Circle((int)center.X, (int)center.Y, (int)radius, Scalar.Red, 2);
        }
    }
 
    Cv2.ImShow("Blur", blur);
    Cv2.ImShow("MinEnclosingCircle detected", detected);
}

4. SimpleBlobDetector

SimpleBlobDetector는 이미지에서 블롭이라 표현되는 영역을 검출하는 데 사용된다. 여기서 블롭이란, 주변과 구분되는 일관적으로 연결된 픽셀들을 뜻한다. SimpleBlobDetector는 단순한 강체 형태의 객체를 빠르게 찾기 위해 고안된 알고리즘이다. 연산은 다음과 같은 과정을 거쳐 진행된다.

1. Multi level thresholding
   입력받은 이미지를 이용하여 다층 구조의 thresholding을 진행한다. MinThreshold ~ MaxThreshold까지, ThresholdStep 간격으로 binary 이미지를 생성한다.

2. Blob detection
   각각의 binary 이미지에서 픽셀의 덩어리 (blob) 를 찾는다. 이후 다른 이미지의 blob들과 비교하게 되는데, 비슷한 위치에 있는 blob들의 중심 좌표가 MinDistBetweenBlobs보다 가까우면 하나의 blob에 해당하는 것으로 판단하여 병합을 진행한다. 모든 binary 이미지에 대한 blob detection이 완료되면 중심 좌표, 크기 등을 계산한다.

3. Filtering
   사용자가 지정한 SimpleBlobDetector.Params 멤버를 이용하여 검출된 각 blob에 대한 필터링을 진행한다. 필터링을 할 수 있는 요소는 다음과 같다.

   • FilterByArea
   • FilterByColor
   • FilterByCircularity
   • FilterByConvexity
   • FilterByInertia

private void Blob(Mat image)
{
    // FindContours와 같은 전처리 이미지 사용
    using var grayscale = image.CvtColor(ColorConversionCodes.BGR2GRAY);
    using var threshold = grayscale.Threshold(150, 255, ThresholdTypes.Binary);
    using var blur = threshold.MedianBlur(3);
 
    // 색상을 포함한 blob 파라미터 설정
    // 60% 이상의 원형도와 볼록함을 가질 때 원으로 취급
    var blobParams = new SimpleBlobDetector.Params()
    {
        FilterByColor = true,
        BlobColor = 255,
        FilterByArea = true,
        MinArea = 50,
        FilterByCircularity = true,
        MinCircularity = 0.6f,
        FilterByConvexity = true,
        MinConvexity = 0.6f
    };
    using var detector = SimpleBlobDetector.Create(blobParams);
    var blobs = detector.Detect(blur);
 
    if (blobs is null || blobs.Length == 0)
    {
        MessageBox.Show("Not found");
        return;
    }
 
    using var detected = image.Clone();
 
    // Blob key point를 이용하여 원 그리기
    // Cv2.DrawKeypoints() 메서드로 그리는 경우 포인트만 표현됨
    foreach (var blob in blobs)
    {
        detected.Circle((int)blob.Pt.X, (int)blob.Pt.Y, (int)blob.Size / 2, Scalar.Red, 2);
    }
 
    Cv2.ImShow("Blob detected", detected);
}

5. 참조 자료

• OpenCV-Python Tutorials - Hough Circle Transform
• OpenCV-Python Tutorials - Contour Features
• OpenCV docs - cv::SimpleBlobDetector Class Reference
• Wiki - Hough transform
• Wiki - Circle Hough transform
• Wiki - Smallest-circle problem
• A COMPARATIVE STUDY OF HOUGH TRANSFORM METHODS FOR CIRCLE FINDING
• Edge detection
• Thresholding
• Contour detection