Comment by snikolov | Hacker News Reader

Comment by snikolov | Hacker News Reader

If you are wondering how they might be doing it, here is one approach that I saw in a computer vision class (no idea if they are doing anything similar to this)

(slides: http://cs.nyu.edu/~fergus/presentations/fergus_deblurring.pd... (~60 MB ppt) paper: http://cs.nyu.edu/~fergus/papers/deblur_fergus.pdf (~10 MB pdf) )

The basic idea is that you have an unknown original image and it is convolved with an unknown blurring kernel to produce the observed image. It turns out that problem is ill-posed. You could have a bizzare original image blurred with just the right bizzare blurring kernel to produce the observed image. So to estimate both the original image and the kernel, you have to minimize the reconstruction error with respect to the observed image, while penalizing unlikely blurring kernels or original images. If one extracts enough statistics from a dataset of natural images, one can tell whether an image is likely or not by comparing that image's statistics to the corresponding statistics of your dataset of natural images. Similarly, simple blurring kernels are favored over complex ones (think "short arc of motion" vs. "tracing the letters of a word with your camera")

----------------------------------------------------

Here are the actual research papers for this video:

http://people.csail.mit.edu/sparis/#publi2011

- Blur kernel estimation using the Radon Transform http://people.csail.mit.edu/sparis/publi/2011/cvpr_radon/Cho...

- Modeling and Removing Spatially-Varying Optical Blur http://people.csail.mit.edu/sparis/publi/2011/iccp_blur/Kee_...

----------------------------------------------------

Fascinating stuff --- thanks for digging that up. The main question in methods like this is how to constrain the blur kernel and the original image. I've only skimmed the first one, but the key idea used there seems to be to constrain things by looking at the edges in the image. The image has its own, natural distribution of edges, but there are also artificial edges created by the blurring that can serve as a clues for the motion of the camera (imagine if everything is blurred diagonally --- there will probably be a lot of artificial diagonal edges)

I recently discovered two neat papers on deconvolution from a Bayesian perspective, written by Kevin Knuth.

http://knuthlab.rit.albany.edu/papers/knuth-ica99.pdf

Abstract: The problem of source separation is by its very nature an inductive inference problem. There is not enough information to deduce the solution, so one must use any available information to infer the most probable solution. We demonstrate that source separation problems are well-suited for the Bayesian approach which provides a natural and logically consistent method by which one can incorporate prior knowledge to estimate the most probable solution given that knowledge. We derive the Bell-Sejnowski ICA algorithm from first principles, i.e. Bayes' Theorem and demonstrate how the Bayesian methodology makes explicit the underlying assumptions. We then further demonstrate the power of the Bayesian approach by deriving two separation algorithms that incorporate additional prior information. One algorithm separates signals that are known a priori to be decorrelated and the other utilizes information about the signal propagation through the medium from the sources to the detectors.

http://knuthlab.rit.albany.edu/papers/knuth-eusipco05-final....

Abstract: Source separation problems are ubiquitous in the physical sciences; any situation where signals are superimposed calls for source separation to estimate the original signals. In this tutorial I will discuss the Bayesian approach to the source separation problem. This approach has a specific advantage in that it requires the designer to explicitly describe the signal model in addition to any other information or assumptions that go into the problem description. This leads naturally to the idea of informed source separation, where the algorithm design incorporates relevant information about the specific problem. This approach promises to enable researchers to design their own high-quality algorithms that are specifically tailored to the problem at hand.

Yes, and it seems that their algorithm needs hints for natural image verses text

I assume the RedLaser barcode app uses something similar from captured video frames combined with data from the accelerometer, no?

I doubt it. Blind deconvolution is hard. I think they may use something like super resolution where multiple blurred pictures can be used to recreate a less blury picture (and this is significantly easier to do than blind deconvolution).

Barcodes are designed to be easy to decode. Even blurred, the 1 or 2 dimensional frequency information is pretty well preserved. If I needed to combine data from several blurred images of a barcode I'd extract the likely values of the barcode from each image separately and then combine those.

Does it make a difference on the technique used if the image is out-of-focus versus blurred by camera motion?

So long as the motion blur is a small enough angle/translation, the difference is only in the shape of the blurring kernel. The kernel will be circular or gaussian for out of focus, while a line or arc for motion.

In one dimension, you'll be looking at a slice (more accurately, a summed projection) of the kernel. Focus = guassian, motion = square wavelet (line) or irregular (arc)

Reply on news.ycombinator.com