Eigenwerte und Eigenvektoren eines 3D-Bildes Laplace

7

Ich muss die Eigenwerte und Eigenvektoren eines 3D-Bildes Laplace berechnen. Ich versuche, den Wärmekern auf dem einheitlichen 3D-Gitter (der durch das voxelisierte Bild erzeugten einheitlichen Struktur) zu verschiedenen Zeitwerten auszuwerten, um eine volumetrische Wärmekernsignatur zu implementieren (siehe Abschnitt "Numerische Berechnung"). Die Domäne, an der ich arbeite, ist nicht rechteckig, daher habe ich an einigen Rasterpunkten Einsen und an anderen Punkten Nullen, wodurch eine binäre 3D-Form entsteht. Ich habe darüber für 2D gelesen: In 2D wird der Laplace-Wert jedes Gitterpunkts berechnet und dann werden die Eigenwerte und Eigenvektoren der resultierenden Matrix berechnet. Wie kann ich das für 3D machen? Alle Informationen und Beispiele, die ich gelesen habe, sind für 2D-Bilder. Die spezifischen Fragen sind:

  1. Wie kann ich eine Matrix aus dem 3D-Bild erhalten, das ich nach dem Anwenden eines (3x3x3) diskreten Laplace-Operators erhalte?
  2. Wenn es keine Möglichkeit gibt, eine Matrix zu erhalten, sollte ich die Eigenwerte und Eigenvektoren eines 3D-strukturierten Gitters berechnen. Was ist der einfachste Weg, dies zu tun? Könnten Sie mir dafür ein Soft empfehlen?

Ich würde mich über jeden Hinweis sehr freuen.

Danke im Voraus.

Federico
quelle
Wie von @nikie hervorgehoben, klären Sie bitte Ihre Frage. Möchten Sie 3D-Ableitungen für die Wärmeverteilung berechnen, dh ein 3D-Vektorfeld über dem Gitter erzeugen?
Dr.D.
Vielen Dank, Dr.D. Ich habe der Frage weitere Informationen und einen Verweis auf das Papier hinzugefügt, das ich implementieren möchte.
Federico
Ich habe keine Ahnung, was eine volumetrische Hörsignatur ist, also kann ich mich irren, aber ich denke, der Artikel, auf den Sie bereits verlinkt haben, handelt von 3D-Formen, nicht wahr? So wie ich es verstehe, kann der Laplace-Wert als Matrixmultiplikation angesehen werden (da er linear ist), und Sie sollten die Eigenwerte dieser Matrix finden (dh eine Matrix mit einer Zeile für jedes Voxel und einer Spalte für jedes Voxel). .
Niki Estner
Ich denke, er versucht, die Eigenwerte des Laplace in 3D zu finden. (aber ich kann mich irren)
Beni Bogosel

Antworten:

3

Diese Antwort kommt etwas spät, aber ich denke, dass es notwendig ist, einige der Unklarheiten darüber zu beseitigen, was die Eigenstruktur eines Laplace ist und wie sie berechnet wird.

Zunächst muss betont werden, dass es nicht um Eigenschaften des lokalen Kernels geht, der zur Berechnung diskreter Ableitungen verwendet wird. Stattdessen müssen Sie den Laplace-Operator als linearen Operator für einen Vektorraum verstehen, dessen Elemente in Ihrem Fall die Volumendatensätze sind.

Das bedeutet, dass der Laplace-Operator eine lineare Karte ist, die einen Vektor (Datensatz) einem anderen Vektor (Datensatz) zuordnet. In diesem Zusammenhang sind die Eigenvektoren des Laplace wiederum Vektoren (Datensätze) in demselben Vektorraum. Die Antwort auf Ihre Frage wäre also ein Satz volumetrischer Datensätze, tatsächlich so viele wie die Dimension Ihres Vektorraums (dh die Anzahl unabhängiger Voxel).

Betrachten wir ein sehr einfaches Beispiel. Nehmen Sie ein eindimensionales Bild, dh eine einzelne Pixelreihe, und verwenden Sie auch nur sehr wenige Pixel, nämlich 4. Dann müssen die beiden mittleren Pixel die Nachbarn lenken, während das erste und das letzte Pixel jeweils nur einen Nachbarn haben.

1234

Mit dieser Pixelgeometrie können wir das Ergebnis des diskreten Laplace-Operators für die beiden mittleren Pixel 2 und 3 als lineare Funktionen der Pixelwerte angeben:

l[2]=p[1]2p[2]+p[3]
l[3]=p[2]2p[3]+p[4]

Die anderen beiden Pixel 1 und 4 haben nicht genügend direkte Nachbarn, um die diskrete zweite Ableitung zu berechnen. Wir könnten dies beheben, indem wir annehmen, dass die Pixel 1 und 4 direkte Nachbarn sind, die Topologie zu einem Kreis schließen und eine sogenannte kreisförmige Randbedingung auferlegen. Oder wir nehmen einfach die zweiten Ableitungen an den Grenzen, um zu verschwinden. Lassen Sie uns beides tun, aber mit der zyklischen Randbedingung beginnen. Also haben wir:

l[1]=p[4]2p[1]+p[2]
l[4]=p[3]2p[4]+p[1]

Diese Abbildung ist linear und kann als Matrixgleichung geschrieben werden, wobei der Spaltenvektor abgebildet wird p:=(p[1],p[2],p[3],p[4]) zu l=(L[1],L[2],L[3],L[4]) durch Multiplikation mit der Matrix M.

L=Mp

Wir nennen diese Matrix die diskrete Darstellung des Laplace-Operators, und in unserem Fall ist dies der Fall

M=(2101121001211012)

Die Eigenvektoren dieser Matrix sind

v1=(1,1,1,1)
v2=(0,1,0,1)
v3=(1,0,1,0)
v4=(1,1,1,1)
mit den zugehörigen Eigenwerten
λ1=4,λ1=2,λ1=2,λ1=0

Sie können diese Vektoren als Basisvektor der diskreten Fourier-Transformation auf diesem Vektor und die Eigenwerte als ihre diskreten Frequenzen erkennen. Dies trifft im Allgemeinen zu, und tatsächlich verallgemeinert die Zerlegung eines Vektors (oder allgemeiner einer Funktion) in das Eigenspektrum eines Laplace-Operators die Idee der Fourier-Transformation.

Lassen Sie uns nun untersuchen, was passiert, wenn wir wo die alternativen Randbedingungen verwenden l[1]=0 und l[4]=0. Die MatrixM ist dann

M=(0000121001210000)

Offensichtlich hat diese Matrix einen anderen Satz von Eigenvektoren und Eigenwerten. Sie sind nicht so intuitiv und interessant, deshalb werde ich sie nicht explizit auflisten. Es ist jedoch erwähnenswert, dass wir jetzt den Eigenwert erhalten0 zweimal bedeutet dies, dass der Eigenraum, in dem der Laplace-Wert verschwindet, zweidimensional ist.

Wie ändern sich die Dinge, wenn wir ein richtiges Bild anstelle einer einzelnen Pixelreihe haben? Nicht viel. Wir müssen nur den Laplace-Wert für jedes einzelne Pixel notieren, während wir die direkte Nachbarbeziehung oder Topologie des Bildes berücksichtigen. Um die Sache etwas kniffliger zu machen, nehmen wir ein unregelmäßig geformtes zweidimensionales Bild.

123|||45678|||||910111213|||141516

Offensichtlich müssen wir jetzt einen zweidimensionalen Laplace-Wert nehmen, indem wir die zweiten partiellen Ableitungen in horizontaler und vertikaler Richtung summieren. Dafür benötigen wir die beiden direkten Nachbarn in jede Richtung. Die inneren Punkte5,6,7,10,11,12haben daher eine volle 2-d laplace erweiterung. Für Punkt5 es sieht zum Beispiel so aus:

l[5]=p[4]2p[5]+p[6]+p[1]2p[5]+p[10]=p[4]+p[6]+p[1]+p[10]4p[5]

Für die Eckpunkte 1,3,4,8,9,13,14,16 Wir können keine diskrete zweite Ableitung konstruieren, also verwenden wir eine Randbedingung, z l[1]=0

Es sind noch zwei Punkte übrig, 2 und 15. Beide haben zwei direkte Nachbarn in horizontaler Richtung, jedoch nicht in vertikaler Richtung. Wir können daher eine Randbedingung anwenden, die nur die vertikale Richtung beeinflusst, indem wir die vertikale zweite Ableitung auf Null setzen, während wir die diskrete zweite Ableitung horizontal auswerten und erhaltenl[2]=p[1]2p[2]+p[3] und ebenso für l[15].

Nach dieser Konstruktion erhalten wir eine lineare Gleichung für jeden Punkt, der sie mit den Pixelwerten in Beziehung setzt. Wieder schreiben wir es als MatrixgleichungL=Mp, wo die Matrix in diesem Fall hat 16×16Einträge. Um genau zu sein, ist es

M=(0000000000000000121000000000000000000000000000000000000000000000100141000100000001001410001000000010014100010000000000000000000000000000000000000000100014100100000001000141001000000010001410010000000000000000000000000000000000000000000001210000000000000000)

Und wieder können wir nach dem Eigensystem dieser Matrix suchen. Eine schöne physikalische Interpretation der Bilder, die Sie als Eigenvektoren erhalten, besteht darin, dass sie die Schwingungsmoden einer Membran darstellen, die wie Ihr Bild geformt ist, wobei die Frequenzen durch die Eigenwerte gegeben sind.

Sie können dieses Spiel problemlos auf eine beliebige Anzahl von Dimensionen erweitern, solange Sie die Nachbarschaftsbeziehungen zwischen Ihren Voxeln kennen. Formulieren Sie einfach die individuelle lineare Gleichung wie oben, konstruieren Sie eine Matrix und finden Sie das Eigensystem.

Mit den aus den Eigenvektoren des Laplace gewonnenen Informationen kann das Lösen von Differenzgleichungen mit dem diskreten Laplace stark vereinfacht werden. Sobald die Eigenstruktur gefunden ist, können abhängig von der Geometrie der Region alle Datensätze leicht in die Eigenbasis zerlegt werden und die Differenzgleichungen werden trivial.

Jazzmaniac
quelle
0

Es ist nicht klar, was Sie versuchen: Der Laplace-Wert ist ein Skalarwert, keine Matrix. Es hat also keine Eigenwerte. Vielleicht meinst du die Eigenwerte / -vektoren des Hessischen?

Um die Eigenwerte und den Eigenvektor des Hessischen zu berechnen, berechnen Sie zunächst das Hessische (eine symmetrische 3x3-Matrix, die die zweiten Ableitungen in jeder der drei Richtungen enthält) für jedes Pixel. Eine einfache Möglichkeit, dies zu tun, besteht darin, drei Verlaufsfilter (in x-, y-, z-Richtung) auf Ihr 3D-Bild anzuwenden. Jetzt haben Sie 3 Bilder. Auf jedes dieser Bilder wenden Sie erneut drei Verlaufsfilter an, die 3x3-Ergebnisbilder ergeben, die die 3x3-Einträge der hessischen Matrix für jedes Pixel enthalten. (Da die Gradientenfilter pendeln, I * gx * gy = I * gy * gx, müssen Sie wirklich nur 6 davon berechnen.)

Es gibt zwei Möglichkeiten, die Eigenwerte und -vektoren dieser 3x3-Matrix zu erhalten: Finden Sie entweder die Wurzeln des charakteristischen Polynoms oder verwenden Sie eine iterative Methode. Das charakteristische Polynom ist kubisch, daher schätze ich, dass iterative Methoden in der Praxis schneller sind (da Kubikwurzeln viel länger brauchen, um die einfache Addition / Multiplikation zu berechnen).

Niki Estner
quelle
Ich werde mein Problem in der Hoffnung darlegen, dass es die Frage klärt. Ich versuche, den Wärmekern auf einem einheitlichen 3D-Gitter zu verschiedenen Zeitwerten zu bewerten. Das Volumen, an dem ich arbeite, ist nicht rechteckig, daher habe ich an einigen Rasterpunkten Einsen und an anderen Punkten Nullen, wodurch eine binäre 3D-Form entsteht. Ich habe darüber in 2D gelesen: In 2D wird der Laplace-Wert jedes Gitterpunkts berechnet und dann werden die Eigenwerte und Eigenvektoren der resultierenden Matrix berechnet. Wie kann ich das für 3D machen?
Federico
Aha. Bitte aktualisieren Sie Ihre Frage mit diesen Informationen, damit ich meine Antwort löschen kann (die Frage wird offensichtlich nicht beantwortet). Beachten Sie beim Aktualisieren Ihrer Frage, dass eine "2D-Matrix" normalerweise eine Matrix mit 2 Zeilen und 2 Spalten bedeutet. Eine 3D-Matrix ist eine Matrix mit 3 Zeilen und 3 Spalten. Ich denke, was Sie meinen, ist keine 3D-Matrix, sondern ein Tensor 3. Ordnung, der überhaupt keine Matrix ist.
Niki Estner
Eigentlich denke ich, dass Ihre Antwort durchaus relevant sein kann. Es ist derselbe Begriff, auf den ich bei dieser Veröffentlichung hingewiesen habe. Es ist einfach nicht ganz klar, wie es auf das 3D-Gitterproblem des OP anwendbar ist.
Dr.D.
0

Vielleicht hilft das (?).

http://en.m.wikipedia.org/wiki/Kronecker_sum_of_discrete_Laplacians

L = Dxx ¤ I ¤ I + I ¤ Dyy ¤ I + I ¤ I ¤ Dzz

Dabei ist ¤ das Kronecker-Produkt (es ist nicht das richtige Symbol, ich wusste nicht, wie ich es hierher bringen kann). Ich denke, die Eigenwerte und Eigenvektoren werden aus der resultierenden Matrix pro Voxel berechnet.

Das Tensorkonzept, wie es im folgenden Abschnitt 4 beschrieben wird, scheint verwandt zu sein, obwohl es nicht genau dasselbe ist. Es ist jedoch eng mit der hessischen Matrix verwandt, wie in der Antwort von @ nikie erwähnt.

Carsten Steger, Subpixel-präzise Extraktion von Linien und Kanten, Internationales Archiv für Photogrammetrie und Fernerkundung (2000).

Das Papier finden Sie hier: http://ias.in.tum.de/people/steger/publications

Dr.D.
quelle