基于位置傳播的ADS40 L0級影像最佳掃描行快速搜索算法

石 寧，馬慧云，張云生，鄒崢嶸，孟俊俊

（中南大學(xué) 地球科學(xué)與信息物理學(xué)院，湖南 長沙410083）

三線陣傳感器以高影像分辨率、多波段成像能力、可形成3對立體像對和地面覆蓋寬［1］等特點逐漸成為獲取攝影測量與遙感數(shù)據(jù)的重要手段。ADS40作為機(jī)載三線陣傳感器的代表，自被推出以來備受青睞［2－3］。它采用推掃式成像，可提供多種類型的數(shù)字影像數(shù)據(jù)［4］，且集成POS（I MU＿DGPS）系統(tǒng)，可為每條掃描線提供較為準(zhǔn)確的外方位元素初值［5］。但由于受氣流等因素影響，機(jī)載平臺的軌道不穩(wěn)定，導(dǎo)致飛行速度、飛行姿態(tài)角以及飛行航高等參數(shù)發(fā)生變化，某些掃描線不再平行，原始影像產(chǎn)生嚴(yán)重的扭曲變形。因此，須對原始影像進(jìn)行幾何預(yù)處理生成Level 1級影像，消除因軌道不平穩(wěn)、姿態(tài)角變化等因素造成的幾何變形。ADS40影像由Level 0級糾正到Level 1級通常有兩種方法：直接法和間接法［6］。在原始影像生成過程中，存在影像重復(fù)或遺漏，采用直接法糾正影像，易導(dǎo)致糾正影像像元排列不規(guī)則、重復(fù)或遺漏，難以進(jìn)行灰度內(nèi)插獲得規(guī)則排列的糾正影像［7］。因此，一般采用間接法糾正影像，即傳統(tǒng)的反投影變換［8］，而如何高效搜索最佳掃描行是其中的關(guān)鍵。

三線陣CCD沿軌道方向推掃成像時，嚴(yán)格遵循中心投影關(guān)系 即共線方程，見式（1 其為反投影計算物方坐標(biāo)和三線陣ADS40影像采用間接法糾正計算最佳掃描行的基礎(chǔ)。

其中：（X，Y，Z）為物方坐標(biāo)；（XS，YS，ZS）為攝影中心坐標(biāo)；a1，a2，a3，b1，b2，b3，c1，c2，c3為旋轉(zhuǎn)矩陣元素；（x，y）為焦平面坐標(biāo)；f為相機(jī)焦距。

ADS40航拍影像有幾萬、十幾萬甚至幾十萬行，如何高效搜索某一地面點的最佳掃描行是目前研究的重點和難點。最佳掃描行搜索算法目前主要有二分法［11］和順序搜索算法［12］等。二分法初始搜索窗口的起始行為原始影像第一行，終止行為原始影像最后一行，影像搜索范圍跨度太大；順序搜索算法需物方點坐標(biāo)經(jīng)共線方程投影到焦平面、焦平面坐標(biāo)投影到原始影像坐標(biāo)、原始影像坐標(biāo)反投影到焦平面，坐標(biāo)系轉(zhuǎn)換復(fù)雜。

本文在對ADS40影像成像規(guī)律和已有搜索算法深入理解分析基礎(chǔ)上，提出一種基于位置傳播的ADS40 L0級影像最佳掃描行快速搜索算法。本算法充分利用ADS40影像成像規(guī)律，其最佳掃描行初始搜索窗口相比二分法大大縮小，可解決傳統(tǒng)搜索算法大量迭代導(dǎo)致的計算效率瓶頸。本文擬采用ADS40影像對算法進(jìn)行驗證并與二分法實驗結(jié)果進(jìn)行對比。

1 基于位置傳播的ADS40 L0級影像最佳掃描行快速搜索算法

1．1 機(jī)載三線陣ADS40影像成像原理

三線陣成像時，放置在同一焦平面上的3個不同線陣（前視、下視、后視）在同一時刻分別捕獲不同的物方點，成像在3個不同的影像條帶上；同一物方點則在不同時刻分別成像在3個不同的影像條帶上，如圖1所示。因此，每個物方點都為三度重疊，任意兩線陣生成的影像均可構(gòu)建立體模型。每次掃描都會生成相應(yīng)的POS數(shù)據(jù)，并有唯一的時間標(biāo)志。

1．1．1 穩(wěn)定情況下的成像規(guī)律

如果飛行平臺穩(wěn)定且飛行速度控制在相機(jī)標(biāo)定范圍內(nèi)，理論上掃描線近似平行相鄰。假設(shè)地物A－L為Level 1級影像某行像元點對應(yīng)的物方點，掃描線第一次掃過地物A部分，第二次掃過地物B部分，以此類推，第N 次掃過地物L(fēng)部分，如圖2（a）所示。由于航拍時，平臺易沿著與航向垂直方向發(fā)生細(xì)微的左右擺動（即“側(cè)滾”），但掃描線中地物像點與地物本身位置順序關(guān)系一致，所以最終形成的原始圖像如圖2（b）所示；具體實驗中，穩(wěn)定情況下，Level 1級影像某行像元點對應(yīng)物方點的最佳掃描行在原始Level 0級影像中的分布情況如圖2（c）所示，其大致分布與圖2（b）中對應(yīng)像點位置所在行類似，即最佳掃描行依次為地物A、B、C、D、E、F、G、H、I、J、K、L等像點所在行。

1．1．2 異常情況下的成像規(guī)律

如果在飛行瞬間，環(huán)境發(fā)生異常，平臺發(fā)生小幅度偏移或抖動，此時某個或某幾個掃描線會發(fā)生錯位偏移。假如掃地物D部分的瞬間，平臺發(fā)生偏移或抖動，以至掃描線首先掃到地物E部分，然后掃到地物D部分，如圖3（a）所示，此時地物D、E兩部分發(fā)生錯位偏移，最終形成的原始影像如圖3（b）所示。具體實驗中，異常情況下，Level 1級影像某行像元點對應(yīng)地面點的最佳掃描行在原始Level 0級影像中的分布情況如圖3（c）所示，其大致分布與圖3（b）中像點位置所在行稍有不同，其最佳掃描行同樣為地物 A、B、C、D、E、F、G、H、I、J、K、L等像點所在行，只是D、E部分發(fā)生錯位，兩部分像點所在行發(fā)生互換。

圖1 ADS40影像成像原理示意圖

圖2 ADS40穩(wěn)定時成像規(guī)律示意圖

圖3 ADS40異常時成像規(guī)律示意圖

1．2 算法原理及流程

最佳掃描行為三線陣掃描地物時其像點在原始影像上的行號。根據(jù)1．1機(jī)載三線陣ADS40影像成像原理可知，掃描線中地物像點與地物本身位置順序關(guān)系一致，因此，穩(wěn)定成像情況下，如地物A部分的最佳掃描行已搜索到，搜索地物B部分的最佳掃描行時，則可以地物A部分的最佳掃描行作為搜索基準(zhǔn)傳播到地物B部分并結(jié)合設(shè)定的初始窗口搜索半徑進(jìn)行搜索；同樣，搜索地物C部分的最佳掃描行時，可以地物B部分的最佳掃描行作為搜索基準(zhǔn)傳播到地物C部分并結(jié)合初始窗口搜索半徑進(jìn)行搜索；異常成像情況下，平臺不穩(wěn)發(fā)生偏移錯位現(xiàn)象，此時地物D部分的最佳掃描行并不一定在地物C部分最佳掃描行的后面，用初始窗口搜索半徑可能搜索不到其最佳掃描行，但地物D部分的最佳掃描行不會偏離地物C部分的最佳掃描行太遠(yuǎn)，可擴(kuò)大窗口搜索半徑搜索地物D部分的最佳掃描行，窗口可循環(huán)擴(kuò)大至搜索到其最佳掃描行為止；每次進(jìn)行下一地物點最佳掃描行搜索時，先以穩(wěn)定成像情況處理，如未能搜索到其最佳掃描行，則以異常情況處理?；谖恢脗鞑サ腁DS40 L0級影像最佳掃描行快速搜索算法流程如圖4所示。

1）程序起始階段，為避免復(fù)雜的矩陣運(yùn)算，利用外方位元素建立旋轉(zhuǎn)矩陣查找表，以后進(jìn)行矩陣運(yùn)算時直接調(diào)用。

2）調(diào)用查找表及相機(jī)檢校文件、相機(jī)支持文件等參數(shù)，計算Level 1級影像范圍大?。ㄐ辛刑枺?/p>

3）執(zhí)行二分法搜索Level 1級影像某行起始像元點對應(yīng)的物方點在Level 0級影像上的最佳掃描行，具體步驟為：①給定初始搜索窗口。窗口起始搜索行為原始影像第一個掃描行TS，窗口終止搜索行為原始影像最后一個掃描行TE。中點搜索行為TM＝［（TS＋TE）／2］。②分別把TS，TE，TM行對應(yīng)的外方位元素代入式（1），分別計算其在像方空間坐標(biāo)系中距原點的距離d xS，d xE，d xM。假如d xS×d xM＜＝0，則 TS＝TS，TE＝TM；反之，則TS＝TM，TE＝TE。反復(fù)迭代直至搜索窗口寬度小于預(yù)先設(shè)定的閾值。③分別計算TS，TE行間對應(yīng)的d x，絕對值最小的d x對應(yīng)的行號為最佳掃描行L。

圖4 位置傳播算法流程圖

4）根據(jù)位置傳播算法原理搜索Level 1級影像本行下一像元點對應(yīng)的物方點在Level 0級影像上的最佳掃描行，以上一像元點對應(yīng)的物方點最佳掃描行L作為搜索基準(zhǔn)，其搜索步驟為：①設(shè)定初始搜索窗口，初始窗口搜索半徑設(shè)定為R，窗口起始行為TS＝L－R，窗口終止行為TE＝L＋R。②將TS，TE行間對應(yīng)的外方位元素代入式（1），計算其在像方空間坐標(biāo)系中距原點的距離d xS，d xE。如d xS×d xE＞0，則擴(kuò)大窗口搜索半徑R，計算d xS，d xE，直至d xS×d xE＜＝0。③分別計算TS，TE行間對應(yīng)的d x，絕對值最小的d x對應(yīng)的行號為最佳掃描行L。

5）判斷此行所有像元點是否已經(jīng)處理完畢，如果為否，重復(fù)步驟4）～5）；如果為是，此行處理完畢。

6）判斷此行是否為Level 1級影像最后一行，如果為否，繼續(xù)下一行的搜索，重復(fù)步驟3）～5）；如果為是，整幅圖像處理完畢，程序結(jié)束。

2 實 驗

實驗均在Micr osoft Windows7操作系統(tǒng)下基于Microsoft Visual Studio 2010 C＋＋集成開發(fā)環(huán)境編寫實現(xiàn)，計算機(jī)硬件配置CPU為Inter（R）Core（T M）i5－2400 3．10GHZ，內(nèi)存容量為4 GB。

2．1 實驗數(shù)據(jù)

本文選取徠卡ADS40影像對算法進(jìn)行驗證，影像參數(shù)見表1。

表1 實驗影像

2．2 實驗結(jié)果

采用1．2節(jié)所介紹的基于位置傳播的ADS40 L0級影像最佳掃描行快速搜索算法對表1中實驗影像進(jìn)行最佳掃描行搜索，統(tǒng)計迭代和耗時結(jié)果，其中初始窗口搜索半徑設(shè)定為1。同時采用二分法對表1中實驗影像進(jìn)行最佳掃描行搜索，步驟參考1．2算法流程中步驟1）～3），統(tǒng)計迭代和耗時結(jié)果，其中二分法閾值設(shè)定為5。采用效率比和迭代比對兩種算法的迭代和耗時結(jié)果進(jìn)行對比，效率比為二分法搜索時間比基于位置傳播的ADS40 L0級影像最佳掃描行快速搜索算法搜索時間；迭代比為二分法平均迭代次數(shù)比基于位置傳播的ADS40 L0級影像最佳掃描行快速搜索算法平均迭代次數(shù)。本文同步進(jìn)行二分法與本算法糾正影像的匹配率統(tǒng)計，即在實驗搜索完最佳掃描行后附加灰度重采樣步驟，生成糾正影像，以二分法糾正生成的圖像為基準(zhǔn)影像，基于位置傳播的ADS40 L0級影像最佳掃描行快速搜索算法糾正生成的圖像為匹配影像。匹配率越高表明兩種算法搜索到的最佳掃描行相同程度越高。二分法與基于位置傳播的ADS40 L0級影像最佳掃描行快速搜索算法對比結(jié)果見表2。

表2 迭代、耗時和匹配率結(jié)果

2．3 結(jié)果分析

對實驗結(jié)果進(jìn)行分析，可得出以下結(jié)論：

1）由表2可知，二分法和基于位置傳播的ADS40 L0級影像最佳掃描行快速搜索算法均受共線方程迭代次數(shù)影響，但二分法平均迭代17次而本算法平均迭代2次，所以相對二分法其迭代次數(shù)更少；由于迭代次數(shù)減少，所以本算法耗時減少，本次實驗中二分法平均耗時為794 188 ms，而本算法平均耗時為119 123 ms。因此，本算法平均搜索效率更高，本次實驗中為二分法的6．66倍。

2）由表1和表2可知，掃描行數(shù)量從73 400行增加到79 000行，二分法搜索次數(shù)逐漸增多，從17．16次增加到17．27次；基于位置傳播的ADS40 L0級影像最佳掃描行快速搜索算法則不受掃描行數(shù)量的影響，只受掃描線偏移量影響，因此，搜索次數(shù)為2保持不變。相比二分法，掃描行數(shù)量越多，本算法越高效，本次實驗中效率從6．59增加到6．73倍。因此，相比二分法，掃描行數(shù)量越多，本算法越高效。

3）由表2可知，基于位置傳播的ADS40 L0級影像最佳掃描行快速搜索算法和二分法搜索算法結(jié)果匹配率非常高，平均達(dá)到99．99%，表明本算法具有較高的準(zhǔn)確性。

3 結(jié)束語

ADS40傳感器獨特的成像方式導(dǎo)致最佳掃描行的搜索必不可少，目前國內(nèi)對于這方面的研究還較少，對ADS40影像最佳掃描行的搜索算法進(jìn)行改進(jìn)，有助于實時、高效地糾正圖像。本文在對ADS40影像成像規(guī)律和已有搜索算法進(jìn)行深入理解分析的基礎(chǔ)上，提出一種基于位置傳播的ADS40 L0級影像最佳掃描行快速搜索算法。本算法充分利用ADS40影像成像規(guī)律，減少了迭代搜索次數(shù)，突破了搜索效率瓶頸，有效提高了ADS40影像最佳掃描行的搜索效率。實驗證明本算法正確、高效，能達(dá)到幾何預(yù)處理成圖的精度。因此，本文提出的基于位置傳播的ADS40 L0級影像最佳掃描行快速搜索算法能為實時、高效處理海量的ADS40數(shù)據(jù)提供支持。

［1］ 劉軍，張永生，范永弘．ADS40機(jī)載數(shù)字傳感器的攝影測量處理與應(yīng)用［J］．測繪學(xué)院學(xué)報，2002，19（3）：186－194．

［2］ TEMPEL MANN U，BORNER A．Photogrammetric soft－ware f or the L H systems ADS40 Air bor ne Digital Sensor［C］．IAPRS，Vol．XXXIII，Amsterdam，2000．

［3］ SANDAU R，BRAUNECKER B．Design Principles of the L H Systems ADS40 Airborne Digital Sensor［C］．IAPRS，Vol．XXXIII，Part B1，Amsterdam，2000，258－265．

［4］ 王永平，李英成，薛艷麗，等．ADS40推掃式數(shù)字航攝儀試驗研究［J］．測繪科學(xué)，2007，32（1）：119－121．

［5］ 陳科，黃天勇，聞平，等．利用勻光勻色建立色彩一致性無縫DOM影像數(shù)據(jù)庫的方法研究［J］．測繪工程，2014，23（2）：66－69．

［6］ 劉軍，張永生，王冬紅，等．INS／DGPS支持的機(jī)載線陣推掃影像幾何校正［J］．遙感學(xué)報，2006，10（1）：21－26．

［7］ 趙雙明，李德仁．ADS40影像幾何預(yù)處理［J］．武漢大學(xué)學(xué)報：信息科學(xué)版，2006，31（4）：308－311．

［8］ 劉軍．GPS／I MU輔助機(jī)載線陣CCD影像定位技術(shù)研究［D］．鄭州：信息工程大學(xué)，2007．

［9］ 李德仁，趙雙明，陸玉紅，等．機(jī)載三線陣傳感器影像區(qū)域網(wǎng)聯(lián)合平差［J］．測繪學(xué)報，2007，36（3），245－250．

［10］涂辛菇，許妙忠，朱衛(wèi)東，等．三線陣機(jī)載傳感器ADS40系統(tǒng)誤差補(bǔ)償方法探討［J］．測繪科學(xué)，2014，39（7）：122－125．

［11］劉軍，王冬紅．基于Level 0級產(chǎn)品的ADS40正射影像快速生成［J］．遙感學(xué)報，2007，11（2）：248－251．

［12］趙雙明．機(jī)載三線陣傳感器影像區(qū)域網(wǎng)聯(lián)合平差研究［D］．武漢：武漢大學(xué)，2007．