基于圖論模型的間接平差計算

胡波，李超，黃赟

(1.重慶市勘測院，重慶 400000； 2.重慶市智能感知大數據產業協同創新中心，重慶 400000)

1 引 言

控制網測量數據處理工作的一般化流程是先進行坐標概算，再進行平差計算。通過坐標概算可獲得較為準確的近似坐標，為測量平差計算提供基礎[1～4]。現有的坐標概算設計以單測站重復迭代處理為主，較少考慮測站間的關聯性和順序性。圖論是一種對數據進行關聯建模、分析及挖掘的有效方法，在電網、交通等相關領域獲得了廣泛應用[5～7]。本文根據測量數據觀測的特點，給出了控制網有向圖的建模方法，基于廣度優先算法進行坐標概算，并利用Python腳本進行算法實現。

2 圖論建模

2.1 基本理論

圖G可以表示為一個二元組(V，E)的集合，其中V是圖的頂點集合，E是圖的邊集合。常用v(E)表示G的頂點集，e(E)表示G的邊集，e(u，v)為圖中的一條邊，w(u，v)為該邊的權值。其中e考慮其方向性時，為有向圖；無方向特性時，為無向圖。根據頂點和邊在現實世界中的不同映射，分別賦予不同權值，可實現對現實世界的動態網絡模擬與分析。如設定道路網絡的交叉口為圖的頂點、道路為圖的邊，道路長度為邊的權值，則可以將道路抽象為有向圖，從而開展實時動態導航與歷史路徑回溯[8]，如圖1所示。

2.2 控制網建模

測量控制網由控制點和觀測值構成，參照圖論的建模方法，將控制點定義為頂點，當控制點間存在觀測值(如距離、角度、高差等)時構建連接邊，邊的權屬性以觀測值確定，考慮到實際控制網觀測過程中存在對向觀測，將控制網構建為有向圖。一個完整的平面控制網圖模型構建過程如圖2所示，其中A，B為測站觀測點，1～4號為其他測點，A站共觀測了1，2，3，B點，構建A站的連接邊，B站觀測了A，1，2，3，4，構建B站的B連接，A，B站存在對向觀測，構建雙向連接邊。

圖1 路網圖論建模

圖2 控制網圖論模型構建

2.3 圖遍歷算法

廣度優先搜索算法是一種常用的圖論遍歷算法，選取圖中的某個點作為初始節點，遍歷該節點的所有鄰接節點，判定目標節點是否在鄰接節點中，若沒有，再對鄰接節點進行重復上述操作，直至發現目標節點為止。

深度優先搜索算法是另一種常用的圖論遍歷算法，同理選取圖中的某個點作為初始節點，利用規則生成排序后的首層鄰接節點，選取首個鄰接節點進行判斷是否為目標節點，不是則對該節點構建新的規則排序后的鄰接點層，循環上述操作直至發現目標節點，當遍歷至最底層都未發現目標節點時，則返回上一層鄰接點對后續節點進行重復遍歷搜索。

從上述兩種常見的搜索算法可以看出，確定初始節點是關鍵環節。在控制網圖模型中，也就是基于既有已知條件確定坐標概算的起算點，常見的起算點包括：①基于已知定向邊的起算點，如圖2中的A，B均為已知點時，可任選一點作為初始節點；②基于后方交會觀測方法確定的起算點，將交會得到的測站點作為初始節點；③基于測站已知點的起算點，如水準網、GNSS控制網中的任一測站已知點可選為初始節點。

2.4 坐標概算

在構建控制網的圖論模型，確定起算初始節點后，根據控制網網型的差異，分別采取不同的遍歷算法進行坐標概算。如導線網采用深度優先搜索算法，確定導線起點到終點間的最短路徑，按照最短路徑上的節點順序進行坐標推算；平面網采用廣度優先搜索算法，以初始節點開始，分層進行坐標推算。以平面網為例，坐標概算的流程如圖3所示：

圖3 坐標概算流程

根據廣度優先算法確定從初始節點開始進行的測點坐標概算的順序，按層級構建鄰接測點，當前測點存在測站觀測記錄時，進行當前測站的坐標概算，根據觀測條件分別采用極坐標、三角高程、幾何水準方法進行，利用概算得到成果循環進行下一測點的坐標概算。該算法一次遍歷所有測點，得到的概算成果基于最短路徑進行，可提高坐標概算成果的精度。進行單測站坐標概算時，如果測站和測點間的觀測值缺失，可根據有向圖采用對向觀測值進行補齊，實現一次遍歷概算。

3 程序設計

本文采用Python腳本語言實現控制網坐標概算及間接平差。Python是一種動態的、面向對象的腳本語言，具有一套標準庫，同時可以利用第三組件庫完成各種復雜計算任務，目前被廣泛應用數據挖掘、機器學習、科學計算、深度學習等任務中。本文利用igraph圖論分析庫進行圖模型的創建，利用numpy，pandas庫進行矩陣運算實現最小二乘法間接平差。以清華三維為例，觀測數據標準格式如圖4所示，第一部分是起算數據，第二部分是觀測數據。

圖4 觀測數據格式

程序實現的關鍵步驟包括：①圖的構建；②坐標概算；③平差計算。

(1)圖的構建

首先對觀測數據文件進行讀取，形成測站觀測列表，測點列表，再根據測站列表構建有向圖模型G(V，E)。

(2)坐標概算

根據算法流程設計，確定控制網坐標概算的起點，如平面控制網的起算條件是兩個相鄰已知點或一個已知點和初始方位角，再利用廣度優先搜索算法進行遍歷，該過程調用igraph庫的bfsiter函數實現。坐標概算過程中某個測點不存在測距觀測值時，可以利用對向觀測值進行計算，基于圖論模型可以實現對向觀測數據的快速存取。

(3)平差計算

首先是根據測站觀測記錄建立觀測方程，確定矩陣B，L，P，V，再根據觀測矩陣進行迭代最小二乘間接平差計算。

4 算法驗證

4.1 基本精度驗證

以附和一級導線(如圖5所示)為例，進行算法基本精度驗證。該導線總長為 790 m，包括4個監測點，利用本文的程序進行坐標概算和迭代平差計算，以清華三維平差計算結果為真值，計算對比結果如表1所示。算例以IJ15X為起算點，從表1可知，附和導線端點PJ53的概算坐標差值最大，X方向達到 -8.6 mm，Y方向為 1 mm，與導線坐標概算的規律一致，經過迭代間接平差后，所有導線點坐標差值均小于1個mm，平差計算結果與清華三維精度相當。

圖5 附和導線圖

計算結果對比 表1

4.2 大型工程驗證

以重慶市璧山片區大型一級導線控制網為例，進行算法的可靠性和穩定性驗證。該項目在平面四等GPS控制點聯測導線網，共布設一級平面導線點185個，總長度 72.3 km。清華三維平差結果為導線相鄰點的相對點位中誤差最大為 19.1 mm，最弱點點位中誤差為 43.5 mm。本算法跟清華山維平差結果對比，平面差值的分布如圖6所示，其中160個點平面差值小于10個mm，占比達到86.5%，保持了較好的一致性，點位的最大平面差值為 30.8 mm。部分點位平面差值較大，受到迭代過程中平差定權策略影響，這個也是本算法后期優化研究的方向。

圖6 坐標差值密度分布

5 結 語

采用圖論模型進行控制網的坐標概算，利用廣度優先遍歷算法可一次準確推導所有測點的近似坐標，并利用Python腳本進行平差算法實現，通過在具體工程中進行實踐驗證表明，該方法具有極好的穩定性和可靠性，可用于測量平差數據處理工作，Python實現的平差算法可進一步應用于海量測量數據挖掘與應用中，實現測量計算模型的服務化。