making XviD lossless: what's needed?

[virus]

Hi!

I have no idea if it's a dumb question or not, but I'm curious about it and the search button didn't return too much on the subject, so I think that opening a thread about this may be interesting...

Let's forget about MPEG-4 compliancy for a moment... so, what tweaks are required in order to make XviD fully lossless in the YV12 domain, where it works? What if you disable any kind of quantization? Also, I can foresee some problems with the DCT/IDCT roudings... can they be controlled under every situation? Or maybe a switch to a simpler trasform (e.g. Hadamard) would also be required?

Looking for thoughts, opinions and/or technical details on the subject :D

cheers :)
virus

[Tommy Carrot]

I think the main obstacle is that the mpeg4 style motion compensation cannot be applied to lossless compression (correct me if i'm wrong), so in the end it would be just another keyframe-only lossless codec, which would be probably inferior to FFV1.

BTW, the ffmpeg devs started to make an experimental wavelet codec, called 'snow', which has lossless option too. Did anyone try it and could share the experiences with us?

[virus]

Originally posted by Tommy Carrot
I think the main obstacle is that the mpeg4 style motion compensation cannot be applied to lossless compression (correct me if i'm wrong)mmhhh, I'm not sure about that. Searching for a matching block should be a lossless operation. Of course, when doing subpixel interpolation you need to keep the required precision... or maybe not? If you round all the terms in a specific way (both during encoding and decoding) you should be able to reproduce exactly everything when reconstructing the frame. But I'm speculating a bit on this ;)

[EthanoliX]

Even if you round in a specific way you get inaccurate results.

You also have DCT, which produces more rounding errors, not even thinking about quantization... (unless you don't have something like the "all-one-matrix")

[sysKin]

The losses come from DCT inaccuraces, from quantization and from limited range if DCT coefficients. If you would address all that, you would probably get a lossless codec.

It would probably perform quaite badly in comparison to other lossless codecs...

[virus]

Originally posted by sysKin
It would probably perform quaite badly in comparison to other lossless codecs... Why? Many lossless codecs are keyframe-only. I cannot understand how a fully MC'ed scheme can perform worse than those... this would be the whole point behind a lossless version if XviD, which already sport some very efficient ME code, as you may know :D

The fact that the DCT is probably sub-optimal for spatial decorrelation (compared with a well tuned context-based DPCM prediction, at least) in a lossless framework should not be that important. The presence of MC should outweight it clearly. Anyway the whole DCT thing should be removed and replaced by something simpler. This will remove lots of problems I think.

[Tommy Carrot]

Originally posted by virus
Why? Many lossless codecs are keyframe-only. I cannot understand how a fully MC'ed scheme can perform worse than those...
This is why i mentioned snow codec, it might be exactly what you're looking for. It is a MC'ed wavelet codec, which has AFAIK more advanced coding tools than xvid and has a lossless option too. Unfortunately i couldn't try it yet.

[virus]

@Tommy

I'm not really "looking for" a codec, just curious ;)
I think that XviD would be a very good starting point to develop a lossless codec. Clean, fast, efficient, stable, open-sourced. :) Apparently you just need to replace the DCT and remove the quantization. Not an huge work it seems.

People seem to live under the assumption that wavelets are better for lossless coding, but I believe this is a misconception. A scheme based on the DWT can support a lossless mode easily, but I think it will be fairly suboptimal. I have no experience on video coding, but I can deduce these things from image coding... JPEG 2000 allows lossless compression within a unified framework that is designed for lossy coding, but its performances are quite bad compared to schemes specifically designed for lossless domains... and they're also much faster!

The DWT is basically a block-transform, just like the DCT or Hadamard, you just use a block large as the frame... and these kind of schemes never really paid off in the lossless world. In some old threads about wavelets, many people here including MfA and sysKin agreed that the real problem are the P-frames, because it's really difficult to find a scheme that handles well the residual of motion compensation, which look quite like white noise.

My personal feeling is that if you really want a bleeding-edge lossless codec, you need to forget about lossy schemes and design something new from scratch... or maybe start with a well-developed framework like XviD and hack it, step by step, until it becomes a lossless-only codec. That is, a fork, a separate project. That would be a fascinating challenge :)

[Tommy Carrot]

The lossless mode of the JPEG2000 is not bad at all, in fact, it's the only impressive part of that standard, and on natural images it outperforms PNG or LS-JPG by quite a large margin.

I keep mentioning snow because it exactly is what this thread is about: a lossless codec which is supposed to take gain from the inter-frame similarities. And it cant hurt if you don't have to worry about block-boundaries, not to mention other advantages over xvid (CABAC entropy coder instead of huffman, etc.).

IMO your idea is quite interesting, but snow has bigger/more potential.

[virus]

Originally posted by Tommy Carrot
The lossless mode of the JPEG2000 is not bad at all, in fact, it's the only impressive part of that standard, and on natural images it outperforms PNG or LS-JPG by quite a large margin.
Eh, Tommy, that's true, but you are comparing JPEG 2000's lossless performance with the crappiest lossless codecs out there! :D
Even the codec I designed some time ago gives a fair 3-4% improvement over JPEG 2000 with a much lower complexity... (note: a 3% gain is considered "quite big" in the lossless world, where stuff cannot be compressed that much). Why? Because JPEG 2000 is designed for lossy compression, and it's optimal for that. Lossless is just... supported, but with poor results.

And the lossless mode of the good old JPEG standard is so old and simplistic that it even stinks :)
Don't confuse it with JPEG-LS (which is a standard on its own), which is both slightly faster and more efficient than PNG. When I talk about state-of-the-art lossless codecs for images I refer to stuff like JPEG-LS or CALIC... or maybe more recent (but very, very complex) schemes like TMW, MRP or BMF. Some of them can go as far as 10-12% better than JPEG 2000. ;) And AFAIK none of them uses the DWT, nor the DCT, nor Hadamard. Just plain context-based DPCM prediction, with an additional lot of clever trickery including arithmetic coding. That's why I don't have faith in the DWT as a mean to provide an optimal lossless codec.

[virus]

Originally posted by Tommy Carrot
And it cant hurt if you don't have to worry about block-boundaries, not to mention other advantages over xvid (CABAC entropy coder instead of huffman, etc.).
just a couple of further remarks... if they do block-based MC, they will have to deal with block boundaries, too. If the do mesh-based MC, they will have to deal with mesh boundaries... there's no escape :)

Also, you can add CABAC to XviD, but it will be sub-optimal, as it will be for snow. You cannot simply rip the entropy coder designed for H.264 and pretend that it's optimal for a different scheme, especially one that is based on the DWT. Too many differences, especially if you target lossless coding instead of lossy. Usually you design the entropy coder adapting it to the signals that your scheme produces. If it's different, it will produce an MC residual with different statistics, and thus it will need a different entropy coder. World domination is not an easy task...

[Tommy Carrot]

It's certainly possible that applying a transformation on the image is not optimal for lossless coding. However, what if it's necessary to exploit the inter-frame redundancies, so doing the MC is not possible without it (this is just an idea, i'm not a codec-developer :D).

CABAC is quite versatile entropy coder, don't forget, FFV1 uses it too, and in my knowledge it's one of the (if not THE) most efficient lossless video codec in existence (and developed by the same guy as the snow codec).

BTW, i meant jpeg-ls, i'm just confusing the names. :p

[Sagittaire]

FFV1 is a very good lossless codec:

- I,P frame
- Cabac


Make a codec LossLess only with DCT, quantification and IDCT process is impossible:


171 161 160 161 164 171 178 181
159 151 150 152 159 171 180 182
133 128 128 136 151 168 179 183
131 151 167 177 181 141 160 172
177 180 127 132 142 155 166 173
178 178 140 146 156 163 168 173
180 179 152 157 165 169 171 173
178 179 152 157 165 169 171 173




-> block after DCT


+1298 −43 +49 +16 +07 −13 −17 −05
−14 −38 −15 −13 +02 +13 +12 +09
+36 +07 +03 +11 −05 +08 +10 −02
+16 +29 +26 +13 −03 −04 −03 −08
+08 +19 −09 −13 +05 −03 −06 +03
+08 −01 −31 −18 +08 +02 +01 +09
-12 −13 +07 +07 −02 +01 +02 −02
−15 −09 +30 +20 −08 +00 +02 −09




-> Block after quantification type H263 Inter Q4


162 −5 5 1 0 −1 −1 0
−1 −4 −1 −1 0 1 1 0
4 0 0 1 0 0 1 0
1 3 3 1 0 0 0 0
0 2 0 −1 0 0 0 0
0 0 −3 −2 0 0 0 0
−1 −1 0 0 0 0 0 0
−1 0 3 2 0 0 0 0




-> Block after IDCT (example)


173 162 159 157 167 171 183 185
157 147 153 151 157 174 185 183
135 128 125 134 158 162 174 185
135 152 164 174 187 144 163 175
172 185 121 136 145 155 162 174
172 175 143 146 152 168 161 177
184 173 157 152 165 162 177 177
172 175 154 157 161 165 174 175




The codec could be lossless only with correction

-> Block Correction


-2 -1 +1 +4 -3 +0 -5 -4
+2 +4 -3 +1 -5 -3 -5 -1
ect ...................





-> After correction


171 161 160 161 164 171 178 181
159 151 150 152 159 171 180 182
133 128 128 136 151 168 179 183
131 151 167 177 181 141 160 172
177 180 127 132 142 155 166 173
178 178 140 146 156 163 168 173
180 179 152 157 165 169 171 173
178 179 152 157 165 169 171 173



Encoding with high quant: low bitrate for DCT + Quant but high bitrate for IDCT correction.
Encoding with low quant: high bitrate for DCT + Quant but low bitrate for IDCT correction ...

Lossless codec with DCT + Quant + Correction could be a very good lossless codec ... ???

[Chainmax]

CorePNG is lossless and has I-Frames too.

[virus]

@Sagittaire

Forget about quantization... it's not used in purely lossless codecs. There's no point in quantizing (that means rounding, thus introducing errors) and then add a correction right after you've "corrupted" the data.
You simply don't quantize at all... that is, you encode directly the numbers you've labelled as "block after the DCT" - if you want to use the DCT, which I'd say is not that a good idea... with lossless coding you lose the ability to round several coefficients to zero through quantization

[708145]

Forget about quantization... it's not used in purely lossless codecs. There's no point in quantizing (that means rounding, thus introducing errors) and then add a correction right after you've "corrupted" the data.


I don't think his approach is too bad. Just have an outer loop which optimizes the quantizer.
Off course it will be difficult with DCT since both the forward and inverse transform have to be bitwise identical on all platforms/implementations. But as stated above not neccessarily lossless.
I'd go for an integer transform or DWT instead to get around those hassles.

That way you still have the optimization space of putting AC's to zero.

bis besser,
T0B1A5

[izx]

Thinking practically, a lossless codec would initially be useless for DVD-backups...it's hard to believe that we could come up with a lossless codec that beats MPEG-2. Eventually, who knows, but with the new dual-layer DVD+Rs coming out, IMO the best way to "losslessly" backup would be a 1:1 copy.

[Tommy Carrot]

The lossless codecs are obviously not aimed for dvd-backups, but mainly for capturing and editing, and they can be also useful if you want to keep a _short_ video in perfect quality (for example you rendered something awesome, and you don't want to spoil it with lossy compression).

[virus]

Other than a practical "temporary framework" for capturing/editing, lossless coding is applied to whatever image/video that has a great importance.
For imaging, for example, medical images (a compression artifact can change a diagnosis and kill a man... think about it) and images from space (NASA used it for the images from Mars... and no doubt than in a maybe not-so-distant future we will probably have some lossless videos at low framerate, too - transmission at optical frequencies, now at the first experimental stages, promises great bandwidths to play with).
For video, well, think about the ultra-high-resolution master copy of a movie, from which you can derive all the lossy compressed version you want (HD-DVD, DVD, SDTV, HDTV, SVCD etc etc.). At least 1 lossless copy of every movie should exist on some archive, even if it's huge... especially if you've spent 100 million $ to shoot it ;)

[Tommy Carrot]

I've found a little test here (http://sourceforge.net/mailarchive/forum.php?thread_id=5424648&forum_id=1506), comparing snow's lossless performance with a few other codecs, and so far it seems very promising, in this test it beats FFV1 by ~15%. It seems, the gain from using the motion compensation successfully is higher than the efficiency loss coming from using wavelets.

[virus]

Originally posted by Tommy Carrot
It seems, the gain from using the motion compensation successfully is higher than the efficiency loss coming from using wavelets. Good, thx for the link. Just imagine how well XviD with its excellent ME routines could perform there with a few tweaks... a question though: the test sequence here is foreman, which is 352x288 @... how many fps? 25 o 30? I'd like to convert the results in bits/pixel. Also, uncompressed test sequences like foreman and similar are in YV12 format already, no?

[Tommy Carrot]

Originally posted by virus
Good, thx for the link. Just imagine how well XviD with its excellent ME routines could perform there with a few tweaks... a question though: the test sequence here is foreman, which is 352x288 @... how many fps? 25 o 30? I'd like to convert the results in bits/pixel. Also, uncompressed test sequences like foreman and similar are in YV12 format already, no?

I don't know the details, it wasn't me who made this test, but here is foreman.yuv (http://www.csee.wvu.edu/%7Exinl/courses/video/foreman.yuv), if you want to clarify something.