双三次插值出现大量伪影；如何修复？

Question

双三次插值出现大量伪影；如何修复？

phpalgorithminterpolationpolynomial-mathbicubic

3

我正在尝试实现一个双三次插值算法，以从高度图中重建更高分辨率的数据。经过一些失败和包含几乎无法理解的数学指令集（我已经有好几年没有学微积分了，我只记得基础知识），我找到了保罗·伯克（Paul Bourke）的文章“用于图像缩放的双三次插值”，其中包含了一个看起来相当简单易于实现的算法。http://paulbourke.net/texture_colour/imageprocess/

然而，与维基百科上的结果完全不同，它产生了这个结果（使用相同的输入数据）： enter image description here

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

以下是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;
    }

- Michał Gawlas

这是我所说的维基百科示例：http://upload.wikimedia.org/wikipedia/commons/thumb/d/d5/BicubicInterpolationExample.png/308px-BicubicInterpolationExample.png - Michał Gawlas

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Michał Gawlas · Accepted Answer

最终，我已经切换到了另一种算法，结合了Don Lancaster所概述的算法和"Numerical Recipes in C" (2nd Edition)，第3.6章中导数和交叉导数公式，第136页。

这与两个小调整相结合：

1. 函数计算缓存了中间一组值，用于最后的y坐标（a successive Interpolate(x,y) call with the same y argument will require four multiplications and three additions, cutting down on processing time） 2. 一个导数集合可以作为public访问，允许将最后两个导数作为前两个传递给坐标(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;
    }
}