Názory k článku Programujeme JPEG: diskrétní kosinová transformace (DCT)

V clankoch o JPEG som este stale nevidel obrazok cik-cak snimania jedneho bloku 8x8, prehliadol som to alebo to tu este nebolo? Alebo nas v skole zase ucili nejake bludy?

Děje se tak kvůli podvzorkování barvonosných složek v horizontálním směru, jak je popsané v předchozím díle. Na zmínku o tom, že by mohl mít DCT blok po převzorkování (decimaci) jinou velikost než 8x8 jsem nenarazil. Zrovna tak jsem se moc spolehlivě nedočetl o tom, že je možné podzorkování jen ve vertikálním směru, což by ale vyloučilo možnost fotky bezztrátově otáčet (ještě zbývá změnit orientaci v EXIFu pro prohlížeče, které podporují automatické otáčení). Při podvzorkování na 1/4 by velikost bloku měla být pro barvonosné složky 32x32.
Posílám aspoň jeden odkaz:
http://www.impulseadventure.com/photo/chroma-subsampling.html

Ano je rychlejsi z toho prosteho duvodu, ze sinova a kosinova transformace jsou specialni pripad transformace fourierovy.

Bazove funkce (spojite) Fourierovy transformace jsou e^(-iwt). Po jednoduchem rozepsani dostaneme 2 vzorce s bazovymi funkcemi cos(wt) a i*sin(wt). V pripade, ze je funkce suda, vyjde integral se sinem jako bazovou funkci nulovy. Zbyde tedy jen integral s cosinem, pricemz 'to, co se integruje' je funkce suda (ve smyslu parametru t). To umoznuje integrovat jen os 0 do +INF. No..a funkci mame definovanou jen na intervalu (nemame nekonecny obrazek), takze od 0 do {alfa}. Pak uz staci jen spojity integral prevest na diskretni sumy a voila ... cosinova transformace :)

Btw. to, ze predpokladame, ze funkce je suda, si muzeme dovolit. Fourierovy transformace probihaji po celem intervalu (-INF, +INF). Mame-li data pro (0, {alfa}), musime si 'zbytek' funkce dodefinovat. A nic nam nebrani dodefinovat si ji jako sudou (preklopeni pres osu Y) a zbytek mimo interval (-{alfa}, {alfa}) jako nulovou. Pri zpetnem prevodu si vezmeme (prevedeme) opet jen 'nas' interval (0, {alfa}).

Stejne tak dobre by se mohla pouzit transformace sinova (funkci si dodefinujem jako lichou). Uz si nepamatuji, jestli byl jeste jiny duvod nez ten, 'ze se proste pouziva kosinova' ;)

Když neuvažuji rychlou variantu (FFT,FDCT) pak jsou rychlé stejně, protože obě vyžadují výpočty stejného množství korelací se sinusoidami o různých frekvencích a počátečních fázích.
Rychlá fourierova transformace využívá pro délku signálu 2^N toho, že se v rovnicích pro různé koeficienty vyskytují stejné výrazy, které lze počítat pro několik koefiecintů společně. Rychlá kosinová transformace většinou využívá k výpočtu FFT s tím, že se nějak poupraví vstup a výsledek. Pro 8 prvků bude asi použit přímo nějaký dobře optimalizovaný výpočet FDCT, ale náročnost by měla být podobná.

Už jsem se o tom trošku zmiňoval v některé předchozí části. Za prvé se DCT dá spočítat dost rychle, ale to FFT taky (ale KLT už ne). Za druhé se u DCT mnohem více energie dostává do několika málo složek, takže výsledkem je matice s mnoha malými hodnotami (ideálně nulovými), které se dobře komprimují. Za třetí - a to je pravděpodobně nejdůležitější důvod - se díky výběru bázových funkcí dají s malou chybou transformovat (a poté zpětně transformovat) typické průběhy v obrázcích, například plynulé přechody barev. To u FFT nejde, protože ta předpokládá, že signál se periodicky opakuje a tak se na jeho konec snaží funkci "otočit" směrem nahoru nebo dolů (pokus je nejlepší dělat na pilovém signálu, kde je v případě FFT patrné zaoblení původně ostrého vrcholu).