Discrete cosine transform: Difference between revisions

Revision as of 16:06, 17 May 2024

Revision as of 04:04, 26 May 2024

Line 308:

This transform is exactly equivalent (up to an overall scale factor of 2) to a [[Discrete Fourier transform|DFT]] of <math>4N</math> real inputs of even symmetry where the even-indexed elements are zero. That is, it is half of the [[Discrete Fourier transform|DFT]] of the <math>4N</math> inputs <math> y_n ,</math> where <math> y_{2n} = 0 ,</math> <math> y_{2n+1} = x_n </math> for <math> 0 \leq n < N ,</math> <math> y_{2N} = 0 ,</math> and <math> y_{4N-n} = y_n </math> for <math> 0 < n < 2N .</math> DCT-II transformation is also possible using 2{{mvar|N}} signal followed by a multiplication by half shift. This is demonstrated by [[John Makhoul|Makhoul]].

Some authors further multiply the <math> X_0 </math> term by <math> 1/\sqrt{N\,} \, </math> and multiply the rest of the matrix by an overall scale factor of <math display="inline">\sqrt{{2}/{N}}</math> (see below for the corresponding change in DCT-III). This makes the DCT-II matrix [[orthogonal matrix|orthogonal]], but breaks the direct correspondence with a real-even [[Discrete Fourier transform|DFT]] of half-shifted input. This is the normalization used by [[Matlab]], for example, see.<ref>{{cite web |url=https://www.mathworks.com/help/signal/ref/dct.html |title=Discrete cosine transform - MATLAB dct |website=www.mathworks.com |access-date=2019-07-11}}</ref> In many applications, such as [[JPEG]], the scaling is arbitrary because scale factors can be combined with a subsequent computational step (e.g. the [[Quantization (signal processing)|quantization]] step in JPEG<ref>{{cite book |isbn=9780442012724 |title=JPEG: Still Image Data Compression Standard |last1=Pennebaker |first1=William B. |last2=Mitchell |first2=Joan L. |date=31 December 1992|publisher=Springer }}</ref>), and a scaling can be chosen that allows the DCT to be computed with fewer multiplications.<ref>{{cite journal |url=https://search.ieice.org/bin/summary.php?id=e71-e_11_1095 |first1=Y. |last1=Arai |first2=T. |last2=Agui |first3=M. |last3=Nakajima |title=A fast DCT-SQ scheme for images |journal=IEICE Transactions |volume=71 |issue=11 |pages= 1095–1097 |year=1988}}</ref><ref>{{cite journal |doi=10.1016/j.sigpro.2008.01.004 |title=Type-II/III DCT/DST algorithms with reduced number of arithmetic operations |year=2008 |last1=Shao |first1=Xuancheng |last2=Johnson |first2=Steven G. |journal=Signal Processing |volume=88 |issue=6 |pages=1553–1564 |arxiv=cs/0703150 |bibcode=2008SigPr..88.1553S |s2cid=986733}}</ref>

The DCT-II implies the boundary conditions: <math> x_n </math> is even around <math> n = -1/2 </math> and even around <math> n = N - 1/2 \,;</math> <math> X_k </math> is even around <math> k = 0 </math> and odd around <math> k = N .</math>

Line 518:

}}).

A recent reduction in the operation count to <math>~ \tfrac{17}{9} N \log_2 N + \mathcal{O}(N)</math> also uses a real-data FFT.<ref>{{cite journal |doi=10.1016/j.sigpro.2008.01.004 |title=Type-II/III DCT/DST algorithms with reduced number of arithmetic operations |journal=Signal Processing |volume=88 |issue=6 |pages=1553–1564 |year=2008 |last1=Shao |first1=Xuancheng |last2=Johnson |first2=Steven G. |arxiv=cs/0703150 |bibcode=2008SigPr..88.1553S |s2cid=986733}}</ref> So, there is nothing intrinsically bad about computing the DCT via an FFT from an arithmetic perspective – it is sometimes merely a question of whether the corresponding FFT algorithm is optimal. (As a practical matter, the function-call overhead in invoking a separate FFT routine might be significant for small <math>~ N ~,</math> but this is an implementation rather than an algorithmic question since it can be solved by unrolling or inlining.)

==Example of IDCT==

Line 557:

{{reflist|refs=

<ref name="Ahmed">{{cite journal |last=Ahmed |first=Nasir |author-link=N. Ahmed |title=How I Came Up With the Discrete Cosine Transform |journal=[[Digital Signal Processing (journal)|Digital Signal Processing]] |date=January 1991 |volume=1 |issue=1 |pages=4–5 |doi=10.1016/1051-2004(91)90086-Z |bibcode=1991DSP.....1....4A |url=https://www.cse.iitd.ac.in/~pkalra/col783-2017/DCT-History.pdf}}</ref>

<ref name="Stankovic">{{cite journal | last1 = Stanković | first1 = Radomir S. | last2 = Astola | first2 = Jaakko T. |title = Reminiscences of the Early Work in DCT: Interview with K.R. Rao | journal = Reprints from the Early Days of Information Sciences | publisher = Tampere International Center for Signal Processing | date = 2012 | volume = 60 | url = https://ethw.org/w/images/1/19/Report-60.pdf | access-date = 2021-12-30 | archive-url = https://web.archive.org/web/20211230214050/https://ethw.org/w/images/1/19/Report-60.pdf | archive-date = 2021-12-30 | url-status = live | issn = 1456-2774 | isbn = 978-9521528187 | via = [[Engineering and Technology History Wiki|ETHW]] | df = dmy-all}}</ref>

Line 619:

* {{Cite journal | last1 = Sorensen | first1 = H. | last2 = Jones | first2 = D. | last3 = Heideman | first3 = M. | last4 = Burrus | first4 = C. | title = Real-valued fast Fourier transform algorithms | doi = 10.1109/TASSP.1987.1165220 | journal = IEEE Transactions on Acoustics, Speech, and Signal Processing | volume = 35 | issue = 6 | pages = 849–863| date=June 1987 | citeseerx = 10.1.1.205.4523 }}

* {{Cite journal |last1=Plonka |first1=G. |author1-link= Gerlind Plonka |last2=Tasche|first2=M. |title=Fast and numerically stable algorithms for discrete cosine transforms |journal=Linear Algebra and Its Applications |volume=394 |issue=1 |pages=309–345 |date=January 2005 |doi=10.1016/j.laa.2004.07.015 |doi-access=free }}

* {{Cite journal | last1 = Duhamel | first1 = P. | last2 = Vetterli | first2 = M. | doi = 10.1016/0165-1684(90)90158-U | title = Fast fourier transforms: A tutorial review and a state of the art | journal = Signal Processing | volume = 19 | issue = 4 | pages = 259–299| date=April 1990 | bibcode = 1990SigPr..19..259D | url = http://infoscience.epfl.ch/record/59946 | type = Submitted manuscript }}

* {{Cite journal | last1 = Ahmed | first1 = N. | author-link1 = N. Ahmed| doi = 10.1016/1051-2004(91)90086-Z | title = How I came up with the discrete cosine transform | journal = Digital Signal Processing | volume = 1 | issue = 1| pages = 4–9 | date=January 1991 | bibcode = 1991DSP.....1....4A | url = https://www.scribd.com/doc/52879771/DCT-History-How-I-Came-Up-with-the-Discrete-Cosine-Transform}}

* {{Cite journal | last1 = Feig | first1 = E. | last2 = Winograd | first2 = S. | doi = 10.1109/78.157218 | title = Fast algorithms for the discrete cosine transform | journal = IEEE Transactions on Signal Processing | volume = 40 | issue = 9 | pages = 2174–2193| date=September 1992b | bibcode = 1992ITSP...40.2174F }}

* {{Citation |last1=Malvar |first1=Henrique |title=Signal Processing with Lapped Transforms |publisher=Artech House |___location=Boston |year=1992 |isbn=978-0-89006-467-2}}