[PYTHON] Niedrigrangige Approximation des Bildes durch Tucker-Zerlegung

Einführung

Führen Sie eine Singularwertzerlegung durch? ＞ Begrüßung

An meinem derzeitigen Arbeitsplatz kündigt jeder bei einem wöchentlichen Meeting an, aber es ist fast so, als hätte ich SVD so gemacht, also [habe ich auch SVD ausprobiert](http://qiita.com/kaityo256/items/ 48de63526b469235d16a), aber es ist eine Fortsetzung.

Der Quellcode ist https://github.com/kaityo256/image_svd Es ist in.

Erstens bin ich nicht gut in Tensoren oder linearer Algebra im Allgemeinen [^ denki]. Daher können wir die Richtigkeit der folgenden Informationen nicht garantieren. Ich werde ein Memorandum sein, weil ich verwirrt bin über "Was? Welches Bein zerquetschst du?"

Auch die [zugehörige Matrix] der Matrix $ A $ (https://ja.wikipedia.org/wiki/%E9%9A%8F%E4%BC%B4%E8%A1%8C%E5%88%97) ( Wir werden das komplexe Konjugat jeder Komponente als $ A ^ \ Dolch $ transponieren und nehmen.

[^ denki]: Deshalb habe ich die elektromagnetische Einheit fallen lassen.

Singularitätszerlegung und Matrixnäherung

Singularitätszerlegung

Betrachten Sie zunächst das Produkt der Matrizen. Das Produkt einer m-mal-n-Matrix und einer n-mal-k-Matrix ergibt eine m-mal-k-Matrix.

\begin{align}
C &= A B \\
C_{ik} &= A_{ij} B_{jk}
\end{align}

Die obige Formel verwendet die Einstein-Konvention. Zu diesem Zeitpunkt ist der Fuß in der Mitte gequetscht. In der Abbildung sieht es so aus.

Ziehen Sie nun in Betracht, die Informationen in einer bestimmten Matrix zu komprimieren. Dies entspricht einer Reduzierung der Abmessungen der Matrix. Betrachten Sie zunächst beispielsweise die Annäherung der $ m $ Zeile $ n $ Matrix $ X $ an $ m $ Zeile $ n '$ Spalte $ (n' <n) $. Bedenken Sie, dass es eine $ n $ Zeile $ n '$ Spaltenmatrix $ P $ gibt, die als dieser "Kompressor" fungiert.

Durch Multiplizieren von $ X $ mit $ P $ wird $ \ chi $ erstellt, wodurch die Anzahl der Spalten von $ n $ auf $ n '$ reduziert wird. Unnötig zu sagen, dass es so aussieht.

Die Höhe bleibt gleich, aber die Breite ist schmaler geworden.

Multiplizieren Sie $ P ^ \ dagger $, um vom komprimierten $ \ chi $ zum ursprünglichen $ X $ zurückzukehren.

Dann wird die komprimierte Matrix $ \ chi $ zu einer Matrix aus $ m $ Zeile $ n $ Spalte, kehrt jedoch aufgrund fehlender Informationen nicht zu $ X $ zurück und zu einer Matrix $, die sich $ X $ annähert. Es wird X '$ sein.

Kurz gesagt, $ P $ ist Informationskomprimierung, $ P ^ \ dagger $ ist eine Informationswiederherstellungsmatrix und das Bild ähnelt Doraemons Werkzeug "Gulliver Tunnel". In diesem Fall ist es jedoch irreversibel ...

Nun kann eine solche Informationskomprimierungs- / Wiederherstellungsmatrix $ P $ durch Singular Value Decomposition (SVD) erstellt werden.

SVD ist eine $ m $ Zeile $ n $ Spaltenmatrix $ X $,

X = U \Sigma V^{\dagger}

Es wird in die Form zerlegt. $ U $ ist jedoch eine einheitliche Matrix aus $ m $ Zeile $ m $ Spalte, $ V $ ist eine $ n $ Zeile $ n $ Spalte und $ \ Sigma $ ist eine $ m $ Zeile $ n $ Spalte mit nur diagonalen Komponenten. Es ist eine Prozession. Diese diagonale Komponente wird als Singularwert bezeichnet.

Die auf diese Weise erstellten $ U $ und $ V $ sind Informationskompressoren. Wenn Sie SVD mit Python usw. ausführen, werden diese in der Reihenfolge der Größe des Singularwerts angeordnet. Beispielsweise kann die Matrix $ v ^ \ dagger $, die durch Nehmen von $ n '$ Zeilen vom oberen Rand von $ V ^ \ dagger $ erstellt wurde, als Restaurator verwendet werden, und die zugehörige Matrix $ v $ kann als Kompressor verwendet werden.

In ähnlicher Weise ist die Spalte $ m '$ links von $ U $ der Kompressor und die zugehörige Matrix der Restaurator.

Tucker Demontage

Im obigen Beispiel haben wir die Matrix komprimiert, aber im Allgemeinen möchten Sie möglicherweise einen Tensor mit hohem Rang (volles Bein) komprimieren. Beim maschinellen Lernen werden Daten anscheinend als Tensor betrachtet, als Vorverarbeitung komprimiert und anschließend geschult. Die Tucker-Zersetzung wird verwendet, um diesen Tensor zu komprimieren.

Stellen Sie sich zum Beispiel einen Tensor $ X $ mit drei Beinen vor. Nehmen wir an, dass die Abmessungen jedes Fußes $ m, n, k $ sind. Erwägen Sie, dies mit einem Tensor $ χ $ mit Beinen der kleineren Dimensionen $ m ', n', k '$ zu approximieren.

Zu diesem Zeitpunkt muss der Fuß mit der Dimension $ m $ auf $ m '$ gequetscht werden. Tun Sie dies mit SVD wie mit einer Matrix.

Setzen Sie zuerst die anderen Beine als die zu zerquetschenden zusammen.

Wir haben gerade den Tensor, der ursprünglich die dritte Ordnung von $ m, n, k $ war, als den Tensor zweiter Ordnung von $ m, n * k $ angesehen, dh eine Matrix. Da dies eine Matrix ist, kann SVD verwendet werden.

X = U \Sigma V^\dagger

Hier ist $ V $ eine einheitliche Matrix, also $ V V ^ \ dagger = I $, dh ein Gleichheitsoperator.

Wenn jedoch die Matrix, die die obere Spalte $ m '$ von $ V ^ \ dagger $ enthält, $ v ^ \ dagger $ ist, wird $ v $ von $ m $ in $ m' $ und $ v konvertiert ^ \ dagger $ ist ein Restaurator von $ m '$ bis $ m $.

Wenn Sie diesen Kompressor für jedes Bein herstellen und dann ausführen, erhalten Sie einen Tensor $ \ chi $, der eine Reduzierung des ursprünglichen Tensors $ X $ darstellt.

Der auf diese Weise erhaltene reduzierte Tensor wird als Kerntensor bezeichnet. Um den ursprünglichen Tensor aus dem Kerntensor wiederherzustellen, können Sie jedem Bein einen Restaurator hinzufügen.

Es scheint, dass eine solche Zerlegung als SVD höherer Ordnung, HOSVD, bezeichnet wird.

Anwendung zur Bildkomprimierung

Jetzt komprimieren wir das Bild mit SVD.

Zweidimensionale Bilddaten können als Tensor dritter Ordnung angesehen werden, da die Werte durch Angabe der x-Koordinate, der y-Koordinate und der Farbe bestimmt werden. Wenn die Breite $ w $ und die Höhe $ h $ ist, sind die Abmessungen (Dicke) jedes Fußes $ w, h, c $. C ist jedoch Farbe und die Abmessung ist 3. Wenn Sie die Daten gehorsam lesen, lautet die Reihenfolge Höhe, Breite und Farbe. Wir werden dies also als "X [y, x, c]" ausdrücken.

Wenn Sie dies mit SVD komprimieren, können Sie SVD am einfachsten wie beim letzten Mal auf jede RGB-Ebene anwenden (http://qiita.com/kaityo256/items/48de63526b469235d16a).

    img = Image.open(filename)
    w = img.width
    h = img.height
    X = np.asarray(img)
    r = perform_svd(X[:,:,0],rank).reshape(w*h)
    g = perform_svd(X[:,:,1],rank).reshape(w*h)
    b = perform_svd(X[:,:,2],rank).reshape(w*h)
    B = np.asarray([r,g,b]).transpose(1,0).reshape(h,w,3)

Wenn Sie eine Datei mit PILs Bild öffnen und in "numpy.asarray" stecken, erhalten Sie einen Tensor dritter Ordnung "X" (Höhe, Breite, Farbe). Wenn Sie beispielsweise "X [:,:, 0]" verwenden, erhalten Sie ein rotes Bild, sodass Sie es durch SVD approximieren können. In ähnlicher Weise können Sie nach dem Erstellen eines ungefähren Bildes von Grün und Blau das Originalbild wiederherstellen, indem Sie es entsprechend "transponieren" und "umformen". [^ 1]

[^ 1]: Um es richtig zu erklären, ist perform_svd eine Funktion, die als eindimensionales Array zurückgegeben wird, also ist r ein eindimensionaler Vektor der Größe w * h. Wenn Sie 3 davon mit "[r, g, b]" anhängen und in "numpy.asarray" einfügen, wird dies zu einem Tensor zweiter Ordnung von (c, h * w). Ersetzen Sie ihn also durch "tranpose" (h * w,). Setzen Sie es auf c) und setzen Sie es auf "h, w, c) mit" repshape ", um den Vorgang abzuschließen.

Als nächstes verwenden wir HOSVD. Dies ist bis zu dem Punkt der Fall, an dem das Bild in den Tensor "X" von (h, w, c) geändert wird. Um eine Matrix zum Quetschen von Breite und Höhe zu erhalten, erstellen wir zunächst eine Matrix "X1", die die Höhe und Farbe der Beine zusammenfasst, und eine Matrix "X2", die die Breite und die Farbe der Beine zusammenfasst.

    X1 =  X.transpose(0,2,1).reshape(h*3,w)
    X2 = X.transpose(1,2,0).reshape(w*3,h)

Die Reihenfolge der Beine wird von (h, w, c) zu (hc, w) bzw. (wc, h) geändert. SVD jeder von diesen.

    U,s,A1 = linalg.svd(X1)
    U,s,A2 = linalg.svd(X2)

Wiederherstellungsmaschinen "a1" und "a2" können erstellt werden, indem die obere Spalte $ r $ der erhaltenen "A1" und "A2" verwendet wird.

    a1 = A1[:r2, :]
    a2 = A2[:r2, :]

Diesmal sind dies Ausführungsspalten. Wenn Sie sie also verschieben, können Sie den Dolch erhalten. Danach wird es durch Anwenden von "a1.T" zerkleinert und dann durch Anwenden von $ a1 $ wiederhergestellt. Da dies jedoch problematisch ist, werde ich eine Matrix (Projektor) erstellen, die sofort "Komprimierung / Wiederherstellung" durchführt.

    pa1 = a1.T.dot(a1)
    pa2 = a2.T.dot(a2)

Sie können einen ungefähren Tensor erhalten, indem Sie den resultierenden Projektor mit den entsprechenden Beinen "tensordot".

    X2 = np.tensordot(X,pa1,(1,0))
    X3 = np.tensordot(X2,pa2,(0,0))
    X4 = X3.transpose(2,1,0)

Hier werden nur die x-Koordinatenbeine und die y-Koordinatenbeine gequetscht, und die farbigen Beine werden nicht gequetscht. Der obige Code

https://github.com/kaityo256/image_svd

Es ist in [color_tucker] implementiert (https://github.com/kaityo256/image_svd/blob/master/image_svd.py#L43).

Vergleich

Vergleichen wir die SVD, indem wir denken, dass jede RGB-Ebene eine Matrix ist, und die SVD zweimal anwenden, indem wir 3 Beine zu 2 (HOSVD) kombinieren. Stellen Sie zunächst fest, wie viele Informationen in den einzelnen Informationen komprimiert wurden. Betrachten Sie ein Farbbild von $ L_1 \ mal L_2 $. Näherungsweise mit Rängen bis zu $ r $.

Beim SVDing jeder der RGB-Ebenen ist das Bild jeder Farbe eine Matrix aus $ L_1 \ mal L_2 $, die in $ L_1 r $, $ L_2 r $ und r Singularwerte komprimiert wird. Da es 3 Farben hat, wird die Information von $ 3L_1 L_2 $ auf $ 3r (L_1 + L_2 + r) $ komprimiert. $ L_1, L_2 \ gg r $ ist $ 3r (L_1 + L_2) $.

Für HOSVD wird der Tensor $ L_1 \ mal L_2 \ mal 3 $ zu einem Kerntensor $ r \ mal r \ mal 3 $ und einer Matrix $ L_1 \ mal r $, $ L_2 \ mal r $ komprimiert. Daher beträgt die Datenmenge nach der Komprimierung $ r (L_1 + L_2 + 3r) \ sim r (L_1 + L_2) $. Es wird sein. Um auf die gleiche Menge an Informationen zu komprimieren, wie sie in der RGB-Ebene durch Ränge von bis zu $ r $ angenähert werden, ist es daher ausreichend, auf HOSVD bis zu $ 3r $ aufzunehmen.

Unten finden Sie einen Vergleich mit entsprechenden Bildern.

Das Originalbild

Die Top 10 jeder RGB-Ebene

HOSVD, die Top 30 rieben x-Koordinaten- und y-Koordinaten-Projektoren.

Es sollte die gleiche Menge an Informationen hinterlassen, aber HOSVD scheint besser zu sein.

Zusammenfassung

Ich dachte, dass die Bilddaten ein Tensor im 3. Stock mit 3 Beinen in Höhe, Breite und Farbe waren, also zerlegte ich sie mit Tucker und machte ein ungefähres Bild. Beim Vergleich mit der gleichen Menge an Informationen scheint es, dass HOSVD, bei dem die Beine zusammen SVDs sind, besser ist als die SVD für jede RGB-Ebene. Auch dieses Mal habe ich SVD nur einmal für jeden Fuß durchgeführt, aber es scheint eine Ausrichtungsiteration höherer Ordnung (HOOI) zu geben, die die Approximationsgenauigkeit verbessert, indem sie dies wiederholt.