Kohonen Networks and Clustering: Comparative Performance in Color Clustering

NeurIPS 1990

TL;DR

This paper compares the performance of Kohonen Self-Organizing Feature Maps (KFM) against traditional clustering methods like k-means and competitive learning for the task of color clustering. The authors found that Kohonen maps significantly outperform other methods in terms of both image quality and computational speed, offering a more efficient and effective solution for reducing the number of colors in an image.

What Problem Does This Paper Address?

The paper tackles the challenge of "color clustering," which is the process of reducing the vast number of possible colors in a full-color image (represented by 24 bits per pixel) to a smaller, manageable set (8 bits per pixel, or 256 distinct colors). This is a computationally intensive problem with significant economic implications, as many display systems are limited to 8 bits per pixel, yet users desire high-quality color reproduction. The goal is to find a set of representative colors (clusters) that best approximate the original image, minimizing visual distortion and computational cost.

Methods

The authors compare three main clustering techniques:

  • k-means clustering (and LBG Vector Quantization): A standard iterative algorithm that aims to partition data points into k clusters by minimizing the variance within each cluster. The LBG algorithm, when applied to this problem with Euclidean distance, is shown to be equivalent to k-means.
  • Competitive Learning (CL): An unsupervised learning approach where data points are presented sequentially, and the closest cluster center is updated to move towards the data point.
  • Kohonen Self-Organizing Feature Maps (KFM): An extension of competitive learning where not only the winning cluster but also its topological neighbors are updated. This topological structure is key to its performance. The paper also introduces a "loneliness term" to prevent clusters from being updated too frequently, similar to the "conscience" mechanism.

Datasets

The paper uses actual color images, specifically mentioning "pictures of faces," for training and evaluation. No new benchmark datasets are introduced; the focus is on applying existing techniques to a practical color clustering problem.

Key Insights and Ideas

  • Kohonen Maps Excel: The Kohonen Feature Map (KFM) consistently provided the best results, both subjectively (visual quality) and objectively (quantization error), and was also the fastest.
  • Topological Structure Matters: The inherent topological ordering of Kohonen maps, where neighboring clusters in the map are also close in feature space, is crucial for its superior performance in color clustering. This allows for a more natural representation of color relationships.
  • "Conscience" or "Loneliness" is Important: Mechanisms like the "conscience" or the paper's "loneliness term" are vital for practical clustering. They prevent certain clusters from being over-represented and ensure a more balanced distribution of cluster updates.
  • RMS Error Can Be Deceiving: While RMS error is a useful metric, it can be misleading. The paper notes that low RMS error doesn't always guarantee good visual quality, especially in image processing, where small regions with large errors can skew the average.
  • Initial Conditions Less Critical for KFM: Unlike competitive learning, which can converge to undesirable renderings based on initial cluster placements, KFM proved robust and yielded good solutions even with arbitrary initial conditions.

Key Results

  • Speed: Kohonen maps achieved the fastest run times. For a 128x128 image, a Kohonen run took 15:42 total time with 1:34 per epoch, while competitive learning took 8:38 total time but with a slower 0:52 per epoch (though it required more epochs for comparable quality).
  • Quality: KFM produced "excellent rendering of color images," particularly noted for rendering blue eyes well. Competitive learning, without careful parameter tuning, tended to render blue eyes as brown due to the dominance of skin tones.
  • Convergence: KFM converged to a stable solution with much lower error than competitive learning, as shown in the quantization error plot.
  • k-means Performance: k-means required approximately 87 minutes to reach subjectively "equally good" quality, but took 9 hours to fully converge.

Limitations and Future Work

  • Subjective vs. Objective Measures: The paper acknowledges that subjective judgment of image quality is important, and RMS error, while quantitative, can be deceiving.
  • Parameter Sensitivity: While KFM is less sensitive to initial conditions than competitive learning, the performance of all methods is still dependent on parameter choices (e.g., learning rate, proximity function).
  • Computational Speed per Epoch: Although KFM has better overall speed, its computational speed per epoch can be slightly slower than competitive learning due to the update of neighboring clusters.
  • Future Work: The paper doesn't explicitly detail future work but implies that further exploration of KFM's topological properties and parameter optimization could lead to even better results. The robustness of KFM suggests it's a strong candidate for practical color image compression.

Summary updated

BibTeX
@inproceedings{1990kohonen,
  title = {{Kohonen Networks and Clustering: Comparative Performance in Color Clustering}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1990},
}
Figure