sparse matrix - Best lossless compression technique for serializing a foot pressure map -


i working pressure-sensing of human feet, , need transmit frames in realtime on serial.

the typical frame below, consisting of flat background , blobs of non-flat data:

enter image description here

the speed of transmission bottleneck due micro-controller overhead caused serial.send commands, engineer using run length encoding compress image, seems due flat, continuous background, compress further.

i tried "coordinate list" encoding format (list<i, j, val> val > 0), size similar enough rle not make significant difference.

while researching bit on so, people "don't reinvent wheel, there lot of tried-and-tested compression algorithms kind of image", wonder best type of image displayed below, considering:

  1. compression performance (since performed micro-controller);
  2. size - since sent serial, bottleneck (sic).

other approach use "sparse-matrix" concepts (instead of "image-compression" concepts), , looks there crs, or csr, couldn't quite understand how implement , how serialize properly, , less how compare image-compression techniques.

update: created gist data used create image. these 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;

proposed algorithm

below possible algorithm using simple operations [1] low memory footprint (no pun intended).

it seems work reasonably but, of course, should tested on several different data sets in order have more precise idea of efficiency.

  1. divide matrix 13x11 blocks of 4x4 pixels

  2. for each block:

    • if block empty, emit bit '0'
    • if block not empty:
      1. emit bit '1'
      2. emit 16-bit bitmask of non-zero pixels in block
      3. emit 8-bit value representing minimum value (other 0) found in block
      4. if there's 1 non-zero pixel, stop here [2]
      5. emit 3-bit value representing number of bits required encode each non-zero pixel in block: b = ceil(log2(max + 1 - min))
      6. emit non-zero pixel data n x b bits

it based on following observations:

  • many blocks in matrix empty
  • non-empty blocks @ frontier of footprint have many empty cells (the 'pressure' / 'no pressure' transition on sensors abrupt)

[1] there's notably no floating point operation. log2() operation used in description of algorithm can replaced simple comparisons against 1, 2, 4, 8, 16, ... 256.

[2] this minor optimization not trigger often. decoder have detect there's 1 bit set in bitmask computing instance: (msk & -msk) == msk.

block encoding example

let's consider 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 12 (00001100) , number of bits required encode each non-zero pixel 5 (101), 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, final encoding block be:

1 0000100011001100 00001100 101 00000 01001 01000 10000 01011 

which 53 bits long (as opposed 16 * 8 = 128 bits in uncompressed format).

however, biggest gain comes empty blocks encoded 1 single bit. fact there many empty blocks in matrix important assumption in algorithm.

demo

here js demonstration code working on 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 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 

Comments

Popular posts from this blog

Spring Boot + JPA + Hibernate: Unable to locate persister -

go - Golang: panic: runtime error: invalid memory address or nil pointer dereference using bufio.Scanner -

c - double free or corruption (fasttop) -