基于遙感圖像信息特征的單調(diào)遞增SSDA算法

王 杉，陳 翔，司寒羽

（華東交通大學(xué)信息工程學(xué)院，江西南昌330013）

遙感是通過不與物體、區(qū)域或現(xiàn)象接觸獲取調(diào)查數(shù)據(jù)，并對數(shù)據(jù)進行分析從而得到物體、區(qū)域或現(xiàn)象的有關(guān)信息的一門科學(xué)和技術(shù)[1]。它是人類在模擬人的視覺系統(tǒng)基礎(chǔ)上逐步發(fā)展起來的一種高科技觀測技術(shù)，通過檢測和度量地物目標(biāo)電磁輻射能量所得到的客觀記錄，把人眼看得到的和看不到的景物都轉(zhuǎn)化為人眼所能看到的圖像，重現(xiàn)地物目標(biāo)電磁輻射特性的空間分布狀況[2]。由于遙感能夠提供大尺度（宏觀）、動態(tài)的觀測且不受地理位置、天氣和人為條件限制，以不同的時空尺度不斷地提供多種地表信息[3]，所以遙感圖像已被廣泛應(yīng)用于環(huán)境監(jiān)測、資源探測、生態(tài)研究、測繪制圖、軍事指揮等眾多領(lǐng)域。例如利用遙感圖像觀測云的移動（臺風(fēng)）、云量、地?zé)帷⑺萚4]全球性同步觀測數(shù)據(jù)已服務(wù)于人們的日常生活。

而遙感圖像配準(zhǔn)是指將取自同一目標(biāo)區(qū)域的兩幅或多幅圖像在空間位置上最佳匹配起來，這些圖像可以是由同一傳感器在不同時間獲取的，也可以是來自不同的傳感器[5]。遙感圖像具有觀測目標(biāo)細(xì)節(jié)能力強、觀測范圍廣的特點，因此遙感圖像的實時性配準(zhǔn)一直都是遙感圖像研究中最主要的難題之一[6]。利用來源于圖像的信息特征進行圖像配準(zhǔn)能夠獲得可信度高、信息完善的目標(biāo)真實狀態(tài)和細(xì)節(jié)，從而大大提高了在復(fù)雜背景和干擾存在的情況下目標(biāo)識別的正確率[7]。

近二十年來，圖像配準(zhǔn)技術(shù)的研究取得了重大進展，涌現(xiàn)出了多種方法，主要分為基于像素相似性的方法和基于特征的方法[8]。而目前針對高分辨率圖像較常用的配準(zhǔn)方法是采用基于圖像灰度信息的定位算法。通常直接利用整幅圖像的灰度信息建立兩幅圖像之間的相似性度量，然后采用某種搜索策略尋找使相似性度量值最大或最小的變換模型的參數(shù)值[9]。這種匹配方法采取的是一種遍歷性搜索策略，需要在搜索區(qū)域內(nèi)所有像素點上進行一對一的區(qū)域相關(guān)配準(zhǔn)計算，數(shù)據(jù)量和計算量很大，配準(zhǔn)速度較慢，對算法的實時性有很大影響[10-11]。為了減少匹配相關(guān)運算量，在文獻(xiàn)[12]中，Barnea提出了一種序列相似性檢測算法（SSDA）。該算法能很快丟棄不匹配的點，減少花在不匹配點上的計算量，從而提高匹配速度。但這類算法依然存在實時性差等缺陷。

基于圖像信息特征的匹配方法可以克服上述算法的不足，由于圖像的特征點比像素點要少很多，從而大大減少了匹配過程的計算量。同時特征點的匹配度量值對位置的變化比較敏感，角點作為圖像最為重要的特征點，對圖像圖形的理解和分析有很重要的作用。通過對遙感圖像角點的提取，可以有效提高匹配的精度和效率[13-14]。基于圖像特征的匹配通常是利用圖像中位置相對不變的特征來進行匹配的，可以克服灰度相關(guān)匹配的一些缺點，但是圖像特征的提取和定位通常是比較困難，如果原圖像和參考圖像是比較復(fù)雜的圖像時匹配是很難獲得好的效果。

因此，在傳統(tǒng)SIFT的基礎(chǔ)上，利用圓形結(jié)構(gòu)的旋轉(zhuǎn)不變性，結(jié)合主成分分析法（principal component analysis，PCA），提出一種PCA-圓形SIFT特征點描述符提取圖像特征角點。通過分析單調(diào)遞增閾值序列SSDA算法的特點，結(jié)合圖像特征點匹配，提出一種基于圖像信息特征的單調(diào)遞增閾值序列SSDA配準(zhǔn)算法，最后通過實驗仿真該算法的可行性。

1 基于PCA-圓形結(jié)構(gòu)SIFT特征點的提取

SIFT特征檢測算法是Lowe提出的一種基于尺度空間的，對圖像縮放、旋轉(zhuǎn)甚至仿射變換保持不變性的圖像局部特征描述算子[15]。SIFT特征描述算子的生成一般包括以下幾個步驟：

1）構(gòu)建尺度空間，檢測極值點，獲得尺度不變性；

2）特征點過濾并進行精確定位；

3）為特征點分配方向值；

4）生成特征描述子；

5）特征向量的匹配。

本文在傳統(tǒng)SIFT的方法基礎(chǔ)上，鑒于圓具有很好的旋轉(zhuǎn)不變性，引用了一種用圓形結(jié)構(gòu)來構(gòu)造SIFT特征點描述符，并結(jié)合PCA方法，建立了一種PCA-圓形結(jié)構(gòu)SIFT算法。該算法通過降維的方式，極大地減少了計算過程，提高了運算速率，并且有效提取了特征點。

1.1 傳統(tǒng)SIFT特征向量的生成

對每一個篩選出的特征點，要以此特征點作為中心點，在這個點的周圍選取一個大小為16×16的區(qū)域，再將這個所選取區(qū)域平均分成4個大小均為4×4的小區(qū)域，并且計算每個小區(qū)域的梯度直方圖，直方圖包含有8方向，這樣就獲得了一個4×4×8=128維的向量，也就生成了SIFT特征描述符向量，直方圖的峰值就是所選特征點的主方向。

1.2 圓形結(jié)構(gòu)SIFT特征向量的生成

圖1（a）的中心點表示SIFT特征描述符提取的特征點位置點P(t1，t2)，設(shè)半徑為r，確定圓形區(qū)域為(x-t1)2+(x-t2)2=r2式中，r是控制圓形區(qū)域的半徑，最大取值為8。構(gòu)造4個半徑不同的同心圓環(huán)，這樣就把圓形窗口分成4個圓環(huán)形區(qū)域。原算法在4×4的方形窗口內(nèi)計算8個方向的梯度方向直方圖，改進算法則是在以特征點為中心的圓形區(qū)域內(nèi)構(gòu)造4個圓環(huán)，在每個圓環(huán)內(nèi)分別計算0°～360°均勻分布的12個方向上的梯度直方圖。

圖1 改進的SIFT特征點描述符Fig.1 The feature point descriptor of improved SIFT

圖1（b）所示為內(nèi)圓生成的12個方向的特征向量。具體統(tǒng)計過程為：如果某個像素點梯度方向落在圖1b）某個箭頭方向（即梯度方向）附近，則其相應(yīng)的梯度高斯加權(quán)幅值就累加在這個方向上，這樣就可以用梯度直方圖統(tǒng)計出內(nèi)圓梯度的累加值，再將這些梯度累加值從小到大排列。內(nèi)圓的12個梯度累加值排列后作為1～12維的特征向量，次外圓梯度累加值排列后作為13～24維的特征向量，依次類推。4個同心圓環(huán)有4×12共48維特征向量作為特征點的描述符[16-17]。

1.3 PCA-圓形結(jié)構(gòu)SIFT特征向量的生成

PCA-SIFT描述符與標(biāo)準(zhǔn)SIFT描述符具有相同的亞像素位置（sub-pixel）、尺度（scale）和主方向（domi?nant orientations），但在特征描述符生成時有所不同，PCA-SIFT[18-19]通過PCA方法將傳統(tǒng)SIFT的128維特征向量進行降維，以達(dá)到更精確的表示方式。

由1.2節(jié)可知，采用圓形結(jié)構(gòu)SIFT可以將傳統(tǒng)128維SIFT特征向量維數(shù)降低至48維。本節(jié)將結(jié)合PCA方法，對48維的圓形結(jié)構(gòu)SIFT特征點描述符繼續(xù)降維，進一步減少了計算量，提高了精確度。利用PCA方法對基于圓形結(jié)構(gòu)48維SIFT特征描述符進行降維的具體方法如下：

1）輸入兩幅待匹配圖像中所有關(guān)鍵點（設(shè)為n個）的48維SIFT特征描述符，將輸入的這n個特征描述符作為樣本，寫出樣本矩陣為，其中xi表示第i個特征點的48維特征向量。

2）計算n個樣本的平均特征向量

3）計算所有樣本點的特征向量與平均特征向量的差，得到差值向量di=xi-，i=1，2，…，n。

5）求協(xié)方差矩陣的48個特征值λi和48個特征向量ei。

6）將求出的48個特征值按從小到大的順序進行排列λ1≥λ2≥…≥λ48和對應(yīng)的特征向量[e1，e2，…，e48]。

7）選取對應(yīng)t個最大特征值的特征向量作為主成分的方向，在實驗中選取t=12。

8）構(gòu)造一個48×12的矩陣A，它的列由t個特征向量組成。

9）把原始的48維SIFT描述符依據(jù)式（6）投影到所計算出的n維子空間M中，就可以得到PCA-SIFT的描述符y1，y2，…，yn，即yi=xiA。

因為實驗中選取t=12，所以矩陣A的大小為48×12，xi的大小為1×48，所以xiA就得到了一個大小為1×12的矩陣，即每一個yi就是一個12維的特征描述符，也就是把原來的48維傳統(tǒng)SIFT特征描述符降成了12維的PCA-SIFT特征描述符。

本文通過PCA-圓形結(jié)構(gòu)SIFT的建立，將傳統(tǒng)SIFT 128的特征描述符，通過先建立圓形結(jié)構(gòu)，后結(jié)合PCA方法兩個步驟降成了12維的特征描述符。為下一步特征向量的匹配，由原先采用歐式距離對具有128維的特征點描述子的相似性進行度量，變成了現(xiàn)在采用歐式距離對具有12維的特征點描述子的相似性進行度量，減少了數(shù)以十倍的計算量，極大的簡化了計算過程，節(jié)約了匹配算法的運行時間。

2 模板的圖像匹配

2.1 傳統(tǒng)SSDA算法

序貫相似性檢測算法（sequential similarity detection algorithms，SSDA）將大小為M×M的模板T在大小為N×N的搜索圖S上平移，模板覆蓋下的那塊搜索圖設(shè)為子圖Sij，i，j為這塊子圖的左上角像點在S中的坐標(biāo)，則i和j的取值范圍為1≤i，j≤N-M+1，如圖2所示。SSDA的算法過程如下[20-22]：

1）定義絕對誤差：

其中

圖2 被搜索圖S和模板TFig.2 The search figure S and the template T

2）取一固定閾值Tk。

3）在子圖Si，j(m，n)中隨機選取對象點。計算它同T中對應(yīng)點的誤差值，然后把這個差值和其他點對的差值累加起來，當(dāng)累加r次誤差超過Tk，則停止累加，并記下次數(shù)r，定義SSDA的檢測曲面為

4）把I(i，j)值大的(i，j)點作為匹配點，因為這點上需要很多次累加才使總誤差超過Tk，如圖3所示，圖中給出了A，B，C這3個參考點上得到的誤差累計增長曲線。A，B反映了模板T不在匹配點上，這時總誤差增長很快，超出閾值，而曲線C中總誤差增長很慢，很可能是一套準(zhǔn)確的候選點[23]。

2.2 單調(diào)遞增閾值序列SSDA算法

基本SSDA算法所選取的閾值T是固定的，對于不同區(qū)域上子圖的閾值選取并不一定是最佳的，容易受到噪聲影響，而且計算量較大。如果采用一種單調(diào)增長的閾值序列[17]，使非匹配點用更少的計算就達(dá)到閾值而被丟棄，真匹配點需更多次誤差累計才達(dá)到閾值，則能夠使閾值T逐漸逼近最佳閾值，從而增加了SSDA算法的準(zhǔn)確性，使得匹配速度大大提高，如圖4所示。

圖3 Tk為常數(shù)時的累計誤差增長曲線Fig.3 Accumulative error growth curves whenTkis constant

圖4 Tk用單調(diào)增加閾值序列的情形Fig.4 Accumulative error growth curves whenTk is monotonically increasing

由于除匹配點以外，絕大數(shù)的情況下都是對非匹配點計算的，顯然，越早丟棄非匹配點將節(jié)省時間。根據(jù)上文傳統(tǒng)的SSDA算法介紹，增長曲線A，B反映了模板T不在匹配點上，可以發(fā)現(xiàn)，A，B在很早的時候就已經(jīng)達(dá)到閾值而被拋棄，和圖2相比，圖4單調(diào)增加閾值算法A，B點經(jīng)歷了更少次的運算，圖4中斜線區(qū)域的面積為此算法所節(jié)省的計算量。曲線C中總誤差增長緩慢，很可能是一套準(zhǔn)確的候選點。基于以上思想，本文提出的改進算法如下：

在匹配過程中，先要獲得初始匹配點(x，y)，并且需要制定一個初始閾值T。可以設(shè)置一個較小的數(shù)值作為初始門限，初始匹配點可以設(shè)置為（0，0），然后使模板圖像與所取到的特征點做相關(guān)運算。在待匹配圖像中每個特征點處同樣利用到公式（1）計算模板圖與搜索子圖的相關(guān)測度ε(i，j)。如果在計算像素點相關(guān)測度ε(i，j)的過程中，ε(i，j)累積超過閾值T，就停止該像素點的相關(guān)性計算，并且把此時計算所得的ε(i，j)作為新的門限閾值，并以此閾值去計算下一個像素點的相關(guān)測度值ε；如果計算完該搜索子圖，而ε仍然小于閾值T，則更新匹配點為此次運算的運算位置。用公式表示為

3 本文遙感圖像匹配流程圖

先將原圖像和模板圖像通過基于PCA-圓形結(jié)構(gòu)SIFT特征點描述符提取圖像角點，將此角點作為單調(diào)遞增閾值序列SSDA算法的基本像素點，通過模板匹配，最后完成圖像匹配。

基本的SSDA模板匹配在選取隨機點時會找到誤差較大的點，從而及早地結(jié)束匹配計算過程。相比之下，利用圖像自身信息特征可以及時發(fā)現(xiàn)并排除孤立的像素點，具有較強的抗干擾能力；而且只利用圖像的特征點進行匹配，能夠大大減少匹配過程的計算量。先利用基于特征的方法獲得一個粗略的匹配，然后利用基于單調(diào)遞增SSDA方法對結(jié)果進行進一步的優(yōu)化，達(dá)到精匹配。

圖5 遙感圖像匹配流程圖Fig.5 The flow chart of remote image registration

4 實驗結(jié)果及分析

為了驗證本文所提出算法的高效性，對固定閾值SSDA算法、單調(diào)遞增閾值序列的SSDA算法以及基于圖像信息特征的單調(diào)增長閾值序列SSDA配準(zhǔn)算法在處理時間上做了比較。處理結(jié)果，如圖（6）所示。

圖6 實驗數(shù)據(jù)源及結(jié)果Fig.6 Experimental data sources and results

圖6中，選取兩幅圖作為圖像匹配實驗圖，第一幅為探測地球外小行星遙感圖像，第二幅為中國氣象局發(fā)布的風(fēng)云二號氣象衛(wèi)星云圖。其中（a），（b），（c）為第一幅圖的圖像匹配序列，（a）為待匹配圖像，尺寸為170×130，（b）為模板圖像，尺寸為30×30，（c）為匹配結(jié)果。（d），（e），（f）為第二幅圖的圖像匹配序列，（d）為待匹配圖像，尺寸為1 720×1 290，（e）為模板圖像，尺寸為179×166，（f）為匹配結(jié)果。

通過統(tǒng)計各種算法在此兩組實驗對象的匹配時間，由表1可知，單調(diào)遞增閾值序列SSDA算法與固定閾值SSDA算法相比能較大的提高匹配速度，但由于隨機點選取方式的影響，使得模板與子圖的大多數(shù)點都需進行匹配，算法速度仍不理想，而基于遙感圖像信息特征的單調(diào)遞增閾值序列SSDA算法則能較好的解決這一問題。這種算法利用圖像信息特征選取匹配點的方式可以提高匹配精度。

表1 各種算法處理時間比較Tab.1 Processing time comparison between different algorithm

本文利用優(yōu)化的PCA-圓形結(jié)構(gòu)SIFT算法結(jié)構(gòu)提取圖像特征角點，降低了特征描述符的維數(shù)，減少相似性度量計算，由此方法建立特征點集，然后采用單調(diào)遞增閾值序列SSDA算法進行精確匹配。該氣象圖像配準(zhǔn)系統(tǒng)不但減少了計算量，縮短了匹配時間，而且也表現(xiàn)出了更好的抗噪聲能力。通過分析可知，在圖像尺寸較大的情況下，本文算法優(yōu)勢更加明顯。

5 結(jié)束語

遙感圖像的實時性配準(zhǔn)一直以來都是制約遙感圖像處理高效性的一個瓶頸。由于遙感圖像觀測范圍廣，包含信息量大，一般的配準(zhǔn)算法很難滿足在保證其配準(zhǔn)精度的前提下實時性方面的需求。本文以經(jīng)典SSDA為基礎(chǔ)，針對現(xiàn)有算法存在的問題，提出一種基于圖像信息特征單調(diào)遞增閾值序列的匹配算法，大大減少了過程的計算量，提高了匹配的精度。另外，在實際應(yīng)用中，可以結(jié)合粗-細(xì)分層搜索策略等進一步提高匹配性能。

[1]LILLESAND T M，KIEFER R W.遙感與圖像解譯[M].彭望綠，余先川，周濤，等，譯.4版.北京：電子工業(yè)出版社，2003：1-34.

[2]戴昌達(dá)，姜小光，唐伶俐.遙感圖像應(yīng)用處理與分析[M].北京：清華大學(xué)出版社，2004：3-75.

[3]趙英時.遙感應(yīng)用分析原理與方法[M].北京：科學(xué)出版社，2003：309-414.

[4]MAITRE H，PINCIROLI M.Fractal characterization of a hydrological basin using SAR satellite images[J].IEEE Transactions on Geoscience and Remote Sensing，1999，37（1）：175-181.

[5]饒俊飛.基于灰度的圖像匹配方法研究[D].武漢：武漢理工大學(xué)，2005.

[6]雷琳，李智勇，粟毅.利用多特征融合匹配實現(xiàn)遙感圖像多目標(biāo)關(guān)聯(lián)[J].信號處理，2009（3）：454-459.

[7]章毓晉.圖像分割[M].北京：科學(xué)出版社，2001：39-45.

[8]梁青，蔣先剛，沈濤.基于顏色互信息的病變細(xì)胞圖像配準(zhǔn)算法研究[J].華東交通大學(xué)學(xué)報，2011，28（4）：14-18.

[9]TTTI L，KOCH C，NIEBUR E.A model of saliency-based visual attention for rapid scene analysis[J].IEEE Transactions on PatternAnalysis and Machine Intelligence，1998，20（11）：1254-1258.

[10]OLSON C F，HUTTENLOCHER D P.Automatic target recognition by matching oriented edge pixels[J].IEEE Transaction son Image Processing，1997，6（1）：103-113.

[11]TTTI L，KOCH C.Computational modeling of visual attention[J].Nature Reviews Neuroscience，2001，2（3）：194-203.

[12]BARNEA D I，SIVERMAN H F.A class of algorithms for digital image registration[J].IEEE Trans Computers，1972，21（2）：179-186.

[13]HATABU A，MIYAZAKI T，KURODA I.Optimization of decision-timing for early termination of SSDA-bassed block matching[C]//International Conference on Multimedia and Expo Piscataway，NJ：IEEE，2003：821-824.

[14]HONG ZHENHUA，ZHU PEIYING.An improved SSDA applied in target tracking[C]//Pattern Recognition 9th IEEEE International Conference，Hardware Software：Computing&Processing，1988：767-769.

[15]王敬東，徐亦斌，沈春榮.一種新的任意角度旋轉(zhuǎn)的景象匹配方法[J].南京航空航天大學(xué)學(xué)報，2005，37（1）：6-10.

[16]姚文偉，張智斌，李國，等.圖像匹配算法 SIFT的改進[J]，鄭州輕工業(yè)學(xué)院學(xué)報，2011，26（6）：67-70.

[17]吳若鴻，基于特征匹配的雙目立體視覺技術(shù)研究[D].武漢：武漢科技大學(xué)，2010.

[18]馬莉，韓燮.主成分分析法（PCA）在 SIFT 匹配算法中的應(yīng)用[J].電視技術(shù)，2012，36（1）：129-132.

[19]ATSUSHI H，TAKASHI M，ICHIRO K.Optimization of decision-timing for early termination of SSDA-bassed block matching[C]//Acoustics，Speech，and Signal Processing，Proceedings（ICASSP 03），2003 IEEE International Conference，2003：821-824.

[20]TAUBMAN D.High performance scalable image compression with EBCOT[J].IEEE Trans on Image Processing，2000，9（7）：1158-1170.

[21]劉海波.Visual C++數(shù)字圖像處理技術(shù)詳解[M].北京：機械工業(yè)出版社，2010：293-296.

[22]沈庭之，方子文，數(shù)字圖像處理及模式識別[M].北京：北京理工大學(xué)出版社，1998：151-152.

[23]LOWE D.Distinctive image features from scale-invariant key-points[J].Int J of Comp Vision，2004，60（2）：91-110.