Violin lessons

Playing around with the Wacom board my family got me for Christmas...

Interesting fact

Did you know that bronze is actually stronger than Iron? [I'm at work looking up properties of metals right now] Shucks, golly, gee-whillager, you could knock me over with a feather... so what's the whole big deal about the "iron age" following the "bronze age" then?? Sounds to me like it must have been a massive global downgrade. Sort of like when Windows Vista was released.

O hisashi

I can't believe the last time I posted was in October... seems a lot longer ago than that. There seems to be some sort of immense barrier in my timeline that divides my unmarried life from my married life. The events on either side of it seem vague and obscured when viewed from the opposing side.

Anyway, I've definitely not been trying to hide from people or neglect anyone. I've been trying to build a solid foundation for a relationship with my wife and start off on the right foot, which takes a lot of work. Good work, enjoyable work, totally worth it. It does mean that certain things like blogging (and facebook) get the shaft. Another thing - we were on the recieving end of much generosity from friends both near, and on the other side of the world around & after our wedding date. Be assured if you read this that we haven't forgotten to thank you and we most certainly will, it's just that sometimes the daily tasks we are faced with at the moment seem overwelmingly huge, and thank-you cards may not be something we are able to complete in the immediate future.

I've had all sorts of thoughts recently that make me think "boy that would make a great blog post!" I just can't remember any of them right now. Hopefully this blog post is an indication that blogging will continue and I'm not leaving this blog to rot.

So anyway, I'll wrap up with some cool tricks I was messing around with on Matlab for a while, then some photos.

****

Deconvolution - how to fix camera-shake

I've wondered for a long time if it's possible to recover an image from a badly distorted image. The thing tha tmade me wonder was when I saw an article in BBC news about how a criminal was identified by undoing a weird digital manipulation of his face to reveal his true identity. I thought "Dang... how did they do that?" and "If they did that, could you use the same trick to fix camera shake?"

Well, turns out that fixing something that has been digitally manipulated can (if the transformation is fairly simple, which in this case it was) be reversed nearly perfectly. Fixing an actual image is a lot harder, and is a heavily discussed issue, generating large numbers of papers in periodic journals.

The fixing camera-shake can be described as a "deconvolution" problem. Without going into great detail, deconvolution is essentially a process that tries to work-backwards to find an initial signal or input (in this case our unshaken, perfect photo) by dividing the transformation (the shaking) from the output of the signal. Now to introduce a very important term: the Point -Spread function, or "PSF". The point-spread function is the resulting image you would have if your camera was looking at a very sharp point of light, and shook exactly how the camera shook for the real image. The resulting blur or streak describes the transformation that maps the original signal to the blurry one your camera sensed. So deconvolution essentially tries to divide the PSF from the image to recover the original.

What's so hard about that? Deconvolution is often described as an "ill-posed" problem, meaning that even if you did know the exact point-spread function and naively tried to divide it from the blurred image, the result will still be garbage, even worse than before. The cause is noise. Dividing by the psf often requires dividing by very small numbers. If you had a perfect (and non-existant) camera, you could do this, but every camera has electronic noise (the scattered grainyness you see in digital photos). The noise ruins the division process, by making the output have huuuuuuge signals when the divisor is small.

So, essentially what I am trying to say is, even if you know exactly how your camera shook, you couldn't get back to the original. Case closed, the end, everyone go home. Just kidding! Lots of smart people, over the course of many years, have developed techniques to approximate the original signal and get around this problem. Because of a problem I was trying to solve at work, I tried to learn about as many of these procedures as I possibly could. Some were dead ends, others worked remarkably well.

Deconvolution algorithms generally fall into two catagories: iterative and non-iterative. Iterative methods are slower, however they have some advantages, namely, if you add certain weighting schemes (which by the way are nearly impossible to understand if you don't have the appropriate background in mathematics and statistics) to them they can repress un-desirable features, such as ringing, which often occur when trying to deconvolve an image with an imperfect reverse transformation. The following is a list of a different deconvolution methods and some of the strengths and weaknesses I observed. A lot of smarter more dedicated people came up with improved methods, but I couldn't decifer their papers very well so I was stuck with these.

Richardson-Lucy algorithm. Class - iterative, non-negative. Strength: fairly simple to implement. Super popular for some reason. Weaknesses: Can't handle negative values. The raw algorithm seems to give freaky, terrible answers if your point-spread is even a bit off. I always got patches in my images that grew to become discontinuities. It did, however, clean up images extremely fast if the point-spread function was known exactly.

Van-Cittert algorithm. Class - iterative. The oldest and probably the most reliable and best working algorithm I could find, if you do the appropriate signal conditioning first. If you do a google search for "image deconvolution", the first link you find is a site that reviews all these methods, and it says that Van-Cittert is the worse and shows how it totally screwed up an image even though the point-spread was relatively simple. All I can say is that they must not have been applying it correctly, because I was able to correct some crazy stuff with the Van-Cittert method, even when my point-spread function was noisy. I found that the algorithm completely fails for even simple stuff, however, if you just try to deconvolve the raw PSF from the image, however.

Landweber algorithm. Class-iterative. This algorithm looks like a modified Van-Cittert algorithm, and worked reasonably well. It could handle raw PSF deconvolution better than the Van-Cittert (but not better than the corrected van-cittert), but converged slower than the Richardson-Lucy for low-noise cases in which the exact point-spread function was known. Also, like the Van-Cittert algorithm, it can handle negative values, which the richardson-lucy can't.

Weiner-deconvolution. Class - non iterative. This algorithm was the simplest and fastest, and returned results as good as the Van-Cittert method. Because it was the quickest, I stuck with it. The only problem with it is that your solution is non-optimal unless you know the power-spectral-density of the original signal and the noise. I don't know either, for a photograph, so my results are non optimal. They are still pretty good, however. A major problem with this algorithm is the propensity for ringing produced near the image as a result of cropping (the point-spread function necessarily has no way of knowing the values past the edge of the image).

Anyway, this is fascinating stuff. I was able to apply it to great efficacy for a problem I was trying to solve at work. A side benefit was that I could try applying it to photos. Here's an example. This is a photo of Hilary I took, playing the piano. I intentionally violently shook the camera when taking this photo:

Original (cropped)

corrected (cropped)

So obviously the "corrected" version has major deficiencies. A ton of ringing is present, which pretty much obliterates the top of the image. However 1) I can tell it's Hilary playing the piano now, instead of just a smudge, 2) I can tell it's an old-school mac in the background, 3) I can make sense of the scene.

With a little more work, we can make even further improvements. The image was cropped, originally. Edges are going to be trouble, but if the edges can be pushed away from the region of interest, then the ringing should be less obnoxious. Furthermore, tapering the edges using a weighting function can also decrease ringing. The following corrected image applied both of those techniques, and is an even better re-construction.

Well, time's up. This is a pretty interesting subject, though, and I'd like to explore it further.