⚡ electrical engineering

Rooftop planes segmentation for point cloud LiDAR data with the partitioning around medoids algorithm and geometrical elevation change variables

This study proposes a simple and robust rooftop segmentation method for LiDAR point clouds that utilizes elevation change features and the Partitioning Around Medoids algorithm to achieve high accuracy (95.9% completeness and 98.1% correctness) while effectively identifying edges and corners for 3D reconstruction.

Original authors: Phuong Le, Jibran Khan, Mikko Kolehmainen

Published 2026-06-25

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Phuong Le, Jibran Khan, Mikko Kolehmainen

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant, messy pile of 3D Lego bricks scattered on a table. These bricks represent a digital map of a city's rooftops, created by a laser scanner flying overhead (LiDAR). Your goal is to sort these bricks into neat, separate piles, where each pile represents a single flat roof section (like a flat top, a slanted side, or a corner).

This paper presents a clever, simple way to sort these "bricks" without needing a supercomputer, complex training, or even looking at photos of the roofs.

The Problem: Sorting the Mess

Usually, when computers try to sort these roof points, they act like a strict librarian who needs to know the exact shape of every book before sorting them. They often have to:

Throw away "bad" bricks (non-flat points) first.
Do heavy math to figure out which way each brick is facing (using "normal vectors").
Run complex training programs or use expensive aerial photos.

This is slow, complicated, and requires a lot of steps.

The Solution: The "Medoid" Organizer

The authors propose a new method using an algorithm called Partitioning Around Medoids (PAM).

Think of PAM as a smart organizer who doesn't just pick a "center" for a group (like a bullseye) but instead picks a real, actual brick from the pile to represent the group. This "representative brick" is called a Medoid.

Why this matters: If you have a weirdly shaped roof (like an L-shape), a "center" might fall in the empty air between the wings. But a "Medoid" is always a real brick sitting on the roof. This allows the algorithm to group together weird, irregular shapes that other methods would miss.

The Secret Sauce: "Elevation Changes"

Instead of asking, "Which way is this brick facing?" (which is hard to calculate and often fails at edges), the new method asks a simpler question: "How much higher or lower is this brick compared to its neighbors?"

The authors call this Elevation Change.

The Flat Roof: If you stand on a flat roof, your neighbors are all at the same height. The change is zero.
The Edge: If you stand on the edge, one neighbor is high, and the other is low. The change is big.
The Corner: If you stand on a corner, you have neighbors at different heights in multiple directions.

The Analogy: Imagine walking through a crowd.

If everyone around you is the same height, you are in the middle of a flat group.
If you suddenly see a giant to your left and a child to your right, you know you are at a boundary or a corner.

By using these "height differences" instead of complex direction vectors, the computer can instantly tell the difference between a flat roof, a sharp edge, and a corner without needing to throw away any data first.

How They Decided How Many Piles to Make

One tricky part of sorting is knowing how many groups (clusters) you need. Do you have 2 roof sections or 10?
The authors used a "Potential Score" system. Imagine dropping a magnet into the pile of bricks.

If a spot is surrounded by many bricks, it has high "potential" to be a group leader (Medoid).
They calculate this for every point, pick the best leader, and then lower the potential of the points nearby so the next leader is far away.
They found that setting the "magnet size" (radius) to about 20% to 40% of the distance across the whole roof worked best.

The Results

The authors tested this on 150 real buildings in Finland.

Success Rate: They correctly identified 95.9% of the roof sections (Completeness) and got 98.1% of the individual points right (Correctness).
Comparison: Even though their method is much simpler and faster than complex Deep Learning or Octree methods, it performed just as well, and in some cases (correctness), even better.

Why This Is a Big Deal

The paper claims this is a "one-step" solution. You don't need to:

Remove bad data points first.
Use aerial photos.
Train a complex AI model.
Re-process the data.

You just feed the raw laser data in, and it spits out the separated roof planes. It's like having a magic wand that instantly sorts a messy pile of Legos into perfect, distinct roof shapes, including the tricky corners and edges that usually confuse computers.

Technical Summary: Rooftop Planes Segmentation for LiDAR Data Using PAM and Elevation Change Variables

Problem Statement
The segmentation of rooftop planes from airborne Light Detection and Ranging (LiDAR) point clouds is a critical step for urban modeling, building reconstruction, and assessing solar potential. Existing approaches generally fall into two categories: model-based methods (e.g., RANSAC, deep learning) and clustering methods (e.g., K-means). However, these methods often suffer from significant drawbacks, including high computational costs, the requirement for extensive preprocessing (such as removing non-planar points), dependence on aerial imagery, complex optimization, and sensitivity to outliers. Furthermore, traditional clustering algorithms like K-means tend to form hyper-spherical clusters and struggle with irregular shapes common in rooftop structures. A specific limitation in current feature sets is the reliance on normal vectors, which can be unstable in sparse data areas and fail to effectively identify edges and corner points without additional reprocessing.

Methodology
The authors propose a straightforward, "instant" segmentation procedure that operates directly on raw LiDAR data without the need for reprocessing or complex model training. The methodology consists of three primary components:

Clustering Algorithm (Partitioning Around Medoids - PAM):
Instead of K-means, the study utilizes the Partitioning Around Medoids (PAM) algorithm. PAM was selected for its robustness against outliers and its ability to form clusters of various, irregular shapes by minimizing the sum of dissimilarities between points within a cluster, rather than minimizing squared Euclidean distances to a centroid. This makes it suitable for the complex geometries of rooftops.
Feature Engineering (Elevation Change Variables):
The study replaces the traditional normal vector variable with "elevation change" features. For each point, elevation changes are calculated relative to its nearest neighbors in four directions: front, back, left, and right (along and across flight lines).
- Geometric Significance: These changes can be positive, negative, or zero. Crucially, the combination and number of these changes allow the algorithm to distinguish between points lying on flat planes, edges, and corners. This eliminates the need to pre-separate planar and non-planar points, as the elevation change variable inherently identifies intersections and boundaries.
Cluster Number Determination:
Since PAM requires a pre-defined number of clusters ( $k$ ), the authors employ a potential-based selection system (Chiu, 1994) to estimate $k$ automatically.
- Potential Calculation: A potential score is computed for each data point based on its distance to neighbors within a fixed radius ( $r_\alpha$ ).
- Optimal Radius: The study determines that the optimal $r_\alpha$ lies between 20% and 40% of the distance between the two most distant points on the rooftop.
- Selection Process: The point with the highest potential is selected as the first medoid. Subsequent medoids are selected iteratively, with potential scores revised to prevent the selection of medoids that are too close to previously chosen ones. The process stops when the potential of a new candidate falls below a specific threshold relative to the first medoid.

Key Contributions

Simplicity and Efficiency: The proposed method achieves high-quality segmentation without the heavy computational burden, model training, or multi-stage optimization required by deep learning or complex region-growing algorithms.
Direct Application: The method processes raw LiDAR data directly, avoiding the need to remove non-planar points or re-fit them after clustering.
Novel Feature Set: By utilizing elevation changes instead of normal vectors, the method simultaneously segments planes and identifies geometric features (edges and corners) that normal vectors often miss.
Robust Clustering: The application of PAM to rooftop segmentation demonstrates that hard clustering methods can effectively handle irregular rooftop geometries when paired with appropriate input variables.

Results
The method was tested on LiDAR data from 150 buildings in Kuopio and Vuorela, Finland, with an average point density of 5 points per square meter. The segmentation results were evaluated using completeness (at the segment level) and correctness (at the point level).

Performance Metrics: The proposed method achieved an average completeness of 95.9% and correctness of 98.1%.
Comparative Analysis: As shown in the paper's quantitative comparison, these results are competitive with, and in terms of correctness superior to, more complex state-of-the-art methods, including boundary-aware clustering (93.3% correctness), metric-learning deep learning (97.1% correctness), and octree-based hybrid region growing (93.3% correctness).
Observations: While the method performs well, the authors note that mislabeling can occasionally occur at segment edges and intersections due to geometric similarities, and segment boundaries may appear rough due to inconsistent LiDAR point distribution.

Significance and Claims
The paper claims that its primary significance lies in demonstrating that a simple, parameter-light approach can yield results comparable to complex, multi-stage methods. The authors emphasize that the combination of elevation changes serves as a robust replacement for normal vectors, providing essential geometric information (edge and corner detection) that aids in 3D reconstruction and boundary extraction. The study concludes that the proposed method is highly adaptable to various rooftop structures and reduces the dependency on external data sources like aerial imagery, making it a practical solution for immediate rooftop plane segmentation. The authors modestly suggest that while the current results are strong, further optimization could potentially enhance performance even further.