Keypoint descriptor generation by complex wavelet analysis

• US 8,712,158 B2
• Filed: 11/05/2009
• Issued: 04/29/2014
• Est. Priority Date: 11/05/2008
• Status: Active Grant

• Current Assignee: Zebra Technologies Corporation
• Original Assignee: Cortexica Vision Systems Limited (Zebra Technologies Corporation)
• Inventors: Bharath, Anil Anthony, Ng Sing Kwong, Jeffrey
• Primary Examiner(s): LE, BRIAN Q
• Application Number:
  US13/127,901
• Publication Number:
  US 20110262041A1
• Time in Patent Office: 1,636 Days
• Field of Search: 382190-195, 382232-253
• US Class Current: 382/190
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 20/647 by matching two-dimensional images to three-dimensional objects

Abstract

The present invention relates to a method of generating a keypoint descriptor for identifying an object in an image or in a sequence of images, the keypoint descriptor being substantially invariant to a transformation of the object in the image. The method includes receiving object data representing an object for identification in an image; processing said object data to generate at least one basis function representing a feature having undergone at least one transformation or a transformation sequence across several consecutive frames, optionally using transformations that are out of the image plane to recognize objects from multiple views; modifying a prototype wavelet function based on said at least one basis function to generate a plurality of modified wavelet functions; comparing the plurality of modified wavelet functions with the at least one basis function; selecting a modified wavelet function of said plurality of modified wavelet functions based on the comparison of the plurality of modified wavelet functions with the at least one basis function; and processing an input image or input orientation field according to said selected modified wavelet function to generate the keypoint descriptor. The present invention further relates to a method of identifying an object in an image using a keypoint descriptor; and apparatus and computer software for implementing a method in accordance with the present invention.

Claims

1. A method of generating a keypoint descriptor for identifying an object in an image or in a sequence of images, the keypoint descriptor being substantially invariant to a transformation of the object in the image, wherein the method is performed using processing apparatus and includes:

a) receiving object data representing an object for identification in an image;

b) processing said object data to generate at least one basis function representing a feature having undergone at least one transformation or a transformation sequence across several consecutive frames, optionally using transformations that are out of the image plane to recognize objects from multiple views;

c) modifying a prototype wavelet function based on said at least one basis function to generate a plurality of modified wavelet functions;

d) comparing the plurality of modified wavelet functions with the at least one basis function;

e) selecting a modified wavelet function of said plurality of modified wavelet functions based on the comparison of step d); and

f) processing an input image or input orientation field according to said selected modified wavelet function to generate the keypoint descriptor,

wherein the prototype wavelet function and the plurality of modified wavelet functions comprise a radial distance component and an azimuthal angle component,

wherein the prototype wavelet function and the plurality of modified wavelet functions have the formula;

Ψ

_k(d,θ

)=d<sup>nk−

1</sup>e<sup>−

α

k d</sup>(n_k−

α

_kd) ·

(cos(m_kθ

)+q_xsin(m_kθ

))

where the term d<sup>nk−

1</sup>e<sup>−

α

kd</sup>(n_k−

α

_kd) is the radial distance component and the term (cos(m_kθ

)+q_x, sin(m_kθ

)) is the azimuthal angle component, and where the term q_x, denotes an imaginary unit.

2. A method according to claim 1, wherein the keypoint descriptor is arranged to identify an object in a single image.

3. A method according to claim 2, wherein the object is a two-dimensional or three-dimensional object in a two-dimensional image.

4. A method according to claim 1, wherein the prototype wavelet function and the modified wavelet functions comprise a non-linear weighting of the radial distance component.

5. A method according to claim 4, wherein the non-linear weighting represents a radial decay.

6. A method according to claim 1, wherein the prototype wavelet function and the modified wavelet functions are quaternion wavelet functions, the keypoint is arranged to identify an object in an image patch, the transformation comprises a rotation, the transformation comprises a translation, said at least one basis function is an eigenfunction, the object is a two-dimensional object in a temporal sequence of images or a three-dimensional object in three-dimensional volumetric data, or the modifying of step c) is performed in accordance with the formula:

7. A method according to claim 1, wherein the comparing of step d) includes matching at least one of the modified wavelet functions with said at least one basis function, and the selected modified wavelet function is selected in step e) according to matching criteria.

8. A method according to claim 7, wherein the processing of step b) includes generating a plurality of basis functions, the comparing of step d) includes matching a number of the plurality of basis functions with at least one of the modified wavelet functions, and the selecting of step e) includes selecting a modified wavelet function for each of the number of the plurality of basis functions according to matching criteria.

9. A method according to claim 8, wherein the keypoint descriptor is generated in step e) on the basis of the selected wavelet functions.

10. A method of identifying an object in an image, using processing apparatus, the method including processing image data representing at least part of said image with a keypoint descriptor generated using the method of claim 1.

11. A method according to claim 10, wherein the keypoint descriptor is a first keypoint descriptor, and including:

i) receiving said image data;

ii) processing said image data to generate at least one second keypoint descriptor representative of at least one keypoint of said image;

iii) comparing the first keypoint descriptor with the at least one second keypoint descriptor; and

iv) determining if said at least one second keypoint descriptor matches the first keypoint descriptor.

12. A method according to claim 10, the method including estimating transformation parameters of the object in the input image or input orientation field from the keypoint descriptor.

13. A method according to claim 12, the method including tracking at least one keypoint from one frame to another frame using the transformation parameters.

14. Processing apparatus arranged to perform the method of claim 10.

15. A computer program product comprising a non-transitory computer-readable storage medium having computer readable instructions stored thereon, the computer readable instructions being executable by a computerised device to cause the computerised device to perform the method of claim 10.

16. Processing apparatus arranged to perform the method of claim 1.

17. A computer program product comprising a non-transitory computer-readable storage medium having computer readable instructions stored thereon, the computer readable instructions being executable by a computerised device to cause the computerised device to perform the method of claim 1.

18. A method of generating a keypoint descriptor for identifying an object in an image or in a sequence of images, the keypoint descriptor being substantially invariant to a transformation of the object in the image, wherein the method is performed using processing apparatus and includes:

a) receiving object data representing an object for identification in an image;

b) processing said object data to generate at least one basis function representing a feature having undergone at least one transformation or a transformation sequence across several consecutive frames, optionally using transformations that are out of the image plane to recognise objects from multiple views;

c) modifying a prototype wavelet function based on said at least one basis function to generate a plurality of modified wavelet functions;

d) comparing the plurality of modified wavelet functions with the at least one basis function;

e) selecting a modified wavelet function of said plurality of modified wavelet functions based on the comparison of step d); and

f) processing an input image or input orientation field according to said selected modified wavelet function to generate the keypoint descriptor,

wherein the object is a three dimensional object in a three dimensional image or the keypoint descriptor is arranged to identify an object in a series of images spaced over time,

wherein the prototype wavelet function and the plurality of modified wavelet functions comprise a radial distance component, an azimuthal angle component and a polar angle component,

wherein the prototype wavelet function and the plurality of modified wavelet functions have the formula;

Ψ

_k(d,θ

,φ

,)=d<sup>nk−

1</sup>e<sup>−

α

kd</sup>(n_k−

α

_kd) ·

(cos(m_kθ

)+q_xsin(m_kθ

)) ·

(cos(l_kφ

)+q_ysin(l_kφ

))

where the term d^nk-1e<sup>−

α

kd</sup>(n_k−

α

_kd) is the radial distance weighting component with radial distance, d, the term (cos(m_kθ

)+q_x, sin(m_kθ

)) is the azimuthal angle component with azimuthal angle θ

, and the term (cos(l_kφ

)+q_ysin(l_kφ

)) is polar angle component with polar angle φ

, and where the terms q_x, and q_y, denote unit quaternions and obey the rules q_x²=q_y²=q_z²=−

1, and q_x, q_y=q_z.

19. A method according to claim 18, wherein the prototype wavelet function and the modified wavelet functions comprise a non-linear weighting of the radial distance component.

20. A method according to claim 19, wherein the non-linear weighting represents a radial decay.

21. A method according to claim 18, wherein the prototype wavelet function and the modified wavelet functions are quaternion wavelet functions, the keypoint is arranged to identify an object in an image patch, the transformation comprises a rotation, the transformation comprises a translation, said at least one basis function is an eigenfunction, the object is a two-dimensional object in a temporal sequence of images or a three-dimensional object in three-dimensional volumetric data, or the modifying of step c) is performed in accordance with the formula:

22. A method according to claim 18, wherein the comparing of step d) includes matching at least one of the modified wavelet functions with said at least one basis function, and the selected modified wavelet function is selected in step e) according to matching criteria.

23. A method according to claim 22, wherein the processing of step b) includes generating a plurality of basis functions, the comparing of step d) includes matching a number of the plurality of basis functions with at least one of the modified wavelet functions, and the selecting of step e) includes selecting a modified wavelet function for each of the number of the plurality of basis functions according to matching criteria.

24. A method according to claim 23, wherein the keypoint descriptor is generated in step e) on the basis of the selected wavelet functions.

25. A method of identifying an object in an image, using processing apparatus, the method including processing image data representing at least part of said image with a keypoint descriptor generated using the method of claim 18.

26. A method according to claim 25, wherein the keypoint descriptor is a first keypoint descriptor, and including:

i) receiving said image data;

ii) processing said image data to generate at least one second keypoint descriptor representative of at least one keypoint of said image;

iii) comparing the first keypoint descriptor with the at least one second keypoint descriptor; and

iv) determining if said at least one second keypoint descriptor matches the first keypoint descriptor.

27. A method according to claim 25, the method including estimating transformation parameters of the object in the input image or input orientation field from the keypoint descriptor.

28. A method according to claim 27, the method including tracking at least one keypoint from one frame to another frame using the transformation parameters.

29. Processing apparatus arranged to perform the method of claim 25.

30. A computer program product comprising a non-transitory computer-readable storage medium having computer readable instructions stored thereon, the computer readable instructions being executable by a computerised device to cause the computerised device to perform the method of claim 25.

31. Processing apparatus arranged to perform the method of claim 18.

32. A computer program product comprising a non-transitory computer-readable storage medium having computer readable instructions stored thereon, the computer readable instructions being executable by a computerised device to cause the computerised device to perform the method of claim 18.

33. A method of generating a keypoint descriptor for identifying an object in an image or in a sequence of images, the keypoint descriptor being substantially invariant to a transformation of the object in the image, wherein the method is performed using processing apparatus and includes:

a) receiving object data representing an object for identification in an image;

b) processing said object data to generate at least one basis function representing a feature having undergone at least one transformation or a transformation sequence across several consecutive frames, optionally using transformations that are out of the image plane to recognise objects from multiple views;

c) modifying a prototype wavelet function based on said at least one basis function to generate a plurality of modified wavelet functions;

d) comparing the plurality of modified wavelet functions with the at least one basis function;

e) selecting a modified wavelet function of said plurality of modified wavelet functions based on the comparison of step d); and

f) processing an input image or input orientation field according to said selected modified wavelet function to generate the keypoint descriptor,

wherein the prototype wavelet function and the modified wavelet functions are quaternion wavelet functions, the keypoint is arranged to identify an object in an image patch, the transformation comprises a rotation, the transformation comprises a translation, said at least one basis function is an eigenfunction, the object is a two-dimensional object in a temporal sequence of images or a three-dimensional object in three-dimensional volumetric data, or the modifying of step c) is performed in accordance with the formula;

34. A method according to claim 33, wherein the comparing of step d) includes matching at least one of the modified wavelet functions with said at least one basis function, and the selected modified wavelet function is selected in step e) according to matching criteria.

35. A method according to claim 34, wherein the processing of step b) includes generating a plurality of basis functions, the comparing of step d) includes matching a number of the plurality of basis functions with at least one of the modified wavelet functions, and the selecting of step e) includes selecting a modified wavelet function for each of the number of the plurality of basis functions according to matching criteria.

36. A method according to claim 35, wherein the keypoint descriptor is generated in step e) on the basis of the selected wavelet functions.

37. A method of identifying an object in an image, using processing apparatus, the method including processing image data representing at least part of said image with a keypoint descriptor generated using the method of claim 33.

38. A method according to claim 37, wherein the keypoint descriptor is a first keypoint descriptor, and including:

i) receiving said image data;

ii) processing said image data to generate at least one second keypoint descriptor representative of at least one keypoint of said image;

iii) comparing the first keypoint descriptor with the at least one second keypoint descriptor; and

iv) determining if said at least one second keypoint descriptor matches the first keypoint descriptor.

39. A method according to claim 37, the method including estimating transformation parameters of the object in the input image or input orientation field from the keypoint descriptor.

40. A method according to claim 39, the method including tracking at least one keypoint from one frame to another frame using the transformation parameters.

41. Processing apparatus arranged to perform the method of claim 37.

42. A computer program product comprising a non-transitory computer-readable storage medium having computer readable instructions stored thereon, the computer readable instructions being executable by a computerised device to cause the computerised device to perform the method of claim 37.

43. Processing apparatus arranged to perform the method of claim 33.

44. A computer program product comprising a non-transitory computer-readable storage medium having computer readable instructions stored thereon, the computer readable instructions being executable by a computerized device to cause the computerized device to perform the method of claim 33.