基于密切多项式近似的多项式插值算法框架

doi:10.11772/j.issn.1001-9081.2015.08.2266

计算机应用 ›› 2015, Vol. 35 ›› Issue (8): 2266-2273.DOI: 10.11772/j.issn.1001-9081.2015.08.2266

基于密切多项式近似的多项式插值算法框架

赵小乐¹, 吴亚东¹, 张红英², 赵静³

1. 西南科技大学计算机科学与技术学院, 四川绵阳 621010;
2. 西南科技大学信息工程学院, 四川绵阳 621010;
3. 四川大学计算机学院, 成都 610045

收稿日期:2015-03-06 修回日期:2015-03-24 出版日期:2015-08-10 发布日期:2015-08-14
通讯作者: 吴亚东(1979-),男,河南周口人,教授,博士,CCF会员,主要研究方向:图形图像处理、信息可视化、人机交互,wyd028@163.com
作者简介:赵小乐(1987-),男,四川南部人,硕士研究生,CCF会员,主要研究方向:数字图像处理; 张红英(1976-),女,四川德阳人,教授,博士,主要研究方向:数字图像处理; 赵静(1991-),女,四川隆昌人,硕士研究生,主要研究方向:数字图像处理。
基金资助:
国家自然科学基金资助项目(61303127);国家科技支撑计划项目(2013BAH32F01);四川省科技厅科技支撑计划项目(2014SZ0223);四川省教育厅重点项目(13ZA0169);中国科学院"西部之光"人才培养计划项目(13ZS0106);西南科技大学创新基金资助项目(15ycx053)。

Polynomial interpolation algorithm framework based on osculating polynomial approximation

ZHAO Xiaole¹, WU Yadong¹, ZHANG Hongying², ZHAO Jing³

1. School of Computer Science and Technology, Southwest University of Science and Technology, Mianyang Sichuan 621010, China;
2. School of Information Engineering, Southwest University of Science and Technology, Mianyang Sichuan 621010, China;
3. College of Computer Science, Sichuan University, Chengdu Sichuan 610045, China

Received:2015-03-06 Revised:2015-03-24 Online:2015-08-10 Published:2015-08-14

摘要/Abstract

摘要：

多项式插值技术是近似理论中一种常见的近似方法,被广泛用于数值分析、信号处理等领域。但传统的多项式插值技术大多是基于数值分析与实验结果相结合得到的,没有统一的理论描述和规律性的解决方案。为此,根据密切多项式近似理论为图像的多项式插值算法提出一个统一的理论框架。密切多项式近似的理论框架包括采样点数目、密切阶数和导数近似规则三个部分,它既可以用于分析现有的多项式插值算法,也可以用于开发新的多项式插值算法。分析了主流多项式插值技术在密切多项式近似理论框架下的表现形式,并以四点二阶密切多项式插值算法为例详细描述了利用密切多项式插值的理论框架开发新的多项式插值算法的一般流程。理论分析和数值实验表明大多数主流插值算法都属于密切多项式插值算法,它们的处理效果与采样点数目、密切阶数和导数近似规则有紧密的关系。

关键词: 密切多项式, 导数近似规则, 密切阶数, 多项式插值, 信号处理

Abstract:

Polynomial interpolation technique is a common approximation method in approximation theory, which is widely used in numerical analysis, signal processing, and so on. Traditional polynomial interpolation algorithms are mainly developed by combining numerical analysis with experimental results, lacking of unified theoretical description and regular solution. A uniform theoretical framework for polynomial interpolation algorithm based on osculating polynomial approximation theory was proposed here. Existing interpolation algorithms could be analyzed and new algorithms could be developed under this framework, which consists of the number of sample points, osculating order for sample points and derivative approximation rules. The presentation of existing mainstream interpolation algorithms was analyzed in proposed framework, and the general process for developing new algorithms was shown by using a four-point and two-order osculating polynomial interpolation. Theoretical analysis and numerical experiments show that almost all mainstream polynomial interpolation algorithms belong to osculating polynomial interpolation, and their effects are strongly related to the number of sampling points, order of osculating, and derivative approximation rules.

Key words: osculating polynomial, Derivative Approximation Rule (DAR), osculating order, polynomial interpolation, signal processing

中图分类号:

赵小乐, 吴亚东, 张红英, 赵静. 基于密切多项式近似的多项式插值算法框架[J]. 计算机应用, 2015, 35(8): 2266-2273.

ZHAO Xiaole, WU Yadong, ZHANG Hongying, ZHAO Jing. Polynomial interpolation algorithm framework based on osculating polynomial approximation[J]. Journal of Computer Applications, 2015, 35(8): 2266-2273.

参考文献

[1] MEIJERING E. A chronology of interpolation: from ancient astronomy to modern signal and image processing [J]. Proceedings of the IEEE, 2002, 90(3): 319-342.
[2] BURDEN R L, FAIRES J D. Numerical analysis [M]. 7th ed. Beijing: Higher Education Press, 2001:104-165.
[3] GONZALEZ R C, WOODS R E. Digital image processing [M]. RUAN Q, RUAN Y, translated. 3rd ed. Beijing: Publishing House of Electronics Industry, 2011: 36-38. (GONZALEZ R C, WOODS R E. 数字图像处理 [M]. 阮秋琦, 阮宇智, 译. 3版. 北京: 电子工业出版社, 2011: 36-38.)
[4] NIEMITALO O. Polynomial interpolators for high-quality resampling of oversampled audio [EB/OL]. [2013-12-24]. http://yehar.com/blog/wp-content/uploads/2009/08/deip.pdf.
[5] LEHMANN T M, GONNER C, SPITZER K. Survey: interpolation methods in medical image processing [J]. IEEE Transactions on Medical Imaging, 1999, 18(11): 1049-1075.
[6] PHILIPPE T, THIERRY B, UNSER M. Image interpolation and resampling [EB/OL]. [2014-02-27]. http://bigwww.epfl.ch/publications/thevenaz9901.pdf.
[7] HER I, YUAN C T. Resampling on a pseudohexagonal grid [J]. CVGIP Graphical Models and Image Processing, 1994, 56(4): 336-347.
[8] FREEDMAN G, FATTAL R. Image and video upscaling from local self-examples [J]. ACM Transactions on Graphics, 2011, 30(2): Article No. 12.
[9] KIM K I, KWON Y. Single-image super-resolution using sparse regression and natural image prior [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 32(6): 1127-1133.
[10] GEORGIS G, LENTARIS G, REISIS D. Single-image super-resolution using low complexity adaptive iterative back-projection [C]//DSP 2013: Proceedings of the 18th International Conference on Digital Signal Processing. Piscataway: IEEE, 2013: 1-6.
[11] YU J, GAO X, TAO D, et al. A unified learning framework for single image super-resolution [J]. IEEE Transactions on Networks and Learning Systems, 2014, 25(4): 780-792.
[12] LI X, ORCHARD M T. New edge-directed interpolation [J]. IEEE Transactions on Image Processing, 2001, 10(10): 1521-1527.
[13] ARÀNDIGA F, YÁÑEZ D F. Cell-average multiresolution based on local polynomial regression: application to image processing [J]. Applied Mathematics and Computation, 2014, 245: 1-16.
[14] BOYD J P. Convergence and error theorems for Hermite function pseudo-RBFs: interpolation on a finite interval by Gaussian-localized polynomials [J]. Applied Numerical Mathematics, 2015, 87: 125-144.
[15] 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.
[16] KEYS R. Cubic Convolution interpolation for digital image processing [J]. IEEE Transactions on Speech and Signal Processing, 1981, 29(6): 1153-1160.
[17] McKINLEY S, LEVINE M. Cubic spline interpolation [J]. Numerical Mathematics: A Journal of Chinese Universities, English Series, 1999, 64(1):44-56.
[18] HOU H S, ANDREWS H. Cubic splines for image interpolation and digital filtering [J]. IEEE Transactions on Acoustics, Speech and Signal Processing, 1978, 26(6): 508-517.
[19] de BOOR C, HOLLIG K, SABIN M. High accuracy geometric Hermite interpolation [J]. Computer Aided Geometric Design, 1987, 4(4): 269-278.
[20] BERRUT J-P, TREFETHEN L N. Barycentric Lagrange interpolation [J]. SIAM Review, 2004, 46(3): 501-517.
[21] SHARIFI M, SOLEYMANI F, KHAN M, et al. On two-point Hermite interpolation: an application of Newton's theorem [J]. World Applied Sciences Journal, 2011, 13(12): 2451-2454.
[22] REICHENBACH S E, GENG F. Two-dimensional cubic convolution [J]. IEEE Transactions on Image Processing, 2003, 12(8): 857-865.
[23] SHI J, REICHENBACH S E. Image interpolation by two-dimensional parametric cubic convolution [J]. IEEE Transactions on Image Processing, 2006, 15(7): 1857-1870.
[24] WANG Z, BOVIK A C, SHEIKH H R, et al. Image quality assessment: from error visibility to structural similarity [J]. IEEE Transactions on Image Processing, 2004, 13(4): 600-612.
[25] CHEN M-J, BOVIK A C. No-reference image blur assessment using multiscale gradient [J]. EURASIP Journal on Image and Video Processing, 2011, 2011: 3.
[26] SILVA E A, PANETTA K, AGAIAN S S. Quantifying image similarity using measure of enhancement by entropy [EB/OL]. [2014-06-21]. http://citeseerx.ist.psu.edu/viewdoc/downloaddoi=10.1.1.160.6126&rep=rep1&type=pdf.

基于密切多项式近似的多项式插值算法框架

Polynomial interpolation algorithm framework based on osculating polynomial approximation

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	孙鹏, 肖经, 赵海盟, 刘帆, 晏磊, 赵红颖. 基于DSP的无人机遥感影像SIFT算法设计与实现[J]. 计算机应用, 2020, 40(4): 1237-1242.
[2]	卢光跃, 周亮, 吕少卿, 施聪, 苏可可. 基于图信号处理的无线传感器网络异常节点检测算法[J]. 计算机应用, 2020, 40(3): 783-787.
[3]	万永菁, 王博玮, 娄定风. 基于三维卷积神经网络的虫音特征识别方法[J]. 计算机应用, 2019, 39(9): 2744-2748.
[4]	王波, 刘德亮. 基于迭代自适应方法的近场源二维参数联合估计[J]. 计算机应用, 2019, 39(2): 523-527.
[5]	唐国斐, 周海芳, 谭庆平. 基于多核DSP的星载并行遥感图像压缩系统设计与实现[J]. 计算机应用, 2017, 37(5): 1246-1250.
[6]	魏昊, 徐庆. 基于冗余分组的轨迹摘要算法[J]. 计算机应用, 2017, 37(5): 1503-1506.
[7]	方建超, 毛雪松. 非等间隔采样信号傅里叶频谱分析方法[J]. 计算机应用, 2016, 36(2): 492-494.
[8]	黄胜兵, 郑启龙, 郭连伟. 分簇VLIW DSP上支持单双字模式选择的SIMD编译优化[J]. 计算机应用, 2015, 35(8): 2371-2374.
[9]	何婷婷, 彭元喜, 雷元武. 基于Goldschmidt算法的高性能双精度浮点除法器设计[J]. 计算机应用, 2015, 35(7): 1854-1857.
[10]	曹开田, 陈晓思, 朱文俊. 基于高阶统计量的压缩宽带频谱盲检测方法[J]. 计算机应用, 2015, 35(11): 3261-3264.
[11]	樊磊, 齐国清. 基于快速傅里叶变换的正弦信号频率高精度估计算法[J]. 计算机应用, 2015, 35(11): 3280-3283.
[12]	张毅刘钰然罗元. 基于视觉的手势识别方法及其在数字信号处理器上的实现[J]. 计算机应用, 2014, 34(3): 833-836.
[13]	索维毅赵荣彩姚远刘鹏. 面向DSP的超字并行指令分析和冗余优化算法[J]. 计算机应用, 2012, 32(12): 3303-3307.
[14]	黄一才郁滨. 基于蓝牙单芯片的复杂密码算法实现机制[J]. 计算机应用, 2012, 32(12): 3453-3455.
[15]	陈浩贾伟李思佳. 基于内插阵列变换的扩展传播算子实值算法[J]. 计算机应用, 2012, 32(08): 2109-2112.