title: Best lossless compression technique for serializing a foot pressure map
body: <p>I am working with pressure-sensing of human feet, and I need to transmit frames in realtime over serial.</p>
  
  <p>The typical frame is like below, consisting of a flat background and blobs of non-flat data:</p>
  
  <p><a href="https://i.stack.imgur.com/n8Yyz.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/n8Yyz.png" alt="enter image description here"></a></p>
  
  <p>The speed of transmission is currently a bottleneck due to micro-controller overhead caused by <code>Serial.send</code> commands, so the engineer is using <a href="https://en.wikipedia.org/wiki/Run-length_encoding" rel="nofollow noreferrer">Run Length Encoding</a> to compress the image, which seems good due to the flat, continuous background, but we would like to compress it even further.</p>
  
  <p>I tried the "Coordinate List" encoding format (<code>List&lt;i, j, val&gt;</code> where <code>val</code> > 0), but the size is similar enough to RLE to not make a significant difference.</p>
  
  <p>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:</p>
  
  <ol>
  <li>Compression performance (since it is to be performed by a micro-controller);</li>
  <li>Size - since it is to be sent by serial, which is currently a bottleneck (sic).</li>
  </ol>
  
  <p>Other approach would be to use "sparse-matrix" concepts (instead of "image-compression" concepts), and it looks like there is something like <a href="https://en.wikipedia.org/wiki/Sparse_matrix#Compressed_sparse_row_.28CSR.2C_CRS_or_Yale_format.29" rel="nofollow noreferrer">CRS</a>, 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.</p>
  
  <p>UPDATE:
  I created a <a href="https://gist.github.com/heltonbiker/834cc10a1f81ee38997f4f9070069319" rel="nofollow noreferrer">Gist</a> with the data I used to create the image. These were the results of compression methods (one byte per entry):</p>
  
  <ul>
  <li>plain: (<code>[n_rows, n_columns, *data]</code>): <strong>2290</strong> bytes;</li>
  <li>coordinate list: (<code>[*(i, j, val)]</code>): <strong>936</strong> bytes;</li>
  <li>run length encoding: (<code>[*(rowlength, rle-pairs)]</code>): <strong>846</strong> bytes;</li>
  <li>list of lists: <strong>690</strong> bytes;</li>
  <li>compact list of lists: (see Gist) <strong>498</strong> bytes;</li>
  </ul>