Can you recover a blurred image?

I was watching a video by Grant Sanderson (aka 3Blue1Brown) about convolutions, image processing, and the Julia programming language (awesome language!) when someone asked this question.

The video by Grant Sanderson. I recommend it very much!

He answered (correctly) that he didn’t think so, because we’d be losing information. However, I thought a little more about the question and figured that it would actually be possible if the output image had the same size as the input one! This way, the output has enough pixels/information to recover the original one.

First, I should start by explaining what a convolution is and how it can be used to blur an image. If you want a thorough explanation, I suggest the video above, but if you want a quick one, I got you. So, a convolution is a mathematical operation that, when applied to images, can be seen as a filter applied to it.

Image from GitHub: vdumoulin/conv_arithmetic .

In this animation, we can see an example of a convolution of an image with a filter/kernel. The original image would be the blue matrix, the kernel the sliding dark blue matrix, and the output the greenish-blue matrix.

The convolution is obtained by multiplying the overlapping kernel and image and summing the products. The following equations may help: given an image x and a kernel k, the result of the convolution will be y,

with

If you already knew how convolutions on images worked, maybe this system of equations isn’t too scary. If you didn’t, don’t worry, you won’t have to remember it, that’s the program job! A useful representation is to interpret the convolution as a matrix multiplication, which isn’t too difficult to write from the equations above:

equivalent to the matrix equation

With this representation, it seems that knowing A and y, then x could be calculated by solving the equation above. However, since A has more columns than rows, the system is said to be undetermined, which means that we can’t obtain only one solution.

I started by saying that, to be possible to reverse a convolution, the input and output sizes would have to be the same. In matrix form, this would correspond to A being square (same number of rows and columns), allowing us to invert it and calculate x as

Now, our input is 4x4 and the output is 2x2. How can we obtain an output with the same size as the input? One way would be to add a padding to the input image, for example, 0-padding,

This way, the output would be 4x4 like the original input. In detail, for this simple case of a convolution with padding, the output dimensions can be calculated as,

If we want the input and output to have the same size, then the padding has to be,

which yields an important condition: the kernel size has to be odd since the padding is an integer value.

This convolution can also be represented as a matrix multiplication as the one above, but I’ll spare you the boredom of reading it since the dimensions would be much larger. One would write the equations of the convolution associated with each entry of y and then structure it as a matrix multiplication as above.

Notice that despite the padded input being 6x6, corresponding to 36 elements, only 4x4 of those elements are unique and unknown variables. Therefore, x in the equation can be only 16x1, instead of 36x1.

To solve for x and reverse the convolution, one only needs to know A and y. To construct A, one needs to know the kernel used for the convolution and the type of padding used.

Now, how could this be used?

An image can be blurred by doing a convolution. For example, a Gaussian Blur is obtained by convolving an image with a kernel/filter that has a Gaussian distribution with the largest value at the center and values that sum to 1. An example would be the kernel

I did a simple implementation of this problem in Julia to check that it is, in fact possible, to reverse the convolution, which you can review and use at the link below.

gonced8/reverse-convolution

So I started by blurring an image with a Gaussian Blur. I did a convolution of the original one with a Gaussian kernel and used replicate padding (values outside the original image are set to the nearest border value, instead of 0).

Original image on the left and blurred one on the right.

Since I knew the kernel used, I was able to construct the matrix A and then solve for x. The results are as expected: the reconstructed image is exactly equal to the original one.

Blurred image on the left and reconstructed one on the right.

Feel free to check the implementation linked above and verify that the original image was not used in the reconstruction.

Now, this 100% reconstruction is only possible because the kernel and padding used are known. What happens if we use a kernel that is not exactly the same as the one used to blur the original image?

Blurred image on the left and reconstructed one on the right, when not using the exact kernel.

And what if we assume 0-padding when replicate padding was used?

Blurred image on the left and reconstructed one on the right, when not assuming the exact padding.

As we can see, if we don’t know the kernel and padding used, then we’re not able to reconstruct the original image. In this sense, it can almost be seen as an encryption problem: if we know the “key”, then we’re able to reconstruct the original message without any loss or additional noise.

Reconstructing the original image is also a very expensive task since matrix A grows very fast depending on the size of the original image. If the original image was 4x4, then A would be 16x16 — the number of elements scale with N².

Hope you liked this brief explanation and found it interesting. I surely did and it was a very good way to learn more about Julia, convolutions, image processing, and linear algebra. If you have any questions and/or find any error, feel free to share.

As a goodbye note, I think we don’t need to worry about people reversing our blurred photos, for now.

Blurred image on the left and reconstructed one on the right.

Featured image.