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:

Zitat von taaktaak (Beitrag 1068374)

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:

Zitat von taaktaak (Beitrag 1068398)

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...

[jfheins]

Zitat:

Zitat von taaktaak (Beitrag 1068409)

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...

Ja, tut mir Leid - ist korrigiert.

Vielleicht etwas anschaulicher: http://www.youtube.com/watch?v=7QrnwoO1-8A
Der Kinect-Controller ist ja auch eine Art Laserscanner. In jede Richtung kann das Teil die Strecke bis zur nächsten Oberfläche ermitteln - aber dahinter sind dann eben diese Abschattungen.

Steht überhaupt eine Veränderung der Messungen zur Debatte oder ist die Punktewolke gegeben und du musst das Beste daraus machen?

[taaktaak]

Obwohl das nicht mein Fachgebiet ist, finde ich das schon recht interessant. Nach kurzer Internet-Recherche habe ich herausgefunden, dass es offenbar Scanner gibt, die

Zitat:

Für jedes reflektierte Signal ... einen dreidimensionalen Punkt und einen Intensitätswert

liefern. Es wäre zu prüfen, ob dies in diesem konkreten Fall auch so ist. Das würde erklären, dass das Scanbild unterschiedlich eingefärbt werden kann. Wenn meine Vermutung zutrifft, könnte ggf. zielführender der Intensitätswert ausgewertet werden.

PS: Auch wenn ich der englischen Erläuterung nicht wirklich folgen konnte, das Video ist tatsächlich sehr anschaulich!

[Cyberstorm]

Zitat:

Zitat von Uwe Raabe (Beitrag 1068390)

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.

das ganze soll im batch für jede menge punktwolken passieren, damit ist punkte von hand festlegen schonmal raus. auch sind die punkte nicht eindeutig, haben keine einzigartige id für jede wolke...
rechnerisch wäre das nicht das problem denke ich. da ich die wolken vorher auf einen akzeptablen wert reduzieren kann. wie berechne ich denn einen Ebenen-Koeffizienten in delphi?

Zitat:

Zitat von taaktaak (Beitrag 1068391)

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...

die bedingung die nur für den boden zutrifft ist einfach und habe ich auch schon geschrieben: es sind viele punkte, die eine relativ planare fläche bilden...
das mit dem grün ist nur eine darstellungssache. das hat nichts mit meinen daten zu tun. ich habe einfach nur die im ersten thread genannten daten, einen array von xyz-koordinaten.

Zitat:

Zitat von Medium (Beitrag 1068394)

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.

die ebene die ich entfernen will (der boden) liegt irgendwo im raum, das weiß ich vorher nicht, habe ich aber auch schon geschrieben...
das ein paar punkte flöten gehen ist schon ok (z.b. in meinem fall die unteren cm. der schuhe meinetwegen.)

Zitat:

Zitat von ibp (Beitrag 1068397)

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.

die bilder sind wie gesagt nur zur visualisierung meiner daten gedacht gewesen...

Zitat:

Zitat von taaktaak (Beitrag 1068398)

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?

es handelt sich wie später auch schon vermutet um einen scan mittels kinect. der schatten entsteht, weil das system mit einem infrarot laser mit einer optik punkte in den raum projeziert, über diese dann die entfernung zur kamera ermittelt werden. da gibt es funktionsbedingt schatten.

Zitat:

Zitat von jfheins (Beitrag 1068406)

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.

richtig, danke ich schau mir die methode mal an.

Zitat:

Zitat von taaktaak (Beitrag 1068409)

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...

ist wie gesagt mit einem gerät nicht zu verhindern. und das der schatten nicht so aussieht wie du ihn vermutest liegt einfach da dran, dass ich die 3d-punktwolke nicht aus dem gleichen winkel betrachte, aus dem sie aufgenommen wurde (sonst würde man auch kaum einen schatten wahrnehmen.

Zitat:

Zitat von taaktaak (Beitrag 1068415)

Obwohl das nicht mein Fachgebiet ist, finde ich das schon recht interessant. Nach kurzer Internet-Recherche habe ich herausgefunden, dass es offenbar Scanner gibt, die

Zitat:

Für jedes reflektierte Signal ... einen dreidimensionalen Punkt und einen Intensitätswert

liefern. Es wäre zu prüfen, ob dies in diesem konkreten Fall auch so ist. Das würde erklären, dass das Scanbild unterschiedlich eingefärbt werden kann. Wenn meine Vermutung zutrifft, könnte ggf. zielführender der Intensitätswert ausgewertet werden.

PS: Auch wenn ich der englischen Erläuterung nicht wirklich folgen konnte, das Video ist tatsächlich sehr anschaulich!

zerbrich dir nicht den kopf über farben ;-). wie gesagt ich habe xyz koordinaten. es handelt sich nur um eine visuelle darstellung in einem externen programm...
und trotzdem ich passend gemappte rgb-werte für die punktwolke habe bringen die mich nicht weiter, weil wenn der boden das nächste mal eine andere farbe hat usw...

beim nächsten mal würde ich einfach das model auf einer erhöhung abfilmen und auch das ausrichten des kinects auf den boden vermeiden, dann hätte ich diese probleme nicht.
aber der dreh ist schon vorbei und ich habe 30gb daten zu verarbeiten für ein musikvideo ;-)

[KarstenK]

Hi,

ist die Reihenfolge der Punkte geordnet?

Ich könnte mir vorstellen, dass sie in horizontal und vertikal Winkel in einem "rechteckigen Raster" angeordnet sind.

Damit könntest Du aus jeweils 3 benachbarten Punkte ein Masche bilden und damit die Normale/Abstand der Ebene erzeugen. Über die Verteilung der Normalen (Die Maschen sollten immer die gleiche haben (+- epsilon) sollte dann die Normale/Abstand der Grundfläche ermittelt werden können. Damit können dann die Punkte entfernt werden.

PS: Da ich nicht weiß wie stark die Messwerte streuen, kann die Normale aus den benachbarten Punkte sehr stark (zu stark) streuen.

[GPR-Man]

Scanner liefern die Daten meist in der Reihenfolge in der die Punkte augenommen wurden, dann sollte sich auch etwas über diese Information machen lassen. Falls dies nicht der Fall ist, bleibt nur etwas brute-force. Hough scheint mir dazu aber viel zu aufwendig und langsam. Ich würde vorschlagen die Punktewolke in kleinere 3D Würfel aufzuteilen. Durch die Punkte in jedem Würfel legt man eine Ebene mit least-squares und berechnet zudem die Varianz. Über einen Vergleich der Varianz (müsste kleiner als ein bestimmter Schwellwert sein) und der Ebenennormalen (wohl am besten Median) sollte sich die Ebene definieren lassen, sprich aus den Daten der der betroffenen Würfel neu berechnen und dann, wie bereits gesagt, innerhalb eines Grenzwertes oberhalt und unterhalb beseitigen. Die Intensität schwankt normalerweise zu stark, als dass man diese einbeziehen könnte.