什么是插值
插值就是在数值分析中根据某种客观的规律,通过一些已知的离散数据来求取部分信息已知(如曲线上一点只知道他的x轴坐标,求其y轴坐标)的未知数据的过程。如下图,插值就是端点P,Q已知,并且知道Q的x的坐标情况下,推断y(函数值)的过程。
插值的方法在数值分析中提到的有很多,这里介绍双线性插值,为了容易理解先从线性插值开始引入。
线性插值
如引入部分提到的那样,已知端点坐标 P(x0,y0)与Q(x1,y1),要得到[x0,x1] 区间内某一位置x在直线上的值y。我们知道直线的斜率可以写作:
k(直线斜率)=y1−y0x1−x0=y−y0x−x0
由于
x值已知,所以可以从公式得到
y的值,进而完成插值:
y=y0+(x−x0)y1−y0x1−x0=x1−xx1−x0y0+x−x0x1−x0y1
然后,仔细观察左右两边,你会发现有个规律:
近朱者赤近墨者黑,靠近谁就更像谁
线性插值可以扩展到有两个变量的函数的双线性插值,双线性插值经常作为一种粗略的抗混叠滤波器使用,三线性插值用于三个变量的函数的插值。线性插值的其它扩展形式可以用于三角形与四面体等其它类型的网格运算。
双线性插值
双线性插值就是对有两个变量的函数进行线性插值的过程,其核心思想是在两个变元方向分别进行一次线性插值(它认为单独考虑一个方向时,仍然是线性插值过程)。
如上图,请注意这是一个具有两个变量的函数z=f(x,y),应该用一个三维空间表示,但为了便于表达插值点的求解过程,这里只画出了x和y轴。其中,绿色的点是已知点,即坐标(x,y)和函数值z都是已知的,紫色点则是我们要求计算的插值点,我们只知道他的坐标值(x,y),但我现在需要知道他的函数值z,怎么破呢?
这里为了求解P点,引入了两个辅助点R1,R2,这里可以迅速的发现R1,R2的坐标位置,如果我们也知道了R1,R2的函数值z,那么我们在y轴方向上对点P使用一次线性插值,就可以求得P点的函数值了。那么,R1,R2的函数值我们不知道啊,但幸运的是我们可以对R1,R2分别在其x轴方向上进行一次线性插值求得其函数值。
那么,现在问题就转化为了,
- 对R1,R2在其x方向上分别进行线性插值,求取R1,R2的函数值;
- 对P在其y方向上进行一次线性插值,最终求得P的函数值;
1)在x方向上对R1,R2进行线性插值
f(R1)≈x2−xx2−x1f(Q11)+x−x1x2−x1f(Q21)f(R2)≈x2−xx2−x1f(Q12)+x−x1x2−x1f(Q22)
2)上面就求得了
f(R1)和
f(R2),紧接着我们在y方向上对
P进行线性插值
f(P)≈y2−yy2−y1f(R1)+y−y1y2−y1f(R2)(1)
什么?上面的式子不知道怎么来的?不要方,我们现在来单独考察下上图中的
Q11,R1,Q21,看一下上面的第一个插值计算是怎么来的,这次我们加上Z轴来一起考虑。
也就是用
Q11和Q21对
R1进行插值,现在大家的
y轴方向的取值都是
y1了,相当于
R1处的
z值只与
x有关,我们考察下
x方向上的斜率,他可以写作:
kx(直线斜率)=f(Q21)−f(Q11)x2−x1=f(R1)−f(Q11)x−x1
于是乎通个分换算下,就得到了下面的样儿:
f(R1)=f(Q11)+(x−x1)f(Q21)−f(Q11)x2−x1=x2−xx2−x1f(Q11)+x−x1x2−x1f(Q21)
当然,我们这里假设他是直线的情况,实际很多情况下他都不是这么理想,因此我们又把它写作了约等的形式,也就是上面的第一次插值的式子:
f(R1)≈x2−xx2−x1f(Q11)+x−x1x2−x1f(Q21)
其他的几个式子也就类似可以计算出来,进而最终式(1)可以写作,
f(P)=f(x,y)≈f(x1,y1)x2−xx2−x1y2−yy2−y1+f(x2,y1)x−x1x2−x1y2−yy2−y1+f(x1,y2)x2−xx2−x1y−y1y2−y1+f(x2,y2)x−x1x2−x1y−y1y2−y1
如果选择一个坐标系统使得
f的四个已知点坐标分别为 (0, 0)、(0, 1)、(1, 0) 和 (1, 1),那么插值公式就写成这样的极简模式:
f(P)=f(x,y)≈f(0,0)(1−x)(1−y)+f(1,0)x(1−y)+f(0,1)(1−x)y+f(1,1)xy(2)
或者矩阵形式:
f(x,y)≈[1−xx][f(0,0)f(1,0)f(0,1)f(1,1)][1−yy]
值得注意的
从上述式(2)中也可以看出,这种插值方法并不是线性的,其形式表现为(a1x+a2)(a3y+a4),也即是两个线性函数的乘积,并不是线性的,只是说在他的两个方向上分别是线性的,所以叫做双线性。
应用实例
LBP中的双线性插值
估计插值的点(待完善)
HOG中的三线性插值
根据双线性插值思想,可在各像素的梯度方向上进行加权运算,如下图所示,将区间[ 0°,180°] 以20°为一个区间划分,每个小区间以中心角度作为直方图的中心数值,假设要对梯度方向为15°的像素点进行处理,显然15与以10和30为中心的直方图最近,也就是将该点的梯度值均摊到跟它相近的两个直方图身上,那每个直方图可以得到多少呢,可以看到权重分别为( 30 - 15) / 20 = 0. 75 和( 15 - 10 )/20 = 0. 25 。
同理运用线性插值方法在各个像素的位置上进行加权运算,下面左图中的方框处为待处理像素点,它位于block中的C 0 单元中,利用该点与四个cell 中的中心像素点(图中4 个圆点)的距离计算权值,将待处理像素点的梯度幅值分别加权累加到C0、C1、C2、C3 中相应的直方图上。
综合考虑,在两个位置坐标(x,y) 和一个方向坐标( θ )上进行三线性插值,关键要解决的问题是应该在哪些 bin上进行加权累加,累加时权值又是多少。将一个像素点处的梯度幅值加权分配到4 个cell 中与该点梯度方向相邻的2 个bin上。按照下面的公式修正直方图向量:
h(x1,y1,z1)h(x1,y1,z2)h(x1,y2,z1)h(x2,y1,z1)h(x1,y2,z2)h(x2,y1,z2)h(x2,y2,z1)h(x2,y2,z2)←h(x1,y1,z1)+ω(1−x−x1bx)(1−y−y1by)(1−z−z1bz)←h(x1,y1,z2)+ω(1−x−x1bx)(1−y−y1by)(z−z1bz)←h(x1,y2,z1)+ω(1−x−x1bx)(y−y1by)(1−z−z1bz)←h(x2,y1,z1)+ω(x−x1bx)(1−y−y1by)(1−z−z1bz)←h(x1,y2,z2)+ω(1−x−x1bx)(y−y1by)(z−z1bz)←h(x2,y1,z2)+ω(x−x1bx)(1−y−y1by)(z−z1bz)←h(x2,y2,z1)+ω(x−x1bx)(y−y1by)(1−z−z1bz)←h(x2,y2,z2)+ω(x−x1bx)(y−y1by)(z−z1bz)
合并看贡献(权重),分摊看影响(权重)
未完待续...