Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> The problem we are addressing in Alvey Project MMI149 is that of using computer vision to understand the unconstrained 3D world, in which the viewed scenes will in general contain too wide a diversity of objects for topdown recognition techniques to work. For example, we desire to obtain an understanding of natural scenes, containing roads, buildings, trees, bushes, etc., as typified by the two frames from a sequence illustrated in Figure 1. The solution to this problem that we are pursuing is to use a computer vision system based upon motion analysis of a monocular image sequence from a mobile camera. By extraction and tracking of image features, representations of the 3D analogues of these features can be constructed. <s> BIB001 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> No feature-based vision system can work unless good features can be identified and tracked from frame to frame. Although tracking itself is by and large a solved problem, selecting features that can be tracked well and correspond to physical points in the world is still hard. We propose a feature selection criterion that is optimal by construction because it is based on how the tracker works, and a feature monitoring method that can detect occlusions, disocclusions, and features that do not correspond to points in the world. These methods are based on a new tracking algorithm that extends previous Newton-Raphson style search methods to work under affine image transformations. We test performance with several simulations and experiments. > <s> BIB002 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> This paper describes a method for the enhancement of curvilinear structures such as vessels and bronchi in three-dimensional (3-D) medical images. A 3-D line enhancement filter is developed with the aim of discriminating line structures from other structures and recovering line structures of various widths. The 3-D line filter is based on a combination of the eigenvalues of the 3-D Hessian matrix. Multi-scale integration is formulated by taking the maximum among single-scale filter responses, and its characteristics are examined to derive criteria for the selection of parameters in the formulation. The resultant multi-scale line-filtered images provide significantly improved segmentation and visualization of curvilinear structures. The usefulness of the method is demonstrated by the segmentation and visualization of brain vessels from magnetic resonance imaging (MRI) and magnetic resonance angiography (MRA), bronchi from a chest CT, and liver vessels (portal veins) from an abdominal CT. <s> BIB003 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> Registration of 3D medical images consists in computing the "best" transformation between two acquisitions, or equivalently, determines the point to point correspondence between the images. Registration algorithms are usually based either on features extracted from the image (feature-based approaches) or on the optimization of a similarity measure of the images intensities (intensitybased or iconic approaches). Another classification criterion is the type of transformation sought (e.g. rigid or non-rigid). In this chapter, we concentrate on feature-based approaches for rigid registration, similar approaches for non-rigid registration being reported in another set of publication [35, 36]. We show how to reduce the dimension of the registration problem by first extracting a surface from the 3D image, then landmark curves on this surface and possibly landmark points on these curves. This concept proved its efficiency through many applications in medical image analysis as we will see in the sequel. This work has been for a long time a central investigation topic of the Epidaure team [2] and we can only reflect here on a small part of the research done in this area. We present in the first section the notions of crest lines and extremal points and how these differential geometry features can be extracted from 3D images. In Section 2, we focus on the different rigid registration algorithms that we used to register such features. The last section analyzes the possible errors in this registration scheme and demonstrates that a very accurate registration could be achieved. <s> BIB004 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> In this article we merge point feature and intensity-based registration in a single algorithm to tackle the problem of multiple brain registration. Because of the high variability of the shape of the cortex across individuals, there exist geometrical ambiguities in the registration process that an intensity measure alone is unable to solve. This problem can be tackled using anatomical knowledge. First, we automatically segment and label the whole set of the cortical sulci, with a non-parametric approach that enables the capture of their highly variable shape and topology. Then, we develop a registration energy that merges intensity and feature point matching. Its minimization leads to a linear combination of a dense smooth vector field and radial basis functions. We use and process differently the bottom line of the sulci from its upper border, whose localization is even more variable across individuals. We show that the additional sulcal energy improves the registration of the cortical sulci, while still keeping the transformation smooth and one-to-one. <s> BIB005 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> Guidance systems designed for neurosurgery, hip surgery, spine surgery and for approaches to other anatomy that is relatively rigid can use rigid-body transformations to accomplish image registration. These systems often rely on point-based registration to determine the transformation and many such systems use attached fiducial markers to establish accurate fiducial points for the registration, the points being established by some fiducial localization process. Accuracy is important to these systems, as is knowledge of the level of that accuracy. An advantage of marker-based systems, particularly those in which the markers are bone-implanted, is that registration error depends only on the fiducial localization and is, thus, to a large extent independent of the particular object being registered. Thus, it should be possible to predict the clinical accuracy of marker-based systems on the basis of experimental measurements made with phantoms or previous patients. For most registration tasks, the most important error measure is target registration error (TRE), which is the distance after registration between corresponding points not used in calculating the registration transform. Here, the authors derive an approximation to the distribution of TRE; this is an extension of previous work that gave the expected squared value of TRE. They show the distribution of the squared magnitude of TRE and that of the component of TRE in an arbitrary direction. Using numerical simulations, the authors show that their theoretical results are a close match to the simulated ones. <s> BIB006 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> Abstract This paper describes the design, implementation and results of a unified non-rigid feature registration method for the purposes of anatomical MRI brain registration. An important characteristic of the method is its ability to fuse different types of anatomical features into a single point-set representation. We demonstrate the application of the method using two different types of features: the outer cortical surface and major sulcal ribbons. Non-rigid registration of the combined feature point-sets is then performed using a new robust non-rigid point matching algorithm. The point matching algorithm implements an iterative joint clustering and matching (JCM) strategy which effectively reduces the computational complexity without sacrificing accuracy. We have conducted carefully designed synthetic experiments to gauge the effect of using different types of features either separately or together. A validation study examining the accuracy of non-rigid alignment of many brain structures is also presented. Finally, we present anecdotal results on the alignment of two subject MRI brain data. <s> BIB007 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> This paper describes a robust hierarchical algorithm for fully-automatic registration of a pair of images of the curved human retina photographed by a fundus microscope. Accurate registration is essential for mosaic synthesis, change detection, and design of computer-aided instrumentation. Central to the algorithm is a 12-parameter interimage transformation derived by modeling the retina as a rigid quadratic surface with unknown parameters. The parameters are estimated by matching vascular landmarks by recursively tracing the blood vessel structure. The parameter estimation technique, which could be generalized to other applications, is a hierarchy of models and methods, making the algorithm robust to unmatchable image features and mismatches between features caused by large interframe motions. Experiments involving 3,000 image pairs from 16 different healthy eyes were performed. Final registration errors less than a pixel are routinely achieved. The speed, accuracy, and ability to handle small overlaps compare favorably with retinal image registration techniques published in the literature. <s> BIB008 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> This paper aims to present a review of recent as well as classic image registration methods. Image registration is the process of overlaying images (two or more) of the same scene taken at different times, from different viewpoints, and/or by different sensors. The registration geometrically align two images (the reference and sensed images). The reviewed approaches are classified according to their nature (areabased and feature-based) and according to four basic steps of image registration procedure: feature detection, feature matching, mapping function design, and image transformation and resampling. Main contributions, advantages, and drawbacks of the methods are mentioned in the paper. Problematic issues of image registration and outlook for the future research are discussed too. The major goal of the paper is to provide a comprehensive reference source for the researchers involved in image registration, regardless of particular application areas. q 2003 Elsevier B.V. All rights reserved. <s> BIB009 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> Motivated by the problem of retinal image registration, this paper introduces and analyzes a new registration algorithm called Dual-Bootstrap Iterative Closest Point (Dual-Bootstrap ICP). The approach is to start from one or more initial, low-order estimates that are only accurate in small image regions, called bootstrap regions. In each bootstrap region, the algorithm iteratively: 1) refines the transformation estimate using constraints only from within the bootstrap region; 2) expands the bootstrap region; and 3) tests to see if a higher order transformation model can be used, stopping when the region expands to cover the overlap between images. Steps 1): and 3), the bootstrap steps, are governed by the covariance matrix of the estimated transformation. Estimation refinement [Step 2)] uses a novel robust version of the ICP algorithm. In registering retinal image pairs, Dual-Bootstrap ICP is initialized by automatically matching individual vascular landmarks, and it aligns images based on detected blood vessel centerlines. The resulting quadratic transformations are accurate to less than a pixel. On tests involving approximately 6000 image pairs, it successfully registered 99.5% of the pairs containing at least one common landmark, and 100% of the pairs containing at least one common landmark and at least 35% image overlap. <s> BIB010 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> Local feature approaches to vision geometry and object recognition are based on selecting and matching sparse sets of visually salient image points, known as 'keypoints' or 'points of interest'. Their performance depends critically on the accuracy and reliability with which corresponding keypoints can be found in subsequent images. Among the many existing keypoint selection criteria, the popular Forstner-Harris approach explicitly targets geometric stability, defining keypoints to be points that have locally maximal self-matching precision under translational least squares template matching. However, many applications require stability in orientation and scale as well as in position. Detecting translational key- points and verifying orientation/scale behaviour post hoc is suboptimal, and can be misleading when different motion variables interact. We give a more principled formulation, based on extending the Forstner-Harris approach to general motion models and robust template matching. We also incorporate a simple local appear- ance model to ensure good resistance to the most common illumination variations. We illustrate the resulting methods and quantify their performance on test images. <s> BIB011 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> In this paper we propose a novel approach for detecting interest points invariant to scale and affine transformations. Our scale and affine invariant detectors are based on the following recent results: (1) Interest points extracted with the Harris detector can be adapted to affine transformations and give repeatable results (geometrically stable). (2) The characteristic scale of a local structure is indicated by a local extremum over scale of normalized derivatives (the Laplacian). (3) The affine shape of a point neighborhood is estimated based on the second moment matrix. ::: ::: Our scale invariant detector computes a multi-scale representation for the Harris interest point detector and then selects points at which a local measure (the Laplacian) is maximal over scales. This provides a set of distinctive points which are invariant to scale, rotation and translation as well as robust to illumination changes and limited changes of viewpoint. The characteristic scale determines a scale invariant region for each point. We extend the scale invariant detector to affine invariance by estimating the affine shape of a point neighborhood. An iterative algorithm modifies location, scale and neighborhood of each point and converges to affine invariant points. This method can deal with significant affine transformations including large scale changes. The characteristic scale and the affine shape of neighborhood determine an affine invariant region for each point. ::: ::: We present a comparative evaluation of different detectors and show that our approach provides better results than existing methods. The performance of our detector is also confirmed by excellent matching resultss the image is described by a set of scale/affine invariant descriptors computed on the regions associated with our points. <s> BIB012 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> Many different low-level feature detectors exist and it is widely agreed that the evaluation of detectors is important. In this paper we introduce two evaluation criteria for interest points' repeatability rate and information content. Repeatability rate evaluates the geometric stability under different transformations. Information content measures the distinctiveness of features. Different interest point detectors are compared using these two criteria. We determine which detector gives the best results and show that it satisfies the criteria well. <s> BIB013 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> The fact that objects in the world appear in different ways depending on the scale of observation has important implications if one aims at describing them. It shows that the notion of scale is of utmost importance when processing unknown measurement data by automatic methods. In their seminal works, Witkin (1983) and Koenderink (1984) proposed to approach this problem by representing image structures at different scales in a so-called scale-space representation. Traditional scale-space theory building on this work, however, does not address the problem of how to select local appropriate scales for further analysis. This article proposes a systematic methodology for dealing with this problem. A framework is presented for generating hypotheses about interesting scale levels in image data, based on a general principle stating that local extrema over scales of different combinations of γ-normalized derivatives are likely candidates to correspond to interesting structures. Specifically, it is shown how this idea can be used as a major mechanism in algorithms for automatic scale selection, which adapt the local scales of processing to the local image structure. ::: ::: Support for the proposed approach is given in terms of a general theoretical investigation of the behaviour of the scale selection method under rescalings of the input pattern and by integration with different types of early visual modules, including experiments on real-world and synthetic data. Support is also given by a detailed analysis of how different types of feature detectors perform when integrated with a scale selection mechanism and then applied to characteristic model patterns. Specifically, it is described in detail how the proposed methodology applies to the problems of blob detection, junction detection, edge detection, ridge detection and local frequency estimation. ::: ::: In many computer vision applications, the poor performance of the low-level vision modules constitutes a major bottleneck. It is argued that the inclusion of mechanisms for automatic scale selection is essential if we are to construct vision systems to automatically analyse complex unknown environments. <s> BIB014 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> Many computer vision problems can be considered to consist of two main tasks: the extraction of image content descriptions and their subsequent matching. The appropriate choice of type and level of description is of course task dependent, yet it is generally accepted that the low-level or so called early vision layers in the Human Visual System are context independent. ::: ::: This paper concentrates on the use of low-level approaches for solving computer vision problems and discusses three inter-related aspects of this: saliencys scale selection and content description. In contrast to many previous approaches which separate these tasks, we argue that these three aspects are intrinsically related. Based on this observation, a multiscale algorithm for the selection of salient regions of an image is introduced and its application to matching type problems such as tracking, object recognition and image retrieval is demonstrated. <s> BIB015 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> Abstract The wide-baseline stereo problem, i.e. the problem of establishing correspondences between a pair of images taken from different viewpoints is studied. A new set of image elements that are put into correspondence, the so called extremal regions , is introduced. Extremal regions possess highly desirable properties: the set is closed under (1) continuous (and thus projective) transformation of image coordinates and (2) monotonic transformation of image intensities. An efficient (near linear complexity) and practically fast detection algorithm (near frame rate) is presented for an affinely invariant stable subset of extremal regions, the maximally stable extremal regions (MSER). A new robust similarity measure for establishing tentative correspondences is proposed. The robustness ensures that invariants from multiple measurement regions (regions obtained by invariant constructions from extremal regions), some that are significantly larger (and hence discriminative) than the MSERs, may be used to establish tentative correspondences. The high utility of MSERs, multiple measurement regions and the robust metric is demonstrated in wide-baseline experiments on image pairs from both indoor and outdoor scenes. Significant change of scale (3.5×), illumination conditions, out-of-plane rotation, occlusion, locally anisotropic scale change and 3D translation of the viewpoint are all present in the test problems. Good estimates of epipolar geometry (average distance from corresponding points to the epipolar line below 0.09 of the inter-pixel distance) are obtained. <s> BIB016 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> Stable local feature detection and representation is a fundamental component of many image registration and object recognition algorithms. Mikolajczyk and Schmid (June 2003) recently evaluated a variety of approaches and identified the SIFT [D. G. Lowe, 1999] algorithm as being the most resistant to common image deformations. This paper examines (and improves upon) the local image descriptor used by SIFT. Like SIFT, our descriptors encode the salient aspects of the image gradient in the feature point's neighborhood; however, instead of using SIFT's smoothed weighted histograms, we apply principal components analysis (PCA) to the normalized gradient patch. Our experiments demonstrate that the PCA-based local descriptors are more distinctive, more robust to image deformations, and more compact than the standard SIFT representation. We also present results showing that using these descriptors in an image retrieval application results in increased accuracy and faster matching. <s> BIB017 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> The paper gives a snapshot of the state of the art in affine covariant region detectors, and compares their performance on a set of test images under varying imaging conditions. Six types of detectors are included: detectors based on affine normalization around Harris (Mikolajczyk and Schmid, 2002; Schaffalitzky and Zisserman, 2002) and Hessian points (Mikolajczyk and Schmid, 2002), a detector of `maximally stable extremal regions', proposed by Matas et al. (2002); an edge-based region detector (Tuytelaars and Van Gool, 1999) and a detector based on intensity extrema (Tuytelaars and Van Gool, 2000), and a detector of `salient regions', proposed by Kadir, Zisserman and Brady (2004). The performance is measured against changes in viewpoint, scale, illumination, defocus and image compression. ::: ::: The objective of this paper is also to establish a reference test set of images and performance software, so that future detectors can be evaluated in the same framework. <s> BIB018 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> This paper evaluates the performance of several popular corner detectors using two newly defined criteria. The majority of authors of published corner detectors have not used theoretical criteria to measure the consistency and accuracy of their algorithms. They usually only illustrate their results on a few test images and may compare the results visually to the results of other corner detectors. Some authors have proposed various criteria for performance evaluation of corner detection algorithms but those criteria have a number of shortcomings. We propose two new criteria to evaluate the performance of corner detectors. Our proposed criteria are consistency and accuracy. These criteria were measured using several test images and experiments such as rotation, uniform scaling, non-uniform scaling and affine transforms. To measure accuracy, we created ground truth based on majority human judgement. The results show that the enhanced CSS corner detector performs better according to these criteria. <s> BIB019 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> In this paper, we compare the performance of descriptors computed for local interest regions, as, for example, extracted by the Harris-Affine detector [Mikolajczyk, K and Schmid, C, 2004]. Many different descriptors have been proposed in the literature. It is unclear which descriptors are more appropriate and how their performance depends on the interest region detector. The descriptors should be distinctive and at the same time robust to changes in viewing conditions as well as to errors of the detector. Our evaluation uses as criterion recall with respect to precision and is carried out for different image transformations. We compare shape context [Belongie, S, et al., April 2002], steerable filters [Freeman, W and Adelson, E, Setp. 1991], PCA-SIFT [Ke, Y and Sukthankar, R, 2004], differential invariants [Koenderink, J and van Doorn, A, 1987], spin images [Lazebnik, S, et al., 2003], SIFT [Lowe, D. G., 1999], complex filters [Schaffalitzky, F and Zisserman, A, 2002], moment invariants [Van Gool, L, et al., 1996], and cross-correlation for different types of interest regions. We also propose an extension of the SIFT descriptor and show that it outperforms the original method. Furthermore, we observe that the ranking of the descriptors is mostly independent of the interest region detector and that the SIFT-based descriptors perform best. Moments and steerable filters show the best performance among the low dimensional descriptors. <s> BIB020 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> We present an efficient spectral method for finding consistent correspondences between two sets of features. We build the adjacency matrix M of a graph whose nodes represent the potential correspondences and the weights on the links represent pairwise agreements between potential correspondences. Correct assignments are likely to establish links among each other and thus form a strongly connected cluster. Incorrect correspondences establish links with the other correspondences only accidentally, so they are unlikely to belong to strongly connected clusters. We recover the correct assignments based on how strongly they belong to the main cluster of M, by using the principal eigenvector of M and imposing the mapping constraints required by the overall correspondence mapping (one-to-one or one-to-many). The experimental evaluation shows that our method is robust to outliers, accurate in terms of matching rate, while being much faster than existing methods <s> BIB021 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> We approach recognition in the framework of deformable shape matching, relying on a new algorithm for finding correspondences between feature points. This algorithm sets up correspondence as an integer quadratic programming problem, where the cost function has terms based on similarity of corresponding geometric blur point descriptors as well as the geometric distortion between pairs of corresponding feature points. The algorithm handles outliers, and thus enables matching of exemplars to query images in the presence of occlusion and clutter. Given the correspondences, we estimate an aligning transform, typically a regularized thin plate spline, resulting in a dense correspondence between the two shapes. Object recognition is then handled in a nearest neighbor framework where the distance between exemplar and query is the matching cost between corresponding points. We show results on two datasets. One is the Caltech 101 dataset (Fei-Fei, Fergus and Perona), an extremely challenging dataset with large intraclass variation. Our approach yields a 48% correct classification rate, compared to Fei-Fei et al 's 16%. We also show results for localizing frontal and profile faces that are comparable to special purpose approaches tuned to faces. <s> BIB022 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> A method is proposed to enhance vascular structures within the framework of scale space theory. We combine a smooth vessel filter which is based on a geometrical analysis of the Hessian's eigensystem, with a non-linear anisotropic diffusion scheme. The amount and orientation of diffusion depend on the local vessel likeliness. Vessel enhancing diffusion (VED) is applied to patient and phantom data and compared to linear, regularized Perona-Malik, edge and coherence enhancing diffusion. The method performs better than most of the existing techniques in visualizing vessels with varying radii and in enhancing vessel appearance. A diameter study on phantom data shows that VED least affects the accuracy of diameter measurements. It is shown that using VED as a preprocessing step improves level set based segmentation of the cerebral vasculature, in particular segmentation of the smaller vessels of the vasculature. <s> BIB023 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> We present large deformation diffeomorphic metric curve mapping (LDDMM-Curve) for registering cortical hemispheres. We showed global cortical hemisphere matching and evaluated the mapping accuracy in five subregions of the cortex in fourteen MRI scans. <s> BIB024 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> The displacement and deformation of brain tissue is a major source of error in image-guided neurosurgery systems. We have designed and implemented a method to detect and correct brain shift using pre-operative MR images and intraoperative Doppler ultrasound data and present its validation with both real and simulated data. The algorithm uses segmented vessels from both modalities, and estimates the deformation using a modified version of the iterative closest point (ICP) algorithm. We use the least trimmed squares (LTS) to reduce the number of outliers in the point matching procedure. These points are used to drive a thin-plate spline transform to achieve non-linear registration. Validation was completed in two parts. First, the technique was tested and validated using realistic simulations where the results were compared to the known deformation. The registration technique recovered 75% of the deformation in the region of interest accounting for deformations as large as 20 mm. Second, we performed a PVA-cryogel phantom study where both MR and ultrasound images of the phantom were obtained for three different deformations. The registration results based on MR data were used as a gold standard to evaluate the performance of the ultrasound based registration. On average, deformations of 7.5 mm magnitude were corrected to within 1.6 mm for the ultrasound based registration and 1.07 mm for the MR based registration. <s> BIB025 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> This article presents a novel scale- and rotation-invariant detector and descriptor, coined SURF (Speeded-Up Robust Features). SURF approximates or even outperforms previously proposed schemes with respect to repeatability, distinctiveness, and robustness, yet can be computed and compared much faster. This is achieved by relying on integral images for image convolutions; by building on the strengths of the leading existing detectors and descriptors (specifically, using a Hessian matrix-based measure for the detector, and a distribution-based descriptor); and by simplifying these methods to the essential. This leads to a combination of novel detection, description, and matching steps. The paper encompasses a detailed description of the detector and descriptor and then explores the effects of the most important parameters. We conclude the article with SURF's application to two challenging, yet converse goals: camera calibration as a special case of image registration, and object recognition. Our experiments underline SURF's usefulness in a broad range of topics in computer vision. <s> BIB026 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> The reconstruction of three-dimensional (3D) ultrasound panorama from multiple ultrasound volumes can provide a wide field of view for better clinical diagnosis. Registration of ultrasound volumes has been a key issue for the success of this panoramic process. In this paper, we propose a method to register and stitch ultrasound volumes, which are scanned by dedicated ultrasound probe, based on an improved 3D Scale Invariant Feature Transform (SIFT) algorithm. We propose methods to exclude artifacts from ultrasound images in order to improve the overall performance in 3D feature point extraction and matching. Our method has been validated on both phantom and clinical data sets of human liver. Experimental results show the effectiveness and stability of our approach, and the precision of our method is comparable to that of the position tracker based registration. <s> BIB027 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> This paper presents a comprehensive extension of the Scale Invariant Feature Transform (SIFT), originally introduced in 2D, to volumetric images. While tackling the significant computational efforts required by such multiscale processing of large data volumes, our implementation addresses two important mathematical issues related to the 2D-to-3D extension. It includes efficient steps to filter out extracted point candidates that have low contrast or are poorly localized along edges or ridges. In addition, it achieves, for the first time, full 3D orientation invariance of the descriptors, which is essential for 3D feature matching. An application of this technique is demonstrated to the feature-based automated registration and segmentation of clinical datasets in the context of radiation therapy. <s> BIB028 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> In the context of computational anatomy, one aims at understanding and modelling the anatomy of the brain and its variations across a population. This geometrical variability is often measured from precisely defined anatomical landmarks such as sulcal lines or meshes of brain structures. This requires (1) to compare geometrical objects without introducing too many non realistic priors and (2) to retrieve the variability of the whole brain from the variability of the landmarks. ::: ::: We propose, in this paper, to infer a statistical brain model from the consistent integration of variability of sulcal lines. The similarity between two sets of lines is measured by a distance on currents that does not assume any type of point correspondences and it is not sensitive to the sampling of lines. This shape similarity measure is used in a diffeomorphic registrations which retrieves a single deformation of the whole 3D space. This diffeomorphism integrates the variability of all lines in a as spatially consistent manner as possible. ::: ::: Based on repeated pairwise registrations on a large database, we learn how the mean anatomy varies in a population by computing statistics on diffeomorphisms. Whereas usual methods lead to descriptive measures of variability, such as variability maps or statistical tests, our model is generative: we can simulate new observations according to the learned probability law on deformations. In practice, this variability captured by the model is synthesized in the principal modes of deformations. As a deformation is dense, we can also apply it to other anatomical structures defined in the template space. This is illustrated the action of the principal modes of deformations to a mean cortical surface. ::: ::: Eventually, our current-based diffeomorphic registration (CDR) approach is carefully compared to a pointwise line correspondences (PLC) method. Variability measures are computed with both methods on the same dataset of sulcal lines. The results suggest that we retrieve more variability with CDR than with PLC, especially in the direction of the lines. Other differences also appear which highlight the different methodological assumptions each method is based on. <s> BIB029 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> In this paper we present a new approach for establishing correspondences between sparse image features related by an unknown non-rigid mapping and corrupted by clutter and occlusion, such as points extracted from a pair of images containing a human figure in distinct poses. We formulate this matching task as an energy minimization problem by defining a complex objective function of the appearance and the spatial arrangement of the features. Optimization of this energy is an instance of graph matching, which is in general a NP-hard problem. We describe a novel graph matching optimization technique, which we refer to as dual decomposition (DD), and demonstrate on a variety of examples that this method outperforms existing graph matching algorithms. In the majority of our examples DD is able to find the global minimum within a minute. The ability to globally optimize the objective allows us to accurately learn the parameters of our matching model from training examples. We show on several matching tasks that our learned model yields results superior to those of state-of-the-art methods. <s> BIB030 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> We consider the problem of finding a matching between two sets of features, given complex relations among them, going beyond pairwise. Each feature set is modeled by a hypergraph where the complex relations are represented by hyper-edges. A match between the feature sets is then modeled as a hypergraph matching problem. We derive the hyper-graph matching problem in a probabilistic setting represented by a convex optimization. First, we formalize a soft matching criterion that emerges from a probabilistic interpretation of the problem input and output, as opposed to previous methods that treat soft matching as a mere relaxation of the hard matching problem. Second, the model induces an algebraic relation between the hyper-edge weight matrix and the desired vertex-to-vertex probabilistic matching. Third, the model explains some of the graph matching normalization proposed in the past on a heuristic basis such as doubly stochastic normalizations of the edge weights. A key benefit of the model is that the global optimum of the matching criteria can be found via an iterative successive projection algorithm. The algorithm reduces to the well known Sinkhorn [15] row/column matrix normalization procedure in the special case when the two graphs have the same number of vertices and a complete matching is desired. Another benefit of our model is the straight-forward scalability from graphs to hyper-graphs. <s> BIB031 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> If a physical object has a smooth or piecewise smooth boundary, its images obtained by cameras in varying positions undergo smooth apparent deformations. These deformations are locally well approximated by affine transforms of the image plane. In consequence the solid object recognition problem has often been led back to the computation of affine invariant image local features. Such invariant features could be obtained by normalization methods, but no fully affine normalization method exists for the time being. Even scale invariance is dealt with rigorously only by the scale-invariant feature transform (SIFT) method. By simulating zooms out and normalizing translation and rotation, SIFT is invariant to four out of the six parameters of an affine transform. The method proposed in this paper, affine-SIFT (ASIFT), simulates all image views obtainable by varying the two camera axis orientation parameters, namely, the latitude and the longitude angles, left over by the SIFT method. Then it covers the other four parameters by using the SIFT method itself. The resulting method will be mathematically proved to be fully affine invariant. Against any prognosis, simulating all views depending on the two camera orientation parameters is feasible with no dramatic computational load. A two-resolution scheme further reduces the ASIFT complexity to about twice that of SIFT. A new notion, the transition tilt, measuring the amount of distortion from one view to another, is introduced. While an absolute tilt from a frontal to a slanted view exceeding 6 is rare, much higher transition tilts are common when two slanted views of an object are compared (see Figure hightransitiontiltsillustration). The attainable transition tilt is measured for each affine image comparison method. The new method permits one to reliably identify features that have undergone transition tilts of large magnitude, up to 36 and higher. This fact is substantiated by many experiments which show that ASIFT significantly outperforms the state-of-the-art methods SIFT, maximally stable extremal region (MSER), Harris-affine, and Hessian-affine. <s> BIB032 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> In this paper we compare the behavior of different interest point detectors and descriptors under the conditions needed to be used as landmarks in vision-based simultaneous localization and mapping (SLAM). We evaluate the repeatability of the detectors, as well as the invariance and distinctiveness of the descriptors, under different perceptual conditions using sequences of images representing planar objects as well as 3D scenes. We believe that this information will be useful when selecting an appropriate landmark detector and descriptor for visual SLAM. <s> BIB033 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> The recent introduction of next generation spectral OCT scanners has enabled routine acquisition of high resolution, ::: 3D cross-sectional volumetric images of the retina. 3D OCT is used in the detection and management ::: of serious eye diseases such as glaucoma and age-related macular degeneration. For follow-up studies, image ::: registration is a vital tool to enable more precise, quantitative comparison of disease states. This work presents a ::: registration method based on a recently introduced extension of the 2D Scale-Invariant Feature Transform (SIFT) ::: framework1 to 3D.2 The SIFT feature extractor locates minima and maxima in the difference of Gaussian scale ::: space to find salient feature points. It then uses histograms of the local gradient directions around each found ::: extremum in 3D to characterize them in a 4096 element feature vector. Matching points are found by comparing ::: the distance between feature vectors. We apply this method to the rigid registration of optic nerve head- (ONH) ::: and macula-centered 3D OCT scans of the same patient that have only limited overlap. Three OCT data set ::: pairs with known deformation were used for quantitative assessment of the method's robustness and accuracy ::: when deformations of rotation and scaling were considered. Three-dimensional registration accuracy of 2.0±3.3 ::: voxels was observed. The accuracy was assessed as average voxel distance error in N=1572 matched locations. ::: The registration method was applied to 12 3D OCT scans (200 x 200 x 1024 voxels) of 6 normal eyes imaged in ::: vivo to demonstrate the clinical utility and robustness of the method in a real-world environment. <s> BIB034 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> Rigid-body point-based registration is frequently used in computer assisted surgery to align corresponding points, or fiducials, in preoperative and intraoperative data. This alignment is mostly achieved by assuming the same homogeneous error distribution for all the points; however, due to the properties of the medical instruments used in measuring the point coordinates, the error distribution might be inhomogeneous and different for each point. In this paper, in an effort to understand the effect of error distribution in the localized points on the performed registration, we derive a closed-form solution relating the error distribution of each point with the performed registration accuracy. The solution uses maximum likelihood estimation to calculate the probability density function of registration error at each fiducial point. Extensive numerical simulations are performed to validated the proposed solution. <s> BIB035 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> This paper addresses the problem of establishing correspondences between two sets of visual features using higher-order constraints instead of the unary or pairwise ones used in classical methods. Concretely, the corresponding hypergraph matching problem is formulated as the maximization of a multilinear objective function over all permutations of the features. This function is defined by a tensor representing the affinity between feature tuples. It is maximized using a generalization of spectral techniques where a relaxed problem is first solved by a multi-dimensional power method, and the solution is then projected onto the closest assignment matrix. The proposed approach has been implemented, and it is compared to state-of-the-art algorithms on both synthetic and real data. <s> BIB036 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> The accurate segmentation of liver vessels is an important step for further computer assisted analysis in oncologic planning tools. Multiscale based vessel enhancement methods are very famous and many papers about this topic were published. Vesselness filters proposed by Sato et al., Frangi et al. and Erdt et al. are based on eigenvalue analysis of the Hessian matrix. They were developed using completely different approaches, namely experimental, geometrical and analytical. In this paper, their behavior at junctions and nearby vessels is systematically compared and evaluated for the enhancement of the liver vasculature. We found that the filter function proposed by Frangi et al. has problems at junctions, while the ones developed by Sato et al and Erdt et al. have problems with nearby vessels. The latter are preferred for the task of liver vessel enhancement. <s> BIB037 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> Segmentation is a fundamental problem in medical image analysis. The use of prior knowledge is often considered to address the ill-posedness of the process. Such a process consists in bringing all training examples in the same reference pose, and then building statistics. During inference, pose parameters are usually estimated first, and then one seeks a compromise between data-attraction and model-fitness with the prior model. In this paper, we propose a novel higher-order Markov Random Field (MRF) model to encode pose-invariant priors and perform 3D segmentation of challenging data. The approach encodes data support in the singleton terms that are obtained using machine learning, and prior constraints in the higher-order terms. A dual-decomposition-based inference method is used to recover the optimal solution. Promising results on challenging data involving segmentation of tissue classes of the human skeletal muscle demonstrate the potentials of the method. <s> BIB038 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> The Scale-Invariant Feature Transform (or SIFT) algorithm is a highly robust method to extract and consequently match distinctive invariant features from images. These features can then be used to reliably match objects in diering images. The algorithm was rst proposed by Lowe [12] and further developed to increase performance resulting in the classic paper [13] that served as foundation for SIFT which has played an important role in robotic and machine vision in the past decade. <s> BIB039 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> A nonrigid registration method is proposed to automatically align two images by registering two sets of sparse features extracted from the images. Motivated by the paradigm of Robust Point Matching (RPM) algorithms 1,2], which were originally proposed for shape registration, we develop Robust Hybrid Image Matching (RHIM) algorithm by alternatively optimizing feature correspondence and spatial transformation for image registration. Our RHIM algorithm is built to be robust to feature extraction errors. A novel dynamic outlier rejection approach is described for removing outliers and a local refinement technique is applied to correct non-exactly matched correspondences arising from image noise and deformations. Experimental results demonstrate the robustness and accuracy of our method. <s> BIB040 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> The traditional Hessian-related vessel filters often suffer from detecting complex structures like bifurcations due to an over-simplified cylindrical model. To solve this problem, we present a shape-tuned strain energy density function to measure vessel likelihood in 3D medical images. This method is initially inspired by established stress-strain principles in mechanics. By considering the Hessian matrix as a stress tensor, the three invariants from orthogonal tensor decomposition are used independently or combined to formulate distinctive functions for vascular shape discrimination, brightness contrast and structure strength measuring. Moreover, a mathematical description of Hessian eigenvalues for general vessel shapes is obtained, based on an intensity continuity assumption, and a relative Hessian strength term is presented to ensure the dominance of second-order derivatives as well as suppress undesired step-edges. Finally, we adopt the multi-scale scheme to find an optimal solution through scale space. The proposed method is validated in experiments with a digital phantom and non-contrast-enhanced pulmonary CT data. It is shown that our model performed more effectively in enhancing vessel bifurcations and preserving details, compared to three existing filters. <s> BIB041 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> This paper introduces a new rigorous theoretical framework to address discrete MRF-based optimization in computer vision. Such a framework exploits the powerful technique of Dual Decomposition. It is based on a projected subgradient scheme that attempts to solve an MRF optimization problem by first decomposing it into a set of appropriately chosen subproblems, and then combining their solutions in a principled way. In order to determine the limits of this method, we analyze the conditions that these subproblems have to satisfy and demonstrate the extreme generality and flexibility of such an approach. We thus show that by appropriately choosing what subproblems to use, one can design novel and very powerful MRF optimization algorithms. For instance, in this manner we are able to derive algorithms that: 1) generalize and extend state-of-the-art message-passing methods, 2) optimize very tight LP-relaxations to MRF optimization, and 3) take full advantage of the special structure that may exist in particular MRFs, allowing the use of efficient inference techniques such as, e.g., graph-cut-based methods. Theoretical analysis on the bounds related with the different algorithms derived from our framework and experimental results/comparisons using synthetic and real data for a variety of tasks in computer vision demonstrate the extreme potentials of our approach. <s> BIB042 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> This book presents a thorough and detailed guide to image registration, outlining the principles and reviewing state-of-the-art tools and methods. The book begins by identifying the components of a general image registration system, and then describes the design of each component using various image analysis tools. The text reviews a vast array of tools and methods, not only describing the principles behind each tool and method, but also measuring and comparing their performances using synthetic and real data. Features: discusses similarity/dissimilarity measures, point detectors, feature extraction/selection and homogeneous/heterogeneous descriptors; examines robust estimators, point pattern matching algorithms, transformation functions, and image resampling and blending; covers principal axes methods, hierarchical methods, optimization-based methods, edge-based methods, model-based methods, and adaptive methods; includes a glossary, an extensive list of references, and an appendix on PCA. <s> BIB043 </s> Deformable Medical Image Registration: A Survey <s> 1) Detecting Points of Interest: <s> This paper presents feature-based alignment (FBA), a general method for efficient and robust model-to-image alignment. Volumetric images, e.g. CT scans of the human body, are modeled probabilistically as a collage of 3D scale-invariant image features within a normalized reference space. Features are incorporated as a latent random variable and marginalized out in computing a maximum a-posteriori alignment solution. The model is learned from features extracted in pre-aligned training images, then fit to features extracted from a new image to identify a globally optimal locally linear alignment solution. Novel techniques are presented for determining local feature orientation and efficiently encoding feature intensity in 3D. Experiments involving difficult magnetic resonance (MR) images of the human brain demonstrate FBA achieves alignment accuracy similar to widely-used registration methods, while requiring a fraction of the memory and computation resources and offering a more robust, globally optimal solution. Experiments on CT human body scans demonstrate FBA as an effective system for automatic human body alignment where other alignment methods break down. <s> BIB044
The first step in geometric registration is to detect points of interest. Images that contain sufficient details facilitate point detection. Medical images are not as rich in details as natural images BIB009 . That is why, point detection has mainly drawn the interest of the computer vision community. Landmark extraction has been studied more in the case of images and less in the case of images. Before continuing, let us refer the interested reader to a recent book by Goshtasby BIB043 where point-detectors and descriptors are more extensively studied. The detection and the matching of points of interest are inherently coupled with the way the landmarks are described. The richness of the description is important in order to detect salient points and better disambiguate between close potential candidates during matching. Moreover, as the imaged objects undergo deformations, the appearance of the points of interest will vary between images. Therefore, descriptors should be invariant to such changes in order to allow robust detection and matching under deformations. A detailed overview of the point detectors that have been proposed in the computer vision literature is out of the scope of this review. Nonetheless, let us give a brief description of some important key-point detector methods. Harris et al. proposed to identify corners by exploiting the information conveyed by the structure tensor BIB001 . Specifically, points of interest are determined by considering the following quantity: . In similar lines, Shi and Tomasi BIB002 proposed to use the minimal eigenvalue of the structure tensor in order to track points of interest. Many extensions to the Harris detector have been proposed in the literature. Their main aim was to impose a certain invariance. One may cite the approach proposed by Triggs BIB011 and affine-invariant Harris and Hessian BIB012 . Affine invariance is important as it enables the detection of points under affine transformations and a lot of efforts have been concentrated in defining such detectors. An evaluation study comparing the most important affine invariant detectors was presented by Mikolajczyk et al. BIB018 . For review of point detection methods, the interested reader is referred to the works of Schmid et al. BIB013 and Triggs BIB011 . Evaluation studies of point and corner detectors have been performed by Schmid et al. BIB013 and Mokhtarian and Mohanna BIB019 . An alternative way to determine point of interests is by performing scale-space analysis and detecting blob-like regions. The use of the Laplacian of Gaussian has been investigated to perform this task. The image is convolved with different scales of a Gaussian kernel and at each level the Laplacian operator is applied. Lindeberg proposed to track across scales the local maxima/minima of the response of the Laplacian operator in order to detect key-points BIB014 . Kadir and Brady BIB015 proposed a multiscale approach for the detection of salient regions. The algorithm was based on the use of local entropy to quantify saliency. Matas et al. proposed a technique for blob detection BIB016 . A multiscale representation of image regions was created by thresholding for different values in the intensity domain. These regions were tracked and selected based on their area's stability to change of the threshold value. Lowe BIB039 proposed to use the Difference of Gaussians, that is an approximation of the Laplacian, to create a scale-space representation. Feature points were detected by extracting the local minima/maxima of the this scale-space representation. The local Hessian information was used to reject spurious points. Lowe's scale invariant feature transform (SIFT) algorithm to describe key-points was based on the gradient information at the scale a point of interest was detected. For every pixel in a neighborhood of the key-point the gradient magnitude was computed. Its value was weighted depending on its distance from the key-point. From these values, gradient orientation histograms were computed and normalized to account for photometric variations. Many variants of SIFT have been proposed. Ke and Sukthankar proposed PCA-SIFT BIB017 where the gradient image of the local patch is projected to lower dimensional space constructed by principal component analysis (PCA). Mikolajczyk and Schmid proposed the use of gradient location and orientation histogram (GLOH) BIB020 . The authors proposed to use a log-polar pattern for the spatial sampling and PCA to decrease the dimensionality of the descriptor. Bay et al. BIB026 proposed the speeded-up robust features (SURF) that are based on the application of the Haar wavelet in the region of the point of the interest. Morel and Guoshen proposed an affine invariant version of SIFT BIB032 . Invariance was introduced by simulating the latitude and longitude angles. For a comparison between the original SIFT and its variants see  . For a comparison of the performance of different feature descriptors, the interested reader is referred to BIB020 , BIB033 . The development of such generic approaches to extract points of interest is less investigated in medical image analysis. Nonetheless, a number of extensions of SIFT in higher dimensions have been proposed. Cheung and Hamarneh extended SIFT in the domain  and reported results for the and case. Ni et al. also presented an extension of SIFT to the image domain BIB027 . These approaches ignored the tilt-orientation information. Allaire et al. BIB028 proposed another extension of SIFT in the domain that is fully orientation invariant. The authors proposed to create an additional histogram to determine the tilt angle. Flitton et al.  proposed the use of a tilt histogram for the full definition of the orientation when extending SIFT in the domain. Cheung and Hamarneh  validated their extension of SIFT by matching landmarks between MR images and CT images. Ni et al. used SIFT to ultrasound volume stitching toward panorama creation BIB027 . Allaire et al. used SIFT to register planning CT data to cone bean CT data BIB028 . Niemeijer et al. used matched SIFT points in order to tackle rigid registration between optical coherence tomography (OCT) images BIB034 . Han extended the SURF descriptor BIB026 to and used it in a hybrid registration framework  . Yang et al. used salient the scale invariant features BIB015 to tackle geometric registration that infers both the correspondence and the spatial transformation BIB040 . Toews and Wells used scale invariant features for rigid model-to-image registration BIB044 . We are going to discuss in more detail these methods in the section that is more related to each one of them. To the best of our knowledge, feature detection in medical image analysis is performed in a task specific manner, usually as product of a segmentation preprocessing step. Pennec et al. extracted points and lines in surfaces through the use of differential geometry for rigid brain registration BIB004 . In brain image registration, sulci information has been used in BIB029 , BIB005 - BIB007 . The cortical surface information has also served as feature in BIB007 - BIB024 . Retina image registration is another application where extracting geometric cues has been investigated. The intensities in the nonvascular part of the image are homogeneous, while important information is conveyed by the vasculature. Can et al. used the branching and crossover points of the blood vessel structure as feature points BIB008 . Stewart et al. additionally used the centerlines of the segmented vasculature BIB010 . For each centerline point, its location, tangent direction and width were retained. Vascular structures are also important in brain sift correction BIB025 , pulmonary CT images BIB041 and liver registration BIB037 . That is why a number of task-tailored detectors have been devised BIB003 - BIB023 . Lastly, fiducial markers are also used to guide image registration. Some resent studies regarding the errors in the process are given in BIB006 - BIB035 . 2) Methods That Infer Only the Correspondences: Methods that belong to this class aim to solve only the correspondence problem. In other words, these methods aim to assign every point to its corresponding point . Establishing solely correspondences can be useful when they are used in combination with an interpolation-based transformation model to estimate dense displacements between the two images. Hybrid registration (see Section III-C) is another case where such methods are of interest. One uses the sparse geometric correspondences along with an iconic criterion to improve the estimation of the spatial transformation. Having established a discriminative and ideally deformation invariant description of the key-points, correspondences may be established either by 1) relying solely on the closeness of the descriptions, or 2) by incorporating structural constraints. For a different classification as well as the presentation of some earlier works in the field, the interested reader is referred to  . a) Matching by Descriptor Distance: In the first case, the information contained by the descriptor is used to determine the correspondences. There is an implicit assumption that the descriptors are constructed so that the use of the Euclidean distance is sufficient to rank potential matches. This construction can be achieved by appropriate rescaling of the feature vector values. Based on an established ranking, different matching strategies may be considered. The simplest strategy is thresholding; points that exhibit a similarity higher than a threshold are matched. The definition of the threshold can be achieved by studying the receiver operating characteristic (ROC) curve. A different strategy is to assign each point to its closest candidate. Closeness is defined based on the Euclidean distance in the descriptor space. As the probability of detecting a false positive is significant, a threshold is still needed to control it. The third strategy is to take into account the ratio between the distance with the nearest and the second nearest neighbor in the feature space. For an evaluation of these strategies, the interested reader is referred to BIB020 . A fourth strategy consists of verifying the uniqueness of the matching by evaluating the third criterion in both the forward and backward direction  , BIB034 ,  . A point is matched to if and only if is the best match for , and is the best match for . While being intuitive and efficient, these matching approaches discard any information regarding the spatial location of the key-points in the image. The incorporation of such knowledge aims to better constrain the matching problem and further reduce the number of erroneous correspondences. b) Matching Through Geometric Constraints: A popular way to introduce structural constraints is by formulating the problem as graph matching. Leordeanu and Hebert BIB021 proposed a spectral technique to solve the matching problem. Pairwise constraints were used to preserve pairwise geometry. Berg et al. BIB022 formulated the problem of recovering feature correspondences as an integer quadratic programming problem. Changes in the length and the direction of vectors defined by pairs of features were penalized. Torresani et al. also employed pairwise constraints to model local spatial coherence BIB030 . Moreover, the authors showed that is possible to handle outliers during the optimization. Despite the success pairwise constraints have had in many applications, they are limited with respect to the relations they can model. Recently, a number of researchers have tried to tackle the graph matching problem with higher order constraints. Duchenne et al. BIB036 generalized the spectral matching method BIB021 to higher order constraints. A tensor power iteration method was employed to solve the matching problem. Zass and Shashua in BIB031 proposed a similar formulation, while using a different optimization method. Wang et al. BIB038 proposed a higher-order graph matching formulation that incorporates learned structural constraints in a segmentation framework. The inference was performed by a dual decomposition based method BIB042 .