← Back to Documentation

Algorithm Reference: K-Means Clustering

Type: Unsupervised Learning / Vector Quantization
Library: OpenCV (cv2) & NumPy
Application: Colour Quantization & Segmentation

K-Means clustering is the core algorithm driving the "Photo to Art" tool on ImageStylo. While simple in concept, implementing it efficiently for high-resolution images requires specific backend optimizations using Python's OpenCV wrapper.

1. Mathematical Formulation

The goal of the K-Means algorithm is to partition n pixels into k clusters in which each pixel belongs to the cluster with the nearest mean (centroid). This results in a partitioning of the colour space into Voronoi cells.

The objective is to minimize the Within-Cluster Sum of Squares (WCSS):

argmin_S ∑_i=1^k ∑_{x ∈ S_i} || x - μ_i ||²

Where μ_i is the mean of points in S_i. In our implementation, we operate in a 3-dimensional colour space (Blue, Green, Red).

2. Python Backend Logic (Snippet)

Standard JavaScript implementations of K-Means often crash the browser tab when processing 4K images. To solve this, ImageStylo routes the data to a Python server where we can utilize optimized C++ bindings via OpenCV.

Below is the core function call we use to cluster the colour channels.

# ... (Reshaping of Image) ...

# Apply K-Means Clustering on the pixel matrix
# 'pixel_values' is the flattened image array
# 'k' is the user-selected number of colours
_, labels, (centers) = cv2.kmeans(
    pixel_values,
    k,
    None,
    10, # Attempts
    cv2.KMEANS_RANDOM_CENTERS
)

# ... (Reconstruction of Image) ...

3. Performance Constraints

The complexity of Lloyd's algorithm (standard K-Means) is O(n × k × d × i), where:

n: Number of pixels (e.g., 1920x1080 = 2,073,600)
k: Number of clusters (user selected)
d: Dimensions (3 for RGB)
i: Number of iterations

To keep processing times fast for the user, we optimize the convergence criteria and limit the maximum number of iterations on the server side.

Ready to test the algorithm?

Launch Live Tool