[PYTHON] Wörterbuch-Lernalgorithmus

Sparse Modeling Der Wörterbuch-Lernalgorithmus von Kapitel 12 wurde in jupyter notebook implementiert. Link zum Jupyter-Notizbuch

Ergebnis

Ungefähr 25.000 8x8-Patches wurden aus Barbara extrahiert und das Wörterbuchlernen wurde durchgeführt.

Zweidimensionales trennbares DCT-Wörterbuch als Anfangswert Wörterbuch, das aus Patches mit der K-SVD-Methode gelernt wurde

Das Lernen des Wörterbuchs reduzierte den spärlichen Ausdrucksfehler.

K-SVD-Algorithmus

• Signalfall $ Y: n \ mal M $ (n ist die Signaldimension, M ist die Anzahl der Fälle)
• Spärliche Darstellung $ X: m \ mal M $ (m ist die Dimension des spärlichen Darstellungsvektors)
• Wörterbuch $ A: n \ mal m $

Stellen Sie $ y_i $ nur spärlich mit $ x_i $ dar, wobei nur $ k_0 $ Elemente ungleich Null sind.

Aufgabe:

\min_{A,\{x_i\}^{M}_{1}} \Sigma_{i=1}^{M} ||y_i-Ax_i|| \text{ subject to } ||x_{i}||_0 \leq k_{0}, 1 \leq i \leq M

Initialisieren:

Als $ k = 0 $

• Erstes Wörterbuch: Zunächst wurde eine 8 × 11 eindimensionale DCT-Matrix $ A_ {1D} $ erstellt. Das $ k $ -te Atom $ (k = 1,2, \ dots, 11) $ ist

a^{1D}_{k}=\cos((i-1)(k-1)\pi/11),(i=1,2,\dots,8)

Ist. Mit Ausnahme des ersten Atoms wird der Durchschnitt und das Kronecker-Produkt abgezogen

A_{2D} = A_{1D} \otimes A_{1D}

Ein erstes Wörterbuch wurde mit erstellt.

• Normalisierung: Normalisieren Sie die Spalte $ A $

Hauptschleife:

Setzen Sie $ k \ leftarrow k + 1 $ und führen Sie die folgenden Schritte aus.

• Sparse Coding: Näherungsweise Lösung mit einem Tracking-Algorithmus.

\hat{x_{i}} = \arg \min_{x} ||y_{i} - Ax||_{2}^{2} \text{ subject to } ||x||_{0} \leq k_{0}

Dann erhalten wir den spärlichen Darstellungsvektor $ \ hat {x} _ {i} $ für $ 1 \ leq i \ leq M $. Verwenden Sie diese, um die Matrix $ X $ zu erstellen.

• K-SVD-Wörterbuch aktualisieren: Führen Sie die folgenden Schritte aus, um die Spalten des Wörterbuchs zu aktualisieren und $ A $ zu erhalten. Wiederholen Sie dies für $ j_0 = 1,2, \ dots, m $.

1. Definieren Sie eine Fallmenge, die das Atom $ a_ {j_ {0}} $ verwendet. $ \ Omega_ {j_ {0}} = \\ {i | 1 \ leq i \ leq M, X [j_ {0}, i] \ neq 0 \\} $

2. Berechnen Sie die Restmatrix. $ E_ {j_ {0}} = Y- \ Sigma_ {j \ neq j_ {0}} a_ {j} x_ {j} ^ {T} $

3. Extrahieren Sie nur die Spalte, die $ \ Omega_ {j_ {0}} $ entspricht, aus $ E_ {j_ {0}} $ und setzen Sie sie als $ E_ {j_ {0}} ^ {R} $.

4. Wenden Sie $ SVD $ an und setzen Sie $ E_ {j_ {0}} ^ {R} = U \ Delta V $. Und das Atom $ a_ {j_ {0}} = u_ {1} $ des Wörterbuchs, der Ausdrucksvektor ist $ x_ {j_ {0}} ^ {R} = \ Delta [1, 1] v_ {1} ^ {T. } Als $ aktualisieren.

*Stoppbedingung: Wenn||Y - AX||^{2}_{F}Wenn die Änderung klein genug ist, endet sie, andernfalls wird sie wiederholt.

Ausgabe:

Holen Sie sich das Ergebnis $ A $.

Referenz

• M. Elad, übersetzt von Toru Tamaki, Sparse Modeling, Kapitel 12
• https://github.com/greyhill/pypbip/blob/master/ksvd.py