[PYTHON] Niedrigrangige Approximation von Bildern durch HOSVD und HOOI

Einführung

Das Zerlegen eines Tensors in eine Reihe von Tensoren (Kerntensoren) und Matrizen mit niedrigem Rang wird als [Tucker-Zerlegung] bezeichnet (https://en.wikipedia.org/wiki/Tucker_decomposition). Unter den Verfahren werden HOSVD (Singularwertzerlegung höherer Ordnung) und HOOI (höhere orthogonale Iteration von Tensoren) verwendet, um eine Annäherung des Bildes mit niedrigem Rang durchzuführen.

Der Quellcode ist https://github.com/kaityo256/hooi_sample Beim.

Tucker-Zersetzung des Tensors

Angenommen, Sie haben einen Tensor dritter Ordnung $ X $ und die Abmessungen jedes Fußes sind $ R_1, R_2, R_3 $. Zu diesem Zeitpunkt der Tensor dritter Ordnung $ \ chi $, dessen Fußabmessungen $ r_1, r_2, r_3 $ sind, und die Matrix $ A_i (i = 1,2,3) $ in der Spalte $ r_i $ Zeile $ R_i $. Zerlegen in. Diese Matrix $ A_i $ ändert ihre Dimension von $ r_i $ in $ R_i $, wenn sie auf das $ i $ -te Bein des Kerntensors reduziert wird, dh $ A_i $ kehrt vom Kerntensor zum ursprünglichen Tensor zurück. Es wird eine Prozession. Wenn Sie dagegen das $ i $ -te Bein des ursprünglichen Tensors und die Kontraktion von $ A_i ^ \ dagger $ nehmen, ändert sich die Dimension des Beins von $ R_i $ zu $ r_i $, dh $ A_i ^ \ dagger $ wird projiziert. Es ist eine Prozession. Es sieht so aus, wenn jedes abgebildet ist.

Zunächst wird der Kerntensor $ \ chi $ erhalten, indem jeder Zweig des ursprünglichen Tensors $ X $ mit einer Projektionsmatrix multipliziert wird.

Das Ergebnis der Multiplikation jedes Schenkels des Kerntensors $ \ chi $ mit der Wiederherstellungsmatrix ist auch der Tensor $ X '$, der eine Annäherung an den ursprünglichen Tensor darstellt.

Ursprünglich war die Informationsmenge im Tensor $ R_0 R_1 R_2 $, aber da die Anzahl der Elemente im Kerntensor $ r_0 r_1 r_2 $ und die Anzahl der Elemente in der Matrix $ A_i $ $ R_i r_i $ beträgt, beträgt die Anzahl der Elemente nach der Komprimierung Es wird $ r_0 r_1 r_2 + R_0 r_0 + R_1 r_1 + R_2 r_2 $.

Die Tucker-Zerlegung ist das Problem, die Menge $ A_i $ der Projektionsmatrix zu finden, die dem ursprünglichen Tensor angesichts der Abmessungen des ursprünglichen Tensors $ X $ und des Kerntensors so genau wie möglich nahe kommt. Lassen Sie uns dies mit zwei Methoden tun, HOSVD und HOOI, basierend auf der niedrigrangigen Approximation des Bildes.

HOSVD

Bei der HOSVD (Singularwertzerlegung höherer Ordnung) wird der Tensor mit vielen Beinen zunächst in zwei Beine aufgeteilt, wobei das eine zu beachten und das andere zu beachten ist. Da dies eine Matrix ist, kann dann SVD (Singular Value Decomposition) angewendet werden. Nach der SVD ist die Wiederherstellungsmatrix des interessierenden Fußes derjenige, der den oberen Rang der rechten Matrix eingenommen hat. HOSVD ist ein Verfahren, das dies für alle Beine wiederholt.

Konzentrieren Sie sich in der obigen Abbildung auf das erste Bein des dreibeinigen Tensors $ X $ und SVD das zweite und dritte Bein zusammen als Matrix von $ R_2 R_3 \ mal R_1 $. .. Dann erscheint auf der linken Seite eine quadratische Matrix von $ R_2 R_3 \ mal R_2 R_3 $ und auf der rechten Seite $ R_1 \ mal R_1 $, aber diejenige, die die obere Reihe $ r_1 $ auf der rechten Seite nimmt, ist die Wiederherstellungsmatrix $ A_1 $ des ersten Schenkels. Werden. In ähnlicher Weise können $ A_2 $ und $ A_3 $ erhalten werden.

HOOI

Nun ist bekannt, dass HOSVD nicht die beste Annäherung liefert. HOOI (höhere orthogonale Iteration von Tensoren) verbessert dies durch Iteration.

Bereiten Sie zunächst die Wiederherstellungsmatrix $ A_i $ zunächst zufällig vor. Dann zerdrücken Sie mit Ausnahme des Fußes von Interesse (zum Beispiel Nr. 1) den Fuß des ursprünglichen Tensors mit $ A_i (i \ neq 1) $. Dann wird wie bei HOSVD die Matrix der interessierenden Beine und der anderen Beine mit SVD multipliziert, und das obere $ r_1 $ der resultierenden Matrix wird als das neue $ A_1 $ genommen.

Beachten Sie, dass der für SVD erforderliche Rechenaufwand erheblich gesunken ist, da die Abmessungen mithilfe der Projektionsmatrix mit Ausnahme des interessierenden Fußes verringert wurden.

Dies wird für alle Beine als eine Schleife ausgeführt, und die Genauigkeit wird durch Drehen dieser Schleife verbessert.

Niedrigrangige Annäherung des Bildes

Ein zweidimensionales Bild kann als Tensor dritter Ordnung mit Dimensionen (Höhe, Breite, 3) betrachtet werden, da der Pixelwert durch Angabe der x-Koordinate, der y-Koordinate und der Farbe (RGB) bestimmt wird. Von diesen wird die Matrix, die die Höhe und Breite zerquetscht, durch HOSVD und HOOI erhalten, und das Bild wird durch einen niedrigen Rang angenähert. Informationen zu HOSVD finden Sie unter Frühere Artikel.

Bei einem Bild mit einer Breite von $ w $ und einer Höhe von $ h $ sollten Sie die Breite auf $ r1 $ und die Höhe auf $ r2 $ reduzieren. Was wir finden wollen, ist eine Projektionsmatrix, die die Breite und Höhe zerquetscht. Sei dies $ a_1 ^ \ Dolch, a_2 ^ \ Dolch $. Was die Farbe betrifft, gibt es nur 3 Dimensionen, also werde ich sie nicht zerdrücken.

Zunächst müssen die Anfangswerte von $ a_1 und a_2 $ vorbereitet werden. Der Anfangswert kann beliebig sein [^ 1], aber jede Zeile muss orthogonal sein. Ich konnte mir keinen guten Weg vorstellen, es zu geben, also habe ich eine zufällige Matrix aus $ w \ times w $ und $ h \ times h $ erstellt, SVD it und die oberen Zeilen $ r_1 und r_2 $ abgerufen. Ich habe es als Wert versucht.

[^ 1]: Um die Approximation von HOSVD zu verbessern, ist es effektiv, das Ergebnis von HOSVD als Anfangswert zu verwenden. Wenn Sie jedoch die Berechnungsreihenfolge als HOSVD verringern möchten, können Sie den Anfangswert zufällig vorbereiten. In jedem Fall können Sie durch mehrmaliges Durchlaufen eine ausreichende Genauigkeit erzielen.

    X1 = np.random.rand(w,w)
    X2 = np.random.rand(h,h)
    U,s,A1 = linalg.svd(X1)
    U,s,A2 = linalg.svd(X2)
    a1 = A1[:r1, :]
    a2 = A2[:r2, :]

Bereiten wir später eine Funktion vor, die einen komprimierten und wiederhergestellten Tensor mit $ a_1 und a_2 $ ergibt.

def restored_tensor(X,a1,a2):
    pa1 = a1.T.dot(a1)
    pa2 = a2.T.dot(a2)
    X2 = np.tensordot(X,pa1,(1,0))
    X3 = np.tensordot(X2,pa2,(0,0))
    return X3.transpose(2,1,0)

Dies ist eine Funktion, die $ X $ mit $ a_i ^ \ dagger $ multipliziert, um einen Kerntensor zu erstellen, und dann $ a_i $ multipliziert, um den wiederhergestellten Tensor zurückzugeben.

Nachdem

1. Zerdrücke das Höhenbein (Nr. 2) mit $ a_2 ^ \ dagger $, dann SVD zusammen mit der Farbe und aktualisiere die Breitenquetschmatrix $ a_1 ^ \ dagger $
2. Zerdrücke das breite Bein (Nr. 1) mit $ a_1 ^ \ dagger $, dann SVD zusammen mit der Farbe und aktualisiere die höhenquetschende Matrix $ a_2 ^ \ dagger $

Sollte wiederholt werden. Der folgende Code implementiert es.

    for i in range(10):
    	X1 = np.tensordot(X,a2.T,(0,0)).transpose(2,1,0).reshape(r2*3,w)
    	U,s,A1 = linalg.svd(X1)
    	a1 = A1[:r1, :]
    	X2 = np.tensordot(X,a1.T,(1,0)).transpose(2,1,0).reshape(r1*3,h)
    	U,s,A2 = linalg.svd(X2)
    	a2 = A2[:r2, :]

Ergebnis

Für den ursprünglichen Tensor $ X $ ist angesichts seines ungefähren Tensors $ X '$ der Rest $ r $

Definiert in. jedoch|X|IstXFrobenius Norm.

Stellen Sie sich eine Transformation vor, die ein geeignetes Bild als Eingabe verwendet und jede der Breiten- und Höhenabmessungen auf 20% komprimiert. Als Eingabebild verwende ich ein Bild des Itanium 2-Geisterpferdes, das ich zufällig zur Hand hatte.

Das folgende Bild ist eine Annäherung an HOSVD.

Der Rest betrug 0,966415890942.

Wenn Sie HOOI 10 Schritte drehen, verringert sich der Rest wie folgt.

1.28857987024
0.97532217632
0.95714093422
0.952636586271
0.950770629606
0.949809071863
0.949257702502
0.948920613334
0.948705104294
0.948562468306

Die erste Zeile ist der Wert ohne Optimierung. Wenn Sie die Schleife von dort zweimal drehen, ist der Rest kleiner als HOSVD. Das Bild nach 10-maligem Drehen ist wie folgt.

Der Rest in diesem Bild ist 0,948562468306, etwas weniger als 2% Verbesserung gegenüber HOSVD, aber der Unterschied ist visuell schwer zu unterscheiden (zumindest für mich).

Zusammenfassung

Da ich dachte, dass das Bild ein Tensor im 3. Stock ist, versuchte ich es mit zwei Methoden, HOSVD und HOOI. Wenn Sie für ein Bild mit einer Größe von $ (w, h) $ die Breite auf $ r_1 $ und die Höhe auf $ r_2 $ reduzieren, hat HOSVD zwei, $ (3h, w) $ und $ (3w, h) $. Sie müssen die Matrix einmal SVD, aber HOOI muss mehrmals schleifen, anstatt eine ziemlich kleine Matrix mit $ (3r_2, w) $ und $ (3r_1, w) $ zu SVDen. .. In dem im Bild getesteten Bereich wurde der Rest jedoch nach mehrmaligem Drehen kleiner als HOSVD. Wenn also die Abmessung des ursprünglichen Tensors groß ist, scheint der Gesamtbetrag der Berechnung in HOOI kleiner zu sein.