Map Compression Methods

[cj-mclaughlin]

List of methods to investigate for compressing maps before transfer:

(Focus is initially on reducing file-size; but it would be especially beneficial if merging could be done on the compressed representaton)

Lossless:

• Encoded Stream Mapping:
  • Encode map as a sequence of bytes, in patterns of (num_cells, cell_transition_symbol), e.g. 24 'U' 10 'F' represents 24 unknown cells followed by 10 free cells.
• Region QuadTree:
  • Recursively divides image into four quadrants, terminating when a full quadrant is either completely free, occupied, or unknown. This should be more robust than the encoded stream mapping, and has the benefit of being able to compute IoU from quadtrees alone (which may be useful for map merge order), but may take longer to compress/decompress.
  • Read more here

Lossy:

• O(log(n)) transfer: https://ieeexplore.ieee.org/abstract/document/9341480

[tylerferrara]

The DAG strategy is super flexible, and can benefit from hashing QuadTrees. This is a much smarter strategy than recursively cutting the map into 4ths.