[Matroska-devel] Request for a hi-speed bitmap compression format standard

Christian HJ Wiesner chris at matroska.org
Mon Aug 11 13:14:03 CEST 2003


please allow me to introduce myself, my name is Christian HJ Wiesner and 
i am one of the project administrators for an openstandard / opensource 
audio/video container format called matroska ( http://www.matroska.org ).

Our project has a couple of goals, of which the most important are :

- Fully replace the old, updated AVI container as the most used video 
container ( still ! )
- Creat a number of matroska file creation/editing/repairing/playback 
tools for all OSes, also Windows ( DirectShow parser filter, etc. )
- Prepare a good and valid set of documents, to make sure matroska can 
be implemented by closed source applications also ( matroska specs are 
public domaine, but libraries are GPL/QPL )

One of our major group of users for matroska files ( .MKV ) are doing so 
because it is offering very good support for most of the existing text 
based subtitles standards already, such as

- USF ( soon )

Typical filesize for a subs stream of  a complete movie is about 20 - 60 
KB, so normally its no problem to include several subtitles streams into 
one file ( see here for a sample file with subs in 18 languages : 
http://matroska.free.fr/samples/mewmew ) .

However, in many cases the subtitles sources are not text, but RLE 
compressed bitmaps. In one of our next tool releases we will offer the 
users the possibility to mux these bitmap subtitles ( also commonly 
called VOBSUBs ) into matroska files, like for DVDs . However, due to 
the weak compression that the RLE standard will offer, they are still 
like 4 - 8 MB in size. For this reason we were planning to compress them 
down further, and did a couple of tests how to do that in best case.

PNG was our first bet ( of course ), but unfortunately the results were 
proving that its unusable for our purpose, at least in its current form, 
as the necessary CPU power to decode a PNG compressed subtitle bitmap is 
simply too high. Imaging that we will play the movies on normal PCs ( 
min standard should be a PIII 800 MHz as per our recommendation ), and 
the CPU has to

- decode the video, mainly MPEG4 or RealVideo9 ( very CPU intensive, 
especially for higher resolutions )
- decode the audio, very often 5.1 AC3 or 5.1 AAC tracks
- decode the compressed subtitle bitmap

More tests were done, and the best solution we currently have is to use 
lzo on the original RLE precompressed subtitles, with a 1:7 compression 
ratio. Here the results when comparing those general use compression 
libs, the code for this comparison as well as the sample file it was 
performed on is attached :


Reading VOBSUB chunk... done

Compressing data...
1) lzo1x_1...
2) lzo1x_999...
3) zlib1g l1...
4) zlib1g l9...
5) bzlib1g l1...
6) bzlib1g l9...

Decompressing data...
1) lzo1x_1...
2) lzo1x_999...
3) zlib1g l1...
4) zlib1g l9...
5) bzlib1g l1...
6) bzlib1g l9...

Results - size:
1)              lzo1x_1 compressed size:   587, ratio: 14.33%
2)            lzo1x_999 compressed size:   542, ratio: 13.23%
3)              zlib l1 compressed size:   561, ratio: 13.70%
4)              zlib l9 compressed size:   535, ratio: 13.06%
5)             bzlib l1 compressed size:   658, ratio: 16.06%
6)             bzlib l9 compressed size:   658, ratio: 16.06%

Results - speed:
1)              lzo1x_1 decompression time: 1111.283ms, 89986.1 blocks/s
2)            lzo1x_999 decompression time: 1504.558ms, 66464.7 blocks/s
3)              zlib l1 decompression time: 13653.456ms, 7324.2 blocks/s
4)              zlib l9 decompression time: 13660.727ms, 7320.3 blocks/s
3)             bzlib l1 decompression time: 40515.699ms, 2468.2 blocks/s
4)             bzlib l9 decompression time: 39775.623ms, 2514.1 blocks/s


  As you can see, lzo clearly compressed best for us in this case and 
its the fastest by almost factor 40 compared to bzlib, while the 
compression ratio is even higher. The typical block size of a bitmap in 
a vobsub subtitle is 4 - 6 KB, thats maybe why. Of course, these results 
are not 100% usable for our purposes, as we cant compress the complete 
subtitles stream and put this into the container, instead we have to 
compress every single bitmap in its own and pack it into a frame block 
in the matroska container, else the file could not be edited in a video 
editing tool. When using this form of compression, we could shrink down 
a complete bitmap subtitle stream from about 4 - 8 MB to about 500 - 
1000 KB, which is much more acceptable compared to the 700 or 800 MB you 
have on a CD.

However, after thinking a while we dont like the original approach of 
simply using lzo on the RLE compressed vobsub too much, for a couple of 
reasons :

- this solution would be a very specific matroska solution, not 
compliant to any existing picture compression standard
- hardware support for this may be impossible, or at least highly 
unlikely to happen ( yes, we have plans to approach hardware 
manufacturers for matroska support also )
- there is a big questionmark behind us implementing RLE decompressor 
algorithms in our playback decoder filters, which is still necessary 
after the first lzo decompressor stage

Now, after this long explanation, here my questions to you guys :

1. Is there any chance to make PNG much faster than it currently is, 
even with the disadvantage of a much lower compression ratio than what 
you guys normally achieve, but still be PNG spec compliant ? To be more 
precise, the PNGs created with our 'special' compressor should be 
decodable by any existing PNG decompressor lib, even when being slow. Of 
course, we know we have to use a special modified lib for decompressing 
at the desired high speed in real time, to gain the speed advantage, but 
thats ok with us.

2. If 1. is not possible, how big are the chances to think of an 
extention to the format, lets call it F-PNG ( Fast PNG ), and add this 
to the official PNG specs ? I am pretty sure, there is other use for 
such a format also.

3. We get a lot of requests from people creating their own subtitles for 
movies, but who make those with special ( even grafical ) tools to 
achieve fancy features, like highlighting words or syllables for 
karaoke, etc. . It is possible to include special scripting languages 
into our container to display those tracks that way, but as the text is 
UTF8 or UF 16 in most cases there is still a big problem to display 
those correctly on any computer ( font problem, etc. ). Using picture 
subs would help here a lot, but with normal BMPs, even RLE compressed, 
the size will become HUGE in the end, as every single change of the 
subtitle requires a new bitmap, so the size of such an 'enhanced' track 
can easily be 10x the one of a normal, and 50 - 80 MB for a subtitle 
track with RLE compression, or even 7 - 10 MB with lzo is absolutely 
unacceptable in most cases. Could a fast version of MNG ( call it F-MNG 
) be used to bring this size down significantly ?

Sorry about the long email, and thanks in advance for some answers.

Best regards

-------------- next part --------------
A non-text attachment was scrubbed...
Name: dst.c
Type: text/x-csrc
Size: 9586 bytes
Desc: not available
URL: <http://lists.matroska.org/pipermail/matroska-devel/attachments/20030811/ae7b3783/attachment.c>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: Makefile
URL: <http://lists.matroska.org/pipermail/matroska-devel/attachments/20030811/ae7b3783/attachment.ksh>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: vobsubsample.sub
Type: application/octet-stream
Size: 40960 bytes
Desc: not available
URL: <http://lists.matroska.org/pipermail/matroska-devel/attachments/20030811/ae7b3783/attachment.obj>

More information about the Matroska-devel mailing list