SYSTEMS AND METHODS FOR MATCHING SCENES USING MUTUAL RELATIONS BETWEEN FEATURES

• US 20110153206A1
• Filed: 12/22/2009
• Published: 06/23/2011
• Est. Priority Date: 12/22/2009
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Lukas, Jan, Kotaba, Ondrej
• Granted Patent: US 9,091,553 B2
• Time in Patent Office: Days
• US Class Current: 701/208
• CPC Class Codes: G01C 21/3804 Creation or updating of map data
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 19/003 Navigation within 3D models or images
• CPC Class Codes: G06T 2207/10004 Still image; Photographic image
• CPC Class Codes: G06T 2207/30252 Vehicle exterior; Vicinity of vehicle
• CPC Class Codes: G06T 7/33 using feature-based methods
• CPC Class Codes: G06T 7/35 using statistical methods
• CPC Class Codes: G06T 7/73 using feature-based methods
• CPC Class Codes: G06T 7/74 involving reference images or patches
• CPC Class Codes: G06V 20/58 Recognition of moving objects or obstacles, e.g. vehicles or pedestrians; Recognition of traffic objects, e.g. traffic signs, traffic lights or roads

Abstract

Embodiments of the present invention provide improved systems and methods for matching scenes. In one embodiment, a processor for implementing robust feature matching between images comprises: a first process for extracting a first feature set from a first image projection and extracting a second feature set from a second image projection; a memory for storing the first feature set and the second feature set; and a second process for feature matching using invariant mutual relations between features of the first feature set and the second feature set; wherein the second feature set is selected from the second image projection based on the identification of similar descriptive subsets between the second image projection and the first image projection.

Claims

1. A computer readable media device having computer-executable instructions for a method for matching image features, the method comprising:

defining a first descriptive subset of features from a feature set A extracted from a first image projection;

selecting a second descriptive subset from a feature set B extracted from a second image projection, wherein the second descriptive subset is selected based on a similarity of invariant mutual relations between features of the first descriptive subset and invariant mutual relations between features of the second descriptive subset, wherein the first descriptive subset and the second descriptive subset define a pair of similar descriptive subsets;

calculating a transformation T from the pair of similar descriptive subsets to form a hypothesis H;

evaluating a quality of the hypothesis H;

storing the hypothesis H into a memory device, the hypothesis H including transformation T and a plurality of paired features that support the hypothesis H.

2. The computer readable media device of claim 1, the method further comprising:

defining a plurality of descriptive subsets of features from the feature set A;

for each of the plurality of descriptive subsets from the feature set A, selecting at least one descriptive subset from feature set B based on a similarity of invariant mutual relations between features to form a plurality of similar descriptive subset pairs;

calculating a hypothetic transformation T for each of the plurality of similar descriptive subset pairs to form at least one hypothesis H;

selecting a final hypothesis H_B having a highest quality as determined by a quality metric; and

storing into memory a plurality of paired features that support the final hypothesis H_B, where this plurality of paired features each include a feature from the feature set A and a feature from the feature set B.

3. The computer readable media device of claim 2, the method further comprising determining a distance to and object based on a best transformation T_B and plurality of paired features that support the final hypothesis H_B.

4. The computer readable media device of claim 1, the method further comprising:

determining a number n of features to include in the first descriptive subset based on a type of projection utilized in an image sensor to generate the first image projection from a real-world scene; and

an anticipated transformation undergone between the first image projection and the second image projection.

5. The computer readable media device of claim 1, wherein selecting a second descriptive subset from a feature set B extracted from a second image projection is performed on a pre-filtered data set of descriptive relations.

6. The computer readable media device of claim 1, wherein the invariant mutual relations between features include at least one of a set of invariant mutual relations including a distance, an area, an angle, a solid angle, a volume, a generalized area or volume to higher dimensions, a central moment or a histogram.

7. The computer readable media device of claim 1, wherein similarity is determined by estimating using one or both of variances and co-variance of invariant properties.

8. The computer readable media device of claim 1, wherein selection of the first descriptive subset is based on one of a random, a pseudorandom, a quasi-random or a deterministic process.

9. The computer readable media device of claim 1, the method further comprising calculating a solution for transformation T from a plurality of paired features that support a final hypothesis H_B using an over determined system parameter estimator.

10. A navigation system for a vehicle, the navigation system comprising:

an image capturing device that produces projections of surrounding scenes;

a processor coupled to the image capturing device, the processor having a process for robust feature matching using invariant mutual relations between features; and

a memory coupled to the processor;

wherein the processor matches at least a descriptive subset of features extracted from a first projection with features from a second projection based on a similarity of invariant mutual relations between features of the at least a descriptive subset from the first projection and the selected features from the second projection;

wherein the processor estimates at least one hypothetic transformation T from the at least a descriptive subset of features extracted from the first projection and the selected features from the second projection;

wherein the processor stores at least one hypothesis H into the memory; and

wherein the processor performs a quality analysis of a plurality of hypotheses H to select a final hypothesis H_B that includes a final transformation T_B.

11. The navigation system of claim 10, wherein the processor obtains at least one of the first projection and the second projection from projections captured by the image capturing device.

12. The navigation system of claim 10, wherein the processor generates a plurality of paired features based on the at least one hypothesis H and stores the plurality of paired features into the memory.

13. The navigation system of claim 10, wherein the processor generates a map in the memory for navigating the vehicle, the map based on matching images from the first projection with the second projection.

14. The navigation system of claim 10, wherein the processor, using a map of features stored in the memory, calculates a match between features from a captured image and features in the map;

and

wherein the processor defines a vehicle position in a navigation reference from the final hypothesis H_B.

15. The navigation system of claim 10, wherein the similarity of invariant mutual relations between features is based on a geometric congruency.

16. A processor for implementing robust feature matching between images, the processor comprising:

a first process for extracting a first feature set from a first image projection and extracting a second feature set from a second image projection;

a memory for storing the first feature set and the second feature set;

a second process for feature matching using invariant mutual relations between features of the first feature set and the second feature set;

wherein the second feature set is selected from the second image projection based on the identification of similar descriptive subsets between the second image projection and the first image projection.

17. The processor of claim 16, wherein the second process selects a first descriptive subset of features from the first feature set and selects a second descriptive subset of features from the second feature set, the second descriptive subset having similar invariant mutual relations between features as the first descriptive subset.

18. The processor of claim 16, wherein the second process pre-processes one or both of the first feature set and the second feature set into a feature table sorted such that invariant mutual relations representing a greatest differential for a selected characteristic appear first in the feature table.

19. The processor of claim 16, wherein the second process selects a plurality of descriptive subsets of features from the first feature set and for each of the plurality of descriptive subsets from the first feature set, the second process selects at least one descriptive subset from the second feature set based on a similarity of invariant mutual relations between features to form a plurality of similar descriptive subset pairs;

wherein the second process calculates a hypothetic transformation T for each of the plurality of similar descriptive subset pairs and stores into the memory a final hypotheses H_B having a highest quality as determined by a quality metric.

20. The processor of claim 16, wherein the first feature set and the second feature set include planar features with invariant mutual relations including angles between normal vectors of the planar features;

and

wherein the similar descriptive subsets are based on minimal subsets of three features.