Deconvolution, can it be done?

[drizztcanrender]

Ok i saw something very interesting the other day.A method of sharpening the image.It's called deconvolution.My knowledge on this is very limited so i'm just pointing otut to the developers,so you can have a look.Alas the main article is in Russian.There is also an app that displays the deconvolution algorithm in action and i must say it is very very impressive.Although it is very slow,which could be aan indication of how slow it could be if it ever became a filter.But sometimes speed is not an issue and there are always optimizations :)
Anyway,stop talking now :)
Here is the page:

http://www.vitiy.boom.ru/deconv.htm

[Richard Berg]

One-sentence summary: if you know the output and the transform function, you can determine the input to arbitrary precision by approximating the transform with Fourier series.

My impression: whoop de do -- it's a math problem out of an undergrad textbook that he happened to solve with a computer. I don't even see the point of re-christening it "deconvolution" since the whole point of convolutions in general is that they're transitive ((f(g(A)) = (f*g)(A)). Get back to me when random noise can be modelled by linear functions.

Of course, feel free to correct me if I'm wrong :)

[trbarry]

An interesting link from our friend Google:

New Efficient Approach to Blind Deconvolution of Images Discovered (http://math.nist.gov/mcsd/highlights/blinddeconvolution.html)

I was reading about deconvolution on some random web page a few months ago when I came up with my UnFilter compromise. But I can't find the link now and I never really did understand the math.

- Tom

[sh0dan]

Although the new technique does require interactive adjustment of parameters, it still enables blind deblurring of 512x512 images in only minutes of CPU time on current desktop workstations.


"only a few minutes" ;)

[morsa]

Someone has done any research about this topic??
I was using Autodeblur from Autoquant and it took only 20 sec to perform 3 iterations on a 1024x768 b/w image @Pentium 3 900 MHZ

[bb]

Originally posted by morsa
Someone has done any research about this topic??
I was using Autodeblur from Autoquant and it took only 20 sec to perform 3 iterations on a 1024x768 b/w image @Pentium 3 900 MHZ Which is more than 40 days for a two-hour movie @ 25fps :eek: :eek: :eek:

bb

[morsa]

But it is not supposed that you will process a movie @ 1024x768 @ pentium3 900 MHz with a software package designed to be use in microscopy, Am I right??

[Xenoproctologist]

Originally posted by bb
Which is more than 40 days for a two-hour movie @ 25fps :eek: :eek: :eek:

But you have to keep in mind that the vast majority of that time is probably spent doing the "Auto..." part, else that site wouldn't be so fired up about it.

Derive the deconvolution algorithm on the first frame, then use it for the rest of the clip. The per-frame calculation beyond that shouldn't be terribly much more than a normal convolution filter.

[morsa]

exactly.
May be 30% of the time.

[Macanudo]

Apparently there is a filter for Vdub in development. It is being discussed on another board. Here is the link:

http://virtualdub.everwicked.com/index.php?act=ST&f=7&t=168&st=30

I am just a nob so it is all greek to me, but it looks promising. I would love to see a similar filter developed for Avisynth 2.5. I hope that some of the talented developers in the forum see it and take it on.

Thanks,
Macanudo

[morsa]

Well, Development seems to be stopped by now.
There aren't enough interested developers to go on at the moment.
There is lot of usefull GPL source code that just need to be ported but I can't find anybody who wants to do it.
Nobody seems to be interested about restoring material, all the efforts are towards compressibility and that stuff.
Sorry, may be in a couple of months.....

[morsa]

Simg.
That's the way to go I think.
It has many modules in Pascal.
One to search for the PSF, and some others for every Deconv method.
I hope some skilled programmers pay attention to this piece of soft cause an Avisynth Deconv filter could be at hand.
If we calculate the PSF for the first frame and then apply it to the whole sequence, processing time won't be so tedious.The same happens if one could only apply deconv to luma channel.
Could it be possible?

[Ookami]

Bump :)

[morsa]

I discovered, reading some pages, that a good deconv could be achieved by first denoising the image using a wavelet denoiser (there is one for Vdub I think)and second applying Wieckert (or something like that, please check the spelling)algorithm to deconvolve the image.The approach gives excellent results.

[Dali Lama]

Here is a link I found about De-Convolution

http://www.maxent.co.uk/examples.htm

Bye,

Dali

[mf]

I tried deconvolution on anime, no use ;). Just so you guys know :D.

[morsa]

I believe this just needs to be ported to Avisynth and to work only on Luma.
Anybody dares??


http://sourceforge.net/projects/refocus

The other Gimp filter called Refocus-It was ported many months ago to work under Vdub environment.Two flavors: RGB and Luma.( This is meant to work for real life stuff not Anime )


At Vdub's forum there is a link to Vdub Refocus plug in (still beta)

http://virtualdub.everwicked.com/index.php?act=ST&f=7&t=168&st=75&hl=

[Mug Funky]

refocus is good, but slow as f***.

the above mentioned deconvolve technique seems more efficient to me, but i'm not sure.

refocus is a brute force method where you give it an approximation of the input blurriness and it seems to apply negatives of that image at random offsets within the "blur envelope" (btw, i don't know the maths and terminology, just what i've observed from using it).

however, refocus falls over at blurs beyond about 2 pixel radii for anything practical (it's AWESOME at sharpening though. i fed it a blurry photo of a guy holding a beer can, at the end i could read the little bit on the beer that says "375ml". i'm impressed by that fact, but the noise amplification was considerable and GIMP and photoshop haven't any good ways to get rid of this)

[vidiot]

Wouldn´t use it for video - to slow even for short clips!

Regarding images:
http://meesoft.logicnet.dk look for "image analyser"

works as the gimp plugin, but you can determine different test steps.
Gives me some useful nice results with defocused picture from my digital camera...(not as impressive as the example pictures on the website though).

Harald

[vcmohan]

I worked in Oil Exploration Seismic Data Processing. There we do a lot of deconvolution. The windowed data is auto correlated and then an inverse filter is designed. Since in Video the data is only in parts defocussed (since normally subjects may be at varying distances and will be in varying degrees of focus, windowing is required) While in seismic a one dimensional filter is designed in video a 2 dimensional filter may be needed. However due to circular symmetry, the one dimensional filter should work with slight adaptation. The filter in seismic is for Minimum Phase criterion while in Video it needs to be Zero phase criteria.

[morsa]

As you like....
Anyway the filter is up and running and proved to be very useful to many people (included me).
If someone is interested about improving it or porting to Avisynth any of them, he/she would be welcome.

[SealTooGreat]

Do any of avisynth develepors/programmers think of creating/porting some kind of blind deconvolution filter?!

[MfA]

My impression: whoop de do -- it's a math problem out of an undergrad textbook that he happened to solve with a computer. I don't even see the point of re-christening it "deconvolution" since the whole point of convolutions in general is that they're transitive ((f(g(A)) = (f*g)(A)).
Deconvolution in the way you describe above would work fine if it wasn't for the fact that images are not critically sampled by a long shot and noise is added after the blur occurs. In practice it's hard to do well.

[rfmmars]

Apparently there is a filter for Vdub in development. It is being discussed on another board. Here is the link:

http://virtualdub.everwicked.com/index.php?act=ST&f=7&t=168&st=30

I am just a nob so it is all greek to me, but it looks promising. I would love to see a similar filter developed for Avisynth 2.5. I hope that some of the talented developers in the forum see it and take it on.

Thanks,
Macanudo

There is a Vdub plugin which I have called "Refocus" Version 0.1.3 which I think is Deconvoltion, a ported "Gimp" plugin very slow but does work.
Have search the web with no results.

See

http://www.wired.com/news/technology/0,1282,69594,00.html
http://refocus-it.sourceforge.net/
http://refocus.sourceforge.net/
http://www.digikam.org/?q=image

Richard
photorecall.net

[dbzgundam]

There is a Vdub plugin which I have called "Refocus" Version 0.1.3 which I think is Deconvoltion, a ported "Gimp" plugin very slow but does work.
Have search the web with no results.

See

http://www.wired.com/news/technology/0,1282,69594,00.html
http://refocus-it.sourceforge.net/
http://refocus.sourceforge.net/
http://www.digikam.org/?q=image

Richard
photorecall.net

You HAVE said filter for virtualdub? I lack GIMP, so I cannot test this filter on still images, but even a super slow vdub version would be nice to see... Post if you can! :D

[rfmmars]

You HAVE said filter for virtualdub? I lack GIMP, so I cannot test this filter on still images, but even a super slow vdub version would be nice to see... Post if you can! :D

Yes e-mail

rfmmars@cox.net

Richard

[SealTooGreat]

@rfmmars
Why don't you post Vdub plugin "Refocus" link here in this thread?!

[rfmmars]

@rfmmars
Why don't you post Vdub plugin "Refocus" link here in this thread?!

Can not find it anymore. Search for "The 79 Jam" or a mix of that.

Richard

[Didée]

Possibly this one?

http://forums.virtualdub.org/index.php?act=ST&f=7&t=168&hl=refocus&st=75

[rfmmars]

Possibly this one?

http://forums.virtualdub.org/index.php?act=ST&f=7&t=168&hl=refocus&st=75

Yes that is the one the VDub is based on but I have had no luck finding for you the Vdub plugin. Here's another free "Deconvolution" program with docs.

http://bigwww.epfl.ch/demo/deconvolution3D/index.html

Richard

[SealTooGreat]

Hey, Didée why have you removed second image from http://forum.doom9.org/showthread.php?p=851781#post851781 You achive very good sharpen result. What have you meant by "sharp TSR with Avisynth"?!Is some kind of deconvolution behind that?When will you release this filter on doom9?And thanx for the link
@rfmmars....Have you tried this 3D Deconvolution filter?

[vcmohan]

FQSharpen is a type of deconvolution. See thread (http://forum.doom9.org/showthread.php?t=120496)

[*.mp4 guy]

You can get pseudo deconvolution by using masking to identify "sharp" areas and sharpening only areas that are not "sharp", obviously this doesn't work aswell as real deconvolution, but it is close enough most of the time.

IE
Function example(clip clp, int "maskradius", int "sharpradius", bool "showmask", string "threshold", string "bias")
{
maskradius = default(maskradius, 2)
sharpradius = default(sharpradius, maskradius)
showmask = default(showmask, false)
threshold = default(threshold, "128")
bias = default(bias, "0")

s = clp
Ablur = s.averageblur(maskradius)
gblur = s.gaussianblur(vary=maskradius, varc=0)
mask1 = yv12lutxy(Ablur, Gblur, "y x - abs "+threshold+" * "+bias+" +", "x", "x", U=3, V=3)
detail = s.unsharp(vary=sharpradius, varc=sharpradius, strength=1)

maskedmerge(detail, s, mask1)
showmask ? mask1 : last

return(last)
}

[Didée]

By the way:

sharpen(x)

already is deconvolution. Possibly the dumbest one, sure, but it IS. :)

(IYAM, there's a bit too much Voodoo-fication about the term "deconvolution".)

[*.mp4 guy]

Well, I think what people are really talking about here is intelligent deconvolution that can operate without knowing exactly what was done to the source image...

[SealTooGreat]

Well, I think what people are really talking about here is intelligent deconvolution that can operate without knowing exactly what was done to the source image...
Yea...You are right - blind deconvolution.
@Didée....What about my previous post?!Could I get an answer?!

[Didée]

Yea...You are right - blind deconvolution.

Yo man, thats da thing we need! Some1 pleeze pleeze c0de da bl00di thing!


Okay, let's assume "discrete" de-convolution (the blurryfilter, eh sorry, the convolution operator , is known), and "blind" deconvolution (nothing is known).


Discrete deconvolution is tricky enough:

- One problem is that the source (usually) is digital, thus the result of the initial convolution is lossy (rounding errors). Precision that has been lost is hard to recover.

- One more problem is that, in mathematical sense, the projection done by the initial convolution is not necessarily bijective: two different sets of pixel combinations might give the same result through the given convolution. If so, the projection is not reversable. Trying nonetheless, either artefacts will arise (aggressive implementation), or the deconvolution will be ineffective (safe implementation).

- One more problem are zero points: A pixel set of 1-9-1-9-1-9-1, convolved by gauss(r=1), results in 5-5-5-5-5-5-5. Anyone wanting to de-convolve a flat area?


Seriously, if the source has undergone only (the equivalent of) a primitive "blur(1)", and hasn't undergone any other than that (i.e. compression), then a real (perfect) de-convolution already is close to impossible. (And if an "approximated" de-convolution is good enough, then (the equivalent of) a slightly modified "sharpen(1)" is not a bad start: no need for Voodoo.

Moreover, one probably never has a "clean" version of the convolved source. As mentioned earlier in this thread, usually your convolved source has undergone at least one more modification: lossy video compression, or other forms of signal degradation during transmission ... and since deconvolution is a difficile task, it will turn the small pebbles of error into Mount Everests of artefacts.


So, the "baby's case" of de-convolution is already highly problematic. Really want to talk about "blind" deconvolution now?


To only slightly touch some points:

"Blind" deconvolution will try to de-convolve a formerly done convolution which is unknown. ONE convolution that is unknown.

But then, all those implementations of "blind" deconvolutions I've come across, in a sense are just a joke: the claim is the algorithms will "find" the appropriate convolution "on their own". But to do so, they come along with a set of dozens and dozens of different parameters, which you have to set up correctly for the source in question, in order to get a reasonable result instead of abstract art. Funny, isn't it. I'd say that the need to explicitely do a precise manual set-up of lengthy parameter sets is nothing else than ... telling the algorithm which convolution originally has been applied. At least it's pretty close to that. Viewing from that angle, all those "blind" deconvolvers are a fake, because their "blindness" is not at all "blind": They need tight guidance.
(And it's particularily funny if you have a minutes-per-frame algorithm, and have to try out lots and lots of different combinations of dozens of different parameters ... perhaps that's why the "showcases" [see below] usually are limited to only one single picture?) ;)

And it gets worse. Note that we're still talking about a single initial convolution that should be reversed ...

But in practice, the source usually is a wild mixture of a multitude of blurring and sharpening operations (during editing, bandwidth reduction for transmission, etc.pp.), noise, compression artefacts, whatnotelse.
All of this, without further arguing, leads blind deconvolution even more ad absurdum.

Sure, I know that there are some specific showcases where blind deconvolution delivers "unbelievable" results. I've seen them like you have (e.g.this (http://math.nist.gov/mcsd/highlights/blinddeconvolution.html)). But that's what they are: showcases. Not more, not less. Usability is a totally different thing.


From the practical side:

Especially for video applications, blind deconvolution is a task being so overly complex and complicated that it's just not usable. Perhaps by the time they get the quantum computer working, but not before that.

Still, if one withdraws from all the marketing hype and realizes what is realistic and what not, then the realistic possibilities aren't too bad, either. (Especially if they finish the task in a reasonable amount of time.)
Some sort of traditional "whacky";) sharpening, combined with motion search and temporal filtering, seems a reasonable way to go.

For example, and answering SealTooGreat's question of post#31 :

That "sharp TSR" thingy was basically an extended SeeSaw, combined with the framework of a motion-compensated denoiser, and a couple of additional twists and pull-ups. The script was fiddled together - from scratch - in about an hour or two. (I'm not even sure if I have it yet, could be the avs file has been overwritten at some time.)
Definetly nothing that's ready for usage, but it showed enough potential to make me confident that something usable can evolve from it.

Holding-your-breath is mistimed, too ... I ultimately have to carry out some very timeconsuming reallife-tasks during 1st half of this year. There are no toys to expect from me in that time. (Perhaps some ranting every now & then, but that's about it.) 2nd half I'll need to catch up again.

[fenomeno83]

Where can i find sharp tsr?thanks

[Didée]

Where can i find sharp tsr?thanks
On my HDD, and nowhere else. :)

Be assured that I'm experienced enough to judge whether-or-not it makes sense to publish something.

Cross-example: Now, people are amazed about MCBob (except for the speed;)).
Before MCBob, one or two proof-of-concept implementations of the method were made. Only one buddy member ever had seen them. It were those POCs that "showed enough potential to make me confident that something usable can evolve from it", i.e. they proofed me that the method once will work out.
But I never ever could've released one of them, because actually they were about the worst deinterlacers you could imagine.

"Ready for usage" is when I say it is. Not sooner, not later.

[Fizick]

Didée,
If you will be absent about half-year,
your sharp TSR may become a little outdated. ;)
BTW, what is MCBob you talk about here?
:)

[SealTooGreat]

Didée is Voodoo killer!:scared:
#37 :goodpost:
Is it possible to give us some kind of sharp TSR "preview"?!:D ...half-year is too long.

[Merlin7777]

@Fizik
You can see the MCBob.avs on his website repository.
Here: http://home.arcor.de/dhanselmann/_stuff/

[jmac698]

There is a blindpp which works, and a free demo. It's a pain to do anything with it (I had to process 3 planes in b/w, then recompose), but it does work. Even easier to just screencap the PSF (Point Spread Function) it finds, then use some other program to reconstruct.

www.quarktet.com/Tria.html