Diskret cosinustransform -

Discrete cosine transform

Flerdimensionella varianter av de olika DCT-typerna följer rakt av de endimensionella definitionerna: de är helt enkelt en separerbar produkt (motsvarande en sammansättning) av DCT: er längs varje dimension.

MD DCT-II

Till exempel utförs en tvådimensionell DCT-II av en bild eller en matris helt enkelt den endimensionella DCT-II, ovanifrån, utfört längs raderna och sedan längs kolumnerna (eller vice versa). Det vill säga, 2D DCT-II ges med formeln (utelämnar normalisering och andra skalfaktorer, som ovan):

${\ displaystyle {\ begin {align} X_ {k_ {1}, k_ {2}} & = \ sum _ {n_ {1} = 0}^{N_ {1} -1} \ left (\ sum _ { n_ {2} = 0}^{N_ {2} -1} x_ {n_ {1}, n_ {2}} \ cos \ vänster [{\ frac {\ pi} {N_ {2}}} \ vänster ( n_ {2}+{\ frac {1} {2}} \ höger) k_ {2} \ höger] \ höger) \ cos \ vänster [{\ frac {\ pi} {N_ {1}}} \ vänster ( n_ {1}+{\ frac {1} {2}} \ höger) k_ {1} \ höger] \\ & = \ sum _ {n_ {1} = 0}^{N_ {1} -1} \ summa _ {n_ {2} = 0}^{N_ {2} -1} x_ {n_ {1}, n_ {2}} \ cos \ vänster [{\ frac {\ pi} {N_ {1}}} \ vänster (n_ {1}+{\ frac {1} {2}} \ höger) k_ {1} \ höger] \ cos \ vänster [{\ frac {\ pi} {N_ {2}}} \ vänster ( n_ {2}+{\ frac {1} {2}} \ höger) k_ {2} \ höger]. \ slut {anpassad}}}$

Inversen av en flerdimensionell DCT är bara en separerbar produkt av inverserna av motsvarande endimensionella DCT: er (se ovan), t.ex. de endimensionella inverser som appliceras längs en dimension i taget i en radkolumnalgoritm.

Den 3-D DCT-II är endast en förlängning av 2-D DCT-II i tredimensionellt rum och matematiskt kan beräknas genom formeln

${\ displaystyle X_ {k_ {1}, k_ {2}, k_ {3}} = \ sum _ {n_ {1} = 0}^{N_ {1} -1} \ sum _ {n_ {2} = 0}^{N_ {2} -1} \ sum _ {n_ {3} = 0}^{N_ {3} -1} x_ {n_ {1}, n_ {2}, n_ {3}} \ cos \ vänster [{\ frac {\ pi} {N_ {1}}} \ vänster (n_ {1}+{\ frac {1} {2}} \ höger) k_ {1} \ höger] \ cos \ vänster [ {\ frac {\ pi} {N_ {2}}} \ vänster (n_ {2}+{\ frac {1} {2}} \ höger) k_ {2} \ höger] \ cos \ vänster [{\ frac {\ pi} {N_ {3}}} \ vänster (n_ {3}+{\ frac {1} {2}} \ höger) k_ {3} \ höger], \ quad {\ text {för}} k_ {i} = 0,1,2, \ dots, N_ {i} -1.}$

Inversen av 3-D DCT-II är 3-D DCT-III och kan beräknas utifrån formeln som ges av

${\ displaystyle x_ {n_ {1}, n_ {2}, n_ {3}} = \ sum _ {k_ {1} = 0}^{N_ {1} -1} \ sum _ {k_ {2} = 0}^{N_ {2} -1} \ sum _ {k_ {3} = 0}^{N_ {3} -1} X_ {k_ {1}, k_ {2}, k_ {3}} \ cos \ vänster [{\ frac {\ pi} {N_ {1}}} \ vänster (n_ {1}+{\ frac {1} {2}} \ höger) k_ {1} \ höger] \ cos \ vänster [ {\ frac {\ pi} {N_ {2}}} \ vänster (n_ {2}+{\ frac {1} {2}} \ höger) k_ {2} \ höger] \ cos \ vänster [{\ frac {\ pi} {N_ {3}}} \ vänster (n_ {3}+{\ frac {1} {2}} \ höger) k_ {3} \ höger], \ quad {\ text {för}} n_ {i} = 0,1,2, \ dots, N_ {i} -1.}$

Tekniskt sett är beräkningen av en två-, tre- (eller -multi) dimensionell DCT med sekvenser av endimensionella DCT längs varje dimension känd som en rad-kolumnalgoritm . Liksom med flerdimensionella FFT -algoritmer finns det dock andra metoder för att beräkna samma sak medan beräkningarna utförs i en annan ordning (dvs sammanfogning/kombination av algoritmerna för de olika dimensionerna). På grund av den snabba tillväxten i applikationerna baserade på 3D-DCT, utvecklas flera snabba algoritmer för beräkning av 3D-DCT-II. Vector-Radix-algoritmer tillämpas för beräkning av MD DCT för att minska beräkningskomplexiteten och för att öka beräkningshastigheten. För att beräkna 3D-DCT-II effektivt, utvecklades en snabb algoritm, Vector-Radix Decimation in Frequency (VR DIF) algoritm.

3-D DCT-II VR DIF

För att kunna tillämpa VR DIF -algoritmen ska inmatningsdata formuleras och ordnas om enligt följande. Transformstorleken N × N × N antas vara 2.

De fyra grundläggande stadierna för beräkning av 3D-DCT-II med VR DIF-algoritm.

${\ displaystyle {\ begin {array} {lcl} {\ tilde {x}} (n_ {1}, n_ {2}, n_ {3}) = x (2n_ {1}, 2n_ {2}, 2n_ { 3}) \\ {\ tilde {x}} (n_ {1}, n_ {2}, N-n_ {3} -1) = x (2n_ {1}, 2n_ {2}, 2n_ {3}+ 1) \\ {\ tilde {x}} (n_ {1}, N-n_ {2} -1, n_ {3}) = x (2n_ {1}, 2n_ {2}+1,2n_ {3} ) \\ {\ tilde {x}} (n_ {1}, N-n_ {2} -1, N-n_ {3} -1) = x (2n_ {1}, 2n_ {2}+1,2n_ {3} +1) \\ {\ tilde {x}} (N-n_ {1} -1, n_ {2}, n_ {3}) = x (2n_ {1}+1,2n_ {2}, 2n_ {3}) \\ {\ tilde {x}} (N-n_ {1} -1, n_ {2}, N-n_ {3} -1) = x (2n_ {1}+1,2n_ { 2}, 2n_ {3} +1) \\ {\ tilde {x}} (N-n_ {1} -1, N-n_ {2} -1, n_ {3}) = x (2n_ {1} +1,2n_ {2}+1,2n_ {3}) \\ {\ tilde {x}} (N-n_ {1} -1, N-n_ {2} -1, N-n_ {3}- 1) = x (2n_ {1}+1,2n_ {2}+1,2n_ {3} +1) \\\ end {array}}}$

var

${\ displaystyle 0 \ leq n_ {1}, n_ {2}, n_ {3} \ leq {\ frac {N} {2}}-1}$

Figuren till intilliggande visar de fyra stegen som är inblandade i beräkningen av 3-D DCT-II med VR DIF-algoritm. Det första steget är 3-D-ordningen med hjälp av indexmappningen som illustreras av ovanstående ekvationer. Det andra steget är fjärilsberäkningen. Varje fjäril beräknar åtta poäng tillsammans som visas i figuren precis nedan, var .

${\ displaystyle c (\ varphi _ {i}) = \ cos (\ varphi _ {i})}}$

Den ursprungliga 3D-DCT-II kan nu skrivas som

${\ displaystyle X (k_ {1}, k_ {2}, k_ {3}) = \ sum _ {n_ {1} = 1}^{N-1} \ sum _ {n_ {2} = 1}^ {N-1} \ sum _ {n_ {3} = 1}^{N-1} {\ tilde {x}} (n_ {1}, n_ {2}, n_ {3}) \ cos (\ varphi k_ {1}) \ cos (\ varphi k_ {2}) \ cos (\ varphi k_ {3})}}$

var

${\ displaystyle \ varphi _ {i} = {\ frac {\ pi} {2N}} (4N_ {i} +1), {\ text {och}} i = 1,2,3.}$

Om de jämna och udda delarna av och och beaktas kan den allmänna formeln för beräkning av 3D-DCT-II uttryckas som

${\ displaystyle k_ {1}, k_ {2}}$

Det enda fjärilsstadiet i VR DIF -algoritmen.

${\ displaystyle X (k_ {1}, k_ {2}, k_ {3}) = \ sum _ {n_ {1} = 1}^{{\ tfrac {N} {2}}-1} \ sum _ {n_ {2} = 1}^{{\ tfrac {N} {2}}-1} \ sum _ {n_ {1} = 1}^{{\ tfrac {N} {2}}-1} { \ tilde {x}} _ {ijl} (n_ {1}, n_ {2}, n_ {3}) \ cos (\ varphi (2k_ {1}+i) \ cos (\ varphi (2k_ {2}+) j) \ cos (\ varphi (2k_ {3}+l))}$

var

${\ displaystyle {\ tilde {x}} _ {ijl} (n_ {1}, n_ {2}, n_ {3}) = {\ tilde {x}} (n_ {1}, n_ {2}, n_ {3})+(-1)^{l} {\ tilde {x}} \ vänster (n_ {1}, n_ {2}, n_ {3}+{\ frac {n} {2}} \ höger )}}$

${\ displaystyle +(-1)^{j} {\ tilde {x}} \ vänster (n_ {1}, n_ {2} +{\ frac {n} {2}}, n_ {3} \ höger) +(-1)^{j+l} {\ tilde {x}} \ vänster (n_ {1}, n_ {2}+{\ frac {n} {2}}, n_ {3}+{\ frac {n} {2}} \ höger)}$

${\ displaystyle +(-1)^{i} {\ tilde {x}} \ vänster (n_ {1} +{\ frac {n} {2}}, n_ {2}, n_ {3} \ höger) +(-1)^{i+j} {\ tilde {x}} \ vänster (n_ {1}+{\ frac {n} {2}}+{\ frac {n} {2}}, n_ { 2}, n_ {3} \ höger)}$

${\ displaystyle+(-1)^{i+l} {\ tilde {x}} \ vänster (n_ {1}+{\ frac {n} {2}}, n_ {2}, n_ {3}+ {\ frac {n} {3}} \ höger)}$

${\ displaystyle+(-1)^{i+j+l} {\ tilde {x}} \ vänster (n_ {1}+{\ frac {n} {2}}, n_ {2}+{\ frac {n} {2}}, n_ {3}+{\ frac {n} {2}} \ höger) {\ text {där}} i, j, l = 0 {\ text {eller}} 1.}$

Aritmetisk komplexitet

Hela 3D-beräkningen av DCT behöver steg, och varje steg innefattar fjärilar. Hela 3D-DCT kräver att fjärilar beräknas. Varje fjäril kräver sju verkliga multiplikationer (inklusive triviala multiplikationer) och 24 riktiga tillägg (inklusive triviala tillägg). Därför är det totala antalet reella multiplikationer som behövs för detta steg och det totala antalet reella tillägg, dvs inklusive posttillägg (rekursiva tillägg) som kan beräknas direkt efter fjärilssteget eller efter bitomvändningssteget ges av

${\ displaystyle ~ [\ log _ {2} N] ~}$

Den konventionella metoden för att beräkna MD-DCT-II använder en Row-Column-Frame (RCF) metod som är beräkningsmässigt komplex och mindre produktiv på de mest avancerade senaste hårdvaruplattformarna. Antalet multiplikationer som krävs för att beräkna VR DIF -algoritm jämfört med RCF -algoritm är ganska många. Antalet multiplikationer och tillägg som är involverade i RCF tillvägagångssätt ges av och respektive. Av tabell 1 framgår att det totala antalet

${\ displaystyle ~ \ left [{\ frac {3} {2}} N^{3} \ log _ {2} N \ right] ~}$

TABELL 1 Jämförelse av VR DIF & RCF-algoritmer för beräkning av 3D-DCT-II

Transform Storlek	3D VR Mults	RCF Mults	3D VR -tillägg	RCF lägger till
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

av multiplikationer associerade med 3D-DCT VR-algoritmen är mindre än den som associeras med RCF-metoden med mer än 40%. Dessutom innefattar RCF -metoden matriotransponering och mer indexering och databyte än den nya VR -algoritmen. Detta gör 3-D DCT VR-algoritmen mer effektiv och bättre lämpad för 3D-applikationer som involverar 3D-DCT-II, till exempel videokomprimering och andra 3D-bildbehandlingsprogram.

Den viktigaste övervägningen vid val av en snabb algoritm är att undvika beräkningsmässiga och strukturella komplexiteter. I takt med att tekniken för datorer och DSP utvecklas, blir körtiden för aritmetiska operationer (multiplikationer och tillägg) mycket snabb, och regelbunden beräkningsstruktur blir den viktigaste faktorn. Därför, även om den ovan föreslagna 3D-algoritmen inte uppnår den teoretiska nedre gränsen för antalet multiplikationer, har den en enklare beräkningsstruktur jämfört med andra 3D-algoritmer för DCT. Den kan implementeras på plats med en enda fjäril och har egenskaperna hos Cooley-Tukey FFT-algoritmen i 3D. Därför presenterar 3D-VR ett bra val för att minska aritmetiska operationer vid beräkningen av 3D-DCT-II, samtidigt som den behåller den enkla strukturen som kännetecknar fjärilstil Cooley – Tukey FFT-algoritmer .

Tvådimensionella DCT-frekvenser från JPEG DCT

av dessa 64 frekvenskvadrater.

${\ displaystyle (~ N_ {1} = N_ {2} = 8 ~)}$

MD-DCT-IV

 dimensionell domän. 2-D DCT-IV för en matris eller en bild ges av

${\ displaystyle X_ {k, \ ell} = \ sum _ {n = 0}^{N-1} \; \ sum _ {m = 0}^{M-1} \ x_ {n, m} \ cos \ vänster (\ {\ frac {\, (2m+1) (2k+1) \ \ pi \,} {4N}} \ \ höger) \ cos \ vänster (\ {\ frac {\, (2n+1 ) (2 \ ell +1) \ \ pi \,} {4M}} \ \ höger) ~,}$

för och

${\ displaystyle ~~ k = 0, \ 1, \ 2 \ \ ldots \ N-1 ~~}$

Vi kan beräkna MD DCT-IV med den vanliga radkolumnmetoden eller så kan vi använda metoden för polynomtransformering för snabb och effektiv beräkning. Huvudidén med denna algoritm är att använda Polynomial Transform för att omvandla den flerdimensionella DCT: n direkt till en serie 1-D DCT: er. MD DCT-IV har också flera applikationer inom olika områden.

Beräkning

(FFT). Man kan också beräkna DCT via FFT i kombination med för- och efterbehandlingssteg. I allmänhet är metoder för att beräkna DCT kända som snabb cosinustransform (FCT) algoritmer.

${\ displaystyle ~ {\ mathcal {O}} (N^{2}) ~}$

${\ displaystyle ~ {\ mathcal {O}} (N) ~}$

), matchar den resulterande algoritmen faktiskt det som länge var det lägsta publicerade aritmetiska antalet för effekt- av två DCT-II ( real-aritmetiska operationer).

${\ displaystyle ~ 4N ~}$

En färsk minskning av antalet operationer för att även använda en FFT med realdata. Så det finns inget som är egentligen dåligt med att beräkna DCT via en FFT ur ett aritmetiskt perspektiv - det är ibland bara en fråga om huruvida motsvarande FFT -algoritm är optimal. (I praktiken kan funktionssamtalskostnaderna för att åberopa en separat FFT-rutin vara betydande för små, men det här är en implementering snarare än en algoritmisk fråga eftersom det kan lösas genom att rulla ut eller infoga.)

${\ displaystyle ~ {\ tfrac {17} {9}} N \ log _ {2} N+{\ mathcal {O}} (N)}$

Exempel på IDCT

Ett exempel som visar åtta olika filter applicerade på en testbild (uppe till vänster) genom att multiplicera dess DCT -spektrum (uppe till höger) med varje filter.

Tänk på denna 8x8 gråskalebild av stor bokstav A.

Originalstorlek, skalad 10x (närmaste granne), skalad 10x (bilinjär).

Grundfunktioner för den diskreta cosinustransformationen med motsvarande koefficienter (specifika för vår bild).
Bildens DCT = .

${\ displaystyle {\ begin {bmatrix} 6.1917 & -0.3411 & 1.2418 & 0.1492 & 0.1583 & 0.2742 & -0.0724 & 0.0561 \\ 0.2205 & 0.0214 & 0.4503 & 0.3947 & -0.7846 & -0.4391 & 0.1001 & -0.2554 \\ 1.0423 & 0.2214 & -1.0017 & -0.2720 & 0.0789 & -0.1952 & 0.2801 & 0.4713 \\-0.2340 & -0.0392 & -0.2617 & -0.2866 & 0.6351 & 0.3501 & -0.1433 & 0.3550 \\ 0.2750 & 0.0226 & 0.1229 & 0. 2183 & -0.2583 & -0.0742 & -0.2042 & -0.5906 \\ 0.0653 & 0.0428 & -0.4721 & -0.2905 & 0.4745 & 0.2875 & -0.0284 & -0.1311 \\ 0.3169 & 0.0541 & -0.1033 & -0.0225 & -0.0056 & 0.1017 & -0.1650 & -0.1500 \\-0.2970 & -0.0627 & 0.1960 & 0.0644 & -0.1136 & -0.1031 & 0.1887 & 0.1444 \\\ end {bmatrix}}}$

Varje basfunktion multipliceras med dess koefficient och sedan läggs denna produkt till den slutliga bilden.

Till vänster är den sista bilden. I mitten är den viktade funktionen (multiplicerad med en koefficient) som läggs till den slutliga bilden. Till höger är den aktuella funktionen och motsvarande koefficient. Bilderna skalas (med hjälp av bilinjär interpolering) med faktor 10 ×.

Se även

• Diskret wavelet -transform
• JPEG#Diskret cosinustransform - Innehåller ett potentiellt lättare att förstå exempel på DCT -transformation
• Lista över Fourier-relaterade transformationer
• Modifierad diskret cosinustransform

Förklarande anteckningar

Citat

Vidare läsning

• Narasimha, M .; Peterson, A. (juni 1978). "Om beräkningen av den diskreta kosinustransformen". IEEE -transaktioner om kommunikation . 26 (6): 934–936. doi : 10.1109/TCOM.1978.1094144 .
• Makhoul, J. (februari 1980). "En snabb cosinustransform i en och två dimensioner". IEEE -transaktioner om akustik, tal och signalbehandling . 28 (1): 27–34. doi : 10.1109/TASSP.1980.1163351 .
• Sorensen, H .; Jones, D .; Heideman, M .; Burrus, C. (juni 1987). "Verkligt värderade snabba Fourier-transformeringsalgoritmer". IEEE -transaktioner om akustik, tal och signalbehandling . 35 (6): 849–863. CiteSeerX  
  10.1.1.205.4523
  . doi : 10.1109/TASSP.1987.1165220 .
• Plonka, G .; Tasche, M. (januari 2005). "Snabba och numeriskt stabila algoritmer för diskreta cosinustransformationer" . Linjär algebra och dess tillämpningar . 394 (1): 309–345. doi :
  10.1016/j.laa.2004.07.015
  .
• Duhamel, P .; Vetterli, M. (april 1990). "Snabba Fourier -transformationer: En studieöversikt och en toppmodern teknik" . Signalbehandling (skickat manuskript). 19 (4): 259–299. doi : 10.1016/0165-1684 (90) 90158-U .
• Ahmed, N. (januari 1991). "Hur jag kom på den diskreta kosinustransformen" . Digital signalbehandling . 1 (1): 4–9. doi : 10.1016/1051-2004 (91) 90086-Z .
• Feig, E .; Winograd, S. (september 1992). "Snabba algoritmer för den diskreta cosinustransformen". IEEE -transaktioner om signalbehandling . 40 (9): 2174–2193. Bibcode : 1992ITSP ... 40.2174F . doi : 10.1109/78.157218 .
• Malvar, Henrique (1992), Signal Processing with Lapped Transforms , Boston: Artech House, ISBN 978-0-89006-467-2
• Martucci, SA (maj 1994). "Symmetrisk krökning och de diskreta sinus- och cosinustransformerna". IEEE -transaktioner om signalbehandling . 42 (5): 1038–1051. Bibcode : 1994ITSP ... 42.1038M . doi : 10.1109/78.295213 .
• Oppenheim, Alan; Schafer, Ronald; Buck, John (1999),
  Discrete-Time Signal Processing
  (2nd ed.), Upper Saddle River, NJ: Prentice Hall, ISBN 978-0-13-754920-7
• Frigo, M .; Johnson, SG (februari 2005). "Design och implementering av FFTW3"
  (PDF)
  . IEEE: s förfaranden . 93 (2): 216–231. CiteSeerX  
  10.1.1.66.3097
  . doi : 10.1109/JPROC.2004.840301 . S2CID  6644892 .
• Boussakta, Said .; Alshibami, Hamoud O. (april 2004). "Snabb algoritm för 3D-DCT-II"
  (PDF)
  . IEEE -transaktioner om signalbehandling . 52 (4): 992–1000. Bibcode : 2004ITSP ... 52..992B . doi : 10.1109/TSP.2004.823472 . S2CID  3385296 .
• Cheng, LZ; Zeng, YH (2003). "Ny snabb algoritm för flerdimensionell typ-IV DCT". IEEE -transaktioner om signalbehandling . 51 (1): 213–220. doi : 10.1109/TSP.2002.806558 .
• Wen-Hsiung Chen; Smith, C .; Fralick, S. (september 1977). "En snabb beräkningsalgoritm för den diskreta kosinustransformen". IEEE -transaktioner om kommunikation . 25 (9): 1004–1009. doi : 10.1109/TCOM.1977.1093941 .
• Tryck, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Avsnitt 12.4.2. Cosine Transform" , Numerical Recipes: The Art of Scientific Computing (3: e upplagan), New York: Cambridge University Press, ISBN 978-0-521-88068-8

externa länkar

• Syed Ali Khayam: The Discrete Cosine Transform (DCT): Theory and Application
• Implementering av MPEG-heltals approximation av 8x8 IDCT (ISO/IEC 23002-2)
• Matteo Frigo och Steven G. Johnson : FFTW , http://www.fftw.org/ . Ett gratis ( GPL ) C-bibliotek som kan beräkna snabba DCT: er (typ I-IV) i en eller flera dimensioner, av godtycklig storlek.
• Takuya Ooura: FFT-paket för allmänna ändamål, http://www.kurims.kyoto-u.ac.jp/~ooura/fft.html . Gratis C & FORTRAN -bibliotek för beräkning av snabba DCT: er (typ II – III) i en, två eller tre dimensioner, effekt på 2 storlekar.
• Tim Kientzle: Snabba algoritmer för beräkning av 8-punkts DCT och IDCT, http://drdobbs.com/parallel/184410889 .
• LTFAT är en gratis Matlab/Octave-verktygslåda med gränssnitt för FFTW-implementering av DCT och DST av typ I-IV.