The Problem

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

Naive Inverse Convolution

• Speed
  Using this method, processing is very fast. Supposing that an image has a size of O(n²), we would have to perform a constant number of operations on each pixel. Hence, the running time of this method would be O(n²).
• 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.

• 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

• 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.

• Not Scalable
  The problem with matrix inversions is two-fold. First, general matrix inversions usually take O(N³) time, where N is the length (or width) of the matrix. The matrix in this case, would have to have length O(n²), the size of the image. Therefore, if we apply a general matrix inversion to this matrix, we would require a running time of O(n⁶) 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(n³) 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(m²) 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(n⁴) 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(n³) space, which would have been 1.6 GB of storage!

Conjugate Gradient

• Near Perfect Inversion
  

  The Blurred Image

  →

  Conjugate Gradient Algorithm ~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
  

• 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
  A^TAx=A^Ty
  x=(A^-1A^-T)A^Ty
  
• Long Running Time
  Having a runtime of O(n⁴) still presents some issues with scalability, although it is not as bad as O(n⁶). 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

Appendix