3D-Punktwolken auswerten: Objekte erkennen und vermessen

Bildverarbeitung

Ein 3D-Scanner über einem Förderband liefert eine Punktwolke: viele tausend Punkte im Raum, ungeordnet, verrauscht und mit Lücken. Die Fragen dahinter sind einfach: Was liegt da? Ist es ein Zylinder, ein Quader, eine Kugel? Wie groß ist es, und welches Volumen hat es?

Die Verarbeitungskette

1. Filtern: Bereich zuschneiden, mit einem Voxelgitter ausdünnen, Ausreißer entfernen – in der Point Cloud Library (PCL) mit CropBox, VoxelGrid und StatisticalOutlierRemoval.
2. Untergrund entfernen: Förderband oder Boden als Ebene finden und abziehen.
3. Segmentieren: Die übrigen Punkte nach Nähe in einzelne Objekte aufteilen, etwa mit EuclideanClusterExtraction.
4. Form erkennen: Modelle wie Ebene, Zylinder oder Kugel anpassen und das mit den meisten passenden Punkten nehmen.
5. Vermessen: Abmessungen, umschließende Box und Volumen bestimmen.

RANSAC: robust gegen Ausreißer

RANSAC (Random Sample Consensus) ist das Arbeitspferd der Punktwolkenauswertung. Es wählt immer wieder zufällig die kleinstmögliche Stichprobe – für eine Ebene drei Punkte –, berechnet daraus das Modell und zählt die Punkte im Toleranzband. Das Modell mit den meisten Treffern gewinnt; Ausreißer finden nie genug Unterstützer.

Die nötige Zahl der Durchläufe ist N = log(1 − p) / log(1 − w^s), mit der Sicherheit p, dem Anteil passender Punkte w und der Stichprobengröße s. Liegen 30 % der Punkte auf dem Band, reichen für 99 % Sicherheit rund 170 Durchläufe.

Die kleinste umschließende Box

Für Verpackung, Lagerplatz oder Sortierung zählt oft die kleinste Box um ein Objekt. Die achsparallele Box hängt davon ab, wie das Objekt liegt, die Box entlang der Hauptachsen (PCA) ist nur eine Näherung. Für Objekte auf einem Band gibt es eine elegante Abkürzung, denn die Box steht auf der Bandebene. Man projiziert die Objektpunkte in diese Ebene und sucht das kleinste Rechteck um den Grundriss. Nach Freeman und Shapira liegt eine Seite dieses Rechtecks immer auf einer Kante der konvexen Hülle. Es genügt also, für jede Hüllkante ein Rechteck zu prüfen – das leisten die Rotating Calipers. In Python übernimmt cv2.minAreaRect diese Suche:

import numpy as np
import cv2


def ebene_ransac(punkte, schwelle=2.0, durchlaeufe=200):
    """Ebene, der die meisten Punkte näher als 'schwelle' (mm) liegen."""
    rng = np.random.default_rng(1)
    beste, beste_anzahl = None, 0
    for _ in range(durchlaeufe):
        p1, p2, p3 = punkte[rng.choice(len(punkte), 3, replace=False)]
        n = np.cross(p2 - p1, p3 - p1)
        if np.linalg.norm(n) < 1e-9:  # drei Punkte auf einer Linie
            continue
        n /= np.linalg.norm(n)
        anzahl = np.count_nonzero(np.abs((punkte - p1) @ n) < schwelle)
        if anzahl > beste_anzahl:
            beste, beste_anzahl = (n, -n @ p1), anzahl
    return beste


def vermesse_objekt(punkte, schwelle=2.0):
    n, d = ebene_ransac(punkte, schwelle)
    abstand = punkte @ n + d
    if np.median(abstand) < 0:  # Normale soll vom Band weg zeigen
        n, abstand = -n, -abstand
    oben = abstand > 3 * schwelle
    # Zwei Achsen in der Ebene aufspannen, Objektpunkte hineinprojizieren
    u = np.cross(n, [1.0, 0, 0] if abs(n[0]) < 0.9 else [0, 1.0, 0])
    u /= np.linalg.norm(u)
    grundriss = np.column_stack((punkte[oben] @ u, punkte[oben] @ np.cross(n, u)))
    _, (a, b), _ = cv2.minAreaRect(grundriss.astype(np.float32))
    return max(a, b), min(a, b), np.percentile(abstand[oben], 99)

Für einen simulierten Quader von 120 × 80 × 50 mm auf geneigtem Band mit 0,5 mm Rauschen liefert der Code 120,5 × 80,4 × 50,9 mm. Das 99. Perzentil für die Höhe dämpft einzelne Ausreißer.

Volumen: Box, Hülle oder Höhenkarte

Das Volumen der Box ist nur eine obere Grenze: Ein Zylinder füllt seine Box zu gut drei Vierteln, eine Kugel zu gut der Hälfte. Genauer ist die konvexe Hülle, bei konkaven Objekten aber immer noch zu groß. Da ein Scanner von oben nur die Oberseite sieht, rechnet man das Volumen oft als Höhenkarte: je Zelle des Grundrisses Fläche mal Höhe über dem Band.

Aus der Praxis

Für einen internationalen Sensorhersteller haben wir Software entwickelt, die in den Punktwolken seiner 3D-Scanner Objekte erkennt, ihre Form klassifiziert – Zylinder, Quader, Kugel – und anschließend schnell das Volumen berechnet. Zum Einsatz kamen unter anderem RANSAC, Minimal Bounding Box, Rotating Calipers und Eigenwertberechnungen. Jeden Algorithmus haben wir zuerst in MATLAB vorberechnet und geprüft, bevor er in C++ mit PCL, OpenCV, Halcon und Eigen umgesetzt wurde. Getestet haben wir im Labor mit Scannern an verschiedenen Positionen, mit Daten aus einer Produktionsanlage und mit einer Scandatensimulation, für die wir den Aufbau in 3D modelliert haben.

Typische Fehler

• Ohne Filter rechnen. Ausreißer und Mehrfachreflexionen blähen jede Box auf.
• Die RANSAC-Toleranz kleiner wählen als das Messrauschen – dann findet das Verfahren die Ebene nicht zuverlässig.
• Das Volumen der Box als echtes Volumen ausgeben.
• Nur mit sauberen Labordaten testen. Daten aus der Anlage und simulierte Grenzfälle gehören dazu.

Aus unseren Projekten: Objekterkennung in Punktwolken und Kalibrierung von 3D-Scannern für einen internationalen Sensorhersteller. Weiterführend: M. A. Fischler, R. C. Bolles, „Random Sample Consensus“, Communications of the ACM 24(6), 1981; H. Freeman, R. Shapira, Communications of the ACM 18(7), 1975; Point Cloud Library.