A bit of tiling...

Question

I just finished writing a small script to combine a lot of png pictures into a bigger one for CSS Sprite.

So basically, I have a list of dimensions [(w1,h2), ..., (wn,hn)] and I need to put them into a frame with dimension (W,H) with WH as small as possible. (Of course they cannot overlap)

The heuristic I used is obviously not optimal. I was wondering if you had any ideas on the subject? Do you think some smarter constraint, like grouping images with similar histograms would make the png smaller?

Answer 1

About making the resulting png smaller:

Be sure to use best compression level (level 9) and if possible, use PNGOUT to compress the PNG even better (there's a PNGOUT plugin for IrfanView, too).

Grouping images with similar histograms could be good, note that PNG uses zLib which uses a sliding window, so it work best if you group the images horizontal.

EDIT: Same for free space. It should be better to have free space at the top or the bottom of the image than at the left or right. The color of the free space shouldn't really matter, some color or black or white should be fine.

By the way, the size of the zLib sliding window is 32K, so it's not that good for detecting image duplicates if images are big. You'd better process the images yourself with an own algorithm in this case and use some duplicate removal or delta filter.

Answer 2

It is not obvious from how you pose the question whether it is the dimensions of the picture, or the size of the PNG file, which you want to optimize, as picture histograms do not affect their dimensions (width and height).

However, finding minimal K so that, say, max(W, H) < K, so that all your pictures can be fit into a rectangular area W wide and H tall is an NP-complete problem, which means that it is difficult to solve well in general. See for example here.

Answer 3

How does the output from your script compare to the output from ImageMagick?