改進的最小獨立閉合環剝蝕搜索算法研究

李靖，朱麗強

(1.蘇州高新區測繪事務所有限公司，江蘇蘇州 215129;2.蘇州工業園區測繪有限責任公司，江蘇蘇州 215021)

1 引言

在GPS網的數據處理過程中，基線解算所得到的基線向量確定了GPS網的幾何形狀，并將作為GPS網平差的起算數據［1］。獨立多邊形閉合環閉合差的大小是評價基線解算成果的一個重要指標，它是對整網觀測精度的初步評判，能夠及時發現基線向量間的系統誤差或粗差，從而控制整個控制網的解算質量。部分商用GPS數據處理軟件雖然具有搜索閉合環功能，然而這類軟件中有些閉合環的搜索和計算速度比較慢，而且不能搜索到所有可能的異步環，易產生遺漏［2］。因此，一個有效快速的、易實現的最小獨立閉合環自動化搜索算法在實際工程應用中顯得尤為重要。

目前較常見的閉合環搜索方法主要有:矩陣變換方法［3～5］，該方法基于矩陣理論進行變換，但涉及系數矩陣是否滿秩或條件方程的系數陣系數不一定為±1等限制，需要人工干預構造矩陣;圖論生成樹法［6］，該方法用到了Dijkstra或類似復雜算法，且需要依賴于觀測值文件或網點信息文件;剝蝕法［7］，該方法需計算GPS點位概略平面坐標、方位角、聯測方向數等，但對控制網圖形結果過于理想化，自動化后遇到某些圖形并不能搜索得到正確的閉合環信息。基于以上方法，本文提出了一種基于通用基線數據交換格式的改進剝蝕算法，避免了人工構建系數矩陣或網點文件，減少了中間環節的干預，真正實現了最小獨立閉合環的自動化搜索。

2 算法設計

由于實際工程控制網的網型結構情況較為復雜，因此在最小獨立閉合環的自動化處理過程中需要綜合考慮。本算法以單個點為基礎，在基線信息中逐點構造獨立環，構造完畢即剔除該點及其相關基線。

算法流程如下:

(1)讀取通用數據格式(*.asc)的基線信息，形成點列表與基線列表。

點列表中點號按照縱坐標由大至小重新排列，形成點列表信息。基線列表中根據基線的唯一性形成基線列表信息。

(2)孤點、極條件等點位與基線信息進行處理。

在基線列表中循環判斷網點的出現次數，確定該點是否為孤點或只出現一次，同時在基線列表、點列表中進行無效標記更新信息。

(3)點信息、基線信息的完善計算。

根據有效的點信息，確定該點的有效連接數、有效連接點等信息。根據有效的基線信息，確定每條基線的最終基線連接數、坐標方位角、基線邊長、觀測時間等信息。

(4)點列表中有效點與第一點(縱坐標最大的點)有關的閉合環搜索。

以第一點A為起點，按基線方位角從小到大進行搜索，依次確定第二點為B，以第二點B為起點，確定與基線BA的順時針夾角最大的基線BC，以C為第三點，如果C與A之間存在基線CA，則需要判斷在以A為起點的閉合環中CA邊是否已經使用了兩次。

當CA邊使用次數沒有超過兩次時，則以AB為起點的三邊獨立閉合環ABCA搜索完成。在保存入庫時需要判斷是否與現在有的以A為起點的閉合環存在重復，當滿足不重復時搜索結果可保存，否則放棄ABC三點構成的閉合環，重新從A點開始再進行搜索。當CA邊使用超過了兩次時，視CA邊為無效，即認為C點與A點之間不存在基線(實際為存在)，繼續按上述查找第3點C一樣查找與基線CB的順時針夾角最大的基線(基線CD)的第4點D，然后再按上述判斷C點是否有效的方法進行判斷D點是否有效，從而判斷是否需要查找第5個點E，進行循環查找并判斷。第一點A的搜索流程見圖1。在生成獨立閉合環的過程中，可以記錄環點名及基線編號，以便同步對獨立閉合環的質量進行檢核。

圖1 A點搜索流程示意圖

原剝蝕法中提到的，如與第一點(x坐標最大)的扣除支點后的聯測方向數為Ni，則與第一點有關的獨立閉合環個數一定為Ni－1，但實際工程中控制網的網型結果往往存有多樣性，實際的獨立閉合環數最多只能是Ni－1，有很多情況下達不到Ni－1個，因此原程序設計時設定為非要找到Ni－1個，結果會出現異常情況。如圖2就是為例外，E01為x坐標最大的點，與點E01有關的聯測方向數為6個，但很明顯與E01有關的獨立閉合環個數只有4個，而非5個。

原剝蝕法中是以C為第3點后，直接尋找CA之間是否有基線存在，而未考慮到基線CA是否已經被使用了兩次或是否存在重復，因此在某些圖形下會導致不能得到正確的搜索結果，在圖2中按照原設計思想基線E01E05將會被使用4次，從而也會得出與E01有關的閉合環個數是5個。

圖2 某GPS控制網網型圖

(5)標記搜索完畢的點和與之相關的基線。

由于直接刪除搜索完畢點的基線信息過程較繁雜，特別是對大型控制網而言。因此，可采用布爾值在點列表中對已搜索完畢點進行無效標記，這樣可大大提高效率。重復第(4)步搜索，直到搜索完全部獨立閉合環為止。

3 理論分析

由測量平差的知識可知，同屬于獨立閉合環的環與環之間不存在相關性，環與環之間類似于獨立觀測值，即不存在由閉合環A和閉合環B構成閉合環C的情況。對于剝蝕法而言，第一，由于在搜索完包含某一點的獨立閉合環后，涉及該點的基線將全部視為無效，因此在后續的搜索中將不會包含與該點相關的基線邊，前后搜索出的環之間也將不會存在關聯性。第二，如果包含點A的所有搜索出的閉合環中兩兩不存在相關性，那么所有搜索出的閉合環也將全部獨立。

對于一個有M個測量點，N條基線的GPS控制網，最小獨立閉合環的個數為N－M+1。以測量點A為例，首先，包含該點A的獨立閉合環個數最大可能為該點連接數NA－1，此處連接數NA為去除比點A縱坐標(X)大的點后的剩余有效連接數，該限制條件確保了獨立閉合環在個數上的完整性。其次，在本次搜索中對包含點A的連接基線的出現次數也做出了限制，不能超過兩次，避免了環1、環2和環3中都出現同一條基線的不獨立情況。最后，是對搜索出的最小獨立閉合環的重復性進行判斷，在一些比較特殊的網圖中，不排除這種重復情況的出現，因此需要在保存結果前進行重復判斷。綜上所述，可以穩定的求出各種復雜控制網圖形中包含的最小獨立閉合環。

4 工程算例

根據上述方法編寫了基于通用基線數據交換格式的基線解算質量檢核軟件，并運用工程實例進行了驗證。圖2為某GPS工程控制網，最小獨立閉合環搜索結果見表1所示。

最小獨立閉合環搜索結果 表1

圖3 文獻6中網型圖

圖3為參考文獻［6］中涉及的分析網型圖，運用本文提出的改進算法搜索到閉合環結果與該文獻中涉及的3種搜索方法結果進行比較，如表2所示。

本文算法與文獻［6］中涉及算法的搜索結果比較 表2

由表2可以發現，本文算法可以搜索出的最小獨立環個數等于應有環個數，搜索結果完整，可靠。

同時，在最小獨立閉合環搜索完成后，利用環點信息也可以對重復基線、同步環和異步環的處理質量進行檢核并生成報告。

5 結語

GPS觀測獲得的是控制點之間的基線向量值，由于誤差的存在，基線構成閉合環的閉合差并不為零。為了在后續平差工作中保證參與平差的基線不存在粗差并滿足相應的限差要求，要對基線構成的重復邊和獨立環進行檢驗。同步環閉合差只能反應軟件模型誤差和實際觀測條件，不能反應系統誤差和人為粗差，而異步環閉合差能反映出不同時段中的星歷誤差、電離層延遲、對流層折射和儀器誤差等因素的綜合影響［7］，因此同步環與異步環檢核是同等的重要。本文通過對原剝蝕算法的優化設計，提高了構環的準確性，算法簡單，自動化程度高，并且基于通用基線數據交換文件，同步搜索出重復基線與最小獨立閉合環，計算出閉合差，在實際工作中可以顯著提高工作效率。

［1］李征航，黃勁松.GPS測量與數據處理［M］.武漢:武漢大學出版社，2005.

［2］徐昌榮，葛山運.基于Delaunay三角網的GPS控制網同步環和異步環自動搜索算法研究［J］.大地測量與地球動力學，2011，31(1):55 ～58.

［3］趙一晗，伍吉倉.控制網閉合環搜索算法的探討［J］.鐵道勘察，2006(3):12～14.

［4］李光炎，王解先.閉合環搜索方法的探討［J］.工程勘察，2004(6):52～53.

［5］游為，范東明，付淑娟.最短獨立閉合環與附合路線的快速搜索方法［J］.測繪科學，2009，34(4):139～140.

［6］鄒進貴，馮晨.控制網最小獨立閉合環搜索算法研究［J］.地理空間信息，2008，6(6):97～99.

［7］劉根友.剝蝕法計算GPS觀測網獨立環閉合差［J］.測繪工程，2001，10(1):33 ～36.

［8］朱廣軼，賈瑞英.GPS測量數據處理的應用研究［J］.沈陽大學學報，2003，15(2):54 ～56.