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
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í.
- Audio zpracování signálu - kódování zvuku , audio komprese dat (ztrátová a bezztrátový), prostorový zvuk , akustické echo a zrušení zpětné vazby , foném uznání, zrušení time-domain aliasing (TDAC)
- Biometrie - orientace otisků prstů , systémy rozpoznávání obličeje , biometrické vodoznaky , biometrické vodoznaky založené na otiscích prstů, identifikace/rozpoznávání otisku dlaně
-
Počítače a internet - World Wide Web , sociální média , internetové video
- Snížení využití šířky pásma sítě
- Spotřební elektronika - multimediální systémy, multimediální telekomunikační zařízení, spotřební zařízení
- Kryptografie - šifrování , steganografie , ochrana autorských práv
-
Komprese dat - transformační kódování , ztrátová komprese , bezeztrátová komprese
- Operace kódování - kvantování , vážení vjemů, kódování entropie , variabilní kódování
- Digitální média - digitální distribuce
- Detekce padělání
- Geofyzikální přechodová elektromagnetika (přechodová EM)
-
Obrázky - identifikace umělce , míra zaostření a rozmazání , extrakce funkcí
- Formátování barev - formátování jasu a barevných rozdílů, barevné formáty (například YUV444 a YUV411 ), dekódovací operace, jako je inverzní operace mezi barevnými formáty zobrazení ( YIQ , YUV , RGB )
- Digitální zobrazování - digitální obrázky , digitální fotoaparáty , digitální fotografie , zobrazování s vysokým dynamickým rozsahem (zobrazování HDR)
- Komprese obrazu - formáty obrazových souborů , vícenásobná komprese obrazu , progresivní přenos obrazu
- Zpracování obrazu - digitální zpracování obrazu , analýza obrazu , na základě obsahu získávání obrazu , detekce roh , směrové blocích reprezentace obrazu , detekce hran , vylepšení obrazu , image fusion , segmentace obrazu , interpolace , obraz šum odhad úrovně, zrcadlení, rotace, stačí -profil znatelného zkreslení (JND), časoprostorové maskovací efekty, fovelované zobrazování
- Hodnocení kvality obrazu -metrika degradace kvality založená na DCT (DCT QM)
- Rekonstrukce obrazu - automatická kontrola směrových textur , obnova obrazu , malování , vizuální obnova
-
Lékařská technologie
- Elektrokardiografie (EKG) - vektorová kardiografie (VCG)
- Lékařské zobrazování - lékařská komprese obrazu, fúze obrazu, vodoznak, klasifikace komprese nádorů mozku
- Rozpoznávání vzorů
- Extrakce oblasti zájmu (ROI)
-
Zpracování signálu - digitální zpracování signálu , signálové procesory digitálních signálů (DSP), DSP software , multiplexování , signalizační , řídicí signály, analogově-digitální konverzi (ADC), tlakové vzorkování , DCT pyramidy zakrytí chyby , podsampluje , převzorkování , signál-to- odhad poměru šumu (SNR), transmux , Wienerův filtr
- Komplexní analýza funkcí
- DCT filtrování
- Digitální kino - digitální kamera , digitální filmové kamery , střih videa , editace filmu , Dolby Digital audio
- Digitální televize (DTV) -digitální televizní vysílání , televize se standardním rozlišením (SDTV), televize s vysokým rozlišením (HDTV), kodéry /dekodéry HDTV , ultra HDTV (UHDTV)
- Digitální video - digitální univerzální disk (DVD), video s vysokým rozlišením (HD)
- Video Coding - komprese videa , Video Coding norem , odhad pohybu , kompenzace pohybu , inter-rámec predikčních, pohybové vektory , kódující 3D video , lokální detekce narušení pravděpodobnost (LDDP) modelu, pohybující se v detekci objektů , Multiview Video Coding (MVC)
- Zpracování videa - analýza pohybu, analýza pohybu 3D-DCT, analýza obsahu videa , extrakce dat , procházení videa , profesionální produkce videa
- Mobilní zařízení - mobilní telefony , smartphony , videotelefony
- Radiofrekvenční (RF) technologie - RF inženýrství , clonová pole , tvarování paprsků , digitální aritmetické obvody , směrové snímání , vesmírné zobrazování
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
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.
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.
- 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
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
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ů .
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
Zvažte tento obrázek ve stupních šedi 8x8 s velkým písmenem A.
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.
Viz také
- Diskrétní vlnková transformace
- JPEG#Diskrétní kosinová transformace - obsahuje potenciálně snáze pochopitelný příklad transformace DCT
- Seznam Fourierových transformací
- Upravená diskrétní kosinová transformace
Vysvětlivky
Citace
Další čtení
- Narasimha, M .; Peterson, A. (červen 1978). „O výpočtu diskrétní kosinové transformace“. Transakce IEEE v komunikaci . 26 (6): 934–936. doi : 10.1109/TCOM.1978.1094144 .
- Makhoul, J. (únor 1980). „Rychlá kosinová transformace v jedné a dvou dimenzích“. Transakce IEEE v oblasti akustiky, řeči a zpracování signálu . 28 (1): 27–34. doi : 10.1109/TASSP.1980.1163351 .
- Sorensen, H .; Jones, D .; Heideman, M .; Burrus, C. (červen 1987). „Skutečné algoritmy rychlé Fourierovy transformace“. Transakce IEEE v oblasti akustiky, řeči a zpracování signálu . 35 (6): 849–863. CiteSeerX 10.1.1.205.4523 . doi : 10.1109/TASSP.1987.1165220 .
- Plonka, G .; Tasche, M. (leden 2005). „Rychlé a numericky stabilní algoritmy pro diskrétní kosinové transformace“ . Lineární algebra a její aplikace . 394 (1): 309–345. doi : 10.1016/j.laa.2004.07.015 .
- Duhamel, P .; Vetterli, M. (duben 1990). „Rychlé Fourierovy transformace: Tutoriálový přehled a současný stav“ . Zpracování signálu (předložený rukopis). 19 (4): 259–299. doi : 10,1016/0165-1684 (90) 90158-U .
- Ahmed, N. (leden 1991). „Jak jsem přišel na diskrétní kosinovou transformaci“ . Digitální zpracování signálu . 1 (1): 4–9. doi : 10,1016/1051-2004 (91) 90086-Z .
- Feig, E .; Winograd, S. (září 1992). „Rychlé algoritmy pro diskrétní kosinovou transformaci“. Transakce IEEE při zpracování signálu . 40 (9): 2174–2193. Bibcode : 1992ITSP ... 40.2174F . doi : 10,1109/78,157218 .
- Malvar, Henrique (1992), Zpracování signálu s lapovanými transformacemi , Boston: Artech House, ISBN 978-0-89006-467-2
- Martucci, SA (květen 1994). „Symetrická konvoluce a diskrétní sinusové a kosinové transformace“. Transakce IEEE při zpracování signálu . 42 (5): 1038–1051. Bibcode : 1994ITSP ... 42,1038 mil . doi : 10,1109/78,295213 .
- Oppenheim, Alan; Schafer, Ronald; Buck, John (1999), zpracování signálu diskrétním časem (2. vydání), Upper Saddle River, New Jersey: Prentice Hall, ISBN 978-0-13-754920-7
- Frigo, M .; Johnson, SG (únor 2005). „Návrh a implementace FFTW3“ (PDF) . Sborník IEEE . 93 (2): 216–231. CiteSeerX 10.1.1.66.3097 . doi : 10.1109/JPROC.2004.840301 . S2CID 6644892 .
- Boussakta, Řekl .; Alshibami, Hamoud O. (duben 2004). „Rychlý algoritmus pro 3-D DCT-II“ (PDF) . Transakce IEEE při zpracování signálu . 52 (4): 992–1000. Bibcode : 2004ITSP ... 52..992B . doi : 10.1109/TSP.2004.823472 . S2CID 3385296 .
- Cheng, LZ; Zeng, YH (2003). „Nový rychlý algoritmus pro vícerozměrný DCT typu IV“. Transakce IEEE při zpracování signálu . 51 (1): 213–220. doi : 10.1109/TSP.2002.806558 .
- Wen-Hsiung Chen; Smith, C .; Fralick, S. (září 1977). „Rychlý výpočetní algoritmus pro diskrétní kosinovou transformaci“. Transakce IEEE v komunikaci . 25 (9): 1004–1009. doi : 10.1109/TCOM.1977.1093941 .
- Stiskněte, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), „Oddíl 12.4.2. Kosinová transformace“ , Numerical Recipes: The Art of Scientific Computing (3. vyd.), New York: Cambridge University Press, ISBN 978-0-521-88068-8
externí odkazy
- Syed Ali Khayam: The Discrete Cosine Transform (DCT): Theory and Application
- Implementace MPEG celočíselné aproximace 8x8 IDCT (ISO/IEC 23002-2)
- Matteo Frigo a Steven G. Johnson : FFTW , http://www.fftw.org/ . Bezplatná ( GPL ) C knihovna, která dokáže vypočítat rychlé DCT (typy I-IV) v jedné nebo více dimenzích libovolné velikosti.
- Takuya Ooura: Balíček FFT pro obecné účely, http://www.kurims.kyoto-u.ac.jp/~ooura/fft.html . Bezplatné knihovny C & FORTRAN pro výpočet rychlých DCT (typy II – III) v jednom, dvou nebo třech rozměrech, výkon 2 velikostí.
- Tim Kientzle: Rychlé algoritmy pro výpočet 8bodových DCT a IDCT, http://drdobbs.com/parallel/184410889 .
- LTFAT je bezplatný soubor nástrojů Matlab/Octave s rozhraními pro implementaci FFTW DCT a DST typu I-IV.