Feature Matching

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

 

각도가 다르게 찍힌 사진에서 같은 부분을 나타내는 keypoint들을 찾고 이들을 연결시키는 문제이다.

A, B 사진에서 keypoint를 패치를 이용해서 찾는다고 했을 때, A사진의 패치의 히스토그램과 B사진 패치의 히스토그램간 차이가 0이 되면 이상적이다.

한 사진에 대해 특징점이 될 수 있는 key point는 여러 개가 있는데, 그 중 매칭되는 것을 어떻게 찾느냐?

 

Feature Matching Algorithm( I1이 주어졌을 때, I2에서의 가장 좋은 매치는?)

1. 두 descriptor를 비교하기 위한 거리 함수를 정의한다. (코사인, 유클리드, L2-norm 등.. 뭘 쓸지)

 

2. 가장 가까운 이웃을 찾는다. 

 - 우선 모든 feature간 거리를 계산한 후,

 - 그 중 최소 거리를 찾는다. (최소 1개는 찾게 됨)

 - 내가 지정한 threshold를 적용해서 이걸 매칭할지 안 할지 결정한다. (거리가 많이 차이나면 매치 ㄴㄴ)

 

근데 이 feature들끼리 구분하는 게 어렵다. 같은 무늬가 반복된다면 그 부분을 나타내는 feature끼리는 매치 확률이 높아지기에!

그래서 '거리'를 사용하는 NNDR 기법을 쓴다.

 

NNDR

그림과 함께 보면 이해가 쉬울 것이다.

여기서 point의 색이 같으면 같은 key point라는 뜻!

왼쪽 원을 보면, 색이 같은 key point지만 원을 벗어나서 Db가 Da와 같은 키포인트로 채택되지 않을 수도 있다.

하지만 그 다음으로 Da와 가까운 key point인 Dc와의 거리인 d2를 봤을 때, d1/d2의 값이 작다면 Db를 채택한다는 것이다.

오른쪽 원에서는 Dc가 Dd와 가까워서 채택될 위험이 있지만, d1'/d2'의 값이 크기 때문에 채택되지 않는 것이다.

 

그래서 아까 말한 반복되는 무늬에서는~ 그런 패턴이 사진에 많기 때문에 ratio로 보면 채택이 안 되니 매칭을 안 한다!

이런 면에서 보면 '잘못된 매치'를 막는, 보수적 매칭이라고 볼 수 있음.

 

3. Ratio Test를 진행한다.

 - NNDR 계산

 - 임계값과 비교해 채택할지 안 할지 결정

ratio test가 있고 없고 매칭되는 개수 차이가 크다. key point 개수 확 줄어듦.

 

4. Bi-directional consistency test

1번 사진과 2번 사진의 key point를 매칭할 때, 1->2 방향에서도, 2->1 방향에서도 매칭되는 bi-directional consistency check가 중요하다.

이때 일대일 매칭을 위해 행렬을 쓰는데,

행이름을 I1의 key point로, 열이름을 I2의 key point로 하는 행렬을 만든 후,

그 행렬 모든 값의 최솟값을 찾아 최솟값이 담긴 열과 행의 값을 모두 Inf값으로 만든다.

예를 들어 (3, 5)의 값이 최솟값이라면 3행과 5열의 모든 값을 Inf로 만드는 것!

그럼 일대일 대응이 될 수밖에 없음..

근데 주의할 점은, 만약 그 최솟값이 threshold보다 크다면 Inf로 만들지 않고 값 그대로 남겨야 한다.

 

stitch multiple images

그럼 다시 두 이미지를 합치는 것으로 돌아와서,

여기서 고려할 점을 단계별로 말해보겠다.

1. 이미지를 어떻게 매치할지 - 같은 위치의 점을 찾아야 함

2. 이미지를 어떻게 맞출지 - 이미지 warping with 기하학적 변형

 

1번은 위에서 다룬 feature matching이니, 2번을 위해 기하학적 변형에 대해 알아보겠다.

 

Geometric Transformation

우리가 결과적으로 원하는 것은, (x, y)좌표를 다른 이미지의 (x', y')좌표로 매핑하는 것이다.

이걸 위해 transformation matrix인 M을 사용하여,

x' = Mx 로 나타낼 수 있다.

여기서 일단 x'는 [x' y']'이고 x는 [x y]'이므로 M은 2x2 행렬임을 알 수 있다.

다양한 변화가 있으니 차근차근 알아보자.

 

1. scaling

크기를 변환하는 것이다.

이렇게 곱하면 됨! 만약 a, b가 모두 2라면 이미지가 4배 커지고, 시작점과 끝점 좌표는 2배씩 커진다.

S는 M과 같다.

 

2. shearing

기울이는 것이다.

이렇게! 크기 변환은 따로 일어나지 않고, 단지 '기울기 변환'만 발생한다.

 

3. rotation

회전하는 것이다.

x를 theta만큼 회전시킨다면? 다음과 같은 M을 쓰게 된다.

 

이러한 2D linear transformation은 6가지가 있다.

 

그럼 '이동'은 어떻게 할까?

 

4. 2D translation

이건 x'=Mx 형태가 아니라, x=t+x형태여야 한다.

근데 모든 변환을 M을 이용해 곱의 형태로 나타내고 싶은데.. 방법이 없을까? 하면,

원래 2x2 행렬이었던 M의 차원을 바꿀 것이다. (당연히 x'와 x의 차원도 바뀐다!)

그럼 이렇게 3x3 행렬로 M을 만들 수 있다!

 

그러면 그냥 3x3 행렬로 통일하자. 

translation은 이미 3x3이니, scaling, rotation, shearing만 바꿔주면 된다.

그냥 진짜 대각원소에 1 하나만 더 추가해주고, 추가된 비대각 원소들은 모두 0으로 해주면 된다.

이렇게 말이다! 

사실 저 맨 마지막 행은 삭제해도 된다.

2*1 = (2*3) * (3*1) 이렇게 바꿔도 된다는 뜻이다.

 

그리고 얘네를 여러 개 적용시키려면 x' = M1 * M2 * M3 * x 이런식으로 행렬을 한 번에 모두 곱해도 된다.

근데 주의해야 할 점은, 저 x'는 x를 M3으로 변경한 후 M2로 변경한 후 M1로 변경한 행렬이라는 것이다.

 

그럼 자주 사용하는 변환은 미리 곱해놓으면 좋을 것이다!

예를 들어 rotation 후 translation하는 행렬은,

이렇게 쓸 수 있는데, 만약 theta가 40이고, dx가 3, dy가 2라고 해서 무조건 40도 회전 후 3, 2로 움직이는 것은 아니다!

(왜지?)

 

~ 다양한 변환행렬들 ~

그리고 이런 변환행렬들을 모두 한 방에 Homography 행렬이라 부를 건데,

그럼 행렬 H는 3x3으로 나타낼 수 있고, 미지수의 개수는 9개가 된다.

그치만 최대한 미지수의 개수를 줄이기 위해, 가장 마지막 원소(h33)로 모든 원소를 나누어,

가장 마지막 원소(h33)가 1이 되게 하고 나머지 원소인 8개만 미지수가 되도록 한다.

그럼 자유도 8!

 

끝~