Hot answers tagged

21

I've been reading about this and there are multiple ways to do it, using different size N. My Matlab is rusty, so here they are in Python (N is length of input signal x, k is arange(N) = $[0, 1, 2, ..., N-1]$): Type 2 DCT using 4N FFT and no shifts Signal [a, b, c, d] becomes [0, a, 0, b, 0, c, 0, d, 0, d, 0, c, 0, b, 0, a]. Then take the FFT to ...


19

The main difference between DCT and PCA (more precisely, representing a dataset in the basis formed by the eigenvectors of its correlation matrix - also known as the Karhunen Loeve Transform) is that the PCA must be defined with respect to a given dataset (from which the correlation matrix is estimated), while the DCT is "absolute" and is only defined by the ...


17

Let me start from the beginning. The standard way of calculating cepstrum is following: $$C(x(t))=\mathcal{F}^{-1}[\log(\mathcal{F}[x(t)])] $$ In the case of the MFCC coefficients case is a bit different, but still similar. After pre-emphasis and windowing, you calculate the DFT of your signal and apply the filter bank of the overlapping triangular ...


10

The Walsh-Hadamard transform requires a Hadamard matrix -- which has entries $\pm 1$ and whose rows are orthogonal vectors. A $n \times n$ Hadamard matrix is known to exist for $n = 2$. Larger Hadamard matrices can exist only if $n$ is a multiple of $4$, though it is not known if there is a Hadamard matrix for every multiple of $4$. However, there is a ...


8

There are two parts to the answer. One has to do with the nature of sharp edges, the second has to do with the how imaging systems (lenses and the human eye) work. As @PeterK's example demonstrates artificial (human created) images tend to have large regions of one color with sharp transitions between the regions. This is similar to a square wave. But if ...


6

High frequencies correspond to rapid changes in pixel intensity over a small displacement (a few pixels) - most "natural" images have large features which change relatively slowly so most of the information is in the lower spatial frequency range. High frequencies tend to be mainly noise, sharp edges or very fine textured features. Note also that a similar ...


6

(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 data window be $x_1[n]$, whose first sample is $x_{old} = x_1[0]$. Now your new data set is denoted as $x_2[n]$ whose samples are actually one sample left ...


6

[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, for a tool at the heart of JPEG and MP3. Natural images are not very stationary, but locally, their covariance is often modeled by a first- or second-order ...


5

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|^2$$ The DFT in your link is called Normalized DFT (NDFT): $$Y_k = \frac{1}{\sqrt{N}} X_k = \frac{1}{\sqrt{N}} \sum_n x_n e^{-j2\pi kn/N}$$ that $$\sum_{n=0}^{N-...


4

Each DCT output bin is a (weighted) correlation against a cosine function of a certain frequency. A negative value would represent a negative correlation, e.g. something in the image data is of the opposite phase to that cosine (e.g. maybe dark when the cosine is 1, and light when the cosine is -1, instead of vice-versa for a positive correlation).


4

You are right! When it comes to quantization, bit allocation or issues like that scanning in zig zag manner seems to be most efficient. As you said, (and I emphasize) in Natural Signals, lower frequency coefficients contain most of the energy. In a DCT matrix, as you go along a row the frequency is increasing in the first dimension and as you go along a ...


4

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 our transforms as matrix operations. DFT In case of a DFT such a matrix would look like $$ F_M = \left( \sqrt{\frac{1}{M}} e^{-2 \pi i k n / M} \right)_{k,n=...


4

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 scipy.fftpack.dct the DC term is $\frac{1}{2}$ and the other terms $\frac{\sqrt{2}}{2}$. But apparently it all nicely cancels out in the inverse transform. The inverse input order is exactly as they come ...


4

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: https://www.dsprelated.com/showarticle/776.php of how to implement a sliding DFT. Basically, for each new sample, you add a new twiddle-multiplied vector to the ...


4

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 = 1.e^{\pi.\imath}$. [EDIT] There are some instances where people use the sign of DCT or (real) wavelet coefficients, for subpixel image registration or ...


4

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 components).


4

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+1)v\pi}{16} $$ The argument of the summation is of the magnitude of $s_{xy}$ times two values which are at most 1 (absolute value). So still 8 bits. You are ...


4

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 this article: https://dr.ntu.edu.sg/bitstream/10356/94137/1/Convolution%20Using%20Discrete%20Sine%20and%20Cosine%20Transforms.pdf. In this paper there is a derivation of circular convolution using DTT's, ...


4

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. sum = sum + y(i).*(cos((pi.*(2.*u(i)+1).*u(j))/(2*N)));


4

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 as a lapped transform, with pre and post windowing providing some protection against reflection artifacts arising from processing (such as quantization) of the ...


3

You already gave the spirit of the answer, but let me put it in other words: First of all, zig-zag scanning is not a property of DCT itself but rather a part of the transform based image coding process. Zig-zag scanning is employed after the quantization of DCT coefficients per N x N image block, and before the Category / Run length coding of the quantized ...


3

The rationale behind it is to separate the correlation in the log-spectral magnitudes (from the filterbank) due to the overlapping of the filters. Essentially, the DCT smooths the spectrum representation given by these log-spectral magnitudes. This is incorrect. There is correlation between the log-spectral magnitudes not just because they overlap, but also ...


3

More than smoothing the DCT reduces the number of dimensions needed to represent the spectrum. DCT is good for dimensionality reduction because it tends to compact most of the energy of the spectrum in the first few coefficients.


3

When we calculate 1D DCT of a signal (vector) we will get the DCT coefficients of same length. The first value in this is the DC coefficient and low frequency components are at the begnning, as the index increases the frequency also increases. And hence the last value in DCT coeffs is the highest frequency (ie. fs/2). Zig zag scanning is done in 2D DCT to ...


3

In Huffman coding frequency refers to the number of times a particular sequence of discrete source symbols has appeared in the input. It is not the same concept as frequency in the continuous space such as sound frequency. As such, it has nothing to do with psychoacoustics or the cochlea. We use fewer bits for the higher frequency source symbols because ...


3

Regarding exceptions: Scanned monochrome documents, especially drawings/engravings/comics/technical blueprints, can have high frequency components, due to the sharp edges, fill patterns and use of cross-hatching.


3

As far as I can see, there are two little mistakes. First of all, you should use dct2() instead of dct(). And second, you shouldn't use the 'transpose' function because you want the DCT matrix not only transposed but also conjugated. So you should do the following: $$\tt{T=dctmtx(4); DCTB = T*B*T'}$$ And this should equal $\tt dct2(B)$. EDIT: As correctly ...


3

Both JPEG and JPEG 2000 use the change of basis compression type. Namely, we transform the data into a different representation assuming in this representation the number of parameters needed to describe to data is lower. Or to the least, most of the information is gathered within few parameters. Now, if you look at the energy level of the DCT coefficients ...


3

Mostly yes, but it depends on the context. Let us elaborate. DCT-II is one of the many forms of Discrete Cosine Transforms, and probably the most widely used one, as it is (somehow) present in JPEG or MP3 formats. "Lossy" often refer to the compression standard which uses it, because the main loss results from quantization (and generally not the transform ...


3

Let's define the N-point IDFT $y[n]$ of a signal $Y[f]$ as $$\begin{align*} y[n] &= \sum\limits_{f=0}^{N-1} Y[f] e^{j2\pi n\,\frac{f}{N}},& n\in \{0,\dots,N-1 \}\tag{1} \end{align*}$$ The DCT-II (which is most probably what we're looking at; the others are mathematically useful, but less nice to implement) $\mathbf{Y}[f]$: $$\begin{align*} \mathbf{...


Only top voted, non community-wiki answers of a minimum length are eligible