基于移動最小二乘法的視差圖像拼接

楚東東 李海晟

(華東師范大學計算機科學與軟件工程學院 上海 200062)

?

基于移動最小二乘法的視差圖像拼接

楚東東 李海晟

(華東師范大學計算機科學與軟件工程學院 上海 200062)

對于視差圖像拼接，現有的工作大都采用單應性變換，這不足以得到好的拼接結果。提出一個新的視差圖像拼接算法。首先檢測圖像的特征點并匹配，隨后用隨機采樣一致算法RANSAC(Random Sample Consensus)和距離相似性篩選出正確的匹配點集；其次，以這些特征點結合移動最小二乘法構造一個全局仿射變換對準圖像；最后，在圖像的重疊區域以像素為頂點構建一個網絡流，用最大流最小割算法尋找最優拼接曲線，并融合圖像。由于提高了特征點匹配的正確性，對準模型的準確性明顯好于以前的工作，圖像拼接結果平滑真實，無扭曲、鬼影等現象。

圖像拼接 特征點匹配 移動最小二乘法 拼接曲線

0 引 言

圖像拼接是計算機圖形學和圖像處理領域的一個研究方向，受到很多研究者的廣泛關注[1-6]。早期的工作解決了重疊區域比較多或者拍攝角度比較一致的圖像拼接問題，主要用一個2D變換矩陣，如單應性矩陣，來對準兩幅圖像[1,6]。部分優秀的方法已集成到商業軟件中，如Adobe Photoshop等。但是實際情況中，因手持相機的角度和方向容易變化，拍攝的相片間往往存在視差。對于這樣的圖像，用上述的2D矩陣來對準和拼接，容易導致幾何結構斷裂和鬼影等一系列問題。盡管使用一些圖像處理方法，如圖像分割[7-8]和圖像融合等技術[9-10]，能夠緩解一些這種人工痕跡現象，但這些圖像處理技術只是部分提高圖像拼接質量，沒有從根本上解決視差圖像間的拼接問題。傳統方法拼接視差圖像不理想的主要原因是一個2D單應性矩陣不能很好地對準有視差圖像的重疊部分，因此近期的圖像拼接工作集中在視差圖像的對準模型方面。這些模型基本上是基于特征的變換方法，很好地提高了視差圖像的拼接質量。但仍舊沒有一種拼接方法能夠完美地解決視差圖像間的拼接問題，這仍是一個挑戰性的課題。

提高特征點匹配的正確性是本文的主要工作，我們提出了距離相似性衡量方法，結合隨機采樣一致算法(RANSAC)[11]，有效地去除特征點之間的錯誤匹配。為了能使一幅圖像的特征點準確地變換到另一幅圖像對應的特征點，我們選用基于移動最小二乘法的變形方法。由此，本文提出了一個新的圖像對準模型。對準了視差圖像后，我們在變形圖像和參考圖像的重疊區域構建網絡流模型，尋找一條合理的拼接線，兩幅圖像沿此曲線進行拼接。

1 相關工作

從20世紀80年代開始，研究圖像拼接問題已有二十多年的歷史，迄今為止積累了許多成果。完整地回顧拼接算法沒有必要，也不在本文的范疇之內，讀者可參閱Szeliski寫的圖像拼接教程[12]。這里我們對近期的視差圖像的拼接工作做一個概要的回顧。

為了得到更好的圖像對準結果，近年來不少研究者提出多種方法。Gao等[13]提出雙單應性變換的思想，他們的方法針對于一種特別的場景，這種場景可以主要分為兩個平面：地平面和遠地面。很顯然這種雙單應性變換很難擴展到任意場景，因為不是所有的場景都可以分成兩個平面，可能場景中只有一個主要的結構或者超過兩個主要的平面。Zaragoza等[2]提出一種投影變換拼接技術，他們把移動直接線性變換和投影變換結合起來形成圖像對準模型，這種方法在圖像視差較小時可以得到很完美的拼接結果，但當圖像視差較大時會出現鬼影等人工痕跡。最近，Zhang等[14]提出一種混合的圖像對準模型，其中包括單應性變換和內容保持變換，此方法只要求圖像存在一個局部區域可以完美的對準。這種方法在圖像視差較大時也可以得到較好的拼接結果，標準的圖割和多帶融合技術同樣應用于此方法。但在非重疊區域，圖像的變形結果有時會出現失真的現象，因為作者強調局部的對準而非全局的圖像對準。

2 視差圖像拼接

視差圖像的拼接算法已有不少，它們的流程基本上相同，大致可以分成以下三個步驟：首先檢測圖像的SIFT特征點，并進行匹配[15]；由于匹配的結果通常包含一些錯誤的匹配點對，因此要對特征點進行篩選，剔除錯誤的匹配點對，通常使用RANSAC；其次，用得到的SIFT匹配點對來對準圖像，一般運用圖像變形的方法實現；最后，對初步對準的圖像直接進行融合拼接或者尋找合理的分割線進行拼接融合。本文的工作采用這個拼接流程，在SIFT特征點的篩選方面，提出了距離相似性方法，進一步驗證RANSAC算法初選后的匹配點的正確性；圖像變形方面，我們使用移動最小二乘法把特征點精確地變到參考圖上對應的點，提高對準精度；最后，用圖割算法計算合理的拼接線。

2.1 特征點選擇

SIFT是一種基于梯度的特征點，具有尺度、光照和旋轉不變性。基于特征的圖像對準模型大都使用SIFT特征點[1-2,13-14]。然而由于它是一種局部的特征點，不含圖像的全局結構信息，所以匹配結果經常包含一些錯誤，尤其當圖像中含有多個類似結構性強的物體，容易把一個物體上的SIFT點匹配到另一個相似的物體上，如圖1所示。圖中圓圈表示SIFT特征點，直線表示匹配結果，很明顯這個結果包含了一些錯誤的特征點匹配。

圖1 出現錯誤對應的SIFT匹配結果

在提取和初步匹配SIFT特征點后，我們用RANSAC算法來對SIFT的匹配結果進行第一步篩選，以去除一些錯誤的匹配。隨機選取四組特征點對，由此構造一個單應性矩陣H，用H去檢測圖像中所有的對應特征點對(p,q)，如果‖Hp-q‖

由于單應性矩陣能保持點的相對位置關系，RANSAC方法去除了大多數的異常匹配。但由于RANSAC使用閾值選取特征點對，具有一定的容忍度，所以對較小的位置扭曲可能會漏檢。為了去除這類錯誤的對應關系，我們分析了圖像拼接的特性： 首先，兩張圖片的尺寸差異不會過分懸殊，因此特征點間的距離基本不變和位置相似；其次，錯誤匹配的特征點比較少，可認為錯誤匹配的特征點附近有正確的特征點對。基于以上觀察，我們使用距離相似性方法進一步篩選特征點對，這個方法類似于Igarashi1等人提出的圖形變形方法[16]。設(p,q)是一對匹配的特征點，p1和p2是與p距離最近的兩個特征點，與它們對應的兩個特征點分別是q1和q2。

我們可用向量p2-p1和它繞點p1逆時針旋轉90度的向量(p2-p1)⊥構建的局部坐標系表示點p：

p=p1+u(p2-p1)+v(p2-p1)⊥

(1)

(p,q)被認為是一個正確的匹配，如果這三個特征點對間滿足下面的公式：

‖q1+u(q2-q1)+v(q2-q1)⊥-q‖

(2)

其中s是一個閾值。圖2直觀地表示出這個判定機制。

圖2 SIFT特征點匹配的不同情況

經過上述操作，盡管基本上移除了錯誤的特征點對，但匹配點對的數量仍然很大。為了提高圖像變形的效率，需要進一步采樣特征點對。這一步采樣要求盡可能地均勻，使得用于變形的特征點對不要過分集中，為此我們引入一個距離閾值λ。先按匹配度大小排序，用貪婪法從大到小選擇特征點，同時滿足下面的均勻性條件：計算當前處理的特征點與已經入選的SIFT特征點集的距離，如果距離小于λ，則舍棄這個特征點，否則加入特征點集。圖3給出了一個經過上述三步篩選的SIFT特征點匹配的結果。

圖3 篩選出的SIFT特征點對集合

2.2 圖像變形

Schaefer等人提出的基于移動最小二乘法的圖像變形方法[17]以圖像中點的集合或者線條集合作為控制集對圖像實施變換，能夠把特征點精確地變到對應的位置。因此我們把圖像中的SIFT特征點對分別看作控制點和變形后的位置點，運用上述變形方法來對準圖像。為了便于理解，下面簡要地回顧該變形方法。

設pi和qi是對應的SIFT特征點，wi是一個權重表示特征點對當前處理的像素點的影響，lv是關于像素點v的一個仿射變換，可以分解成一個線性變換M和一個平移變換T，即：

lv(x)=xM+T

(3)

我們尋找最優的M和T，使得下述函數值最小：

(4)

其中wi如式(5)所示：

(5)

式(4)的優化求解可以轉化成一個最小二乘法問題，能夠精確求得顯式解如下：

(6)

(7)

(8)

對圖像中的每個像素點應用仿射變換，再結合一種雙線性插值技術就可以得到最終的圖像變形結果。圖4給出了一張圖像的變形結果。

圖4 原始圖像和圖像最終變形結果

2.3 拼接曲線

圖割技術被廣泛應用在計算機視覺的多個領域，包括圖像拼接，視頻合成[7]和數字蒙太奇圖片的制作[8]等。在圖像對準后，基于縫隙的拼接方法大多采用圖割技術尋找變形圖片和參考圖片的最優拼接縫。我們參考Boykov等[18]提出的圖割技術，以兩幅圖像的重疊區域上的像素為頂點，四鄰域為連接關系，各邊的容量由像素的對應關系確定，構建一個網絡流D(V,E,C)。尋?e={p,q}∈E，e的容量c(e)具體定義如下：

c(p,q)=D(p)+D(q)

(9)

D(v)=|I1(v)-I2(v)|

(10)

其中p和q是兩個相鄰的像素，I(v)是v點的顏色強度，c(p,q)表示定義在p和q像素點上的平滑懲罰值。對于D(V,E,C)，應用最大流/最小割算法，我們得到網絡流的一個最小割，與此對應的圖像上的分割線就是圖像重疊區域的拼接縫。圖5顯示了一個具體的拼接縫結果。在最終的拼接圖像中，在拼接縫左邊的像素點將會采用變形圖片；落在右邊的像素點則采用參考圖片。同樣圖像融合技術被用來消除微小的對準誤差和圖像間的曝光差異，在實驗中，僅分別對圖像的拼接縫隙周圍像素的三個通道采取加權平均的方法來實現融合。

圖5 對重疊區域運用圖割之后的拼接結果

3 實驗結果和討論

利用Visual Studio和OpenCV，我們在Windows平臺實現了上述方法。通過測試，算法中用到的各個參數的合理取值如下：d=10，s=12，λ=圖像的寬高之積的平方根與20的比值。為了評估本文的方法，我們拍攝了一組內容多樣的有視差的照片，涵蓋人物、建筑、樹、河流等自然景象，我們的方法能夠理想地拼接大部分的照片，圖6給出了這組照片的一個測試結果。

圖6 強結構性圖像的拼接

下面是我們的方法與兩個當下流行的圖像拼接軟件Auto-Stitch和Microsoft ICE以及近期的拼接算法[14]的比較。實驗采用Zhang等[14]所建立的一個圖片庫(http://graphics.cs.pdx.edu/project/stitch)，這個圖片庫有35組場景圖片，我們測試了所有的圖片，總體性能與文獻[14]的算法相當。這里給出了在結構性占優的圖片和自然景物圖片上的四種方法的拼接結果。圖7是含有橋梁、腳手架等結構性強的圖片的拼接。Auto-Stitch是基于文獻[1]中的圖像拼接思想進行開發的軟件，這種方法采用一個簡單的二維變換來對準圖片，當圖像間視差較大時，將會帶來嚴重的對準誤差如圖7(b)所示，Auto-Stitch的結果出現重影。ICE在Auto-Stitch的基礎上應用了拼接縫技術[8]。這種圖像后處理技術可以幫助掩蓋圖像的對準偏差以及拼接縫隙。但是和Auto-Stitch一樣由于對準模型的局限性，ICE拼接的效果同樣不理想，如圖7(c)所示出現較大對準偏差。視差容忍的拼接方法混合了全局單應性變換及局部內容保持變換，可以很好地應對圖像間的視差，因此可以得到看起來真實無縫隙的拼接結果如圖7(d)。但在圖像的非重疊區域，該方法的外插結果有時會導致圖像內的顯著物體形狀變形從而帶來失真。我們的實驗結果如圖7(e)。

(a) 輸入圖像

(b) Auto-Stitch

(c) ICE

(d) 視差容忍圖像拼接

(e) 我們的拼接結果圖7 強結構性圖像的拼接比較

4 結 語

本文提出了一種新的視差圖像拼接方法,結合RANSAC及距離相似性對SIFT特征點進行篩選，并利用移動最小二乘思想和仿射變換構成圖像對準模型。它能精確對準篩選出的SIFT特征點對以此來平衡圖像間的視差及圖像的對準偏差。在圖像對準完成后，使用圖割和圖像融合技術進一步平滑拼接結果。實驗結果表明，此方法能夠可靠地完成視差圖像的拼接，利用圖像融合技術，可以基本消除由對準偏差、曝光差異等因素帶來的人工痕跡，從而得到無縫且感官上真實的拼接結果。

[1] Brown M, Lowe D G. Automatic panoramic image stitching using invariant features[J].International Journal of Computer Vision, 2007, 74(1):59-73.

[2] Zaragoza J, Chin T J, Brown M S, et al. As projective-as-possible image stitching with moving DLT [C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. California, USA, 2013:2339-2346.

[3] Shum H Y, Szeliski R. Construction of panoramic mosaics with global & local alignment[J].International Journal of Computer Vision, 2000, 36(2):101-130.

[4] Lin W Y, Liu S, Matsushita Y, et al. Smoothly varying affine stitching[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. New Jersey, USA, 2011:345-352.

[5] Eden A, Uyttendaele M, Szeliski R. Seamless image stitching of scenes with large motions and exposure differences[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. U.C. Berkeley, USA, 2006:2498-2505.

[6] Szeliski R, Shum H Y. Creating full view panoramic image mosaics and environment maps[C]//Computer Graphics Proceedings. New York, USA, 1997:251-258.

[7] Kwatra V, Schodl A, Essa I, et al. Graphcut textures: image and video synthesis using graph cuts[J].ACM Transactions on Graphics, 2003, 22(3):277-286.

[8] Agarwala A, Dontcheva M, Agarwala M, et al. 2004. Interactive digital photomontage[J].ACM Transactions on Graphic, 2004, 23(3):294-302.

[9] Burt P J, Adelson E H. A multiresolution spline with application to image mosaics[J].ACM Transactions on Graphics, 1983, 2(4):217-236.

[10] Perez P, Gangnet M, Blake A. Poisson image editing [J]. ACM Transactions on Graphics, 2003, 22(3):313-318.

[11] 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.

[12] Szeliski R. Image alignment and stitching: a tutorial[J].Foundations and Trends in Computer Graphics and Vision, 2006, 2(1):1-104.

[13] Gao J, Kim S J, Brown M S. Constructing image panoramas using dual-homography warping[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. New Jersey, USA, 2011:49-56.

[14] Zhang F, Liu F. Parallax-tolerant image stitching[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Ohio, USA, 2014:3262-3269.

[15] Lowe D G. Distinctive image features from scale-invariant key points[J].International Journal of Computer Vision, 2004, 60(2):91-110.

[16] Igarashi T, Moscovich T, Hughes J F. As-rigid-as-possible shape manipulation[J].ACM Transactions on Graphics, 2005, 24(3):1134-1141.

[17] Schaefer S, McPhail T, Warren J. Image deformation using moving least squares[J].ACM Transactions on Graphics, 2006, 25(3):533-540.

[18] Boykov Y, Veksler O, Zabih R. Fast approximate energy minimization via graph cuts[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001,23(11):1222-1239.

PARALLAXIMAGESTITCHINGBASEDONMOVINGLEASTSQUAREMETHOD

Chu Dongdong Li Haisheng
(SchoolofComputerScienceandSoftwareEngineering,EastChinaNormalUniversity,Shanghai200062,China)

Parallax image stitching usually utilizes the feature-based transformation. Existing works focused on the image transformation model, especially a homography, but this is inadequate to obtain better alignment. This paper presents a new stitching method. Firstly, detect and match features in images, then RANSAC and distance similarity are used to investigate the accuracy of matching features. Then, based on these matching point pairs, moving least squares is used to construct a global affine transformation to align two images and get the overlapped region of them. Finally, constructing a network flow whose vertices are the pixels on the overlapped region, and max-flow/min-cut algorithm is adopted to search for a best seam, then stitch and blend images according to this seam. As our method effectively strengthens the matching reliability between SIFT points, the alignment accuracy of two images is better than previous method. Image stitching result is smooth and authentic, no distortion, ghosting or other artifact.

Image stitching Feature matching Moving least square method Stitching curve

2016-08-22。楚東東，碩士生，主研領域：計算機視覺和圖像處理。李海晟，副教授。

TP751.1

A

10.3969/j.issn.1000-386x.2017.08.041