Circling the answer through RANSAC

Here in Michael Baker's Mobile LiDAR Center of Excellence, we are routinely challenged with developing new ways to extract the most from our data. Our focus is to minimize the amount of human interaction required to extract a relevant piece of data from the voluminous point clouds we collect. Understanding our necessary and recurring requirements within automated processes is important to us for the types of products we deliver. Knowing requirements helps us to determine if we are in a “buy versus build” decision for a particular software automation task. Many software companies are developing robust commercial software tools for feature extraction from LiDAR point clouds. However, the rights to modify any commercially developed software and inherent intellectual property and licensing costs can make the “buy” decision onerous and costly for us.

Understanding the likely and underlying algorithms we’d choose to employ in any software we look to build, or buy and license is vital. As engineers, surveyors and subject matter experts with a deep awareness of LiDAR data and its processing we know what we want and need for automation. Knowledge and necessity are not mutually exclusive. They should optimally align to produce the best solutions. That Rolling Stones lyric comes to mind. Yet, we don’t agree with the song’s implied result when it comes to software: “You don’t always get what you want, but you get what you need.”

In the best case, we get what we want and also need as it comes to our requirements for LiDAR processing. Too many needs are fulfilled inefficiently with commercial software. We must avoid “kluge approaches” when fulfilling a specific software or task sequencing approach, so in house development allows us to fulfill these needs specifically and efficiently in our LiDAR processing.

As an example let’s examine how we might fulfill a very repetitive task while using a computer to find the precise center, radius and circumference of a circle within the chaos of thousands of LiDAR points in a point cloud through a combination of geometry and algorithm design.

RANSAC (Random Sample Consensus) is an iterative based outlier detection method. The basic principle of which has been evolved to work with geometric equations allowing the system to determine the best fit circle within the LiDAR point data as well as locating the center of the best fit circle. The system creates “slices” through the points at a specified thickness in the vertical plane then determines the best fit circle and center point for each slice. Once we determine the location of a phenomena that might represent a circular object, we can use an automation tool to facilitate automatic extraction.

The advantages of such a tool include:

1. Ability to calculate the taper of any circular object ( columns, posts, poles, water tanks, etc.) and project the taper to a point that may be obscured by an object in the LiDAR data
2. Determining if an object is leaning by analyzing the center points of all the slices along the height of the object
3. Reducing the human error of manual attempts to extract the circle and center points.

We are continuously striving to expand our LiDAR data extraction capabilities at Michael Baker while appropriately making the correct buy or build choices with any software we utilize. When working with repetitive processes on tens of thousands of single functions of extractions per week, the simplest software process is better and more efficient for us. Geometric shapes are precise forms. They are mathematically consistent. Circles represent just one shape of the most basic and important forms of geometric objects. Squares, spirals, triangles are also basic forms. Extracting basic forms efficiently and cost effectively is very important to us.

We continually focus on getting everything right with one right extraction process at a time. This RANSAC system of processing is one of many developments that we will continue to exploit which sets us apart, ensuring Michael Baker International is the first name in LiDAR.

Regards,
Sandor

Sandor Laszlo, PE is a Software Engineering Supervisor with Michael Baker's Mobile LiDAR Center of Excellence.  Sandor's current focus is on the development of semi-automatous systems for extraction of features from LiDAR point cloud information.