Request for algorithm to reduce number of used colours...

Thread View: sci.image.processing

3 messages

[T] Back to Threads [V] Tree View [G] Group Articles

3 total messages Started by Angus "Fluffy" Rae Wed, 22 Jul 1992 15:33

#146

Author: Angus "Fluffy" Rae
Date: Wed, 22 Jul 1992 15:33

22 lines
1377 bytes

Hi. 

A friend of mine has written a program to take (on an Atari ST) a 512
colour picture produced by GFA-Raytrace and reduce the number of colours
to 16 to make a standard Degas picture. This he does by simply counting
the number of times each of the 512 possible colours are used and using
the 16 most popular, converting the rest to the closest of the popular
16. This is a) slow and b) doesn't give the 16 most _useful_ colours.

Can anyone point me at an algorithm for this sort of colourmap
reduction? a) and b) above might be mutually exclusive - a fast routine
that is pretty kludgy as far as colour selection goes would also be
useful. I've heard the phrase "mean-cut" or something like it in
reference to b).

Thanks in advance for any help.

-- 
Angus G Rae, the Cuddly Vampire Teddy Bear [asr@castle.edinburgh.ac.uk]
CATHY VoiceMail, Computer Science Dept., Edinburgh University
"I'm on the run from the Facist Police with a murderer and
 a mass murderer and a man in a bri-nylon shirt."  Rimmer, Red Dwarf V

Re: Request for algorithm to reduce number of used colours...

#218

Author: Michael Jones
Date: Tue, 28 Jul 1992 20:49

25 lines
1632 bytes

In article <24050@castle.ed.ac.uk> asr@castle.ed.ac.uk (Angus "Fluffy" Rae) writes:
[ description of color palette reduction algorithm deleted ]
>Can anyone point me at an algorithm for this sort of colourmap
>reduction? a) and b) above might be mutually exclusive - a fast routine
>that is pretty kludgy as far as colour selection goes would also be
>useful. I've heard the phrase "mean-cut" or something like it in
>reference to b).

The best paper I've seen on this is "Color Image Display with a Limited
Palette Size", Bouman and Orchard, Proceedings of the SPIE Visual
Communications and Image Processing Conference IV, SPIE Vol. 1199,
pp 522-533, 1989

This is basically the median split algorithm using statistical analysis
for each node to determine the direction and location of the split.
(you do have to find the principal eigenvalue of a 3x3 matrix, so have
your _Numerical Recipes_ handy).

I've gotten excellant results by combining this median split algorithm
with a couple of iterations of the Linde-Buzo-Grey algorithm and
Floyd-Steinberg dithering, but the LBG algorithm is quite slow.

Mike Jones

Re: Request for algorithm to reduce number of used colours...

#242

Author: Angus "Fluffy" Rae
Date: Thu, 30 Jul 1992 15:09

18 lines
1175 bytes

Thanks to everyone who responded to me on this request - I've responded
to those who Emailed individually (I hope) but if I missed you for some
reason, thanks anyway!

For those of you intersted, the original version of the software I'm
helping to revise is on the cover disk of ST Format magzine, not sure
which issue... it's part of a package of three GFA Raytrace utilities.
The author is listed as "Stargate 42".

The next version is expected sometime before the Big Crunch.
:-)


-- 
Angus G Rae, the Cuddly Vampire Teddy Bear [asr@castle.edinburgh.ac.uk]
CATHY VoiceMail, Computer Science Dept., Edinburgh University
"I'm on the run from the Facist Police with a murderer and
 a mass murderer and a man in a bri-nylon shirt."  Rimmer, Red Dwarf V

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads