Losslessness of Laplacian Pyramid

Question

I was just reading up on the Gaussian pyramid and the Laplacian pyramid, used in compression applications of image. The source is here - Carnegie Mellon 16-385 Computer Vision - Spring 2019, Lecture 3 - Image Pyramids and Frequency Domain.

The slide claims that during Laplacian Pyramid based compression, the original image can be reconstructed back perfectly, because of saving the residuals images.

My understanding of the process is as follows

• Convolve original scale image with a Gaussian

• Compute the residual image, and save it

• Downsample the convolved image, dropping alternate row and column to get to the next level (lower size image).

• Repeat process at this scale, till you reach lowest resolution desired.

Now, it says that given the lowest size image, and the residuals, we can reconstruct back the highest size image.

However, since we are dropping alternate rows and columns while downsampling, isn't this information lost? How can the reconstruction be perfect?

Answer 1

A very simple example on a $2\times 2$ image

$$I_0=\begin{bmatrix}a&b\\c&d\end{bmatrix}$$

with (very crude Gaussian) low-pass:

$$g=1/4\begin{bmatrix}1&1\\1&1\end{bmatrix}$$

yields a downsampled $I_1$ after filtering, with only one pixel (out of 4): $$I_1=\begin{bmatrix}(a+b+c+d)/4\end{bmatrix}$$

It can be upsampled as:

$$U(I_1) = I_1^\cdot=\begin{bmatrix}(a+b+c+d)/4 & (a+b+c+d)/4\\(a+b+c+d)/4 & (a+b+c+d)/4\end{bmatrix}$$

hence with the difference matrix: $\Delta_1 =I_0-I_1$

$$\Delta_1=\begin{bmatrix}(3a-b-c-d)/4 & (-a+3b-c-d)/4\\(-a-b+3c-d)/4) & (-a-b-c+3d)/4\end{bmatrix}$$ one can write:

$$I_0 = U(I_1)+\Delta_1$$

Splitting a matrix in a sum of matrices with different behaviors can be called morphological decomposition, deflation, etc. Per se, getting two matrices instead of one, or $4+1$ values instead of $4$, is not efficient. But if the two matrices have different distributions, or can be altered with respect to vision, such a decomposition is useful for sparse processing or compression.

A more generic Laplacian pyramid of course works at several levels, with less crude filters.

Answer 2

Actually the down sampling has no role here.
It is all based on a real simple equation:

$$ I = A + B $$

It is always enough to keep 2 terms of the 3 to restore completely and perfectly the information.

So let's look on this:

$$ {I}_{0} = \left( \left( {I}_{0} \downarrow \right) \uparrow \right) + {R}_{0} $$

So if we keep $ {R}_{0} $ and we have $ \left( \left( {I}_{0} \downarrow \right) \uparrow \right) $ we can recover $ {I}_{0} $ right?
But we can fully recover $ \left( \left( {I}_{0} \downarrow \right) \uparrow \right) $ form $ \left( {I}_{0} \downarrow \right) $ as it is deterministic known operation (Up sampling) right?

So instead of $ {I}_{0} $ we will keep $ {I}_{1} = \left( {I}_{0} \downarrow \right) $ and $ {R}_{0} $.

We now can repeat the same trick for $ {I}_{1} $:

$$ {I}_{1} = \left( \left( {I}_{1} \downarrow \right) \uparrow \right) + {R}_{1} $$

So instead of keeping $ {I}_{1} $ we can again keep $ {I}_{2} = \left( {I}_{1} \downarrow \right) $ and $ {R}_{1} $.
So in order to resotre $ {I}_{1} $ perfectly all we need is $ {I}_{2} $, $ {R}_{1} $ and $ {R}_{0} $.

Keep doing this and you will get the Laplacian Pyramid which says keep the residual of each level and the Low Pass image of the last image.

The trick here isn't the accurate definition of $ \downarrow $ or $ \uparrow $ but being able to get the same result every time you use them. Namley:

$$ \left( \left( \left( \left( I \downarrow \right) \uparrow \right) \downarrow \right) \uparrow \right) = \left( \left( I \downarrow \right) \uparrow \right) $$