Image representation and matching with geometric-edge random structure graph

Structure graphs are often used in image structural representation by organizing the units of image (such as feature points). However, due to “noise” or non-rigid deformations, the graphs generated from images are usually not stable. To overcome this problem, image matching and recognition can usually be achieved by inexact graph matching means. There has been recent much work on inexact graph matching, but not much on robust graph modeling itself. In this paper we develop a new robust structure graph model for image representation and matching. We believe that a robust structure graph model should adapt to the noise or perturbation of the image units. Here, we explore random graphs instead of traditional graph models and propose a novel random structure graph, called Geometric-Edge random graphs (G-E graphs), for image representation and matching. The main idea of G-E graphs is that the probabilities of edges between node pairs are explored to indicate the uncertainty or variations of edges in the geometric graph generated under some noise or perturbation of the image units. Promising experimental results on both image matching and pattern space embedding show that the proposed G-E graphs are effective and robust to structural variations and significantly outperform traditional graph models.