Corner detection

Peponi │ 5/22/2025 │ 14m

NugetPackageOpenCvSharp4HarrisShi-TomasiFASTApproxPolyDPCornerSubPix

Corner detection

5/22/2025

14m

Peponi

NugetPackageOpenCvSharp4HarrisShi-TomasiFASTApproxPolyDPCornerSubPix

1. Introduction

Flat

Edge

Corner

이미지 프로세싱에서 corner는 두 개 이상의 edge가 교차하는 지점으로, 이미지의 특정 지점에서 밝기가 두 개 이상의 방향으로 급격하게 변화하는 것을 의미한다. 선 형태를 가진 Edge가 gradient 방향으로 움직일 때만 급격한 밝기 변화를 보여주는 것과 달리, 점의 형태를 가진 corner의 경우 어느 방향으로 움직이더라도 급격한 밝기 변화를 보여준다. 즉, 이미지에서 주변 영역보다 많은 정보를 가지고 있는 것으로 간주할 수 있다. 이런 특징으로 인해 corner는 파노라마 이미지, 객체 추적, SLAM 등의 분야에서 중요한 요소로 활용된다.

Corner detection은 특정 영역의 밝기 분포의 변화를 측정하여 corner를 검출하게 된다. 기본적으로 Sobel, Scharr 과 같은 커널을 이용한 correlation 연산을 통해 각 방향의 gradient 정보를 얻은 후 이를 활용하여 cornerness를 산출하게 된다. 이후 thresholding, non-maximum suppression 등의 과정을 거쳐 최종 코너 지점이 결정된다.

한편, corner detection은 구조적으로 noise, contrast 등에 취약하여 검출 정확성을 위한 전처리가 필요하다. 체커 보드, 기와 지붕 등 패턴이 있는 경우에는 해당 패턴들이 corner로 오검출되어 후처리가 필요한 상황이 발생한다. 또한, Harris와 같은 초기 검출 알고리즘의 경우 scale, rotation 등에 취약한 점이 나타나기도 한다. 따라서 corner detection을 수행하는 경우에는 전처리, 후처리와 함께 적절한 검출 algorithm을 선택하여 use case에 따른 최적화가 필요하다.

이 문서에서는 Harris, Shi-Tomasi, FAST algorithm 및 ApproxPolyDP() 메서드를 이용한 corner detection, 그리고 detection point를 subpixel 단위로 정밀하게 계산하는 방법을 알아본다.

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

2. Harris

Harris response

Harris detected

Harris corner detection은 가장 기초적인 corner detection algorithm 중 하나이다. Structure tensor ( $M$ )을 구성하고, $M$ 의 고유값을 이용하여 corner response ( $R$ ) 를 계산한다. 이후 사용자는 Harris 연산을 통해 얻은 $R$ 값을 설정한 임계값과 비교하여 최종 corner를 산출한다. $R$ 값을 구하기 위한 structure tensor, corner response function은 다음과 같다.

$M = \sum_{x,y} w(x,y) \begin{bmatrix}I_x I_x & I_x I_y \\ I_x I_y & I_y I_y \end{bmatrix}$

$Where$
$I_x = \text{Partial derivative of x}$
$I_y = \text{Partial derivative of y}$
$w = \text{Window function (Rectangular or gaussian kernel)}$

$R = \text{Determinant}(M) - k \cdot (\text{Trace}(M))^2$

private void Harris(Mat image)
{
    using var grayscale = image.CvtColor(ColorConversionCodes.BGR2GRAY);
 
    using var corners = new Mat();
 
    // Corner detection (일반적으로 blockSize = 2, ksize = 3, k = 0.04~0.06)
    Cv2.CornerHarris(grayscale, corners, 2, 3, 0.05);
 
    // 결과를 표시하기 위해 변환
    using var normalized = corners.Normalize(0, 255, NormTypes.MinMax);
    using var harris = normalized.ConvertScaleAbs();
 
    Cv2.ImShow("Harris response", harris);
 
    // 원본 이미지에 검출된 결과 필터링
    using var detected = image.Clone();
 
    // 검출 최대값 찾기
    corners.MinMaxIdx(out var min, out var max);
 
    for (int i = 0; i < corners.Width; i++)
    {
        for (int j = 0; j < corners.Height; j++)
        {
            // 검출 최대값의 2% 이상을 가진 픽셀을 코너로 취급 (thresholding)
            if (corners.Get<float>(j, i) >= max * 0.02)
                detected.Circle(i, j, 3, Scalar.LightGreen);
        }
    }
 
    Cv2.ImShow("Harris corner detected", detected);
}

3. Shi-Tomasi

Shi-Tomasi detected

Shi-Tomasi corner detection은 Harris algorithm과 유사하게 $M$ 을 사용하지만, $R$ 을 계산하는 방법이 다르다.

$R = \min(\lambda_1, \lambda_2)$

$Where$
$\lambda_n = \text{Eigenvalue of M}$

Shi-Tomasi corner detection은 Mat.GoodFeaturesToTrack() 메서드의 기본 검출 알고리즘으로 쓰이며, 사용자가 설정한 qualityLevel 값을 이용하여 임계값 ( $T$ ), 코너 후보 산출에 활용하게 된다. Mat.GoodFeaturesToTrack() 메서드는 $R$ > $T$ 인 코너 후보들 중 non-maximum suppression (minDistance) 을 통해 인접 후보를 제거한 후, $R$ 값 순서대로 maxCorners 만큼을 추려내어 최종 corner points 를 반환한다. 이 때, $T$ 를 계산 하는 방법은 다음과 같다.

$T = R_{max} \times qualityLevel$

private void ShiTomasi(Mat image)
{
    using var grayscale = image.CvtColor(ColorConversionCodes.BGR2GRAY);
 
    // Corner detection (최대 코너의 수, 코너 품질 최소값 (0~1), 코너 사이의 최소 거리 (픽셀), ROI mask, 이웃 픽셀 크기, harris options...)
    // Harris detector를 false로 설정하는 경우 Shi-Tomasi algorithm 적용
    var corners = grayscale.GoodFeaturesToTrack(500, 0.02, 10, null!, 3, false, 0);
 
    using var detected = image.Clone();
 
    foreach (var corner in corners)
    {
        detected.Circle(new OpenCvSharp.Point(corner.X, corner.Y), 3, Scalar.LightGreen);
    }
 
    Cv2.ImShow("Shi-Tomasi corner detected", detected);
}

4. GoodFeaturesToTrack with Harris

GoodFeaturesToTrack detected

Mat.GoodFeaturesToTrack() 메서드는 $R$ 을 계산하는 방법으로 Harris algorithm 또한 지원한다. useHarrisDetector = true로 설정하면 Harris algorithm으로 동작하며 k는 Cv2.CornerHarris()의 k와 동일하다.

private void GoodFeaturesToTrackWithHarris(Mat image)
{
    using var grayscale = image.CvtColor(ColorConversionCodes.BGR2GRAY);
 
    // Corner detection (최대 코너의 수, 코너 품질 최소값 (0~1), 코너 사이의 최소 거리 (픽셀), ROI mask, 이웃 픽셀 크기, harris options...)
    // Harris detector를 true로 설정하는 경우, 코너의 반응 값을 minimum eigenvalue 대신 Harris 공식으로 변경
    var corners = grayscale.GoodFeaturesToTrack(500, 0.02, 10, null!, 3, true, 0.05);
 
    using var detected = image.Clone();
 
    foreach (var corner in corners)
    {
        detected.Circle(new OpenCvSharp.Point(corner.X, corner.Y), 3, Scalar.LightGreen);
    }
 
    Cv2.ImShow("GoodFeaturesToTrack with harris corner detected", detected);
}

5. FAST

FAST detected

FAST (Features from Accelerated Segment Test) algorithm은 실시간 비전 동작 시 특징점을 빠르게 검출하기 위해 개발된 algorithm이다. 주변 픽셀과 밝기 차이를 비교하여 일정 수 이상의 연속된 픽셀에서 급격한 밝기 변화를 가지는 경우 코너로 판정한다. 구체적인 과정은 다음과 같다.

주변 픽셀과의 밝기 비교
검출하고자 하는 픽셀을 ( $P$ ) 기준으로 반지름 3 이내의 픽셀들과 밝기 차이를 비교한다.
corner 검출
연속된 $n$ $n$ 개 이상의 픽셀이 다음 조건 중 하나를 만족하는 경우 corner로 검출한다. 일반적으로 $n$ $n$ 은 12를 사용한다.
- 연속된 $n$ 개 이상의 픽셀이 검출 픽셀보다 매우 밝다. ( $P + t< P_i$ )
- 연속된 $n$ 개 이상의 픽셀이 검출 픽셀보다 매우 어둡다. ( $P > P_i + t$ )
Non-maximum suppression (Option)
FAST algorithm은 하나의 corner에 대해 여러 픽셀이 검출될 수 있는 구조를 가지고 있다. 많은 경우 non-maximum suppression을 추가로 적용하여 인접 corner 중 응답 값 (주변 픽셀과의 밝기 차이 합) 이 가장 높은 corner만 제외하고 제거한다.

위와 같은 단순한 과정으로 인해 FAST algorithm은 매우 빠른 속도로 corner detection을 수행할 수 있다. 다만, 연산이 단순한 만큼 noise, scale 등에 의해 결과가 크게 달라질 수 있어 사용 시 주의가 필요하다.

private void FAST(Mat image)
{
    using var grayscale = image.CvtColor(ColorConversionCodes.BGR2GRAY);
 
    // FAST 코너 검출 : 검출 픽셀과 주변 픽셀의 밝기, threshold 값을 이용하여 코너 판정
    var corners = Cv2.FAST(grayscale, 75);
 
    using var detected = new Mat();
 
    Cv2.DrawKeypoints(image, corners, detected, Scalar.LightGreen);
 
    Cv2.ImShow("FAST detected", detected);
}

6. ApproxPolyDP

FindContours with ApproxPolyDP

앞선 방법들과 달리, 이 방법은 다각형 근사를 통해 corner를 찾는 방식이다. 특정 이미지에 대해 contour detection을 수행하면 객체의 윤곽선을 찾을 수 있는데, OpenCV에서 제공하는 Cv2.ApproxPolyDP() 메서드를 통해 윤곽선을 다각형으로 근사시킬 수 있다. 이 방법은 주로 뚜렷한 형상을 가진 객체의 corner를 찾을 때 사용된다.

private void FindContoursWithApproxPolyDP(Mat image)
{
    using var grayscale = image.CvtColor(ColorConversionCodes.BGR2GRAY);
    using var threshold = grayscale.Threshold(-1, 255, ThresholdTypes.Binary | ThresholdTypes.Otsu);
 
    // Contour detection : 가장 바깥쪽 외곽선만 가져오고, 필요한 최소한의 포인트만 구함
    threshold.FindContours(out var contours, out var hierarchy, RetrievalModes.External, ContourApproximationModes.ApproxSimple);
 
    using var detected = image.Clone();
 
    // 면적이 너무 작은 외곽선은 객체가 아닐 가능성이 높음
    var contourThreshold = 10;
 
    foreach (var contour in contours)
    {
        if (Cv2.ContourArea(contour) < contourThreshold)
            continue;
 
        // 다각형 계산 : epsilon 값은 보통 외곽선 길이의 5% 이하로 설정 (허용 오차)
        var corners = Cv2.ApproxPolyDP(contour, 0.03 * Cv2.ArcLength(contour, true), true);
 
        foreach (var corner in corners)
        {
            detected.Circle(corner, 3, Scalar.LightGreen);
        }
    }
 
    Cv2.ImShow("FindContours with ApproxPolyDP", detected);
}

7. Subpixel correction

Shi-Tomasi detected

Subpixel correction

앞선 Harris, GoodFeaturesToTrack, FAST와 같은 방법은 검출된 corner들의 위치를 정수 단위로 반환한다. 실제 corner의 위치가 픽셀 사이에 위치한다면 검출된 위치와 맞지 않게 되는데, OpenCV에서는 정밀한 위치를 구하기 위한 방법으로 Cv2.CornerSubPix() 메서드를 제공하고 있다. Cv2.CornerSubPix()는 입력받은 corner 위치 주변 영역을 탐색하면서 밝기 변화가 가장 뚜렷하게 나타나는 지점을 소수점 단위의 좌표로 추정한다. Subpixel correction은 주로 calibration, precision tracking과 같은 고정밀 작업에 활용된다.

private void ShiTomasiWithSubPixelCorrection(Mat image)
{
    // 예시로 ShiTomasi 사용
 
    using var grayscale = image.CvtColor(ColorConversionCodes.BGR2GRAY);
 
    // Corner detection (최대 코너의 수, 코너 품질 최소값 (0~1), 코너 사이의 최소 거리 (픽셀), ROI mask, 이웃 픽셀 크기, harris options...)
    var corners = grayscale.GoodFeaturesToTrack(500, 0.02, 10, null!, 3, false, 0);
 
    // 위에서 찾은 정수 단위 corners에 대한 정밀 연산 : 소수점 단위로 조정 (실제로는 코너가 픽셀 사이에 걸쳐있을 수 있음)
    // winSize : 코너 위치를 기준으로 정밀 탐색을 수행할 윈도우 크기의 1/4 지정 (아래처럼 3, 3 지정하는 경우 실제 윈도우는 7, 7)
    // zeroZone : 탐색 윈도우 안에서 무시할 영역의 크기 (winSize와 마찬가지로 1/4 지정). 보통 -1, -1 사용하여 무시하는 영역이 없게 설정
    // criteria : 탐색 반복 설정 - type : 멈추는 조건 설정, maxCount : 최대 반복 수, epsilon : 정확도 수준 (값이 작을 수록 정밀)
    var correctedCorners = Cv2.CornerSubPix(grayscale, corners, new OpenCvSharp.Size(3, 3), new OpenCvSharp.Size(-1, -1), new TermCriteria(CriteriaTypes.Eps, 10, 0.05));
 
    using var detected = image.Clone();
 
    foreach (var corner in correctedCorners)
    {
        detected.Circle(new OpenCvSharp.Point(corner.X, corner.Y), 3, Scalar.LightGreen);
    }
 
    Cv2.ImShow("Shi-Tomasi corner detected with subpixel correction", detected);
}

8. 참조 자료

Contents

1. Introduction
2. Harris
3. Shi-Tomasi
4. GoodFeaturesToTrack with Harris
5. FAST
6. ApproxPolyDP
7. Subpixel correction
8. 참조 자료