php - 双三次插值中的大量伪影；怎么修？

Question

我正在尝试实现双三次插值算法以从高度图重建更高分辨率的数据。经过一些失败和包含几乎无法理解的数学的指令集(我已经有几年没有微积分了，除了基础知识我不再记得太多)，我找到了 Paul Bourke 的文章“Bicubic Interpolation for Image Scaling”包含什么似乎是一个相当简单和易于实现的算法。 http://paulbourke.net/texture_colour/imageprocess/

但是，我并没有生成与维基百科上的插值结果相差甚远的插值结果，而是得到了这个(来自相同的输入数据):

是什么导致了错误，更重要的是 - 如何修复它？

下面的 PHP 代码(是的，这可能应该 - 并且将会 - 在 C 中重新实现；当它工作时)

class BicubicInterpolator
{
    private $data;
    public function Set_data($d)
    {
        $this->data=$this->denull($d);
    }
    public function Interpolate($dx,$dy)
    {   
        $r=0;
        for ($m=-1; $m<2; $m++)
            for ($n=-1; $n<2; $n++)
                $r+=$this->data[$m+1][$n+1] * $this->R($m-$dx) * $this->R($dy-$n);
        return $r;
    }
    private function denull($d)
    {
        //Substituting null values with nearest known values as per "A Review of Some Image Pixel Interpolation Algorithms" by Don Lancaster (supposed to produce same output as example image)
        if ($d[0][1]===null) for ($i=0; $i<4; $i++) $d[0][$i]=$d[1][$i];
        if ($d[1][0]===null) for ($i=0; $i<4; $i++) $d[$i][0]=$d[$i][1];
        if ($d[3][1]===null) for ($i=0; $i<4; $i++) $d[3][$i]=$d[2][$i];
        if ($d[1][3]===null) for ($i=0; $i<4; $i++) $d[$i][3]=$d[$i][2];
        return $d;
    }
    function R($x)
    {
        return (      $this->P($x+2)
            - 4 * $this->P($x+1)
            + 6 * $this->P($x)
            - 4 * $this->P($x-1) )/6;
    }
    function P($x)
    {
        if ($x>0) return $x*$x*$x;
        return 0;
    }

Answer 1

最后，我改用了另一种算法，该算法基于 Don Lancaster 概述的算法与“C 中的数值食谱”(第 2 版)第 3.6 章第 136 页的导数和交叉导数公式的组合。

这结合了两个小调整:

1. 函数计算缓存一组中间值最后一个 y 坐标(连续的 Interpolate(x,y) 调用具有相同的y 参数将需要四次乘法和三次加法，减少处理时间)
2. 一组衍生品可以公开访问，允许最后一个两个作为坐标中网格单元的前两个传递(x, y+1) 并将获得每个所需的计算量减半每个单元格的那些衍生集。

这是实现，没有明显的故障:

class BicubicInterpolator
{
    private $last_y;
    private $last_y_a;
    private $a;
    public $x;
    public function __construct()
    {
        for ($i=0;$i<4;$i++)
            $this->x[$i]=false;
    }
    public function Set_data($d)
    {
        $d=$this->denull($d);
        $x=$this->x;
        for ($j=1; $j<3; $j++)
            for ($k=1; $k<3; $k++)
            {
                $r=($j-1)*2+($k-1);
                $w[$r]=$d[$j][$k];
                //Derivatives and cross derivatives calculated as per Numerical Recipes in C, 2nd edition.
                if (!$x[$r]) $x[$r]=( $d[$j][$k+1] - $d[$j][$k-1] ) / 2;
                $y[$r]=( $d[$j+1][$k] - $d[$j-1][$k] ) / 2;
                $z[$r]=( $d[$j+1][$k+1]-$d[$j+1][$k-1]-$d[$j-1][$k+1]+$d[$j-1][$k-1] )/4;
            }
        $this->x=$x;
        /* Coefficient calculation as per "A Review of Some Image Pixel Interpolation Algorithms" by Don Lancaster, 
        + addressing changed to (x,y) instead of (y,x)
        + reformulated to minimize the number of multiplications required */
        $this->a[0][0] = $w[0];
        $this->a[1][0] = $y[0];
        $this->a[2][0] = 3*($w[2]-$w[0])-2*$y[0]-$y[2];
        $this->a[3][0] = 2*($w[0]-$w[2])+$y[0]+$y[2];
        $this->a[0][1] = $x[0];
        $this->a[1][1] = $z[0];
        $this->a[2][1] = 3*($x[2]-$x[0])-2*$z[0]-$z[2];
        $this->a[3][1] = 2*($x[0]-$x[2])+$z[0]+$z[2];
        $this->a[0][2] = 3*($w[1]-$w[0])-2*$x[0]-$x[1];
        $this->a[1][2] = 3*($y[1]-$y[0])-2*$z[0]-$z[1];
        $this->a[2][2] = 9*($w[0]-$w[1]-$w[2]+$w[3])+6*($x[0]-$x[2]+$y[0]-$y[1])+3*($x[1]-$x[3]+$y[2]-$y[3])+4*$z[0]+2*($z[1]+$z[2])+$z[3];
        $this->a[3][2] = 6*($w[1]+$w[2]-$w[3]-$w[0])+4*($x[2]-$x[0])+3*($y[1]-$y[0]-$y[2]+$y[3])+2*($x[3]-$z[0]-$z[2]-$x[1])-$z[1]-$z[3];
        $this->a[0][3] = 2*($w[0]-$w[1])+$x[0]+$x[1];
        $this->a[1][3] = 2*($y[0]-$y[1])+$z[0]+$z[1];
        $this->a[2][3] = 6*($w[1]+$w[2]-$w[0]-$w[3])+3*(-$x[0]-$x[1]+$x[2]+$x[3])+4*($y[1]-$y[0])+2*($y[3]-$y[2]-$z[0]-$z[1])-$z[2]-$z[3];
        $this->a[3][3] = 4*($w[0]-$w[1]-$w[2]+$w[3])+2*($x[0]+$x[1]-$x[2]-$x[3]+$y[0]-$y[1]+$y[2]-$y[3])+$z[0]+$z[1]+$z[2]+$z[3];

        $this->last_y=false;
    }
    public function Interpolate($x,$y)
    {
        if ($y!==$this->last_y)
        {
            for ($i=0; $i<4; $i++)
            {
                $this->last_y_a[$i]=0;
                for ($j=0; $j<4; $j++)
                    $this->last_y_a[$i]+=$this->a[$j][$i]*pow($y,$j);
            }
            $this->last_y=$y;
        }
        $r=0;
        for ($i=0; $i<4; $i++)
            $r+=$this->last_y_a[$i]*pow($x,$i);
        return $r;
    }
    private function denull($d)
    {
        //Substituting null values with nearest known values 
        //as per "A Review of Some Image Pixel Interpolation Algorithms" by Don Lancaster
        if ($d[0][1]===null)    for ($i=0; $i<4; $i++)  $d[0][$i]=$d[1][$i];
        if ($d[1][0]===null)    for ($i=0; $i<4; $i++)  $d[$i][0]=$d[$i][1];
        if ($d[3][1]===null)    for ($i=0; $i<4; $i++)  $d[3][$i]=$d[2][$i];
        if ($d[1][3]===null)    for ($i=0; $i<4; $i++)  $d[$i][3]=$d[$i][2];
        return $d;
    }
}