Town of Banff LiDAR Classification

Trees are a large part of every city and town. As such, it is important to have an inventory of trees for infrastructure planning, risk mitigation, and many other applications. By developing an algorithm that automatically finds and classifies all trees in a desired area, the time-consuming process of tracking trees becomes significantly more efficient, and consequently cheaper.

Our project uses an algorithm to detect trees within the semi-forested Town of Banff. While most tree detection algorithms in urban areas use satellite remote sensing and aerial or ground LiDAR, our approach involves only aerial LiDAR scanning. Our solution involves the application and combination of two tree inventory algorithms, which are documented to have high accuracy in forested areas. Using the combination method, our solution takes the most effective parts of each algorithm to produce a balanced method of tree inventory that is both accurate and correct in detection.

Using the combination method, our solution detects trees using a top-down nearest neighbor search, then checks the detected tree against a shape modelling RANdom SAmple Consensus (RANSAC) variant algorithm. The top-down approach allows for the majority of trees to be detected, and the modified RANSAC algorithm ensures few false positives, such as cars or walls, are identified as trees.

Our design consists of two algorithms combined into one. By performing the tree classification on the two precursor algorithms and the finalized combination algorithm, we can analyze the results of each and compare them to collected orthophotos and the existing Town of Banff database. A variety of test cases were chosen, specifically to account for both areas of high tree density, as well as areas with many man-made structures. For each test case, the number of trees found was documented and compared to the algorithm results.

To measure the efficacy of the solution, the accuracy and correctness were calculated. The accuracy of the solution is measured by the number of false postives present in the dataset, while the correctness of the solution is dependent on the number of false negatives. False positives are points that have been classified as trees, but are not actually trees. False negatives are points that were not classified, when they should have been. A higher accuracy or correctness indicate fewer occurences of these errors. Examples of accuracy and correctness are shown in the following figures.

The feasibility of the solution is contingent on the amount of time spent making the algorithm run as efficiently as possible. For instance, many of the errors for the 3 algorithms are tied to the presence of buildings. While it was possible to remove most buildings in the area, there is still a decent amount of urban infrastructure (streetlights, powerlines, etc.) that, if removed, would improve the accuracy and correctness of the solution. Additionally, the solution is limited by the number of points required to constitute a tree, and the assumption that the solution can isolate individual trees from other objects.

In its current state, our solution provides decent and feasible results, with the solution maintaining a balance between accuracy and correctness. The weighted average accuracy obtained is 82%, while the weighted average correctness is 76%.

Shown in Figure 4 is the results of our solution. Blue dots indicate a higher likelihood of being coniferous, while red indicates a higher likelihood of being deciduous or man-made structures, such as a building or power lines. Overall, our algorithm identified 26437 trees in the Town, and after applying the expected accuracy of 82%, the assumed number of correctly identified trees was approximately 21596. Accounting for the 76% expected correctness, the number of trees assumed to be missed is approximately 6915.