3D Punktwolken und GroundDetection

[Cyberstorm]

Hallo.

Ich zerbreche mir die ganze Zeit den Kopf über folgendes Proglem was ich habe (leider ohne Erfolg bis jetzt):
Ich habe eine Punktwolke:

Delphi-Quellcode:

type
T3DPoint = record
  x, y, z: Single;
end

var
  Punktwolke: Array of T3DPoint;

Ich möchte nun in der Punktwolke den Boden löschen (eine einigermaßen planare Fläche). Es ist immer die Einzige planare Fläche in der Wolke!
Folgende vorgehensweise habe ich mir überlegt:

• Nacheinander Punktepaare auswählen
• Prüfen ob diese in einer Ebene liegen
• ggf. löschen

Was mir unklar ist:
Brauche ich 3er Punktepaare oder 4er?
Wie kann ich errechnen, ob die ausgewählten Punkte auf einer Ebene liegen (mit x % Toleranz)?

[taaktaak]

Moin, Moin.
Eine Ebene im Raum wird durch mindestens 3 Punkte eindeutig definiert. Damit wird dann aber tatsächlich eine Ebene (und nicht eine einigermaßen plane Fläche) festgelegt. Das Wichtigste scheint mir hier die Definition des "Boden" zu sein - ist damit die Ebene gemeint, die durch die 3 Punkte mit den kleinsten "Hochwerten" gebildet wird? Oder gibt es eine andere Anforderung? Ist die Boden-Ebene definiert, reduziert sich der Rest wohl auf die Fragestellung "Punkt in Ebene?"

[Cyberstorm]

moin

Zitat von taaktaak:

Das Wichtigste scheint mir hier die Definition des "Boden" zu sein - ist damit die Ebene gemeint, die durch die 3 Punkte mit den kleinsten "Hochwerten" gebildet wird? Oder gibt es eine andere Anforderung? Ist die Boden-Ebene definiert, reduziert sich der Rest wohl auf die Fragestellung "Punkt in Ebene?"

Ich habe mal zwei Bilder zur verdeutlichung hinzugefügt. Es handelt sich einen "realen" "Boden" von einem 3D-Scan. Ich meine mit "Boden" also viele 3D-Koordinaten, welche zusammen eine "einigermaßen" planare Fläche ergeben. Diese möchte ich entfernen.

Dieser Boden ist in meinem lokalen Koordinatensystem aber "verdreht" -- also irgendwo im Raum. Sonst könnte ich ja alle Punkte mit einer Höhe weniger X wegschmeißen...
Ich hoffe nun ist klar, was ich meine?!

Danke und viele Grüße

[Uwe Raabe]

Ich denke mal, du hast nur eine Chance, wenn du mindestens drei Punkte festlegen kannst, von denen du weißt, daß sie in der Ebene liegen. Ansonsten musst du über alle 3er-Kombinationen iterieren und die Ebenen-Koeffizienten berechnen und dann statistisch die wahrscheinlichste Ebenengleichung bestimmen. Die Anzahl der 3er-Kombinationen bei n Punkten ist n*(n-1)*(n-2)/6, was schnell eine ziemlich hohe Zahl ergeben kann (z.B. bei n=1000 gibt das schon 166.167.000 Kombinationen). Das ist in vertretbarer Zeit nicht zu machen. Da kommst du nur mit einem anderen Verfahren zum Ziel. Ohne weitere Kenntnisse über die Datenmenge kann man da aber nur schwer eine Aussage treffen.

[taaktaak]

Ok, jetzt ist die Sache schon konkreter. Aber nun fehlt mir ebenfalls eine zündende Idee. Selbst wenn die "Boden-Ebene" nicht willkürlich im lokalen Koordinatensystem vorliegen würde, fällt mir spontan keine Bedingung ein, die "nur" von den Bodenkoordinaten erfüllt werden. Interessant ist zwar, dass das Scanbild den Boden überwiegend in sehr dunklem Grün darstellt, aber eben auch nur überwiegend. Teilweise nimmt die Bodendarstellung auch die Farbe der gescannten Dame an - sorry, da muss ich passen. Ist wohl eher eine Problemstellung für einen Mathematiker...

[Medium]

Liegt der Boden immer im wesentlichen in der XZ-Ebene und ist dort in alle Richtungen am "größten"? Wenn ja, könntest du ggf. eine Hand voll Punkte mit maximalem XZ-Abstand zum XZ-Zentrum der Wolke ermitteln um eine Schätzung der Y-Varianz zu ermitteln, und daraus 2 XZ-Ebenen ableiten zwischen denen du alle Punkte killst. Unabdingbare Voraussetzung ist hier eben, dass der Scan weitestgehend "gerade" ist.
Man wird vermutlich aber nie ganz verhindern können, dass entweder einzelne Bodenpunkte bleiben, oder ein paar der vom Objekt löscht, die direkten Kontakt haben.

[ibp]

wie wäre es um drei Punkte vom Boden zu ermitteln einen "scan" horizontal von unten zur Bildmitte, dann den ersten den du findest. Das gleiche dann nochmal mit einer Vertikalen von rechts und links zur Mitte.

[taaktaak]

Mal eine spontane Überlegung:
Beim Betrachten der wohlgeformten Extremität des ersten Bildes fällt auf, dass so etwas wie ein "Schattenwurf" erzeugt wird; teilweise fehlen in einem Bereich des Bodens die dargestellten Bildpunkte. Warum? Viellicht sollte die Aufgabenstellung nicht durch die auswertende Software gelöst, sondern bereits zu einem früheren Zeitpunkt vermieden werden.
Was führte in dem Beispielbild dazu, dass "hinter dem Bein" keine Bildpunkte gescannt wurden? Kann man dies u.U. nutzen um die Übertragung der Bodenebene von vornherein zu vermeiden?

[jfheins]

Zitat von taaktaak:

Mal eine spontane Überlegung:
Beim Betrachten der wohlgeformten Extremität des ersten Bildes fällt auf, dass so etwas wie ein "Schattenwurf" erzeugt wird; teilweise fehlen in einem Bereich des Bodens die dargestellten Bildpunkte. Warum? Viellicht sollte die Aufgabenstellung nicht durch die auswertende Software gelöst, sondern bereits zu einem früheren Zeitpunkt vermieden werden.
Was führte in dem Beispielbild dazu, dass "hinter dem Bein" keine Bildpunkte gescannt wurden? Kann man dies u.U. nutzen um die Übertragung der Bodenebene von vornherein zu vermeiden?

Das liegt daran, dass der Laserscanner auch nur normales Licht benutzt um zu scannen. was hinter dem Bein ist, sieht er nicht und dort können auch keine Datenpunkte gesammelt werden.

Zum Problem. Die Holzhammermethode, die mir jetzt spontan einfällt ist die Hough-Transformation - Eine Ebene hat 3 Parameter. ist sicherlich einiges an Rechenaufwand, aber es sollte gehen.

[taaktaak]

Zitat:

nur normales list benutzt

Was ist darunter zu verstehen?
Meintest du "Licht"?

Anyway - Der Grundgedanke, das einscannen des Bodens zu verhindern, könnte möglicherweise zu einer effizienten Lösung führen. Die Frage, ob dieses mit vertretbarem Aufwand realisiert werden kann, würde ich (auch als Programmierer) schon stellen.

PS: Dann ist der Sichtschatten des Scanners aber seltsam...