楚東東 李海晟

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

?

基于移動(dòng)最小二乘法的視差圖像拼接

楚東東 李海晟

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

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

圖像拼接 特征點(diǎn)匹配 移動(dòng)最小二乘法 拼接曲線(xiàn)

0 引 言

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

提高特征點(diǎn)匹配的正確性是本文的主要工作，我們提出了距離相似性衡量方法，結(jié)合隨機(jī)采樣一致算法(RANSAC)[11]，有效地去除特征點(diǎn)之間的錯(cuò)誤匹配。為了能使一幅圖像的特征點(diǎn)準(zhǔn)確地變換到另一幅圖像對(duì)應(yīng)的特征點(diǎn)，我們選用基于移動(dòng)最小二乘法的變形方法。由此，本文提出了一個(gè)新的圖像對(duì)準(zhǔn)模型。對(duì)準(zhǔn)了視差圖像后，我們?cè)谧冃螆D像和參考圖像的重疊區(qū)域構(gòu)建網(wǎng)絡(luò)流模型，尋找一條合理的拼接線(xiàn)，兩幅圖像沿此曲線(xiàn)進(jìn)行拼接。

1 相關(guān)工作

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

為了得到更好的圖像對(duì)準(zhǔn)結(jié)果，近年來(lái)不少研究者提出多種方法。Gao等[13]提出雙單應(yīng)性變換的思想，他們的方法針對(duì)于一種特別的場(chǎng)景，這種場(chǎng)景可以主要分為兩個(gè)平面：地平面和遠(yuǎn)地面。很顯然這種雙單應(yīng)性變換很難擴(kuò)展到任意場(chǎng)景，因?yàn)椴皇撬械膱?chǎng)景都可以分成兩個(gè)平面，可能場(chǎng)景中只有一個(gè)主要的結(jié)構(gòu)或者超過(guò)兩個(gè)主要的平面。Zaragoza等[2]提出一種投影變換拼接技術(shù)，他們把移動(dòng)直接線(xiàn)性變換和投影變換結(jié)合起來(lái)形成圖像對(duì)準(zhǔn)模型，這種方法在圖像視差較小時(shí)可以得到很完美的拼接結(jié)果，但當(dāng)圖像視差較大時(shí)會(huì)出現(xiàn)鬼影等人工痕跡。最近，Zhang等[14]提出一種混合的圖像對(duì)準(zhǔn)模型，其中包括單應(yīng)性變換和內(nèi)容保持變換，此方法只要求圖像存在一個(gè)局部區(qū)域可以完美的對(duì)準(zhǔn)。這種方法在圖像視差較大時(shí)也可以得到較好的拼接結(jié)果，標(biāo)準(zhǔn)的圖割和多帶融合技術(shù)同樣應(yīng)用于此方法。但在非重疊區(qū)域，圖像的變形結(jié)果有時(shí)會(huì)出現(xiàn)失真的現(xiàn)象，因?yàn)樽髡邚?qiáng)調(diào)局部的對(duì)準(zhǔn)而非全局的圖像對(duì)準(zhǔn)。

2 視差圖像拼接

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

2.1 特征點(diǎn)選擇

SIFT是一種基于梯度的特征點(diǎn)，具有尺度、光照和旋轉(zhuǎn)不變性。基于特征的圖像對(duì)準(zhǔn)模型大都使用SIFT特征點(diǎn)[1-2,13-14]。然而由于它是一種局部的特征點(diǎn)，不含圖像的全局結(jié)構(gòu)信息，所以匹配結(jié)果經(jīng)常包含一些錯(cuò)誤，尤其當(dāng)圖像中含有多個(gè)類(lèi)似結(jié)構(gòu)性強(qiáng)的物體，容易把一個(gè)物體上的SIFT點(diǎn)匹配到另一個(gè)相似的物體上，如圖1所示。圖中圓圈表示SIFT特征點(diǎn)，直線(xiàn)表示匹配結(jié)果，很明顯這個(gè)結(jié)果包含了一些錯(cuò)誤的特征點(diǎn)匹配。

圖1 出現(xiàn)錯(cuò)誤對(duì)應(yīng)的SIFT匹配結(jié)果

在提取和初步匹配SIFT特征點(diǎn)后，我們用RANSAC算法來(lái)對(duì)SIFT的匹配結(jié)果進(jìn)行第一步篩選，以去除一些錯(cuò)誤的匹配。隨機(jī)選取四組特征點(diǎn)對(duì)，由此構(gòu)造一個(gè)單應(yīng)性矩陣H，用H去檢測(cè)圖像中所有的對(duì)應(yīng)特征點(diǎn)對(duì)(p,q)，如果‖Hp-q‖

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

我們可用向量p2-p1和它繞點(diǎn)p1逆時(shí)針旋轉(zhuǎn)90度的向量(p2-p1)⊥構(gòu)建的局部坐標(biāo)系表示點(diǎn)p：

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

(1)

(p,q)被認(rèn)為是一個(gè)正確的匹配，如果這三個(gè)特征點(diǎn)對(duì)間滿(mǎn)足下面的公式：

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

(2)

其中s是一個(gè)閾值。圖2直觀地表示出這個(gè)判定機(jī)制。

圖2 SIFT特征點(diǎn)匹配的不同情況

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

圖3 篩選出的SIFT特征點(diǎn)對(duì)集合

2.2 圖像變形

Schaefer等人提出的基于移動(dòng)最小二乘法的圖像變形方法[17]以圖像中點(diǎn)的集合或者線(xiàn)條集合作為控制集對(duì)圖像實(shí)施變換，能夠把特征點(diǎn)精確地變到對(duì)應(yīng)的位置。因此我們把圖像中的SIFT特征點(diǎn)對(duì)分別看作控制點(diǎn)和變形后的位置點(diǎn)，運(yùn)用上述變形方法來(lái)對(duì)準(zhǔn)圖像。為了便于理解，下面簡(jiǎn)要地回顧該變形方法。

設(shè)pi和qi是對(duì)應(yīng)的SIFT特征點(diǎn)，wi是一個(gè)權(quán)重表示特征點(diǎn)對(duì)當(dāng)前處理的像素點(diǎn)的影響，lv是關(guān)于像素點(diǎn)v的一個(gè)仿射變換，可以分解成一個(gè)線(xiàn)性變換M和一個(gè)平移變換T，即：

lv(x)=xM+T

(3)

我們尋找最優(yōu)的M和T，使得下述函數(shù)值最小：

(4)

其中wi如式(5)所示：

(5)

式(4)的優(yōu)化求解可以轉(zhuǎn)化成一個(gè)最小二乘法問(wèn)題，能夠精確求得顯式解如下：

(6)

(7)

(8)

對(duì)圖像中的每個(gè)像素點(diǎn)應(yīng)用仿射變換，再結(jié)合一種雙線(xiàn)性插值技術(shù)就可以得到最終的圖像變形結(jié)果。圖4給出了一張圖像的變形結(jié)果。

圖4 原始圖像和圖像最終變形結(jié)果

2.3 拼接曲線(xiàn)

圖割技術(shù)被廣泛應(yīng)用在計(jì)算機(jī)視覺(jué)的多個(gè)領(lǐng)域，包括圖像拼接，視頻合成[7]和數(shù)字蒙太奇圖片的制作[8]等。在圖像對(duì)準(zhǔn)后，基于縫隙的拼接方法大多采用圖割技術(shù)尋找變形圖片和參考圖片的最優(yōu)拼接縫。我們參考Boykov等[18]提出的圖割技術(shù)，以?xún)煞鶊D像的重疊區(qū)域上的像素為頂點(diǎn)，四鄰域?yàn)檫B接關(guān)系，各邊的容量由像素的對(duì)應(yīng)關(guān)系確定，構(gòu)建一個(gè)網(wǎng)絡(luò)流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是兩個(gè)相鄰的像素，I(v)是v點(diǎn)的顏色強(qiáng)度，c(p,q)表示定義在p和q像素點(diǎn)上的平滑懲罰值。對(duì)于D(V,E,C)，應(yīng)用最大流/最小割算法，我們得到網(wǎng)絡(luò)流的一個(gè)最小割，與此對(duì)應(yīng)的圖像上的分割線(xiàn)就是圖像重疊區(qū)域的拼接縫。圖5顯示了一個(gè)具體的拼接縫結(jié)果。在最終的拼接圖像中，在拼接縫左邊的像素點(diǎn)將會(huì)采用變形圖片；落在右邊的像素點(diǎn)則采用參考圖片。同樣圖像融合技術(shù)被用來(lái)消除微小的對(duì)準(zhǔn)誤差和圖像間的曝光差異，在實(shí)驗(yàn)中，僅分別對(duì)圖像的拼接縫隙周?chē)袼氐娜齻€(gè)通道采取加權(quán)平均的方法來(lái)實(shí)現(xiàn)融合。

圖5 對(duì)重疊區(qū)域運(yùn)用圖割之后的拼接結(jié)果

3 實(shí)驗(yàn)結(jié)果和討論

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

圖6 強(qiáng)結(jié)構(gòu)性圖像的拼接

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

(a) 輸入圖像

(b) Auto-Stitch

(c) ICE

(d) 視差容忍圖像拼接

(e) 我們的拼接結(jié)果圖7 強(qiáng)結(jié)構(gòu)性圖像的拼接比較

4 結(jié) 語(yǔ)

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

[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。楚東東，碩士生，主研領(lǐng)域：計(jì)算機(jī)視覺(jué)和圖像處理。李海晟，副教授。

TP751.1

A

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