Three-dimentional plane panorama creation through hough-based line detection

• US 10,475,232 B2
• Filed: 11/16/2017
• Issued: 11/12/2019
• Est. Priority Date: 08/02/2012
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: HERE Global B.V. (Nokia Corporation)
• Inventors: Chon, Jaechoon
• Primary Examiner(s): Flora, Nurun N
• Application Number:
  US15/815,206
• Publication Number:
  US 20180089887A1
• Time in Patent Office: 726 Days
• Field of Search: None
• CPC Class Codes: G06T 15/08 Volume rendering
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 2200/08 involving all processing steps from image acquisition to 3D model generation
• CPC Class Codes: G06T 2207/10028 Range image; Depth image; 3D point clouds
• CPC Class Codes: G06T 2207/20061 Hough transform
• CPC Class Codes: G06T 2207/30184 Infrastructure
• CPC Class Codes: G06T 2210/56 Particle system, point based geometry or rendering
• CPC Class Codes: G06T 3/067 Reshaping or unfolding 3D tree structures onto 2D planes
• CPC Class Codes: G06T 3/12 Panospheric to cylindrical image transformations
• CPC Class Codes: G06T 7/33 using feature-based methods
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation

Abstract

A method for creating a plane panorama from point cloud data using Hough transformations is disclosed. The method involves converting the three-dimensional point cloud into a two-dimensional histogram with bins grouping neighboring points, and performing a Hough transformation on the histogram. The resulting transformed data is segmented and the method searches the segments iteratively for a major line, followed by lines that are orthogonal, diagonal, or parallel to the major line, and discards outlying data in each bin as lines are identified. The detected lines are connected to form planes, and the planes are assembled into a hole- and gap-filled panorama. The method may also use an algorithm such as a Random Sample Consensus (RANSAC) algorithm to detect a ground plane.

Claims

1. A method comprising:

detecting a ground plane in a three-dimensional point cloud;

applying a rotation matrix to the three-dimensional point cloud to change coordinate systems;

converting the three-dimensional point cloud to a two-dimensional histogram with bins grouping neighboring points in the three-dimensional point cloud;

performing a transformation on the two-dimensional histogram to segment into one or more segments, each segment including one or more of the bins;

identifying a road from the ground plane;

discarding lines inside of the road; and

assembling a plurality of lines to represent the road.

2. The method of claim 1, further comprising:

removing noise caused by neighboring points in each of the bins that do not lie along the initial major line of the plurality of lines.

3. The method of claim 2, further comprising:

detecting one or more related lines that are orthogonal, parallel or diagonal with respect to the initial major line.

4. The method of claim 3, further comprising:

choosing a largest one of the plurality of lines as a next major line, wherein one or more planes are assembled from at least the initial major line and the next major line.

5. The method of claim 1, wherein the three-dimensional point cloud is derived from two offset images.

6. The method of claim 1, wherein detecting the ground plane comprises:

performing a Random Sample Consensus (RANSAC) ground plane detection algorithm on the three-dimensional point cloud.

7. The method of claim 6, wherein the ground plane includes smallest height values from the three-dimensional point cloud.

8. The method of claim 1, wherein the rotational matrix converts the three-dimensional point cloud to a coordinate system for a global positioning system.

9. The method of claim 8, wherein the two-dimensional histogram is based on the coordinate system for a global positioning system.

10. The method of claim 1, further comprising:

constructing a three-dimensional plane panorama including the road.

11. The method of claim 10, further comprising:

performing one or both of gap or hole filling on the three-dimensional plane panorama including the road.

12. The method of claim 10, wherein converting the three-dimensional point cloud to the two-dimensional histogram further comprises discarding points in the three-dimensional point cloud that do not meet a predefined threshold.

13. An apparatus comprising:

at least one processor; and

at least one memory including computer program code for one or more programs, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform at least the following;

detecting a ground plane in a three-dimensional point cloud;

applying a rotation matrix to the three-dimensional point cloud to change coordinate systems;

converting the three-dimensional point cloud to a two-dimensional histogram with bins grouping neighboring points in the three-dimensional point cloud;

performing a transformation on the two-dimensional histogram to segment into one or more segments, each segment including one or more of the bins;

identifying a road from the ground plane;

discarding lines inside of the road; and

assembling a plurality of lines to represent the road.

14. The apparatus of claim 13, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform:

removing noise caused by neighboring points in each of the bins that do not lie along an initial major line of the plurality of lines.

15. The apparatus of claim 14, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform:

detecting one or more related lines that are orthogonal, parallel or diagonal with respect to the initial major line.

16. The apparatus of claim 13, wherein the three-dimensional point cloud is derived from two offset images.

17. The apparatus of claim 13, wherein the rotational matrix converts the three-dimensional point cloud to a coordinate system for a global positioning system.

18. A method comprising:

detecting a ground plane in a point cloud;

applying a rotation matrix to the three-dimensional point cloud to change coordinate systems;

converting the point cloud to a histogram with bins grouping neighboring points in the point cloud;

performing a transformation on the histogram to segment into one or more segments, each segment including one or more of the bins;

identifying a road from the ground plane;

discarding lines inside of the road;

assembling a plurality of lines including an initial major line to represent the road; and

constructing a plane panorama including the road.