[PYTHON] Versuchen Sie, die Daimyo-Prozession in Tucker zu zerlegen

Einführung

Die lineare Algebra hat eine Operation namens Singularitätszerlegung, die zur Approximation der Matrix verwendet wird. Weitere Informationen finden Sie im obigen Abschnitt "Versuchen Sie die Singularwertzerlegung der Daimyo-Matrix".

Eine Matrix ist nun wie ein zweidimensionales Array in einem Programm. Sie können den Wert eines zweidimensionalen Arrays ermitteln, indem Sie zwei Indizes angeben. In ähnlicher Weise kann eine Matrix ein Element angeben, indem zwei Indizes angegeben werden, eine Zeile und eine Spalte. Ein Tensor ist eine Erweiterung einer Matrix zu einem mehrdimensionalen Array. Es ist eine Menge Mühe, Tensoren ernsthaft zu diskutieren, aber in diesem Artikel ist es in Ordnung, es nur als "mehrdimensionales Array" zu betrachten.

Nun besteht wie bei der Matrix die Notwendigkeit, den Tensor zu approximieren. Im Fall einer Matrix war die Singularitätszerlegung die beste Annäherung (im Sinne der Frobenius-Norm), aber es ist nicht gut verstanden, wie man einen allgemeinen Tensor approximiert [^ 1]. Die Zerlegung, die einen Tensor in einen kleinen Tensor (Kerntensor) und einen Satz von Matrizen unterteilt, die jedem Modus entsprechen, wird als Tucker-Zerlegung bezeichnet. Oben dachte ich, dass das monochrome Bild eine Matrix ist, wie es war, und zerlegte es in singuläre Werte, aber in diesem Artikel denke ich, dass das Farbbild ein Tensor dritter Ordnung ist und zerlegt es durch Tucker. Es wurden verschiedene Algorithmen zum Erhalten der Tucker-Zerlegung vorgeschlagen, aber in diesem Artikel werden wir den einfachsten Algorithmus namens SVD höherer Ordnung (HOSVD) vorstellen, der gehorsam die Singularwertzerlegung verwendet.

[^ 1]: Vielleicht gibt es eine allgemeine Theorie, aber ich weiß es nicht.

TODO: Laden Sie Code auf GitHub hoch

Tucker Demontage

Bevor ich die Tucker-Zerlegung erkläre, werde ich die in diesem Artikel verwendeten Begriffe, Matrizen und grafischen Darstellungen der Tensoren zusammenfassen [^ 2]. Der Index einer Matrix oder eines Tensors wird als "Fuß" bezeichnet. Die Prozession hat zwei Beine. Diese Anzahl von Zeilen und Spalten wird als "Dimension" des Fußes bezeichnet. Beachten Sie, dass in mehrdimensionalen Arrays die "Anzahl der Beine" als Dimension bezeichnet wird, in Matrizen und Tensoren jedoch die "Art der Werte, die indiziert werden können" als Dimension bezeichnet wird.

[^ 2]: Ich bin damit nicht sehr vertraut. Bitte beachten Sie, dass das Folgende möglicherweise nicht branchenweit notiert ist.

Eine Matrix oder ein Tensor wird durch ein "Quadrat" mit "Linien" dargestellt. Die "Linie" ist der Fuß. Die Prozession hat zwei Beine und der Tensor im dritten Stock hat drei Beine. Wenn Sie die Abmessung jedes Fußes verdeutlichen möchten, schreiben Sie ihn in die Nähe.

Das Wichtigste bei der grafischen Darstellung ist übrigens der Betrieb von Verbindungslinien. Sie können eine neue Matrix erstellen, indem Sie die Beine mit denselben Abmessungen summieren. Beispielsweise kann eine Matrix das Produkt einer m-mal-n-Matrix und einer n-mal-l-Matrix sein, was zu einer m-mal-l-Matrix führt. Dies mit Quadraten und Linien auszudrücken, sieht so aus.

Selbst mit Tensoren können Sie diese Beine zerdrücken, um einen neuen Tensor zu erstellen, indem Sie die Beine mit derselben Abmessung summieren. In der Diagrammdarstellung verbinden Sie Ihre Beine wie eine Matrix. Der resultierende Tensor ist ein Tensor mit den Abmessungen jedes Beins, wobei die Anzahl der verbleibenden Beine die Anzahl der Stockwerke ist.

Jetzt können Farbbilddaten durch ein dreidimensionales Array mit drei Indizes dargestellt werden: Höhe, Breite und Farbe. Stellen Sie sich dies als einen Tensor mit drei Beinen vor und versuchen Sie, ihn durch Singularitätszerlegung zu approximieren. Im Allgemeinen nähert sich die Tucker-Zerlegung allen Beinen an, aber dieses Mal werden wir, da es nur drei Dimensionen von "farbigen" Beinen gibt, nur "Beine" und "Breite" Beine annähern.

Ursprünglich ist ein Tensor mit drei Beinen der Höhe h, der Breite w und der Farbe c in ein Produkt aus einem Tensor und zwei Matrizen getrennt. Der zentrale Tensor wird als "Kerntensor" bezeichnet und hat in diesem Fall farbige Beine und Beine, die durch die Dimension r mit der linken und rechten Matrize verbunden sind. Die linke und rechte Matrize haben Beine der Höhe h und Beine der Dimension r, Beine der Breite w bzw. Beine der Dimension r, und r ist das Bein, das "Informationen überträgt". Die Tucker-Zerlegung komprimiert Informationen, indem die Dimension von r verringert wird. Lass es uns unten versuchen.

Machen Sie ein Bild von einer Daimyo-Prozession

Lassen Sie uns zunächst ein Bild der Ziel-Daimyo-Prozession erstellen. Das letzte Mal habe ich es in Schwarzweiß gemacht, aber dieses Mal werde ich ein Farbbild machen. Die vier Buchstaben sind gelb (R, G, 0), cyan (0, G, B), magenta (R, 0, B) bzw. weiß (R, G), so dass die aufgrund der Annäherung "blutende" Farbe leicht verstanden werden kann. Färben wir mit, B). Ist es so Die Schriftart wird unterwegs für Google Colab installiert und der Pfad der Schriftart angegeben. Wenn Sie jedoch eine andere Umgebung verwenden, korrigieren Sie diese bitte entsprechend.

from PIL import Image, ImageDraw, ImageFont
import numpy as np
from scipy import linalg
from IPython.display import display
!apt-get -y install fonts-ipafont-gothic
fpath='/usr/share/fonts/opentype/ipafont-gothic/ipagp.ttf'
fontsize = 50
font = ImageFont.truetype(fpath, fontsize)
LX = 200
LY = fontsize
img  = Image.new('RGB', (LX,LY),color="black")
draw = ImageDraw.Draw(img)
draw.text((0,0), "Groß", fill=(255,255,0), font=font)
draw.text((0,0), "Name", fill=(0,255,255), font=font)
draw.text((0,0), "Linie", fill=(255,0,255), font=font)
draw.text((0,0), "Säule", fill="white", font=font)
img

Bei der Ausführung wird ein solches Bild erstellt.

Lassen Sie uns die Daten aus dem Bild erhalten.

data = np.array(img.getdata()).reshape(LY,LX,3)

Sie können sich "Daten" als dreidimensionales Array vorstellen, als Tensor mit drei Beinen mit jeweils drei Dimensionen: Höhe LY, Breite LX und Farbe. Die Aufgabe dieses Artikels ist es, dies zu approximieren. Schauen wir uns vorher die einzelnen RGB-Flugzeuge an.

R = data[:,:,0]
G = data[:,:,1]
B = data[:,:,2]
display(Image.fromarray(np.uint8(R)))
display(Image.fromarray(np.uint8(G)))
display(Image.fromarray(np.uint8(B)))

Wenn Sie nur die Welt von R, nur die Welt von G und nur die Welt von B betrachten, fehlt in jedem ein Buchstabe. Da die "Spalte" weiß ist, wird sie auch nicht abgebrochen.

Singularitätszerlegung

Lassen Sie uns zunächst eine Funktion erstellen, die einzelne Werte zerlegt. Siehe oben für Details. Eine Funktion, die eine Matrix verwendet und zwei Matrizen zurückgibt, die bei einem bestimmten Rang nahe beieinander liegen, sieht folgendermaßen aus:

def perform_svd(X, rank):
  U, s, V = linalg.svd(X)
  Ur = U[:, :rank]
  Sr = np.diag(np.sqrt(s[:rank]))
  Vr = V[:rank, :]
  A = Ur @ Sr
  B = Sr @ Vr
  return A, B

Wenn Sie die Matrix "X" einfügen, werden zwei Matrizen "A" und "B" zurückgegeben. Sie können "A @ B" berechnen, um "X" zu erhalten, was eine Annäherung mit "Rang" ist.

Tensol-Näherung

Lassen Sie uns nun den Tensor approximieren, aber da es eine große Sache ist, versuchen wir verschiedene Approximationsmethoden.

Singularwertzerlegung mit dem Gedanken, dass es sich gewaltsam um eine Matrix handelt

Diesmal hat der Tensor eine Höhe von 50, eine Breite von 200 und eine Farbe von 3. Die Anzahl der Elemente beträgt 30.000. Ignorieren Sie die ursprüngliche Struktur vollständig, stellen Sie sie sich als 200 * 150-Matrix vor, zerlegen Sie sie in singuläre Werte und approximieren Sie sie. Wird es eine solche Funktion sein?

def simple_image(X, rank):
  X = data.reshape((200,150))
  A, B = perform_svd(X, rank)
  Y = (A @ B).reshape(LY,LX,3)
  Y = np.clip(Y, 0, 255)
  Y = np.uint8(Y)
  print((A.size+B.size)/X.size)
  return Image.fromarray(Y)

Das Ausführungsergebnis sieht so aus.

display(simple_image(data, 50))
display(simple_image(data, 21))
display(simple_image(data, 8))

Die Datenkomprimierungsrate wird ebenfalls angezeigt. Von oben sind 58,3%, 24,5% und 9,3%. Dies ist die Summe der Anzahl der Elemente von A und B geteilt durch die Anzahl der Elemente von X, wenn die 200 * 150-Matrix X in zwei Matrizen A und B geteilt wird. Trotz der sehr groben Methode bleibt die ursprüngliche Struktur unverändert.

Singularitätszerlegung der RGB-Ebene

Bei der vorherigen Methode wurden die drei Strukturen Höhe, Breite und Farbe ursprünglich vollständig ignoriert. Betrachten wir nun die ursprüngliche Struktur ein wenig. Eine einfache Möglichkeit, den Tensor zu approximieren, der ein Farbbild ausdrückt, besteht darin, sich die Ebenen R, G und B als "Matrix" vorzustellen, sie in singuläre Werte zu zerlegen und sie dann zu kombinieren. Machen wir das.

def rgb_svd(X, rank):
  R = X[:,:,0]
  G = X[:,:,1]
  B = X[:,:,2]
  Rh, Rw = perform_svd(R, rank)
  Gh, Gw = perform_svd(G, rank)
  Bh, Bw = perform_svd(B, rank)
  return Rh, Rw, Gh, Gw, Bh, Bw

Der Tensor "X" ist in eine Matrix unterteilt, die die RGB-Ebene darstellt, R ist in Rh und Rw getrennt, G ist in Gh und Gw getrennt und B ist in Bh bzw. Bw getrennt. Wenn Sie "Rh @ Rw" ausführen, wird die R-Ebene wiederhergestellt. Wenn Sie also die G- und B-Ebene auf dieselbe Weise wiederherstellen, wird das Originalbild wiederhergestellt. Die Bildwiederherstellung sieht folgendermaßen aus.

def rgb_image(X, rank):
  Rh, Rw, Gh, Gw, Bh, Bw = rgb_svd(X, rank)
  R = Rh @ Rw
  G = Gh @ Gw
  B = Bh @ Bw
  Y = np.asarray([R,G,B]).transpose(1,2,0)
  Y = np.clip(Y, 0, 255)
  Y = np.uint8(Y)
  print((Rh.size+Rw.size)*3/X.size)
  return Image.fromarray(Y)

Lass es uns laufen.

display(rgb_image(data, 50))
display(rgb_image(data, 10))
display(rgb_image(data, 4))

Die Kompressionsverhältnisse betragen 125%, 25% und 10% von oben. Die Singularitätszerlegung kann mehr Elemente als die Originaldaten enthalten, wenn der verbleibende Rangwert groß ist. Bei den anderen beiden habe ich versucht, das Komprimierungsverhältnis an die zuvor erwähnte grobe Methode anzupassen. Ich dachte, dass die Annäherung besser wäre, weil die Struktur berücksichtigt wurde, aber es war unerwartet schlecht.

Tucker Demontage

Lassen Sie uns nun das Hauptthema von Tucker aufschlüsseln. Siehe auch Niedrigrangige Annäherung von Bildern durch Tucker-Zerlegung für das Prinzip der Tucker-Zerlegung. Diese Funktion unterteilt den dreibeinigen Tensor "X" in den Kerntensor "C" und die linken und rechten Matrizen "U" und "V".

def tucker_decomposition(X, rank):
  X = X.transpose(0,2,1)
  XR = X.reshape(LY*3, LX)
  _, _, V = linalg.svd(XR)
  V = V[:rank,:]
  Vt = V.transpose(1,0)
  XL = X.reshape(LY, LX*3)
  U, _, _ = linalg.svd(XL)
  U = U[:,:rank]
  Ut = U.transpose(1,0)
  # Make a core tensor
  UX = np.tensordot(Ut, X, (1,0))
  C = np.tensordot(UX, Vt, (2, 0))
  return U, C, V

Eine Funktion, die ein Bild aus einer zerlegten Matrix und einem Tensor wiederherstellt, sieht folgendermaßen aus.

def tucker_image(X, rank):
  U, C, V = tucker_decomposition(X, rank)
  UC = np.tensordot(U,C,(1,0))
  Y = np.tensordot(UC, V, (2,0))
  Y = Y.transpose((0,2,1))
  Y = np.clip(Y, 0, 255)
  Y = np.uint8(Y)
  print((U.size+C.size+V.size)/X.size)
  return Image.fromarray(Y)

Lass es uns laufen.

display(tucker_image(data, 50))
display(tucker_image(data, 23))
display(tucker_image(data, 10))

Die Kompressionsverhältnisse betragen 66,7%, 24,5% und 9,3% von oben. Es ist eindeutig besser als die Zerlegung einzelner Werte für jedes RGB, aber ist es ein subtiler Vergleich mit der groben Methode?

Zusammenfassung

Ich dachte, das Farbbild "Daimyo Matrix" sei ein dreibeiniger Tensor und versuchte, die Informationen durch Singularwertzerlegung zu komprimieren. Es war überraschend, dass es besser wäre, die gesamte RGB-Ebene gewaltsam in Singularwerte zu zerlegen, als sie jeweils in Singularwerte zu zerlegen. Im Gegensatz zu Matrizen ist die Tensornäherung nicht sehr selbsterklärend, was zu tun ist. Ich hoffe, Sie probieren diesen Code aus und denken: "Ich verstehe, die niedrigrangige Annäherung von Tensol ist tief."

Ergänzungsmaterial

TODO: Schreiben Sie in diesem Artikel eine Beschreibung des Tucker-Zerlegungsalgorithmus.