Graph-based Image Matching via Random Walks

Abstract

영상 사이에 특징점 정합을 찾는 문제는 컴퓨터 비전의 심장부에 놓여있으며, 지금까지 수많은 알고리즘들이 제안되어 물체 인식, 영상 검색, 영상 정합과 같은 폭넓은 분야들에 쓰여왔다. 그러나, 이전에 제안되었던 기법들의 대부분은 물체의 강체 운동 또는 배경잡음이 없는 참조 영상과 같은 제한적인 가정이나 감독적인 환경을 요구하였다. 비강체 왜곡이나 범주내 다양성 그리고 배경 잡음 등을 해결해야하는 강인한 영상 특징점 정합은 일반적인 실세계 환경에서 여전히 풀리지 않는 문제로 남아있다. 본 논문에서는 랜덤 워크에 기반하여 강인한 영상 정합을 위한 그래프 이론적 접근법을 다룬다. 본 논문의 목적은 강인한 영상 정합, 물체 발견, 배경잡음 제거라는 3가지의 상호 연관된 문제를 풀기위한 그래프 기반의 영상 정합틀을 확립하는 것이다. 이 목적을 위해서, 3가지의 기법이 제안된다: (1) 리웨이티드 랜덤 워크를 통한 그래프 (또는 하이퍼-그래프) 정합, (2) 진보적 그래프 정합, (3) 그래프 상의 모드 탐색. 제안하는 그래프 정합 기법은 비강체 왜곡과 외형 변화에 강인한 특징정 정합을 수행하며, 진보적 그래프 정합이라는 틀은 효율적인 방식을 통해 기존의 그래프 매칭의 성능을 획기적으로 끌어올린다. 그리고, 제안하는 그래프 상의 모드 탐색이 이러한 기법들과 결합하게 되면 신뢰할만한 정합 집합을 물체로 탐지하고 나머지를 배경잡음으로 간주하여 제거할 수 있게 된다. 본 논문은 실험적 평가들을 통하여 제안된 기법들이 영상 정합에서 가지는 우수성을 증명함과 동시에 다른 다양한 그래프 기반의 문제들에 대한 잠재력을 보여줄 것이다.

Establishing feature correspondence between images lies at the heart of computer vision problems, and a myriad of matching algorithms have been proposed to date for a wide range of applications such as object recognition, image retrieval, and image registration. Most of them, however, require some restrictive assumptions or supervised settings; e.g., a rigid motion assumption or a reference image without severe clutter. Robust feature matching under non-rigid deformation or intra-category variation still remains as an open problem in general real-world scenarios. In this thesis, a graph-theoretic approach to robust image matching is studied based on a random walk view. The goal of this thesis is to develop a robust graph-based image matching framework for the interconnected problems of robust feature matching, object discovery, and outlier elimination. For this purpose, three kinds of novel graph-based methods are proposed: (1) graph (and hyper-graph) matching by reweighted random walks, (2) progressive graph matching, (3) mode-seeking on graphs. The proposed (hyper-)graph matching method provides robust feature matching under non-rigid deformation and appearance variation, and the progressive graph matching framework dramatically improves the performance of graph matching in an efficient way. Moreover, combined with these methods, the proposed graph-based mode-seeking can discover reliable clusters of matches as objects and eliminate the others as outliers. Experimental evaluations demonstrate the superiority of the proposed methods in image matching and the potential to other graph-related tasks.