Image compression

 

In image compression applications, we are given the pixel representation of a “target” image, as a vector in y \in \mathbb{R}^m. We would like to represent the image as a linear combination of “basic” images a_j, j=1,\ldots,n, where the matrix A=[a_1,\ldots,a_n] \in \mathbb{R}^{m \times n} is called the dictionary. The picture on the left shows a total of n “basic” images.

To represent the image in terms of the dictionary, we would like to find coefficients x_j, j=1,\ldots,n such that

    \[y = \sum_{j=1}^{n} x_j a_j,\]

or, more compactly, y = Ax.

If the representation of the image (that is, the vector x) has many zeros (we say: x is sparse), then we can represent the entire image with only a few values (the components of x that are not zero). We may then, for example, send the image over a communication network at high speed. Provided the receiver has the dictionary handy, it can reconstruct perfectly the image.

In practice, it may be desirable to trade off the sparsity of the representation (via x) against the accuracy of the representation. Namely, we may prefer a representation x that achieves Ax = y only approximately but has way more zeros. The process of searching for a good sparsity/accuracy trade-off is called image compression.

License

Icon for the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License

Linear Algebra and Applications Copyright © 2023 by VinUiversity is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License, except where otherwise noted.

Share This Book