Computer Vision - Correspondence (Template Matching)

1. Template Matching

- 원본 영상에서 노랑 패치와 동일한 부분을 찾으려고 한다.
- 노랑 patch를 sliding시켜서 convolution하다보면 일치하는 부분이 더도드라져 보인다.
- 픽셀값들이 유사할수록 곱하고 더했을때(convolution) 결과로 더 큰 값이 나오기 때문이다.
- 즉 little picture mask를 가지고 sliding하며 convolution시키면 같은 부분을 찾아낼 수 있다.
- 이런걸 일치문제라고 한다.

- 좌 우 서로 다른 사진이지만 동일한 물체를 담고 있다.
- 템플릿 매칭으로 이 두 사진에서 동일한 지점을 찾는 것이다.

- 왼쪽의 red box와 일치하는 green box는 누구인지 찾는다고 해보자.
- Correlation-based algorithm : 모든 픽셀 값을 조사해서 일치여부 판단 (dense)
- Feature-based algorithm : feature만 비교해서 일치여부 판단 (sparse), SIFT(다음 장에 자세히 알아보자)
- 혹은 두 가지 아이디어를 섞어서 활용할 수 있다.

2. Comparing Window

- 정량적으로 appearance similarity function을 만들어서 판단을 해보자.(얼마나 비슷한지 정량적으로 계산)
- 그리고나서 화면을 sliding하면서 같은 녀석을 찾아나간다.

- 픽셀값들의 차이를 전부 구해서 absolute difference를 구해서 같은지 다른지 판단한다. (AD), AD의 최대값만 고를 수도 있도 다 합할 수도 있다.
- 혹은 sum of squared error를 구할수도 있다. (SSD)
- 아니면 곱해서 cross-correlation을 구할수도 있다. (C)

3. Example

- 로봇이 depth를 파악할 수 있도록 스테레오 카메라를 사용하면 위처럼 왼쪽에서 보는 화면과 오른쪽에서 보는 화면을 찍는다.
- 사진 중앙의 돌멩이를 집기 위해 왼쪽 사진에서의 patch와 동일한 점을 오른쪽 사진에서 찾으려고한다.

- 구한 패치를 가지고 오른쪽 사진에서 cross-correlation을 구해보았는데 이상한 곳에서 높은 일치율을 보이고 있다.

- 원인을 살펴보면 허공이 땅보다 밝기가 2v로 높기 때문에 cross-correlation을 구했을때 더 높은 값이 나온 것이였다.
- patch가 일치하지는 않는데 단순히 허공의 밝기 값들이 커서 생긴 오류였다.

- 그래서 zero-mean template을 사용해서 패치의 어두운 부분이 어두운 부분과 만났을때 correlation score가 크도록(밝은 부분이 밝은 부분과 만났을때 c가 크도록) 해서 문제를 해결하려고 했다.
- 템플릿 매칭을 할 영역의 평균값들을 그 영역을 구성하는 각 픽셀에게서 빼준 것이다. 그렇게 만들어진 이미지 영역과 템플릿을 컨볼루션해서 결과 값을 구한다.
- 하지만 여전히 원하는 결과를 얻지는 못했다.

- 그래서 이번에는 correlation말고 sum of squared error를 사용했다. 더 좋은 결과가 나왔다.
* 참고로 block matching에서 SSD를 사용한다. 티비가 영상을 송출할때 화면 전체를 구성하는 픽셀값들을 전달할수 없다. 데이터가 워낙에 많아서 전부다 송출을 못한다. 따라서 화면을 block단위로 쪼개서 t초에서 block의 위치가 t+1초에 어디로 이동하는지의 정보로 영상을 송출한다(block을 구성하는 픽셀값들을 다 전송할 필요가 없어짐). 이때 block일치 여부를 판단할때 SSD를 사용한다.

- 만약 우측 사진이 좌측 사진보다 더 어둡게 찍혔다면 (카메라의 차이 때문에) 위처럼 normalize로 성능을 높일 수 있다.
- 그래서 intensity들을 normalize해줬다. 템플릿의 평균값들을 템플릿을 구성하는 각 픽셀에게서 빼준것과 더불어 표준편차로 나눠서 normalization을 해준다.
- normalize한 다음 cross-correlation으로 비교를 할때, normalize cross correlation, NCC라고 부른다.

- 하지만 여전히 한계는 존재하는데 모델이 기울거나(Rotation) 크기가 커지면(scaling) match가 잘 되지 않는다.

- translation, rotation, scale에 invariant한 이미지들의 일치여부 판별을 위해 SIFT를 도입할 수 있다. 나중에 깊게 다뤄보자.

4. Template matching Source code

5. Histogram Source Code