Systems and methods for matching scenes using mutual relations between features

• US 9,449,431 B2
• Filed: 06/11/2015
• Issued: 09/20/2016
• Est. Priority Date: 12/22/2009
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Kotaba, Ondrej, Lukas, Jan
• Primary Examiner(s): To, Tuan C.
• Assistant Examiner(s): SMITH, ISAAC G
• Application Number:
  US14/736,738
• Publication Number:
  US 20150279099A1
• Time in Patent Office: 467 Days
• Field of Search: 701/523, 701/28
• US Class Current: 1/1
• 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 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;

defines a first descriptive subset of features, including at least one minimal subset, from a feature set A extracted by at least one processor from a first image projection,

selects at least two second descriptive subsets from a feature set B extracted by the at least one processor from a second image projection, the at least two second descriptive subsets correlated to at least two minimal subsets, which meet a congruency criteria with the first descriptive subset of features from the feature set A, wherein the at least two second descriptive subsets are selected based on a similarity of invariant mutual relations between features of one of the at least one minimal subset in the first descriptive subset and invariant mutual relations between features of the at least two minimal subsets in the at least two second descriptive subsets, wherein the first descriptive subset and the at least two second descriptive subsets define at least two pairs of similar descriptive subsets,

calculates at the at least one processor a transformation T from at least one of the at least two pairs of similar descriptive subsets to form a hypothesis H,

evaluates at the at least one processor a quality of the hypothesis H,

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

selects a final hypothesis H_B having a high quality as determined by a quality metric, the method further comprising at least one of;

determining coordinates for a new position by applying the transformation T belonging to the selected final hypothesis H_B to coordinates in a navigation frame; and

generating a map in the memory device for navigating a vehicle, the map based on matching features from the first image projection with the second image projection.

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

3. The navigation system of claim 1, wherein the processor:

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

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

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

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

4. The navigation system of claim 1, wherein the processor determines a distance to an object based on a best transformation T_B and plurality of paired features that support the final hypothesis H_B.

5. The navigation system of claim 1, wherein the processor

determines a number n of features to include in the first descriptive subset based on:

a type of projection utilized in the image capturing device 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.

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

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

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

a memory for storing the feature set A and the feature set B;

a second process for feature matching, the second process including;

defines a first descriptive subset of features, including at least one minimal subset, from the feature set A extracted,

selects at least two second descriptive subsets from the feature set B, the at least two second descriptive subsets correlated to at least two minimal subsets, which meet a congruency criteria with the first descriptive subset of features from the feature set A, wherein the at least two second descriptive subsets are selected based on a similarity of invariant mutual relations between features of one of the at least one minimal subset in the first descriptive subset and invariant mutual relations between features of the at least two minimal subsets in the at least two second descriptive subsets, wherein the first descriptive subset and the at least two second descriptive subsets define at least two pairs of similar descriptive subsets,

calculates at the at least one processor a transformation T from at least one of the at least two pairs of similar descriptive subsets to form a hypothesis H,

evaluates at the at least one processor a quality of the hypothesis H,

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

selects a final hypothesis H_B having a high quality as determined by a quality metric, the method further comprising at least one of;

determining coordinates for a new position by applying the transformation T belonging to the selected final hypothesis H_B to coordinates in a navigation frame; and

generating a map in the memory device for navigating a vehicle, the map based on matching features from the first image projection with the second image projection.

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

9. The processor of claim 7, wherein the feature set A and the feature set B 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.