一種改進的圖像無縫拼接算法

陳淑清

（1.莆田學院信息工程學院，福建莆田351100；2.福建省大數(shù)據(jù)管理新技術與知識工程重點實驗室&智能計算與信息處理福建省高等學校重點實驗室，福建泉州362000）

一種改進的圖像無縫拼接算法

陳淑清1，2

（1.莆田學院信息工程學院，福建莆田351100；2.福建省大數(shù)據(jù)管理新技術與知識工程重點實驗室&智能計算與信息處理福建省高等學校重點實驗室，福建泉州362000）

針對圖像拼接過程產(chǎn)生的接縫問題，采用最佳接縫選擇算法縫合圖像接縫。然而合適的能量函數(shù)是最佳接縫選擇算法的關鍵。提出一種基于Canny邊緣檢測算子改進的能量函數(shù)，其目的是最小化圖像重疊區(qū)域的梯度差異。通過實驗將提出的能量函數(shù)與亮度誤差、梯度差、梯度和、梯度差和梯度和的加權和以及Canny邊緣檢測算子等五種常用能量函數(shù)的最佳接縫選擇結果進行對比。結果表明，提出的能量函數(shù)可以減少拼接圖像的結構接縫，而且對于光照變化具有更好的分割穩(wěn)定性，使得拼接之后的圖像看起來更加自然美觀。

無縫拼接；Canny邊緣檢測算子；多分辨率融合

圖像拼接是圖像處理領域的主要研究課題之一，近年來國內(nèi)外專家學者在這個領域做了大量的研究工作。圖像拼接的兩個關鍵步驟是圖像配準和接縫消除［1］。拼接圖像的接縫包括紋理結構不一致引起的結構接縫和亮度不一致引起的光學接縫。針對這兩種接縫，最常用的接縫消除算法分別是最佳接縫選擇算法和接縫平滑算法。目前一些主流的最佳接縫選擇算法在不同程度上都會割裂紋理結構，造成比較明顯的結構接縫。本文著重討論最佳接縫選擇算法，本著使待拼接圖像重疊區(qū)域內(nèi)、接縫周圍圖像紋理差異最小的指導思想，提出了基于Canny邊緣算子改進的最佳接縫選擇算法。對于存在亮度差異的圖像，在選擇了最佳接縫的基礎上應用多分辨率融合算法，使圖像之間平滑過渡，同時又能使得圖像依然保持清晰的紋理。實驗表明，文章提出的方法與其它五種的接縫優(yōu)化算法相比，能夠更好地保持拼接圖像紋理結構的一致性。

1　主要最佳接縫選擇算法

圖1　部分重疊圖像示意圖

如圖1所示。在已經(jīng)配準的兩幅部分重疊的圖像和的重疊區(qū)域Ω內(nèi)，求解一條符合某種約束條件的縫合接縫。最佳接縫選擇算法涉及兩個關鍵步驟，一是約束條件，二是求解滿足約束條件的分割算法。常見求解最佳接縫的算法有動態(tài)規(guī)劃算法和圖割算法。接下來以垂直接縫為例來敘述。

約束條件往往是沿著接縫線上的所有像素點的能量之和達極小值。不同的能量函數(shù)構成了不同的約束條件。能量函數(shù)有直接基于圖像像素灰度值的，也有基于圖像梯度域的。令和分別為沿著垂直接縫線上的兩個重疊塊，如圖2所示。常見的能量函數(shù)主要有以下幾種。

圖2　接縫約束條件

（1）最小化接縫上重疊像素的亮度誤差，對于RGB圖像，可以分別計算每個通道的亮度差，再取三通道誤差的和。能量函數(shù)如下：

公式（1）中E1表示單組重疊塊的亮度誤差，I1和I2分別表示重疊塊B1和B2的上各點的像素值，B表示重疊塊區(qū)域；

（2）最小化重疊區(qū)域梯度和。能量函數(shù)如下：

（3）最小化重疊區(qū)域梯度差。能量函數(shù)如下：

其中表示梯度運算。

（4）最小化E2和E3的加權和［2］。能量函數(shù)如下：

其中β=0.7。

對于以上四種主要的能量函數(shù)，設Γ為最佳接縫線，求解最佳接縫的約束條件是沿著接縫所有重疊塊能量之和達最小值。即，

2　提出的方法

兩幅經(jīng)過配準、存在重疊區(qū)域的待拼接圖像之間可能存在亮差、色差，也可能存在一些幾何結構上的錯位。直接加權融合這樣的圖像往往會引起圖像在亮度或色彩上的過渡不自然而留下的光學接縫以及由于幾何結構錯位引起的重影、鬼影或者圖像模糊等現(xiàn)象。在實驗分析的過程中發(fā)現(xiàn)，常見的最佳接縫的算法常常會切斷一些幾何結構的邊緣，結構錯位容易呈現(xiàn)出來。想要合成一幅在幾何結構上無明顯錯位的圖像，接縫應該使周圍圖像重疊區(qū)域的邊緣或紋理盡量一致。文章提出采用基于Canny邊緣檢測算子改進的最佳接縫選擇算法。對于存在明顯亮度差異的圖像，可以在選擇好最佳接縫之后，對圖像的重疊區(qū)域應用基于最佳接縫掩膜的多分辨率融合，平滑接縫周圍的亮度差異。

2.1Canny邊緣檢測算子

Canny邊緣檢算子［3］是Canny于1986年提出來的一種雙閾值邊緣檢測算子。邊緣體現(xiàn)在二維圖像信號上即為亮度的階躍變化，常常用圖像的梯度來度量邊緣的強度。邊緣檢測的過程本質(zhì)上就是對圖像梯度進行檢測、度量和定位的過程。Canny檢測算子的步驟：（1）平滑圖像，抑制噪聲；（2）檢測圖像梯度的幅值和方向；（3）對梯度的幅值應用非極大值抑制；（4）用雙閾值算法檢測和連接邊緣。

2.2基于Canny改進的能量函數(shù)

基于Canny的能量函數(shù)，最小化Canny邊緣差異：

其中C1和C2分別是重疊塊內(nèi)兩幅圖像的Canny二值邊緣響應。

在Canny邊緣算子的基礎上，提出新的能量函數(shù)，它是基于圖像的梯度幅值的。該能量圖像E（x，y）的計算方法如公式（7）和（8）所示。

其中NC為論文提出的基于Canny邊緣算子的一種新的邊緣度量方法，M（x，y）是Canny算子中梯度幅值，其計算方法和Canny算子［3］一樣，th1和th2分別為Canny邊緣算子中的高、低兩個閾值，e（x，y）=1表示當前像素屬于Canny邊緣點，e（x，y）=0表示當前像素不屬于Canny邊緣點。對于彩色圖像，文章采用的方法是計算R、G、B三通道的能量圖像之和，見公式（9）；也可以先將彩色圖轉(zhuǎn)換成灰度圖像再計算能量圖像。

結合Canny的雙閾值邊緣檢測算子，使算法具有更好的魯棒性。這里的邊緣度量方式是基于圖像的梯度幅值，對于圖像亮度的加性變化具有不變性，但圖像的乘性變化會使圖像梯度幅值發(fā)生相應的改變。為了讓梯度幅值對圖像的亮度具有仿射不變性，在計算過程中對圖像的梯度幅值進行了規(guī)范化處理。

2.3最佳接縫選擇算法

最佳接縫選擇算法的目標是在圖像的重疊區(qū)域內(nèi)找到一條縫合線，使得沿著縫合線的所有像素的能量之和最小。本文采用動態(tài)規(guī)劃算法來求解最佳縫合線［4］。以垂直方向的縫合線為例，如圖3所示。對于縫合線上的每個點，它的鄰接點只能為左上方、正上方和右上方三個點。垂直方向的縫合線，不考慮其水平鄰接點。則動態(tài)規(guī)劃算法的遞歸式如公式（10）所示。

圖3　動態(tài)規(guī)劃

Eij表示累計誤差，（i，j）為縫合線Γ上的一點，min為取最小值操作。選擇當（i，j）落在圖像的底部時，累計誤差最小的軌跡即為最佳接縫。對于大小為m×n的圖像重疊區(qū)域，自上而下計算接縫線上的能量之和S（i，j），其中第一行等于E（i，j），之后的每一行的計算方法見公式（10）。最后一行S（m，j）的值即為n個當前最小能量之和。取S（i，j）最后一行S（m，j）中的最小值即為最佳縫合線上的能量之和。沿著這個最小值往前回溯，找出最佳縫合線。

2.4基于最佳接縫掩膜的多分辨率融合

文章提出的方法重點在于處理結構上的差異，但是沒有考慮兩幅圖像的亮度差異，需要應用接縫平滑算法來使重疊區(qū)域在亮度上能夠平滑過渡。對于存在明顯亮度差異的兩幅圖像，可以先應用文章提出的最佳接縫算法分割重疊區(qū)域，再應用多分辨率融合算法以平滑重疊區(qū)域亮度的差異。即，將最佳分割應用于融合掩模R，置分割左邊的R值為1，分割線右邊的R值為0。

多分辨融合的思想是Burt和Adelson［5］提出來的。它首先將待融合的圖像分解成不同頻帶的子圖，然后對不同的頻帶沿著分割邊界應用不同的融合半徑，對于像圖像亮度等大尺度特征，分布在低頻帶，采用大的融合半徑，使圖像在重疊區(qū)域過度自然，對于紋理等細節(jié)特征，分布在高頻帶，采用小的融合半徑，以免圖像模糊或重影。通過這種多分辨率融合算法巧妙地把分割算法和融合算法整合在一起。

多分辨率融合算法首先需要對原圖像進行多分辨率分解，構建多分辨率金字塔，這一步有不同的算法可以應用，如拉普拉斯、小波分解、離散傅里葉變換等。這里以構建拉普拉斯金字塔為例闡述多分辨融合的一般步驟如下：

（1）分別構建圖像A和B的拉普拉期金字塔LA和LB；

（2）構建融合掩模R的高斯金字塔GR；

（3）以高斯金字塔GR上對應結點為融合權值構建拉普拉斯金字塔LA和LB的融合金字塔LC：

（4）由拉普拉斯金字塔LC重構最終的融合圖像C。

3　實驗及結果分析

3.1算法相關參數(shù)設置

最佳接縫選擇過程中，計算能量圖像的時候，首先需要考慮的是計算接縫線上每個像素的能量所采用的重疊塊B的大小。如圖4所示，通過實驗比較了6－領域塊和2－鄰域塊這兩種不同重疊塊大小對分割結果的影響。圖中的黑點表示像素點，用紅色的圓圈出來的點表示當前需要計算能量的像素。通過仿真實驗分別比較了這兩種塊大小在不同能量函數(shù)情況下的分割效果。實驗結果表明，總體上2-領域塊優(yōu)于6-領域塊，且能量函數(shù)的1范數(shù)和2范數(shù)的表現(xiàn)差別不大。因此在后續(xù)的實驗中，所有的能量函數(shù)圖像均采用2-領域塊和1范數(shù)，即絕對值來計算。

圖4　能量圖像中重疊塊B的選擇

最后，探討Canny邊緣算子閾值的選擇。這個閾值是基于梯度幅值的，由于圖像的對比度各不相同，選擇的一個確定的閾值是很困難的。這里采用相對閾值的方法，假設一幅圖像中有一定百分比的像素點為非邊緣點。這里取70%，把比70%的像素點的梯度幅值高的幅值確定為高閾值th1，并令th2=0.4th1。

3.2仿真實驗

本實驗采用的一組仿真圖像均截取自同一張圖像，大小為512×512，左圖和右圖在垂直方向存在8個像素的錯位，并對右圖加上1.1的乘性亮度變化和20的加性亮度變化，生成新的右圖。這組圖像存在圓弧形邊緣，比較全面的包含了各種不同的邊緣方向，圖像中不均勻的亮度包括了各種不同的邊緣強度，是一組比較有代表性的仿真圖像。采用直接取中線作為垂直接縫的拼接結果如圖5所示。兩幅圖像均存在明顯的結構接縫，圖5（b）還存在亮度差異。兩幅圖像在視覺上明顯失真，看起來不自然。

圖5　取中線作為垂直接縫直接拼接的圖像

3.2.1最佳接縫選擇

圖6　對無亮差圖像應用最佳接縫選擇

圖7　對存在亮度差異圖像應用最佳接縫選擇

先后比較了本文提出的能量函數(shù)、四種常用能量函數(shù)及基于Canny邊緣算子差的能量函數(shù)在圖像沒有亮度差異和有亮度差異兩種情況下的接縫選擇的結果。對于梯度域的能量函數(shù)，在計算能量函數(shù)之前都對圖像的梯度做了規(guī)范化。實驗結果如圖6和圖7所示。本實驗使用離中線左右各60像素的區(qū)域作為接縫的候選區(qū)域。

分析圖6可以看出，圖（b）、（c）和（d）在中間自上而上第一朵小白花或第二朵小白花左邊的弧形輪廓上存在多處比較明顯的裂痕；圖（e）在第一朵小花左上方輪廓線上存在一處比較明顯的毛邊；圖（a）與論文提出的方法最接近，在第一朵小花的左上方存在一處與圖（f）相似的細微接縫，但是它在第二朵小花左上方輪廓線上存在一處比較明顯的結構接縫。圖（f）只是在第一朵小白花左上方的輪廓上存在一點點細微的結構接縫，肉眼看起來并不明顯，整體效果比其它五種能量函數(shù)的拼接結果都要好一些。

分析圖7可以看出，同樣是論文提出的算法獲得了比較好的拼接結果。圖（f）除了在亮度上存在差異之外，在結構縫合上接近完美，肉眼上看不出結構接縫。此外，基于梯度域的E2、E3和E4整體表現(xiàn)與圖6并無明顯上的差異，符合預期。E1能量函數(shù)應用在存在亮度差異圖像上分割結果有了比較明顯的變化，簡單的亮度差異最小化不適合用于存在亮度差異圖像的拼接。Canny邊緣算子差的能量函數(shù)E5也因圖像亮度的變化導致求解的分割線產(chǎn)生了不小的波動。相比之下，文章提出的能量函數(shù)E產(chǎn)生的分割比較穩(wěn)定，沒有因為亮度差異而產(chǎn)生明顯的變化。

3.2.2接縫平滑

圖8　對圖7（f）應用多分辨率融合

如圖7（f）所示，正如預期，拼接圖像中間存在比較明顯的亮度差異。對拼接圖像中間120像素寬的重疊區(qū)域應用多分辨率融合算法，其結果如圖8所示。經(jīng)過基于最佳接縫掩膜的多分辨率融合之后的拼接圖像處理的結果圖像沒有明顯的結構接縫，也在一定程序上抑制了光學接縫，整幅圖像亮度過度自然。

4　小結

本文著重探討結構接縫的消除或最小化，提出了一種用于最佳接縫選擇的能量函數(shù)。這種能量函數(shù)是基于Canny邊緣算子改進而來的，它是基于圖像的梯度幅值的。對于存在亮度差異的圖像，可以在最佳分割的基礎上應用基于最佳接縫掩膜的多分辨率融合算法，平滑接縫。實驗表明，與原來的直接基于Canny邊緣響應差的能量函數(shù)或其它四種常用的能量函數(shù)相比，本文提出的能量函數(shù)具有較好的分割效果，且能適應圖像亮度變化，具有更好的分割穩(wěn)定性。在最佳分割的基礎上再應用多分辨率融合，能夠兼顧紋理結構一致和亮度的平滑，取得較好的效果。

［1］李海超，郝勝勇，朱琦.多片遙感圖像的快速無縫拼接方法［J］.經(jīng)外與激光工程，2011，40（7）：1381-1386.

［2］Jiaya J，Chi-Keung T.Image stitching using structure deformation［J］.Pattern Analysis and Machine Intelligence，IEEE Transactions on，2008，30（4）：617-631.

［3］Canny J.A computational approach to edge detection［J］.Pattern Analysis and Machine Intelligence，IEEE Transactions on，1986（6）：679-698.

［4］Avidan S，Shamir A.Seam carving for content-aware image resizing［C］.ACM Transactions on graphics（TOG）.ACM，2007，26（3）：10.

［5］Burt P J，Adelson E H.A multi-resolution spline with application to image mosaics［J］.ACM Transactions on Graphics（TOG），1983，2（4）：217-236.

（責任編輯：華偉平）

An Improved Algorithm for Seamless Image Stitching

CHEN Shuqing1，2
（1.College of Information Engineering，Putian University，Putian，F(xiàn)ujian 351100；2.Fujian Provincial Key Laboratory of Data Intensive Computing&Key Laboratory of Intelligent Computing and Information Processing，F(xiàn)ujian Province University，Quanzhou，F(xiàn)ujian 362000）

Concerned the seams problem arising from image stitching，an optimal seam selection algorithm is used.And an appropriate energy function is the key to the algorithm.An improved energy function based on Canny detector is proposed in this paper.Its goal is to minimize the differences of the gradients between overlapped areas of the images.Moreover，the proposed energy function is compared with the other five common ones by experiments，which include the brightness errors，the gradient errors，the gradient sums，the weighted sum of the gradient errors and sums，and Canny edge detector.The results show that the proposed algorithm can effectively reduce the structure seams，and has robust segmentation against changing illumination and itmakes themosaic imagesmore natural.

seamless stitching；Canny edge detector；multi-resolution fusion

TN911.73

A

1674-2109（2016）06-0065-05

2016-04-11

莆田學院育苗基金資助項目（2014057）。

陳淑清（1977-），女，漢族，講師，主要從事視頻運動目標檢測、圖像拼接的研究。