We propose new ideas and efficient algorithms towards bridging the gap between bag-of-features and constellation descriptors for image matching. Specifically, we show how to compute connections between local image features in the form of a critical net whose construction is repeatable across changes of viewing conditions or scene configuration. Arcs of the net provide a more reliable frame of reference than individual features do for the purpose of invariance. In addition, regions associated with either small stars or loops in the critical net can be used as parts for recognition or retrieval, and subgraphs of the critical net that are matched across images exhibit common structures shared by different images. We also introduce the notion of beta-stable features, a variation on the notion of feature lifetime from the literature of scale space. Our experiments show that arc-based SIFT-like descriptors of beta-stable features are more repeatable and more accurate than competing descriptors. We also provide anecdotal evidence of the usefulness of image parts and of the structures that are found to be common across images.
Given a function f that is defined on a 2D grid, the critical net is a directed bipartite graph whose nodes are composed of the local extrema of f and a local minimum is connected to a local maximum if there exists an ascending path ( the pixel values increase monotonically along the path ) going from the minimum to the maximum. In the following, we demonstrate the invariance of the critical net under various image distortion. Here are the MATLAB Code for computing the critical net, together with the original Paper and the Slides. We appreciate if you decide to Cite our paper.
