Common visual pattern discovery via directed graph model

In this paper, a novel directed graph (or digraph) model-based approach is proposed to discover visual patterns commonly shared by two images. Unlike the conventional undirected graph model with only one weight value on each link, the directed graph model has two link weights, one for each direction of the link. In our work, it takes two phases to compute the link weights. First, the principle of pairwise spatial consistency is exploited to generate the initial link weights. The entire initial weights are then modified to generate the relative link weights by further considering the “relativeness” of neighboring vertices for each vertex using our proposed n-ranking value. Consequently, the resulted relative link weights are more robust to combat various commonly encountered scenarios such as large viewpoint variations and inaccurate feature descriptors. Based on the relative link weights, the strongly-connected subgraph for each scale value under consideration is then extracted from the graph by applying the non-cooperative game theory for handling non-symmetric adjacency matrix issue. All the vertices (i.e., point-to-point feature correspondences) belonging to the subgraph are collectively denoted as one common visual pattern. Preliminary simulation results have reasonably demonstrated the efficacy and robustness of the proposed method on discovering common visual patterns.