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平台上運行，對於大數據可以更有效地執行演算法。在今後的工作中，我們將一一處理這些問題。