Kappi Patterson (kp6)

Visualisation of results.

Part 1- Interest Point Detection

For this part I determined created filters to take derivatives of the input image. I used sobel filters: [1,0,-1;2,0,-2;1,0,-1], in order to find the x derivative and y derivative of each pixel in the image.

I then blurred the square of each image using a gaussian filter to obtain stronger and less noisy results.

The next step was to calculate where in these composed images of derivatives both eigenvalues were strong, for this I used the formula: (Ximage.*Yimage - XYimage.^2) - alpha*(Ximage + Yimage).^2 , where alpah = 0.06.

Now I had an image composed of interest points, which I filtered through again using a threshold of: averageHarrisNumber + 0.1*stdDev, where averageHarrisNumber was the average of the interst points matix and stdDev was the Standard Deviation of it. I filtered by removing any points that did not meet the threshold, thus retaining only the stronger values.

The final step was to apply non-maxima suppression. For this I used the colfilt function to slide over 5x5 windows and discard everything but the local maxima. Finally I added the remaining points to an X array and a Y array in order to return the coordinates of interest points.

Part 2 - Building Feature Descriptors

For part 2 I had to build descriptors around each of my chosen interest points, in order to have a method of comparison for the final stage. I chose to build my descriptors by computing the gradient of each pixel within a 'feature width' size block around the pre-computed interest point. I blurred the images to gain a more general area to test on. The amount of Gaussian blue here varied my results greatly, and the filter fspecial('gaussian',max(1,fix(120)), 2), which I was advised to use by a web blog on SIFT implementation, provided the best results (took my accuracy from 81% to 89%). I then used the gradient to compute it's direction. I then added each pixel within a sub-matrix of the block to a bucket, depending on it's direction (buckets corresponding to 8 basic cardinal directions). Each pixel's gradient was added to the bucket as the value so as to acheive better weighting. Initally I just added 1 unit to each bucket (using the histogram feature of matlab), but when I weighted the buckets I gained an accuracy of about 15%. The 16 buckets I computed from the original feature point block were then concatenated together to form a 1*128 vector to act as the descriptor for the interest point. This descriptor was then normalized and added to a return array of all computed descriptors.

Part 2 - Matching Features

Part 3 took in computed descriptors from 2 different images and compared them, in order to decide which matched. There were two filtering processes involved in this step to ensure the best matches being made. First, each descriptor was compared to every descriptor in the other image. At first I calculated the Euclidean distance but the results were not a good as when I simply took the abolute value of the the scalar difference. This made my algorith improve by around 10%. As this was being done, I kept track of the two most similar decriptors to the current one. At the end of the loop I compared the difference between the descriptor in question and it's most similar counterart in the other image with the difference between it and it's second most similar counterpart in the other image. If this ratio was higher than 0.65, I determined that the point was too similar to a number of points in the other image and it wasn't likely to make a good match. Once removing points with bad ratios, I sorted the list of matches by their ratios that I computed above. I then return the top 100 with the smallest ratios, ie the ones that were the most distinct matches.

Examples of the algorithm working on various images