ROBUST INTEREST POINT DETECTOR AND DESCRIPTOR

• US 20090238460A1
• Filed: 04/30/2007
• Published: 09/24/2009
• 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: Tuytelaars, Tinne, Van Gool, Luc, Bay, Herbert, Yanagihara, Hiromichi, Funayama, Ryuji
• Granted Patent: US 8,165,401 B2
• Time in Patent Office: Days
• US Class Current: 382/181
• 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 datastructures 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 comprising a set of pixels;

inspecting contrasts in the neighbourhood of the interest point in at least one direction having a fixed relation to the orientation using at least one digital filter to thereby generate first scalar contrast measures for each direction independently, 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.

3. The method of claim 1, wherein the descriptor includes a second element, the second element being the sign of the Laplacian at the interest point.

4. The method of claim 1, wherein the at least one digital filter is a Haar wavelet filter.

5. The method of claim 1, wherein first elements are based on summed absolute values resulting from application of the at least one digital filter in at least two directions.

9. 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, the method further comprising:

filtering the image using at least one digital filter, and

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

the measure being a non-linear combination of the outputs of the at least one digital filter, the measure capturing variations of an image parameter in more than one dimension or direction, the at least one digital filter being a combination of box filters, at least one box filter having a spatial extent greater than one pixel.

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

11. The method of claim 1 any of the claim 1, including determining an interest point in the image, the image having a plurality of pixels suitable for working at different scales and/or rotations, the method further comprising:

filtering the image using at least one digital filter, and

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

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

the application of the at least one digital filter using integral images.

12. The method of claim 11, wherein the at least one digital filter is a combination of box filters, at least one box filter having a spatial extent greater than one pixel.

13. The method of claim 9, wherein the combination of box filters approximates derivatives of a smoothing filter in more than one direction.

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

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

16. The method of claim 9, wherein application of the at least one filter comprises application of at least three digital filters.

17. The method of claim 9, wherein the at least one digital filter is derived from the second order derivative of a smoothing filter.

18. The method according to claim 9, wherein the at least one digital filter is applied at different scalings to the image to generate a plurality of filtered images.

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

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

2. 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 region in a neighbourhood around the interest point aligned with the orientation of the interest point, the neighbourhood comprising a set of pixels;

examining tiles of the region, and for each tile generating a contrast related response using at least one digital filter,

summing response values from application of the at least one digital filter in at least two orthogonal directions to generate summed values, and

generating a multidimensional descriptor having first elements, each first element being based on the summed values.

6. 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, and a neighbourhood having been defined around the interest point aligned with the orientation of the interest point, the neighbourhood comprising a set of pixels;

the method comprising;

inspecting contrasts in the neighbourhood of the interest point using at least one digital filter,

generating a multidimensional descriptor based on the results of the application of the at least one digital filter and absolute values of these results.

7. The method of claim 6, wherein the descriptor includes the sign of the Laplacian at the interest point.

8. A method for assigning the orientation of an interest point in an image having a plurality of pixels, the interest point having a location, the method comprising:

identifying a region enclosing the interest point,

determining an orientation for the interest point by;

examining a plurality of tiles of the region, each tile comprising a plurality of pixels, determining for each tile filtered values related to contrast in two directions to thereby determine for that tile an orientation and a magnitude for that orientation, and assigning an orientation to the interest point by selecting the determined orientation with largest magnitude.

21. A method for determining an interest point in an image having a plurality of pixels suitable for working at different scales and/or rotations, the method comprising:

filtering the image using at least one digital filter, and

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

the measure being a non-linear combination of the outputs of the at least one digital filter, the measure capturing variations of an image parameter in more than one dimension or direction, the at least one digital filter being a combination of box filters, at least one box filter having a spatial extent greater than one pixel.

22. The method of claim 21 wherein application of the at least one digital filter to the image is performed with integral images.

25. The method of claim 21, wherein the combination of box filters approximates derivatives of a smoothing filter in more than one direction.

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

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

28. The method of claim 21, wherein application of the at least one filter comprises application of at least three digital filters.

29. The method of claim 21, wherein the at least one digital filter is derived from the second order derivative of a smoothing filter.

30. The method according to claim 21, wherein the at least one digital filter is applied at different scalings to the image to generate a plurality of filtered images.

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

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

23. A method for determining an interest point in an image having a plurality of pixels suitable for working at different scales and/or rotations, the method comprising:

filtering the image using at least one digital filter, and

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

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

the application of the at least one digital filter using integral images.

24. The method of claim 23, wherein the at least one digital filter is a combination of box filters, at least one box filter having a spatial extent greater than one pixel.