[PYTHON] Approximation de bas rang de l'image par décomposition de Tucker

introduction

Faites-vous une décomposition de valeurs singulières? ＞ Salutations

Sur mon lieu de travail actuel, tout le monde annonce lors d'une réunion hebdomadaire, mais c'est presque comme "J'ai fait du SVD comme ça", alors [j'ai aussi essayé SVD](http://qiita.com/kaityo256/items/ 48de63526b469235d16a), mais c'est une continuation.

Le code source est https://github.com/kaityo256/image_svd C'est dedans.

Tout d'abord, je ne suis pas doué pour les tenseurs ou l'algèbre linéaire en général [^ denki]. Par conséquent, nous ne pouvons garantir l'exactitude des informations suivantes. Je vais être un mémorandum parce que je suis confus quant à "Quoi? Quelle jambe écrasez-vous?"

De plus, la [matrice d'accompagnement] de la matrice $ A $ (https://ja.wikipedia.org/wiki/%E9%9A%8F%E4%BC%B4%E8%A1%8C%E5%88%97) ( Nous allons transposer et prendre le conjugué complexe de chaque composant) comme $ A ^ \ dagger $.

[^ denki]: C'est pourquoi j'ai laissé tomber l'unité électromagnétique.

Décomposition de singularité et approximation de la matrice

Décomposition de singularité

Considérons d'abord le produit des matrices. Le produit d'une matrice m-par-n et d'une matrice n-par-k donne une matrice m-par-k.

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

La formule ci-dessus utilise la convention d'Einstein. A ce moment, le pied au milieu est écrasé. Cela ressemble à ceci lorsqu'il est illustré.

Maintenant, pensez à compresser les informations dans une certaine matrice. Cela équivaut à réduire les dimensions de la matrice. Tout d'abord, considérons, par exemple, approximer la $ m $ ligne $ n $ matrice $ X $ comme $ m $ ligne $ n '$ colonne $ (n' <n) $. Considérez qu'il existe une matrice de colonnes $ n $ row $ n '$ $ P $ qui agit comme ce "compresseur".

Multiplier $ X $ par $ P $ crée $ \ chi $, ce qui réduit le nombre de colonnes de $ n $ à $ n '$. Inutile de dire que cela ressemble à ceci.

La hauteur reste la même, mais la largeur est devenue plus étroite.

Multipliez $ P ^ \ dagger $ pour revenir du $ \ chi $ compressé au $ X $ d'origine.

Ensuite, la matrice compressée $ \ chi $ devient une matrice de $ m $ row $ n $ column, mais elle ne revient pas à $ X $ faute d'informations, et une matrice $ qui se rapproche de $ X . Ce sera X '.

En bref, $ P $ est une compression d'informations, $ P ^ \ dagger $ est une matrice de restauration d'informations, et l'image est comme l'outil de Doraemon "Gulliver Tunnel". Cependant, dans ce cas, il est irréversible ...

Maintenant, une telle matrice de compression / restauration d'informations $ P $ peut être créée par Singular Value Decomposition (SVD).

SVD est une matrice de colonnes $ m $ row $ n $ $ X $,

X = U \Sigma V^{\dagger}

Il est démonté dans la forme. Cependant, $ U $ est une matrice unitaire de $ m $ ligne $ m $ colonne, $ V $ est $ n $ ligne $ n $ colonne et $ \ Sigma $ est une colonne $ m $ ligne $ n $ avec seulement des composantes diagonales. C'est une procession. Cette composante diagonale est appelée une valeur singulière.

Les $ U $ et $ V $ ainsi créés sont des compresseurs d'informations. Si vous faites SVD avec Python etc., ils seront arrangés dans l'ordre de la taille de la valeur singulière. Par exemple, la matrice $ v ^ \ dagger $ créée en prenant $ n '$ lignes du haut de $ V ^ \ dagger $ peut être utilisée comme un restaurateur, et sa matrice d'accompagnement $ v $ peut être utilisée comme un compresseur.

De même, la colonne $ m '$ à partir de la gauche de $ U $ est le compresseur et sa matrice associée est le restaurateur.

Démontage Tucker

Dans l'exemple ci-dessus, nous avons compressé la matrice, mais plus généralement, vous voudrez peut-être compresser un tenseur de rang élevé (jambe complète). En machine learning, il semble que les données soient considérées comme un tenseur, compressées en prétraitement, puis soumises à un apprentissage. La décomposition de Tucker est utilisée pour compresser ce tenseur.

Par exemple, considérons un tenseur $ X $ à trois jambes. Supposons que les dimensions de chaque pied soient $ m, n, k $. Pensez à l'approximer avec un tenseur $ χ $ avec des jambes de plus petites dimensions $ m ', n', k '$.

A ce moment, le pied de dimension $ m $ doit être écrasé en $ m '$. Faites cela avec SVD comme vous le feriez avec une matrice.

Tout d'abord, rassemblez les jambes autres que celle à écraser.

Nous venons de considérer le tenseur, qui était à l'origine du troisième ordre de $ m, n, k $, comme le tenseur du deuxième ordre de $ m, n * k $, c'est-à-dire une matrice. Puis comme il s'agit d'une matrice, SVD peut être utilisé.

X = U \Sigma V^\dagger

Ici, $ V $ est une matrice unitaire, donc $ V V ^ \ dagger = I $, c'est-à-dire un opérateur d'égalité.

Cependant, si la matrice qui prend la colonne $ m '$ supérieure de $ V ^ \ dagger $ est $ v ^ \ dagger $, $ v $ sera utilisé pour le compresseur de $ m $ à $ m' $, et $ v ^ \ dagger $ est un restaurateur de $ m '$ à $ m $.

Si vous faites ce compresseur pour chaque jambe et que vous l'exécutez ensuite, vous obtiendrez un tenseur $ \ chi $ qui est une réduction du tenseur original $ X $.

Le tenseur réduit ainsi obtenu est appelé tenseur de noyau. Pour restaurer le tenseur d'origine du tenseur du noyau, vous pouvez mettre un restaurateur sur chaque jambe.

Il semble qu'une telle décomposition s'appelle SVD d'ordre supérieur, HOSVD.

Application à la compression d'image

Maintenant, compressons l'image en utilisant SVD.

Les données d'image bidimensionnelles peuvent être considérées comme un tenseur du troisième ordre car les valeurs sont déterminées en spécifiant la coordonnée x, la coordonnée y et la couleur. Si la largeur est $ w $ et la hauteur est $ h $, les dimensions (épaisseur) de chaque pied sont $ w, h, c $. Cependant, c est la couleur et la dimension est 3. Si vous lisez les données avec obéissance, l'ordre est la hauteur, la largeur et la couleur, nous allons donc l'exprimer comme X [y, x, c].

Lors de la compression avec SVD, le moyen le plus simple est d'appliquer SVD à chaque plan RVB comme vous l'avez fait la dernière fois.

    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)

Si vous ouvrez un fichier avec l'image de PIL et le rentrez dans numpy.asarray, vous obtiendrez un tenseur du troisième ordreX (hauteur, largeur, couleur). Par exemple, si vous utilisez X [:,:, 0], vous pouvez obtenir une image rouge, donc vous pouvez l'approcher par SVD. De même, après avoir créé une image approximative de vert et de bleu, vous pouvez restaurer l'image d'origine en "transposant" et en "remodelant" de manière appropriée. [^ 1]

[^ 1]: Pour expliquer correctement, perform_svd est une fonction qui retourne sous forme de tableau unidimensionnel, donc r est un vecteur unidimensionnel de taille w * h. Si vous attachez 3 d'entre eux avec [r, g, b] et les mettez dans numpy.asarray, cela devient un tenseur du second ordre de (c, h * w), alors remplacez-le par tranpose (h * w, Réglez-le sur c) et réglez-le sur (h, w, c) avec repshape pour terminer.

Ensuite, utilisons HOSVD. Il en est de même jusqu'au point où l'image est changée en tenseur «X» de (h, w, c). Tout d'abord, afin d'obtenir une matrice pour écraser la largeur et la hauteur, créons une matrice «X1» qui résume la hauteur et la couleur des jambes et une matrice «X2» qui résume la largeur et la couleur des jambes.

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

L'ordre des jambes est changé de (h, w, c) à (hc, w) et (wc, h), respectivement. SVD chacun de ceux-ci.

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

Les machines de restauration ʻa1 et ʻa2 peuvent être créées en prenant la colonne $ r $ supérieure des ʻA1 et ʻA2 obtenus.

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

Cette fois, ce sont des colonnes d'exécution, donc si vous les déplacez, vous pouvez obtenir le poignard. Après cela, ʻa1.T` est appliqué pour l'écraser, puis $ a1 $ est appliqué pour le restaurer, mais comme c'est gênant, une matrice (projecteur) qui effectue une "compression / restauration" à la fois est créée en premier.

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

Vous pouvez obtenir un tenseur approximatif en «tensordot» le projecteur résultant avec les jambes appropriées.

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

Ici, seules les jambes de coordonnée x et les jambes de coordonnée y sont écrasées et les jambes colorées ne sont pas écrasées. Le code ci-dessus

https://github.com/kaityo256/image_svd

Il est implémenté dans color_tucker.

Comparaison

Comparons SVD en pensant que chaque plan RVB est une matrice et appliquant SVD deux fois en combinant 3 jambes en 2 (HOSVD). Tout d'abord, découvrez la quantité d'informations compressées dans chacun d'eux. Considérons une image couleur de $ L_1 \ fois L_2 $. Faites une approximation avec des rangs jusqu'à $ r $.

Lors de la SVD de chacun des plans RVB, les images de chaque couleur sont dans une matrice de $ L_1 \ fois L_2 $, qui est compressée en $ L_1 r $, $ L_2 r $ et r valeurs singulières. Puisqu'il a 3 couleurs, l'information de $ 3L_1 L_2 $ est compressée en $ 3r (L_1 + L_2 + r) $. $ L_1, L_2 \ gg r $ est $ 3r (L_1 + L_2) $.

Pour HOSVD, le tenseur $ L_1 \ times L_2 \ times 3 $ est compressé en un tenseur $ r \ times r \ times 3 $ core et une matrice $ L_1 \ times r $, $ L_2 \ times r $. Par conséquent, la quantité de données après compression est $ r (L_1 + L_2 + 3r) \ sim r (L_1 + L_2) $. Ce sera. Par conséquent, pour compresser à la même quantité d'informations que lorsqu'elle est approximée par des rangs jusqu'à $ r $ sur le plan RVB, il suffit de prendre jusqu'à $ 3r $ sur HOSVD.

Voici une comparaison avec des images appropriées.

L'image originale

Les 10 premiers rangs de chaque plan RVB

HOSVD, les 30 meilleurs projecteurs de coordonnées x et de coordonnées y frottés.

Il devrait laisser la même quantité d'informations, mais HOSVD semble être meilleur.

Résumé

Je pensais que les données d'image étaient un tenseur du 3e étage avec 3 pattes de hauteur, de largeur et de couleur, alors je l'ai décomposée avec Tucker et j'ai fait une image approximative. En comparant avec la même quantité d'informations, il semble que HOSVD, qui SVD les jambes ensemble, est meilleur que SVDing chaque plan RVB. De plus, cette fois, je n'ai fait SVD qu'une fois pour chaque pied, mais il semble y avoir une itération d'alignement d'ordre supérieur (HOOI) qui améliore la précision d'approximation en répétant cela.