New very slow FFT denoiser

[Fizick]

I make experimental very slow FFT denoiser. :)
FFT3DFilter - 3D Frequency Domain filter-denoiser

FFT3DFilter uses Fast Fourier Transform method for frequency selecting an removing.

The algorithm is based on the 3D IIR/3D Frequency Domain Filter from:
MOTION PICTURE RESTORATION. by Anil Christopher Kokaram. Ph.D. Thesis. May 1993.
http://www.mee.tcd.ie/~ack/papers/a4ackphd.ps.gz



It is a spatial-temporal (3D) filter, and works as follows:

1) get 3 frames (previous, current, and next);
2) divide every frame to small overlapped blocks;
3) get frequency spectrum by windowed forward 3D FFT transform of every block of 3 frames;
4) reduce weak frequencies (with small power spectral density) by optimal Wiener filter with some given noise value;
5) make inverse 3D FFT transform of cleaned spectrum for every block;
6) do windowed summation of cleaned overlapped blocks to output frame.

Features:
1. Works only in YV12 color format.
2. Directly works with progressive clips. For interlaced sources, probably you must use SeparateFields etc.
3. Tested with Avisynth 2.55.
4. Uses fast external FFTW library version 3 (http://www.fftw.org)
as Windows binary DLL (compiled with gcc under MinGW by Alessio Massaro),
which support for threads and have AMD K7 (3dNow!) support in addition to SSE/SSE2.
It may be downloaded from ftp://ftp.fftw.org/pub/fftw/fftw3win32mingw.zip
You MUST put FFTW3.DLL file from this package to some directory in path (for example, C:\WINNT).
Filter will NOT work without it!
5. It is slooow! :(

EDIT: New versions are not so slow now ;) and have some other features and restrictions. See updated doc included with filter!
I do not want to change this first post by historical reasons :)

[Soulhunter]

Sounds nice, but for some reason I cant download it... :(


Bye

[Fizick]

link fixed

[Soulhunter]

Question...

Smaller blocks should give better results, no ???


Bye

[Mug Funky]

blocks are overlapped, so in theory there shouldn't be much difference?

small blocks might give less spatial smearing (what's the image equivalent of pre-echo?).

i gotta try this filter now :)

[edit]

on large values of sigma, on bw=bh=16, i get a strange screen pattern. increasing the blocksize to something large fixes it.

interesting filter. it removes a lot of the subtle crap in a picture. also seems to stabilize edges somewhat. too large values of sigma cause ringing, of course.

[Soulhunter]

Originally posted by Mug Funky

On large values of sigma, on bw=bh=16, i get a strange screen pattern...


Looks it like a grate/grid or so ???

Guess I got the same effect...


Bye

[SirCanealot]

I was going to try, but the link seems to be down again :(
Is it just me?

[hampel]

Can you please post the link to the filter plugin and to the 3dFFT dll again? The current FTP address requires a password authentification :-/

The principle sounds good to me, at least in music restoration FFT filtering is the only proper way to do the job - and the same method should give superior results, although finding the right FFT filter parameters is mostly a painstakingly time-consuming job, and the results of a slight overprocessing are received as "very artificial" by the human eye, so conservative settings are a must.

Bernard (having done a lot of FFT filtering on "pictures" of particle physics detectors, but with hardware DSP solutions of the first generation in 1994)

[708145]

Originally posted by Soulhunter
Question...
Smaller blocks should give better results, no ???


WIMNI, larger blocks give higher precision to the fft, thus better decision about what is unneccessary.

bis besser,
Tobias

[Soulhunter]

Originally posted by 708145

WIMNI, larger blocks give higher precision to the fft, thus better decision about what is unnecessary.

Interesting, thanks for the info... :)


Bye

[oledoe]

I've been looking for a filter to get the best possible results on a very noisy CATV signal, with lots of noise in the Y channel.
This is by far the best one I have found.
Thanks!

[morsa]

Yes, it is real good, I tried it on a noisy DV source and I made miracles.Removed all the noise keeping perfect quality.
YOU DID IT AGAIN, FIZICK!!!!!!!

[Mug Funky]

WIMNI, larger blocks give higher precision to the fft, thus better decision about what is unneccessary.

actually, it's a trade-off between spatial (transient in audio) accuracy and frequency accuracy. this is why (good) audio codecs based on frequency transforms will have 2 or more block-lengths. short blocks for sharp transients (where time is more important than freq, like percussion, applause, impulses) and long blocks (where freq is more important than time, like highly tonal instruments, etc).

in images, at least with this filter, larger blocks give more severe ringing. seeing as human eyes are less discerning than ears as far as frequency goes, i'd say it's safe to use smaller blocks and keep the edges happy :)

[Soulhunter]

Would a variable block-size improve this filter ???


Bye

[708145]

Thanks for your explanation Mug Funky.

What about correlating the results of smaller and larger blocks? If, like in audio, there are only so many things happening at the same time (per block) then use small blocks to determine where and correlate with the result of larger blocks to get more exact frequencies.

Is the above nonsense?

bis besser,
Tobias

[krieger2005]

Does someone noticed, that the border on the right and at the bottom where not proceeded by the filter, when the last block (in the image) is smaller that the block needed by the filter... I use then Addborders(0,0,X,X).FFT...().crop(0,0,-X,-X)

[Mug Funky]

@ tobias:

i'm not sure how useful that would be, but then Fizick is the programmer, not me :)

i've also noticed that larger blocks require smaller values of sigma. i guess this makes sense, as the larger the FFT, the lower the energy of each measured frequency.

i've been playing with 64x64, and that seems to be giving nice results.

using varying block sizes sounds interesting though - it could be used to allow higher denoising but protect the edges. but i think if we're going that far, we should be using a wavelet-based denoiser like Vague.

i'm liking the results this filter gives. definitely worth the wait :)

@ krieger2005:

cool. i'll try that, as i just noticed the problem :) i suppose a small wrapper function could be made that adds borders to pad the input clip out to the nearest mod(blocksize) number, then crop after.

[Fizick]

I release version 0.2
Add BETA parameter to low ringing

beta - noise margin (float?1.0, default=1.0 for no noise left)
control noise amount left in the restoration, max filter noise attenuation = (beta-1)/beta

(see Kokaram doc for detail).


I also know about border feature ;)

[DarkFoon]

I was wondering what you guys would think if this filter had control over the temporal filtering. So that it could be user defined,
for example:
temp=<value>
where <value> could be,
-n, where it only processes previous N number of frames (and current)
0, temporal off
n, where it does previous and future N number of frames. i.e if N = 2, then it would do 2 previous frames and 2 future frames, greatly slowing it all down, of course.

I like the filter, but the reason I suggest this is because my experiences with big or small values of sigma and bh/bw, I get horrible ghosting on my anime images (they're rather grainy CATV captures from live broadcast). Perhaps this filter is bad for anime? I know that temporal is a strong point of this filter, however, there are situations where temporal filtering can be undesireable.

I also thought that if there was a parameter to make the filter run all three planes (or a combination thereof) with only one filter instance in the script. I think this would be good because the user could, for example, turn off temporal and turn on all three planes and there would be no gain/loss in filter speed; it would still be processing three planes, but all within the same frame, as opposed to the current way things are.

let me know what you guys think of all this.
By the way, I like the idea of dynamic block sizing. The arguments for dynamic block sizing are compelling.

[morsa]

My experience has been fantastic using this filter!!!
Complete noise removal with a lot of subtle details preversed at the same time!!

I use it with its default values, just changing sigma on color planes. (red higher than Y and blue higher than red..)
after it I just add a little temporal and ready..

[DarkFoon]

@morsa
what kind of sourse do you use these settings on?
analog capture? DV capture? DVD? VHS? Broadcast?
Also, what sigma values do you actually use?

[Leo 69]

Actually I'd be very grateful to some guys here who'd post some good settings for this filter.For example "light denoising" "heavy denoising" etc. And "High Quality Standard denoising" would be great!:D

Сheers

[Fizick]

So, people want 2D :)

Got it!

Version 0.3, 21 December 2004 - added block temporal size parameter bt (was fixed =3 internally).

bt - block temporal size, number of frames (1, 2, or 3, default = 3):

1 - only current frame (spatial 2D filter - fastest);
2 - previous and current frame;
3 - previous, current and next frame (slowest)


IMHO, for big noise we must use big sigma, and more large block 32x32 to prevent grid artifactes.

Probably for 2D block 32x32 is better too.

[morsa]

for More oe less noisy DV I use plane 0 sigma=2, plane 1 sigma=3 ,plane 2 sigma =4.
I don't remember the block size right now but I guess it was 16....

[krieger2005]

great filter, ass always... and you are right: it's very slow.

To prevent "bluring" of edges with high sigma-values one can use "FineEdges"-Function from "Didée" i guess. Here my try:
function CleanUp(clip c, int "eEnd", int "eStart", int "bw", int "bh", float "sigma", int "sharp", bool "mask"){c

eEnd=default(eEnd,8)
Flaechen" markiert
eStart=default(eStart,68)
bw=default(bw,32)
bh=default(bh,32)
sigma=default(sigma,3.0)
sharp=default(sharp,180)
mask=default(mask,false)

ed=c.FineEdge(16)
SurfaceMask=ed.Levels(eEnd,1,eStart,255,0,false)
ret=mask ? MaskedMerge(c,c.BlankClip(pixel_type="YV12", color=$66FF66),SurfaceMask,Y=3,U=3,V=3,useMMX=true) : NOP()
cleanSurface=c.AddBorders(0,0,bw+20,bh+20).FFT3DFilter(bw=bw, bh=bh, sigma=sigma).crop(0,0,-(bw+20),-(bh+20)).xsharpen(sharp)

ret= (!mask) ? MaskedMerge(c,cleanSurface,SurfaceMask,Y=3,U=3,V=3,useMMX=true) : ret

return ret
}

great job.

[DarkFoon]

@Fizick
How does the "previous frame" part of the filter work?
does it take the unprocessed previous frame, and then process it, or does it take the processed previous frame and process it again?
Hmm, an example would be good, that doesn't seem to make sense...

For example:
The filter is set "bt=2".
I randomly access frame 10. The filter processes frame 9, and frame 10 in the FFT, and then gives the filtered output frame 10.
Then I move over to frame 11. When the filter processes frame 11, it also processes frame 10, but does it take filtered output frame 10, or does it take the original frame 10?

Gosh, I hope that makes sense. Anybody else know what I'm saying?

[State of Mind]

Ok, I also have a noisy DV source, what are the commands to use this plugin? I am VERY eager to see how well this denoises my DV.

[State of Mind]

???

[Fizick]

DarkFoon,
current versions has no memory, and procesed (spatially) all frames at every time step. It is not optimal, but easy coded. My filter is still experimental. I had some think about optimizing, and may be another temporal algo (Kalman) for 2D frequency "frames", but not rigth now. Sorry.
But (IMHO) the speed factor will not =2 for bt=2. Overlapped frame is large.

State of Mind,
do you have your own eyes? Try!

[DarkFoon]

@State of Mind
I tested this filter on my noisy DV capture and *angelic choir* it worked a miracle!!!
It would appear that the Y channel (plane=0, in the filter) is the noisiest. You can turn the filtering on so that it processes the other channels, but you wont get as dramatic of an improvement as you would with just the luma (Y, or whatever) being filtered.

Supposing that your capture is still 720x480 when you run this filter:

FFT3dFilter(sigma=2.0, bt=3, plane=0, bh=48, bw=48, measure=false)

That is what I used on my capture. Experiment with filtering the other planes in addition to this one.

@Fizick
Does the filter need square block sizes? Or could I get away with, for example, bh=48, bw=90? [for this example, assume that the block sizes fit exactly into the video frame.]

[Fizick]

DarkFoon, do you see any limitation or constrain on block size in my filter "manual" :)
But some sizes will result in very slow procesing due to FFT method implementation.
See FFTW doc for more info.
48 and 90 is OK.

[DarkFoon]

where in the docs does it say what sizes might slow it down? Or what should I look for? Sorry, I'm not a programmer, so I am lost in those kinds of things.

[Fizick]

FFTW works most efficiently for arrays whose size can be factored into small primes (2, 3, 5, and 7), and otherwise it uses a slower general-purpose routine.

48 = 2*2*2*2*3 is OK
90 = 2*3*3*5 is OK

[DarkFoon]

Thanks!

Keep up the good work!
This filter has great potential, don't let it fall between the cracks.

[Leak]

Originally posted by Fizick
FFTW works most efficiently for arrays whose size can be factored into small primes (2, 3, 5, and 7), and otherwise it uses a slower general-purpose routine.

48 = 2*2*2*2*3 is OK
90 = 2*3*3*5 is OK

Shouldn't this info be in your filter's documentation, under "Performance considerations" or something like that?

(NB: I haven't tried your filter as I don't have sources that are noisy enough, so apologies if it's already in there... :))

np: Donnacha Costello - Dry Retch (Pop Ambient 2002)

[gst]

This filter is really powerfull. Maybe the best denoiser out there, and one of the slowest to.
I've got interesting results with this combination on a noisy dvd source :

DRemoveGrain(mode=2).DRemoveGrain(mode=2)
crop()
Lanczos4Resize()
Unfilter(-5,-5).FFT3DFilter(sigma=3,bh=32,bw=32).Unfilter(-5,-5).DRemoveGrain(mode=1)

I've also made a few test with the block size. You can see results here :
http://x.spirit.free.fr/FFT3D.zip (4.69Mo)

Block size tested :
8x8;16x16;32x32;64x64

Codec : xvid
Matrix : eqm_v3ulr_rev2
Bitrate: 1.050mb/s

32x32 give me the best quality, but there's no big difference between 16x, 32x and 64x. 8x is the worst value for my source.

Good job Fizick

[DarkFoon]

I usually work on anime, so my filter combination is much stronger than for video, for obvious reasons. But here it is, for those interested:

fft3dfilter(sigma=2.0, plane=0, bt=2, bh=48, bw=48, measure=false) #<- Y plane
fft3dfilter(sigma=3.0, plane=1, bt=2, bh=48, bw=48, measure=false) #<- U plane
fft3dfilter(sigma=4.0, plane=2, bt=2, bh=48, bw=48, measure=false) #<- V plane
msmooth(threshold=5, strength=3, mask=false)

Note: I use 48 because it is the largest number the divides into 720 and 480.

This is incredibly slow on my PIII, but it works excellently.
An explanation: the eye is most sensitive to luma, so that is filtered the least. But the difference between not filtering the luma and filtering it is quite visible; this can make or break the quality.
The reds (V plane, whatever you call it) are the most subsampled with my source (MPEG2 TV capture) so they can be filtered more powerfully.
Msmooth is to blend out the 'ghosting' that results (sometimes) from the temporal part of the filter. It's most noticeable when there are fast motions across large solid color areas.

To illustrate this, I have some pictures for comparison.

Original source frame (after IVTC, but no denoising):
http://www.freewebs.com/cassumnox/6343-original.png

Frame after FFT3D, but no Msmooth:
http://www.freewebs.com/cassumnox/6343-unsmoothed.png

Frame after FFT3D and Msmooth:
http://www.freewebs.com/cassumnox/6343-smoothed.png

The 'ghosting' I am talking about can be seen on the suitcase.

Note: compare the file sizes of the pictures too ;)

Sorry the host is so slow, my usual server is down. :'(

[Fizick]

...When the filter processes frame 11, it also processes frame 10, but does it take filtered output frame 10, or does it take the original frame 10? Gosh, I hope that makes sense. Anybody else know what I'm saying?

DarkFoon, seems now I understand your question :)

All normal temporal filters (fft3d too) always take only original frames on input, not prefiltered by previous steps.


Other comment: V plane is not quite "red". Ask Wilbert (or see his guide) for detail :)

[DarkFoon]

V is not red?
Crap! Curse the internet's wealth of misinformation!

[Wilbert]

V is the red minus the luma. Highering V will turn your clip to red and lowering it to green (you can check that with ColorYUV(off_v=x)).

btw, V and U are sampled "equally", so you can apply the same amount of filtering on them.

[DarkFoon]

I thought U and V were sampled differently.
Ex. -YUV 4:2:0 (YV12, MPEG1/2, etc.) The luma is fully sampled, because the eye notices luma differences the most, and thus it is least compressed. U is subsampled, and V is even more so.
-YUV 4:2:2 (YUY2) The luma is not subsampled (perhaps that is the wrong word?) The U and V are equal, and because of such, there is more data than YV12.
-YUV 4:1:1 (DV) I'm noticing a luma pattern here ;) The U and V are again equal, but smaller than YUY2.
-YUV 4:4:4 (???) fully sampled, lots of data.
I draw my data conclusions (which become the explanations for my understanding of this) by taking an AVS in said colorspace, and opening it in Vdub, and then looking at the bitrate in the information box.
YV12 is the smallest, RGB32 is the largest.
I think I may be right...
Unless I am totally misunderstanding the YUV numbers and such... ^_^;;

[Wilbert]

Ex. -YUV 4:2:0 (YV12, MPEG1/2, etc.) The luma is fully sampled, because the eye notices luma differences the most, and thus it is least compressed. U is subsampled, and V is even more so.
No. There's one UV sample per four (2x2) luma samples.

YUV 4:2:2 (YUY2)
One UV sample per two (horizontal) luma samples.

http://www.avisynth.org/Sampling

-YUV 4:1:1 (DV)
One UV smaple per four (horizontal) luma samples.

Yeah, the notation is a bit weird. I don't understand how you can read of the vertical subsampling. More info:

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dnwmt/html/YUVFormats.asp

[Poutnik]

YUV 4:2:0 : U and V are not sampled differently, but only one of them is coded in a TV line, alternating each other, i.e. one line U, one line V.

Y=+0.299 R + 0.587 G + 0.114 B
U=-0.1687 R - 0.3313 G + 0.5 B
V=+0.5 R - 0.4187 G -0.0813 B

[DarkFoon]

Thanks for clearing that up Wilbert and Poutnik!
I remember reading about all this a long time ago, I guess time has decayed my memory...

Y=+0.299 R + 0.587 G + 0.114 B
U=-0.1687 R - 0.3313 G + 0.5 B
V=+0.5 R - 0.4187 G -0.0813 B

Poutnik, what is this? The RGB-> YUV conversion table?

[Poutnik]

Yes, it is. It was related to Wilbert=s note:

"V is the red minus the luma. Highering V will turn your clip to red and lowering it to green (you can check that with ColorYUV(off_v=x))."

[DarkFoon]

Thanks again!
Now back to the topic:

@Fizick, is there a possibility of a speed increase in the near future with FFT3D? Or perhaps variable block size based upon some parameter M that defines the sensitivity to detail?
Tell us the ideas that you have for your filter. It seems the people here on the forum don't contribute ideas very often, so if you give it a jump-start with your ideas, then we all could comment and derive something, yadda, yadda, yadda...

[gst]

Or perhaps variable block size based upon some parameter M that defines the sensitivity to detail?

+1
I don't know what blocksize is the best for optimal quality, this M parameter would be a great idea.

[DarkFoon]

I have done some thinking about variable block size, and I think this 'parameter M' would be better suited to modifying the sigma value than the block size.
Changing block size (making it smaller) really doesn't affect the quality, it just makes the filter more ineffective. A large block size with a small sigma, in my opinion, is better than a smaller block size with a large sigma. And it would appear that the data is on my side: larger blocks remove more noise.
The 'parameter M' would be more useful as this:
a complexity calculator would be run over the block, if the block is a solid color with some noise (the complexity calculator would find this block to be very 'simple'), the sigma value would be raised, according to the value of 'parameter M'
Now, lets say the block is over an eye. The complexity calculator would find this block to be very complex, and would lower the sigma, so it wouldn't blur the delicate details.
A high 'parameter M' would mean that when the filter processes a complex block, it would blur it more, and ignore the fine details more. But a low 'parameter M' would mean that it would not blur complex details.
Ideally, the user could specify just the 'parameter M' and let the filter decide what is complex and what isnt. Or, the user could specify the 'parameter M' and sigma, and sigma would act as a bias to 'parameter M', such that, if sigma is low, then the sigma would not be raised very high even if the block is detected as 'simple'.
And if the sigma is high, then the sigma would be modified to be higher even if the block is detected as complex.

If this doesn't make sense (as I suspect it wont) please message here, and I'll try to explain it better. This is just my rough idea.

[Mug Funky]

the trick here is how to determine what's visually complex (ie, relating to human perception) rather than complex in frequency. with FFT the most complex you're going to get is white noise. in this case, i think FFT3d will probably pass about half of it through (i'm guessing here, as i can't be bothered generating test videos and running fft3dfilter on them), possibly regardless of the sigma value used.

my understanding is that if there's "spikes" in frequency plus a background that would approach pink or white noise, then sigma determines where to draw the line between the noise floor and the spike (which is assumed to be detail). of course, i too may be wrong.

anyhoo, it strikes me that it would be exceedingly difficult to determine from the FFT that you have a complex object like an eye in the spatial domain.

however, some kind of adaptive sigma is still a good idea. i wonder how it would work? rather like LAME's floating ATH is how i imagine it, where the noise floor is determined per-block, and the threshold (ATH in LAME, or sigma in FFT3dfilter) expresses a desired ratio rather than a constant. this would also mean that no matter the block size, sigma can be kept constant and perform the same (right now larger blocks mean more noise removal for the same value of sigma).

btw, this baby works REALLY well when you motion-compensate it :) i can't wait for MVtools to include overlapped-block motion compensation, so it doesn't throw off FFT3d's groove...

[DarkFoon]

I imagine the edge detector in Msmooth as the complexity calculator. I mean, what is (fine) detail? Edges! So, perhaps an edge detector could act as a good complexity calculator. Only problem is, it could pick up the noise as edges.. :/
I also remember seeing while using libAVcodec to encode MPEG2, an RC control algorithm called "texture complexity", perhaps there's a complexity calculator that could be taken from there?
I quote these because they are open source, and the source could be used in the filter, I guess.
Your ideas, Mug Funky, intrigue me. I can't say I like or dislike the idea of a ratio. It just... intrigues me. OH!
How I wish I could program so I could test all these things and see if they're any good!

By the way, what do you mean:
this baby works REALLY well when you motion-compensate it :) i can't wait for MVtools to include overlapped-block motion compensation, so it doesn't throw off FFT3d's groove...

How do you motion compensate this filter? Why do you do that? Explain... Tell me your knowledge!