Graph matching is an important problem in the field of computer vision. Graph matching problem can be represented as quadratic assignment problem. Because the problem is known to be NP-hard, optimal solution is hardly achievable so that a lot of algorithms are proposed to approximate it. Although there have been many studies about fast and accurate approximations, there have been few studies about graph learning. This thesis presents a graph learning algorithm which works in an unsupervised way. The process requires neither annotated dataset nor training dataset. The algorithm learns a graph from a model image using a variation of random walk, which I call \textit{center biased random walk with restart} (CBRWR). This algorithm can be implemented using two-dimensional Gaussian distribution. For this, I propose a modified histogram-based attribute. The attributes consider relationship between edges as well as nodes. Image matching is done using the model graph which is created by my method. I conducted image classification experiments to check the competitiveness of my algorithm.
그래프 매칭은 컴퓨터 비전 분야의 중요 문제 중 하나이다. 그래프 매칭 문제는 NP-hard 문제로 알려져 있는 2차 할당 문제(quadratic assignment problem)로 표현할 수 있기 때문에 최적해를 구하는 것은 현실적으로 불가능하다. 이 문제를 해결하기 위해 다양한 근사법이 연구되었지만, 그래프를 학습하는 방법에 대한 연구는 거의 진행되지 않았다. 이에 본 논문에서는 자율 학습 방식을 따르는 그래프 학습 방법을 제안한다. 제안 방법은 입력 데이터 외에 추가적인 데이터를 필요로 하지 않는다. 본 논문에서는 무작위 행보의 일종인 \textit{중심 편향 무작위 행보}를 제안하고 이를 통하여 그래프를 학습한다. 제안 방법은 2차원 가우시안 분포를 통하여 구현되며, 이 과정에서 히스토그램 기반 속성을 수정하여 사용한다. 속성은 정점 사이의 관계 뿐만 아니라 간선 사이의 관계까지 고려하여 결정된다. 이미지 매칭은 이 과정을 통해 생성된 모델 그래프를 사용하여 진행되며, 제안 방법의 경쟁력을 확인하기 위해 이미지 분류 실험을 수행하였다.
