Compressione di immagini mediante algoritmi di clustering

This thesis aims to investigate the use of the k-means clustering algorithm developed by Stuart Lloyd in order to compress colored images in RGB format. First, the formal elements which will be referred to throughout the discussion are discussed; then, lossless encoding based on the k-means algorithm is presented: by comparing the algorithm with a normal Huffman encoding, it is shown that an algorithm such as the proposed one only surpasses the performance of a Huffman encoding if due measures have been taken; for what concerns the lossy encoding, an algorithm which performs such compression and which is based on the k-means algorithm is presented; different implementations of the latter are discussed, with the purpose of showing which of them is the best; the impact of the number k of clusters used in the first phase of the algorithm is then investigated and ultimately the proposed algorithm is compared with the Jpeg algorithm, showing that, at equal compression rates, the first of the two returns better images when at almost-without-loss rates of compression.

Questa tesi vuole indagare l'utilizzo dell'algoritmo di k-means clustering sviluppato da Stuart Lloyd al fine di comprimere immagini a colori in formato RGB. Dapprima si espongono gli elementi formali ai quali si farà riferimento nella discussione; successivamente si procede a discutere la codifica senza perdite sfruttando l'algoritmo k-means: confrontando l'algoritmo con una normale codifica di Huffman, si mostra che un algoritmo come quello proposto è in grado di superare le prestazioni della codifica di Huffman solo avendo preso dovuti accorgimenti; per quanto riguarda la codifica con perdite, si propone un algoritmo che svolga la compressione con perdite sfruttando l'algoritmo di k-means clustering e se ne analizzano varie implementazioni al fine di mostrare quale sia la migliore; si indaga poi l'impatto del numero di cluster k utilizzato nella prima fase dell'algoritmo e si confronta l'algoritmo ideato con l'algoritmo Jpeg, trovando che il primo restituisce, a parità di compressione, immagini migliori in situazioni quasi senza perdite.