基于几何分类的自适应图像插值算法*

梁 云，朱为鹏，李 峥，3

(1.华南农业大学 信息学院，广东 广州 510642;2.中山大学 信息科学与技术学院∥数字家庭教育部重点实验室，广东 广州 510006;3.广东工业大学 计算机学院，广东 广州 510090;4.深圳市数字生活网络与内容服务重点实验室，广东 深圳 518057;5.中山大学 深圳研究院，广东 深圳 518057)

随着媒体技术的发展，数字图像越来越多应用到生活和工作的各个领域。数字电视 (Digital TV)，移动电视 (Mobile TV)，网络电视 (Online TV)等的到来，人们对高分辨率图像的需求越来越迫切。与低分辨率图像相比，高分辨图像像素密度高，能提供更多的细节信息，而这些细节是实际应用所不可或缺的。目前，大量现存的图像摄取设备只能获取低分辨率图像，不能满足人们需要。更换这些设备耗费巨大，不易实现，且分辨率也不能无限制提高。一种有效获取高分辨率图像的方法是插值低分辨图像。现有方法的主要缺陷是不能很好的保持图像边缘，插值后图像上产生锯齿。

本文提出了一种基于几何分类的自适应图像插值方法。算法分3步:首先将低分辨率图像赋值给高分辨率图像部分像素点;然后划分高分辨率图像已知像素点所构成的插值单元;最后，对不同几何类型插值单元的未知像素分别求解，获取高分辨率图像。

本文的主要贡献有以下2点。其一是:根据初步赋值后的高分辨率图像的已知像素点和未知像素点的相对位置关系，将插值未知像素点的插值单元分为矩形插值单元和菱形插值单元，保证插值图像的边缘走向和宽度，提高插值图像的质量。其二是:从8个方向分别对两种插值单元进行几何分类，最后再根据每个像素点所属的相关插值单元进行分类插值，保证图像边缘的尖锐特征，提高插值图像的质量。

1 相关工作

近几年，通过插值获取高分辨率图像已成为一个研究的热点。主要方法可分为两大类，基于图形学的插值方法 (如:样条插值等)和基于统计的插法方法。

插值图像的边缘保持决定了插值图像的质量。人们越来越多的通过研究分析图像的统计特性来保持图像的边缘进而插值图像［1－4］。Li等［1］提出基于边缘的插值，通过保持低分辨图像的局部几何特征来提高插值图像质量，但速度慢。Morse等［2］建议基于等高线插值图像。Fattal［3］研究低分辨率图像边缘的统计特性，并将特征强加于插值后的图像来提高放大图像质量，缺陷是统计特征的微小变化将很大的程度上影响图像效果。Sun等［5］则对图像边缘的梯度变化进行研究，并将梯度变化信息附加在高分辨率图像，该方法虽然能够在一定程度上提高插值图像的质量，但是受图像噪声的影响比较严重。

此外，Battiato等［6］建议用边缘自适应方法插值。实验证明基于等高线或边缘自适应的方法对于去除图像的锯齿效果比较有效。但仍有不足，特别是对小面积重复区域的处理。Shan等［7］建议用卷积处理的方法插值视频、图像，可以满足实时性要求。Kopf等［8］将联合双边滤波器运用到了色调映射等图像处理中，通过高分辨图像的引导信息提高插值图像的效果。Sajjad等［9］建议一种新的图像插值方法根据已知像素点的邻结点分类已知像素点。但是他的方法只是水平和垂直的方向，对角线情况没有处理。事实上，大部分边的方向都是对角线方向。因为缺乏对对角线因素的考虑，Muhammad方法中有些未知像素点由与它距离较远的已知像素点决定。因此，某系已知像素间的相关信息被丢失，从而引入锯齿效应。

基于图形学的插值方法主要采用样条插值图像。Unser等［10］提出了基于样条的插值，Keys等［11］建议用三次卷积放大图像。它们缺陷是插值后图像变模糊。

2 几何分类插值单元

若插值低分率图像S(M×N)得到高分辨图像T(2M ×2N)。首先设定所有T2i，2j像素点均来自于Si，j，i，j为整数，图1(a)黑色点，我们将这些像素点称为已知像素点。因此，图像插值的关键是如何确定Ti，j像素点的值，且i，j不同时为偶数，图1(a)中白色点，设为未知像素点。基于几何分类的方向自适应图像插值首先算法首先根据高分辨图像中已知像素点和未知像素点间的相对位置关系，将未知像素点分成为3种，分别用图1(a)中的1，2，3描述，并把它们插值单元分为矩形插值单元和菱形插值单元，再根据8个方向的零交叉点对插值单元进行几何分类，最后对不同类型插值单元的未知像素点求解获取高分辨图像。

2.1 矩形插值单元和菱形插值单元

若高分辨率图像中未知像素点的x，y坐标均为奇数，则未知像素点被其周围上、下、左、右4个与之等距的已知像素点和4个未知像素点所包围。如图1(a)中1和图1(b)蓝色象素点所代表的未知像素点。图1(a)中的黑色部分代表已知像素点，白色部分代表未知像素点，图1(b)的黑色点代表已知像素点，蓝色点的x，y坐标均为奇数，选中的黑色点对蓝色点构成矩形插值单元。

若高分辨率图像中未知像素点的x，y坐标一个为奇数一个为偶数，未知像素点被2个已知像素点和2个x，y坐标均为奇数的未知像素点和2个x，y坐标一个为奇数且一个为偶数的像素点包围。如图1(a)的数字2，3和图2中红色点和绿色点所代表的未知像素点。将图2中红色点和绿色点周围被选中的4个点，所构成的插值单元作为中心未知像素点的菱形插值单元。

2.2 几何分类矩形插值单元

保证低分辨率的图像边缘决定了插值图像的质量。图像梯度的局部最大值处可能存在边，因此亮度的二阶导数的零交叉点可判断边的存在。根据零交叉点的值，分割插值区域为不同类型的区域。

除图像边界点外，每两个像素点间的零交叉点都可能来在2个方向的计算。如图3，x2和x3间的零交叉点可以由x2，x3和x4计算，也可以由x1，x2和x3计算。

若公式 (3)成立，则表示x2和x3之间至少有一个零交叉点存在，其中T是一个常数。

矩形插值单元中共存在8个可能零交叉点，分别位于4对像素间。如图4，虚线为可能存在零交叉点的位置。这些零交叉点的组合将插值单元中具有高对比度的像素区分开，即可能存在的图像的边，带箭头的切割线区分出高对比度的像素点。根据以上理论，矩形插值单元可以被几何分类为3种情况:有1个点和其他3个点有高度比度;2个点和另外2个点有高对比度;没有点和其他点具有高对比度。

以矩形插值单元左上角像素点具有高对比度为例来阐述情况。若图4中像素点 (2i，2j)和 (2i，2j+2)，(2i，2j)和(2i+2，2j)间的零交叉点值满足公式 (3)，则像素点 (2i，2j)与其它3个像素点间具有高对比度，图4左上角的切割线存在。此时，我们认为矩形插值单元的左上角像素点对中心未知像素点没有贡献，与待求未知像素点无关，只有其它3个点对中心点有贡献，图5(a)和(b)描述了这种情况，图5(b)是图5(a)的等价表示。具有高对比度像素点可能位于右上角，左下角或右下角，情况与左上角类似，见图5(c)，(d)和 (e)。

当2个像素点与其他像素点具有高对比度，矩形插值单元存在图4中的水平或竖直割线。未知像素点的左半部分或右半部分具有较大差异，图6。若图4中割线水平，则 (2i，2j)和 (2i+2，2j)，(2i，2j+2)和 (2i+2，2j+2)之间存在零交叉线，如图6(a)，图6(b)是图6(a)的等价表示，其他几种形式如图6(c)，(d)和 (e)。

如果插值单元中不存在零交叉线，这意味着插值单元是一个变化不大的连续平滑区域。

公式 (4)，(5)用来判断平滑区域，f1，f2，f3，f4分别表示插值单元中的已知像素点，f为它们的均值，σ为区域内的均方差。当某个区域的已知像素点满足公式 (5)时，则表示该区域是连续平滑区域。未知像素点被包含在该区域内，此时未知像素点的值可以用它的四个最邻近的已知像素点的值平均值求得。

2.3 几何分类菱形插值单元

菱形插值单元内的8个零交叉点是斜对角线方向上相关像素点确定的。如图3中介于x7和x10之间的零交叉点。同矩形插值单元类似，x7和x10之间也存在2个方向的零交叉点，由x4，x7，x10和x13，x7，x10这两组像素点决定。

若公式 (8)满足则表示在x4和x7之间至少有一个零交叉点存在，其他点对间的零交叉点的判断类似。

图7是一个菱形插值核的几何分类判别图，虚线为可能存在的零交叉点，位于不同对像素点间的2个零交叉点形成一条割线，割线将菱形插值核分成不同的几何类型。

图7 菱形插值单元的几何分类Fig.7 Geometrical classification of rectangular interpolating unit

图8为菱形区域内1个像素点具有高对比度的情况。若将菱形插值核中的4个顶点 (2i，2j)，(2i+2，2j)， (2i+1，2j－1)， (2i+1，2j+1)分别称作左点，右点，上点，下点。当上点和左点间，左点和下点间存在零交叉点时，左点与其他像素点之间存在明显差异，左侧竖直切割线形成。在左点右侧存在边。菱形的每个顶点都有可能与其它像素点形成明显对比，对应图5中的某个竖直或水平割线，所有4种情况如图8。

图8 菱形插值核的1个像素点具有高对比度Fig.8 One point of high contrast in rhombic interpolating unit

零交叉点点不相邻时，割线形成左对角线或右对角线2种情况。若割线为左对角线，菱形插值核如图9(a)或图9(b)。插值单元中心的未知像素点只与割线一侧的像素点有关，即图9(a)或图9(b)的阴影部分。如果割线形成右对角线，如图9(c)或图9(d)，图7中零交叉点位于左点和下点，右点和上点之间。这两组之间存在较高的对比，未知像素点的值只能与其中的一组相关。如果所有的8个零交叉点都不存在，未知像素点被4个灰度值相似的点包围，未知像素点处于平滑区域，对这种情况的处理与菱形插值单元类似。

图9 菱形插值核的2个像素点具有高对比度Fig.9 Two points of high contrast in rhombic interpolating unit

3 自适应的插值方法

基于几何分类的方向自适应图像插值方法分步对插值图像的未知像素点处理。首先根据T2i，2j=Si，j对高分辨率图像中x，y坐标值均为偶数的像素点进行赋值。然后再矩形插值单元中插值x，y坐标值为奇数的未知像素点。对每个矩形插值单元的8个零交叉点计算，根据计算值分类插值单元，然后用公式 (9)求解未知像素点。当有一个像素点与其他像素点有高对比时，该像素与未知像素点间有边存在，公式 (9)中该像素点相关系数为0;当有2个像素点与其它2个像素点有高对比时，则有2个像素的系数为0。若矩形区域为平滑区域，则未知像素点的值取4个像素点的均值。

用矩形插值单元对图像插值后，已知像素点和部分已求未知像素点构成菱形插值单元，再对x坐标为奇数，y坐标为偶数或x坐标为偶数，y坐标为奇数的未知像素点插值。用斜对角线方向的8个零交叉点来判断菱形插值单元的几何类类型，然后根据公式 (10)求出菱形插值单元内的中心像素点。若几何分类为图8中的某种情况，则具有高对比度的像素点在公式 (10)中的相关系数赋为0。若几何分类为图9的某一种，则将白色区域对应的像素点的系数赋为0。若菱形区域为平滑区域，则未知像素为菱形4个像素的均值。两次插值后，90%以上的未知像素点已求出。若仍有未知像素点，则用它周围的已知像素点线性插值。

4 实验结果

在Intel Pentium dual core 1.73 GHz处理器和2 GB内存的PC机上实现本文算法。图10对Lena(60×60)放大2倍，Lena帽檐处的锯齿非常少。放大同样倍数时，本文算法能够更好的保持图像边缘的尖锐特征。

图10 Lena放大2×2结果对比图Fig.10 Comparison of the results of Magnifying Lena by 2×2

图11是三角形 (60×60)放大2倍的结果。可以发现，本文推荐的方法在消除插值后的锯齿方面非常有效。

图11 三角形放大2×2结果的对比图Fig.11 Comparison of the results of magnifying triangle by 2×2

本文用 MSE(Mean Squared Error)［9，12］，PSNR(Peak Signal to Noise Ratio)［13］定量分析插值效果，如表1和表2。

表1 Lena，Beach，Triangle的MSE值Table 1 MSE of Lean，Beach and Triangle

表2 Lena，Beach，Triangle的PSNR值Table 2 MSE of Lean，Beach and Triangle

表1和表2分别是最近邻 (NN)，双线性(BI)，双三次 (BC)，Muhammad方法 (MU)和本文方法 (PR)插值 Lena(64×64)，三角形(60×60)和beach(60×60)后MSE和PSNR的数据统计，数据已分别被归一化到0～70和0～30。图12和图13分别是它们的MSE和PSNR的柱状描述图。

对同一幅图用不同的方法插值放大相同的倍数，MSE越小，PSNR越大，则该种方法的效果越好。由表1，2和图12，13知本文方法比最近邻、双线性、双三次和Muhammad's方法效果好。更多实验结果见图14，15。

5 总结与展望

本文提出了一种基于几何分类的自适应的图像插值方法放大图像。该方法最重要的贡献是提出了八个方向的割线来判断插值单元的分类，特别是斜对角方向，并基于未知像素点所属插值单元的几何分类插值图像。本文方法保持插值后图像的边缘走向和宽度，保证图像边缘的尖锐特征，从而提高插值图像的质量。

本文方法更准确的对插值单元进行几何分类，并根据未知像素点周围最近邻的已知像素点插值。因此，能够更好的保持图像尖锐特征，提高插值图像的质量。进一步的工作是将本文方法扩展到视频放大。

［1］LI X，ORCHARD M T.New edge-directed interpolation［J］.IEEE Transactions on Image Processing，2001，10(10):1521－1527.

［2］MORSE B S，SCHWARTZWALD D.Isophote-based interpolation［C］∥Proc IEEE Int Conf on Image Processing，1998，3:227－231.

［3］FATTAL R.Image upsampling via imposed edges statistics［C］∥SIGGRAPH，2007，26(3):95－102.

［4］THURNHOFER S，MITRA S.Edge-enhanced image zooming［J］.Optical Engineering，1996，35(7):1862 －1870.

［5］SUN J，XU Z B，SHUM H Y.Image super-resolution using gradient profile prior［C］∥CVPR，2008.

［6］BATTIATO S，GALLO G，STANCO F.A New Edge-A-daptive Zooming Algorithm for Digital Images［C］∥Proc Signal Processing and Communication，2000:144－149.

［7］SHAN Q，LI Z R，JIA J Y，et al.Fast image/video upsampling［J］.ACM Transactions on Graphics，2008，27(5):153－159.

［8］KOPF J，COHEN M，LISCHINSKI D，et al.Joint bilateral upsampling［J/OL］.ACM Transactions on Graphics，2007，26(3):96［2010 － 05 － 19］.http:∥doi.acm.org/10.1145/1275808.1276497.

［9］SAJJAD M，KHATTAK N，JAFRI N.Image magnification using adaptive interpolation by pixel level data-dependent geometrical shapes［J］.International Journal of Computer Science and Engineering，2007:118－127.

［10］UNSER M，ALDROUBI A，EDEN M.Fast B-spline transforms for continuous image representation and interpolation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1991，13(3):277 －285.

［11］KEYS R.Cubic convolution interpolation for digital image processing ［J］.IEEE Trans Acoustics，Speech，Signal Processing，1981，29(6):1153－1160.

［12］MALGOUYRES F，GUICHARD F.Edge direction preserving image zooming:A mathematical and numerical analysis［J］.Society for Industrial and Applied Mathematics，2001，39(1):1－37.

［13］YOUNGJOON C，SEONGJAI K.Error-amended sharp edge schemes for image interpolation［C］∥ICIP，2006:701－704.