Posterize action for file size/bandwidth saving on PNGs

I would love to include it in this module, as I and, I guess, many others as well, could (should) use this option more often.

To be included:
- The effect should be easy and intuitive to use. Parameters that users may want to specify, should be on the effect form. The effect form should include some explanation.
- It should off course implement all image effect callbacks.
- The code should be clear, readable and conform Drupal coding standards (http://drupal.org/coding-standards). (I know that not all current code conforms so, but when I make changes I also update the code to be better conform the standards.)
- All functions, classes, files, etc should be documented according to code documentation standards (http://drupal.org/coding-standards/docs).
- Preferably, Imagemagick and GD should be supported!
- Where applicable, please use utility functions from this module (e.g. RGB form fields, RGB conversion utilities).
- Patch structure may be as being part of the coloractions submodule or as a separate submodule (like text effect).
- I would like you to join us as co-maintainer and that you give support to at least your own effect, but preferably all issues in general.

Off course, the main maintainer, dman, should agree as well.

Found this while trying to compress my PNG images for a certain preset to use only 32 colors. Copied the contents of the image_gd_posterize() function to a custom action and it worked like a charm!

Hope this could be added to the module! It reduced file size from 178kb to 40kb for a black/white/grey png.

BTW I barely see the difference in quality! Thanks!

I tested this patch and it appeared to work really well to save bandwidth for PNGs. I had to use 100 colors to get it to look nice with the GD toolkit. Unfortunately it won't work in a production environment for me because I need a solution that preserves transparency and this didn't appear to do that.

I haven't tried it with ImageMagick. I don't have that installed on my local machine just yet.

Well, switching to doing a full per-pixel process, and then doing a dozen calculations and things inside each pixel of that tight loop (twice) is sure to be a lot more inefficient (and 4x the memory) than just using the binary routines already available. Can you link to or explain the algorithm you are using there?
Without any theory documented, or any way to know what the expected difference is between this output and the normal one, I can't begin to make suggestions for improving it.
Your reference to http://php.net/manual/en/function.imagetruecolortopalette.php#44803 in the comment looks misleading. What are you actually doing here and why?

At this point, I'd consider making both available - with the the earlier basic algorithm available as a switch, and notes to the effect that switching to the high-fidelity pixel-based one may be painful for smaller servers. That would break though any reluctance on my part.
I just can't have processes that kill cheap servers so trivially, and uploading a retina HD image that goes through this algorithm can kill someones site.
(if imagecache generation fails, it tries again next time, so if the derivative is expected to show up, and balloons the memory, the server stops)

As an option for graphiceers however, I'm sure it has some advantage. I think the natural order of things will be
Out-of-the-box, you can use the GD version, which some folk may find a little muddy
If you care more, or work in hi-res, you should probably be using the ImageMagick toolkit by choice anyway.

Yeah, my first thought when I saw you splitting the channels was for colorize, but that's not the same thing at all. If you colorized them merged you'd just end up with grey :-)

I understand from reading the code what you've done there, but I was a little surprised at the process so I could not tell if I was missing something, or whether what you do is actually the trick...

What I see is you split off the three channels, and get three versions of the image, one made with n shades of red, one with n shades green, one with n shades of blue.
Soo, actually n*3 colors. But the patterns will be different, and red number 3 will be on the canvas in different places that blue number three.

When you recombine those palettes again, you have the potential to be making a new image containing n*n*n new colors.
No?
I can't quite see what the imagecolormatch() step does, though the docs hint that it changes the values of similar colors in the palette a bit. Seeing as the palette at that point will be monochrome, I'd imagine that this won't have a lot of hits. Though I may totally misunderstand that step.

What *I* imagine - from looking at your code - is that in the end you will have reduced the palette from 256*256*256 color down to n*n*n colors, ... which is a long way from reducing it to n.

Which is why I don't understand it. I'm missing something in your process.
Can you explain to me where I'm wrong?

(with pictures? :-)

I'd have to run diagnostics myself before I believed that your final color count was what you say it is...

Yeah, I thought as much.
I tried this patch, and ran the default image through it. I asked for 16 colors.
I got 1081.
And that's even considering it was starting from a lot of flat digital colors to begin with.
It's *better* than the 23431 colors the original has ... but it's not 16 colors.

identify -format %k filename

If I ask for 100 colors, what I actually get is 4,707

So... whatever your code is doing, it's not reducing the palette anywhere near as much as you think it is.

Ah. So I am actually misunderstanding the terminology 'posterize'. I guess it really does trace back to the old printing processes, as the name suggests.
Imagemagicks -posterize 3
does mean 3 levels of R, G and B each (plus zero I guess?)
And yeah, with three-color printing sheets, n runs of each can certainly produce n^3 effective colors.

When I do
convert sample.png -posterize 3 sample-posterize3.png

I get a result with 26 colors (though actually incredibly good given that palette, apart from the dithering).

So I misunderstand 'posterize' as 'reduce colors to a limited palette' - the palette IS, deliberately n^3

Your algorithm is true to that approach. It's my expectations that are wrong about the terminology.

Well, first, I don't think you'll win big as long as you are using a PHP-level per-pixel algorithm.
That will never be efficient. :-/

However, I can't deduce any way of avoiding it, if you are still having to build the process by hand.

Secondly, doing a per-pixel scan TWICE should be avoided. If you could calculate what to write at read-time would be better.
But seeing as you seem to need an 'adaptive' palette, I can't see a way out of that either.

Sooo.

Like above, if you just let GD proper do its best effort, and stop messing with it by hand you should be OK.

But note, that you can tell GD to use n^3, not just n.

Imagemagick 'posterize' 10 or 50
is equivalent to GD imagetruecolortopalette(1000) or imagetruecolortopalette(125000)
If you want to compare like-to-like.

As for file size. Well, GD just isn't as good when it comes to optimizing for saving (AFAIK)

If you 'posterize' a JPEG using GD, it will be for the visual effect only, not reliably impacting on the filesize anyway. I didn't think that jpeg algorithm was channel-based anyway, so I dunno why posterizing using this method would provide any wins!

Alpha however does have an answer. But I guess this means you've been testing on PNGs all along anyway? What are the filesize savings you see with JPEGs?

Well, we can't support just Imagemagick without a GD version.
But the primary thing about 'effects' is that they produce visually similar results. And the user gets to choose which of those is appropriate. And if we also affect filesize as well, that's secondary. But still an interesting feature, if there are real and consistent benefits.

The first way to measure "Output" is the visual result. "Posterize" is a visual effect. The filesize is a technical side-effect. But if it's also plain-color sort of picture being saved as PNG, it has that bonus.
I don't think we can get similar savings using the same method for all image types all the time - that just may not be possible.

PNGs saving JPEG-type images from the GD toolkit are pretty bad for filesize. Tweaks exist.
JPEG saving PNG-style images (logos and text and plain-colours) are pretty scrappy, in either toolkit.
So there will be no one-size-fits all.

But the effect of posterize as a visual Palette-limiter can go into the toolkit.
The advertised filesize reduction using all toolkits and all image types without visual degradation is not something that can be promised however.

It can go in with :
* if you are working mostly with PNGs
* and the images are logo-text like
* and you are using the imagemagick toolkit
= then you will also get a better filesize most of the time.

The rest of the time you just get the visual effect - but hopefully consistently.

So long as this doesn't start making filesize results worse, then it's just an 'effect' that folk can use.

> It also actually works fairly well with photo type images as you can see in the images attached at the top. Usually to get that reduction with JPG you would have more artifacting.
You must have a better monitor than mine.

Here is what I see when I look at your original, your posterized example, and what happens if I just ask Imagemagick to recompress your original with
convert hr10_sample_image_02_original.jpeg -quality 80 hr10_sample_image_02_recompressed.jpg

Zoomed in a few times, still can't pick it with my eyes.. But that's why I stare at code all day and let other folk squint at color differences and monitor gamma balances..
File sizes: 2.0M, 716K, 634K

The labels are in the second attachment. No peeking.

Are you sure that the filesize improvements you are seeing are not just Imagemagick doing its normal good job of compression? With or without posterizing?

Re alpha -
Try setting
imagealphablending($image->resource, FALSE);
BEFORE you set the pixels. If alpha blending was on at the time when you do imagesetpixel() , the new color paints over the top of the old one and combines. If it's off, then it would replace the pixel - which is what you are intending.

OK then. So - this filesize saving is only seen if working with strictly with PNG input and PNG output.

That fits with my understanding of the entropy-based JPEG algorithm (such as it is) where a palette-based change would get scrambled on save anyway.

If your output is jpg, then 'posterize' would be a visual effect only, and the main denominator on filesize will be the toolkit compression ratio.

If you are doing PNG to PNG, then reducing the palette is more likely to help a bit as the save algorithm (that imagemagick uses?) is largely palette-based (?).

If I understood the 'compression strategy' etc (I cannot comprehend all of what that explanation is telling me - it reads like it's self-contradictory to me), I'd still try to spend some time experimenting with those options, as in my gut I suspect that the maths designed specifically for delivering better filesizes at a binary level will be more clever than what we can do with pixel-pushing alone.
I know that the numbers mean quite different things between PNG and JPEG ... but I also imagine that different numbers (filter-type?) would produce different results - but I don't know how to evaluate when the degradation gets too bad.
All I know is I can take JPEGs down to 80 before the designer starts to notice ...

:-}

I can't figure this out any deeper. People write masters thesis' on this stuff.

But anyway - if we can just ensure that this effect will not totally kill small machines if installed, we can continue with putting it in...

Well, the concept of 'reduce palette' and 'posterize' are understood to be visually different effects anyway, so I don't think we can use the two algorithms interchangeably - or even really call them the same thing.
As posterize IS (as you have shown) a channel-based reduction then recombination, the look of the resulting image could be off by a lot if you compare the two methods. Though harder to distinguish with high numbers.

Speed is just too bad for underpowered servers, but it's memory footprint that is death and would lead to repeated attempts.
With the algorithm currently assigning at least 4x the size of an uncompressed image object in working memory ... I dunno.

This algorithm looks (I just scanned it) to be able to do its calculations in one pass.
http://www.axiomx.com/posterize.htm - though I'm not going into the maths.
- I suspect that your step of building the three three channels as full images, and then generating an adaptive palette reduction of them is not the same as using an equidistant range - which is what I'd naively expect from a 'traditional' screen-printing posterize process.

THIS algorithm is a lot more like what I would write:
http://www.qtcentre.org/threads/36385-Posterizes-an-image-with-results-i...

A single pass-though that can perform its actions directly on the source image would be much more performant

Applied patch works well.

Works quickly in Imagemagick (6.5.8-10 2012-03-08 with quality at 75%) and looks fine.
Reducing the sample png 164 KB
to 4 colors-per-channel takes it to 23.4 KB

Running the same under GD seemed just as quick (!) but saved it as the slightly larger 34.7 KB - which is about what I'd expect.

Ramping it up to a cleaner 50 colors-per channel (where there is still just visible banding on the PNG gradients)
IM: 117 KB
GD: 141 KB

... increasing it ... I still get slight banding on that PNG, even at 80 or 100 levels in IM.
Though GD is actually performing well here now! ... I can still just find banding at 150 if I really twist my monitor, though I've already met the sample filesize of 164KB, so no saving there (with GD)
However, I've got no problems at all with the performance now, and that's the biggest concern I had!

Moving from PNG to JPEG however...
I actually found that palette reduction hurts!
From a sample image (already slightly degraded from JPEG artifacts - as is common)
that starts at 349K ...
colors | IM | GD
(none) | 186K | 128K
150 | 191K | 129K
75 | 191K | 130K
25 | 199K | 135K (noticeably degraded)
5 | 265K | 166K (horrible of course)

By the time I get down to 5 levels, I can see that although the GD and IM effects are behaving equivalently, they are not the same, and are choosing quite different colors to dominate. Probably a rounding method difference still. That's to be expected.

Most interesting of all was that NOT running the palette reduction at all on either toolkit led to the best filesize :-B
Simply letting IM or GD open and re-save the JPEG file worked best. - given that I had my global 'quality' setting at a modest 75% already.

Anyway - the point now is that :
* the posterize effect works as advertised - equivalently (though not identical) in both toolkits
* the processing stress and memory footprint on the server under GD is less than 1/4 what it was in the first version, and seems as efficient as any other action we have. (not fantastic for huge images, but 1 or 2 seconds, not half a mnute now)

I'd be OK to RTBC this now and call any further work an update to it - If you are happy with this being stable enough now @corey.aufang ?

Due to #2060173: Support image labels (introduced by D7.23), I want to release a 7.x-1.4 version within a few days. I'm fine with adding this to that version as well. How about you @dman?

I believe we are ready to go on this. Currently it does what it says, and I'm OK with the performance.
Any further refinements can be follow-ups. It's RTBC

Committed. Thanks corey.aufang for all the work. Thanks dman for reviewing, testing and discussing the code and algorithms used.

I set it to NW as I want the following questions answered:
1 name of the effect
2 help text on the form
3 summary text

ad 1) To me, posterize is the technical action, wile "reduce file size" is the goal. Should we mention that in the name of the effect or should we accept that posterize can be an (artistic) effect on its own and that reducing file size is not always the goal?

ad 2) A bit more explanation of what colors per channel does mean and what to (typically) expect

ad 3) Imagemagick documentation defines posterize as:

-posterize levels

reduce the image to a limited number of color levels per channel.

Should we also use the term color levels?

I committed the code, as I want to refactor all of the coloractions code anyway, I will process your answers to the above questions in that round.

Given my test runs, I cannot sell 'file size reduction' as a feature of this effect at all, as
* there was only demonstrable size reduction on PNG-PNG conversions, and that within a specific range of image styles (not photos) and color levels. In all other cases, results varied
* Using compression settings of a few points difference had the biggest direct effect on file size, in both toolkits, and is what you really need to use if going for smaller images.
= this is a primarily visual effect.

I'm afraid we sort of do have to use the term 'color levels' which is at least consistent terminology with what you'll find in other docs and graphics programs. Though as I found, it's not completely intuitive.
That term could be replaced with a short story about old screen-printing techniques and how a clever printer could use 2 passes of red, green and blue stamps on "posters" to generate a result that actually has 8 effective colors on it... And that's called 'posterizing' :-}
TMI

OK, we stay with posterize as effect name. But I did notice quite some file size reduction in a past project where photos (jpg) were thumbnailed, bordered and rotated (transparent background). In that project I used Imagick::setImageDepth(8). Reproducing as Drupal image style (not sure if it is doing the same, but I guess it is):

a:3:{s:4:"name";s:12:"test_1854270";s:5:"label";s:12:"test 1854270";s:7:"effects";a:6:{i:217;a:3:{s:4:"name";s:21:"imagecache_autorotate";s:4:"data";a:0:{}s:6:"weight";s:3:"-10";}i:215;a:3:{s:4:"name";s:20:"coloractions_convert";s:4:"data";a:2:{s:6:"format";s:9:"image/png";s:7:"quality";s:2:"95";}s:6:"weight";s:2:"-9";}i:211;a:3:{s:4:"name";s:11:"image_scale";s:4:"data";a:3:{s:5:"width";s:3:"200";s:6:"height";s:3:"200";s:7:"upscale";i:1;}s:6:"weight";s:2:"-8";}i:214;a:3:{s:4:"name";s:26:"canvasactions_definecanvas";s:4:"data";a:4:{s:3:"RGB";a:1:{s:3:"HEX";s:7:"#333333";}s:5:"under";i:1;s:5:"exact";a:4:{s:5:"width";s:0:"";s:6:"height";s:0:"";s:4:"xpos";s:6:"center";s:4:"ypos";s:6:"center";}s:8:"relative";a:4:{s:8:"leftdiff";s:1:"3";s:9:"rightdiff";s:1:"3";s:7:"topdiff";s:1:"3";s:10:"bottomdiff";s:1:"3";}}s:6:"weight";s:2:"-7";}i:213;a:3:{s:4:"name";s:12:"image_rotate";s:4:"data";a:3:{s:7:"degrees";s:1:"6";s:7:"bgcolor";s:0:"";s:6:"random";i:0;}s:6:"weight";s:2:"-6";}i:219;a:3:{s:4:"name";s:22:"coloractions_posterize";s:4:"data";a:1:{s:6:"colors";s:2:"16";}s:6:"weight";s:1:"6";}}}

Perhaps the biggest file size reduction achieved here is unifying the color in the fully transparent part... No: without rotation I go from 64 to 25KB (16 levels)

Color versus color levels: number of colors within 1 (primary color) channel was also not intuitive to me, so I will go for color levels unless we can come up with something even better.

Changed colors to color levels. That completes this issue.

BTW: Can we optimize speed further by changing:

      $a = $rgb >> 24 & 255; // Alpha
      ...
      $color_combined = ($a << 24) | ($new_r << 16) | ($new_g << 8) | $new_b;

to:

$shift_left_24_255 = 255 << 24;
...
      $a = $rgb & $shift_left_24_255; // Alpha
      ...
      $color_combined = $a | ($new_r << 16) | ($new_g << 8) | $new_b;

Shaves off 2 shift operations per pixel...