A center-biased graph learning algorithm for image classification

Abstract

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 paper 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 we call center biased random walk with restart (CBRWR). This algorithm can be implemented using two-dimensional Gaussian distribution. For this, we 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 our method. We conducted image classification experiments to check the competitiveness of our algorithm.