数据结构与算法

插值（内插）

插值是确定某个函数在两个采样值之间的数值时采用的运算过程。插值通常是利用曲线拟合的方法，通过离散的输入采样点建立一个连续函数，用这个重建的函数便可以求出任意位置处的函数值。这样便可以不受仅在采样点处抽取输入信号值的限制。

我们知道，对有限带宽的信号采样会产生无限带宽信号，插值过程正好相反，它通过对离散信号作低通滤波处理，减少了信号的带宽。插值函数对采样数值的平滑作用，恢复了在采样过程中丢失的信息。因而插值可以看做是采样的逆过程。

对于等间隔采样数据，插值可以表示为：

其中h为插值核，ck为权系数，卷积对k个数据作处理。上面的方程将插值用卷积操作来表示，在实际应用中，h总是对称的，即有h(x)=h(-x)，ck即为采样值。

插值核的性质可以通过其在频率域的特性来评估。理想的插值核在带通区具有单位增益，在带阻区具有０增益。因而可以有效地通过和抑制不同频率的信号成分。

理想滤波器在空间域中都具有很宽的拓区，故称为无限脉冲响应滤波器（iir），但这种滤波器在实际中是无法实现的。仅能在一定程度上近似实现这类滤波器。

另一类可实现的滤波器常称为有限脉冲响应滤波器(fir)，fir滤波器的每一个输出值都是其邻域有限输入元素的加权和。fir滤波器在信号与图象处理中具有广泛应用。常用的fir滤波器有盒式、三角、三次卷积b样条及加窗sinc函数等。

它们都可以作为插值函数的插值核来使用。下面列举几种比较有效的插值核：

1、最近邻域法。

这是最简单的算法，每一个输出像素都赋给输入图象中与其最邻近的采样点的值。

2、线形插值。

3、sinc

在这里介绍的是hann/hamming窗：

其中n为窗口下的采样点数。当取0.5时，称hann窗，当取0.54时，称hamming窗。

这里没有介绍三次样条，是因为排版和理论上的原因，但是提供了一个三次样条的范例程序。程序可能有错，请勿见怪。

下面是程序

三次样条插值范例程序。

/ name : ispline-gen (

/ function: interpolating cubic spline function for irregularly-spaced poinis.

/ parametcrs: y1 : is a list of irregular data points (len1 entries).

/ x1 : x-coordinaies of the adta siored in y1.

/ y2 : cubic spline sampled according io x2 (len2 entries).

/ calls : getyd_gen (

void ispline_gen(double x x1 ,double x y1 ,int len1 ,doublc & x2 ,double x y2 ,int len2)

int i, j;

double * yd, a0, a1, a2, a3, x, dx, dy, p1, p2, p3;

yd = double x ) calloc (len1 , sizeof(double) )

getyd_ gen ( x1 , y1 , yd , len1 )

/ *error checking *

if (x2 [0]x1 [len1 - 1 ]

p3 = x2 [0]-1 ;

for (i = j = 0 ; i

x = p2-p1 ;

y2[i]= a3 * x+a2) *x+a1) *x+a0;

free( (char * yd) ;

/ name : getyd_ gen (

/ function : compute 1st derivaiives of data in x and y(len entries).

/ the not-a-knot boundary is used.

/ parameters : y : is a list of irregular data points (len1 entries).

/ x : x-coordinatcs of the adta stored in y1.

/ yd : output data (len entries) .

/ calls : tridiag_gen (

void getyd_gen (double * x ,doublc * y ,double * yd ,int len)

int i ;

double h0,h1 ,r0,r1 , a, *b, *c;

a =(double * calloc (len , sizeof (double )

b =(double x ) calloc (len , sizeof(double) )

c =(double x ) calloc (len , sizeof(double )

h0 =x [1 ]-x [0] ;

h1 =x [2]-x [1 ]

r0 =(y[1 ]-y[0] )h0 ;

r1 = y[2]-y[1] )h1 ;

b[0] =h1 * h0+h1 )

c[0]=(h0+h1 ) h0+h1 )

yd[0]=r0 * 3 * h0 * h1+2 * h1 * h1)+r1 * h0 * h0;

for (i = 1 ; i

a[i] =h0-h1 ) h0+h1 )

b[i] =h0 * h0+h1 )

c[i] =h0 ;

yd[i]=r0 * h1 * h1+r1 * 3 * h0 * h1+2 * h0 * h0) ;

/ *solve for the tridiagonal mairix. *

tridiag_gen ( a , b , c , yd , len )

free( (char * a) ;

free( (char * b) ;

free( (char * c) ;

/ name : tridiag_gen( )

/ function : solve for the tridiagonal matrix using gauss

/ backsubstitution method.

/ parameters: a ,b ,c, d : is a list of store data points (len entries).

void tridiag_gen (double * a , double * b , double * c ,double * d , int len )

int i ;

double b , f ;

f = double * calloc (len , sizeof(double )

b = b[0] /b ;

d[0]= d[0] /b ;

for ( i=1 ; i< len ; i ++

d[i]= d[i]-d[i-1]* a [i] )b ;

for ( i=len- 2 ; i >=0 ; i--

d[i]=(d[i+1]*f[i+1]);

free ( char * f) ;

数据结构与算法

数据结构与算法

算法与数据结构

算法与数据结构

其他用户还读了