Common Visual Pattern Discovery via Directed Graph

A directed graph (or digraph) approach is proposed in this paper for identifying all the visual objects commonly presented in the two images under comparison. As a model, the directed graph is superior to the undirected graph, since there are two link weights with opposite orientations associated with each link of the graph. However, it inevitably draws two main challenges: 1) how to compute the two link weights for each link and 2) how to extract the subgraph from the digraph. For 1), a novel n-ranking process for computing the generalized median and the Gaussian link-weight mapping function are developed that basically map the established undirected graph to the digraph. To achieve this graph mapping, the proposed process and function are applied to each vertex independently for computing its directed link weight by not only considering the influences inserted from its immediately adjacent neighboring vertices (in terms of their link-weight values), but also offering other desirable merits-i.e., link-weight enhancement and computational complexity reduction. For 2), an evolutionary iterative process for solving the non-cooperative game theory is exploited to handle the non-symmetric weighted adjacency matrix. The abovementioned two stages of processes will be conducted for each assumed scale-change factor, experimented over a range of possible values, one factor at a time. If there is a match on the scale-change factor under experiment, the common visual patterns with the same scale-change factor will be extracted. If more than one pattern are extracted, the proposed topological splitting method is able to further differentiate among them provided that the visual objects are sufficiently far apart from each other. Extensive simulation results have clearly demonstrated the superior performance accomplished by the proposed digraph approach, compared with those of using the undirected graph approach.