# Losslessness of Laplacian Pyramid

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?

• Always use full name of the paper you link to. As one day its address will change yet if you share its name it can be searched for.
– Royi
Oct 19 '19 at 8:28

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 level, with less crude filters.

• Thanks for the example! This makes it very clear. Oct 20 '19 at 19:41

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)$$

• do the down arrows and up arrows denote up and downsampling? Also my doubt arises since downsampling loses info. If i a downsample an image, and upsample it back, we do not get the same image right? Oct 19 '19 at 9:21
• You don't get the same. But you don't need to. As you keep the residual from the image when you go down and up. It could have been any (Well almost) operation and still you'd get a perfect reconstruction as you keep 2 terms of the 3.
– Royi
Oct 19 '19 at 9:30
• Okay, so If I understand, r is not original image - convolved. Rather, it is original - (upsampled (downsampled(convolve)), is that correct? Oct 19 '19 at 9:43
• Convolution is just a Pre Processing step for Down Sampling. It could be any operation you want. For example let's say $\uparrow$ is multiplication by 2 and $\downarrow$ is division by 4. Still you'd get perfect reconstruction.
– Royi
Oct 19 '19 at 10:02