1D Image Block Matching using Gradient

영상 인식과 영상 압축에 이용되는 블록 매칭은 기준 블록과 가장 유사한 타깃 영상 내의 블록을 찾는 방법이다. 타깃 영상 내에서 가장 유사한 블록을 찾기 위해, 타깃 영상 내에서 각 위치에 대응하는 블록과 기준 블록 간의 유사성 척도를 계산하여 비교한다. 타깃 영상 내의 모든 위치에 대해 전체 검색을 진행하는 경우 계산량이 매우 크기 때문에, 검색 범위를 제한하거나 sparse 검색을 하는 방법들이 종종 활용된다. 그러나 이 경우 매칭의 정확도가 떨어질 수 있다. 이러한 문제를 해결하기 위해, 본 논문에서는 블록 매칭에서 전체 검색 대신 라인 검색을 통한 방향 탐색 방법을 제안한다. 기존의 방향 탐색 방법들은 three step 등 heuristic 방식을 사용함으로써 수렴성과 정확도가 보장되지 않았는데, 이러한 단점을 보완하기 위해 본 논문에서는 전역 수렴이 보장되는 경사 하강법을 이용한 방향 탐색 방법을 제안한다. 이 접근 방법의 공식화 예로 LSE(Least Squares Error) 유사성 척도를 이용한 블록 매칭의 경우를 살펴본다.