Smart resize filter (continued from rududu thread)

[MfA]

yeah, a (avisynth/directshow) resizer with this might be cool, but without any sourcecode or at least a paper that discribes it,...

Well he described very briefly how it worked on this thread (http://www.interpolatethis.com/phpBB2/viewtopic.php?t=107) (interesting board, but the discussion seems to have died down). It is based on NEDI, or in other words ... it is going to be very slow.

There are a couple of methods which could run in realtime I would try out if I wasnt so lazy.

This one (http://www.compuphase.com/graphic/scale2.htm) is one of the simplest. Although for the horizontal/vertical interpolation I would try 75:25 averages instead of the 50:50 averages he used, the center pixel is closer to the new higher resolution pixels than the neighbour pixels after all.

This one (http://ipl.univ.trieste.it/ipl/publications/icip96-sergio.ps.gz). Although it will need a reciprocal calculation per pixel, which limits the potential for SIMD ... still should be plenty fast for real-time.

Also more robust forms of ELA (edge based line averag) like SangNom are good candidates for real-time resizing.

[TheXung]

wow. there's actually a forum devoted entirely to resizing images. I'm just amazed. wow.

[bond]

moved to avisynth forum

[mf]

Originally posted by TheXung
wow. there's actually a forum devoted entirely to resizing images. I'm just amazed. wow.
Same amazement here. I'm going to have to post my SSXS filter (http://mf.onthanet.com/supersampled_xsharpen) there :D. Crappy as it is, choice should always be available :).

[morsa]

Well, my scale2X is the implementation of the first link, and nobody seams to take care of it...
BTW nobody ever mentions Avery's edge directed resampler which is exactly the implementation of Xing Li algorithm (EDI or NEDI don't know)

[MfA]

Oh I thought your filter was still based on the scale2x algorithm used in emulators.

As for Avery's filter ... dunno if he ever improved it, but default NEDI is unstable and prone to artifacts as you can see on Alexy Lukin's page. Of course it isnt very suited for realtime upsizing, which is the most interesting.

[morsa]

But it would be great to have Avery's filter ported to YV12 cause It hasn't distracting artifacts and could be used for the same task as Sangnom but with much better image quality at a reasonable speed and an open source code wich Sangnom will never has.

About my filter it is still something between nearest neighborhood (it maintains its sharpness)and may be bicubic...
I'm still looking for a way to have a better matrix to get better diagonals but can't find one, i'm planning to test a 5x5 to see what happens but I lack time these days..

[justin]

/me doesn't know if this is the same but for playback, FFDShow has a warpsharp filter

[tritical]

Well, I saw this thread and thought I might as well toss out some ideas I have been having and toying with.

First, I actually implemented an adaptive type of NEDI (a variation that uses the condition number of the CtC matrix to incrementally increase the window size from 4x4 up to 16x16, and at worst falls back to the base type of interpolation, such as bilinear, bicubic, lanczos3, lanczos4, or whatever...) as an AviSynth filter working only in YV12. The result was a filter whose output looked good, but ran way too slow for video processing (about 1 fps when going from 720x480 up to 1440x960 on a 2.2 Ghz p4)... though this was also because I coded it in about the slowest way imaginable (didn't try to make use of redundant calculations or anything in the way of optimization, this was mainly a filter for testing purposes).

For those that don't know the main problem of NEDI is that it can produce wild results around very sharp edges and in very detailed areas for small window sizes, due mainly to ill conditioned CtC matrices. This problem goes away as the window size is increased, but larger windows cause both blurring and LARGE increases in processing time. After testing out a lot of combinations I think the only workable NEDI based resizing algorithm that would run with any acceptable type of speed for video processing (on today's computers) and avoid nasty artifacts is one that uses a constant 8x8 window size on luma only (for YV12 or YUY2 colorspaces), but also defaults back to bicubic (or lanczos) if either 1. - the condition number of the current CtC matrix is too large, 2. - the calculated pixel value is outside of a + or - 4 (or some other reasonable value) max or min range of its four surrounding neighbor pixels, or 3 - the local variance is below a given threshold (to avoid using NEDI in areas that aren't edges, this is talked about in the original NEDI paper). These extra constraints eliminate about 99.9% of the unwanted artifacts, and that last one helps to speed up the algorithm greatly.

Second, I also implemented the first algorithm MfA linked to at the beginning of the thread. While it was definately fast, I did not have very good results with it. I also tried quite a few variations on it as well, but without much luck. The main problem is it can only adapt to 4 real types of edges (45% slant right, 45% slant left, horizontal, or vertical) and its sampling window to detect the direction of edges is too small. Anyways, I definitely preferred a bicubic, lanczos3, or lanczos4 resize to it. Although, I might have just been implementing the algorithm wrong, but I don't think so (hopefully).

Well, that’s enough of my rambling. First post though ;) Weird that I've been reading these boards for about 2 years, just never got around to registering and replying...

P.S. If anyone wants to take a look at the source code for the filter I talked about above, or play around with it (to try out the slowest AviSynth filter ever coded) I can make it available.

[mf]

Tritical, you've never heard of me, have you? :rolleyes:
FYI: To my filters, 1fps is fast. :D

[morsa]

It would be nice if you could let us try it and see if it is of any use to some of us (people who aren't too worried about 1 fps processings):)
BTW, you said it!! The problem with my Scale2X is that it manages right only 45 degrees diagonals, and that was my problem.Thank you.
apart from this problem, I've found it really useful to improve the stair steps left by deinterlacers.

Also remember we've got really mad code optimizers here at the forum (shodan, kurosu, are you there........?)

[tritical]

Here it is... and when I said 1 fps I was definitely over exaggerating ;)

EDIUpsizerv091.zip (http://www.missouri.edu/~kes25c/EDIUpsizer.zip)
FastEDIUpsizerv090.zip (http://www.missouri.edu/~kes25c/FastEDIUpsizer.zip)

Anyways, this filter is really more for testing purposes then for actual use. It supports using adaptive or fixed window sizes (4x4 up to 16x16), using condition number testing, using the min/max neighborhood pixel testing, enabling or disabling NEDI on the chroma planes, and quite a few fall back interpolation options. It could also be sped up by a large amount with just a few small changes to the current algorithm. I coded it in a way that made adding all those features easy, but sacrificed all speed... For example, it currently resizes the entire frame once using the fall back interpolation option and then replaces pixels calculated using NEDI. This made it so I didn't have to handle fall back and edge conditions. It also completely recalculates the entire CtC matrix for every pixel, and regathers all the values for the two matrices for every pixel.

Btw, I'm still planning to implement a filter based off the ideas I previously mentioned, and to concentrate a little more on the speed side of things, i.e. not resizing every frame twice ;), reducing the redundant calculations for the CtC matrix such as Avery's edgeresample filter does, etc... I think it could run at a more then acceptable speed. Only problem is that it is the week before spring break here and free time is hard to come by...

[morsa]

Congratulations!!!!!
Its quality is outstanding, I've tested Lanczos4 with NEDI and I could call it the best upsizer ever.
It is really slow although, as you said.Avery´s faster but yours has better quality to the naked eye.
Just for curiosity, I'be been reading a lot about using LUTs for speeding up image processing, Do you think it is aplicable to EDIUpsizer?
In many cases I´ve read, LUTs give higher speeds than SIMD optimization with the same quality.

[MfA]

The dimensionality is too great for a LUT, but you could use a (tree-) VQ classifier to get the interpolation weights ... training is hard though (how do you make sure it generalizes well?).

[tritical]

Like Mfa said, the number of possible combinations and interpolation weights is far too big for a LUT to be useable... Using an 8x8 window size the uniqueness would come down to the neighbor matrix of the MxM window pixels. That would be 64x4 = 256 pixels, however only 100 of those would be unique. So, 255^100 = roughly 4.5x10^240 combinations, give or take a few billion :D. As, for the VQ Classifier suggestion I'm afraid I don't have the knowledge needed to comment on it. I know what the VQ stands for and that's about it.

[MfA]

A VQ is really just a sparse LUT, so you can use it to approximate any function ... with each entry in the VQ you associate the appropriate function output.

[sh0dan]

Originally posted by tritical
Here it is... and when I said 1 fps I was definitely over exaggerating ;)

Looks great!

You can use the builtin resize functions. That will give you a fair speedup. It's fairly simple, add:
PClip internal_resized;

As member of your function, you can then use:
const char* upsizerString;

if (lstrcmpi(upsizer, "bilinear") == 0)
upsizerString="BilinearResize";
else if (lstrcmpi(upsizer, "bicubic") == 0)
upsizerString="BicubicResize";
else if (lstrcmpi(upsizer, "lanczos") == 0)
upsizerString="LanczosResize";
else if (lstrcmpi(upsizer, "point") == 0)
upsizerString="PointResize";
else
env->ThrowError("EDIResizer: Upsizer must be either \"Point\", \"Bilinear\", \"Bicubic\" or \"Lanczos\"");

AVSValue up_args[3] = { child, vi.width, vi.height };
internal_resized = env->Invoke(upsizerString, AVSValue(up_args,3)).AsClip();
... in your constructor.

Then you can get a resized frame by using:
PVideoFrame resized = internal_resized.GetFrame(n, env);.. in you own GetFrame.

As for the bicubic coefficients, they can be changed by changing the invokation parameters.

I could add Lanczos4 to the core, if some of you see any improvement over Lanczos3.

Btw, Welcome! You have definately earned the:
:helpful:
Award!

[morsa]

Well I would like having the option of Lanczos4 into Avisynth.It won't hurt and someone may find the exact case where to use it.Maybe Me...
@shodan BTW: Couldn't you port Avery's edge directed to Avisynth?
I've tried but it is too much for my limited knowledge.

[sh0dan]

Originally posted by morsa
Well I would like having the option of Lanczos4 into Avisynth.It won't hurt and someone may find the exact case where to use it.Maybe Me...
I have added it. Look out for the next CVS binary. Differences to Lanczos3 are however _very_ small.


@shodan BTW: Couldn't you port Avery's edge directed to Avisynth?
I've tried but it is too much for my limited knowledge.
No. Sorry. :rolleyes:

[mf]

It's easy to port to AVISynth :D. I'll do it this afternoon ;). But remember, it'll be slow as hell :D.

[mf]

Okay, it was easy to script, but as my user title says, AVS "dislikes" my scripts :D.

function EDIResize(clip c, int width, int height) {

LoadVirtualdubPlugin(VirtualDub_plugin_directory+"\edgeresample.vdf", "_VD_EdgeResample")

Try {
c.GreyScale().ConvertToRGB()._VD_EdgeResample()
((width >= c.width*2) || (height >= c.height*2)) \
? _VD_EdgeResample().ConvertToYV12() : ConvertToYV12()
y = last
c.UToY().ConvertToRGB()._VD_EdgeResample()
((width >= c.width*2) || (height >= c.height*2)) \
? _VD_EdgeResample().ConvertToYV12() : ConvertToYV12()
u = last
c.VToY().ConvertToRGB()._VD_EdgeResample()
((width >= c.width*2) || (height >= c.height*2)) \
? _VD_EdgeResample().ConvertToYV12() : ConvertToYV12()
v = last
YToUV(u, v, y)
yuv = last
}

Catch(err_msg) {
c.ConvertToRGB()
((width >= c.width*2) || (height >= c.height*2)) \
? _VD_EdgeResample()._VD_EdgeResample() : _VD_EdgeResample()
rgb = last
}

c.IsYUV() ? yuv : rgb
semifinal = last

semifinal.LanczosResize(width, height)

}

Gives an unrecognized exception on the LanczosResize. Without the conditionals, it gives an "Unsupported VBitmap method: RectFill".
I'd say, happy debugging :D.

[tritical]

Well, I've been busy lately, but did manage to get around to making a slimed down version of EDIUpsizer that is quite a bit faster. It's called FastEDIUpsizer. It uses a constant 8x8 window size, only uses NEDI on the luma plane, and always uses bicubic interpolation for fallback. I haven't gotten around to speeding up the matrix calculations, but it doesn't resize the entire frame twice anymore ;) and the minimum local variance rejection is significantly faster then before (a silly logic mistake in EDIUpsizer made the fast rejection much slower then it should be). I'm very interested in what some other people think about its quality and speed. It can still be sped up a good bit.. but I'm not sure whether its quality is that much better then other (faster) resizers that it would actually be worth it. The key edges in an image are definitely smoother, but it sometimes actually makes other things look worse.

Anyways, I added a link to FastEDIUpsizer below the link to EDIUpsizer in my earlier post... didn't want to start scattering links all over the place.

One thing I did notice about Avery's edgeresample filter that makes its so much faster is that for the minimum local variance it uses a value that is 16 times higher then what is recommended in the original paper (or maybe I'm using a value that is 16 times lower). Anyways, I decided to make the value configurable, it defaults to 8 which is the value I've been using, set it to 128 to get the value used in edgeresample... it will speed things up a good bit since more pixels will default back to bicubic.

@shodan: I had originally planned to use AviSynth's internal resizers, but the problem is that the NEDI algorithm calls for pixels from the original image (x,y) to be copied to (x*2,y*2) on the final image. Then the lattices are interpolated from those pixels. This results in a 1/2 pixel shift up and 1/2 shift left. Avisynth's resizers, correctly, keep the image centered on resize... so it wouldn't work out. Although the difference probably wouldn't be that big. And yeah, there isn't much difference between Lanczos3 and Lanczos4, but an extra option can't hurt I guess... especially since your fast and already added it :)

[SoonUDie]

The new version kicks much ass. Thanks for the great filter.

One thing I would suggest: raise the default mvar value. As it is, it ends up processing a lot of edges that it shouldn't (same goes for the old version; I have an illustration that kills both EDI and fastEDI on default settings). 16 seems to work well, processing the most visible edges, but I haven't tested extensively, and I assume it differs from picture to picture.

Also, there are still some NEDI-type artifacts left over after processing. The best way I've found to get rid of them (and "enchance edges") without modifying the code is to use a convolution with a matrix that looks like this:


0 0 0 -1 0
-1 1 1 1 0
0 1 6 1 0
0 1 1 1 -1
0 -1 0 0 0


I developed this many months ago, and it works great for reducing noise while keeping edges sharp and filling small gaps. However, Avisynth doesn't seem to deal with it properly - I get much better results using paint shop pro.

Unfortunately, this is also a 5x5 filter, which I try to stay away from...

[pieter1976]

Originally posted by MfA
The dimensionality is too great for a LUT, but you could use a (tree-) VQ classifier to get the interpolation weights ... training is hard though (how do you make sure it generalizes well?).

I have done interpolation by using a LUT and it gives some interesting result. I use a normal image of a girl to fill the LUT. This means that not all combinations are stored. The LUT is filled with 3x3 pixels(low detail) and 2x2 pixels(high detail).A find best match algorithm is used to do the interpolation. The resulting image has more detail. Unfortunely some noise is added because the find best match Algorithm doesn't always find a good match.

[SoonUDie]

Originally posted by pieter1976
I have done interpolation by using a LUT and it gives some interesting result.Hmm, sounds *very* interesting! I would love to see this, if it was compatible with either Avisynth or Virtualdub.

Also, how many entries can you have in a LUT before it noticeably slows down? I'd assume we can't store all 3x3 or even 2x2 matrices, as there are 10,891,649,009,473,375 r-combinations and 172,061,505 r-combinations (unique possibile tables), respectively. That's assuming that you can apply a routine to account for rotation before doing the lookup... if you can't, the number of values is ~ 300,000 times larger and 24 times larger, respectively.

Am I right in assuming a combination of all of the possible unique 2x2 tables at 7-bit accuracy (128 values per pixel) would take up ~35.6 megs [(9 entries * (7/8) bytes per pixel * 172,061,505)/(1024*1024)]? And 6-bit (64 values per pixel) would take up about 2.1 megs?

Also, is there a reason why you use a hybrid 3x3 and 2x2 approach? I don't know anything about LUT processing, but I would intuitively assume that you could simply average the results of 4 2x2 look-ups per pixel.

Another interesting idea would be to use a window-based technique where you dynamically create a LUT for a certain portion of a frame, processing it in blocks (take the average of every 9 pixel group; could be done via a quick (1,1,1)x(1,1,1) convolution; would be equivalent to resizing to 1/3rd the size, so your LUT is valid locally for a 3x resize, or assuming a nyquist restriction (which I really don't know anything about) a 1.5x resize). This approach should be able to handle most of the pixel values per block with reasonable accuracy. Block size of course depends on how big you want your LUT to be... 32x32x8bit would only be something like 4kbtyes [(32*32*4*1bpp)/1024] for a 4-entry table, and 9kbytes for a 9-entry table... 144k for 128x128x8bpp 9 entries...

[pieter1976]

I take a 3x3 matrix and calculate te average.
The average is subtracted from the pixels.
The value are made logarithmic.
The result is about 4 bit a pixel.

Now i make a database with 3x3 pixel combinations which are found the most times in a collection of images.

About 100000 combinatios would be enough for good results i think

[pieter1976]

I can send you a small delphi program to show you the results.
I only have a noisy version but you can see that it works.

[SoonUDie]

Hmm, that's an interesting way to do things. Do you go into negative numbers or drop values below the average?

I would be interested in seeing this in action - do you have anywhere to host it? If you don't (and don't want to use something like geocities), then I can host it for a while, if you like.

[pieter1976]

yes the values get below zero.

I use a factor to multiply the 3x3 value to find a good match

I wil put the program on my site so you can download it.

[pieter1976]

findbestmatch3x3.exe (http://home.zonnet.nl/pieterboots/findBestmatch3X3.exe)

[pieter1976]

The result of the program are a not so good.

But now I have found a way to improve it.
I ran the program 10 times and I use a different LUT every time.
This gives 10 noisy images but when I take the average of the 10 noisy images I get a good image.

I can't produce 1 frame per sec. It's closer to 1 frame per half hour but there are lots of possibilities to speed it up.








Hope I can be an inspiration to others

[SoonUDie]

@pieter1976
Your program produces some really interesting and encouraging results, though it seems to crash / not work properly with an LUT with over 1000 entries.

[pieter1976]

I have put some more time in it and this is the result

Smartresize (http://home.zonnet.nl/pieterboots/Project1.exe)

It is still a bit noisy around straight edges.

[morsa]

Wouldn't it be better to open the code and let others work on it?
I guess a couple of people here could be really helpful, even the scriptting-people.Just my opinion.
I really like its results and I understand it is more a proof of concept than a usefull filter at this moment.

[pieter1976]

Yes that would be better but I think it is a bit soon to give the code away. But first I will try to make it preform a bit better before I will post the code somewhere.

The difference with the previous version is that this version uses edge direction detection. The Lut is filled with pixels of the image that is going to be interpolated.

[pieter1976]

here are some images

Before

http://home.zonnet.nl/pieterboots/pic160x120.gif

Interpolated

http://home.zonnet.nl/pieterboots/pic320x240.gif

[SoonUDie]

Not bad! It looks like it has a lot of potential, and it's definately sharper than something like a Lanczos resize.

[morsa]

A-M-A-Z-I-N-G !!!!:D
Still a bit blocky, don´t know its speed but it could become one of the best resizers ever, keep going on please.I´ve been waiting for something like this many years...

[Didée]

Just to give an alternate view: same picture, quickly thrown at iiP (to finish my office's day).

http://img7.imageshack.us/img7/130/pic_160x120-iiP-640x480.png

I know it's comparing apples with oranges ... but it's not all too bad, however. ;)

- Didée

[pieter1976]

I have combined my algorithm with that of the SAR image processor.

http://home.zonnet.nl/pieterboots/SAR_and_Findbestmatch.gif

[SoonUDie]

Wow, that really seems to solve most of your problems! But I bet it's slow as hell now :rolleyes:

[pieter1976]

It takes maybe 5 seconds to complete a 160x120 image. This doesn't make it a good candidate for realtime processing but my algorithm isn't optimized at the moment. This means that still there is a lot of room for speed increase.

[Longinus]

I have used SAR Image Processor for some time now... and one of the things I really like about it is the Isophote Smoothing. It can be VERY usufull to smooth jagged lines... I use it betweem a supersample operation... Than resize down with lanczos..

I have no idea as how it works... but using it as a postprocessing in some resize filter would be really good..

Check the result of a strong isophote smoothing in a very bad Evangelion picture I got from mf's site..

http://unkind.no-ip.org:666/doom9/smooth1.png
Before..

http://unkind.no-ip.org:666/doom9/smooth2.png
After...

It does have some blurring effect that some people may not like... But some sharpen would take care of it, and besides I found the effect rather nice on animes... And yes, it's slowwwww.. =D

[pieter1976]

I have read some interesting things about curvelets and contourlets. They are very usefull for removing noise.

Do a search on google and you wil find some good documents.

Here is one of them:Beyond wavelets (http://www.ifp.uiuc.edu/~minhdo/talks/ECE_GradSem.pdf)

I think it can be used for resizing to.

[Soulhunter]

Originally posted by Longinus
Check the result of a strong isophote smoothing in a very bad Evangelion picture I got from mf's site...
Looks a bit like Photoshops anisotropic luma interpolation !!!


Sample:

http://img12.imageshack.us/img12/9048/smooth6.png

[MfA]

Little less impressive, the blocking in the air is still there ... and yet it still manages to be blurrier overall.

[AS]

sangnom at default

http://img20.imageshack.us/img20/9290/sangnom0.png

My workaround for some of the artifacts of sangnom

http://img14.imageshack.us/img14/4268/sangnomfix.png

These are without any extra filtering like smooth nor deblock, I think these are better. :p

Less destructive and leaving more room for you can fix up the rest of the image with other tools

Now that I look at it, it has better edges too.

[Longinus]

Where can I get sangnom?
Mark FD posted a link, but it's dead now..

[tritical]

As smoothed by TIsophote(iterations=5,tStep=0.5,type=0)

http://www.missouri.edu/~kes25c/tisophoteT0.PNG

As smoothed by TIsophote(iterations=5,tStep=0.5,type=2)

http://www.missouri.edu/~kes25c/tisophoteT2.PNG

Obviously not as impressive as some of the above results, though it's not that bad considering the filter only does pure and simple unconstrained level-set (isophote) smoothing w/o any type of pre/intermediate/post processing. It is also pretty fast for less intensive smoothing (fewer iterations) then what this image needs, though even 5 iterations is not all that slow. Yep, you guessed it, another useless filter brought to you by tritical :D.

TIsophotev0.9.1 (http://www.missouri.edu/~kes25c/TIsophotev091.zip)

[Wilbert]

Where can I get sangnom?
Mark FD posted a link, but it's dead now..

Third post of this thread:

http://atlas2.tgv.net/~media-video/forum2/viewtopic.php?t=3655&start=30

without source of course :(