Interest points detection and description Pavel Cagaš 395960 Interest points •Points in an image suitable for subsequent processing •Points with interesting surrounding •Usually found in places with high contrast difference – edges, corners... •Useful for many computer vision applications: –Object detection –Object recognition –Motion analysis –... Interest points found in an image C:\Users\Pavel\Documents\BcWork\i2b952.png C:\Users\Pavel\Documents\BcWork\i2p952.png SURF – Speeded-Up Robust Feature •Method for detecting and desribing interest points in an image •Scale and rotation invariance •Four parts needed for understanding: –Scale-Space theory –Integral image –Interest point detection –Interest point description Scale-Space •Real world objects are relevant only in certain scale •Importance of internal representation •Object as a whole or detailed structure? •Need of representation in all scales •Finding a way of getting rid of some image detail •Frequency domain: • high frequency – detailed structure •Possible solution – Gaussian filter •Greater s parameter ® greater blurring ® detail suppression •Scale-Space layer: L(x,y,s) = G(x,y,s) * I(x,y) •Scale-Space pyramid •DoG rather than LoG •D(x,y,s) = L(x,y,ks) – L(x,y,s) C:\Users\Pavel\Documents\BcWork\sift-dog-idea.jpg C:\Users\Pavel\Documents\BcWork\scale space.png C:\Users\Pavel\Documents\BcWork\DoG.png Scale-space octaves Difference of Gaussians Integral image •Structure generated from the input image for computing sum of any rectangular area in constant time •Every pixel of integral image has value of sum of pixels in rectangular area of the input image defined by origin and given pixel C:\Users\Pavel\Documents\BcWork\IntegralImage1.png C:\Users\Pavel\Documents\BcWork\Integral image formula.jpg Interest point detection •Hessian matrix determinant based detection •Matrix of partial derivatives of function f • • • •The value of the determinant is used to clasify the results into local maxima or minima, based on second order derivative test C:\Users\Pavel\Documents\BcWork\Hessian0.png C:\Users\Pavel\Documents\BcWork\HessianMatrix.png •Conversion into discrete image domain: • • • •Where Lxx is convolution of given point with Gaussian second order derivative at point x, and similarly for others •Calculated for every point in am image C:\Users\Pavel\Documents\BcWork\Hessian.png C:\Users\Pavel\Documents\BcWork\GaussSecondDerivation.png Fast Hessian •Discretized and cropped Gaussian filters: • • • •Approximated Gaussian filters: • • • •Deviation correction: det(Happrox) = DxxDyy - (0,9*Dxy)2 C:\Users\Pavel\Documents\BcWork\Gaussian Kernel Real.jpg C:\Users\Pavel\Documents\BcWork\Gaussian Kernel Approximated.jpg Scale Invariance •In order to detect points on different scales, we increase the size of Box Filters rather than progressively blurring and sub-sampling the input image C:\Users\Pavel\Documents\BcWork\Gaussian Kernel Approximated Size.jpg C:\Users\Pavel\Documents\BcWork\generating scale.png C:\Users\Pavel\Documents\BcWork\SigmaApprox.png Interest point localization •Response map thresholding •Determining local maxima in • areal surronding of a point • - comparing each point with • 26 points in total of three • scales of the same octave • •Interpolating data into sub-pixel position • - Hessian determinant ® Taylor expansion up to quadratic terms C:\Users\Pavel\Documents\BcWork\scale.png C:\Users\Pavel\Documents\BcWork\Interpolation.png C:\Users\Pavel\Documents\BcWork\interpolation2.png Interest point description •Desriptor is a 64-dimensional vector used for describing each detected interest point •In order to keep rotation invariance, we need to determine each interest point orientation •Descriptor extraction is performed relative to this orientation Assigning orientation •Using Haar wavelets for x • and y direction •We calculate responses in • a circular area around the • interest point and weight it with Gaussian •All sizes relative to • Responses are represented as points in space with their own x and y value • • • C:\Users\Pavel\Documents\BcWork\Haar wavelet.jpg •Orientation vectors are calculated in a circular sector of p/3 rotating around the iterest point •Dominant orientation is determined as the greatest calculated vector C:\Users\Pavel\Documents\BcWork\DominantOrientation.png Descriptor extraction •Rectangular window around interest point is created •Haar wavelets in every of 16 subregions are calculated for 25 evenly distributed • sample points C:\Users\Pavel\Documents\BcWork\Descriptor.png C:\Users\Pavel\Documents\BcWork\subregionVector.png Thank you for attention Feel free to ask any question