Efficient scale-space extraction and description of interest points

• US 8,798,377 B2
• Filed: 09/01/2010
• Issued: 08/05/2014
• Est. Priority Date: 02/08/2010
• Status: Active Grant

• Current Assignee: Carear Incorporated (Xerox Holdings Corp.)
• Original Assignee: Telefonica SA
• Inventors: Adamek, Tomasz, Sanjuan, David Marimon, Llofriu, Arturo Bonnin, Hernandez, Roger Gimeno
• Primary Examiner(s): Repko, Jason M
• Assistant Examiner(s): ROWLAND, JHERE M
• Application Number:
  US12/873,595
• Publication Number:
  US 20110194772A1
• Time in Patent Office: 1,434 Days
• Field of Search: None
• US Class Current: 382/205
• CPC Class Codes: G06T 15/04 Texture mapping
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]

Abstract

Method, system and computer program for efficiently extracting and describing scale-space interest points. It is 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.

Claims

1. A method of keypoint scale-space extraction and description in an image, the method comprising the steps of:

a) filtering the image with triangle kernel filters at different scales;

b) computing an approximation of a determinant of Hessian at each scale, the approximation at each scale k being calculated as |∂

^k_xx(i, j)·

∂

^k_yy(i, j)−

∂

^k_xy(i, j)²| where ∂

_xx is a second horizontal derivative of Gaussian over a filtered image response L(k, i, i) obtained in step a) at scale k at point (i, j), ∂

_yy is a second vertical derivative of Gaussian over the filtered image response L(k, i, j), and ∂

_xy is the cross derivative of Gaussian over the filtered image response L(k, i, j), using a first design parameter d₁ for computing a second horizontal and vertical derivatives of Gaussian, ∂

_xx and ∂

_yy, and a second design parameter d₂ for computing a cross derivative of Gaussian ∂

_xy, being both the first design parameter d₁ and the second design parameter d₂ proportional to a deviation σ

of a 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) for each keypoint, localized at an extremum value, detecting the 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.

2. The method of claim 1, wherein the step of detecting the dominant orientations comprises the following steps:

for each keypoint, a number of samples inside a neighborhood of the keypoint are selected,

for each sample (i, j), a horizontal gradient is calculated as ∂

^k_x=L(k, i−

d₃,j)−

L(k, i+d₃,j) and a vertical gradient is calculated as ∂

^k_y=L(k, i, j−

d₃)−

L(k, i, j+d₃)

where L(k, i, j) is the filtered image response obtained in step a) at scale k at point (i, j) and d₃ is a design parameter,

each gradient is accumulated into a histogram with a weight proportional to its magnitude and with a Gaussian kernel centered at the keypoint,

the dominant orientations are found by searching for peaks with values near the maximum.

3. The method of claim 2, wherein the neighborhood is a circular neighborhood.

4. The method of claim 1, wherein the descriptor is composed of oriented gradients sampled with a specific layout, where the oriented gradients are calculated

where L(k, i, j) is the filtered image response obtained in step a) at scale k at point (i, j) and d₃ is a design parameter, and θ

is the angle of the dominant orientation of the keypoint.

5. The method of claim 4, 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 center of the segment is placed at the same Euclidean distance from the keypoint.

6. The method of claim 1, where the calculation of the keypoint is done with sub-pixel and sub-scale accuracy.

7. The method of claim 6, wherein the calculation of the keypoints is done fitting a quadratic function centered in each extremum value to determine the interpolated location and searching in the neighboring pixels of the same scale, the upper and the lower ones.

8. The method of claim 1, wherein the filters are 2D triangle shaped filters.

9. The method of claim 1, where d₁ and d₂ are proportional to the σ

(sigma) of the approximated second derivative of Gaussian kernel.

10. A system comprising:

a processor, the processor executing a program code adapted to perform a method of keypoint scale-space extraction and description in an image, the method comprising the steps of

a) filtering the image with triangle kernel filters at different scales;

b) computing an approximation of a determinant of Hessian at each scale, the approximation at each scale k being calculated as |∂

^k_xx(i, j)·

∂

^k_yy(i, j)−

∂

^k_xy(i, j)²| where θ

_xx is a second horizontal derivative of Gaussian over a filtered image response L(k, i, j) obtained in step) a) at scale k at point (i, j), ∂

_yy is a second vertical derivative of Gaussian over the filtered image response L(k, i, j), and ∂

_xy is the cross derivative of Gaussian over the filtered image response L(k, i, j), using a first design parameter d₁ for computing a second horizontal and vertical derivatives of Gaussian, ∂

_xx and ∂

_yy, and a second design parameter d₂ for computing a cross derivative of Gaussian ∂

_xy, being both the first design parameter d₁ and the second design parameters d₂ proportional to a deviation σ

of a 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) for each keypoint, localized at an extremum value, detecting the 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.

11. The system of claim 10, wherein the step of detecting the dominant orientations comprises the following steps:

for each keypoint, a number of samples inside a neighborhood of the keypoint are selected,

for each sample (i, j), a horizontal gradient is calculated as θ

^k_x=L(k, i−

d₃,j)−

L(k, i+d₃,j) and a vertical gradient is calculated as ∂

^k_y=L(k, i, j−

d₃)−

L(k, i, j+d₃)

where L(k, i, j) is the filtered image response obtained in step a) at scale k at point (i, j) and d₃ is a design parameter,

each gradient is accumulated into a histogram with a weight proportional to its magnitude and with a Gaussian kernel centered at the keypoint,

the dominant orientations are found by searching for peaks with values near the maximum.

12. The system of claim 10, wherein the descriptor is composed of oriented gradients sampled with a specific layout, where the oriented gradients are calculated

where L(k, i, j) is the filtered image response obtained in step a) at scale k at point (i, j) and d₃ is a design parameter, and θ

is the angle of the dominant orientation of the keypoint.

13. The system of claim 10, where the calculation of the keypoint is done with sub-pixel and sub-scale accuracy.

14. The system of claim 13, wherein the calculation of the keypoints is done by fitting a quadratic function centered in each extremum value to determine the interpolated location and searching in the neighboring pixels of the same scale, the upper and the lower ones.

15. The system of claim 10, wherein the filters are 2D triangle shaped filters.

16. A non-transitory computer readable medium storing a program code which, when executed by a processor, is adapted to a method of keypoint scale-space extraction and description in an image, the method comprising the steps of

a) filtering the image with triangle kernel filters at different scales;

b) computing an approximation of a determinant of Hessian at each scale, the approximation at each scale k being calculated as |∂

^k_xx(i, j)·

∂

^k_yy(i, j)−

∂

^k_xy(i, j)²|, where ∂

_xx is a second horizontal derivative of Gaussian over a filtered image response L(k, i, j) obtained in step a) at scale at point (i, j), ∂

_yy is a second vertical derivative of Gaussian over the filtered image response L(k, i, j), and ∂

_xy is the cross derivative of Gaussian over the filtered image response L(k, i, j), using a first design parameter d₁ for computing a second horizontal and vertical derivatives of Gaussian, ∂

_xx and ∂

_yy, and a second design parameter d₂ for computing a cross derivative of Gaussian ∂

_xy, being both the first design parameter d₁ and the second design parameters d₂ proportional to a deviation σ

of a 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) for each keypoint, localized at an extremum value, detecting the 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.

17. The medium of claim 16, wherein the step of detecting the dominant orientations comprises the following steps:

for each keypoint, a number of samples inside a neighborhood of the keypoint are selected,

for each sample (i, j), a horizontal gradient is calculated as ∂

^k_x=L(k, i−

d₃,j)−

L(k, i+d₃,j) and a vertical gradient is calculated as ∂

^k_y=L(k, i, j−

d₃)−

L(k, i, j+d₃)

where L(k, i, j) is the filtered image response obtained in step a) at scale k at point (i, j) and d₃ is a design parameter,

each gradient is accumulated into a histogram with a weight proportional to its magnitude and with a Gaussian kernel centered at the keypoint,

the dominant orientations are found by searching for peaks with values near the maximum.

18. The medium of claim 16, wherein the descriptor is composed of oriented gradients sampled with a specific layout, where the oriented gradients are calculated

where L(k, i, j) is the filtered image response obtained in step a) at scale k at point (i, j) and d₃ is a design parameter, and θ

is the angle of the dominant orientation of the keypoint.

19. The medium of claim 16, where the calculation of the keypoint is done with sub-pixel and sub-scale accuracy.

20. The medium of claim 19, wherein the calculation of the keypoints is done by fitting a quadratic function centered in each extremum value to determine the interpolated location and searching in the neighboring pixels of the same scale, the upper and the lower ones.