1. Co to jest system multimedialny - podać przykłady:
System multimedialny  system zdolny do przetwarzania obok statycznych mediów dyskretnych co najmniej jednego typu dynamicznych mediów
ciągłych. Elementy systemu multimedialnego: z
ródła (np. kamera, mikrofon) -> kodowanie -> nośniki danych (CD, DVD, HDD) -> dekodowanie ->
urządzenia końcowe (słuchawki, ekran, głośniki). Przykłady: telewizja analogowa, telefony komórkowe, laptopy, odtwarzacz DVD.
2. Proszę omówić najważniejsze etapy rozwoju multimediów:
Pierwszy znaczący rodzaj mediów: prasa (tekst, grafika, fotografie). Przełom XIX/XX wieku: powstanie radia (1895 Marconi, 1919 pierwsza
rozgłośnia). Początek XX wieku: film (1895  bracia Lumiere). Telewizja: 1935 rozgłośnie eksperymentalne w Niemczech i Wielkiej Brytanii, 1941
komercyjna rozgłośnia w USA (CBS), 1954 telewizja kolorowa. Multimedia na komputerach (wersja skrócona): 1945-Vannevar Bush-Memex: idea
urządzenia do gromadzenia, organizacji i kojarzenia (linki) informacji rożnego rodzaju, 1960-1968  Douglas Engelbart rozwija NLS w SRI
(zintegrowane środowisko do wspołpracy z komputerem: mysz, system okien, pomoc kontekstowa, edytory tekstu, poczta elektroniczna, linkowanie
hypertekstowe), 1989 Tim Barnes-Lee: propozycja protokołu http i języka html  powstanie WWW. Rok poz
niej  pierwszy browser, 1991  standard
MPEG-1 (w tym MP3), 1992  standard JPEG, 1993  NCSA Mosaic  pierwszy browser graficzny, 1994  Jim Clark & Mark Andreessen: Netscape,
1995  Java (język dla aplikacji niezależnych od platformy), 1996  video na DVD, 2000  zawartość WWW szacowana na 1 mld stron.
3. Omówić przykładowe narzędzia do tworzenia multimediów
Narzędzia do produkcji/edycji dz
więku:Cubase  produkt firmy Steinberg, sekwencer MIDI, technologia VST i ASIO, pozwala łączyć ście\
ki MIDI i
audio; funkcje edycyjne, filtry, miksowanie, efekty, cena: Ź 150 (Cubase SE 3), Ź 880 (Cubase 4). Cakewalk (Sonar - Ź 590/350), Logic Pro (Apple -
$500)  inne konkurencyjne produkty. Adobe Audition 3 (Cool Edit Pro)  system cyfrowej rejestracji i edycji dz
więku; emulacja profesjonalnego
studia (obsługa do 128 śladów, uzyskiwanie złożonych miksów, wyrafinowane efekty i filtry);cena ~ $ 350; można ściągnąć wersję próbną (~30 MB). 2
Narzędzia graficzne: Adobe Illustrator CS3  potężne narzędzie graficzne, pozwala na produkcję i edycję grafiki wektorowej; cena ~$600 Adobe
Photoshop  standardowe narzędzie manipulacji grafiką i fotografiami: oddzielne warstwy (obraz, grafika, tekst  obrabiane oddzielnie); wyrafinowane
filtry; cena ~$1000 (wersja CS3 Extended), wersja próbna (140 MB).3 Narzędzia video: Adobe Premiere  edytor video (pozwala na jednoczesną
edycje 99 ścieżek audio i video); duża biblioteka przejść, filtrów, efektów specjalnych; cena ~ $800 (wersja CS3), wersja próbna (~170 MB). Ulead
Video Studio  prosty program edycji video, cena ~$100. 4. Narzędzia integracji multimediów: Macromedia Flash  interakcyjne filmy.
Macromedia Director  pełne interakcyjne prezentacje, język skryptowy Lingo.
4. Percepcja dz
więku przez człowieka
Człowiek może słyszeć dz
więki z zakresu częstotliwości: 16 Hz - 20 kHz (długości fal 21.3 m - 1.7 cm).
5. Prezentacja cyfrowa dz
więku
Digitalizacja  zamiana na dyskretny ciąg liczb. Dyskretna siatka w kierunku czasowym  próbkowanie, w kierunku sygnału  kwantyzacja. Jakość digi-
talizacji zależy od ilości poziomów kwantyzacji i częstości próbkowania. Kwantyzacja  zależy od ilości bitów przeznaczonych na reprezentacją numeru
progu kwantyzacji
_ Kwantyzacja N-bitowa  2N poziomów
_ 8 bitów  256 poziomów kwantyzacji
_ 16 bitów  65536 poziomów kwantyzacji
_ Błąd kwantyzacji = wartość sygnału  wartość najbliższego
poziomu kwantyzacji Ł�Ł�połowa odległości między poziomami
6. Twierdzenie Nyquista.
Aby móc dokładnie odtworzyć ciągły sygnał o ograniczonym paśmie z jego próbek, należy zastosować częstość próbkowania równą co najmniej
podwojonej najwyższej częstości sygnału.
Wnioski:
 aby przenieść całe pasmo akustyczne należy wziąć fp >= 40 kHz (stosuje się 44.1 kHz)
 aby dobrze przenieść mowę (100 Hz � 3.5 kHz) należy wziąć fp >= 7 kHz (stosuje się 8 kHz)
 aby uniknąć aliasingu należy zastosować filtr dolnoprzepustowy z częstością obcięcia fo = fp/2
7. Co to jest aliasing? Jak możemy uniknąć jego skutków?
Aliasing  przekłamania w odtworzeniu częstości z próbek - gdy częstość próbkowania jest za mała
f alias = f samp - f true, dla f true < f samp < 2f true
Ogólnie: obserwowana częstość  najniższa możliwa częstość sinusoidy, która ma te same próbki co dana sinusoida wejściowa
fsamp = 8 kHz
Jak możemy uniknąć jego skutków?
 aby uniknąć aliasingu należy zastosować filtr dolnoprzepustowy z częstością obcięcia fo = fp/2 ??
8. Formaty plików dz
więkowych
*.wav, *.aiff, *.au  pliki kodowane PCM dla Windows, Mac, Unix
*.mp3, *.ra, *.wma, *.ogg  formaty strumieniowe
Format WAVE
-Opracowany przez Microsoft format zapisu audio  szczególny przypadek specyfikacji RIFF (pochodnej EA IFF)
-Ogólna struktura pliku  nagłówek specyfikujący typ i rozmiar pliku, szereg różnego rodzaju porcji (chunks) opisujących struktur_ i wartości danych
- W WAVE  obowiązkowe porcje typu  fmt  i  data ; segment formatu musi poprzedzać dane.
- Wszystkie liczby specyfikowane w porządku od najmłodszego do najstarszego bytu (little endian).
- Formaty AIFF i AU  podobne
- Dane próbek muszą się mieścić w parzystej liczbie bajtów
- Próbki 8-bitowe s_ składowane jako liczby bez znaku: 0 .. 255
- Próbki 16-bitowe s_ składowane jako liczby ze znakiem: -32768 .. 32767
9. Mechanizm widzenia barw
Oko: Pręciki  widzenie zmierzchowe
Czopki  widzenie barwne, w pełnym świetle; Trzy typy czopków, każdy z typów wrażliwy na
różne fragmenty spektrum.
Czułości spektralne czopków i czułość jasnościowa oka
Maksima dla: 440 nm (niebieskie), 545 nm (zielone), 580 nm (czerwone); 550 nm (jasność)
Charakterystyki sygnału kolorowego:
Kolor  wyspecyfikowany przez trójkę liczb (R,G,B). Tak więc kolory określone są w 3-wymiarowej przestrzeni wektorowej. Różne widma mogą dać
te same (R,G,B)  te same kolory. Mieszanina kolorów  > nowy kolor
10. Diagram chromatyczności
można dobrać tak trzy barwy podstawowe, by każdy kolor można było uzyska_ przez ich dodatnie kombinacje ale nie będą to czyste kolory
- 1931, CIE, barwy podstawowe X,Y,Z
Współrzędne X, Y, Z:
Płaszczyzna X+Y+Z=1
Własności diagramu:
_ Krawędzie diagramu odpowiadają  czystym kolorom widmowym
_ Biel (temperatura 6447 K)  punkt W
_ Dla każdych dwóch kolorów ich kombinacja daje punkt leżący na linii je łączącej
_ Dla każdych trzech kolorów ich wszystkie mieszanki leżą we wnętrzu trójkąta rozpiętego na nich
11. Addytywny i subtraktywny model kolorów
Addytywny model RGB
_ Wyświetlacz ma 3 rodzaje fosforu, które różnie świecą przy pobudzeniu
_ Kolor uzyskuje się przez odpowiednie pobudzenie każdego rodzaju
Subtraktywny model CMY
_ Używany dla urządzeń drukujących (barwa  pochłanianie światła w pigmencie)
_ Barwy podstawowe  cyjan (-C), magenta (-M), żółty (-Y).
_ Kolor  usunięcie z białego
RGB CMY
Transformacje pomiędzy modelami:
Model CMYK
" Równe ilości C, M i Y  powinny dać czerń
" W praktyce  nie dają (zamiast tego  brudny brąz)
" Taniej i łatwiej używać CMY oraz czerni (K) w sposób jak niżej
12. Modele kolorów dla video
Model YUV
- Używany do reprezentacji kolorów w video PAL
- Y  luminancja  podstawowa zmienna CIE (odpowiadająca czułości
oka na jasność Y = 0.299 R + 0.587 G + 0.114 B
- Chrominancja  różnica między kolorem a światłem białym o tej samej
jasności. Reprezentowana przez składowe U, V.
- Definicja pierwotna:
U = B  Y
V = R  Y
- Aktualnie używa się wartości przeskalowanych (aby sygnał composite video był w wygodnym zakresie):
U = 0.492 (B  Y)
V = 0.877 (R  Y)
Zalety modelu:
- Kompatybilne z telewizją czarno-białą (gdy tylko Y)
- Różna czułość oka na luminancje i chrominancje  ważne dla alokacji pasma w transmisji sygnału analogowego, czy częstości próbkowania sygnału
cyfrowego.
Model YCbCr
- Blisko powiązany z YUV
- Składowe chrominancji przeskalowane i przesunięte:
Cb = (B  Y)/1.772 + 0.5
Cr = (R  Y)/1.402 + 0.5
- Tak zdefiniowane współczynniki Y, Cb, Cr mają wartości
pomiędzy 0 a 1
- YCbCr używane w kompresji JPEG i MPEG
Model YIQ
- Używany do reprezentacji kolorów w systemie NTSC
- Stara się lepiej niż YUV dopasować do zdolności percepcyjnych oka ludzkiego
- I, Q  przeskalowane i obrócone U, V; I  oś pomarańczowo-niebieska; Q  purpurowo-zielona
I = 0.877 (R  Y) cos 33�  0.492 (B  Y) sin 33�
Q = 0.877 (R  Y) sin 33 � + 0.492 (B  Y) cos 33�
- Oko najbardziej czułe na Y, następnie I, potem Q.
Podsumowanie
- Kolorowe obrazy są kodowane przez trójki liczb określających barwę
- RGB jest addytywnym modelem używanym przez urządzenia emitujące światło, CMY  subtraktywnym modelem używanym dla drukarek
- YUV i YIQ są najczęściej używanymi modelami koloru dla video
- Modele YUV, YIQ wykorzystują własności oka ludzkiego do przypisania wagi informacji różnego typu
- Modele RGB, CMK, YUV, YIQ są zorientowane na sprzęt. Oprócz nich są możliwe inne modele (np. HSB)
13. Elementy grafiki rastrowej (piksel, rozdzielczość obrazu, aspect ratio, głębokość
bitowa koloru)
Grafika rastrowa - reprezentacja obrazu za pomocą pionowo-poziomej siatki odpowiednio kolorowanych pikseli na monitorze komputera,
drukarce lub innym urządzeniu wyjściowym.
Elementy:
- Piksel  najmniejszy element obrazu cyfrowego
- Rozdzielczość obrazu  ilość pikseli
- Aspect ratio  parametr określający geometrię monitora  stosunek ilości kolumn i wierszy. Zwykle równy 4:3. Nowe systemy TV wprowadzają
aspect ratio 16:9
- Głębokość bitowa koloru - liczba bitów przeznaczona w danym trybie RGB do zapisu wartości barwy. Im większa głębokość bitowa, tym więcej
bitów informacji potrzeba do opisania pojedynczego piksela, stąd też większa objętość pliku.
14. Porównaj 8- i 24- bitową reprezentację kolorowego obrazu
8-bitowe: 24-bitowe
-Każdy piksel opisany przez 1 bajt -każdy piksel opisany przez 3 bajty (np. RGB)
-konieczność używania LUT ( Look-Up Table  paleta) -powala na użycia 256^3 kolorów
-możliwe 256 kolorów -obraz 640x480 zajmuje 900kB
-obraz 640x480 zajmuje 300kB (+rozmiar LUT)
-możliwe półtonowanie
15. Podstawowe formaty graficzne
GIF (GIF87a, GIF89a)
" Rozwinięty przez CompuServe i UNISYS
" Pozwala na prezentację 8-bitowego koloru
" Używa kompresji bezstratnej (LZW)
" Pozwala na wyświetlanie z przeplotem
" GIF89a pozwala na zapis animacji
JPEG
" Rozwinięty przez Joint Photografic Expert Group
" Wykorzystuje ograniczenia wzroku ludzkiego dla uzyskania
" lepszej kompresji; kompresja stratna
" Pozwala na odwzorowanie koloru 24-bitowego
" Bardzo dobrze nadaje się do zapisu zdjęć i naturalnych obrazów
" Użytkownik określa jakość/stopień kompresji
TIFF (Tagged Image File Format)
" Opracowany przez Aldus Corp. (1986) póz
niej wspierany przez
" Microsoft, pomyślany jako mechanizm wymiany danych
" rastrowych w sposób niezależny od platformy
" Pozwala na zapis wielu różnych typów obrazów
" Bez kompresji lub kompresja bezstratna
Postscript/PDF
" Produkt Adobe, specjalny język opisu strony
" Pozwala na włączanie tekstu, grafiki wektorowej, bitmap
" Nie ma wbudowanej kompresji, często bardzo duże pliki
PNG
" Powstał jako reakcja na wprowadzenie opłat za używanie GIF
" Może prezentować wszystkie typy grafiki rastrowej
" Trochę lepsza kompresja niż GIF (kompresja bezstratna)
" 2-wymiarowy przeplot
" Brak możliwości animacji
Formaty zależne od platformy:
" BMP Windows/OS
" PAINT, PICT Mac
" XBM X-Windows
16. Typy sygnałów video
Component video  każda składowa podstawowa jest przesyłana jako oddzielny sygnał video
" Składowymi podstawowymi mogą być RGB lub pochodne (YUV)
" Zaleta  optymalne odwzorowanie sygnału
 " Wymaga więcej pasma i dobrej synchronizacji składowych
Composite Video  składowe luminancji i chrominancji mieszane w jeden sygnał
" Mniejsze wymagania co do pasma
" Nie ma kłopotów z synchronizacją
" Nieunikniona interferencja między sygnałami
S Video (np. w S VHS)  rozwiązanie kompromisowe.
Używa dwóch linii  jeden dla luminancji, drugi  chrominancji
17. Co to jest przeplot? Dlaczego był/jest stosowany?
Przeplot  technika wyświetlania obrazu, polegająca na naprzemiennym wyświetlaniu parzystych i nieparzystych linii obrazu, powszechnie stosowana
w telewizji. Stosuje się ją w celu zmniejszenia pasma przenoszenia przesyłanego sygnału, bądz
w celu zwiększenia pozornej rozdzielczości
wyświetlanego obrazu. W telewizji stosowana głównie do zmniejszenia efektu migotania ekranu (dwukrotnie częstsze wyświetlenie połowy linii,
zamiast rzadszego wyświetlania pełnej klatki).
Przeplot stosują wszystkie tradycyjne standardy nadawania obrazu telewizyjnego (PAL, SECAM, NTSC), oraz jest używany w niektórych trybach
graficznych w niektórych monitorach. Stosowanie przeplotu zostało zapoczątkowane w latach 20. XX wieku, kiedy to pojawiły się pierwsze odbiorniki
telewizyjne. Ówczesna technika wymusiła wprowadzanie przeplotu, gdyż wyświetlanie obrazu z częstotliwością stosowaną w kinach (20 obrazów na
sekundę) wywoływało duże migotanie obrazu. Postanowiono w celu zmniejszenia efektu migotania fragmentów obrazu oraz w celu uproszczenia
elementów synchronizacji nadawać obraz z częstotliwością napięcia w sieci energetycznej (w Europie 50 Hz). W tamtych czasach potrafiono już
analizować dokładnie obraz, lecz nadawanie dużej liczby linii powodowało zwiększenie częstotliwości odchylania poziomego oraz pasma sygnału
obrazu. Aby temu zaradzić postanowiono, że zamiast wyświetlać całą ramkę, w tym samym czasie można wyświetlić dwa półobrazy.
Ze względu na coraz większe i jaśniej świecące kineskopy problem migotania powrócił, rozwiązano go poprzez zwiększenie częstotliwości wyświetlania
do 100 Hz. W tych telewizorach odbierany sygnał obrazu jest zapamiętywany i wyświetlany z dwukrotnie większą częstotliwością i każdy dwa razy.
18. Standardy video analogowego
NTSC
" 525 linii skanowania/ramkę , 30 ramek/sec (a właściwie 29.97 fps, 33.37 msek/ramkę )
" Wyświetlany z przeplotem, 2 pola/ramkę , 262.5 linii/pole
" 20 linii na początku każdego pola zarezerwowane na dane kontrolne (vertical retrace); część pikseli pomiędzy liniami skanowania
" Maks. 485 linii widzialnych
" Dyski laserowe i S-VHS mają rozdzielczość ~ 420 linii
" Zwykła telewizja  rozdzielczość ~ 320 linii
" Reprezentacja koloru  model YIQ. Przydział pasma: Y 
" 4.2 MHz, I  1.6 MHz, Q  0.6 MHz
" Wyświetlenie pojedynczej linii  63.5 źsek
PAL
" 625 linii skanowania/ramkę , 25 ramek/sec, 40 msek/ramkę )
" Wyświetlany z przeplotem, 2 pola/ramkę , 312.5 linii/pole
" ~25 linii na początku każdego pola zarezerwowane na dane kontrolne
" Maks. 576 linii widzialnych
" Reprezentacja koloru  model YUV. Przydział pasma: Y  5.5 MHz, U, V  1.8 MHz
" Wyświetlenie pojedynczej linii  64 źsek
" Sygnał chromy  zmiana znaku pomiędzy kolejnymi liniami skanowania (stąd nazwa); średniowanie, lepsze wyznaczenie Y
19. Standardy video cyfrowego
" Reprezentowane jako sekwencja obrazów cyfrowych
" Zalety w porównaniu z systemem analogowym:
" Dost p bezpośredni  łatwo edycji nieliniowej
" Nie ma kłopotów z wielokrotnym przegrywaniem
" Brak problemów z sygnałami przejścia linii i obrazu (synchronizacja)
" Prawie wszystkie systemy video cyfrowego to systemy typu component video
" Oko jest bardziej czułe na jasno ni na kolor  stosuje się podpróbkowanie chrominancji
20. Na czym polega próbkowanie chrominancji? Po co się je stosuje?
21. Dlaczego kompresja danych jest niezbędnym elementem systemów multimedialnych?
22. Czym jest kompresja danych? Jakie są jej podstawowe typy?
Definicja kompresji:
" Kompresja  sztuka reprezentowania danych w zwięzłej formie
Dane  znaki w pliku tekstowym, próbki mowy, muzyki, reprezentacje pikseli obrazu itp.
" Kompresja możliwa, bo w danych jest nadmiar informacji (redundancja)
" Jeden z pierwszych przykładów 
alfabet Morse a
Zasada: znaki często występujące  krótkie kody,
znaki rzadsze  długie kody
Kompresja  podanie dwóch algorytmów:
Typy kompresji:
Wyróżnik  relacja między X i X
in out
" Jeżeli wymagamy, by X = X  kompresja bezstratna
in out
- Stosowana tam, gdzie nie można dopuścić do różnicy między danymi a ich rekonstrukcją
- Typowe zastosowanie  tekst, rekordy bazy danych a także obrazy, które podlegaj dalszej obróbce (zdjęcia rentgenowskie, zdjęcia satelitarne itp.)
" Jeżeli dopuszczamy, by X != X  kompresja stratna
in out
- Zwykle pozwala na znacznie wyższy poziom upakowania
- Typowe zastosowania: mowa, dz
więk, obraz, sekwencje video
23. Miary jakości kompresji
" Możliwe kryteria
- Złożoność algorytmu
- Ilość potrzebnej pamięci
- Szybkość działania na komputerze danego typu
- Stopień kompresji
- Podobieństwo danych wyjściowych i ich rekonstrukcji
" Kompresja bezstratna
- Stopie kompresji = rozmiar(X )/rozmiar(X )
in C
- Miara redukcji = (rozmiar(X )  rozmiar(X ))/rozmiar(X ) %
in C in
" Kompresja stratna
- Dodatkowo rozważamy zniekształcenia
- Optymalizujemy stopień kompresji przy danych zniekształceniach (lub zniekształcenia przy zadanym poziomie kompresji)
24. Fazy konstruowania algorytmu kompresji
" Kompresja  usunięcie redundancji z opisu danych. Aby to było możliwe musimy rozumie struktur danych
" Pierwsza faza procesu kompresji to modelowanie  stworzenie zbioru reguł opisujących dane
" Druga faza  kodowanie. Kodujemy zarówno opis modelu jak też opis informacji jak dane różnią się od modelu
25. Entropia i jej znaczenie
Entropia
" Eksperyment  możliwe wyniki: zdarzenia A , ich suma  zdarzenie pewne. Wtedy entropia eksperymentu:
i
" W kompresji  z
ródło generuje symbole (litery) ze zbioru symboli (alfabetu) o rozmiarze m. Wtedy entropia z
ródła:
" Gdy wszystkie elementy ciągu mają identyczny i niezależny rozkład (iid) to formuła na entropii upraszcza się do formuły na entropii 1 rzędu:
" Założenie (iid) ważne  przykład:
1 2 1 2 3 3 3 3 1 2 3 3 3 3 1 2 3 3 1 2
- Gdy patrzymy wyraz po wyrazie: P(1) = P(2) = 0.25; P(3) = 0.5, co daje
H =1.5 minimalna ilość bitów = 20*1.5 = 30.
1
- Gdy patrzymy na ciągi po 2 symbole: P(12) = P(33) = 0.5, co daje
H =1 minimalna ilość bitów = 10 * 1 = 10
2
" Shannon: entropia jest miarą średniej ilości bitów potrzebnych do zakodowania ci gu kolejnych symboli generowanych przez z
ródło
26. Co to jest kodowanie? Jakie wymagania powinien spełniać dobry kod?
" Kodowanie  przyporządkowanie elementom alfabetu ciągów binarnych, tak by zredukować całkowitą ilość bitów potrzebną do reprezentacji
" Średnia ilość bitów na symbol ważna, ale nie najważniejsza  kody muszą być jednoznacznie dekodowalne
Litera Prawdop. Kod 1 Kod 2 Kod 3 Kod 4
a 0,5 0 0 0 0
1
a 0,25 0 1 10 01
2
a 0,125 00 00 110 011
3
a 0,125 11 11 111 0111
4
Średnia długość 1,13 1,25 1,75 1,88
Kody 1 i 2  nie są jednoznacznie dekodowalne.
Kod 3  natychmiastowy, kod 4  prawie natychmiastowy
Natychmiastowo wygodna ale niekonieczna  przykład:
a1 0
a2 01
a3 11
Otrzymujemy ciąg:
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Pierwsze słowo to może by a1 lub a2  aby to rozstrzygnąć musimy odkodować cały ciąg.
27. Co to jest kod prefiksowy. Znaczenie kodów prefiksowych.
Kody prefiksowe:
" Kod w którym żadne słowo kodowe nie jest prefiksem innego  kod prefiksowy. Kod taki jest jednoznacznie dekodowalny
" Jak najprościej sprawdzić czy kod jest kodem prefiksowym  drzewo binarne kodu
Kod prefiksowy  słowa kodowe = tylko wierzchołki zewnętrzne.
Kody prefiksowe najwygodniejsze  czy można się do nich ograniczyć ?
Tw. 1. C  kod o N słowach kodowych o długościach l , l , ..., l . Jeżeli C  jednoznacznie dekodowalny, to zachodzi nierówność :
1 2 N
Tw. 2. Dla każdego zbioru liczb całkowitych l , l , ..., l spełniających nierówność jak w Tw. 1 można znalez
ć kod prefiksowy o długościach słów
1 2 N
wynoszących l , l , ..., l .
1 2 N
Wniosek  wystarczy brać pod uwag tylko kody prefiksowe.
28. Kodowanie Shanona-Fano
Kodowanie entropijne:
Sformułowanie problemu:
" y
ródło S generuje symbole (litery) a z alfabetu A
i
" Zadany jest model probabilistyczny określający prawdopodobieństwa P(ai) i entropię H z
ródła
" Znalez
ć kod prefiksowy minimalizujący redundancję
Historycznie pierwszy taki algorytm  Shannon (Bell Labs), Fano (MIT), 1949
Kodowanie Shannona  Fano:
1. Tworzymy listę liter
2. Sortujemy ją wg. malejących częstości wystąpienia (prawdopodobieństw)
3. Dzielimy listę na dwie podlisty, tak by sumy częstości na obu były jak najbliższe
4. Wszystkim literom na górnej liście przypisujemy 0, na dolnej 1
5. Stosujemy rekursywnie krok 3 i 4 dopóki każdy z symboli stanie się liściem w drzewie
Przykład: Alfabet {a, b, c, d, e} opisany częstościami:
a b c d e
15 7 6 6 5
Kody Shannona-Fano  własności:
" A
atwy do zaprogramowania, dość efektywny algorytm
" Z konstrukcji  kod prefiksowy
" Kod typu  od góry  do dołu (od korzenia do liści).
" Czy jest to kod optymalny (czy dla danego modelu probabilistycznego minimalizuje średnią długość)?
Odpowiedz
 niekoniecznie!!!
29. Kodowanie Huffmana - działanie algorytmu i własności
30. Na czym polega dynamiczne kodowanie Huffmana?
31. Zasada kodowania słownikowego
Chcemy zakodować zdanie angielskie:
A good example of how dictionary based compression works
Słownik: Longman Dictionary of Contemporary English
Kodowanie: wskaz
nik do słowa to x/y, x  nr strony, y  nr słowa na stronie. Wynik:
1/1 489/7 377/19 755/36 548/13 303/7 73/3 223/1 1270/25
Liczba stron w słowniku: 1280  x kodujemy przez 11 bitów
Liczba słów na stronie < 128  y kodujemy przez 7 bitów
Wskaz
nik x/y  18 bitów. Całkowita ilo bitów: 9*18 = 162
Normalne kodowanie ASCII  48 bajtów, czyli 384 bity
Stopie kompresji  2.37 : 1
32. Algorytm LZ77
Algorytm LZ77:
" Słownik  fragment wcześniej zakodowanej części danych
" Przeglądamy dane przez przesuwające się okno o rozmiarze W
" Okno dzieli się na:
- bufor słownikowy  zawiera ostatnio zakodowany fragment ciągu danych
- bufor kodowania  zawiera fragment ciągu, który właśnie mamy kodować
" Praktyczne implementacje  rozmiar bufora słownikowego: 8  16 kB, rozmiar bufora kodowania ~ 100 bajtów
" Zasada działania:
1) Umieszczamy wskaz
nik przeszukiwania na końcu bufora słownikowego
 2) Przesuwamy wskaz
nik w lewo (liczba miejsc  o) aż do napotkania symbolu równego pierwszemu symbolowi w buforze kodowania
3) Sprawdzamy, czy następne symbole w obu buforach nie są sobie równe. Liczba równych sobie symboli  długość dopasowania l
4) Przeglądamy w ten sposób cały bufor słownikowy tak, by zmaksymalizować dopasowanie
5) Optymalne dopasowanie kodujemy jako (o, l, c), gdzie c  kod symbolu w buforze kodowania występujący jako pierwszy niedopasowany
symbol
6) Ostatni element trójki  na wypadek zerowego dopasowania
7) Po wysłaniu kodu (o, l , c) przesuwamy okno o l + 1 w prawo i powtarzamy procedurę
" Długość zapisu kodującego dla kodowania o stałej długości
- niech rozmiar okna = W, rozmiar bufora słownikowego = S, rozmiar alfabetu = A
- wtedy długość zapisu = log2 S + log2 W + log2 A
UWAGA: dopasowanie może przekroczyć rozmiar bufora słownikowego
Algorytm LZ77  kodowanie:
Kodujemy ciąg:
. k a b r a k a d a b r a r r a r r a d .
Zakładamy, e podciąg k a b r a k a jest już zakodowany.
Parametry okna: W=13, S=7
Kolejne kroki kodowania:
Algorytm LZ77  dekodowanie:
" Startujemy z odkodowanego podciągu k a b r a k a
" Odkodowujemy (0,0,C(d))  czyli C(d)
" Odkodowujemy (7,4,C(r))
" Odkodowanie (3,5,C(d))
Algorytm LZ77  własności:
" Prosta metoda adaptacyjna, nie wymaga wcześniejszej wiedzy o charakterze z
ródła
" Kodowanie może być czasochłonne (dużo porównań);
dekodowanie proste i szybkie
" Nieduże wymagania dotyczące pamięci
" Asymptotycznie  wyniki najlepsze jakie można uzyskać przy pełnej częstości pojawiania się znaków i korelacji między nimi
" Można zastosować różne modyfikacje algorytmu poprawiające jego efektywność
33. Algorytm LZW
Algorytm LZW:
" Zaproponowany w 1984 przez Terry ego Welcha
" Główna modyfikacja  koder nie wysyła kodu pierwszego niedopasowanego znaku (a tylko indeks słownika)
" Aby to było możliwe  słownik na starcie zawiera wszystkie litery wyjściowego alfabetu
" Procedura kodowania:
" Próbujemy dopasować kawałek łańcucha wejściowego
" Niech s  maksymalny podłańcuch który ma wzorzec w słowniku
" (indeks j) o długo ci d, c  pierwszy niedopasowany znak
" Na wyj cie: j (indeks wzorca zgodnego z s)
" Do słownika dodajemy s+c
" Przesuwamy znacznik pozycji o d
" Przykład: kodujemy ciąg a b c a b b c a b b a
a w D, ab  nie, ab do D4, wyj cie 1
b w D, bc  nie, bc do D5, wyj cie 2
c w D, ca  nie, ca do D6, wyj cie 3
ab w D, abb  nie, abb do D7, wyj cie 4
bc w D, bca  nie, bca do D8, wyj cie 5
abb w D, abba  nie, abba do D9, wyj cie 7
a w D, wyj cie 1
Wynik: 1234571
Algorytm LZW  dekodowanie:
Odkodujemy ci g 1 2 3 4 5 7 1 ze słownikiem początkowym {a, b, c}
1 ==> wyj cie a ==> awD
2 ==> wyj cie b ==> ab nie w D, ab do D4
3 ==> wyj cie c ==> bc nie w D, bc do D5
4 ==> wyj cie ab ==> ca nie w D, ca do D6
5 ==> wyj cie bc ==> abb nie w D, abb do D7
7 ==> wyj cie abb ==> bca nie w D, bca do D8
1 ==> wyj cie a ==> abba nie w D, abba do D9
" Niekiedy w odkodowywaniu LZW problem  konieczno
u ycia wzorca, który jest w trakcie formowania.
" Przykład: zakodowa ci g a b a b a b a b
" Standardowe post powanie daje kod: 1 2 3 5 2
" Odkodowanie:
1 ==> wyjście a ==> a w D
2 ==> wyjście b ==> ab nie w D, ab do D3
3 ==> wyjście ab ==> ba nie w D, ba do D4
5 ==> ale pozycja 5 w słowniku jeszcze niegotowa !!!
Wiemy, e D5 musi si zaczyna od ab  abx.
Czyli D5 to prefiks ababx którego jeszcze nie ma w D  czyli aba
5 ==> wyjście aba ==> aba do D5
2 ==> wyjście b ==> abab do D6
Zastosowanie LZW:
" Polecenie compress
ć% Rozmiar słownika (i długość kodów indeksów) zmienia si ę dynamicznie
ć% Zaczynamy od słownika o rozmiarze 512 (słowo kodowe 9- bitowe). Gdy słownik się zapełnia, podwajamy rozmiar
ć% Rozmiar maksymalny = 2b, gdzie b  pomiędzy 9 a 16 (default równy 16).
ć% Gdy rozmiar maksymalny osiągnięty  słownik się nie zmienia
ć% Algorytm analizuje stopień kompresji; gdy zbyt niski, słownik jest czyszczony i budowany od nowa
" Format GIF
ć% Podstawa  b = ilość pikseli na bit.
ć% Zaczynamy od słownika o rozmiarze 2b+1. Po wypełnieniu  zwiększamy o czynnik 2.
ć% Maksymalny rozmiar  4096. Po jego osiągnięciu  słownik jest zamrożony.
" Kompresja danych wysyłanych przez modem (V.42 bis)
ć% Może pracować w trybie przez
roczystym i trybie kompresji
ć% Tryb kompresji  algorytm LZW ze słownikiem o zmiennej długości
ć% Standard pozwala na okresowe czyszczenie słownika z napisów, które pojawiły się w przeszłości, lecz nie były używane ostatnio
34. Algorytm LZ78
Algorytm LZ78:
" Wada algorytmu LZ77  skończony czas, w jakim wzorzec jest pamiętany  wzorce odległe o bardziej niż szerokość bufora słownikowego nie
 czują swej obecności
" LZ78

zastąpienie bufora słownikowego słownikiem tworzonym explicite  dynamicznie w trakcie kodowania i dekodowania
" Słowniki  tabela zawierająca indeks i odpowiadający mu wzorzec. Na początku kodowania (dekodowania)  słownik pusty. Potem  ostatnio
dopasowany wzorze + niedopasowany znak
" Kodowanie  para (i,c), gdzie i  indeks, c  kod pierwszego niedopasowanego znaku
LZ78  przykład:
Ciąg do zakodowania: aa_bbb_cccc_ddddd_e
Kodowanie: Słownik:
(0,a)(1,_)(0,b)(3,b)(0,_)(0,c)
(6,c)(6,_)(0,d)(9,d)(10,_)
(0,e)
Do słownika wstawiane s ą
coraz dłuższe wzorce. Jeżeli
jakaś fraza się powtarza, to
wkrótce znajdzie się w
całości w słowniku.
Odkodowanie  bardzo proste.
Własności algorytmu LZ78:
" Szybsze kodowanie niż dla LZ77 (znacznie mniej porówna stringów)
" A
atwe dekodowanie (choć wolniejsze niż dla LZ77  konieczność odbudowy słownika)
" Wzorce są stale dodawane do słownika (1 wzorzec na jeden proces kodowania) i nie zapominane  niebezpieczeństwo przepełnienia pamięci
" Jest punktem wyjścia dla algorytmów pochodnych  najbardziej znany algorytm LZW.
35. Zastosowania algorytmów kodowania słownikowego
Takie metody dobrze kompresują dane, w których podciągi powtarzają się, np. w przypadku tekstów naturalnych (teksty książek, czasopism itp.) wiele
słów a nawet całych fraz występuje wielokrotnie.
36. Na czym polegają algorytmy bezstratnego kodowania predykcyjnego (zasada ogólna, prosty przykład)
Zasada kodowanie predykcyjnego:
" Im bardziej zróżnicowane prawdopodobieństwa wystąpienia symboli tym większą kompresję można uzyskać
" Przykład 1: alfabet dwuznakowy, prawdopodobieństwa p, q; p + q = 1.
Entropia H = -plog p  (1-p)log (1-p)
2 2
" Przykład 2  alfabet ośmioznakowy:
Im bardziej zróżnicowane prawdopodobieństwa, tym mniejsza entropia, czyli mniejsza średnia bitowa.
" Jak osiągnąć tak sytuację ?
ć% Użyć odwracalnego przekształcenia transformującego ciąg wejściowy na ciąg o zróżnicowanych prawdopodobieństwach
ć% Używać innego rozkładu prawdopodobieństwa dla każdego symbolu, by zwiększyć prawdopodobieństwo wystąpienia kodowanego
symbolu (kontekst)
ć% Zadbać , by dekoder bez żadnej dodatkowej informacji  wiedział jakiej transformacji lub jakiego rozkładu użyto przekształcenie
odwrotne lub rozkład będzie do odtworzenia bez żadnych dodatkowych informacji (np. na podstawie znajomości wcześniej
zakodowanych elementów).
" Tak działające algorytmy = algorytmy kodowania predykcyjnego.
Kodowanie przedykcyjne  przykład:
" Przykład  kodowanie różnic:
ć% Predykcja : xn = xn-1
ć% Transformacja: xn en = xn  xn
ć% Rozkład różnic bardziej zróżnicowany  kompresja
Przykład: plik 2_ch, fragment (8 x 16 pikseli)
Rozkład oryginalnych zmiennych:
Rozkład różnic
37. Miary zniekształceń w kompresji stratnej
" Błąd średniokwadratowy:
" Stosunek sygnału do szumu SNR:
" Stosunek sygnału do szumu SNR wyrażony w decybelach:
" Poziom zniekształceń odniesiony do warto ci szczytowej sygnału:
" Średnia miara błędu bezwzględnego (do oceny algorytmów kompresji obrazów:
" Maksymalna wielkość błędu:
38. Co to jest kwantyzacja? Jakie znasz odmiany kwantyzacji?
Kwantyzacja  reprezentacja dużego (w szczególności nieskończonego) zbioru wartoci przez mniejszy, skonńczony zbiór wartoci. Opiera się na parze
odwzorowań: koder i dekoder. Koder dzieli caly zakres zmienności sygnału na przedziały i przypisuje im jednoznaczne słowa kodowe. Dekoder zaś
każdemu słowu kodowemu przypisuje rekonstruowaną wartość.
Kwantyzacja skalarna  każda wartość w ciągu jest kwantyzowana osobno (kodowanie pojedynczych próbek, liczb)
Kwantyzacja wektorowa  polega na kodowaniu sekwencji  zestawów liczb (wektorów).
Kwantyzacja adaptacyjna w przód - dane dzielone na bloki, bloki analizowane i kwantyzowane osobno, przesyłamy dodatkowe informacje o rodzaju
kwantyzacji.
Kwantyzacja adaptacyjna wstecz  dostosowujemy kwantyzacj�e w oparciu o wyniki kwantyzatora (zmieniamy ilość i wielkość przedziałów
kwantyzacji  kwantyzator Jayanta).
Kwantyzacja nierównomierna  opiera się na pełnej optymalizacji, która powinna zapewni lepsze pokrycie obszarów o wi ększym prawdopodobieństwie
. Jedyne kryterium doboru granic decyzyjnych i poziomów reprezentacji to minimalizacja bł ędu średniokwadratowego
Kwantyzacja z kompanderem - Idea: zamiast zmniejsza długo kroku  zwi ększamy rozmiar przedziału, w którym prawd. wejścia jest duże.
39. Na czym polega problem niedopasownia w kwantyzacji skalarnej. Jak można
sobie z nim radzić?
Niedopasowanie:
" Wyznaczenie " zależy od rozkładu (jego typu i parametrów)
" Użycie kwantyzatora zaprojektowanego dla pewnego rozkłady danych
do danych o innym rozkładzie  nieoptymalność (niedopasowanie)
" Sposób na przezwyciężenie niedopasowania  dopasowanie
charakterystyk kwantyzatora do statystyk danych wejściowych 
kwantyzacja adaptacyjna
ć% przód (off-line)
ć% wstecz (on-line)
40. Na czym polega kwantyzacja adaptacyjna w przód?
" Procedura kwantyzacji adaptacyjnej w przód
ć% Dzielimy dane na bloki
ć% Analizujemy ka dy blok przed kwantyzacją, estymujemy parametry rozkładu
ć% Przesyłamy parametry rozkładu (informacje dodatkowe), używamy ich do ustalenia parametrów kwantyzatora
ć% Kodujemy blok
ć% Powtarzamy procedurę dla następnych bloków
" Wpływ wielkości bloku
ć% Duży blok:
- Duży czas opóz
nienia potrzebny na przetworzenie bloku
- Niebezpieczeństwo zmiany charakterystyki danych
ć% Mały blok
- Więcej danych dodatkowych (pogorszenie stopnia kompresji
41. Na czym polega kwantyzacja adaptacyjna wstecz?
" Kwantyzator dostosowywany na podstawie już skwantyzowanych próbek
" Obserwacja wyj cia porównanie z oczekiwaniami
ć% Gdy więcej (niż oczekiwano) przypadków w przedziałach wewnętrznych  skrócenie "
ć% Gdy więcej (niż oczekiwano) przypadków w przedziałach zewnętrznych  wydłużenie "
" Kwantyzator Jayanta
ć% Korekta kwantyzatora po każdym kroku kwantyzacji
ć% Każdemu przedziałowi przypisujemy mnożnik M (wewnętrzne  M < 1, zewnętrzne  M > 1)
i i i
ć% Jeżeli w wyniku kwantyzacji wejście wpada do przedziału i, to nowy parametr " spełnia związek:
"n = "n-1 M
i
42. Zasada działania kwantyzacji wektorowej.
Zasada kwantyzacji wektorowej:
" Kwantyzacja skalarna  koduje oddzielnie każdą próbkę
" Shannon  kodowanie sekwencji może być korzystniejsze niż kodowanie pojedynczych próbek
" Schemat kwantyzacji wektorowej
" Działanie kodera i dekodera  różna złożoność obliczeniowa
"  Koder  wiele porównań wektora wejściowego z wektorami słownika
duża złożoność
"  Dekoder  tylko odczytanie z tablicy
" Średnie bitowe
Rozmiar wektora  L
Rozmiar słownika  M
Średnia bitowa na próbkę:
" Zniekształcenie
43. Na czym polega i czemu służy algorytm LGB?
W10.pdf
44. Zasada i ogólny algorytm kodowania różnicowego.
Kodowanie różnicowe  zasada:
" Jakość kwantyzacji  szeroko przedziału "  wariancja, rozpiętość danych
" Obrazy, dz
więki  korelacja w danych
" Wykorzystanie korelacji  kwantyzacja wektorowa.
Problem  złożona implementacja
" Bezstratna kompresja predykcyjna  poprawa stopnia
" kompresji
" Kompresja stratna  zamiast wartości ciągu próbek bierzemy ciąg różnic. To daje zmniejszenie rozpiętości danych, zmniejszenie wariancji 
pozwala na zmniejszenie szerokości kwantyzacji, czyli poprawę jej jakości.
" Przesyłanie informacji poprzez przesyłanie różnic  kodowanie różnicowe.
" Przykład 1 :
ć% Sygnał harmoniczny, próbkowany z częstości 30 próbek/cykl
ć% Kwantyzacja 4-poziomowa:
ć% Ciąg różnic:
ć% Kwantyzacja różnic:
Podstawowy algorytm:
" Wariant 1  obliczamy ci g różnic, kwantyzujemy. To będzie podstawa do wyznaczenia rekonstrukcji.
" Przykład:
ć% ciąg danych:
ć% ciąg różnic :
ć% kwantyzacja ciągu różnic (kwantyzator 7-poziomowy):
ć% Rekonstrukcja, błędy rekonstrukcji:
ć% Problem  błędy rekonstrukcji znacznie większe od oczekiwanych
" Analiza wariantu 1:
d1=x1-x0, D1=d1+q1, X1=X0+D1 = x0+x1-x0+q1 = x1+q1
d2=x2-x1, D2=d2+q2, X2=X1+D2 = x1+q1+x2-x1+q2 = x2+q1+q2
d3=x3-x2, D3=d3+q3, X3=X2+D3 = x2+q1+q2+x3-x2+q3 x3+q1+q2+q3
" Wniosek  wariant 1 powoduje kumulacj bł dów
" Koder i dekoder korzystaj z innych informacji
" Wariant 2: dn = xn  Xn-1
" Analiza wariantu 2:
d1=x1-X0, D1=d1+q1, X1=X0+D1 = X0+x1-X0+q1 = x1+q1
d2=x2-X1, D2=d2+q2, X2=X1+D2 = X1+x2-X1+q2 = x2+q2
d3=x3-X2, D3=d3+q3, X3=X2+D3 = X2+x3-X2+q3 = x3+q3
ogólnie: Xn = x n + q n
" Przykład numeryczny
Wariant 1: sigma2 = 51.52; wariant 2: sigma2 = 6.61
" Przykład: funkcja harmoniczna
" Schemat podstawowego algorytmu
45. Co to jest ADPCM?
ADPCM to adaptacyjna różnicowa modulacja kodowo-impulsowa. Jest to metoda kompresji cyfrowego zapisu dz
więku oraz technika kodowania
analogowego sygnału mowy na postać cyfrową PCM w celu zmniejszenia ilości danych i transmisji przez kanał o przepływnościach od 16 do 32 kb/s.
Metoda kodowania ADPCM polega na tym, że zamiast samych próbek dz
więków zapisuje się tylko ich kolejne różnice. Jest to tzw. technika
predykcyjna (prognozująca) wykorzystująca fakt, że np. w kolejnych sekwencjach sygnał mowy lub dz
więku z reguły zmienia się nieznacznie,
wystarczy więc zakodować jedynie różnicę.
Liczba bitów informacji o zmianie jest automatycznie dopasowywana do potrzeb. Dzięki technice ADPCM można na pojedynczej płycie CD-ROM
zapisać około 16 godzin muzyki (z akceptowalną utratą jakości dz
więku), w odróżnieniu od około jednej godziny w przypadku zapisu standardowego.
ADPCM jest często używana jako technika do kodowania dz
więku i mowy, jest wykorzystywana w standardzie kompresji dz
więku G.726.
46. Co to są systemu Modulacji Delta?
Modulacja delta:
" Prosta odmiana schematu DPCM z jednobitowym kwantyzatorem (różnica kodowana jaki  " lub +" )
" Gdy różnica odbiega od "  wzrost zniekształcenia. Aby temu zapobiec:
ć% Duża częstotliwość próbkowania (fp >> 2 fmax)
ć% Adaptacja kroku kwantyzatora
" Rodzaje zniekształceń
ć% Słabo zmienne wejście  obszar ziarnisty (artefakt dużej częstości próbkowania i sposobu kwantyzacji) konieczność filtrowania
ć% Szybko zmienne wejście  obszar przeciążonych zboczy (obszar nadmiaru)
Zastosowania:
" Bardzo popularne w kodowaniu mowy
" Używane powszechnie w
ć% Systemach telefonicznych
ć% Systemach poczty głosowej
ć% Aplikacjach multimedialnych
" Standardy przemysłowe opisane w zaleceniach ITU-T:
ć% G.721
ć% G.723
ć% G.726
ć% G.722
" Kodowanie obrazów  rzadziej stosowane
47. Przedstaw ogólną zasadę kodowania transformacyjnego.
Kodowanie transformacyjne  zasada:
" Zasada podstawowa: na danych wykonujemy transformacje, która:
ć% Likwiduje korelacje
ć% Skupia  energię  w kilku komponentach
" Każdy z komponentów podlega kwantyzacji i kodowaniu zgodnego z jego natur ą
" Najbardziej znana implementacja  kodowanie stratne JPEG
" Ogólny schemat kodowania przedstawia rysunek
48. Najważniejsze przekształcenia używane w kodowaniu transformacyjnym
Ważne przekształcenia:
" Przekształcenia Karhunena-Loevego (Hotellinga) KLT
ć% Zbudowane z wektorów własnych macierzy autokorelacji
Rij= E[x x ]
n n+|i-j|
ć% Jest przekształceniem ortonormalnym
ć% Maksymalizuje G  optymalne dla kodowania transformacyjnego
TC
ALE:
ć% Zależy od danych, wyliczenie skomplikowane
ć% Musi by wyliczone dla każdego bloku oddzielnie
ć% KLT dla bloków 2-wymiarowych nie jest przekształceniem rozłącznym
ć% Autokorelacja nie jest znana odbiorcy  musi by przesłana dodatkowo
KLT rzadko używana w praktyce  bardziej popularne przekształcenia niezależne od danych
" Dyskretne przekształcenie kosinusowe (DCT)
" Kolejne wiersze  coraz wyższa częstotliwość (rysunek dla N=8)
Baza macierzy dwuwymiarowych:
Wzrost wariancji od b do b :
00 77
Własności DCT:
ć% Nie zależy od danych
ć% Jest przekształceniem ortogonalnym
ć% Dla danych z dużą korelacją b. dobrze aproksymuje KLT
ć% Istnieją efektywne sposoby obliczania DCT (dla N=8 zamiast 1024 mnożeń i 896 dodawań tylko 54 mnożeń , 464 dodawań i 6 przesunięć
" DCT blisko zwi zane z DFT i DST
" DST lepiej aproksymuje KLT dla małych korelacji
" DCT daje lepsze zagęszczenie energii ni DFT dla większych korelacji
49. Standard JPEG
Standard JPEG:
" Najbardziej znana metoda stratnej kompresji obrazów, od 1993 standard ISO
" Znakomita reprezentacja obrazów z 1 bpp, znośna z 0.25 bpp
" Główne etapy algorytmu :
" Każda ze składowych (RGB, YIQ, YUV) jest przetwarzana
oddzielnie
" Krok pierwszy  przesuwamy warto piksela o 2p-1 (dla p=8 o 128)
" Krok drugi  podział na bloki o rozmiarze 8 x 8. Gdy wymiar w którym kierunku nie jest wielokrotnością 8, uzupełniamy ostatni wiersz
(kolumn ) odpowiedni ilość razy. Wykonujemy DCT
" Krok trzeci  kwantyzacja
ć% Kwantyzacja stała w zerze
ć% Krok kwantyzacji dla każdego współczynnika określony w tablicy kwantyzacji Q
ij
" Przepis na kwantyzacj ę
" Tabela kwantyzacji  oko ludzkie bardziej czułe na niskie częstości nią na wysokie  stąd taki dobór Qij
" Sygnał DC  wolno zmienny od bloku do bloku  kodowanie DPCM. Różnice kodowane kodem Huffmana
" Sygnał AC  zamieniony na wektor o 63 składowych poprzez skanowanie zigzac
" Powstały wektor  duża szansa na to, że zawiera długie serie zer
ć% Gdy końcowa sekwencja zawiera same zera  wysyłamy symbol EOB po ostatnim niezerowym elemencie
ć% Wcześniejsze sekwencje kodujemy jako Z/C, gdzie Z  liczba
etykiet zerowych poprzedzających symbol za C  kategoria
symbolu niezerowego, jaki mamy zakodować
ć% AC w naszym przykładzie: 1 -9 3 0 0 0 .... 0
ć% Sekwencje Z/C kodujemy wykorzystuj c ustalone tablice
kodowania Huffmana
ć% Zakodowanie całej sekwencji (DC i AC) naszego bloku
wymaga 18 bitów  czyli 9/32 bpp.
Podsumowanie:
" JPEG  bardzo efektywny schemat kompresji obrazów naturalnych  stopień kompresji lepszy niż 1:10
" Przy ni szych średnich bitowych widoczne efekty zblokowania
50. Ogólna zasada kodowania podpasmowego
Kodowanie podpasmowe - zasada ogólna:
" Rozkład sygnału z
ródłowego na części składowe (jak w kodowaniu transformacyjnym)
" Wada kodowania transformacyjnego  sztuczny podział na bloki. Problemy z rekonstrukcją na krawędziach bloków
" Tutaj: sposób rozdziału  rozkład na różne pasma częstotliwościowe za pomocą filtrów cyfrowych
" Kodowanie każdego pasma oddzielnie
" Główny obszar zastosowań: kodowanie mowy (G.722), dz
więku (MPEG audio)
" Widoczne komponenty o różnej zmienności:
ć% Szybkozmienna składowa krótkofalowa
ć% Wolnozmienna składowa długofalowa (linia przerywana)
" Wyznaczenie składowej wolnozmiennej  średniowanie próbek w przesuwającym się oknie
51. Co to jest filtr cyfrowy? Podstawowe rodzaje filtrów.
Filtry cyfrowe  działają na ciągi liczb (zwykle są to próbki sygnału ciągłego).
" Filtr cyfrowy  relacja między wejściem {xn} a wyjściem {yn}:
ai , bi - współczynniki filtra.
" Reakcja impulsowa filtra hn  odpowiedz
filtra na wejście x0 =1, xi = 0 dla i>0
ć% Jeżeli bi = 0, to odpowiedz
zaniknie po N próbkach  filtry FIR (finite impulse response). Wtedy N  rząd filtra, zaś an = hn
ć% Jeżeli niektóre współczynniki bi `" 0, to reakcja impulsowa może być nieskończona  filtry IIR (infinite impulse reaction).
" Filtry używane w przykładzie numerycznym:
ć% Dolnoprzepustowy: h0 = 0.5, h1 = 0.5, hn = 0 dla n>1
ć% Górnoprzepustowy: h0 = 0.5, h1 =  0.5, hn = 0 dla n>1
" Filtr IIR  niech a0 =1, b1 = b. Wtedy hn :
h0 = 1*1 + b*0 = 1
h1 = 1*0 + b*1 = b
h2 = 1*0 + b*b = b2
...............................
hn = 1*0 + b*bn-1 = bn gdy b>1  filtr niestabilny.
" Filtry FIR  zawsze stabilne.
" Filtry IIR mogą dawać lepsze wyniki (ostrzejsze odcięcie, mniejszy szum w paśmie przejścia.
" Najbardziej popularne  lustrzane filtry kwadraturowe (QMF)
ć% Własność  jeżeli {hn } zadaje filtr dolnoprzepustowy, to
ć% {(-1)n h } określa filtr górnoprzepustowy
N-n-1
ć% Popularna grupa filtrów tej klasy  filtry Johnstona
" Inna popularna grupa filtrów  filtry Smitha-Barnwella
" Zasady ogólne:
ć% Im wyższy rząd filtra, tym lepszy filtr
ć% Filtr Smitha-Barnwella lepszy od filtra Johnstona tego samego rzędu
52. Na czym polega efekt maskowania?
Maskowanie :
Polega na  przesłanianiu wrażenia brzmienia dz
więków przez inne  sąsiadujące w dziedzinie częstotliwości lub czasu.
53. Kodowanie dz
więku w standardzie MPEG-1 audio
54. Co to jest MP3?