How do I reduce a bitmap to a known set of RGB colours

Question

For a hobby project I'm going to build a program that when given an image bitmap will create a cross-stitch pattern as a PDF. I'll be using Cocoa/Objective C on a Mac.

The source bitmap will typically be a 24bpp image, but of the millions of colours available, only a few exist as cross-stitch threads. Threads come in various types. DMC is the most widely available, and almost their entire range is available as RGB values from various web sites. Here's one, for instance.

DMC#  Name               R   G   B
----- ------------------ --- --- ---
blanc White              255 255 255
208   Lavender - vy dk   148  91 128
209   Lavender - dk      206 148 186
210   Lavender - md      236 207 225
211   Lavender - lt      243 218 228
      ...etc...

My first problem, as I see it, is from a starting point of the RGB from a pixel in the image choosing the nearest colour available from the DMC set. What's the best way of finding the nearest DMC colour mathematically, and ensuring that it's a close fit as a colour too?

Although I'll be using Cocoa, feel free to use pseudo-code (or even Java!) in any code you post.

Answer 1

Use the LAB color space and find the color with the nearest euclidean distance. Doing this in the RGB color space will yield counter-intuitive results. (Or use the HSL color space.)

So just iterate over each pixel and find the color with the closest distance within the color space you choose. Note that the distance must be computed circularly for some color spaces (e.g. those employing hue).

(Most color quanization revolves around actually choosing a palette, but that has already been taken care of in your case, so you can't use the more popular quantization techniques.)

Also, check out this question.

To find the HSB hue in Cocoa, it looks like you can use the getHue method declared in NSColor.h.

However, if you just convert an image to a cross-stitch design using this technique, it will be very hard to actually stitch it. It will be full of single-pixel color fields, which sort of defeats the purpose of cross-stitching.