c语言线性插值法

A. FPGA如何通过查找表实现其功能

在计算机科学中，查找表是用简单的查询操作替换运行时计算的数组或者 associative array 这样的数据结构。由于从内存中提取数值经常要比复杂的计算速度快很多，所以这样得到的速度提升是很显着的。
一个经典的例子就是三角表。每次计算所需的正弦值在一些应用中可能会慢得无法忍受，为了避免这种情况，应用程序可以在刚开始的一段时间计算一定数量的角度的正弦值，譬如计算每个整数角度的正弦值，在后面的程序需要正弦值的时候，使用查找表从内存中提取临近角度的正弦值而不是使用数学公式进行计算。
在计算机出现之前，人们使用类似的表格来加快手工计算的速度。非常流行的表格有三角、对数、统计 density 函数。另外一种用来加快手工计算的工具是滑动计算尺。
一些折衷的方法是同时使用查找表和插值这样需要少许计算量的方法，这种方法对于两个预计算的值之间的部分能够提供更高的精度，这样稍微地增加了计算量但是大幅度地提高了应用程序所需的精度。根据预先计算的数值，这种方法在保持同样精度的前提下也减小了查找表的尺寸/
在图像处理中，查找表经常称为LUT，它们将索引号与输出值建立联系。颜色表作为一种普通的 LUT 是用来确定特定图像所要显示的颜色和强度。
另外需要注意的一个问题是，尽管查找表经常效率很高，但是如果所替换的计算相当简单的话就会得不偿失，这不仅仅因为从内存中提取结果需要更多的时间，而且因为它增大了所需的内存并且破坏了高速缓存。如果查找表太大，那么几乎每次访问查找表都回倒置 cache miss，这在处理器速度超过内存速度的时候愈发成为一个问题。在编译器优化的 rematerialization 过程中也会出现类似的问题。在一些环境如Java 编程语言中，由于强制性的边界检查带来的每次查找的附加比较和分支过程，所以查找表可能开销更大。
何时构建查找表有两个基本的约束条件，一个是可用内存的数量；不能构建一个超过能用内存空间的表格，尽管可以构建一个以查找速度为代价的基于磁盘的查找表。另外一个约束条件是初始计算查找表的时间——尽管这项工作不需要经常做，但是如果耗费的时间不可接受，那么也不适合使用查找表。
[编辑本段]
例子

[编辑本段]
计算正弦值
许多计算机只能执行基本的算术运算，而不能直接计算给定值的正弦值，它们使用如下面泰勒级数（en:Taylor series）这样的复杂公式计算相当高精度的正弦值：
(x 接近 0)
然而，这样的计算费用可能是非常大的，尤其是在低速的处理器上。有许多的应用程序，尤其是传统的计算机图形每秒需要几千次的正弦值计算。一个常用的解决方案就是在刚开始计算许多均匀分布数值的正弦值，然后在表中查找最接近所需 x 的正弦值，这个值非常接近于正确的数值，这是因为正弦函数是一个有限变化率的连续函数。例如：
real array sine_table[-1000..1000]
for x from -1000 to 1000
sine_table[x] := sine(x/1000/pi)
function lookup_sine(x)
return sine_table[round(x/1000/pi)]
Image:Interpolation example linear.png
部分正弦函数的线性插值不幸的是，查找表需要一定的空间：如果使用 IEEE 双精度浮点数的话，将会需要 16,000 字节。如果使用较少的采样点，那么精度将会大幅度地下降。一个较好的解决方案是线性插值，在表中待计算点左右两侧两个点的值之间连直线，这个点对应的直线上的值就是所计算点的正弦值。这种方法计算速度也很快，对于如正弦函数这样的平滑函数来说也有更高的精度。这里是使用线性插值的一个例子：
function lookup_sine(x)
x1 := floor(x/1000/pi)
y1 := sine_table[x1]
y2 := sine_table[x1+1]
return y1 + (y2-y1)*(x/1000/pi-x1)
当使用插值的时候，可以得益于不均匀采样，也就是说在接近直线的地方，使用较少的采样点，在变化较快的地方使用较多的采样点以最大限度地接近实际的曲线。更多的信息请参考插值。
[编辑本段]
计算 1 的位数
population function。例如，数字 37 的二进制形式是 100101，所以它包含有三个设置成 1 的位。一个计算 32 位整数中 1 的位数的简单c语言程序是：
int count_ones(unsigned int x) {
int i, result = 0;
for(i=0; i<32; i++) {
result += x & 1;
x = x >> 1;
}
return result;
}
不幸的是，这个简单的算法在现代的架构上将需要数以百计的时钟周期才能完成，这是因为它造成了许多分支和循环，而分支的速度是很慢的。这可以使用 loop unrolling 和其它一些聪明的技巧进行改进，但是最简单快捷的解决方案是查找表：简单地构建一个 包含每个字节可能值包含的 1 的个数的256 个条目的表。然后使用这个表查找整数中每个字节包含的 1 的个数，并且将结果相加。没有分支、四次内存访问、几乎没有算术运算，这样与上面的算法相比就可以大幅度地提升速度。
int count_ones(unsigned int x) {
return bits_set[x & 255] + bits_set[(x >> 8) & 255]
+ bits_set[(x >> 16) & 255] + bits_set[(x >> 24) & 255];
}
[编辑本段]
硬件查找表
在数字逻辑中，n位查找表可以使用多路复用器来实现，它的选择线是 LUT 的输入，它的输入是常数。n 位 LUT 通过将布尔逻辑函数建模为真值表从而可以编码任意 n 位输入，这是编码布尔逻辑函数的一个有效途径，4 位 LUT 实际上是现代 FPGAs 的主要元件。

B. 怎么用matlab进行非线性的多元函数拟合

方法一：

1、最常用的是多项式拟合，采用polyfit函数，在命令窗口输入自变量x和因变量y。

C. 求双线性插值法的C语言程序！帮帮忙！拜托各位了！

ab
t
cd
就是两次线性插值，先在x方向插出t上下方的_t1、_t2，然后再用它们插出t来
floattest(floatx,floaty)
{
float_t1,_t2,t;
_t1=a+(b-a)*(x-ax)/(bx-ax);
_t2=c+(d-c)*(x-cx)/(dx-cx);
t=_t1+(_t2-_t1)*(y-ay);
returnt;
}

D. C语言算法速查手册的目录

第1章绪论1
1.1程序设计语言概述1
1.1.1机器语言1
1.1.2汇编语言2
1.1.3高级语言2
1.1.4C语言3
1.2C语言的优点和缺点4
1.2.1C语言的优点4
1.2.2C语言的缺点6
1.3算法概述7
1.3.1算法的基本特征7
1.3.2算法的复杂度8
1.3.3算法的准确性10
1.3.4算法的稳定性14
第2章复数运算18
2.1复数的四则运算18
2.1.1[算法1]复数乘法18
2.1.2[算法2]复数除法20
2.1.3【实例5】 复数的四则运算22
2.2复数的常用函数运算23
2.2.1[算法3]复数的乘幂23
2.2.2[算法4]复数的n次方根25
2.2.3[算法5]复数指数27
2.2.4[算法6]复数对数29
2.2.5[算法7]复数正弦30
2.2.6[算法8]复数余弦32
2.2.7【实例6】 复数的函数运算34
第3章多项式计算37
3.1多项式的表示方法37
3.1.1系数表示法37
3.1.2点表示法38
3.1.3[算法9]系数表示转化为点表示38
3.1.4[算法10]点表示转化为系数表示42
3.1.5【实例7】系数表示法与点表示法的转化46
3.2多项式运算47
3.2.1[算法11]复系数多项式相乘47
3.2.2[算法12]实系数多项式相乘50
3.2.3[算法13]复系数多项式相除52
3.2.4[算法14]实系数多项式相除54
3.2.5【实例8】复系数多项式的乘除法56
3.2.6【实例9】实系数多项式的乘除法57
3.3多项式的求值59
3.3.1[算法15]一元多项式求值59
3.3.2[算法16]一元多项式多组求值60
3.3.3[算法17]二元多项式求值63
3.3.4【实例10】一元多项式求值65
3.3.5【实例11】二元多项式求值66
第4章矩阵计算68
4.1矩阵相乘68
4.1.1[算法18]实矩阵相乘68
4.1.2[算法19]复矩阵相乘70
4.1.3【实例12】 实矩阵与复矩阵的乘法72
4.2矩阵的秩与行列式值73
4.2.1[算法20]求矩阵的秩73
4.2.2[算法21]求一般矩阵的行列式值76
4.2.3[算法22]求对称正定矩阵的行列式值80
4.2.4【实例13】 求矩阵的秩和行列式值82
4.3矩阵求逆84
4.3.1[算法23]求一般复矩阵的逆84
4.3.2[算法24]求对称正定矩阵的逆90
4.3.3[算法25]求托伯利兹矩阵逆的Trench方法92
4.3.4【实例14】 验证矩阵求逆算法97
4.3.5【实例15】 验证T矩阵求逆算法99
4.4矩阵分解与相似变换102
4.4.1[算法26]实对称矩阵的LDL分解102
4.4.2[算法27]对称正定实矩阵的Cholesky分解104
4.4.3[算法28]一般实矩阵的全选主元LU分解107
4.4.4[算法29]一般实矩阵的QR分解112
4.4.5[算法30]对称实矩阵相似变换为对称三对角阵116
4.4.6[算法31]一般实矩阵相似变换为上Hessen-Burg矩阵121
4.4.7【实例16】 对一般实矩阵进行QR分解126
4.4.8【实例17】 对称矩阵的相似变换127
4.4.9【实例18】 一般实矩阵相似变换129
4.5矩阵特征值的计算130
4.5.1[算法32]求上Hessen-Burg矩阵全部特征值的QR方法130
4.5.2[算法33]求对称三对角阵的全部特征值137
4.5.3[算法34]求对称矩阵特征值的雅可比法143
4.5.4[算法35]求对称矩阵特征值的雅可比过关法147
4.5.5【实例19】 求上Hessen-Burg矩阵特征值151
4.5.6【实例20】 分别用两种雅克比法求对称矩阵特征值152
第5章线性代数方程组的求解154
5.1高斯消去法154
5.1.1[算法36]求解复系数方程组的全选主元高斯消去法155
5.1.2[算法37]求解实系数方程组的全选主元高斯消去法160
5.1.3[算法38]求解复系数方程组的全选主元高斯-约当消去法163
5.1.4[算法39]求解实系数方程组的全选主元高斯-约当消去法168
5.1.5[算法40]求解大型稀疏系数矩阵方程组的高斯-约当消去法171
5.1.6[算法41]求解三对角线方程组的追赶法174
5.1.7[算法42]求解带型方程组的方法176
5.1.8【实例21】 解线性实系数方程组179
5.1.9【实例22】 解线性复系数方程组180
5.1.10【实例23】 解三对角线方程组182
5.2矩阵分解法184
5.2.1[算法43]求解对称方程组的LDL分解法184
5.2.2[算法44]求解对称正定方程组的Cholesky分解法186
5.2.3[算法45]求解线性最小二乘问题的QR分解法188
5.2.4【实例24】 求解对称正定方程组191
5.2.5【实例25】 求解线性最小二乘问题192
5.3迭代方法193
5.3.1[算法46]病态方程组的求解193
5.3.2[算法47]雅克比迭代法197
5.3.3[算法48]高斯-塞德尔迭代法200
5.3.4[算法49]超松弛方法203
5.3.5[算法50]求解对称正定方程组的共轭梯度方法205
5.3.6[算法51]求解托伯利兹方程组的列文逊方法209
5.3.7【实例26】 解病态方程组214
5.3.8【实例27】 用迭代法解方程组215
5.3.9【实例28】 求解托伯利兹方程组217
第6章非线性方程与方程组的求解219
6.1非线性方程求根的基本过程219
6.1.1确定非线性方程实根的初始近似值或根的所在区间219
6.1.2求非线性方程根的精确解221
6.2求非线性方程一个实根的方法221
6.2.1[算法52]对分法221
6.2.2[算法53]牛顿法223
6.2.3[算法54]插值法226
6.2.4[算法55]埃特金迭代法229
6.2.5【实例29】 用对分法求非线性方程组的实根232
6.2.6【实例30】 用牛顿法求非线性方程组的实根233
6.2.7【实例31】 用插值法求非线性方程组的实根235
6.2.8【实例32】 用埃特金迭代法求非线性方程组的实根237
6.3求实系数多项式方程全部根的方法238
6.3.1[算法56]QR方法238
6.3.2【实例33】用QR方法求解多项式的全部根240
6.4求非线性方程组一组实根的方法241
6.4.1[算法57]梯度法241
6.4.2[算法58]拟牛顿法244
6.4.3【实例34】 用梯度法计算非线性方程组的一组实根250
6.4.4【实例35】 用拟牛顿法计算非线性方程组的一组实根252
第7章代数插值法254
7.1拉格朗日插值法254
7.1.1[算法59]线性插值255
7.1.2[算法60]二次抛物线插值256
7.1.3[算法61]全区间插值259
7.1.4【实例36】 拉格朗日插值262
7.2埃尔米特插值263
7.2.1[算法62]埃尔米特不等距插值263
7.2.2[算法63]埃尔米特等距插值267
7.2.3【实例37】 埃尔米特插值法270
7.3埃特金逐步插值271
7.3.1[算法64]埃特金不等距插值272
7.3.2[算法65]埃特金等距插值275
7.3.3【实例38】 埃特金插值278
7.4光滑插值279
7.4.1[算法66]光滑不等距插值279
7.4.2[算法67]光滑等距插值283
7.4.3【实例39】 光滑插值286
7.5三次样条插值287
7.5.1[算法68]第一类边界条件的三次样条函数插值287
7.5.2[算法69]第二类边界条件的三次样条函数插值292
7.5.3[算法70]第三类边界条件的三次样条函数插值296
7.5.4【实例40】 样条插值法301
7.6连分式插值303
7.6.1[算法71]连分式插值304
7.6.2【实例41】 验证连分式插值的函数308
第8章数值积分法309
8.1变步长求积法310
8.1.1[算法72]变步长梯形求积法310
8.1.2[算法73]自适应梯形求积法313
8.1.3[算法74]变步长辛卜生求积法316
8.1.4[算法75]变步长辛卜生二重积分方法318
8.1.5[算法76]龙贝格积分322
8.1.6【实例42】 变步长积分法进行一重积分325
8.1.7【实例43】 变步长辛卜生积分法进行二重积分326
8.2高斯求积法328
8.2.1[算法77]勒让德-高斯求积法328
8.2.2[算法78]切比雪夫求积法331
8.2.3[算法79]拉盖尔-高斯求积法334
8.2.4[算法80]埃尔米特-高斯求积法336
8.2.5[算法81]自适应高斯求积方法337
8.2.6【实例44】 有限区间高斯求积法342
8.2.7【实例45】 半无限区间内高斯求积法343
8.2.8【实例46】 无限区间内高斯求积法345
8.3连分式法346
8.3.1[算法82]计算一重积分的连分式方法346
8.3.2[算法83]计算二重积分的连分式方法350
8.3.3【实例47】 连分式法进行一重积分354
8.3.4【实例48】 连分式法进行二重积分355
8.4蒙特卡洛法356
8.4.1[算法84]蒙特卡洛法进行一重积分356
8.4.2[算法85]蒙特卡洛法进行二重积分358
8.4.3【实例49】 一重积分的蒙特卡洛法360
8.4.4【实例50】 二重积分的蒙特卡洛法361
第9章常微分方程(组)初值问题的求解363
9.1欧拉方法364
9.1.1[算法86]定步长欧拉方法364
9.1.2[算法87]变步长欧拉方法366
9.1.3[算法88]改进的欧拉方法370
9.1.4【实例51】 欧拉方法求常微分方程数值解372
9.2龙格-库塔方法376
9.2.1[算法89]定步长龙格-库塔方法376
9.2.2[算法90]变步长龙格-库塔方法379
9.2.3[算法91]变步长基尔方法383
9.2.4【实例52】 龙格-库塔方法求常微分方程的初值问题386
9.3线性多步法390
9.3.1[算法92]阿当姆斯预报校正法390
9.3.2[算法93]哈明方法394
9.3.3[算法94]全区间积分的双边法399
9.3.4【实例53】 线性多步法求常微分方程组初值问题401
第10章拟合与逼近405
10.1一元多项式拟合405
10.1.1[算法95]最小二乘拟合405
10.1.2[算法96]最佳一致逼近的里米兹方法412
10.1.3【实例54】 一元多项式拟合417
10.2矩形区域曲面拟合419
10.2.1[算法97]矩形区域最小二乘曲面拟合419
10.2.2【实例55】 二元多项式拟合428
第11章特殊函数430
11.1连分式级数和指数积分430
11.1.1[算法98]连分式级数求值430
11.1.2[算法99]指数积分433
11.1.3【实例56】 连分式级数求值436
11.1.4【实例57】 指数积分求值438
11.2伽马函数439
11.2.1[算法100]伽马函数439
11.2.2[算法101]贝塔函数441
11.2.3[算法102]阶乘442
11.2.4【实例58】伽马函数和贝塔函数求值443
11.2.5【实例59】阶乘求值444
11.3不完全伽马函数445
11.3.1[算法103]不完全伽马函数445
11.3.2[算法104]误差函数448
11.3.3[算法105]卡方分布函数450
11.3.4【实例60】不完全伽马函数求值451
11.3.5【实例61】误差函数求值452
11.3.6【实例62】卡方分布函数求值453
11.4不完全贝塔函数454
11.4.1[算法106]不完全贝塔函数454
11.4.2[算法107]学生分布函数457
11.4.3[算法108]累积二项式分布函数458
11.4.4【实例63】不完全贝塔函数求值459
11.5贝塞尔函数461
11.5.1[算法109]第一类整数阶贝塞尔函数461
11.5.2[算法110]第二类整数阶贝塞尔函数466
11.5.3[算法111]变型第一类整数阶贝塞尔函数469
11.5.4[算法112]变型第二类整数阶贝塞尔函数473
11.5.5【实例64】贝塞尔函数求值476
11.5.6【实例65】变型贝塞尔函数求值477
11.6Carlson椭圆积分479
11.6.1[算法113]第一类椭圆积分479
11.6.2[算法114]第一类椭圆积分的退化形式481
11.6.3[算法115]第二类椭圆积分483
11.6.4[算法116]第三类椭圆积分486
11.6.5【实例66】第一类勒让德椭圆函数积分求值490
11.6.6【实例67】第二类勒让德椭圆函数积分求值492
第12章极值问题494
12.1一维极值求解方法494
12.1.1[算法117]确定极小值点所在的区间494
12.1.2[算法118]一维黄金分割搜索499
12.1.3[算法119]一维Brent方法502
12.1.4[算法120]使用一阶导数的Brent方法506
12.1.5【实例68】使用黄金分割搜索法求极值511
12.1.6【实例69】使用Brent法求极值513
12.1.7【实例70】使用带导数的Brent法求极值515
12.2多元函数求极值517
12.2.1[算法121]不需要导数的一维搜索517
12.2.2[算法122]需要导数的一维搜索519
12.2.3[算法123]Powell方法522
12.2.4[算法124]共轭梯度法525
12.2.5[算法125]准牛顿法531
12.2.6【实例71】验证不使用导数的一维搜索536
12.2.7【实例72】用Powell算法求极值537
12.2.8【实例73】用共轭梯度法求极值539
12.2.9【实例74】用准牛顿法求极值540
12.3单纯形法542
12.3.1[算法126]求无约束条件下n维极值的单纯形法542
12.3.2[算法127]求有约束条件下n维极值的单纯形法548
12.3.3[算法128]解线性规划问题的单纯形法556
12.3.4【实例75】用单纯形法求无约束条件下N维的极值568
12.3.5【实例76】用单纯形法求有约束条件下N维的极值569
12.3.6【实例77】求解线性规划问题571
第13章随机数产生与统计描述574
13.1均匀分布随机序列574
13.1.1[算法129]产生0到1之间均匀分布的一个随机数574
13.1.2[算法130]产生0到1之间均匀分布的随机数序列576
13.1.3[算法131]产生任意区间内均匀分布的一个随机整数577
13.1.4[算法132]产生任意区间内均匀分布的随机整数序列578
13.1.5【实例78】产生0到1之间均匀分布的随机数序列580
13.1.6【实例79】产生任意区间内均匀分布的随机整数序列581
13.2正态分布随机序列582
13.2.1[算法133]产生任意均值与方差的正态分布的一个随机数582
13.2.2[算法134]产生任意均值与方差的正态分布的随机数序列585
13.2.3【实例80】产生任意均值与方差的正态分布的一个随机数587
13.2.4【实例81】产生任意均值与方差的正态分布的随机数序列588
13.3统计描述589
13.3.1[算法135]分布的矩589
13.3.2[算法136]方差相同时的t分布检验591
13.3.3[算法137]方差不同时的t分布检验594
13.3.4[算法138]方差的F检验596
13.3.5[算法139]卡方检验599
13.3.6【实例82】计算随机样本的矩601
13.3.7【实例83】t分布检验602
13.3.8【实例84】F分布检验605
13.3.9【实例85】检验卡方检验的算法607
第14章查找609
14.1基本查找609
14.1.1[算法140]有序数组的二分查找609
14.1.2[算法141]无序数组同时查找最大和最小的元素611
14.1.3[算法142]无序数组查找第M小的元素613
14.1.4【实例86】基本查找615
14.2结构体和磁盘文件的查找617
14.2.1[算法143]无序结构体数组的顺序查找617
14.2.2[算法144]磁盘文件中记录的顺序查找618
14.2.3【实例87】结构体数组和文件中的查找619
14.3哈希查找622
14.3.1[算法145]字符串哈希函数622
14.3.2[算法146]哈希函数626
14.3.3[算法147]向哈希表中插入元素628
14.3.4[算法148]在哈希表中查找元素629
14.3.5[算法149]在哈希表中删除元素631
14.3.6【实例88】构造哈希表并进行查找632
第15章排序636
15.1插入排序636
15.1.1[算法150]直接插入排序636
15.1.2[算法151]希尔排序637
15.1.3【实例89】插入排序639
15.2交换排序641
15.2.1[算法152]气泡排序641
15.2.2[算法153]快速排序642
15.2.3【实例90】交换排序644
15.3选择排序646
15.3.1[算法154]直接选择排序646
15.3.2[算法155]堆排序647
15.3.3【实例91】选择排序650
15.4线性时间排序651
15.4.1[算法156]计数排序651
15.4.2[算法157]基数排序653
15.4.3【实例92】线性时间排序656
15.5归并排序657
15.5.1[算法158]二路归并排序658
15.5.2【实例93】二路归并排序660
第16章数学变换与滤波662
16.1快速傅里叶变换662
16.1.1[算法159]复数据快速傅里叶变换662
16.1.2[算法160]复数据快速傅里叶逆变换666
16.1.3[算法161]实数据快速傅里叶变换669
16.1.4【实例94】验证傅里叶变换的函数671
16.2其他常用变换674
16.2.1[算法162]快速沃尔什变换674
16.2.2[算法163]快速哈达玛变换678
16.2.3[算法164]快速余弦变换682
16.2.4【实例95】验证沃尔什变换和哈达玛的函数684
16.2.5【实例96】验证离散余弦变换的函数687
16.3平滑和滤波688
16.3.1[算法165]五点三次平滑689
16.3.2[算法166]α-β-γ滤波690
16.3.3【实例97】验证五点三次平滑692
16.3.4【实例98】验证α-β-γ滤波算法693

E. GPU上图像拼接的快速计算

图像拼接已被研究并广泛应用于计算机科学的许多领域，但在特征匹配、扭曲和混合步骤中存在大量计算。从而无法满足某些应用的实时性需求。幸运的是，已经在图形处理器单元 (GPU) 上开发并实现了一些可以加快拼接过程的相关并行操作。在本文中，我们使用统一计算设备架构 (CUDA) 提出了基于 GPU 的图像拼接的并行实现。我们在执行时间方面获得了比在中央处理单元 (CPU) 上实现更好的结果。在实验中使用集成 GPU GTX745 时，我们对大输入图像实现了高达 27.6 倍的加速比。

典型的拼接过程主要包括三个不同的图像处理步骤，即配准、扭曲和插值以及混合。图像配准是图像拼接的关键任务。配准是指在描绘同一场景的一对图像之间建立几何变换，该变换由一个8自由度的平面单应性决定。

GPU以其强大的并行计算能力吸引许多领域的研究，作为一种协处理器对计算量大的算法加速已成为实践的重要途径。在前人的研究中，他们都避免了考虑两个极其耗时的步骤，即特征匹配和随机样本共识（RANSAC）。作为图像配准中的两个关键过程，在提出的 GPU 加速并行算法中应考虑它们。

使用GPU并行计算会遇到两个限制

CUDA的出现解决了上述问题，并且CUDA使用C语言，最初为CPU编写的C语言函数可以移植到CUDA内核，无需修改。

在CUDA中，一定数量的线程被分组到一个块中，一定数量的块以规则的网格模式在逻辑上排列（见图1）。每个块都映射到一个多处理器，一个多处理器可以同时运行多个线程块。由于本地资源（寄存器和共享内存）在块之间进行划分，包含在同一块中的线程可以访问相同的共享内存并快速实现同步操作。但是，不同块中的线程并不能直接实现通信和同步。除了本地寄存器和共享内存，所有线程都可以访问全局内存、常量内存和纹理内存。

A. 特征匹配

令点 经过仿射变换后得到 ，即

向量 是平移分量， 控制缩放、旋转效果。利用齐次坐标系，方程(2)也可以写为

接着计算两幅图像特征点之间的欧几里得距离，并将距离按照升序排序，比较升序排序中第一和第二的比值如果小于某个阈值，则认为是匹配点。

由于 中有六个未知参数，随机选择3对不共线的点匹配 ，使用该矩阵 计算剩余 对匹配点的误差。执行大量迭代，直到内点对最多。可以使用最小二乘估计器估计所有六个参数。

B. 变形和插值

扭曲变形过程中，可能使像素点位置出现负值或者没有数值与之对应，在这种抢矿下需要插值算法创建更平滑和准确的数值，进一步减少翘曲中产生的变形。最常用的插值方法是最近邻插值、双线性插值和双三次插值。考虑到精度和计算复杂度之间的权衡，实验采用双线性插值算法。

C. 混合

为了实现并行计算，本文采用了基于羽化的混合方法，其混合函数可以表示为：

其中 是像素 的权重函数。

A. 并行匹配

匹配分为粗匹配和精匹配。粗匹配过程中，块线程数由特征元素数决定，每个块可以实现一个关键点之间的匹配，每个线程计算两个图像两个特征向量的距离。在计算完所有距离后，使用并行计算的归并排序对距离值排序。最后，所有块得到的匹配结果存储在全局内存中，然后传送到CPU。

精匹配过程，设计内核执行RANSAC迭代，只启动一个block，线程数为 ，首先用CPU将三个非共线点计算得到的变换矩阵 ，然后将 、阈值和剩余 个点传到GPU，判断内外点。

通过内存分配，可以实现精细匹配优化。

B. 平行变形和插值

将 矩阵的逆矩阵 存放在常量内存中，由于需要频繁地调用。将待校正的图像存放在纹理内存中，纹理内存是专门为本地访问模式设计的。

为了进一步提升性能，若两个坐标小数部分小于0.2则强度值分配为整数部分，否则使用双线性插值。

C. 并行混合

由于混合数是像素和像素的混合，因此线程数等于重叠部分包含的像素。令重叠图像的列数设置为16的倍数。 gridDim.x的大小等于重叠图像的行数，gridDim.y的大小等于重叠图像的列数重叠图像除以16。

基于 CPU 的算法在配备 16GMB DDR3 RAM 的 Intel Core i7-4790、3.60GHz 处理器上实现。基于 GPU 的算法在 NVIDIA GeForce GTX745 集成显卡上进行测试，每块最大 1024 个线程和 4096 MB 全局内存。

可以清楚地看到，这两种图像之间几乎没有差异。原因是实验中使用的GPU卡支持浮点计算，与CPU版本相比产生的误差非常小。

在本文中，我们提出了一种使用 CUDA 架构在 GPU 上运行的并行图像拼接方法。顺序算法通过几个 CUDA 内核转换为并行版本。通过使用不同类型的内存，我们实现了并行算法的优化。同时，将GPU获得的结果与CPU获得的结果进行比较，我们实现了高达27.6的加速比。尽管所提出的方法显着提高了计算性能，但仍有许多工作要做。例如，更精确的插值方法（双三次插值）和可变权重 c( x, y) 可以考虑进一步改善镶嵌结果。此外，并行镶嵌算法也可以在多个GPU平台上运行，对于大数据可以更有效地执行算法。在今后的工作中，我们将一一处理这些问题。