number of cosine waves in DCT

Question

Why is it $N\cdot N$ a sufficient number of cosine waves equal to the size of the image or to a portion of it to describe it (or a portion of it) completely without losing information applying the DCT.

For example, in the JPEG encoding I divide the image into 8x8 blocks and I will have, for each block, a table of exactly 8x8 coefficients: one for each wave. But... why?

Answer 1

Pixels in a block or in the whole image can be considered as "independent" samples in general. The indices $_{i,j}$ denote the coordinates of each pixel, whose luminance is $p_{i,j}$. Standard representations root on the concept of vector spaces, and bases. Imagine a simple image where only pixel $p_{i,j}$ is lit, the others being black. Whatever the value of $p_{i,j}$, you can find a linear representation: take an all-black image, and only set the value at $_{i,j}$ to be $1$, let us call this $e(i,j)$. The simple image above can be expressed as $p_{i,j}\times e(i,j)$. Now, for any image $\mathcal{I}$ with $I \times J $ pixels, you can represent it as a weighted sum of basis images $e(i,j)$:

$$\mathcal{I} = \sum_{I,J} p_{i,j}\times e(i,j)\,.$$

This is the basis for the linear algebra, or vector space representation of images, using here the trivial or the natural "each-pixel" basis". For finite spaces, the number of basis vectors is exactly the number of samples/pixels.

Yet, other discrete representations (linear combinations) of pixels can be useful of image processing tasks:

• [your question case] most use the same number of vectors: they correspond to square matrices. When they don't lose information, they are called inversible or critical. Most are additionally orthogonal, like PCA, DCTs, Fourier, Walsh-Hadamard, etc., in block or not. They are generally used in compression, to allow n a priori bijective relation, tunable in precision through quantification.
• some use less coefficients: this can be called data condensation in statistics, undersampled transfoms in signal. This happens when you extract a few statistics (average and variance, edge maps), generally known in adavance.
• some use more coefficients: they are called overcomplete, oversampled, redundant. This can be used for classification or learning, possibly when features are abundant, and not precisely known. When taking about vector spaces, one can find a novel set of vectors that form a frame. More vectors than needed, but usually for numerical reasons.

DCT (type-II) falls in the first category. The set of $N\times N$ cosines forms an orthogonal basis, representing original pixels faithfully. And for most classical images, and for the human visual system, this bais is more efficient than the natural basis. Combined with coding methods, it yields useful compression

Answer 2

N orthogonal basis vectors can completely describe a point in N dimensional space. Same for N * N orthogonal vectors and N * N samples describing an N*N dimensional space.

A DCT matrix is constructed from an orthonormal set of basis vectors.