基于軌道約束的空間目標球面網格索引及區域查詢應用

呂 亮，施群山，藍朝楨，陳 宇，劉一萍，梁 靜

(1.信息工程大學 地理空間信息學院，鄭州 450052； 2.鄭州測繪學校 航空攝影測量與遙感教學部，鄭州 450015) (*通信作者電子郵箱lvliangvip@163.com)

基于軌道約束的空間目標球面網格索引及區域查詢應用

呂 亮1*，施群山1，藍朝楨1，陳 宇1，劉一萍1，梁 靜2

(1.信息工程大學 地理空間信息學院，鄭州 450052； 2.鄭州測繪學校 航空攝影測量與遙感教學部，鄭州 450015) (*通信作者電子郵箱lvliangvip@163.com)

針對海量、高速運動的空間目標檢索查詢效率低的問題，提出一種基于軌道約束的空間目標球面網格索引構建方法。該方法利用地球慣性系下空間目標軌道相對穩定的特性，通過維護球面剖分網格內途經的空間目標列表，實現了對高速運動目標的穩定索引。在此基礎上，提出基于目標球面網格索引的區域查詢應用方案，首先，依據一定步長離散查詢時段；然后，計算查詢區域在慣性空間的邊界點坐標并確定交叉網格；其次，提取網格中的空間目標，計算并判斷目標與區域的位置關系；最后，遞歸查詢整個時段，實現空間目標過境查詢分析。仿真實驗中，傳統逐目標查詢方法耗時與目標數量線性正相關而與區域大小無關，單目標平均耗時0.09 ms；與之相比，所提方法用時隨區域面積減小呈線性遞減，區域格網數小于2 750時，時間效率高于對比方法，且能夠維持相當的準確率。實驗結果表明，該方法在實際區域應用中可以有效提升查詢的效率。

空間目標；軌道約束；交叉格網；網格索引；區域查詢

0 引言

近年來，導航定位、資源遙感、海洋氣象等衛星系統以得天獨厚的空間優勢獲取了豐富的地球信息資源，產生了巨大的經濟和社會效益。然而隨著太空探索的持續升溫，人類愈發頻繁的航天活動讓整個空間日益擁擠，數以千萬計的空間碎片威脅著每一個航天器的運行安全。作為空間態勢信息的重要組成，海量、高速運動的空間目標的監管問題成為各國所面臨的共同挑戰[1]。這其中，空間目標索引的優劣將直接影響數據查詢和檢索的速度，一定程度上決定了數據處理的效率。

目前國內外提及空間目標時空索引的文獻相對較少，考慮到空間目標同樣屬于運動目標，可以為其提供參考。從實現原理上，運動目標時空索引主要包含3類：1)R樹及其變形樹[2-4]，基于最小外包矩形建立，可直接對占據一定范圍的空間對象進行索引，然而隨著空間維數的增加，死空間和重疊問題較為嚴重；2)四叉樹及其變形樹[5]，依據分布密度無重疊地將空間遞歸劃分為大小相等的4個象限，可有效索引多維數據，但樹深的差異可能導致空間利用率的急劇下降；3)網格結構及其變形算法[6-7]，將研究區域劃分為固定的網格，其中記錄所包含的空間實體，查詢操作時首先定位網格位置，進而對其中包含的對象進行檢索，但其對線或面對象進行索引時同樣存在冗余問題。

上述索引方法的提出均具有一定的針對性，就前兩類常用方法來說，空間目標數量大、運行速度高，索引的快速更新將使其結構變得高維和復雜，進而大大降低查詢和檢索的效率。考慮到在慣性空間中目標受軌道動力學約束，運行相對穩定并非毫無規律，因此本文建立了基于軌道約束的空間目標球面網格索引，并據此提出區域查詢的具體應用方案。

1 空間目標球面網格索引構建原理

空間目標受軌道動力學約束，以地球為焦點作橢圓運動，其絕對位置雖然隨時間高速變化，但其運行軌道一定時間內在慣性空間保持相對穩定。本文提出的網格索引方法是在慣性空間，將地球的外層空間進行球面網格剖分，計算各空間目標的軌道所經過的網格，并將該目標編號記錄到對應的網格中，實現對高速運動目標的穩定索引，為空間目標的各類查詢打下基礎。需要說明的是，目前球面網格剖分方法很多，包括經緯網格剖分[8]、正多面體網格剖分[9-10]、Voronoi網格剖分[11-12]和球面等分剖分[13]等幾大類，考慮到實用、高效的原則，本文采用球面等間隔經緯網格剖分方法進行索引構建。具體構建步驟如下。

1)在地心慣性系——J2000球坐標系下對地球外層空間進行球面等經緯網格剖分，如圖1所示，球面網格依照赤經、赤緯方向劃分，赤經方向從春分點開始，逆時針為正，順時針為負，實際應用中為了處理的方便，由赤經-180°依次對網格進行編號；赤緯方向從南極開始向北極計算網格編號，每個網格可以用grid[col][row]來表示，對應的赤經赤緯范圍為[αcol,αcol+1,βrow,βrow+1]，其中：

(1)

其中：Δα為網格赤經方向的間隔，Δβ為網格赤緯方向的間隔。

圖1 球面等經緯網格定義

2)依次計算目標所經過的所有網格編號，具體的計算方法是：依照一定的步長預報一個周期內空間目標的位置，計算這些位置所落的空間網格。

依據軌道預報模型計算空間目標在給定時刻J2000坐標系下的空間直角坐標，依照式(2)將坐標換算到對應的天球坐標系下，換算過程中需要注意象限的判斷及分母為0時的處理。

(2)

其中，α的取值范圍是[-π,π]，β的取值范圍是[-π/2,π/2]，空間目標所在網格編號的計算公式為：

(3)

其中，?·」為向下取整符號。

3)每個空間網格中維護一個目標列表，如果某一個空間目標在其預報周期內有點落在該網格中，則將該目標編號記錄在網格的目標列表中。目標列表的形式如下：

grid[col][row]:〈num,ID1,ID2,…,IDn〉

(4)

其中grid[col][row]表示編號為(col,row)的網格，〈num,ID1,ID2,…,IDn〉為經過對應網格的目標列表，num為目標數，ID1,ID2,…,IDn為詳細的目標編號。

4)索引結構更新。由于受到地球扁率、大氣阻尼等攝動因素的影響，空間目標的軌道會發生變化，為此需要對空間目標索引結構進行更新，方法是建立一個空間目標編號Hash表，Hash表的結構如式(5)所示，Hash表記錄了對應的空間目標所經過的網格，索引結構更新時，首先獲取需要更新目標所經過的所有網格編號，然后在所有經過網格中刪除對應的目標編號，最后按照步驟2)和步驟3)重新將該目標插入索引結構，完成更新。

ID:grid1,grid2,…,gridn

(5)

其中：ID表示目標編號；grid1,grid2,…,gridn為該目標所穿過的網格。

2 基于索引的區域查詢應用方案

查詢是目標索引研究的主要目的，查詢的性能是評價索引的重要指標。針對空間目標的查詢應用主要有區域查詢、K最近鄰查詢、聚集查詢、連續查詢和密度查詢等類型[14]。其中，區域查詢應用最為廣泛，可解算空間目標經過某區域的時間或探尋指定的時間段內經過某區域的空間目標，完成空間目標的過境分析預報。

空間目標區域查詢的一般過程，即傳統方法是：在指定的時間范圍內，按照一定步長逐個預報目標的空間位置，通過判斷星下點與區域的關系確定其進入和離開指定區域的時間。SKYMAP Pro[15]是由英國SKYMAP公司開發的一款業界公認的天文仿真分析軟件，采用如上方法根據用戶輸入的空間目標軌道數據完成過境分析，其更新效率將在后文中加以分析。

本文提出了基于球面網格索引的區域查詢應用方案，同時用于檢驗該索引方法的效率。下面給出指定時刻，該區域查詢方案的具體步驟，如圖2所示。

1)查詢時段離散化，要查詢一段時間內指定區域的空間目標過境情況，需要將查詢時間區間按照一定的步長進行離散化，將連續的時間轉變為一系列查詢時間片。

2)區域慣性空間邊界計算，對于給定的區域，計算其在查詢時刻所對應的慣性系下的區域邊界。假設區域范圍的邊界點在大地坐標系下的坐標為(L1,B1),(L2,B2),…,(Ln,Bn)，則首先將其換算到J2000坐標系下的空間直角坐標，然后依照式(2)計算出其對應的J2000地心球坐標系下的坐標(α1,β1),(α2,β2),…,(αn,βn)。

圖2 區域查詢方案流程

3)交叉網格確定，計算查詢區域與空間球面索引網格的相交情況，可以用如下的方法進行計算：

①首先將查詢區域球面網格映射到(α,β)參數坐標系中，變為二維平面網格，如圖3所示。

②求取查詢區域的外包圍矩形，如圖3所示，外包圍矩形的4個角點坐標分別是：(αmin,βmin),(αmax,βmin),(αmax,βmax),(αmin,βmax)，其中：

(6)

圖3 查詢區域外包圍矩形示意圖

④查詢區域跨邊界問題的處理。如果查詢區域跨越邊界，則需要按照邊界將查詢區域切分成多個子查詢區域，分別計算各個子查詢區域與網格的相交情況，圖4是幾種切分示意圖。

4)網格內目標位置計算與判斷，取出相交的網格中的目標編號，在給定的時刻，根據軌道預報模型計算這些目標的星下點坐標，并判斷這些目標的星下點是否在查詢區域內。

5)遞歸查詢，根據時間步長確定下一查詢時刻，按步驟1)到步驟3)循環執行，直至時間超界結束。

3 實驗驗證與分析

為了驗證所提方法的優越性，本文開展了相關實驗，電腦硬件環境為Intel i5 CPU處理器，4 GB內存，NVIDIA NVS 4200M 顯卡(1 GB內存)，操作系統為Windows 7平臺，編程環境為Qt5.4.1。實驗數據主體為STK網站公布的13 864條空間目標TLE雙行根數，利用SGP4/SDP4預報模型進行軌道預報。

圖4 查詢區域切分示意圖

如第1章所述，目前運動目標的時空索引主要包含R樹、四叉樹和網格索引3類方法，在慣性系下若采用前兩種方法進行區域查詢，則在查詢時間段內的每一個離散時刻均需要重新構建索引，眾所周知索引的意義在于通過對象的提前編排來提高檢索的效率，其構建的時長遠大于利用索引進行查詢的時長，如此而言，針對空間目標的區域查詢時長將隨查詢時長線性增長且十分耗時，因而理論分析即可排除前兩種方法應用的可能性，僅僅需要比較傳統方法(見第2章)，即未構建索引直接判斷目標星下點和區域位置關系，與本文所提方法之間的優劣。

從原理上講，影響傳統方法和本文所提方法進行空間目標區域查詢效率的因素包括查詢時長、目標數和查詢區域大小。其中，查詢時長對于兩種方法的影響是一致的，不再討論；由于要逐目標判斷與查詢區域的關系，因此傳統方法的效率主要受限于目標數，而與區域大小幾無關系；本文方法由于提前將所有空間目標的軌道計算工作置于索引構建中，所以在實際的區域查詢時，不需要對所有目標進行遍歷，只需判斷與查詢區域相交的網格中的目標是否滿足條件即可，查詢效率得以提升，因此，本文首先對傳統方法用時與空間目標數之間的關系進行分析實驗，進而針對不同區域大小對所提方法的時間效率開展驗證，最后在固定區域下測試了本文查詢方法的準確性。

3.1 傳統方法與目標數關系分析

傳統方法采用逐目標驗證其星下點位置與區域關系的思路進行區域查詢分析，實驗起止時間為2013- 06- 03T12:00:00至2013- 06- 04T12:00:00，步長為60 s，范圍為經度[50,115]，緯度[25,30]的矩形區域進行查詢。表1列出了不同空間目標數下的分析用時，其中第1列給出了實驗分析中不同的空間目標數；第2列給出了對應數量下采用傳統方法進行查詢所消耗的時間；第3列給出了單個目標平均查詢用時。圖5展示了傳統方法分析用時和空間目標數之間的關系，并繪制了擬合曲線。

從實驗結果可以看出，隨著空間目標數的增加，利用傳統方法進行區域查詢用時所消耗的時間呈線性增長，平均每個目標耗時均穩定在0.09 ms左右，從而印證了傳統方法耗時與空間目標數之間的線性正相關性。

利用傳統方法對目前在軌工作的1 300多個空間目標進行24 h內的過境預報時，需要消耗超過85 ms的時間；如果算上目前能觀測的空間碎片，空間目標超過17 000，這時消耗的時間將達到1 530 ms。可以預見，隨著人類太空活動的加劇和觀測能力的提升，供分析空間目標的數必將不斷增加，采用傳統方法進行查詢的速度顯然無法滿足需求。

表1 傳統方法用時與空間目標數之間的關系

圖5 傳統方法分析用時和空間目標數之間的關系

3.2 時間效率驗證與分析

由前面分析可知，查詢區域的面積不同時，基于空間目標時空索引的區域查詢所消耗的時間也不同，為此本文固定查詢時間，變化查詢區域來測試基于空間目標時空索引的區域查詢所用時間，實驗中起止查詢時間段為2013- 06- 08T15:32:23至2013- 06- 08T15:43:23，步長為60 s。表2列出了查詢區域范圍及用時，圖6展示了兩種方法區域查詢用時和查詢區域所占網格數目的關系。

表2 不同區域范圍查詢用時對比

從實驗結果可知，當查詢區域所占網格數增加時，基于空間目標時空索引的區域查詢所用的時間呈線性增長，而傳統方法則恒定在1 250 ms上下，實驗結果與前文理論分析相符，本文所提方法受查詢面積影響較大，但是當所占網格數小于2 750時，所用的查詢時間仍然小于傳統方法。實際應用當中，查詢區域面積一般遠小于2 750個網格數，此時基于球面網格索引的區域查詢具有很大的優勢。

圖6 區域查詢用時和查詢區域所占網格數的關系

3.3 準確性分析

為了測試所提方法的準確性，本文進一步選取時間段為2013- 06- 08T15:32:23至2013- 06- 08T15:43:23，步長為60 s，范圍為經度[50,115]，緯度[25,30]的矩形區域進行實驗。表3列出了傳統方法和本文方法所查詢的過境空間目標具體數，其中第1列時刻指查詢時離散化的時間片，這里以儒略日的形式給出，第2列給出了方法1在對應時刻所查詢出的過境空間目標數，第3列給出了方法2在對應時刻所查詢出的過境空間目標數，第4列給出了兩種方法所查詢到的過境目標數差值。

表3 過境目標區域查詢數的對比

從實驗結果可以看出，本文方法查詢得到的過境目標數和傳統方法的相同，此外通過逐目標人工比對，兩種方法的查詢目標結果同樣一致，一般可以將傳統方法查詢的結果作為基準值，因此該實驗結果驗證了基于空間目標時空索引的區域查詢方案準確性。

4 結語

本文針對海量、高速空間目標的快速索引問題，通過慣性空間內目標位置的預先計算，構建基于軌道約束的空間目標球面網格索引。在此基礎上，提出相應的空間目標區域查詢應用方案，支持一定時長范圍內的目標的區域過境分析。實驗結果表明傳統的查詢方法耗時與空間目標數線性正相關，因此無法滿足海量空間目標的查詢需求；與其相比，對于一般的區域范圍，本文方法在保證準確率的前提下可以大幅提高時間效率。后續將考慮開展基于空間目標球面網格索引的K近鄰查詢、空間碎片預警等方面的應用研究。

References)

[1] 徐青,姜挺,周楊,等.空間態勢感知信息支持系統的構建[J].測繪科學技術學報,2013,30(4):424-432.(XU Q, JIANG T, ZHOU Y, et al. Construction of space situational awareness information support system [J]. Journal of Geomatics Science and Technology, 2011, 30(4): 424-432.)

[2] GUTTMAN A. R-trees: a dynamic index structure for spatial searching [C]// Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data. New York: ACM, 1984: 47-57.

[3] TAO Y, PAPADIAS D, SUN J. The TPR*-tree: an optimized spatio-temporal access method for predictive queries [C]// Proceedings of the 2003 International Conference on Very Large Data Bases. [S.l.]: VLDB Endowment, 2003: 790-801.

[4] FANG Y, CAO J, WANG J, et al. HTPR*-tree: an efficient index for moving objects to support predictive query and partial history query [C]// Proceedings of the 2011 International Conference on Web-Age Information Management. Berlin: Springer, 2012: 26-39.

[5] FINKEL R A, BENTLEY J L. Quad trees a data structure for retrieval on composite keys [J]. Acta Informatica, 1974, 4(1): 1-9.

[6] MYKLETUN E, NARASIMHA M, TSUDIK G. Authentication and integrity in outsource databases [J]. ACM Transactions on Storage, 2006, 2(2): 107-138.

[7] 李峰,羅磊.基于道路網絡的時空索引方法IMon-tree[J].計算機應用,2012,32(8):2205-2208.(LI F, LUO L. Spatiotemporal index for moving objects in networks: IMon-tree [J]. Journal of Computer Applications, 2012, 32(8): 2205-2208.)

[8] 李德仁,肖志峰,朱欣焰,等.空間信息多級網格的劃分方法及編碼研究[J].測繪學報,2006,35(1):52-56.(LI D R, XIAO Z F, ZHU X Y, et al. Research on grid division and encoding of spatial information multi-grids [J]. Acta Geodaetica et Cartographica Sinica, 2006, 35(1): 52-56.)

[9] 程承旗,吳飛龍,王崢,等.地球空間參考網格系統建設初探[J].北京大學學報(自然科學版),2016,52(6):1041-1044.(CHENG C Q, WU F L, WANG Z, et al. Study on globe spatial grid reference system construction [J]. Acta Scientiarum Naturalium Universitatis Pekinensis, 2016, 52 (6): 1041-1044.)

[10] 童曉沖,賁進,謝金華,等.全球六邊形離散格網的幾何最優化設計與空間度量[J].地球信息科學學報,2015,17(7):774-781.(TONG X C, BEN J, XIE J H, et al. Geometry optimization design for hexagonal discrete global grid system and spatial measurement [J]. Journal of Geo-information Science, 2015, 17(7): 774-781.)

[11] KOLAR J. Representation of geographic terrain surface using global indexing [C]// Proceeding of the 12th International Conference on Geoinformatics-Geospatial Information Research. G?vle: University of G?vle, 2004: 321-328.

[12] MOSTAFAVI A, GOLD C. A global kinetic spatial data structure for a marine simulation [J]. International Journal of Geographic Information Science, 2004, 18(3): 211-227.

[13] GORSKI K M, HIVON E, BANDAY A J, et al. HEALPix: a framework for high-resolution discretization and fast analysis of data distributed on the sphere [J]. Astrophysical Journal, 2005, 622(2): 759-771.

[14] 劉良旭.移動對象數據庫中時空數據管理若干關鍵技術研究[D].上海:東華大學,2008:5-6.(LIU L X. Research on key technologies of spatial-temporal data management in moving object database [D]. Shanghai: Donghua University, 2008: 5-6.)

[15] MARRIOTT C A. SkyMap astronomy software [EB/OL]. [2016- 11- 16]. http://www.skymap.com.

This work is partially supported by the Science and Technology Research Project of Henan Province (172102210020).

LYULiang, born in 1990, Ph. D. candidate. His research interests include digital earth information resources, space situational awareness expression.

SHIQunshan, born in 1985, Ph. D., lecturer. His research interests include photogrammetry and remote sensing.

LANChaozhen, born in 1979, Ph. D., associate professor. His research interests include space photogrammetry.

CHENYu, born in 1990, M. S. candidate. His research interests include oblique image processing.

LIUYiping, born in 1991, M. S. candidate. Her research interests include remote sensing image interpretation.

LIANGJing, born in 1990, M. S., assistant lecturer. Her research interests include digital photogrammetry.

Spacetargetspheregridindexbasedonorbitrestraintandregionqueryapplication

LYU Liang1*, SHI Qunshan1, LAN Chaozhen1, CHEN Yu1, LIU Yiping1, LIANG Jing2

(1.InstituteofSurveyingandMapping,InformationEngineeringUniversity,ZhengzhouHenan450052,China;2.DepartmentofPhotogrammetryandRemoteSensing,ZhengzhouSchoolforSurveyingandMapping,ZhengzhouHenan450015,China)

Since the efficiency of retrieval and query of mass and high-speed space targets remains in a low level, a construction method of sphere grid index to the space targets based on the orbit restraint was proposed. The advantage that the orbit of space target is relatively stable in earth inertial coordinate system was used in the method to achieve the stabilized index to high-speed moving objects by maintaining the list of the space targets that pass through the sphere subdivision grid. On this basis, a region query application scheme was proposed. Firstly, the query time period was dispersed according to a particular step value. Secondly, the boundary coordinates of the query region in the inertial space were calculated and the staggered mesh was confirmed. Then the space targets in the grid were extracted and the spatial relationship between targets and the region was calculated and estimated. Finally, the whole time period was queried recursively and the space targets transit query analysis was accomplished. In the simulation experiment, the consumed time of the traditional method by calculating one by one has a linear positive correlation with the target number, but it has no relevance with the region size. One target costs 0.09 ms on average. By contrast, the time of the proposed method in the paper shows a linear decrease with the decline of area size. When the number of the region grids is less than 2 750, the time efficiency is higher than that of the comparison method. Furthermore, it can maintain a fairly good accuracy. The experimental results show that the proposed method can improve the efficiency of the query in the actual region application effectively.

space target; orbit restraint; staggered mesh; grid index; region query

TP311.11

:A

2017- 01- 06;

:2017- 02- 20。

河南省科技攻關項目(172102210020)。

呂亮(1990—)，男，山東棗莊人，博士研究生，主要研究方向：數字地球信息資源、空間態勢感知信息表達； 施群山(1985—)，男，江蘇鹽城人，講師，博士，主要研究方向：攝影測量與遙感； 藍朝楨(1979—)，男，福建龍巖人，副教授，博士，主要研究方向：航天攝影測量；陳宇(1990—)，男，山西太原人，碩士研究生，主要研究方向：傾斜影像處理； 劉一萍(1991—)，女，山東青州人，碩士研究生，主要研究方向：遙感影像判繪； 梁靜(1990—)，女，河南周口人，助理講師，碩士，主要研究方向：數字攝影測量。

1001- 9081(2017)07- 2095- 05

10.11772/j.issn.1001- 9081.2017.07.2095