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
- Is this truly best way to delete last element in C?
- Understanding the difference in timing of two functions that increment each element of an integer array
- Why MSVC generates warning C4127 when constant is used in "while" - C
- Executing a user-space function from the kernel space
- Why must the variable used to hold getchar's return value be declared as int?
- mpirun -np 4 ./a.out doesn't use all my cores (ubuntu 24.04LTS)
- Shadowing an iterator inside a for loop has undefined (?) behaviour in C
- Sleep for N seconds and wait for keypress
- Dereference twice in gdb
- Is this declaration UB?
- return type defaults to 'int' [-Wimplicit-int]
- What is the scope of `fesetround()`?
- Which specific optimization flag causes libm functions to be treated as pure?
- How to render text in SDL2?
- Why would you use 'extern "C++"'?
- Strange Behavior Compiler Ignoring NULL Check Unless I Print Something in the if Statement
- Fast inverse square root using fixed point instead of floating point
- What is the const qualifier attached to in C: the memory area or the pointer?
- GCC options for strictest C code?
- How to do an explicit fall-through in C
- How do compilers treat CONST qualifier when the pointer points to a memory location obtained with malloc()?
- C: cmocka headers - how to unittest?
- Why in C when I print a double with a one decimal it round it to the next number
- Android C to Java SWIG unable to compile: incompatible types: byte cannot be converted to SWIGTYPE_p_uint8_t
- GNU Make in Ubuntu giving fatal error: rpc/types.h: No such file or directory
- How can I exclude non-numeric keys? CS50 Caesar Pset2
- How change every struct in an array of pointers?
- Optimized 2x2 matrix multiplication: Slow assembly versus fast SIMD
- Simple frame by frame video decoder library
- GCC no longer implements <varargs.h>