color quantization algorithm of Photoshop & ImageMagick
by
generate palettes from RGB image) used by Adobe Photoshop 4 & 5?
I'm writing some color quantization code and it basicly does two things:
generating a 256-color palette from an RGB image, and dither an RGB
image to a 256-color palette.
Comparing to Photoshop, speed-wise my code is not noticeably different.
But Photoshop has much better output quality. Basicly my output images
suffer from grainy-ness. But if I use Photoshop to quantize an image
first and save out the resulting palette, and then use my code to dither
the image to the palette generated by Photoshop, then the my output
image is very comparable to Photoshop output. I suppose this means my
dithering code is OK, but something is wrong with my palette-generating
code.
ImageMagick (www.imagemagick.org) program generates output with
comparable quality to Photoshop, however it seems a lot slower, maybe
this is because ImageMagick is using C code while Photoshop has
hand-tune assembly code ? (it's just a guess I don't know if Photoshop
has assembler code for quantization and dithering) ImageMagick has a web
page describing the algorithm they used
(http://www.imagemagick.org/www/quantize.html), to me it looks similar
to octree but not quite like octree. I found it hard to visualize
exactly how the algorithm works by reading that web page. I looked at
ImageMagick's quantization source code, which is like 30 pages and even
more difficult to understand than the web page. Any online documentation
that explains it better ?
I know there're algorithms like Heckbert median-cut, octree, uniform,
popularity, variance-based median cut, SOM, what algorithm do you think
Photoshop is using ?
Thanks, Bo
Adam D. Moss
I have followed up only to sci.engr.color since that is
the group I actually read.
by wrote:
> Anyone care to speculate on the color quantization algorithm (used to
> generate palettes from RGB image) used by Adobe Photoshop 4 & 5?
Which? The algorithms used by Photoshop 4 and Photoshop 5's 'best'
quantization are very different.
> I know there're algorithms like Heckbert median-cut, octree, uniform,
> popularity, variance-based median cut, SOM, what algorithm do you think
> Photoshop is using ?
I have examined the output of PhotoShop's quantizer rather than it's
dithering, so I can only speak of that. PS4 appears to use a median-cut
in very coarse RGB space. Mediocre quality. PS5's 'best' quantization
seems to operate in L*A*B* space and the results are very good, but I am
unsure of the technique. I would suspect that it's something akin to
Gaussian clustering if the 'best' quantization is rather slow, but I
have
no idea of its speed as I only have output and no test setup (anyone?).
--Adam @ gimp . org
Tim Boescke
> I'm writing some color quantization code and it basicly does two things:
> generating a 256-color palette from an RGB image, and dither an RGB
> image to a 256-color palette.
>
> Comparing to Photoshop, speed-wise my code is not noticeably different.
> But Photoshop has much better output quality. Basicly my output images
> suffer from grainy-ness. But if I use Photoshop to quantize an image
> first and save out the resulting palette, and then use my code to dither
> the image to the palette generated by Photoshop, then the my output
> image is very comparable to Photoshop output. I suppose this means my
> dithering code is OK, but something is wrong with my palette-generating
> code.
Photoshop prior to 4.0 used an _extremly_ bad algorithm. But now it is quite
good.
I would recommend you to do a websearch for "Neuquant". This is a quantizer
that
uses Kohonen Neural Networks. Its quite slow, but the quality is among the
best
you can get.
Adam D. Moss
> Photoshop prior to 4.0 used an _extremly_ bad algorithm. But now it is quite
> good.
>
> I would recommend you to do a websearch for "Neuquant". This is a quantizer
> that
> uses Kohonen Neural Networks. Its quite slow, but the quality is among the
> best
> you can get.
So is this PhotoShop 5's 'best' quantizer? If so I presume that it
it not operating in RGB space and/or has other improvements -- I
experimentally integrated NeuQuant with GIMP 'as-is' about 18 months
ago but was disappointed with the speed/quality on my testsuite;
certainly the implementation provided on the NeuQuant page does not
seem to come close to the (rather good) quality of Photoshop 5.0's
'best' technique.
--Adam
Uwe Behrens
>
> > I'm writing some color quantization code and it basicly does two things:
> > generating a 256-color palette from an RGB image, and dither an RGB
> > image to a 256-color palette.
> >
> > Comparing to Photoshop, speed-wise my code is not noticeably different.
> > But Photoshop has much better output quality. Basicly my output images
> > suffer from grainy-ness. But if I use Photoshop to quantize an image
> > first and save out the resulting palette, and then use my code to dither
> > the image to the palette generated by Photoshop, then the my output
> > image is very comparable to Photoshop output. I suppose this means my
> > dithering code is OK, but something is wrong with my palette-generating
> > code.
>
> good.
Let me add that the quality of a color quantization depends to a *very*
large amount on the color space used. In order to produce good results,
you must choose a perceptually uniform space, which RGB is *not*!
I suggest you have a look at the very good colorspace faq posted monthly
to comp.graphics.agorithms by Charles Poynton (sp?). Look at www.deja.com
I set f'up to 'comp.graphics.algorithms' to avoid excessive crossposting.
Cheers
--
__________________________________________________________________________
Uwe Behrens <beh...@acm.org> (aka <uwe.b...@gmd.de>)
Tim Boescke
> > Photoshop prior to 4.0 used an _extremly_ bad algorithm. But now it is
quite
> > good.
> >
quantizer
> > that
> > uses Kohonen Neural Networks. Its quite slow, but the quality is among
the
> > best
> > you can get.
>
> So is this PhotoShop 5's 'best' quantizer? If so I presume that it
Photoshop probably usues an other algorithm, I have no idea what
photoshop is actually using.
> it not operating in RGB space and/or has other improvements -- I
> experimentally integrated NeuQuant with GIMP 'as-is' about 18 months
> ago but was disappointed with the speed/quality on my testsuite;
The neuquant.c source has some problems. The remapper is not
optimal. In addition the parameters for the network can be tweaked
for better quality.
Dont expect it to get really fast though.
Travis Anton
<t.bo...@tu-harburg.de> wrote:
> > I'm writing some color quantization code and it basicly does two things:
> > generating a 256-color palette from an RGB image, and dither an RGB
> > image to a 256-color palette.
> >
> > Comparing to Photoshop, speed-wise my code is not noticeably different.
> > But Photoshop has much better output quality. Basicly my output images
> > suffer from grainy-ness. But if I use Photoshop to quantize an image
> > first and save out the resulting palette, and then use my code to dither
> > the image to the palette generated by Photoshop, then the my output
> > image is very comparable to Photoshop output. I suppose this means my
> > dithering code is OK, but something is wrong with my palette-generating
> > code.
>
> Photoshop prior to 4.0 used an _extremly_ bad algorithm. But now it is quite
> good.
Was my educated impression that past 4.0 they still used the same old
weighted median cut. There are no differences in the effective results
from Photoshop 2.5 through the current version, though they changed the
hype and the dialog a bit along the way. Perhaps they changed something
else as well, but if so I have a hard time putting my finger on what makes
it better than before.
Like something along the lines as described in "Color Quantization by
Dynamic Programming and Principal Analysis" by Xiaolin Wu. I believe the
Quant GIMP plug-in uses a take off of that, too. Might be an example for
you.
I might have even been able to give some tip on your palette generation
without giving trade secrets away, but since I've no idea what you're
trying I can't...
I would guess, that you're either doing a simple median or popularity
algo, and have somewhere between jack and squat for interface so far or
speedwise there'd be quite a bit of difference between yours and
Photoshop's. I know ten ways that you can do better than Photoshop on
quality and size, but not how to match their speed while doing as well or
better. Theirs is quite fast.
Their dithering is actually pretty hard to beat for visual quality, so if
you've got your dithering doing as well as them, you aren't off to a bad
start. That is usually the harder piece of the puzzle.
Unless of course, you haven't thrown a comprehensive test suite of images
at it, and you don't realize the situations where your dithering may fall
on it's face.
> I would recommend you to do a websearch for "Neuquant". This is a quantizer
> that
> uses Kohonen Neural Networks. Its quite slow, but the quality is among the
> best
> you can get.
Makes nice palettes, unless you have a picture of a red ball on a grass
lawn, then you'll get a green ball on a green grass lawn. It's not quite
ready for prime time in the sample code configuration, in my opinion, but
if you get really skippy there is some potential there as long as speed
isn't your main criteria. You can find it at:
http://www.ozemail.com.au/~dekker/NEUQUANT.HTML
You want a nice, easy text book compromise between good and fast use
octree. If I remember right, that's what ImageMagick uses. You won't do
better with any of the text book algorithms.
But you can always do better than the text book ones... I just can't say
how or I loose my job ;)
--
Travis Anton, Digital Spokes Model
BoxTop Software, Inc. - http://www.boxtopsoft.com
"BoxTop Software's ProJPEG plug-in consistently produces JPEG files
that are routinely 50% smaller than Photoshop." - Jon Warren Lentz,
Mac Art & Design, Photoshop 5 Reviewed.
Chris Cox
tra...@boxtopsoft.com (Travis Anton) wrote:
> In article <81m5eg$fie$1...@rztsun2.tu-harburg.de>, "Tim Boescke"
> <t.bo...@tu-harburg.de> wrote:
>
> > > I'm writing some color quantization code and it basicly does two things:
> > > generating a 256-color palette from an RGB image, and dither an RGB
> > > image to a 256-color palette.
> > >
> > > Comparing to Photoshop, speed-wise my code is not noticeably different.
> > > But Photoshop has much better output quality. Basicly my output images
> > > suffer from grainy-ness. But if I use Photoshop to quantize an image
> > > first and save out the resulting palette, and then use my code to dither
> > > the image to the palette generated by Photoshop, then the my output
> > > image is very comparable to Photoshop output. I suppose this means my
> > > dithering code is OK, but something is wrong with my palette-generating
> > > code.
> >
> > Photoshop prior to 4.0 used an _extremly_ bad algorithm. But now it is quite
> > good.
>
> Was my educated impression that past 4.0 they still used the same old
> weighted median cut. There are no differences in the effective results
> from Photoshop 2.5 through the current version, though they changed the
> hype and the dialog a bit along the way. Perhaps they changed something
> else as well, but if so I have a hard time putting my finger on what makes
> it better than before.
Actually, a LOT changed between 4.0 and 5.0. Then 5.5 added the selective
color and perceptual weighting to the mix.
Only part of the new algorithms can be found in literature.
In short: you're not going to match Photoshop 5.
Chris
Adam D. Moss
> In short: you're not going to match Photoshop 5.
I beg to differ. =) Hopefully with clean source to
replace talk with chalk, and before the end of time.
--Adam
Alan Murphy
Adam D. Moss <ad...@uk.uu.net> wrote in message
news:3843FEFB...@uk.uu.net...
Chris Cox
> Chris Cox wrote:
> > In short: you're not going to match Photoshop 5.
>
> I beg to differ. =) Hopefully with clean source to
> replace talk with chalk, and before the end of time.
Good luck -- but I _really_ doubt that you can match the results.
You might do better, or you might do worse, but you're not going to match.
Chris
--
Opinions expressed herein do not reflect those of my employer.
Blah, blah, blah, so-on and so-forth, yackety schmackety......