The discrete cosine transform can be understood as a trigonometric interpolation problem. Given some data, like , I want to find the coefficients such that
with . (This is different from the unitary scaling preferred in image processing.) Matlab’s signal processing toolbox, as well as “signal” package of Octave-Forge both have
dcp command. But the former is expensive and the latter is not entirely painless to install. Let’s work with the standard tool
fft, readily available in Matlab, Scilab, and Octave.
The full Fourier series reduces to cosines when the function is even. Therefore, we need to extend by an even reflection. One might imagine such an extension as
but this is incorrect. Thinking of the six values as the samples of a function at helps: the even reflection across should not duplicate the boundary value at . Also, gets reflected to , which is the same as due to periodicity, so this value also should not be repeated. The appropriate reflection is
In Matlab terms,
y = [3 1 4 1 5 9] z = [y, y(end-1:-1:2)] w = fft(y)
The output is real, as desired. It also has the same kind of symmetry as the input.
The term is simply the sum of the -values, but the constant term in Fourier expansion is the mean value. So, division by the data size () is needed to get the coefficients. Now that we have them, it seems that the interpolating function should be
but this is incorrect. Although this function does pass through the given points,
it wiggles too much due to high frequency terms such as . The aliasing comes into play: at the multiples of , the function is the same as .
Similarly, should be replaced by in the interpolating function, etc. This results in a much smoother interpolant, which is a linear combination of cosines up to .
The final answer is
Here is the complete Matlab code for this process of reflection, transforming and subsequent “folding” of the coefficients.
y = [3 1 4 1 5 9] z = [y, y(end-1:-1:2)] w = real(fft(z))/length(z) a = [w(1), 2*w(2:end/2), w(end/2+1)]
Taking real part of FFT makes sure that nothing imaginary slips in through the errors associated with numeric computation.