王東波，趙 寧，黃 鶴，張會(huì)彬

高精度導(dǎo)航地圖道路線形參數(shù)估計(jì)方法

王東波1，趙 寧1，黃 鶴2，張會(huì)彬3

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

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

道路邊線；曲線擬合；迭代圓擬合；曲線識(shí)別；精度驗(yàn)證

0 引言

未來(lái)的無(wú)人駕駛汽車(chē)能夠在道路上安全行駛，需要依靠高精度的導(dǎo)航電子地圖的參與，其中車(chē)道級(jí)別的高精度導(dǎo)航地圖數(shù)據(jù)庫(kù)尤其重要。車(chē)道級(jí)別的要素信息需要獲取的前期數(shù)據(jù)包括道路形狀[1]，車(chē)道的曲率、坡度、航向、高程以及側(cè)傾等主要數(shù)據(jù)。道路要素?cái)?shù)據(jù)中對(duì)無(wú)人駕駛汽車(chē)的路徑規(guī)劃和引導(dǎo)起到關(guān)鍵作用的當(dāng)屬道路曲率[2]，因?yàn)樗械牡缆肥┕し桨覆豢赡芡耆勒赵O(shè)計(jì)方案來(lái)執(zhí)行，因地制宜的現(xiàn)象導(dǎo)致道路的真實(shí)曲率會(huì)發(fā)生很多偏差，這就給高精度導(dǎo)航地圖數(shù)據(jù)的道路要素參數(shù)入庫(kù)時(shí)帶來(lái)困難。需要更高精度的無(wú)人駕駛汽車(chē)對(duì)車(chē)道級(jí)別的地圖數(shù)據(jù)要求更高。無(wú)人駕駛汽車(chē)在行駛時(shí)需要獲取前方道路的轉(zhuǎn)彎趨勢(shì)和方向，以提前調(diào)整變換車(chē)道和速度，就必須在地圖數(shù)據(jù)庫(kù)中錄入精確的道路曲率，以保證車(chē)輛安全行駛[3-5]。因此，目前應(yīng)用廣泛的導(dǎo)航電子地圖在定位檢測(cè)精度和地圖要素信息細(xì)致程度方面均不能滿(mǎn)足未來(lái)無(wú)人駕駛汽車(chē)發(fā)展的需求。

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

1 迭代圓擬合算法

本文中所選的曲線段[6]是具有單一半徑的最小單位，曲線段的半徑為（曲率為-1，而切線段的半徑為無(wú)窮大（曲率為零））。水平曲線由曲線段和曲線點(diǎn)（PC）及切線點(diǎn)（PT）描繪的切線段組成，如圖1（a）所示。對(duì)于更復(fù)雜的水平曲線，則存在相鄰的曲線段或由內(nèi)切線段和分開(kāi)的曲線段組成，例如反曲線，如圖1（b）所示。本研究的目的是準(zhǔn)確識(shí)別曲線和切線段，將相應(yīng)線段可靠地聚類(lèi)成不同的水平曲線類(lèi)型，并沿著確定的曲線測(cè)量相應(yīng)的半徑。

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

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

圖2 迭代圓擬合算法原理

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

(2)

式中、、分別是誤差函數(shù)的系數(shù)和常數(shù)項(xiàng)。

處理式（4）得

是點(diǎn)集中的點(diǎn)的個(gè)數(shù)，其中令

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

圖3 細(xì)分割的1個(gè)小路段

2 曲線識(shí)別

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

圖4 數(shù)據(jù)采集車(chē)

圖5 GNSS軌跡數(shù)據(jù)樣本

曲線識(shí)別的目的是根據(jù)上1步得出的劃分線段的空間分布和鄰接關(guān)系，自動(dòng)識(shí)別水平曲線和相應(yīng)的曲線類(lèi)型[11]。

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

圖7 實(shí)驗(yàn)數(shù)據(jù)采集路段

圖8 校準(zhǔn)數(shù)據(jù)集中心角的分布

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

圖9 不同曲線類(lèi)型的段相鄰模式的圖示

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

在分段驗(yàn)證過(guò)程中選擇2段道路數(shù)據(jù)進(jìn)行逐點(diǎn)對(duì)比，如圖10和圖11所示，程序中設(shè)置的GNSS-RTK數(shù)據(jù)為“真值（圖中放大圓圈中的左側(cè)曲線）”，而采集車(chē)采集的數(shù)據(jù)設(shè)置為“產(chǎn)品（圖中放大圓圈中的右側(cè)曲線）”，程序自動(dòng)讀取之后計(jì)算出驗(yàn)證數(shù)據(jù)和圖像數(shù)據(jù)。

圖10 XOY平面投影

圖11 XOY平面投影內(nèi)插點(diǎn)

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

圖12 數(shù)據(jù)點(diǎn)坐標(biāo)差對(duì)比

3 實(shí)驗(yàn)與結(jié)果分析

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

對(duì)于檢測(cè)性能測(cè)試，使用1類(lèi)誤差（未檢測(cè)到現(xiàn)有曲線）和2類(lèi)誤差（將直線部分錯(cuò)誤識(shí)別為曲線）。當(dāng)?shù)孛鎸?shí)況中的曲線完全錯(cuò)過(guò)或者檢測(cè)到的曲線段重疊不到相應(yīng)地面實(shí)況的75%時(shí)，將會(huì)報(bào)告1類(lèi)錯(cuò)誤；而當(dāng)將地面實(shí)際的曲線段檢測(cè)為直線段過(guò)程完成時(shí)，報(bào)告2類(lèi)誤差。最后的測(cè)試結(jié)果顯示，只有38條曲線被檢測(cè)為1類(lèi)誤差和27條曲線被檢測(cè)為2類(lèi)誤差，達(dá)到了90.1%的正確檢出率。還應(yīng)該注意的是，在38個(gè)1類(lèi)誤差中，只有10條曲線完全錯(cuò)過(guò)了，而其余的28條曲線仍然被所提出的方法部分檢測(cè)到。

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

表1 用于曲線分類(lèi)測(cè)試的混淆矩陣

表2 曲率評(píng)估成果

4 結(jié)束語(yǔ)

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

[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] 張莉婷. 基于出租車(chē)GNSS軌跡的導(dǎo)航道路數(shù)據(jù)更新[D]. 昆明: 昆明理工大學(xué), 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] 潘桂新, 鄧德標(biāo). 圓曲線擬合方法及數(shù)據(jù)采集分析[J]. 城市勘測(cè), 2014(5): 143-145.

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

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

[10] 唐力明, 丁華祥, 朱紫陽(yáng). 應(yīng)用車(chē)載DGNSS數(shù)據(jù)計(jì)算道路線形參數(shù)[J]. 測(cè)繪科學(xué)技術(shù)學(xué)報(bào), 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

王東波，趙寧，黃鶴，等. 高精度導(dǎo)航地圖道路線形參數(shù)估計(jì)方法[J]. 導(dǎo)航定位學(xué)報(bào),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—），男，安徽靈璧人，碩士，編輯，研究方向?yàn)楦呔葘?dǎo)航地圖與智能駕駛。