kam@dlogics.UUCP (Kevin Mitchell) (11/29/89)
I'm using a Floyd-Steinburg dither to reduce the number of colors in an image. To find the colors I need quickly, I'm using an inverse table- a three-dimensional array indexed by color value yielding the color index to put into the image. Right now, I'm comparing each color position in the inverse table to each color in the color lookup table to find the index I want. Since I'm using the Pythagorean Theorem to find the distance, I'm executing thousands of multiplications and it takes a long time (Macintosh Plus; 68000 at 8Mhz). I must be missing something obvious, since I know that there are fast implementations out there; such as in Apple's color QuickDraw software. Please reply if you have any comments on: o Fast ways of stuffing inverse color tables. o Better ways of converting colors to color indices. Thanks. -- Kevin A. Mitchell (312) 266-4485 Datalogics, Inc Internet: kam@dlogics.UUCP 441 W. Huron UUCP: ..!uunet!dlogics!kam Chicago, IL 60610 FAX: (312) 266-4473
oster@dewey.soe.berkeley.edu (David Phillip Oster) (11/30/89)
In article <248@dlogics.UUCP> kam@dlogics.UUCP (Kevin Mitchell) writes: >I'm using a Floyd-Steinburg dither to reduce the number of colors in >an image. To find the colors I need quickly, I'm using an inverse table- >a three-dimensional array indexed by color value yielding the color index >to put into the image. >I must be missing something obvious, since I know that there are fast >implementations out there; such as in Apple's color QuickDraw software. I do this in the BarneyScan Mac color scanner driver. There is no need to do multiplies to compute the pythagorean distance between the color you've got and the closest color in the color table. Consider: If you use a color cube that is a power of two on a side, and is uniformly distributed in color space, you can just use the appropriate number of high order bits of red, blue, and green to index directly to the closest color. You can avoid round off by adding an appropriate offset to your original color before you start. The Floyd-Steinberg dithering algorithm will propogate the error between the color you want and the color you get, so the next pixels will pick up the slack. If your color aren't uniformly distributed, you can still use a uniform color cube to get you to the head of a list of colors that are close to the one you've got, then you can binary search the list to find the actual one. This is still alot better than binary searching the entire color cube. > The mac is a detour in the inevitable march of mediocre computers. > drs@bnlux0.bnl.gov (David R. Stampf) --- David Phillip Oster -master of the ad hoc odd hack. Arpa: oster@dewey.soe.berkeley.edu Uucp: {uwvax,decvax}!ucbvax!oster%dewey.soe.berkeley.edu
pest@konech.UUCP (Wolfgang Pest) (12/01/89)
In article <248@dlogics.UUCP>, kam@dlogics.UUCP (Kevin Mitchell) writes: > > Right now, I'm comparing each color position in the inverse table to > each color in the color lookup table to find the index I want. Since I'm > using the Pythagorean Theorem to find the distance, I'm executing thousands > of multiplications and it takes a long time (Macintosh Plus; 68000 at 8Mhz). > > I must be missing something obvious, since I know that there are fast > implementations out there; such as in Apple's color QuickDraw software. I am not very experienced in computer graphics, but your problem is mentionned briefly in the latest issue of a German computer journal, called "c't" (issue 12/89 pp. 166-178) and I hope I have understood that article. There the author describes the method you are using in detail and mentions that it could be made more efficient by "pre-sorting the color lookup table in sub-cubes of the RGB space and determining the nearest neighbours". (Instead of comparing with _each_ entry of the color index table, he means obviously). As a reference, he gives "Heckbert, P.: Color Image Quantization for Frame Buffer Display, SIGRAPH 1982 Proceedings, pp. 297-307"