THREE-DIMENSIONAL POINT PROCESSING AND MODEL GENERATION

[0001] This application claims the benefit of and is a continuation-in-part of U.S. application Ser. No. 13/833,078, filed Mar. 15, 2013 and claims the benefit of U.S. provisional application, 61/710,270 filed Oct. 5, 2012, each of which is herein incorporated by reference in its entirety.

[0002] The present invention relates to three-dimensional point processing and model generation of objects and more particularly to identification and modeling of pipe systems.

[0003] Computer modeling is currently a very time-consuming labor-intensive process. Many systems allow manual interaction to create surfaces and connections in an editing system (e.g., Maya, 3DS). Higher level interaction can be used to increase productivity (e.g., CloudWorx, AutoCAD), but human interaction is typically required to build a model. More recently, automatic systems have been introduced, but these have limitations on the types of structure they can model. In the case of aerial LiDAR (Light Detection And Ranging), systems have been developed to model buildings and ground terrain, Ground-based LiDAR scans can be processed to model simple geometry such as planar surfaces and pipes. A general scan, however, often contains objects that have specific shapes and function. Specifically, in industrial scans, while pipes are prevalent, their junctions may be complex, and pipes often connect to valves, pumps, tanks and instrumentation. Typical systems do not provide a capability to detect and model both simple primitive shapes such as cylinder and planar structure, as well as, general shaped objects such as valves, pumps, tanks, instrumentation and/or the interconnections between them. The creation of accurate and complex computer models may have application in the creation of three-dimensional virtual environments for training in various industries including the oil and gas industry.

[0004] A method for three-dimensional point processing and model generation includes providing data comprising a three-dimensional point cloud representing a scene, the three-dimensional point cloud comprising a plurality of points arrayed in three dimensions, applying a primitive extraction to the data to associate primitive shapes with points within the three-dimensional point cloud, the primitive extraction comprising, estimating normal vectors for the three-dimensional point cloud, projecting the estimated normal vectors onto a Gaussian sphere for the three-dimensional point cloud, detecting and eliminating point-clusters corresponding to planar areas of the three-dimensional point cloud to obtain a residual Gaussian sphere, detecting great-circle patterns on the residual Gaussian sphere to produce a segmented point cloud, projecting each segment of the segmented point cloud onto respective planes to produce respective two-dimensional point clouds, detecting circle patterns in each two-dimensional point cloud, and processing the circle patterns to determine cylinder parameters for each of a plurality of candidate cylinders, and assembling the candidate cylinders into a three-dimensional surface model of the scene,

[0005] A system for three-dimensional point processing and model generation includes a database configured to store data comprising a scan of a scene comprising a point cloud, the point cloud comprising a plurality of points, a computer processer configured to receive the stored data from the database, and to execute software responsive to the stored data, and a software program executable on the computer processer, the software program containing computer readable software instructions which when executed perform a for three-dimensional point processing and model generation, including providing data comprising a three-dimensional point cloud representing a scene, the three-dimensional point cloud comprising a plurality of points arrayed in three dimensions, applying a primitive extraction to the data to associate primitive shapes with points within the three-dimensional point cloud, the primitive extraction comprising, estimating normal vectors for the three-dimensional point cloud, projecting the estimated normal vectors onto a Gaussian sphere for the three-dimensional point cloud, detecting and eliminating point-clusters corresponding to planar areas of the three-dimensional point cloud to obtain a residual Gaussian sphere, detecting great-circle patterns on the residual Gaussian sphere to produce a segmented point cloud, projecting each segment of the segmented point cloud onto respective planes to produce respective two-dimensional point clouds, detecting circle patterns in each two-dimensional point cloud, and processing the circle patterns to determine cylinder parameters for each of a plurality of candidate cylinders, and assembling the candidate cylinders into a three-dimensional surface model of the scene.

[0006] A non-transitory processor readable medium containing computer readable software instructions used for three-dimensional point processing and model generation including providing data comprising a three-dimensional point cloud representing a scene, the three-dimensional point cloud comprising a plurality of points arrayed in three dimensions, applying a primitive extraction to the data to associate primitive shapes with points within the three-dimensional point cloud, the primitive extraction comprising, estimating normal vectors for the three-dimensional point cloud, projecting the estimated normal vectors onto a Gaussian sphere for the three-dimensional point cloud, detecting and eliminating point-clusters corresponding to planar areas of the three-dimensional point cloud to obtain a residual Gaussian sphere, detecting great-circle patterns on the residual Gaussian sphere to produce a segmented point cloud, projecting each segment of the segmented point cloud onto respective planes to produce respective two-dimensional point clouds, detecting circle patterns in each two-dimensional point cloud, and processing the circle patterns to determine cylinder parameters for each of a plurality of candidate cylinders, and assembling the candidate cylinders into a three-dimensional surface model of the scene.

[0021] Embodiments of this disclosure relate to the fields of three-dimensional (3D) point processing and 3D model construction. As will be described, a system, method, and computer program product are disclosed for generating a 3D Computer-Aided Design (CAD) model of a scene from a 3D point cloud. As used herein, a point cloud refers to a data array of coordinates in a specified coordinate system. In a three-dimensional (3D) point cloud, the data array contains 3D coordinates. Point clouds may contain 3D coordinates of visible surface points of the scene. Point clouds obtained by any suitable methods or devices as understood by the skilled artisan may be used as input. For example, point clouds could be obtained from 3D laser scanners (e.g., LiDAR) or from image-based methods. 3D point clouds can be created from a single scan or viewpoint, or plurality of scans or viewpoints. The 3D model that is created includes 3D polygons or other mathematical 3D surface representations. In addition, the created model can contain metadata describing the modeled parts, their specific parameters or attributes, and their connectivity. Such data is normally created and contained within hand-made CAD models and their data files.

[0022] Embodiments of this disclosure process a scene point cloud and determine a solution to an inverse-function. This solution determines what objects are in the scene to create a given point cloud. As will be described, two processes may be used to compute the inverse function solution. The first is a primitive extraction process that finds evidence of cylinder and planar geometry in the scene and estimates models and parameters to fit the evidence. The second process is a part matching process that matches clusters of 3D points to 3D models of parts stored in a part library. The part located which best batches the point cloud, and that part's associated polygon model, is then used to represent the point cluster. Iterations of primitive extraction and part matching processes are invoked to complete a 3D model for a complex scene consisting of a plurality of planes, cylinders, and complex parts, such as those contained in the parts library. The connecting regions between primitives and/or parts are processed to determine the existence and type of connection joint. Constraints can be imposed on orientations and connections to ensure a fully connected model and alignment of its component primitives, parts, and joints.

[0023] Embodiments of this disclosure create a 3D CAD model of a scene from a 3D point cloud. Point clouds will contain 3D coordinates of visible surface points of the scene. Any 3D point cloud can be used as input. For example, point clouds could be obtained from 3D laser scanners (e.g., LiDAR) or from image-based methods. 3D point clouds can be created from a single scan or viewpoint, or plurality of scans or viewpoints.

[0024] In embodiments, the generated model may be used to, for example, create CAD models of a plant, such as an oil and gas facility, or to update an existing CAD model. Oil and gas, or more generally hydrocarbon, facilities of interest may be, for example, exploration and production platforms which may be either land or ocean based, facilities including pipelines, terminals, storage facilities, and refining facilities.

[0025] During a construction operation, such models may be used to verify construction progress and to compare against selected milestones. The construction may be checked against an existing model to ensure that construction is proceeding in accordance with the building plan. Additionally, information determined regarding construction progress may be passed to supply chain processes, for example to create or verify orders for additional construction materials.

[0026] In an embodiment, the generated model may be used to determine whether there is space for potential new equipment or facilities to be added to an existing plant. Likewise, the model may be used to determine whether there is available access to maintain, replace, or augment equipment already in place.

[0027] Embodiments of this disclosure process a scene point cloud and determines what objects are in a scene to create a given point cloud. A primitive extraction process finds evidence of cylinder and planar geometry (e.g., primitive geometries and/or shapes) in the scene and estimates models and parameters to fit the evidence. A 3D part matching process matches clusters of points to models of parts stored in a part library to locate the best matching part and use its polygon model to represent the point cluster. Iterations of the primitive extraction and part matching processes are invoked to complete a 3D model for a complex scene consisting of a plurality of planes, cylinders, and complex parts, such as those contained in the parts library. The connecting regions between primitives and/or parts are processed to determine the existence and type of joint connection. Constraints can be imposed on positions, orientations and connections to ensure a fully connected model and alignment of its component primitives, parts, and joints.

[0028] In an embodiment, 3D points are processed as input (i.e., it is possible to proceed without use of any 2D imagery). Primitive shapes (e.g., cylinders and planes) are detected by an automated global analysis. There is no need for manual interaction, local feature detection, or fitting to key points. 3D matching methods are used to automatically match entire clusters of points to a library of parts that are potentially in the scene. The best match determines which one more part models are used to represent the cluster. By matching library parts to entire point clusters, there is no need for constructing the 3D part model by connecting or fitting surfaces to input points. In addition, all the part attributes in the part library are included with the output model.

[0029] The modeling system may contain optional components to enhance and extend its functions. For example, connectivity and constraints can be enforced and stored with the model in the final modeling stage where primitives and matched parts are connected with joints. In embodiments, a virtual scanner can accept CAD models as input and compute surface points. This allows CAD models to be imported to the matching database. In embodiments, a point part editor allows users to interactively isolate regions of a point cloud and store them in the matching database for object matching. In embodiments, a parts editor and database manager allows users to interactively browse the matching database and edit its contents. This also provides import capability from external systems with additional data about parts in the database. In embodiments, a modeling editing and export function allows users to view a model and interactively edit it using traditional edit functions such as select, copy, paste, delete, insert (e.g., Maya, 3DS, AutoCAD) and output the model in standard formats such as Collada, KML, VRML, or AutoCAD.

[0030] FIG. 1 shows a flow diagram of 3D point processing and 3D model construction according to an embodiment. Dark shaded boxes denote data that is passed from one function to another. Light shaded boxes denote the processing functions that operate on an input data and produce an output data.

[0031] The input Point Cloud (100) may be a data array of 3D coordinates in a specified coordinate system. These points can be obtained from LiDAR or other sensor systems known to those skilled in the art. These points convey surface points in a scene. They can be presented in any file format, including Log ASCII Standard (LAS), or X,Y,Z, file formats. The coordinate system may be earth-based, such as global positioning system (GPS) or Universal Transverse Mercator (UTM), or any other system defining an origin and axes in three-space. When several scans are available, their transformations to a common coordinate system can be performed. Additional data per-point may also be available, such as intensity, color, time, etc.

[0032] Primitive Extraction (110) is the process that examines the point cloud to determine whether it contains points suggesting the presence of planes or cylinders. FIG. 2 shows an example of Primitive Extraction (110) process in detail. Normal vectors are computed for each data point. For example, this can be performed using a method such as that taught in Pauly, M., “Point Primitives for Interactive Modeling and Processing of 3D Geometry,” Hartung-Gorre (2003), which is incorporated herein by reference in its entirety. The normals are projected onto the Gaussian sphere at step (111). For example, this can be performed using a method such as that taught in J. Chen and B. Chen, “Architectural Modeling from Sparsely Scanned Range Data,” IJCV, 78(2-3):223-236, 2008, which is incorporated herein by reference in its entirety. Circles indicate cylinders and point-clusters indicate planar surfaces are present. Then, these two kinds of primitives are detected separately, at steps (112-116) and steps (117-119 and 121-122). A determination may be made at step (112) regarding whether all point-clusters have been detected, and if no, one of them may be picked at step (113). In an embodiment, the point-clusters can be detected by an algorithm. For example, a Mean-shift algorithm, which is taught in Comaniciu, D., Meer, P., “Mean Shift: A Robust Approach Toward Feature Space Analysis.” Pattern Analysis and Machine Intelligence, IEEE Transactions on 24 (2002) 603-619, and incorporated herein by reference in its entirety, can be used. Each point in this cluster is examined at steps (114-116), where points belonging to the same plane are extracted and their convex hull is calculated and added to the detected planes. Cylinders may be detected in a similar manner at steps (117-119, 121-122). In an embodiment, detection of circles on the Gaussian sphere may be based on a Random Sample Consensus (RANSAC) process at step 117. The RANSAC process is taught in Fischler, M., Bolles, R., “Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography,” Communications of the ACM 24 (1981) 381-395, and is incorporated herein by reference in its entirety. When a circle is selected at step 118, its points may be checked and all points belonging to the same cylinder may be extracted. Then, the information of the cylinder may be calculated and added to detected cylinders at step 122.

[0033] Residual Point Cloud (120) contains points that are not part of the detected Primitives. They are passed to the clustering algorithm (130) for grouping by proximity.

[0034] Point Cloud Clustering (130) is performed on the Residual Point Cloud (120). This process is described in FIG. 3 and it determines the membership of points to clusters. Each point is assigned to a cluster based on its proximity to other cluster members. For example, this process determines the membership of points to clusters and can be based on “R. B. Rusu, “Semantic 3D Object Maps for Everyday Manipulation in Human Living Environments,” Ph.D. dissertation, Computer Science department, Technische Universität München, Germany, October 2009,” which is incorporated herein by reference in its entirety. Each point is assigned to a cluster based on its proximity to other cluster members. Specifically, two points with Euclidean distance smaller than the threshold d_th will be assigned to the same cluster. The process starts with step (131) where a determination is made regarding whether all points have been checked. As long as not all points are visited, one of the unvisited points is randomly selected as the seed (denoted as p) at step (132). The process of finding a cluster from the seed p is called the flood-fill algorithm, which begins at step (133), where a queue (denoted as Q) is set up with the only element p. Another empty queue (denoted as C) is also set up to keep track of the detected cluster. A determination is made on whether Q is empty at step (134). As long as Q is not empty, the cluster C can be expanded. The first element of Q (denoted as q) is removed from Q and added to C at step (135). Next, neighbors of q (denoted as P_q) in a sphere with radius r<d_th is searched at step (136), and all the unchecked points in P_q are added to Q at step (137) and are simultaneously marked as “checked”. This process is iterated until Q is empty, where a cluster C is said to be found and added to the set Clusters, at step (138). After all the points are checked, all the clusters are found and each point is assigned to exactly one cluster. These clusters, as well as their associated bounding boxes calculated at step (139), are output as Point Cloud Clusters (140).

[0035] Point Cloud Clusters (140) are sets of points that form clusters based on their proximity. Each cluster of points has an associated bounding box. For example, a pump may be in line with two pipes. Once the pipes are discovered and modeled in the Primitive Extraction (110) process, the pipe points are removed, leaving the Residual Point Cloud (120) with only the points on the pump surface. The Point Cloud Clustering (130) process discovers that these points are proximate to each other and groups them into a cluster with a bounding box. The bounded cluster of pump points is added to the Point Cloud Cluster (140) data. Depending on the scanned scene, there may be zero, one, or many clusters in the Point Cloud Cluster (140) data.

[0036] Part Matching (150) can be implemented in many ways. Two methods that can be used are described below; however, one skilled in the art will appreciate that other methods or variations of these methods are possible. In one embodiment according to a first method of matching, an entire part in the Parts Library (230) to a region in the point cloud using a classifier. The method makes use of the Parts Library (230), and when a suitable match is found the matched-points are removed from the Point Cloud Clusters (140). The output of Matched Parts (160) is a 3D surface part model in a suitable representation such as polygons or non-uniform rational basis splines (NURBS) along with their location and orientation in the model coordinate system.

[0037] A classifier-based implementation of Part Matching (150) is described here and shown in FIG. 4. The inputs to the Part Matching process are the Point Cloud Clusters (140), which contain points that were not identified as primitive shapes (cylinders or planes) during earlier processing. The Parts Library (230) data includes a polygon model and a corresponding point cloud for each part. The coordinate axes of the polygon models and point clouds are the same, or a transformation between them is known.

[0038] Each library part in the Part Library (230) has a part detector (151) obtained from a training module (152). The detector consists of N weak classifier c_i (default N=20), each with a weight α_i. Each weak classifier evaluates a candidate part (point clouds within the current search window), and returns a binary decision (1 if it's identified as positive, 0 if not). Each weak classifier is based on a Haar feature, such as taught in P. Viola and M, Jones, “Rapid Object Detection using a Boosted Cascade of Simple Features,” Proceedings of CVPR, 1: I-511-I-518, 2001, and incorporated herein by reference in its entirety, whose value is the sum of pixels in half the region minus the sum in the other half. In two dimensions, a Haar feature may be used to extract an object's boundary, as that is the portion that tends to be distinctive in an object. Similarly, 3D Haar-like features may extract three dimensional object boundaries. Alternately, a set of binary occupancy features may be used instead of Haar-like features. The method may generally be applied to a variety of more or less complex local features with success.

[0039] The final part detector (151), or strong classifier, is a combination of all weighted weak classifiers, producing an evaluation of the candidate part as Σ_iα_ic_i. The weighted sum is then compared to a predetermined threshold t (=0.5 Σ_iα_i by default) to determine whether the candidate part is a positive match. The threshold test Σ_iα_ic_i−t is also used to estimate a detection confidence.

[0040] Pre-processing (153) may be employed before training the classifier. The candidate point cloud may first be converted to volumetric data or a 3D image of voxels. Each voxel in the converted 3D image corresponds to a grid-like subset of the original point cloud. The intensity value of each voxel equals the number of points within it, and coordinate information of each point may be discarded. To smooth any bordering effect due to the grid conversion, each point in the point cloud may be made to contribute to more than one voxel through interpolation (e.g., linear interpolation). In one embodiment, each grid may be set to approximately 1/100 of the average object size. As will be appreciated, the grid size may be increased or decreased depending on the particular application. The 3D image is further processed as a 3D integral image, also known as a summed-area table, which is used to the compute sum of values in a rectangular subset of voxels in constant time. An example of summed-area tables are taught in “F. Crow. Summed-area tables for texture mapping. Proceedings of SIGGRAPH, 18(3): 207-212, 1984,” which is incorporated herein by reference in its entirety.

[0041] In an embodiment, the 3D integral image is made up of 3D rectangular features, such as Haar-like features. As known to those of skill in the art, Haar-like features, which in this context may be features in which a feature value is a normalized difference between the sum of voxels in a bright area and a sum of voxels in a shaded area. In this approach, the integral image at a location x, y, z contains the sum of the voxels with coordinates no more than x, y, z inclusive,

ii(x, y, z)=Σ_{x′≦x,y′,z′≦z}i(x, y, z)   (Eqn. 1)

where ii(x, y, z) is the 3D integral image and i(x, y, z) is the original 3D image.

[0042] A set of recursive equations may be defined:

s(x, y, z)=s(x, y, z−1)+i(x, y, z)   (Eqn. 2)

ss(x, y, z)=ss(x, y−1, z)+s(x, y, z)   (Eqn. 3)

ii(x, y, z)=−1, y, z)+ss(x, y, z)   (Eqn. 4)

where s (x, y, z) and ss (x, y, z) are the cumulative sums s (x, y,−1)=0, ss (x−1, z)=0, ii(−1, y, z)=0. On the basis of these, the 3D integral image may be computed in one pass over the original 3D image. Any two 3D Haar-like features defined at two adjacent rectangular regions may, in general, be computed using twelve array references.

[0043] The training phase can use a machine learning training framework (155), such as an AdaBoost algorithm. For example, AdaBoost, short for Adaptive Boosting, training is taught in Y. Freund, R. E. Schapire. “A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting, Computational Learning Theory,” Eurocolt. pp. 23-37, 1995, which is incorporated herein by reference in its entirety. The input positive training samples (156) are produced from library parts (either scanned point clouds or from a virtual scanner), by random down-sampling with option of additional noise and occlusions. Negative input samples (156) are produced from negative point cloud regions (region without the target part), by randomly sampling a subset with the size of the target part.

[0044] Each training sample (positive or negative) is assigned a weight (the same in the beginning), and pre-processed by 3D image conversion and integral image computation. A target number of weak classifiers (default=20) is processed and trained one by one in each cycle. Firstly, a pool of candidate weak classifiers is randomly generated (within the bounding box determined by the target part). The best parameters for all candidate weak classifiers (optimal threshold minimizing the weighted classification error) are trained based on the samples and their current weights. The candidate weak classifier with the minimum weighted error is selected as the weak classifier for this cycle. The weight of the weak classifier is computed based on the weighted error. The samples are reweighted—lowering the weight if a sample is correctly identified by the selected weak classifier. Then all weights are normalized.

[0045] The Detection Module (154) input comes from the Point Cloud Clusters (140). The clusters are pre-processed (153) as described above into a 3D Integral Image for efficient processing. A 3D detection window is moved to search across each of the clusters, evaluating the match between each subset of a cluster point cloud and a candidate part in the Parts Library (230).

[0046] For each library part in the Part Library (230), the Part Matching (150) process searches within each Point Cloud Cluster (140) for a match using the corresponding part detector (151). An evaluation window for each library part is positioned on a 3D search grid of locations in the Point Cloud Cluster (140). The search grid locations are established by computing a 3D image or voxel array that enumerates the points with each voxel. Each window position within the Point Cloud Cluster (140) is evaluated as a candidate part match to the current library part. To cope with potential orientation changes of a part, a principle direction detector is applied at each window position before match evaluation. The detected direction is used to align the candidate part to the same orientation as the library part.

[0047] The candidate part is evaluated by the Part Detector (151). This process uses multiple weak classifiers, combines their scores with weight factors, and compares the result to a threshold and produces a confidence score.

[0048] After all library parts are evaluated, all detected positive match instances are further processed by non-maximum suppression, to identify the library part with the best match and confidence above a threshold. If a best-match with a confidence above threshold exists, the best match part is output as a Matched Part (160) for integration into the final model. The points corresponding to the best match part are removed from the cluster.

[0049] The Point Cloud Cluster (140) is considered to be fully processed when the number of remaining points in the Point Cloud Cluster falls below a threshold % (e.g., 1%) of the number of initial cluster points. If all library parts in the Part Library (230) have been searched for in the cluster and successful matches do not remove enough points to consider the cluster fully processed, the remaining points are left in the Point Cloud Cluster (140) for later visualization during Model Editing & Export (300) or manual part creation with the Point Part Editor (240), which allows unmatched parts to be added to the Part Library (230) for use in subsequent processing.

[0050] The output of Part Matching (150) is the Matched Parts (160) list including their surface representations and transformation matrices, along with any metadata stored with the part in the Part Library (230).

[0051] FIG. 5 illustrates an alternate method of Part Matching (150). This method finds local features in the point cloud data. A multi-dimensional descriptor encodes the properties of each feature. A matching process determines the similarity of feature descriptors in the Parts Library (230) to feature descriptors the point cloud. The best set of feature matches that meet a rigid body constraint are taken as a part match and the matched-points are removed from the Point Cloud. Clusters (140). The output of Matched Parts (160) is a 3D surface part model in a suitable representation such as polygons or NURBS along with their location and orientation in the model coordinate system.

[0052] The inputs of the FIG. 5 Part Matching (150) process are the Point Cloud Clusters (140). Given a CAD Model (200) of a part, an offline process may be used to create a corresponding point cloud model data in the Parts Library (230). The CAD Model (200) is imported and converted to a point cloud by a Virtual Scanner (220). The virtual scanner simulates the way a real scanner works, using a Z-buffer scan conversion and back-projection to eliminate points on hidden or internal surfaces. Z-buffer scan conversion is taught, for example, in “Straβer, Wolfgang. Schnelle Kurven- and Flächendarstellung auf graphischen Sichtgeräten, Dissertation, TU Berlin, submitted 26.4.1974,” which is incorporated herein by reference in its entirety.

[0053] In an embodiment, the Part Library (230) point cloud models may be pre-processed to detect features and store their representations for efficient matching. The same feature detection and representation calculations are applied to the input Point Cloud Clusters (140), as shown in FIG. 5. The variances, features, and descriptors of the point clouds are computed. The Variance Evaluation follows the definition of variance of 3D points. The Feature Extraction process detects salient features with a multi-scale detector, where 3D peaks of local maxima of principle curvature are detected in both scale-space and spatial-space. Examples of feature extraction methods are taught in D. G. Lowe, “Object Recognition from Local Scale-Invariant Features,” Proceedings of the 7th International Conference on Computer Vision, 1999 and A. Mian, M. Bennamoun, R. Owens, “On the Repeatability and Quality of Keypoints for Local Feature-based 3D Object Retrieval from Cluttered Scenes.” IJCV 2009, which are both incorporated herein by reference in its entirety.

[0054] Given an interest point and its local region, there are two major steps to construct the descriptor. Firstly, the self-similarity surface is generated using the similarity measurements across the local region, where the similarity measurements can be the normal similarity, or the average angle between the normals in the pair of regions normalized in the range of 0-1. Then, the self-similarity surface is quantized along log-spherical coordinates to form the 3D self-similarity descriptor in a rotation-invariant manner. The self-similarity surface is the 3D extension of the 2D self-similarity surface, which is described in E. Shechtman and M. Irani, “Matching Local Self-Similarities Across Images and Videos,” Computer Vision and Pattern Recognition, 2007, which is incorporated herein by reference in its entirety. The normal and curvature estimation are provided by open-source libraries such as a Point Cloud Library (PCL), an example of which is described in R. B. Rusu and S. Cousins, “3D is here: Point Cloud Library (PCL),” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA '11), Shanghai, China, May 2011, which is incorporated herein by reference in its entirety.

[0055] The output of the Descriptor Generation is the feature representation with point descriptors of a cluster containing a group of feature points (x, y, z coordinates and the detected scale), each of which is assigned with a point descriptor i.e. a 5*5*5=125 dimensional vector.

[0056] During online processing, the input clusters are first passed through the sub-module of Cluster Filter (Coarse Classification). The Cluster Filter consists of several filters that rule out or set aside clusters with or without certain significant characteristic. The filters are extremely fast while able to filter out quite a number of impossible candidates. Our implementation uses two filters: linearity filter and variance filter.

[0057] The linearity filter is independent of the query target (from the part library). The linearity is evaluated by the absolute value of the correlation coefficient r in the Least Squares Fitting on the 2D points of the three projections. An example of Least Squares Fitting is taught by Weisstein, Eric W. “Least Squares Fitting,” MathWorld—A Wolfram Web Resource, which is incorporated herein by reference in its entirety. If |r| is above a threshold in one of the projections, the cluster is considered as a ‘linear’ cluster. Note that planes and cylinders may fall in the linear category, but since both have been detected in the Primitive Extraction (110) step, any remaining linear clusters are considered missed primitives or noise. Linear clusters may be ignored or an optional least-square fitting process may be used as a Linear Modeler to approximate the cluster with polygon surfaces.

[0058] The variance filter is partially dependent on the target. If the variances of the points between the candidate cluster and the target are very much different from each other, the candidate would be unlikely to be matched to the target, thus would not be passed on to the point descriptor matching process.

[0059] During Point Descriptor Matching (Detailed Matching), the descriptors for the targets generated in the offline processing are compared against the descriptors for the candidate clusters generated during the online processing and the transformation is estimated if possible. Note that the features and the descriptors will not be computed twice for efficiency.

[0060] One step in the matching process may be a Feature Comparison, the process of comparing the feature representations with point descriptors between the candidate clusters and part library targets. Initially all nearest-neighbor correspondences, or pairs of features, with any Nearest Neighbor Distance Ratio (NNDR) value are computed and then, a greedy filtering strategy is used to look for the top four correspondences that fit the distance constraint. K. Mikolajczyk and C. Schmid, “A Performance Evaluation of Local Descriptors,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 27, no. 10, pp. 1615-1630, October 2005, which is incorporated herein by reference in its entirety, evaluates various point descriptors. The number of remaining correspondences that fit the hypothesis may be used as the matching score. If the matching score between a cluster and a target is higher than some threshold, the cluster is considered to be an instance of the target, or they are said to be matched to each other. The output of Feature Comparison are the combined correspondences i.e., the correspondences, fitting the distance constraints, between the candidate cluster and the target that are considered matched.

[0061] The final steps, the Transformation Estimation and the Refinement are processes of estimating the transformation and refinement between the candidate cluster and the target, based on the combined correspondences. Specifically, a 3*3 affine transformation matrix and a 3D translation vector is solved from the equations formed by the correspondences. A rigid-body constraint may be used to refine the result through Gram-Schmidt Orthogonalization. An example of Gram-Schmidt Orthogonalization is taught by Weisstein, Eric W, “Gram-Schmidt Orthogonalization,” MathWorld—A Wolfram Web Resource, which is incorporated herein by reference in its entirety. These parameters may be used to transform the polygon model in the part library to Matched Parts that could fit in the scene model.

[0062] Referring back to FIG. 1, Matched Parts (160) are 3D CAD models that were determined to be in the Point Cloud Clusters (140). The Matched Parts (160) data identifies the CAD models that were discovered within the point cloud as well as the meta-data for those models. These CAD models have a suitable surface representation such as polygons or Bezier patches or NURBS, including their locations and orientations within the point cloud. Related information about each CAD model is stored in the Parts Library (230), including connector information, which is utilized in Model Integration (180).

[0063] Primitives (170) are the cylinders and planes extracted by the Primitive Extraction (110) process. These are CAD models with a suitable surface representation such as polygons or Bezier patches or NURBS, including their locations and orientations within the point cloud.

[0064] FIG. 6 illustrates an example process for Model Integration (180), which takes Detected Primitives (170) and Matched Parts (160) as inputs. This process adjusts the positions of primitives and parts in a local scope in order to connect them. It also generates joints between primitives and/or parts. This process starts with setting up a set of detected cylinders (denoted as S_C) and a set of generated joints (denoted as S_J) at step (181). Connectors associated with each matched part are converted into virtual cylinders at step (182), which are zero-length cylinders indicating their expected connection to other primitives.

[0065] The process of joint generation may be composed of two parts. One is a parallel connection, as shown in steps (183-188), which adjusts positions and generates joints of parallel cylinders. The other is non-parallel connection, shown as steps (189, 191-195), which generates bent and straight joints for non-parallel cylinders.

[0066] A parallel connection begins with a determination at step (183) regarding whether all pairs of cylinders have been checked. If not, one is them (denoted as c₁, c₂) is selected at step (184). A parallel connection is needed between c₁ and c₂ if step (185) determines that their end-to-end distance is below a threshold and their axes are parallel within a threshold angle. If these cases are met, their axes are adjusted to coincide exactly and a parallel connection is generated at step (186). The process of checking every pair of cylinders is performed iteratively, until no more cylinders are adjusted at step (188). Next, non-parallel connections are generated in a similar manner at steps (189, 191-195), with the difference that no iterations are needed at this stage.

[0067] Adjusted Model (190) is the result of all the automatic processing of Primitives and Parts and Joints. The data at this stage includes CAD surface models with a suitable surface representation such as polygons or Bezier patches or NURBS, including their locations and orientations with respect to a common coordinate system. The point cloud coordinate system is suitable, but not the only possible coordinate system that could be used for the model. The model at this stage also includes the connectivity information that was produced in the Model Integration (180) stage. Connectivity data records the physical connections between Primitives, Parts, and Joints. Such data can be used to determine flow paths through pipes and valves and joints, for example.

[0068] CAD Model Parts (200) may be 3D part models obtained from outside sources. For example, a valve vendor may provide a CAD model of the valves they sell. This 3D model can be added to the Parts Library (230) for matching to Point Cloud (100) data. 3D models may be in varied data formats such as Maya, KML, Autocad, 3DS or others. The Model data may represent the Part surfaces as polygons or Bezier patches or NURBS, defined within a local coordinate system.

[0069] CAD Part Importer & Virtual Scanner (220) inputs varied CAD Model Parts (200) formats and converts them to the point and polygon representation used in the Parts Library (230). This may be an automatic or manually-guided process. It need only be performed once for any specific CAD model. This process may also convert CAD Model (200) coordinates to a standard coordinate system, units, and orientation used within the Parts Library (230). The input CAD Model (200) is a surface representation. The Parts Library (230) has both a surface representation and a point cloud representation for each part. The CAD Model (200) surface is processed by a Virtual Scanner (220) to simulate the scan of the part. The Virtual Scanner (200) may perform scans at varied resolution (point density) and from varied viewpoints to obtain a complete point cloud for the CAD Model (200). A Z-buffer scan conversion [Str] and back-projection are used to eliminate points on hidden or internal surfaces of the model. Hidden internal surfaces would never be seen by an actual scan of the object in use. For example, the interior of a valve flange would not appear in an actual scan since the flange would be connected to a pipe or other object in actual use.

[0070] Parts Library (230) contains the surface and point cloud models for all parts to be matched in the modeling process. The parts are stored in a defined coordinate system, units, and orientation. The Part Matching (150) process can use either or both the surface and point cloud models for the matching and modeling process.

[0071] The models in the Parts Library (230) may be obtained from two sources. The CAD Part Importer (220) allows CAD surface models to be processed for inclusion in the library. The Point Part Editor and Importer (240) allows the actual scanned points of an object to be included as parts in the library. This means surface models and scanned point clouds can become parts in the Parts Library (230). Any part in the library can be accessed for Part Matching (150). Preprocessing of the parts in the library may be done to facilitate the Part Matching (150) process. Preprocessing may result in additional data that is stored for each part and accessed during Part Matching (150).

[0072] The library also contains connector information for each Part, which indicates its interface type and area(s) of connection to other cylinders or Parts. Specifically, the connector information contains positions, orientations and radii or geometry of the connecting surfaces. This information is usually obtained by manually marking the Part data with the Part Editor (250), or it can be obtained as External Part Data (260).

[0073] The library may contain additional meta-data for each Part, such as manufacturer, specifications, cost or maintenance data. The meta-data is obtained from Externals Part Data (260) sources such as manufacturer's spec sheets or operations data. A manual or automatic process in the Parts Editor and Database Manager (250) is used to facilitate the inclusion of External Part Data (260) or manually entered data for parts within the Parts Library (230).

[0074] Point Part Editor and Importer (240) allows construction of parts for the Parts Library (230) from actual scanned data. The Point Part Editor and Importer (240) provides the interactive tools needed for selecting regions of points within a Point Cloud (100) or Point Cloud Clusters (140). The selected points are manually or semi-automatically identified by selecting and cropping operations, similar to those used in 2D and 3D editing programs. Once the points corresponding to the desired object are isolated, they are imported into the Parts Library (230) for Part Matching (150). The Point Part Editor (240) also includes manually-guided surface modeling tools such as polygon or patch placement tools found in common 3D editing programs. The surface editing tools are used to construct a surface representation of the isolated points that define the imported part. The surface representation is also included in the Parts Library (230) model of the part.

[0075] Parts Editor and Database Manager (250) allows for interactive browsing of the Parts Library data, as well as interactive editing of metadata stored with the parts in the Parts Library (230). In addition to editing metadata, External Part Data (260) may be imported from sources such as data sheets or catalogs, or manually entered.

[0076] External Part Data (260) is any source of data about parts that are stored in the Parts Library (230) for Part Matching (150). These sources may be catalogs, specification sheets, online archives, maintenance logs, or any source of data of interest about the parts in the library. These data are imported by the Parts Editor and Database Manager (250) for storage and association with parts in the Parts Library (230).

[0077] Model Editing & Export (300) allows for viewing and interactive editing of the Adjusted Model (190) created by Model Integration (180). The Model Editing (300) capabilities are provided by a standard editing tool suite provided by commercial tools such as Maya, AutoCAD, and 3DS. In fact, such commercial tools already provide the Model Editing & Export (300) functions, so they can be used for this purpose rather than constructing a new module. At the operator's discretion, any element of the Adjusted Model (190) can be edited, replaced, or new elements can be added. The surface models in the Parts Library (230) may be used to add or replace portions of the model. For comparison to the initial Point Cloud (100), the points can also be displayed to allow manual verification of the surface model's accuracy and to guide any edits the operator deems desirable.

[0078] Once the operator deems the model to be correct, it may be exported in one or more suitable formats as the Final Model (310). These are all common features of commercial modeling software such as Maya, AutoCAD, and 3DS. As such, no further description is provided of this function. In the absence of the automatic methods, the entire model would generally have to be constructed with this module.

[0079] In addition to the model editing described above, the Model Editing & Export (300) module also read the connectivity information of the Adjusted Model (190) and the meta-data for each matched part in the model, from the Parts Library (230). Both of these data are output as part of the Final Model (310).

[0080] Final Model (310) is the completed surface model. The 3D models may be in varied data formats such as Maya, KML, Autocad, 3DS or others: The Final Model data represents surfaces by polygons or Bezier patches or NURBS, defined within a local coordinate system. The Final Model also includes connectivity information discovered and stored in the Adjusted Model (190) and parts metadata associated with the matched parts in the Parts Library (230).

[0081] FIG. 7 shows an example case of an industrial site scan. Primitive Extraction accounts for 81% of the LiDAR points, while Part Matching and Joints account for the remaining 19% of the points. The result is a complete 3D polygon model composed of Primitives, Parts, and Joints.

[0082] In an embodiment, the automated system is adapted for identifying and modeling pipe runs. In particular, the pipe-run identification system in accordance with this embodiment takes advantage of particular characteristics of pipes in performing a primitive extraction process.

[0083] As illustrated in FIG. 8, the point cloud (100) is processed to extract cylinders. The input point cloud (100) is first processed by a normal estimation module (402). The normal estimation module begins by subdividing the initial volume (404). The subdivision may be, for example, a division into a set of uniform cubic sub-volumes that are each separately processed in accordance with the remainder of the algorithm. This subdivision of the data may allow for a reduction in computational complexity and for application of the method to arbitrarily large input point clouds. The size of the sub-volumes may be predetermined, a user input parameter, or may be dynamically calculated by the system based on available processor and memory capacities. By way of example, a typical block may be on the order of hundreds of millions of points, which in a typical application may represent a 5 m cube of point data. As will be appreciated, the number of points will be resolution dependent and the number of points appropriate for a sub-volume will typically depend on the computational power available and may vary as improvements are made in computer processors and memories.

[0084] The output of the sub-volume division is a plurality of divided point clouds (406). Each divided point cloud (406) is processed by the normal estimation and projection module (408).

[0085] The normal estimation and projection module (408) computes normal vectors for the divided point cloud (406) and projects them onto a Gaussian sphere (410). For each data point, a normal vector is computed. For example, this can be performed using a method such as that taught in Pauly, discussed above. The projection of the computed normal vectors may be performed using a method such as that taught in Chen and Chen, discussed above.

[0086] The resulting Gaussian sphere (410) is a collection of all normal vectors of the point cloud (406), i.e., one Gaussian sphere (410) corresponding to each sub-volume. The normal vectors may be normalized to form a unit sphere representing the distribution of normal vectors over the point cloud (406).

[0087] The Gaussian spheres (410) are then processed by a global similarity acquisition module (412) by a point-cluster detection process (414). This process seeks point-cluster patterns on Gaussian sphere (410) using an algorithm such as a mean-shift algorithm, for example. Point cluster may be considered as corresponding to generally planar areas in the original divided point cloud (406). Because they are not helpful to identification of pipe structures, they may be removed from the Gaussian sphere (410). Once the point clusters are removed, a residual Gaussian sphere (416) remains.

[0088] The residual Gaussian spheres (416) are then processed using a great-circle detection module (418). In particular, because the normal of a point lying on a cylinder is perpendicular to the cylinder axis, the point normals from cylinders of the same direction d will all be perpendicular to d. When mapped onto the Gaussian sphere, they are distributed as a great circle that is perpendicular to d, as illustrated in FIG. 9(a). In the example of FIG. 9(a), a first great circle (436) represents cylinders along a first direction and a second great circle (438) represents cylinders along a second direction.

[0089] In an embodiment, the great-circle detection on the Gaussian sphere is based on a Random Sample Consensus (RANSAC) process as described above. In particular, it is possible to choose many random point pairs and compute cylinder direction candidates that lie on a spherical map of potential cylinder direction as illustrated in FIG. 9b, wherein the points at a first set of poles (440) correspond to the first great circle (436) and the points from a second set of poles (442) correspond to the second great circle (438). Once the great circles are detected and potential cylinder direction are identified, the divided point cloud (406) is segmented, based on the cylinder orientations, producing segmented point clouds (420). Each segmented point cloud (420) is a segmentation of its source divided point cloud (406) based on great-circle patterns produced by the great-circle detection (418). Thus, each segmented point cloud (420) belongs to the cylinders of the same orientation. In particular, points within a thick stripe on the Gaussian sphere may be identified as a category with the same cylinder orientation as shown in FIG. 9c, wherein the cylinders (444) correspond to the first great circle (436) and first poles (440) and the cylinders (446) correspond to the second great circle (438) and second poles (442).

[0090] The segmented point clouds (420) are then passed to the primitive detection module (422) where they are processed by the 2D projection module (424). The 2D projection module (424) projects each respective segmented point cloud (420) onto a 2D plane (448) that is perpendicular to the orientation of the cylinders (444, 445) to which it corresponds, as shown in FIG. 10a. In the example of FIG. 10a, cylinders (444) are a group of similar cylinders arrayed next to each other while cylinder (445) is separated from and larger than the members of the first group.

[0091] The resulting 2D point cloud (426) contains 2D projections of segmented point cloud (420). These points belong to cylinders of the same orientation. Then, 2D circle detection module (428) identifies circle patterns (450, 451) in the 2D point cloud (426), where projections (450) correspond to cylinders (444) while projection (451) corresponds to cylinder (445), illustrated in FIG. 10b. An algorithm for detection of circles on the 2D point cloud is a mean-shift algorithm similar to the great-circle detection algorithm (418) described above. Detected circles may be considered to represent cylinder placements (430) (i.e., positions, orientations and radii). These candidate circles tend to form clusters as shown in FIG. 10c, and the center of these clusters, identified with the mean-shift algorithm, approximate the cross-sections of cylinders and their associated points from the point cloud. Centers (452) correspond to projections (450), and furthermore to great circle (436), poles (440), and cylinders (444), while center (453) corresponds to projection (451), and furthermore to great circle (438), poles (442), and cylinder (445).

[0092] The cylinder placements (430) are then processed using the cylinder boundary extraction module (432) which calculates boundaries of the identified cylinders (i.e., start and end of cylinder axis). In an embodiment, boundaries are determined by point coverage along cylinder surfaces. Another condition that may be set is requiring 180-degrees of cross-section coverage. This process is illustrated in FIG. 11 in which FIG. 11a illustrates a candidate cylinder (454) having a plurality of apparent gaps (456). The cylinders are smoothed (FIG. 11b) and the gaps are assessed against a threshold and closed if shorter than the threshold (FIG. 11c).

[0093] The resulting cylinders (434) are an output of the primitive detection module (422) and an input to the joint verification module illustrated in FIG. 12.

[0094] The joint verification module begins with the application of three related joint detection modules. In practice, the three modules may be constituted as a single multi-function module, or may be separate. Likewise, they may be applied serially or in parallel to the input cylinders (434).

[0095] T-junction detection module (462) acts to determine potential positions of T-junctions (502) connecting detected cylinders (434). T-junctions (502), illustrated in FIG. 13a, are extensions of one cylinder end merging into another cylinder's side. Heuristic criteria (e.g., joint radius, gap distance, skew and angle) are adopted for detection of joints.

[0096] Elbow detection module (464) determines potential positions of elbows (504) connecting detected cylinders (434). Elbows (504), illustrated in FIG. 13b, are curved joints connecting ends of two cylinders that are aligned along different directions. Similar heuristic criteria are adopted as in T-junction detection (462).

[0097] Boundary joint detection (466) determines potential positions of boundary joints (506) connecting detected cylinders (434). Boundary joints (506), illustrated in FIG. 13c, are cylinder segments that fill small gaps between two cylinders aligned end to end along a same direction. Because gaps within a single cylinder are generally resolved during the application of the boundary extraction module (432), gaps present during the boundary joint detection process tend to be at a boundary of divided sub-volumes. Evaluation of boundary joints makes use of similar heuristic criteria to those used in T-junction and elbow detection (462, 464).

[0098] The output of the three joint detection modules together constitutes a set of unverified joints (470), i.e., a set of detected T-junctions, elbows and boundary joints. At this stage of the detection, they may be considered to be candidate or hypothetical joints, to be verified by a joint verification module (472).

[0099] Joint verification module (472) takes as an input the detected unverified joints (470) and the initial point cloud (100), and verifies the existence of detected joints in the point cloud. The heuristic criteria used for joint verification may include parameters including joint radius, gap distance (defined as the nearest distance between central lines), skew and angle, illustrated in FIG. 14. These parameters are limited to reasonable ranges that are functions of the connecting pipe diameters. Using this approach tends to ensure that connecting cylinders are near to each other, similar in size, co-planar and non-parallel for T-junctions and curved joints, or parallel for boundary joints. Joints that pass the verification process (472) are output as verified joints (474).

[0100] In general, reconstruction into solid bodies is possible because all of the key parameters have been determined. For T-junctions, the joint can be modeled by extending the end point of one cylinder into the axis of another cylinder. For boundary joints, a cylinder connecting two adjacent ones is constructed.

[0101] If two cylinders are connected with a curved joint, the only free parameter is the major radius. The major radius of the optimal curved joint is determined as being the one with the most points lying on its surface among the range of possible major radius options. In this regard, if each data point in the hypothetical joint volume is counted as a vote for radius values such that the joint surfaces touch it, the radius value with most votes would be the optimal radius for that joint.

[0102] Further discussion of the items described herein is provided in the following paper: Qiu, R., Neumann, U., Zhou, Q. “Pipe-Run Extraction and Reconstruction from Point Clouds.” This paper is hereby incorporated by reference in its entirety.

[0103] In an embodiment, a false alarm reduction algorithm may be included. In this approach, false detections are used as additional negative training samples to retrain the detector. False detections used for retraining may be detected from negative scenes that are known and/or chosen specifically because they lack the target object. The retraining may be iterated to further reduce false detections.

[0104] Accordingly, embodiments include modeling systems and methods, which may automatically create CAD models based on a LiDAR (Light Detection and Ranging) point cloud, and automates the creation of 3D geometry surfaces and texture maps from aerial and ground scan data. In particular, this system utilizes a robust method of generating triangle meshes from large-scale noisy point clouds. This approach exploits global information by projecting normals onto Gaussian spheres and detecting specific patterns. This approach improves the robustness of output models and resistance to noise in point clouds by clustering primitives into several groups and aligning them to be parallel within groups. Joints are generated automatically to make the models crack-free.

[0105] The above described methods can be implemented in the general context of instructions executed by a computer. Such computer-executable instructions may include programs, routines, objects, components, data structures, and computer software technologies that can be used to perform particular tasks and process abstract data types. Software implementations of the above described methods may be coded in different languages for application in a variety of computing platforms and environments. It will be appreciated that the scope and underlying principles of the above described methods are not limited to any particular computer software technology.

[0106] Moreover, those skilled in the art will appreciate that the above described methods may be practiced using any one or a combination of computer processing system configurations, including, but not limited to, single and multi-processer systems, hand-held devices, programmable consumer electronics, mini-computers, or mainframe computers. The above described methods may also be practiced in distributed computing environments where tasks are performed by servers or other processing devices that are linked through a one or more data communications networks. In a distributed computing environment, program modules may be located in both local and remote computer storage media including memory storage devices.

[0107] Also, an article of manufacture for use with a computer processor, such as a CD, pre-recorded disk or other equivalent devices, could include a computer program storage medium and program means recorded thereon for directing the computer processor to facilitate the implementation and practice of the above described methods. Such devices and articles of manufacture also fall within the spirit and scope of the present invention.

[0108] As used in this specification and the following claims, the terms “comprise” (as well as forms, derivatives, or variations thereof, such as “comprising” and “comprises”) and “include” (as well as forms, derivatives, or variations thereof, such as “including” and “includes”) are inclusive (i.e., open-ended) and do not exclude additional elements or steps. Accordingly, these terms are intended to not only cover the recited element(s) or step(s), but may also include other elements or steps not expressly recited. Furthermore, as used herein, the use of the terms “a” or “an” when used in conjunction with an element may mean “one,” but it is also consistent with the meaning of “one or more,” “at least one,” and “one or more than one.” Therefore, an element preceded by “a” or “an” does not, without more constraints, preclude the existence of additional identical elements.

[0109] While in the foregoing specification this invention has been described in relation to certain preferred embodiments thereof, and many details have been set forth for the purpose of illustration, it will be apparent to those skilled in the art that the invention is susceptible to alteration and that certain other details described herein can vary considerably without departing from the basic principles of the invention. For example, the invention can be implemented in numerous ways, including for example as a method (including a computer-implemented method), a system (including a computer processing system), an apparatus, a computer readable medium, a computer program product, a graphical user interface, a web portal, or a data structure tangibly fixed in a computer readable memory.