Are there any compressors/tools that re-arrange/block-divide data(pictures)?

[NorthWay]

AFAIK (corrections welcome) both IFF and GIF store picture data on a line by line basis.
Colours are typically much more locally clustered, and this is also how JPEG (and others?) arrange pixel data to take advantage of local similarities.

Are there any compressors or other tools that will do such blocking or rearranging of data to increase compression ratios?
Can you affect the ratio for a standard IFF/GIF by re-arranging the palette and thereby the data combinations?

[temisu]

Well, all modern picture compressors have more context than a single scanline.

PNG has a pre-filter which takes input from 3 pixels from previous line and 1 previous pixel from same line. (after filtering it compresses the delta with deflate)

JPEG operates in blocks and JPEG 2000 and other wavelet compressors have naturally 2-dimensional context since the picture is filtered by both x and y axis.

IFF/ILBM is RLE-based. Only way to improve it by palette tricks would be to reduce the number of palette entries. (maybe to get rid of bitplanes)

GIF is LZW, same thing really. The encoding efficiency does not really depend on the ordering of the code words. Obviously dropping palette entries will have some effect since the initial dictionary is smaller.

[chb]

Originally Posted by NorthWay

AFAIK (corrections welcome) both IFF and GIF store picture data on a line by line basis.
Colours are typically much more locally clustered, and this is also how JPEG (and others?) arrange pixel data to take advantage of local similarities.

Are there any compressors or other tools that will do such blocking or rearranging of data to increase compression ratios?
Can you affect the ratio for a standard IFF/GIF by re-arranging the palette and thereby the data combinations?

For bitplane-based, run-length-encoded images, you can achieve some improvement by re-arranging the palette. Imagine e.g. a 4-bitplane image with a 2-color checkerboard pattern. If you'd use color 0 and color 15 for those two colors, you get the pattern in all bitplanes, so bad compressibility for RLE. If you use color 0 and 1, three out of for bitplanes are just constant -> perfect compressibility. In real world applications, the gains are of course lower, but I remember a thread here on EAB were a reduction of ~20% was given for real-world images.

[meynaf]

From what i've seen the best lossless image compression ratios are obtained by taking uncompressed chunky data and crunching that with good general purpose crunchers, e.g. you can take a windows bmp image and compress it with bzip2, you'll get a smaller file than with iff, gif or png.

[temisu]

Originally Posted by chb

For bitplane-based, run-length-encoded images, you can achieve some improvement by re-arranging the palette. Imagine e.g. a 4-bitplane image with a 2-color checkerboard pattern. If you'd use color 0 and color 15 for those two colors, you get the pattern in all bitplanes, so bad compressibility for RLE. If you use color 0 and 1, three out of for bitplanes are just constant -> perfect compressibility. In real world applications, the gains are of course lower, but I remember a thread here on EAB were a reduction of ~20% was given for real-world images.

IFF/ILBM RLE operates per-pixel (chunky) instead of per bitplane. You'd have save the image as uncompressed and then compress it by some generic compression algorithm to do this...

[meynaf]

Originally Posted by temisu

IFF/ILBM RLE operates per-pixel (chunky) instead of per bitplane. You'd have save the image as uncompressed and then compress it by some generic compression algorithm to do this...

No, IFF-ILBM is planar mode. It outputs first line for each plane, then next line for each plane, etc. Even IFF-24 is planar.

[invent]

Hi Northway, I did notice a refinement in the reduction of file size by arranging the indexed colour palette, possibly darkest/lightest or most common colours or some other random method?

Not sure if it was IFF or gif/png but had some success, this was back in the day of dialup modems and end of Amiga Classics era.

A quick test for example of exporting a png-8 file via photoshop with no distinguishable differences in colours of some sprites has a file size changing from 10.03K and 10.13K file just by changing from either "Selective" or "adaptive" palettes.

The test file "Rygar" sprites has 20 colour and I was saving as a 32 png file.

I hope this is some use, if I find something else will add more detail, but back in the day when I descovered the reduction I was very surprised.

Jpg files, only success was using some extra tools with masking but was time consuming selecting which areas I wanted more compressed (usually flat colours)

[idrougge]

Originally Posted by meynaf

No, IFF-ILBM is planar mode. It outputs first line for each plane, then next line for each plane, etc. Even IFF-24 is planar.

Well, it's neither per-bitplane or chunky. It's per-line, per-bitplane. That's why it's called InterLeaved BitMap.

[Leffmann]

Originally Posted by NorthWay

AFAIK (corrections welcome) both IFF and GIF store picture data on a line by line basis.
Colours are typically much more locally clustered, and this is also how JPEG (and others?) arrange pixel data to take advantage of local similarities.

I played a bit with this a while back and found that rearranging the data according to a Hilbert-curve gave better compression for simple images, but it wasn't much, maybe 20% on monochrome images at best, and with higher bit-depths the difference was not worth it.

The compression gain is definitely there, but it's too little and too cumbersome to be of practical use.

[Trachu]

Originally Posted by NorthWay

AFAIK (corrections welcome) both IFF and GIF store picture data on a line by line basis.
Colours are typically much more locally clustered, and this is also how JPEG (and others?) arrange pixel data to take advantage of local similarities.

Are there any compressors or other tools that will do such blocking or rearranging of data to increase compression ratios?
Can you affect the ratio for a standard IFF/GIF by re-arranging the palette and thereby the data combinations?

Try this:
http://www.pouet.net/prod.php?which=71288

[NorthWay]

Thanks!

[NorthWay]

Did anyone try that tool? I might be missing what its point was.
"ZZ_MadMan" went from a 62K IFF to a 67K IFF when saved by the tool. I haven't tried converting to raw and compressing with some other tool if that was the purpose...

[chb]

Originally Posted by NorthWay

Did anyone try that tool? I might be missing what its point was.
"ZZ_MadMan" went from a 62K IFF to a 67K IFF when saved by the tool. I haven't tried converting to raw and compressing with some other tool if that was the purpose...

From the readme:

About BPLOptimize: BPLOptimize is an IFF ILBM and DEGAS PI1 converter that optimizes bitplanes for better compression with LZ-like compression algorithms.

IFF-ILBM only applies RLE-compression, so yes, you should try with another (Lz-like) compressor, probably raw conversion is not necessary.

EDIT: the tool has an option ("-nc") to write uncompressed IFFs, not sure if the better compression ratio is also valid when LZ-compression is applied to already RLE-encoded files.

[ross]

I've a tiny intro where i'm really space constrained, containing a raw 5 planes (interleaved) bitmap logo and other bitmap content.
The final executable will be packed by a LZH family compressor.
Because I need to really squeeze every byte, I thought about the possible alternatives.
I could use shrinkler but is an A500 intro so it would be better to find something else to save these few hundred bytes.

An idea that come to my mind is to rearrange the colors map (so the bit positions in raw data) to better suit the LZ part of the compressor.
To not reinvent the wheel I've searched and found this thread
and http://eab.abime.net/showthread.php?t=82826 and BPLOptimize (by TEK) http://www.pouet.net/prod.php?which=71288.
The concept applied by this program is exactly what I thought and what interests me, it simply need some better support for raw data
(but this can be obviated by a little effort by the final user ).

Unfortunately NorthWay is right, I too have done some tests, especially about images with BPL>=4 and heuristic reordering often gives worse results than the initial version of the image.
Brute force logically is perfect.

So an improvement for the program could be to allow the code to be blocked during brute search and to forcefully accept the best found up to that point.

[NorthWay]

I had a think about this a while back and came to the obvious solution:

You take your original picture, pick whatever is largest of width(X) or height(Y) (call that N), scale N up to the closest power-of-2 (call that M), recreate your picture as size M*M with zero data to the right and below.
Recursively partition your picture data in quarters (so you divide your new picture into 4 parts), and keep on doing this until your partition contains only 1 pixel. Then output that bit (if using bitplanes (which was my intention)) or byte (if 8-bit chunky). Or just stop when you are down to a width of 1 byte (which is different for bitplane and chunky ofc).

The resulting pile of data should be highly localized. Feed it to your prefered LZ+Huffman packer.
(I'm sure you can apply some heuristics for X and Y if you want to avoid compression of lots of 0s.)

At this point a brute force palette re-arranger could be used as a first step to iterate through the above.
I couldn't quite wrap my head around what parts of the brute force would be redundant as you end up with the exact same bits in a bitplane except that now those bits are in, say, bitplane 3 instead of 1.

[oRBIT]

Try to store the image rotated in 90 degrees. I did a simple slideshow a few years back and stored the images like that and the crunching worked alot better (with my images anyway).