Project 2: Local Feature Matching

In this project, I need to implement the three major steps of a local feature matching algorithm.

  1. Interest point detection in get_interest_points.m
  2. Local feature description in get_features.m
  3. Feature Matching in match_features.m

Interest point detection

In interest point detection, I basicly accord to the algorithm to detect interest points.

  1. At first, I computed the horizontal and vertical derivatives of the image Ix and Iy. Actually, the book suggests us to convolve the orginal image with derivatives of Gaussians but it will result few interest points shown in my assignment. In order to get more interest points to detect, I deceided to use a [-2 -1 0 1 2] filter as orginal "Harris" detecor algorithm in this step to satisfy the 100 matches. Also, I suppress the edge pixels in this step.
  2. Secondly, I computed the three images corresponding to the outer products of these gradients for matrix A - Ix2, Iy2, Ixy and convolved each of the images with a 3x3 Gaussian.
  3. Thirdly, I computed a scalar interest measure using Harris Corner Algorithm
  4. In the end, I find local maxima above a certain threshold and report them as detected feature point locations. The method I used is to transfer image to binary image and find connected components in thresholded binary image. Then, I can find local maxima and mark it to be one interest point.

Code with highlighting


%get the derivatives of x and y.
	[Ix, Iy] = imgradientxy(image); 

%Three images corresponding to the outer products of these gradients for matrix A
	gaussian = fspecial('Gaussian',[3 3], 1);          
	Ix2 = imfilter(Ix.^2, gaussian);
	Iy2 = imfilter(Iy.^2, gaussian);
	Ixy = imfilter(Ix.*Iy,gaussian);

%formula of harris corner detection
	har = Ix2.*Iy2 - Ixy.*2 - alpha*((Ix2+Iy2).^2);   

%connected components in thresholded binary image
	cc = bwconncomp(im2bw(har, graythresh(har))); 

%find local maxima in binary image and mark it to be interest point
	for i=1:cc.NumObjects
		a = cc.PixelIdxList{i};
		[~, indices] = max(har(a));                    
		[y(i), x(i)] = ind2sub(size(har), a(indices));
	end

Local feature description


In local feature description, I used Scale invariant feature transform(SIFT). As the leature slides or book suggest, I computed the gradient at each pixel in a 16x16 window around the detected keypoint by Gaussian pyramid at the location the keypoint was detected. Then I divided it to 4x4 quadrant and each quadrant has 8 vectors. After that, I formed it to be a histogram with 8 histogram bins and each of histogram bin represent the sum of weighted gradient values. In the end, I reshaped them to 128 vectors and normalized them to be a valid feature.

Code with highlighting


%16*16 window around interest point
	for i = 1 : length(x)
        subwindow = image(y(i) - 8:y(i)+7, x(i)-8 : x(i) + 7);
%get mag and dir of window
	[gmag, gdir] = imgradient(subwindow);   
%weigh mag with gaussian	
	Gmag = imfilter(gmag, fspecial('Gaussian')); 

%divide cell to 4*4
	angle_binranges = -180:45:180;	

%convet c to histogram 	
    for j = 1:size(gdir_c,1)                                               
        c = gdir_c(:, j); 
        [~, indices] = histc(c, angle_binranges);                          
        sum_hist = zeros(1,8); 
%sum of each histogram bins		
		for k = 1:length(indices)
            sum_hist(indices(k)) = sum_hist(indices(k)) + gmag_c(k,j);
        end	
%normalize descriptor
    D = D /norm(D);                                                          
    features(i, :) = D; 
%values are clipped to 0.2
	features = features.^0.8;

Feature Matching


In feature matching, I computed the euclidean distance from features in images1 to features in image2. And then I computed the ratio of d1 and d2 which means the two shortest distance from feature1 to all feature2. In the end, I set a threshold to 0.8 to be a good feature matching.

Results

In this section, I used orginal Harris Corner Detection and 0.8 threshold which result 116 correct points and 17 incorrect points with 87% accuracy.

In this section, I used small and larger gaussian and 0.7 threshold which result 40 correct points and 3 incorrect points with 93% accuracy.

In this section, I used orginal Harris Corner Detection and 0.8 threshold which result 138 correct points and 14 incorrect points with 91% accuracy.

In this section, I used small and larger gaussian and 0.7 threshold which result 26 correct points and 2 incorrect points with 93% accuracy.

Observations

In this project, I used the orginal harris corner detection to fit the reqirement of 100 feature matching and 80% accuracy. However, it can be much more accurate using lower threshold and small and large gaussian filter but with lower interest point. Furthermore, I want to find another method to detect more interest points with high accuracy. In addition, this project is a basic detection project but it can be learned much more and help me a lot in future projects such as edge detecion and sports tracking in vedio.