基于加窗SIFT和分布式優(yōu)化的多圖自動(dòng)拼接算法

柯磊　劉福強(qiáng)　康琦

摘 要： 針對(duì)無(wú)先驗(yàn)信息傳統(tǒng)算法中普遍存在的誤差累計(jì)問(wèn)題，提出基于加窗尺度不變特征變換（W?SIFT）和分布式優(yōu)化的多圖自動(dòng)拼接算法。根據(jù)多圖拼接應(yīng)用的特性，對(duì)尺度不變特征變換算法進(jìn)行修改，提出加窗SIFT算法更高效地提取待拼接圖像的特征點(diǎn)。運(yùn)用隨機(jī)抽樣一致（RANSAC）算法計(jì)算出兩兩圖像的變換矩陣。之后，建立了一個(gè)分布式優(yōu)化模型，求解出多圖拼接的全局最優(yōu)解。實(shí)驗(yàn)結(jié)果表明，基于加窗SIFT和分布式優(yōu)化的多圖自動(dòng)拼接算法能夠有效地消除誤差累積現(xiàn)象，能夠得到更加精確的多圖拼接結(jié)果。

關(guān)鍵詞： 分布式優(yōu)化算法； 分布式優(yōu)化模型； 尺度不變特征變換； 隨機(jī)抽樣一致； 多圖自動(dòng)拼接

中圖分類號(hào)： TN911.73?34； TP181 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2017）07?0059?04

Multi?image automatic splicing algorithm based on windowed?SIFT

and distributed optimization

KE Lei1， LIU Fuqiang2， KANG Qi2

（1. School of Transportation and Automobile Engineering， Panzhihua University， Panzhihua 617000， China；

2. School of Information and Electronics， Beijing Institute of Technology， Beijing 100081， China）

Abstract： Aiming at the error accumulation problem existing in the traditional algorithms without prior information， a multi?image automatic splicing algorithm based on windowed scale invariant feature transformation （W?SIFT） and distributed optimization is proposed. The scale invariant feature transformation algorithm is modified according to the application characteristics of the multi?image splicing. The W?SIFT algorithm is proposed to extract the feature points of the splicing image efficiently. The random sample consensus （RANSAC） method is used to calculate the transformation matrix of two images. A distributed optimization model was established to solve the global optimal solution of the multi?image splicing. The experimental results show that the multi?image automatic splicing algorithm based on W?SIFT and distributed optimization can eliminate the error accumulation phenomenon effectively， and obtain the accurate multi?image splicing results.

Keywords： distributed optimization algorithm； distributed optimization model； scale invariant feature transformation； random sample consensus； multi?image automatic splicing

0 引 言

圖像拼接是計(jì)算機(jī)視覺(jué)中的一項(xiàng)重要研究方向，特別是在車載場(chǎng)景構(gòu)建和街景生成中有廣泛的應(yīng)用。尤其是在數(shù)字地圖，數(shù)字城市和自動(dòng)駕駛等日益發(fā)展和普及的背景下，自動(dòng)多幅圖像拼接算法更是吸引了廣泛的關(guān)注和研究。

在多幅圖像拼接應(yīng)用領(lǐng)域，有兩類應(yīng)用廣泛的技術(shù)手段：一類是依據(jù)相機(jī)的先驗(yàn)位置信息的算法[1]；另一類是不需要相機(jī)先驗(yàn)位置信息的算法[2?3]?；谙鄼C(jī)信息的這類算法依據(jù)相機(jī)信息計(jì)算出圖像的相對(duì)位置，再進(jìn)行圖像拼接。這類方法應(yīng)用廣泛，并且也有良好的精度，但時(shí)刻需要知道相機(jī)的位置信息。

對(duì)于不需要相機(jī)先驗(yàn)信息的多圖拼接算法，是基于兩幅圖像的自動(dòng)拼接算法，拓展到多幅圖像拼接應(yīng)用中。Lowe提出的尺度不變特征變換（Scale Invariant Feature Transform，SIFT）特征提取精確，被廣泛的應(yīng)用在自動(dòng)配準(zhǔn)、拼接領(lǐng)域。但依據(jù)迭代公式將其運(yùn)用到多幅圖像拼接算法中，會(huì)存在誤差累積的問(wèn)題。特別當(dāng)圖像數(shù)量增加時(shí)，誤差明顯。

針對(duì)無(wú)先驗(yàn)信息多圖拼接算法誤差累積的問(wèn)題，本文基于加窗尺度不變特征變換（Windowed Scale Invariant Feature Transformation，W?SIFT）和分布式優(yōu)化算法，提出一種不需要先驗(yàn)信息的多圖自動(dòng)拼接算法。首先，依據(jù)多圖拼接的特性修改了傳統(tǒng)尺度不變特征變換算法，提出W?SIFT，能夠快速地提取待拼接圖像的有效特征點(diǎn)。其次，運(yùn)用隨機(jī)抽樣一致（Random Sample Consensus，RANSAC）算法計(jì)算出兩兩圖像的變換矩陣。之后，建立了一個(gè)分布式優(yōu)化模型用于消除誤差累積。求解這個(gè)分布式優(yōu)化模型便可得到全局最優(yōu)多圖拼接結(jié)果。最后，本文進(jìn)行了一系列對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果說(shuō)明本文的算法能夠高效地實(shí)現(xiàn)多幅圖像拼接，在精度上比傳統(tǒng)算法有較大提高。

1 加窗尺度不變特征變換算法

Lowe 提出了尺度不變特征變換（SIFT），被廣泛地應(yīng)用在計(jì)算機(jī)視覺(jué)各個(gè)領(lǐng)域。其中，在圖像拼接和圖像配準(zhǔn)應(yīng)用中均取得了成功。然而，Lowe的尺度不變特征變換的算法復(fù)雜度是相對(duì)較高的，本文針對(duì)多幅圖像拼接的應(yīng)用背景，對(duì)SIFT進(jìn)行了相應(yīng)的修改，提出了加窗尺度不變特征變換（W?SIFT）算法。W?SIFT在能夠滿足拼接需求的基礎(chǔ)上減少了算法的復(fù)雜度。

1.1 尺度不變特征變換

SIFT包含三個(gè)基礎(chǔ)模塊：差分高斯金字塔，興趣點(diǎn)篩選和描述子生成。差分高斯金字塔（DOG）用于提取尺度不變和選擇不變的特征點(diǎn)；極值點(diǎn)檢測(cè)用于刪除邊緣的點(diǎn)和不顯著的點(diǎn)，以及對(duì)特征點(diǎn)進(jìn)行擬合；描述子生成用于生成有區(qū)別能力的描述子。如圖1所示，SIFT算法中，描述子生成占用計(jì)算時(shí)間約為總體時(shí)間的73%，差分高斯金字塔占用計(jì)算時(shí)間約為24%。

1.2 加窗算法

在多幅圖像拼接的應(yīng)用中，尺度變換并不是顯著的，而旋轉(zhuǎn)和仿射變換情況較顯著；拼接與配準(zhǔn)不同，拼接的有效區(qū)域在圖像周邊，而圖像內(nèi)部區(qū)域的作用并不顯著?；谏鲜鰞牲c(diǎn)特性，對(duì)傳統(tǒng)的SIFT算法進(jìn)行改進(jìn)，提出W?SIFT算法，在保證拼接有效性的基礎(chǔ)上，降低了算法的復(fù)雜度。

W?SIFT算法流程如圖2所示。首先，利用高斯尺度空間替代原始算法中的高斯金字塔，這樣一方面節(jié)省了建立高斯金字塔的時(shí)間，另一方面也減少了一部分低分辨率（高層級(jí)）的特征點(diǎn)。低分辨率的特征點(diǎn)在拼接中是較少用到的，并且生成這些低分辨率特征點(diǎn)的描述子需要更復(fù)雜的計(jì)算。減少低分辨率特征點(diǎn)會(huì)節(jié)約更多的計(jì)算時(shí)間。

高斯空間和差分高斯空間的構(gòu)建方式如下：

[L（x，y，σ）=12πσ2e-（x2+y2）2σ2*I（x，y）] （1）

[D（x，y，σ）=L（x，y，kσ）-L（x，y，σ）] （2）

式中[Ix，y]代表輸入圖像。

在差分高斯空間中引入理想窗函數(shù)，限制特征點(diǎn)的空間范圍，理想窗函數(shù)如下：

[f（x，y）=1， x<τ，A-x<τ，y<τ，B-y<τ0， other] （3）

式中：[x，y]為像素坐標(biāo)；[A，B]為圖像尺寸；[τ]為有效拼接特征點(diǎn)的區(qū)域范圍。

通過(guò)上述手段，W?SIFT生成的特征點(diǎn)較原始SIFT的特征點(diǎn)大幅度減少，同時(shí)又保證了拼接應(yīng)用具備足夠的有效特征點(diǎn)。并且，W?SIFT不需要在大范圍進(jìn)行特征點(diǎn)的描述，這樣也大大減低了描述子生成的算法復(fù)雜度。

1.3 仿射變換與圖像拼接

仿射變換能很恰當(dāng)?shù)乇碚鲌D像拼接的坐標(biāo)變換關(guān)系，仿射變換公式[4]如下：

[x=a1x+b1y+c1y=a2x+b2y+c2] （4）

式中：[x，y]和[x，y]分別代表待拼接圖像和基準(zhǔn)圖像。

設(shè)[X=x，y，1T，][X′=x′，y′，1T，]式（4）可寫成向量形式，具體如下：

其中：[X′=HXH=a1b1c1a2b2c2111]

圖像拼接的任務(wù)便是估計(jì)式（4）的各個(gè)參數(shù)，也就是估計(jì)式（5）中的變化矩陣[H。]

本文首先運(yùn)用W?SIFT提取出待拼接圖像和基準(zhǔn)圖像中的特征點(diǎn)，再采用歐式距離最小的原則計(jì)算特征點(diǎn)的匹配對(duì)，最后利用隨機(jī)抽樣一致（RANSAC）[5]算法來(lái)估計(jì)轉(zhuǎn)換矩陣[H。]

2 分布式優(yōu)化與多圖拼接

提出的W?SIFT算法實(shí)現(xiàn)待拼接圖像和基準(zhǔn)圖像的特征點(diǎn)提取，利用RANSAC方法實(shí)現(xiàn)轉(zhuǎn)換矩陣估計(jì)，從而完成待匹配圖像與基準(zhǔn)圖像的拼接。傳統(tǒng)的多圖拼接方法在此基礎(chǔ)上逐級(jí)遞推，這樣就造成了誤差的累積。本文在傳統(tǒng)多圖拼接算法的基礎(chǔ)上，推出了一種能夠消減誤差累積的分布式優(yōu)化算法，用于實(shí)現(xiàn)高精度的多圖拼接。

2.1 傳統(tǒng)的多圖拼接模型

傳統(tǒng)的多圖拼接的主要思想是以某一幅圖為基準(zhǔn)，在拼接時(shí)，某一幅圖與基準(zhǔn)圖像的轉(zhuǎn)換矩陣為基準(zhǔn)圖像的變換矩陣，當(dāng)前圖像與前一幅圖像的變換矩陣和前一幅圖像與基準(zhǔn)圖像的轉(zhuǎn)換矩陣三者的積。具體公式[3]如下：

[Hk=ΔHkHk，k-1Hk-1] （6）

式（6）展開(kāi)則如下：

[Hk=ΔHkHk，k-1ΔHk-1Hk-1，k-2…ΔH1H1，0H0] （7）

式中：基準(zhǔn)圖像為第0幅，[Hk]代表第[k]幅圖像與基準(zhǔn)圖像的變換矩陣；[ΔHk]攜帶每次拼接完成基準(zhǔn)圖像坐標(biāo)產(chǎn)生的變化信息；[Hk，k-1]代表第[k]幅圖像與第[k-1]幅圖像的變換矩陣；[H0]為單位對(duì)角陣。

可見(jiàn)，前一幅圖像拼接誤差會(huì)累積到之后的圖像拼接中，會(huì)對(duì)多幅圖像拼接產(chǎn)生較大的誤差，尤其是圖像數(shù)目較多的情況下。

2.2 分布式優(yōu)化算法

設(shè)[Hk]為第[k]幅圖像到拼接結(jié)果圖像變換矩陣的最優(yōu)估計(jì)，[pk]為第[k]幅圖像的特征點(diǎn)集，[p]為拼接結(jié)果圖像的特征點(diǎn)集，則：

[Hk=argminHkp-Hkpk2] （8）

式中[p]是未知的，用式（9）對(duì)[p]進(jìn)行估計(jì)。式（8）的物理意義是：[Hk]應(yīng)使拼接變換后的圖像與拼接變換前的圖像對(duì)應(yīng)位置像素保持一致。

式（8）中，[pk]是已知量，而[p]是未知量，因此需要對(duì)[p]進(jìn)行估計(jì)。估計(jì)[p]的思想是：在給定部分[p]初始值為[p0]的情況下，在第[k]次迭代，將第[k-1]次的[p]的最優(yōu)估計(jì)[pk-1]進(jìn)行拼接變換的點(diǎn)，即[Hk-1pk-1]，作為第[k]次[p]點(diǎn)集合的擴(kuò)展。具體迭代公式如下：

[p={H0p0，H1p1，H2p2，…，Hk-1pk-1}] （9）

式中[p]在求取[Hk]時(shí)是變化的。

式（8），式（9）是利用優(yōu)化的方法來(lái)盡可能消減誤差累積，之所以不是避免誤差累積的原因是：在不給定初始值的情況下，分布式優(yōu)化會(huì)成為一個(gè)不適定問(wèn)題（ill?posed problem）。因此在解決上述問(wèn)題時(shí)給定一個(gè)初始值，即為[p0]。

3 實(shí) 驗(yàn)

本文進(jìn)行了一系列實(shí)驗(yàn)來(lái)驗(yàn)證上述算法的有效性。實(shí)驗(yàn)是在Matlab R2013a下進(jìn)行仿真，計(jì)算機(jī)性能參數(shù)為：Intel[?] Core[?] i5?3470 CPU，4 GB RAM，64位操作系統(tǒng)。實(shí)驗(yàn)仿真使用的圖像均為[728×408]的24位深圖。

3.1 特征提取實(shí)驗(yàn)

本文分別用SIFT以及W?SIFT方法實(shí)現(xiàn)特征點(diǎn)提取，并對(duì)其性能進(jìn)行比較，實(shí)驗(yàn)結(jié)果如圖3，圖4所示。

對(duì)比圖3，圖4可以發(fā)現(xiàn)，W?SIFT算法對(duì)于有效特征點(diǎn)的提取更加高效，省略了在拼接中較少使用的特征點(diǎn)。在圖3，圖4中，黃圈面積代表待生成特征點(diǎn)描述子的遍歷范圍，W?SIFT算法遍歷范圍小，運(yùn)算量下降。

3.2 多圖拼接實(shí)驗(yàn)

利用W?SIFT算法提取特征點(diǎn)后，采取分布式優(yōu)化算法實(shí)現(xiàn)多圖拼接，對(duì)20幅圖像進(jìn)行多圖拼接后的實(shí)驗(yàn)結(jié)果如圖5所示。

利用W?SIFT以及分布式優(yōu)化算法實(shí)現(xiàn)多圖拼接，利用均方根誤差衡量拼接精度，并結(jié)合算法使用時(shí)間衡量多圖拼接算法的性能，對(duì)比結(jié)果如表2所示。

均方根誤差的計(jì)算公式如下：

在表2中，W?SIFT+（8）表示W(wǎng)?SIFT分布式優(yōu)化算法，W?SIFT+（7）表示W(wǎng)?SIFT傳統(tǒng)拼接算法，SIFT+（7）表示SIFT傳統(tǒng)拼接算法，“手動(dòng)”代表手動(dòng)拼接方法。

通過(guò)對(duì)比可知：W?SIFT分布式優(yōu)化算法從算法所需時(shí)間上遠(yuǎn)小于SIFT傳統(tǒng)拼接算法，主要是由于W?SIFT算法節(jié)省運(yùn)算量，算法效率高。W?SIFT分布式優(yōu)化算法與W?SIFT傳統(tǒng)拼接算法有微小差別，是因?yàn)榉植际絻?yōu)化需要進(jìn)行迭代計(jì)算，然而作為多圖拼接算法，算法精度的優(yōu)劣直接影響著拼接圖像的質(zhì)量；從算法性能角度來(lái)看，W?SIFT分布式優(yōu)化算法性能較其余算法有了很大的提升，可以完成高精度多圖拼接。

4 結(jié) 語(yǔ)

本文主要提出了基于W?SIFT的圖像配準(zhǔn)方法和分布式優(yōu)化算法的多圖拼接算法，實(shí)現(xiàn)了無(wú)先驗(yàn)信息的實(shí)際場(chǎng)景圖像的高精度多圖拼接。提出的W?SIFT分布式優(yōu)化算法從運(yùn)算時(shí)間以及圖像拼接性能上得到全面的優(yōu)化。W?SIFT算法為加窗SIFT算法，通過(guò)在差分高斯空間加理想窗函數(shù)完成，W?SIFT算法在不影響性能的基礎(chǔ)上大幅降低了運(yùn)算量，使得算法的實(shí)現(xiàn)效率更高；而分布式優(yōu)化算法可以大幅度消減傳統(tǒng)拼接算法帶來(lái)的誤差累積問(wèn)題。

本文算法雖然大幅度消減了誤差累積現(xiàn)象，但依然存在一定誤差。并且，本文算法依然需要一幅圖像提供分布式優(yōu)化的初始值，也就造成了拼接結(jié)果依然是以一幅圖像為基準(zhǔn)。上述兩方面問(wèn)題需要未來(lái)進(jìn)一步的研究。

參考文獻(xiàn)

[1] ZITOVA B， FLUSSER J. Image registration methods： a survey [J]. Image and vision computing， 2003， 21（11）： 977?1000.

[2] 黃大坤，陸冬良，嚴(yán)志明，等.多圖無(wú)縫拼接的配準(zhǔn)算法[J].微型電腦應(yīng)用，2014（2）：62?65.

[3] SAWHNEY H S， KUMAR R. True multi?image alignment and its application to mosaicing and lens distortion correction [J]. IEEE transactions on pattern analysis and machine intelligence， 1999， 21（3）： 235?243.

[4] SANSOSTI E， BERARDINO P， MANUNTA M， et al. Geometrical SAR image registration [J]. IEEE transactions on geoscience and remote sensing， 2006， 44（10）： 2861?2870.

[5] FISCHLER M A， BOLLES R C. Random sample consensus： a paradigm for model fitting with applications to image analysis and automated cartography [J]. Communications of the ACM， 1981， 24（6）： 381?395.

[6] DE CASTRO E， MORANDI C. Registration of translated and rotated images using finite Fourier transforms [J]. IEEE transactions on pattern analysis and machine intelligence， 1987， 9（5）： 700?703.

[7] LOWE D G. Distinctive image features from scale?invariant keypoints [J]. International journal of computer vision， 2004， 60（2）： 91?110.

[8] BARNEA D I， SILVERMAN H F. A class of algorithms for fast digital image registration [J]. IEEE transactions on compu?ters， 1972， 21（2）： 179?186.

[9] 吳樂(lè)富，丁廣太.基于區(qū)域的圖像拼接算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2010（18）：4044?4046.

[10] 嚴(yán)格.基于灰度相關(guān)特征點(diǎn)的圖像拼接算法[J].包裝工程，2009（4）：82?83.

[11] 李利軍，李云偉.基于圖像灰度的拼接技術(shù)研究[J].計(jì)算機(jī)與數(shù)字工程，2007（9）：128?130.

[12] REDDY B S， CHATTERJI B N. An FFT?based technique for translation， rotation， and scale?invariant image registration [J]. IEEE transactions on image processing， 1996， 5（8）： 1266?1271.