Image compression via least-squares
We can use least-squares to represent an image in terms of a linear combination of ‘‘basic’’ images, at least approximately.
An image can be represented, via its pixel values or some other mechanism, as a (usually long) vector . Now assume that we have a library of
‘‘basic’’ images, also in pixel form, that are represented as vectors
. Each vector
could contain the pixel representation of a unit vector on some basis, such as a two-dimensional Fourier basis; however, we do not necessarily assume here that the
‘s form a basis.
Let us try to find the best coefficients , which allow approximating the given image (given by
) as a linear combination of the
‘s with coefficients
. Such a combination can be expressed as the matrix-vector product
, where
is the
matrix that contains the basic images. The best fit can be found via the least-squares problem
Once the representation is found, and if the optimal value of the problem above is small, we can safely represent the given image via the vector . If the vector
is sparse, in the sense that it has many zeros, such a representation can yield a substantial saving in memory, over the initial pixel representation
.
The sparsity of the solution of the problem above for a range of possible images is highly dependent on the images’ characteristics, as well as on the collection of basic images contained in
. In practice, it is desirable to trade-off the accuracy measure above, against some measure of the sparsity of the optimal vector
.