[OpenCV] Harris Corner Detector

Theory

Computer Vision 분야에 있어 Feature(특징점)는 매우 중요한 개념입니다. Feature를 이용하여 서로 다른 Frame 간에 어떠한 변화가 있는지 감지할 수 있기 때문입니다. 즉, 컴퓨터가 이미지를 통해 사물을 인식하는 방식은 이미지 전체가 아닌 이미지가 가지고 있는 Feature들을 통해 인식하기 때문입니다.

그렇다면 Image Feature로 정의되는 것들은 무엇일까요?

첫째, Edges,

둘째, Corners

셋째, Blobs(Region of Interest, ROI라고도 함)

이들 Feature의 유형 중 Corner Detector의 하나인 Harris Corner Detector에 대해 알아보기로 하겠습니다.

Harris Corner Detector는 1988년에 발표된 "A COMBINED CORNER AND EDGE DETECTOR" 논문의 저자 중 한 명인 Chris Harris의 이름을 따온 것입니다. 원리는 서로 다른 Frame(이미지)에서 영역(Window)을 설정하고 두 개의 Frame 간의 차이에 대한 제곱합(SSD, Sum of Squared Difference)을 이용하여 현저한 값을 가지는 곳을 Corner로 정의합니다. 여기서, 현저한 값을 추출하기 위해 특정 행렬의 Eigenvalue를 이용합니다.

Grayscale Image의 Intensity(밝기값) I의 밝기변화 E를 다음과 같이 정의합니다:

\( E(u,v) = \sum_{x,y}{w(x,y)[I(x+u,y+v) - I(x,y)]^2} \)

여기서,

w(x,y) : 위치 (x,y)에서의 Window

u : x 방향으로의 변위(displacement)

v : y 방향으로의 변위(displacement)

Taylor Series Expansion에 의해,

\( I(x+u,y+v) \approx I(x,y) + uI_x + vI_y \)

이므로, 다음과 같이 수식적으로 근사화할 수 있습니다:

\( E(u,v) \approx \displaystyle{\sum_{x,y}{w(x,y)[I(x+u,y+v) - I(x,y)]^2}} \)

           \( = \displaystyle{\sum_{x,y}{w(x,y)[I(x,y) + uI_x + vI_y - I(x,y)]^2}} \)

           \( = \displaystyle{ \sum_{x,y}{w(x,y)[uI_x + vI_y]^2}} \)

           \( = \displaystyle{ \sum_{x,y}{ w(x,y)[u^2 I_x^2  + 2uvI_x I_y + v^2 I_y^2] } } \)

           \( = \begin{bmatrix} u & v \end{bmatrix} \begin{pmatrix} \displaystyle{ \sum_{x,y}{w(x,y) \begin{bmatrix} I_x^2 & I_x I_y \\ I_x I_y & I_y^2 \end{bmatrix} } } \end{pmatrix} \begin{bmatrix} u \\ v \end{bmatrix} \)

           \( = \begin{bmatrix} u & v \end{bmatrix} \mathbf{M} \begin{bmatrix} u \\ v \end{bmatrix} \)

여기서,

\( \mathbf{M} = \displaystyle{ \sum_{x,y}{w(x,y) \begin{bmatrix} I_x^2 & I_x I_y \\ I_x I_y & I_y^2 \end{bmatrix} } } \)

이므로 결론적으로,

\( E(u,v) \approx \begin{bmatrix} u & v \end{bmatrix} \mathbf{M} \begin{bmatrix} u \\ v \end{bmatrix} \)

입니다. 행렬 \(\mathbf{M}\)은 다음과 같이 정리됩니다:

\( \mathbf{M} = \displaystyle{ \sum_{x,y}{ w(x,y) \begin{bmatrix} I_x^2 & I_x I_y \\ I_x I_y & I_y^2 \end{bmatrix}} = \begin{bmatrix} <I_x^2> & <I_x I_y> \\ <I_x I_y> & <I_y^2> \end{bmatrix} } \)

괄호 <>은 지정된 Window에 대한 평균값을 의미한다.

행렬 \( \mathbf{M} \)의 두 개의 Eigenvalue, \(\lambda_1\), \(\lambda_2\)의 크기에 따라 다음과 같이 정의된다:

(1) 만약 \(\lambda_1 \approx 0\), \(\lambda_2 \approx 0\)이면 픽셀 (x,y)는 Feature가 아니라고 판단한다.

(2) 만약 \(\lambda_1 \approx 0\), \(\lambda_2\)는 충분히 큰 값이면 픽셀 (x,y)는 Edge의 일부로 판단한다.

(3) 만약 \(\lambda_1\), \(\lambda_2\)가 모두 충분히 큰 값이면 픽셀 (x,y)는 Corner로 판단한다.

Eigenvalue를 직접 계산하는 것은 계산량이 매우 많기 때문에 다음의 식으로 간접적으로 계산합니다:

\( \mathbf{M}_c = \lambda_1 \lambda_2 - \kappa(\lambda_1 + \lambda_2) = det(\mathbf{M}) - \kappa * tr(\mathbf{M})^2 \)

여기서, \(\kappa\)는 민감도 조정 계수이며, trace \(tr\)는 행렬 \(\mathbf{M}\)의 대각선 성분을 모두 합한 것, 즉,

\( tr(\mathbf{M}) = \displaystyle{ \sum_{i}{m_{i,i}} } \)

입니다.

이론 및 코드와 관련하여 좀더 자세한 내용은 OpenCV Python Tutorial을 참고하시기 바랍니다.

C++ Example

Example Code

#include <iosream>
#include <opencv2/opencv.hpp>
 
#include <stdlib.h>
#include <stdio.h>
 
using namespace std;
using namespace cv;
 
cv::Mat src, src_gray;
int thresh = 200;
int max_thresh = 255;
char* source_window = "Source image";
char* corners_window = "Corners detected";
void cornerHarris_demo( int, void* );
 
 
/* @ function main */
int main( int argc, char** argv )
{
  src = cv::imread( {YOUR_IMAGE_PATH}, 1 );
   
  cv::cvtColor( src, src_gray, COLOR_BGR2GRAY );
   
  cv::namedWindow( source_window, WINDOW_AUTOSIZE );
   
  cv::createTrackbar( "Threshold: ", source_window, &thresh, max_thresh, cornerHarris_demo );
   
  cv::imshow( source_window, src );
   
  cornerHarris_demo( 0, 0 );
   
  cv::waitKey(0);
 
  return(0);
}
 
 
/* @function cornerHarris_demo */
void cornerHarris_demo( int, void* )
{
  cv::Mat dst, dst_norm, dst_norm_scaled;
  dst = cv::Mat::zeros( src.size(), CV_32FC1 );
 
  int blockSize = 2;
  int apertureSize = 3;
  double k = 0.04;
 
  cv::cornerHarris( src_gray, dst, blockSize, apertureSize, k, BORDER_DEFAULT );
 
  cv::normalize( dst, dst_norm, 0, 255, NORM_MINMAX, CV_32FC1, Mat() );
 
  cv::convertScaleAbs( dst_norm, dst_norm_scaled );
 
  for( int j = 0; j < dst_norm.rows ; j++ ) {
    for( int i = 0; i < dst_norm.cols; i++ ) {
      if( (int) dst_norm.at<float>(j,i) > thresh ) {
        cv::circle( dst_norm_scaled, Point( i, j ), 5,  Scalar(0), 2, 8, 0 );
      }
    }
  }
 
  cv::namedWindow( corners_window, WINDOW_AUTOSIZE );
 
  cv::imshow( corners_window, dst_norm_scaled );
}

함수 cv::cornerHarris()에 대한 자세한 정보는 다음 링크를 참고합니다:

http://docs.opencv.org/master/d4/d7d/tutorial_harris_detector.html

Results

Original Image (harris.png)

실행화면

Python Example

Example Code

import cv2
import numpy as np
 
# load image
filename = './resources/harris.png'
img = cv2.imread(filename)
 
# convert to gray image
gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
gray = np.float32(gray)
 
# extract corners with Harris corner detector
dst = cv2.cornerHarris(gray, 2, 3, 0.04)
 
# result is dilated for marking the corners, not important
dst = cv2.dilate(dst, None)
 
# Threshold for an optimal value, it may vary depending on the image.
img[dst > 0.01 * dst.max()] = [0,0,255]
 
cv2.imshow('dst', img)
if cv2.waitKey(0) & 0xff == 27:
    cv2.destroyAllWindows()
    cv2.waitKey(1)

코드에 대한 설명은 다음과 같습니다:

• Line 1~2: OpenCV와 numpy 라이브러리를 임포트합니다.

• Line 5~6: imread() 함수를 이용하여 harris.png 이미지 파일로부터 픽셀 정보를 얻어옵니다. 픽셀 정보는 Blue, Green, Red(BGR) 순서로 배열되어 있습니다.

• Line 9~10: 컬러 이미지를 Grayscale로 변환하고 numpy의 float32로 데이터형을 변환합니다.

• Line 13: cornerHarris() 함수를 이용하여 Harris Corner를 추출합니다. 함수의 파라미터 정보는 다음과 같습니다:
  cornerHarris(gray,   #img: 이미지 데이터
                        2,       #blockSize: Corner detection을 위해 고려되는 인접 픽셀 크기
                        3,       #ksize: Sobel derivative의 Aperture 파라미터
                        0.04,  #k, Harris detector 파라미터)

• Line 16: 주석문 내용 그대로 감지된 Corner 포인트들을 확장하여 표기하기 위한 것입니다.
  

• Line 19: Corner로 표시되는 포인트들을 빨간점(B=0, G=0, R=255)들로 표기합니다.

• Line 21~24: 결과 이미지를 출력합니다.

Result