Parallel Kmeans-based Images Compressor

This project implements a parallel KMeans-based image colors compressor, aimed at reducing the number of colors in a natural image while preserving its overall visual appearance. The program clusters similar colors using the KMeans algorithm and applies parallel computing techniques to compress the image through the color quantization technique. It supports sequential, OpenMP, MPI, and CUDA implementations to explore different levels of performance and scalability.

Authors

5 September 2024

• Leonardo Ignazio Pagliochini Master's Degree student in High-Performance Computing Engineering at Politecnico di Milano

  GitHub: leonardopagliochini
  Email: leonardoignazio.pagliochini@mail.polimi.it

• Francesco Rosnati Master's Degree student in High-Performance Computing Engineering at Politecnico di Milano

  GitHub: RosNaviGator
  Email: francesco.rosnati@mail.polimi.it

This project was developed for the course Advanced Methods for Scientific Computing,
Professor: Luca Formaggia
Assistant Professor: Matteo Caldana
Politecnico di Milano

Doxygen Documentation

The documentation of the project can be found here.

Prerequisites

OpenCV C++ Library

A comprehensive library for computer vision and image processing tasks. You can refer to the official page to download.

Mpicc

A C compiler wrapper for parallel programming with the MPI library. It is advised to use openmpi, official page, as we experienced some bugs with mpich due to experimental version of g++.

OpenMP

A C++ API for parallel programming on shared-memory systems.

Boost

Boost is a versatile, cross-platform, and comprehensive collection of highly optimized, portable, reliable, and robust C++ libraries designed to enhance software development efficiency and extensibility.

Getting Started

Cloning repo

Standard coloning with git clone, no submodules are implemented in this repo.

Install dependencies

Debian based

# Run commands from PROJECT ROOT DIRECTORY
sudo chmod +x ./dependencyInstaller/dependencyInstallerDebianBased.sh
source ./dependencyInstaller/dependencyInstallerDebianBased.sh

Arch based

# Run commands from PROJECT ROOT DIRECTORY
sudo chmod +x ./dependencyInstaller/dependencyInstallerArchBased.sh
source ./dependencyInstaller/dependencyInstallerArchBased.sh

Compile&Run

Program can be built with or without CUDA, you obviously need nvcc to be able to compile with CUDA. To compile the project, navigate to the project root directory in your terminal and run the following commands.

DO NOT USE mkmodules

Program uses a version of g++ with very recent standards, that were not supported by mkmodules, it is important to unload modules, including gcc-glibc in order to succesfully compile.

Without CUDA

# make without running
make
# make and run the menu (or simply run if already built)
make run

With cuda

# make without running (bulding also CUDA)
make cuda
# make and run the menu (building also CUDA)
make cudarun

Standard Run

For a standard run program will guide you to choose an image path, parallel method, configuration settings. See section "What to expect" for more infromation.

Debug/Preconfigured Run

If you want to avoid having to input all the information through the prompts requested by the program, you can preconfigure the options in the .config file.

What to expect

Once the program is started, the following screen appears, through which it is possible to compress a new image or decompress an already compressed image.

Compress an image

Set

If you choose the "Compress an image" option you will be asked to select:

1. Type of parallelization among sequential, MPI, OpenMP (also CUDA if nvcc was used during the compiling process), the type of compression, and the path of the original image.
2. Color level: five levels of compression, each corresponding to a certain percentage of retained colors (it's possible to visualize such percentages in the .config file).
3. Image path: The location of the original image file to be compressed.
4. Three methods of compression:
   • Light Compression: Preserves the most detail, recommended for smaller images where maintaining high quality is a priority. This level may take more time to process.
   • Medium Compression: Uses chroma subsampling to reduce image size and processing time. This is a balanced option for moderate size reduction while retaining good image quality.
   • Heavy Compression: Applies both chroma subsampling and resizing, significantly reducing the image size. Suitable for larger images where file size reduction is more important than retaining the highest possible quality.

Launch

After prompting all required settings the menu executable will exploit boost/process to launch a specific process (executable) relative to the chosen method, using the given settings as arguments.

Decode image

The menu will launch the decoder process (again with boost/process), there you will be asked to choose which .kc ('kmeans-compressed') to decode and visualize. Program creates list of .kc available to decode from the output folder.

Project Structure

The project is organized as follows:

Folders

• benchmarkImages: Images used for benchmarking the program. It can be used to test the program's performance.
• outputs: Contains the compressed images. After installing the program, you may notice that the outputs folder is not present. However, don't worry! It will be automatically created during the first execution of the program.
• include: Header files of the project. These define the classes and functions that are used in the program.
• src: Contains the source files of the project. These files contain the implementation of the classes and functions defined in the header files.
• build: Object files generated during the compilation process.
• dependencyInstaller: This folder contains the two scripts that can be used to install the required libraries.
• performanceEvaluation: Python codes used to evaluate performance and scalability of the four type of executions.

Files and Executables

• menu: This is the executable file generated after compiling the project. It is the main program that can be executed to compress or decompress images.
• Makefile: This file contains the instructions for compiling the project. It specifies the dependencies and the commands to compile the project.
• .config: This file contains the configuration of the program. It is used to store some hyperparameters that can be modified to change the behavior of the program.
• Doxyfile: Is a configuration file used by Doxygen to customize the generation of documentation from annotated source code.
• Readme.md: You already know that buddy ;)

How does it work?

KMeans is a widely used clustering technique that partitions data into a given number K of clusters. In the context of image compression KMeans is employed to reduce the color palette by grouping similar colors (color quantization), possibly minimizing the data required to represent the image.

Kmeans

The algorithm begins with an initialization phase, where $k$ initial cluster centers (means) ${\mu }_1^0,{\mu }_2^0,\dots ,{\mu }_k^0$ are chosen. After initialization, the algorithm enters an iterative phase, often referred to as Lloyd’s algorithm, which repeatedly executes two main steps until convergence is reached.

1. Assign each data point to the nearest centroid.
2. Recompute the centroids based on the data points assigned to them.

It is important to note that K-means-based compression is a form of lossy compression. Unlike lossless compression techniques, where the original data can be perfectly reconstructed,lossy compression involves some level of data loss. In the context of K-means, each pixel's color is approximated by the nearest centroid among the $k$ chosen colors. This approximation inevitably leads to a loss of some color information, making the compression irreversible. The degree of perceptible data loss is often minimal when the number of clusters $k$ is adequately chosen, but it can become noticeable if $k$ is too low, resulting in a more significant approximation error

Parallelization Techniques

The program uses several parallelization techniques to enhance performance. These techniques include:

• OpenMP: OpenMP is an API for parallel programming on shared-memory systems. It allows the program to parallelize the computation of the k-means algorithm by distributing the work among multiple threads.
• MPI: MPI is a message-passing library for parallel programming on distributed-memory systems. It allows the program to parallelize the computation of the k-means algorithm by distributing the work among multiple processes running on different nodes.
• CUDA: is a parallel computing platform and programming model developed by NVIDIA for general-purpose computing on GPUs (Graphics Processing Units). CUDA enables the acceleration of computationally intensive algorithms, like k-means clustering, by offloading the work to GPUs, which can process thousands of threads simultaneously. This results in a significant speedup, especially for tasks that involve large datasets and require high computational throughput.

What Parallelization Technique Should I Choose?

That is a really good question... as everithing in computer science it depends. Here you can see an overview of the execution time behaviour for increasing complexity tasks:

Report

For any additional information on the methods and implementation, please refer to the report

Instruction manual

For a thorough and detailed explanation of the code, please refer to the code manual (doxygen) in html or in pdf