基于局部區域梯度最小點的遙感圖像鑲嵌算法

程 紅，鄭 悅，孫文邦

(中國人民解放軍空軍航空大學，長春 130022)

0 引言

遙感圖像鑲嵌的目的是構造一個視覺效果好的整幅圖像，以便更好地進行處理、解譯和分析。在鑲嵌圖像中的拼接縫附近，2景圖像在色調或紋理上的差別都會產生明顯的拼接縫痕跡。由于地面環境的微小變化、成像角度、曝光強度和自然光線照射強度等的差異等都可能造成鑲嵌邊界附近色調和紋理上的差異。因此，在遙感圖像鑲嵌過程中，尋找一條最佳拼接縫并對其進行消除有著重要意義。

目前，常用的拼接縫消除方法有平分線法和灰度差值最小法。平分線法是將相鄰2景圖像重疊區域的平分線作為拼接縫進行圖像鑲嵌，操作簡單，易于實現，但其確定的拼接縫上的對應像素的灰度差異往往很大，且易穿越重要目標;因此，拼接縫消除后有可能使得重要目標產生較大變化，影響后期的圖像解譯。灰度差值最小法則是在2景圖像重疊區域內選取對應灰度差值最小的像素作為最佳拼接點，再將最佳拼接點連接起來，形成最佳拼接縫。使用該算法進行圖像鑲嵌，當最佳拼接縫上2幅圖像灰度差別很小時，鑲嵌的圖像不存在明顯的拼接縫;但當重疊區域中圖像的灰度差異較大時，該方法難以在重疊區域中找到滿意的拼接縫;對于內容復雜的圖像，當所選拼接縫與某些地物邊緣相交時，有可能在后期消除拼接縫時出現消除效果不理想、甚至產生局部突變的現象[1－2]。在目前尋找最佳拼接縫算法的研究中，自Duplaquet采用動態規劃的思想確定最佳拼接縫以來，方亞玲等[3]又在其基礎上進行了改進，但仍未解決動態規劃法容易陷入局部最優解的問題;Wen，Chon 和王軍等[4－6]分別利用灰色理論和最大相關系數尋找最佳拼接縫;方賢勇[7]通過帶權有向圖的最佳切割路徑來確定最佳拼接縫;Pan等[8]利用 Voronoi圖法(又稱泰森多邊形或Dirichlet圖，是由連接2鄰點直線的垂直平分線組成的連續多邊形)有效地解決了尋找多幅圖像最佳拼接縫的問題，但對于初始拼接縫的修改仍有待改進;范永弘等[9]采用蟻群優化算法確定數字表面模型權值，然后基于流水模型設計了拼接縫自動選擇規則，最后利用數學形態學運算對所提取的拼接縫進行膨脹處理，有效規避建筑物的投影差，避免拼接縫與建筑物邊緣重合，確保了最佳拼接縫提取的有效性。上述方法大多只考慮到對應像素灰度的差異最小，卻沒有考慮圖像中目標的完整性;因而確定的最佳拼接縫會穿越圖像中的目標，從而破壞了目標的完整性，影響到整幅鑲嵌圖像的質量。針對以上問題，本文提出一種能夠有效避免切割圖像中的目標，盡量使得找到的最佳拼接縫既能繞過目標邊緣、又保留目標完整性的最佳拼接縫尋找方法。實驗結果表明，該方法具有一定的可行性和有效性。

1 基本原理與算法流程

遙感圖像灰度的梯度可以用來表示圖像中灰度變化的快慢，梯度值愈大，說明該區域灰度變化愈劇烈(梯度值大的像素一般為圖像中的邊緣信息);梯度值愈小，則說明該區域灰度變化愈平緩，與周圍像素的灰度值愈相近。因此，本文提出的最佳拼接縫尋找算法的基本原理是:通過計算重疊區域內各個像素灰度的梯度值，選取搜索范圍內梯度值最小的像素(即灰度變化較為平緩的位置)作為最佳拼接縫，由此得到的拼接縫兩側圖像灰度差異較小，可在一定程度上滿足對應像素灰度差異盡量小的要求;并利于后期拼接縫消除處理，避免因拼接縫兩側灰度差異過大而導致的橫向帶狀效應，最終提高圖像的整體視覺效果。本文算法的技術流程如圖1所示。

圖1 本文算法的技術流程Fig.1 Technique flowchart of algorithm proposed in this paper

1)計算重疊區域內每個像素的灰度梯度值。圖像f(x，y)在位置(x，y)處的梯度定義為

式中Gx和Gy分別為像素(x，y)在x方向和y方向的梯度。梯度向量的方向為(x，y)處f(x，y)的最大變化方向，其值為

計算重疊區域內每個像素周圍鄰域(本文選取以當前像素為中心的3像素×3像素的鄰域)內的“梯度和”;在起始行選擇梯度和最小的點作為拼接縫的起始位置，為了使得最佳拼接縫處于圖像重疊區域的中間區域(而不明顯偏向于重疊區域的某一邊界)，當出現梯度和相等的點時，選擇距離重疊區域中垂線較近的點作為初始拼接點。

2)以確定的拼接縫初始位置為起點，以后每一行都在上一行已經確定的拼接縫位置所在列H(i－1)兩側各q個像素內(根據需要確定q，本文取q=5)尋找梯度和最小的點，作為該行的拼接縫位置;若出現2個點的梯度和相等的情況，由于每一行都是在以上一行拼接點為中心的兩側固定范圍內尋找該行的最佳拼接點，所以拼接點的位置不會過多地偏離重疊區域的中間區域。因此，為了滿足最佳拼接縫上對應像素差異最小的要求，盡量選擇對應像素灰度差值較小的點作為該行的最佳拼接縫位置，該位置所對應的列值為H(i)。

3)連接各行確定的拼接點，即可在圖像上得到最佳拼接縫的位置;再根據得到的位置對拼接縫進行消除。目前普遍采用的拼接縫消除方法是“漸入漸出法”和“強制改正法”。前者必須同時擁有2景具有重疊區域的待鑲嵌圖像，且在灰度差較大情況下易出現“鬼影”現象;后者只需要1景已經完成幾何鑲嵌的遙感圖像即可，但其在消除原拼接縫的同時又易出現列方向上的橫向帶狀效應，會影響鑲嵌圖像的整體視覺效果。針對以上問題，本文對強制改正法進行改進，提出一種“差值拼接縫消除算法”。其基本思想是:分別統計各行拼接縫兩側相鄰像素的灰度差值，并使灰度差值在改正范圍內逐漸過渡，越靠近拼接縫位置改正值越大，改正范圍邊界處的改正值為0;為了消除上述帶狀效應，對各改正值進行卷積平滑處理，得到每個像素對應的新的改正值;再根據新得到的改正值對各像素進行改正，最終得到無拼接縫、視覺效果較好的鑲嵌圖像。

2 仿真實驗與對比分析

為說明本文算法的可行性和有效性，筆者在Intel(R)Core(TM)2 Quad CPU Q9400 2.66 GHz、內存4 GB的計算機上，Matlab7.1的編程條件下進行實驗。選取的2景待鑲嵌實驗圖像為某機場的航空遙感圖像(圖2)。

圖2 實驗用航空遙感圖像Fig.2 Airborne remote sensing images for experiment

鑒于目前普遍采用的確定拼接縫算法為平分線法和灰度差值最小法，本文重點與上述2種算法進行對比實驗，以驗證本文算法的可行性和有效性。

2.1 與平分線法比較

圖3分別為根據平分線法和本文算法確定的最佳拼接縫位置。

圖3 本文算法與平分線法確定的拼接縫對比Fig.3 Comparison between seam－lines determined with proposed algorithm and bisection algorithm

很明顯，用平分線法確定的最佳拼接縫固定在圖像的中間位置，未能有效地避開圖像中的建筑物或其他重要目標，并切割了機場跑道的影像(圖3(a));而用本文算法確定的最佳拼接縫則在一定程度上繞開了圖像中的目標(圖3(b))。以紅色圓圈所示區域中的機場跑道為例，本文算法確定的最佳拼接縫與機場跑道平行，繞開了跑道的邊緣。由于本實驗圖像中機場跑道橫穿整個重疊區域，因此確定的拼接縫不可避免地要與跑道相交;但若目標較小，本文算法確定的最佳拼接縫則可很好地繞開目標，達到較好的效果。如在圖3(b)黃色圓圈所示區域中，本文算法確定的拼接縫有效地沿著2種不同地物的分界線將2種地物分別劃分在不同的圖像上，避免了機械地切割某一地物目標，從而保證了地物目標的完整性。這在一定程度上也解決了圖像中的微小錯位問題，即消除了結構性拼接縫。

使用本文提出的差值拼接縫消除方法對圖3中的2幅圖像進行拼接縫消除處理，結果如圖4所示。

圖4 本文算法與平分線法的拼接縫消除結果對比Fig.4 Comparison between seam－line removal results of proposed algorithm and bisection algorithm

由圖4可以看出，2種方法的結果圖像均實現了拼接縫的平滑過渡。但由于用平分線法確定的拼接縫位于圖像中部(如紅色框所示)，而圖像中部的機場跑道是圖像解譯的主要目標，所以用平分線法確定的拼接縫直接切割了圖像的主體，經消除灰度差異后整體影像色調偏暗，對比度不強，不利于圖像分析(圖4(a));而用本文算法確定的拼接縫由于繞開了機場跑道的中間區域，保證了機場跑道的完整性，拼接縫消除后跑道的主體色調正常，對比度也優于平分線法，從而更有利于圖像的分析和解譯(圖4(b))。同樣，在與上述分析對應的黃色框中，本文算法的對比度也優于平分線法，視覺效果較好。

為定量地說明本文算法的有效性，采用空間頻率活動性(spatial frequency activity，SFA)和結構對比度(structural contrast degree，SCD)等評價指標對用上述2種算法得到鑲嵌圖像進行對比分析[10]。

SFA體現邊緣的粗糙程度，反映了拼接縫消除效果的優劣。SFA值越小說明活動性越弱，即拼接縫消除效果越好、越光滑。空間頻率分為空間行頻率fr和空間列頻率fc，分別定義為

式中:M，N分別為圖像的列、行數;i，j分別為圖像的列、行坐標。

SFA定義為

SCD體現鑲嵌處理后圖像灰度的整體和諧性。以sn，tn分別表示2景圖像的重疊區域，鑲嵌完成后的對應區域為hn，則SCD定義為

基于上述分析，分別對2種算法的拼接縫消除效果進行了參數對比(表1)。

表1 本文算法與平分線法參數對比Tab.1 Comparison between parameters of proposed algorithm and bisection algorithm

從表1可以看出，用本文算法得到的鑲嵌圖像的清晰度較高;SFA和SCD均小于平分線法，即在鑲嵌圖像中拼接縫的消除使色調過度更平滑、灰度的整體和諧性更好。但在運算耗時方面，由于平分線法直接機械地以垂直平分線作為最佳拼接縫的位置，并未經過一定規則的篩選，因此平分線法的運行時間明顯少于本文算法是符合實際情況的。但本文算法的運行時間已能夠滿足用戶的需求。

2.2 與灰度差最小法比較

如圖5所示，由于基于灰度值差最小方法確定的最佳拼接縫選取的是對應像素灰度差最小的點，因此在一定程度上也可以避開一些目標(如圖5中黃色圓圈所示區域中的機場跑道);但其確定的拼接縫波動性較大，某些點與機場跑道相切或者過于接近，不利于后期的拼接縫消除。而用本文算法確定的拼接縫與機場跑道平行且相距一定距離，較穩定地沿繞著跑道的邊緣。

圖5 本文算法與灰度差最小法確定的拼接縫對比Fig.5 Comparison between seam－lines determined with proposed algorithm and minimum gray difference algorithm

在圖5的下部(如藍色箭頭所示)，用最小灰度 差法確定的拼接縫穿過了一些變化復雜的地物，若根據該方法確定的拼接縫進行拼接縫的消除，有可能會使同一地物出現不同變化，產生錯誤信息(圖5(a));而用本文方法確定的最佳拼接縫則有效地繞過了變化復雜的地物，使拼接縫位于灰度變化較為平緩的區域，這樣可以減少同一地物出現不同變化的現象，使得拼接縫消除處理后的鑲嵌圖像的整體視覺效果更佳(圖5(b))。

分別對圖5中2幅鑲嵌圖像采用本文提出的差值拼接縫消除方法進行拼接縫消除處理，得到結果圖像如圖6所示。

圖6 本文算法與灰度差最小法的拼接縫消除結果對比Fig.6 Comparison between seam－line removal results of proposed algorithm and minimum gray difference algorithm

由圖6可以看出，基于灰度差值最小的方法確定的拼接縫偏向圖像的一邊，因此容易造成拼接縫消除后的圖像一邊較亮而另一邊較暗(圖6(a))，圖像的大部分偏亮，而較靠近右側的圖像偏暗，因此雖然消除了拼接縫痕跡，但由于灰度分布不均勻，仍然在一定程度上影響了鑲嵌圖像的整體視覺效果;而本文算法確定的拼接縫分布均勻，基本集中在圖像中間區域，在消除灰度差異后，灰度分布較均勻，色調過渡自然(圖6(b))，保證了圖像中機場跑道主體部分的色調和對比度都比較適中，便于圖像的分析處理。表2對比了2種拼接縫消除算法的參數。

表2 灰度差最小法與本文算法參數對比Tab.2 Comparison between parameters of proposed algorithm and minimum gray difference algorithm

由表2可以看出，與上一組對比實驗相同，用本文算法得到的鑲嵌圖像的SFA和SCD均較小，即本文算法的拼接縫消除效果明顯，色調過渡更為平滑，灰度的整體和諧性較高，圖像較清晰，視覺效果基本令人滿意;此外，本文算法的耗時少于灰度值差最小法，運算效率提高近30%，具有明顯的優勢。

3 結論

本文提出了一種利用圖像灰度的梯度信息確定最佳拼接縫的算法，經過實驗驗證，具有一定的可行性和有效性。

1)本文在鑲嵌圖像的重疊區域內選取局部區域梯度最小點作為最佳拼接點，進而將最佳拼接點連接起來形成最佳拼接縫，根據確定的最佳拼接縫進行拼接縫消除的效果遠好于目前常用的平分線法和灰度值差最小法。

2)本文提出的基于局部區域梯度最小點的最佳拼接縫尋找算法能夠有效地繞開圖像中目標的邊緣，保留目標的完整性，使得拼接縫位于圖像中灰度變化較平緩的區域;而本文提出的差值拼接縫消除方法能夠在消除拼接縫的同時避免強制改正法容易產生的橫向帶狀效應，尤其在鑲嵌圖像間灰度差異較大的情況下，這種優勢更為明顯。

3)通過清晰度、空間頻率活動性(SFA)、結構對比度(SCD)和計算時間等參數的對比評價可知，使用本文方法得到的鑲嵌遙感圖像清晰，色調過渡平滑，具有較好的整體和諧性;且運算時間較少，效率明顯提高。

[1]Davis J.Mosaics of scenes with moving objects[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition，Santa Barnara:IEEE，1998:354－360.

[2]溫紅艷，周建中.基于灰色理論的遙感圖像最佳鑲嵌線檢測[J].計算機工程與應用，2009，45(15):31－33.Wen H Y，Zhou J Z.Optimal seam line detection algorithm of remote sensing image mosaic based on grey system theory[J].Computer Engineering and Applications，2009，45(15):31－33.

[3]方亞玲，焦偉利.利用對稱動態輪廓模型自動檢測最優鑲嵌線[J].科學技術與工程，2007，7(14):3451－3456 Fang Y L，Jiao W L.Detecting the optimal seam line automatically in image mosaic with twin snakes model[J].Science Technology and Engineering，2007，7(14):3451－3456.

[4]Wen H Y，Zhou J Z.An improved algorithm for image mosaic[C]//International Symposium on Information Science and Engineering.Shanghai:ISISE，2008:497－500.

[5]Chon J，Kim H，Lin C S.Seam－line determination for image mosaicking:A technique minimizing the maximum local mismatch and the global cost[J].ISPRS Journal of Photogrammetry and Remote Sensing，2010，65(1):86－92.

[6]王 軍，朱寶山，朱述龍，等.基于相關系數的遙感圖像拼接線檢測算法[J].測繪與空間地理信息，2011，34(3):151－153.Wang J，Zhu B S，Zhu S L，et al.A stitching line detection algorithm of remote sensing image based on correlation coefficient[J].Geomatics and Spatial Information Technology，2011，34(3):151－153.

[7]方賢勇.圖像拼接技術研究[D].杭州:浙江大學，2005.Fang X Y.Studies on image mosaic[D].Hangzhou:Zhejiang University，2005.

[8]Pan J，Wang M，Li D R ，et al.Automatic generation of seamline network using area Voronoi diagrams with overlap[J].IEEE Transactions on Geoscience and Remote Sensing，2009，47(6):1737－1744.

[9]范永弘，萬惠瓊，靳建立，等.基于DSM的遙感圖像拼接線自動生成技術[J].測繪科學技術學報，2011，28(1):33－36.Fan Y H，Wan H Q，Jin J L，et al.Remote sensing image mosaic line auto－ extraction based on DSM[J].Journal of Geomatics Science and Technology，2011，28(1):33－36.

[10]武 新，張煥龍，舒云星.基于視覺感知的鑲嵌圖像質量評價方法[J].計算機工程，2008，34(18):220－222.Wu X，Zhang H L，Shu Y X.Mosaic image quality evaluation method based on visual perception[J].Computer Engineering，2008，34(18):220－222.