插值算法（通用7篇）
插值算法 篇1
图像插值的直接后果是原来由较少的像素所刻划的图像变成了由较多的像素所刻划的图像。常用的经典图像插值方法有最近邻插值, 双线性插值, 双三次插值三种, 也是经典的插值方法。图像插值实际上是图像的几何变换, 一个几何运算需要两个独立的算法, 一个用来描述空间变换本身, 即描述每个像素从其初始位置到终止位置的“移动”, 一个用来描述空间变换之后的图像灰度的插值计算。
1 算法原理介绍
在几何变换中, 如果我们将输入图像定义为f (x, y) , 把输出图像定义为g (x, y) , 那么, 几何变换就是一个从f到g的映射。在实际中我们可以通过空间变换来建立原像素坐标 (x, y) 和结果像素坐标 (x′, y′) 之间的空间映射, 这实际上是像素灰度值的位移。实践中, 我们常常使用的是逆映射变换, 它在计算上比较有效和方便。
1.1 最近邻插值法
最近邻插值, 也称零阶插值, 是最简单的插值算法。它输出的像素灰度值等于距离它映射到的位置最近的输入像素的灰度值。新图像的象素颜色是原图像中与创造的象素位置最接近象素的颜色。
1.2 双线性插值法
双线性插值, 也称一阶插值, 它是三次线性插值的结果。线形插值如图3所示, 如果已经知道了两点x0, x2处的函数值f (x0) , f (x) 2, 现在要求x1处的函数值f (x) 1。我们假设函数是线形的, 利用几何知识可以知道:
在图象处理中需要将线形插值扩展到二维的情况, 即采用双线形插值。如图就是先在A, B间线性插值得到E, C, D间线性插值得到F, 然后在E, F间线性插值得到最后的结果G。现在我们用坐标映射的方法来描述, 对于一个目的像素, 设置坐标通过反向变换得到的浮点坐标为G (i+u, j+v) , 其中i, j均为非负整数, u, v为[0, 1) 区间的浮点数, 则这个像素的值f (i+u, j+v) 可由原图像中坐标为A (i, j) , B (i+, 1j) , C (i, j+1) , D (i+1, j+1) 所对应的周围四个像素的值决定, 即:
1.3 双三次插值法
它考虑的是一个浮点坐标 (i+u, j+v) 周围的16个邻点加权平均得到, 目标像素f (i+u, j+v) 可以通过一下的过程来得到:
首先确立16个邻点的坐标, 可以构成一个点的矩阵[B], 如下:
然后在另外构造两个向量, 一个行向量[A]和一个列向量[C]:
其中, S (x) 是对Sin (x*Pi) /x的逼近 (Pi是圆周率—π) 。
2 仿真结果
本仿真实验主要是对灰度图像进行的插值, 才用了128×128尺寸的图像作为源图像进行插值放大两倍, 并与已知256×256原始高分辨率图像进行对比, 从而得出三种经典插值算法在算法运行时间, 均方差, 峰值性噪比方面的差异。
最近邻插可以很明显的看出有很明显的锯齿状, 细节部分很不清晰。双线性插值质量更高一些, 没有出现图像像素不连贯的现象, 锯齿难以觉察, 但是图像的边缘有轻微的模糊现象。双三次插值结果是三种插值方法中效果最好的, 它能够产生比双线性插值更加平滑的边缘。从实验数据来看, 算法的运行时间是依次递增, 均方误差逐次递减, 峰值信噪比依次递增。
3 结语
最近邻插值会增加图像的可见锯齿, 优点是速度快。双线性插值效果要好于最近邻插值法, 只是程序相对复杂一些, 运行时间也稍长些, 计算量大, 但缩放后图像质量高, 不会出现像素值不连续的情况。由于双线性插值具有低通滤波器的性质, 使高频分量受损, 所以可能会使图像轮廓在一定程度上变得模糊。双三次插值能够克服以上两种方法的不足, 计算的精度很高, 但是计算量也很大。
参考文献
[1]陈书海, 傅录祥.实用数字图像处理[M].科学出版社, 2005.
[2]何东健.数字图像处理[M].西安电子科技大学出版社, 2003.
[3]李将云.图像处理中的插值和缩放若干技术研究[D].浙江大学, 2002.
[4]艾海舟.数字图像处理[Z].2000.
插值算法 篇2
实际中许多多项式插值问题不仅要求在各插值节点上插值多项多式函数与被插函数的函数值相等，而且还要求对应的点的导数值也相等。在所有节点上具有一阶导数信息，且要求插值函数与被插函数对应的同阶导数相等的Hermite插值问题研究已经有了良好的算法设计[1,2]，也有学者研究不是所有的节点上都要求插值函数与被插函数导数值相等的问题[3,4]。本文提出的插值节点有二阶导数信息的Hermite插值算法 (简称CMHA) ，研究了插值节点插值多项式与被插函数函数相等、对插值节点上一部插值多项式与被插函数有一阶导数或二阶导数值相等的情况。
2、插值节点具有不同阶导数信息的Hermite插值算法
2.1问题描述
f (x) ∈C2[a, b], 设x0<x1<x2<x3…<xs是[a, b]上s+1个节点。
其中h≤m≤s；设n=s+m+h+2；要求次数≤n插值多项式H (x) ，使之满足插值条件：
可以证明满足条件（1）的次数≤n多项式H (x) 是唯一的。因（1）中包含n+1个条件，所以能够确定次数≤n的代数多项式H (x) ，用反证法，假设P (x) 与H (x) 一样均满足条件，且次数≤n，于是： ( (x) =H (x) -P (x) 也是次数≤n的多项式，但 ( (x) 关于x0, …xh是3重零点，xh+1, …xm是2重零点，xm+1, …xs是1重零点，共n+1个零点，故 ( (x) ≡0，唯一性得证。
2.2 H (x) 的构造
其中αβγ满足表1 (δki是Kronecker记号) 条件，就可满足插值条件（1）。
由表1推得
将 (3) - (8) 代入 (2) 得相应的插值多项式。
2.3 CMHA算法描述
（一）输入x0, x1，……，xs;y0, y1，……，ys;u0, u1, ……, um;v0, v1, ……, vh, H=0
（二）对k=0, 1, 2, …h
用 (5) (7) (8) 计算αk (x) , βk (x) , γk (x)
（三）对k=h+1, …m
用 (4) (6) 计算αk (x) , βk (x)
（四）对k=m+1, …s
用 (3) 计算αk (x) ；%H=H+αk (x) yk
（五）输出H
3、实验结果
对函数在区间[0, 5]上任给出10个不等距节点上的函数值、一阶和二阶导数值（具有六位有效数字，空白格表示该点处未给出导数信息），将有二阶和一阶导数的点排到最前面。见表2。
在[0, 4.27]任选4个不等距节点如x列，利用CMHA算法写出C程序计算在这些节点处的近似值（CMHA列），f (x) 列是原函数相应的值。如表3。
4、结束语
实验结果可以发现，CMHA方法在内插值时精度可达到一定要求，但CMHA与IDIH[4]比较有些点的精度反而有些下降，这是由于CMHA对应的多项式次数比次数高（上实例IDIH对应是14次插值多项式，而CMHA是18次数插值式多项式）造成的，这说明高次插值多项式尽管在插值节点及附近与原函数f有更好的近似，但也会出现波动差异较大的地方。
可以证明当f (x) ∈C n+1[a, b]，x∈[a, b]、n=s+m+h+2，其截断误差为：其中ξ∈[a, b]
摘要：给出了在插值节点上具有函数信息和二阶导数信息的Hermite插值多项式的构造方法, 生成了相应的算法, 并指出了相应的截断误差公式。
关键词：多项式插值,导数,截断误差
参考文献
[1]徐士良, C常用算法程序集[M], 清华大学出版社, 1996.
[2]关治、陈景良, 数值计算方法[M], 清华大学出版社, 1990.
[3]孙英慧、杨柳, 基于Hermite算法的曲线拟合[J], 长春师范学院学报, 2009, 28 (4) :72-75.
[4]高红, 插值节点不完全具有导数信息的Hermite插值算法[J], 山西广播电视大学学报, 2010, 15 (2) :72-75.
[5]王仁宏, 数值逼近[M], 高等教育出版社, 1999.
观测迭代的插值滤波算法 篇3
虽然卡尔曼滤波器(KF)能够很好的处理线性滤波问题。然而在现实世界中我们所面对的问题大多是非线性问题。为解决非线性滤波问题,众多学者进行了大量的研究并取得了不少的成果。在众多研究成果中较为典型的算法有扩展卡尔曼滤波器(Extended Kalman filter),Unscented卡尔曼滤波(Unscented Kalman filter),基于Bayes理论的粒子滤波器(Particle filter),和基于Stirling,s内插公式的插值滤波器(DDF)。
EKF简单容易实现特点使其被大量应用到现实工程中,但EKF实现性差,估计精度差的缺点限制了其进一步的应用。PF算法虽然有着较高的跟踪精度但其庞大的计算量和粒子退化问题限制其在现实工程应用。2000年由Magnus Nrgaard等人提出的DDF算法,该算法和EKF相类似:算法简单,容易实现。但与EKF相比DDF采用Stirling插值公式进行线性化处理,避免了求解微分应算过程,在非线性程度较高的系统中DDF的跟踪精度要好于EKF。
但标准DDF算法被应用到初始化误差大或弱观测性条件下的非线性系统,常出现收敛速度慢,稳定性不足及跟踪精度低等问题。为此本文对一阶DDF算法上进行改进。在一阶DDF观测更新过程中加入迭代过程取代近似条件估计用于量测预测数据更新。仿真结果表明该算法在大噪声,及初始误差较大的情况下有着更优的跟踪精度和收敛速度。
1插值滤波器
考虑如下非线性系统∑:
其中xk∈ℜn为n×1状态向量,yk∈ℜm为m×1观测向量。wk∈ℜq为q×1过程噪声,而vk∈ℜr为r×1观测噪声。并假设噪声序列均为高斯白噪声其均值和方差为:
DDF算法和EKF十分的相似,不同的是DDF采用Stirling插值公式对系统进行线性化处理而非泰勒公式,从而避免了求解Jacobin矩阵,在状态数据更新上和EKF完全一样,只是在对协方差进行更新的时候可以采取更为简单的方法:通过更新协方差的平方Cholesky因子来完成。DDF算法如下描述:
计算平方Cholesky因子:
其中Sx为x的协方差0P的平方Cholesky因子,Sw为过程噪声w的协方差Q的平方Cholesky因子,Sv为量测噪声v的协方差R的平方Cholesky因子。
sx,p表示为Sx的第p列,相同的定义其他几个因子则有下面等式:
上述式子中h为一区间长度参数在高斯环境下一般有h=3,xk+1为预测状态向量有下述式子计算得到:
Sx-(k+1)为平方Cholesky因子由(10)进行通过Householder三角变换转换得到:
量测数据更新:
Sv(k+1)也需要进行通过Householder三角变换转换。
则量测和状态的相关矩阵为:
计算增益进行数据更新:
在对协方差更新上注意到式子(9),(10),(12),(13)及(14)之间的关系则在协方差更新中有:
所以使用协方差的平方Cholesky因子(可以由(19)通过Householder三角变换转换得到)更新来取代协方差进行更新可以简化计算。
上述即为DDF算法,详细的推导过程可以参见文献。
2迭代内插滤波器
2.1观测迭代
DDF和EKF一样,在量测预测更新上由ˆy(k|k-1)=g(ˆx(k|k-1),k)得到,这样就由于使用ˆx(k|k-1)来代替x(k)从而无法避免的引入了对观测的误差,同时对非线性量测方程进行内插公式线性化的时候也不可避免的增加了观测的误差。
为了解决上述问题,本文在观测中加入一个迭代过程来取代单纯的近似条件均值估计,用于代替x(k)的xˆk,j通过迭代过程不断的逼近x(k)减小量测预测更新过程的误差,提高算法的鲁棒性及跟踪性能。
式子中的ey,j和ex,j有如下定义
算法通过上述条件不等式来判断xˆk,j是否达到精度要求从而判断是否结束本次迭代。迭代从xˆk,0开始直至满足不等式子要求,或者达到最大迭代次数N结束迭代,进入下一时刻的估计。
2.2 IDDF算法
本算法和DDF算法的最大差别在于量测更新,本算法通过迭代环节减小了量测更新的误差具体如下:
假设系统方程为(1)则:
1.初始化算法参数:j=1,Pk,j=Pk,xˆkj,=xˆk。
2.计算平方Cholesky因子:
3.状态和协方差计算:
4.量测及相关协方差更新:
5.计算增益进行数据更新:
6.定义如下等式:
7.判断是否结束迭代:
如果j≤N下不等式成立,则使j=j+1重复上述算法过程直至不等式不成立或j>N。
8.数据更新:在上述不等式不成立
当不等式于j>N依然成立时取:
上述即为IDDF算法,要注意的是如Sx,j+1等平方Cholesky因子必须要进行Householder三角变换转换。
2.3 IDDF收敛性
假设
由于Pk,j+1,Pk-,j及Pkv,jv为正定,则那么根据(36)式将有
在j=1,2,L<∞下成立。又因为Pk,j+1,Pk-,j的每个元素均有界,所以:
成立。则根据(36),(48)及(49)可以得到:
成立。与(47)矛盾。所以可知假设(47)不成立(50)成立。
假设κk,j→0当j>N时成立,则从(36)及(38)可以知道有:
成立,即说明随着迭代过程,算法是收敛的。和标准DDF算法比较,该算法通过修正量测提高对状态估计的精度,同时在初始化值和最优值相距较远时,算法自动校正状态及协方差矩阵以加快收敛速度。
由于Pk,j+1,Pk-,j及Pkv,jv为正定,则那么根据(36)式将有:
在j=1,2,L<∞下成立。又因为Pk,j+1,Pk-,j的每个元素均有界,所以:
成立。则根据(36),(48)及(49)可以得到:
成立。与(47)矛盾。所以可知假设(47)不成立(50)成立。
假设κk,j→0当j>N时成立,则从(36)及(38)可以知道有:
成立,即说明随着迭代过程,算法是收敛的。和标准DDF算法比较,该算法通过修正量测提高对状态估计的精度,同时在初始化值和最优值相距较远时,算法自动校正状态及协方差矩阵以加快收敛速度。
3仿真实验
假设如下非线性模型:
在上述模型中wk为高斯噪声其方差为Qk=diag⎡⎣0.220.32⎤⎦,时间间隔T=0.2s。xk中的变量分别表示为x方向的位移和速度,y方向的位移和速度。
其中量测包括方向角θk及方向角变化率θ&k,量测方程如下:
其中rk=xk2+yk2,nθk及nθ&k为独立高斯噪声其方差为Rk=diag⎡⎣0.120.82⎤⎦,对上述系统进行M=150独立实验仿真。
均方根误差为:
由下述仿真实验数据可以看出IDDF算法在精度和稳定性上的表现都要比DDF和EKF优秀。
4结论
DDF算法在应对非线性程度高的滤波问题上的不仅在精度上而且在稳定性都要优于EKF。在DDF基础上的改进算法IDDF其精度,稳定性则要好于DDF。IDDF虽然提高了算法的精度及稳定性,但其增加的迭代过程,将加大算法的计算负担。同时对DDF这中改进算法也只适用于高斯噪声的环境,在面对非高斯噪声环境也是无能为力。
摘要：针对非线性跟踪系统中由于弱观测性,大的初始化误差使的系统出现不稳定、跟踪收敛速度慢,鲁棒性能差的问题,本文在内插公式滤波器的基础上提出了基于观测迭代插值滤波器。该算法在插值滤波器基础上,利用观测迭代过程来取代单纯的近似条件估计进行预测,减小观测函数线性化所带来的误差影响具有更精确的状态和协方差估计性能。仿真结果表明该算法在大噪声和大初始化误差条件下拥有比传统算法更高的跟踪精度,和更快的收敛速度。
关键词：非线性滤波,插值滤波器,迭代插值滤波器
参考文献
[1]Kotecha,J.H,Djuric,P.M,Gaussian Particle Filtering[J].IEEE Transactions on Signal Processing.2003.
[2]Julier S J,Uhlmann J K.A New Method for The Nonlinear Transformation of Means and Covariances in Filters and Estimators[J].IEEE Transactions on Automatic Control,2000.
[3]Julier S J,Uhlmann J K.Unscented Filtering and Nonlinear Estimation[J].Proceedings of the IEEE.2004.
[4]袁泽建,郑南宁,贾新春.高斯-厄米特粒子滤波器[J].电子学报.2003.
[5]Ngarrd M,Poulsen N M,Ravn O.New Developments in State Estimation for Nonlinear System[J].Automatica.2000.
基于曲线插值算法的巷道自动建模 篇4
巷道系统是矿山三维虚拟场景的重要组成部分, 是构建数字矿山的基础。井下巷道纵横交错、错综复杂, 工作地点及资源条件不断变化, 如何立体、直观、准确地表现并反映井下巷道及其空间关系, 是矿山测绘科技工作者的重要研究课题, 也是煤矿安全、高效、合理开发的重要保障[1]。
由于每个矿井的实际巷道不同, 对矿井巷道用三维软件建模得出的模型不宜推广。本文基于对煤矿安全培训系统的研究, 编写出根据具体巷道数据信息生成不同矿井巷道的具体模拟系统。
1 巷道的网格模型
在三维图形程序设计中, 网格模型占有非常重要的地位, Direct3D支持的模型文件格式为*.X文件格式, *.X文件模型通常是由大量的三角形拼接成的网格 (mesh) 模型。
1.1 解析.X文件
三维模型建模软件很多, 而三维模型可以转换成Direct3D能够识别的数据文件格式 (后缀名为.X) , 这样在Diect3D中载入和渲染文件模型就很方便了。
对坐标系中的物体进行点采样 (Point Sample) , 这些采样点按一定顺序连接成为一系列的小平面 (三角形或共面的四边形, 五边形等) , 这些小平面称为图元 (Primitive) , 3D引擎会处理每一个图元, 称为一个独立的渲染单位。这样取样后的物体看起来像是由许许多多的三角形, 四边形或五边形组成的, 就像网一样, 称为一个网格 (Mesh) 。 纪录这些顶点数据和连线情况到一个文件中, 3D引擎读取这些数据, 依次渲染每一个图元, 就能在显示屏幕上再现物体。取样的点越多, 再现的物体也会越逼真, 要处理的数据量也越大。在D3D中, 纪录这些顶点数据和连线情况的文件称为X文件 (X File) 。它是以X作为文件名后缀的。.X文件主要是用来存储网格数据的, 它通常存储了三维模型的顶点坐标、颜色、法向量、纹理坐标以及动画帧等信息。
.X文件是由模板驱动 (Template-Driven) 的, 模板定义了如何存储一个数据对象, 这使得这种文件格式具有结构自由, 内容丰富, 易应用, 可移植性高等优点[2]。
1.2 编写.X文件自动生成模型
3ds Max或Maya等三维建模软件所制作的网格模型可导出为Direct3D所支持的.X文件模型, 利用三维建模工具制作的三维模型通常比较复杂, 即多边形数量很多, 而多边形数量越多, 图形渲染速度越慢, 所以在自动建模时, 在不明显影响视觉效果的前提下尽量减少多边形的数量。
一般来说巷道体的断面表现为梯形或直壁拱形, 其规律和断面点信息比较容易找出, 并且在尽量减少多边形数量而不影响视觉效果的前提下, 可以找出规律并按照矿井实际数据, 编写.X文件, 制作相对应的巷道网络结构, 提高了加载、渲染速度[3]。
2 巷道的三维建模及算法
巷道断面是巷道几何建模中的重要参数, 主要有拱形、矩形、梯形、斜梯形等形态, 本文是利用拱形断面来制作巷道模型的, 根据巷道底面中线上点的位置信息来求取巷道断面上点的位置信息, 从而应用Direct3D扩展库提供的函数来编程实现巷道自动建模。
2.1 拱形巷道断面
Direct3D中的坐标系是左手坐标系, 图1是初始拱形断面在Direct3D坐标系中的位置。
一个断面上设置12个点, 并给出这12个点的初始信息, 如图1所示, 其中undefined。
利用D3DX扩展函数库d3dx9.lib提供的D3DXMatrixRotationY ( ) 、D3DXMatrixScaling ( ) 、D3DXMatrixTranslation ( ) 等函数, 旋转、缩放、平移断面初始信息, 得到所需断面信息, 编程实现断面点信息的连接, 写好.X文件, 即可完成巷道的自动生成。
由图2可知, 在中线上加载两个断面可以生成一个直巷道, 但实际情况, 一个煤矿有许多不同的巷道。对于含分岔口的巷道, 作加载半断面处理, 即对于图1所示的拱形断面, 分半保存点信息, 点0至点5组成半断面, 点6至点11组成半断面。在分岔口处加载半断面即可构成巷道体, 如图3所示, 在A2-A, A-A1, B-B1, B-B2, C2-C, C-C1, D2-D, D-D1, E2-E, E-E1线上加载半断面, 所加载的半断面要由初始半断面经过平移、缩放、旋转得到, 加载上断面后, 写好.X文件, 巷道模型即可生成。为了点B1、B2处的拐弯过度的圆滑一些, 可以在A-A1与D-D1之间, C-C1与D-D2之间内插出几个半断面。内插的半断面可以根据改进的Bezier插值算法求出。
2.2 曲线插值算法
曲线Q (u) 有三个控制点P0, P1, P2, 控制点的坐标发生改变, 曲线的形状随之改变。
曲线以参数u (0≤u≤1) 来定义, 曲线上的每一个点都是通过一个三次多项式对每一个控制点进行比例调节来确定的, 曲线Q (u) 是由B样条曲线改进所得, undefined
插值曲线的矩阵形式:
undefinedundefined
利用曲线插值算法对巷道内插断面, 如图4所示, 内插断面的点U1, B, U2必须在巷道的中线上, 来保证巷道无缝连接[4]。
2.3 采用插值算法的效果
直接利用断面的加载生成的巷道模型的拐弯处很尖, 不符合实际。为了使模型更逼真一些, 采用曲线插值算法, 内插一些断面, 使巷道模型拐弯处过度的更圆滑一些。比较图5和图6可以看出采用插值算法后的效果。
3 结束语
Direct3D是一套非常优秀的高性能三维图形程序可编程接口, 它对游戏、三维图形程序开发提供了全方位的支持。本文所采用的编程写.X文件自动建模方法可以快速、逼真地构造出巷道模型系统。文中提到的曲线插值算法实现起来比较简单, 运行速率也比较高。实验证明, 这种巷道自动建模方法, 大大简化了模型的设计和程序的编制。
摘要：通过分析Direct3D所能识别的数据文件 (.X文件) 格式, 编程实现组织数据得到.X文件, 快速自动生成三维巷道模型。并针对巷道拐弯处的圆滑问题, 采用了改进的B样条曲线插值算法。实验表明, 基于曲线插值算法的巷道自动建模, 比建模软件建模易推广且运行速率高。
关键词：三维巷道,自动建模,插值算法
参考文献
[1]王德才, 杨关胜, 孙玉萍.精通DirectX3D图形与动画程序设计[M].人民邮电出版社, 2007.
[2]汪云甲, 伏永明.矿井巷道三维自动建模方法研究[J].武汉大学学报, 2006, 31 (12) .
[3][英]Alan Watt.3D计算机图形学[M].包宏, 译.北京:机械工业出版社, 2005.
插值算法 篇5
实验结果表明, 此方法与最近邻插值和双线性插值相比, 得到的放大图像可以达到更好的感知和客观的质量, 并且此插值算法的复杂度也相对较低。
1 典型传统插值算法
本文研究将一个低分辨率的图片X, 尺寸为H×W;转变成一个高分辨率图片Y, 尺寸为n H×n W的算法。为了简洁和不失一般性, 该示例使用n=3, 即采用3X插值为例, 进而扩展到其他n X插值。
1.1 最近邻插值法
最近邻插值法是最简单的一种插值方法, 该方法的原理为在待求象素的四邻象素中, 将距离待求象素最近的邻象素灰度赋给待求象素。设i+u, j+v (i, j为正整数, u, v为>0, <1的小数, 下同) 为待求象素坐标, 则待求象素灰度值f (i+u, j+v) 如图1所示。
如果 (i+u, j+v) 落在A区, 即u<0.5, v<0.5, 则将左上角象素的灰度值赋给待求象素, 同理, 落在B区则赋予右上角的象素灰度值, 落在C区则赋予左下角象素的灰度值, 落在D区则赋予右下角象素的灰度值。最近邻算法计算量小, 但会造成插值生成图像灰度上的不连续, 在灰度变化的地方可能出现明显的锯齿状。此算法得到3X效果如图2所示。
1.2 双线性插值法
双线性内插法是利用待求象素4个邻象素的灰度在两个方向上作线性内插, 其坐标如图3所示。
A (i, j) B (i, j+1) C (i+1, j+1) D (i+1, j) 对于 (i, j+v) , f (i, j) 到f (i, j+1) 的灰度变化为线性关系, 则有
同理对于 (i+1, j+v) 则有
从f (i, j+v) ~f (i+1, j+v) 的灰度变化为线性关系, 由此可推出待求象素灰度的计算式如下
双线性内插法的计算比最邻近点法复杂, 计算量大, 但其克服了灰度不连续的缺点, 图像效果较好。但其具有低通滤波性质, 使高频分量受损, 因此图像轮廓可能会略微模糊[12,13,14]。此算法得到3X效果图如图4所示。
2 差分投影快速定向图像插值算法
本文提出的算法是通过二次线性插值。第一次插值中, 第一组缺失象素的像素值是基于原始像素值内插所得。第二次插值中, 第二组缺失象素的像素值是基于原始像素值和第一组像素值插值所得。第一组像素包含块内点像素, 每个块内点对应一个像素位置, 每个块内点像素是由原来的4个原始像素形成。第二组像素包含块上点像素, 每个块上点像素对应边缘的一个像素位置, 是由两个原始像素形成。如图5所示黑点代表图片X的原始像素;灰点和白点是被插到像素空间的丢失的像素。相邻的4个黑色的点形成的正方形 (通过虚线标记) , 在虚线块中的灰色像素为“块内点” (in-block) 像素。白点是由两个相邻像素的边缘上形成的 (在虚线上) , 并且称为“块上点” (on-block) 像素。
本文为得到图Y丢失像素的梯度, 首先计算X的梯度, 然后采用双线性插值来计算高分辨率像素, 这个过程在此称作“梯度扩散”。在获得高分辨率的梯度, 四个“in-block”像素被插值如图7的I0, I1, I2, I3。因其几何对称, 在此采用I0为例。如图6过有一条线/垂直于梯度方向, 沿着该方向的局部变化最小。这条线与原始像素A, B, C, D组成的正方形有两个交点P和Q, 根据的不同坡度 (用表示) , 有3种类型的P和Q的分布。根据I0的梯度, 可以计算k和P, Q的位置。P和Q是通过其所在的正方形边的两个顶点双线性插值所得, 然后P和Q线性插值生成I0。
此处通过Sobel算子来计算X与Y的梯度, 进而由Y的梯度值得到有效像素的系数k, 通过以上分析可以推导出插值公式
由于几何对称性, 可以通过镜像A, B, C, D和I使用相同的权重求出I1, I2, I3。表1给出了相应的权重与, 表2为可用的像素的序列和转换斜率。
当块内点像素生成时, 在两个六边形的块上点像素由原像素和块内点像素进行插值。块上点插值步骤与块内点插值方法类似。表3给出了相应的权重与k, 表4为可用的像素序列和转换斜率, 其插值公式为
由于原始的算法没有保护好原始像素和插值像素的连续性。针对此问题, 在此采用“差分投影”。
由于低分率图片X的原始像素是可用的, 即不直接修改高分辨率图片Y的连续性。而是根据方程 (6) 由原始像素插值得出插值像素, 进而由插值得出的像素再次进行插值, 得到“原始虚拟”像素, 最后计算出原始像素与“原始虚拟”像素之间的差异值。这种差异值通过再次采用定向插值器传播到其他像素, 进而得到预期差值, 在此所采用的梯度与之前相同。其使用的求值公式为
通过“差分投影”求出差异值, 在此设F表示in-block和on-block混合插值, F+包括原始虚拟插值和F。X~为高分辨率图片, 该图片由从图片X的黑色圆点、灰色和白色点复制而来。由图可知, 预期差异值加到插值像素后, 原有像素会被迫连续而其值持续不变。在这里所用的求值公式如下:
此算法得到3X效果如图12所示。
3 差分投影插值算法的优化
通过图2, 图4和图12对比可知, 图12明显有更好的感知和客观的质量。但图12仍然存在噪点。传统去噪方法是对图像所有像素点做统一处理, 不会针对某一点做单独处理, 由于本文所提算法的特殊性, 在此针对特殊的点做特殊处理。
由于“块内点”和“块上点”皆由原始像素插值而来, 所以其像素值与原始像素的插值相差较小, 经实验验证, 出现噪点的位置皆是差值出的“块内点”和“块上点”对应的位置, 因此对每个插值出来的点做处理:若“块内点”对应的位置有噪点, 进而使用其对应的周围四个原始像素点的均值代替。判断是否为噪点, 应由该“块内点”与上述均值相比, 若差值超过一定阈值, 即判定此块上点是噪点。若“块上点”对应的位置有噪点, 方法同上。
此算法去噪后得到3X效果如图15所示。
4 结束语
本文提出一个快速定向插入器, 其可以发现和利用任意边缘梯度来确定丢失像素的权重。此外, 文中提出的“差分投影”方法可以提高一阶插值缺乏的连续性, 使被插值的图像被迫连续。由于其适应性和一致性, 所描述的定向插值器在不同的方向保护边缘。此算法不仅与其他自适应算法相比计算量较小, 同时它可以扩展到任何整数放大比率。以此算法为基础, 通过去除噪点对该算法进行优化, 使得放大图像有更好的感性质量, 给观察者一种更好的观察体验。
摘要：针对图像放大时分辨率会降低, 图像的感知质量变差等问题, 并考虑到计算的复杂度, 提出了一种差分投影快速定向图像插值算法。该方法通过对低分辨率图像的梯度扩散确定高分辨图像的丢失像素, 由特殊的去噪方法对该算法进行优化, 并与最近邻插值法与双线性插值算法等相比较。实验结果表明, 该方法具有较高的分辨率和较低的计算复杂度, 优于其他方法。
几种经典插值算法的放大结果比较 篇6
1 最近邻域插值算法
最近邻域插值算法是经典插值算法中最为简单的算法, 其对应的插值像素的灰度值主要选取的是离该点最近的已经求解得到的像素点的灰度值, 类似于灰度值复写功能, 所以最近邻域法又被称之为零阶保持插值算法或者像素复写插值算法。
假设 (i, j) 、 (i, j+1) 、 (i+1, j) 以及 (i+1, j+1) 是求解灰度值之前的一个四个交叉领域点, 再假设其对应的灰度值分别为g (i, j) 、gi, g (i, j+1) 、g (i+1, j) 以及g (i+1, j+1) 。采取最近邻域插值算法便是要求得这四个交叉点中间的某个点 (u, v) 像素点的灰度值。根据最近邻域插值算法可以求解得到 (u, v) 像素点的灰度值, 如式 (1) 所示:
最近邻域插值算法求解简单, 但是该算法最为明显的一个缺点便是非常容易造成图像出现“马赛克”现象。如果在某个四个交叉点组成的领域区间内形成更加多的像素点的时候, 最近邻域插值算法的缺点就变得愈加的明显, 经过校正处理之后的图像存在着明显锯齿形状, 锯齿形状便描述了灰度的连续情况, 即说明了该插值算法存在灰度不连续性的弊端。最近邻域 (Nearest) 插值算法虽然精度不是很高, 但是其运算速度非常快, 非常适合于一般场合的普通需求。
2 双线性内插算法
双线性内插算法是对最近邻域 (Nearest) 插值算法的改进, 该方法的具体实现过程是“利用周围4个邻点的灰度值在两个方向上作线性内插以得到待采样点的灰度值”, 即待采样像素点的灰度值的求解是根据待采样像素点与相邻点的距离差值的权值。
在双线性内插算法中, 既定f (x, y) 是一个二维函数, 假定其在单位正方形顶点的值已知, 则通过插值算法便可以求解得到正方形内所有点的f (x, y) 值, 现在假定二维函数f (x, y) 为线性的, 则其对应的数学表达式如式 (2) 所示:
定义一个双曲抛物面和已知的四个点拟合, 则a、b、c以及d四个系数的选定与f (x, y) 密切相关。经过中外文献资料的研究, 得出一种非常简单的算法, 该算法能够非常快速的求解得到双线性插值函数, 使其能够与f (x, y) 四个顶点的值拟合。首先, 采用线性插值算法对上面的两个点进行插值, 对下面的两个顶点同样采取线性插值算法。算法的最后便是对垂直方向的点进行线性插值, 便可以得到式 (3) :
双线性内插算法虽然是最近邻域插值算法的改进, 但是该算法在实现的过程中充分考虑到了待采样点周围四个直接相邻点对待采样点的直接影响。所以, 很大程度上解决了最近邻域插值算法灰度值不连续的问题, 但无形中也增加了算法的计算量, 此外, 该算法考虑的仅仅是与待采样点相邻的四个点灰度值的影响, 但是从未考虑到相邻点与相邻点之间灰度变化率的影响, 一定程度上具备了低通滤波器的特征, 使得经过缩放处理的图像的高频部分分量受到一定影响, 经过处理之后的图像的轮廓变得非常模糊。双线性内插算法处理之后的图像依然存在因为计算模型考虑不周而造成的图像精度下降以及图像质量退化的缺陷。
3 双三性内插算法
在众多的经典插值算法中, 双三性内插算法是现阶段应用广泛的插值算法, 是双线性内插算法以及最近邻域插值算法两者的改进算法, 考虑到了最近邻域插值算法灰度不连续的弊端以及双线性内插算法没有考虑相邻像素点灰度值变化率影响等缺陷, 在二者的基础上提出了采用待采样点周围更大邻域内像素的灰度值作三次插值, 双三性内插算法运用了三次多项式s (x) , s (x) 对应的数学表达式如式 (4) 描述所示:
双三性内插算法与双线性插值算法比较而言, 双三性内插算法由于考虑的问题兼顾了双线性内插算法以及最近邻域插值算法, 所以双三性内插算法相对比较复杂, 其对应的处理速度上相对比较慢, 但是其具备较高的插值精度, 能够创造出更加平滑的图像边缘。双三性内插算法通常被应用在一些专业的制图软件中、数码相机中或者打印机中, 对原始图像进行放大通常会取得非常有效的效果。
参考文献
[1]郝彬彬, 冯象初.一种基于小波和矩阵型扩散的图像放大[J].光子学报, 2008, 37 (11) :2365–2368
[2]曹亚君, 邵玉兰.基于双线性内插的图像处理算法及其优化[J].中州大学学报, 2012, 29 (3) :115-117
插值算法 篇7
关键词：图像插值,边缘信息,自适应
0 引 言
图像放大处理在医学、军事、气象、遥感、动画制作和电影合成等方面均有普遍的应用。图像放大的方法很多,目前比较成熟的算法有最近点插值, 双线性插值以及立方卷积插值等。其中立方卷积插值法普遍认为效果比较好。
文献[1]提出了相邻像素加权的插值算法,算法简单速度快但精度不高。文献[2]提出了一种根据图像内部特征的插值算法,算法复杂难以大规模应用。文献[3]提出了自适应双线性和自适应立方卷积算法,得到的图像精度有一定的改善。在文献[4]中提出了一种利用边缘信息的快速插值算法,该算法成功地实现了图像的放大且具有较好的图像质量,但由于在放大图像边缘部分时,利用的是其相邻的新生成的像素点来估算待插入像素点的值,这样会产生累积误差,影响图像质量。文献[5]在文献[3]自适应立方卷积算法的基础上提出了改进方法,考虑了邻点间灰度值变化率对图像的影响,算法实现较复杂。本文提出的基于边缘信息的图像自适应插值算法思想是:利用阈值将图像区分为非边缘部分和边缘部分,区分与插值同时进行,针对图像边缘的特性采用了自适应插值算法,这样既不会产生累积误差还能加快插值速度。
1 基于边缘信息的图像自适应插值算法
1.1 利用阈值区分图像非边缘部分和边缘部分
本算法首先将原图分成两部分:非边缘部分和边缘部分,而后针对不同的部分采取不同的插值算法。具体思路如图1所示。
要定义非边缘部分和边缘部分首先需预置一个阈值,然后,分别沿水平、垂直和两个对角共四个方向计算像素间差值,再与预置阈值比较。如果像素点间差值比预置阈值小, 则待内插像素点归类为非边缘像素点,直接使用双线性插值算法;反之,如果像素点间差值比预置阈值大,则待内插像素点就归为边缘像素点,则使用本文下面介绍的自适应插值算法。具体算法描述如下:
E1= | f(i,j)-f(i+1,j) |
E2= | f(i,j)-f(i,j+1) |
E3= | f(i,j)-f(i+1,j) |
E4= | f(i,j)-f(i,j+1)) |
If( E1<r)&(E2<r)&(E3<r)&(E4<r))
Then 双线性插值
Else 自适应插值
其中f(i,j)为原图坐标点(i,j)的灰度,r为预置的阈值。
1.2 立方卷积插值
立方卷积插值是一种应用较广泛的插值方式,不仅考虑到四个直接邻点灰度值的影响, 还考虑到各邻点间灰度值变化率的影响, 利用了待采样点周围更大邻域内像素的灰度值作三次插值。此法用了三次多项式S(w),其数学表达式为:
式中w为自变量;S(w)为三次多项式的值。计算时利用周围16个邻点的灰度值按下式进行内插:
f(i+u,j+v)=A·B·C (2)
分析式(1)和式(2),可得:
S(1+u)=4-8|1+u|+5|1+u|2-|1+u|3=-(|u|-2|u|2+|u|)
S(u)=1-2|u|2+|u|3=(1-|u|)+(|u|-2|u|2+|u|3)
令k=|u|-2|u|2+|u|3
则: S(1+u)=-k S(u)=(1-|u|)+k (3)
若令k = 0, 则立方卷积法就退化为双线性内插法。因此,可以把用三次多项式插值的立方卷积法看成由两部分组成, 其中( 1 - | u | )代表直接邻点的灰度值对待采样点的影响, 而k则代表邻点间灰度值的变化率对待采样点的影响。与双线性内插法相比, 立方卷积法不仅考虑了直接邻点的灰度值对待采样点的影响, 还考虑了邻点间灰度值变化率的影响, 因此具有更高的插值精度。
1.3 自适应插值法
由于人眼对图像边缘特别敏感,插值图像边缘部分的分辨率对整个图像放大有着非常重要的影响。由于图像边缘灰度值变化剧烈,不仅要考虑邻点灰度值的影响,同时也必须考虑邻点间灰度值变化率的影响, 因此可将(3)式改写成:
S(1+u)=-λk S(u)=(1-|u|)+λk (4)
当λ=0时,式(4)为双线形插值,当λ=1时,式(4)为立方卷积插值。λ越大,邻点间灰度值变化率的影响权值就越大;λ越小,直接邻点灰度值的影响权值就越大。经过计算与统计分析可以发现,当λ取0～1之间的值时,内插效果优于立方卷积法。但固定的λ值只在图像某个邻域内效果比较好,因此可根据该映射点周围各邻点灰度值的变化情况,自适应地调整λ值,以此来达到提高插值精度和缩放质量的目的。判据可以有多种选择,为简化算法采用了直接邻点与间接邻点的灰度差是否大于一个给定的阈值来判断该映射点的周围是高频区或低频区,再以此来自适应地选择一个λ值进行插值运算。
r=f(i)-f(i-1)
在缩放时,λ的取值由下式决定:
2 实验结果
分别用256×256的pepper、baboon、lena灰度图像进行缩放实验。实验时先把每幅图缩小2倍,然后再放大2倍,再根据放大后图像与原图的峰值信噪比(PSNR)作为缩放质量的标准。PSNR越高说明插值图像与原图像相符合的程度越高。实验结果如表1所示。
从表1中可以看出,在对三种图像pepper、baboon、lena进行缩放实验时,本文算法的PSNR值最高,说明本文算法的效果是比较好的。
为进一步验证本插值算法的有效性,把512×512的Lean灰度图用四种算法放大到1024×1024的图像,图2显示了放大后的局部图像。从图2中可以可看到,本文算法的视觉效果优于其它算法。
表2显示4种插值算法分别连续插值处理10幅Lena灰度图512 ×512到1024 ×1024的平均CPU处理时间(s/图像) (实验条件P4 CPU 2.6GHz,内存512M,编译系统Matlab7.0)。从表2看出本文算法CPU处理插值的平均时间与Bicubic算法相近,因此,本文算法不但有较好的视觉质量,而且有相对较低的计算复杂性及平均CPU处理时间。
3 结 论
本文主要研究了一种基于图像边缘信息自适应插值算法,使用本算法对低分辨率图像进行重建,效果要比传统插值法好,特别在边界部分清晰自然, 明显好于传统插值方法。从实验结果也看到,本文算法还是比较有效的。当然根据图像的复杂度如何更好的选取边缘预置阈值和参数λ的值还有待进一步的研究。
参考文献
[1]Lukin A,Kubasov D.High-quality algorithm for Bayer Pattern interpo-lation[J].Programming and Computer Software,2004,30(6):347-358.
[2]El-Khamy S E,Hadhoud MM,Dessouky MI,et al.Efficient implemen-tation of image interpolation as an inverse problem[J].Digital SignalProcessing.2005(15):137-152.
[3]庞博,张旭东,徐小红.自适应图像插值在超分辨率图像重建中的应用[J].合肥工业大学学报:自然科学版,2006(7):825-829.
[4]Mei-Juan Chen,Chin-Hui Huang,Wen-Li Lee.Afast edge-oriented al-gorithm for image interpolation[J].Image and Vision Computing,2005(23):791-798.