Smooth in time and space?

[vlad59]

Originally posted by bb
@vlad59:
I would like to test the Convolution3D with standard and full-1 matrix at the same time; this way it's easier to compare.
BTW: What do you say about the possibility of optimizing the algorithm for a full-1 matrix (in fact you wouldn't need a matrix at all in this special case)?

bb

I don't fully understand, what I'll do is to provide a new Convolution wich has a new parameter to choose between the two matrix.
I hope that's what you want ;)

Optimizing for the full 1 matrix is not easy, let's take an example :

Tresholded matrix are :
10 11 11 13 15 5 10 11 11
10 11 11 13 15 5 10 11 11
10 11 11 13 15 5 10 11 11

To find my new convoluted values I've to add all the matrix values :
Sum = 10 + 11 + 11 + 13 + 15 + 5 + .........

And then divide by the numbers of matrix value i.e. 9+9+9 = 27

new values = sum / 27

That division is the problem :
- I have no MMX opcode to perform a division (or I missed something)
- and a simple division will be way too slow.

That's why I first tried having a weight matrix like that :
1 1 1 1 1 1 1 1 1
1 2 1 2 2 2 1 2 1
1 1 1 1 1 1 1 1 1

With this I can use a left shift to divide by 32
But with this the compressibility test is worse than with the standard matrix


So if anybody has an idea .... :rolleyes:
I have got no time to think about it this weekend, thursday is off in France so you can expect a release in 2 or 3 days max.

[dividee]

If you don't have division... use multiplication.
Basic Idea:
If you accumulate the sums in words in an MMX register, load an MMX register with four times 65536/27. The usual way in C code would be to multiply by that value and then >> 16. In MMX code, you can use PMULHW (or PMULHUW in ISSE) so you don't even have to do the shift.

Take care of rounding (if you don't want Acaila to complaint about a green tint ;)):
in C code you could do:
(sum * 65536/27 + 32768) >> 16
but that doesn't work with PMULHW (3DNow has a nice PMULHRW, though).
The technique I used in MMX code can be described in C code as:
((sum<<1) + sum) * 32768/27) >> 16

It becomes more difficult to do the "divisions" in parallel if the divisor can vary for each word.
In TemporalSoften(2), I had independent divisors for each word that can vary from 1 to 16, so I constructed a big lookup table with 16^4 QWORD entries. I packed four divisors in a WORD to use as an index in the table an so was able to do 4 "divisions" in parallel.

[vlad59]

@dividee

That's what I call a clear explaination, thanks a lot.

I'll have a look to TemporalSoften code to be sure I have understood.

thanks again, I'm now obliged to optimize better Convolution3D ;) ;) ;)

[bb]

@vlad59:
Just another idea: what about using a 2x2x2 or a 4x4x2 matrix?

bb

[vlad59]

@bb

In theory it's possible but with those matrix you have not a center pixel. I think it's annoying.
I thought about a 5x5x5 matrix, but it will be slower and I first want to have a stable Convolution3d before changing too much the basis.
But if you explain me better what could be cool with this, I can change my mind. You usually have great ideas ;) .

I also thought of not using the previous and next frame when there is too much difference between prev, current and next pixel (only luma will be checked). I should help a lot in fade in or fade out scene.

[trbarry]

Vlad -

As a small point on performance issues you can usually expand the matrix horizontally faster than vertically. That's because the data will be coming from the same cache lines. So something like a 3x5 will probably be faster than a 4x4 by more than you might expect.

- Tom

[bb]

@trbarry:
You are probably the master of filter optimisation. What do think about my proposal of interleaving the frames before filtering, then de-interleave again? Like you store 1st line of 1st frame, then 1st line of 2nd frame, then 1st line of 3rd frame, then 2nd line of 1st frame, etc., like
1111111111111111 (first line)
2222222222222222 (first line)
3333333333333333 (first line)
1111111111111111 (second line)
2222222222222222 (second line)
3333333333333333 (second line)
...

This way the pixels you have to touch during filtering would be close together in memory, which - I think - would improve cache hits.

Non-cubic matrices will have an impact on the picture, as far as I can see. You could get the effect that it smoothes more horizontally than vertically. I also thought about dropping the edge pixels, because they have the biggest distance to the center pixel. The perfect 3D matrix would probably be a sphere, not a cube... What do you think?

@vlad59:
You're right, not having a center pixel is annoying, I thought of that problem. I had the idea of something like a running total; the value of a pixel would be updated more than once while the algorithm is "passing by". I still have to think that over, but I can post my idea if you find it useful.

There's a VirtualDub filter using a 5x5x2 matrix, but I was a little disappointed with that one...

bb

[trbarry]

bb -

Dunno, you'd have to try it. But in order to do this you would have to copy the data 2 extra times and I'm not sure whether that would make up for the (hopefully) better arrangement. And the gain would be processor dependent since the different machines have different cache sizes and stuff.

- Tom

[dividee]

Why 2 extra times ? Or do you count read & write as 2 times ?
TemporalSoften (and TemporalSmoother) use a similar idea as bb exposed (I didn't invent it, that's the technique Avery used in Temporal Smoother for Virtualdub), except these filters interleave the clips on a per pixel basis instead of per line.
So you have ,with bb's notation (center = frame 2)
123123123...

Since these filters only operate on the temporal axis, it makes the inner loop works totally linearly. As long as the clip is read in sequential order, all you have to do for the next frame is replace the oldest pixels by the newest ones:
423423423 (for frame 3)
and then
453453453 (for frame 4)
The pixel replacement is also done in the inner loop.

The arithmetic of using such a circular buffer is sometimes a bit complicated (especially when you try to add full-scene change detection in the mix ;) ), but I think it's worth it.

[trbarry]

Maybe I didn't think it through well enough. I was thinking that if you wanted to work with the data in a different format that you would also have to copy/reformat the results back at some point, but that's not necessarily true I guess.

But again, I guess you would have to try it and see if what you gain makes up for the up-front overhead.

When I wrote Greedy/HM (DScaler GreedyHMA version) I reformated the data into what I thought was a clever arrangement that got around some then-current DScaler limitations but in hind sight I'm not sure it was worth it. And I'm almost certain that if I went to the work of pulling out that stuff for the Avisynth version it would go faster. But maybe I just did something silly when I designed the data structure I used.

I guess the way I think about it now is that it is not as important to keep everything close together in memory as it is to minimize the number of cache lines that have to be repeatedly filled on each pass through the filter. So if you hit say, 6 or 8 cache lines (of 32, 64, or 128 bytes each), but then move 8 bytes to the right and it is still the same 6 or 8 cache lines, then you sort of get it for free. But when you move to the next line of the screen then it is probably going to be a different cache line or at least a different (slower) level of memory cache.

There, I have thoroughly confused myself. What did I just say? ;)

- Tom

[vlad59]

@dividee
you've made a typo when you explain me how to divide :
instead of :
((sum<<1) + sum) * 32768/27) >> 16
you should have written :
((sum<<1) + 1) * 32768/27) >> 16

I just coded it, it works without any problem, thanks again.

@all
Tomorrow you'll have the new matrix (full 1).

[dividee]

Indeed I made a typo, but your correction is also wrong; it should be
((sum<<1)+27)*(32768/27))>>16 (or: ((sum+(27/2))*(65536/27))>>16 )
which is equivalent to the previously given
(sum * 65536/27 + 32768) >> 16

[Koepi]

walk like an egyptian... ;)

[vlad59]

@dividee

Of course you're right dividee, I really regret all the time I spent sleeping instead of listening to my Maths teacher.
Sorry to be such a pain in .... :( :( :(

@Koepi
I love the way you walk ;)

@all

thanks to dividee, you can now download the new version of convolution3D (beta 1) with sources (not commented at all :rolleyes: , I'll make that in 2 days).

You now have the full 1 weight matrix. The compressibility is better with this matrix.

No more speed for now, but I'll need a day or 2 to understand the discussion between Tom and Dividee ;)

EDIT : Removed old attachment

[Koepi]

vlad:

wanna walk that way as well?

then we could change to RunDMC feat. airosmith(?) - walk this way... and nod our heads like will smith. ;)

Maybe that helps understanding all those formulars.

I'm glad that I finally found out that there's a simple shift operator in c/++ - guess what I had to code around that in the xcdbackupcreator :-/

Dancing,

Koepi

NP: Velvet Acid Christ - Alien Surfaces

[baz00ie]

Thanks for your work, Vlad59.
I've noticed an increase in quality and speed with the latest release.

take care
baz

[vlad59]

@baz00ie

First, thanks for testing and using my filter.
Increase in speed ??, I've done nothing yesterday to speed up Convolution3D :confused: . I'll make benchs tonight.

[vlad59]

Here is the beta 2 of Convolution3D.

The main changes are the new temporal tresholds (thanks Tom for the idea) that will allow to have better compressibility and less ghosting.

This version shouldn't be faster than the beta 1.

I change some part of the internal engine, so if you see some difference, post here.

thanks in advance for testing.

I made some tests :
On my torture test (an old noisy anime badly mastered) :
Convolution3d (1, 12, 20, 8, 8, 0)
and
TemporalSmoother (4)
have roughly the same compressibility test (51.8 for C3D and 50.8 for TS)
but TemporalSmoother produce some ghosting and handle very badly fade in scene (C3D was also bad but somehow better than TS, Tom's STMedianFilter was the best for this scene).
On still scene TS is way better but lose some details.

I'll make new tests with MAM tomorrow.

[trbarry]

Vlad -

I just took a peek at your code. Looks like you've done a pretty good job optimizing in MMX. :)

I even learned something new from it. I hadn't realized the pinsrw and pextrw instructions could use general purpose register operands. Cool.

- Tom

[vlad59]

Originally posted by trbarry
Vlad -

I just took a peek at your code. Looks like you've done a pretty good job optimizing in MMX. :)

I even learned something new from it. I hadn't realized the pinsrw and pextrw instructions could use general purpose register operands. Cool.

- Tom

Thanks Tom, I read a lot of code (from you and dividee mainly) to understand better asm and learn new tips. I think I learned something :D . But I'm still not satisfied with my code, there is still a lot to do :o (especially to comment more).

Yep I used pinsrw and pextrw to compute each luma value individually, it cost a lot of time, and I still don't know if it really usefull.

[wotef]

after doing some tests on some pretty tough analogue VHS transfers, i just want to echo wilbert and koepi's comments - as dr evil would say, convolution3d is frikkin' excellent! i think it should go up on doom9's filters download page as soon as appropriate

[bb]

@vlad59:
Just a silly question: When you calculate the 3D convolution, do you always process the new values from the original frames? Or do you use the already averaged pixels, e.g. when referring to the previous frame (which would be a bad idea IMO)?

At a first glance the new filter (beta 2) gives great results on my test material (I don't have much time this weekend, sorry).

IMO the filter should get some speed improvement before "giving it to the public" at doom9's downloads.

bb

[vlad59]

@bb

I'm a little tired (done too much tests last night), so maybe I won't answer to your question. In convolution3d, nothing is buffered now so for each pixel of each frame everything is calculated.
And with avisynth, the frames I get are always unprocessed by my filter, so I always deal with original frames.

Speed improvements !!!
That's the problem, adding buffering can improve speed but I'm afraid it will be hard to make it faster than TemporalSmoother:( :(

[Marc FD]

Hi :)
I'm back ....
MAM and MAD (and copysame too) would not be continued...
so MAM v0.6 spe3 was the last version...
...until the Mpack implementation works :)

[Guest]

You guys keep talking about a 3D convolution in YUV space. That will be just dandy for luma. But because chroma is subsampled by 2, you cannot formally implement a 3x3 operation on it. So I have to ask: how are you implementing a 3x3 blur of chroma? I suspect you are causing chroma to leak outside the 3x3 area.

[vlad59]

@neuron2

In fact I implement the 3*3 operation on each plane Y, U and V. In my Readme.txt I perhaps talk about pixel it's just to simplify the reading.
In my Convolution3D I deinterleave YUY2 to simply work with coherent (don't know if it's an english word) data. I used the 3*3 blur on each plane and reinterleave in YUY2.

That also explain the speed of my filter ;) :( ;) :(

Hope I've been clear enought

EDIT : Oooops just get it, You're right Donald, I use a 3*3 matrix for luma, but for chroma I use 5*3 pixel so 3*3 chroma values.
You're right.

[Guest]

@vlad59

Well, sure, it had to be. But actually you have 6x3 pixels.

But it is really, really bad! If you iterate this thing, you start spreading chroma horizontally way past where it should be relative to the luma adjustments.

This is a serious problem that I have not yet solved (for 3x3).

Apparently only kernels that are even-sized in the horizontal dimension can be implemented correctly. One could do 4x3 for example.

That would make your filter even slower. :(

[Guest]

But then there is no center pixel. Oh, woe is me. Is there no solution?

[Koepi]

Ok, I know you don't see me as knowledgeable in this place, but did you try to use your 3x3 matrix, and for chroma... now it comes:

luma:
111
111
111

chroma:
xy11z
x11yz
xy11z

x, y and z get interpolated to respond to the "borders" given by luma.
You'd have a biased center, but it's somehow a center.

I don't know if this explains what I mean, but I hope the idea is visible: luma information should be different if chroma information is... at lest you won't "leak" wrong colors too much.

It's still far from perfect, but at least a try.

I hope this doesn't look as stupid as I see it now, it doesn't really fully explain what I try to say.

Best regards,
Koepi

[Guest]

@koepi

>Ok, I know you don't see me as knowledgeable in this place

Heavens, whatever gave you that idea? You must have misinterpreted something I said.

I don't understand your idea. Maybe you could make it clearer?

As I see it, any kind of interpolation is going to leak, and any kind of off center is going to make asymmetric output. Both of these look really awful after iterating many times.

The problem is only serious/observable after iterating, so it looks like my only solution is to just adopt a larger kernel to start with. This is for my new smoother. The downside is that I then have to muck around with boundary fill to find the pixels to blur. But it's probably better not to iterate anyway.

[Koepi]

Hum, knew it... it's really not easy to explain...

well, we _want_ to interpolate a 3x3 matrix. with luma, this can be done without big hassles.
In chroma, we have the problem that just 1 or 2 (depending on the yuv space) pixels are stored within such a matrix.

so if we have

luma:
111
111
111

and chroma:
1x1
xxx
1x1

or

1x1
1x1
1x1

(1 means, information stored, x means - thin air)

we should use something that "toggles" the center to be more "right centered" in the first step, and more "right centered" in the next.

So we have sometimes a little more weight on the color information from the left, and then again from the right.

so if we have to use something like a 5x3 matrix for chroma anyways, we should "move" the center around. This way, we would be closer to the original. It's like dithering, I'd say.

And about the luma respecting thing: if there is a huge jump in luma (or, if it's above <threshold>), it should mean that something different is starting there, so the interpolation has to be "cut off" at that place. SO if we have

(2 means "above threshold"

luma:

111
122
222

then the chroma should be calculated like this:

111yx
11xxx
xxxxx

(x now means: something deriving form the right, y means: possibly interpolated between the neighbour pixels - if too slow to use internally 4:4:4 yuv, or not noticable, just use 1 again)

I don't know if this is realistic.

I hope this is clarifying my idea - it's more or less that luma should make an "early stop" possible in calculating our convolution "chroma" matrix.

Best regards,
Koepi

[Guest]

Sorry, I still don't understand. Never mind; I'm a plodder when it comes to thinking.

For example, you start by saying "we _want_ to interpolate a 3x3 matrix". But that is not what I want to do, so right away I'm lost.

[dividee]

This chroma problem is what discouraged me of writing spatial filters in YUY2...

@Koepi: I must be dumb or something but I still don't grasp what you explained...

I have another idea:
Let's assume we would convert to YUV 4:4:4 before filtering. The chroma in YUY2 is supposed to be located on the left pixel of the pair. I can see two "easy" ways of doing that conversion.
a) duplicate chroma:
YUY2 : A B C
YUV 4:4:4 : A [A] B [B] C [C]

A,B,C represents chroma pixels; [] represents information that is not present in YUY2.
Applying a [1 1 1] horizontal matrix at position B would yield : (A+2B)/3; so it's equivalent to filtering in YUY2 (as vlad is doing now) with a matrix [1 2 0].
For the [1 2 1] matrix it gives (A+3B)/4 or a [1 3 0] matrix in YUY2.

b) interpolate chroma:
YUY2 : A B C
YUV 4:4:4 : A [(A+B)/2] B [(B+C)/2] C [(C+D)/2]

Same calculations as above:
[1 1 1] to pixel B gives (A+4B+C)/6 or [1 4 1]
[1 2 1] becomes [1 6 1]

I don't know if one method is better, but i like more method b). It still doesn't avoid some chroma bleeding, but reduce it by giving more weight to the center pixel (but it also reduce filter strength on chroma, of course).

I wonder how Sh0dan dealed with this in SmoothHiQ...

[Guest]

sh0dan did not have to iterate his kernel, I believe. No bleeding or asymmetry at all is acceptable if you want to iterate it a lot, because it magnifies the defects.

I've concluded the problem is insoluble and I can't do iteration. I am writing a configurable sized kernel instead. Even that is hard.

[Guest]

@dividee

Isn't it the conversion back to 4:2:2 that will cause the dilemma? In other words after converting back we will still have an asymmetric result with bleeding.

[Marc FD]

Hey, it exactly the problem i'm having with Blur/Soften MMX YUY2 optimisation.

My MMX version is very good (and damn fast, it's MMXed after all)
but when i come to massive iteration (x20/x40 !!) i get some artifacts in YUY2 because i used a bigger kernel in chroma :(
But because it's so fast in MMX, it's really dumb to be not able to use some iteration.

When i think of it, Sharpen(1,1) x 20 will give you _VERY_ ugly artifacts, so my little deviation in chroma is not very noticable...

I'll release a bin of Focus2 soon, and if you think it's good, i'll send my source to a avs coder with CVS acces.

[vlad59]

I'll have a second look to Tom's STMedianFilter to see how he handle this case.

I think that Convolution3D can keep it's actual way of averaging chroma.
But if I intend to make a multipass filter : I think I'll filter chroma only verticaly with a 2 pixel *3 pixel matrix (so 2 chroma value * 3). And I'll keep the same method for luma (3*3).
Optionaly I'll add a horizontal chroma averaging that will only be performed last to avoid leak.

[Defiler]

Vlad: If you want, I can host Convolution3D and the readme on some of my webspace. That would make it easier to link from the "Avisynth Q&A" thread.

[vlad59]

@Defiler

I agree, I'll be happy if you could host Convolution3d. As I already said I'm allergic to HTML stuff.

Thanks a lot.

Just PM me if you need something to do that.

[Defiler]

OK. It's up.
http://hellninjacommando.com/con3d/
Not a marvel of design, but simple and permanent.
Feel free to link to it in any imaginable way.

[vlad59]

@Defiler

Bravo (as we say in France)
I love the design (simple, easy to read, effective).

Just two little remarks :

- I'm not sure I'm talented ;) , If one day I'm able to optimize Convolution3D to gain 50% in speed, I'll accept this compliment ;) .
But I'll have to wait a long time for that moment :rolleyes: .

- I think it's important to credit bb who has the original idea. bb was the inventor and I only was the coder.

Thanks again Defiler, You've made a good work :D

Edit : I love your signature, I remember where Tom wrote that, in the Dvd2avi Sourceforge Project thread (a long one too).

[Defiler]

Thanks.
Do you have any contact info for bb? Should I just say something about "bb" having the original concept/design, or can I link to his homepage, etc?

[vlad59]

Nope no contact info for bb, just credit him for the concept and for the tests (look at the first page of this looooooong thread, I only arrived at the second or third page).

I'm sure if he want a special link, he'll ask it later ;) ;) .

Thanks

Ps : it's time to begin to think about the beta 3 (or maybe v1.0), let's code a little.

[Bulletproof]

Could somebody port convolution3d or STMedian to Virtualdub with a preview button so that we could tweak easier?

[bb]

@vlad59:
Thank you for the flowers. I would have tried to code it myself, if I only had the time... But unfortunately my time is very limited, therefore the project wouldn't ever have been realized. Thank you very much for picking up the idea; in my opinion the coding is at least as important as the concept.

Concerning the link to my homepage: I prefer to stay anonymous, and there is no homepage for my bb identity (yet). Do you think I should set up a page with a cute description of the 3D convolution (I mean with pictures, abstract algoritm explanation and such)?

If you want to give me some credits, just mention bb (the mod of doom9's DV forum).

If you want to contact me, you can simply send a PM. My e-mail address is bb_doom9<AT>gmx.de (replace the <AT> with an @ ;-)). For certain conversation I prefer using PGP.

bb

[Marc FD]

Originally posted by Bulletproof
Could somebody port convolution3d or STMedian to Virtualdub with a preview button so that we could tweak easier?

??? do you realize the colorspace conversions problems ???
it seems to me that porting a avisynth filter to VirtualDub is really dumb.

a combinaison of a animate() and FreezeFrame() can help you to tweak settings, and is (in my point of view) far more powerfull than a dumb preview box... but of course it's a little harder to use the first time ;)

[Koepi]

I just edit my avs script, hit ALT, hit "cursor down" twice, hit enter, use ALT+TAB (brings my vdub to front), hitting ALT again, 1x cursor down, 5x cursor up, enter - and then watch through the video via slider again... easiest way to tweak the settings, and you get used to it very fast, too ;)

Regards,
Koepi

[bb]

Although this is getting off-topic now:
Don't you think AviSynth support in VirtualDub would be nice? Like an AviSynth menu where you can select filters, preview the filter chain, edit the AVS script, etc.

What do you think?

bb

[Belgabor]

Even a 'reload' function would suffice, where you would end up on the same frame as before.

Belgabor

[Marc FD]

a coder (like me or koepi) could create a little prog who reloads your avisynth script in VDub when you hit a key-combo.

i played with keyboard simulation to make my PSX Pad work on my computer and to play emulated SNES/NEOGEO games with some month ago.

some threading and simple API calls. i can try to use the concept to do a little notepad-virtualdub compatible reload function.