[ComputerVision] Correspondence Matching

Correspondence Problem

stereo와 motion 추정과 같은 vision task는 두 개 이상의 view로부터 correspondence features를 찾아야 한다.

코너를 찾으면?

1) object의 형상/구조를 알 수 있음.
2) 같은 객체를 가지고 correspondence point(pair가 되는 point)
→ correspondence point를 많이 찾을수록 depth정보가 많이 생기므로 이를 이용해 3차원 정보를 추정할 수 있음.

The Correspondence Problem

• Basic assumptions
  • 대부분의 scene points가 두 이미지에서 모두 보여야 함.
  • corresponding image regions은 유사해야 함.
• These assumptions hold if:
  • 카메라로부터 object의 거리가 많이 떨어져야 한다. 위의 것들이 가능하고, shape deformation이 없으려면, 가능하면 거리가 멀면 좋음.
• We must choose:
  • elements to match →corresponding point
  • A similarity measure to compare elements →유사하다고 판단한 근거가 됨

Correspondence Problem

• Two cases of algorithms:
  • Correlation-based algorithms
    : Produce a DENSE set of correspondences ; 유사한 부분을 모두 다 찾겠다! → reconstruction할 때 사용
  • Feature-based algorithms
    : Produce a SPARSE set of correspondences ; 한 40개 정도의 유사한 부분을 찾겠다 → robust하다는 장점

Correlation-based Algorithms

4개의 patch 중 가장 유사한 patch가 무엇인가?

1) 유사도 함수(similarity function)가 필요하다.
2) 가장 높은 유사도를 구하기 위한 search strategy가 필요하다.

Comparing windows

• SSD: dissimilarity; 값이 클수록 dissimilar, 값이 작을수록 similar
• C: correlation/similarity measure; 값이 클수록 similar

Example

cross-correlation을 이용해 template matching을 하려고 한다.

cross-correlation 결과, 일치하는 곳과 다른 곳에서 유사도가 가장 높게 나왔다.

Problem with Correlation of Raw Image Templates

Consider correlation of templates with an image of constant grey value:

Now consider correlation with a constant image that is twice as bright.

밝기를 2배 했으니, 결과값이 당연히 커질 수밖에 없지 않겠냐

이것이 위에서 매칭되는 point보다 highest point가 correlation 값이 더 높게 나온 이유이다.

solution : 평균을 빼주자

Correlation, zero-mean template

아까보다 나아지긴 했지만, 아직도 highest score는 correct match가 아니다.
Note: physical constraint(카메라 위치 변화)를 추가해 영역 주변에서 찾아보면 된다.

"SSD" or "block matching"(Sum of Squared Differences)

Relation between SSD and Correlation

• correlation은 클수록 유사함
• 따라서 SSD가 작을수록 유사!

SSD

드디어 highest score와 correct match가 일치했다.

하나의 object를 다른 각도에서 찍더라도, 밝기(intensity) 외에는 다른 변화가 있으면 안된다. 이렇게나 제약이 많은데도 correspondence problem에서 밝기 정보가 변화하면 이조차 패턴 파악이 조금 어렵게 됨.

solution: 밝기 정보가 다른 두 image에서 correspondence point를 찾기 위해서는 intensity normalization(평균을 뺀 뒤, 표준편차로 나눔)을 한다.

맨 위의 그래프에서와 같이 두 이미지의 밝기 차이가 클 때, zero-mean(평균을 빼줌)을 하여 두 번째 그래프처럼 바꾼 뒤, 표준 편차로 나누어 3번째 그래프처럼 range를 맞춰준다.

한 이미지는 빛 RGB를 다 포함하는데, 다른 한 이미지는 R만 주는 경우엔 어떻게 correspondence probelm을 푸나?

이런 경우에는 shape 정보(edge)를 이용해 찾음. 그러나 이런 경우가 아니라면, 위와 같이 zero-mean하고 normalization함으로써 밝기 정보를 맞춰줌.

요약

• correspondence problem. 일치하는 영역을 찾는 데 corner를 이용하는 게 편리하므로 corner를 이용해 찾으려 한다.
• DENSE/SPARSE하게 찾는 방법이 있다. DENSE하게는 일치하는 모든 곳을 찾는 방법이고, 3D reconstruction할 때 사용(correspondence point를 많이 찾을수록 depth정보가 많이 생기므로)한다. SPARSE하게는 예를 들어 일치하는 영역 50개만 찾는 방법이고, robust하다는 장점이 있다.
• 첫 번째 이미지의 어떤 patch이 두 번째 이미지의 1,2,3,4번 patch 중 어떤 것과 일치하는지 판단하는 방법으로, SSD 또는 correlation이 있다.
• correlation은 클수록 유사하고, SSD는 작을수록 유사하다.
• correlation을 이용해서 highest point를 찾았는데, correct match와 일치하지 않는다면, 이를 해결할 방법으로 physical constraint를 추가하는 방법이 있다.
• SSD가 correlation보다 더 정확한 편이다.
• 두 이미지 사이에 intensity 차이나 range 차가 크다면, zero-mean을 해준 뒤, normalization(표준편차로 나눔)을 해줌으로써 두 이미지의 intensity를 맞춰준다.