Intercoding in lossless video compression?

[bullitB]

I'm a bit new to the concepts of data compression, but something occured to me after looking at Huffyuv. It sounds to me like Huffyuv basically operates as a lossless MJPEG compressor would; it uses predictive coding followed by a modified-huffman entropy encoder. In other words, there is no temporal compression whatsoever. Now, it seems to me that for a given pixel in a frame of video, there is a higher correlation between it and the corresponding frame in the previous picture than the pixel or few pixels around it in its frame.

So, my question is basically this: Would it make sense, or would it even be possible, to make a lossless video codec that used some form of intercoding to produce relatively good compression ratios compared to current lossless compressors like Huffyuv or lossless MJPEG? I'm doing some work that requires a lossless intermediate format, so if this is possible, then I would be very interested.

[gabest]

Once I made such, but since it wasn't as effective as huffyuv I only released the LZW version (http://vobsub.edensrising.com/codecs/codecs.html). The intra frames were about 20-30% smaller.

[-h]

Cool, I was actually planning on forking XviD into a lossless codec (maybe even using PNG as the lossless step), and was interested in the kind of savings a motion estimation step would give us in a lossless codec.

Time is against me though

-h

[bullitB]

I've been looking into how this kind of compression could work out, and I realized something. It seems low motion parts of videos work better with intercoding, while high motion parts work better with intracoding. So, maybe the best system would involve using some kind of macroblock system like MPEG does, except instead of using the the blocks with motion vectors and stuff, use them for determining which compression method would be better for that particular part of the frame being encoded. I'm going to try to post a comparison between intracoding and intercoding soon...

[-h]

I've been looking into how this kind of compression could work out, and I realized something. It seems low motion parts of videos work better with intercoding, while high motion parts work better with intracoding. So, maybe the best system would involve using some kind of macroblock system like MPEG does, except instead of using the the blocks with motion vectors and stuff, use them for determining which compression method would be better for that particular part of the frame being encoded. I'm going to try to post a comparison between intracoding and intercoding soon...

I think the most crucial part of lossless image coding is getting the residual as small as possible - I can imagine having not only 16x16 and 8x8 vectors as per MPEG-4, but 8x4 or even 4x4 as well in an attempt to get the error information as close to 0 as possible. Motion vectors can require comparitively quite a few bits in MPEG-4 due to the residual being quantized, however in a lossless situation the reverse would be true - you'd want to spend as much on the vectors as possible to get the residual smaller.

It all depends on what kind of cases you tweak your entropy coder for I suppose.

-h

[LigH]

There are already a few standard codecs available which use lossless coding combined with delta frames; AFAIR, there are e.g. MS-RLE8 AVI codec at 8 bit, or the Apple QuickTime Video codec (lower quality settings might work lossy by introducing longer runs of identical colors as replacement for very similar colors, if I detected that well).

The usual approach here is to introduce a special code for a "transparent" (as representation for "unchanged") run of pixels. Then it works similar to animated GIFs with partly transparent overlay images, which encode only the changes to the previous, still underlying image.

I rather doubt that such codecs will work remarkably more efficient on natural image sources; especially randomly noisy material will kill the delta frame technology; "grain" (temporally blended noise) instead might not hurt so much, therefore preprocessing with a "temporal smoother" like filter shall be very recommendable...

[maven]

-h: (codec -> png)
have a look at http://www.maven.de -> code -> wavelet image compression.

certainly beats png on natural images, source included.

[LigH]

The fact that wavelets can beat JPEG in still image compression (perceptual quality versus data size) is proven at least since LuRaWave; unfortunately, LuRaTech is broke, therefore we might probably never get a motion video codec out of this house.

PicVideo's wavelet codec couldn't convince me, it requires a much bigger bandwidth than MPEG4 to achieve a comparable quality. And it is absolutely not lossless, even with its highest quality setting! {Dear maven: Can your codec on one hand encode losslessly at a comparable compression factor, and on the other hand is it useful for lossy motion compression (e.g. is it easy to get better compression with interframes)?}

And something more about PNG compression for a lossless codec: a "Multi-image PNG" file format (MNG) already exists, it is used e.g. by AnimationShop 3 (part of PaintShop Pro 7), and I remember having found an implementation as Delphi unit at www.delphi32.com once.

[bullitB]

Maven-
Wow...I'm getting some really amazing results with that wavelet compressor. Out of curiousity, do you know if you're violating any patents with that code?

[maven]

LigH:
it compresses lossless and lossy very well, but i have to admit that i haven't thrown motion fields at it (yet).

bullitB:
no patents AFAIK, but as i did not try to consciously avoid them, it's entirely possible that i violated some.
but i would not know what you could patent in there, it's all very straightforward...

[-h]

it compresses lossless and lossy very well, but i have to admit that i haven't thrown motion fields at it (yet).

You are awesome.

I had my doubts regarding its ability to deal with block-copy-style blocking artifacts, but it all looks good. A little creative re-ordering of motion-compensated blocks would have it performing a bit better I dare say.

-h

[Ookami]

LCL (Loss-Less Codec Library) by Oshima-san

"LCL is Loss-Less Codec for Video For Windows. Since LCL is a lossless codec, it does not have degradation of quality. LCL is suitable for digital animation or the animation of 3DCGs. LCL contains two kinds of codecs. AVIzlib: Is the high compression codec which uses zlib. AVImszh: It is a codec for digital animation."

http://www.geocities.co.jp/Playtown-Denei/2837/

[Belgabor]

Heh, I had thought about someting similar a few weeks ago, but never actually came around to follow it.

So here are my 5 euro cents on that, tough I havent looked into it:
- mplayer actually seems to support MNG in avis, so we just would need some windoze codec for it. Albeit, I havent checked what it actually produces.

- Theres a MNG Library at source forge, tough it seems mainly to do something like animated gifs in png.

@gabest:
I remember using your codec a long time ago, it gave me better compression on that source (cant remember what itr was, thoug) than HuffYuv. My system was just too slow to use it for capturing (Hm, gotta retry that with my current one).

Regards
Belgabor

[Sarreq Teryx]

Originally posted by -h
I think the most crucial part of lossless image coding is getting the residual as small as possible - I can imagine having not only 16x16 and 8x8 vectors as per MPEG-4, but 8x4 or even 4x4 as well in an attempt to get the error information as close to 0 as possible. Motion vectors can require comparitively quite a few bits in MPEG-4 due to the residual being quantized, however in a lossless situation the reverse would be true - you'd want to spend as much on the vectors as possible to get the residual smaller.
[/B]

I've had this in my head for a while, would it be feasible to have variable sized macroblocks? 4x4 up to 64x64, allowing for rectangular blocks also, I'd think it'd tend to improve compression/quality a nice bit. but then again, i could just be insane.

[Belgabor]

Originally posted by Ookami
LCL (Loss-Less Codec Library) by Oshima-san

"LCL is Loss-Less Codec for Video For Windows. Since LCL is a lossless codec, it does not have degradation of quality. LCL is suitable for digital animation or the animation of 3DCGs. LCL contains two kinds of codecs. AVIzlib: Is the high compression codec which uses zlib. AVImszh: It is a codec for digital animation."

I gave it some tries yesterday (one ~10 sec natural video clip and ~10 sec Anime clip, both tv caps, anime after some filtering to get rid of noise). Results:

- None of the codecs was able to compress during capturing on my system (1.4 GHz Athlon), and from the Framedrops, I suspect it wont work on any public available system currently in existance (well, perhaps on a dual P4 2 GHz )

- On natural video HuffYuv gave the best results (= samllest size).

- On anime, HuffYuv was third after AVIzlib (max. compression, smallest size) and AVIzlib (max. speed)

If someones interested, I can post exact results.

Regards
Belgabor

P.S: AVIzlib has a also a 'normal' mode, which didnt give any compression at all (imho).

[spyder]

To the best of my knowledge Huffyuv doesn't use the DCT in any form. It simply huffman codes the YUV data.