基于全球網格的衛星成像區域目標規劃算法

楊紀偉 付偉 韓麗 顏博 岳群彬 張麗霞

(1 中國電子科技集團公司第五十四研究所，石家莊 050081)(2 北京市遙感信息研究所，北京 100192)

隨著全球遙感行業的蓬勃發展，衛星成像已成為戰場監視、國土測量、環境監測、氣象預測等工作必不可少的一種手段。通過成像衛星對地面區域進行觀測、測繪等工作，具有不受空間位置限制、成像范圍廣、單次成像區域大等優點，對于合成孔徑雷達(SAR)衛星等成像衛星，還兼有全天時、全天候、不受天氣影響等特點。當前全球在軌成像衛星數以千計，成像衛星對地面的觀測需求，已逐漸由單星成像轉為多星協同成像[1-2]。對區域目標的觀察，需要對區域目標進行分解，不同的分解方式在一定程度上影響著衛星對區域目標的觀測效率。因此各國研究者針對不同的衛星及其載荷，提出了多種區域目標分解規劃方法。目前主要包括以下幾類：一是基于獨立場景的點目標覆蓋方法，該方法依據獨立單景將區域目標分解化為集合覆蓋問題；二是基于固定寬度的條帶分解方法，該方法依據衛星飛行方向和成像幅寬將區域目標分解為固定寬度的平行條帶；三是基于高斯投影的條帶分解方法，該方法利用高斯投影區域目標從大地坐標系轉換到平面坐標系，在平面坐標系下對目標進行分解再利用高斯反算將其轉換到大地坐標系下；四是基于預定義參考系的單景分解方法，依據定義的全球參考系，該方法將區域目標分解多個獨立的場景[3]。這些方法處理的區域目標面積相對較小，對于經度差較大的區域目標分解誤差較大，另外采用高斯投影的分解方法時要進行多次高斯投影及反向運算，計算量大效率低。針對以上區域目標分解算法的不足，本文提出了一種基于全球網格的區域目標規劃算法，旨在將區域規劃算法反應速度限制在10秒量級，并能適應不同面積的區域目標規劃，滿足小范圍精確觀測、大范圍廣域搜索的需求。

1 基于全球網格的區域目標規劃算法

基于全球網格的區域目標規劃算法通過全球網格預先計算、任務區域分解、可見區域匹配、條帶選取等步驟最終生成多星協同方案,流程如圖1所示。通過貪婪算法，每次選取的條帶都是當前看來最好的選擇，也就是說，不從整體最優加以考慮，算法得到的是某種意義上的局部最優解。流程中涉及到的關鍵技術包括分幅比例尺的選擇、全球數據更新、多星協同策略生成及網格金字塔算法。

1.1 分幅比例尺的選擇

基于全球網格的區域目標規劃算法首先采用軍用分幅標準對全球進行網格劃分，比例尺的選擇既要兼顧精度又要兼顧數據量。本算法選擇的比例尺大小為1∶50 000，在1∶50 000比例尺下，全球約分為112萬個大小約為22 km×17.8 km的網格，如果以衛星最大覆蓋范圍1000 km計算，一天的數據量約為190萬條(光學成像衛星由于受太陽高度角限制，約為90萬條)，更新數據時間受訪問計算能力限制，以20個訪問計算節點計，更新一天數據約需要2～3 min[4]。

1.2 全球數據更新

全球數據更新，需要預先計算衛星在未來特定時段對地面目標的訪問情況，并進行記錄。首先根據衛星的軌道高度、衛星側視能力計算特定時間段(可配置，本算法中取2 min)衛星覆蓋區域，由所求得的衛星覆蓋的區域計算覆蓋的網格，然后通過點目標訪問計算算法計算所有網格在當前時間段內的訪問情況[5]。計算特定時間段衛星覆蓋區域示意如圖2所示。

圖2 衛星覆蓋距離示意圖Fig.2 Scheme diagram of the coverage distance of satellite

圖2中R代表地球半徑，h為衛星軌道高度，θ為衛星最大側擺能力，Φ為衛星覆蓋范圍的球心角，單位為(°)，L為最大覆蓋距離，單位km，由正弦定理有

(1)

由式(1)得

(2)

經簡單運算可得

L=φ·111

(3)

圖2計算了空間位置的可見性，考慮到光學成像衛星對太陽高度角的要求，計算完四角點后，首先計算四角點在當前時間段內的太陽高度角是否滿足要求，如果全部不滿足太陽高度角要求，則不計算當前時間段內衛星對當前區域的可視情況[6]。

通過并行目標訪問計算對所有需要計算的點目標進行可見性分析，并行目標訪問計算架構如圖3所示。

并行計算調度服務器將收到的訪問計算申請分發到訪問計算節點，訪問計算節點計算完成后將結果返回。

訪問計算結果返回后，讀取訪問計算結果，將目標位置、目標編號、衛星代號、訪問時刻、側擺角信息保存。

圖3 并行目標訪問計算架構圖Fig.3 Architecture diagram of parallel target access computing

1.3 多星協同策略

根據區域范圍，計算在當前區域范圍內的所有網格，按照衛星信息、時間段范圍取出所有網格的訪問情況，對所有訪問情況進行分組，得到所有可能的衛星對當前區域的訪問時段，對所有條帶按照訪問開始時間升序排序，按照策略依次選定當前處理條帶的側擺角，生成協同方案采用貪婪算法，之所以選擇貪婪算法作為生成協同方案的算法，是因為貪婪算法選擇條帶更簡單更迅速，能夠以較快的速度生成局部最優的區域協同觀測方案。

選擇條帶側擺角的策略總共有3種：覆蓋面積最大、單次成像最優、加權最優。

覆蓋面積最大考慮的是衛星單次覆蓋面積。即根據當前衛星訪問區域的側擺角范圍，以0.1°為步進，計數不同側擺角下衛星覆蓋的網格數，取衛星覆蓋網格數最多的側擺角作為當前條帶的側擺角。其中，對于已被之前條帶覆蓋過的網格，不再計數，即計數的網格為沒有被覆蓋過的網格。

單次成像最優考慮的是衛星成像的效果。對于光學成像衛星，一般來說，側擺角的絕對值越大，所成圖像質量越差。單次成像最優即優先選擇側擺角絕對值最小的條帶。如某衛星視場角范圍為左右各1°，如果某次訪問，能夠覆蓋區域的側擺角范圍為-10°～+10°，則選擇的條帶為0°；如果某次訪問，能夠覆蓋區域的側擺角范圍為0～10°，則選擇的條帶為1°，因為其中考慮到衛星還有1°的視場角。

加權最優既考慮單次覆蓋面積，又考慮衛星成像效果。加權最優對衛星覆蓋面積進行正加權，對側擺角的絕對值進行負加權。首先計算不同側擺角下衛星的覆蓋面積，記為m，取單位面積的加權為1/m，對于規則四邊形區域，選任意側擺角的概率相同。覆蓋面積m的計算，可以用覆蓋距離L代替[7-9]。計算不同側擺角下覆蓋距離L的示意如圖4所示。

圖4 求某側擺角下衛星覆蓋距離Fig.4 Calculate the satellite coverage distance under a certain roll angle

記衛星視場角為α(半場角)，L單位為(km)，φ′、φ″單位均為(°)。由公式得

(4)

(5)

則覆蓋距離為

L=(φ″-φ′)·111

(6)

在計算加權得分時，同樣需要將覆蓋過的網格排除。如果選擇不同側擺角時加權得分相同，則按照特定規則(覆蓋面積最大或單次成像最優)選定側擺角。

進一步對覆蓋面積最大、單次成像最優、加權最優3種策略進行解釋說明：由于覆蓋面積最大策略每次選擇的條帶都是有效覆蓋面積(排除已經覆蓋過的面積)最大的條帶，該策略更適合于最快覆蓋的需求，可以以較短的時間達到指定的覆蓋率；單次成像最優策略，由于每次選擇的條帶都是成像效果最優的條帶，該策略更適合于總成像時間要求較低，但成像質量要求較高的需求；加權最優策略則是對以上兩種策略的一種中和考慮，同時考慮了成像效果以及總成像時間。此3種策略基本上能夠覆蓋區域觀測時間最快、效果最優等需求。

1.4 網格金字塔

按照固定的比例尺對全球預先分點，計算并記錄所有網格的觀測情況；對于區域規劃任務，首先獲取區域所包含的當前比例尺下的所有網格的訪問情況，對所有網格的訪問情況按照特定規則、采用貪婪算法，生成觀測條帶集合。

按照上述過程進行區域規劃，存在一個準備數據時長和條帶精度的矛盾。如果比例尺小，相應的每個網格的面積小，全球網格數多，提前準備的數據量大，但是條帶精度會高；如果比例尺大，相應的每個網格的面積大，全球網格數少，提前準備的數據量小，但是條帶精度低。為了解決上述矛盾，本文提出一種網格金字塔算法。

對于預先計算網格訪問情況，采用的比例尺大，全球網格數少，對所有網格進行訪問計算并記錄訪問計算結果；在進行區域規劃時，采用的比例尺小，精度高。只有當一個較大網格包含的所有較小網格都被覆蓋，才認為該較大網格被完全覆蓋。以1∶25 000和1∶50 000為例，每個1∶50 000的網格由4個1∶25 000的小網格組成，如圖5所示。

圖5 相鄰比例尺網格關系Fig.5 Relationship of adjacent scale

處理時，只有4個1∶25 000的小網格均被覆蓋，才認為該1∶50 000的網格完全被覆蓋。本文采用的比例尺為計算訪問可能性采用1∶100 000的比例尺，生成條帶采用1∶25 000的比例尺。

2 仿真試驗分析

2.1 仿真條件設定

隨機選擇了3塊矩形區域作為試驗對象，區域大小分別約為100 km×100 km、1000 km×1000 km、2000 km×2000 km；10顆成像衛星，預先計算5天的網格可見性，對區域從小到大分別采用單次成像最優、加權最優、覆蓋面積最大算法進行區域規劃；衛星根數信息、側擺角信息及視場角信息參見表1。

表1 試驗數據表Table 1 Data table of experiment

2.2 仿真結果及分析

試驗1用單次成像最優的算法對約100 km×100 km區域采用3顆衛星進行24 h區域目標規劃，觀測覆蓋率和計算耗時如表2所示。

試驗2用加權最優策略對約1000 km×1000 km區域采用6顆衛星進行72 h區域目標規劃，覆蓋率和計算耗時如表3所示，區域覆蓋效果如圖6所示。

試驗3用覆蓋面積最大策略對約2000 km×2000 km區域采用10顆衛星進行72 h區域目標規劃，區域覆蓋效果如圖7所示，覆蓋率和計算耗時如表4所示。

3次試驗的結果說明：對于小區域(約100 km×100 km)，同等條件下容易達到指定的覆蓋率，本文采用單次成像最優策略(單次成像效果好，但單次覆蓋率相對較小)進行試驗分析，并且記錄了相應條帶信息，覆蓋率為61.50%，計算耗時為8.2 s；對于大區域(約2000 km×2000 km)，同等條件下需要更多的條帶才能達到指定覆蓋率，采用覆蓋面積最大策略(單次成像覆蓋率大，但成像效果相對較差)進行實驗分析，覆蓋率為69.56%，計算耗時為24.5 s，由于條帶過多未記錄條帶具體信息；對于約1000 km×1000 km區域，作為比較試驗中的大小適中區域，采用加權最優策略(同時考慮了成像效果和覆蓋率)進行實驗分析，覆蓋率為64.58%，計算耗時為17 s，由于條帶過多未記錄條帶具體信息。

從3個區域覆蓋性試驗可以看出：該算法對不同衛星數量、不同大小的區域采用不同的規劃策略，計算時間可以達到10秒量級，滿足小范圍快速精確觀測、大范圍廣域快速搜索的工程使用需求。

表2 試驗1數據表Table 2 Data table of experiment 1

表3 試驗2數據表Table 3 Data table of experiment 2

圖6 試驗2效果圖Fig.6 Effect map of experiment 2

圖7 試驗3效果圖Fig.7 Effect map of experiment 3

3 結束語

本文設計了基于全球網格的區域目標規劃算法，能夠實現成像衛星對同一區域的多星協同觀測。在采用貪婪算法的前提下，針對不同大小區域設計單次成像最優、加權最優、覆蓋面積最大3種模式，計算24 h區域觀測情況，反應時間數量級在10秒量級。同時該區域目標規劃算法已應用于某衛星任務規劃系統，規劃出的多星協同規劃方案，能夠滿足觀測可見性要求。但是據試驗觀察，有不低于50%反應時間消耗在網格可見性數據獲取上，基于此，后續將探索使用大并發數據庫存儲網格可見性數據，以進一步提高反應速度。同時，基于貪婪算法的區域規劃算法，生成的條帶集合并非全局最優組合，后續將探索使用遺傳算法對條帶進行組合，以期獲得全局最優組合。