Kompresja SVD | mysimulator.uk

Każda macierz jest sumą prostych elementów

Obraz w skali szarości to tylko macierz: jedna liczba dla każdego piksela, ułożona w wierszach i kolumnach. Rozkład singularny (SVD) mówi, że dowolna taka macierz A, o dowolnej postaci, może być dokładnie zapisana jako sumę prostych elementów rank-1 — każdy z nich jest iloczynem wektora kOLUMNOWEGO i wektora wierszowego, skaliowanych przez pojedynczą liczbę.

A = U Σ Vᵀ = Σᵢ σᵢ · uᵢ vᵢᵀ uᵢ, vᵢ — i-ty kOLUMNOWY wektor macierzy U i V (ortonormalne „kierunkowe” wektory) σᵢ — i-ta wartość singularna, σ₁ ≥ σ₂ ≥ σ₃ ≥ ... ≥ 0 uᵢ vᵢᵀ — macierz rank-1: taka sama postać jak A, ale zbudowana tylko z dwóch wektorów Kluczowe jest kolejność: wartości singularne σᵢ są zawsze uporządkowane od największej do najmniejszej, a każda z nich mówi dokładnie, ile dany jednokładnik rank-1 wpływa na odtworzenie A. Pierwszy klad, ważony przez σ₁, jest jednym z najważniejszych wzorów w całym obrazie; drugi klad go ulepsza; a dopiero gdy dotrzemy do najmniejszych wartości singularnych, dodajemy drobne tekstury, ostre krawędzie i — w rzeczywistym fotografii — szum senzorowy.

A = U Σ Vᵀ  =  Σᵢ σᵢ · uᵢ vᵢᵀ

uᵢ, vᵢ   — the i-th columns of U and V (orthonormal "direction" vectors)
σᵢ       — the i-th singular value, σ1 ≥ σ2 ≥ σ3 ≥ ... ≥ 0
uᵢ vᵢᵀ   — a rank-1 matrix: same shape as A, but built from just two vectors

demo na żywo · powiązana symulacja● LIVE

Najlepsza możliwa aproksymacja stopnia k

Ograniczenie sumy po pierwszych k wyrazach daje macierz o stopniu k, a twierdzenie Eckart-Young gwarantuje, że to nie jest tylko dobre przybliżenie — to dowodowo najbliższa macierz stopnia k w sensie najmniejszych kwadratów, lepsza niż każda inna macierz stopnia k, którą można stworzyć za pomocą jakiejkolwiek innej metody. Ta gwarancja sprawia, że kompresja SVD jest więcej niż zainteresowaniem: dla ustalonego bugetu kompresji matematycznie najlepszym wyborem jest utrzymanie top k wartości singularnych.

A_k = Σᵢ₌₁ᵏ σᵢ · uᵢ vᵢᵀ         (rank-k approximation, k terms kept)

reconstruction error:  ||A − A_k||  =  σ(k+1)     (the largest dropped singular value)

Dlaczego naturalne obrazy kompresują się tak dobrze

Macierz losowa, bez żadnej struktury, rozrzuca swoją energię prawie równomiernie po wartościach singularnych, a skompresowanie jej źle powoduje bardzo szybkie zatępienie rekonstrukcji przy niewielkim liczbie zachowanych wyrazów. Fotografia nie wygląda na to: piksele sąsiadujące są silnie korelowane — pasek nieba jest prawie jednolity, twarz ma gładkie gradienty światła i cienia — a ta nadmierna wartość wskazuje, że wartości singularne maleją szybko, często prawie eksponencjalnie na początku kilkudziesięciu pierwszych. Pierwsze kilka warstw rank-1 już złapano groszowate kształty, ogólne oświetlenie i główne kontury; twarz lub krajobraz stać się rozpoznawalny z przybliżenia stopnia 20 lub 40 obrazu, który może mieć bok długości 512 pikseli, daleko przed zachowaniem prawie wszystkich 512 wartości singularnych.

Gdy zachowywanie wartości k rzeczywiście zapisuje miejsce

Zapis pełnej obrazu o rozmiarach m × n kosztuje mn liczb. Zapis przybliżenia stopnia k kosztuje k kolumn U (każda zawierająca m liczby), k wartości singularnych oraz k wierszy Vᵀ (każdy zawierający n liczb) — w sumie k(m + n + 1) liczb. To jest mniejsze od mn tylko gdy k jest wystarczająco małe:

k(m + n + 1) Dlatego kompresja SVD jest ilustratywna, a nie standardem branżowym dla przechowywania zdjęć: obliczenie pełnej SVD jest drogie dla dużych obrazów, a formaty takie jak JPEG uzyskują porównywalną lub lepszą kompresję używając szybszej transformacji kosinusowej dyskretnej na małych blokach zamiast niej. Gdzie SVD rzeczywiście się wyróżnia, to na danych o silnej globalnej korelacji i autentycznym potrzebę struktury niskorankowej — kompresja przesunięć sensorów, zmniejszanie wymiarowości dużych zbiorów danych numerycznych, lub jako podstawowy element systemów rekomendacyjnych, gdzie „obraz” do rozkładu to macierz preferencji użytkowników zamiast pikseli.

k(m + n + 1)  <  m·n     ⇒     k  <  mn / (m + n)   (roughly)

for a square n×n image:   k  <  n/2   is where compression starts to win

Często zadawane pytania

Dlaczego utrzymanie tylko kilku wartości singularnych nadal wygląda jak oryginalna obrazówka?

Wartości singularne są uporządkowane od największych do najmniejszych, a według twierdzenia Eckart-Young najlepsze k z nich najlepiej przybliżają oryginalną obrazówkę w sensie minimalnego kwadratu. Najnaturalniejsze obrazówki mają rzędy i kolumny z dużą korelacją, więc mała liczba prowadzących warstw rank-1 już rekonstruuje groszowe kształty i gradienty, podczas gdy pozostałe, znacznie mniejsze wartości singularne dodają tylko ciepłą teksturę i szum.

Czy kompresja SVD jest rzeczywiście używana w rzeczywistych formatach obrazów jak JPEG?

Nie. JPEG używa transformacji kosinusowej dyskretnego na małe bloki, co jest znacznie tańsze do obliczenia niż pełna SVD i nie wymaga przechowywania dodatkowych wektorów podstawowych. Kompresja SVD jest głównie narzędziem pedagogicznym i jest stosowana w niektórych kontekstach kompresji danych naukowych i strukturalnych, takich jak kompresja danych z czujników skorelowanych lub zmniejszanie wymiarowości dużych zbiorów danych, a nie w konsumerskich formatach obrazów fotograficznych.

Kiedy utrzymanie k wartości singularnych rzeczywiście oszczędza miejsce na przechowywanie?

Przechowywanie k warstw rank-1 obrazówki m x n kosztuje k(m + n + 1) liczb w porównaniu do mn dla oryginalnej, więc zapisywanie tylko oszczędza miejsce, gdy k jest znacząco mniejsze niż mn/(m+n). Dla kwadratowej obrazówki ten próg wynosi około k < n/2, a spowalniając k znacznie niżej od tego, kompresja SVD staje się naprawdę przydatna, a nie tylko straconym demonstracją.

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz SVD Compression i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.

▶ Otwórz symulację SVD Compression

Kompresja SVD: Obraz Jest Sumą Warstw Stopnia 1