[Computer Vision / Image Precessing] Harris Corner Detetor

해리스 코너 검출기 (Harris Coner Detector)

해리스 코너 검출기는 컴퓨터 비전 알고리즘에서 영상의 코너(Corner)를 추출하고 특징을 추론하는 데 일반적으로 사용되는 코너 검출 연산자입니다. 1988년 크리스 해리스(Chris Harris), 마이크 스티븐스(Mike Stephens)가 모라벡(Moravec)의 코너 검출기를 개선하면서 처음 소개되었습니다. 해리스 코너 검출기는 이전과 비교하여 45도 각도마다 패치를 이동하는 대신 직접 방향을 기준으로 코너 점수의 차이를 고려했으며, 엣지(edge)와 코너를 더 정확하게 구별한다는 것이 입증되었습니다. 이후 영상을 전처리하기 위해 많은 알고리즘에서 개선 및 채택되었습니다.

 

 

코너 (Corner)

코너는 주변 지역이 두 개의 강하고 서로 다른 엣지 방향으로 맞물린 지점을 말합니다. 즉, 밝기가 급격하게 변하는 두 엣지의 연결 지점이라고 할 수 있습니다. 코너는 영상의 중요한 특징이며, 변환(translation) / 회전(rotation) / 조명(illumination)에 불변하는 관심점입니다.

 

 

위 그림에서 평평한(flat) 지역에서는 어떠한 방향으로도 기울기 변화가 관찰되지 않습니다. 엣지(edge) 지역에서는 엣지 방향에 따라서 기울기 변화가 관찰되지 않습니다. 따라서 평평한 지역과 엣지 지역에서는 모든 방향을 구별할 수 없기 때문에 패치(일정 영역) 매칭(patch matching)을 하기 어렵습니다(유사한 패치가 다수 존재). 그러나 코너 영역에서는 모든 방향에서 의미있는 기울기 변화를 관찰할 수 있습니다. 때문에 코너는 패치 매칭에 적합(어느 방향으로든 패치를 움직이면 외관이 크게 변함)하며 일반적으로 시점의 변화에 더 안정적입니다.

 

 

코너 검출 (Corner Detection)

해리스 코너 검출에 적용되는 아이디어는 영상의 각 픽셀 p 주위에 작은 윈도우를 고려하는 것입니다. 모든 고유한 윈도우를 식별하는 것이 목표입니다. 고유성은 각 윈도우를 지정된 방향으로 조금씩 이동(shift)시키고 픽셀 값의 변화량을 계산하여 측정할 수 있습니다.

 

 

수학적 공식을 통해 살펴보면, 이동 전후 픽셀 값의 제곱의 차(SSD, Sum of Squared Difference)를 취하고 8 방향의 이동에 대해 SSD 값이 큰 픽셀 윈도우를 식별합니다. 함수 E(u, v)는 모든 SSD의 합으로 정의했습니다. 여기서 u, v는 3 x 3 윈도우 내 모든 픽셀의 x, y 좌표이고 I는 픽셀의 강도(밝기) 값입니다. 영상의 특징은 일부 임계값에 의해 정의되며, 함수 E(u, v)에 대해 큰 값을 갖는 모든 픽셀들입니다.

 

 

코너 검출을 위해 함수 E(u, v)를 최대화해야 합니다. 따라서 SSD가 표현된 항을 최대화해야 합니다. 위 방정식에 테일러 전개를 적용하고 계산을 통해 다음과 같은 최종 방정식을 얻을 수 있습니다.

 

 

위 행렬의 이름을 M으로 짓겠습니다.

 

 

이제 방정식을 다음과 같이 표현할 수 있습니다.

 

 

SSD의 값은 8 방향에 대해 커야하고, 어느 방향에서도 작지 않아야합니다. 행렬 M의 고유벡터를 구함으로써, SSD의 가장 큰 증가 방향과 가장 작은 방향을 둘 다 얻을 수 있습니다. 해당 고유값은 실제 증가량을 의미합니다. 다음 점수 R은 각 윈도우마다 계산됩니다.

 

 

λ1과 λ2는 행렬 M의 고유값입니다. 따라서 λ1, λ2의 값은 해당 영역이 코너인지, 엣지 혹은 평평한 지역인지 결정합니다.

• λ1과 λ2의 값이 작아 |R|이 매우 작은 값이면(부호 상관 없이), 해당 영역은 평평하다.
• λ1가 λ2보다 매우 크거나 혹은 그 반대이기 때문에 R의 값이 0보다 작으면, 해당 영역은 엣지이다.
• λ1과 λ2의 값이 커 R의 값이 0보다 크면, 해당 영역은 코너이다.

 

 

 

(원 저작자에게 이용 허락을 받고 옮긴 글입니다.)

https://medium.com/data-breach/introduction-to-harris-corner-detector-32a88850b3f6

Introduction to Harris Corner Detector