Corner Detection

본 포스팅은 충남대 고영준 교수님의 강의자료를 바탕으로 작성한 글입니다.

 

오늘은 다들 아는 '파노라마'에 대해 알아볼 것이다.

옆으로 길게 찍는 사진 말이다. 그런 사진을 어떻게 만들 수 있을까?

파노라마를 찍을 때도 보면 손이 어쩔 수 없이 흔들리게 될 텐데 그 사진이 웬만해선 잘 이어져있다. 어떻게?!

 

이어 붙이기?

정말 간단한 방법이다. 모두가 생각해낼 수 있을 것이다.

이 방법도 물론 가능하다. 

정확히 수평으로, 경계를 맞춰서 찍는다면 말이다.

그렇게 찍기는 당연히 어렵다..

 

그럼 이제 (완벽하지 않은) 여러 이미지를 이어붙일 때 필요한 것이 무엇인지 생각해보겠다.

 

1. 같은 곳을 찾는다.

   각 픽셀이 어디에 위치해있는지 찾는 것!

2. 이미지가 어긋나있을 텐데, 그걸 어떻게 정렬할지 찾는다.

   기하학적 변형을 줘서 이미지를 warping시킨다.

3. 이미지를 블렌딩하는 방법을 찾는다.

   겹치는 부분은 밝기/각도 이런 부분에서 당연히 다를 텐데, 이걸 경계선 없이 자연스럽게 합치는 방법 말이다.

 

그럼 이제 이런 것들을 위해 필요한 corner detection을 진짜 해보겠다!

 

Corner detection

우리의 목표는?

점 by 점 매칭이 아니라, 패치 by 패치로 매칭!

픽셀별로 같은 위치의 픽셀을 찾기에는 어려움이 있을 것이기 때문이다.

 

패치의 종류는?

그럼 패치를 찾아야 하는데, 좀 unique한 패치를 찾는 게 아무래도 매칭에 쉬울 것이다.

예를 들어 하늘이 있는 그림에서 하늘쪽 패치를 정하면? 하늘 부분의 패치들은 다 서로 비슷하니깐 매칭이 어렵기 때문이다.

그렇게 거의 변화가 없는, unique하지 않는 부분을 flatten하다고 한다.

 

flatten한 부분 말고 또다른 패치로는 Edge가 있다. 경계선이 보이는 패치이다. 

예를 들어 바닥에 그림자가 지면 그 부분에 경계가 생기는.. 이런 곳을 말한다.

이게 그나마 flatten보단 특징점이 있긴 하지만 그래도 edge끼린 비슷비슷 하니 그렇게 큰 효과는 없다.

 

그럼 마지막으로 corners부분이다. 

뭐 이것도 아에 유일하다고는 할 수 없겠지만, 그 각도 등이 특징적일 것이기에 edge, flatten에 비해서는 확실한 패치이다.

 

그럼 코너는 어떻게 찾지?

이 그림을 보면 쉽게 이해할 수 있을 것이다.

첫 번째 그림을 먼저 보겠다.

저 패치는 검정 공간에서 어디를 움직이든 패치 내용이 별 차이가 없을 것이다.

두 번째 그림을 보면,

양옆으로 움직인다면 패치가 계속 달라질 것이다. 그치만 위아래로 움직인다면 패치 내용의 차이가 없을 것이다.

마지막 세 번째 그림에서는,

패치가 어떤 방향으로 움직이든 패치 내용이 계속 달라진다.

이를 이용할 것이다!

 

Step1.

패치가 씌워진 부분에 대한 x, y방향 gradients를 계산한다.

순서대로 그림1, 그림2, 그림3

 

각 그래프는 x축 변화량과 y축 변화량에 대해 2차원 그래프로 나타낸 것이다.

 

그림1에서는 어떤 방향으로든 변화가 거-의 없기에 변화량이 0에 가깝워서 점들이 원점에 몰릴 것이다.

 

그럼 그림2에서는? edge와 직교하는 '축'에 점이 몰리게 된다.

핑크 부분은 x축으로든, y축으로든 변화가 없지만 초록 부분은 x축 방향으로는 변화가 많기 때문이다.

 

마지막으로 그림3에서는, 어느 부분 edge냐에 따라 좌표상 값이 다르다.

편하게 생각하려면, 이미지상 corner 또는 edge인 부분을 오른쪽으로 90도 회전하면 derivation 좌표가 찍히게 된다.

 

 

Step2. 

edge image gradient 값에서 그 평균을 빼준다.

이것은 좌표상의 gradient 값들이 '원점'을 중심으로 모이게 해준다.

 

Step3. 

각 픽셀에 대해 공분산행렬을 계산한다. 

근데 공분산이라기엔.. 그냥 Image를 x로 미분한 행렬과 y로 미분한 행렬을 같은 위치 원소끼리 곱해 합한 행렬을 말한다.

그리고 그 패치에서 중심일수록 더 중요하기에 가중치를 up해줄 수 있는 가우시안 가중치를 곱해준다.

왜냐면? 지금 여기서 원하는 것은 "이 패치의 중심 픽셀이 corner인가?" 이기 때문!

근데 그냥 편하게 1행렬로 해도 괜찮긴 함.

 

Step4.

공분산 행렬(or 유사도 행렬)로부터 고유값과 고유벡터를 계산한다.

그걸 계산해보면 좀 전 그림을 봤을 때,

그림1에서는 구해진 고유값이 둘 다 작고,

그림2에서는 구해진 고유값이 하나는 작고 하나는 크다.

그림3에서는 구해진 고유값이 둘 다 크다.

그럼 이게 작냐 크냐를 따질 '기준'이 있어야 한다.

 

patch difference를 생각해볼 것이다. 이걸 기준으로 삼겠다는 것이다!

모든 그림에서 파란 부분이 중심 패치라고 생각하겠다.

그림1은 중심 패치에서 어느 방향으로 움직여도 패치가 닿는 부분이 중심패치와 유사할 것이다.

그림2는 중심 패치 기준 위아래로 움직이면 패치가 닿는 부분이 중심패치와 유사하겠지만, 양옆으로 움직이면 유사하지 않을 것이다.

그림3은 어느 방향으로 움직여도 유사하지 않다.

 

이걸 이용하기 위해 한 가지 수식을 생각해낸다. (중심 패치(빨간 부분)를 target patch라 하고,)

새로운 image(filter?) E를 계산할 건데, 어떻게 계산하냐면?

가중치 w(가우시안 or 1)를 각 픽셀에 곱한 중심패치의 픽셀들과 주변패치의 픽셀들간 차이를 제곱해서 더한 것이다!

위 그림에서 나타내는 E(3, -2)픽셀은 x축 방향으로는 3, y축 방향으로는 -2만큼 이동한 곳을 주변 패치로 선정한 제곱합 결과값이다.

따라서 u, v = 0이라면 자기 자신을 주변 패치로 선정할 것이므로 모든 픽셀간 차이가 0이기에 E의 중심픽셀값은 항상 0이 된다.

 

 

Auto-correlation

아주 작은 u, v에 대해 

이 Error function 근사에 대해서는,

일단 테일러 급수를 적용시키면 이 Error function은 u.T * H * u 가 된다.

여기서 H는 아래와 같다.

 

그리고 이를 타원으로 시각화하는데, 고유값이 둘 다 커야지 타원이 유지된다.

요런 타원!

 

고유값이 둘 다 크다면 corner, 한쪽만 크다면 horizontal 혹은 vertical edge가 되고, 둘 다 작다면 flat region이 된다.

 

step 5.

고유값에 대한 임계값을 이용해 corner인지 아닌지 판별

이런식으로, 또는 그냥 십자모양으로 만들어도 됨.

 

가장 작은 고유값을 임계값과 비교하면 됨.

 

원래 R을 고유값 둘 중 작은 거로 구하는데, 이 식을 조금 변형해서

R = det(H) - k*trace(H)^2으로 구할 수 있다. 이럼 고유값을 안 구해도 되는 것이다.

아니면 그냥 R = det(H)/(trace(H) + epsilon)을 주로 쓴다. epsilon은 trace가 0인 경우에 대비하는 것.

 

Cov matrix를 계산하려 할 때, 일단 gaussian filter, derivatives, Img derivative를 미리 만들어놓고 사용하면 편하다.

 

이미지 크기와 필터 크기에 따라, 만약 이미지가 큰데 필터가 작다면 corner 부분이 corner로 탐지되지 않을 수도 있기에  문제 생김.