perf: Replace O(n²) color clustering with scipy.spatial.cKDTree #22

New issue

Closed

opened 2026-06-10 05:45:46 +00:00 by Mark · 0 comments

Mark commented

2026-06-10 05:45:46 +00:00

Owner

Problem

image_processor.py:318 and color_quantizer.py:295 use nested loops to compare every pair of unique colors via Delta E. This is O(n²) where n = number of unique colors. Each Delta E calculation involves CIELAB conversion and Euclidean distance.

For images with 100-500 unique colors after quantization, this means 5K-125K expensive Delta E computations.

Proposed Fix

Pre-compute LAB values for all unique colors in a single batch, then use scipy.spatial.cKDTree for nearest-neighbor clustering:

from scipy.spatial import cKDTree

lab_colors = np.array([rgb_to_lab(c) for c in unique_colors])
tree = cKDTree(lab_colors)
assigned = [False] * len(unique_colors)
for i, color1 in enumerate(unique_colors):
    if assigned[i]:
        continue
    neighbors = tree.query_ball_point(lab_colors[i], delta_e_threshold)
    cluster = [unique_colors[j] for j in neighbors if not assigned[j]]
    assigned[i] = True
    for j in neighbors:
        assigned[j] = True
    merged_colors.append(np.round(np.mean(cluster, axis=0)).astype(int))

Impact

5-20x faster for images with many unique colors.

Files

src/raster/image_processor.py:318-336
src/raster/color_quantizer.py:295-320

## Problem `image_processor.py:318` and `color_quantizer.py:295` use nested loops to compare every pair of unique colors via Delta E. This is O(n²) where n = number of unique colors. Each Delta E calculation involves CIELAB conversion and Euclidean distance. For images with 100-500 unique colors after quantization, this means 5K-125K expensive Delta E computations. ## Proposed Fix Pre-compute LAB values for all unique colors in a single batch, then use `scipy.spatial.cKDTree` for nearest-neighbor clustering: ```python from scipy.spatial import cKDTree lab_colors = np.array([rgb_to_lab(c) for c in unique_colors]) tree = cKDTree(lab_colors) assigned = [False] * len(unique_colors) for i, color1 in enumerate(unique_colors): if assigned[i]: continue neighbors = tree.query_ball_point(lab_colors[i], delta_e_threshold) cluster = [unique_colors[j] for j in neighbors if not assigned[j]] assigned[i] = True for j in neighbors: assigned[j] = True merged_colors.append(np.round(np.mean(cluster, axis=0)).astype(int)) ``` ## Impact 5-20x faster for images with many unique colors. ## Files - `src/raster/image_processor.py:318-336` - `src/raster/color_quantizer.py:295-320`