胡波，李超，黃赟

(1.重慶市勘測院，重慶 400000； 2.重慶市智能感知大數(shù)據(jù)產(chǎn)業(yè)協(xié)同創(chuàng)新中心，重慶 400000)

1 引 言

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

2 圖論建模

2.1 基本理論

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

2.2 控制網(wǎng)建模

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

圖1 路網(wǎng)圖論建模

圖2 控制網(wǎng)圖論模型構建

2.3 圖遍歷算法

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

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

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

2.4 坐標概算

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

圖3 坐標概算流程

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

3 程序設計

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

圖4 觀測數(shù)據(jù)格式

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

(1)圖的構建

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

(2)坐標概算

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

(3)平差計算

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

4 算法驗證

4.1 基本精度驗證

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

圖5 附和導線圖

計算結果對比 表1

4.2 大型工程驗證

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

圖6 坐標差值密度分布

5 結 語

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