AI helps find trees in a forest: Researchers achieve 3D forest reconstruction from remote sensing data

WEST LAFAYETTE, Ind. — Existing algorithms can partially reconstruct the shape of a single tree from a clean point-cloud dataset acquired by laser-scanning technologies. Doing the same with forest data has proven far more difficult. But now a team from Purdue University’s Department of Computer Science and Institute for Digital Forestry and Germany’s Kiel University has introduced a new AI method for isolating and reconstructing forest trees that they call TreeStructor.

The team introduced TreeStructor in IEEE Transactions on Geoscience and Remote Sensing. The paper’s first author, Xiaochen Zhou, who earned his PhD in computer science from Purdue this year, has posted a dynamic visualization that shows how the system works.

Urban structures, furniture, cars and other human-built products display a high degree of symmetry, making them easier to detect from point-cloud datasets collected by light detection and ranging (lidar) and other remote sensing technologies. But nature tends to produce irregular stochastic structures — those that contain randomized characteristics.

“Symmetries are usually missing in stochastic structures,” said co-lead author Bedrich Benes, professor and associate department head of computer science at Purdue. “That makes them extremely difficult to reconstruct. And that means most methods that work for artificial structural reconstruction usually fail on vegetation. However, vegetation includes many repeating parts at different scales — a small twig is similar to a large branch — and this is the key idea behind TreeStructor.”

People can instantly discern the structure of individual trees from a point-cloud forest dataset. “Your eyes will send data to the brain, the brain will literally connect the dots, and you perceive the data as a three-dimensional structure,” Benes said.

Two years in the making, TreeStructor does more with point clouds than the human brain. It helps to detect and isolate repeating parts and capture tree shapes, which provides both scientific and economic benefits, among other useful measures.

Overlapping and intertwining tree branches complicate forest reconstruction. Lidar works by shooting laser pulses at the target objects, then detecting the reflected light. Tree trunks and branches standing behind the reflecting objects remain invisible, and the canopy dissipates the reflections to almost random directions. The workaround is to combine the results of multiple scans from various angles from the ground and sometimes from a drone flying above.

The human brain, too, can have trouble telling two trees apart from a distance if they stand close together with intertwined canopies. TreeStructor sees the difference. Most previous work, however, focused on extracting single trees from a generally clean forest dataset. “The data we work with is challenging, and we work with complete forests,” said co-author Sören Pirk, professor of computer science at Kiel University.

One of the most successful methods that predates deep learning represents trees as groups of circles or small cylinders that can be connected. “Branching points are complicated for these algorithms if you try to connect them,” Benes noted, and they often fail. The other problem is that the result is a crude approximation of the reconstructed three-dimensional objects.

AI methods, meanwhile, work well with artificial objects that contain symmetries. “But what was missing — this is where we are filling the gap — are AI methods that figure out these features for stochastic structures,” Benes said. 

The researchers exploited the repetitive aspect of complex natural structures. “All maple leaves, for example, display variations of a theme, but once you see a few, you can recognize most of them,” Benes noted. Assuming that trees display repeating structures at varying scales, they created what computer scientists call a representative dataset — a dictionary — and let AI learn the items in its contents and find them quickly in the point-cloud data.

The dictionary consists of a point cloud and a set of corresponding, unsorted meshes of geometric shapes. TreeStructor’s innovation is an AI model that takes an unseen point cloud and sorts through the objects in its dictionary to see how well the point clouds fit those objects. It then replaces the point cloud with the best-matching part from the dictionary.

The model matches sections of the point cloud to a mesh of disconnected three-dimensional geometric shapes that represent tree trunks and the branching parts that were difficult to detect by previous methods. The result is a network of interconnecting shapes that Benes compared to pipes in a plumbing system.

“The creation of the tree dictionary is a significant step toward species identification,” said co-author Songlin Fei, the Dean’s Chair in Remote Sensing and director of the Institute for Digital Forestry. “Further development of the dictionary will not only help you to reconstruct a tree but also tell you what kind of trees they are.”

Before data reconstruction could begin, the researchers developed the source code needed to train a synthetically generated dataset. They created thousands of virtual trees that were scanned by a virtual lidar and chopped into identifiable and connectable tree parts. After that, the time-consuming AI training process begins. Once TreeStructor is trained, it can be used to detect trees.

“Then we take the real-world data from the lidar scans. We divide it into small pieces. And for each piece, we try to find the corresponding geometry. Then we take the point cloud and replace it with a geometry,” Pirk said. In the last step, TreeStructor links the unconnected geometric shapes. And it runs fast, processing hundreds of trees in minutes without special computer equipment.

The researchers validated TreeStructor’s accuracy in a battery of tests. These included reconstructing the same tree model with laser scans collected via backpack, terrestrial laser scanning and drones, and comparing that to methods that reconstruct single trees. “The method is quite robust toward different sensors,” Benes said.

TreeStructor’s limitations include its inability to detect dead trees, bushes and other debris in the forest understory. Lidar sensor resolution also plays a factor. “Every year, we have higher and higher quality lidars, but there is a technological limit to these sensors,” Benes said.

Purdue co-authors include Ayman Habib, the Dr. Thomas A. Page Professor in Civil Engineering and associate director of the Institute for Digital Forestry; Bosheng Li, who received his PhD in computer science last May; and Jinyuan Shao, a PhD candidate in forestry and natural resources. This work was supported by the National Science Foundation, the National Institute of Food and Agriculture, the Natural Resources Conservation Service, and the European Research Council.