Transformacja falkowa

9

Chcę wykonać dyskretną transformatę falkową 2D haar i odwrotną DWT na obrazie. Czy możesz wyjaśnić dyskretną transformatę falkową 2D haar i odwrotną DWT w prostym języku i algorytmie, za pomocą którego mogę napisać kod dla 2D haar dwtInformacje podane w Google były zbyt techniczne. Zrozumiałem podstawowe rzeczy, takie jak podział obrazu na 4 podpasma: LL, LH, HL, HH, ale tak naprawdę nie rozumiem, jak napisać program do wykonywania DWT i IDWT na Przeczytałem również, że DWT jest lepszy niż DCT, ponieważ jest wykonywany na obrazie jako całości, a potem pojawiło się jakieś wyjaśnienie, które przeleciało mi przez głowę. Mogę się tu mylić, ale myślę, że techniki kompresji DWT i DCT ponieważ rozmiar obrazu zmniejsza się, gdy wykonywany jest na nich DWT lub DCT. Chłopaki, którzy dzielą się częścią swojej wiedzy i poszerzają moją wiedzę.

Dziękuję Ci

Re: Czy to ma coś wspólnego z formatem obrazu. Co to jest „wartość piksela” używana w DWT? Przyjąłem, że jest to wartość rgb obrazu.

import java.awt.event.*;
import javax.swing.*;
import java.awt.image.BufferedImage;
import javax.swing.JFrame;
import javax.swing.SwingUtilities;
import java.io.*;
import javax.swing.JFileChooser;
import javax.swing.filechooser.FileFilter;
import javax.swing.filechooser.FileNameExtensionFilter;
import javax.imageio.ImageIO;
import java.awt.*;
import java.lang.*;
import java.util.*;

class DiscreteWaveletTransform

{

    public static void main(String arg[])
    { DiscreteWaveletTransform dwt=new DiscreteWaveletTransform();
      dwt.initial();
    }


    static final int TYPE=BufferedImage.TYPE_INT_RGB;
    public void initial()
    {
    try{

        BufferedImage buf=ImageIO.read(new File("lena.bmp"));
        int w=buf.getWidth();
        int h=buf.getHeight();
        BufferedImage dwtimage=new BufferedImage(h,w,TYPE);
        int[][] pixel=new int[h][w];
        for (int x=0;x<h;x++)
        {
            for(int y=0;y<w;y++)
            {
                pixel[x][y]=buf.getRGB(x,y);


            }
        }
        int[][] mat =  new int[h][w];
        int[][] mat2 =  new int[h][w];

        for(int a=0;a<h;a++)
        {
            for(int b=0,c=0;b<w;b+=2,c++)
            {
                mat[a][c]    = (pixel[a][b]+pixel[a][b+1])/2;
                mat[a][c+(w/2)]  = Math.abs(pixel[a][b]-pixel[a][b+1]);
            }
        }
        for(int p=0;p<w;p++)
        {
            for(int q=0,r =0 ;q<h;q+=2)
            {
                mat2[r][p]   = (mat[q][p]+mat[q+1][p])/2;
                mat2[r+(h/2)][p] = Math.abs(mat[q][p]-mat[q+1][p]);
            }
        }
        for (int x=0;x<h;x++)
        {
            for(int y=0;y<w;y++)
            {
                dwtimage.setRGB(x,y,mat2[x][y]);
            }
        }
        String format="bmp";
        ImageIO.write(dwtimage,format, new File("DWTIMAGE.bmp"));
        }

        catch(Exception e)
        {
            e.printStackTrace();
        }
    }
}

Wyjście to czarny obraz z cienką linią pośrodku, krótko mówiąc nigdzie w pobliżu rzeczywistego wyniku. Myślę, że źle zinterpretowałem logikę. Proszę wskazać błędy. pozdrowienia

użytkownik1320483
źródło
Powyższy kod wiele dla mnie znaczy, dziękuję. Czy możesz podać kod Java dla odwrotnej transformacji haar 2D

Odpowiedzi:

15

Czy możesz wyjaśnić dyskretną transformatę falkową 2D haar i odwrotną DWT w prostym języku?

Warto pomyśleć o transformacie falkowej w kategoriach dyskretnej transformaty Fouriera (z wielu powodów, patrz poniżej). W transformacie Fouriera rozkładasz sygnał na szereg ortogonalnych funkcji trygonometrycznych (cos i sin). Konieczne jest, aby były one ortogonalne, aby można było rozłożyć sygnały na szereg współczynników (dwóch funkcji, które są zasadniczo NIEZALEŻNE od siebie) i ponownie skomponować je ponownie.

Mając na uwadze to kryterium ortogonalności , czy można znaleźć dwie inne funkcje, które są ortogonalne oprócz cos i grzechu?

Tak, możliwe jest wymyślenie takich funkcji z dodatkową przydatną cechą, że nie rozciągają się one na nieskończoność (tak jak cos i grzech). Jednym z przykładów takiej pary funkcji jest falka Haara .

Teraz, jeśli chodzi o DSP, być może bardziej praktyczne jest myślenie o tych dwóch „funkcjach ortogonalnych” jako dwóch filtrach o skończonej odpowiedzi impulsowej (FIR) i dyskretnej transformacie falkowej jako serii zwojów (lub innymi słowy, stosowanie tych filtrów kolejno w niektórych szeregach czasowych). Możesz to zweryfikować poprzez porównanie i porównanie wzorów 1-D DWT i wzorów splotu .

W rzeczywistości, jeśli zauważysz ściśle funkcje Haar, zobaczysz dwa najbardziej podstawowe filtry dolnoprzepustowy i górnoprzepustowy. Oto bardzo prosty filtr dolnoprzepustowy h = [0,5,0,5] (na chwilę nie martw się skalowaniem) znany również jako filtr średniej ruchomej, ponieważ zasadniczo zwraca średnią z dwóch sąsiednich próbek. Oto bardzo prosty filtr górnoprzepustowy h = [1, -1] znany również jako czynnik różnicujący, ponieważ zwraca różnicę między dowolnymi dwoma sąsiadującymi próbkami.

Aby wykonać DWT-IDWT na obrazie, wystarczy po prostu zastosować dwuwymiarowe wersje splotu (do sukcesywnego stosowania filtrów Haar).

Być może teraz możesz zacząć widzieć, skąd pochodzą części LowLow, LowHigh, HighLow, HighHigh obrazu poddanego DWT. JEDNAK pamiętaj, że obraz ma już DWIE WYMIARY (może to być mylące czasami). Innymi słowy, musisz wyprowadzić niskie-wysokie częstotliwości przestrzenne dla osi X i takie same zakresy dla osi Y (dlatego są dwie niskie i dwie wysokie na oś)

i algorytm, za pomocą którego mogę napisać kod 2D haar dwt?

Musisz naprawdę spróbować samodzielnie kodować to od pierwszych zasad, aby zrozumieć cały proces. Bardzo łatwo jest znaleźć gotowy fragment kodu, który zrobi to, czego szukasz, ale nie jestem pewien, czy to naprawdę pomoże ci w dłuższej perspektywie.

Mogę się tutaj mylić, ale myślę, że techniki kompresji DWT i DCT, ponieważ rozmiar obrazu zmniejsza się, gdy wykonuje się na nich DWT lub DCT

W tym miejscu naprawdę „opłaca się” myśleć o DWT w kategoriach transformacji Fouriera. Z następującego powodu:

W transformacie Fouriera (i oczywiście również DCT) transformujesz WIELE PRÓBEK (w dziedzinie czasu) do JEDNEGO (złożonego) współczynnika (w dziedzinie częstotliwości). Wynika to z faktu, że konstruujesz różne sinusoidy i cosinusoidy, a następnie mnożysz je za pomocą sygnału i uzyskujesz średnią tego produktu. Zatem wiesz, że pojedynczy współczynnik Ak reprezentuje przeskalowaną wersję sinusoidy o pewnej częstotliwości (k) w twoim sygnale.

Teraz, jeśli spojrzysz na niektóre funkcje falek, zauważysz, że są one nieco bardziej złożone niż proste sinusoidy. Rozważmy na przykład transformatę Fouriera filtra górnoprzepustowego Haar ... Filtr górnoprzepustowy Haar wygląda jak fala prostokątna, tzn. Ma ostre krawędzie (ostre przejścia) ... Co potrzeba, aby utworzyć OSTRE KRAWĘDZIE? .. ... Wiele, wiele różnych sinusoid i współsinusoidów (!)

Dlatego reprezentowanie sygnału / obrazu za pomocą falek oszczędza więcej miejsca niż reprezentowanie go za pomocą sinusoidów DCT, ponieważ JEDEN zestaw współczynników falek reprezentuje WIĘCEJ WSPÓŁCZYNNIKÓW DCT. (Nieco bardziej zaawansowanym, ale pokrewnym tematem, który może być pomocny w zrozumieniu, dlaczego to działa w ten sposób, jest Filtrowanie dopasowane ).

Dwa dobre linki online (moim zdaniem przynajmniej :-)) to: http://faculty.gvsu.edu/aboufade/web/wavelets/tutorials.htm i; http://disp.ee.ntu.edu.tw/tutorial/WaveletTutorial.pdf

Osobiście uważam, że bardzo pomocne są następujące książki: http://www.amazon.com/A-Wavelet-Tour-Signal-Processing/dp/0124666051 (autor: Mallat) i; http://www.amazon.com/Wavelets-Filter-Banks-Gilbert-Strang/dp/0961408871/ref=pd_sim_sbs_b_3 (autor: Gilbert Strang)

Oba są absolutnie genialnymi książkami na ten temat.

mam nadzieję, że to pomoże

(przepraszam, właśnie zauważyłem, że ta odpowiedź może być nieco zbyt długa: - /)

A_A
źródło
Jestem zachwycony, że odpowiedziałeś. Dziękuję, że odpowiedziałeś A_A. Na podstawie matematycznej interpretacji DWT, którą znalazłem w artykule IEEE, napisałem kod. Jednak wszystko, co otrzymuję, to czarny obraz, proszę, pomóż mi.
user1320483
Napisanie kodu do wykonania DWT naprawdę wiele dla mnie znaczy. (Proszę) ^ ∞. Będę naprawdę wdzięczny. Wysłałem powyższy kod.
user1320483
W kodzie należy zwrócić uwagę na dwie rzeczy: a) Przejrzyj dwuwymiarową wersję splotu (w tym przypadku nie jest to prostsze) i b) Pamiętaj, że „obraz” jest zbiorem współczynników, które mogą być bardzo małe lub bardzo duże, a w każdym razie poza wspólnym zakresem dynamicznym 255 kolorów. Dlatego musisz znaleźć zakres swoich współczynników i przeskalować go do przedziału 0,255. Czy wybierasz tylko jeden poziom rozkładu?
A_A
a) Proszę przejrzeć dwuwymiarową wersję splotu (w tym przypadku nie jest to prostsze). Nie jestem pewien, co przez to rozumiesz. „obraz” to zestaw współczynników, które mogą być bardzo małe lub bardzo duże, a poza tym mają wspólny zakres dynamiczny 255 kolorów. Oznacza to, że po dodaniu muszę sprawdzić, czy wartość przekracza 255 i czy zaczyna się od 0? Czy wybierasz tylko jeden poziom rozkładu? Tak, dziękuję bardzo
1320483
Rozumiem przez (a), że jeśli chcesz zastosować filtry Haar (zgodnie z odpowiedzią podaną powyżej), będziesz musiał sprawdzić, jak to się dzieje poprzez operację splotu, aw przypadku filtrów Haar jest to bardzo prosty. Tak, musisz znormalizować swoje współczynniki w zakresie 0-255, aby móc je „zobaczyć”. Jeśli chodzi o RGB, proszę skupić się na obrazach w skali szarości (tylko jedna wartość). Musisz najpierw zrozumieć, co musisz zrobić, a następnie to zrobić. Poszukiwanie „kodu” na dłuższą metę będzie bardziej czasochłonne.
A_A
8

Zacząłem pisać to przed odpowiedzią z @A_A , ale ta odpowiedź jest doskonała. Mimo to mam nadzieję, że poniższe informacje mogą nieco poprawić twoje zrozumienie.

Dyskusja na temat falek i tak dalej wchodzi w ogólną dyskusję na temat podstawowego rozkładu sygnałów. Rozumiemy przez to, że możemy reprezentować nasz sygnałx jako produkt jakiejś macierzy bazowej, H, a wektor reprezentujący nasz sygnał w podstawie alternatywnej (rozkład podstawy), x~. To jest:

x=Hx~
Podstawa macierzy H jest zazwyczaj macierzą ortonormalną (np. dyskretną macierzą Fouriera, macierzą falkową Haara), ale nie musi być - istnieją całe dziedziny badań nad rozkładem sygnałów na nadmiernie kompletne słowniki, co oznacza H szerszy niż jest wysoki (np. dzięki algorytmom minimalnej normy L1).

Ideą leżącą u podstaw dekompozycji sygnału jest to, że sygnał może być reprezentowany w lepszy sposób w alternatywnej podstawie. Mówiąc lepiej , mamy na myśli, że sygnał jest w jakiś sposób bardziej podatny na przetwarzanie, zrozumienie lub cokolwiek innego - to naprawdę nie ma znaczenia.

Należy zauważyć, że szczególnie w przypadku transformacji ortonormalnej twój sygnał jest nadal sygnałem niezależnie od tego, w jakiej jest on podstawie. Nie powinieneś myśleć o jednej podstawie jako w jakiś sposób właściwej domenie (używam domeny jako podstawy w ogólnym znaczeniu) .

Teraz różne zasady mają różne właściwości. Jestem pewien, że doskonale zdajesz sobie sprawę z twierdzenia splotowego opisującego użyteczny związek między domeną Fouriera a dziedziną czasu. To sprawia, że ​​domena Fouriera jest przydatna do wykonywania operacji splotu w dziedzinie czasu.

Zasadniczo dziedzinę czasu (lub piksela) można uznać za posiadającą doskonałą rozdzielczość czasową (przestrzenną) i rozdzielczość złej częstotliwości. I odwrotnie, dziedzinę Fouriera można uznać za posiadającą doskonałą rozdzielczość częstotliwości i rozdzielczość czasu złego (lub przestrzennego).

Podstawy falkowe pasują gdzieś pośrodku powyższych dwóch. Zwykle mają dobrą rozdzielczość częstotliwości i dobrą rozdzielczość czasową lub przestrzenną. Jedną z właściwości transformacji falkowej jest dobre sparifikowanie naturalnych obrazów. Rozumiem przez to, że energia z obrazu jest skompresowana do kilku dużych współczynników i wielu małych współczynników. Oznacza to, że większość istotnych informacji o sygnale jest reprezentowana przez stosunkowo niewielki zestaw wartości. To jest istota kompresji.

Różne falki mają różne właściwości. Oprócz odniesień z @A_A, polecam również ten samouczek IEEE na temat DTCWT. Głównym celem nie jest tutorial na transformaty falkowej per se , ale powodem polecam go z powodu fantastycznej intuicji Przedstawia on problemów wiąże się ze DWT i jak mogą być złagodzone (powiedziałbym, że wymaga podstawowej wiedzy najpierw). Naprawdę łączy zrozumienie fal z rozumieniem transformacji Fouriera i dlaczego ta ostatnia ma ładne właściwości.

Jeśli chcesz więcej kodu referencyjnego na temat transformacji Haara, mój były przełożony ma kilka przykładów matlaba na swojej stronie internetowej (plik zip w „Kursie kodowania obrazu 4F8”, HAAR2D.M i IHAAR2D.M). Są to jednak bardzo przykłady nauczania.

Henry Gomersall
źródło