[FIXED] What is wrong with my bilinear interpolation algorithm?

Issue

I am using PHP to test out my bilinear algorithm. The code is un-optimized for clarity.

Here is what the code below is doing:

1. Plot the original pixels from the 2x2 image to the 10x10 destination image. These will leave blank pixels.

Note: The images here are resized from 10x10 to 100x100 for better viewing.

2. Interpolate the row of pixels.

3. Interpolate the remaining pixels going from left to right, top to bottom using the row of pixels in step 2:

However, it does not match the result I get in Photoshop using bilinear resampling:

Full source code:

<?php
$image1 = imagecreatefrompng( 'test.png' );

$w1 = imagesx( $image1 );
$h1 = imagesy( $image1 );

$w2 = 10;
$h2 = 10;
$image2 = imagecreatetruecolor( $w2, $h2 );

imagefill($image2, 0, 0, imagecolorallocate($image2, 0x4c, 0x4c, 0x8e)); // added bg for pixels to stand-out

function lerp($v0, $v1, $t) {
    return $v0 + $t*($v1-$v0);
}

function getPixel($image, $x, $y){
    $rgb = imagecolorat( $image, $x, $y );
    $r     = ($rgb >> 16) & 0xFF;
    $g     = ($rgb >> 8) & 0xFF;
    $b     = $rgb & 0xFF;
    return array($r,$g,$b);
}

$maxY1 = $h1 - 1;
$maxX1 = $w1 - 1;
$maxY2 = $h2 - 1;
$maxX2 = $w2 - 1;

// plot original pixels from source to destination
for($y = 0; $y <= $maxY1; $y++) { // loop thru src height

    $newY = floor(($y/$maxY1) * $maxY2);

    for ($x = 0; $x <= $maxX1; $x++) { // loop thru src width

        $newX = floor(($x/$maxX1) * $maxX2);
        $rgb = imagecolorat( $image1, $x, $y );
        $r1     = ($rgb >> 16) & 0xFF;
        $g1     = ($rgb >> 8) & 0xFF;
        $b1     = $rgb & 0xFF;

        imagesetpixel( $image2, $newX, $newY, imagecolorallocate( $image2, $r1, $g1, $b1 ) );

    }
}
imagepng( $image2, 'out1.png' );

// interpolate pixels from pixel[1,0] to pixel[8,0]
$y = 0;
$rgb = imagecolorat( $image2, 0, $y );
$r0     = ($rgb >> 16) & 0xFF;
$g0     = ($rgb >> 8) & 0xFF;
$b0     = $rgb & 0xFF;

$rgb = imagecolorat( $image2, 9, $y );
$r1     = ($rgb >> 16) & 0xFF;
$g1     = ($rgb >> 8) & 0xFF;
$b1     = $rgb & 0xFF;
for($x=1; $x <= 8; $x++){
    $t = $x / 9;
    $r = lerp($r0, $r1, $t);
    $g = lerp($g0, $g1, $t);
    $b = lerp($b0, $b1, $t);
    imagesetpixel( $image2, $x, $y, imagecolorallocate( $image2, $r, $g, $b ) );
}
imagepng( $image2, 'out2.png' );

// interpolate pixels from pixel[1,9] to pixel[8,9]
$y = 9;
$rgb = imagecolorat( $image2, 0, $y );
$r0     = ($rgb >> 16) & 0xFF;
$g0     = ($rgb >> 8) & 0xFF;
$b0     = $rgb & 0xFF;

$rgb = imagecolorat( $image2, 9, $y );
$r1     = ($rgb >> 16) & 0xFF;
$g1     = ($rgb >> 8) & 0xFF;
$b1     = $rgb & 0xFF;

for($x=1; $x <= 8; $x++){
    $t = $x / 9;
    $r = lerp($r0, $r1, $t);
    $g = lerp($g0, $g1, $t);
    $b = lerp($b0, $b1, $t);
    imagesetpixel( $image2, $x, $y, imagecolorallocate( $image2, $r, $g, $b ) );
}
imagepng( $image2, 'out3.png' );

// interpolate remaining pixels
for($x=0; $x <= 9; $x++){
    $rgb = imagecolorat( $image2, $x, 0 );
    $r0     = ($rgb >> 16) & 0xFF;
    $g0     = ($rgb >> 8) & 0xFF;
    $b0     = $rgb & 0xFF;

    $rgb = imagecolorat( $image2, $x, 9 );
    $r1     = ($rgb >> 16) & 0xFF;
    $g1     = ($rgb >> 8) & 0xFF;
    $b1     = $rgb & 0xFF;
    for($y = 1; $y <= 8; $y++){
        $t = $y / 9;
        $r = lerp($r0, $r1, $t);
        $g = lerp($g0, $g1, $t);
        $b = lerp($b0, $b1, $t);
        imagesetpixel( $image2, $x, $y, imagecolorallocate( $image2, $r, $g, $b ) );
    }
}
imagepng( $image2, 'out4.png' );

header('Content-type: image/png');
imagepng( $image2);
imagedestroy( $image1 );

What am I missing?

Solution

Photoshop is correct. In your version the original 4 pixel values end up in the extreme corners of the new image but in the correct bilinear interpolation they end up in the centers of 4 quadrants of the new image. There is no information beyond the edge of the original image so photoshop does constant extrapolation at the edge:

2x2:

10x10 before interpolation:

If you started with a 3x3 image instead of 2x2, your method would cause the original edge pixels to have a diminished contribution to the final image relative to the center pixels, biasing the result.

Answered By - atb

Answer Checked By - Cary Denson (PHPFixing Admin)