王東波，趙 寧，黃 鶴，張會彬

高精度導航地圖道路線形參數估計方法

王東波1，趙 寧1，黃 鶴2，張會彬3

（1. 星球地圖出版社，北京 100088；2. 北京建筑大學 測繪與城市空間信息學院，北京 102616；3. 32017部隊 拉薩 850000）

針對高精度導航中傳統(tǒng)的道路車道線模型在道路曲率估計中很難實現(xiàn)，且相關曲線擬合計算量較大的問題，提出1種基于全球衛(wèi)星導航系統(tǒng)（GNSS）數據計算道路曲率的“迭代圓擬合”曲率估計算法：在數據點附近增加一定數量的相鄰點，并對選取的數據點進行擬合，直到達到最小擬合誤差，從而得到道路邊線的擬合曲線；然后以中心角大小為參數對擬合得到的曲線段進行識別分類；最后對識別得到的曲線進行曲率估算，且將得到的估算值與真實值對比進行精度驗證。結果表明，該算法所提取的道路邊線具有較高的準確性，且能保證邊界點精度。

道路邊線；曲線擬合；迭代圓擬合；曲線識別；精度驗證

0 引言

未來的無人駕駛汽車能夠在道路上安全行駛，需要依靠高精度的導航電子地圖的參與，其中車道級別的高精度導航地圖數據庫尤其重要。車道級別的要素信息需要獲取的前期數據包括道路形狀[1]，車道的曲率、坡度、航向、高程以及側傾等主要數據。道路要素數據中對無人駕駛汽車的路徑規(guī)劃和引導起到關鍵作用的當屬道路曲率[2]，因為所有的道路施工方案不可能完全依照設計方案來執(zhí)行，因地制宜的現(xiàn)象導致道路的真實曲率會發(fā)生很多偏差，這就給高精度導航地圖數據的道路要素參數入庫時帶來困難。需要更高精度的無人駕駛汽車對車道級別的地圖數據要求更高。無人駕駛汽車在行駛時需要獲取前方道路的轉彎趨勢和方向，以提前調整變換車道和速度，就必須在地圖數據庫中錄入精確的道路曲率，以保證車輛安全行駛[3-5]。因此，目前應用廣泛的導航電子地圖在定位檢測精度和地圖要素信息細致程度方面均不能滿足未來無人駕駛汽車發(fā)展的需求。

針對傳統(tǒng)的道路車道線模型在曲率估計中很難實現(xiàn)，且對車道線模型直接進行相關曲線擬合帶來的計算量又很大的問題，本文提出1種基于全球衛(wèi)星導航系統(tǒng)（global navigation satellite system, GNSS）數據估算道路曲率的“迭代圓擬合”算法。該算法主要是利用直線擬合的結果來定性估計車道線曲率的正負，以此可確定前方道路的彎曲方向，即道路的拐彎趨向。利用該方法對道路曲率進行估計時，首先需要采集道路邊線的GNSS數據（沿著車道邊線等距離采集）；然后根據視場的遠近將實驗區(qū)域的道路圖像劃分成為近視區(qū)和遠視區(qū)2個區(qū)域；最后利用直線模型擬合上述2個區(qū)域的車道線，以分別獲得2個場區(qū)的車道線中點。將獲得的2個中點進行連線以計算其斜率，此斜率可近似描述實驗道路的曲率，最終實現(xiàn)對道路曲率的相對定量估計。

1 迭代圓擬合算法

本文中所選的曲線段[6]是具有單一半徑的最小單位，曲線段的半徑為（曲率為-1，而切線段的半徑為無窮大（曲率為零））。水平曲線由曲線段和曲線點（PC）及切線點（PT）描繪的切線段組成，如圖1（a）所示。對于更復雜的水平曲線，則存在相鄰的曲線段或由內切線段和分開的曲線段組成，例如反曲線，如圖1（b）所示。本研究的目的是準確識別曲線和切線段，將相應線段可靠地聚類成不同的水平曲線類型，并沿著確定的曲線測量相應的半徑。

圖1 由PC和PT繪制的水平曲線圖解

本文提出1種迭代的圓形擬合算法[7-8]來獲得初始的圓形擬合結果。該算法不是選擇固定數量的相鄰點進行擬合，而是嘗試增加一定數量的相鄰點，直到達到最小擬合誤差；而產生最小擬合誤差的數據將與這組GNSS點（即L）相關聯(lián)。擬合誤差是通過實際GNSS點與近似圓相比的適應度來度量的。如圖2所示，對誤差曲線進行單獨監(jiān)測和記錄，直到在所有嘗試的迭代中達到全局最小值。如果當前的1組GNSS點（即L）已經選擇了相鄰點的數量，則下1個圓形擬合將跳過當前點組重新開始。這樣，通過迭代為每1組GNSS點（即曲線段）選擇優(yōu)化的GNSS點個數。圖2中Ite為Iteration（迭代次數）的縮寫，Error表示迭代的錯誤率。

圖2 迭代圓擬合算法原理

圓形擬合方法定義了用于圓形擬合的采樣點與近似圓之間的最小平方誤差的最小化問題[9]。具體算法如下：

(2)

式中、、分別是誤差函數的系數和常數項。

處理式（4）得

是點集中的點的個數，其中令

圖3為從迭代圓擬合導出的合成分段的圖示。圖3中使用的替代顏色是突出描述。單個半徑測量與同1段內的所有GNSS點相關聯(lián)。在隨后的步驟中將確定劃定的線段是否彎曲或相切。

圖3 細分割的1個小路段

2 曲線識別

GNSS軌跡數據由某地圖公司自動導航研究中心開發(fā)的傳感車輛采集。圖4為采集車輛，圖5為所收集的GNSS軌跡數據的示例。在本文中，原始的GNSS軌跡數據以5 Hz的頻率以60 km/h的行駛速度獲取。由于數據通過移動平臺收集，因此許多因素將影響原始GNSS軌跡數據的準確性，例如，精度衰減因子(dilution of precision, DOP）、暫時的衛(wèi)星丟失和有限的停留時間等[10]。因此，原始的GNSS軌跡數據需要通過差分調整和三角測量進行后處理，使用連續(xù)運行參考站（continuously operating reference stations, CORS）采集基站數據，以減少這些不利因素對精度的影響。雖然慣性導航系統(tǒng)（inertial navigation system, INS）數據在所提出的方法中不是必需的，但它可以用來補償在衛(wèi)星不可見的位置處GNSS數據的丟失，例如在隧道里。

圖4 數據采集車

圖5 GNSS軌跡數據樣本

曲線識別的目的是根據上1步得出的劃分線段的空間分布和鄰接關系，自動識別水平曲線和相應的曲線類型[11]。

式中：為以弧度表示的第n段的中心角；Rn為由第n段的迭代圓形擬合計算的半徑；Sn為第n段的弧長；m為包含在第n段中的GNSS點（即間隔）的數量；vi為GNSS在第i個點獲取的瞬時車速；f為GNSS采集頻率。圖6中RC、RT分別表示C段和T段曲線的曲率半徑，SC和ST分別表示其弧長，ΔC和ΔT分別表示其中心角。

圖7 實驗數據采集路段

圖8 校準數據集中心角的分布

曲線分類：經過驗證的曲線和切線段根據其鄰接模式被分類為不同的曲線類型[14]。圖9為不同曲線類型的典型模式。無論曲線類型如何，始終存在進入和離開中心曲線段（即在圖9中橫軸上投影曲率值為0所對應的曲線部分）的前后切線段。因此，中心曲線段（即圖9中橫軸投影曲率值不為0部分）的圖案確定曲線類型：①非曲線（直線），供連續(xù)的切線段；②簡單的曲線，呈現(xiàn)單個曲線段；③復合曲線，提供2個曲線方向相同的曲線段；④反向曲線，提供2個曲線方向相反的曲線段；⑤螺旋曲線，提供3個具有相同曲線方向和對稱曲率測量的曲線段。

圖9 不同曲線類型的段相鄰模式的圖示

曲線識別模擬實驗的作用是驗證本文提出的算法在各類型曲線識別效果和成功率，對于算法在道路真實數據的擬合精度方面還須進行實驗驗證。本文在實驗路段利用GNSS實時動態(tài)載波相位差分(real time kinematic,RTK），以1 m間隔沿道路邊線進行數據采集，將采集得到的坐標數據利用本文提出的算法進行擬合計算，然后將處理后的數據進行精度對比。為了更直觀地通過數據和圖像形式表達驗證過程，現(xiàn)將本文所提出的方法以C#開發(fā)語言為工具將核心算法集成為1個通用的驗證器。

在分段驗證過程中選擇2段道路數據進行逐點對比，如圖10和圖11所示，程序中設置的GNSS-RTK數據為“真值（圖中放大圓圈中的左側曲線）”，而采集車采集的數據設置為“產品（圖中放大圓圈中的右側曲線）”，程序自動讀取之后計算出驗證數據和圖像數據。

圖10 XOY平面投影

圖11 XOY平面投影內插點

從圖10中可以看出，道路邊線的2種數據在該系統(tǒng)中的走勢是完全一致的，而且契合度非常高，即使在比例尺很大的情況下也只能觀察到細小的分離。圖11中顯示的是道路邊線的“邊線+節(jié)點”形式對比圖，在顯示比例為1∶10的情況下能夠明顯看到2種數據擬合的曲線點幾乎在同一位置。圖12中的坐標縱軸的單位為m，橫軸為驗證對比點號。從圖12中可以明顯看出，選取參加驗證的數據點的估計點位誤差平均為0.004 m（圖表中加粗橫線），該精度已經遠高于高精度電子地圖的需求精度，完全達到導航電子地圖車道級精度要求。

圖12 數據點坐標差對比

3 實驗與結果分析

由于從現(xiàn)實世界中準備具有所有類型的曲線（尤其是復雜曲線）的綜合數據集是比較困難的，因此通過插入具有已知幾何公式的合成路段來順序創(chuàng)建全面的合成數據集；然后合成數據被采樣到離散的合成GNSS軌跡。為了與實際情況保持一致，根據現(xiàn)實的情況，對綜合數據集曲線的尺度進行了標注，然后根據5 Hz的GNSS采集頻率和60 km/h的默認驅動速度對GNSS軌跡進行離散化處理。為了測試所提方法的魯棒性，在合成數據中模擬了幾種從實際GNSS軌道觀測到的GNSS干擾，包括隨機GNSS誤差和GNSS缺失點，這些干擾可以在GNSS信號中斷時保持軌跡的連續(xù)性。模擬測試總共生成337條曲線，然后通過檢測性能和分類性能評估模擬測試的準確性。

對于檢測性能測試，使用1類誤差（未檢測到現(xiàn)有曲線）和2類誤差（將直線部分錯誤識別為曲線）。當地面實況中的曲線完全錯過或者檢測到的曲線段重疊不到相應地面實況的75%時，將會報告1類錯誤；而當將地面實際的曲線段檢測為直線段過程完成時，報告2類誤差。最后的測試結果顯示，只有38條曲線被檢測為1類誤差和27條曲線被檢測為2類誤差，達到了90.1%的正確檢出率。還應該注意的是，在38個1類誤差中，只有10條曲線完全錯過了，而其余的28條曲線仍然被所提出的方法部分檢測到。

表1顯示了不同類型的混淆矩陣結果。從混合矩陣的對角單元可以看出，所提出的方法在區(qū)分4種曲線類型方面表現(xiàn)出總體良好的性能?？傮w而言，所提出的方法正確地分類了87.3%的檢測曲線。即使對于具有挑戰(zhàn)性的螺旋曲線，所提出的方法也能達到63.3%的正確分類率。然而，由于道路曲線與其對應的螺旋之間的錯誤描繪，36.7%的螺旋曲線被錯誤地歸類為簡單曲線或復合曲線。

表1 用于曲線分類測試的混淆矩陣

表2 曲率評估成果

4 結束語

本文提出的迭代圓擬合算法無論是在離散點均勻采集還是非均勻采集的情況下都具有良好的擬合效果，其精度并不低于目前在圓曲線擬合方法中普遍采用的最小二乘法，證明了該擬合方法的正確性與可行性。通過對該算法擬合估算的道路曲線曲率數據進行精度驗證，發(fā)現(xiàn)道路邊線曲率的準確性較高，且保證了邊界點精度，算法整體完成較好，達到了在保證精度的同時減少數據量、提高運算效率的預期目標。

[1]JIA L, LUO J, LI S. Road curvature estimation based on linear lane model[J]. Journal of Jiangsu University, 2012, 33(4):373-378.

[2]BYUNG-HYUN L, JONG-HWA S, JUN-HYUCK I, et al. GNSS/DR error estimation for autonomous vehicle localization[J]. Sensors, 2015, 15(8): 20779-20798.

[3]GONZáLEZ D, PéREZ J, LATTARULO R, et al. Continuous curvature planning with obstacle avoidance capabilities in urban scenarios[C]//The Institute of Electrical and Electronic Engineers(IEEE). Proceedings of the 17th International IEEE Conference on Intelligent Transportation Systems (ITSC).Qingdao, China: IEEE, 2014:1430-1435.

[4]UPADHYAY S , RATNOO A . Continuous-curvature path planning with obstacle avoidance using four parameter logistic curves[J]. IEEE Robotics and Automation Letters, 2016, 1(2): 609-616.

[5] 張莉婷. 基于出租車GNSS軌跡的導航道路數據更新[D]. 昆明: 昆明理工大學, 2014.

[6] HONG C, KIM B W. Performance improvement of collision warning system on curved road based on intervehicle communication[J]. Mathematical Problems in Engineering, 2015, 2015(3): 1-7.

[7] 潘桂新, 鄧德標. 圓曲線擬合方法及數據采集分析[J]. 城市勘測, 2014(5): 143-145.

[8] 陳明晶, 方源敏, 馬波, 等. 一種迭代法的圓曲線擬合方法[J]. 測繪科學, 2016, 41(5): 133-136.

[9] 陳明晶, 方源敏, 陳杰. 最小二乘法和迭代法圓曲線擬合[J]. 測繪科學, 2016, 45(1): 194-197.

[10] 唐力明, 丁華祥, 朱紫陽. 應用車載DGNSS數據計算道路線形參數[J]. 測繪科學技術學報, 2008, 25(5): 321-323.

[11] HANS Z, SOULEYRETTE R, BOGENREIF C. Horizontal curve identification and evaluation[EB/OL].[2019-05-26].https://pdfs.semanticscholar.org/d000/7718259a60493e9c0991e001a5333e433fc1.pdf.

[12] AI Chengbo,TSAI Yichang.Automatic horizontal curve identification and measurement method using GPS data[EB/OL].[2019-05-26]. https://www.researchgate.net/profile/Chengbo_Ai/publication/266080116_Automatic_ Horizontal_Curve_Identification_and_Measurement_Method_Using_GPS_Data/links/579abe2e08ae425e491845a2/Automatic-Horizontal-Curve-Identification-and-Measurement-Method-Using-GPS-Data.pdf.

[13] LUO W, LIN L, WANG K C P. Automated pavement horizontal curve measurement methods based on inertial measurement unit and 3D profiling data[J]. Journal of Traffic & Transportation Engineering, 2016, 3(2): 137-145.

[14] AI Chengbo,TSAI Yichang.An automatic horizontal curve radii measurement method for roadway safety using GPS data[EB/OL].[2019-05-26].http://aichengbo.com/wp-content/uploads/2014/08/C-TRB-2014-LiDAR-Curve-Radii-Paper.pdf.

Road curvature estimation method for high precision navigation map

WANG Dongbo1, ZHAO Ning1, HUANG He2, ZHANG Huibin3

（1. Star Map Press, Beijing 100088, China; 2. School of Geomatics and Urban Spatial Information, Beijing University of Civil Engineering and Architecture, Beijing 102616, China; 3. Troops 32017, Lhasa 850000, China）

Aiming at the problems that it is difficult to realize the road curvature estimation for traditional lane line model, and the computation of related curve fitting is large in high-precise navigation, the paper proposed an iterative circle-fitting curvature estimation algorithm for calculating road curvature based on GNSS data: a certain number of adjacent points near the data points were added, and the selected data points were fitted until reaching the minimum fitting error, so that the curve of the road edge was gained; then the central angle was chosen as the parameter to identify the fitted curve segments; finally the curvature of the identified curves were estimated, and the true values were used to verify the accuracy of the estimation. Result showed that the road edges extracted by the proposed method would have high veracity and guarantee the accuracy of boundary points.

road edge; curve fitting; iterative circle fitting; curve recognition; accuracy verification

P228

A

2095-4999(2020)02-0049-06

王東波，趙寧，黃鶴，等. 高精度導航地圖道路線形參數估計方法[J]. 導航定位學報,2020,8(2): 49-54.（WANG Dongbo, ZHAO Ning, HUANG He, et al. Road curvature estimation method for high precision navigation map[J]. Journal of Navigation and Positioning, 2020, 8(2): 49-54.）

10.16547/j.cnki.10-1096.20200209.

2019-07-17

王東波（1990—），男，安徽靈璧人，碩士，編輯，研究方向為高精度導航地圖與智能駕駛。