Recent Patents in Signal Processing (December 2016) – Point Cloud Processing

For our December 2016 issue, we cover recent patents dealing with point cloud processing, including point cloud segmentation, mesh generation, point cloud registration and object separation.

In patent no 9,508,186 a method, apparatus, system, and computer readable storage medium provide the ability to pre-segment point cloud data. Point cloud data is obtained and segmented. The segment information is stored. An indexing structure is created and instantiated with the point cloud data and the segment information. Based on the segment information, a determination is made regarding points needed for shape extraction. Needed points are fetched from the indexing structure and used to extract shapes. The extracted shapes are used to cull points from the point cloud data.

In patent no. 9,412,040 a method extracts planes from three-dimensional (3D) points by first partitioning the 3D points into disjoint regions. A graph of nodes and edges is then constructed, wherein the nodes represent the regions and the edges represent neighborhood relationships of the regions. Finally, agglomerative hierarchical clustering is applied to the graph to merge regions belonging to the same plane.

In the embodiment no. 9,406,138, a technique is provided for semi-automatically extracting a polyline from a linear feature in a point cloud. The user may provide initial parameters, including a point about the linear feature and a starting direction. A linear feature extraction process may automatically follow the linear feature beginning in the starting direction from about the selected point. The linear feature extraction process may attempt to follow a linear segment of the linear feature. If some points may be followed that constitute a linear segment, a line segment modeling the linear segment is created. The linear feature extraction process then determines whether the end of the linear feature has been reached. If the end has not been reached, the linear feature extraction process may repeat. If the end has been reached, the linear feature extraction process may return the line segments and create a polyline from them.

In the patent no. 9,355,462 a system and method of estimation motion of a machine is disclosed. The method may include determining a first point cloud and a second point cloud corresponding to an environment in a vicinity of the machine. The method may further include generating a first extended gaussian image (EGI) for the first point cloud and a second EGI for the second point cloud. The method may further include determining a first EGI segment based on the first EGI and a second EGI segment based on the second EGI. The method may further include determining a first two dimensional distribution for points in the first EGI segment and a second two dimensional distribution for points in the second EGI segment. The method may further include estimating motion of the machine based on the first and second two dimensional distributions.

Invention no. 9,292,961 presents a method for detecting an opening in a structure represented by a three-dimensional point cloud, which may include the steps of: (1) creating a three-dimensional point cloud map of a scene, the three-dimensional point cloud map including a plurality of points representing a ground plane and the structure upon the ground plane, (2) identifying an absence of points within the plurality of points representing the structure, and (3) determining whether the absence of points represents the opening in the structure.

In patent no. 9,265,434 3-dimensional cardiac reconstruction is carried out by catheterizing a heart using a probe with a mapping electrode, and acquiring electrical data from respective locations in regions of interest in the heart, representing the locations of the electrical data as a point cloud, reconstructing a model of the heart from the point cloud, applying a set of filters to the model to produce a filtered volume, segmenting the filtered volume to define components of the heart, and reporting the segmented filtered volume.

In patent no. 9,251,399 a method of separating an object in a three dimension point cloud is presented, including acquiring a three dimension point cloud image on an object using an image acquirer, eliminating an outlier from the three dimension point cloud image using a controller, eliminating a plane surface area from the three dimension point cloud image, of which the outlier has been eliminated using the controller, and clustering points of an individual object from the three dimension point cloud image, of which the plane surface area has been eliminated using the controller.

If you have an interesting patent to share when we next feature patents related to point cloud processing, or if you are especially interested in a signal processing research field that you would want to be highlighted in this section, please send email to Csaba Benedek (benedek.csaba AT sztaki DOT mta DOT hu).

References

Number: 9,508,186
Title:  Pre-segment point cloud data to run real-time shape extraction faster
Inventors: Poelman; Ronald (San Rafael, CA), Akman; Oytun (Kensington, CA)
Issued: November 29, 2016
Assignee: Autodesk, Inc. (San Rafael, CA)

Number: 9,412,040
Title:  Method for extracting planes from 3D point cloud sensor data
Inventors: Feng; Chen (Ann Arbor, MI), Taguchi; Yuichi (Arlington, MA), Kamat; Vineet (Cambridge, MA)
Issued: August 9, 2016
Assignee: Mitsubishi Electric Research Laboratories, Inc. (Cambridge, MA)

Number: 9,406,138
Title:  Semi-automatic polyline extraction from point cloud
Inventors: St-Pierre; Mathieu (Ste-Brigitte De Laval, CA)
Issued: August 2, 2016
Assignee: Bentley Systems, Incorporated (Exton, PA)

Number: 9,355,462
Title:  Motion estimation system utilizing point cloud registration
Inventors: Chen; Qi (Dunlap, IL)
Issued: May 31, 2016
Assignee: Caterpillar Inc. (Peoria, IL)

Number: 9,292,961
Title:  System and method for detecting a structural opening in a three dimensional point cloud
Inventors: Korchev; Dmitriy V. (Irvine, CA), Zhang; Zhiqi (Santa Clara, CA), Owechko; Yuri (Newbury Park, CA)
Issued: March 22, 2016
Assignee: The Boeing Company (Chicago, IL)

Number: 9,265,434
Title:  Dynamic feature rich anatomical reconstruction from a point cloud
Inventors: Merschon; Asaf (Karkur, IL), Massarwa; Fady (Baka El Gharbiya, IL)
Issued: February 23, 2016
Assignee: Biosense Webster (Israel) Ltd. (Yokneam, Il)

Number: 9,251,399
Title:  Method of separating object in three dimension point cloud
Inventors: Hwang; Hyo Seok (Seoul, KR), Roh; Kyung Shik (Seongnam-si, KR), Yoon; Suk June (Seoul, KR)
Issued: February 2, 2016
Assignee: Samsung Electronics Co., Ltd. (Gyeonggi-Do, KR)