New version of MLC lossless codec. [Archive]

View Full Version : New version of MLC lossless codec.

Pages : [1] 2 3

MiroLx

10th July 2007, 17:41

Hello.

I have finished version 0.2 of lossless MLC codec. Link is here http://www.linek.sk/mlc/

Changes from previous version:
- now three color spaces are supported losslessly (YUY2,YV12,RGB24)
- better compression

more in readme file.

It is free, has many options... Comments are welcome.

P.S.
This is a new codec and I haven't oportunity to test it in all operating systems and configurations.
If you will have any problems with installation or basic functionality please let me know. Namely in Windows Vista I haven't test it at all.

Update: Version 0.7 26.10.2009

Dark Shikari

10th July 2007, 19:28

How does it compare in terms of:

a) compression ratio
b) decoding speed
c) encoding speed

to Lagarith, HuffYUV, and lossless x264?

mitsubishi

10th July 2007, 19:54

I'm currently toying around with the lossless codecs, tested this one, compression isn't bad and is validly lossless, but really quite slow.

Initial test from a simple 5 min d2v source, all on fastest settings:

Codec Enc.Time Size Dec. time
MLC 186 1.22GB 304
FFD huffy 43 2.12GB 92
Alpy 40 1.65GB 250

MiroLx

10th July 2007, 20:19

Thank's Sirber. It is corrected now.

Dark Shikari:

From codecs you mentioned I only tested it against Huffy. MLC is slower with higher compression.

mitsubishi:

Please can you tell me your configaratin. Is it MP? With single processor MLC is roughly 2 times slower than Huffy. But I didn't test version you mentioned.

Sirber

10th July 2007, 20:58

There's also a delete button ;)

removing my post above, gonna remove this one later.

mitsubishi

10th July 2007, 23:04

Yeah MiroLx, I have a c2d E6300. I am testing by running an avisynth script containing nothing more than a d2v source through VDub I plan on doing a full test later, with a harder source and encoding off the decoded result, both of which should negate the advantage of multithreaded versions.

Like I say this is only a rough test, but I've added lagarith and huffyyuv

Codec Enc.Time Size Dec. time
MLC 186 1.22GB 304
FFDs huffy 43 2.12GB 92
Alpy 40 1.65GB 250
Lagarith 134 1.34GB 193
Huffyyuv 45 2.56GB 104

Dark Shikari

11th July 2007, 06:32

What is the algorithmic reason for slower decode time than encode time, in this case?

MiroLx

11th July 2007, 07:55

Sirber:
Thanks again.

mitsubishi:
This codec wasn't really tested in MP enviroment so your test results would be very interesting.

Dark Shikari:

The reason is in range coder (modification of arithmetic coder), which is faster encoding than decoding. It is similar with codec's which use Huffman'c code (Huffy...)

Dark Shikari

11th July 2007, 09:45

The reason is in range coder (modification of arithmetic coder), which is faster encoding than decoding. It is similar with codec's which use Huffman'c code (Huffy...)
Ah k, so it basically works similarly to Lagarith.

I've been thinking for a while about an LZMA-based lossless codec, i.e. 7zip's algorithm; it would give considerably fast decoding than encoding while getting better compression ratio than any of the ones listed here.

The only way to beat it I would think would be to use a codec that doesn't only use I-frames, or to use something even slower like a PAQAR-based algorithm.

MiroLx

11th July 2007, 16:59

Dark Shikari:
I had to do some web browsing, because I am not very familiar with compression methods you post, so only some remarks:
- they both use range coder at the end
- they are both more text oriented compression methods, and compressing text and video are really 2 different things
-non key frames algorithm is nice idea (MLC also use it) but very time consuming.

In any case if you decide to implement video codec I wish you good luck.

MfA

12th July 2007, 03:38

I've been thinking for a while about an LZMA-based lossless codec, i.e. 7zip's algorithm; it would give considerably fast decoding than encoding while getting better compression ratio than any of the ones listed here.
I would not be so sure about that. Generic history based coder implicitly learn a model for the probabilities of a stream of symbols, rather than having an in build explicit model which you try to fit to the data. The problem is the curse of dimensionality, with a large context around a pixel you get an exponential growth in the possible combinations. The history will only ever cover a very small amount of that and it can not efficiently generalize (some "smart" coders can do partial matching to determine probabilities, but that is not nearly enough).

Even for text the state of the art has moved to including language models (see the Hutter prize winners).

Dark Shikari

12th July 2007, 05:39

I would not be so sure about that. Generic history based coder implicitly learn a model for the probabilities of a stream of symbols, rather than having an in build explicit model which you try to fit to the data. The problem is the curse of dimensionality, with a large context around a pixel you get an exponential growth in the possible combinations. The history will only ever cover a very small amount of that and it can not efficiently generalize (some "smart" coders can do partial matching to determine probabilities, but that is not nearly enough).

Even for text the state of the art has moved to including language models (see the Hutter prize winners).
The language models aren't very helpful for the PAQ encoders; they help a bit but PAQ8 is quite good overall and can pack basically anything, not just text. Language modelling and dictionary replacement helps a bit but not a huge amount.

I've done tests of LZMA-compressed uncompressed AVIs; it seems to perform a good bit better than Lagarith or HuffYUV. Adding delta-frame compression for cartoons and such would probably help further.

MiroLx

12th July 2007, 07:58

I've done tests of LZMA-compressed uncompressed AVIs; it seems to perform a good bit better than Lagarith or HuffYUV. Adding delta-frame compression for cartoons and such would probably help further.

I have also done some tests with 7-zip but with different results. Problem is that AVI is a mess of video data, audio data, indexes.. and universal compression program has no chance to decide which is which. Even if you separate only RAW video data such program can only find line similarities, but not row or interframe similarities if he doesn't explicitely know organization of picture data - colorspace and dimensions of the frame.

mitsubishi

12th July 2007, 13:48

MfA

12th July 2007, 16:36

We are talking about encoding speeds an order of magnitude slower than decoding speed and the encoding speed of fast lossless coders. Even though you decode twice if you are using some fast filters it's going to slow you way down.

Dark Shikari

12th July 2007, 18:20

Dark Shikari, I'd certainly be interested in a faster decoding lossless codec. As you saw in another post I am trying to find which has the fastest (1x encode + 2x decode) since this gives the best advantage in prerendering for a two-pass encode.
LZMA is not fast in any sense of the word.

HuffYUV is fast.

LZMA is 1-1.5Mb/s encode, 6-8Mb/s decode.

That's only a few frames per second decoding on most video.

akupenguin

12th July 2007, 18:45

The reason is in range coder (modification of arithmetic coder), which is faster encoding than decoding. It is similar with codec's which use Huffman'c code (Huffy...)
I don't know if this applies to MLC, but entropy coding isn't the only reason huffyuv decoding is slower than encoding. There's also the pixel prediction algorithm: when encoding, all pixels are independent so they can be predicted in parallel with SIMD, whereas when decoding each pixel depends on the previous so they have to run in series with latency-bound scalar math.
I have some ideas about how to fix this, but they can't be implemented without changing the bitstream. Maybe some future version of ffvhuff.
And the only thing which might be faster than that is keeping byte alignment, a la LZO. (Not that I'm suggesting to actually use LZO, just look at how it's optimized compared to other LZ codecs.)

I've been thinking for a while about an LZMA-based lossless codec
To expand on the reasons why this isn't a good idea:
A generic context model will require much more context than a domain-specific model to provide the same prediction efficiency. Even if you do spend that extra memory and cpu-time it won't be as good, because increasing the number of contexts without incresing the prediction efficiency will dilute each context, thus it will take longer for the generic model to adapt to the current probabilities. This is especially problematic in an intra-only codec, because it has to reset the probabilities at the beginning of each frame.

I've done tests of LZMA-compressed uncompressed AVIs; it seems to perform a good bit better than Lagarith or HuffYUV.
That's because the LZ sliding window is a half-assed version of inter prediction. But LZ fails compared to real inter prediction because (a) it's line based instead of block based, so each motion vector has to be specified many times, (b) it has no subpixel interpolation, and (c) LZ can only match or not, it has no concept of residual.

or to use something even slower like a PAQAR-based algorithm
FFV1 beats PAQ8L for still image compression (and PAQ8L does have an image-specific model). All of PAQ's model mixing and other stuff that costs tons of memory and cpu are useless here: only the image model gets used.

Even for text the state of the art has moved to including language models (see the Hutter prize winners).
Language models are a filter, they don't replace the LZMA/PAQ/other entropy coding step. The most well-known equivalent for images is Paeth.

1x encode + 2x decode
The fastest algorithm for anything is not to compute it at all:
You can get away with 1x encode + 1x decode, simply by forking the the decompressed video stream and sending one copy to the first pass of the lossy coder and the other copy to the lossless coder.
avs2yuv (http://akuvian.org/src/avisynth/avs2yuv/) supports this, or you can do it in general with tee (http://unixhelp.ed.ac.uk/CGI/man-cgi?tee) + named pipes (http://unixhelp.ed.ac.uk/CGI/man-cgi?mkfifo).

MfA

13th July 2007, 00:47

I have some ideas about how to fix this, but they can't be implemented without changing the bitstream. Maybe some future version of ffvhuff.
With some sideband information (starting value/location of image rows) you could parallelize predict left when a matching encoder was used without changing the bistream, doesn't make too much sense to spend the effort though.

akupenguin

13th July 2007, 04:05

I don't need any sideband info, I only need to eliminate huffyuv's weird convention whereby the rightmost pixel of one row is considered to be the left neighbor of the next row.
It's not worthwhile for left prediction, but median is 30% of the decode time, whereas the encoder side version with SIMD is 12 times faster.

squid_80

13th July 2007, 04:41

The fastest algorithm for anything is not to compute it at all:
You can get away with 1x encode + 1x decode, simply by forking the the decompressed video stream and sending one copy to the first pass of the lossy coder and the other copy to the lossless coder.
avs2yuv (http://akuvian.org/src/avisynth/avs2yuv/) supports this, or you can do it in general with tee (http://unixhelp.ed.ac.uk/CGI/man-cgi?tee) + named pipes (http://unixhelp.ed.ac.uk/CGI/man-cgi?mkfifo).There's an avisynth filter called twriteavi that does a similar thing.
I doesn't need any sideband info, I only need to eliminate huffyuv's weird convention whereby the rightmost pixel of one row is considered to be the left neighbor of the next row.I can see how that could be faster, but can't see how it helps with SIMD.

akupenguin

13th July 2007, 05:35

Each pixel depends on its left, top, and topleft neighbors. I can't load consecutive pixels in an mmreg because that violates the left dependency, but I can load a diagonal stripe into an mmreg.

Pixels in their logical arrangement in a frame, with one register's worth highlighted:
http://img227.imageshack.us/img227/6629/stripe0fa7.png
How I'd store the temporary values in memory:
http://img151.imageshack.us/img151/9839/stripe1xg5.png
Cost: one extra transpose operation (the other transpose is free, since the bitstream parser has to store pixels one by one into an array anyway.)

MiroLx

13th July 2007, 08:55

I don't know if this applies to MLC, but entropy coding isn't the only reason huffyuv decoding is slower than encoding. There's also the pixel prediction algorithm: when encoding, all pixels are independent so they can be predicted in parallel with SIMD, whereas when decoding each pixel depends on the previous so they have to run in series with latency-bound scalar math.
I have some ideas about how to fix this, but they can't be implemented without changing the bitstream. Maybe some future version of ffvhuff.

Thanks for your explanation akupenguin. I don't use SIMD in
MLC (maybe futere version). If I understand it right you are able to use bytes for calculations, but numbers in MLC are bigger (32bit) in most cases so the advantage of SIMD is falling down. I am also waiting for Barcelona (desktop version) but AMD seems to have some problems recently...

akupenguin

13th July 2007, 10:11

MiroLx

13th July 2007, 11:48

32bit numbers still get 4x parallelism from SSE*, just not as much as the 16x that bytes get.
BTW, how do you get 32bit numbers out of video with 8bit colordepth? I can't think of any process that would add so much dynamic range without impeding lossless compression.

No nothing like that. It's index to context model, which has to be big. So at the beginning there are 8bit color numbers and at the end 32bit index numbers. But you are right 4x parallelism is still better than none.

Dark Shikari

15th July 2007, 09:08

That's because the LZ sliding window is a half-assed version of inter prediction. But LZ fails compared to real inter prediction because (a) it's line based instead of block based, so each motion vector has to be specified many times, and (b) it has no subpixel interpolation
You're right about that: in fact, except in the case of actual constant image data between frames, LZMA fails to provide any benefit for inter compression at all. Therefore any LZMA codec would be intra-only like HuffYUV or Lagarith, as inter-frame compression with LZMA would basically be useless.

FFV1 would probably end up being better anyways.

And FFV1 outperforms PAQ8?? I've never tried it but PAQ8's image compression has always impressed me, it nearly doubles the compression ratio of PNG.

MfA

15th July 2007, 18:57

PAQ8 uses linear predictive coding in a roundabout way, so I wouldn't be surprised if it did well ... still if you want to go for unusably slow MRP has it beat.

akupenguin

16th July 2007, 07:14

I think the main problem with PAQ8's image compression is that the linear prediction is only for determining contexts, it's not used as a filter. Thus, if PAQ8 predicts a pixel value to be 128 and it turns out to be 127, then every single bit is predicted wrong (or if it knows the prediction is inaccurate, then every bit is coded with near 50% probability). Whereas in FFV1 that would be a residual of -1, which still compresses well.
There's also context dilution: If FFV1 sees a neighborhood of (128,128,128) and the current pixel is 128, then that's also evidence for a neighborhood of (127,127,127) implying that pixel is 127. PAQ8 treats those as separate events, and doesn't infer the probability of one from observations of the other.

Dark Shikari

16th July 2007, 08:36

PAQ8 uses linear predictive coding in a roundabout way, so I wouldn't be surprised if it did well ... still if you want to go for unusably slow MRP has it beat.
Yeah, even its image compression (with the special BMP context model, no context mixing) is 100KB/s on a fast machine... too slow to be useful for video.

But I think its still faster than the MSU lossless codec... ;)

MfA

16th July 2007, 17:40

For laughs I'll try a combination of MED prediction and QuickLZ, it should be fast enough for realtime ... dunno if the performance will be worth crap though.

MfA

17th July 2007, 20:15

Well crap was just about right, even slightly worse than huffyuv on some really clean CGI anime I tried it with (best case for this kind of entropy coding) ... still it might be of interest to someone (cut down and cleaned up cedocida, fitting in a different type of compression requires only minimal changes now).

http://karton.student.utwente.nl/sc.0.2.zip

MiroLx

18th July 2007, 04:04

MfA

18th July 2007, 04:40

Almost the same ... but both are probably mostly disk limited on my crappy system so that doesn't mean much. Didn't spend too much time with it ... it's not meant as competition, it's just a toy ;)

Dark Shikari

18th July 2007, 06:31

Almost the same ... but both are probably mostly disk limited on my crappy system so that doesn't mean much. Didn't spend too much time with it ... it's not meant as competition, it's just a toy ;)Test it encoding to /dev/null then :p

bill_baroud

18th July 2007, 09:18

Dark Shikari

18th July 2007, 16:01

MfA

18th July 2007, 16:35

I did consider it for a moment, but I am not sure it would be a sure win. If you are just encoding a straight edge between 2 colored planes then you can't generally pick a block and overlap it with the present one to get a good match. When you just encode lines though then in the line above you can always pick a section which you can overlap with the edge on the present line.

Still, it's not a lot of trouble to try it ...

MiroLx

18th July 2007, 17:19

Just a thought: would it be beneficial to apply a transform to video going into a line-based compressor (like LZ, etc) to turn, say, 8x8 blocks into 64-long lines, so that the compressor acted more efficiently rather than scanning across lines of the video?

I am afraid this would be problematic, because when finding block match you have to slide one block in pixel steps and your model only allows block steps.

mitsubishi

18th July 2007, 17:22

Thanks akupenguin and squid on the heads up on the one decode methods, I'll look into those more thoroughly later.

MfA, I tested your codec, not bad.

Codec Enc.Time Size Dec. time
MLC 186 1.22GB 304
FFDs huffy 43 2.12GB 92
Alpy 40 1.65GB 250
Lagarith 134 1.34GB 193
Huffyyuv 45 2.56GB 104
sc.0.2 103 2.56GB 120

Through "read.avs"
AVIsource("w:\1.avi")which I use for the decode speed test and lossless verification it is fine, but is all blue tinted when played back in MPC directly.

squid_80

18th July 2007, 17:39

MfA, I tested your codec, not bad.Are these tests using YUY2? Everytime I compare original huffyuv with ffdshow using YUY2 (no adaptive tables), ffdshow ends up about 40% bigger. Using adaptive for both the size difference is < 0.1% (as you'd expect). Am I just choosing bad material?

mitsubishi

18th July 2007, 17:59

Everything is in the sources YV12, except for Huffyyuv which I had to convert back on reading it.

source.avs
DGDecode_mpeg2source("D:\test1.d2v")

read.avs
AVIsource("w:\1.avi")

verify.avs
A=import("source.avs")
b=import("read.avs") #.converttoyv12() # needed for huffyyuv

return ssim(a,b,"results.csv","averageSSIM.txt")

I've only tested on one source so far, I intend to check a HD source later. This source is clip from Doctor Who (DVB)

Dark Shikari

18th July 2007, 19:09

I am afraid this would be problematic, because when finding block match you have to slide one block in pixel steps and your model only allows block steps.
Yeah but it would be better than linear encoding wouldn't it? Block-matching would make a lossless codec much too slow I'd think.

MiroLx

18th July 2007, 20:04

Yeah but it would be better than linear encoding wouldn't it? Block-matching would make a lossless codec much too slow I'd think.

I don't know. Certainly it could be better. Some experiment would be usefull..

akupenguin

18th July 2007, 22:16

would it be beneficial to apply a transform to video going into a line-based compressor (like LZ, etc) to turn, say, 8x8 blocks into 64-long lines, so that the compressor acted more efficiently rather than scanning across lines of the video?
Take a look at the Hilbert curve. You don't have to pick a block size; Hilbert maximizes the spatial locality at any scale.

It may help in codecs where the entropy coder exploits the correlation between consecutive pixels (e.g. zero run). But it shouldn't matter for explicit-context-based codecs like ffv1, and it should interfere with LZ compression. When pixels are coded in raster order, a line in one place will match the same line in another place. If you munge the pixel order, the same image content may end up with a different byte representation depending on where it is.

MfA

19th July 2007, 03:24

but is all blue tinted when played back in MPC directly.
Oops, got the yv12 to rgb conversion wrong (only used when you are playing it back with a media player, since it doesn't accept anything else except for yv12 and when you are testing it you are requesting yv12 output directly). Reversing the U/V pointers in the transform code makes it work right.

bill_baroud

20th July 2007, 08:16

Codec Enc.Time Size Dec. time
Alpy 40 1.65GB 250

Hi, sorry to barge in but i skipped this codec from your results, the speed and the size looks very good compared to the others, but google or doom9 search only point to this thread when looking for "Alpy". Where can I find this codec ?

Thanks.

Boulder

20th July 2007, 09:14

Hi, sorry to barge in but i skipped this codec from your results, the speed and the size looks very good compared to the others, but google or doom9 search only point to this thread when looking for "Alpy". Where can I find this codec ?

Thanks.http://www.alparysoft.com/products.php?item=35

MiroLx

22nd November 2007, 19:12

Hello.

There is new version (0.3) of codec.

Changes:

- faster and better compression (in most cases)
- some bugs corrected (I have to change inner format ...)
- some problems with vfw interface solved

video_magic

29th November 2007, 08:09

MiroLx

29th November 2007, 15:19

Thank You for this promising codec. I intend to try it for my next lot of captures, and I wondered whether a P4 version could be made available and if this would give better performance (less CPU usage when capturing)?
Thanks again.

Hello video_magic.

No I don't plan version for Pentium4, sorry...I have some plans for new version (MP and also 64bit version), but for some time vesion 0.3 should be the last.

video_magic

2nd December 2007, 09:07

Okay, that's great - I appreciate what You have done.

Does 'MP' mean multi-processor, and if so, does that mean it will take advantage of the Hyper-threading of my P4 Prescott which can show up as 2 CPUs in task-manager?

Thankyou again for the really nice codec.

I use Windows XP SP2.