K-Centroid Image Scaler & Color Quantizer - WebAssembly Module

A Rust/WebAssembly implementation of the K-Centroid image downscaling algorithm and advanced color quantization tools, converted from the original Lua/Aseprite script.

Features

1. K-Centroid Image Scaling

Intelligent downscaling using K-means clustering on image tiles to preserve important colors.

2. Color Quantization

Two high-quality algorithms for reducing color palettes:

• Median Cut: Best quality, ideal for photographs and complex images
• K-Means: Faster processing, great for graphics and illustrations

3. Color Analysis with Spatial Sorting

Advanced color analysis with multiple sorting algorithms:

• Z-Order (Morton): Groups similar colors using space-filling curves
• Hilbert Curve: Superior locality preservation for color relationships
• Hue-based: Sort by color wheel position
• Luminance: Sort by brightness
• Frequency: Sort by usage percentage

4. Dominant Color Extraction

Automatically identifies and quantizes dominant colors with configurable minimum coverage thresholds.

5. Palette Extraction

Extract dominant colors from any image for analysis or design purposes.

Algorithm Overview

K-Centroid Scaling

1. Tile Division: The image is divided into tiles based on the target dimensions
2. K-Means Clustering: Each tile undergoes K-means clustering to identify dominant colors
3. Color Selection: The most dominant color (centroid with most pixels) represents each tile
4. Downscaling: Each pixel in the output image uses the dominant color from its corresponding tile

Color Quantization

• Median Cut: Recursively divides the color space to find optimal palette
• K-Means: Clusters similar colors together for palette reduction
• Floyd-Steinberg Dithering: Optional error diffusion for smoother gradients

Module Interface

K-Centroid Resize

k_centroid_resize(
    image_data: &[u8],      // RGBA image buffer
    original_width: u32,    // Source image width
    original_height: u32,   // Source image height
    target_width: u32,      // Desired output width
    target_height: u32,     // Desired output height
    centroids: u32,         // Number of color centroids (2-16 recommended)
    iterations: u32,        // K-means iterations (1-20 recommended)
) -> ImageResult

Color Quantization (Median Cut)

quantize_colors_median_cut(
    image_data: &[u8],      // RGBA image buffer
    width: u32,             // Image width
    height: u32,            // Image height
    num_colors: u32,        // Target color count (2-256)
    dithering: bool,        // Apply Floyd-Steinberg dithering
) -> ImageResult

Color Quantization (K-Means)

quantize_colors_kmeans(
    image_data: &[u8],      // RGBA image buffer
    width: u32,             // Image width
    height: u32,            // Image height
    num_colors: u32,        // Target color count (2-256)
    iterations: u32,        // K-means iterations
    dithering: bool,        // Apply Floyd-Steinberg dithering
) -> ImageResult

Palette Extraction

extract_palette(
    image_data: &[u8],      // RGBA image buffer
    max_colors: u32,        // Maximum colors to extract
) -> ColorPalette

Color Analysis with Sorting

analyze_colors(
    image_data: &[u8],      // RGBA image buffer
    max_colors: u32,        // Maximum colors to return (capped at 256)
    sort_method: &str,      // Sorting algorithm
) -> ColorAnalysis

Sort Methods:

• "z-order" or "morton": Space-filling curve for color grouping
• "hilbert": Hilbert curve for better locality preservation
• "hue": Sort by hue value (color wheel position)
• "luminance" or "brightness": Sort by perceived brightness
• "frequency": Sort by usage percentage (most to least common)

Return Structure:

{
    colors: [{
        hex: string,        // "#RRGGBB" format
        percentage: number, // % of image (0-100)
        count: number,      // Pixel count
        r: number,          // Red (0-255)
        g: number,          // Green (0-255)
        b: number           // Blue (0-255)
    }],
    totalColors: number,    // Unique colors found
    totalPixels: number     // Pixels analyzed
}

Dominant Colors with Auto-Quantization

get_dominant_colors(
    image_data: &[u8],      // RGBA image buffer
    num_colors: u32,        // Target dominant colors
    min_coverage: f32,      // Minimum % coverage threshold
) -> ColorAnalysis

Usage Examples

Basic Color Quantization

import init, { quantize_colors_median_cut } from './pkg/k_centroid_scaler.js';

async function reduceColors() {
    await init();
    
    // Get image data
    const canvas = document.getElementById('canvas');
    const ctx = canvas.getContext('2d');
    const imageData = ctx.getImageData(0, 0, canvas.width, canvas.height);
    
    // Reduce to 16 colors with dithering
    const result = quantize_colors_median_cut(
        imageData.data,
        canvas.width,
        canvas.height,
        16,     // 16 colors
        true    // Enable dithering
    );
    
    // Display result
    const outputImageData = new ImageData(
        new Uint8ClampedArray(result.data),
        result.width,
        result.height
    );
    ctx.putImageData(outputImageData, 0, 0);
}

Complete Processing Pipeline

async function processImage(imageData, width, height) {
    // Step 1: Downscale
    const scaled = await downscaleImage(
        imageData, width, height,
        width / 2, height / 2,
        { centroids: 4, iterations: 5 }
    );
    
    // Step 2: Quantize colors
    const quantized = await quantizeColorsMedianCut(
        scaled.data,
        scaled.width,
        scaled.height,
        { numColors: 8, dithering: true }
    );
    
    return quantized;
}

Extract Color Palette

async function getPalette(imageData) {
    const palette = await extractColorPalette(imageData, 16);
    console.log(`Found ${palette.count} colors:`, palette.colors);
    // Returns array of {r, g, b} objects
}

Analyze Colors with Z-Order Sorting

async function analyzeColors(imageData) {
    const { analyze_colors } = await init();
    
    // Get up to 256 colors sorted by Z-order (groups similar colors)
    const analysis = analyze_colors(imageData, 256, 'z-order');
    
    // Access color information
    analysis.colors.forEach(color => {
        console.log(`${color.hex}: ${color.percentage.toFixed(2)}% (${color.count} pixels)`);
    });
    
    // Generate CSS variables
    const cssVars = analysis.colors
        .slice(0, 10)  // Top 10 colors
        .map((c, i) => `--color-${i+1}: ${c.hex};`)
        .join('\n');
}

Get Dominant Colors

async function getDominantPalette(imageData) {
    const { get_dominant_colors } = await init();
    
    // Get 16 dominant colors, ignoring colors below 0.1% coverage
    const dominant = get_dominant_colors(imageData, 16, 0.1);
    
    // Create HTML palette display
    const paletteHTML = dominant.colors
        .map(c => `
            <div style="display: inline-block;">
                <div style="width: 50px; height: 50px; background: ${c.hex};"></div>
                <small>${c.percentage.toFixed(1)}%</small>
            </div>
        `)
        .join('');
}

Export Color Analysis Results

// Export as JSON
const colorData = {
    palette: analysis.colors.map(c => ({
        hex: c.hex,
        rgb: [c.r, c.g, c.b],
        usage: c.percentage
    }))
};

// Export as CSS custom properties
const css = `:root {
${analysis.colors.slice(0, 20).map((c, i) => 
    `  --palette-${i}: ${c.hex}; /* ${c.percentage.toFixed(1)}% */`
).join('\n')}
}`;

// Export as SCSS/Sass variables
const scss = analysis.colors.slice(0, 20)
    .map((c, i) => `$color-${i}: ${c.hex};`)
    .join('\n');

Parameter Guidelines

Quantization Method Selection

• Median Cut: Use for photographs, natural images, gradients
• K-Means: Use for graphics, logos, illustrations with flat colors

num_colors (2-256)

• 2-4: Extreme stylization, poster effect
• 8-16: Retro gaming aesthetic
• 32-64: Good balance of quality and compression
• 128-256: Near-original quality with reduced file size

dithering (true/false)

• Enable: For smooth gradients and photographs
• Disable: For pixel art or when crisp edges are needed

iterations (K-Means only, 1-50)

• 5-10: Fast processing, good results
• 20-30: Better color accuracy
• 40-50: Maximum quality, slower processing

Performance Optimizations

Algorithm Complexity

• Median Cut: O(n log n) where n = unique colors
• K-Means: O(n × k × i) where n = pixels, k = colors, i = iterations
• Dithering: O(w × h) single pass through image

WebAssembly Optimizations

• K-means++ initialization for better convergence
• Weighted color averaging based on pixel frequency
• Efficient color distance calculations
• Floyd-Steinberg dithering with minimal memory overhead

Build Instructions

Prerequisites

• Rust toolchain (curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh)
• wasm-pack (curl https://rustwasm.github.io/wasm-pack/installer/init.sh -sSf | sh)

Building

chmod +x build.sh
./build.sh

Comparison: Quantization Methods

| Method | Best For | Speed | Quality | Dithering Support | |--------|----------|-------|---------|-------------------| | Median Cut | Photos, gradients | Medium | Excellent | Yes | | K-Means | Graphics, logos | Fast | Very Good | Yes | | K-Centroid Resize | Downscaling | Fast | Good | No |

Advanced Features

Custom Initialization

The K-means algorithm uses K-means++ initialization for optimal starting centroids, ensuring better convergence and more consistent results.

Weighted Clustering

Colors are weighted by their frequency in the image, ensuring common colors are better represented in the final palette.

Error Diffusion

Floyd-Steinberg dithering distributes quantization errors to neighboring pixels, creating smoother gradients with limited colors.

License

Converted to Rust/WebAssembly for web usage. Original K-Centroid algorithm from Aseprite Lua script.