Path: utzoo!censor!becker!bdb
From: bdb@becker.UUCP (Bruce Becker)
Newsgroups: comp.graphics
Subject: Re: help with quick color map search
Message-ID: <964@becker.UUCP>
Date: 20 Oct 89 18:16:32 GMT
References: <67563@tut.cis.ohio-state.edu>
Reply-To: bdb@becker.UUCP (Bruce Becker)
Organization: G. T. S., Toronto, Ontario
Lines: 61

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