⚡ electrical engineering

Performance Benchmarking and Optimisation of Clustering Algorithms for Local and Non-Local Similarity Measure in Medical Image Analysis

This paper evaluates and optimizes five clustering algorithms for medical image analysis, finding that agglomerative clustering is best for preserving fine details in MRI and ultrasound, mini-batch k-means offers the best balance for chest X-rays, while standard k-means and bisecting k-means struggle with intra-cluster variability, and BIRCH consistently underperforms across all modalities.

Original authors: Sisipho Hamlomo, Marcellin Atemkeng

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sisipho Hamlomo, Marcellin Atemkeng

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive, ultra-high-definition photo of a brain, a beating heart, or a chest. It's so detailed that it's like a library containing millions of tiny, unique puzzle pieces. The problem? Storing and sending these giant libraries is a nightmare for hospitals; they take up too much space and move too slowly.

To fix this, scientists try to compress the images. But here's the catch: if you squish the image too hard, you might accidentally blur out the tiny, life-saving details a doctor needs to see.

This paper is like a detective story where the authors test five different "organizers" (clustering algorithms) to see which one can sort these puzzle pieces into neat, identical piles. The goal? To group pieces that look exactly alike so they can be squished together tightly without losing any important information.

The Five Contenders

The authors put five different sorting methods through a rigorous training camp using three types of medical images: brain scans (MRI), ultrasound images, and chest X-rays. They didn't just guess; they used a "random search" to tune every single setting for every method to make sure they were performing at their absolute best.

The five methods were:

K-means: The classic, straightforward sorter.
Mini-batch K-means: A faster version that sorts in small batches.
Agglomerative Hierarchical Clustering: A method that starts with every piece as its own group and slowly merges them together, like building a family tree.
BIRCH: A method designed to handle huge data by building a summary tree first.
Bisecting K-means: A method that starts with one giant pile and keeps splitting it in half until it's done.

The Big Reveal: "Good" isn't always "Best"

Here is the twist the paper uncovers. If you just look at the standard scoreboard (metrics like the Silhouette score, Davies-Bouldin index, and Calinski-Harabasz index), K-means and Bisecting K-means seem like the champions. They get the highest scores, meaning they separate the groups very clearly.

However, the paper argues against using them for the final job.

Think of it like this: K-means and Bisecting K-means are like a strict teacher who puts all the students into just two or three huge classrooms. While the classrooms are clearly separated from each other, the students inside are a mess! One kid is wearing a tuxedo, another is in pajamas, and a third is in a superhero costume. They are all in the same room, but they are very different. If you tried to compress this room (the image patch), you'd have to be very gentle, or you'd ruin the details.

The paper found that for MRI and Ultrasound images, Agglomerative Hierarchical Clustering was the real hero. Even though it took a bit more computer power to run, it acted like a meticulous librarian. It created many more, smaller groups where every single item was nearly identical to its neighbors.

The Result: For MRI and Ultrasound, this method produced clusters with much lower "intra-cluster variability" (meaning the items inside were very similar). This allows the image to be compressed much more aggressively without losing the fine, critical details doctors need.
The Numbers: In the MRI tests, Agglomerative clustering formed 7 clusters, while K-means only formed 3. In Ultrasound, Agglomerative formed 11 clusters compared to just 2 for K-means.

The X-Ray Exception

But wait, there's a plot twist for the chest X-rays!
For this specific type of image, Mini-batch K-means struck the perfect balance. It managed to create 4 clusters that were both high-quality and compact enough for compression. It was the "Goldilocks" solution for X-rays, offering a better trade-off than the other methods.

The Loser

One method, BIRCH, consistently underperformed across all three types of images. Whether it was sorting brain scans, ultrasounds, or X-rays, it simply didn't create the tight, uniform groups needed for effective compression. The paper suggests it is the least suitable option for this specific task.

The Bottom Line

The paper doesn't claim to have solved the world's compression problems forever. Instead, it suggests that the "best" tool depends entirely on what you are looking at.

If you are looking at MRI or Ultrasound, the authors suggest using Agglomerative Hierarchical Clustering because it keeps the tiny details safe by making very uniform groups.
If you are looking at Chest X-rays, Mini-batch K-means seems to be the best fit.
If you are looking at K-means or Bisecting K-means, the paper suggests being careful: they look great on paper scores, but they might group too many different things together, making it risky to compress the image without losing important medical clues.

In short, the paper proves that for medical images, you can't just use the "fastest" or "highest-scoring" sorter; you need the one that keeps the puzzle pieces inside each pile as identical as possible.

Technical Summary: Performance Benchmarking and Optimisation of Clustering Algorithms for Local and Non-Local Similarity Measure in Medical Image Analysis

Problem Statement
High-resolution medical imaging (MRI, CT, ultrasound, X-ray) generates vast amounts of high-dimensional data, creating significant challenges for storage, transmission, and computational processing. While Low-Rank Matrix Approximation (LoRMA) techniques offer efficient compression by exploiting structural redundancy, global approaches often fail to preserve the local details critical for diagnosis. Recent research has shifted toward patch-based strategies that exploit non-local self-similarity to group structurally similar regions for adaptive compression. However, a critical gap remains in identifying which clustering technique most effectively forms the homogeneous, low-variance clusters required for high-fidelity adaptive compression. Different algorithms prioritize different trade-offs: some optimize global separation (yielding good metrics but high intra-cluster variability), while others form tighter groups at the cost of creating more clusters. This variability directly impacts compression performance, as homogeneous clusters allow for aggressive compression without losing clinically significant information.

Methodology
This study presents a systematic benchmarking of five clustering algorithms applied to overlapping square patches extracted from medical images. The image $A \in \mathbb{R}^{H \times W}$ is divided into patches of size $p \times p$ with a stride $s < p$ , vectorized into column vectors, and clustered to group similar regions.

The five evaluated techniques represent both partitioning-based and hierarchical-based approaches:

k-means: Standard partitioning algorithm.
Mini-batch k-means: A scalable variant using small random batches to update centroids.
Agglomerative Hierarchical Clustering: A bottom-up approach using linkage criteria (single, complete, average, or Ward's).
BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies): An incremental algorithm using a Clustering Feature (CF) tree to summarize large datasets.
Bisecting k-means: A hierarchical approach that recursively partitions a set into two clusters until $K$ clusters are formed.

Optimization and Evaluation:

Hyperparameter Tuning: All algorithms were optimized using random search over a feasible hyperparameter space (including the number of clusters $K$ , batch sizes, linkage criteria, and tree thresholds) to ensure optimal performance for each modality.
Datasets: Experiments were conducted on representative images from three modalities: Brain MRI (BraTS2020), Breast Ultrasound, and Chest X-ray (COVIDqu).
Metrics: Cluster quality was assessed using:
- Silhouette Score: Measures cohesion and separation (range [-1, 1]).
- Davies-Bouldin (DB) Index: Lower values indicate better compactness and separation.
- Calinski-Harabasz (CH) Index: Higher values indicate distinct, well-separated clusters.
Critical Analysis: Beyond standard metrics, the study specifically analyzed intra-cluster variability (via box-plots) to determine suitability for post-processing tasks like adaptive compression.

Key Results

MRI and Ultrasound: Standard k-means and bisecting k-means achieved the highest Silhouette scores and lowest DB indices, indicating strong global cohesion. However, they formed a small number of clusters (e.g., 2–3) with high intra-cluster variability. In contrast, Agglomerative clustering produced a larger number of clusters with significantly lower intra-cluster variability, resulting in tighter, more homogeneous groups despite slightly lower global metric scores.
Chest X-ray: Mini-batch k-means achieved the best balance between clustering quality metrics and intra-cluster compactness, outperforming other methods in this specific modality.
BIRCH: Consistently underperformed across all modalities in both clustering quality metrics and intra-cluster homogeneity.

Contributions
The paper makes three primary contributions:

A systematic evaluation of four (five in practice) clustering techniques across three distinct medical imaging modalities (MRI, Ultrasound, X-ray).
The application of random search to tune hyperparameters for every clustering algorithm, ensuring a fair and optimized comparison.
Modality-specific recommendations on which clustering technique to employ, prioritizing intra-cluster homogeneity for adaptive compression over raw metric scores.

Significance and Claims
The authors claim that the choice of clustering algorithm must be guided by the specific imaging modality and the trade-off between computational efficiency and compression fidelity.

For MRI and Ultrasound: Agglomerative clustering is recommended. Although computationally more intensive, its ability to form tighter, more homogeneous clusters with low intra-cluster variability makes it superior for preserving fine diagnostic details during adaptive LoRMA-based compression.
For Chest X-rays: Mini-batch k-means is recommended as it offers the best balance between clustering quality and compactness.
General Finding: While standard k-means variants often yield superior Silhouette and CH scores, their tendency to form few, high-variance clusters limits their effectiveness for adaptive compression tasks where preserving local structural details is paramount. The study concludes that optimizing for intra-cluster homogeneity is critical for high-fidelity medical image compression, a nuance often missed when relying solely on standard clustering metrics.