基于圖論模型的間接平差計(jì)算

胡波，李超，黃赟

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

1 引 言

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

2 圖論建模

2.1 基本理論

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

2.2 控制網(wǎng)建模

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

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

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

2.3 圖遍歷算法

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

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

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

2.4 坐標(biāo)概算

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

圖3 坐標(biāo)概算流程

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

3 程序設(shè)計(jì)

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

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

程序?qū)崿F(xiàn)的關(guān)鍵步驟包括：①圖的構(gòu)建；②坐標(biāo)概算；③平差計(jì)算。

(1)圖的構(gòu)建

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

(2)坐標(biāo)概算

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

(3)平差計(jì)算

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

4 算法驗(yàn)證

4.1 基本精度驗(yàn)證

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

圖5 附和導(dǎo)線圖

計(jì)算結(jié)果對比 表1

4.2 大型工程驗(yàn)證

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

圖6 坐標(biāo)差值密度分布

5 結(jié) 語

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