Matching Local Image Feature Descriptors in Image Analysis

• US 20190311214A1
• Filed: 04/05/2019
• Published: 10/10/2019
• Est. Priority Date: 04/05/2018
• Status: Active Grant

• Current Assignee: Imagination Technologies Limited (Imagination Technologies Group Ltd.)
• Original Assignee: Imagination Technologies Limited (Imagination Technologies Group Ltd.)
• Inventors: Lakemond, Ruan, Smith, Timothy
• Granted Patent: US 10,885,376 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06T 2207/20164 Salient point detection; Corner detection
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: G06T 7/593 from stereo images
• CPC Class Codes: G06T 7/73 using feature-based methods
• CPC Class Codes: G06V 10/443 by matching or filtering
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 20/10 Terrestrial scenes scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59

Abstract

A method of feature matching in images captured from camera viewpoints uses the epipolar geometry of the viewpoints to define a geometrically-constrained region in a second image corresponding to a first feature in a first image; comparing the local descriptor of the first feature with local descriptors of features in the second image to determine respective measures of similarity; identifying, from the features located in the geometrically-constrained region, (i) a geometric best match and (ii) a geometric next-best match to the first feature; identifying a global best match to the first feature; performing a first comparison of the measures of similarity for the geometric best match and the global best match; performing a second comparison of the measures of similarity for the geometric best match and the geometric next-best match; and, if thresholds are met, selecting the geometric best match feature in the second image.

Claims

1. A computer-implemented method of matching features identified in first and second images captured from respective camera viewpoints related by an epipolar geometry, each identified feature being described by a local descriptor, the method comprising:

using the epipolar geometry to define a geometrically-constrained region in the second image corresponding to a first feature in the first image represented by a first local descriptor;

comparing the first local descriptor with local descriptors of features in the second image, thereby determining respective measures of similarity between the first feature in the first image and the respective features in the second image;

identifying, from the features located in the geometrically-constrained region in the second image, (i) a geometric best match feature to the first feature, and (ii) a geometric next-best match feature to the first feature;

identifying, from any of the features in the second image, a global best match feature to the first feature;

performing a first comparison of the measures of similarity determined for the geometric best match feature and for the global best match feature, with respect to a first threshold;

performing a second comparison of the measures of similarity determined for the geometric best match feature and for the geometric next-best match feature, with respect to a second threshold; and

in dependence on whether the first and second thresholds are satisfied, selecting the geometric best match feature in the second image as an output match to the first feature in the first image.

2. The computer-implemented method as claimed in claim 1, wherein the selecting comprises not providing an output match if either the first or second threshold is not satisfied.

3. The computer-implemented method as claimed in claim 1, wherein the first threshold is satisfied when, according to their respective similarity measures, the geometric best match feature is not worse than the global best match feature as a match to the first feature by an amount defined by a first predefined factor.

4. The computer-implemented method as claimed in claim 1, wherein the second threshold is satisfied when, according to their respective similarity measures, the geometric best match feature is better than the geometric next-best match feature as a match to the first feature by an amount defined by a second predefined factor.

5. The computer-implemented method as claimed in claim 1, wherein performing the first and second comparisons comprises calculating first and second ratios of the magnitudes of the respective measures of similarity, the first and second thresholds being satisfied if the respective ratios satisfy the first and second thresholds, respectively.

6. The computer-implemented method as claimed in claim 5, wherein the comparing the first local descriptor with local descriptors of features in the second image comprises forming descriptor distances between the first local descriptor and the respective local descriptor for each of said features in the second image, and the identifying geometric best match and next-best match features comprises identifying the shortest and next-shortest descriptor distances corresponding to features in the geometrically-constrained region in the second image.

7. The computer-implemented method as claimed in claim 6, wherein the identifying the global best match feature comprises identifying the shortest descriptor distance between the first local descriptor and the local descriptors of features in the second image not limited to those features lying in the geometrically-constrained region.

8. The computer-implemented method as claimed in claim 1, wherein each measure of similarity determined is a descriptor distance between the first local descriptor and the local descriptor of the respective feature of the second image.

9. The computer-implemented method as claimed in claim 8, wherein each local descriptor is a vector representing characteristics of pixels of the respective feature and determining each descriptor distance comprises performing a vector subtraction between the respective local descriptors and determining the magnitude of the resulting vector.

10. The computer-implemented method as claimed in claim 1, wherein said using the epipolar geometry to define a geometrically-constrained region in the second image comprises using the epipolar geometry to derive an epipolar line or area in the second image corresponding to the first feature in the first image, wherein the epipolar line or area is used to define the geometrically-constrained region.

11. The computer-implemented method as claimed in claim 10, wherein the geometrically-constrained region comprises all pixels of the second image within a predefined distance of the epipolar line or area.

12. The computer-implemented method as claimed in claim 11, wherein the predefined distance is determined in dependence on one or more measures of error in the epipolar geometry.

13. The computer-implemented method as claimed in claim 11, wherein the predefined distance is a predefined perpendicular distance to the epipolar line or boundary of the epipolar area which varies with position in the respective image in dependence on the epipolar geometry.

14. The computer-implemented method as claimed in claim 1, wherein each feature represents a localised set of pixels in the respective image and a feature is determined to be located in the geometrically-constrained region using one of more of the following determinations:

determining whether any pixel represented by the feature lies in the geometrically-constrained region;

determining whether one or more predetermined pixels represented by the feature lie in the geometrically-constrained region;

determining whether a predetermined proportion of pixels represented by the feature lie in the geometrically-constrained region.

15. The computer-implemented method as claimed in claim 1, further comprising:

receiving camera data identifying limits on the viewable range from one or both of the camera viewpoints; and

processing the camera data so as to identify bounds on the geometrically-constrained region in the second image in accordance with the epipolar geometry.

16. The computer-implemented method as claimed in claim 15, wherein the camera data comprises for one or both camera viewpoints:

depth information indicating nearest and/or furthest regions viewable from the camera viewpoint;

field of view information indicating regions viewable from the camera viewpoint;

a view frustum for the camera viewpoint; and

data indicating regions in front of and/or behind the camera viewpoint.

17. The computer-implemented method as claimed in claim 10, wherein the epipolar geometry is used to derive an epipolar line and the method further comprises transforming the coordinate system of the second image so as to map the epipolar line parallel to one of the coordinate axes and, subsequently in the transformed coordinate system, identifying the features located in the geometrically-constrained region in the second image.

18. The computer-implemented method as claimed in claim 1, further comprising:

using the epipolar geometry to define a second geometrically-constrained region in the first image corresponding to the geometric best match feature in the second image;

comparing the local descriptor of the geometric best match feature with local descriptors of features in the first image, thereby determining respective measures of similarity between the first feature in the first image and the respective features in the second image;

identifying, from the features located in the second geometrically-constrained region in the first image, (i) a second geometric best match feature to the geometric best match feature of the second image, and (ii) a second geometric next-best match feature to the geometric best match feature of the second image;

identifying, from any of the features in the first image, a second global best match feature to the geometric best match feature of the second image;

performing a first comparison of the measures of similarity determined for the second geometric best match feature and for the second global best match feature, with respect to the first threshold;

performing a second comparison of the measures of similarity determined for the second geometric best match feature and for the second geometric next-best match feature, with respect to the second threshold; and

in dependence on whether the first and second thresholds are satisfied, confirming the geometric best match feature in the second image as the output match to the first feature in the first image.

19. A data processing system for matching features identified in first and second images captured from respective camera viewpoints related by an epipolar geometry, each identified feature being described by a local descriptor, the data processing system comprising:

a geometry unit configured to use the epipolar geometry to define a geometrically-constrained region in the second image corresponding to a first feature in the first image represented by a first local descriptor;

a comparison unit configured to compare the first local descriptor with local descriptors of features in the second image thereby determining respective measures of similarity between the first feature in the first image and the respective features in the second image; and

a match unit configured to;

identify, from the features located in the geometrically-constrained region in the second image, (i) a geometric best match feature to the first feature, and (ii) a geometric next-best match feature to the first feature,

identify, from any of the features in the second image, a global best match feature to the first feature,

perform a first comparison of the measures of similarity determined for the geometric best match feature and for the global best match feature, with respect to a first threshold,

perform a second comparison of the measures of similarity determined for the geometric best match feature and for the geometric next-best match feature, with respect to a second threshold, and

in dependence on whether the first and second thresholds are satisfied, select the geometric best-match feature in the second image as an output match to the first feature in the first image.

20. A non-transitory computer readable storage medium having stored thereon computer readable instructions that, when executed at a computer system, cause the computer system to perform a method of matching features identified in first and second images captured from respective camera viewpoints related by an epipolar geometry, each identified feature being described by a local descriptor, the method comprising:

using the epipolar geometry to define a geometrically-constrained region in the second image corresponding to a first feature in the first image represented by a first local descriptor;

comparing the first local descriptor with local descriptors of features in the second image, thereby determining respective measures of similarity between the first feature in the first image and the respective features in the second image;

identifying, from the features located in the geometrically-constrained region in the second image, (i) a geometric best match feature to the first feature, and (ii) a geometric next-best match feature to the first feature;

identifying, from any of the features in the second image, a global best match feature to the first feature;

performing a first comparison of the measures of similarity determined for the geometric best match feature and for the global best match feature, with respect to a first threshold;

performing a second comparison of the measures of similarity determined for the geometric best match feature and for the geometric next-best match feature, with respect to a second threshold; and

in dependence on whether the first and second thresholds are satisfied, selecting the geometric best match feature in the second image as an output match to the first feature in the first image.