10
votes
Accepted
Convolution Theorem using DCT
I did it for the DCT-I and DCT-II.
At first I thought it is about circular convolution, but it is not. After desperate attempts to do it by myself I found the article: Convolution Using Discrete Sine ...
- 366
7
votes
Accepted
Understanding the DCT
Given $\{x_n, 0 \leq n \leq N - 1\}$, the conventional DFT is defined as
$$X_k = \sum_n x_n e^{-j2\pi kn/N}$$
The Parseval theorem gives
$$\sum_{n=0}^{N-1} |x_n|^2 = \frac{1}{N}\sum_{k=0}^{N-1} |X_k|^...
- 6,725
7
votes
Accepted
Fast DCT implementation
Alright, after some days of staring at this problem I hope I can provide a bit of guidance to the next poor soul.
Yes the scaling is different. Compared to ...
- 248
6
votes
Accepted
Online DFT Algorithm
(Note: the paper pointed by hotpaw2's link is actually describing in more detail the algorthm I presented here)
Consider a data window length of $N$ samples from $n=0$ to $n=N-1$. Let your original ...
- 28.4k
6
votes
Accepted
What is the maximum value that can result from a 2D DCT?
As suggested in the comments by Marcus Müller, you have to start from the equation of the DCT:
$$
S_{uv} = \frac{1}{4} C_u C_v \sum_{y=0}^7 \sum_{x=0}^7 s_{xy} \cos\frac{(2x+1)u\pi}{16} \cos\frac{(2y+...
- 236
6
votes
Accepted
How does DCT decorrelate images?
[EDIT] In 1991, Nasir Ahmed wrote: "How I Came Up with the Discrete Cosine Transform". Interesting to read, on how he was inspired by Chebyshev polynomials, and on how he didn't get funding,...
- 32.3k
5
votes
Is the DCT prone to spectral leakage like the DFT?
A window function other than rectangular can be applied to suppress sidelobes also with the discrete cosine transform (DCT). Window functions are also sometimes used together with some flavors of DCT ...
- 13.7k
4
votes
Data representation of largest DCT coefficients
How is bit reduction achieved practically in JPEG?
First, the whole graylevel (8-bit per pixel) image is divided into adjacent blocks of 8 x 8 = 64 pixels. Then, each block is independently DCT ...
- 28.4k
4
votes
Data representation of largest DCT coefficients
Your question is very accurate. Storing only the value of the largest (1 % for instance) coefficients, even from a good sparsifying transform (DCT, wavelet, else) is fool's-gold, since you (more ...
- 32.3k
4
votes
Do DCT results contain phase spectrum?
A DCT is equivalent to a DFT of real data that is doubled and mirrored, thus rendering it symmetric. The DFT of any symmetric real signal has a phase of zero (its all cosines, no antisymmetric sine ...
- 35.7k
4
votes
Do DCT results contain phase spectrum?
Not really, as the transform is real. However, one could interpret the sign as a poor man's phase, being "quantized" or restricted to values $0$ or $\pi$. In other words, $1 = 1.e^{0.\imath}$ and $-1 =...
- 32.3k
4
votes
Illustration of time domain aliasing cancellation (TDAC, MDCT, lapped transform)
Edit: I have recently created two Jupyter Notebooks that illustrate this behaviour and let you play around with some actual matrices and actual signals.
I find understanding MDCT easiest if we define ...
- 446
4
votes
Online DFT Algorithm
The algorithm for which you may be looking is called a "sliding DFT". For a small number of result bins, that number of "sliding Goertzel" filters can also be used. Here's one online description: ...
- 35.7k
4
votes
Accepted
Computation of the Inverse DCT (IDCT) Using DCT Or IFFT
Have a look at Fast DCT Algorithm (PDF Version).
It has both DCT and Inverse DCT using DFT (FFT).
They show how to do a DCT and Inverse without the reflection trick.
The standard (Less efficient ...
- 20.5k
4
votes
Accepted
1D DCT matlab code
You have mistyped the formula, replace this line
sum = sum + y(i).*(cos((pi.*(2.*y(i)+1).*u(j))/(2*N)));
with the one below, and it works fine.
...
- 28.4k
3
votes
Accepted
How to get a real signal from complex ifft values?
You can plot the real and imaginary components from the FFT result separately (or the magnitude and the phase results separately, as two plots). Then you can recombine the data from the two plots ...
- 35.7k
3
votes
Accepted
validation of a pseudo jpeg compression
If you compute a $8\times 8$ 2D-DCT, and keep the top left corner only, you are keeping a quantity that is proportional to the average of each $8\times 8$ block. This is the DC component, similar to ...
- 32.3k
3
votes
Understanding the DCT even symmetry
Just as the DFT assumes a periodic signal by construction, the DCT assumes an even signal by construction. We can think of taking a DFT of a non-periodic signal by extending it periodically, but ...
- 107
3
votes
Accepted
What are the cosine functions in JPEG's DCT-II table?
Those 2D cosine functions are independent of your input image. They are just "cosine waves", or the 64 basis functions that yield 64 coefficients when transforming "$8\times 8$" blocks. Given a $D$ $8\...
- 32.3k
3
votes
1D DCT matlab code
For clarity, I would write this DCT as:
$$F(u) = \alpha(u)\sum_{i=0}^{N-1}f(i)\cos\left(\frac{\pi u}{2N}(2i+1)\right)$$
We note that, with this 1-indexing of Matlab:
$$y[i+1] = f(i)\,.$$
Then I would ...
- 32.3k
3
votes
Solve for minimum and maximum value of dct coefficient
The max value for a DCT coefficient with this formula would be when $k_1 = 0$ and $k_2 = 0$. Using this give us the $\cos(0) = 1$ so you simply sum up the pixel values. Since the pixel values are $0-...
- 244
3
votes
Is there mathematical relationship between the FFT and DCT transforms
You have some confusion in the indices, maybe the correct expression would be
$$Y[k] = \sum_{n=1}^N \left[
\sum_{m=1}^N x[m] \cos\left( \frac{(2m+1)n\pi}{2N} \right) \right] e^{-\frac{j2\pi k n}{N}}$...
- 2,393
3
votes
DCT - Measures of energy compaction gain achieved using DCT over FFT
In Discrete-Time Signal Processing by Oppenheim, chapter 8.5, there is a quantification of mean squared error by setting coefficients to 0 for both DCT and DFT:
From this, you can of course calculate ...
- 11.2k
2
votes
Fast Cosine Transform via FFT
For true scientific computing, the amount of memory usage is important too.
Therefore the N point FFT is more attractive to me. This is only possible due to Hermitian Symmetry of the signal.
The ...
- 121
2
votes
DCT: Alternatives to quantization
From what I read there are certain quantisation matrices for different applications, Adobe Photoshop has like 15 or something. The idea is that although there are error based mathematical calculations ...
2
votes
Accepted
The magnitude of taking discrete cosine transform of an image two times is similar to the original
It's beacuse the inverse discrete fourier transform (DCT) is almost identical to the forward DCT. So taking twice the transform will be similar to the original signal. In fact if you provide which DCT ...
- 28.4k
2
votes
Accepted
Need help implementing DCT Type 4 algorithm
I found the solution. There was a mistake in the paper.
On the first 2 lines of Algorithm 2:
w0 ← x0
vN/2 ← xN−1
x0 and xN-1 should be scaled by 2, giving:
<...
- 177
2
votes
Accepted
discrete cosine transformation (dct-II) own implementation with loops
You are missing a $\sqrt{\frac{2}{N}}$ scaling factor. Change the following line:
tmp(k+1,n+1) = sqrt(2/N)*cos((n+0.5)*k*pi/N);
You can also simply use Matlab's ...
- 4,315
2
votes
Accepted
Image not divisable by 8? (JPEG Compression)
Then its size is extended by padding zeros or repeating at the end, such that the new size is divisible by 8. Note that reverse repetition at the end reduces the DCT compression size on that block ...
- 28.4k
2
votes
DCT vs DST for image compression
A DCT is roughly equivalent to a DFT of a vector after it is doubled by mirroring by a symmetric reflection. This produces FFT input that does not have a discontinuity either in the middle or ...
- 35.7k
Only top scored, non community-wiki answers of a minimum length are eligible