Linear interpolation on canvas

Question

I'm trying to understand how image resampling methods work. I've read/watched several pages/videos and I think I got the idea. However, I couldn't find any working example on how to implement it. So I thought I should start with the basics: nearest neighbor resampling on 1D.

This was very straightforward and I think I got it. JSFiddle Demo.

function resample() {

    var widthScaled   = Math.round(originalPixels.width * scaleX);
    var sampledPixels = context.createImageData(widthScaled, originalPixels.height);

    for (var i = 0; i < sampledPixels.data.length; i+=4) {

        var position  = index2pos(sampledPixels, i);
        var origPosX  = Math.floor(position.x / scaleX);
        var origColor = getPixel(originalPixels, origPosX, position.y);

        setPixel(sampledPixels, position.x, position.y, origColor);
    }

    loadImage(context, sampledPixels);
}

Next, I moved on to linear interpolation. Thought it'd be simple too, but I'm having problems. First, how do I deal with the last pixel (marked red)? It has only one neighboring pixel. Second, my result is too sharp when compared to Photoshop's. Is my method flawed, or is PS doing some extra work? JSFiddle Demo.

function resample() {

    var sampledPixels = context.createImageData(originalPixels.width * scaleX, originalPixels.height);

    for (var i = 0; i < sampledPixels.data.length; i+=4) {

        var position  = index2pos(sampledPixels, i);
        var origPosX  = position.x / scaleX;

        var leftPixelPosX  = Math.floor(origPosX);
        var rightPixelPosX = Math.ceil(origPosX);

        var leftPixelColor  = getPixel(originalPixels, leftPixelPosX, position.y);
        var rightPixelColor = getPixel(originalPixels, rightPixelPosX, position.y);

        var weight = origPosX % 1;
        var color  = mix(leftPixelColor[0], rightPixelColor[0], weight);
            color  = [color, color, color, 255];

        setPixel(sampledPixels, position.x, position.y, color);
    }

    loadImage(context, sampledPixels);
}

function mix(x, y, a) {
    return x * (1 - a) + y * a;
}

Answer 1

Linear interpolation of pixels

There is no real right and wrong way to do filtering, as the result is subjective and the quality of the result is up to you, Is it good enough, or do you feel there is room for improvement.

There are also a wide variety of filtering methods, nearest neighbor, linear, bilinear, polynomial, spline, Lanczos... and each can have many variations. There are also factors like what is the filtering output format; screen, print, video. Is quality prefered over speed, or memory efficiency. And why upscale when hardware will do it for you in real-time anyways.

It looks like you have the basics of linear filtering correct

Update Correction. Linear and bilinear refer to the same type of interpolation, bilinear is 2D and linear is 1D

Handling the last Pixel

In the case of the missing pixel there are several options,

• Assume the colour continues so just copy the last pixel.
• Assume the next pixel is the background, border colour, or some predefined edge colour.
• Wrap around to the pixel at the other side (best option for tile maps)
• If you know there is a background image use its pixels
• Just drop the last pixel (image size will be 1 pixel smaller)

The PS result

To me the PhotoShop result looks like a form of bilinear filtering, though it should be keeping the original pixel colours, so something a little more sophisticated is being used. Without knowing what the method is you will have a hard time matching it.

A spectrum for best results

Good filtering will find the spectrum of frequencies at a particular point and reconstruct the missing pixel based on that information.

If you think of a line of pixels not as values but as volume then a line of pixels makes a waveform. Any complex waveform can be broken down into a set of simpler basic pure tones (frequencies). You can then get a good approximation by adding all the frequencies at a particular point.

Filters that use this method are usually denoted with Fourier, or FFT (Fast Fourier Transform) and require a significant amount of process over standard linear interpolation.

What RGB values represent.

Each channel red, green, and blue represent the square root of that channel's intensity/brightness. (this is a close general purpose approximation) Thus when you interpolate you need to convert to the correct values then interpolate then convert back to the logarithmic values.

Correct interpolation

function interpolateLinear(pos,c1,c2){ // pos 0-1, c1,c2 are objects {r,g,b}
    return {
       r : Math.sqrt((c2.r * c2.r + c1.r * c1.r) * pos + c1.r * c1.r),
       g : Math.sqrt((c2.g * c2.g + c1.g * c1.g) * pos + c1.g * c1.g),
       b : Math.sqrt((c2.b * c2.b + c1.b * c1.b) * pos + c1.b * c1.b),
    };
}

It is important to note that the vast majority of digital processing software does not correctly interpolate. This is in part due to developers ignorance of the output format (why I harp on about it when I can), and partly due to compliance with ye olde computers that struggled just to display an image let alone process it (though I don't buy that excuse).

HTML5 is no exception and incorrectly interpolates pixel values in almost all interpolations. This producing dark bands where there is strong hue contrast and darker total brightness for up and down scaled image. Once you notice the error it will forever annoy you as today's hardware is easily up to the job.

To illustrate just how bad incorrect interpolation can be the following image shows the correct (top) and the canvas 2D API using a SVG filter (bottom) interpolation.

2D linear interpolation (Bilinear)

Interpolating along both axis is done by doing each axis in turn. First interpolate along the x axis and then along the y axis. You can do this as a 2 pass process or a single pass.

The following function will interpolate at any sub pixel coordinate. This function is not built for speed and there is plenty of room for optimisation.

// Get pixel RGBA value using bilinear interpolation.
// imgDat is a imageData object, 
// x,y are floats in the original coordinates
// Returns the pixel colour at that point as an array of RGBA
// Will copy last pixel's colour
function getPixelValue(imgDat, x,y, result = []){ 
    var i;
    // clamp and floor coordinate
    const ix1 = (x < 0 ? 0 : x >= imgDat.width ? imgDat.width - 1 : x)| 0;
    const iy1 = (y < 0 ? 0 : y >= imgDat.height ? imgDat.height - 1 : y | 0;
    // get next pixel pos
    const ix2 = ix1 === imgDat.width -1 ? ix1 : ix1 + 1;
    const iy2 = iy1 === imgDat.height -1 ? iy1 : iy1 + 1;
    // get interpolation position 
    const xpos = x % 1;
    const ypos = y % 1;
    // get pixel index
    var i1 = (ix1 + iy1 * imgDat.width) * 4;
    var i2 = (ix2 + iy1 * imgDat.width) * 4;
    var i3 = (ix1 + iy2 * imgDat.width) * 4;
    var i4 = (ix2 + iy2 * imgDat.width) * 4;

    // to keep code short and readable get data alias
    const d = imgDat.data;

    for(i = 0; i < 3; i ++){
        // interpolate x for top and bottom pixels
        const c1 = (d[i2] * d[i2++] - d[i1] * d[i1]) * xpos + d[i1] * d[i1 ++];
        const c2 = (d[i4] * d[i4++] - d[i3] * d[i3]) * xpos + d[i3] * d[i3 ++];

        // now interpolate y
        result[i] = Math.sqrt((c2 - c1) * ypos + c1);
    }

    // and alpha is not logarithmic
    const c1 = (d[i2] - d[i1]) * xpos + d[i1];
    const c2 = (d[i4] - d[i3]) * xpos + d[i3];
    result[3] = (c2 - c1) * ypos + c1;
    return result;
}


 const upScale = 4;
 // usage
 const imgData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);
 const imgData2 = ctx.createImageData(ctx.canvas.width * upScale, ctx.canvas.height * upScale);
 const res = new Uint8ClampedArray(4);
 for(var y = 0; y < imgData2.height; y++){
     for(var x = 0; x < imgData2.width; x++){
         getPixelValue(imgData,x / upScale, y / upScale, res);
         imgData2.data.set(res,(x + y * imgdata2.width) * 4);
     }
 }

Example upscale canvas 8 times

The example uses the above function to upscale a test pattern by 8. Three images are displayed. The original 64 by 8 then, the computed upscale using logarithmic bilinear interpolation, and then using the canvas standard API drawImage to upScale (Using the default interpolation, bilinear) .

// helper functions create canvas and get context
const CImage = (w = 128, h = w) => (c = document.createElement("canvas"),c.width = w,c.height = h, c);
const CImageCtx = (w = 128, h = w) => (c = CImage(w,h), c.ctx = c.getContext("2d"), c);
// iterators
const doFor = (count, cb) => { var i = 0; while (i < count && cb(i++) !== true); }; 
const eachOf = (array, cb) => { var i = 0; const len = array.length; while (i < len && cb(array[i], i++, len) !== true ); };

const upScale = 8;
var canvas1 = CImageCtx(64,8);
var canvas2 = CImageCtx(canvas1.width * upScale, canvas1.height * upScale);
var canvas3 = CImageCtx(canvas1.width * upScale, canvas1.height * upScale);


    // imgDat is a imageData object, 
    // x,y are floats in the original coordinates
    // Returns the pixel colour at that point as an array of RGBA
    // Will copy last pixel's colour
    function getPixelValue(imgDat, x,y, result = []){ 
        var i;
        // clamp and floor coordinate
        const ix1 = (x < 0 ? 0 : x >= imgDat.width ? imgDat.width - 1 : x)| 0;
        const iy1 = (y < 0 ? 0 : y >= imgDat.height ? imgDat.height - 1 : y) | 0;
        // get next pixel pos
        const ix2 = ix1 === imgDat.width -1 ? ix1 : ix1 + 1;
        const iy2 = iy1 === imgDat.height -1 ? iy1 : iy1 + 1;
        // get interpolation position 
        const xpos = x % 1;
        const ypos = y % 1;
        // get pixel index
        var i1 = (ix1 + iy1 * imgDat.width) * 4;
        var i2 = (ix2 + iy1 * imgDat.width) * 4;
        var i3 = (ix1 + iy2 * imgDat.width) * 4;
        var i4 = (ix2 + iy2 * imgDat.width) * 4;

        // to keep code short and readable get data alias
        const d = imgDat.data;

        // interpolate x for top and bottom pixels
        for(i = 0; i < 3; i ++){
            const c1 = (d[i2] * d[i2++] - d[i1] * d[i1]) * xpos + d[i1] * d[i1 ++];
            const c2 = (d[i4] * d[i4++] - d[i3] * d[i3]) * xpos + d[i3] * d[i3 ++];

            // now interpolate y
            result[i] = Math.sqrt((c2 - c1) * ypos + c1);
        }

        // and alpha is not logarithmic
        const c1 = (d[i2] - d[i1]) * xpos + d[i1];
        const c2 = (d[i4] - d[i3]) * xpos + d[i3];
        result[3] = (c2 - c1) * ypos + c1;
        return result;
    }
     const ctx = canvas1.ctx;    
     var cols = ["black","red","green","Blue","Yellow","Cyan","Magenta","White"];
     doFor(8,j => eachOf(cols,(col,i) => {ctx.fillStyle = col; ctx.fillRect(j*8+i,0,1,8)}));
     eachOf(cols,(col,i) => {ctx.fillStyle = col; ctx.fillRect(i * 8,4,8,4)});
     
     const imgData = ctx.getImageData(0, 0, canvas1.width, canvas1.height);
     const imgData2 = ctx.createImageData(canvas1.width * upScale, canvas1.height * upScale);
     const res = new Uint8ClampedArray(4);
     for(var y = 0; y < imgData2.height; y++){
         for(var x = 0; x < imgData2.width; x++){
             getPixelValue(imgData,x / upScale, y / upScale, res);
             imgData2.data.set(res,(x + y * imgData2.width) * 4);
         }
     }
     canvas2.ctx.putImageData(imgData2,0,0);
     function $(el,text){const e = document.createElement(el); e.textContent = text; document.body.appendChild(e)};
   
     document.body.appendChild(canvas1);
     $("div","Next Logarithmic upscale using linear interpolation * 8");
     document.body.appendChild(canvas2);
     canvas3.ctx.drawImage(canvas1,0,0,canvas3.width,canvas3.height);
     document.body.appendChild(canvas3);
     $("div","Previous Canvas 2D API upscale via default linear interpolation * 8");
     $("div","Note the overall darker result and dark lines at hue boundaries");

canvas { border : 2px solid black; }