发布时间: 2018-05-16 摘要点击次数: 全文下载次数: DOI: 10.11834/jig.170369 2018 | Volume 23 | Number 5 GDC 2017会议专栏

1. 山东财经大学大学计算机科学与技术学院, 济南 250014;
2. 山东省数字媒体技术重点实验室, 济南 250014;
3. 山东大学数学学院, 济南 250100
 收稿日期: 2017-07-11; 修回日期: 2017-10-27 基金项目: 国家自然科学基金项目（61373080，61332015，61672018，61402261，U1609218）；山东省高等学校优势科研人才团队培养计划；山东省重点研发计划（2016GSF120013，2017GGX10109） 第一作者简介: 杜宏伟(1992-), 男, 山东财经大学计算机应用技术专业硕士研究生, 主要研究方向为图像插值。E-mail:hongweidumr@163.com. 中图法分类号: TP391.41 文献标识码: A 文章编号: 1006-8961(2018)05-0766-12

# 关键词

Rational function interpolation algorithm based on gradient optimization
Du Hongwei1,2, Zhang Yunfeng1,2, Bao Fangxun3, Wang Ping1,2, Zhang Caiming1,2
1. School of Computer Science and Technology, Shandong University of Finance and Economics, Jinan 250014, China;
2. Shandong Provincial Key Laboratory of Digital Media Technology, Jinan 250014, China;
3. School of Mathematics, Shandong University, Jinan 250100, China
Supported by: National Natural Science Foundation of China(61373080, 61332015, 61672018, 61402261, U1609218)

# Abstract

Objective Image interpolation has become an active area of research in image processing, which can be easily extended to diverse applications ranging from medical imaging, remote sensing, aviation, animation production, and multimedia entertainment industries. A large number of image interpolation methods have been proposed by researchers. Generally, the interpolation methods can be divided into discrete and continuous methods. The adaptive interpolation methods based on discrete ideas can preserve the image structure of the edge. However, its performance in maintaining image details is less than satisfactory. The image cannot be amplified at any multiple by using discrete methods. And such methods are considerably time consuming. The interpolation methods based on continuous ideas can obtain rich image detail information but cannot maintain the image edge structure well. A new method of rational function image interpolation based on gradient optimization that has the advantages of the discrete and continuous methods is proposed. Method First, a novel bivariate rational interpolation function is constructed. With varying shape parameters, the function has different forms of expression, i.e., an organic unity of polynomial and rational models. The constructed ${{\rm{C}}^2}$ continuous rational function interpolation model has the advantages of the continuous method, in which the appearance of the jagged edge is reduced to some extent and becomes smooth. Second, according to the regional characteristics, the image is divided into the texture and smooth regions automatically using the isoline method. If the interpolation unit has at least an isoline, then the unit belongs to the texture region. If the interpolation unit does not have isolines, then the unit belongs to the smooth region. The smooth region is interpolated by the polynomial model, and the texture region is interpolated by the rational model. Finally, according to the isotropic Sobel operator, the image gradient of the interpolation unit is calculated and the direction of the texture region is determined. According to the image gradient and texture direction, the weight of the influencing factor of every interpolation unit is obtained. Then, the center of the image patch with different directions is optimized by convoluting with the weight matrix. Result A rational function image interpolation algorithm based on gradient optimization is proposed. The proposed algorithm is tested in three different aspects, namely, objective data, visual effect, and time complexity. Compared with the state-of-the-art interpolation algorithms, the average peak signal-to-noise ratio of the proposed method is 1.5, 0.36, 0.14, 0.28, 1.11, and 0.95 dB higher than that of the bicubic, RSAI, DFDF, NARM, NEDI, and Lee's algorithms, respectively. The average structural similarity of the proposed method is 0.0968, 0.007 2, 0.007 6, 0.005 2, 0.014 1, and 0.023 7 higher than that of the bicubic, RSAI, DFDF, NARM, NEDI, and Lee's algorithms, respectively. The image reconstructed by the proposed method has richer texture detail and sharper edge structure than that by the bicubic, RSAI, DFDF, NARM, NEDI, and Lee's algorithms. The average runtime of the proposed method is 7 s, which is 3.28, 5.26, 53.28, 43.53, and 418.54 times faster than that of DFDF, NEDI, RSAI, Lee's, and NARM algorithms. For texture images such as Baboon, Barbara, and Metal, the proposed method is highly competitive not only in objective data but also in visual effect. Conclusion We construct a bivariate rational interpolation function in this study. On the basis of this model, an image interpolation algorithm based on gradient optimization is presented, which is not only able to scale the reconstructed image indefinitely but also has a low time complexity. Experimental results show that the proposed algorithm preserves the image details and structures of the edge effectively and generates a high-quality interpolation image.

# Key words

image interpolation; rational function; gradient optimization; regional division; isoline method

# 1 双变量有理插值函数

$\varpi :\left[{a, b;c, d} \right]$为平面区域，$\{ ({x_i}, {y_j}, {f_{i, j}}),$ $i = 1, 2, \cdots, n;j = 1, 2, \cdots, m\}$为给定的数据集，其中$a = {x_1} < {x_2} < \cdots {x_n} = b$, $c = {y_1} < {y_2} < \cdots {y_m} = d$为节点空间。$f\left( {{x_i}, {y_j}} \right)$表示点$\left( {{x_i}, {y_j}} \right)$处的函数值，记为${f_{i, j}}$${d_{i, j}}$${e_{i, j}}$分别表示在点$\left( {{x_i}, {y_j}} \right)$偏导数$\frac{{\partial f\left( {x, y} \right)}}{{\partial x}}$$\frac{{\partial f\left( {x, y} \right)}}{{\partial y}}。令{h_i} = {x_{i + 1}} - {x_i}$${l_j} = {y_{j + 1}} - {y_j}$，对$xy$平面上任意点$\left( {x, y} \right) \in [{x_i}, {x_{i + 1}};{y_j}, {y_{j + 1}}]$，令$\theta = \frac{{x - {x_i}}}{{{h_i}}}$$\eta = \frac{{y - {y_j}}}{{{l_j}}}。记\Delta _{i, j}^{\left( x \right)} = \frac{{{f_{i + 1, j}} - {f_{i, j}}}}{{{h_i}}}$$\Delta _{i, j}^{\left( y \right)} = \frac{{{f_{i, j + 1}} - {f_{i, j}}}}{{{l_j}}}$

 $P_{i,j}^*\left( x \right) = \frac{{p_{i,j}^*\left( x \right)}}{{q_{i,j}^*\left( x \right)}};i = 1,2, \cdots ,n - 1$ (1)

 $\left\{ {\begin{array}{*{20}{c}} \begin{array}{l} p_{i,j}^*\left( x \right) = {\left( {1 - \theta } \right)^3}{f_{i,j}} + \theta {\left( {1 - \theta } \right)^2}V_{i,j}^*\left( x \right) + \\ {\theta ^2}\left( {1 - \theta } \right)W_{i,j}^*\left( x \right) + {\theta ^3}{f_{i + 1,j}}\\ q_{i,j}^*\left( x \right) = {\left( {1 - \theta } \right)^2} + \theta \left( {1 - \theta } \right){\alpha _{i,j}} + {\theta ^2}\\ V_{i,j}^* = \left( {{\alpha _{i,j}} + 1} \right){f_{i,j}} + {h_i}{d_{i,j}} + \\ \theta \left( {1 - \left( {1 - \theta } \right){\alpha _{i,j}}} \right)\left( {{f_{i + 1,j}} - {f_{i,j}} - {h_i}{d_{i,j}}} \right)\\ W_{i,j}^* = \left( {{\alpha _{i,j}} + 1} \right){f_{i + 1,j}} - {h_i}{d_{i,j}} - \\ \left( {1 - \theta } \right)\left( {1 - \theta {\alpha _{i,j}}} \right)\left( {{f_{i + 1,j}} - {f_{i,j}} - {h_i}{d_{i + 1,1}}} \right) \end{array}&{;{\alpha _{i,j}} > 0} \end{array}} \right.$

$P_{i, j}^ * \left( x \right)$满足$P_{i, j}^ * \left( x \right)$=${f_{i, j}}$$P_{i, j}^ * \left( {{x_{i+1}}} \right) = {f_{i + 1, j}}$$P{{_{i,j}^{*}}^{\prime }}\left( {{x}_{i}} \right)={{d}_{i,j}}$$P{{_{i,j}^{*}}^{\prime }}\left( {{x}_{i+1}} \right)={{d}_{i+1,j}}。当  {d_{i,j}} = \frac{{{h_{i - 1}}\Delta _{i,j}^{\left( x \right)} + {h_i}\Delta _{i - 1,j}^{\left( x \right)}}}{{{h_{i - 1}} + {h_i}}};\;i = 2,3, \cdots ,n - 1 (2) 则式(1)定义的插值函数在区间 \left[ {a,b} \right]$${{\rm{C}}^2}$连续，满足

 $\begin{array}{l} P''\left( {{x_i}} \right) = \frac{2}{{{h_{i - 1}} + {h_i}}}\left( {\Delta _{i,j}^{\left( x \right)} - \Delta _{i - 1,j}^{\left( x \right)}} \right)\\ \;\;\;\;\;\;\;\;\;\;\;i = 2,3, \cdots ,n - 1 \end{array}$ (3)

 ${P_{i,j}}\left( {x,y} \right) = \frac{{{p_{i,j}}\left( {x,y} \right)}}{{{q_{i,j}}\left( y \right)}}$ (5)

 $i = 1,2, \cdots n - 1;j = 1,2, \cdots m - 1$

 $\begin{array}{l} {p_{i,j}}\left( {x,y} \right) = {\left( {1 - \eta } \right)^3}P_{i,j}^*\left( x \right) + \eta {\left( {1 - \eta } \right)^2}{V_{i,j}} + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\eta ^2}\left( { - 1\eta } \right){W_{i,j}} + {\eta ^3}P_{i,j + 1}^*\left( x \right) \end{array}$

 ${q_{i,j}}\left( y \right) = {\left( {1 - \eta } \right)^2} + \eta \left( {1 - \eta } \right){\beta _{i,j}} + {\eta ^2}$

 ${V_{i,j}} = \left( {{\beta _{i,j}} + 1} \right)P_{i,j}^*\left( x \right) + {l_j}{\phi _{i,j}}\left( x \right) + {\phi _{i,j}}\left( {x,y} \right)$

 ${W_{i,j}} = \left( {{\beta _{i,j}} + 1} \right)P_{i,j + !}^*\left( x \right) - {l_j}{\phi _{i,j + !}}\left( x \right) + {\psi _{i,j}}\left( {x,y} \right)$

 $\begin{array}{l} {\phi _{i,s}}\left( x \right) = {\left( {1 - \theta } \right)^3}\left( {1 + 4\theta + 9{\theta ^2}} \right){e_{i,s}} + \\ \;\;\;\;\;\;\;{\theta ^3}\left( {6 - 8\theta + 3{\theta ^2}} \right){e_{i + 1,s}},s = j,j + 1 \end{array}$

 $\begin{array}{l} {\phi _{i,j}}\left( x \right) = \left( {\eta - \eta \left( {1 - \eta } \right)\left( {{\beta _{i,j}} + 1} \right)} \right)\left( {P_{i,j + 1}^*\left( x \right) - } \right.\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;P_{i,j}^*\left( x \right) - {l_j}\phi \left. {_{i,j}\left( x \right)} \right) \end{array}$

 $\begin{array}{l} {\psi _{i,j}}\left( x \right) = \left( {1 - \eta - \eta \left( {1 - \eta } \right)\left( {{\beta _{i,j}} + 1} \right)} \right)\left( {P_{i,j}^*\left( x \right)} \right.\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;P_{i,j + 1}^*\left( x \right) + {l_j}\phi \left. {_{i,j}\left( x \right)} \right) \end{array}$

 ${\beta _{i,j}} > 0$

 ${P_{i,j}}\left( {{x_r},{y_s}} \right) = f\left( {{x_r},{y_s}} \right)$

 $\frac{{\partial {P_{i,j}}\left( {{x_r},{y_s}} \right)}}{{\partial x}} = {d_{r,s}}$

 $\frac{{\partial {P_{i,j}}\left( {{x_r},{y_s}} \right)}}{{\partial y}} = {e_{r,s}}$

 $r = i,i + 1;s = j,j + 1$

# 2.1 自适应区域划分

 $\lambda = \frac{{\sum\limits_{r = - 1}^2 {\sum\limits_{s = - 1}^2 {{f_{i + r,j + s}}} - \left[ {\begin{array}{*{20}{c}} {{f_{i - 1,j - 1}} + {f_{i - 1,j + 2}} + }\\ {{f_{i + 2,j - 1}} + {f_{i + 2,j + 2}}} \end{array}} \right]} }}{{12}}$

# 2.3.2 权重的计算

$\left[{i, j} \right]$插值单元内，令$\left[{i + r, j + s} \right]$像素点对中心点优化的权重影响因子为${\varpi _{i + r, j + s}}, \left( {r, s = 0, 1, 2} \right)$$\left[{i + r, j + s} \right]处像素点与中心点的连线与纹理方向所在直线的较小夹角为{\theta _{i + r, j + s}}({\theta _{i + r, j + s}} \in [0, \pi /2])$${\varpi _{i + r, j + s}}$的计算公式为

 ${\varpi _{i + r,j + s}} = \frac{{\rm{ \mathsf{ π} }}}{{2 \times {\theta _{i + r,j + s}}}}$ (6)

 $f:{\varpi _{i + r,j + s}} \to {w_{i + r,j + s}};{w_{i + r,j + s}} \in \left[ {0,2} \right]$ (7)

$\left[{i, j} \right]$插值单元的权重系数矩阵为

 $\left( {\begin{array}{*{20}{c}} {{w_{i,j}}}&{{w_{i,j + 1}}}&{{w_{i,j + 2}}}\\ {{w_{i + 1,j}}}&{{w_{i + 1,j + 1}}}&{{w_{i + 1.j + 2}}}\\ {{w_{i + 2,j}}}&{{w_{i + 2,j + 1}}}&{{w_{i + 2,j + 2}}} \end{array}} \right)$

 $\begin{array}{*{20}{c}} {{f_{i + 1,j + 1}} = \frac{{\sum\limits_{r = 0}^2 {\sum\limits_{s = 0}^2 {{f_{i + r,j + s}} \times {w_{i + r,j + s}}} } }}{{\sum\limits_{r = 0}^2 {\sum\limits_{s = 0}^2 {{w_{i + r,j + s}}} } }}}\\ {r,s = 0,1,2} \end{array}$ (8)

# 3 实验结果与分析

Table 2 PSNR and SSIM Comparison of Different Methods

 图像 双三次插值 RSAI DFDF NARM NEDI Lee’s 本文算法 Baboon PSNR/dB 21.60 22.93 22.62 22.55 21.40 22.02 23.02 SSIM 0.768 4 0.867 1 0.855 6 0.862 6 0.864 0 0.848 3 0.870 4 Barbara PSNR/dB 23.18 22.98 24.44 23.35 22.21 22.70 24.54 SSIM 0.795 4 0.854 8 0.871 3 0.858 7 0.842 9 0.844 3 0.875 3 Boat PSNR/dB 24.52 25.98 26.08 26.22 25.41 25.49 26.24 SSIM 0.811 0 0.891 6 0.888 8 0.893 0 0.889 0 0.881 3 0.892 5 Dollar PSNR/dB 18.06 18.95 19.07 18.76 18.91 18.29 19.05 SSIM 0.716 9 0.802 2 0.802 2 0.797 0 0.803 0 0.778 6 0.805 2 Fence PSNR/dB 19.34 20.55 21.30 21.35 19.48 20.55 21.38 SSIM 0.621 4 0.700 8 0.713 4 0.725 8 0.674 1 0.695 1 0.714 9 Houses PSNR/dB 20.89 22.80 22.96 23.34 22.56 22.31 22.89 SSIM 0.829 0 0.908 4 0.909 7 0.916 2 0.904 4 0.902 4 0.909 4 Metal PSNR/dB 13.88 14.81 14.75 14.05 14.78 13.64 15.07 SSIM 0.426 7 0.638 3 0.626 1 0.626 4 0.637 0 0.584 9 0.662 8 Rail PSNR/dB 21.82 22.86 23.07 22.78 22.54 22.28 23.16 SSIM 0.734 7 0.781 4 0.778 2 0.779 4 0.776 8 0.764 9 0.782 5 Sky PSNR/dB 28.42 29.75 29.69 29.87 27.43 29.19 29.82 SSIM 0.845 3 0.909 3 0.908 1 0.910 4 0.903 0 0.901 1 0.911 4 Wall PSNR/dB 23.29 24.88 24.70 24.97 24.24 24.03 24.87 SSIM 0.793 0 0.883 2 0.879 8 0.887 6 0.874 2 0.871 4 0.884 9 平均 PSNR/dB 21.50 22.64 22.86 22.72 21.89 22.05 23.00 SSIM 0.734 1 0.823 7 0.823 3 0.825 7 0.816 8 0.807 2 0.830 9 注：加粗数据表示与其他算法相比，该算法具有最高的PSNR或SSIM值。

Table 3 The Run Time Comparison of Different Methods

 /s 双三次插值 NEDI DFDF RSAI NARM Lee’s 本文算法 Baboon 1.49 23.2 12.4 197.6 1547.0 162.6 4.8 Barbara 1.16 19.4 12.3 202.6 1411.1 162.3 3.7 Boat 1.14 29.0 18.6 312.5 2496.4 263.0 5.5 Dollar 1.13 19.6 12.4 205.6 1526.6 165.8 3.7 Fence 1.12 2.7 1.8 26.3 139.0 22.42 0.5 Houses 1.13 20.1 12.3 207.7 1550.7 162.1 3.7 Metal 1.14 21.0 12.6 191.4 1702.1 163.2 3.8 Rail 1.14 4.6 3.2 43.1 246.2 40.0 0.9 Sky 1.20 28.7 19.0 310.3 2408.5 244.4 5.5 Wall 1.14 30.2 18.9 311.7 2751.5 255.4 5.6 平均 1.18 19.85 12.35 200.88 1577.91 164.1 3.77

# 参考文献

• [1] Keys R. Cubic convolution interpolation for digital image processing[J]. IEEE Transactions on Acoustics, Speech, and Signal Processing, 1981, 29(6): 1153–1160. [DOI:10.1109/TASSP.1981.1163711]
• [2] Hou H, Andrews H. Cubic splines for image interpolation and digital filtering[J]. IEEE Transactions on Acoustics, Speech, and Signal Processing, 1978, 26(6): 508–517. [DOI:10.1109/TASSP.1978.1163154]
• [3] Yang Z X, Lu F, Guan L T. Image enlargement and reduction with arbitrary accuracy through scaling relation of B-spline[J]. Journal of Computer-Aided Design & Computer Graphics, 2001, 13(9): 824–827. [杨朝霞, 逯峰, 关履泰. 用B样条的尺度关系来实现图像任意精度的放大缩小[J]. 计算机辅助设计与图形学学报, 2001, 13(9): 824–827. ] [DOI:10.3321/j.issn:1003-9775.2001.09.012]
• [4] Carrato S, Tenze L. A high quality 2 x image interpolator[J]. IEEE Signal Processing Letters, 2000, 7(6): 132–134. [DOI:10.1109/97.844630]
• [5] Li X, Orchard M T. New edge-directed interpolation[J]. IEEE Transactions on Image Processing, 2001, 10(10): 1521–1527. [DOI:10.1109/83.951537]
• [6] Zhang L, Wu X L. An edge-guided image interpolation algorithm via directional filtering and data fusion[J]. IEEE Transactions on Image Processing, 2006, 15(8): 2226–2238. [DOI:10.1109/TIP.2006.877407]
• [7] Zhang X J, Wu X L. Image interpolation by adaptive 2-D autoregressive modeling and soft-decision estimation[J]. IEEE Transactions on Image Processing, 2008, 17(6): 887–896. [DOI:10.1109/TIP.2008.924279]
• [8] Hung K W, Siu W C. Robust soft-decision interpolation using weighted least square[J]. IEEE Transactions on Image Processing, 2012, 21(3): 1061–1069. [DOI:10.1109/TIP.2011.2168416]
• [9] Dong W S, Zhang L, Lukac R, et al. Sparse representation based image interpolation with nonlocal autoregressive modeling[J]. IEEE Transactions on Image Processing, 2013, 22(4): 1382–1394. [DOI:10.1109/TIP.2012.2231086]
• [10] Lee S J, Kang M C, Uhm K H, et al. An edge-guided image interpolation method using Taylor series approximation[J]. IEEE Transactions on Consumer Electronics, 2016, 62(2): 159–165. [DOI:10.1109/TCE.2016.7514715]
• [11] Zhang Y F, Zhang C M, Chi J, et al. An algorithm for enlarged image enhancement[J]. ICIC Express Letters, 2009, 3(3): 669–674.
• [12] Duan Q, Zhang H L, Zhang Y F, et al. Bounded property and point control of a bivariate rational interpolating surface[J]. Computers & Mathematics with Applications, 2006, 52(6-7): 975–984. [DOI:10.1016/j.camwa.2006.04.021]
• [13] Zhang Y F, Bao F X, Zhang C M, et al. Local shape control of a bivariate rational interpolating surface with mixing conditions[C]//The 8th International Symposium on Voronoi Diagrams in Science and Engineering. Qingdao, China: IEEE, 2011: 200-205. [DOI:10.1109/ISVD.2011.34]
• [14] Sun Q H, Bao F X, Zhang Y F, et al. A bivariate rational interpolation based on scattered data on parallel lines[J]. Journal of Visual Communication and Image Representation, 2013, 24(1): 75–80. [DOI:10.1016/j.jvcir.2012.11.003]
• [15] Yao X X, Zhang Y F, Ning Y, et al. Multi-scale feature image interpolation based on a rational fractal function[J]. Journal of Image and Graphics, 2016, 21(4): 482–489. [姚勋祥, 张云峰, 宁阳, 等. 多尺度有理分形的图像插值算法[J]. 中国图象图形学报, 2016, 21(4): 482–489. ] [DOI:10.11834/jig.20160410]
• [16] Liu Y F, Zhang Y F, Guo Q, et al. Image interpolation based on weighted and blended rational function[M]//Jawahar C V, Shan S G. Computer Vision-ACCV 2014 Workshops. Cham: Springer, 2015: 78-88. [DOI:10.1007/978-3-319-16631-5_6]
• [17] Zhao Q J, Hu M, Tan J Q. Many-knot splines technique for image interpolation[J]. Journal of Image and Graphics, 2006, 11(5): 667–671. [赵前进, 胡敏, 檀结庆. 图像插值的多结点样条技术[J]. 中国图象图形学报, 2006, 11(5): 667–671. ] [DOI:10.3969/j.issn.1006-8961.2006.05.010]
• [18] Wen Y H, Liu Y J. An isoline generating algorithm based on Delaunay[C]//Proceedings of the 20102nd International Conference on Computer Engineering and Technology. Chengdu, China: IEEE, 2010: V7-173-V7-176. [DOI:10.1109/ICCET.2010.5485290]