Diskrétní kosinová transformace - Discrete cosine transform

Diskrétní kosinová transformace ( DCT ) vyjadřuje konečná posloupnost datových bodů z hlediska součtu kosinových funkcí oscilujících na různých frekvencích . DCT, který poprvé navrhl Nasir Ahmed v roce 1972, je široce používanou transformační technikou při zpracování signálu a kompresi dat . Používá se ve většině digitálních médií , včetně digitálních obrázků (například JPEG a HEIF , kde lze vyřadit malé vysokofrekvenční součásti), digitálního videa (například MPEG a H.26x ), digitálního zvuku (například Dolby Digital , MP3 a AAC ), digitální televize (jako SDTV , HDTV a VOD ), digitální rádio (jako AAC+ a DAB+ ) a kódování řeči (jako AAC-LD , Siren a Opus ). DCT jsou také důležité pro mnoho dalších aplikací ve vědě a technice , jako je zpracování digitálního signálu , telekomunikační zařízení, snížení využití šířky pásma sítě a spektrální metody pro numerické řešení parciálních diferenciálních rovnic .

Použití funkcí kosinu spíše než sinu je pro kompresi kritické, protože se ukazuje (jak je popsáno níže), že k přiblížení typického signálu je zapotřebí méně kosinusových funkcí , zatímco pro diferenciální rovnice kosiny vyjadřují konkrétní volbu okrajových podmínek . DCT je konkrétně Fourierova transformace podobná diskrétní Fourierově transformaci (DFT), ale používá pouze reálná čísla . DCT se obecně vztahují k koeficientům Fourierovy řady periodicky a symetricky rozšířené sekvence, zatímco DFT se vztahují k koeficientům Fourierovy řady pouze periodicky rozšířených sekvencí. DCT jsou ekvivalentní DFT zhruba dvojnásobné délky a pracují na skutečných datech se sudou symetrií (protože Fourierova transformace skutečné a rovnoměrné funkce je reálná a rovnoměrná), zatímco u některých variant jsou vstupní a/nebo výstupní data posunuta o polovinu vzorek. Existuje osm standardních variant DCT, z nichž čtyři jsou běžné.

Nejběžnější variantou diskrétní kosinové transformace je DCT typu II, kterému se často říká jednoduše „DCT“. Toto byl původní DCT, který poprvé navrhl Ahmed. Jeho inverzní typ DCT typu III se odpovídajícím způsobem často nazývá jednoduše „inverzní DCT“ nebo „IDCT“. Dvě související transformace jsou diskrétní sinusová transformace (DST), která je ekvivalentní DFT skutečných a lichých funkcí, a modifikovaná diskrétní kosinová transformace (MDCT), která je založena na DCT překrývajících se dat. Multidimenzionální DCT (MD DCT) jsou vyvinuty za účelem rozšíření konceptu DCT na MD signály. Existuje několik algoritmů pro výpočet MD DCT. Pro snížení výpočetní náročnosti implementace DCT byla vyvinuta řada rychlých algoritmů. Jedním z nich je celočíselná DCT (IntDCT), celočíselná aproximace standardního DCT, používaná v několika mezinárodních normách ISO/IEC a ITU-T .

DCT komprese, známá také jako bloková komprese, komprimuje data v sadách diskrétních DCT bloků. Bloky DCT mohou mít řadu velikostí, včetně 8x8 pixelů pro standardní DCT, a různé celočíselné velikosti DCT mezi 4x4 a 32x32 pixely. DCT má silnou vlastnost „zhutnění energie“, schopnou dosáhnout vysoké kvality při vysokých poměrech komprese dat . Při použití silné komprese DCT se však mohou objevit artefakty blokové komprese .

Dějiny

Nasir Ahmed , vynálezce diskrétní kosinové transformace (DCT), kterou poprvé navrhl v roce 1972.

Diskrétní kosinovou transformaci (DCT) poprvé navrhl Nasir Ahmed , když pracoval na Kansaské státní univerzitě , a tento koncept navrhl National Science Foundation v roce 1972. Původně měl DCT v úmyslu pro kompresi obrazu . Ahmed vyvinul praktický algoritmus DCT se svým doktorandem T. Natarajanem a přítelem KR Rao na University of Texas v Arlingtonu v roce 1973 a zjistili, že to byl nejefektivnější algoritmus pro kompresi obrazu. Své výsledky představili v příspěvku z ledna 1974 s názvem „Diskrétní kosinová transformace“. Popisoval to, čemu se nyní říká DCT typu II (DCT-II), a také inverzní DCT typu III (IDCT). Jednalo se o srovnávací publikaci a od jejího vydání byl citován jako zásadní vývoj v tisících děl. Základní výzkumné práce a události, které vedly k rozvoji DCT, byly shrnuty v pozdější publikaci Ahmeda „Jak jsem přišel s diskrétní kosinovou transformací“.

Od svého zavedení v roce 1974 probíhá významný výzkum DCT. V roce 1977 Wen-Hsiung Chen publikoval článek s C. Harrisonem Smithem a Stanleyem C. Fralickem o rychlém algoritmu DCT a založil Compression Labs pro komercializaci technologie DCT. Další vývoj zahrnuje dokument z roku 1978 od MJ Narasimhy a AM Petersona a dokument z roku 1984 od BG Lee. Tyto výzkumné práce, spolu s původním papírem Ahmed z roku 1974 a papírem Chen z roku 1977, citovala skupina Joint Photographic Experts Group jako základ algoritmu JPEG pro ztrátovou kompresi obrazu v roce 1992.

V roce 1975 John A. Roese a Guner S.Robinson upravili DCT pro kódování videa s kompenzací pohybu mezi snímky . Experimentovali s DCT a rychlou Fourierovou transformací (FFT), přičemž pro oba vyvinuli hybridní kodéry mezi snímky, a zjistili, že DCT je díky své snížené složitosti nejefektivnější, schopné komprimovat obrazová data až na 0,25 bitů na pixel pro scénu videotelefonu s kvalitou obrazu srovnatelnou s kodérem uvnitř rámce vyžadujícím 2-bit na pixel. DCT použil na kódování videa Wen-Hsiung Chen, který v roce 1977 vyvinul rychlý algoritmus DCT s CH Smith a SC Fralick a založil Compression Labs pro komercializaci technologie DCT. V roce 1979 Anil K.Jain a Jaswant R. Jain dále vyvinuli pohybově kompenzovanou DCT kompresi videa, nazývanou také bloková kompenzace pohybu. To vedlo k tomu, že Chen vyvinul praktický algoritmus komprese videa, nazývaný DCT s kompenzací pohybu nebo kódování adaptivní scény, v roce 1981. DCT s kompenzací pohybu se později od konce 80. let stal standardní kódovací technikou pro kompresi videa.

Celé číslo DCT se používá v Advanced Video Coding (AVC), zavedeném v roce 2003, a High Efficiency Video Coding (HEVC), zavedeném v roce 2013. Celé číslo DCT se používá také ve formátu High Efficiency Image Format (HEIF), který využívá podmnožinu z HEVC Video Coding formát pro kódování statických snímků.

Varianta DCT, modifikovaná diskrétní kosinová transformace (MDCT), byla vyvinuta Johnem P. Princenem, AW Johnsonem a Alanem B. Bradleyem na univerzitě v Surrey v roce 1987, v návaznosti na dřívější práci Princena a Bradleye v roce 1986. MDCT se používá ve většině moderních formátů komprese zvuku , jako je Dolby Digital (AC-3), MP3 (který používá hybridní algoritmus DCT- FFT ), Advanced Audio Coding (AAC) a Vorbis ( Ogg ).

Diskrétní sinus transformaci (DST) byl odvozen od DCT, nahrazením stav Neumann při x = 0 s podmínkou Dirichlet . DST byl popsán v papíru DCT z roku 1974 Ahmedem, Natarajanem a Rao. DST typu I (DST-I) později popsal Anil K.Jain v roce 1976 a typ II DST (DST-II) poté popsali HB Kekra a JK Solanka v roce 1978.

Nasir Ahmed také vyvinul bezztrátový algoritmus DCT s Giridhar Mandyam a Neeraj Magotra na univerzitě v Novém Mexiku v roce 1995. To umožňuje použít techniku ​​DCT pro bezeztrátovou kompresi obrázků. Je to modifikace původního DCT algoritmu a zahrnuje prvky inverzní DCT a delta modulace . Je to efektivnější bezeztrátový kompresní algoritmus než entropické kódování . Bezztrátový DCT je také známý jako LDCT.

Aplikace

DCT je nejpoužívanější transformační technika při zpracování signálu a zdaleka nejpoužívanější lineární transformace při kompresi dat . Nekomprimovaná digitální média i bezeztrátová komprese měly neprakticky vysoké požadavky na paměť a šířku pásma , což bylo výrazně sníženo vysoce účinnou ztrátovou kompresní technikou DCT , schopnou dosáhnout poměrů komprese dat od 8: 1 do 14: 1 pro kvalitu blízkou studiu, až 100: 1 pro obsah přijatelné kvality. Standardy komprese DCT se používají v technologiích digitálních médií, jako jsou digitální obrázky , digitální fotografie , digitální video , streamovací média , digitální televize , streamovaná televize , video na vyžádání (VOD), digitální kino , video ve vysokém rozlišení (HD video) a televize s vysokým rozlišením (HDTV).

DCT, a zejména DCT-II, se často používá při zpracování signálu a obrazu, zejména pro ztrátovou kompresi, protože má silnou vlastnost „zhutnění energie“: v typických aplikacích má většina informací o signálu tendenci být koncentrována v několik nízkofrekvenčních komponent DCT. U silně korelovaných Markovových procesů se DCT může přiblížit účinnosti zhutnění Karhunen-Loèveovy transformace (která je optimální ve smyslu dekorelace). Jak je vysvětleno níže, vyplývá to z okrajových podmínek implicitních v kosinových funkcích.

DCTs jsou také široce používají v řešení parciálních diferenciálních rovnic pomocí spektrálních metod , kde se různé varianty DCT odpovídají mírně odlišnými i / lichých okrajových podmínek na obou koncích pole.

DCT jsou také úzce spjaty s Chebyshevovými polynomy a rychlé DCT algoritmy (níže) se používají v Chebyshevově aproximaci libovolných funkcí řadou Chebyshevových polynomů, například v Clenshaw -Curtisově kvadratuře .

DCT je kódovací standard pro multimediální telekomunikační zařízení. Je široce používán pro snížení přenosové rychlosti a snížení využití šířky pásma sítě . Komprese DCT výrazně snižuje množství paměti a šířku pásma potřebnou pro digitální signály .

Obecné aplikace

DCT je široce používán v mnoha aplikacích, mezi které patří následující.

  • Dohled
  • Automobilová kamera v černé skříňce
  • Video
  • Vodoznak - digitální vodoznak , vodoznak obrazu, vodoznak videa, 3D video vodoznak, reverzibilní skrytí dat , detekce vodoznaku
  • Bezdrátová technologie
  • Bezdrátová senzorová síť (WSN) - bezdrátové akustické senzorové sítě
  • Standardy vizuálních médií DCT

    DCT-II, také známý jednoduše jako DCT, je nejdůležitější technikou komprese obrazu . Používá se ve standardech komprese obrazu, jako je JPEG , a standardech komprese videa, jako jsou H.26x , MJPEG , MPEG , DV , Theora a Daala . Tam se vypočítají dvojrozměrné bloky DCT-II a výsledky se kvantizují a kódují entropie . V tomto případě je obvykle 8 a vzorec DCT-II je aplikován na každý řádek a sloupec bloku. Výsledkem je pole transformačních koeficientů 8 × 8, ve kterém je prvek (vlevo nahoře) složkou DC (nulová frekvence) a položky se zvyšujícími se svislými a vodorovnými hodnotami indexu představují vyšší svislé a vodorovné prostorové frekvence.

    Advanced Video Coding (AVC) používá celočíselné DCT (IntDCT), celočíselné přiblížení DCT. Používá celistvé bloky DCT 4x4 a 8x8. High Efficiency Video Coding (HEVC) a High Efficiency Image Format (HEIF) používají různé celočíselné velikosti DCT bloků mezi 4x4 a 32x32 pixely . Od roku 2019 je AVC zdaleka nejčastěji používaným formátem pro záznam, kompresi a distribuci video obsahu, který používá 91% vývojářů videa, následovaný HEVC, který používá 43% vývojářů.

    Formáty obrázků

    Standard komprese obrazu Rok Běžné aplikace
    JPEG 1992 Nejpoužívanější standard komprese obrazu a digitální formát obrazu ,
    JPEG XR 2009 Otevřete XML Paper Specification
    WebP 2010 Grafický formát, který podporuje kompresi ztrátovou z digitálních snímků . Vyvinuto společností Google .
    Vysoce účinný formát obrazu (HEIF) 2013 Formát obrazového souboru založený na kompresi HEVC . Vylepšuje kompresi ve formátu JPEG a podporuje animaci s mnohem efektivnější kompresí než animovaný formát GIF .
    BPG 2014 Na základě komprese HEVC
    JPEG XL 2020 Rastrový grafický formát bez licenčních poplatků, který podporuje ztrátovou i bezeztrátovou kompresi.

    Formáty videa

    Standard pro kódování videa Rok Běžné aplikace
    H.261 1988 První z rodiny standardů pro kódování videa . Používá se především ve starších videokonferenčních a video telefonních produktech.
    Motion JPEG (MJPEG) 1992 QuickTime , úpravy videa , nelineární úpravy , digitální fotoaparáty
    Video MPEG-1 1993 Distribuce digitálního videa na disku CD nebo internetovém videu
    Video MPEG-2 (H.262) 1995 Ukládání a zpracování digitálních obrázků ve vysílacích aplikacích, digitální televizi , HDTV , kabelové, satelitní, vysokorychlostní internet , distribuce DVD videa
    DV 1995 Videokamery , digitální kazety
    H.263 ( MPEG-4 část 2 ) 1996 Videotelefonie přes veřejnou komutovanou telefonní síť (PSTN), H.320 , digitální síť integrovaných služeb (ISDN)
    Pokročilé kódování videa (AVC / H.264 / MPEG-4 ) 2003 Nejběžnější formát záznamu/komprese/distribuce videa HD , internetové video , YouTube , disky Blu-ray , vysílání HDTV , webové prohlížeče , streamování televize , mobilní zařízení , spotřebitelská zařízení, Netflix , videotelefonie , Facetime
    Theora 2004 Internetové video, webové prohlížeče
    VC-1 2006 Windows media, Blu-ray disky
    Apple ProRes 2007 Profesionální video produkce .
    WebM Video 2010 Multimediální open source formát vyvinutý společností Google určeny k použití s HTML5 .
    Vysoce účinné kódování videa (HEVC / H.265) 2013 Vystupující nástupce standardu H.264/MPEG-4 AVC, který má podstatně vylepšené možnosti komprese.
    Daala 2013

    MDCT zvukové standardy

    Obecný zvuk

    Standard komprese zvuku Rok Běžné aplikace
    Dolby Digital (AC-3) 1991 Kino , digitální kino , DVD , Blu-ray , streamovaná média , videohry
    Adaptive Transform Acoustic Coding (ATRAC) 1992 MiniDisc
    MPEG Layer III (MP3) 1993 Digitální distribuce zvuku , přehrávače MP3 , přenosné přehrávače médií , streamovaná média
    Perceptual Audio Coder (PAC) 1996 Služba digitálního audio rádia (DARS)
    Pokročilé kódování zvuku ( zvuk AAC / MP4 ) 1997 Digitální distribuce zvuku , přenosné přehrávače médií , streamovací média , herní konzole , mobilní zařízení , iOS , iTunes , Android , BlackBerry
    Vysoce účinné pokročilé kódování zvuku (AAC+) 1997 Digitální rádio , digitální zvukové vysílání (DAB+), Digital Radio Mondiale (DRM)
    Kuchařský kodek 1998 RealAudio
    Windows Media Audio (WMA) 1999 Windows Media
    Vorbis 2000 Digitální distribuce zvuku , rozhlasové stanice , streamovací média , videohry , Spotify , Wikipedia
    High-Definition Coding (HDC) 2002 Digitální rádio, HD rádio
    Dynamické přizpůsobení rozlišení (DRA) 2008 Čínský národní zvukový standard, China Multimedia Mobile Broadcasting , DVB-H
    Dolby AC-4 2017 ATSC 3.0 , televize s ultra vysokým rozlišením (UHD TV)
    MPEG-H 3D zvuk

    Kódování řeči

    Standardní kódování řeči Rok Běžné aplikace
    AAC-LD (LD-MDCT) 1999 Mobilní telefonie , Voice-over-IP (VoIP), iOS , FaceTime
    Siréna 1999 VoIP , širokopásmový zvuk , G.722.1
    G.722.1 1999 VoIP, širokopásmový zvuk, G.722
    G.729.1 2006 G.729 , VoIP, širokopásmový zvuk, mobilní telefonie
    EVRC-WB 2007 Širokopásmový zvuk
    G.718 2008 VoIP, širokopásmový zvuk, mobilní telefonie
    G.719 2008 Telekonference , videokonference , hlasová pošta
    KELTŠTINA 2011 VoIP, mobilní telefonie
    Opus 2012 VoIP, mobilní telefonie, WhatsApp , PlayStation 4
    Vylepšené hlasové služby (EVS) 2014 Mobilní telefonie, VoIP, širokopásmový zvuk

    MD DCT

    Multidimenzionální DCT (MD DCT) mají několik aplikací, hlavně 3-D DCT, jako je 3-D DCT-II, který má několik nových aplikací, jako jsou kódovací systémy Hyperspectral Imaging, 3-D DCT kódování s proměnnou časovou délkou, algoritmy kódování videa , adaptivní kódování videa a 3-D komprese. Vzhledem k vylepšení hardwaru, softwaru a zavedení několika rychlých algoritmů se nutnost používání MD DCT rychle zvyšuje. DCT-IV si získal popularitu díky svým aplikacím v rychlé implementaci polyfázových filtračních bank s reálnými hodnotami, lapovaných ortogonálních transformací a kosinově modulovaných vlnkových základen.

    Zpracování digitálních signálů

    DCT hraje velmi důležitou roli v digitálním zpracování signálu . Použitím DCT lze signály komprimovat. DCT lze použít v elektrokardiografii ke kompresi signálů EKG. DCT2 poskytuje lepší kompresní poměr než DCT.

    DCT je široce implementován v procesorech digitálního signálu (DSP) a také v softwaru pro zpracování digitálního signálu. Mnoho společností vyvinulo DSP založené na technologii DCT. DCT jsou široce používány pro aplikace, jako je kódování , dekódování, video, audio, multiplexování , řídicí signály, signalizace a převod analogově na digitální . DCTs jsou také běžně používané pro televize s vysokým rozlišením (HDTV) kodéru / dekodéru čipů .

    Kompresní artefakty

    Běžným problémem komprese DCT v digitálních médiích jsou artefakty blokové komprese způsobené bloky DCT. Algoritmus DCT může při použití silné komprese způsobit artefakty založené na blocích. Vzhledem k tomu, že DCT se používá ve většině standardů digitálního kódování obrázků a videa (jako jsou formáty JPEG , H.26x a MPEG ), jsou artefakty blokové komprese založené na DCT v digitálních médiích rozšířené . V algoritmu DCT je obraz (nebo snímek v obrazové sekvenci) rozdělen na čtvercové bloky, které jsou zpracovávány nezávisle na sobě, poté je odebrán DCT těchto bloků a výsledné koeficienty DCT jsou kvantovány . Tento proces může způsobit artefakty blokování, především při vysokých poměrech komprese dat . To může také způsobit efekt „ komářího šumu “, který se běžně vyskytuje v digitálním videu (například ve formátech MPEG).

    DCT bloky se často používají v glitch art . Umělec Rosa Menkman využívá ve svém závadovém umění kompresní artefakty založené na DCT, zejména bloky DCT, které se nacházejí ve většině formátů digitálních médií, jako jsou digitální obrázky JPEG a digitální zvuk MP3 . Dalším příkladem je Jpegs od německého fotografa Thomase Ruffa , který používá záměrné artefakty JPEG jako základ stylu obrázku.

    Neformální přehled

    Jako každá Fourierova transformace, diskrétní kosinové transformace (DCT) vyjadřují funkci nebo signál ve formě součtu sinusoidů s různými frekvencemi a amplitudami . Stejně jako diskrétní Fourierova transformace (DFT), DCT pracuje na funkci v konečném počtu diskrétních datových bodů. Zjevný rozdíl mezi DCT a DFT spočívá v tom, že první používá pouze kosinové funkce, zatímco druhý používá jak kosinus, tak sinus (ve formě komplexních exponenciálů ). Tento viditelný rozdíl je však pouze důsledkem hlubšího rozlišení: DCT implikuje různé okrajové podmínky od DFT nebo jiných souvisejících transformací.

    Transformace související s Fourierem, které fungují na funkci přes konečnou doménu , jako je DFT nebo DCT nebo Fourierova řada , lze považovat za implicitně definující rozšíření této funkce mimo doménu. To znamená, že jakmile napíšete funkci jako součet sinusoidů, můžete tento součet vyhodnotit libovolně , a to i v případě, že nebyl určen originál. DFT, stejně jako Fourierova řada, znamená pravidelné rozšiřování původní funkce. DCT, jako kosinová transformace , znamená rovnoměrné rozšíření původní funkce.

    Ilustrace implicitních sudých/lichých rozšíření vstupních dat DCT pro N = 11 datových bodů (červené tečky) pro čtyři nejběžnější typy DCT (typy I-IV).

    Protože však DCT fungují na konečných , diskrétních sekvencích, vyvstávají dva problémy, které neplatí pro kontinuální kosinovou transformaci. Za prvé, je třeba určit, zda funkce sudé nebo liché na obou levé a pravé hranice domény (tj min- n a MAX n hranice v následujících definicích, v tomto pořadí). Za druhé, je třeba určit, v jakém bodě je funkce sudá nebo lichá. Zejména zvažte posloupnost abcd čtyř stejně rozložených datových bodů a řekněte, že zadáme sudou levou hranici. Existují dvě rozumné možnosti: buď jsou data dokonce o vzorku a , v takovém případě je sudé rozšíření dcbabcd , nebo jsou data dokonce o bodu v polovině mezi a a předchozím bodem, v takovém případě je sudé rozšíření dcbaabcd ( a se opakuje).

    Tyto volby vedou ke všem standardním variantám DCT a také k diskrétním sinusovým transformacím (DST). Každá hranice může být sudá nebo lichá (2 volby na hranici) a může být symetrická k datovému bodu nebo k bodu v polovině mezi dvěma datovými body (2 volby na hranici), celkem tedy 2 × 2 × 2 × 2 = 16 možnosti. Polovina těchto možností, ty, kde je levá hranice sudá, odpovídá 8 typům DCT; druhá polovina je 8 typů letního času.

    Tyto různé okrajové podmínky silně ovlivňují aplikace transformace a vedou k jedinečně užitečným vlastnostem pro různé typy DCT. Většina přímo, při použití s Fourierovou transformací související řešit parciální diferenciální rovnice podle spektrálních metod , okrajové podmínky jsou přímo určeny jako součást řešeného problému. Nebo u MDCT (na základě DCT typu IV) jsou okrajové podmínky důvěrně zahrnuty v kritické vlastnosti MDCT zrušení aliasu časové domény. Subtilnějším způsobem jsou okrajové podmínky zodpovědné za vlastnosti „zhutnění energie“, díky nimž jsou DCT užitečné pro kompresi obrazu a zvuku, protože hranice ovlivňují rychlost konvergence jakékoli Fourierovy podobné série.

    Zejména je dobře známo, že jakékoli diskontinuity ve funkci snižují rychlost konvergence Fourierovy řady, takže je zapotřebí více sinusoidů k ​​reprezentaci funkce s danou přesností. Stejný princip řídí užitečnost DFT a dalších transformací pro kompresi signálu; čím je funkce hladší, tím méně termínů v jejích DFT nebo DCT je zapotřebí k její přesné reprezentaci a tím více ji lze komprimovat. (Zde uvažujeme o DFT nebo DCT jako o aproximacích pro Fourierovu řadu nebo kosinovou řadu funkce, abychom mluvili o její „hladkosti“.) Implicitní periodicita DFT však znamená, že diskontinuity se obvykle vyskytují při hranice: jakýkoli náhodný segment signálu pravděpodobně nebude mít stejnou hodnotu na levé i pravé hranici. (Podobný problém nastává u letního času, kdy podmínka liché levé hranice znamená diskontinuitu pro jakoukoli funkci, která na této hranici není náhodou nulová.) Naproti tomu DCT, kde jsou obě hranice sudé, vždy přináší souvislé prodloužení při hranice (i když sklon je obecně nesouvislý). To je důvod, proč DCT a zejména DCT typů I, II, V a VI (typy, které mají dvě sudé hranice) obecně fungují lépe pro kompresi signálu než DFT a DST. V praxi je pro takové aplikace obvykle upřednostňován DCT typu II, částečně z důvodu výpočetního pohodlí.

    Formální definice

    Formálně je diskrétní kosinová transformace je lineární , invertibilní funkce (kde označuje soubor reálných čísel ), nebo ekvivalentně invertibilní N x N čtvercové matice . Existuje několik variant DCT s mírně upravenými definicemi. Tyto N reálná čísla jsou transformovány do N reálných čísel podle jednoho ze vzorců:

    DCT-I

    Někteří autoři dále Vynásobte a termíny podle a odpovídajícím způsobem Vynásobte a podmínky podle což DCT-I matice ortogonální . Pokud se dále vynásobí celkovým faktorem měřítka, ale přeruší přímou korespondenci se skutečným sudým DFT .

    DCT-I je přesně ekvivalentní (až do celkové měřítko 2), na DFT z reálných čísel s ještě symetrie. Například DCT-I reálných čísel je přesně ekvivalentní DFT osmi reálných čísel (sudá symetrie) děleno dvěma. (Naproti tomu DCT typy II-IV zahrnují posun polovičního vzorku v ekvivalentním DFT.)

    Všimněte si však, že DCT-I není definován pro méně než 2. (Všechny ostatní typy DCT jsou definovány jako pozitivní

    DCT-I tedy odpovídá okrajovým podmínkám: je rovnoměrně kolem a dokonce kolem ; podobně pro

    DCT-II

    DCT-II je pravděpodobně nejběžněji používanou formou a často se mu jednoduše říká „DCT“.

    Tato transformace je přesně ekvivalentní (až do celkové měřítko 2) na DFT ze skutečných vstupů i symetrie, kde i-indexované prvky jsou nulové. To znamená, že je polovina z DFT ze vstupů , kde k a pro transformaci DCT-II je také možné, za použití 2 N signálu následuje vynásobení půl směny. To předvádí Makhoul .

    Někteří autoři dále vynásobí termín a vynásobí výslednou matici faktorem celkového měřítka (odpovídající změnu DCT-III viz níže). Díky tomu je matice DCT-II ortogonální , ale přeruší přímou korespondenci se skutečným rovnoměrným DFT napůl posunutého vstupu. Toto je normalizace, kterou používá například Matlab , viz. V mnoha aplikacích, jako je JPEG , je škálování libovolné, protože měřítkové faktory lze kombinovat s následným výpočetním krokem (např. Krok kvantizace v JPEG) a lze zvolit měřítko, které umožňuje výpočet DCT s menším počtem násobení.

    DCT-II implikuje okrajové podmínky: je sudý kolem a dokonce i kolem je sudý kolem a lichý kolem

    DCT-III

    Protože se jedná o inverzní DCT-II (až do faktoru měřítka, viz níže), je tento formulář někdy jednoduše označován jako „inverzní DCT“ („IDCT“).

    Někteří autoři dělí termín místo 2 (což vede k celkovému termínu) a vynásobí výslednou matici faktorem celkového měřítka (odpovídající změnu DCT-II viz výše), takže DCT-II a DCT- III jsou navzájem transponovány. Díky tomu je matice DCT-III ortogonální , ale přeruší přímou korespondenci se skutečným rovnoměrným DFT napůl posunutého výstupu.

    DCT-III implikuje okrajové podmínky: je sudý kolem a lichý kolem je sudý kolem a dokonce kolem

    DCT-IV

    Matice DCT-IV se stává ortogonální (a je tedy jasně symetrická a vlastní inverzní), pokud se dále vynásobí faktorem celkového měřítka

    Varianta DCT-IV, kde se data z různých transformací překrývají , se nazývá modifikovaná diskrétní kosinová transformace (MDCT).

    DCT-IV implikuje okrajové podmínky: je sudý kolem a lichý kolem podobně pro

    DCT V-VIII

    DCT typů I – IV zacházejí s oběma hranicemi konzistentně, pokud jde o bod symetrie: jsou sudé/liché kolem datového bodu pro obě hranice nebo v polovině cesty mezi dvěma datovými body pro obě hranice. Naproti tomu DCT typu V-VIII znamenají hranice, které jsou sudé/liché kolem datového bodu pro jednu hranici a na půli cesty mezi dvěma datovými body pro druhou hranici.

    Jinými slovy, typy DCT I – IV jsou ekvivalentní skutečným sudým DFT sudého řádu (bez ohledu na to, zda je sudý nebo lichý), protože odpovídající DFT má délku (pro DCT-I) nebo (pro DCT-II a III ) nebo (pro DCT-IV). Čtyři další typy diskrétní kosinové transformace odpovídají v podstatě reálným sudým DFT logicky lichého řádu, které mají faktory ve jmenovatelích kosinových argumentů.

    Zdá se však, že tyto varianty se v praxi používají jen zřídka. Jedním z důvodů je možná to, že algoritmy FFT pro DFT s lichou délkou jsou obecně komplikovanější než algoritmy FFT pro sudé DFT (např. Nejjednodušší algoritmy radix-2 jsou pouze pro sudé délky) a tato zvýšená složitost se přenáší i na DCT jak je popsáno níže.

    (Triviální reálné sudé pole, délka jedna DFT (lichá délka) jednoho čísla a  , odpovídá DCT-V délky )

    Inverzní transformace

    Pomocí výše uvedených normalizačních konvencí je inverzní DCT-I DCT-I vynásobená 2/( N  -1). Inverzní DCT-IV je DCT-IV násobí 2 / N . Převrácená hodnota DCT-II je DCT-III vynásobená 2/ N a naopak.

    Stejně jako u DFT je normalizační faktor před těmito definicemi transformace pouze konvencí a liší se mezi léčbami. Někteří autoři například násobí transformace tak, že inverzní nevyžaduje žádný další multiplikativní faktor. V kombinaci s příslušnými faktory 2 (viz výše) to lze použít k vytvoření ortogonální transformační matice .

    Multidimenzionální DCT

    Multidimenzionální varianty různých typů DCT přímo vyplývají z jednorozměrných definic: jsou jednoduše oddělitelným produktem (ekvivalentně, složením) DCT v každé dimenzi.

    MD DCT-II

    Například dvourozměrný DCT-II obrázku nebo matice je jednoduše jednorozměrný DCT-II, shora, prováděný podél řádků a poté podél sloupců (nebo naopak). To znamená, že 2D DCT-II je dán vzorcem (vynechání normalizace a dalších faktorů měřítka, jak je uvedeno výše):

    Inverze vícerozměrného DCT je pouze oddělitelným součinem inverzí odpovídajících jednorozměrných DCT (viz výše), např. Jednorozměrné inverze aplikované podél jedné dimenze současně v algoritmu řádků a sloupců.

    3-D DCT-II je pouze rozšíření 2-D DCT-II v trojrozměrném prostoru a matematicky je možno vypočítat podle vzorce

    Převrácená hodnota 3-D DCT-II je 3-D DCT-III a lze ji vypočítat ze vzorce

    Technicky je výpočet dvoj-, tří- (nebo -multi) dimenzionálního DCT sekvencemi jednorozměrných DCT podél každé dimenze známý jako algoritmus řádek-sloupec . Stejně jako u vícerozměrných algoritmů FFT však existují i ​​jiné metody pro výpočet stejné věci při provádění výpočtů v jiném pořadí (tj. Prokládání/kombinování algoritmů pro různé dimenze). Vzhledem k rychlému růstu aplikací založených na 3-D DCT bylo vyvinuto několik rychlých algoritmů pro výpočet 3-D DCT-II. Algoritmy Vector-Radix se používají pro výpočet MD DCT ke snížení výpočetní složitosti a ke zvýšení výpočetní rychlosti. Pro efektivní výpočet 3-D DCT-II byl vyvinut rychlý algoritmus, algoritmus Vector-Radix Decimation in Frequency (VR DIF).

    3-D DCT-II VR DIF

    Aby bylo možné použít algoritmus VR DIF, musí být vstupní data formulována a přeskupena následovně. Velikost transformace N × N × N se předpokládá 2.

    Čtyři základní fáze výpočtu 3-D DCT-II pomocí algoritmu VR DIF.
    kde

    Obrázek vedle zobrazuje čtyři fáze, které se podílejí na výpočtu 3-D DCT-II pomocí algoritmu VR DIF. První fází je 3-D přeuspořádání pomocí indexového mapování znázorněného výše uvedenými rovnicemi. Druhou fází je výpočet motýla. Každý motýl vypočítá dohromady osm bodů, jak ukazuje obrázek těsně níže, kde .

    Původní 3-D DCT-II lze nyní zapsat jako

    kde

    Pokud jsou brány v úvahu sudé a liché části a a, obecný vzorec pro výpočet 3-D DCT-II lze vyjádřit jako

    Fáze jednoho motýla algoritmu VR DIF.

    kde

    Aritmetická složitost

    Celý výpočet 3-D DCT vyžaduje fáze a každá fáze zahrnuje motýly. Celá 3-D DCT vyžaduje počítání motýlů. Každý motýl vyžaduje sedm skutečných násobení (včetně triviálních násobení) a 24 skutečných přírůstků (včetně triviálních sčítání). Celkový počet skutečných násobení potřebných pro tuto fázi je tedy a celkový počet skutečných přírůstků, tj. Včetně post-přírůstků (rekurzivní sčítání), které lze vypočítat přímo po fázi motýla nebo po fázi bitového obrácení, jsou dány vztahem

    Konvenční metoda pro výpočet MD-DCT-II používá přístup RCF (Row-Column-Frame), který je výpočetně složitý a méně produktivní na nejpokročilejších současných hardwarových platformách. Počet násobení potřebných k výpočtu algoritmu VR DIF ve srovnání s algoritmem RCF je poměrně malý. Počet násobení a přírůstků zahrnutých v přístupu RCF je dán a . Z tabulky 1 je vidět, že celkový počet

    TABULKA 1 Porovnání algoritmů VR DIF a RCF pro výpočet 3D-DCT-II
    Velikost transformace 3D VR Mults RCF Mults Přidává 3D VR RCF přidává
    8 × 8 × 8 2,625 4.5 10,875 10,875
    16 × 16 × 16 3.5 6 15,188 15,188
    32 × 32 × 32 4,375 7.5 19,594 19,594
    64 × 64 × 64 5.25 9 24,047 24,047

    násobení spojených s algoritmem 3-D DCT VR je menší než násobení související s přístupem RCF o více než 40%. Přístup RCF navíc zahrnuje transpozici matice a více indexování a výměny dat než nový algoritmus VR. Díky tomu je algoritmus 3-D DCT VR efektivnější a vhodnější pro 3-D aplikace, které zahrnují 3-D DCT-II, jako je komprese videa a další aplikace pro zpracování obrazu 3-D.

    Hlavním hlediskem při výběru rychlého algoritmu je vyhnout se výpočetním a strukturálním složitostem. Jak postupuje technologie počítačů a DSP, doba provádění aritmetických operací (násobení a sčítání) se stává velmi rychlou a pravidelná výpočetní struktura se stává nejdůležitějším faktorem. Přestože výše uvedený 3-D VR algoritmus nedosahuje teoretické dolní hranice počtu násobení, má ve srovnání s jinými 3-D DCT algoritmy jednodušší výpočetní strukturu. Může být implementován na místě pomocí jediného motýla a má vlastnosti algoritmu Cooley-Tukey FFT ve 3-D. 3-D VR proto představuje dobrou volbu pro redukci aritmetických operací při výpočtu 3-D DCT-II při zachování jednoduché struktury, která charakterizuje FFT algoritmy Cooley – Tukey ve stylu motýlů .

    Dvourozměrné frekvence DCT z JPEG DCT

    Obrázek vpravo ukazuje kombinaci horizontálních a vertikálních frekvencí pro dvourozměrný DCT 8 × 8 . Každý krok zleva doprava a shora dolů představuje zvýšení frekvence o 1/2 cyklu. Například pohyb doprava z levého horního čtverce vede k nárůstu horizontální frekvence o půl cyklu. Další pohyb doprava přináší dva půlcykly. Pohyb dolů přináší dva půlcykly horizontálně a půl cyklu vertikálně. Zdrojová data (8 × 8) jsou transformována na lineární kombinaci těchto 64 frekvenčních čtverců.

    MD-DCT-IV

    MD DCT-IV je jen rozšířením 1-D DCT-IV na M  dimenzionální doménu. 2-D DCT-IV matice nebo obrazu je dáno vztahem

    pro a

    Můžeme vypočítat MD DCT-IV pomocí metody pravidelných sloupců nebo můžeme pro rychlý a efektivní výpočet použít metodu polynomické transformace. Hlavní myšlenkou tohoto algoritmu je použít polynomickou transformaci k přímému převodu vícerozměrného DCT na řadu 1-D DCT. MD DCT-IV má také několik aplikací v různých oblastech.

    Výpočet

    Přestože by přímá aplikace těchto vzorců vyžadovala operace, je možné stejnou věc vypočítat pouze se složitostí rozdělením výpočtu podobně jako u rychlé Fourierovy transformace (FFT). Lze také vypočítat DCT pomocí FFT v kombinaci s kroky před a po zpracování. Obecně jsou metody pro výpočet DCT známé jako algoritmy pro rychlou kosinovou transformaci (FCT).

    Nejúčinnějšími algoritmy jsou v zásadě obvykle ty, které jsou specializovány přímo pro DCT, na rozdíl od používání běžného FFT plus dalších operací (výjimku viz níže). I „specializované“ algoritmy DCT (včetně všech těch, které dosahují nejnižšího známého počtu aritmetiky, alespoň pro velikosti dvou mocnin) jsou však obvykle úzce spjaty s algoritmy FFT-protože DCT jsou v podstatě DFT skutečných sudých dat, lze navrhnout rychlý algoritmus DCT tak, že vezmeme FFT a odstraníme nadbytečné operace díky této symetrii. To lze dokonce provést automaticky ( Frigo & Johnson 2005 ). Algoritmy založené na algoritmu Cooley -Tukey FFT jsou nejběžnější, ale lze použít i jakýkoli jiný algoritmus FFT. Algoritmus Winograd FFT například vede k algoritmům minimálního násobení pro DFT, i když obecně za cenu více přírůstků, a podobný algoritmus navrhl ( Feig, Winograd a červenec 1992 ) pro DCT. Protože všechny algoritmy pro DFT, DCT a podobné transformace spolu velmi úzce souvisí, jakékoli zlepšení algoritmů pro jednu transformaci teoreticky povede k okamžitému zisku i pro ostatní transformace ( Duhamel & Vetterli 1990 ).

    Zatímco algoritmy DCT, které používají nemodifikovaný FFT, mají často určitou teoretickou režii ve srovnání s nejlepšími specializovanými algoritmy DCT, první z nich má také výraznou výhodu: široce dostupné jsou vysoce optimalizované programy FFT. V praxi je tedy často snazší získat vysoký výkon pro obecné délky N pomocí algoritmů založených na FFT. Specializované algoritmy DCT naopak vidí široké využití pro transformace malých, pevných velikostí, jako je 8 × 8 DCT-II používaný při kompresi JPEG , nebo malé DCT (nebo MDCT), které se obvykle používají při kompresi zvuku. (Snížená velikost kódu může být také důvodem pro použití specializovaného DCT pro aplikace integrovaných zařízení.)

    Ve skutečnosti jsou dokonce i algoritmy DCT využívající obyčejný FFT někdy ekvivalentní prořezávání nadbytečných operací z většího FFT skutečných symetrických dat a dokonce mohou být optimální z pohledu aritmetických počtů. Například DCT typu II je ekvivalentní DFT velikosti se skutečnou sudou symetrií, jejíž sudé indexované prvky jsou nulové. Jednu z nejběžnějších metod pro výpočet pomocí FFT (např. Metoda používaná ve FFTPACK a FFTW ) popsali Narasimha & Peterson (1978) a Makhoul (1980) a tuto metodu lze zpětně vnímat jako jeden krok Alixový algoritmus Cooley – Tukey radix-4 v čase aplikovaný na „logický“ reálný sudý DFT odpovídající DCT-II. Protože prvky se sudým indexováním jsou nulové, je tento krok radix-4 přesně stejný jako krok s rozděleným radixem. Pokud je FFT následné velikosti reálných dat také prováděno algoritmem split-radix reálných dat (jako v Sorensen et al. (1987) ), pak výsledný algoritmus ve skutečnosti odpovídá tomu, co bylo dlouho nejnižší publikovaný počet aritmetik pro výkon- ze dvou DCT-II ( reálné aritmetické operace).

    Nedávné snížení počtu operací také používá FFT s reálnými daty. Na výpočtu DCT pomocí FFT z aritmetické perspektivy tedy není nic vnitřně špatného - někdy je jen otázkou, zda je odpovídající algoritmus FFT optimální. (Z praktického hlediska může být režie volání funkce při vyvolání samostatné rutiny FFT významná pro malé, ale toto je spíše implementace než algoritmická otázka, protože ji lze vyřešit rozvinutím nebo vložením.)

    Příklad IDCT

    Příklad zobrazující osm různých filtrů aplikovaných na testovací obrázek (vlevo nahoře) vynásobením jeho DCT spektra (vpravo nahoře) s každým filtrem.

    Zvažte tento obrázek ve stupních šedi 8x8 s velkým písmenem A.

    Původní velikost, zmenšená 10x (nejbližší soused), zmenšená 10x (bilineární).
    Základní funkce diskrétní kosinové transformace s odpovídajícími koeficienty (specifické pro náš obraz).
    DCT obrázku = .

    Každá základní funkce je vynásobena jejím koeficientem a poté je tento produkt přidán do konečného obrázku.

    Vlevo je konečný obrázek. Uprostřed je vážená funkce (vynásobená koeficientem), která je přidána do výsledného obrázku. Vpravo je aktuální funkce a odpovídající koeficient. Obrázky jsou zmenšeny (pomocí bilineární interpolace) faktorem 10 ×.

    Viz také

    Vysvětlivky

    Citace

    Další čtení

    externí odkazy