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
źródło
Odpowiedzi:
Przegląd
Krótka odpowiedź jest taka, że mają maksymalną liczbę
vanishing moments
dla danegosupport
(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 widziszD4
falkę określaną jakoD4
lubdb2
.4
Oznacza liczbę współczynników, a2
odnosi 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/7
użytoJPEG 2000
dwóch nazw zamiast jednej. W rzeczywistości jest również nazywanybior 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! Liczby9/7
i4.4
nadal odnoszą się odpowiednio do podparć i momentów zanikania, ale teraz istnieją dwa zestawy współczynników, które definiują falkę. Technicznym terminem jest toorthogonal
, ż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:
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 ] → [ . . 0,0 , 1 , 2 , 3 , 0 , 1 , 2 , 3 , . . . ] [0,1,2,3]→[...,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:
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):
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)ϕ ψ . 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/2–√
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:x0=1 [2,2,2,2]
A co dzieje się przy drugim przejściu, które działa tylko na wygładzonym sygnale:
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.8 82 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ę:
Notatka
Powyższy artykuł zdaje się sugerować, że falka JPEG2000 nosi nazwę Daubechies 9/7 i różni się od falki CDF 9/7.
Projekt standardu JPEG2000 ( link pdf ), który przeglądałem, również nazywa oficjalny filtr Daubechies 9/7. Odwołuje się do tego dokumentu:
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.
źródło
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) .
źródło
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.
źródło
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 - 1k−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.
źródło
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ę.
źródło
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.
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:
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
każę wierzyć, że „najlepszy” aspekt 9/7 nie jest ani w pełni wyjaśniony, ani zapewniony.
źródło