compressionsparse-matriximage-compressionrun-length-encoding
Best lossless compression technique for serializing a foot pressure map
I am working with pressure-sensing of human feet, and I need to transmit frames in realtime over serial.
The typical frame is like below, consisting of a flat background and blobs of non-flat data:
The speed of transmission is currently a bottleneck due to micro-controller overhead caused by Serial.send commands, so the engineer is using Run Length Encoding to compress the image, which seems good due to the flat, continuous background, but we would like to compress it even further.
I tried the "Coordinate List" encoding format (List<i, j, val> where val > 0), but the size is similar enough to RLE to not make a significant difference.
While researching a bit on SO, people say "don't reinvent the wheel, there are a lot of tried-and-tested compression algorithms for any kind of image", so I wonder what would be the best for the type of image displayed below, considering:
- Compression performance (since it is to be performed by a micro-controller);
- Size - since it is to be sent by serial, which is currently a bottleneck (sic).
Other approach would be to use "sparse-matrix" concepts (instead of "image-compression" concepts), and it looks like there is something like CRS, or CSR, which I couldn't quite understand how to implement and how to serialize properly, and even less how it would compare with image-compression techniques.
UPDATE: I created a Gist with the data I used to create the image. These were the results of compression methods (one byte per entry):
- plain: (
[n_rows, n_columns, *data]): 2290 bytes; - coordinate list: (
[*(i, j, val)]): 936 bytes; - run length encoding: (
[*(rowlength, rle-pairs)]): 846 bytes; - list of lists: 690 bytes;
- compact list of lists: (see Gist) 498 bytes;
Solution
Proposed algorithm
Below is a possible algorithm that is using only simple operations [1] with a low memory footprint (no pun intended).
It seems to work reasonably well but, of course, it should be tested on several different data sets in order to have a more precise idea of its efficiency.
Divide the matrix into 13x11 blocks of 4x4 pixels
For each block:
- If the block is empty, emit bit '0'
- If the block is not empty:
- emit bit '1'
- emit 16-bit bitmask of non-zero pixels in this block
- emit 8-bit value representing the minimum value (other than 0) found in this block
- if there's only one non-zero pixel, stop here [2]
- emit 3-bit value representing the number of bits required to encode each non-zero pixel in this block: b = ceil(log2(max + 1 - min))
- emit non-zero pixel data as N x b bits
It is based on the following observations:
- Many blocks in the matrix are empty
- Non-empty blocks at the frontier of the footprint usually have many empty cells (the 'pressure' / 'no pressure' transition on the sensors is abrupt)
[1] There's notably no floating point operation. The log2() operation that is used in the description of the algorithm can easily be replaced by simple comparisons against 1, 2, 4, 8, 16, ... up to 256.
[2] This is a minor optimization that will not trigger very often. The decoder will have to detect that there's only one bit set in the bitmask by computing for instance: (msk & -msk) == msk.
Block encoding example
Let's consider the following block:
0, 0, 0, 0
12, 0, 0, 0
21, 20, 0, 0
28, 23, 0, 0
The bitmask of non-zero pixels is:
0, 0, 0, 0
1, 0, 0, 0 = 0000100011001100
1, 1, 0, 0
1, 1, 0, 0
The minimum value is 12 (00001100) and the number of bits required to encode each non-zero pixel is 5 (101), as log2(28 + 1 - 12) ~= 4.09.
Finally, let's encode non-zero pixels:
[ 12, 21, 20, 28, 23 ]
- [ 12, 12, 12, 12, 12 ]
------------------------
= [ 0, 9, 8, 16, 11 ] = [ 00000, 01001, 01000, 10000, 01011 ]
So, the final encoding for this block would be:
1 0000100011001100 00001100 101 00000 01001 01000 10000 01011
which is 53 bits long (as opposed to 16 * 8 = 128 bits in uncompressed format).
However, the biggest gain comes from empty blocks which are encoded as one single bit. The fact that there are many empty blocks in the matrix is an important assumption in this algorithm.
Demo
Here is some JS demonstration code working on your original data set:
var nEmpty, nFilled;
function compress(matrix) {
var x, y, data = '';
nEmpty = nFilled = 0;
for(y = 0; y < 44; y += 4) {
for(x = 0; x < 52; x += 4) {
data += compressBlock(matrix, x, y);
}
}
console.log("Empty blocks: " + nEmpty);
console.log("Filled blocks: " + nFilled);
console.log("Average bits per block: " + (data.length / (nEmpty + nFilled)).toFixed(2));
console.log("Average bits per filled block: " + ((data.length - nEmpty) / nFilled).toFixed(2));
console.log("Final packed size: " + data.length + " bits --> " + ((data.length + 7) >> 3) + " bytes");
}
function compressBlock(matrix, x, y) {
var min = 0x100, max = 0, msk = 0, data = [],
width, v, x0, y0;
for(y0 = 0; y0 < 4; y0++) {
for(x0 = 0; x0 < 4; x0++) {
if(v = matrix[y + y0][x + x0]) {
msk |= 1 << (15 - y0 * 4 - x0);
data.push(v);
min = Math.min(min, v);
max = Math.max(max, v);
}
}
}
if(msk) {
nFilled++;
width = Math.ceil(Math.log(max + 1 - min) / Math.log(2));
data = data.map(function(v) { return bin(v - min, width); }).join('');
return '1' + bin(msk, 16) + bin(min, 8) + ((msk & -msk) == msk ? '' : bin(width, 3) + data);
}
nEmpty++;
return '0';
}
function bin(n, sz) {
var b = n.toString(2);
return Array(sz + 1 - b.length).join('0') + b;
}
compress([
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 10, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 15, 15, 9, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 10, 9, 11, 7, 12, 21, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 13, 15, 13, 0, 0, 15, 28, 23, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 7, 8, 0, 0, 0, 0, 14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 14, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 11, 10, 0, 0, 11, 19, 12, 9, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 12, 12, 14, 24, 26, 21, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 21, 33, 38, 30, 23, 26, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 15, 16, 17, 22, 29, 32, 26, 18, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 22, 38, 46, 47, 42, 33, 27, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 14, 18, 18, 23, 28, 32, 31, 23, 12, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 7, 7, 17, 31, 52, 54, 55, 48, 36, 34, 32, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 12, 12, 17, 22, 29, 28, 26, 17, 7, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 10, 26, 40, 50, 51, 48, 38, 28, 30, 25, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 14, 23, 22, 20, 16, 10, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 20, 30, 38, 40, 42, 37, 27, 19, 18, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11, 15, 13, 12, 10, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 13, 24, 27, 28, 30, 32, 26, 13, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 12, 9, 11, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 14, 26, 27, 24, 24, 19, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 7, 20, 22, 19, 17, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 15, 16, 17, 14, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 15, 14, 15, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 16, 18, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 17, 19, 17, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 19, 20, 20, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 18, 20, 21, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 19, 16, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 11, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 8, 8, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 12, 12, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 10, 10, 13, 13, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 20, 25, 24, 17, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 13, 20, 26, 25, 24, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 20, 28, 32, 31, 24, 13, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 20, 28, 36, 39, 34, 26, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11, 29, 36, 39, 37, 30, 18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 22, 31, 43, 50, 58, 39, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 19, 39, 46, 46, 40, 32, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 24, 38, 51, 60, 64, 54, 26, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 25, 40, 49, 49, 44, 33, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 25, 45, 59, 65, 68, 66, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 40, 46, 46, 42, 31, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 22, 44, 56, 66, 70, 61, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11, 31, 35, 38, 31, 18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11, 31, 55, 66, 64, 52, 25, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 17, 18, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 17, 36, 50, 50, 32, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 13, 22, 21, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
]);The final output is 349 bytes long.
Empty blocks: 102
Filled blocks: 41
Average bits per block: 19.50
Average bits per filled block: 65.51
Final packed size: 2788 bits --> 349 bytes
- How to update tar (NOT append)
- Python ungzipping stream of bytes?
- Notice: ob_end_flush(): failed to send buffer of zlib output compression (1) in
- Practical way of explaining "Information Theory"
- Decompressing Large Gzip File not working using System.IO.Compression
- Library for further (lossless) Jpeg-compression
- Decompressing large zst files
- CSS compression & combining / js minification - Better to do at runtime or at build time?
- Exclude one folder and a filetype from Get-childitem
- How to convert BC7 to ASTC directly and fastly?
- PDF convert big vector file to small pixel file within R with magick
- Repair apparently damaged pdf and reduce file size
- Is there a way to compress an object in memory and use it transparently?
- pdftk compression option
- Python gzip decompression failing
- Is repacking a repository useful for large binaries?
- Is there a way to compress a long string to a smaller one and vise versa by code?
- How to write already generated Huffman Codes to file in Rust
- How to determine compression method of a ZIP/RAR file
- Does PieCloudDB offer data compression at the table level?
- Cannot decompress zlib compressed file using NodeJS
- Compressing a string to a fixed length
- Is there a way in PHP to strip whitespace from JSON without using ob_gzhandler?
- How do I compute the approximate entropy of a bit string?
- How to use one StreamWriter to write to multiple underlying streams?
- Write a lossless-compressed image with multiple layers
- Bz2 Decompression in C#
- How to zip a file in python?
- Enable QuestDB compression on Mac
- can a random byte-array be decompressed? What algorithm would be used?