이미지에서 keypoint를 찾는 것은 중요하다. keypoint 주변 픽셀들이 window가 되는데, local descriptor를 통해 window의 지역적 특징을 표현하게 된다. 이미지 내의 다양한 keypoint들로부터 온 지역적 특징들을 기반으로 이미지는 설명된다. keypoint 중 가장 대표적인 것이 corner(꼭짓점)이다. 이미지 내에서 꼭짓점을 찾아내는 대표적인 알고리즘인 Harris detector에 대해 알아보겠다.
기본적인 아이디어는 이렇다. corner 근처의 window는 다른 지역의 window와 다르게, 모든 방향으로 조금만 움직여도 gradient 변화가 크다. 아래 그림을 보면 이해가 쉽다.
왼쪽 그림은 모든 방향으로 움직여도 변화가 없다. 가운데의 edge window는 edge의 방향(그림에서는 위아래)으로 움직였을 때에 gradient의 변화가 크다. 오른쪽 그림의 corner window는 모든 방향에서 gradient의 변화가 크게 나타난다.
이미지 내의 모든 픽셀은 각각 아래와 같은 에너지 행렬 E를 가진다. 이 행렬을 통해 해당 픽셀 근처의 픽셀값 변화의 정도를 확인한다. 에너지 행렬을 구하는 과정을 자세히 살펴보자. k는 1로 가정하겠다. (이 경우, window의 크기는 3이 된다.)
편의상 흰 픽셀을 1, 검은 픽셀을 0으로 하였다. 흑백 이미지라면 0부터 255까지의 픽셀값을 가질 것이다.
우선, 당연히 E[0, 0]은 0이다.
E[0, 1]은 빨간색 window의 각 원소값에서 검은색 window의 각 원소값을 각각 뺀 것들의 제곱의 합이다.
즉, E[0, 1]의 값은 (1-1)^2 + (1-1)^2 + (1-1)^2 + (0-1)^2 + (0-0)^2 + (0-0)^2 + (0-1)^2 + (0-0)^2 + (0-0)^2 = 2이다.
이와 같은 방식으로 에너지 행렬을 채우게 된다. 아래와 같은 행렬이 완성된다.
꼭짓점에 위치한 픽셀의 에너지 행렬은 다음과 같이 모든 방향의 값이 크다. 만약 모서리에 위치한 픽셀이었다면, 모서리 방향의 값이 크고 나머지 방향의 값은 작았을 것이다.
하지만 이렇게 힘든 방법으로 모든 픽셀의 에너지 행렬을 구하지 않아도 된다.
아래의 간단한 행렬곱으로 근사하여 구한다. 근사하는 이유는 계산상 편리함도 있지만 추후에 eigenvalue를 구하기 위함도 있다.
행렬 M은 2*2 크기의 행렬로 수직 방향으로의 미분값과 수평 방향으로의 미분값을 이용하여 구한다.
굳이 행렬 E를 계산하지 않더라도, 행렬 M의 원소들만 보고 corner detection이 가능하다. M 행렬의 구성을 보고 대략 유추가 가능하다. 수직, 수평 방향의 미분값이 모두 크다면 corner일 것이고, 한쪽 방향만 크다면 edge이다.
