Critical Nets and Beta-Stable Features forImage MatchingSteve Gu and Ying Zheng and Carlo TomasiDepartment of Computer ScienceDuke UniversityDurham, North Carolina, USA 27708{steve,yuanqi,tomasi}@cs.duke.eduAbstract. We propose new ideas and efficient algorithms towards bridg-ing the gap between bag-of-features and constellation descriptors for im-age matching. Specifically, we show how to compute connections betweenlo cal image features in the form of a critical net whose construction isrepeatable across changes of viewing conditions or scene configuration.Arcs of the net provide a more reliable frame of reference than individualfeatures do for the purpose of invariance. In addition, regions associatedwith either small stars or loops in the critical net can be used as partsfor recognition or retrieval, and subgraphs of the critical net that arematched across images exhibit common structures shared by differentimages. We also introduce the notion of beta-stable features, a variationon the notion of feature lifetime from the literature of scale space. Ourexperiments show that arc-based SIFT-like descriptors of beta-stable fea-tures are more repeatable and more accurate than competing descriptors.We also provide anecdotal evidence of the usefulness of image parts andof the structures that are found to be common across images.Key words: bag-of-features, constellation, image matching1 IntroductionImage matching enables at least tracking, stereo, recognition, and retrieval, andis therefore arguably the most important problem in computer vision.A fundamental tension exists between the repeatability and distinctiveness ofthe features used in matching (our terminology is from a recent survey [1]). Fea-tures with a small image support can often be made to be repeatable in the sensethat they can be found reliably in different views of the same s ce ne. Featureswith more extended supports are potentially more distinctive in that two large,distinct regions are less likely to look like each other, ceteris paribus, than twosmall ones. Because of this, repeatability reduces false negatives in matching,and distinctiveness reduces false positives. Unfortunately, larger features tend tobe less repeatable: They often deform more than sm aller features under changesof viewing conditions or scene configuration, and occlusions are more likely tohide different parts of large features in different views.2 Steve Gu, Ying Zheng, Carlo TomasiTwo approaches in the literature have shown considerable success in easingthis tension. The “constellation” approach [2–4] des cribes both the appearanceand the relative positions of small features. The “bag of features” approach [5–8]foregoes the description of positions, and relies on aggregate statistics of appear-ance. Constellations subsume bags of features, so the wide use of the latter isjustified by considerations of efficiency.Important steps have been made in recent literature [9, 10] to connect localfeatures into more global models efficiently. In this paper, we propose a furtherstep towards practical constellations by defining repeatable connections betweenlocal features. Specifically, we introduce the notion of a critical net, a non-planarbut low-average-degree graph that connects extrema of a function of the imageintensities. Repeatability is a consequence of the fact that the critical net isinvariant to affine deformations of the image domain and a certain wide classof changes in the function values. Our critical nets are a close relative of theMorse-Smale graph [11, 12], but can be computed much more reliably and veryefficiently on images defined on the integer grid.We then show how critical nets can be used for matching. First, the primi-tives being matched are arcs of the net, rather than nodes. Arcs encode relativepositions of local features, and are more reliable than individual features in estab-lishing an image-dependent frame of reference to be used as a basis for invarianceto geometric image transformation. Second, we use the connectivity induced bythe critical net to identify both repeatable image parts and common structuresof interest across images. Specifically, parts are regions associated with eithersmall stars or loops in the critical net, and common structures of interest arethe convex hulls of connected components that are matched across two images.To complement the repeatability of critical nets, we also introduce a notionof β-stable features based on a Laplacian scale-space description of the image.We choose the Laplacian for several reasons: this operator has been proven suc-cessful in empirical evaluations [13]; the resulting extrema detect image contrastbut remain invariant to multiplicative changes or the addition of any harmonicfunction to the image; and the choice of the Laplacian facilitates comparisonwith operators like SIFT [14] and its variants (see [1] for a survey). The conceptof β-stability is a variation on the theme of a feature’s lifetime (a.k.a. ’stability’[15] or ’persistence’ [11]) familiar to the literature of scale space [16–20], and isbuilt on the notion of convexity: rather than selecting features that persist overa wide interval of scales, we compute the features at a scale chosen so that thenumber of convex and concave regions of the image brightness function remainsconstant within a scale interval of length β. We show that this shift in selectioncriterion leads to robustness to high-frequency perturbations of the image, inaddition to the invariance advantages deriving from the use of the Laplacian.For ease of exposition, β-stable features are described first, in section 2,followed by a discussion of the concept of critical net in section 3. Sections 4 and5 then introduce concepts for – and experiments with – image matching and thedefinition of image parts and common structures of interest. Section 6 concludesand outlines future work.Critical Nets and Beta-Stable Features for Image Matching 32 Beta-Stable Features in Scale SpaceFig. 1. The maximally convex regions Lk> 0 are shown in white for k ranging from 1 to100 in approximately equal steps. Image boundaries are handled in standard way: padimages by replication b efore pro ces sing, then remove boundary regions in the results.Unless otherwise indicated, input images in this paper are from Caltech 101 [7].One of the most common feature detectors is based on the Laplacian of theGaussian (LoG, [18, 19]). First, the input image