Eigenwerte und Eigenvektoren eines 3D-Bildes Laplace

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.

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.

$$1 - 2 - 3 - 4$$

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] - 2*p[2] + p[3]$$ $$l[3] = p[2] - 2*p[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] - 2*p[1] + p[2]$$ $$l[4] = p[3] - 2*p[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 = M \cdot p$$

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

$$M= \left( \begin{array}{cccc} -2 & 1 & 0 & 1 \\ 1 & -2 & 1 & 0 \\ 0 & 1 & -2 & 1 \\ 1 & 0 & 1 & -2 \\ \end{array} \right)$$

Die Eigenvektoren dieser Matrix sind

$$v_1 = (-1,1,-1,1)$$ $$v_2 = (0,-1,0,1)$$ $$v_3 = (-1,0,1,0)$$ $$v_4 = (1,1,1,1)$$ mit den zugehörigen Eigenwerten $$\lambda_1 = 4 , \lambda_1 = 2 , \lambda_1 = 2 , \lambda_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 Matrix$M$ ist dann

$$M=\left( \begin{array}{cccc} 0 & 0 & 0 & 0 \\ 1 & -2 & 1 & 0 \\ 0 & 1 & -2 & 1 \\ 0 & 0 & 0 & 0 \\ \end{array} \right)$$

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 erhalten$0$ 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.

$$\begin{array}{ccccccccc} && 1 &-& 2 &-& 3 && \\ && | & & | & & | \\ 4 &-& 5 &-& 6 &-& 7 &-& 8 \\ | & & | & & | & & | & & | \\ 9 &-& 10 &-& 11 &-& 12 &-& 13 \\ && | & & | && | & & \\ && 14 &-& 15 &-& 16 && \\ \end{array}$$

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 Punkte$5,6,7,10,11,12$haben daher eine volle 2-d laplace erweiterung. Für Punkt$5$ es sieht zum Beispiel so aus:

$$l[5] = p[4] - 2 p[5] + p[6] + p[1] - 2 p[5] + p[10] \\= p[4] + p[6] + p[1] + p[10] - 4 p[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 erhalten$l[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 Matrixgleichung$L=Mp$, wo die Matrix in diesem Fall hat $16\times 16$Einträge. Um genau zu sein, ist es

$$M=\left( \begin{array}{cccccccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & -2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & -4 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & -4 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & -4 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & -4 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & -4 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & -4 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & -2 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{array} \right)$$

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.

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

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