[컴퓨터비젼] 5. Corner Detection와 Harris Operator

Feature Extraction : Corners 과 blobs

 

이미지에서는 코너(Corner)와 블락(blob)을 알아내는 것이 중요합니다. 

이미지에서 로컬하게 특징을 짓을 수 있는 이미지를 찾아내는 것이 Feature을 추출하는 것인데요.

이 피쳐(Feature)에는 Corner와 blob으로 나뉠 수 있습니다.

아래 사진을 보면 뭐가 코너고 블락인지를 직관적으로 알아낼 수 있습니다.

 

그럼 이러한 Feature 추출이 왜 중요한 것일까요?

예를 들면 파노라마와 같이 사진을 잇는 기술에 이런 Feature을 추출하는 것이 중요하게 쓰입니다.

사진의 피처를 찾아서 연결하는 거죠.

 

그럼 아래 그림을 어떻게 연결할까요?

사진을 보시면 산봉우리 같은 구간을 Peak라고 합니다. 사진에서 이 Peak를 통해 매칠을 해 이미지 사이에 Tranformation을 가능하게 해 결합하는 것이죠. 

첫 번째 Feature Extract 두번째 스텝 Match Feature 세번째 align image 입니다.

물론 충분한 수의 피처가 존재해야겠죠. 

 

사실 이렇게 사진을 잇는 것은 쉬운 작업이 아닌데요. 

아래의 사진과 같이 사진의 각도, 색감 등이 다를 수 있기 때문이죠. 

 

더 어려운 경우에는 다음과 같이 아예 연관이 없어 보이는 사진도 있을 수 있습니다.

이런 경우 Feature을 어떻게 뽑아 낼까요? 두 사진의 연관성을 어떻게 찾아낼까요.

어떠한 알고리즘을 통해 공통된 Feature을 뽑아낼 수 있습니다. 

왼쪽 사진의 왼쪽 위 부분을 보면 이 Feature 들을 확인할 수 있습니다. 

 

왼쪽 책을 오른쪽 그림에서 찾아낼려면 어떻게 해야할까요?

사진이 매우 복잡하기 때문에 책을 판단할 수 있는 패치를 정해서 구해야합니다. 

하지만 이 경우 오리엔테이션에 따라서 모두 계산을 해주어야하는데 매칭되는 경우가 무수히 많기 때문에 연산이 매우 복잡합니다. 즉 효율적이지 못하다는 것이죠. 

 

Local Feature

기하학적 다양성 : 위치, 크기, 변역

사진적 다양성, 밝기, 노출 등등 

 

Local Feature의 장점

1. Locality : 견고
2. Quantity : 많은 수의 이미지 
3. Distinctiveness : 차별화를 두어 결정 지어줄 수 있음 특징 
4. Efficiency 

---

 

그럼 이제 Featrue을 찾아내는 접근 방식에 대해 배워 보자. 

 

1. Feature Detection : find it
2. Feature Descriptor : repesent it
3. Feature Matching " match 

 

앞에서 나왔던 산 사진을 사용하여 Feature 값을 찾아보자 .

1. Detection : 포인트 정의

 2. Description : 주변 포인트들을 통해 벡터 피쳐를 추출

3. Matching : 두 이미지 간 상응되는 포인트 매칭 

 

 

---

그럼 과연 어떤 게 좋은 피쳐일까요? 

쉽게 말해보자면 unique한 부분이어야합니다. 

다른 무언가를 찾아내야하는데 그럼 이 유니크한 건 어떤 걸가요?

 

 

 

1. Flat : 어느 방향으로 움직여도 변화 없음
2. Edge : edge 방향으로만 움직이면 변화 없음
3. Corner : 모든 방향으로 움직여도 변화 있음

 

Flat이 가장 안 좋은 피쳐고 Corner 가 가장 좋은 피쳐라는 것을 ㅇ라 수 있습니다. 

그럼 이 Corner 을 찾는 방법을 배워야겠죠?

 

수식이 나왔지만 무서워할 필요없습니다. 단지 새롭게 옮겨진 위치에서의 값을 원래 위치에서의 값으로 빼면 됩니다. 

이는 SSD "error" E(u,v)로 정의되는데 이 값이 높을 수록 변화가 크다고 생각하시면 됩니다. 

 

하지만 모든 픽셀을 계산해야하는 것은 좋지 못한 방식입니다. 

 

그래서 저희는 선형대수학에서 배웠던 태일러 급수를 통해서 계산하는데요. 

사실 저도 테일러 급수가 무엇인지 정확히 기억이 나지 않습니다.

그저 미분을 통해 근사값을 계산하고 더 많은 편미분을 할 수록 더 정확한 값을 없을 수 있다는 것입니다. 

물론 완벽히 일치하는 값은 아닙니다. 

이렇게 편미분을 이용하면 다음과 같이 정리할 수 있습니다. 

결국 수식이 다음과 같이 정리된다는 것을 알 수 있습니다. 

 

식이 이차식인 거 보이시나요? 

2차함수는 대부분 최소값이 존재하죠. 

저희는 이를 통해 최소값을 구할 수가 있습니다.

아래 그림을 보면 이를 통해 그린 그래프도 확인 할 수 있습니다. 

A는 x축 방향 C는 y축 방향이라고 생각하면 조금 더 이해가 쉬울 거 같습니다. 

 

좀 어려워 보이지만 예시를 보면 그렇게 까지 어렵지는 않다는 것을 알 수 있을텐데요. 

우리는 이렇게 구한 A,B,C 값들을 가지고 Harris Matrix 도 구할 수 있습니다.

Harris Matrix

아래 그림에 해리스 행렬을 구해보겠습니다. 

 

A는 x축을 이동합니다. 하지만 x축을 이동해도 edge 방향으로 변화를 얻을 수 없기 때문에 값은 0이 됩니다. 

그럼 자동으로 B도 0이 될 것입니다. 그럼 해리스 행렬을 다음과 같이 구성이 되고 E(u,v)도 다음과 같이 그릴 수 있습니다.

 

그럼 아래의 경우도 쉽게 행렬과 그래프를 생각해낼 수 있을 겁니다.

---

그럼 대체 H 행렬을 왜 구해야할까요? 이는 최소값 람다를 구하기 위해서 입니다. 

H행렬을 구하면 eigenvalue 와 eigenvector 를 정의하여 Ellipse equation 을 계산할 수 있습니다

그러면 람다의 최대값과 최소값을 게산할 수 있는데 이를 통해서 가장 천천히 변하는 방향인 람다 min 값을 구할 수가 있고 이 값이 가장 눈여겨 봐야하는 값입니다. 

 

 

이 eigenvalue와 eigenvector 을 구하는 법은 간단하게 첨부하겠습니다.

 

 

Corner detection : the math

 

이제 드디어 Corner detection위한 feature 을 계산할 수 있습니다.

다음 람다와 x의 의미를 아래와 같습니다. 

간단히 말하면 x는 변화가 가장 큰 방향이고 람다는 이 방향에서 변화량입니다.

 

람다 min 이 우리가 가장 주의깊게 봐야하는 값이라고 했습니다. 

이는 람다min 자체가 detecion value보다 크게 되면 어떤 방향을 가든지 람다 min 이상의 변화가 있는 걸 알 수 있습니다. 

즉 람다 min을 통한 최소값 계산이 가능하다는 것 입니다. 

 

조금 더 직관적인 이해를 위해서 예시 사진을 확인해보겠습니다.

람다 min 부분을 보시면 edge가 교차하는 코너들만 특징적으로 표현한 것을 볼 수 있습니다. 

가장 효율적인 corner detection을 한 것입니다. 

 

 

마지막으로 Corner detection을 정리해보겠습니다. 

1. 각 포인트마다 gradient 계산
2. Ix, Iy를 계산하여 H 행렬 구성
3. eigenvalue 계산
4. 람다 min에 대한 threshold 값을 두고 이 값 이상이 되면 corner로 판단
5. local maximum으로 정제된 코너를 선택 

 

---

Harris operator 

문제는 람다를 구하는 게 쉽지 않다는 것입니다. 

각 픽셀마다 구해야하기 때문이죠.

그래서 저희는 Harris operator 를 사용해서 람다 min 값을 근사시키는 겁니다.

아래 사진을 보면 각 계산을 적용시킨 픽셀을 보여주는데 Harris operator 와 람다min이 크게 차이가 나지 않는 다는 것을 확인할 수 있습니다.

 

Harris Detector 

 

Second moment matrix 

1. Image derivatives(optionally, blur first)

이미지를 유도하는데 선택적으로 가우시안 블러링을 합니다. 

2. Square of derivatives 

제곱하여 second moment 을 찾습니다. 

3. Gaussian filter 

4. Cornerness function - both eigenvalues are strong

5. Non-maxima suppression 

 

 

 

Harris Corner을 구하는 게 왜 이렇게 복잡할까요. 

단순히 gradient를 계산하는 것은 edge를 찾는 것이지 corner을 찾는게 아니기 때문입니다. 아래의 그림을 보면 알 수 있습닌다.

---

이상으로 Corner detection에 대해 알아보았습니다!