Fractional Bilinear Interpolation

This is an archive of a topic from NESdev BBS, taken in mid-October 2019 before a server upgrade.
View original topic
Fractional Bilinear Interpolation
by on (#122759)
I've been playing around with some image scaling stuff tonight and came up with the following. I'm interested in your opinions.

In this post, tepples talks about doubling the image size with nearest-neighbor interpolation before performing any additional resizing with bilinear interpolation. The method I came up with is essentially an extension of this idea, except that it's done in one step and the amount of bilinear interpolation is adjustable (hence the 'fractional' in fractional bilinear filtering).

The implementation is pretty simple. Here's the shader code.

fbi.fx:
Code:
/*
Copyright (c) 2013 James Slepicka

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/

Texture2D tex;

SamplerState sam_linear
{
 Filter = MIN_MAG_MIP_LINEAR;
 AddressU = Clamp;
 AddressV = Clamp;
};

matrix world;
matrix view;
matrix proj;

float2 tex_size;
float2 input_size;
float2 output_size;
float sharpness = 1.0;

struct VS_INPUT
{
 float4 pos : POSITION;
 float2 tex : TEXCOORD0;
};

struct PS_INPUT
{
 float4 pos : SV_POSITION;
 float2 tex : TEXCOORD0;
};

PS_INPUT VS (VS_INPUT input)
{
 PS_INPUT output = (PS_INPUT)0;
 output.pos = mul (input.pos, world);
 output.pos = mul (output.pos, view);
 output.pos = mul (output.pos, proj);
 output.tex = input.tex;   
 return output;
}

float4 PS (PS_INPUT input) : SV_Target
{
 float2 scale = output_size / input_size;
 float2 interp = saturate((scale - lerp(scale, 1.0, sharpness))/(scale * 2.0));
 float2 p = input.tex.xy * tex_size + .5;
 float2 i = floor(p);
 float2 f = p - i;
 f = saturate((f - interp) / (1.0 - interp * 2.0));
 p = ((i + f) - .5) / tex_size;
 float4 r = tex.Sample(sam_linear, p);
 r.a = 1.0;
 return r;
}

technique10 render
{
 pass P0
 {
  SetVertexShader(CompileShader(vs_4_0, VS()));
  SetGeometryShader(NULL);
  SetPixelShader(CompileShader(ps_4_0, PS()));
 }
}


Some sample images to help illustrate the concept:

Nearest-neighbor:
Image

Bilinear interpolation:
Image

And somewhere in-between:
Image

If you'd like to play around with it, I put together a demo app. Use the up and down arrows (or page up/down) to adjust the amount of interpolation. DX10 (Win Vista+) is required and you may need to download some libraries from Microsoft if you get messages about missing dlls: MSVC++ redistributable and the DirectX runtime.
Re: Fractional Bilinear Interpolation
by on (#122760)
In that post tepples describes I believe a practical way to achieve the following (and additionally how to achieve it with other filters like Scale2x, without rewriting any of the filter code).

Overlay the output display pixel grid over the NES pixel image. Wherever an output pixel covers part of only a single NES pixel, output that color. Where an output pixel covers more than one NES pixel, mix the colors in ratios equal to the relative areas of the overlap.

This results in sharp-edged blocky pixels with minimal inconsistencies in appearance, even when the NES image is being expanded into rectangular pixels on an output display only slightly larger than the original NES image, e.g. 256x240 to 584x480. Vertically there will be no mixing. Horizontally there will only be at most one pixel of intermediate mixed color between two pixels.

Examining more closely, consider the case of expanding a 4x1 image (in) into 10x1. The output pixels will consist of in[0], in[0], in[0]*0.5+in[1]*0.5, in[1], in[1], in[2], in[2], in[2]*0.5+in[3]*0.5, in[3], in[3]. If the output were 100 pixels wide, the output pixels would be each input pixel repeated 25 times, without any mixing. With linear rescaling there would be massive mixing of most pixels, making it a big blur.

Can your shader do the above? I notice that the 0.30 example showed vertical mixing. An easy way to test it is to do a large integer expansion on both axes and be sure there is no pixel mixing at all. Then do a non-integer expansion on only the X axis and ensure that there is no pixel mixing between horizontal edges (vertically), only horizontally, and that the mixing is no more than one pixel wide. [maybe yours passes this test and you're expanding a non-integer amount vertically in your example]

Thinking more about this, it gets at the core of the basic meaning of a pixel image. Is it a set of infinitely-small samples at the center of each grid rectangle, or is it a representation of the color across the entire grid rectangle? The former is the interpretation that leads to linear (or similar) interpolation, while the latter is what leads to the rescaling described here. In a way, this is what nearest-neighbor scaling is a poor approximation of.
Re: Fractional Bilinear Interpolation
by on (#122764)
blargg wrote:
Can your shader do the above?

Yes; at sufficiently high levels of interp_adjust (this is at .3), there is no mixing between edges on axes scaled by an integer ratio. On axes scaled by non-integer ratios, mixing is limited to one pixel.

Image
Re: Fractional Bilinear Interpolation
by on (#122771)
Nice. Apologies for one more request, but I lack Windows. What happens when you use interp_adjust of 0.3 with an X scaling of say 4.9? Still only one-pixel-wide mixing between pixels?
Re: Fractional Bilinear Interpolation
by on (#122778)
blargg wrote:
Nice. Apologies for one more request

No worries -- I'm happy to discuss and try out stuff.

blargg wrote:
What happens when you use interp_adjust of 0.3 with an X scaling of say 4.9? Still only one-pixel-wide mixing between pixels?

interp_adjust needs to be increased with higher scaling factors. 8x scaling needs about .425, for example. It should be easy to programmatically determine the optimal value. I'll work on that.
Re: Fractional Bilinear Interpolation
by on (#122780)
So interp_adjust appears to set the flat area of each texel in units of the width of 2 texels. In that case, the optimal value would be (scalefactor - 1) / (2 * scalefactor). This works fine as long as the horizontal and vertical scale factors are within 1 pixel/texel of each other, such as most uses on NES. But what happens in SNES pseudo-hires mode, where the horizontal and vertical scale operations need separate interp_adjust values due to the decidedly rectangular (4:7) pixel aspect ratio?

In any case, TVs themselves introduce blurring, and interp_adjust = 0.25 might produce a more accurate simulation of a PlayChoice, RGB SNES, or component Wii.
Re: Fractional Bilinear Interpolation
by on (#122785)
tepples wrote:
(scalefactor - 1) / (2 * scalefactor)

Yep -- this works well. Thanks.

tepples wrote:
But what happens in SNES pseudo-hires mode, where the horizontal and vertical scale operations need separate interp_adjust values due to the decidedly rectangular (4:7) pixel aspect ratio?

If you need separate interp_adjust values, you can do this:
Code:
 f.x = (f.x-interp_adjust_x)/(1.0-interp_adjust_x*2.0);
 f.x = saturate(f.x);
 
 f.y = (f.y-interp_adjust_y)/(1.0-interp_adjust_y*2.0);
 f.y = saturate(f.y);
Re: Fractional Bilinear Interpolation
by on (#122788)
I knew I'd seen something like this mentioned somewhere before, and i guess ImageWorsener's documentation calls itpixel mixing.
Re: Fractional Bilinear Interpolation
by on (#122822)
Yeah, I guess it is the same thing. So much for fame and fortune.

In any event, I've incorporated it into the latest release of my emulator.

tepples wrote:
TVs themselves introduce blurring, and interp_adjust = 0.25 might produce a more accurate simulation

Can't really comment on accuracy, but just a bit of blurring looks better, I think. I've included a sharpness adjustment to allow for this.
Re: Fractional Bilinear Interpolation
by on (#122828)
It's great that you added a blur adjustment, to go from no mixing at all, one-pixel-wide mixing, or full bilinear. And it's a shader, so less CPU load. As far as I can tell, it's still rare for an emulator to support this kind of rescaling, so you can preserve the aspect ratio and still get sharp pixels.
Re: Fractional Bilinear Interpolation
by on (#122835)
A trick I used to use a long time ago, prior to having pixel shaders ...

Blit the image to the screen using nearest-neighbor (eg GL_NEAREST), and then blit the image again using bilinear filtering (eg GL_LINEAR) with a source alpha. This alpha value is effectively a blur factor (0.0 = sharp, 0.5 = middle-of-the-road, 1.0 = blurry)

This works with any hardware accelerated API that supports alpha blending (Direct3D, OpenGL, etc) and does not require any pixel shaders.

Of course if you have shaders, there are much better techniques. Fes' pixellate shader is particularly impressive, for instance. It's effectively the absolute minimum blurring needed to make non-even-multiple scaling look perfect in pixellated form.
Re: Fractional Bilinear Interpolation
by on (#122842)
byuu wrote:
Fes' pixellate shader is particularly impressive, for instance. It's effectively the absolute minimum blurring needed to make non-even-multiple scaling look perfect in pixellated form.

Assuming that you're talking about the pixellate shader distributed with higan, this method produces identical output. edit: identical output in center mode, but mine looks better in scale and stretch modes.
Code:
<?xml version="1.0" encoding="UTF-8"?>
<shader language="HLSL">
  <source><![CDATA[
    texture rubyTexture;
    float4 rubyInputSize;
    float4 rubyOutputSize;
    float4 rubyTextureSize;
    sampler s0 = sampler_state { texture = <rubyTexture>; };

    float4 PS (in float2 Tex : TEXCOORD0) : COLOR0
    {
     float2 scale = rubyOutputSize / rubyInputSize;
     float2 interp = (scale - 1.0) / (scale * 2.0);
     saturate(interp);

     float2 p = Tex.xy;
     p = p * rubyTextureSize + .5;
     float2 i = floor(p);
     float2 f = p - i;

     f = (f-interp) / (1.0-interp*2.0);
     f = saturate(f);

     p = i + f;
     p = (p - .5) / rubyTextureSize;
     float4 r = tex2D(s0, p);
     r.w = 1.0;
     return r;
    }

    Technique T0
    {
      pass p0 { PixelShader = compile ps_2_0 PS(); }
    }
  ]]></source>
</shader>
Re: Fractional Bilinear Interpolation
by on (#122854)
I can't compare GLSL to HLSL to verify that claim, but it sounds very impressive!

Would you consider writing your shader in GLSL? None of my primary PCs support Direct3D, and even on my Windows build box, I've removed HLSL support in an effort to promote portability.

I've changed the uniform names and use GLSL 1.5 (no fixed functions), however. I can ask on my forum for a port and post if back here if that's okay with you, too.

EDIT: aliaspider ported it.

Code:
#version 150

uniform sampler2D   source[];
uniform vec4      sourceSize[];
uniform vec4      targetSize;

in Vertex {
   vec2 texCoord;
};
out vec4 fragColor;

void main() {
   vec2 scale = targetSize.xy*sourceSize[0].zw;
   vec2 interp = (scale - vec2(1.0,1.0)) / (scale * 2.0);
   clamp(interp,0.0,1.0);
   vec2 p = texCoord.xy;
    p = p * sourceSize[0].xy + 0.5;
    vec2 i = floor(p);
    vec2 f = p - i;

    f = (f-interp) / (1.0-interp*2.0);
    f = clamp(f,0.0,1.0);

    p = i + f;
    p = (p - 0.5) * sourceSize[0].zw;
    vec4 r = texture(source[0], p);
    r.w = 1.0;
    fragColor=r;
}
Re: Fractional Bilinear Interpolation
by on (#122863)
Does OpenGL work on Windows RT and Xbox One? I was under the impression that these were supposed to be "legacy-free" platforms, and OpenGL was legacy. Perhaps someone is aiming for a publisher to use this to port old software to new consoles, just as Atlus, Jaleco, and Konami used PocketNES.
Re: Fractional Bilinear Interpolation
by on (#122865)
byuu wrote:
EDIT: aliaspider ported it.

There's something wrong with it; it looks blurry.
Re: Fractional Bilinear Interpolation
by on (#122866)
I spent a few minutes trying to fix it, but didn't have much luck. I'll try again later. In the meantime, here's a comparison of the two shaders in scale mode:

pixellate
Image

fbi
Image
Re: Fractional Bilinear Interpolation
by on (#122868)
According to that screenshot, pixellate is equivalent to FBI with an interp_adjust_y equal to 0.5, that is, full nearest-neighbor vertically.

Some level of blurring is unavoidable unless you redraw everything as vector graphics.
Re: Fractional Bilinear Interpolation
by on (#122871)
Yeah, I believe the reason pixellate works that way is that higan tries to maintain even multiples in scaling by default.

It is primarily meant to help ease the pain of aspect ratio correction, which is done by changing only the width of the image.

If I recall, SNES Mega Man's energy bar was always the most extreme example of the downside of vertical interpolation. Damn near impossible to make that thing look nice at arbitrary scale factors. And yes I'm aware you could rotate that energy bar 90 degrees and have the same issue with horizontal interpolation (and you could correct aspect by stretching only the height by an uneven multiple.)
Re: Fractional Bilinear Interpolation
by on (#122883)
One thing doesn't look right in both; it gets dark between the left edge of mario's hat and the background green.
Re: Fractional Bilinear Interpolation
by on (#122884)
Hah, I wonder if that's due to not converting to a linear RGB space before mixing.
Re: Fractional Bilinear Interpolation
by on (#122886)
The TVs of the time didn't convert to a linear RGB space either.
Re: Fractional Bilinear Interpolation
by on (#122887)
I didn't think we were simulating TVs here. I thought we were trying to expand a hard-edged pixel image to a non-integer scaling without some pixels being one unit wider/taller than others. When two different-color pixel edges fall next to each other and there's no mixing, it should look similar to when two fall half way across an output pixel such that they are mixed half and half. If this mixing is done in sRGB, the mixed version will look overly dark, which I think is what is happening here.

EDIT: indeed, that was the cause of that unexplained darkness (darker is naive mixing, lighter is correct mixing):

Image
Re: Fractional Bilinear Interpolation
by on (#122966)
mikejmoffitt wrote:
One thing doesn't look right in both; it gets dark between the left edge of mario's hat and the background green.

blargg wrote:
If this mixing is done in sRGB, the mixed version will look overly dark...EDIT: indeed, that was the cause of that unexplained darkness (darker is naive mixing, lighter is correct mixing):

Thanks, guys. Fixed in the WIP version of nemulator.
Re: Fractional Bilinear Interpolation
by on (#122993)
tepples wrote:
The TVs of the time didn't convert to a linear RGB space either.


Fortunately, we're discussing scaling and filtering algorithms, not how televisions displayed. What a television does is absolutely irrelevant here.

As long as we're mentioning TVs, though, it should be pointed out that a lot of televisions do seem to implement this incorrect edge mixing that produces dark borders when any upscaling is being performed.
Re: Fractional Bilinear Interpolation
by on (#123482)
James wrote:
Thanks, guys. Fixed in the WIP version of nemulator.


Hey James, thanks for this!

Would you be kind enough to open source your shader + the latest fixes so that I can see it gets ported to Cg and other formats for cross-platform use in OpenEmu or RetroArch?

There's a pretty good community built around the Cg format (https://github.com/libretro/common-shaders) and your shader looks very nice.
Re: Fractional Bilinear Interpolation
by on (#123486)
Hi clobber,

clobber wrote:
your shader looks very nice.

Thanks!

clobber wrote:
Would you be kind enough to open source your shader

Sure. I've updated the code in the first post of this thread. Have at it.

re: sRGB stuff -- that fix is implementation dependent. You can specify that your texture and back buffer are in sRGB color space and let DirectX/OpenGL handle the conversion to/from linear color space. I don't think you can fix this within the shader itself unless you write your own texture sampler.
Re: Fractional Bilinear Interpolation
by on (#123487)
I know nothing about shaders, but if you can apply a power function (gamma), do 2.2, mix, then 1/2.2. This will work for sRGB. If things are calculated in more than 8 bits per component, this won't cause any banding.
Re: Fractional Bilinear Interpolation
by on (#123488)
blargg wrote:
if you can apply a power function (gamma), do 2.2, mix, then 1/2.2.

Yeah, this is what I was referring to when I said you'd need to write your own texture sampler. If you wanted to do this, you wouldn't be able to use the built-in linear sampler because you can't modify the pre-interpolation values. You'd have to point sample the texture, apply gamma corrections, and manually interpolate.