Problematika ztratove komprese (puvodne 'Zvuky (???)')

[Martin Fedor <fedor@dcse.fee.vutbr.cz>]

Omlouvam se, ze tady pisu tento 'off-topic' (i z tohoto duvodu jsem
zmenil subject), ale myslim si, ze
ostatni by mohli z vypravenek nize uvadeneho pisatele dojit ke spatnym
zaverum.
A proto chci uvest veci na pravou miru.

Abych nebyl narcen z toho, ze si vymyslim a ze vychazim ze svych
vlastnich neobjektivnich domnenek (coz je zrejme pripad onoho pisatele),
tak budu zkracene citovat z odborne literatury.

Debata se v prubehu 'threadu' ztocila od problematiky zvuku az k jpegu a
to zavinenim onoho pisatele, ktery
zacal tak mohutne michat jablka a hrusky, ze z toho vznikl ovocny
kompot. A tak jsme dotriftovali od problematiky obsahu AIFF, prez
MPEG1-layer3 az po JPEG kompresi (posledni dve maji nastesti spolecnou
ztratovou kompresi).

Rad bych proto pro zavedeni svetla do teto problematiky zkracene popsal
princip JPEG komprese. Vychazim (namatkou!) z knihy Moderni pocitacova
grafika autoru Zary, Benese a Felkela, vydalo nakladatelstvi Computer
Press (tato kniha je u nas velmi popularni a lehce k mani v knihovnach a
knihkupectvich).

Metoda rizene ztratove komprese vyuzivajici kosinove transformace byla
vyvinuta skupinou JPEG (Joint Photographic Experts Group) v ramci
mezinarodni standartizacni komise ISO.
Postup komprese se sklada z techto kroku:
1. Transformace barev do barvoveho prostoru YCbCr.
2. Redukce barev. Je mozne pred samotnou kompresi zredukovat barevnost
nekterych pixelu zprumerovanim (bud dvoji nebo ctveric sousednich
pixelu). Pozn. Toto je jedine prumerovani v teto metode! Navic vsak neni
povinne a predchazi samotne metode komprese!
3. Dopredna diskretni kosinova transformace. Bloky 8x8 obrazu se
prevedou na bloky 8x8 koeficientu DCT. 

F(u,v)=1/4 * C(u)C(v) * SUM(x=0..7)[ SUM(y=0..7)[ f(x,y) *
cos((2x+1)*u*PI/18) * cos((2y+1)*v*PI/16) ] ]
(Ony SUM jsou sumace)
Na tomhle vzorci je zajimave to, ze pripomina vazeny prumer (vahy jsou
ony kosiny  pro ruzne frekvence).
Zde se tedy pisateli stalo, ze dosel k zaveru, ze vse je zprumerovano.
Sumace jsou zde vsak mozne jen pro diskretni signal. Pro spojity (a v
obecne definici transformace) jsou samozrejme uvedeny integraly.

4. Kvantovani koeficientu DCT. V tomto kroku se deli 8x8 koeficientu v
tabulce hodnotami (danymi normami ISO), ktere jsou ulozene v
kvantovacich tabulkach. V dusledku to znamena, ze se v tomto kroku
odstranuji nektere vyssi frekvence. Tyto kvantizacni koefiecienty se
jeste pred samotnym kavantovanim(delenim) neprimo umerne upravuji
hodnotou komprese (to je ono cislo obvykle v rozsahu 0..1 [0-100%]).
5. Kodovani. Takto vytvorena tabulka a kvantifikovana DCT tabulka se
koduje huffmanovym kodovanim (resp. se koduji diference mezi jejimi
hodnotami).

Dekodovani techto dat je "jen" opacnym postupem k vyse uvadenemu. V
praxi to ovsem znamena, ze jsme odstranili vyssi frekvence z obrazu a
tak samozrejme rekonstruovany obraz (signal) neodpovida presne
puvodnimu. A jak tedy vznikaji ony "artefakty" na hranach? Prave ony
hrany obrazu v objektu tvori ony vyssi frekvence ve spektru (velky
gradient zmen barvy/intenzity). Odstranenim vyssich frekvenci ovsem
ztracime informaci o hrane a v dusledku se nam snizuje gradient mezi
sousednimi pixely. Proto misto hrany mame "rozplizlou" sekvenci pixelu,
ktere jsou interpolaci rekonstruovaneho obrazu(signalu).

Nemohu primo rici, ze obdobne je tomu u zvukoveho formatu MPEG1-Layer3
(mp3). Tam se pouziva Fourierova transformace, vzdy se odstranuji
frekvence od urcite urovne vys a dale se jiz pouziva jina strategie
odstranovani nekterych frekvenci ve spektru (hledaji se vyssi frekvence,
ktere jsou 'prekryty' frekvencemi nizsimi o vyssi intenzite). Vysledek
se vsak opet koduje huffmanovym kodovanim.

A pokud jde o tem sum.
Sum je obvykle chapan jako nahodna funkce, ktera je realizaci nahodneho
procesu. Samotnych sumu je z matematickeho hlediska definovano nekolik.
Nejcasteji se vyuziva matematickych vlastnosti tzv. bileho sumu (white
noise), jehoz stredni hodnota je nulova. Jedna se tedy o
nedeterministicky prubeh, ktery je namodulovan na nas znamy prubeh.
A mne by tedy moc zajimalo, kde by se takovy prubeh pri jasne a
deterministiky dane metode komprese a dekomprese signalu vzal.
Samozrejme, ze pri kompresi/dekompresi dochazi k chybam (at uz ke
kvantovacim v dusledku zaokrouhlovani nebo pri rekonstrukci z duvodu
aliasingu), ale to neni sum, ale jasne (deterministicky) definovatelna
chyba!

Ohledne rekonstrukce signalu a definic nahodnych procesu doporucuji
knihu Cislicova filtrace, analyza a restaurace signalu od Prof. Jiriho
Jana.

A jeste jedna reakce, ktera je uplne 'off-topic' i vuci vyse uvedenemu
vykladu:

> Vazne ti pripada logicky, ukladat nejvyznamnejsi bit na posledi pozici?
Nejvyznamnejsi _bit_ se neuklada na posledni pozici. Na posledni pozici
se uklada nejvyssi bajt cisla.
A tobe prijde logicky nejvyznamnejsi bajt cisla ukladat na _nejnizsi_
adresu pameti a naopak?
Opakuji jeste jednou, ze oba zapisy maji sve vyhody a nevyhody. U
systemu pouzivaneho na Motorole je jedinou mne znamou vyhodou to, ze se
cislo lepe cte pri primem (bajtovem!) vypisu.
Jinak zpusob zapisu pouzivany na Intel x86 procesorech ma tu vyhodu, ze
adresa ulozeni cisla se nemeni podle typu ukladaneho cisla, respektive
ze stejne adresy se nacte vzdy potrebny bajt, word nebo longword
Priklad Motorola:
adr	dc.l	0
	move.l	#10,adr
a ted jak to vypada, pokud chci cislo deset nacist jako rozdilny datovy
typ:
pokud bych chtel nacist long pak	move.l adr,d0
pokud bych chtel nacist word pak	move.w adr+2,d0
pokud bych chtel nacist byte pak	move.b adr+3,d0

a intel:
adr	dd	0
	mov	dword ptr adr,10
adekvatne pak
pokud bych chtel nacist long pak	mov eax,adr
pokud bych chtel nacist word pak	mov ax,adr
pokud bych chtel nacist byte pak	mov al,adr




defor



Pavel Narozny wrote:
> 
> ...
> >>>> Mel bych dotaz na hudebni formaty AIFF a WAV.Jakej je v tom rozdil? A co
> 
> > Toto byl puvodni dotaz, na ktery bylo odpovezeno, ze rozdil mezi AIFF a
> > WAV je "maximalne pouze v hlavicce souboru". Neni tomu tak. Je sice pravda,
> > ze oba typy maji mnoho spolecneho (jsou to soubory, ktere maji strukturu
> > tvorenou tzv. chunky, nebol-li logicky oddelenymi datovymi bloky s rozdilnym
> > vyznamem -- IFF [interchange file format] a WAV je jen zvukovy RIFF).
> > Pokud oba soubory obsahuji pouze zvukova data v PCM formatu (pulse coded
> > modulation), tak skutecne se oba soubory muhou lisit jen v dodatecnych
> > informacich a hlavickach (hlavicka uvozuje kazdy chunk).
> 
> ...spravne. A to je v 99.999% pripadu. Myslel jsem, ze pro Amigu toto obecne
> vysvetleni staci.
> 
> > Realita je vsak takova, ze oba formaty umoznuji nest ve svych chunk
> > castech data ruznych typu a zejmena ruznych kompresi(vcetne napr.
> > MPEG1-Layer3=mp3), coz vse zavisi jen na tom, zda pro dana data existuje
> > "codec" -- nebo-li ovladac/program/algoritmus pro jejich dekompresi.
> 
> Aha. To fakt nevim a ani si nejsem jist jestli je to mozne. Chapu vyznam
> 'evenlope' formatu (stejny je treba QuikTime nebo AVI, kde avi je sice
> avi, ale muze mit rozne codecy, od nekompresovaneho, pres RLE8/16/24
> ci Intel Indeo (3.x/4.x/5.x) nebo Radius Cinepak, nebo m$ video.. nebo...)
> ovsem domnivam se, ze tato vlastnost neni podporovana snad skoro nicim.
> Alespon ja jsem se s programem, ktery zpracovava AIFF v jinem(ych), nez
> standardne pouzivanem PCM formatu dat jeste nesetkal. Muzes nejaky
> doporucit na zkousku, co to vlastne umi?  (preferuji MacOS program...)
> 
> > Jeste truchlivejsi realitou je to, ze AIFF se ponejvice vyuziva na Apple
> > Macintosh, zatimco WAV ve Win32. Proto se lehce narazi na AIFF, ktery ve
> > Win32 (nebo jinde) nelze prehrat, nebot neexistuje na teto platforme
> > potrebny "codec" (resp. prevedeny algoritmus pro jejich rozkodovani).
> 
> To je ale blbost! Vrazim CD (s svyma AIFFkama) do pC a hraje to.
> Slysel jsi nekdy o QT pod win32???  Asi ne...
> Proste to jde.
> 
> Jen s RAWem v Motorola byte orderingu si to nejak neeeee poradilo :)
> 
> >> Zadny. Jen hlavicka je jina. ...ok, wav bude asi v intel bytes (little
> >> endian) formatu. Co to je? Intel udrzuje cislo tisic takto: 0001
> >> To je tzv. little endian format. Nejvice vyznamny bit je posledni.
> >> Motorola pouziva logictejsi big endian format, tisic je proste tisic.
> >> To je jediny mozny rozdil, co me napada. V MakeCD si muzes zvolit, jestli
> >> se bude ripovat do little ci big endian formatu...
> 
> > Tady bych uz chtel spise reagovat na nektere nesmyslne vyroky:
> > - Intel urcite neudrzuje cislo 1000 ve formatu 0001.
> 
> Hey! To byl priklad!!!
> 
> > Pojem "intel bytes" je nesmysl, nebot razeni samotnych bitu v bajtu je
> > samozrejme vsude stejne. Pokud uz bych chtel nejak vysvetlit rozdil mezi
> > little a big endian, tak bych musel ono cislo tisic nejdriv prevest do
> > takoveho formatu, aby bylo zrejme razeni bajtu! (1000=03E8h)
> 
> Vazne, ono by bylo nejlepsi pouzit dvojkovou soustavu, kdyz uz jsme
> u toho, ale zacinam mit dojem ze nechapes co je jednoduchy a snadno
> pochopitelny priklad - aneb jak vysvetlit rozdil mezi little a big
> endianem na jeden radek. He?
> 
> > Motorola nepouziva logictejsi razeni bajtu. Jednoduse pouziva jine
> > razeni bajtu. O logice se nema smysl bavit, nebot oba zpusoby ukladani
> > vicebajtovych slov v pameti maji sve vyhody i nevyhody.
> 
> Vazne ti pripada logicky, ukladat nejvyznamnejsi bit na posledi pozici?
> 
> >> Diskretni kosinava transformace je vznezeny slovo pro prumerovani a hledani
> >> podobnych useku... Viz jpeg, v kterym jsou napisy mensim fontem, specielne
> >> ty kontrastni... Zde i necvicene oko vidi ty artefakty, protoze v zavislosti
> >> na stupni komprese se urcuje podobnost - nemusi (a nikdy to neni) 100% podobnost,
> >> takze nam tam zustavaji bugy...
> >> V mpeg audiu je princip velmi podobny, az na to, za samplovany data jsou
> >> trosku jine konzistence a sum, takto vneseny do signalu se vyrovna sumu,
> >> bezne vzniklemu vedenim audio nestineneho kabelu podel sitoveho pripojeni
> >> ci audio vystupu pres 3.5' stereo jack konektor... :(
> 
> > Tak z toho jde des a hruza. Nazyvat kosinovou transformaci prumerovanim
> > a hledanim podobnych useku je do nebe volaji hovadina.
> 
> Vazne? Kdyz si 'odmyslis' tu cast, co 'dela z obrazkovych BLOKU cisla'
> tak zbytek je jen a jen porovnavani a prumerovani (pri encodingu).
> Na kazdym jpegu je to PEKNE videt, kdyz mas oci a monitor na vysi.
> 
> > Prevod z casove oblasti do frekvencniho spektra (tzn. jen jiny popis
> > tehoz!) nazyvat prumerovanim je (a nenabizi se mi jine slovo) DILETANSTVI!
> 
> Vazne jde o neco jineho nez opetovne pouzivani jednoho useku zvuku (obrazu)
> VICEKRAT ???  Chces to nazvat jinak nez prumerovani?
> Jak to chces jednoduse vysvetlit (na par radku) nekomu, kdo nikdy nevidel
> jpeg zdrojaky ani se nezabival tim, jak to tak asi funguje?
> 
> > Hledanim podobnych useku se snad jeste da nazvat korelace
> > (prip. autokorelace), ale integralni transformace???
> > Absolutne netusim, co pisatel chtel vysvetlit onim "Viz jpeg, v kterym
> > jsou napisy mensim fontem, specielne ty kontrastni...". Pripomina mi to
> > jen blaboleni.
> 
> Tak jeste jednou. Pri prume... ok, korelaci se useky porovnavaji a matchuji
> na shodu. Ta nikdy neni 100% (no, je to mozne... :), ale je vzdy mensi.
> Je to podle nastaveneho stupne komprese. To vi kazdy. Kdyz se ale podivas
> na vysledek, je jasny, ze zavadi do obrazu - typicky na vrcholech ctvercu -
> sum, zpusobeny tim, ze ten ctverec tam vlastne 'nepatri', ze je 'vzat' odjinud.
> Pokud mas oci, zkus se nekdy podivat nebo si zkusit uvedeny priklad a treba
> to pochopis, ty blabole!
> 
> > Veta "v zavislosti na stupni komprese se urcuje podobnost" je uplnym
> > nepochopenim JPEG komprese a kdyz uz pisatel pouziva slova jako
> > "podobnost" snad by se vice hodily na kompresi fraktalni.
> 
> Shoda bloku je zakladnim kamenem komprese a nejinak je to u jpegu.
> Doporucuji ke studiu jpeg dokumentaci...
> 
> > Je zrejme zbytecne, abych vse uvadel do poradku. K tomu si staci precist
> > jakoukoliv knizku o zpracovani signalu, kompresi obrazu nebo primo popis
> > JPEG komprese!
> 
> Yenah. Uz zacni.
> 
> > Jenom ve zkratce. DCT se pouzije pro prevod obrazu do frekvencni oblasti,
> > v zavislosti na stupni komprese se (zjednodusene receno!) odstrani ze
> > signalu vyssi frekvence (oko v obraze nejvice vnima nizzsi frekvence)
> 
> ...to je vysledek. Ovsem kdyz pochpis co to vlastne dela, tak zjistis,
> ze dochazi presne k tomu, co jsem uvedl. Mimochodem, Dafor, VYNECHALS
> jednu DOST dulezitou pasaz o rozdeleni obrazu na bloky!!
> (neni div, ze pak nechapes co pisu)
> 
> > a nakonec vsechny koeficienty jednotlivych zachovanych harmonickych
> > zakoduje Huffmanovym kodovanim ke zmenseni redundance.
> 
> Hmmm.
> 
> > Vrchol vseho je vyrok "...sum, takto vneseny do signalu se vyrovna
> > sumu...". Komprese timto zpusobem samozrejme zadny sum do signalu
> > nezanasi (zadne zvyseni entropie). Nevim, kde pisatel dosel k tomuto
> > zaveru.
> 
> =:-DDDDDDDD   Ty cloveka dokazes rozesmat...  Kdy jsi naposledy videl
> najaky jpeg, he? ...pripominam ze s audiem je to to samy...
> Zkus osciloskop!!! :))))
> 
> > Asi by normalne nestalo za to, tento e-mail komentovat, ale mnozstvi
> > blabolu, ktere se v nem objevily, a zejmena protoze se tvari jako
> > "edukativni", mne donutilo na tyto nesmysly upozornit.
> 
> Yenah. Some education is need, but unfortunaltely it seems that the
> need is valid for ya! ;)
> 
> > Na zaver si neodpustim poznamku, ze pokud pisatel podobnym diletantskym
> > zpusobem mluvi do vseho, pak Buh s kazdym, kdo mu nasloucha...
> > defor
> 
> Buh spise s tebou, Defore. Mozna sice popisujeme jen jedno a to samy,
> jen kazdy z jineho hlediska, ale prece jen mam velmi vazne vyhrady
> vuci nekterym pasazim...
> To prece nemuzes myslet vazne!
> 
> See ya!
> 
> Pavel Narozny, Troda of PEGAS, troda@cbnet.cz
> 
> "Intel inside, idiot outside."