rosenbl@cis.ohio-state.edu (Robert Rosenblum) (10/20/89)
I'm writing an application which involves taking a given rgb value and
finding the color in the color map which is closest. My routine
performs a linear search through the color map, comparing the
"distance" between my rgb value and each color map entry, and the
index of the closest color is returned. However, this technique is
very slow.
Is there is a more efficient way to find the closest color in a color
map? Any help would be greatly appreciated.
Thanks in advance.....
Rob Rosenblum
Rob Rosenblum
The Ohio State University
Department of Computer and Information Science
2036 Neil Ave. Columbus OH USA 43210-1277
rosenbl@cis.ohio-state.edu
or ...!osu-cis!cis.ohio-state.edu!rosenblerichs@microsoft.UUCP (Erich Stehr) (10/20/89)
In article <67563@tut.cis.ohio-state.edu> rosenbl@cis.ohio-state.edu (Robert Rosenblum) writes: >My routine >performs a linear search through the color map, comparing the >"distance" between my rgb value and each color map entry, and the >index of the closest color is returned. However, this technique is >very slow. Are you doing a square root for each iteration? If you are, that's one of your problems. All you need is the relative "distance" between the colors, and the squares of the distances will have the same relative ordering. Erich Stehr "The Sorceress' Apprentice" uunet!microsoft!erichs
bdb@becker.UUCP (Bruce Becker) (10/21/89)
In article <67563@tut.cis.ohio-state.edu> rosenbl@cis.ohio-state.edu (Robert Rosenblum) writes: |I'm writing an application which involves taking a given rgb value and |finding the color in the color map which is closest. My routine |performs a linear search through the color map, comparing the |"distance" between my rgb value and each color map entry, and the |index of the closest color is returned. However, this technique is |very slow. | |Is there is a more efficient way to find the closest color in a color |map? Any help would be greatly appreciated. I needed to do this some time ago, so I'll try to remember roughly what I did. First, form an octree from the available color palette such that each cell contains a single color. This is done by inserting cells into the tree and subdividing when a target cell is already occupied. Once this is done the test rgb value is test-inserted into the octree, and compared in distance to the target cell contents and all adjacent neighbors. The worst case # of distance measurements is 27, but usually it is far less. A useful variant is to convert rgb to a form which expresses hue saturation and value in orthogonal axes. (HSV as usually implemented does NOT meet this criterion). One way to do this is to convert to Yxy CIE form, and produce hue & saturation values by: x = xc - xw y = yc - yw hue = arctan(y/x) (0.0 if x == 0.0) 2 2 sat = sqrt(x + y ) Where xc,yc are the CIE color values and xw,yw are for the reference white. YIQ values can be used for the conversion without much problem to the end result. If the octree and the test color are expressed in these terms such that the relative weighting of the distance function is something like 4:2:1 for normalized brightness:hue:saturation values, then it is possible to get better matches from a visual point of view, especially when the reference palette is limited or has a poor perceptual distribution. Remember that this is off the top of my head from work done some years ago; your mileage may vary; contents have certainly settled during shipment; etc... Cheers, -- .... Bruce Becker Toronto, Ont. w \**/ Internet: bdb@becker.UUCP, bruce@gpu.utcs.toronto.edu `/C/-e BitNet: BECKER@HUMBER.BITNET _/ >_ "But... but.. reality isn't *real*..." - Pippy the Zkinhead
kensy@microsoft.UUCP (Ken Sykes) (10/21/89)
In article <8126@microsoft.UUCP> erichs@microsoft.UUCP (Erich Stehr) writes: >In article <67563@tut.cis.ohio-state.edu> rosenbl@cis.ohio-state.edu (Robert Rosenblum) writes: >>My routine >>performs a linear search through the color map, comparing the >>"distance" between my rgb value and each color map entry, and the >>index of the closest color is returned. However, this technique is >>very slow. > >Are you doing a square root for each iteration? If you are, that's >one of your problems. All you need is the relative "distance" between >the colors, and the squares of the distances will have the same relative >ordering. > >Erich Stehr "The Sorceress' Apprentice" uunet!microsoft!erichs The real problem here is searching (I assume) 256 entries for each pixel. Paul Heckbert used a local search technique in his paper on color reduction to reduce the list size: "Color Image Quantization for Frame Buffer Display" Paul Heckbert ACM Transactions on Computer Graphics Vol 16, Number 3 (July 1982) pp. 297 - 304 Using this technique he was able to reduce the average number of tests from 256 to 11 for his test suite of 17 images. Definitely worth looking into. If anyone knows of other methods that are faster or use less memory, please post! Sincerely, Ken Sykes
garnett@rpp386.cactus.org (John Garnett) (10/21/89)
In article <67563@tut.cis.ohio-state.edu> rosenbl@cis.ohio-state.edu (Robert Rosenblum) writes: >I'm writing an application which involves taking a given rgb value and >finding the color in the color map which is closest. My routine >performs a linear search through the color map, comparing the >"distance" between my rgb value and each color map entry, and the >index of the closest color is returned. However, this technique is >very slow. > >Is there is a more efficient way to find the closest color in a color >map? Any help would be greatly appreciated. You may wish to investigate "An Algorithm for Finding Best Matches in Logarithmic Expected Time" by Jerome M. Friedman, Jon Louis Bentley, and Raphael Ari Finkel in the September 1977 issue of the _ACM Transactions on Mathematical Software_, p. 209. -- +------------------------------------+-----------------------------------+ | John Garnett | Base 1.9 | | garnett@rpp386.cactus.org | | | {bigtex|texbell}!rpp386!garnett | "It's almost binary" |
planting@hobbes.cs.pittsburgh.edu (Dr. Harry Plantinga) (10/23/89)
In article <8134@microsoft.UUCP> kensy@microsoft.UUCP (Ken Sykes) writes: >The real problem here is searching (I assume) 256 entries for each pixel. >Paul Heckbert used a local search technique in his paper on color >reduction to reduce the list size... > >If anyone knows of other methods that are faster or use less memory, please >post! I don't know if this is Paul Heckbert's technique, but in the Macintosh toolbox Apple uses the following technique: They construct an inverse color table based on the first 3-, 4-, or 5- bits each of R, G, and B. Thus, in order to find the best match for a given color, you concatenate the first few bits of the R, G, and B components and look up the best match in the inverse table. If there is more than one possibility, they are all stored and searched sequentially. This technique uses a table with 512, 4096, or 32768 entries.