Template Matching Increases Productivity of Topography Extraction from LiDAR Data

A 3.935Mb PDF of this article as it appeared in the magazine complete with images is available by clicking HERE

Certainty 3D has invested over a decade in the development of TopoDOT processing software. Our focus has been the productive extraction of high quality 3D CAD models from point clouds and LiDAR data in general. Early on, we found prospective customers conditioned to opening traditional survey projects where the "intelligence" associated with each coordinate was added manually in the field. These coordinates were simply imported into software which connected line work based on this associated metadata. It was therefore often difficult for LiDAR technology newcomers to not expect the same type of performance upon import of incredibly dense point clouds.

We thus spent much of our time explaining that while the point cloud contains the information, there was no direct intelligence associated with the data. This intelligence must be applied in the office during the model extraction process. More succinctly, we explained there was no "magic button" to automatically extract 3D vectors from complex point clouds. Today that button still doesn’t exist, yet TopoDOT’s new template matching technique has taken us significantly closer to achieving the level of automation expected by our customers over the past years. In this article, we would like to explain our approach to the problem and how our customers are already experiencing significant increases in extraction productivity.

The 3D World Broken Down to 2D Templates
While the design, engineering and construction industries are rapidly moving to a designs based on 3D models, it is instructive to appreciate just how much of our civil infrastructure has been successfully built using only 2D designs, drawings and models. Clearly 2D drawings representing profiles, cross-sections, and plan views are rich in information, easily interpreted and have been successfully employed in constructing the world’s infrastructure for hundreds or even thousands of years. In fact the underlying construction of just about all complex structures can be broken down to 2D templates linearly extrapolated along some orthogonal line.

An appreciation for the role of 2D templates has long been a key contributor to TopoDOT’s success in extracting 3D models from complex point clouds, images and related data. Many TopoDOT tools very efficiently orient a local coordinate system along a line within the complex 3D point cloud such that a 2D profile is presented for interpretation to the user. When available, calibrated images with point cloud data presented in the same perspective view significantly increase the information available to the user for interpretation. Vectors and break-line points are then easily identified and extracted in what is often described as an efficient but semi-manual process.

Automated Extraction of 2D Templates in 3D Data
It has long been obvious that automatic extraction of 2D templates would greatly increase processing productivity. The Certainty 3D team was of course not the first to recognize this potential. However reliable extraction of 2D templates from point cloud data poses considerable technical challenges. Inconsistencies in point cloud data quality and template structure make automation difficult. In addition there are virtually an infinite number of possible 2D profiles to be defined and extracted. So while many software applications attempted this level of automation, the results typically did not meet the quality requirements needed to effectively feed design, engineering and construction operations.

Certainty 3D has recently developed an automatic break-line extraction tool based on template recognition and extraction which successfully addresses the aforementioned technical challenges. This TopoDOT tool allows the user to easily define custom templates and save them in a cell library. Automatic template extraction is extremely reliable and accurate. An interactive approach to post-extraction quality assurance makes finding and fixing glitches fast and reliable. User-friendly techniques for defining templates accommodate change in template size along the extraction path.

Defining the Template
TopoDOT’s Template Extraction tool first requires definition of the template. In the following topography example, one begins by using TopoDOT’s cross section tool to quickly extract a point cloud data profile across a curb line to be used in defining the template. Using the profile view of the point cloud data simple polylines are used to define the template. Line thickness along the defined template is modified to weight the most unique areas of the template more heavily. Breakpoints along the template are identified by red "X"s.

Extracting Break-lines Using Template Matching
TopoDOT’s Template Extraction tool currently provides the user a very automated, intuitive and fast means of modeling topography break-lines. Once the user has defined the custom template, using the Template Extraction tool is very easy. From the top view, use the mouse to trace an initial line along the direction of the break-line to be extracted. The Template Extraction tool uses a proprietary least-squares-fit algorithm to automatically optimize the placement of the template within the point cloud. The tool then automatically moves the template forward a specified distance along the line initially traced by the user. The operation is repeated there and the break lines are connected. The tool continues moving through the cloud until it can no longer find suitable match of the template within the point cloud.

For less distinct template structures often occluded by random organic material, the TopoDOT Template Extraction tool offers an alternative mode of operation. In this mode, the user may quickly define a 2D line path along the break-line in top view. The Template Extraction tool uses this information to limit its search to data along this path. This method has proven very reliable in quickly extracting break-lines along features such as curb lines within organic material such as grass, dirt, leaves, etc.

Note that extracted curb lines are terminated where they connect with more complex 3D structures such as ADA ramps. TopoDOT also offers the unique "Smart Cell" feature to automatically insert the 3D cell into the point cloud adjusting its size to match the break line termination points and placing vertices on the point cloud. Final vertex position may be adjusted by simply dragging the vertex to the proper location. Together TopoDOT’s Template Extraction and the Smart Cell tools increase topography extraction productivity by several hundred percent.

Case Study: ATKINS North America
One of the first TopoDOT users to apply Template Extraction was Atkins Engineering National Geomatics Division located in Miami, Florida. Mr. Allen McDonald, Atkins CAD Technician, learned the Template Matching tool in a short online training session with Certainty 3D. After some practice, Mr. McDonald applied the tool to the processing of mobile LiDAR data acquired in the city of Hollywood, Florida by EMC Survey, Grenada Mississippi. Mr. McDonald reported significant productivity increase over the semimanual approach when applied to curbs in moderate to good condition. In areas where curbs were severely damaged or heavily covered by organic material, the traditional TopoDOT semi-manual Breakline Extraction tool often proved superior. Overall, Mr. McDonald estimated TopoDOT’s Template Extraction tool increased processing productivity by about 100% for the project.

In the typical LiDAR data processing workflow, it now falls upon the CAD technician to identify features and extract intelligent models in the office. This intelligence is no longer applied in the field and thus there still is no "magic" button automatically extracting all line work. Yet improvements in model extraction technology like TopoDOT’s Template Extraction tool further accelerate the already exponential growth in the productivity of LiDAR data processing operations.

Ted Knaak is President of Certainty 3D, LLC. Certainty 3D’s primary product is TopoDOT, is a software application designed to extract 3D topography and CAD models from static, mobile and airborne LiDAR system data.

A 3.935Mb PDF of this article as it appeared in the magazine complete with images is available by clicking HERE

About the Author

Ted Knaak

Ted Knaak started his professional career as a control systems analyst for General Electric Space Systems Division through the eighties. In 1990, he moved to Florida where he was exposed to lidar technology at Schwartz Electro-Optics serving as marketing/sales and program manager. Mr. Knaak founded Riegl USA in 1993 and has since been actively involved with lidar and laser scanning technology. In 2011 he founded Certainty 3D, a company focused on data processing software and technology solutions for the laser scanning industry. Certainty 3D’s primary product is TopoDOT™ a point cloud/calibrated image processing program for extracting CAD models from LiDAR data. Mr. Knaak holds MSEE and MSME degrees from Brown and Drexel universities.
Contact Ted Article List Below