plik

Sławomir Kulesza

slawek.kulesza@gmail.com

Wydział Matematyki i Informatyki

Cyfrowe przetwarzanie sygnałów (6/7)

Wykład dla studentów I roku Informatyki UWM w Olsztynie

Specjalność: Multimedia

Transformaty ortogonalne – przypomnienie

Transformatą T nazywamy przekształcenie, które sygnałowi x przyporządkowuje
sygnał y taki, że:

y=T⋅x

gdzie:

x=

[

...

N −1

]

; y=

[

...

N −1

]

; T =

[

0,0

0,1

...

0, N −1

1,0

1,1

...

1, N −1

...

N −1,0

N −1,1

... t

N −1, N −1

]

Spośród wszystkich możliwych przekształceń sygnału, pozycję wyróznioną
zajmują transformaty ortogonalne.

Własności przekształceń ortogonalnych

Przekształcenia ortogonalne:

–

zachowują energię sygnału (są transformatami bezstratnymi):

y

=y

⋅y=x

⋅x=x



T⋅x

⋅

T⋅x=x

⋅

T⋅x

Macierz odwrotna transformaty powstaje przez transpozycję macierzy prostej:

T =

[

0,0

0,1

...

0, N −1

1,0

1,1

...

1, N −1

...

N −1,0

N −1,1

... t

N −1, N −1

]

−

[

0,0

1,0

...

N −1,0

0,1

1,1

...

N −1,1

...

0, N −1

1, N −1

... t

N −1, N −1

]

Przykłady przekształceń ortogonalnych

Do przekształceń ortogonalnych zalicza się m.in.:

–

transformatę Karhunena-Loevego,

–

dyskretną transformatę Fouriera,

–

dyskretną transformatę kosinusową,

–

transformaty falkowe.

Transformaty ortogonalne – transformata Karhunena-Loevego



–

Transformata optymalna w sensie upakowania energetycznego sygnału –
dekorelacja próbek obniża entropię sygnału do wartości minimalnej.

–

Funkcje bazowe są konstruowane w oparciu o sygnał kodowany –
transformata adaptacyjna.



–

Wynik kodowania silnie uzależniony od danych wejściowych (kłopot dla
kodowania predykcyjnego).

–

Duża złożoność obliczeniowa (obliczenie macierzy kowariancji, rozwiązanie
zagadnienia własnego) – brak szybkich algorytmów.

Transformata jako przekształcenie rzutujące

Przekształcenie ortogonalne można wyobrażać sobie jako rzutowanie wektora
sygnału na przestrzeń rozpinaną przez wektory bazowe tworzące macierz
przekształcenia. Wówczas, otrzymane współczynniki transformaty opisują
podobieństwo sygnału transformowanego oraz wektorów bazowych.

Rzutowanie na przykładzie DFT

Zdjęcie oryginalne (16x16 px) oraz wektor bazowy (u=15, v=15):

Rzutowanie polega na wysumowaniu iloczynów wartości piksela obrazu i bazy.
W ten sposób określa się podobieństwo obrazu do wzorca ('zawartość' wzorca w obrazie).

Tablica wektorów bazowych FT dla bloków 16x16 px

Transformaty ortogonalne –

dyskretna transformata kosinusowa (DCT)

Prosta i odwrotna transformaty kosinusowe zdefiniowane są następująco:

S u=

C u



N / 2

∑

x=0

N −1

s x⋅cos



2 x1⋅u⋅

2⋅N



s x =

∑

u=0

N −1

C u



N /2

S u⋅cos



2 x1⋅u⋅

2⋅N



gdzie:

C u=

{



⇔

u=0

1⇔u0

}

DCT jest transformatą ortogonalną

∑

x=0

N −1

C u



N / 2

⋅

cos



2 x1⋅u⋅

2⋅N



⋅

C v 



N / 2

⋅

cos



2 x1⋅v⋅

2⋅N



{

1⇔ u=v
0⇔ u≠v

}

Tak więc:





S u⋅S v =



⇒



v =S

−



v

Przy tym:

S v =S



v 

Macierz DCT jest więc także symetryczna.

2D (i)DCT

2-wymiarowa DCT zdefiniowana jest następująco:

S u , v =

C u



N /2

⋅

C v 



N /2

∑

x=0

N −1

∑

y=0

N −1

s x , y⋅cos



2 x1⋅u⋅

2⋅N



⋅

cos



2 y1⋅v⋅

2⋅N



Transformata odwrotna ma postać:

s x , y =

∑

u=0

N −1

∑

v=0

N −1

C u



N / 2

⋅

C v



N /2

S u , v ⋅cos



2 x1⋅u⋅

2⋅N



⋅

cos



2 y1⋅v⋅

2⋅N



Tablica wektorów bazowych DCT dla bloków 8x8 px

Separowalność 2D DCT

2-wymiarową DCT można wyrazić jako:

S u , v =

C u



N /2

⋅

C v 



N /2

∑

x=0

N −1

∑

y=0

N −1

s x , y⋅cos



2 x1⋅u⋅

2⋅N



⋅

cos



2 y1⋅v⋅

2⋅N



...

...=

C u



N /2

⋅

C v 



N /2



∑

x=0

N −1

cos



2 x1⋅u⋅

2⋅N



⋅



∑

y =0

N −1

s x , y⋅cos



2 y1⋅v⋅

2⋅N



Oznacza to, że 2D DCT można obliczyć poprzez dwukrotne wykonanie 1D DCT
na wierszach oraz kolumnach obrazu:

Kodowanie i kompresja DCT – przykład

Obraz oryginalny

2D DCT (log 10)

Rekonstrukcja obrazu po obcięciu 80 % współczynników DCT

Rekonstrukcja obrazu po obcięciu 90 % współczynników DCT

Rekonstrukcja obrazu po obcięciu 95 % współczynników DCT

Rekonstrukcja obrazu po obcięciu 99 % współczynników DCT

Związki pomiędzy DCT a DFT

Zauważmy, że z dowolnego sygnału rzeczywistego s(n) można zawsze wydzielić
składową parzystą (even, symmetric) i nieparzystą (odd, antisymmetric):

sn=s



ns



n

gdzie:



n=



sns−n





n=

1
2



sn−s−n



Z własności DFT wynika jednak, że:

DFT  sn=DFT



ns



n



=ℜ

S n j⋅ℑS n

Ostatecznie:

DFT



n



=ℜ

S n

DFT



n



= ℑ

S n

Przedłużenie symetryczne sygnału

Ponieważ funkcje cos są parzyste, zaś współczynniki DCT – rzeczywiste, istnieje
analogia do transformowania sygnałów parzystych przy pomocy DFT. Należy
zatem oczekiwać, iż DCT daje się wyrazić przy pomocy parzystego rozwinięcia
DFT.

Z dowolnego sygnału można utworzyć sygnał parzysty, gdy dokona się jego
symetrycznego przedłużenia:

Obliczenia DCT przy pomocy DFT (FFT)

W celu obliczenia DCT można wykorzystać algorytmy FFT, co jest możliwe dzięki
istnieniu zależności takich jak np.:

S k =



ℜ



exp−

j k 

2 N



∑

m=0

2N−1



⋅

exp−

j 2

2 N



k⋅m



(*)

gdzie: S(k) – oznacza współczynniki DCT, zaś um jest wektorem sygnału s(m)
uzupełnionym zerami:

u  m=





... , 

N −1

, 

N 1

,... , 

2N−1





... , s

N −1

, 0,0, ,... , 0



Zauważmy, że powyższe wyrażenie zawiera k-ty współczynnik DFT (FFT):



k =

∑

m=0

2N−1



⋅

exp



−

j 2

2 N



k⋅m

Stąd też, k-ty współczynnik DCT wynosi:

S k =



ℜ



exp



−

j k 

2 N



⋅



k 



Widmo DCT

Dzięki analogii do DFT, transformatę DCT można traktować jak dekompozycję
częstotliwościową sygnału. Współczynniki o dużej energii okazują się być
niskoczęstotliwościowymi składowymi dekompozycji częstotliwościowej, podczas
gdy te o niewielkich wartościach są składowymi wysokoczęstotliwościowymi.

Upakowanie energii w widmie DCT

Energia (wartość) współczynników transformaty jest zlokalizowana w dolnych
częstotliwościach widma.

Podobieństwo DCT do KLT – dekorelacja sygnału

Podstawowym zadaniem transformaty jest usunięcie nadmiarowości
przestrzenno-czasowej pomiędzy sąsiednimi próbkami sygnału, co obniża jego
entropię i pozwala kodować współczynniki transformaty niezależnie.

Porównajmy dwa obrazy: nieskorelowany (a) oraz wysoce skorelowany (b).

Na kolejnych rysunkach przedstawiono histogramy obu obrazów:

Oraz ich znormalizowane funkcje autokorelacji:

Porównajmy następnie funkcje autokorelacji tych samych obrazów z funkcjami
autokorelacji ich widm DCT:

Widać wyraźny spadek amplitudy autokorelacji na całej powierzchni obrazów po
zastosowaniu DCT, co świadczy o dobrych własnościach dekorelacyjnych DCT.

Zależność pomiędzy DCT a KLT

Rozważmy sygnał generowany według formuły:

sk 1=⋅s k z k 

gdzie: ρ = (0, 1); s(k) – k-ta próbka sygnału, z(k) – próbka szumu.
Porównajmy macierz wektorów własnych macierzy kowariancji sygnału s (lewa)
oraz macierz przekształcenia DCT (prawa):

Podobieństwo pomiędzy oboma przekształceniami jest tym większe, im
współczynnik korelacji ρ jest bliższy jedności. Tym samym, DCT osiąga
optymalne własności dekorelacyjne (upakowanie energii, obniżenie entropii) dla
sygnałów wysoce skorelowanych.

Podsumowanie DCT



–

Transformata o własnościach dekorelacyjnych zbliżonych do KLT, a więc prawie
optymalna.

–

DCT dokonuje analizy częstotliwościowej w sposób zbliżony do DFT, jednak
wymaga znacznie mniejszych zasobów systemowych – współczynniki DCT są
wyłącznie rzeczywiste.

–

DCT może być liczona w oparciu o algorytmy FFT.

–

Dla N próbek sygnału DCT produkuje N próbek jego widma, które nie wykazuje
symetrii cechującej DFT sygnałów rzeczywistych.

–

DCT tłumi wysokie harmoniczne powstające na krawędziach obrazu – silne
upakowanie energii i brak artefaktów (efekt Gibbsa).



–

DCT stosuje się zwykle do makrobloków 8x8 lub 16x16 px, co nie usuwa
korelacji pomiędzy blokami.

Porównanie widm DFT i DCT ('cow.wav') pod kątem symetrii

Widmo DFT

Widmo DCT

Powstawanie artefaktów na obrazach – nieciągłość transformat

Podział obrazu na bloki powoduje zerwanie ciągłości funkcji bazowych i powstanie
efektów krawędziowych widocznych zwłaszcza na względnie płaskich obszarach
obrazu (efekt maskowania wizualnego).

Nieciągłość transformat na brzegach bloków

Powstawanie artefaktów na obrazach – nieciągłości sygnału

Analiza sygnału przy pomocy funkcji ciągłych powoduje powstanie silnych
oscylacji (wysokie harmoniczne) w punktach nieciągłości sygnału (np. krawędzie
obiektów), co jest dodatkowo uwypuklone przez obcięcie wysokich harmonicznych
podczas kwantyzacji (efekt maskowania wizualnego).

5 0

1 0 0

1 5 0

-0 . 5

0 . 5

1 . 5

Kodowanie makrobloków

Zastosowanie DCT – kodowanie JPEG

Cechy formatu JPEG (nie mylić z JPEG 2000 (kompresja falkowa)):

–

pierwszy ogólnoświatowy standard kompresji obrazów cyfrowych,

–

typowe poziomy kompresji: od 10:1 do 50:1,

–

kompresja stratna lub bezstratna:

–

sekwencyjna,

–

progresywna (sukcesywne wyostrzanie obrazu – przesyłanie najpierw
składowych niskich i sukcesywne dosyłanie wysokich (Internet)),

–

hierarchiczna (wielorozdzielcza),

–

bezstratna.

JPEG – ogólny schemat kodowania

1 etap kodowania JPEG – przygotowanie obrazu

–

Przygotowanie obrazu – stratny,

–

separacja kolorów (RGB → YCbCr (YUV)),

–

podpróbkowanie chrominancji (4:2:0),

–

podział obrazu na bloki 8x8 px przetwarzane dalej niezależnie.

Różnice w postrzeganiu luminancji i chrominancji

2 etap kodowania JPEG – analiza

–

Analiza częstotliwościowa DCT – bezstratny,

–

współczynnik S(0,0) – składowa DC (średnie natężenie sygnału w całym
bloku),

–

współczynnik S(7,7) – składowa o najwyższej częstotliwości,

3 etap kodowania JPEG – progowanie i kwantyzacja

–

Progowanie i kwantyzacja – stratny,

–

progowanie DCT – usuwanie wsp. o wartościach poniżej ustalonego progu,

–

dzielenie wartości współczynników DCT przez wartości macierzy kwantyzera
t(u,v), mnożenie przez współczynnik jakości Q i zaokrąglanie
całkowitoliczbowe,

–

wyższe wartości t oznaczają większą kompresję, ale gorszą jakość (utrata
składowych DCT),

–

wyższe wartości t stosuje się zwykle dla składowych wysokiej częstotliwości

–

wyższe wartości Q oznaczają lepszą jakość, ale gorszą kompresję,

Original block

Transformed block

139 144 149 153 155 155 155 155

235.

-1.0 -12.1 -5.2 2.1 -1.7 -2.7 1.3

144 151 153 156 159 156 156 156

-22.

-17.5 -6.2 -3.2 -2.9 -0.1 0.4 -1.2

150 155 160 163 158 156 156 156

-10.

-9.3 -1.6 1.5 0.2 -0.9 -0.6 -0.1

159 161 162 160 160 159 159 159

-7.1 -1.9 0.2 1.5 0.9 -0.1 0.0 0.3

159 160 161 162 162 155 155 155

-0.6 -0.8 1.5 1.6 -0.1 -0.7 0.6 1.3

161 161 161 161 160 157 157 157

1.8 -0.2 1.6 -0.3 -0.8 1.5 1.0 -1.0

162 162 161 163 162 157 157 157

-1.3 -0.4 -0.3 -1.5 -0.5 1.7 1.1 -0.8

162 162 161 161 163 158 158 158

-2.6 1.6 -3.8 -1.8 1.9 1.2 -0.6 -0.4

Quantization matrix

Quantized coefficients

51 61

-1

60 55

-2

-1

69 56

-1

80 62

-1

68 109 103 77

81 104 113 92

87 103 121 120 101

98 112 100 103 99

Dequantized coefficients

Decompressed block

240

-10

144 146 149 152 154 156 156 156

-24 -12

148 150 152 154 156 156 156 156

-14 -13

155 156 157 158 158 157 156 156

160 161 161 162 161 159 157 155

163 163 164 163 162 160 158 156

163 164 164 164 162 160 158 157

160 161 162 162 162 161 159 158

158 159 161 161 162 161 159 158

Strefowe próbkowanie vs. strefowe kodowanie transformaty

Odrzucamy składowe o najmniejszej spodziewanej energii. Kształt i wielkość stref
próbkowania może się zmieniać dynamicznie podczas kodowania.
Lepsze efekty daje strefowe kodowanie transformaty, gdzie na składowe niskie
przeznacza się 4-8 bitów, zaś na składowe wysokie 0-3 bitów.

Tablice kwantyzerów

Jeszcze lepsze efekty daje użycie wielu tablic kwantyzerów, dostosowanych do
dynamiki sygnału w danym bloku (wartość wariancji), co wymaga jednak
kodowania dwuprzebiegowego (zebranie statystyk i podział bloków na klasy +
właściwe kodowanie z użyciem tablic kwantyzerów właściwych dla danej klasy).

Luminance

Chrominance

16 11 10 16 24 40 51 61

17 18 24 47 99 99 99 99

12 12 14 19 26 58 60 55

18 21 26 66 99 99 99 99

14 13 16 24 40 57 69 56

24 26 56 99 99 99 99 99

14 17 22 29 51 87 80 62

47 66 99 99 99 99 99 99

18 22 37 56 68 109 103 77

99 99 99 99 99 99 99 99

24 35 55 64 81 104 113 92

99 99 99 99 99 99 99 99

49 64 78 87 103 121 120 101

99 99 99 99 99 99 99 99

72 92 95 98 112 100 103 99

99 99 99 99 99 99 99 99

Klasy obrazów

ORIGINAL IMAGE

TRANSFORMED IMAGE

FLAT

40.0

0.0

IMPULSE

42.5

1.4

-2.5

-3.2

1.4

0.7

-1.4

-1.8

-2.5

-1.4

2.5

3.3

-3.2

-1.8

3.3

4.3

EDGE (vertical)

60.0

-18.4

0.0

7.7

0.0

EDGE (horizontal)

60.0

0.0

-18.4

0.0

7.7

0.0

4 etap kodowania JPEG – kodowanie widma

–

kolejkowanie tablicy współczynników (zig-zak)

–

kodowanie długości serii (RLE) – bezstratny

–

kodowanie Huffmana – bezstratny

Kodowanie odbywa się z użyciem 'drzewa kodowego':