Random data & video compression
Author
I want to write a video compression/decompression program just for fun to use it in my graphics applications. The thing is i know little about compression algorithms in general(just RLE, Huffman, LZW). I'm also interested in random data compression and what i need to know is what are some possible video compression and random data, patent-free algorithms i should look into. It would be great to know about such algorithms that provide a good ratio between simplicity/ease of implementation and compression power, being said i'm a beginner when it comes to these.
The reason why i want to write such a program myself is portability: i could port it to linux too not just windows and why not mac os x.
So what should i choose?
Compression works by exploiting redundancy and patterns in the message, I don't think one can compress random data. This applies to true random data - pseudo random data can (details depend on the algorithm) be compressed to something like a seed value, which would usually provide a pretty decent compression ratio [grin]
I have never researched video compression algorithms, but I would say that if you can find a cross platform library with a favourable license that does this then you should use it for your actual applications. You should draw the line between implementing an algorithm for your own understanding (and fun) and using stable, well tested code.
I have never researched video compression algorithms, but I would say that if you can find a cross platform library with a favourable license that does this then you should use it for your actual applications. You should draw the line between implementing an algorithm for your own understanding (and fun) and using stable, well tested code.
As I understand it, a data stream with 100% entropy is uncompressable. But I don't know enough about information theory to say why.
1) Random data does not compress.
2) "random" data might compress if treated properly to expose patterns.
a .exe is "random data" but the fact that it consists of opcodes, addresses, and immediate values it is actually possible to shuffle the exe around in a reversible manner so as to exploit redundancy in the code.
images are "random" data, but throw out things our eyes won't miss and you can smooth out all the noise and come up with patterns.
Look at different block processing routines, Move To Front, burrows wheeler transform, RLE, delta encoding. They are all designed to get some pattern from what would otherwise look to be totally random.
And also, think about what the data represents. In text, only blocks of adjacent characters have meaning. In an image the data at N is most closely related to N-1 N+1 and N-width and N+width, so the pattern is all scattered if you only look byte by byte.
3) For image compression, look into something like "wavelet" compression. It is what JPG does to compress the image. It exploits patterns in the edges and gradients of an image while ignoring anything it thinks it can call noise.
4) For motion video compression look into delta encoding and motion-vector encoding.
You for the most part pick a keyframe (later stored via step #3).
For all frames from there to the next keyframe find the motion vector encoding between frames (used to shuffle pixels around to get the next frame) and compress
the motionvector data one by delta encoding within a frame, and two delta encoding to the next frame. Then do a RLE or HUFFMAN or LZW pass over the deltaencoded data stream.
Lastly) It is a pain in the ass. Just find a library that does it all for you. You will have a hard enough time tweaking the encoding options to make something that matches your expectation of quality vs size.
2) "random" data might compress if treated properly to expose patterns.
a .exe is "random data" but the fact that it consists of opcodes, addresses, and immediate values it is actually possible to shuffle the exe around in a reversible manner so as to exploit redundancy in the code.
images are "random" data, but throw out things our eyes won't miss and you can smooth out all the noise and come up with patterns.
Look at different block processing routines, Move To Front, burrows wheeler transform, RLE, delta encoding. They are all designed to get some pattern from what would otherwise look to be totally random.
And also, think about what the data represents. In text, only blocks of adjacent characters have meaning. In an image the data at N is most closely related to N-1 N+1 and N-width and N+width, so the pattern is all scattered if you only look byte by byte.
3) For image compression, look into something like "wavelet" compression. It is what JPG does to compress the image. It exploits patterns in the edges and gradients of an image while ignoring anything it thinks it can call noise.
4) For motion video compression look into delta encoding and motion-vector encoding.
You for the most part pick a keyframe (later stored via step #3).
For all frames from there to the next keyframe find the motion vector encoding between frames (used to shuffle pixels around to get the next frame) and compress
the motionvector data one by delta encoding within a frame, and two delta encoding to the next frame. Then do a RLE or HUFFMAN or LZW pass over the deltaencoded data stream.
Lastly) It is a pain in the ass. Just find a library that does it all for you. You will have a hard enough time tweaking the encoding options to make something that matches your expectation of quality vs size.
Quote:Original post by Sc4Freak
As I understand it, a data stream with 100% entropy is uncompressable. But I don't know enough about information theory to say why.
It may be a little confusing, but it shouldn't be too hard to understand.
Random numbers, entropy (also called Self Information) and compression are closely related.
100% entropy would mean that you cannot guess the next number. There is no more useful information you can extract.
In data compression you are trying to remove information. For any information, there exist some optimal form for a given context.
Uncompressible information cannot be expressed in a more compact form, so it is the optimal form. It has 100% entropy, that is, you cannot remove any more information from it without destroying it.
Here are descriptive examples, not proofs, of how uncompressible data has an optimal form in a given context.
Quote:Guaranteed Compression Machine
Imagine we construct a lossless-compression machine. We can run any data stream into the machine and it will reduce the data size by at least one unit (the word is UNIT, not BIT, we cannot build this machine to work with bits), or we can feed it the other way to recover the original.
We could feed any data stream into the compression machine until we hit zero units in length. We can count the number of iterations until it reaches zero-byte size, giving n iterations. We now know that to restore our original data, we must iterate the decompression machine n times on another data stream.
As our stream shrinks, the value n increases. At some point the size of the data stream becomes smaller than the size of n.
In this scenario, the optimal form is the iteration where the size of n and the size of the data stream is minimized.
In that case, the compression machine is nothing more than an infinite enumerator: every possible data stream can be represented by a number.
Quote:Pigeon-Hole Principle and Guaranteed Compression Within a Single Context
If we do not allow contexts to change, you cannot guarantee a more optimal representation exists.
To verify this, imagine all unique data streams s with length less than n.
If we run all s data streams through the Guaranteed Compression Machine, we will still have s data streams. It is impossible for each compressed stream to have length < n.
In other words, if processed all data streams under 8 bits you would be attempting to compress 256 total data streams, which we can represent with the numbers between 0 and 255.
Because the machine cannot change the context, the output must also be a number. (If it could change the context it could change it to some other notation like "0-255".)
Number theory has postulates of equality and inequality, among them are that every constant is distinct from all others, unique, and is exactly equal to itself.
So assuming all 256 numbers must remain as distinct numbers (we can't change their context), then we can map them to any other 256 distinct numbers, but we cannot reduce them to fewer than 256 distinct numbers unless we violate terms of equality: somehow two of those numbers that were unequal are able to occupy the same value.
You cannot convert all 256 distinct numbers into fewer than 256 distinct without losing one of the numbers.
Compression works by changing the context of data (finding a different way to state it) and by mapping it to a smaller value (replacing a long sequence with a smaller number).
Eventually you will reach the point were there is no more efficient way to encode the data, and the encodings are in their smallest possible form.
Quote:Original post by DeliveranceThat is a good learning exercise....
I want to write a video compression/decompression program just for fun
Quote: to use it in my graphics applications.... but that is a bad idea because ...
Quote:The thing is i know little about compression algorithms in general(just RLE, Huffman, LZW).... you don't know enough about the information theory side to produce something good enough for a released application.
Quote:I'm also interested in random data compression and what i need to know is what are some possible video compression and random data, patent-free algorithms i should look into.Image compression is very complex. Video compression is like image compression, but even more complex.
If you want to check out how other people have done it, look at the source code for ImageMagick.
Quote:It would be great to know about such algorithms that provide a good ratio between simplicity/ease of implementation and compression power, being said i'm a beginner when it comes to these.The people who write them usually have advanced degrees in mathematics and computer science. You don't have those. Since you don't, I would suggest relying on their efforts.
Quote:The reason why i want to write such a program myself is portability: i could port it to linux too not just windows and why not mac os x.ImageMagick is already available on those platforms.
Quote:So what should i choose?I would use ImageMagick. The license is very generous.
Or you can search for other graphics packages, I'm sure there are several other distinguished open source products that you can use.
An optimally compressed stream is indistinguishable from a random stream, unless you know where to start.
As has already been mentioned but it should be repeated again and again, normally distributed uniform random data is not compressible. It is already at its entropy.
The best compressors today all use some variation of the same theme. Use a model to predict the next symbol in the stream. The better the predictions, the less you have to store. Random streams by definition are unpredictable.
As has already been mentioned but it should be repeated again and again, normally distributed uniform random data is not compressible. It is already at its entropy.
The best compressors today all use some variation of the same theme. Use a model to predict the next symbol in the stream. The better the predictions, the less you have to store. Random streams by definition are unpredictable.
Random data can be compressed, just not in any lossless fashion.
You can happily take an image of static (such as if your TV aerial came unplugged), compress it, and decompress that to another image that just looks like static. It might have the same frequencies, saturation brightnes etc in the image, but it wont be the same image.
I think you get my point.
Anyway I haven't done any video compression yet, but I've learnt a reasonable amount about the theory. You start with a keyframe, and compress that normally, then for the next say 20 frames you 'subtract' each one from the previous frame, then just encode the differences. If the differences are too great (such as when the camera changed scenes) then you just omit another keyframe.
It's the encoding of those differenes that is the tricky part. You need to search for transformations that describe the changes well enough, and can be represented by a small amount of data.
You can happily take an image of static (such as if your TV aerial came unplugged), compress it, and decompress that to another image that just looks like static. It might have the same frequencies, saturation brightnes etc in the image, but it wont be the same image.
I think you get my point.
Anyway I haven't done any video compression yet, but I've learnt a reasonable amount about the theory. You start with a keyframe, and compress that normally, then for the next say 20 frames you 'subtract' each one from the previous frame, then just encode the differences. If the differences are too great (such as when the camera changed scenes) then you just omit another keyframe.
It's the encoding of those differenes that is the tricky part. You need to search for transformations that describe the changes well enough, and can be represented by a small amount of data.
I believe that most people here are misunderstanding the OP. When he says "random data" what he means is "arbitrary data", such as a typical file on the computer that can be of practically any format. Obviously such an algorithm will do worse than specialized algorithms unless it incorporates them, but it allows much more to be compressed.
Quote:Original post by Extrarius
I believe that most people here are misunderstanding the OP. When he says "random data" what he means is "arbitrary data"
Keep in mind that arbitrary data, even when known to be rooted in high redundancy, could quite ACCIDENTALLY have the characteristics of random data.
Like the office manager who suggests encrypting highly redundant data like a text file (perhaps a CSV worksheet) before compressing it.. he will be left wondering why he couldn't compress it at all.
This stuff can crop-up midway through a project and can be hard to diagnose depending on the order of implementation of things, especialy if you decide to only encrypt a couple of the regularly occuring fields in your data stream (causing only a 10 or 20% bloat in your compressed stream.) Might even cost you considerable money upgrading hardware to compensate for this oversight.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
