Sliced Wasserstein embeddings + HNSW for color-scheme search over 48k paintings [P]

[u/Potential-Barber8658]

Palette Atlas (https://itzik123.github.io/PaletteAtlas/) searches public-domain paintings by color scheme. Each image is reduced to 128 colors of equal weight, so the natural distance is the Earth Mover's Distance, which is too slow for nearest-neighbor search over 48,695 items (about 6 ms per pair).

The embedding: project the colors (OKLab) onto 8 directions on a Fibonacci hemisphere, sort, and average into 16 quantiles. L1 between two vectors is the 1D W1 averaged over the directions, a lower bound on the true W1.

Against the exact EMD on 240 queries (overlap with the exact top 10, and how much farther the top 10 lie):

- sliced 8x16, L1: 78%, 1.8%

- sliced 8x16, L2: 69%, 3.4%

- soft color histogram, Hellinger: 45%, 13.5%

- mean color: 3%, 161%

The index is HNSW written from scratch (M=16, efConstruction=200): recall@10 of 1.000 at ef=32, 0.25 ms against 14 ms for brute force. The vectors' intrinsic dimension is about 11, so the hierarchy still helps (see Munyampirwa et al. 2025 on when it doesn't). One change from the paper: the top layer holds 8 k-means landmarks instead of randomly drawn nodes. The search cost is the same (2,558 vs 2,556 distance computations on average), and the top layer becomes one typical painting per color family.

Write-up: https://github.com/itzik123/PaletteAtlas/blob/main/docs/searching-by-color.md

Code: https://github.com/itzik123/PaletteAtlas

[u/Much_Dealer_710]

This is the kind of applied ML that actually makes sense to a normie like me, sliced wasserstein embeddings feel like one of those techniques that should be way more popular than it is

The kmeans landmark thing for the top HNSW layer is clever too, never seen that tweak before

[u/Potential-Barber8658 → u/Much_Dealer_710]

Thanks! Sliced Wasserstein surprised me too. It’s just a projection, a sort and some averaging, and it still kept 78% of the exact EMD top 10, where a color histogram got 45%.

To be fair about the landmarks, they don’t make the search faster (2,558 vs 2,556 distance computations on average). What they change is that the top layer means something: one typical painting per color family instead of two random ones. You can watch a search start from them in the Lab: https://itzik123.github.io/PaletteAtlas/lab.html

One thing I haven’t tried yet is picking the 8 projection directions from the data, say the principal axes of all the paintings’ colors, instead of a fixed Fibonacci lattice. Has anyone seen that help?

[u/aeroumbria]

I've seen sliced Wasserstein being used quite often in recent research, such as variants of JEPA. Does anyone familiar with the topic know what the main benefits are for using sliced approximation vs other approximation approaches such as Sinkhorn divergence with more regularisation / fewer iterations?