Mean Shift Parallelization

Table of Contents

1. Introduction
2. Prerequisites
3. Quick Start
4. Complete Workflow - Example
5. Complete Workflow - Custom
6. Useful Scripts
7. Recommandations
8. Performance

Introduction

This repository is part of my B.Sc. Thesis, which focuses on the parallelization of the Mean Shift algorithm for modern high-performance computing architectures.

Mean Shift is a density-based clustering method which is particularly attractive for its capability of allowing flexible identification of clusters without extensive manual tuning of parameters. Unlike other clustering methods, it can discover clusters directly from the data without explicitly setting the number of groups or constraining their shapes. This makes it one of the most widely used algorithms for image segmentation, where boundaries and groupings can vary greatly depending on the input.

However, this comes at the cost of a quadratic computational complexity, which limits its scalability to large datasets and high-resolution images.

Therefore, leveraging the inherently independent operations of Mean Shift, the project explores four different parallel implementations:

• OpenMP over naive Mean Shift
• OpenMP over matrix-based Mean Shift
• OpenMP + OpenBLAS over matrix-based Mean Shift
• OpenACC over naive Mean Shift

Additionally, based on the existing integration with Simple Linear Iterative Clustering (SLIC) for superpixel generation, this projects extends the sequential SLIC-Mean Shift approach by providing:

• A fully parallel SLIC–Mean Shift pipeline

where SLIC is parallelized using both OpenMP and OpenACC.

Examples

Samples images from BSDS300 dataset, using different bandwidth values:

Original	bw=13	bw=20
Original	bw=9	bw=15

Prerequisites

• C++ compiler compatible with C++11 or higher (GCC, Clang, or MSVC)
• CMake (version 3.10 or higher), optional but highly recommended
• Python 3.12
  • Create and activate a virtual environment (optional but recommended):

    python -m venv venv

    • On Windows:

      venv\Scripts\activate

    • On Linux/macOS:

      source venv/bin/activate

  • Install the required Python packages using requirements.txt:

    pip install -r requirements.txt

Quick Start

To try it immediately you can run the automated demo script:

# Clone the repository
git clone https://github.com/martinadep/meanshift_parallelization
cd meanshift_parallelization

# Install Python dependencies
pip install -r requirements.txt

# Run the plug-and-play demo for Mean Shift
./mean_shift_demo.sh 

or

# Run the plug-and-play demo for SLIC - Mean Shift
./slic_ms_demo.sh 

This script will:

1. Convert the sample image to CSV format
2. Build the Mean Shift / SLIC Mean Shift implementation
3. Run the algorithm with optimal settings
4. Convert the result back to an image
5. Show you the segmented output

Your segmented image will be saved as data/demo_segmented_result.jpg.

Complete Workflow - example

The following steps use default example configurations defined in config.py. However, arguments can be configured to customize the execution as shown below.

Note that OpenACC is not enabled by default. If you want to use the OpenACC implementation, please see recommandations.

1. Clone the repository:

   git clone https://github.com/martinadep/meanshift_parallelization
   cd meanshift_parallelization

2. Run the Mean-Shift algorithm:

   On Windows (MinGW):

   cmake -B build
   cmake --build build --target mean_shift
   ./build/mean_shift -i ./data/example_90x60.csv

   On Linux/macOS:

   cmake -B build
   cmake --build build --target mean_shift
   ./build/mean_shift -i ./data/example_90x60.csv

   This will process the CSV file and generate a new output CSV file.

   You can also repeat this process adding the target slic_ms, and executing it using ./data/example_481x321 as input image.

3. Convert the output CSV back to an image:

   python ./py_utils/csv_to_img.py

   This will transform the processed data back into a segmented image.

Complete Workflow - custom

The following steps allows to configure the input image path and enables Mean-Shift bandwidth and kernel selection, as well as using other variants.

Mean Shift:

• mean_shift
• mean_shift_matrix
• mean_shift_matrix_blas
• mean_shift_acc

SLIC - Mean Shift:

• slic_ms
• slic_ms_matrix
• slic_ms_matrix_blas
• slic_ms_acc

1. Clone the repository:

   git clone https://github.com/martinadep/meanshift_parallelization
   cd meanshift_parallelization

2. Convert input image to CSV format:

   You can specify the input image and output CSV file paths by providing arguments in the command line:

   python ./py_utils/img_to_csv.py -i image.jpg -o output.csv

   This will generate a CSV file that will be processed by the C++ program.

3. Run the Mean-Shift algorithm:

   On Windows using MinGW:

   cmake -G "MinGW Makefiles" -B build
   cmake --build build

   On Linux/macOS:

   cmake -B build
   cmake --build build

   You can specify the bandwidth, and the input and output CSV file paths, by providing arguments in the command line:

   ./build/mean_shift [--kernel | -k kernel_name] [--bandwidth | -b bandwidth] [--input | -i input_csv] [--output | -o output_csv] [--superpixels | -s num_superpixels]

   Example

   Selecting kernel function and bandwidth

   ./build/mean_shift -k gaussian -b 20

   This will process the CSV file and generate a new output CSV file.

4. Convert the output CSV back to an image:

   You can specify the output image and input CSV file paths by providing arguments in the command line:

   python ./py_utils/img_to_csv.py -i input.csv -o image.jpg

   This will transform the processed data back into your segmented image.

Useful Scripts

Several scripts are provided into scripts directory which enable different analysis on both Mean Shift and SLIC, including strong scaling, breakdowns and profiling.

Recommandations

Enabling OpenACC (disabled by default)

OpenACC is NOT enabled automatically. You must turn it on at configure time:

cmake -B build -DENABLE_OPENACC=ON
cmake --build build 

Kernel

You can choose between three different Kernels: gaussian, uniform and epanechnikov, through the --kernel | -k flag via CLI. The Gaussian is the most accurate, while the Epanechnikov allows for faster executions.

Bandwidth

Recommended bandwidth values for image segmentation are typically between 10 and 20. Set it via the CLI with the --bandwidth | -b flag.

Performance

Mean Shift

Considering 128x85 resized images from BDSD300 dataset:

Variant	Sequential Version	Parallel Version	Speedup
mean_shift	4.08 s	0.07 s	58.29
mean_shift_matrix	4.13 s	0.09 s	45.89
mean_shift_matrix_blas	36.59 s	1.56 s	23.45
mean_shift_acc	4.08 s	---	---

SLIC - Mean Shift

Considering 481x321 images from BDSD300 dataset:

Variant	Sequential Version	Parallel Version	Speedup
slic_ms	4.98 s	0.74 s	6.72
slic_ms_matrix	5.43 s	0.68 s	7.99
slic_ms_matrix_blas	5.63 s	0.65 s	8.66
slic_ms_acc	4.98 s	0.24 s	20.75

Evaluation with SbatchMan

Please read SbatchMan documentation at https://sbatchman.readthedocs.io/en/latest/.

In summary from the root of the project (either locally or on a remote cluster), run:

# Run these commands, only the first time
sbatchman set-cluster-name <your_cluster_name>
sbatchman init
sbatchman configure --file sbatchman_configs.yaml

To run experiments:

sbatchman launch --file sbatchman_launch_all.yaml
# To check jobs status
sbatchman status

Generating plots:

python3 plots/strong_scaling_sbatchman.py