基于動態(tài)規(guī)劃的單線陣影像自動分段技術(shù)

楊成敏，胡 堅，黎荊梅

（1.中國科學(xué)院定量遙感信息技術(shù)重點實驗室 北京 100094；2.中國科學(xué)院光電研究院 北京 100094；3.中國科學(xué)院大學(xué) 北京　100049）

基于動態(tài)規(guī)劃的單線陣影像自動分段技術(shù)

楊成敏1，2，3，胡 堅1，2，黎荊梅1，2

（1.中國科學(xué)院定量遙感信息技術(shù)重點實驗室 北京 100094；2.中國科學(xué)院光電研究院 北京 100094；3.中國科學(xué)院大學(xué) 北京100049）

針對搭載有GPS/IMU的航空單線陣影像幾何糾正中的影像分段問題，提出了一種使用了動態(tài)規(guī)劃的思想，利用二次多項式對影像各行POS數(shù)據(jù)的角元素進行擬合，通過多階段搜索迭代使得擬合誤差最小，最終得到最佳分段的方法。實驗表明，該算法可以根據(jù)POS數(shù)據(jù)中的角元素變化趨勢對影像進行自動分段，能有效降低擬合誤差，提高糾正精度。

單線陣影像；動態(tài)規(guī)劃；自動分段；POS數(shù)據(jù)

在使用基于點和直線特征的幾何糾正方法對航空單線陣影像進行糾正時，影像分段是建立平差的基礎(chǔ)，錯誤的分段可能導(dǎo)致外方位元素求解精度不高，甚至無法收斂。對于使用點和直線特征進行航空單線陣影像幾何糾正方法來說，制約其糾正效果的一個重要原因是影像的分段［1-3］。國外學(xué)者Changno Lee使用了均勻分段在中低分辨率的航空單線陣影像中取得了較好的效果［4］。但是這種方法并不適合于高分辨率影像的幾何糾正，并且不能很好的根據(jù)預(yù)知的POS數(shù)據(jù)較好的判斷分段大?。?-6］，國內(nèi)目前還沒有針對幾何糾正的相關(guān)分段方法的研究。因此，研究高分辨率航空單線陣影像幾何糾正中的分段技術(shù)顯得尤為重要。

文中針對預(yù)知影像的POS數(shù)據(jù)，提出了一種基于動態(tài)規(guī)劃，使用二次多項式對POS數(shù)據(jù)的角元素進行擬合，以分段內(nèi)擬合誤差平方和為代價函數(shù)，以影像所有點擬合誤差為目標函數(shù)，通過多階段搜索以最小化目標函數(shù)，最終迭代多次得到最佳分段的方法。該算法能有效的利用POS數(shù)據(jù)中角元素的變化趨勢對影像進行自動分段。

1　基于動態(tài)規(guī)劃的影像自動分段原理

動態(tài)規(guī)劃是運籌學(xué)的一個分支，是求解多段決策過程最優(yōu)化的數(shù)學(xué)方法，其基本思想是將多階段過程轉(zhuǎn)化為一系列的單階段問題，利用各階段之間的關(guān)系，逐個求解，從而得到問題的最優(yōu)解。

傳統(tǒng)的影像分段方法為均勻分段，即每個分段大小一致［4］。這種方法的優(yōu)點是簡單，不需要額外的算法，缺點是不能很好的利用給定的POS數(shù)據(jù)進一步提升幾何糾正精度。本文在研究了已有的基于曲線進行分段的方法基礎(chǔ)上，提出了一種根據(jù)POS數(shù)據(jù)基于動態(tài)規(guī)劃的單線陣影像自動分段方法。

圖1　單線陣影像分段示意圖Fig.1　Sketch map of segmentation of single linear array image

首先假設(shè)一個單線陣影像分為N個影像段，如圖1所示，然后對POS數(shù)據(jù)的角元素進行擬合，則每個影像段內(nèi)擬合的誤差平方和為ei（1≤i≤N），i表示分段號，則影像內(nèi)所有分段的誤差平方和為式（2）。

為使平差效果最理想，需使etotal最小化，即

通過采用動態(tài)規(guī)劃的思想可以求解這個問題。每個分段的誤差平方和ei為代價函數(shù)，為目標函數(shù)。對于第i個分段來說，其分段的大小是由左右兩個邊界決定，即由第i-1和第i+1個分段共同決定。所以，第i個分段的誤差為式i=E（ei-1，ei，ei+1）。且第i分段的誤差僅與第i-1和第i+ 1個分段有關(guān)。于是，式（2）可等價于

則式（3）等價于

因此，求解目標函數(shù)最小化的可以分為多個階段，且每個求解階段與上一階段有聯(lián)系。應(yīng)用動態(tài)規(guī)劃的思想求解可以得到，對于第i個階段Si，有式（6）

其中，S（i-1，ei）為上一個階段的最優(yōu)解，表示第i-1個分段的左邊界和第i-1個分段的右邊界（即第i個分段的左邊界）已經(jīng)確定，且此時第i+1個分段的右邊界固定。

圖2　一個分段示例Fig.2　A example of segmentation

我們來考慮一個簡單的例子。假設(shè)共分為5段，即N=5，每個邊界有3個選擇：左邊，中間，右邊，如圖2所示。那我們需要計算各個階段的最優(yōu)解，如式（7）所示

通過階段S1可以確定第1個分段的右邊界，通過階段S2可以確定第2個分段的右邊界，以此類推，通過階段Si可以確定第i個分段的右邊界，最后一個邊界為影像末尾行。

2　算法求解

2.1代價函數(shù)計算

對于單線陣影像來說，每個分段的誤差平方和ei是通過平差時得到的。根據(jù)先期實驗，在能夠平差的條件下，每個分段大小在5～50之間?？紤]在極限條件下，相鄰兩個分段大小均為5，則根據(jù)式，每個分段的未知數(shù)個數(shù)為15個，假設(shè)有a個控制點，b個直線特征點，則共有未知數(shù)15*2+b，能建立誤差方程共2a+2b個，需滿足15*2+b<2a+2b，即2a+b＞30。對于大小為5的兩個相鄰分段來說，控制點總個數(shù)a一般不超過4個，當(dāng)只有一個直線特征，則b不超過10，則不滿足2a+b＞30。因此在平差中計算代價函數(shù)ei是不可以的?？紤]到最終的目標為對POS數(shù)據(jù)的修正，即通過使用多項式對POS數(shù)據(jù)分別進行擬合，求得最優(yōu)解，因而在根據(jù)預(yù)知的POS數(shù)據(jù)對單線陣影像分段時采用了多項式擬合，并使用擬合后與原數(shù)據(jù)的誤差作為代價函數(shù)ei，從而可以得到單線陣影像分段的邊界。

2.2最大分段數(shù)目的確定

通過坐標轉(zhuǎn)換，可將GPS/IMU數(shù)據(jù)轉(zhuǎn)換為攝影中心的外方位元素。慮到角元素與線元素的數(shù)量級不同，因此基于線元素和基于角元素分開擬合［4］，在經(jīng)過大量實驗分析，同線元素相比，角元素對于影像糾正的效果影像更明顯。因此，本文中選取角元素作為最終的擬合分段的依據(jù)。

根據(jù)提取到同名特征點和同名特征直線后，根據(jù)平差條件：平差方程個數(shù)需大于未知數(shù)個數(shù)，可以求得最大分段數(shù)。

2.3算法流程

將上文中的算法總結(jié)歸納可得如下流程：

1）根據(jù)提取得到的同名點及同名直線個數(shù)計算最大分段數(shù)segCountMax，并根據(jù)搜索窗口大小設(shè)置分段間隔segGap，初始化分段數(shù)segCount；

2）根據(jù)分段數(shù)segCount和影像長度imgLength，平均化分段長度gap（i）=imgLength/segCount，以初始化每一個分段的邊界；

3）設(shè)置迭代次數(shù)iterNum；

4）針對第i個分段內(nèi)的右邊界，在搜索區(qū)間內(nèi)對角元素分別進行二次多項式擬合，計算每一個分段上所有點的擬合誤差平方和，選取最小誤差平方和所在位置為新的右邊界，以此確定每一個分段間隔gap（i）；

5）迭代iterNum次，以使得影像內(nèi)誤差平方和不再變化，達到最??；

6）輸出分段位置。

3　實驗與結(jié)果

為了進一步分析分段的影像，選取了2011年7月貴州安順機場的無人機飛行測試數(shù)據(jù)。實驗中截取了一段830*1 030的線陣CCD原始影像，分辨率為0.5 m，如圖3所示，用于參考的相應(yīng)區(qū)域的正射影像分辨率為0.4 m。分別使用了均勻分段法和基于動態(tài)規(guī)劃的自動分段法進行糾正，其中基于動態(tài)規(guī)劃分段法相關(guān)參數(shù)設(shè)置如表1。使用文中所述的基于動態(tài)規(guī)劃的影像自動分段方法對其進行自動分段。分段數(shù)為24至30，且每個分段數(shù)下迭代12次，分段數(shù)的搜索窗口為7，分段邊界的搜索窗口為5。在每個分段數(shù)下的迭代中，如圖4所示，隨著迭代次數(shù)增多，分段內(nèi)影像點的角元素擬合誤差平方和在逐漸減小，最終達到一個最小值并不再變化，那么此時的分段即為當(dāng)前分段數(shù)N下的最佳分段。將N為24至30的分段數(shù)匯總得到圖5。如圖5所示，在搜索窗口內(nèi)當(dāng)分段數(shù)為25時角元素擬合誤差平方和最小，那么即選取25為最佳分段數(shù)。當(dāng)N=25時迭代穩(wěn)定時的分段即為最佳分段，如圖6所示。分別使用兩種分段方法對影像進行幾何糾正，得到糾正影像局部對比圖如圖7所示。在兩幅影像上分別選取了10對檢查點，提取坐標并計算幾何精度得到表2。同基于均勻分段的幾何糾正方法相比，使用基于動態(tài)規(guī)劃的影像自動分段方法糾正后，檢查點誤差在x方向上從0.91 m（1.82個像素）減少至0.68 m（1.36個像素），在y方向上從0.92 m（1.84個像素）減少至0.71 m（1.42個像素）?？梢钥闯?，文中提出的方法對單線陣影像內(nèi)部幾何畸變校正有很大的改善。

表1　參數(shù)設(shè)置Tab.1　Parameter setting

圖3　原始影像Fig.3　The original single array image

圖4　N=26時分段內(nèi)誤差平方和與迭代次數(shù)的關(guān)系Fig.4　Relation between error sum squares and iterations in a segment which N=26

圖5　影像誤差平方和與分段數(shù)的關(guān)系Fig.5　Relation between error sum squares and numbers of segments

圖6　分段結(jié)果Fig.6　The result of segmentation

表2　幾何糾正精度分析Tab.2　Analysis of geometric rectification accuracy

圖7　幾何糾正結(jié)果Fig.7　Result of geometric rectification

4　結(jié)束語

為了進一步提高影像的糾正精度，本文使用了基于POS數(shù)據(jù)的影像分段技術(shù)。針對POS數(shù)據(jù)的特點，提出了一種能有效改進糾正結(jié)果的影像分段方法。影像分段是外方位元素模型建立以及平差的基礎(chǔ)，錯誤的分段可能導(dǎo)致外方位元素求解精度不高，甚至無法收斂。影像的自動分段需要基于POS數(shù)據(jù)，尤其是3個姿態(tài)角的數(shù)據(jù)變化趨勢進行分析，同時結(jié)合段間平滑問題，確定合理的分段條件，以保證平差處理的有效性。文中提出了一種使用了動態(tài)規(guī)劃的思想，利用二次多項式對影像各行POS數(shù)據(jù)的角元素進行擬合，以分段內(nèi)擬合誤差平方和為代價函數(shù)，以影像所有點擬合誤差為目標函數(shù)，通過多階段搜索以最小化目標函數(shù)，最終迭代得到最佳分段。實驗表明，該算法能有效的根據(jù)POS數(shù)據(jù)中的角元素變化趨勢對影像進行自動分段，在提高自動化作業(yè)的同時，能有效降低分段誤差，提高糾正精度。

［1］李傳榮.無人機遙感載荷綜合驗證系統(tǒng)技術(shù) ［M］.北京：科學(xué)出版社，2014.

［2］Aldrich W S，Kappus M E，Resmini R G，et al.Hydice postflight data processing［C］//Aerospace/Defense Sensing and Controls.International Society for Optics and Photonics，1996：354-363.

［3］張浩，張兵，衛(wèi)征.基于POS的高光譜影像快速幾何糾正［J］.測繪通報，2009（1）：14-17.

［4］Lee C，Theiss H J，Bethel J S，et al.Rigorous mathematical modeling of airborne pushbroom imaging systems［J］.Photogrammetric Engineering and Remote Sensing，2000，66（4）：385-392.

［5］張祖勛，張劍清.數(shù)字攝影測量學(xué)［M］.武漢：武漢大學(xué)出版社，1997.

Automatic image segmentation of single linear array image based on dynamic programming

YANG Cheng-min1，2，3，HU Jian1，2，LI Jing-mei1，2
（1.Key Laboratory of Quantitative Remote Sensing Information Technology，Chinese Academy of Sciences，Beijing 100094，China；2.Academy of Opto-electronics，Chinese Academy of Sciences，Beijing 100094，China；3.University of Chinese Academy of Sciences，Beijing 100049，China）

An automatic image segmentation based on dynamic programming which minimizes the error of fitting through mutiple-step searching by using quadratic polynomials to fit the angle elements of exterior orientation in POS data is presented for geometric rectification of the aerial single linear array image in the platform with GPS/IMU.The result of experiment indicated that algorithm can be used for segmentation of image based on change trend of the angle elements of exterior orientation in POS data，and it is feasible for decreasing error of fitting and improving precision of rectification.

single linear array image；dynamic programming；auto segmentation；POS data

TN29

A

1674－6236（2016）03-0156-04

2015-04-22稿件編號：201504236

中國科學(xué)院光電研究院創(chuàng)新項目（Y40B08A14Y）

楊成敏（1989—），男，山西陽泉人，碩士研究生。研究方向：數(shù)字圖像處理。