基于加窗SIFT和分布式優化的多圖自動拼接算法

柯磊　劉福強　康琦

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

關鍵詞： 分布式優化算法； 分布式優化模型； 尺度不變特征變換； 隨機抽樣一致； 多圖自動拼接

中圖分類號： TN911.73?34； TP181 文獻標識碼： A 文章編號： 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 引 言

圖像拼接是計算機視覺中的一項重要研究方向，特別是在車載場景構建和街景生成中有廣泛的應用。尤其是在數字地圖，數字城市和自動駕駛等日益發展和普及的背景下，自動多幅圖像拼接算法更是吸引了廣泛的關注和研究。

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

對于不需要相機先驗信息的多圖拼接算法，是基于兩幅圖像的自動拼接算法，拓展到多幅圖像拼接應用中。Lowe提出的尺度不變特征變換（Scale Invariant Feature Transform，SIFT）特征提取精確，被廣泛的應用在自動配準、拼接領域。但依據迭代公式將其運用到多幅圖像拼接算法中，會存在誤差累積的問題。特別當圖像數量增加時，誤差明顯。

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

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

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

1.1 尺度不變特征變換

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

1.2 加窗算法

在多幅圖像拼接的應用中，尺度變換并不是顯著的，而旋轉和仿射變換情況較顯著；拼接與配準不同，拼接的有效區域在圖像周邊，而圖像內部區域的作用并不顯著?；谏鲜鰞牲c特性，對傳統的SIFT算法進行改進，提出W?SIFT算法，在保證拼接有效性的基礎上，降低了算法的復雜度。

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

高斯空間和差分高斯空間的構建方式如下：

[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]代表輸入圖像。

在差分高斯空間中引入理想窗函數，限制特征點的空間范圍，理想窗函數如下：

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

式中：[x，y]為像素坐標；[A，B]為圖像尺寸；[τ]為有效拼接特征點的區域范圍。

通過上述手段，W?SIFT生成的特征點較原始SIFT的特征點大幅度減少，同時又保證了拼接應用具備足夠的有效特征點。并且，W?SIFT不需要在大范圍進行特征點的描述，這樣也大大減低了描述子生成的算法復雜度。

1.3 仿射變換與圖像拼接

仿射變換能很恰當地表征圖像拼接的坐標變換關系，仿射變換公式[4]如下：

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

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

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

其中：[X′=HXH=a1b1c1a2b2c2111]

圖像拼接的任務便是估計式（4）的各個參數，也就是估計式（5）中的變化矩陣[H。]

本文首先運用W?SIFT提取出待拼接圖像和基準圖像中的特征點，再采用歐式距離最小的原則計算特征點的匹配對，最后利用隨機抽樣一致（RANSAC）[5]算法來估計轉換矩陣[H。]

2 分布式優化與多圖拼接

提出的W?SIFT算法實現待拼接圖像和基準圖像的特征點提取，利用RANSAC方法實現轉換矩陣估計，從而完成待匹配圖像與基準圖像的拼接。傳統的多圖拼接方法在此基礎上逐級遞推，這樣就造成了誤差的累積。本文在傳統多圖拼接算法的基礎上，推出了一種能夠消減誤差累積的分布式優化算法，用于實現高精度的多圖拼接。

2.1 傳統的多圖拼接模型

傳統的多圖拼接的主要思想是以某一幅圖為基準，在拼接時，某一幅圖與基準圖像的轉換矩陣為基準圖像的變換矩陣，當前圖像與前一幅圖像的變換矩陣和前一幅圖像與基準圖像的轉換矩陣三者的積。具體公式[3]如下：

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

式（6）展開則如下：

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

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

可見，前一幅圖像拼接誤差會累積到之后的圖像拼接中，會對多幅圖像拼接產生較大的誤差，尤其是圖像數目較多的情況下。

2.2 分布式優化算法

設[Hk]為第[k]幅圖像到拼接結果圖像變換矩陣的最優估計，[pk]為第[k]幅圖像的特征點集，[p]為拼接結果圖像的特征點集，則：

[Hk=argminHkp-Hkpk2] （8）

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

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

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

式中[p]在求取[Hk]時是變化的。

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

3 實 驗

本文進行了一系列實驗來驗證上述算法的有效性。實驗是在Matlab R2013a下進行仿真，計算機性能參數為：Intel[?] Core[?] i5?3470 CPU，4 GB RAM，64位操作系統。實驗仿真使用的圖像均為[728×408]的24位深圖。

3.1 特征提取實驗

本文分別用SIFT以及W?SIFT方法實現特征點提取，并對其性能進行比較，實驗結果如圖3，圖4所示。

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

3.2 多圖拼接實驗

利用W?SIFT算法提取特征點后，采取分布式優化算法實現多圖拼接，對20幅圖像進行多圖拼接后的實驗結果如圖5所示。

利用W?SIFT以及分布式優化算法實現多圖拼接，利用均方根誤差衡量拼接精度，并結合算法使用時間衡量多圖拼接算法的性能，對比結果如表2所示。

均方根誤差的計算公式如下：

在表2中，W?SIFT+（8）表示W?SIFT分布式優化算法，W?SIFT+（7）表示W?SIFT傳統拼接算法，SIFT+（7）表示SIFT傳統拼接算法，“手動”代表手動拼接方法。

通過對比可知：W?SIFT分布式優化算法從算法所需時間上遠小于SIFT傳統拼接算法，主要是由于W?SIFT算法節省運算量，算法效率高。W?SIFT分布式優化算法與W?SIFT傳統拼接算法有微小差別，是因為分布式優化需要進行迭代計算，然而作為多圖拼接算法，算法精度的優劣直接影響著拼接圖像的質量；從算法性能角度來看，W?SIFT分布式優化算法性能較其余算法有了很大的提升，可以完成高精度多圖拼接。

4 結 語

本文主要提出了基于W?SIFT的圖像配準方法和分布式優化算法的多圖拼接算法，實現了無先驗信息的實際場景圖像的高精度多圖拼接。提出的W?SIFT分布式優化算法從運算時間以及圖像拼接性能上得到全面的優化。W?SIFT算法為加窗SIFT算法，通過在差分高斯空間加理想窗函數完成，W?SIFT算法在不影響性能的基礎上大幅降低了運算量，使得算法的實現效率更高；而分布式優化算法可以大幅度消減傳統拼接算法帶來的誤差累積問題。

本文算法雖然大幅度消減了誤差累積現象，但依然存在一定誤差。并且，本文算法依然需要一幅圖像提供分布式優化的初始值，也就造成了拼接結果依然是以一幅圖像為基準。上述兩方面問題需要未來進一步的研究。

參考文獻

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

[2] 黃大坤，陸冬良，嚴志明，等.多圖無縫拼接的配準算法[J].微型電腦應用，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] 吳樂富，丁廣太.基于區域的圖像拼接算法[J].計算機工程與設計，2010（18）：4044?4046.

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

[11] 李利軍，李云偉.基于圖像灰度的拼接技術研究[J].計算機與數字工程，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.