# Inverse Image Filtering with Conjugate Gradient

Presented at BOOM 2003
by Zhengyun Zhang

### The Problem

Suppose that we are given a filtered image, along with the exact filter that was applied to the image, how do we find/compute the original image?
 The Original Image

# →

 0 1 2 1 0 1 2 3 2 1 2 3 4 3 2 1 2 3 2 1 0 1 2 1 0 Filter

# →

 The Blurred Image

### Possible Solutions

1. Naive Inverse Convolution (details)
Suppose we are given the above convolution filter, a straightforward approach would be to take the processed pixel and subtract out appropriately weighted values of the surrounding pixels. This is the general basis for standard "sharpen" filters.
 0 1 2 1 0 1 2 3 2 1 2 3 4 3 2 1 2 3 2 1 0 1 2 1 0 Original Filter

# →

 0 -1 -2 -1 0 -1 -2 -3 -2 -1 -2 -3 40 -3 -2 -1 -2 -3 -2 -1 0 -1 -2 -1 0 "Inverse" Filter
2. Matrix Inversion (details)
If we look closely at convolution and represent an image as an extremely long vector, a convolution is actually a linear transformation on an image vector. Therefore, this means we can represent the filter as a giant matrix. Provided that the matrix is invertible, we can invert the matrix and apply it to our processed image to get the original image back. In fact, it is not necessary to invert the matrix fully. We can also factor the matrix using Gaussian elimination or Cholesky factorization.
 A=filter matrix, x=original image, y=filtered image Ax=y A-1y=x
Following the assumption that the transformation is a matrix, we can also find the original image by using iterative methods. Moreover, if the transformation is a symmetric positive definite matrix, we can use a relatively fast method called the Conjugate Gradient method to iteratively solve for the original image.

### Naive Inverse Convolution

Pros:
• Speed
Using this method, processing is very fast. Supposing that an image has a size of O(n2), we would have to perform a constant number of operations on each pixel. Hence, the running time of this method would be O(n2).
• Ease of Implementation
Programming something to perform the "inverse" convolution is very straightforward. All one has to do is first "invert" the filter and then apply it the same way the original filter was applied.
Cons:
• Image Error
 The Blurred Image

# →

 0 -1 -2 -1 0 -1 -2 -3 -2 -1 -2 -3 40 -3 -2 -1 -2 -3 -2 -1 0 -1 -2 -1 0 "Inverse" Filter

# →

 The Blurred Image Sharpened
As can be seen from the diagram, using this method incurs a great amount of error between the final image and the original image. The ripples nearly all disappear, and it is very hard to distinguish separate branches on the trees in the distance. Therefore, for high quality tasks, this method is not appropriate.

### Matrix Inversion

Pros:
• Correctness
As long as the forward transform is invertible, we can theoretically obtain the original image by inverting the transformation matrix and applying it to the processed image.
Cons:
• Not Scalable
The problem with matrix inversions is two-fold. First, general matrix inversions usually take O(N3) time, where N is the length (or width) of the matrix. The matrix in this case, would have to have length O(n2), the size of the image. Therefore, if we apply a general matrix inversion to this matrix, we would require a running time of O(n6) which definitely does not scale well with size. However, one may say that a specialized algorithm can be developed to handle these convolutions specifically, since such matrices have nice properties such as sparseness and some sort of order. The problem then becomes finding an algorithm that does not run in O(n3) that can work for as many filters as possible, and this is very hard to accomplish.
The second problem is storage. The original transform can be stored very compactly, since it is determined by O(m2) values, where m is the width or length of the convolution filter. However, the inverse transformation poses problems, because the inverse matrix is no longer sparse. Therefore, we may have to store the entire matrix, which takes O(n4) bytes. That is a serious issue. For example, let us consider a 600×600 image. The size of the inverse matrix would be 600×600×600×600 or 100 billion entries. Now, assuming each entry is a double precision real number, we are looking at 1.0368 bytes, or roughly 965.6 GB. Not many machines possess this much hard drive space, let alone memory. However, one can argue that for such a specialized task, a specialized algorithm can be developed in such a way that there is a small, factored form. When I attempted to do that for a simple 3×3 blur filter, it took me days to work out the algorithm using pencil and paper and it still required O(n3) space, which would have been 1.6 GB of storage!

Pros:
• Near Perfect Inversion
 The Blurred Image

# →

~400 iterations, 29 seconds on Athlon 800
target r2 = 0.001

# →

 The Processed Image using CG
As one can see, the conjugate gradient method applied in this case gets near perfect results. The tree branches are very distinguishable, and we can see clearly the ripples and the bird. However, this inversion is not perfect, as some of the dithering on the top right corner is slightly different from the original image. However, this is not very noticeable.
• Efficiency
Cons:
e convolution filter, the matrix vector multiply is actually O(N) or O(n2) instead of O(N2). Therefore, the total running time for a nbyn image is O(n4) which is markedly better than the brute force matrix inversion algorithm.
The key advantage CG has to pure matrix inversion is storage. In each iteration, one only needs to store a few vectors, and the iteration only needs those vectors for that iteration or the one immediately afterwards. Hence, we can store the intermediate data in O(n2) space, much better than the O(n4) needed for pure matrix inversion.
• Intermediate Values
The nice thing about iterative methods is that they can be interrupted halfway and still compute a good approximate. The image above was not run for 254×190=48260 iterations. Rather, it was interrupted at roughly 400 iterations after the residual (a measure of how close the filtered guess is to the filtered original image) and still showed excellent results.
• Cons:
• Not Applicable to All Filters
This algorithm, while creating great results, does not apply to all filters. The conjugate gradient algorithm requires that the matrix be symmetric positive definite to guarantee an exact result. However, most pure image convolutions that are used (we discount sharpen here because we either have to clip the result, or we have to recenter the results, making it either nonlinear or affine) are going to be positive semidefinite, because we simply cannot use negative values in images. It turns out that semidefiniteness is enough to get a pretty good approximation of the inverse.
The main problem is the symmetry. If the filter is not symmetric, the CG method falls apart completely, and doesn't converge. However, this can be solved (hopefully) by noting that any matrix multiplied by its transpose is a symmetric matrix. Therefore, we can find the original image by:
Ax=y
ATAx=ATy
x=(A-1A-T)ATy
• Long Running Time
Having a runtime of O(n4) still presents some issues with scalability, although it is not as bad as O(n6). Therefore, this algorithm cannot compare in speed to something like our first attempt, the naive "inverse" filter. However, we can terminate the iterations prematurely and still obtain a decent result.

### Conclusions

• Feasability
Currently, the CG algorithm is feasible and applies to a good subset of the original problem statement. It can generate much better results than a simple sharpen filter for deblurring. Its storage requirement scales very well, and its running time is shorter than a brute force matrix inversion.
• Applications
There are some situations in which this algorithm would be useful. Suppose that we have some sort of digital imaging device that has a known and measured lens/sensor error. For example, a pixel sensor may accidentally pick up a fraction of signals from neighboring pixels. If this error data is put into the form of a convolution filter, we can theoretically correct all images that have this error.

### Appendix

Below are comparison images (zoomed in) for a 64×64 black and white text image.
 The Original Image

# →

 0 1 0 1 4 1 0 1 0 Original Filter

# →

 The Blurred Image
 The Blurred Image

# →

 0 -1 0 -1 8 -1 0 -1 0 Sharpen Filter

# →

 The Sharpened Image(using fixed size filter)
 The Blurred Image