Systems and methods for 3D data based navigation using descriptor vectors

• US 9,153,067 B2
• Filed: 01/21/2013
• Issued: 10/06/2015
• Est. Priority Date: 01/21/2013
• Status: Active Grant

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Dobes, Michal, Lukas, Jan, Ma, Yunqian
• Primary Examiner(s): Alavi, Amir
• Application Number:
  US13/745,892
• Publication Number:
  US 20140204081A1
• Time in Patent Office: 988 Days
• US Class Current: 1/1
• CPC Class Codes: G06T 15/10 Geometric effects
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2207/20152 Watershed segmentation
• CPC Class Codes: G06T 2207/30252 Vehicle exterior; Vicinity of vehicle
• CPC Class Codes: G06T 7/248 involving reference images or patches

Abstract

Systems and methods for 3D data based navigation using descriptor vectors are provided. In at least one embodiment, a method for identifying corresponding segments in different frames of data comprises identifying a first segment set in a first frame in multiple frames acquired by at least one sensor, and identifying a second segment set in a second frame in the multiple frames. The method also comprises calculating a first and second set of descriptor vectors, wherein the first and second sets of descriptor vectors comprise a descriptor vector for each segment in the respective first and second segment set, wherein a descriptor vector describes an indexed plurality of characteristics; and identifying corresponding segments by comparing the first set of descriptor vectors against the second set of descriptor vectors, wherein the corresponding segments describe characteristics of the same feature in the environment.

Claims

1. A system for identifying corresponding segments in different 3D data frames, the system comprising:

at least one 3D data sensor configured to acquire a plurality of frames of data from an environment containing the at least one 3D data sensor, wherein the plurality of frames of data provide three-dimensional range and image information of a portion of the environment;

a processing unit configured to receive the plurality of frames of data from the sensor, wherein the processing unit is configured to;

identify a first segment set in a first frame of data in the plurality of frames of data, wherein the first segment set includes segments identified through segmentation of the first frame of data;

identify a second segment set in a second frame of data in the plurality of frames of data, wherein the second segment set includes segments identified through segmentation of the second frame of data;

calculate a first set of descriptor vectors, wherein the first set of descriptor vectors comprises a descriptor vector for each segment in the first segment set, wherein a descriptor vector describes a plurality of segment characteristics, wherein each characteristic is indexed within the descriptor vector;

calculate a second set of descriptor vectors, wherein the second set of descriptor vectors comprises a descriptor vector for each segment in the second segment set; and

identify a set of corresponding segments by comparing the first set of descriptor vectors against the second set of descriptor vectors, wherein corresponding segments describe at least one characteristic of the same feature in the environment.

2. The system of claim 1, wherein the first frame of data and the second frame of data are acquired at different times.

3. The system of claim 1, wherein the processing unit compares a first descriptor vector in the first set of descriptor vectors against a second descriptor vector in the second set of descriptor vectors by correlating descriptor vectors with one another using the plurality of characteristics in the correlated descriptor vectors.

4. The system of claim 3, wherein the processing unit determines that the first descriptor vector corresponds to the second descriptor vector, wherein the first descriptor vector corresponds to the second descriptor vector when the correlation of the first descriptor vector with the second descriptor vector is greater than both the correlation of the first descriptor vector with descriptor vectors in the second set of descriptor vectors other than the second descriptor vector and the correlation of the second descriptor vector with the descriptor vectors in the first set of descriptor vectors other than the first descriptor vector.

5. The system of claim 1, wherein the processing unit compares a first descriptor vector in the first set of descriptor vectors against a second descriptor vector in the second set of descriptor vectors by calculating a sum of normalized differences between the first descriptor vector and the second vector, wherein the sum of normalized differences is a sum of absolute values of differences between characteristics in the descriptor vectors with respect to the sum of absolute values of the characteristics.

6. The system of claim 5, wherein the processing unit determines that the first descriptor vector, corresponds to the second descriptor vector, wherein the first descriptor vector corresponds to the second descriptor vector when the sum of normalized differences between the first descriptor vector and the second descriptor vector is less than both the sum of normalized differences between the first descriptor vector and descriptor vectors in the second set of descriptor vectors other than the second descriptor vector and the sum of normalized differences between the second descriptor vector and descriptor vectors in the first set of descriptor vectors other than the first descriptor vector.

7. The system of claim 1, wherein the processing unit is further configured to:

determine differences between corresponding segments including the differences in position and orientation; and

calculate motion information of the at least one sensor with respect to the environment based on the differences.

8. The system of claim 7, wherein the processing unit determines the motion of the at least one sensor to calculate a navigation solution for a navigation system.

9. The system of claim 1, wherein the at least one sensor is at least one of:

a LiDAR sensor;

at least two electro-optical sensors;

combination of electro-optical sensor with either LiDAR or radar sensor; and

a radar sensor.

10. A method for identifying corresponding segments in different frames of data, the method comprising:

identifying a first segment set in a first frame of data in a plurality of frames of data acquired by at least one sensor, wherein a frame of data provides three-dimensional range and image information from an environment of the at least one sensor, wherein the first segment set includes segments identified through segmentation of the first frame of data;

identifying a second segment set in a second frame of data in the plurality of frames of data, wherein the second segment set includes segments identified through segmentation of the second frame of data;

calculating a first set of descriptor vectors, wherein the first set of descriptor vectors comprises a descriptor vector for each segment in the first segment set, wherein a descriptor vector describes an indexed plurality of characteristics;

calculating a second set of descriptor vectors, wherein the second set of descriptor vectors comprises a descriptor vector for each segment in the second segment set; and

identifying a set of corresponding segments by comparing the first set of descriptor vectors against the second set of descriptor vectors, wherein corresponding segments describe at least one characteristic of the same feature in the environment.

11. The method of claim 10, wherein the first segment set and the second segment set are identified through a watershed algorithm.

12. The method of claim 10, wherein the first frame of data and the second frame of data are acquired at different times.

13. The method of claim 10, wherein identifying a set of corresponding vectors comprises comparing a first descriptor vector in the first set of descriptor vectors against a second descriptor vector in the second set of descriptor vectors by correlating the plurality of characteristics in the descriptor vectors with one another.

14. The method of claim 13, further comprising determining that the first descriptor vector corresponds to the second descriptor vector, wherein the first descriptor vector corresponds to the second descriptor vector when the correlation of the first descriptor vector with the second descriptor vector is greater than both the correlation of the first descriptor vector with descriptor vectors in the second set of descriptor vectors other than the second descriptor vector and the correlation of the second descriptor vector with descriptor vectors in the first set of descriptor vectors other than the first descriptor vector.

15. The method of claim 10, wherein identifying a set of corresponding vectors comprises comparing a first descriptor vector in the first set of descriptor vectors against a second descriptor vector in the second set of descriptor vectors by calculating the sum of normalized differences between the first descriptor vector and the second descriptor vector, wherein the sum of normalized differences is a sum of absolute values of differences between characteristics in the descriptor vectors with respect to the sum of absolute values of the characteristics.

16. The method of claim 15, further comprising determining that the first descriptor vector corresponds to the second descriptor vector, wherein the first descriptor vector corresponds to the second descriptor vector when the sum of normalized differences between the first descriptor vector and the second descriptor vector is less than both the sum of normalized differences between the first descriptor vector and descriptor vectors in the second set of descriptor vectors other than the second descriptor vector and the sum of normalized differences between the second descriptor vector and descriptor vectors in the first set of descriptor vectors other than the first descriptor vector.

17. The method of claim 10, further comprising:

determining differences between corresponding segments including their mutual positions and orientation; and

calculating motion information of the at least one sensor with respect to the environment based on the differences.

18. The method of claim 17, further comprising determining the motion of the at least one sensor to calculate a navigation solution for a navigation system.

19. The method of claim 18, further comprising computing the navigation solution to a human machine interface for display to a user.

20. A processor-readable medium comprising a plurality of instructions tangibly stored on a non-transitory storage medium for identifying corresponding segments in different frames of data, the instructions operable, when executed, to cause a processing unit to:

identifying a first segment set in a first frame of data in a plurality of frames of data acquired by at least one sensor, wherein a frame of data provides three-dimensional range and image information from an environment of the at least one sensor, wherein the first segment set includes segments identified through segmentation of the first frame of data;

identifying a second segment set in a second frame of data in the plurality of frames of data, wherein the second segment set includes segments identified through segmentation of the second frame of data;

calculating a first set of descriptor vectors, wherein the first set of descriptor vectors comprises a descriptor vector for each segment in the first segment set, wherein a descriptor vector describes an indexed plurality of characteristics;

calculating a second set of descriptor vectors, wherein the second set of descriptor vectors comprises a descriptor vector for each segment in the second segment set; and

identifying a set of corresponding segments by comparing the first set of descriptor vectors against the second set of descriptor vectors, wherein corresponding segments describe at least one characteristic of the same feature in the environment.