UnBlur: image deblurring

What is UnBlur?

UnBlur is a position-space image deblurring algorithm I developed between 1999 and 2001. In 2021 I re-implemented UnBlur using my current ANSI C codebase (available below).

In principle, the UnBlur algorithm can be applied with a completely position-dependent point spread function (PSF). In practice, however, I have only coded it up for the assumption of a position-independent PSF.

As with all deblurring algorithms, UnBlur can only do a fairly good job when the number of pixels in the PSF is relatively small—for example, for a moderate amount of motion blur (which does not need to be in a straight line, and may be non-uniform in intensity). When the PSF contains too many pixels, each pixel of the original unblurred image is distributed amongst too many blurred image pixels for any algorithm to be able to sensibly disentangle the blurring and trace each contribution back to its source, given that quantization and other errors will always be present in the blurred image. The UnBlur code below automatically aborts if it detects that its estimate of the unblurred image is worse than its previous estimate; in the case of PSF with a large number of pixels compared to the typical features in the unblurred image, this will happen even after the first iteration. (The initial estimate is allowed to have a greater error than the input image, since there are cases in which iterations of the process actually reduce such an error below that of the input image.)

I have provided a brief history of the development of UnBlur on a separate page.

Examples

Example uses of the use of UnBlur, using the ANSI C code provided below, are provided on this page.

How does it work?

Point spread function

The programs provided below each extract the PSF to be used from a grayscale image provided by the user. The PSF can be provided as white on black (i.e. black is the zero-signal background) or black on white (i.e. white is the zero-signal background); each program analyzes the set of boundary pixels of the PSF image, and chooses whichever of these two choices is most consistent.

The PSF is automatically normalized, and is stored relative to its center of mass in each direction, rounded to the nearest pixel, so that both blurring and unblurring does not change the position of the center of mass of any signal, to within half a pixel in each direction.

Fundamental operations

The two fundamental operations used in the programs below are blurring and back-propagation. Blurring simply convolves the PSF with an unblurred image, creating a blurred image. Back-propagation, described below, attempts to infer what unblurred image would, under blurring with the PSF, create a given blurred image. In this sense it is an attempt at deblurring, but in most cases it is only one step in the process: back-propagation and reblurring need to be applied iteratively to successively reduce the error between the reblurred image and the supplied blurred image.

Extension boundary conditions are applied in all cases. As with all image processing algorithms, this means that if there is a signficant amount of signal information near any boundary, the extension of this signal across the boundary to the exterior of the image may cause artifacts.

In the following, the three channels of a color image are each processed separately: “intensity” should be read to mean the three-vector of all three components of intensity. (In practice, the three channels are just processed separately, so that the “intensity” is actually just that of the given channel.)

I will also refer to “original unblurred image,” as if this actually existed and then was blurred by the PSF to provide the blurred image that we have. Conceptually, it did exist, even if only as photons entering a camera lens, that may have moved relative to the objects being photographed while the shutter was open, or may not have been perfectly focused. For testing the UnBlur algorithm, of course, actual sharp ground-truth images can be blurred; these sharp source images are the “original unblurred images” that I refer to.

Back-propagation

The heart of the UnBlur algorithm is the back-propagation algorithm.

It starts by constructing an initial estimate of the original unblurred image. For each pixel in the initial estimate, it looks at all of the pixels in the blurred image that are connected by an entry in the PSF to the given estimate pixel. For each such blurred pixel, it asks the question: what intensity value would the estimate pixel need to have, to produce this blurred pixel, if that estimate pixel was the only source? To do this, it actually divides the blurred pixel intensity by the weight of the corresponding entry in the PSF—“undoing” the multiplication used in the blurring operation.

For each estimate pixel, all of these estimated intensity values are collected. The next task is to decide on a single intensity value for this estimate pixel. Now, since each of these values has been obtained by dividing by the corresponding PSF weight, and since some PSF weights may be small, it would not be sensible to simply compute, say, the mean of the set of values, since the large values corresponding to small weights could introduce instabilities. Instead, the back-propagation algorithm computes the median of them, and stores those values as the initial estimate.

Now, for those (in practice rare) cases in which the original unblurred image consists solely of isolated pixels with nonzero intensity, on a background of zero intensity, separated spatially sufficiently that none of their blurred versions overlap, then it is straightforward to see that this estimate will actually be a perfect reconstruction of the original unblurred image, since each of the back-propagated estimated intensity values for each estimate pixel will be precisely the intensity of the original unblurred image, and so the median of them will likewise be precisely this intensity.

In most practical cases, however, more than one source pixel will contribute to any given blurred pixel. The initial estimate overcounts all of those contributions. So the next stage of the back-propagation algorithm is to reblur the initial estimate with the PSF, and then determine how much of an overcounting has occurred, for each reblurred pixel, and decide on a “multiplier” for each such reblurred pixel that compensates for this overcounting. For this it simply compares each reblurred pixel with its original blurred counterpart. If they are of different sign (which will be possible later in the algorithm), then the estimate is way off, and the multiplier is set to zero. If the original blurred pixel intensity is zero, but the reblurred is not, then again the multiplier is set to zero. If the reblurred pixel intensity is zero, then we arbitrarily set the multiplier to unity, since there is no contribution anyway. If the reblurred pixel intensity is less than that of the original, then in fact we have an undercounting, rather than an overcounting, and the multiplier is set to unity. (We don’t want to set the multiplier higher than unity, to avoid introducing instabilities.) Finally, in the case that the reblurred pixel intensity is in fact greater than the original, then we set the multiplier to be the latter divided by the former, to “undo” the overcounting.

The back-propagation algorithm then back-propagates this set of multipliers itself, back to the original unblurred space, with the difference that values are not divided by the corresponding weight of the PSF. The medians for each unblurred-space pixel are then computed, as the “back-propagated multipliers.” By construction, it is clear that these multipliers will be between zero and unity.

The initial estimate is then scaled by this back-propagated multiplier image, and returned as the best estimate of the back-propagation algorithm.

Iteration

The remainder of the UnBlur algorithm is rather simple. The back-propagated estimate is reblurred, and the error difference between this and the original blurred image is computed. This error is then itself back-propagated, and forms a delta to be added to the estimate.

This process is iterated, until either the mean absolute value of the error image is lower than the specified tolerance, or the maximum number of iterations specified is reached.

Initial estimate

The UnBlur code also allows for an initial estimate image to be provided. This can arise in practice where one is deblurring frames of a video or film, where one frame is sharp but the next is blurred by motion blur. Because of the short time between the two frames, the first frame is (if correctly rotated and translated to be precisely overlaid) often a very good initial approximation to the blurred frame. To the extent that it is consistent with the blurred frame, the UnBlur algorithm will leave it alone; to the extent of any inconsistencies, UnBlur will adjust the estimate based on the back-propagation of the error. This allows for a much more accurate reconstruction of the original unblurred image to be obtained. Note, however, that in this process one is “dropping in” detail of the image from another image, and such a step only represents reality to the extent that one can assume that the other image is a good first approximation.

Reference ANSI C implementation of UnBlur

The 2021–2022 reference implementation of UnBlur is contained in the following ANSI C code:

There are four sample programs included:

make_linear_blur
Make a point spread function (PSF) file that is a simple linear blur of constant intensity.
make_magic_blur
Make a circularly symmetric “blob” PSF file using the Magic Blur.
blur_image_psf
Blur an image with a PSF.
unblur_image
Deblur a blurred image using the given PSF.

There are also 79 executables of unit tests and death tests provided.

Instructions for building the code are contained in the _README file within the archive.

Note that all code provided here is from my personal codebase, and is supplied under the MIT License.

Other image processing resources

If you like UnBlur, then you may also find useful the following image processing resources that I have put into the public domain over the decades:

The Magic Kernel
World-beating resizing algorithm, superior to the popular Lanczos kernels, that helps power Facebook and Instagram (2006–2021).
The Magic Edge Detector
Edge detection algorithm, leveraging the power of Magic Kernel Sharp, that is superior to the common Sobel, Scharr, Prewitt, and Roberts-cross algorithms (2011–2021).
JPEG-Clear
A top-down progressive image (mipmapping) algorithm, leveraging the power of Magic Kernel Sharp (2006–2021).
3D JPEG-Clear
The same algorithm as JPEG-Clear, but applied to 3D volumetric data (2010–2021).
UnBlock
Algorithm for removing the “blockies” from images and videos without the need for any parameter tuning (2005–2021).

Disclaimers

This page describes personal hobby research that I have undertaken since 1999. All opinions expressed herein are mine alone. As described in the history page, I put UnBlur into the public domain, via this page and its predecessor on my previous domain, on September 9, 2001. All code provided here is from my personal codebase, and is supplied under the MIT License.