# Does this progressive image compression exists?

I want to know if this progressive image compression that I have in mind exists and it it does I want know its name and/or get some references about it.

The algorithm consists of converting one high resolution image in multiple low resolution images (all of the same size, not like in wavelet transform) with the following properties:

• If you have one of them, any of them, you can reconstruct a low resolution approximation to the original image.
• You can compose many of those in any order to get better approximations to the original image.
• If you combine all low resolution images you get the original image or a very good approximation of it without perceptible artifacts.
• Algorithm is real-time, i.e. it can display a meaningful partial reconstruction of the original image at any time of the reconstruction process (independently of received sub-images and their order).

Does this algorithm exits? Is it possible at all?

I know about image reconstruction techniques, but those use similar but different images to reconstruct a higher resolution one and the result is always noisy and full of artifacts. This is not I am asking for.

• You can subsample your image with different shifts. – Yuval Filmus Jul 2 '18 at 21:38
• @YuvalFilmus The main question is how to recombine them. It's straightforward to take 256 down-sampled images from an original, but how you progressively reconstruct the original from the down-sampled images receiving them in any order and number? You can not just put each new received pixel like in PNG or JPEG standards because you don't have levels of down-sampled images. You have a bunch of equal sized down-sampled images. A naive reconstruction will be very unpleasant to look at. If possible I want a real progressive resolution enhancement for each newly combined down-sampled image. – user3368561 Jul 3 '18 at 8:55
• On the contrary, it's very easy to have perfect reconstruction. Divide your original picture into small squares or rectangles, and subsample by taking one point from each. – Yuval Filmus Jul 3 '18 at 8:57
• You interpolate in some smart way. This is classical signal processing. – Yuval Filmus Jul 3 '18 at 9:36
• If you have downsampled by a factor $d$ in both axes, you only need to add $\log d^2$ bits to each downsampled image to identify which of the $d^2$ pairs of shifts it was computed from. This is essentially free. If you only have a subset of the downsampled images, for any "missing" pixel, you can reconstruct an approximation to the original by taking a weighted average of the colours of nearby known pixels, weighting each by (some function of) the inverse of their distance. – j_random_hacker Jul 3 '18 at 9:48

I believe that the Stationary Wavelet Transform (SWT) meets your requirements: https://en.wikipedia.org/wiki/Stationary_wavelet_transform

1) Any given level of coefficients could be used to reconstruct the original image by running normal reconstruction but assuming zeros for the other levels.

2) Each level of coefficients stores data about a different range of spatial frequencies in the original image, and thus they can be recombined arbitrarily.

3) Unless you quantize when or after you perform the transform, the SWT is lossless.

4) I haven't done any processing time evaluation, but optimized libraries are available: https://www.mathworks.com/help/wavelet/ug/discrete-stationary-wavelet-transform-swt.html

In general though, unless you require translation invariance, you would benefit from the downsampling in the more common Discrete Wavelet Transform (DWT). The downsampling results in smaller images which requires less space to store and time to process. No information is lost by this downsampling as the frequency filters in the DWT filter out and then store (in the higher resolution levels) the frequencies that then get lost in the downsampling. The lower frequencies simply need fewer samples to be accurately reconstructed (https://en.wikipedia.org/wiki/Nyquist_frequency).

• Interesting algorithm. Maybe it will fit my needs. My problem with conventional wavelet transform is that each new level produces a bigger image. To fit it in a fixed size network packet you need to split them in regions, so if you lose one packet, instead of a global degradation you get a localized one, which produces very ugly visual results. – user3368561 Jul 18 '18 at 20:39
• Since I don't know your packet structure well I can't comment on its applicability to your problem, but I can say that the DWT maintains the same size after transformation. Each iteration downsamples by two in each dimension (by 4 all told) and divides the result into 4 coefficients for HH, HL, LH, and LL. Because you downsampled by 4 and created 4 different outputs, you end up with the same total number of values! Also, if you like the answer, please accept it so I get get those sweet sweet points :) – Kantthpel Jul 18 '18 at 21:47
• But each iteration is 1/3 the size of the previous, so if your last iteration fits inside one packet, previous iteration will need 3 packets to be fully transferred, next will need 12, next 48, and so on. A naive split of each level into fixed size packets is not capable of recovery from data loss. – user3368561 Jul 18 '18 at 23:14
• Ah I see, you're sending each level individually. Well, then the SWT should work for you! – Kantthpel Jul 19 '18 at 17:20

If you have one of them, any of them, you can reconstruct a low resolution approximation to the original image.

this means that they duplicate the information. imagine а 8x8 blue area. if each sample carries info that this are is blue, you carry N duplicates of the same info. So, the compression ratio will suffer

• Not really. You can split one image in two taking even pixels in one sub sampled image odd pixels in another. Each sub sampled image is capable of reconstructing an approximate of the original image and there is no duplication of information, you just "cut" the original image in half – user3368561 Jul 4 '18 at 8:50
• @user3368561if the image is black-white "chessboard" then one of this "approximation images" will be full white and another one full black – Bulat Jul 5 '18 at 11:24