0
$\begingroup$

Is there a specialized lossless compressor for sparse matrices, i.e. large fraction (>40%) of values == 0? LZ4 worked well on 1D signals, but now whether I feed a sparse 2D or an all-zeros array makes no difference, still ~2x compression.

Slightly lossy compression (<5% MAE) also suffices. If relevant, data is float32 not uint8 (.mat/.npy), and it's not actually an image but a 2D array resulting from absolute value of synchrosqueezed CWT of a signal. float16 might be an option, I've not decided, but ideally float32 is preserved in compression. Data ultimately fed to a neural net.

$\endgroup$
2
  • $\begingroup$ Did you finally find an answer that could be validated? $\endgroup$ – Laurent Duval Apr 5 at 16:54
  • $\begingroup$ @LaurentDuval Both are informative answers, but a simple cast to float16 suffices for me so I didn't get to check the advanced methods. I'd add, an SSQ representation has many small values that can be safely zeroed to greatly increase compression rate. $\endgroup$ – OverLordGoldDragon Apr 5 at 20:55
2
$\begingroup$

Start simple: that calls for any Run-Length coding (RLE).

Also, floating point makes very little sense for image data, so the first step that will probably save you 50% of space is conversion to unsigned fixed point (multiply every value with 2¹⁶, then divide through the largest value of the original image, round to nearest integer, keep the result as uint16).

5% mean absolute error means: you don't need floating point; rounding small values to zero is absolutely¹ acceptable to you. So, drop the float idea and convert to integer, as described above.

If for some (somewhat untypical for image data) reason you want to keep it floating point, convert it to a format where you store the mantissa and exponent bits separately and the latter at all only for non-zero mantissa values. Since pixel data typically only has a positive sign, you don't even need to store the sign bit.

After reducing the number of exponents you've stored, maybe any further compression isn't necessary to achieve your goal (don't overengineer!).

Then, look at your data: It's also quite likely that your exponents don't need the full 2⁻¹²⁶ to 2¹²⁷ range, so dropping bits on your exponents makes a lot of sense, too. Make sure you're not totally killing it with the number of mantissa bits, too. Wild guess: half as many as in 32 bit IEEE754 will do.

If after doing these thing it still is necessary to compress further, RLE or Lempel-Ziv would be appropriate solutions. (LZ4 is kind of exotic; the more established LZMA algorithm as e.g. in XZ should work sufficiently well, and it really doesn't sound like you're CPU bound here...)

In all seriousness, though, sounds like a job PNG, high-quality JPEG, or if you have access to that, JPEG-XL, could do out of the box, so I'd simply look into converting my data to a format that makes sense to readily available lossless image codecs instead of trying to roll my own.


¹ hurr durr, a pun!

$\endgroup$
6
  • $\begingroup$ Updated question; I'll look into the suggested compressors. If I'm going lossy I likely better look into neural nets, hardly anything beats these in the "close to perfect" game. $\endgroup$ – OverLordGoldDragon Dec 20 '20 at 20:50
  • $\begingroup$ Fairly neat idea on uint16; I'll benchmark to see if CPU overhead for converting back to float32 and rescaling upon load is acceptable. $\endgroup$ – OverLordGoldDragon Dec 20 '20 at 21:06
  • $\begingroup$ @OverLordGoldDragon at least on modern x86 (in any case, on x86_64), and on most ARM64/aarch64, there's SIMD instructions which can do multiple "multiply floats with other float" and "convert float to integer" operations in one, so that in my experience, anything that is in L1 cache can be treated as described above in less than a single CPU cycle (amortized). Anything that needs to be fetched from RAM (large images, for example) will take longer to fetch than to treat with your CPU. Honestly, no other compression algorithm will even be close to that fast. $\endgroup$ – Marcus Müller Dec 21 '20 at 8:22
  • $\begingroup$ ("Fast" really wasn't one of the things I optimized for, since you made no mention of the required throughput and size of the images) $\endgroup$ – Marcus Müller Dec 21 '20 at 8:26
  • $\begingroup$ and again, I bet you'll have nearly no real loss when converting to integer, anyways, if you combine with the companding method that Laurent described; your NN is a stochastic thing, anyway, so it will rather gracefully deal with the quantization noise. (by the way, NNs internally can often work just as well with highly reduced bitwidths, without loss of performance. That means feeding in high-precision data doesn't have inherently a great benefit.) $\endgroup$ – Marcus Müller Dec 21 '20 at 8:35
1
$\begingroup$

I'd second Marcus' answer. I have experienced that LZMA was very efficient for lossless compression of 32 bits 3D scientific data decomposed by discrete wavelet transforms (a benckmark is: HexaShrink, an exact scalable framework for hexahedral meshes with attributes and discontinuities: multiresolution rendering and storage of geoscience models).

Then, the choice may depend on the location of the sparse data. From a Synchrosqueezed Wavelet Transform, they are probably gathered around ridges. If you want something fancy, ridgelet or bandlet compression could be tested, to further sparsify the data, based on linearity and continuity of the features.

Yet, for simplicity, as the precise amplitudes of the ridges are probably less important than their orders of magnitude, I would suggest to use a companding function (called compander or compandor) to emulate a non-uniform quantization of the float-point data to the number of bits of the targeted unsigned-integer image format. Typically, a power law $x\to x^\alpha $, $\alpha \in] 0,1]$ (a square root for instance) would do the job before casting them to uint16 for monochannel PNG coding. If the continuous wavelet is already logarithmically tranformed, then ($c_{t,a}\to \log(|c_{t,a}|+1)$) already plays the role of companding, and it may not be necessary to apply them twice. You can even shrink the maximum value to a smaller limit, like $2^{12}-1$, to help the prediction and an the DEFLATE algorithm for the coding of errors.

You can also plug a preprocessing soft-shrinkage to discard low incoherent values.

$\endgroup$
7
  • 1
    $\begingroup$ Oh, companding, an excellent idea! $\endgroup$ – Marcus Müller Dec 21 '20 at 8:27
  • 1
    $\begingroup$ Hm, there's a few things that I'd like a student to look into (sadly only in German, will have to translate) w.r.t. to lossless compression of (dense) floating point data from radio receivers; the core is really just seeing (signs,mantissas) (mantissae?) and exponents as separable data streams with their own statistical properties, and then trying out standard 1D signal compression approaches (LPC) plus entropy coding to them; then, extend to complex (order of magnitude of real and imaginary part of a number correlate?). $\endgroup$ – Marcus Müller Dec 21 '20 at 9:09
  • 1
    $\begingroup$ then do a couple of predictive things linking back mantissa and exponent: is there a rule from which we can infer that the exponent is likely to change based on observation of the mantissa? such things. $\endgroup$ – Marcus Müller Dec 21 '20 at 9:16
  • 1
    $\begingroup$ We are currently finishing a PhD thesis on the compression of 3D petrophysical properties, and its impact on flow simulation. A paper should be submitted soon (and a patent filled). I definitely would like to do the same on complex data. There were rare complex works in speech compression. I am thinking of a collaborative project in a couple of years $\endgroup$ – Laurent Duval Dec 21 '20 at 9:16
  • 1
    $\begingroup$ oooh! That sounds nice! Just saw your email, thanks! $\endgroup$ – Marcus Müller Dec 21 '20 at 9:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.