Method of matching image features with reference features and integrated circuit therefor

• US 9,378,431 B2
• Filed: 11/18/2011
• Issued: 06/28/2016
• Est. Priority Date: 11/18/2011
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Metaio GmbH (Apple Inc.)
• Inventors: Stoeffler, Norbert, Meier, Peter
• Primary Examiner(s): PATEL, KANJIBHAI B
• Application Number:
  US14/359,029
• Publication Number:
  US 20150049955A1
• Time in Patent Office: 1,684 Days
• Field of Search: 382/190, 382/220
• US Class Current: 1/1
• CPC Class Codes: G02B 27/0101 characterised by optical features G02B27/0172 takes precedence
• CPC Class Codes: G06F 16/50 of still image data
• CPC Class Codes: G06F 16/53 Querying
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06V 10/955 using specific electronic processors
• CPC Class Codes: H04N 23/651 for reducing power consumption by affecting camera operations, e.g. sleep mode, hibernation mode or power off of selective parts of the camera

Abstract

The invention is related to a method of matching image features with reference features, comprising the steps of providing a current image captured by a capturing device, providing reference features (r), wherein each of the reference features comprises at least one reference feature descriptor (d(r)), determining current features (c) in the current image and associating with each of the current features at least one respective current feature descriptor (d(c)), and matching the current features with at least some of the reference features by determining a respective similarity measure (D(c, r)) between each respective current feature descriptor (d(c)) and each respective reference feature descriptor (d(r)). According to the invention, the determination of the similarity measure is performed on an integrated circuit by hardwired logic or configurable logic which processes logical functions for determining the similarity measure. The invention is also concerned with an integrated circuit for matching of image features with reference features.

Claims

1. A method of matching image features with reference features, comprising the steps of:

obtaining a current image captured by a capturing device;

determining current features in the current image;

associating, with each of the current features, at least one respective current feature descriptor;

loading the current feature descriptors into a dedicated memory of an integrated circuit; and

matching the current features with two or more reference features by determining a respective similarity measure between each respective current feature descriptor and each respective reference feature descriptor corresponding to a respective reference feature of the two or more reference features, comprising, for at least two of the of the two or more reference features;

loading the reference feature descriptor corresponding to the reference feature to a unit of the integrated circuit, and

determining, for each respective current feature descriptor, a similarity measure between the at least one feature descriptor and the reference feature descriptor,

wherein the integrated circuit is dedicated to logical functions for determining the similarity measure.

2. The method according to claim 1, wherein the current image is one selected from a group consisting of an intensity image and a depth image.

3. The method according to claim 1, wherein determining, for each respective current feature descriptor, a similarity measure further comprises:

determining a respective distance measure between one or more properties of the respective current feature including the respective current feature descriptor and one or more properties of the respective reference feature including the reference feature descriptor for the determination of the similarity measure.

4. The method according to claim 3, further comprising weighting at least one of the properties of the respective current feature and the respective reference feature, when determining the respective similarity measure between the respective current feature descriptor and the reference feature descriptor.

5. The method according to claim 3, wherein determining the respective distance measure, and the respective check parameter are performed in parallel in a pipelined manner on the integrated circuit.

6. The method according to claim 3, wherein one respective distance measure and check parameter is calculated per clock cycle of a clock signal of the integrated circuit.

7. The method according to claim 3, further comprising:

determining from the computed distance measures a lowest distance measure; and

storing an index of the respective current feature descriptor for which the lowest distance measure has been determined.

8. The method according to claim 1, wherein determining a similarity measure comprises calculating a check parameter to determine whether a feature pair with one of the current features and one of the reference features is eligible to be a valid match.

9. The method according to claim 8, wherein determining, for each respective current feature descriptor, a similarity measure further comprises:

determining a respective first distance measure between each respective current feature descriptor and each respective reference feature descriptor for the determination of the similarity measure.

10. The method according to claim 9, wherein determining, for each respective current feature descriptor, a similarity measure further comprises:

determining a respective second distance measure between position information of the respective current feature descriptor in the current image and position information of the respective reference feature descriptor in a common coordinate system.

11. The method according to claim 10, wherein determining, for each respective current feature descriptor, a similarity measure further comprises:

determining a respective third distance measure indicative of an angle between position information of the respective current feature descriptor in the current image and position information of the respective reference feature descriptor in a common coordinate system.

12. The method according to claim 11, wherein determining, for each respective current feature descriptor, a similarity measure further comprises:

determining a respective fourth distance measure between a scalar property of the respective current feature descriptor in the current image and a scalar property of the respective reference feature descriptor.

13. The method according to claim 12, further comprising computing sum-of-differences or sum-of-square-differences for determining the respective first distance measure over a respective dimension.

14. The method according to claim 13, further comprising determining at least one respective check parameter by comparing at least one of the respective second, third and fourth distance measures with at least one respective threshold, wherein the check parameter is used to determine whether a feature pair with one of the current features and one of the reference features is eligible to be a valid match.

15. The method according to claim 14, wherein the at least one respective threshold and the weighting depend on an uncertainty of an initial estimate of a pose of the capturing device.

16. The method according to claim 1, wherein after determining a respective similarity measure, the method further comprises storing a most similar and a second most similar similarity measure from the similarity measures determined, and an index of the respective current feature descriptor associated with the most similar similarity measure.

17. The method according to claim 16, wherein the most similar similarity measure is compared with a derivative of the second most similar similarity measure, wherein if this comparison fulfills a predetermined condition, the most similar and second most similar similarity measure, the index, and the associated reference feature descriptor is provided for further processing.

18. The method according to claim 1, wherein the integrated circuit comprises a register bank that holds a reference feature descriptor vector and two accumulator registers for holding a respective check parameter and a respective distance measure, wherein only parts of a respective current feature descriptor vectors and reference feature descriptor vector are compared at once.

19. The method according to claim 1, wherein the current feature descriptors are retrieved from the memory without wait states.

20. The method according to claim 1, wherein at least a pixel of the current image is set as a respective current feature in the current image.

21. The method according to claim 1, wherein a first set of the current features are determined utilizing a first feature extraction process, and a second set of the current features is determined utilizing a second feature extraction process, wherein the first feature extraction process and the second feature extraction process are different from each other.

22. The method according to claim 1, further comprising performing geometric verification to remove incorrect feature matches.

23. The method according to claim 1, wherein each of the reference features comprises at least one first parameter which is at least partially indicative of a position of the reference feature with respect to a global coordinate system, wherein the global coordinate system is an earth coordinate system or an object coordinate system the method further comprising:

associating with a respective current feature at least one second parameter which is at least partially indicative of a position of the current feature with respect to the global coordinate system; and

matching the current feature with at least one of the reference features of the set of reference features by determining the similarity measure between the at least one first parameter and the at least one second parameter.

24. The method according to claim 23, further comprising:

defining a search space with a reduced number of reference features within the set of reference features when matching the respective current feature, wherein the search space is determined based on the at least one second parameter.

25. The method according to claim 1, wherein at least one of the current feature descriptor or the reference feature descriptor is invariant to scale.

26. An integrated circuit for matching of image features with reference features, comprising:

a memory comprising a number of current feature descriptors of respective current features taken from a current image captured by a capturing device;

a unit for receiving a number of reference feature descriptors of respective reference features; and

a logic circuit for matching the current features with two or more reference features by determining a respective similarity measure between each respective current feature descriptor and each respective reference feature descriptor corresponding to a respective reference feature of the two or more reference features, comprising, for at least two of the of the two or more reference features;

loading the reference feature descriptor corresponding to the reference feature to a unit of the integrated circuit, and

determining, for each respective current feature descriptor, a respective similarity measure between each respective current feature descriptor and each respective reference feature descriptor.

27. The integrated circuit of claim 26, wherein the current image is one selected from a group consisting of an intensity image and a depth image.

28. The integrated circuit of claim 26, wherein determining, for each respective current feature descriptor, a similarity measure further comprises:

determining a respective distance measure between one or more properties of the respective current feature including the respective current feature descriptor and one or more properties of the respective reference feature including the reference feature descriptor for the determination of the similarity measure.

29. The integrated circuit of claim 28, wherein determining the respective distance measure, and the respective check parameter are performed in parallel in a pipelined manner on the integrated circuit.

30. The integrated circuit of claim 28, wherein one respective distance measure and check parameter is calculated per clock cycle of a clock signal of the integrated circuit.