lossless diff codec

[mf]

I just came up with an idea. I wonder what compression one could gain from normal lossless codecs, by giving a lossy codec a chance at it first, and then recording the difference between the output of the lossy codec and the original (of course compressed).

1. You would just encode your clip in XviD or whatever you like at the highest settings (constant quant 1 or something).
2. You would then fire up the diff program (I don't think you could do this with a VfW codec, so you'd need a seperate app), open both the original file and the encoded file, and let it encode the differences between the two inside a second video stream. In a normal directshow player, the AVI/OGM/whateveryoulike parser would spit out 2 streams, of which the first would be decompressed by the suitable decompressor, the ouput of which would go along with the second stream into the diff filter where the two images are combined into one lossless output (that would be given that the first decompressor does not postprocess.


Any ideas ? Will work/won't work ? Why ? Interested in trying it out ?

[Tommy Carrot]

There is similar thing in the audio compression world. But i don't think it is any good for video compression. You won't get better result, than with the normal lossless. Storing the differences would be almost the same amount of information than the raw video.

[Neo Neko]

Well as a short observation. Wouldn't a 640x480 lossless encoded diff file generally take up as much space as the original encoded with the same codec at 640x480? Give or take some mega bytes? I can't see a feesable way to use a diff file with better compression to get the original file back.

While we are on the topic of new codecs or codec methods. I was wondering what the usefullness of a M-PNG codec would be. And how feesable such a beast would be. Would it be possible with it and some small moddifications to create a lossless codec on par with huffyuv only more like M-jpeg? I wonder.

[Tommy Carrot]

Just a question. Could a lossless codec gain benefit from motion compensation or estimation, thus giving smaller output than the current only-keyframe huffyuv, or this is impossible? Is there exist any lossless ME algorithm?

[shlezman]

After reducing redundancy and achieving compression by motion vectors or using a prior codec, the diff (delta) has very poor compressibility for two reasons:

1. It’s dynamic range is higher. When you compress a byte you have the range of 0..255 and when you copress a delta-byte you get a range of -255..+255 which is at least another bit, and that's before you begin the compression.

2. The delta has a very bad correlation (you cant use any assumptions like low freq as you do with DCT compression) and is almost uncompressible (can be mathematically proved using the information theory)

lossless compression is a tricky business !!!

[mf]

Originally posted by Tommy Carrot
Just a question. Could a lossless codec gain benefit from motion compensation or estimation, thus giving smaller output than the current only-keyframe huffyuv, or this is impossible? Is there exist any lossless ME algorithm?
This was exactly what I mean. MPEG-4 codecs have all that, but can't be lossless (the format prohibits it, since a quantizer of 1 still drops a lot of information). That's why I thought of the lossless diff layer.

[Atamido]

The size of the lossy compressed video plus the size of the diff losslessly compressed would be about the same size as the same video losslessly compressed. That doesn't sound very useful initially because you would be doing much more work for the same result. However, the data would be stored differently and would give the benefit of being able to use the data seperately.

For instance, you lace the data of the two stream and practice bit shaving (ala vorbis style) where you stream the lossy stream somewhere, and when there is extra bandwidth, you include the lossless diff data. Now, realizing that the diff data is going to be pretty large, and the resulting bandwidth would be pretty high, there is something else you could do with this.

You could do a lossy compression on the diff itself, a do the same lacing and bitshaving to basically have on the fly quality control of a video stream. And you could do it more than once so that you could have two or three diff layers that were compressed in a lossy format, layering them, depending on the amount of bandwidth available for transfering the video.

The nice thing about a system like this is it would basically be codec independant. You could have a codec that compressed video, and then a seperate application that created a diff layer from the original, and the compressed output. If each of the diff layers were stored in seperate streams, the the codec would need to know that this had been done, and whatever application was showing the video could take the main video stream and alter it using the diff layer that it received. OGG and MKV should both hadn't this type of thing pretty well given the number of streams that they both can handle.

There are two sides that would need to be developed for this to be useful. A server that can dynamically decide when to drop packets for only specific streams. And, an application that could take the decoded video stream and correct it using the decoded diff stream.

There are also a few other ideas that could be developed along those lines, such as a codec that could use both its normal compressed data, and the diff layer. Because as you get further from an keyframe in a lossy stream, the greater the margin of error. So, the diff stream would get more complicated the further the main stream was from a keyframe. So, if a codec could produce its normal lossy video, and then a lossy diff layer, it could render the two together to decide how to encode the following frame.

It would be very interesting to see what kinds of artifacts could be produced from these methods....

[shlezman]

Originally posted by Pamel
You could do a lossy compression on the diff itself


Though I like the idea of making scalable video system that is codec independent, compressing the diff is impossible as I explained before.

I see no good reason to stream lossless video, for the home applications lossy video with 2..6 MB is more then enough. In more exotic storage and archive or video editing applications, scalability of that kind is redundant.

Many methods of scalability for streaming applications exploit the codec's properties to gain quality. There are two main types of scalability, Temporal and spatial. In the temporal scalability additional frames are added and thus the frame-rate is increased/decreased with the addition/subtraction of levels. In the spatial scalability the codec's properties are heavily used, for example in MPEG the higher levels can carry additional DCT coefficients and increase the video quality. In wavelet compression (which is designed for scalability) additional sub-bands are stored in the higher levels. H.264 has a great way to make scalable video using specially encoded transition frmaes.

Being practical, Xvid can be altered to create scalable video in both ways.
1. make the B frames is separate layer (Temporal scalability)
2. create a higher level cosisting of diff in the DCT domain (the diffs of the quantized coefficients), this is a trickey business due to the dependancy of the P frames.

[mf]

Why would the difference take up as much as the video itself ? You could make delta frames of delta frames as well.

[shlezman]

The proposed diff data will have drastic changes between pixels this can be easily checked. The result is white noise

White noise is uncompressible in known methods.

If someone could propose a compression method that will result diff picture which isnt similar to white noise :D , then it would be possible, but then that will prove that the original compression is crap
:scared:

[69link]

I had a similar idea some years ago, but aiming for lossless pictures instead of video.

I did some tests with photoshop and was able to produce a lossless picture with a 30% compression (from say 1MB -> 700KB).

What I did was:
1. Compress the image with JPEG from 1MB -> 100KB
2. Make a diff between the JPEG and the original in photoshop.
3. Save the diff from photoshop as PNG.
4. ZIP the diff.png and the jpg pictures together.

Ok, PNG isn't the best way to compress the DIFF. The question is how compressable the DIFFS are? The rest is simple.

[Atamido]

Originally posted by shlezman
compressing the diff is impossible as I explained before.


Not quite. The diff would mostly be white noise, as you said, but depending on the encoding quality, and the noise in the original, the noise could be very localized.

If there is a lot of noise in the original video, then the diff will be almost completely random noise as noise doesn't compress very well. However, if the source is clean, then the noise in the diff should be very localized, like around the edges of a moving object. That would compress very well, even with lossless codec like huffyuv.

The problem is that for most codecs today, the error rate increases, the further you get from a keyframe, so the noise ratio would increase. But, I think that it would be very difficult to determine exactly the type of noise that would be generated without doing some tests. If someone would like to perform some tests by taking two video stream, comparing them, and then creating a third video stream using the difference of the two, that would be peachy. You could do this all by hand pretty easily by using a video clip that was only ~5 frames long.

It is also good to note that a perfectly clean source, such as rendered video, would probably work for this type of thing quite well. But I do have my doubts about the usefulness of this in the real world. We would have to see some examples to know for sure.


@69link: How small were you able to compress the original picture by zip'ing it? And how did you create the diff picture in Photoshop?

[shlezman]

Pamel is correct, there's a relation between the quality of the source and the quality of the base layer compression to the way the diff image would look. And the further the frame is from the key frame, the whiter the noise gets.

When using low bitrates for the base layer, you'll get edges of the figures in the picture, which could be compressed but I dont know how well, this is something worth checking.

to 69link, did you reconstruct the original frame ? please check my first post regarding the signes of the diff image, did you handle that issue ?

In any case, there are better ways to make lossless video then MPEG compression and zipping the diff, both in compression ratio and computation power.

[bergi]

I think using diffs for lossless compression isn't so great. Using only wavelet lossless compression will be faster and better in file size.

[mf]

Originally posted by bergi
I think using diffs for lossless compression isn't so great. Using only wavelet lossless compression will be faster and better in file size.
I know, but Gldm is nowhere to be seen :(. He had DVD-bitrate (8mbit) lossless(with a few rounding errors, so strictly speaking not lossless) wavelet compression. He also planned to get rid of the rounding errors with a new algorithm (supposedly even compatible with quantizers), but he disappeared after that.

[Atamido]

Originally posted by shlezman
In any case, there are better ways to make lossless video then MPEG compression and zipping the diff, both in compression ratio and computation power. Yes, there are much better ways. Huffyuv gets pretty good compression and is very fast to boot. However, as I was saying, there is the possibility that this could be used for streaming with variable quality. Unfortunately, I have no idea how to determine the effectiveness this would have without an actual test.


If someone would be willing, the best way to test this would be to render a 3D video clip in a lossless format (Huffyuv?) so that you have a perfectly clean source to start from (to test optimal situations). A clip of 5-10 frames would probably be best as you would have to do this all manually.

Open the clip with virtualdub and save a sequence of pictures. Encode this clip using your favorite lossy codec. Then open the encoded clip in virtualdub and save another sequence of pictures. Open the pictures in Photoshop and create a diff picture for each set of frames. Then use VirtualDub to create a video clip using the sequence of diff picutures and save to the same lossless format.

If (lossy clip) + (lossless diff) < (lossless clip)
Then (mf's idea)=(good)
Else (mf's idea)=(something that needs more work)


Other tests could include coming from different types of video, such as real life, and from other lossy sources such as an MPEG2 source, so see if it would be possible to take less space than the source if the source is lossy. Also, try compressing the diff with a lossy codec, recombine the lossied diff and the lossy clip, and see how it looks. But as the original question was on lossless, I would suggest trying the above expirement first.

BTW, if anybody does try it, I would love to see the the three video clips to get an idea of actual artifacts produced by codecs rather than just those that can be easily percieved.

[shlezman]

what about the sign of the diff picture, any image processing format including photoshop would treat the diff as abs(diff) and you'll never be able to reconstruct the original.

To make this experiment correctly, we'll have to write a compression for 9 bits per pixel (-255..+255), that's a pain in the butt even if we'll base the code on the huffyuv or use some zip.

[bergi]

I'm working on a wavelet image (video) compression, you can test it here (http://www.muehlhausen.org/home/bergi/004.exe ), parameters i[input file] o[output file] q[quantizier] l[levels]

example 004 iinput.bmp ooutput.bmp q1 l5

q1 is lossless.

I have many plans but not so much time for the project, but i'm working on it and if there is a working codec, i will let you know.

I think the only lossless way is yuvhuff or same integer wavelets, other ways will work, but file size will not better and speed will also not be better.

[mf]

Well Pamel, with that method you still don't have delta-delta frames (diff from the previous diff).

[Atamido]

Originally posted by shlezman
what about the sign of the diff picture, any image processing format including photoshop would treat the diff as abs(diff) and you'll never be able to reconstruct the original.

Okay, I wasn't sure how photoshop did it. But someone could write a utility to do it, just for the test.

To make this experiment correctly, we'll have to write a compression for 9 bits per pixel (-255..+255), that's a pain in the butt even if we'll base the code on the huffyuv or use some zip.
Not quite. There is no need to store whether the number is negative or not because all you have to do is loop the byte. If you start off with a base of 0 for the diff then:

A difference of +20 on the green would result in a diff value of 20.
A difference of -20 on the green would result in a diff value of 236.

This example is for RGB, but it would work for all of the values of YUV also.

Originally posted by mf
Well Pamel, with that method you still don't have delta-delta frames (diff from the previous diff).

I'm not sure if I follow you, but if you're looking to get the diff of a lossy encoded diff, you could use the same method used above. If you mean to reproduce the original video from the lossy video, and the diff, then you should be able to do the above process in reverse. Then you could take the diff of the original and the reproduced video to see if they are identical.

But maybe I misunderstood you completely. Could you clarify please?

[mf]

Originally posted by Pamel
But maybe I misunderstood you completely. Could you clarify please?
Compression of the diff stream can be:
diff of the frame per-frame (keyframes only)
or:
diff of the frame, but if parts of the diff are identical to the diff of the previous frame, don't code them (delta frames).

[Atamido]

Are there any lossless video codecs that do P(delta) frames? You could compress the diff lossy and use P frames, using your favorite MPEG-4 codec, but I have no idea what the artifacts would be like...

[mf]

Originally posted by Pamel
Are there any lossless video codecs that do P(delta) frames? You could compress the diff lossy and use P frames, using your favorite MPEG-4 codec, but I have no idea what the artifacts would be like...
What's the point in doing a lossy diff? The whole idea was to make MPEG-4 codecs lossless and hopefully ending up with a smaller file than with huffyuv/vble.

[Atamido]

Are there any lossless video codecs that do P(delta) frames?

[mf]

Originally posted by Pamel
Are there any lossless video codecs that do P(delta) frames?
WARP :p

[Tommy Carrot]

Originally posted by Pamel
Are there any lossless video codecs that do P(delta) frames?

I've asked this earlier, and the answer was no. But i still believe, that for a very clean source, some kind of ME, or other method would be viable way, so a lossless codec would have benefit from P-frames. But if the source is noisy, the hell would be coming. :D

[shlezman]

Originally posted by Pamel
A difference of +20 on the green would result in a diff value of 20.
A difference of -20 on the green would result in a diff value of 236.


How do you hope to represent diff of +236 ? :D

Guess what happens when you diff on diff :scared:

[Atamido]

Originally posted by shlezman
How do you hope to represent diff of +236 ? :D

You would store it as 236, which is fine. The thing you have to remember is that you are simply adding this onto another amount that is only goes from 0 to 255 also, so it will also loop.
Example: A pixels original green value is 37.

Situation A:
After using a lossy codec on in, the green value is changed to 57. So, you store the diff value of the green as 20. When you want to recompute the original value, you take the compressed value of 57, subtract 20, and you get 37.

Situation B:
After using a lossy codec on in, the green value is changed to 17. So, you store the diff value of the green as 236 (If you subtract 0 from 20 in a field with only 256 values, then it loops to the top and will start at 255 again). When you want to recompute the original value, you take the compressed value of 17, subtract 236, and you get 37. (Again, same principle where you are subtracting 236 from a field with only 256 values, it will loop.)

Situation C:
After using a lossy codec on in, the green value is changed to 253. So, you store the diff value of the green as 216. When you want to recompute the original value, you take the compressed value of 253, subtract 216, and you get 37.

Originally posted by shlezman
Guess what happens when you diff on diff :scared:

Well, if it was done correctly and the original diff was stored losslessly, then the result would be a solid black picture. (All values at 0). If the original diff was stored lossy, then you would have an extremely compressible image with some static scattered throughout it.


BTW, I was thinking that if someone really wanted to try and implement this, they should place the diff value of 0 at the value of 127 for RGB, or the equivalent for YUV as it would create a much more compressible image when the values are scattered up and down of the original. Otherwise two pixels that are slightly darker and slightly lighter next to each other will produce pixels on the diff that are black and white next to each other, and that is not good for compressions. If you center the "No difference" value at 127, then small differences would look like very small differences in shades of grey.

[shlezman]

To Pamel,
You're right, but using this modolu methode you get diff values with very high variance (pixel values change from one to another). Which are harder to compress, thogh it is possible to invent some kind of method which will eventually will have to treat the data as signed.

Original pixels : 122, 124, 131, 135
Reconstructed : 121, 126, 129, 131
diff with sign : -1, +2, +3, -4
diff modulu : 255, 2, 3, 252

[Atamido]

Originally posted by shlezman
You're right, but using this modolu methode you get diff values with very high variance

I'm not positive that I follow you, so correct me if I don't.

If you are talking about the high variance with:

diff modulu : 255, 2, 3, 252

Then yes you are right. This would produce a bright pixel, two dark pixels, and a dark pixel, all right next to each other. However, if you center the value of 'zero' around '127', this normalizes things.

diff modulu(centered) : 126, 129, 130, 123

And that would produce several pixels in a row that are very close to gray, and fairly compressible. In fact, the better the motion estimation is working, I would bet the closer all of the diff values would end up in gray.

****************

If you were talking about

diff with sign : -1, +2, +3, -4

being a high amount of variance, this is also a bit true. However, Most of the diff values should be centered around these values, making compression relatively efficient. You should basicaly almost never have a dark and light pixel next to each other.

[shlezman]

I've just gave it another thought and It seems that I missed a point. Treating the diff values as signed 8bit (by casting) when compressing is enough, when compensating the diff values should be treated as unsigned (yet another simple cast).

I guess that some kind of huffman code with run-length can be used for the diff compression to achieve good results, but with some restriction on the original compression, like very high bitrate or low quantization. Without these restrictions I think the diff might take as much space as any lossless coded.

[Atamido]

I agree completely. Unfortunately it would be impossible to tell the thresholds without performing real world tests. So, basicaly, someone would have to perform the test I lined out earlier to see if it was even feasible.

[charact3r]

You could use an off-the-shelf MPEG-4 codec and just replace the lossy parts (iDCT, quant) with a lossless entropy coding engine. Would probably have to use Arithmetic Coding or similar to achieve fractional bits/symbol as you'd likely get error data like:

-1 -1 0 1 2 1 1 0 1 -2 -1 0 etc.

[shlezman]

here are the results of some quick tests I've done:
Two "foreman" qcif 30fps with QP=4 and QP=25
I looked at the first I frame and the 100 P frame.
that's hoe the diff looks like :
I, QP=4
-1 7 0 -1 -5 -4 4 6 4 5 -2
3 -3 3 0 -1 0 5 7 2 2 1
3 3 7 3 1 4 -1 4 4 3 -2
5 -1 5 3 1 0 2 -2 7 2 -2
0 1 -4 4 2 -3 -7 3 1 2 -8
3 -6 3 2 3 -2 0 -1 7 4 5
0 -1 1 3 -3 6 -1 3 4 5 -2
2 -1 5 -5 -1 0 4 -3 1 -6 1
0 2 -3 2 0 3 0 8 -2 -1 -3
4 -3 5 -1 6 -1 4 1 4 2 1
0 -1 3 6 4 4 -2 1 2 1 2
I, QP=25
-13 1 8 8 0 1 1 -4 -2 7 5
-6 -5 9 5 2 -1 2 -3 -3 2 8
-5 -3 5 8 -2 3 1 -1 -2 5 6
2 -7 3 -5 -2 -2 -1 -7 2 4 5
0 0 -2 7 -1 2 -2 0 -5 2 1
4 2 11 10 10 2 -6 -6 0 4 5
-1 7 9 18 10 5 -9 -7 -1 6 4
1 5 14 4 5 -3 -4 -4 1 1 7
-1 4 3 8 2 4 1 8 0 5 4
-1 -2 7 6 6 6 11 8 11 4 4
1 3 4 8 4 11 5 8 8 5 -3
P, QP=4
3 6 0 1 -5 -8 5 6 -9 4 -1
4 6 7 -3 19 0 6 1 1 4 3
0 5 1 -8 -1 5 6 4 0 4 1
6 6 2 -4 5 2 4 -2 5 0 5
-2 5 -1 6 -5 0 0 -1 1 0 -1
2 0 3 5 -5 -1 9 -3 -4 -2 2
-1 4 4 7 -2 1 -5 2 -1 4 0
-1 4 3 1 -2 1 5 0 7 1 7
0 -1 -4 11 -12 1 -2 4 0 5 1
1 1 2 7 -3 -9 0 -5 4 0 4
-1 1 0 3 5 2 8 3 -9 -4 -2
P, QP=25
5 -6 -13 -17 -13 -19 -6 4 -9 -13 -17
-1 -11 -11 -15 5 -26 -5 9 3 -24 -20
-5 0 -10 -13 -7 -24 11 23 -2 -19 -22
8 4 -3 -15 -12 -21 19 17 1 -17 -4
0 10 0 -12 -29 -2 13 11 -3 -3 1
-1 3 7 -17 -28 11 18 5 -4 2 3
-4 14 8 -12 -18 18 4 6 -4 2 -3
3 9 14 -4 -5 16 9 4 4 2 4
-9 2 6 13 -15 19 8 1 3 9 9
-9 -8 6 9 -8 -5 -2 -11 1 8 14
-10 -2 -8 7 7 1 -9 -9 -12 -1 2

These are typical segments of the diff frames, It's hard to find long sequences of the same value, the histograms look like crap and the variance is sky high.
The max and min values of the diff range
from +-90 when QP=25
and +-27 when QP=4

Any ideas ?

[Atamido]

Well, if you were going to encode lossy, it would compress REALLY well because mpeg will only store the colors used in a block, and all of those values are VERY close together.

Other than that, the values seem pretty random. Maybe someone could invent a lossless codec that was optimized for color stripping, where it only had to store the range displayed?

BTW, how did you do that?

[shlezman]

Originally posted by Pamel
all of those values are VERY close together.


The values are close by value but have much higher variance compared to the original picture and DCT cant assure us good compression.

Ohh how could I miss that, the IDCT cannot assure us bit-exact reconstruction of data, IEEE defined an acceptable error range. Therefore it's impossible to achieve "real" lossless compresion based on MPEG.

H.264 has an integer transform that can assure bit-exact result in any decoder. I still have to check H.264 with quantizer of 1, maybe it's almost lossless.

By the way I used matlab for that test and the Y component of a decoded frame.

[jonas]

just a short note:
After reading this thread a week ago I downloaded the avisyth simplesample and rewote it to do the diff stuff. Well, I didn't get everything right with the colorspaces since I was just guessing on how to do it and spent about 10mins of total time. But with the expeption of a few pixels the diff comes out correctly.
I then got a friend to send me a no noise (rendered) clip encoded with VBLE.

Fist short encoding tests showed that a lossy Divx a highest Bitrate encode plus VBLE encode of the diff video where about 85% of the original VBLE encode.

since the diff is pretty much gray niose I don't believe doing a lossy diff encode + lossless diff encode of that would give any further improovement, but there may be codecs better than VBLE for this lossless encoding step.

jonas

[Atamido]

Thank you very much for taking the time to look this over.

[INCESTICIDE1967]

HI EVERY BODY...Jonas how can install the VBLE codec???...I download the file (vble video codec (beta version).zip) and descompress...but I not that to do with two files vble.dll and vble.inf...how install the codec???...:confused: :confused: :confused: .

Bye.

[lighty]

@INCESTICIDE1967

Simply right click on .inf file and select "Install".:p

[chepe36]

in avisynth:
lossless = avisource("YV12.avi")
lossy = avisource("MPEG4.avi")
Sub = Subtract(Lossy,Lossless)
Subtract(Lossy,Sub)

Example:
YV12.avi is the original clip MPEG4.avi is the lossy compressed clip, so if i substract the lossy from the lossless i get the pure noise and artifacts and if i substract thi noise and artifacts from the MPEG4avi file i get a clean and original file :D

so here is your answer it works!

[Atamido]

Wow, I don't know how you would have stumbled onto this thread...

Yes, it would work. The issue was if you could make a lossy + diff that was smaller than a lossless encode.

[chepe36]

The answer is no!

the diference has to be completly and 100% lossles otherwise it hurts more than what it helps.

Note: the avisynth thing was just for proving it works i know thats not the way to do it it just to prove the teory.

[shlezman]

The simplest way to prove that such codec is worth or not is to compress the Substact result with losssless huffyuv.
Then check the size of both files (MPEG4 and Huffyuv) and you'll know if it's worth the effort.

[trbarry]

Sometimes the goal of these scalability schemes is not to achieve the smallest possible total space but maybe to have a lower resolution compatible clip (say MPEG-2?) that can optionally be expanded to a larger resolution (HD-DVD?).

Pixonics has made some interesting announcements here.

http://www.pixonics.com/

And I also like the idea of having a smaller clip that could be downloaded or even streamed and yet an additional one that can turn it into HDTV. For instance this scheme could be used for a free OTA digital channel with a premium HDTV upgrade available. Current USA HDTV transmission are pretty much locked into MPEG-2 for compatibility but the premium upgrade channel could still be H264 or something.

- Tom