KMeans for Image Compression, PCA / MDS / SVD for Visualization in the reduced dimension

Image Compression and Color-based segmentation with KMeans

  • This problem appears in an exercise of the Coursera ML course by Andrew Ng.
  • Couple of colored images are used as input 3D dataset and the Kmeans clustring is run with k arbitray cluster centroids. After the algorithm converges, each pixel x is assigned to the color of the nearest cluster \(argmin_{i}d(x,c_i)\).
  • If the input image contains n different colors, the output image can be represented using only k << n colors, achieving high level of compression, by grouping regions with similar colors in a single cluster.
  • The following animations show the result of the clustering with two different images and for a few diffeent k values.
  • Next, a bird image is segmented with k=16.bird_cluster
  • Next, a face image is segmented with k=16.
    me_cluster16
  • Next, the same face image is segmented with k=8. As can be noticed, the image quality becomes poorer, as lesser and lesser number of colors are used.me_cluster8
  • Next, the same face image is segmented with k=2 to obtain a binary image. Also, the convergence is achieved much faster (within first two iterations) in this case.
    me_cluster2

    Using PCA and MDS for Visualization in the reduced dimension

    • This problem also appears in an exercise of the Coursera ML course by Andrew Ng.
    • First, the 3-D RGB reprentation of the bird image is compressed with kmean clustering.
    • First, PCA and then MDS are used to reduce the dimension (to n=2) of the compressed image and then it is visualized in reduced dimension.
    • As can be seen, although the spatial neighborhood is not preserved in the very representation of the image, still some structure of the bird is preserved even in the reduced dimensions.bird_pca.png
    • Next the face dataset is used (with 5000 images of size 32×32) and PCA is used to find the top k dominant eigenvectors for different k. The eigenvectors look like faces, so they are called eigenfaces. The following image shows 100 of those faces and a few of the principal component eigenfaces.eigenfaces.png
    • The next figure / animation shows 100 of those normalized eigenfaces and the faces reconstructed with top k eigenfaces using Xapprox ≈ X.e1:k.(e1:k)’. As can be seen that the original faces can be closely reconstructed, when only k=100 principal components are used, instead of using all of 1024 dimensions.egf 00egf

Using SVD, PCA and FFT for dimension reduction and compression

  • First, the following two different implementations of the PCA will be used to reduce the dimensions of a 453×378 image and reconstruction of the image in the reduced dimension.
    1. Implemented with the SVD (numerically stable, as done by R prcomp)
    2. Implemented with the Eigen-decomposition of covariance matrix computed with the z-score-normalized image matrix (numerically less stable, as done by R princomp)
  • In both the above cases, only the first k orthonormal principal components will be used to reconstruct the image, as shown in the following animation (the first one being the SVD implementation of PCA).

svd

pca

  • As can be seen from above, the SVD implementation of PCA is much more robust and less susceptible to numerical errors, only first few principal components suffice to have a very close representation of the image.
  • Next, FFT will be used to transform the image to frequency domain and then only first k orthonormal Fourier basis vectors in the frequency domain will be used to reconstruct the image, as shown in the following animation.
  • As can be seen from above, PCA works better than DFT in terms of quality of image reconstructed in the reduced dimensions.
  • The following figures show the decrease in errors (in between the original and the approximated image using the Frobenius norm / MSE).mses
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s