Image Compression via Least-Squares

L. El Ghaoui

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 $y \in \mathbf{R}^m$ . Now assume that we have a library of $n$ ‘‘basic’’ images, also in pixel form, that are represented as vectors $a_1, \ldots, a_n$ . Each vector $a_j$ 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 $a_j$ ‘s form a basis.

Let us try to find the best coefficients $x_j, j=1, \ldots, n$ , which allow approximating the given image (given by $y \in \mathbf{R}^m$ ) as a linear combination of the $a_j$ ‘s with coefficients $x_j$ . Such a combination can be expressed as the matrix-vector product $Ax$ , where $A=\left[a_1, \ldots, a_n\right]$ is the $m \times n$ matrix that contains the basic images. The best fit can be found via the least-squares problem

$\min _x\|A x-y\|_2$

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 $x$ . If the vector $x$ 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 $y$ .

The sparsity of the solution of the problem above for a range of possible images $y$ is highly dependent on the images’ characteristics, as well as on the collection of basic images contained in $A$ . In practice, it is desirable to trade-off the accuracy measure above, against some measure of the sparsity of the optimal vector $x$ .

Image Compression via Least-Squares

License

Share This Book