Scale-Invariant Feature Transfrom

  This is a MATLAB/C implementation of the SIFT detector and
  descriptor [1]. You can:

  * Use SIFT() to detect the SIFT frames (keypoints) of a given image
    and compute their descriptors. Then you can use SIFTMATCH() to
    match the descriptors.

  * Use PLOTSS(), PLOTSIFTDESCRIPTOR(), PLOTSIFTFRAME(),
    PLOTMATCHES() to visualize the results.

  As SIFT is implemented by several reusable M and MEX files, you can
  also run portions of the algorithm. Specifically, you can:

  * Use SIFTDESCRIPTOR() to compute the SIFT descriptor from a list
    of frames and a scale space or plain image.

  * Use GAUSSIANSS() and DIFFSS() to compute the Gaussian and DOG
    scale spaces.

  * Use SIFTLOCALMAX(), SIFTREFINEMX(), SIFTORMX() to manually
    extract the SIFT frames from the DOG scale space. More in
    general, you can use SIFTLOCALMAX() to find maximizers of any
    multi-dimensional arrays.

  REFERENCES

  [1] D. G. Lowe, "Distinctive image features from scale-invariant
      keypoints," IJCV, vol. 2, no. 60, pp. 91 110, 2004.

  See also PDF:SIFT.INTRODUCTION.

      

   DSS=DIFFSS(SS) returns a scale space DSS obtained by subtracting
   consecutive levels of the scale space SS.

   In SIFT, this function is used to compute the difference of
   Gaussian scale space from the Gaussian scale space of an image.

   See also GAUSSIANSS(), PDF:SIFT.USER.SS.

      

   SS = GAUSSIANSS(I,SIGMAN,O,S,OMIN,SMIN,SMAX,SIGMA0) returns the
   Gaussian scale space of image I. Image I is assumed to be
   pre-smoothed at level SIGMAN. O,S,OMIN,SMIN,SMAX,SIGMA0 are the
   parameters of the scale space as explained in PDF:SIFT.USER.SS.

   See also DIFFSS(), PDF:SIFT.USER.SS.

      

   I=IMREADBW(FILE) reads the image FILE and converts the result to a
   gray scale image (with DOUBLE storage class anr range normalized
   in [0,1]).

      

   PLOTMATCHES(I1,I2,P1,P2,MATCHES) plots the two images I1 and I2
   and lines connecting the frames (keypoints) P1 and P2 as specified
   by MATCHES.

   P1 and P2 specify two sets of frames, one per column. The first
   two elements of each column specify the X,Y coordinates of the
   corresponding frame. Any other element is ignored.

   MATCHES specifies a set of matches, one per column. The two
   elementes of each column are two indexes in the sets P1 and P2
   respectively.

   The images I1 and I2 might be either both grayscale or both color
   and must have DOUBLE storage class. If they are color the range
   must be normalized in [0,1].

   The function accepts the following option-value pairs:

   'Stacking' ['h']
      Stacking of images: horizontal ['h'], vertical ['v'], diagonal
      ['h'], overlap ['o']

   'Interactive' [0]
      If set to 1, starts the interactive session. In this mode the
      program lets the user browse the matches by moving the mouse:
      Click to select and highlight a match; press any key to end.
      If set to a value greater than 1, the feature matches are not
      drawn at all (useful for cluttered scenes).

   See also PLOTSIFTDESCRIPTOR(), PLOTSIFTFRAME(), PLOTSS().

      

   PLOTSIFTDESCRIPTOR(D) plots the SIFT descriptors D, stored as
   columns of the matrix D. D has the same format used by SIFT().

   PLOTSIFTDESCRIPTOR(D,F) plots the SIFT descriptors warped to the
   SIFT frames F, specified as columns of the matrix F. F has
   the same format used by SIFT().

   H=PLOTSIFTDESCRIPTOR(...) returns the handle H to the line drawing
   representing the descriptors.

   REMARK. Currently the function supports only descriptors with 4x4
   spatial bins and 8 orientation bins (Lowe's default.)

   See also PLOTSIFTFRAME(), PLOTMATCHES(), PLOTSS().

      

   H=PLOTSIFTFRAME(FRAMES) plots the SIFT frames FRAMES and returns
   and handle H to the resulting line set. FRAMES has the same format
   used by SIFT().

   A SIFT frame is denoted by a circle, representing its support, and
   one of its radii, representing its orientation. The support is a
   disk with radius equal to six times the scale SIGMA of the
   frame. If the standard parameters are used for the detector, this
   corresponds to four times the standard deviation of the Gaussian
   window that has been uses to estimate the orientation, which is in
   fact equal to 1.5 times the scale SIGMA.

   Option-value pairs
   
   'Labels' []
     Specify a cell-array of labels, one for each keypoint. These
     will be drawn close to the keypoint centers.

   'Style' ['circle']
     Plot style: circles ('circle'),  arrows ('arrow')

   This function is considerably more efficient if called once on a
   whole set of frames as opposed to multiple times, one for each
   frame.

   See also PLOTMATCHES(), PLOTSIFTDESCRIPTOR(), PLOTSS().

      

   PLOTSS(SS) plots all octaves of the scale space SS.

   See also GAUSSIANSS(), DIFFSS().

      

   [FRAMES,DESCR]=SIFT(I) extracts the SIFT frames FRAMES and their
   descriptors DESCR from the image I.

   The image I must be gray-scale, of storage class DOUBLE and
   ranging in [0,1].

   FRAMES is a 4xK matrix storing one SIFT frame per column. Its
   format is:

     FRAMES(1:2,k)  center (X,Y) of the frame k,
     FRAMES(3,k)    scale SIGMA of the frame k,
     FRAMES(4,k)    orientation THETA of the frame k.

   DESCR is a DxK matrix stores one descriptor per columm (usually
   D=128).

   [FRAMES,DESCR,GSS,DOGSS]=SIFT(...) returns the Gaussian and
   Difference of Gaussians scale spaces computed by the algorithm.

   The function accepts the following option-value pairs:

   Verbosity - Verbosity level [{0},1]
     0 = quiet, 1 = print detailed progress report

   BoundaryPoint - Remove frames on the image boundaries [0,{1}]
     Remove points whose descriptor intersects the boundary.

   NumOctaves - Number of octaves [1,2,...]
     Number of octaves of the Gaussian scale space. By default it is
     computed to cover all possible feature sizes.

   FirstOctave - Index of the first octave [...,-1,{0},+1,...]
     Setting the parameter to -1 has the effect of doubling the image
     before computing the scale space.

   NumLevels - [1,2,...]
     Number of scale levels within each octave.

   Sigma0 - Base smoothing [pixels]
     Smoothing of the level 0 of octave 0 of the scale space. By
     default it is set to be equivalent to the value 1.6 of [1].
     Since however 1.6 is the smoothing of the level -1 and Simga0
     of the level 0, the actual value is NOT 1.6.

   SigmaN - Nominal smoothing [pixels, {0.5}]
     Nominal smoothing of the input image.

   Threshold - Strenght threshold [>= 0, {0.01}]
     Maxima of the DOG scale space [1] below this threshold are
     ignored. Smaller values accept more features.

   EdgeThreshold - Localization threshold [>= 0, {10}]
     Feature which have flattness score [1] above this threshold are
     ignored. Bigger values accept more features.

   Magnif - Descriptor window magnification
     See SIFTDESCRIPTOR().

   NumSpatialBins - Number of spatial bins [2,{4},6,...]
     See SIFTDESCRIPTOR().

   NumOrientbins - Number of orientation bins [1,2,...,{8},...]
     See SIFTDESCRIPTOR().

  REFERENCES
  [1] D. G. Lowe, "Distinctive image features from scale-invariant
      keypoints," IJCV, vol. 2, no. 60, pp. 91 110, 2004.

   See also GAUSSIANSS(), DIFFSS(), PLOTSIFTFRAME(), PLOTSIFTDESCRIPTOR(),
            SIFTDESCRIPTOR(), SIFTMATCH().


      

   Compiling under Windows requires at least Visual C 6 or LCC. You
   might try other compilers, but most likely you will need to edit
   this file.

      

   This demo computes the SIFT descriptor on a pair of well known
   test images.

   See also SIFT_DEMO2().

      

   This is similar to SIFT_DEMO().

   See also SIFT_DEMO().

      

   This compares our and D. Lowe's implementation. Not perfect,
   but close.

      

   This compares our and D. Lowe's implementation. Not perfect,
   but close.

      

   Finding eggs.

      

   Using custom keypoints.

      

   DESCR = SIFTDESCRIPTOR(G, P, SIGMA0, S, MINS) returns the SIFT
   descriptors DESCR of the SIFT frames P defined on the octave G of
   the Gaussian scale space. SIGMA0, S and MINS are the the parameter
   of the scale space as explained in PDF:SIFT.USER.SS. P has one
   column per frame, specifiying the center X1,X2, the scale index s
   and the orientation THETA of the frame in this order. Note that:

   - The functions operates on a single octave G of the scale
     space. In order to process frames spanning more than one
     octave the function must be called multiple times

   - The scale of a SIFT frame is given by SIGMA(s,o) = SIGMA0
     2^(o+s/S) where o is the octave index and s is the scale
     index. Since SIFTDESCRIPTOR() operates on a specific octave G, P
     contains the scale index s rather than the scale SIGMA.

   DESCR = SIFTDESCRIPTOR(I, P, SIGMA) operates on a plain image I
   which is assumed to be pre-smoothed at scale SIGMA. In this case P
   specifies X1,X2 and the orientation THETA (but NOT the scale
   index). Note that:

   - SIGMA is the scale and not the scale index.

   - While the Gaussian scale space octaves are downsampled, I is
     not.

   Other parameters can be specfied as option-value paris. These
   are:

   'Magnif' [3.0]
      Frame magnification factor. Each spatial bin of the SIFT
      histogram has an exentsion equal to magnif * sigma, where
      magnif is the frame magnification factor and sigma is the scale
      of the frame.

   'NumSpatialBins' [4]
      This parameter specifies the number of spatial bins in each
      spatial direction X1 and X2. It must be a positive and even
      number.

   'NumOrientBins' [8]
      This parameter specifies the number of orietnation bins. It
      must be a positive number.

   See also SIFT(), GAUSSIANSS(), DIFFSS(), SIFTLOCALMAX(), 
            PDF:SIFT.USER.DESCRIPTOR.

      

   SEL=SIFTLOCALMAX(F) returns the indexes of the local maximizers of
   the Q-dimensional array F.

   A local maximizer is an element whose value is greater than the
   value of all its neighbors.  The neighbors of an element i1...iQ
   are the subscripts j1...jQ such that iq-1 <= jq <= iq (excluding
   i1...iQ itself).  For example, if Q=1 the neighbors of an element
   are its predecessor and successor in the linear order; if Q=2, its
   neighbors are the elements immediately to its north, south, west,
   est, north-west, north-est, south-west and south-est
   (8-neighborhood).

   Points on the boundary of F are ignored (and never selected as
   local maximizers).

   SEL=SIFTLOCALMAX(F,THRESH) accepts an element as a mazimizer only
   if it is at least THRES greater than all its neighbors.

   SEL=SIFTLOCALMAX(F,THRESH,P) look for neighbors only in the first
   P dimensions of the Q-dimensional array F. This is useful to
   process F in ``slices''.

   REMARK.  Matrices (2-array) with a singleton dimension are
   interpreted as vectors (1-array). So for example SIFTLOCALMAX([0 1
   0]) and SIFTLOCALMAX([0 1 0]') both return 2 as an aswer. However,
   if [0 1 0] is to be interpreted as a 1x2 matrix, then the correct
   answer is the empty set, as all elements are on the boundary.
   Unfortunately MATLAB does not distinguish between vectors and
   2-matrices with a singleton dimension.  To forece the
   interpretation of all matrices as 2-arrays, use
   SIFTLOCALMAX(F,TRESH,2) (but note that in this case the result is
   always empty!).

      

   MATCHES=SIFTMATCH(DESCR1, DESCR2) matches the two sets of SIFT
   descriptors DESCR1 and DESCR2.

   The function uses the same algorithm suggested by D. Lowe [1] to
   reject matches that are too ambiguous.

   SIFTMATCH(DESCR1, DESCR2, THRESH) uses [1] with the specified
   threshold THRESH. A descriptor D1 is matched to a descriptor D2
   only if the distance d(D1,D2) multiplied by THRESH is not greather
   than the distance of D1 to all other descriptors. The default
   value of THRESH is 1.5.
   
   The storage class of the descriptors can be either DOUBLE, FLOAT,
   INT8 or UINT8. Usually interger classes are faster.
   
   [1] D. G. Lowe, 
       `Distinctive image features from scale-invariant keypoints,'
       IJCV, vol. 2, no. 60, pp. 91–110, 2004.

   See also SIFT(), SIFTDESCRIPTOR().

      

   [FRAMES, DESCRIPTORS] = READSIFT(FILE) reads the frames and the
   descriptors from the specified file. The function reads files
   produced by Lowe's SIFT implementation.
     
   FRAMES and DESCRIPTORS have the same format used by SIFT(). 

   REMARK. Lowe's and our implementations use a silightly different
   convention to store the orientation of the frame. When the file
   is read, the orientation is changed to match our convention.

   See also SIFT().

      

   Q = SIFTREFINEMX(P, OCTAVE, SMIN) refines, thresholds and performs
   the on-edge test for the SIFT frames P extracted from the DOG
   octave OCTAVE with parameter SMIN (see GAUSSIANSS()).

   Q = SIFTREFINEMX(P, OCTAVE, SMIN, THRESH, R) specifies custom
   values for the local maximum strength threshold THRESH and the
   local maximum peakedeness threshold R.

   OCTAVE is an octave of the Difference Of Gaussian scale space. P
   is a 3xK matrix specifying the indexes (X,Y,S) of the points of
   extremum of the octave OCTAVE. The spatial indexes X,Y are integer
   with base zero. The scale index S is integer with base SMIN and
   represents a scale sublevel in the specified octave.

   The function returns a matrix Q containing the refined keypoints.
   The matrix has the same format as P, except that the indexes are
   now fractional. The function drops the points that do not satisfy
   the strength and peakedness tests.

   See also SIFT().

      

   H = TIGHTSUBPLOT(K,P) returns an handle to the P-th axis in a
   regular grid of K axes. The K axes are numbered from left to right
   and from top to bottom.  The function operates similarly to
   SUBPLOT(), but by default it does not put any margin between axes.

   H = TIGHTSUBPLOT(M,N,P) retursn an handle to the P-th axes in a
   regular subdivision with M rows and N columns.

   The function accepts the following option-value pairs:

   'Spacing' [0]
     Set extra spacing between axes.  The space is added between the
     inner or outer boxes, depending on the setting below.

   'Box' ['inner'] (** ONLY >R14 **)
     If set to 'outer', the function displaces the axes by their
     outer box, thus protecting title and labels. Unfortunately
     MATLAB typically picks unnecessarily large insets, so that a bit
     of space is wasted in this case.  If set to 'inner', the
     function uses the inner box. This causes the instets of nearby
     axes to overlap, but it is very space conservative.

   REMARK. While SUBPLOT kills any pre-existing axes that overalps a
   new one, this function does not.

   See also SUBPLOT().