rescaling wouldn't work as the filter can only reconstruct information that has formerly been present. I got the idea when doing an astronomy course, using a telescope's point spread function to estimate what the stars looked like before they passed the optics.
Convolution in fourier space is a multiplication, thus "undoing" it can be acheived by simply dividing out the convolution. So the process is
Image --FT--> Spectrum
Spectrum/=Convolution Kernel --FT--> Reconstructed Image
As I know the point spread function (the gaussian matrix used for smoothing it in first place) this process is really easily done, you can look up "Wiener filter" on Wikipedia if you're familiar with some analysis:
http://en.wikipedia.org/wiki/Wiener_deconvolutionAs I said, noise makes the thing way more difficult, that's where the ringing effects in the first pictures come from.
The first images don't go through fourier transformation, so I need to iterate an estimate. The algorithm is known as "Richardson-Lucy" for those who are interested in it.
There's also something called "blind deconvolution", which tries to estimate the psf from the source material itself. For stars it's pretty straightforward, since you "know" their shapes. I haven't found out how to do it properly for a normal image, though.
