Harris corner detection

코너( corner )란?

• 두 방향의 edge가 만나는 지점으로, 한 점 주변으로 보면 모든 방향으로 강한 밝기 변화가 일어나는 특징을 가짐
• 코너는 영상내에서 객체의 모양을 표현하는 중요한 특징점이다.

 

 

 

 

image에서의 Gradient

• 이미지의 각 pixel에서 x,y 방향의 밝기 변화량을 나타낸다.
  • 보통 sobel 연산자 같은 미분 연산자를 사용해서 계산한다.
• 변화량에 따라서 이를 3가지로 분류한다.
  • 1. Flat : 픽셀 값이 어느 방향으로든 변화가 없다.
  • 2. Edge : 픽셀값이 한 방향으로만 변화가 존재
  • 3. Corner : 픽셀 값이 모두 방향으로 변화가 존재

 

 

 

구조 텐서 ( second moment matrix )

• 구조 텐서는 각 pixel에서 국소적인 변화량 ( gradient 변화)를 표현하는 2x2 대칭 행렬이다.
• 각 pixel의 graident 정보를 기반으로 계산되며 아래와 같이 정의한다.
  • ( 근데 정확히 말하면 미분이 아니라 미분 근사값이다. )

즉, 구조 텐서는 특정 픽셀 주변에서 밝기 변화가 얼마나 심한지를 나타내는 행렬이다.

 

 

 

구조 텐서의 예시 1 ( 평탄 영역 Flat Region )

• 상황 : 이미지의 일부분이 거의 균일하여 밝기 변화가 거의 없는 경우...

모든 합이 0이니, 해당 영역은 강한 방향 변화가 없으니, 코너나 엣지가 아닌 평탄한 영역임을 의미.

 

 

구조 텐서의 예시 2 ( 엣지 영역 Edge Region )

• 상황 : 이미지의 한 부분에서 한 방향으로 강한 변화가 존재하는 경우. ( 여기서는 수평 방향이다. )

해당 행렬은 한 방향(여기서는 y방향)으로만 변화가 있음을 보여준다. 고유값은 0과 255이며, 하나의 값만 크고 다른 값은 0에 가까워지니 edge임을 나타냄.

 

 

 

구조 텐서의 예시 3 ( corner region )

• 이미지의 한 점 주변에서 두 방향 모두에서 강한 변화가 있어서 corner가 형성되는 경우
  • 아래는 3x3윈도우 내 픽셀의 graident값이다. ( 각 픽셀에 대한 Ix , Iy값... )

( 3 , 1 )	( 3 , 1 )	( 1, 3)
( 3 , 1 )	( 1, 3)	( 1, 3)
( 1, 3)	( 1, 3)	( 3 , 1 )

 

 

 

Harris corner detection

• 특징점 검출 알고리즘 중 하나이다. ( 이미지의 gradient 변화를 기반으로 코너를 검출한다. )
• 이미지 내에서 'corner'를 효과적으로 만나는 점을 찾기 위해 제안되었다.
  • corner란? ==> 두개의 edge가 만나는 점
• 장점
  • 1. 회전 불변성( 이미지가 회전해도 동일한 코너를 검출할수있다)
  • 2. 계산 효율성 ( 상대적으로 단순한 연산으로 빠르게 코너를 검출할 수 있다. )
  • 3. 강건한 특징 검출 ( 노이즈가 존재해도, 어느정도 안정된 검출 결과를 출력한다.)
• 단점
  • 1. 스케일 불변성 부족 ( 이미지 크기가 달라지면 코너 검출 결과가 달라질수있으니, 멀티스케일 접근이 필요할수있음)
  • 2. 적절한 임계치를 선택해야한다.
  • 3. edge근처의 corner가 제대로 구분안될수 있어서 후처리  과정이 필요할 수 있음.
• 알고리즘의 단계
  • 1. gradient 계산
    • 입력 이미지에 sobel 필터 등을 사용해서 I x 와 I y를 구한다.
  • 2. 구조 텐서를 구성
    • 각 픽셀 주변의 윈도우에서 (Ix)^2 , (Iy)^2 , (Ix)*(Iy)를 계산하고, Gaussian 필터를 적용해서 노이즈에 강인한 합을 구한다.
      • (만약에 윈도우가 3x3이라고 하자. 그러면 총 9개의 픽셀에 대해서 sobel연산을 수행한다. 그러하면 Ix와 Iy는 총 9개,9개씩 나온다.)
  • 3. 코너 응답 값 R을 계산 ( 아래 식 참고 )
    • 위에서 구한 M행렬에 대해서 R = det(M)-k*(trace(M))^2을 계산
  • 4. Thresholding을 적용
    • 미리 설정한 임계치보다 R값이 큰 픽셀들을 코너 후보로 선택한다.
  • 5. Non-Maximum Suppression
    • 후보들 중에서 지역 최대값만 남기고, 주변 값보다 낮은 응답을 보이는 픽셀들은 제거하여, 최종적으로 확실한 코너 위치만을 남긴다.

 

 

 

 

응답함수에 대한 식