內含動態目標的圖像拼接算法與優化

孫光靈

(安徽建筑大學 信息網絡中心，安徽 合肥 230601)

在計算機圖像領域，為了得到寬幅的全景圖像(panoramic picture)必須將多個圖像拼在一起。

圖像拼接技術(image mosaic)是采用圖像配準和圖像融合技術，解決如何將小幅的照片拼接成一張寬幅照片的問題，以滿足用戶全景攝影的要求，被廣泛應用于遙感圖像處理、虛擬現實技術等領域。

作為研究熱點領域之一，相關的研究人員和學者對這個領域作了探索，取得了一些進展。Barnea提出了一種配準的算法[1]，是最早發表有關圖像配準的文章。1981年，研究者Lucas等運用(Newton-Raphson)圖像迭代法進行有效的匹配[2]，提出了一種從圖像強度估計曝光強度參數和配準參數的一般方法[3]，然后對圖像進行配準和校正。盡管避免了因曝光差異造成的視差問題，但是整體效果并不理想。

增益補償也被用在圖像拼接過程中[4]，即取每個圖像中的平均像素值乘以一個常系數得到的點積來實現，意圖減小補償時函數的誤差。該方法在提高增益同時，也帶來了新的問題。兩幅圖像會因亮度的不同而留下肉眼可見的接縫，由此產生了鬼影或視差。

傳統的圖像拼接算法都是基于靜止背景的[5-6]，多張圖像中的背景是靜止不變。對于具有運動物體的圖像拼接中，Alec Mills等提出的基于縫合線融合方法可以解決拼接具有運動物體后出現的鬼影現象[7]，但是卻丟失了很多運動的目標。基于運動區域單元概念隨后被提出[8]，但是對于多張圖像中出現同一個運動物體并在該物體的位置發生變化時仍然出現鬼影現象。本文基于最佳縫合線的基礎之上進一步完善，通過判斷物體沖突與否來處理物體保留后可能會發生鬼影現象，最后根據非沖突運動物體所處的位置進行縫合線修正。

1 Sift匹配與RANSAC原理

1.1 Sift匹配及原理

Sift稱為尺度不變特征變換，用來把圖像數據轉化局部特征，轉化過程中尺度坐標不發生變化。由于Sift特征是基于圖像的局部特征，具有如下優點：

1) 魯棒性強，對視角變化、仿射變換、噪聲能保持一定的穩定性，對旋轉、尺度縮放、亮度變化也保持不變性；

2) 信息量很大，獨特性也較好，比較適用于數據庫中含有大量特征進行匹配的情形。

3) 多量性，即使少數的幾個物體也可以產生大量Sift特征向量。

Sift主要流程如圖1所示。

圖1 Sift工作過程

其中，在第4步的匹配過程中，一般采用的是歐氏距離進行計算，找到對應的匹配點。

1.1.1 關鍵點檢測方法

二維Gauss函數：

(1)

式中σ稱為高斯核，與尺度坐標相對應。

一幅二維圖像，可以定義為圖像函數I(x,y)與高斯核G(x,y,σ)卷積得到：

(2)

其中，圖像的尺度空間用L表示，。圖像用不同的尺度表示，如同給圖像變換了坐標系，新的坐標值愈小則表明該圖像被平滑的也越小，這時候的尺度值也越小。

1.1.2 描述子

首先必須計算讀取點8鄰域最大梯度值作為主方向。在完成關鍵點的梯度計算后，統計鄰域內像素的梯度和的直方圖，如圖2所示，關鍵點的主方向就是直方圖的峰值方向。

圖2 梯度方向的計算

描述子生成均以此主方向為基礎，確保新生成的描述子具有旋轉不變的特性。

描述子的生成方式如下：

1) 對任意一個關鍵點，在其所在的尺度空間，取以關鍵點為中心的8×8的窗口。

2) 再將每個領域分為16在個子區域,對每個子區域內統計并計算梯度直方圖。

3) 對16個子區域進行排序，排序規則是根據每個子區域的8鄰域梯度直方圖的位置先后，生成了一個128維的向量，得到Sift描述子。

當兩幅圖像的Sift描述子生成后，需要對兩幅圖像中關鍵點的相似性進行度量，準則是采用關鍵點特征向量的歐氏距離進行判定。首先選取待拼接圖像1中的某個關鍵點，搜索其與待拼接圖像2中距離最近的前兩個關鍵點。在這兩個關鍵點中，如果最近的距離除以次近的距離小于某個閾值Q，則搜索出的最近匹配點正確，否則是錯誤匹配。

1.2 RANSAC原理及分析

RANSAC是根據樣本數據集，數據集包括了有效數據和異常數據，通過數據的模型參數計算，得到有效樣本的算法。

RANSAC算法中異常數據產生的原因多種多樣，錯誤的測量、錯誤的假設、錯誤的計算等均可產生的異常數據。RANSAC算法假設，給定一組正確的數據，存在可以計算出正確數據集的方法。

首先，由于特征點的穩定性，在等待拼接的兩幅圖像中尋找灰度梯度最大的點作為特征點；

然后初步建立兩幅圖像重疊范圍內的特征點之間的對應關系，進行圖像間的特征匹配。根據候選匹配特征點對，用RANSAC估計算法，計算出兩幅圖像之間的變換矩陣。通過變換矩陣能夠確定一幅圖像中的點在另一幅圖像中所對應的位置，變換矩陣見式(3)。

(3)

式中mi為變換矩陣元素值，(x,y)和(x′,y′)為候選匹配點對。

RANSAC估計算法的步驟如圖3所示。

圖3 RANSAC估計算法

根據坐標轉換關系將一幅圖像變換到另一幅圖像上，實現兩幅圖像的拼接。

2 圖像拼接

為將數張有重疊部分的圖像拼成一幅無縫高分辨率的寬幅圖像，圖像配準和圖像融合是其中的兩個內容，拼接的過程如下：

1) 對兩幅圖像利用Sift算法進行特征提取。

2) 采用歐氏距離判斷兩幅圖像中的Sift特征的相似性，并查找出匹配的特征對。

3) 利用RANSAC對步驟2的特征對進行處理，消除錯誤的特征對并建立射影矩陣H。

4) 利用射影矩陣H將帶拼接圖像的重合區域進行融合得到拼接重構的平滑無縫全景圖像。

3 搜索策略

由上述圖像拼接方法可以看出，一般的圖像拼接方法在處理具有運動物體時會出現圖像重疊而成的鬼影現象。另一種情況也有些相似，物體雖然不是同一物體，但由于圖像的疊加，使這兩個物體處于同一個位置，從而產生了沖突。參考文獻[1]提出了一種可行的辦法，可以解決這種沖突或鬼影現象，就是在兩張圖像的重疊區域中找出一條縫合線，縫合線會把圖像分成左右兩部分，左邊的部分取左圖像的像素，右邊部分取右圖像的像素，從而解決以上的鬼影和沖突現象。

圖4 實驗拼接圖

圖5 搜索策略

文獻[1]的方法對強度與梯度進行了計算。利用Dijkstra搜索縫合線的思想進行縫合線的搜索。搜索時從重疊區的第一行出發建立該行上每一個像素為起點的縫合線，然后從重疊區域中尋找出一個最佳的縫合線。詳細步驟如下：

Step1：初始化。首先從第一行開始，首行的各列像素點對應為一條縫合線。縫合線的強度值賦各個點的準則值，該縫合線的列值即為初始點。

Step2：延伸擴展。從Step1中計算過強度沿縫合線不斷擴展，直到尾行為止。

Step3：選擇最佳縫合線。從所有計算出的縫合線中選取強度值最小的那一個，作為最佳縫合線。

這種方法雖然可以消除了鬼影和沖突的現象，但是對于一些非沖突的目標，也同時被消去了，從圖5(c)中，右圖中的摩托車因為縫合線偏左而被消掉了。一種改進的算法通過判斷重疊區域中的景象是否沖突，如果非沖突則可以通過修改縫合線保留重疊區域的一些景象，從而使得拼接更加逼真。

4 改進的搜索策略

改進的方法中采用動態規劃的方法進行縫合線的搜索，而非Dijkstra方法。首先分析重疊區域中的兩幅圖像的物體是否有沖突，對于沒有沖突的物體進行提取，在進行拼接的時候修改縫合線，把非沖突的目標也包含進去。

首先對重疊區域的圖像進行二值化，圖6是對圖5(c)的圖像進行二值化。二值圖像中的白色區域是由于兩幅圖像中的不同景物或同一景物位置發生了改變，從而造成疊加不一致。

圖6 配準后圖像二值化

其次，為了標記二值圖像，可以采用的方法有很多，本文是采用了連通域標記方法，根據標記后的結果提取相應連通域的所有像素。對于得到的二值圖像，對其目標可以分為三種情況加以考慮：

1) 同一個物體位置發生了變化，導致疊加時不一致。這種情況可以根據第一部分的Sift進行過濾，因為在進行匹配過程中會用到Sift算法，而對于同一個物體，一般會有很多匹配對，當發現兩個連通域中對應的景物在第一步處理中有正確的匹配對，這說明了該物體是因為發生了位置變化導致疊加不一致，其中的一個連通域可以通過縫合進行切割。

2) 不同時間點拍攝的兩張圖像在某位置分別有兩個不同的物體，在進行疊加時就會發生沖突，這種景物也可以通過縫合線進行切割。圖5(a)中紅色的汽車與圖5(b)中白色的汽車就是這種情況。

3) 某個目標在一張圖像中出現，而在另一張圖像中沒有出現，并且該目標后面的背景與另外一張圖像中對應位置的背景相一致。圖5(b)中的摩托車在圖5(a)中沒有出現就是這種情況。圖5(a)中對應位置位置是空曠的路面。這種情況可采用以下方式解決：

Step1：第一步是統計兩幅圖像中背景點像素值。根據圖6所示的二值圖像，對于像素值為0的點是左右兩幅圖像疊加一致的點，這些點稱為背景點。

Step2：提取圖像6中屬于情況三的目標區域。

Step3：查找步驟二提取的目標區域對應左右圖像區域是否屬于背景區，如果其中一個區域是背景區，說明目標沒沖突，否則按沖突處理。

5 結果與分析

本文的實驗平臺為Intel Core I5-4210M CPU，內存4G，實驗軟件為win8+matlab2012。經過實驗對比，結果如圖7所示。圖7(a)給出的是原算法進行拼接結果，圖7(b)給出的是原算法融合的縫合線。圖7(c)給出的是改進算法的融合效果，從圖7(c)可以看到非沖突的景物(摩托車)被包含到融合圖像中并且是非常自然。圖7(d)給出的是改進算法的縫合線，因為修改后的縫合線與修改前的縫合線所包含的區域沒有沖突物體，所以最終縫合線通過直接水平線平移修改得到。

圖7 算法比較

6 結語

筆者對具有運動物體的圖像拼接方法進行了有效的改進，改進后的方法首先從重疊區域中分析兩幅圖像的背景像素，然后通過分析沖突目標是否存在于重疊區域中，從而確定融合圖像中是否保留此目標。最后通過尋找縫合線，根據非沖突物體的狀態修改縫合線得到最佳的效果。該算法相對于原算法可以生成景物更多的融合圖，包含更全更多的信息，具有一定的實用價值。

參考文獻：

[1]Daniel I.Barnea，Harvey F Silverman. A Class of Algorithms for Fast Digital Image Registration[J]. IEEE Transactions on Computers， 1972， 100(2): 179-186.

[2]Bruce D Lucas，TakeoKanade. An Iterative Image Registration Technique with an Application to Stereo Vision[C].// International Joint Conference on Artificial Intelligence. Morgan Kaufmann Publishers Inc. 1981:674-679.

[3]AseemAgarwala. Efficient Gradient-domain Compositing using Quadtrees[C]. ACM，2007: 94-94.

[4]Yehuda Afek，Ariel Brand. Mosaicking of OrthorectifiedAerial Images[J]. Photogrammetric Engineering and Remote Sensing， 1998，64(2): 115-124.

[5]邵聃，金立左.一種圖像拼接的點特征匹配算法[J].東南大學學報(自然科學版)，2008，38(2)：150-153.

[6]Abdukholikov M, Whangbo T. Fast Image Stitching Method for Handling Dynamic Object Problems in Panoramic Images[J].Ksii Transactions on Internet & Information Systems, 2017, 11(11):5419-5435.

[7]Alec Mills，Gregory Dudek. Image Stitching with Dynamic Elements[J]. Image and Vision Computing，2009， 27(10): 1593-1602.

[8]Brown M, Lowe D G. Automatic Panoramic Image Stitching using Invariant Features[J]. International Journal of Computer Vision, 2007, 74(1):59-73.

[9]Karlinsky L, Dinerstein M, Ullman S. Unsupervised Feature Optimization (UFO): Simultaneous Selection of Multiple Features with their Detection Parameters[C]. CVPR 2009: San Francisco, CA, USA, 2009:1263-1270.

[10]AnatLevin, AssafZomet,ShmuelPeleg,et al. Seamless Image Stitching in the Gradient Domain[J]. Proc Eccv, 2004, 3024:377-389.

[11]RichardSzeliski. Image Alignment and Stitching: aTutorial[J]. Foundations and Trends in Computer Graphics and Vision， 2006，2(1): 1-104.

[12]Heung-Yeung Shum，Richard Szeliski. Systems and Experiment Paper: Construction of Panoramic Image Mosaics with Global and Local Alignment[J]. International Journal of Computer Vision， 2000，36(2): 101-130.

[13]Thomas Porter，Tom Duff. Compositing Digital Images[C]. ACM，1984:253-259.

[14]ShmuelPeleg. Elimination of Seams from Photomosaics[J]. Computer Graphics and Image Processing， 1981， 16(1): 90-94.

[15]Yang Xiong，Ken Turkowski. Registration，Calibration and Blending in Creating High Quality Panoramas[C]. IEEE，1998:69-74.

[16]潘恒輝.圖像拼接中鬼影消除算法研究[J].艦船電子工程，2010，30(3)：125-127.