Jakie właściwości sprawiają, że niektóre fale są „lepsze” niż inne w kompresji obrazu?

39

Próbuję nauczyć się więcej na temat kompresji obrazu za pomocą metody transformacji falkowej. Moje pytanie brzmi: co jest takiego w niektórych falach, które czynią je lepszymi podczas kompresji obrazów? Czy łatwiej je obliczyć? Czy zapewniają płynniejsze obrazy? Itp...

Przykład: JPEG 2000 używa Wavelet Cohen-Daubechies-Feauveau 9/7 ... dlaczego ten?

image-processing wavelet

— użytkownik807566
źródło

O ile wiem falka Daubechies zapewnia gładką podstawę, stąd wysoce skompresowane obrazy są „zamazane”. Na przykład falka Haara produkowałaby blokowe artefakty. Ponieważ wspomniałeś o JPEG 2000, chciałbym zauważyć, że również schemat kodowania niezerowych współczynników falkowych ma wpływ na zdekodowane obrazy (EZW, SPIHT, ...).

— Libor,

Na twoje pytanie zostało udzielonych odpowiedzi. Nie wahaj się głosować na te przydatne i zaakceptuj najbardziej odpowiednie

— Laurent Duval

26

Przegląd

Krótka odpowiedź jest taka, że mają maksymalną liczbę vanishing momentsdla danego support(tj. Liczbę współczynników filtra). Jest to „ekstremalna” właściwość, która ogólnie wyróżnia falki Daubechies . Mówiąc luźniej, więcej zanikających momentów oznacza lepszą kompresję, a mniejsze wsparcie oznacza mniej obliczeń. W rzeczywistości kompromis między znikającymi momentami a rozmiarem filtra jest tak ważny, że dominuje sposób, w jaki nazywane są falki. Na przykład często widzisz D4falkę określaną jako D4lub db2. 4Oznacza liczbę współczynników, a2odnosi się do liczby zanikających momentów. Oba odnoszą się do tego samego obiektu matematycznego. Poniżej wyjaśnię więcej o tym, jakie są chwile (i dlaczego chcemy, aby zniknęły), ale na razie po prostu zrozum, że ma to związek z tym, jak dobrze możemy „złożyć” większość informacji w sygnale na mniejszy liczba wartości. Utratę kompresji uzyskuje się poprzez zachowanie tych wartości i odrzucenie pozostałych.

Być może zauważyłeś, że w nazwie CDF 9/7użyto JPEG 2000dwóch nazw zamiast jednej. W rzeczywistości jest również nazywany bior 4.4. To dlatego, że wcale nie jest to „standardowa” dyskretna falka. W rzeczywistości nie zachowuje nawet energii w sygnale, a ta właściwość jest powodem, dla którego ludzie byli tak podekscytowani DWT! Liczby 9/7i 4.4nadal odnoszą się odpowiednio do podparć i momentów zanikania, ale teraz istnieją dwa zestawy współczynników, które definiują falkę. Technicznym terminem jest to orthogonal, że są biorthogonal. Zamiast zagłębiać się w matematyczne rozumowanie, ja ”

JPEG 2000

Bardziej szczegółowe omówienie decyzji projektowych dotyczących falki CDF 9/7 można znaleźć w następującym artykule:

Usevitch, Bryan E. Samouczek na temat nowoczesnej kompresji stratnego obrazu falkowego : podstawy JPEG 2000 .

Po prostu przejrzę tutaj główne punkty.

Dość często ortogonalne falki Daubechies mogą w rzeczywistości powodować zwiększenie liczby wartości wymaganych do przedstawienia sygnału. Efekt jest nazywany coefficient expansion. Jeśli wykonujemy kompresję stratną, która może, ale nie musi mieć znaczenia (ponieważ i tak wyrzucamy wartości na końcu), ale zdecydowanie wydaje się, że w kontekście kompresji jest to bezproduktywne. Jednym ze sposobów rozwiązania tego problemu jest traktowanie sygnału wejściowego jako okresowego.
Traktowanie danych wejściowych jako okresowych powoduje nieciągłości na krawędziach, które są trudniejsze do skompresowania i są tylko artefaktami transformacji. Rozważmy na przykład skoki z 3 do 0 w następującym okresowym przedłużeniu: . Aby rozwiązać ten problem, możemy zastosować symetryczne okresowe przedłużenie sygnału w następujący sposób: . Eliminowanie przeskoków na krawędziach jest jednym z powodów, dla których zamiast DFT w JPEG używana jest dyskretna transformacja kosinusowa (DCT). Reprezentacja sygnału za pomocą cosinusów domyślnie zakłada „zapętlenie od przodu do tyłu” sygnału wejściowego, dlatego chcemy falek, które mają tę samą właściwość symetrii. $[0,1,2,3] \rightarrow [...0,1,2,3,0,1,2,3,...]$ $[0,1,2,3] \rightarrow [...,0,1,2,3,3,2,1,0,0,1...]$
Niestety jedyną ortogonalną falą, która ma wymagane cechy, jest falka Haar (lub D2, db1), która jest tylko jednym znikającym momentem. Ugh. To prowadzi nas do biortogonalnych falek, które w rzeczywistości są zbędnymi reprezentacjami, a zatem nie zachowują energii. Powodem, dla którego falki CDF 9/7 są stosowane w praktyce, jest to, że zostały zaprojektowane tak, aby były bardzo bliskie oszczędzania energii. Sprawdzili się również w praktyce.

Istnieją inne sposoby rozwiązania różnych problemów (wspomniane pokrótce w artykule), ale są to ogólne uderzenia czynników.

Znikające chwile

Więc jakie są chwile i dlaczego się nimi przejmujemy? Gładkie sygnały mogą być dobrze aproksymowane przez wielomiany, tj. Funkcje postaci:

a + b x + c x^{2} + d x^{3} + . . .

$a + bx + cx^2 + dx^3 + ...$

Momenty funkcji (tj. Sygnału) są miarą jej podobieństwa do danej potęgi x. Matematycznie wyraża się to jako iloczyn wewnętrzny funkcji i potęgi x. Znikający moment oznacza, że iloczyn wewnętrzny jest równy zero, a zatem funkcja nie „przypomina” mocy x w następujący sposób (w przypadku ciągłym):

\int x^{n} f (x) d x = 0

$\int{x^n f(x) dx = 0 }$

Teraz każda dyskretna, ortogonalna falka ma dwa powiązane z nią filtry FIR , które są używane w DWT . Jeden to filtr dolnoprzepustowy (lub skalowany) , a drugi to filtr górnoprzepustowy (lub falkowy) $\phi$ $\psi$ . Ta terminologia wydaje się nieco różna, ale tego tu użyję. Na każdym etapie DWT filtr górnoprzepustowy służy do „odrywania” warstwy szczegółów, a filtr dolnoprzepustowy zapewnia wygładzoną wersję sygnału bez tych szczegółów. Jeśli filtr górnoprzepustowy ma momenty zanikania, momenty te (tj. Cechy wielomianowe niskiego rzędu) zostaną wypchnięte w uzupełniającym wygładzonym sygnale, a nie w sygnale szczegółowym. Mam nadzieję, że w przypadku kompresji stratnej sygnał szczegółów nie będzie zawierał zbyt wielu informacji, dlatego też możemy go wyrzucić.

Oto prosty przykład użycia falki Haar (D2). Zazwyczaj występuje współczynnik skalowania , ale pomijam go tutaj, aby zilustrować tę koncepcję. Dwa filtry są następujące: $1/\sqrt{2}$

ϕ = [1, 1] ψ = [1, - 1]

$\phi = [1,1] \\ \psi = [1,-1]$

Filtr górnoprzepustowy znika dla momentu zerowego, tj. , dlatego ma jeden moment zanikania. Aby to zobaczyć, rozważ ten stały sygnał: . Teraz intuicyjnie powinno być oczywiste, że nie ma tam dużo informacji (ani żadnego stałego sygnału). Możemy to samo opisać, mówiąc „cztery dwójki”. DWT umożliwia nam wyraźne opisanie tej intuicji. Oto, co dzieje się podczas jednego przejścia DWT za pomocą falki Haar: $x^0 = 1$ $[2,2,2,2]$

[2, 2, 2, 2] \to_{ψ}^{ϕ} {\begin{array}{rr} [2 + 2, 2 + 2] = [4, 4] \\ [2 - 2, 2 - 2] = [0, 0] \end{array}

$[2,2,2,2] \rightarrow_{\psi}^{\phi} \left\{ \begin{array}{rr} \left[2 + 2, 2 + 2\right] = \left[4,4\right] \\ \left[2-2,2-2\right] = \left[0,0\right] \end{array}\right.$

A co dzieje się przy drugim przejściu, które działa tylko na wygładzonym sygnale:

[4, 4] \to_{ψ}^{ϕ} {\begin{array}{rr} [4 + 4] = [8] \\ [4 - 4] = [0] \end{array}

$[4,4] \rightarrow_{\psi}^{\phi} \left\{ \begin{array}{rr} \left[4 + 4\right] = \left[8\right] \\ \left[4-4\right] = \left[0\right] \end{array}\right.$

Zauważ, że stały sygnał jest całkowicie niewidoczny dla przebiegów detali (które wszystkie mają wartość 0). Zauważ też, jak cztery wartości zostały zredukowane do pojedynczej wartości . Gdybyśmy chcieli przesłać oryginalny sygnał, moglibyśmy po prostu wysłać , a odwrotny DWT może zrekonstruować oryginalny sygnał, zakładając, że wszystkie współczynniki detalu są zerowe. Falki z momentami zanikania wyższego rzędu pozwalają na uzyskanie podobnych wyników z sygnałami, które są dobrze aproksymowane liniami, parabolami, sześciennymi itp. $2$ $8$ $8$

Dalsza lektura

Przeglądam DUŻO szczegółów, aby powyższe leczenie było dostępne. Poniższy artykuł zawiera znacznie głębszą analizę:

M. Unser i T. Blu, Matematyczne właściwości filtrów falkowych JPEG2000 , IEEE Trans. Image Proc., Vol. 12, nr 9 września 2003 r., Str. 1080-1090.

Notatka

Powyższy artykuł zdaje się sugerować, że falka JPEG2000 nosi nazwę Daubechies 9/7 i różni się od falki CDF 9/7.

Wyprowadziliśmy dokładną formę filtrów skalowania JPEG2000 Daubechies 9/7 ... Filtry te wynikają z faktoryzacji tego samego wielomianu co [10]. Główną różnicą jest to, że filtry 9/7 są symetryczne. Co więcej, w przeciwieństwie do biortogonalnych splajnów Cohena-Daubechies-Feauveau [11], nieregularna część wielomianu została podzielona między obie strony i możliwie równomiernie. $Daubechies_{8}$

[11] A. Cohen, I. Daubechies i JC Feauveau, „Biortogonalne zasady falo wspieranych fal”, Comm. Pure Appl. Math., Vol. 45, nr 5, str. 485–560, 1992.

Projekt standardu JPEG2000 ( link pdf ), który przeglądałem, również nazywa oficjalny filtr Daubechies 9/7. Odwołuje się do tego dokumentu:

M. Antonini, M. Barlaud, P. Mathieu i I. Daubechies, „Kodowanie obrazu przy użyciu transformaty falkowej”, IEEE Trans. Image Proc. 1, s. 205–220, kwiecień 1992 r.

Nie przeczytałem żadnego z tych źródeł, więc nie mogę powiedzieć na pewno, dlaczego Wikipedia nazywa falę JPEG2000 CDF 9/7. Wydaje się, że może istnieć różnica między nimi, ale ludzie i tak nazywają oficjalną falkę JPEG2000 CDF 9/7 (ponieważ jest oparta na tej samej podstawie?). Niezależnie od nazwy, artykuł Usevitch opisuje ten, który jest używany w standardzie.

— Datageist
źródło

@datageist Fantastyczna odpowiedź! Kolejnym powodem, dla którego 9/7 istniało, było to, że był to alternatywny sposób na uwzględnienie wielomianu rekonstrukcji, z ograniczeniem symetryczności filtrów . W ten sposób odpowiedź fazowa pozostaje liniowa. (W przeciwieństwie do tego, falka daub4, podczas gdy FIR, jest asymetryczna i indukuje fazy nieliniowe w przetwarzanym sygnale). 9/7 zostało użyte w JPEG ze względu na subiektywną skłonność do lubienia zniekształceń liniowych nad nieliniowymi na obrazach.

— Spacey,

1

Niezły artykuł. Informacje w artykule na Wikipedii odpowiadają cytowanym źródłom, zasadniczo Daubechies „10 Lectures”, więc mogą być nieaktualne w stosunku do JPEG2000. Jedna korekta: biortogonalna nie jest zbędna. Warunki biortogonalności narzucają dokładnie odwrotne banki filtrów. Zbędne transformacje zaczynają się od frameletów.

— Dr Lutz Lehmann

10

Dobroć transformacji sygnału jest oceniana na podstawie dwóch różnych wskaźników: kompresji, aw przypadku kompresji stratnej - jakości. Kompresja jest definiowana przez kompresję energii, ale jakość jest trudniejsza.

Tradycyjnie jakość mierzono za pomocą błędu średniego kwadratu lub średniego SNR na piksel. Jednak ludzie nie mają tendencji do oceny sygnałów za pomocą MSE lub SNR. Ludzie są bardzo wrażliwi na ustrukturyzowany hałas, gdzie MSE zwykle nie jest. Opracowywanie algorytmów dostarczających wskaźniki jakości podobne do ludzkich jest aktywnym obszarem badań. Dobrym początkiem jest indeks Bovik Structural SIMilarity (SSIM) .

— totowtwo
źródło

6

Jako bardzo krótka odpowiedź - każda transformacja jest lepsza niż inna transformacja, gdy ma, co jest znane jako „właściwość zagęszczania energii”, co wyjaśniono poniżej:

„gdy tylko niewielki ułamek współczynników transformacji ma tak duże wartości, że utrzymywanie tylko kilku współczynników oraz odrzucanie lub kwantyzowanie innych nadal pozwala na prawie całkowitą odbudowę”. Taka właściwość jest związana z zdolnością dekorelacji jednostkowych przekształceń ”.

Transformacja z właściwością mniejszego zagęszczenia energii to taka, która będzie wymagała najmniejszej liczby symboli, a tym samym mniejszych bitów.

Transformacja o najwyższej właściwości zagęszczania energii to DCT.

Dipan.

— Dipan Mehta
źródło

1

DCT ma najwyższe zagęszczenie energii dla nieznanych klas sygnałów. Jeśli potrafisz scharakteryzować swoją domenę sygnałową, możesz zrobić lepiej.

— totowtwo 24.10.11

Zgadzam się @totowtwo. Chodzi mi o to, że „właściwość zwartości energii” sprawia, że pewna transformacja jest tym, co czyni ją preferowaną w przypadku silników kodeków.

— Dipan Mehta,

5

Naturalne obrazy składają się z różnych funkcji obrazu, możemy ogólnie podzielić je na gładkie lub wolno zmieniające się funkcje, tekstury i krawędzie. Dobra metoda kompresji to taka, która przekształca obraz w domenę, w której cała energia sygnału jest zachowana w zaledwie kilku współczynnikach.

Transformacja Fouriera próbuje przybliżyć obraz za pomocą sinusów i cosinusów. Teraz sinus i cosinus mogą dość zwięźle aproksymować gładkie sygnały, ale są niezbyt dobre dla przybliżania nieciągłości. Jeśli znasz zjawisko Gibbsa, będziesz wiedział, że potrzeba wielu liczbowych współczynników Fouriera, aby uniknąć artefaktów przybliżania nieciągłości w czasie. Jednak im mniejsza liczba współczynników, tym lepsza kompresja. Dlatego istnieje nieodłączny kompromis między liczbą współczynników a stratą metody kompresji, którą zwykle nazywamy kompromisem zniekształcenia stopy.

Szukając lepszego schematu kompresji niż jpeg, który wykorzystuje transformaty Fouriera, potrzebowalibyśmy transformacji, która może aproksymować nieciągłości o mniejszych współczynnikach niż transformata Fouriera, dla tego samego zniekształcenia. Wprowadź falki, które oferują lepsze przybliżenie, a tym samym lepszą kompresję osobliwości punktowych bez zjawiska Gibbsa, takiego jak artefakty. W praktyce obrazy nigdy nie są czysto gładkie, dlatego też falki są bardziej uniwersalne niż Fourier dla różnych funkcji obrazu. Gdybyśmy porównali najlepsze przybliżenie k-termiczne obrazu zawierającego krawędzie przy użyciu zarówno Fouriera, jak i falek, błędy zanikałyby jako i $k^{-2/3}$ $k^{-1}$ , odpowiednio, kolejno. Przy tej samej liczbie terminów błąd zanika szybciej dla falek. Oznacza to, że falki mają lepsze zagęszczenie energii, gdy obrazy nie są idealnie gładkie (powoli się zmieniają) i zawierają osobliwości.

Jednak jak dotąd nie mamy ani jednej podstawy ani transformacji, które mogłyby aproksymować gładkie elementy, osobliwości punktowe, krawędzie i tekstury.

— użytkownik3303
źródło

4

DCT ma bardzo dobre zagęszczenie energii dla wielu popularnych sygnałów, a także dość dobrze zazębia się z tym, jak działa dyfrakcja (podstawowy proces fizyczny w obrazowaniu), ponieważ dyfrakcję można przedstawić jako jądro czteroliniowe. Dają to wiele zalet.

Problem polega na tym, że współczynniki DCT są koniecznie przeniesione na cały obszar transformacji. Wymaga to utworzenia wielu małych obszarów transformacji (bloków), aby energia w jednym obszarze nie rozlewała się na inny podczas transformacji. Ogranicza to zdolność transformacji do kompaktowania energii, a także wprowadza artefakty na wielu granicach bloków.

Nie zrobiłem wiele z falkami, więc mogę się mylić, ale są one bardziej delokalizowane, z różnymi współczynnikami reprezentującymi różne kompromisy obszar / częstotliwość. Pozwala to na większe rozmiary bloków z mniejszą liczbą artefaktów. Nie ma jednak pewności w praktyce, ile to naprawdę robi różnicę.

— saratoga
źródło

0

Mówiąc o lepszych falkach, powinniśmy wziąć pod uwagę, że mają oni ten sam enkoder z tyłu: wydajność transformacji jest ściśle powiązana z kwantyzacją i kodowaniem. Wydajność to zwykle: lepsza kompresja dla tej samej jakości lub lepsza jakość dla tej samej kompresji. Kompresja jest łatwym środkiem, jakość nie. Ale załóżmy, że mamy jeden.

$\times 124$ $\times 4$

Wreszcie, zależy to od klasy obrazów, które chcesz skompresować: uniwersalnego lub skoncentrowanego, jak w przypadku obrazów medycznych lub kompresji danych sejsmicznych, z ograniczonymi, specyficznymi typami danych? Tutaj znowu falki mogą być różne.

Jakie są główne składniki morfologiczne obrazów i jak radzą sobie z nimi falki:

powolne trendy, zmieniające się tła: znikające momenty, które pozbywają się wielomianów w podpasmach falkowych,
nierówności: ok z funkcjami skalowania,
krawędzie: wychwytywane przez pochodny aspekt falek,
tekstury: oscylacje uchwycone przez poruszający się aspekt falek,
reszta, która jest głośna, niemodelowana: zarządzana przez ortogonalność (lub też blisko).

Więc po stronie analizy najlepsze falki są dobre, ładnie zagęszczając powyższe cechy na całym świecie. Po stronie syntezy najlepsze falki łagodzą efekty kompresji, na przykład kwantyzację, aby uzyskać przyjemny aspekt. Właściwości wymagane przy analizie / syntezie są nieco inne, dlatego biortogonalne falki są ładne: możesz oddzielić właściwości analizy (momenty zanikania) / syntezy (gładkości), których nie można zrobić z ortogonalnymi, i powoduje zwiększenie długości filtra , dość szkodliwe dla wydajności obliczeniowej. Dodatkowe, biortogonalne falki mogą być symetryczne, dobre dla krawędzi.

Wreszcie, czy chcesz trochę bezstratnej kompresji? Następnie potrzebujesz falek podobnych do „liczb całkowitych” (lub binletów).

A wszystko to w połączeniu z zagadnieniami obliczeniowymi: oddzielne falki, niezbyt długie. I proces standaryzacji w komitecie JPEG.

Wreszcie, 5/3 jest dość dobry na bezstratny, wystarczająco krótki. Niektóre z 9/7 są również dobre. O wiele lepszy niż falka 13/7 ? Nie bardzo, a nawet jeśli jest to w PSNR, nie najlepsza jakość obrazu.

Tak więc najlepsze falki znajdują się w odległości krótkiego spaceru od tradycyjnych obrazów i osobistej komunikacji z autorami

M. Unser i T. Blu, Matematyczne właściwości filtrów falkowych JPEG2000 , IEEE Trans. Image Proc., Vol. 12, nr 9 września 2003 r., Str. 1080-1090.

każę wierzyć, że „najlepszy” aspekt 9/7 nie jest ani w pełni wyjaśniony, ani zapewniony.

$M$

— Laurent Duval
źródło