【阅读笔记】New Edge Diected Interpolation，NEDI算法，待续

一、概述

由Li等提出的新的边缘指导插值(New Edge—Di-ected Interpolation，NEDI)算法是一种具有良好边缘保持效果的新算法，它利用低分辨率图像与高分辨率图像的局部协方差问的几何对偶性来对高分辨率图像进行自适应插值。

2001年Xin Li和M.T. Orchard提出了一种针对自然图像的边缘定向插值算法（New edge-directed interpolation）。其基本思想是首先根据低分辨率图像估计局部协方差系数，然后根据低分辨率协方差和高分辨率协方差之间的几何对偶性，使用这些协方差估计来以更高分辨率调整内插。仿真结果表明，这种新插值算法大大提高了插值图像的质量。2006年Lei Zhang和Xiaolin Wu通过定向滤波和数据融合提出了一种新的边缘引导非线性插值技术。 对于要内插的像素，在两个正交方向上定义两个观察组，并且每个组产生像素值的估计。 通过线性最小均方误差估计（LMMSE）技术将这些方向的估计值融合为更稳健的估计值，并使用两个观测集的统计量。 他们还提出了基于LMMSE的插值算法的简化版本，以降低计算成本而不牺牲很多插值性能。

NEDI算法与传统线性插值算法相比避免了由于跨越边缘插值而引入的边缘细节退化现象，显著提高了图像的视觉质量，但是由于迭代过程可能出现的错误会导致放大图像边缘噪声仍然比较明显，而且算法具有较高的复杂度，不适合硬件实现和图像实时处理。

二、算法思想

NEDI算法的基本思想是先计算低分辨率图像各像素点的局部协方差系数，再利用低分辨率与高分辨率协方差间的几何对偶性，来计算高分辨率图像中需要插入的像素点的值。

三、算法原理

设放大倍率为2，低分辨率图像X的矩阵大小为H×W，相应的高分辨率图像Y矩阵大小为2H×2W，则Y_{2i,2j}=X_{i,j}。

插值限制在4个方向，即该点在高分辨率栅格中，对角线方向最近的4个像素点，如下图所示，求黑点Y_{2i+1,2j+1}则有：

其中，放大倍数不同，k、l数值不同，步进数值为1/放大倍数。

因为Y_{2i,2j}=X_{i,j}，所以可以通过上公式插值出Y_{2i+1,2j+1}

现在得到4个对角线的最近像素，假设四个邻像素为一个局部平稳的高斯过程 ，由经典 Wiener滤波理论可知，最优的 MMSE(Minimum MeansSquare Error)线性插值系数计算公式如下：

其中，r表示在高分辨率图像中的局部协方差

$$ R=R_{kl}\ r=R_{k} $$

高分辨率图像中的R_{kl}，r_k和低分辨率的\hat R_{kl}，\hat r_k具有几何上的对偶性。即R_{kl},\hat R_{kl}在不同的分辨率以相同的方向分别链接一对像素，可以用后者估计前者。

低分辨率上协方差系数可采用标准方法在一个局部模板(大小为 MXM)中计算得到：

$$ \hat R=\frac{1}{M^2}CC^T \ \hat r=\frac{1}{M^2}Cy $$

其中，y=[y_1,...y_{M^2}]是一个包含MxM个点像素的数值向量，这些像素包含在一个局部模板内；数值矩阵C大小4M^2，第k列向量为y_k对角线方向的最近邻4点像素值，得到

于是，计算每一个坐标(2i+1)(2j+1)的像素Y_{2i+1,2j+1}的最优插值权重\alpha。

于是Y_{i,j}(mod(i+j,2)=0)的估算公式如下：

于是Y_{i,j}(mod(i+j,2)=1)可以用Y_{i,j}(mod(i+j,2)=1)估计，公式如下：

上述的Y_{i,j}(mod(i+j,2)=1)和Y_{i,j}(mod(i+j,2)=0)计算相似，二者只相

差一个伸缩系数2^{1/2}和旋转系数\pi/4，所以只需少量改动就可以。

以上是算法原理推导，大概理解一下就行，主要看算法步骤。

四、算法步骤

使用经典NEDI算法将图像放大两倍需要两个步骤：

第l步：插出原始四个像素的中心点（2i+1.2j+1），如下图所示。

第2步：原始像素和第一步的插值像素的基础上，再插出水平(和垂直方向上的像素（2i+1,2j)、(2i,2j+1)、(2i+1,2j+2)、(2i+2,2j+1)，如下图所示。

而当图像被放大4倍时，还要重复同样的过程，由于这一次所使用的像素数日是之前所需的4倍，所以计算量将成指数增长。另外，由于引入迭代运算，如果某一个环节中产生了误差，这个误差将会传递到下一次插值，从而导致图像的插值错误。

优点：

根据统计信息进行插值，细节保持较好

缺点：

算法复杂，计算量大，运算速度较慢