Robust interest point detector and descriptor

• US 8,165,401 B2
• Filed: 04/30/2007
• Issued: 04/24/2012
• Est. Priority Date: 04/28/2006
• Status: Active Grant

• Current Assignee: Eidgenoessische Technische Hochschule Zurich, KU Leuven Research & Development, Toyota Jidosha Kabushiki Kaisha (Toyota Motor Corporation)
• Original Assignee: Eidgenoessische Technische Hochschule Zurich, KU Leuven Research & Development, Toyota Motor Europe SA (Toyota Motor Corporation)
• Inventors: Yanagihara, Hiromichi, Tuytelaars, Tinne, Funayama, Ryuji, Van Gool, Luc, Bay, Herbert
• Primary Examiner(s): Perungavoor, Sath V
• Application Number:
  US12/298,879
• Publication Number:
  US 20090238460A1
• Time in Patent Office: 1,821 Days
• Field of Search: 382/190
• US Class Current: 382/190
• CPC Class Codes: G06V 10/36 Applying a local operator, i.e. means to operate on image points situated in the vicinity of a given point; Non-linear local filtering operations, e.g. median filtering
• CPC Class Codes: G06V 10/446 using Haar-like filters, e.g. using integral image techniques
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]

Abstract

Methods and apparatus for operating on images are described, in particular methods and apparatus for interest point detection and/or description working under different scales and with different rotations, e.g. for scale-invariant and rotation-invariant interest point detection and/or description. The present invention can provide improved or alternative apparatus and methods for matching interest points either in the same image or in a different image. The present invention can provide alternative or improved software for implementing any of the methods of the invention. The present invention can provide alternative or improved data structures created by multiple filtering operations to generate a plurality of filtered images as well as data structures for storing the filtered images themselves, e.g. as stored in memory or transmitted through a network. The present invention can provide alternative or improved data structures including descriptors of interest points in images, e.g. as stored in memory or transmitted through a network as well as data structures associating such descriptors with an original copy of the image or an image derived therefrom, e.g. a thumbnail image.

Claims

1. A method for deriving a descriptor of an interest point in an image having a plurality of pixels, the interest point having a location in the image and an orientation, the method comprising:

identifying a neighbourhood around the interest point aligned with the orientation of the interest point, the neighbourhood being divided into sub-regions, each sub-region comprising a set of pixels;

inspecting contrasts at pixels of the set of pixels in the sub-regions in at least two directions having a fixed relation to the orientation using at least one first digital filter to thereby generate first scalar contrast measures for each direction independently, each first scalar contrast measure being a component of an intensity gradient represented by the change of contrast or image intensity along each direction at each pixel of the set of pixels; and

generating a multidimensional descriptor comprising first elements, each first element being a second scalar contrast measure that is a combination of the first scalar contrast measures from only one direction.

2. The method of claim 1 wherein inspecting contrasts in the neighbourhood of the interest point in the first direction having a fixed relation to the orientation and in the second direction orthogonal to the first direction is carried out using convolution filters.

3. The method of claim 1, further comprising a second element, including using the second element to distinguish a type of contrast of the interest point.

4. The method of claim 3, wherein the second element is used to distinguish bright blobs on dark backgrounds from a reverse.

5. The method of claim 3, including using as the second element the sign of the Laplacian at the interest point.

6. The method of claim 1, including using as the at least one first digital filter a Haar wavelet filter.

7. The method of claim 1, including basing the first elements on summed absolute values resulting from application of the at least one first digital filter in the at least two directions.

8. The method of claim 1, including

determining the interest point in the image, the image having a plurality of pixels suitable for working at different scales and/or rotations,

filtering the image using at least one second digital filter,

selecting an interest point based on determining a measure resulting from application of the at least one second digital filter,

the measure being a non-linear combination of the outputs of the at least one second digital filter, and

the measure capturing variations of an image parameter in more than one dimension or direction.

9. The method of claim 8, wherein application of the at least one second digital filter to the image is performed with integral images.

10. The method of claim 8, including using as the at least one second digital filter a combination of box filters, at least one box filter of the combination of box filters having a spatial extent greater than one pixel.

11. The method of claim 10, including using as a combination of box filters a combination that approximates derivatives of a smoothing filter in more than one direction.

12. The method of claim 8, further comprising providing a plurality of filtered images at different scales using the at least one digital filter.

13. The method of claim 8, wherein the measure is the determinant of a Hessian matrix constructed from the results of applying the at least one filter.

14. The method of claim 8, wherein application of the at least one second filter comprises application of at least three digital filters, or wherein the at least one second digital filter is derived from the second order derivative of a smoothing filter, or wherein the at least one second digital filter is applied at different scalings to the image to generate a plurality of filtered images.

15. The method of claim 8, wherein an interest point is determined as a local extreme value of the measure within a neighbourhood including a region of a filtered image.

16. The method of claim 15, wherein the neighbourhood is a space defined by at least three of a plurality of filtered images logically arranged in an image pyramid.

17. The method of claim 1, wherein the first scalar contrast measures are weighted.

18. The method of claim 1, wherein the image is a 2D image, 3D solid image, or spatio-temporal video.

19. A non-transitory computer-readable medium storing a computer program product for executing the method recited in claim 1.

20. A computer based system configured to carry out the method recited claim 1.