Fast, lossless compression of a video stream

I have a video coming from a stationary camera. Both the resolution and the FPS are quite high. The data I get is in Bayer format and uses 10 bit per pixel. As there's no 10 bit data type on my platform, the original data is stored in memory using 16-bit words. I want to implement some kind of lossless compression of the data before transmitting it over a network.

• The camera does not move, so big parts of consecutive frames are nearly identical - but still not completely, due to the inevitable noise (denoising is not an option, as it is supposed to be lossless and shouldn't "lose" even the noise).
• Because of high FPS, even the parts that change don't change much between any two consecutive frames.
• However, it looks like the camera also shakes a little. Very little, but still, even the stationary objects are not completely so in the image space.
• The compression has to be done on the fly, so I can not gather a lot of frames and compress them all together, but I can look 1 frame back and use it as a reference.

Based on the above, my first thought was to bit-pack the data, so that those 6 redundant bits are not wasted on every word. However, I thought that if I use some entropy coding (e. g. Huffman etc.), that redundancy would be automatically taken into account, so no extra packing is necessary. So I've done the following:

• Took binary difference between two consecutive frames. The original data range was 0~1023 (e. g. unsigned 10 bits). Difference data becomes signed and the range increases to -1023~1023, but the data variation (or what's the correct mathematical term) becomes much less than in the original data, in fact, most of the values are, not surprisingly, close to zero.
• Applied Rice coding to the difference. From what I understand, it looks like a good choice for data sets of mostly small numerical values.

This gives me about 60% reduction in size for 1280x720 frames, and my test system (Linux in VirtualBox on a single core) can do ~40 such compressions per second (without much optimization). Not that great, but reasonable, I guess (or is it?).

Are there better ways? Any common mistakes I made? Any general steps I missed? Higher resolution frames may be used later - should I expect better compression rates for bigger frame sizes?

UPD.:

• I used this library for Rice encoding. The library is very slow (the author himself describes it as something for learning rather than for real use), for example it reads and writes bits one-by-one in loops, which kills performance. Initially it only gave me ~20 FPS, after some very basic optimization it became 40 FPS (as reported above), later I optimized it some more, it became 80. That is on a single i7 core without vectorization.
• As for vectorization, though, unfortunately I couldn't think of a way to vectorize Rice code (don't even know if it is at all possible - could not find any data on Rice code, what I could find about Huffman code suggests that it's sequential and can't be efficiently vectorized, that may apply to Rice code as well as other variable-length codes).
• I also tried a completely different approach: split the data into small pieces (e. g. like 64 pixel apiece) and use simple zero suppression. We find the biggest number in a block, write the number of bits required to represent it to the beginning of the block (4 additional bits were required for that, in my case), then reduce all numbers in the block to the same number of bits. I expected compression rate to be bad, but if the pieces are small, many of them won't have noise spikes, therefore their binary difference can be reduced to something like 4~6 bits per value, and it was, in fact, only about 5% worse than that of Rice code, while being about twice as fast (e. g. 160 FPS for my case). I tried vectorizing it, but I kinda suck at vectorization, so maybe because of that I could only achieve about x1.8 of further speed-up.

Because negative numbers don't have leading zeros, I applied zigzag encoding after binary difference and before Rice/zero suppression.

• You could use a standard codec like h264 which supports a 10 bit mode. "Setting -crf or -qp to 0 forces x264 in lossless mode the -preset settings then impact just the speed/size ratio." (But I don't know if it'll manage real time performance) – CodesInChaos Jul 4 '16 at 10:00
• @CodesInChaos, would it do much for just two frames? – Headcrab Jul 4 '16 at 10:08
• Perhaps, even more importantly - can standard codecs even encode Bayer images? If I am not mistaken, conversion of Bayer to RGB involves interpolation, and is, therefore, irreversible. – Headcrab Jul 5 '16 at 3:09

You've got temporal prediction, but no spatial. For better compression at the cost of speed, you should be able to use the pixels above and to the left of the current pixel in the current frame as predictors, as well as the pixel at the same location in the previous frame. The reason for only looking up and left is the same as the reason for only looking at the previous frame; you want to only rely on data you've already decoded, and limit how much of it you have to keep around.

Rice codes are probably a good tradeoff between efficiency and speed, but a static Huffman code (precomputed by you on a sample of video data) might be more efficient and equally fast.

As for speed, make sure that your code is getting vectorized — either by using the right compiler flags and code patterns to allow the compiler to auto-vectorize, or by hand-writing the code to use vector intrinsics or assembly.

Finally, is dropping down to 8 bits per pixel a possibility? Obviously that's leaving the realm of "lossless", but not only would it reduce the size of your compressed output, it would also, with vectorized code, possibly increase your throughput up to 2x.

• I guess reducing the 10bpp to 8 is not possible, but it could be possible to store the deltas in fewer bits, in much the same way as UTF-8 uses 1 or sometimes 2 bytes to store a character. If the deltas are nearly 0 all the time, then it would be quite rare to see all 10 bits change, and so worth the effort of determining 1 or 2 bytes to store them. – gbjbaanb Jul 4 '16 at 9:56
• @gbjbaanb that's what the Rice coding accomplishes. Most deltas will be small, and thus only use a few bits. – hobbs Jul 4 '16 at 9:57
• @hobbs, by "spatial prediction" do you mean something like replacing a pixel value `x5` with the difference `(x5 - x4)`? – Headcrab Jul 4 '16 at 10:06
• @Headcrab - an approach I've seen used before is to use the median value of previous pixel and the pixels above and left in the current frame. – Jules Jul 5 '16 at 7:45
• @Jules if a pixel is replaced by some kind of median value of surrounding pixels, is it possible to restore its original value? – Headcrab Jul 6 '16 at 2:42

You are probably best served by using existing implementations of compression and decompression. Your existing implementation seems similar to the HuffYUV codec, so it might be worth trying that to see if it works well enough for you.

• libx264 " preset ultrafast" has served me quite well historically FWIW... – rogerdpack Jan 2 '17 at 18:37
• @rogerdpack - It's worth noting that libx264's setting for lossless encoding results in an output that's not H.264 compliant and breaks on some players. But it could be useful for the OP's application, at least. – Jules Jan 8 '17 at 10:06
• interesting do you have any links to that? Bug report? Also note that a video encoded with HuffyYUV is probably not "uni player friendly" either, I'd imagine :) – rogerdpack Jan 9 '17 at 18:12