Efficient scale-space extraction and description of interest points

Abstract

Method, system and computer program for efficiently extracting and describing scale-space interest points designed towards low overall computational complexity. On one hand, the data acquired during extraction in the description phase is intensively re-used. On the other hand, an algorithmic optimization of the description that dramatically speeds up the process, is proposed. First, the image is filtered with triangle kernel at different scales. The triangle filtered images are reused for extraction of the keypoints dominant orientation and the computation of the DAISY-like descriptor.

1 . A method being performed by a system, for keypoints scale-space extraction and description in an image, the method comprising the following steps:
 a) filtering the image with triangle kernel filters at different scales where the filters are 2D triangle shaped filters;   b) computing an approximation of a determinant of Hessian at each scale, where this approximation at each scale k, is calculated as |∂ k   xx (i, j)·∂ k   yy (i, j)−∂ k   xy (i, j) 2 | where
   ∂ xx   k   =L ( k,i−d   1   ,j )−2 ·L ( k,i,j )+ L ( k,i+d   1   ,j )
 
   ∂ yy   k   =L ( k,i,j−d   1 )−2 ·L ( k,i,j )+ L ( k,i,j+d   1 )
 
   ∂ xy   k   =L ( k,i−d   2   ,j−d   2 )− L ( k,i+d   2   ,j−d   2 )− L ( k,i−d   2   ,j+d   2 )+ L ( k,i+d   2   ,j+d   2 )
 
   
       where L(k, i, j) is the filtered image response obtained in step a) at scale k at point (i, j) and here d 1  and d 2  are design parameters, being d 1  and d 2  proportional to the sigma, σ, of the approximated second derivative of Gaussian kernel;
 c) searching for extremum values both within a single scale and along the scale space of the approximation of the determinant of Hessian obtained in step b) and calculating the keypoints from these extrema values; 
 d) detecting for each keypoint, localised at an extremum value, dominant orientations from gradient information calculated using the filtered image response obtained in step a); and 
 e) calculating for each dominant orientation a keypoint descriptor, wherein the descriptor is composed of oriented gradients sampled with a specific layout, where the oriented gradients are calculated as:
   ∂ x   θ   =L ( k,i−d   3 ·cos θ, j−d   3 ·sin θ)− L ( k,i+d   3 ·cos θ, j+d   3 ·sin θ)
 
 
 
       where L(k, i, j) is the filtered image response obtained in step a) at scale k at point (i, j) and d 3  is a design parameter, and θ is the angle of the dominant orientation of the keypoint. 
     
     
         2 . The method of  claim 1 , wherein the step of detecting the dominant orientations comprises the following steps:
 selecting, for each keypoint, a number of samples inside a neighborhood of the keypoint;   calculating for each sample (i,j), horizontal gradient as
   ∂ k   x   =L ( k,i−d   3   ,j )− L ( k,i+d   3   ,j )
 
   
       and vertical gradient as:
   ∂ k   y   =L ( k,i,j−d   3 )− L ( k,i,j+d   3 )
 
 
       where L(k, i, j) is the filtered image response obtained in step a) at scale k at point (i, j) and d 3  is a design parameter; 
       accumulating each gradient into a histogram with a weight proportional to its magnitude and with a Gaussian kernel centered at the keypoint; and 
       searching for peaks with values near the maximum to find the dominant orientations. 
     
     
         3 . The method of  claim 2 , wherein the neighborhood is a circular neighborhood. 
     
     
         4 . (canceled) 
     
     
         5 . The method of  claim 1  wherein the layout consists of a number of segments and rings, each segment is a portion of the neighborhood of the keypoint and each ring is a group of segments that share the following property: the centre of the segment is placed at the same Euclidean distance from the keypoint. 
     
     
         6 . The method of  claim 1 , wherein the calculation of the keypoints is done with sub-pixel and sub-scale accuracy. 
     
     
         7 . The method of  claim 6 , wherein the calculation of the keypoints is done by fitting a quadratic function centred in each extremum value to determine the interpolated location and searching in the neighbouring pixels of the same scale, the upper and the lower ones. 
     
     
         8 - 9 . (canceled) 
     
     
         10 . A system comprising means adapted to perform the method according to  claim 1 . 
     
     
         11 . A computer program comprising computer program code means adapted to perform the method according to  claim 1  when said program is run on a computer, a digital signal processor, a field-programmable gate array, an application-specific integrated circuit, a micro-processor, a micro-controller, or any other form of programmable hardware.