[Kde-imaging] Lossless image compression

[Dmitry Kazakov]

> Before it can be useful, however, I need input about the API design.
> The plan is to have a low-level C++ template based compression
> library, allowing to code raw 8/16 bit RGB(A) pixel image data from/to
> memory, where the layout of the pixels (RGB vs. BGR, ARGB vs. RGBA,
> etc.) and the resulting code stream (bytes vs. machine words) can be
> customized via custom templates or template arguments.
>

I can tell what we currently have.

Swapping
We have tiling, pooling and swapping at the level higher than the
compression itself. Every tile, which is 64 by 64 pixels is compressed
independently. The compressed data is written to a file mapped to RAM and
OS decides when this mapped data should be actually swapped out to the hard
drive. Of course the size of the mapped region is limited so the data is
flushed automatically when the "sliding window" of the mapped region moves
forward in the file. The size of the window is 16 MiB. It is chosen in
consideration to house 8-bit RGBA image of size 2048x2048 pixels (not
counting the reduction of size due to compression). No benchmarks were
actually done, so the size of the window might be not optimal. Actually, I
think we can make this window larger on modern machines, but I haven't
finished the benchmark yet.

Compression
For the actual compression of the tile data we use LZF algorithm. I did
some research on the compression times of LZO and LZF [0], [1]. It turned
out that LZF has better times. It takes twice faster to compress the image
with LZF while keeping almost the same compression rate. One more thing I
found then is that it is faster to "linearize" colors before compression
and then compress the image than compress the image directly (RGBARGBA ->
RRGGBBAA). It boosts both the speed and the compression rate. The time of
the "linearization" itself is negligible in comparison with the boost it
give, so now we do it this way.

API
The compression is done at the level of the datamanager so it doesn't know
the colorspace we work in. It knows the size of a tile and the size of a
pixel. The algorithm is split into two classes:  KisTileCompressor2 [2] and
KisLzfCompression [3]. The benchmarks are placed in [4].


[0] - http://dimula73.narod.ru/lzo_vs_lzf.pdf
       In "Linearized" column you see the total time of linearization +
compression.

[1] -
http://markmail.org/message/enjpz5lyiohy2y3k#query:+page:1+mid:enjpz5lyiohy2y3k+state:results

[2] -
http://quickgit.kde.org/index.php?p=calligra.git&a=blob&h=c46843999c159f88553e1846e7d4681e375a7e3c&hb=194ee7c39975e0be1ce37bb9394456290b326019&f=krita%2Fimage%2Ftiles3%2Fswap%2Fkis_tile_compressor_2.cpp
[3] -
http://quickgit.kde.org/index.php?p=calligra.git&a=blob&h=13910830b29418a81407078619a0c47e8d794d63&hb=194ee7c39975e0be1ce37bb9394456290b326019&f=krita%2Fimage%2Ftiles3%2Fswap%2Fkis_lzf_compression.cpp
[4] -
http://quickgit.kde.org/index.php?p=calligra.git&a=blob&h=13910830b29418a81407078619a0c47e8d794d63&hb=194ee7c39975e0be1ce37bb9394456290b326019&f=krita%2Fimage%2Ftiles3%2Fswap%2Fkis_lzf_compression.cpp

-- 
Dmitry Kazakov
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.kde.org/pipermail/kde-imaging/attachments/20120207/452a2af8/attachment-0001.html>