Course:CPSC312-2017-Image Vector Quantization

Image Vector Quantization

Authors: Edwin Chen, Trisha Huang, Yu Ju Liang.

What is the problem?

We will be using K-means clustering algorithm to implement vector quantization of an image file. We will separate the image pixels into n clusters, where the RGB values within the same cluster are changed to the mean values. After the clustering is completed and the RGB values of the pixels are updated, we will throw away all RGB values for each pixel within the same cluster and only keep the RGB values in the centroids. The algorithm compresses an image so that less number of bits are used to store an image. The process is useful when storage space is limited, such as uploading images to the web. https://docs.scipy.org/doc/scipy/reference/cluster.vq.html

What is the something extra?

Converting an image file to Haskell readable format will be a challenging task. We need to create a data structure to store the RGB values and the coordinates of each pixel, and process the image file pixel by pixel to read in the RGB values and coordinates to our internal representation. Our goal is to convert each pixel in the uploaded file to three 8-bits unsigned integers which represent their RGB values. Once the pixels are formated, we can apply vector quantization to compress the image and output the image. We also support different image types, such as jpg, png, tiff, bmp. The output image will be the same type as the input.

What did we learn from doing this?

Using Haskell to compress an image through k-means clustering and vector quantization is a feasible task. We were able to successfully implement a program that converts image files of bmp, jpg, png, and tiff formats into a compressed image of the same file type as the input image.

We initially considered implementing a function that would determine the optimal k, or the number of clusters, that would produce a compressed image that would have nearly no visible difference from the original image. However, we eventually decided to have k as an input so that the user could freely choose the degree of compression. The output image is sensitive to the choice of k. For example, a smaller k would produce a rough image, since there would be fewer clusters of pixels on different k-means.

As we tested our code against images of different file sizes, we discovered that processing larger images would result in longer run times or a stack overflow. This is because our program processes the input image by recursing through each pixel of the image. A larger image contains more pixels, and thus more data to process. So although it is feasible to perform color quantization of images with Haskell, improvements could still be made to optimize the performance.

Link to our project: https://github.com/kanchine/cpsc312project2.git