Ellipsoid fitten

pumpkin_1768a9 · 13. Januar 2009 um 15:45

Moien

ich habe ein Volumen (3D) das in einen aquivalenten* Ellipsoiden umgeformt werden soll. Das Volumen ist als boolsche Funktion IsInside(x,y,z) gegeben, wobei x, y und z ganze Zahlen sind. Wichtig sind mir die Längen der 3 Achsen. Bekannt ist der Mittelpunkt.

Ist der Weg richtig?

den Mittelpunkt auf 0,0,0 verschieben (damit das rechnen einfacher wird)
Alle Punkte i innerhalb des Ellipsoiden als Vektor v_i = (x_i,y_i,z_i) nehmen und die Matrix v_i * v_i^t = M_i ausrechnen.
M = Summe aller M_i bestimmen.
Eigenwerte von M bestimmen.

Ich glaube die Eigenwerte müssten dann den Achslängen entsprechen. Oder klappt das gar nicht … ?

Danke.

* aquivalent im Sinne von gleiches eingeschlossenes Volumen wäre klasse.

anonym1_502ae7 · 13. Januar 2009 um 18:40

Hallo pumpkin,

lies mal das:

http://deposit.ddb.de/cgi-bin/dokserv?idn=967374103

Insbesondere Anhang B.1.

Da geht es zwar um die Ausgleichsebene. Dabei wird nur der zum kleinsten Eigenwert gehörige Eigenvektor benutzt.
Bei einer Ausgleichsgerade nähme man den Eigenvektor, der zum größten Eigenvektor gehört.
Das Ellipsoid ist dann durch alle drei Eigenvektoren bestimmt.

ich habe ein Volumen (3D) das in einen aquivalenten*
Ellipsoiden umgeformt werden soll. Das Volumen ist als
boolsche Funktion IsInside(x,y,z) gegeben, wobei x, y und z
ganze Zahlen sind.

Ich habe das so verstanden: Du suchst ein Ellipsoid, das die Punktwolke, die Du durch IsInside(x, y, z) bekommst möglichst gut annähert.

Es ist hier natürlich problematisch, welche x, y, z Du bei der Auswertung berücksichtigst. Auf den hier genannten Algorithmus kommt man, wenn man Fehlerquadrate minimiert. So wie Du es beschreibst, willst Du wohl eher soetwas wie das kleinste umhüllende Ellipsoid, dafür brauchst Du einen anderen Algorithmus.

Wichtig sind mir die Längen der 3 Achsen.

Und deren Richtung?

Bekannt ist der Mittelpunkt.

Ist der Weg richtig?

den Mittelpunkt auf 0,0,0 verschieben (damit das rechnen
einfacher wird)

Stimmt.

Alle Punkte i innerhalb des Ellipsoiden als Vektor
v_i =
(x_i,y_i,z_i)
nehmen und die Matrix v_i *
v_i^t =
M_i ausrechnen.

M = Summe aller M_i bestimmen.

Da bin ich mir nicht ganz sicher, was Du damit meinst.

Jedenfalls musst Du sechs verschiedene Summen bilden, die die Elemente einer symmetrischen 3x3-Matrix ergeben. Diese Summen findest Du in obigem Link.

Eigenwerte von M bestimmen.

Und die Eigenvektoren, sofern auch die Orientierung des Ellipsoids interessiert.

Ich glaube die Eigenwerte müssten dann den Achslängen
entsprechen.

Über die absoluten Längen bin ich mir nicht ganz sicher, aber die Verhältnisse zueinander stimmen. Dir fhlt also allenfalls nur noch ein Skalierungsfaktor.

* aquivalent im Sinne von gleiches eingeschlossenes Volumen
wäre klasse.

Mit der Funktion IsInside(x,y,z) gegeben, wobei x, y und z ganze Zahlen sind,
bekommst Du nur einzelne Punkte. Du kannst Dich nicht beliebig genau an die Oberfläche herantasten. Insofern ist Dein zu erreichendes Volumen nicht recht gut definiert.

Viele Grüße
Stefan

pumpkin_1768a9 · 13. Januar 2009 um 20:03

Moien

ich habe ein Volumen (3D) das in einen aquivalenten*
Ellipsoiden umgeformt werden soll. Das Volumen ist als
boolsche Funktion IsInside(x,y,z) gegeben, wobei x, y und z
ganze Zahlen sind.

Ich habe das so verstanden: Du suchst ein Ellipsoid, das die
Punktwolke, die Du durch IsInside(x, y, z) bekommst möglichst
gut annähert.

Japp.

Es ist hier natürlich problematisch, welche x, y, z Du bei der
Auswertung berücksichtigst. Auf den hier genannten Algorithmus
kommt man, wenn man Fehlerquadrate minimiert. So wie Du es
beschreibst, willst Du wohl eher soetwas wie das kleinste
umhüllende Ellipsoid, dafür brauchst Du einen anderen
Algorithmus.

Nein, umhüllen wäre doof, da die Wolke durchaus Ausreisser hat. Stell dir als Wolke ein Ball mit Durchmesser 100 bei 0,0,0 und zusätzlich 2-3 Punkte in der Nähe von 1000,1000,1000 vor. Ein Umhüllen-Ansatz würde schon was finden, aber der Körper würde viel, viel mehr Raum umfassen als die ursprüngliche Wolke. Und es geht indirekt um das Volumen (hauptsächlich um die Achsen, aber das ergibt sich ja dann…). Klar kann man die Ausreisser finden und eliminieren, aber wenn es anders geht wäre mir das lieber.

Wichtig sind mir die Längen der 3 Achsen.

Und deren Richtung?

Erstmal völlig wurscht (kann aber noch kommen, das entscheide ich nicht selbst).

den Mittelpunkt auf 0,0,0 verschieben (damit das rechnen
einfacher wird)

Stimmt.

Im Vergleich zu B.1 fallen alle m und M raus.

Alle Punkte i innerhalb des Ellipsoiden als Vektor
v_i =
(x_i,y_i,z_i)
nehmen und die Matrix v_i *
v_i^t =
M_i ausrechnen.

M = Summe aller M_i bestimmen.

Da bin ich mir nicht ganz sicher, was Du damit meinst.

Das ist die Formel aus B.1, nur anders aufgeschrieben. Wenn man das ausschreibt und umstellt kommt das gleiche raus.

Ich glaube die Eigenwerte müssten dann den Achslängen
entsprechen.

Über die absoluten Längen bin ich mir nicht ganz sicher, aber
die Verhältnisse zueinander stimmen. Dir fhlt also allenfalls
nur noch ein Skalierungsfaktor.

Ich habe da einen Verdacht: muss ich die Formel mit allen Punkten aus dem Volumen oder mit allen Punkten der Oberfläche füttern? Die Ellipsoide sind nämlich alle zu klein. Die Oberflächenpunkte finden wird allerdings (relativ) komplex. Die Erfassung macht keinen Unterschied zwischen Oberfläche und Inhalt.

* aquivalent im Sinne von gleiches eingeschlossenes Volumen
wäre klasse.

Mit der Funktion IsInside(x,y,z) gegeben, wobei x, y und z
ganze Zahlen sind,
bekommst Du nur einzelne Punkte. Du kannst Dich nicht beliebig
genau an die Oberfläche herantasten. Insofern ist Dein zu
erreichendes Volumen nicht recht gut definiert.

Diese IsInside arbeitet auf einem grossen 3D Gitter. Die Wolken haben grob 400 Punkte Durchmesser. Für jeden Punkt des Gitters ist bekannt ob er Teil des Körper ist oder nicht (+ Ausreisser). Das Gitter ist regelmässig und jeder Punkt steht für das gleiche Raumvolumen. Volumen abschätzen könnte ich also schon … nur ist die Erfassung nicht wirklich vollständig.

Danke.

JPL · 14. Januar 2009 um 08:53

Moinsen,

Nein, umhüllen wäre doof, da die Wolke durchaus Ausreisser
hat. Stell dir als Wolke ein Ball mit Durchmesser 100 bei
0,0,0 und zusätzlich 2-3 Punkte in der Nähe von 1000,1000,1000
vor. Ein Umhüllen-Ansatz würde schon was finden, aber der
Körper würde viel, viel mehr Raum umfassen als die
ursprüngliche Wolke. Und es geht indirekt um das Volumen
(hauptsächlich um die Achsen, aber das ergibt sich ja
dann…). Klar kann man die Ausreisser finden und eliminieren,
aber wenn es anders geht wäre mir das lieber.

Vielleicht verstehe ich das auch falsch, aber:
Wenn es keine Ausreisse gibt, ist die Umhüllung das einfachste und beste Mittel, alle Punkte per Ellipsoid einzufassen. Wenn es aber Ausreisser gibt, dann wird - wie du schon schreibst- das Ellipsoid zu groß, weil es viel „Leerraum“ enthält (aus raum, in dem kein vorgegebener Punkt liegt). Um das zu umgehen, könntest du die Ausreisser definieren/finden/klassifizieren (z.B. via Clusteranalyse) und erstmal für jedes Cluster eine eigene Hülle berechnen. Anschließend kannst du Hüllen verbinden.

Grüße,
JPL

Roland_Tille · 20. Januar 2009 um 00:25

Hüstel,

keine Ahnung, worum’s eigentlich geht, fand bei der Suche nach einer anderen Frage das hier
http://www.compgeom.com/~piyush/publicat.html
5. Topic.

Grüße Roland