C05.3 - Correspondance Estimation Clarification and SIFT

• patch descriptors

  • -> i.e. patch of intensity values

  • needs to be warped into canonical space

• census descriptor

  • a vector with integer/float values

• trying to find the correct scale between two patches to compare

• -> brute force try SSD for all (patch1) x (patch2 x scales) cobinations

• inefficient

• -> O(N^2S)

  • where N are the features per image

  • and S is the number of scales to try (i.e. we only try diff. scales in one image)

• as we fix scale of left patch

  • -> cannot guarantee that it is optimal (distinctive enough)

• general: assume that we know the scale beforehand (a priori)

  • -> only O(N^2)…

• gial: automatically determine scale before matching (independent of it) before we actually match

  • => i.e. determine scale based on single image

    
    

• we want to automatically find a scale (size)

• for both images individually

• => i.e. independent of tentative matching unlike before

• harris descriptor

• use gradients vector

• use harris detector as it is rotation invariant

• -> as eigenvalues of M matrix correspond to diretoins of quickest and slowest changes of SSD

• => eigenvalues form an ellipse that can rotate, but shaoe stays the same

• => easy to assign rotation…

1. compute gradients vector at each pixel within a patch

2. build histogram of gradient orientations (0-2pi) weighted by gradient magnitude (norm of vector)

3. using this information -> extract local maxima above certain threshold

   1. => constitute a candidate dominant directoin (typically 3)

4. use these dominant directions to align the rotatoin for both patches

• the one based on gradient orientations

• -> more robust

• given single image

• -> detect blobs and automatically assign them “appropriate” scales

• blobs inherently encode scale informaiton

  • -> corner can hardly do this..

• => blobs can directly be resized to evaluate two pacthed by SSD

• radius of the circle that denotes scale

• for two matched blobs

• -> their respectve centers constitute the corresponding points

• blob centers may not be very precise

• compared with corners

• make use of LoG (laplacian of gaussians)

  • -> defined for fixed scale sima

  • try set of candidate scales sigma for which we compute LoG (applying kernel)

• the LoG corresponds to the so called “response”

• -> find the sigma where the response is maxium

• => this is our optimal scale

• disregard too close patches with same scale

• -> as are probably the same…

• overlapping: centers are close, sigma is the same

• => use Non maximum suppresion

• => only keep the blob wiht higher response (i.e. LoG extrema)

1. build laplacian space, starting with an iinitial scale and go for n interations

   1. generate a (scale-normalized) LoG filter at a given scale (k^n*initial)

   2. filter image with LoG kernel

   3. save square of laplacian filter response for current level of scale space

   4. increase scale by factor k

2. perform non-maximum suppresion in scale space (-> find best scale for each blob)

3. display resulting circles at their characteristic scales

• bruteforce matching with straightforward scale search (one-step method)

  • S*N^2

• bruteforce matching with automatic scale search (two step method)

  • N*S + N*S + N^2

• if warping not estimated accurately

  • -> very small errors in rotaiton, scale, viewpoint will affect matching score based on SSD

• LoG is relative inefficient

  
  

• census descriptor based methodd

• in census descriptor based methods

• -> we do not directly compare patches with SSD

• -> but compare associated vector descriptors

  • -> less sensitive to noise

=> i.e. use vector to describe patch instead of pixel-wise SSD

• use the difference of gaussian DoG kernel

• scale invariant feature transform

1. key point extraction based on extreme detection using DoG (instead of LoG)

2. census descriptor assignment by HoG

• LoG -> use kernel

• DoG -> approximates LoG without using convolution

• -> uses diffference of gaussian blurs at different scales

• we have source image

• compute several gaussian blurs of it (with different StdDev)

  • sigma = 1; sigma = 2, …

• calcualte difference between adjacent blurred images

• => result in DoG images

=> do this for different scales of the image (so called ocatves)

• detect local extrema in these DoG images

• the SIFT key points

• each pixel is compared to 26 neighbors

  • 8 around it (neighbors in current image)

  • 9 above it (adjacent upper scale)

  • 9 below it (adjacent lower scale)

  • -> i.e. like a surronding cube in the DoG pyramid)

• if pixel is local extrema -> select as SIFT feature

• location (x,y) (pixel that is lcoal extrema)

• scale s (scale in pyramid at which local extrema resides

• histogram of oriented gradients (HOG) descriptor

• input: de-rotated patch

• divide pacth into 4x4 cels

• for each cell: generate 8-bin histogram (i.e. 8 directions)

• => concatenate all histograms into single 1D vector

• 4 (cells) x 4(cells) x 8 (bins) = 128

• location (-> pixel coords of center of patch): 2D vector

• scale (-> high scale -> high blur in gauss pyramid..): 1 scalar value

• orientation (-> dominant direction of HoG): 1 scalar value (i.e. angle of patch)

• Descriptor (128 values …)

• dominant direction:

  • pixel level

  • use HoG to find out how to de-rotate

• descriptor generation:

  • already de-rotated

  • then use for cell-level descriptor generation