Proposal: Median Upscaler

[pbristow]

Hi, it's me again with one of my daft little ideas that I don't seem to have the powers of concentration to code up for myself, and wonder if anyone else would be interested in tackling it.

The idea is for a fast "rough-n-ready" 2x upscaler. In theory it should be almost as fast a simple resizer (such as bicubic), but *slightly* more edge-aware / edge-directed. It's not supposed to be challenger to NNEDI3 in quality terms, of course, but simply to be an alternative to normal resizers that reduces the "stair" effect on diagonal and curved edges.

I suspect that the results of, say, running this median 2x upscaler on an image, and then reducing the output to 1.5x time the original size with a BicubicResize, would look noticably better than simply enlarging to 1.5x with Bicubic Resize alone.


Here's the procedure:



1. Copy all source pixels from a w x h frame to 2w x 2h frame, with empty spaces between them, thus:

S S S S
S S S S
S S S S => S S S S
S S S S
S S S S


2. Fill in all diagonal pixels by taking the median of their 4 diagonal neighbours:

S S S S
\ / \ / \ /
M M M
/ \ / \ / \
S S S S
\ / \ / \ /
M M M
/ \ / \ / \
S S S S


3. Now fill in all remaining blank pixels by, again, taking the median of the four existing neighbours:

S -> o <- S -> o <- S
v ^ v ^ v
o <- M -> o <- M -> o
^ v ^ v ^
S -> o <- S -> o <- S
v ^ v ^ v
o <- M -> o <- M -> o
^ v ^ v ^
S -> o <- S -> o <- S
v ^ v ^ v



... (I hope my clumsy ASCII art survives the posting process! =:o} )

Anyone interested in trying it?

[MysteryX]

This is so simple. I'd almost be tempted to use that as a C# sample with AvsNetFilter.

[jpsdr]

The idea is interesting. The issue is that a median filter is something very slow (i know, for having done such a filter in VDub), so, i don't know if finaly the speed benefit vs nnedi3 will be very great.

[wonkey_monkey]

This idea fails my sniff test because it allows for interpolated pixels to be determined solely by pixels whose average position is not the position of the interpolated pixel - i.e., a pixel's value could be decided solely by the upper right and upper left pixels, or by the lower left and upper left pixels. I don't think this is "right" from a mathematical point of view.

But if no-one's coded it up by later tonight, I'll give it a stab.

[pbristow]

Seems it is a sort of a bilinear resizer.

...Just a lot more "bi" than "linear". :D

[feisty2]

median is naïve
maybe bilateral if you want it to be edge-aware

[jpsdr]

There is no computation/interpolation of pixel value, only duplication, so it's closer to a "PointResize" method.

[pbristow]

The idea is interesting. The issue is that a median filter is something very slow (i know, for having done such a filter in VDub), so, i don't know if finaly the speed benefit vs nnedi3 will be very great.

Speed of calculating a median depends a lot on how many samples are being sorted, though. Just using 4 should be pretty quick, shouldn't it? NNEDI3 does multiple calculations on multiple pixels per output pixel: In terms of complexity, this would be a bit like adding a new, *very* tiny kernel to the NNEDI3 options, with simplifed calculation as well.

Anyway, for now they key thing is just to get a working demo and see what results the process gives on a variety of test images and clips. If it looks useful, then maybe we can scratch our collective heads about how to optimise it later. =:o}

[feisty2]

so, how about
x could be the blend of its neighbor samples
bending weights are determined by both the distance between each sample and the center pixel,
and the absolute error between each sample and the median value of the neighborhood of x

[MysteryX]

Already done, except the handling of borders for step 3.
Source code (https://github.com/mysteryx93/AvsFilterNet/blob/master/MedianUpscaler/MedianUpscaler.cs)

Is this the desired outcome?


ColorBarsHD(30, 20)
MedianUpscaler()
PointResize(Width*8, Height*8)


https://s4.postimg.org/6am9ggsk9/Median_Resize.png (https://postimg.org/image/6am9ggsk9/)

[pbristow]

median is naïve
maybe bilateral if you want it to be edge-aware

Yep, like me, it's very naive. But as naive approaches go, it's one that I haven't seen anyone try before or found any papers discussing, so I'm curious to see how it turns out. =:o}

[feisty2]

Yep, like me, it's very naive. But as naive approaches go, it's one that I haven't seen anyone try before or found any papers discussing, so I'm curious to see how it turns out. =:o}

you could even try pixel matching(aka. NLMeans) for an advanced upscaling algorithm:
blending weights are determined by the SAD between the neighborhood of the reference pixel and the neighborhood of the center pixel

[pbristow]

Is this the desired outcome?



Hmmm... Does odd things to horizontal and vertical lines, doesn't it? =:o\

Maybe we need to just use the median on the diagonals (stage 2), and something like bicubic at stage 3?

Let me have a play with it on some real video, and get back to y'awl. And thanks for indulging my curiosity on this one.
:thanks:

[pbristow]

Already done, except the handling of borders for step 3.
Source code (https://github.com/mysteryx93/AvsFilterNet/blob/master/MedianUpscaler/MedianUpscaler.cs)


Ah, just realised you didn't include the plugin.
[EMBARASSED SHUFFLE]

[FLUTTERS EYELASHES APPEALINGLY]

I don't actually have a development environment, you see. I've tried twice before to set one up on this machine, and hit snafus both times. A long time ago I was compiling Avisynth plugins OK on a laptop, but that died. =:o{

Maybe, with Win10 on this box, and with (I gather) a wider choice of compilers than we used to have for doing AViSynth stuff, it's time I tried again...

[MysteryX]

You can get Visual Studio 2015 Community Edition for free which allows coding both C++ and C#

Then you can play with the code

[pbristow]

https://s4.postimg.org/6am9ggsk9/Median_Resize.png (https://postimg.org/image/6am9ggsk9/)


I'm studying that image, and I can't figure why we're seeing those incorrect shades/colours on alternate pixels either side of the horizontal and vertical lines. Consider the case of a black zone next to a white one:

Step two should create a column of mid-grey pixels (which it does).

Step three should
(1) fill the rest of that column with identical grey pixels, greating a solid grey line (this is working correctly), and
(2) fill in the blank spaces either side with either solid black (on the edge of the black zone) or solid white (on the edge of the white zone).

OK, I've never tried C# before, but at first sight that source code looks remarkably lean and simple compared to what I've seen for even the most basic plugins in C. .. Which C# compiler / IDE do you recommend I try? =:o}

Thanks again, MysteryX!

[pbristow]

You can get Visual Studio 2015 Community Edition for free which allows coding both C++ and C#

Then you can play with the code

Ah, you beat me to the question. =:o}

It was a previous version of Visual Studio that refused to behave on this machine before, and ended up leaving me with a choice of either a non-function installation or a never-completely successfully uninstallation; plus two failed updates permanently stuck in my queue, either way. Maybe, being a different version, this one will just by-pass any left behind crud from the earlier one and "just work, dammit"...?

I'll have to give it a try, but I think that's an experiment for some time next week, when I've got a couple of free days ahead to sort out whatever mess I create. =:o?

[MysteryX]

OK, I've never tried C# before, but at first sight that source code looks remarkably lean and simple compared to what I've seen for even the most basic plugins in C.
How else would I get it done in less than 2 hours?

[jpsdr]

Stupid question : What is the color format of the test picture ? RGB, YV24, something else ?

[feisty2]

Better resizer should find edges and reconstruct them. It is not a simple solution.

since resampling and blurring/denoising are both convolution, you can get a simple solution by analogy

blurring weighting on distance -> resizing weighting on distance(typical resizing algorithm)

bilateral denoising -> bilateral resizing, should be edge-aware just like how it works as a denoiser

NLMeans denoising -> pixel matching based resizing, the quality should excellent like NLMeans denoising

but I'm just too lazy to implement these analogies...
I really really dislike programming...

[TheFluff]

y'all haven't read http://virtualdub.org/blog/pivot/entry.php?id=86
y'need to do that, stat

[pbristow]

I really really dislike programming...

30 years ago, it was my favourite hobby. These days, it seems I just can't hold enough details straight in my head at once to work my way through a significant chunk of code (or solve a non-tricial installation problem) before needing a long lie down... =:o\

... Ah, don't be defeatist, old $SELF: Give C# a try. You know you want to. =}:o| Just need to get this marathon run of work shifts out of the way first... and this heat-wave...

[pbristow]

y'all haven't read http://virtualdub.org/blog/pivot/entry.php?id=86
y'need to do that, stat

I *have* read that, and I'm aware that the unvarnished version of what I've asked for violates rule 2 in particular. The point here is to get a basic proof/disproof of concept.

All of the "normal" resizers, with one exception have a problem: They're very influenced by the fact that we're dealing with a square grid of pixels. They have only 4-point rotational symmetry, not full circular symmetry, and this is why they tend leave significant stair-case effects on bold diagonals (and curves). The exception is the Gaussian resizer, which achieves theoretically perfect rotational symmetry, but at the cost of being very blurry, sacrificing a great deal of detail. But for upscaling, the *last* thing you want to do is sacrifice existing detail!

Now, what I'm trying to do here won't have full circular symmetry either, but the hope is that it will get a bit closer by addressing the construction of the diagonal missing points first, as top priority, then basing the vertical and horizontal ones off those. Indeed, it may actually produce the *opposite* kind of dependence on the square grid to standard resizers/resamplers. If that's the case, then polishing the output by running it through a standard resizer such as bicubic, set to give the same (or smaller) size, and correct the offset at the same time, might actually give the best of both worlds.

I dunno. All I wanna do is try it out and *see*.

[Groucho2004]

Ah, don't be defeatist, old $SELF: Give C# a try.
Please don't. The only way you can use C# for an Avisynth filter is to use a wrapper library like AVSFilterNet. This adds a useless abstraction layer with the usual performance issues.
Imagine you live in a foreign country and instead of learning the language, you use a phone with Google translate to communicate with people.
C# and .NET can be very useful in a professional environment where developers are under time pressure. For a hobby coder this hardly applies.

Use the native API (with either C or C++) to interface with Avisynth.

[MysteryX]

Stupid question : What is the color format of the test picture ? RGB, YV24, something else ?
YV24

Please don't. The only way you can use C# for an Avisynth filter is to use a wrapper library like AVSFilterNet. This adds a useless abstraction layer with the usual performance issues.
Imagine you live in a foreign country and instead of learning the language, you use a phone with Google translate to communicate with people.
Considering 99% of the CPU work is in the actual frame per-pixel processing, I don't think the overhead makes much of a difference at all, although it would have to be measured.

Also, for something experimental like this, we can give it a try and focus purely on the mathematics of it without bothering with all the C++ details before even knowing if it's worth it. As the sample shows, the proposed algorithm doesn't work, and we could see it quickly.

[vivan]

All of the "normal" resizers, with one exception have a problem:All 1D resizers, but we also have 2D (like Jinc aka EWA Lanczos).

[feisty2]

30 years ago, it was my favourite hobby. These days, it seems I just can't hold enough details straight in my head at once to work my way through a significant chunk of code (or solve a non-tricial installation problem) before needing a long lie down... =:o\

... Ah, don't be defeatist, old $SELF: Give C# a try. You know you want to. =}:o| Just need to get this marathon run of work shifts out of the way first... and this heat-wave...

not going C# and C++14 is definitely my type of programming language, it could be low level like C, unlimited and direct manipulation to RAM via raw pointers, it could also be high level like Python, you don't even have to care about type stuff anymore, auto and decltype make variables look almost "typeless" like some kind of dynamic language, you could even do some functional style programming with lambda expressions, and smart pointers give you automatic GC like Java or C#

it has the ability to do literally everything, I like it because it always offers me more than enough choices to do whatever I want and LIBERTY matters

I just don't like coding things because it requires a lot of work

[MysteryX]

I just don't like coding things because it requires a lot of work
What I coded just here didn't require much work at all, and that's one big plus, on top of increasing maintainability.

The C# code sample does use raw pointers. It requires the 'unsafe' keyword and works fine.

I do have to say, however, that everybody using the same standard language does have its advantages.

[feisty2]

What I coded just here didn't require much work at all, and that's one big plus, on top of increasing maintainability.

The C# code sample does use raw pointers. It requires the 'unsafe' keyword and works fine.

I do have to say, however, that everybody using the same standard language does have its advantages.

sure a median algorithm needs nothing more than "std::nth_element" in c++

and what I proposed there, bilateral and NLMeans are way more complicated than that..

edit:
and plus, I will try C# if you can make my C++ implementation (http://forum.doom9.org/showthread.php?p=1776182#post1776182)of SATD much simpler with C#

[MysteryX]

sure a median algorithm needs nothing more than "std::nth_element" in c++
std::nth_element is for sorting. Here we're not doing any sorting, we're adding 4 values and dividing by 4 to get the average.

and plus, I will try C# if you can make my C++ implementation (http://forum.doom9.org/showthread.php?p=1776182#post1776182)of SATD much simpler with C#
What is that code supposed to do?

AvsFilterNet doesn't work in VapourSynth to begin with; it would require a completely separate wrapper. Or perhaps it could be possible to provide a common .NET interface that works in both Avisynth and VapourSynth... maybe... I don't know enough of VapourSynth to know how feasible that would be technically.

I'm thinking that creating a wrapper class around the pointer could make it a lot easier to navigate and get pixels by their relative position, and that would make all the code a whole lot simpler, especially for complex code. (which could be done in C++ too)

[feisty2]

std::nth_element is for sorting. Here we're not doing any sorting, we're adding 4 values and dividing by 4 to get the average.
????
are you aware of the difference between Mean and Median?
that's elementary school math, dude

What is that code supposed to do?

SATD (https://en.wikipedia.org/wiki/Sum_of_absolute_transformed_differences)
Hadamard Transform
(https://en.wikipedia.org/wiki/Hadamard_transform)


AvsFilterNet doesn't work in VapourSynth to begin with; it would require a completely separate wrapper. Or perhaps it could be possible to provide a common .NET interface that works in both Avisynth and VapourSynth... maybe... I don't know enough of VapourSynth to know how feasible that would be technically.

I'm thinking that creating a wrapper class around the pointer could make it a lot easier to navigate and get pixels by their relative position, and that would make all the code a whole lot simpler, especially for complex code. (which could be done in C++ too)

that's not a filter, just an independent function that calculates the SATD between 2 macroblocks

[Nevilne]

Has anyone made cpu yv12 sXBR yet? I've only seen RGB and GPU variants afaik.

[wonkey_monkey]

There is no computation/interpolation of pixel value, only duplication, so it's closer to a "PointResize" method.

The median of a set with an even number of members is the average of the two "middle" members.

[MysteryX]

The median of a set with an even number of members is the average of the two "middle" members.
Oh. I think I'm calculating it wrong then. I was doing average.

So for median, when there are 4 values, I take the average of the 2 middle, when there are 3 values, I take the middle, and when there are 2 value, I take the average?

[captaiŋadamo]

Oh. I think I'm calculating it wrong then. I was doing average.



So for median, when there are 4 values, I take the average of the 2 middle, when there are 3 values, I take the middle, and when there are 2 value, I take the average?



Yes, that would be what a median is. Median is the "middle" value of a set that separates the upper and lower halves.

[MysteryX]

Oh my bad. Fixed the code to use median value instead of average. It does look better!!

https://s3.postimg.org/do8e12sbz/Median_Resize.png (https://postimg.org/image/do8e12sbz/)

Source code updated. (https://github.com/mysteryx93/AvsFilterNet/blob/master/MedianUpscaler/MedianUpscaler.cs)

sure a median algorithm needs nothing more than "std::nth_element" in c++
or List.Sort()

[feisty2]

Oh my bad. Fixed the code to use median value instead of average. It does look better!!

https://s3.postimg.org/do8e12sbz/Median_Resize.png (https://postimg.org/image/do8e12sbz/)

Source code updated. (https://github.com/mysteryx93/AvsFilterNet/blob/master/MedianUpscaler/MedianUpscaler.cs)


or List.Sort()

except nth_element is much faster than sort

edit:
did some googling and noticed that list in c# = vector in c++

[MysteryX]

My implementation isn't the fastest but it will tell us whether the method works. It can be optimized later.

As for your SATD algorithm, the only way you can simplify a complicated algorithm is by creating well-designed abstraction classes in an object-oriented way; and that can be done both in C++ or C#.

[MysteryX]

Performance-wise, the best C# solution would do the sorting and median calculation using System.Numerics.Vectors that translate into SIMD... if that supports the necessary operations, and if it generates SIMD for x86 (that's unclear). SIMD in .NET still a work in progress.

This is a good test to see how C# can do such tasks.

[wonkey_monkey]

MysteryX, what's your test script? I'd like to compare my results to yours.

[MysteryX]

I posted my script already; you can find it

[wonkey_monkey]

Yup, found it now :o

I get a largely similar result (but I used RGB24 and did some approximate gamma correction):

http://i.imgur.com/QXEqpCN.png

Edit: sudden realisation - with a such a plain test image this is going to basically be bilinear along all the edges. Only "corner" pixels will be any different.

[pbristow]

Edit: sudden realisation - with a such a plain test image this is going to basically be bilinear along all the edges. Only "corner" pixels will be any different.

Yeah, the whole point is to see what it does on *diagonal* lines and on curves. On verticals and horizontals, it is indeed just doing exactly what bilinear would.

Glad we got the mean/median confusion sorted out. Just a technical note to MysteryX: "Average" is an ambiguous term. Mean, median and mode are all averages, but they are calculated in different ways and give different results, and have different uses. RMS is another averaging technique, that's designed to pay more attention to high absolute values, and less to low ones (values closest to zero). Designing "custom" averaging techniques is one of my weirder niche hobbies. =:o}

[MysteryX]

Yeah, the whole point is to see what it does on *diagonal* lines and on curves. On verticals and horizontals, it is indeed just doing exactly what bilinear would.

In that case, here's the Lighthouse with MedianResize twice.

https://s14.postimg.org/p1ksnjwot/Median_Lighthouse.png (https://postimg.org/image/p1ksnjwot/)

Kind of blurry.

On the plus side, diagonals are not worse than the rest of the image :D

[MysteryX]

I asked on StackOverflow about using Vectors to find the median and he posted a really great solution performance-wise


I assume you have separate vectors for left/top/right/bottom. Having them packed together in a vector would be extremely annoying, and actually harder to set up too because that cannot be done with a simple load.

You don't have to sort (which would require a lot of comparisons and ConditionalSelects) to find the median of 4. It is enough to find the minimum and maximum and remove those (once each, of course). Finding the minimum and maximum is easy, just apply Vector.Min and Vector.Max a couple of times. "Removing" means subtracting them from the sum of the 4 things. Of course since the result of that represents the sum of two bytes, it cannot fit in a byte itself[note 1], so unfortunately most of the computation has be done in 16bit, halving the throughput. In the end, just shift the sum of the two middle values right by 1 to get their average, which you can convert back to 8bit.

Or in short, the median-of-4 is, without sorting:

median = (a + b + c + d - min(a, b, c, d) - max(a, b, c, d)) >> 1;
Optionally you can add 1 before the shift to get a rounded-up average.

1: if it wasn't for that, letting the calculations wrap would have solved everything. If it was median-of-3, the result would fit in 8 bits, so it could be done without widening (even though the sum may wrap, the subtractions would "unwrap" it by the same amount). Of course it could also be done with XOR then, for which it is more obvious that it works.

[pbristow]

In that case, here's the Lighthouse with MedianResize twice. [...] Kind of blurry.


Indeed, and with some interesting patterns of tiny dots appearing... I wonder what's causing that?

I never imagined anyone trying to do it twice! :eek: Have you got the intermediate image, with it done just once?

Useful tips there from StackOverflow. It occurs to me that the problem of exceeding 8 bits could be circumvented by pre-dividing (or pre-shifting) all the operands a, b, c and d, rather than doing the divide/shift at the end. But unless there's a nifty operation to do that on a whole block of 8 bit integers at once, it's probably just slowing things down for not much benefit. (3 extra 8-bit shifts, versus the cost of converting up to / down from 16 bit? How does that work out?)

[wonkey_monkey]

I asked on StackOverflow about using Vectors to find the median and he posted a really great solution performance-wise

I'm quite pleased that I came up with that one by myself for my tests! I didn't use vectors though, as I wrote it in RPN, but I was still proud of working out the min/max thing myself :)

Out of curiosity, MysteryX, what's your FPS for the following:

ColorBarsHD(300, 200)
MedianUpscaler()

[colours]

I'm quite pleased that I came up with that one by myself for my tests! I didn't use vectors though, as I wrote it in RPN, but I was still proud of working out the min/max thing myself :)

You can do slightly better, of course.

def median_of_four(a, b, c, d):
abmin, abmax, cdmin, cdmax = min(a, b), max(a, b), min(c, d), max(c, d)
return (max(abmin, cdmin) + min(abmax, cdmax) + 1) >> 1

Exactly the same number of min/max operations as finding the minimum and maximum simultaneously, but now you also get to just average two values instead of doing a weighted average on six values, and I think x86 SIMD can handle that.

Taking care of the rounding bias is left as an exercise for the reader.

Also, this thread sorta reminds me of ImageMagick's mesh interpolation (http://www.imagemagick.org/Usage/misc/#mesh); this idea takes the second and third values sorted numerically, whereas mesh interpolation takes the diagonal pair with the closest values.

[StainlessS]

left as an exercise for the reader.


I love these exercise quotes, means "I know how to do it but cant be bothered to tell".

ie 'I'm really clever, prove that you are worthy'.

Mind you, colors is really clever, and most of us, just aint worthy.
(Sad but true).

EDIT: Incidentally, YPlaneMedian() is implemented as YPlaneMin(Threshold=50.0) # 50.0%
EDIT: Where the accumulated number of pixels (stepping by luma value) is greater than or equal to 50.0% of total number of pixels.
EDIT: Result is luma value where above is true.

[colours]

I love these exercise quotes, means "I know how to do it but cant be bothered to tell".

ie 'I'm really clever, prove that you are worthy'.

Mind you, colors is really clever, and most of us, just aint worthy.
(Sad but true).

lol

On one hand, getting rid of the rounding bias is not hard per se. One way is to round half to even (https://en.wikipedia.org/wiki/Rounding#Round_half_to_even), and another is to round towards one of the input values. Yet another is to alternate between rounding down and rounding up, but this can produce significant visual artifacts for upscaling purposes. Or we have the "dumb" way of increasing precision to 9 bits temporarily, then applying error diffusion (Floyd-Steinberg, etc.), which has the best quality but is also the slowest.

On the other hand, getting rid of the rounding bias in as few operations as necessary seems to be very nontrivial and it seems that all four options I listed above will be a significant speed hit versus just ignoring the rounding bias. Hence: exercise for you, the reader!