1 Abstract—An efficient image identification algorithm was implemented in MATLAB to extract scale invariant features from a given set of images. Our algorithm is based on Lowe’s approach to extract distinctive image features from scale-invariant key-points. The extracted features are highly distinctive as they are based on local gradient properties of scale-space images and are well localized in spatial and frequency domains. The extracted features are partially invariant to illumination and affine transformations hence suitable for matching differing images of same object. The cost of extracting these features is minimized by taking a cascading approach in which computationally intensive operations are applied only to set of sample points which pass an initial test. Index Terms—scale-space extrema detection, Keypoint localization, orientation assignment, keypoint descriptor I. INTRODUCTION URING the past two decades, the topic of Image identification by using a set of local interest points has led to many interesting works by Moraves(1981), Harris(1992), Mohr(1997), Lowe(1999) and others. The ground breaking work of Mohr showed that local invariant feature matching can be extended to general image recognition problems in which a feature is matched against a large database of images. It used rotationally invariant descriptor of local image regions like Harris corner to select points of interest. As the Harris corner detector is very sensitive to changes in image scale, it does not provide a good basis for matching images of different sizes. Later on, Lowe extended the local feature approach to achieve scale invariance. Our work provides an efficient implementation of Lowe’s approach to extract local descriptor features of an image which are scale invariant and affine invariant to considerable range. For efficient detection of key points, a cascade filtering approach is used in which computationally Manuscript submitted June 2nd, 2007. This paper details the implementation of an image processing algorithm to extract Scale Invariant Featues (SIFT) of an image. The work was done as a ‘Class Project’ for the Course EE368 – Digital Image Processing under the guidance of Prof. Bernd Girod during Spring, 2007 at Stanford University. Vikram Srivastava is a first year graduate student at the Department of Electrical Engineering, Stanford University (email: [email protected]) Prashant Goyal is a first year graduate student at the Department of Electrical Engineering, Stanford University (email: [email protected]) intensive operations are applied only to those sample points which pass an initial test. Following are the major steps of our cascading approach to generate the set of image features. 1. Scale Space Extrema Detection 2. Key-point Localization 3. Orientation assignment of key-points 4. Calculation of Descriptor vector of key-points We first extract these SIFT features for a set of given reference images and store them in a database. For a given input image, we first extract its SIFT features and compare them with our database to find the best match based on a nearest neighbor approach. This paper describes the implementation of Lowe’s approach [1] to develop a technique to recognize paintings on display in Cantor arts center based on snapshots taken with a camera-phone. A detailed explanation of our algorithm is provided in Section II. Section III provides a brief explanation of our earlier approach based on Histogram matching of color space. Section IV details the results achieved with our final algorithm. Finally concluding remarks are presented in Section V. II. IMAGE FEATURES EXTRACTION The steps of our Feature extraction algorithm are described below: 1) Detection of scale-space extrema The first step in identifying keypoints is to identify locations that are invariant to scale change and differing views of same object. Such an scale-space of an image can be created by convolving the image I(x,y) with a variable scale Gaussian(,, )Gxyσ. (,, ) (,, )*(, )Lxy Gxy Ixyσσ= (1) To efficiently detect stable key-points difference of Gaussians are calculated by simple image subtraction of two nearby scales separated by a constant multiplicative factor k. (, , ) (, , ) (,, )DoG x y L x y k L x yσσσ=− (2) In our algorithm first octaves of scale space are created by convolving the input image with Gaussians. Each octave corresponds to a doubling of σ and divided into an integer An Efficient Image Identification Algorithm using Scale Invariant Feature Detection Vikram Srivastava and Prashant Goyal D2number of s of intervals. The value of multiplicative factor k is chosen to be 1/2s. Subsequent octaves are created by down-sampling the Gaussian image that has twice the initial value of σ and process repeated. For each octave s+3 gaussian blurred images are produced and maxima/minima of DoG images are detected by comparing a pixel to its 26 neighbours in a 3*3 region at the current and adjacent scales. Hence, for an octave with a scale s, we need to produce s+2 DoG’s in that octave and therefore, s+3 gaussian blurred images. To maximize the key-point repeatability, the value of s is chosen to be 3 as shown in Lowe’s paper. Although keypoint repeatability increases with large value of σ, a large value of σincreases computational cost as window size increases(3*σ). Therefore, a value of σ= 1.6 is chosen for optimal repeatability. Finally local extrema of DoG images are calculated by comparing each sample point to its 8 neighbors in current scale and 9 neighbors in the scale above and below. The cost of this check is reasonable as most sample points will be eliminated during this check. 2) Key-point Localization This stage attempts to eliminate more points from the above identified list of key-points by finding those that have low contrast or are poorly aligned on edges. This is done by first finding the interpolated locations of extrema by using Taylor series expansion of scale-space function. 2211() ( )22TTDDDx D x x xxx∂∂=+ +∂∂ (3) where D and its derivative are evaluated at the sample point and (,, )Txxyσ= is the offset from the point. The location of the extremum is defined by taking the derivative of the function with respect to x and setting it to zero. The location of the extremum is given by, X = 212()DDxx−∂∂∂∂