ADAS導航地圖多源數據高程異常修正算法研究

黃 鶴，陳志鋒，衣鵬軍

(1.北京建筑大學測繪與城市空間信息學院，北京 102616；2.未來城市設計北京市高精尖創新中心，北京102616)

隨著汽車導航技術的不斷發展，自動駕駛技術成為研究熱點,但就現階段而言，自動駕駛處于試驗研究階段，技術上需要可靠性與穩定性的突破，政策上需要相關法律與標準的跟進，甚至基礎設施也需要相應的投入。目前，ADAS(高級駕駛輔助系統)是汽車技術由機械化向智能化轉變的重要條件。在最新的ADAS研究報告中，ADAS的功能方案和具體試驗已經非常成熟。在《中國制造2025》中，也已經明確給出了ADAS相關內容標準和框架，說明目前國家在ADAS方面已經有了較為明確的方向、標準及術語定義。ADAS中最重要的是地圖數據中高程信息的引入，ADAS導航地圖作為ADAS重要的先驗信息，除傳統的平面坐標信息之外，同時為車輛提供道路的曲率、坡度等重要信息。高程作為ADAS數據中一個關鍵要素對ADAS決策和駕駛中的人機交互具有十分重要的輔助作用[1]。

目前ADAS高精度導航地圖數據的采集基本依賴于移動道路測量系統，該系統集成了傳感器集、GNSS、INS系統等，采集方式按照精度的不同主要分為3種，包括基于MMS(GPS/IMU+激光掃描儀，經驗精度0.1～1.0 m)、基于MMS(GPS/IMU或第三方供應商，經驗精度0.5～5.0 m)、基于SRTM3 DEM(柵格分辨率90 m)。其中實采數據采集的是具有一定距離間隔的點(形狀點)的坐標和高程信息[2]。將這些點的信息擴展成彼此獨立的線幾何信息，一定數量的點構成的線幾何就成為ADAS數據中LANE的基本單位LINK，LINK端點區別于形狀點，定義為NODE。顯然，符合實際的LINK之間的高程應該是連續的。但是由于數據采集的環境、采集設備的參數、人員、時間等一系列不可預知因素的存在，以及數據采集完成后內業人員對數據進行的后處理過程中不可避免的數據篩選和處理過程等，這些因素都造成ADAS數據中實際LINK間的節點(NODE點)在不同的LINK上具有不同的高程值。對整個ADAS數據而言，該問題的存在使整個ADAS數據中的道路線具有了高程突變現象。在傳統導航地圖主導的電子導航時代，由于地圖數據中不存在高程信息，因此不存在該問題。但是在ADAS高精度導航地圖領域，高程作為重要的決策和人機交互參考信息而存在，數據中的高程異常問題需進行后處理糾正。鑒于ADAS對地圖信息有著極高的實際符合性要求，高程異常的糾正過程并非簡單的LINK二次“搭接”，而是要在滿足整體合理性的基礎上做到高度的實際符合性，即調整后的數據應該符合實際道路信息。同時對原始數據改動應該限定在一定的閾值之內。

針對上述問題，基于水準網平差的基本思想，探索相應算法，修正ADAS高精度導航地圖中的高程異常，以解決ADAS數據中的高程不連續問題。本文主要對如何一次統一ADAS高精度導航地圖中的高程異常問題中的控制層處理問題進行論述。文中高程異常指LINK間同名NODE點的多值性問題。

由于高程信息涉及國家安全問題，因此本文中所涉及的高程數據均是算法加密后數據。

1 ADAS數據結構及高程異常問題

現實世界的道路是由線幾何表示的，在ADAS數據中線幾何是由各個獨立的LINK連接而成。LINK表示現實道路的形狀，每一條LINK都有一個唯一編號，并有1個起始NODE、1個終點NODE，以及數目不等的具有一定密度間隔(一般為5 m)的形狀點。當幾條LINK相交時，會共用同一個NODE。每一個NODE有一個唯一編號。LINK通過NODE點和形狀點經度、緯度、絕對高程來表達三維特征，如圖1所示。

圖1 ADAS數據組織結構示意圖

在地理信息產業領域，非等精度數據問題由來已久，目前行業內并沒有數據質量評定的統一標準[3]。此外設備不同及測量單元和環境的影響還將會給每段LINK帶來不同的系統誤差。理論上，在一個LINK塊內，數據中包含的系統誤差是穩定的，精度也具有相同的性質。如圖2所示，大量的實采數據已經證明上述結論。以上這些主要因素導致ADAS數據中LINK間高程不連續的問題，即同一區域高程存在差異且道路交叉點處的同一NODE高程存在多值性。由于該系統誤差具有穩定性，且數據具有較好的相對精度[4]，因此LINK內的坡度變化與現實情況具有高度的符合性。

圖2 ADAS數據中的LINK高程趨勢變化

2 解決思路

由于需要處理的道路數據屬于多源、非等精度觀測數據，因此將數據分為5個等級，按照分級布設、逐級控制，先整體、后局部的原則，分級控制，先全國、后分省分區域，如圖3所示。由于高速公路在觀測條件、連續性及數據的完整性方面較其他等級道路具有的優勢，以高速公路作為控制的最高級。考慮ADAS中道路的曲率、坡度等信息是重要的基礎信息，因此在進行數據整體調整的過程中，優先考慮坡度信息，將坡度的變化嚴格控制在一定的閾值之內。ADAS數據中的非實采低精度數據對坡度無要求。與一般測繪意義上的最優估計不同，ADAS數據處理整個過程并非為了提高精度，而是主要保證整體符合性與整體合理性，同時盡量降低對原始數據的改動。

圖3 ADAS數據處理逐級控制

根據逐級控制的思路，首級控制為次級道路提供了必要的控制參考，建立了ADAS數據高程控制框架。對于首級控制借鑒大型水準網平差方法，結合本問題的特點，采用整體最優估計思想處理高速數據。考慮ADAS數據的具體特點，為將ADAS高精度導航地圖中的線幾何抽象為水準網中的水準線路，在數據處理前建立了3個新的概念，即VISCOSITY(量化NODE點與LINK關聯度參數)、EFFECTIVE_NODE、EDGE，如圖4所示。數據預處理過程的首要工作是計算ADAS導航數據中的點—線拓撲關系，基于該拓撲關系計算全部NODE點的黏度參數，基于VISCOSITY參數信息提取NODE點中VISCOSITY參數≥3的NODE點，并定義為EFFECTIVE_NODE，EFFECTIVE_NODE之間的連接關系為EDGE。

圖4 EDGE與EFFECTIVE_NODE的定義

通過對問題的抽象，借鑒水準網平差中的整體最優估計基本思想，綜合本文的實際需求綜合處理ADAS數據中的高程異常問題。將方案基本過程模塊化，主要過程如圖5所示。

圖5 ADAS頂層控制處理流程

2.1 數據預處理

提取作為控制的高等級數據，首先計算NODE點與LINK的完整拓撲關系，基于拓撲關系計算NODE點VISCOSITY參數，作為篩選EFFECTIVE_NODE的依據，EFFECTIVE_NODE篩選完成后，建立EFFECTIVE_NODE之間的全部連接(EDGE)。記錄每條連接及連接內部的LINK集合，按照EDGE建立的方向記錄EDGE的起點和重點NODE編號，同時按照樹形生長方向計算EDGE的高差，高差計算算法如圖6所示，將每個EDGE的第一條LINK作為基準LINK，其后的LINK依次接合到上一LINK的公共NODE點上，同時計算LINK內NODE點的新高程值，依次進行，直至訪問到EFFECTIVE_NODE時結束。完成全部EDGE信息的計算后就將原始的ADAS數據抽象為準水準網的數據結構。

圖6 EDGE高差計算算法

考慮建立EFFECTIVE_NODE與EDGE的過程中，可能會出現附和路線連接，如圖7所示，在記錄EDGE時以EDGE路線的距離作為判斷依據，自動記錄較短EDGE。

圖7 局部附和線路示意圖

2.2 獨立閉合環高效搜索

對于獨立閉合環的搜索，采用基于生成樹-余樹的閉合環搜索算法[5]，該算法能夠穩定地搜索出全部獨立閉合環，但是計算量會隨著搜到的最小獨立閉合環數量的增多而急劇增加，對于網結構不是非常復雜，網內閉合環數目不是十分龐大的對象其計算量是可以接受的。對于ADAS數據，由于形成閉合環的數目十分龐大，因此搜索效率是必須考慮的問題。在生成樹-余樹搜索算法的基礎上，對算法進行優化，盡量減小搜索時間。利用網形信息構建最優樹模型，同時得到余枝信息，然后以余枝為基礎條件，可穩定地搜索出所有最小獨立閉合環[6]。

閉合環數目個數的確定規則如下：所有的閉合環中邊數最少的環是三邊形，對于由n個點、m條獨立觀測邊構成的網(附和路線和支路線在前期數據處理過程中已經剔除)，其必要觀測數為n-1，多余觀測數為n-m+1，因此對于任意網內的獨立閉合環的個數為n-m+1[7]。

基于生成樹-余樹的閉合環搜索算法的基本思路為：從網中某一結點開始，建立樹型結構，余枝數為獨立閉合環個數r。將每條余枝分別加到樹上，即可生成一組閉合環，每個閉合環都至少包含一條不屬于其他環的余枝(邊)，因而這一組閉合環是相互獨立的。但生成的閉合環因樹型結構生成的方法和添加余枝的次序不同而不同，因而得到的閉合環不一定是最小閉合環。

為了保證每條余枝都能生成一個最小環，余枝加到樹上的順序及構成環的策略應該有所考慮。首先嘗試把所有余枝加到樹上，計算出每條余枝生成環的邊數，選出其中邊數最小的環為一個最小環，相應的余枝優先加到樹上，樹上添加余枝后生成的樹稱為當前樹。然后，在其他余枝中分別找出每條余枝兩個端點在當前樹中的最短路徑，計算構成環的邊數，邊數最少(距離最短)的環就是最小環，相應的余枝加到當前樹中。經過有限次循環后即可找到一組r個獨立的最小環。基于該算法的改進思路是將抽象形成的網(連通圖)進行合理的碎化處理，由于在碎化過程中切割是沿著連通圖連接關系進行的，因此在這個過程中避免了數據損失。

2.3 網調整參數的最優估計

ADAS高精度地圖數據在經過抽象之后，形成了以EDGE連接EFFECTIVE_NODE的網絡結構，此時數據的高程信息依然是離散的，相互關聯的LINK之間不連續。此時的最優估計是直接針對EDGE高差的。通過對EDGE高差的整體微調，使整個網內的所有EFFECTIVE_NODE之間的相對高差完全合理，即給定一定數量的已知高程信息，通過不同的路徑推算某個EFFECTIVE_NODE的高程不會出現沖突，即為整體合理性。此處的平差側重點不再為了提高整個網的數據精度，而在于使ADAS一級路網首先滿足整體合理性。這也是后續分配閉合差進行各級數據微調的前提和基礎。

ADAS數據采集過程雖然在一定程度上排除了人為干擾，但是GNSS+INS的采集方式卻不可避免地受到環境影響，如進出隧道附近的數據會明顯產生一定程度的漂移。從采集到的數據所反映的實際來看，在極個別情況下這種誤差會達到十米級。顯然這樣的誤差將給純粹依賴最小二乘的平差帶來十分不利的影響，如何探測該誤差或將該誤差的影響降到最低是必須要考慮的問題。目前對于消除粗差的研究相對成熟[8-9]，對于粗差處理和最優估計理論已有很多成熟的研究[10-14]，已有消除或減弱誤差的方法一般分為兩種思路。一類是通過統計學原理對粗差進行探測定位并加以消除，這方面的研究以文獻[15]的粗差探測法為代表。另一類是通過平衡數據來源的權重來最大限度地降低或減弱粗差對估值的影響，這種方法不對粗差進行定位和消除，因此估值方法選擇尤為重要(如L1范數最小估計、M估計等)。李德仁院士于1984年提出的選權迭代法是該方向一種重要的方法[16]。

由本文討論的問題出發，在獲取已知數據的同時獲得了道路的等級和道路形態信息，通過這些信息可以大致反映觀測值的精度水平，也就是說，本問題在平差計算前一定程度上相當于獲得了觀測值的先驗精度信息。因此，本問題更適合第二類抗粗差方法。

如何將道路形態信息通過一定的數學法則映射成為觀測值的先驗權問題需要進行多次試驗，不斷優化。

為控制調整后的整體網形與實際路網相符合，采用附有限制條件的約束平差，在有條件方程形成的方程組下，加入由一定量已知點所形成的附和路線約束方程作為約束整體解算，從而使解算后的網形盡量貼合實際情況。

關于定權問題，必須指出的是，ADAS的數據采集方式依賴移動道路測量系統，移動道路測量系統獲取的ADAS地圖數據的最小數據單位為點的位置信息，以GNSS方式獲取的數據在單個點的位置上沒有誤差累計，因此，EDGE的長度與EDGE的高差沒有直接聯系。在當前不考慮GNSS采集環境差異的情況下，LINK與EDGE的高差信息均是獨立的，因此建立在EDGE層級上的最優估計確立采用單位權處理。

2.4 數據重建

數據重建過程分為4個部分，分別為閉合差分配、LINK重建、EDGE重建和網重建，各部分之間依次進行。參數估計后獲得的改正數是對EDGE的改正數。已經論證，ADAS的數據采集方式所獲取數據的最小單位為形狀點。由于ADAS數據中的LINK長度不一，為避免在分配改正數時，某一LINK上形狀點的高程改動幅度過大，影響實采的坡度信息，在閉合差分配時采用按長度定權的分配方式。根據式(1)計算同一LINK上各點的改正數，將改正數合理分配到每一個形狀點上，如圖8所示，從而保證坡度信息的準確性，同時將數據調整的幅度控制在一定的閾值之內。

圖8 LINK重建

將各個EDGE上的改正數按照以上規則分配后得到每段LINK的改正參數，對每一段LINK進行數據微調，微調方向基于數據預處理中的EDGE生長方向。各形狀點的微調計算公式如下

vvi=(n-1)·vi

(1)

在完成對LINK數據的重建后，需要以EDGE為單位對EDGE進行重建，目的是將EDGE連接成為連續的線幾何曲線，從而為后續對全部的EDGE賦予絕對高程信息作數據準備。

EDGE重建的過程與求EDGE高差的過程類似，對于所有的EDGE逐條處理，按照EDGE生長方向依次將LINK接合在相鄰LINK的同名NODE點上，在此過程中對LINK內的形狀點的高程作二次校正。

EDGE重建完成后，結合給定的起算數據進行網重建，網重建的已知起算數據為約束平差中具有實際高程值的已知NODE點。此時選取一個起算點，向四周擴展，即可將具有準確相對高程關系的EDGE數據賦值以絕對高程。此時已經完成了對控制層的高程異常處理。

3 試驗及結果分析

數據處理結果中，本文抽取北京地區的數據為例進行試驗結果的介紹。北京地區FC=1(Function Class)總計396 606條數據記錄，經過數據預處理獲取有效EDGE記錄412條，篩選得到的關鍵NODE節點282個，相關LINK總計6874條。基于抽象形成的EDGE總計搜索計算得到閉合環131個，閉合環邊數最大為13。在整體最優化估計處理結果中，EDGE改正數最大為2.156 m，最小為0.000 724 813 9 m，EDGE改正數均方差為0.147 5 m，平均單個形狀點的改正幅度為毫米級。

高差驗證方面，本文隨機抽取了京津冀地區的S10線河北易縣至淶源縣段，該段線路在數據預處理后對應的EDGE編號及直線總計82.533 km，線路總計101.135 km。編號為1490和925的EDGE分別為該線路的上行線和下行線。EDGE信息和程序計算得到的線路高差見表1。

表1 相關EGDE信息表 m

在谷歌地球中標記該線路的端點坐標，如圖9所示。記錄線路和對應大地坐標，計算兩端點的相對大地高差為813.278 m，證明本文方案中的高差計算算法嚴謹可靠。

圖9 線路示意圖

由于大區域范圍數據量龐大，難以直觀展示，因此截取數據中天津北部的處理結果進行展示。經過驗證，該算法可以快速進行數據處理，實現對數據中高程異常的修正，如圖10—圖12所示。

圖10 試驗數據區塊(天津北部)

圖11 處理前數據

圖12 處理后數據

對單個閉合環進行隨機取樣抽檢可以優先檢測整體合理性與實際符合性。通過隨機提取閉合環號，提取了部分閉合環進行單環展示，閉合環號編號為6的閉合環數據處理前的LINK在空間內的展示如圖13所示，處理后效果如圖14所示。

圖13 處理前單個閉合環空間展示

圖14 處理后單個閉合環空間展示

該方法對原始坡度信息的改動是微小的。圖15所示為隨機完整閉合環線路，通過處理前后的剖面圖可以明顯地反映坡度的變化情況，這一點在坡面圖上也可以得到很好的反映。

圖15 處理前后符合度與改動幅度展示

4 結 語

在ADAS高精度導航地圖數據高程異常優化改正運算結果中隨機選取其中任意閉合環進行質量檢查，結果符合預期，證明該算法可以實現對ADAS高精度導航地圖中的高程異常問題的處理，具有整體符合性好、數據改動幅度小、整體合理的優點。通過逐級控制完成控制層的數據處理后，基于各級控制形成的控制網絡，按照具體數據等級的處理要求將非控制數據按照一定的算法規則接合在控制網內，從而實現對ADAS高精度導航地圖的全面高程異常修正。

在下一步的工作中，筆者將對ADAS數據中可能存在的其他問題進行進一步分析，如基于DEM數據附加實采數據約束的擬合方法、道路雙線的約束方法、獨立異常網絡的探測、大型復雜三維網絡的連通圖表達、大型連通圖的閉合環高速搜索算法等。