New zlib strategy proposal: Z

Proposal for a new zlib strategy: Z_RLE

Update: Starting with zlib-1.2.1, the Z_RLE strategy is supported by the official distribution!
The original proposal (15 May 2000) will continue to stay here, and show the motivation that lead to the implementation of Z_RLE.

Currently, zlib defines the following strategies:

#define Z_DEFAULT_STRATEGY  0
#define Z_FILTERED          1
#define Z_HUFFMAN_ONLY      2

I propose the following strategy to define in zlib:

#define Z_RLE               3

This strategy is loosely based on the Run-Length Encoding (RLE) algorithm. It is an impure variation of it, because it must produce valid zlib streams.

Background

Several variations of the RLE algorithm can encode the sequence ABBCCCC in different ways. Here are a few examples:

[(1, A), (2, B), (4, C)] - the sequence is encoded as a list of (length, repeated_value). According to the Compression FAQ, this particular encoding is patented.
[(3, A, B, B), (4, C)] - the sequence is encoded as a list having alternate element types: (count, value, value, ...), (length, repeated_value).
[(A), (B), (B), (Esc, 4, C)] - if there is a special escape code (value) Esc different than any other value, the run lengths are identified by this special escape code. Only run-lengths bigger than 3 are considered for special encoding; otherwise, each value is encoded as is. This way it is possible to avoid expansion of uncompressible data.
[(A), (B), (max_value+4, C)] - if the maximum value that can actually exist is less than the maximum value that can be encoded, it is possible to use the remaining space for encoding lengths.

RLE in zlib

An item from the output string of the LZ algorithm in zlib has either the form (value) if value is between 0 and 255, or (value, match_distance) if value is between 256 and 511. In the second case, match_length = value-256+3. If match_distance is restricted to 1, then any LZ sequence [(value1), (value2, 1)] can be regarded as a run-length encoding of value1 repeated 1+value2-256+3 times. This encoding is similar to the last RLE version from the list above. The main difference consists in the presence of the bogus match_distance which is always 1, but its presence is necessary in order to comply with the LZ algorithm; hence the impurity mentioned.

The advantage of using this strategy would be the same as the advantage of using Z_HUFFMAN_ONLY, in that it does not need a sliding window or a hash table at all. Thus, it considerably reduces the memory requirements of the encoder by approx. 128 KB. The memory is needed only to store the Huffman buffer and to construct the Huffman trees. Regarding the execution speed of Z_RLE, it should be comparable to that of Z_HUFFMAN_ONLY. The execution speed is expected to be better for the strategy that produces a smaller output.

Implementation

We are working on providing a reliable Z_RLE implementation to be integrated into the official zlib distribution. This page reflects the current progress of the Z_RLE implementation.

Note: An additional Z_RLE_FILTERED was implemented experimentally, but it will not be integrated into zlib. This strategy was similar to Z_RLE, but it only accepted run lengths of size 6 or higher.

Results

One might expect Z_RLE to produce good results especially on business graphics and other artificially-created images. Surprisingly, it performs well enough on the Kodak ColorSet, as shown in the table below. The table shows the sizes of the concatenated IDAT chunks, not the file sizes. The filter selection method is PNG_ALL_FILTERS with default heuristics, unless noted otherwise. For Z_RLE and Z_RLE_FILTERED, lazy matches are used, unless noted otherwise.

The observations obtained from the investigation of this image set are:

Z_RLE was better than Z_BEST_SPEED+Z_FILTERED in 13 (out of 24) cases. It is remarkable that all the cases where Z_RLE lost (Z_BEST_SPEED+Z_FILTERED won) were cases where the default heuristics for achieving the best compression (Z_BEST_COMPRESSION+Z_FILTERED+PNG_ALL_FILTERS) did not give the best results either.
Z_RLE was always better than Z_HUFFMAN_ONLY.
In 23 out of 24 cases, Z_RLE was better than Z_RLE_FILTERED.
In 23 out of 24 cases, for Z_RLE, lazy matches were better than non-lazy matches.
While experimenting with LENA (not shown in this table), Z_RLE and Z_RLE_FILTERED were the best strategies, comparing to all the other strategies and compression methods. You can see here the smallest image file, compressed using Z_RLE, with the zlib memlevel=9.

The next test case will consist of a set of paletted images. Z_RLE is expected to have a good behavior here, too.

Given these results, I think Z_RLE is serious enough to be considered for inclusion in the subsequent releases of zlib. It achieves a better compression than Z_HUFFMAN_ONLY while maintaining the same complexity level (no sliding window or hash table), and many times it achieves a better compression than Z_BEST_SPEED+Z_FILTERED at an even higher speed and at significantly lower memory requirements. Consequently, I propose to consider Z_RLE as a replacement of Z_BEST_SPEED as the (default) heuristics, when the highest compression speed is needed.

kodim01.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	732479	Level=3, Strategy=0
Z_BEST_SPEED, Z_FILTERED	737309
Z_HUFFMAN_ONLY	811264
Z_RLE	802033
Z_RLE_FILTERED	806162

kodim02.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	617865
Z_BEST_SPEED, Z_FILTERED	659840
Z_HUFFMAN_ONLY	636898
Z_RLE	631621
Z_RLE_FILTERED	633880

kodim03.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	506794	Filter=1, Strategy=0
Z_BEST_SPEED, Z_FILTERED	595931
Z_HUFFMAN_ONLY	582414
Z_RLE	573748
Z_RLE_FILTERED	578330

kodim04.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	637302
Z_BEST_SPEED, Z_FILTERED	674590
Z_HUFFMAN_ONLY	665420
Z_RLE	659514
Z_RLE_FILTERED	662747

kodim05.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	782790	Level=3, Strategy=0
Z_BEST_SPEED, Z_FILTERED	791803
Z_HUFFMAN_ONLY	830739
Z_RLE	823712
Z_RLE_FILTERED	827763

kodim06.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	631753	Filter=1, Strategy=0
Z_BEST_SPEED, Z_FILTERED	688245
Z_HUFFMAN_ONLY	715134
Z_RLE	709775
Z_RLE_FILTERED	713414

kodim07.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	558405	Filter=1
Z_BEST_SPEED, Z_FILTERED	633007
Z_HUFFMAN_ONLY	607587
Z_RLE	598822
Z_RLE_FILTERED	603083

kodim08.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	772010	Level=3, Strategy=0
Z_BEST_SPEED, Z_FILTERED	777854
Z_HUFFMAN_ONLY	813056
Z_RLE	804645
Z_RLE_FILTERED	808533

kodim09.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	582769
Z_BEST_SPEED, Z_FILTERED	626159
Z_HUFFMAN_ONLY	618891
Z_RLE	611683
Z_RLE_FILTERED	616175

kodim10.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	593333
Z_BEST_SPEED, Z_FILTERED	638947
Z_HUFFMAN_ONLY	630399
Z_RLE	622645
Z_RLE_FILTERED	627057

kodim11.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	629756	Strategy=0
Z_BEST_SPEED, Z_FILTERED	664488
Z_HUFFMAN_ONLY	692514
Z_RLE	680871
Z_RLE_FILTERED	687324

kodim12.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	533892	Filter=1, Strategy=0
Z_BEST_SPEED, Z_FILTERED	614485
Z_HUFFMAN_ONLY	608036
Z_RLE	600097
Z_RLE_FILTERED	604337

kodim13.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	825519	Level=2, Filter=1, Strategy=0
Z_BEST_SPEED, Z_FILTERED	831775
Z_HUFFMAN_ONLY	901623
Z_RLE	899707
Z_RLE	897723	Non-lazy
Z_RLE_FILTERED	899707

kodim14.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	703800	Filter=1, Strategy=0
Z_BEST_SPEED, Z_FILTERED	736728
Z_HUFFMAN_ONLY	770736
Z_RLE	762875
Z_RLE_FILTERED	767461

kodim15.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	603229	Filter=2, Strategy=0
Z_BEST_SPEED, Z_FILTERED	662264
Z_HUFFMAN_ONLY	651709
Z_RLE	642043
Z_RLE_FILTERED	645206

kodim16.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	541217	Filter=1, Strategy=0
Z_BEST_SPEED, Z_FILTERED	604958
Z_HUFFMAN_ONLY	627751
Z_RLE	619932
Z_RLE_FILTERED	624553

kodim17.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	610346	Filter=1, Strategy=0
Z_BEST_SPEED, Z_FILTERED	653295
Z_HUFFMAN_ONLY	654799
Z_RLE	647901
Z_RLE_FILTERED	652129

kodim18.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	772747	Level=3, Filter=3, Strategy=0
Z_BEST_SPEED, Z_FILTERED	780453
Z_HUFFMAN_ONLY	787888
Z_RLE	786328
Z_RLE_FILTERED	787725

kodim19.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	667061	Strategy=0
Z_BEST_SPEED, Z_FILTERED	684366
Z_HUFFMAN_ONLY	685407
Z_RLE	682900
Z_RLE_FILTERED	685043

kodim20.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	498043	Filter=1, Strategy=0
Z_BEST_SPEED, Z_FILTERED	545036
Z_HUFFMAN_ONLY	539409
Z_RLE	528864
Z_RLE_FILTERED	524956

kodim21.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	651536	Filter=1, Strategy=0
Z_BEST_SPEED, Z_FILTERED	689068
Z_HUFFMAN_ONLY	698324
Z_RLE	695215
Z_RLE_FILTERED	697370

kodim22.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	701840
Z_BEST_SPEED, Z_FILTERED	728751
Z_HUFFMAN_ONLY	710112
Z_RLE	708193
Z_RLE_FILTERED	709290

kodim23.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	557466
Z_BEST_SPEED, Z_FILTERED	616796
Z_HUFFMAN_ONLY	572045
Z_RLE	567744
Z_RLE_FILTERED	569511

kodim24.png

Level+Strategy	IDAT size	Comments
Best compression (pngcrushed)	698106	Filter=2, Strategy=0
Z_BEST_SPEED, Z_FILTERED	725410
Z_HUFFMAN_ONLY	748763
Z_RLE	728071
Z_RLE_FILTERED	732744

Back to PNG-Tech Home