為針對(duì)傳統(tǒng)曲線特征點(diǎn)的提取 *** 均采用Douglas-Peucher(D-P)算法給定閾值的思路，在曲度較大處易造成一 些重要特征點(diǎn)缺失，在彎曲的水平距離較小處易造成非特征點(diǎn)保留的問題，該文提出一種改進(jìn)的曲線特征點(diǎn)提取 *** ，通過自適應(yīng)來提取曲線的全局特征點(diǎn)，即通過標(biāo)準(zhǔn)差分別計(jì)算出間隔點(diǎn)連線的參考值和中間點(diǎn)到該線垂線的參考值，比較曲線上每個(gè)點(diǎn)的彎曲程度與曲線整體彎曲程度的大小，來提取曲線的全局特征點(diǎn)。以道路和河流的實(shí)際線數(shù)據(jù)進(jìn)行了實(shí)驗(yàn)，結(jié)果表明，該 *** 不僅很好地保持了曲線整體形狀特征，而且大幅降低了壓縮誤差、提高了精度。

關(guān)鍵詞：特征點(diǎn)；統(tǒng)計(jì)法；自適應(yīng)；標(biāo)準(zhǔn)差；彎曲度

微信號(hào)：MeetyXiao
添加微信好友, 獲取更多信息
復(fù)制微信號(hào)

能夠概括曲線基本形狀的點(diǎn)叫做曲線的特征點(diǎn)[1]。線要素化簡(jiǎn)算法[2-5]的核心思想是在盡可能保持曲線形狀特征的前提下，減少其節(jié)點(diǎn)的數(shù)量， 所以準(zhǔn)確提取特征點(diǎn)十分重要。目前單線壓縮的算法已經(jīng)較為成熟，曲線特征點(diǎn)的提取主要基于垂距、斜率、角度等[6-10] *** ，垂距法具有旋轉(zhuǎn)不變性和位移不變性的優(yōu)點(diǎn)，受到廣泛的應(yīng)用。垂距法來源于經(jīng)典D-P算法，通過預(yù)先給定閾值，再比較曲線上的點(diǎn)到曲線首末端點(diǎn)連線 的垂距與給定閾值的大小，來提取特征點(diǎn)；很多算法都是在此基礎(chǔ)上進(jìn)行了改進(jìn)，如：文獻(xiàn)[11]提出的面向自然岸線抽稀的改進(jìn)D-P算法，該算法是將曲線上的一些特殊凸點(diǎn)作為分段點(diǎn)，使用D-P進(jìn)行化簡(jiǎn)，提取自然岸線凸點(diǎn)作為備選分段點(diǎn)集，根據(jù)凸點(diǎn)與相鄰兩點(diǎn)組成的三角形面積大小篩選分段點(diǎn)，接著利用相鄰分段點(diǎn)作為D-P算法的首尾點(diǎn)，以基于最小二乘法的擬合曲線選定更優(yōu)距離閾值，并作為初始閾值，進(jìn)行逐段抽稀。文獻(xiàn) [12]提出的基于Ping的D-P算法抽稀閾值優(yōu)化選取，將測(cè)深條帶中每Ping數(shù) 據(jù)看做一條空間曲線，然后利用D-P算法進(jìn)行多波束測(cè)深數(shù)據(jù)的抽稀，選取不同抽稀閾值對(duì)Ping進(jìn)行抽稀運(yùn)算；文獻(xiàn)[13]提出的矢量數(shù)據(jù)壓縮算法的實(shí)現(xiàn)與改進(jìn)，即徑向約束D-P算法，通過預(yù)先給定的垂距閾值和徑向約束閾值，然后比較曲線上的點(diǎn)到曲 線首末端點(diǎn)連線的垂距與給定閾值的大小，再比較曲線上的點(diǎn)到曲線首末端點(diǎn)連線的值與給定徑向約束閾值 的大小，來提取特征點(diǎn)；上述算法基本上都是D-P算法的延伸和拓展，通 過給定閾值的方式來提取特征點(diǎn)，在曲度較大處易造成一些重要特征點(diǎn)缺失，在彎曲的水平距離較小處易造成一些非特征點(diǎn)的保留。本文針對(duì)徑向約束D-P算法[13]提取曲線全局特征點(diǎn)的不足，提出了一種全新的曲線全局特征點(diǎn)的識(shí)別 *** 。通過標(biāo)準(zhǔn)差分別計(jì)算出間隔點(diǎn)連線的參考值和中 間點(diǎn)到該線垂線的參考值，通過比較曲線上每個(gè)點(diǎn)的彎曲程度與曲線整體彎曲程度[14]的大小，來提取曲線的全局特征點(diǎn)。

１）D-P算法。D-P算法是曲線矢簡(jiǎn)量數(shù)據(jù)壓縮 的一種常用而有效的算法，利用遞歸過程能夠非常簡(jiǎn)潔的完成算法實(shí)現(xiàn)，先連接曲線首尾兩點(diǎn)構(gòu)成一條直線，然后計(jì)算曲線上其余各個(gè)點(diǎn)到該直線的距離ｄ，選取其中的更大值Dk與規(guī)定的臨界值Ｄ作比較，若曲線上的點(diǎn)到該直線上距離的更大值Dk都小于規(guī)定的臨界值Ｄ，則直接舍去曲線上首尾間的各個(gè)點(diǎn)，若曲線上的點(diǎn)到該直線上距離的更大值Dk不小于規(guī)定的臨界值Ｄ，則保留曲線上的該點(diǎn)。以圖１為例，具體步驟如下：①設(shè)曲線由點(diǎn)序P１，P２，…，Pｎ構(gòu)成，取P１，Pｎ為首尾兩點(diǎn)；②計(jì)算曲線上所有內(nèi)點(diǎn)Pｉ（ｉ＝２，３，…， ｎ－１）到直線P１Pｎ的距離Dｉ，選取曲線上的點(diǎn)到直線距離更大的點(diǎn)Pk；③判斷曲線到直線P１Pｎ上的更大距離Dk與給定的臨界值Ｄ的大小，若Dk小于給定的臨界值，則該點(diǎn)不是特征點(diǎn)，若Dk不小于給定的臨界值，則該點(diǎn)Ｐｋ成為特征點(diǎn)。

２）帶有徑向約束的D-P算法。D-P算法僅利用 垂向距離作為約束條件來決定曲線內(nèi)點(diǎn)的取舍，當(dāng)給定的臨界值差別比較大時(shí)，會(huì)導(dǎo)致曲線 的壓縮結(jié)果完全不同；該算法在大比例尺度壓縮過程中不能有效控制面積誤差[15]，致使壓縮后的面積與原圖形面積差距比較大；文獻(xiàn)[13]針對(duì)這些問題引進(jìn)了徑向距離約束條件的 *** ，提出了一種矢 量數(shù)據(jù)壓縮的D-P算法的實(shí)現(xiàn)與改進(jìn)，降低了壓縮后圖形面積與原圖形面積的誤差，取得了較好的效果。該算法的基本思想是在D-P算 法②、③ 中間加一個(gè)徑向約束條件ｒ，步驟如下：步驟的① 和②不變；③給定徑向約 束 條 件ｒ；ｒ?yàn)?曲線 一 定距離的弧段；④判斷曲線到直線P１Pｎ上的更大 距離Dk與給定的臨界值Ｄ的大小，若Dk小于給定臨界值，則再判斷｜PKP１｜或｜PKＰｎ｜的距離與徑向約束條件ｒ的大小，只要有一個(gè)距離大于徑向約束條件ｒ，則點(diǎn)PK仍作為特征點(diǎn)保留；若 Dk不小于給定的臨界值，則該點(diǎn)為特征點(diǎn)。

該壓縮算法仍然采用D-P 算法的思路，導(dǎo)致在曲線曲度較大處易 造成一些重要特征點(diǎn)缺失， 在彎曲的水平距離較小處易造成非特征點(diǎn)的保留，最終影響壓縮后的圖形效果[16]。見圖２（ａ），該閾值下特征點(diǎn)為B、C、Ｄ、Ｅ、Ｇ、Ｈ、Ｉ、Ｋ、Ｌ、 Ｍ、Ｏ。由于閾值較小，在彎曲的水平距離較小處 造成非特征點(diǎn) Ｄ、Ｋ、Ｍ 的 保 留，見 圖２（ｂ），該閾值下特征點(diǎn)為Ｃ、Ｄ、Ｅ、Ｇ、Ｉ、Ｏ。由于閾值較大，在彎曲的水平距離較小處造成非特征點(diǎn)Ｄ的保留以及在曲度較大處造成特征點(diǎn) Ｂ、Ｆ 的缺失。

本文針對(duì)大比例尺下徑向約束D-P算法提取曲 線全局特征點(diǎn) *** 的不足，結(jié)合基于D-P算法特征點(diǎn)的選取 *** 與基于帶有徑向約束D-P算法特征點(diǎn) 的選取 *** ，提出一種改進(jìn)的曲線特征點(diǎn)提取 *** 。核心內(nèi)容為通過自適應(yīng)來提取曲線的全局特征點(diǎn)， 先分別計(jì)算出點(diǎn)到間隔點(diǎn)連線垂距的平均數(shù)和中位數(shù)以及間隔點(diǎn)連線的平均數(shù)和中位數(shù)，再通過比較各自的標(biāo)準(zhǔn)差，選取各自更優(yōu)的平均數(shù)或中位數(shù)作為能否保留曲線特征點(diǎn)的參考值，最后通過比較曲 線上每個(gè)點(diǎn)的彎曲程度與曲線整體彎曲程度[17-18]的 大小，來提取曲線的全局特征點(diǎn)。線要素化簡(jiǎn)算法的核心思想是在盡可能保持 曲線形狀特征的前提下，減少其節(jié)點(diǎn)的數(shù)量，同時(shí)盡可能多地保留 曲線全局特征點(diǎn)。提取曲線全局特征點(diǎn)主要有以下４個(gè)步驟，見圖３。

１）遍歷曲線上所有的點(diǎn)，連接曲線上的每一個(gè)間隔點(diǎn)，同時(shí)過中間點(diǎn)做間隔點(diǎn)連線的垂線，見圖３，依次類推，直至遍歷完曲線上所有的點(diǎn)，垂線分別記為 Ｍ１、Ｍ２、Ｍ３…，間隔點(diǎn)連線的長度分別記為 Ｎ１、Ｎ２、Ｎ３…。

２）統(tǒng)計(jì)出每條垂線的長度 Ｍ 以及每一條間隔點(diǎn) 連線的長度Ｎ，計(jì)算出垂線的中位數(shù) ＭＰ、平均數(shù)ＭＱ和標(biāo)準(zhǔn)差，同時(shí)計(jì)算出間隔點(diǎn)連線長度的中位數(shù)ＮＰ、平均數(shù)ＮＱ和標(biāo)準(zhǔn)差（這里的 標(biāo)準(zhǔn)差是指分別以中位數(shù)為參考值求出的標(biāo)準(zhǔn)差和 以平均數(shù)為參考值求出的標(biāo)準(zhǔn)差），標(biāo)準(zhǔn)差反映一組 數(shù)據(jù)的離散程度，標(biāo)準(zhǔn)差越小離散程度越小，標(biāo)準(zhǔn) 差越大離散程度越大，見表１和式（１）～式（８）。

中位數(shù)：將一組數(shù)從大到小或從小到大進(jìn)行有序排列，位于最中間的那個(gè)數(shù)稱為中位數(shù)。ＭＱ表示垂線的平均數(shù)，ＮＱ表示間隔點(diǎn)連線的平均數(shù)；ＭＰ表示垂線的中位數(shù)，ＮＰ表示間隔點(diǎn)連線的中位 數(shù)；δＭ表示垂線的標(biāo)準(zhǔn)差，δＮ 表示間隔點(diǎn)連線的標(biāo)準(zhǔn)差；D(M)表示垂線的方差，D(N)表示間隔點(diǎn)連線的方差。

３）分別比較以平均數(shù)為參考值求出的標(biāo)準(zhǔn)差和以中位數(shù)為參考值 求出的標(biāo)準(zhǔn)差值的大小，若以中位數(shù)ＭＰ為參考值計(jì)算出標(biāo)準(zhǔn)差的值小，則以垂線的中位數(shù)ＭＰ為參考值；若以平均數(shù)ＭＱ為參考值計(jì)算出的標(biāo)準(zhǔn) 差的值小，則以垂線的平均數(shù)ＭＱ為參考值。同理，若以中位數(shù)ＮＰ為參考值計(jì)算出的標(biāo)準(zhǔn)差的值小，則以間隔點(diǎn)連線的中位數(shù)ＮＰ為參考值；若以平均數(shù)ＮＱ為參考值計(jì)算出的標(biāo)準(zhǔn)差的值小，則以間隔點(diǎn)連線的平均數(shù) ＮＱ為參考值。

４）表示曲線在i點(diǎn)的彎曲程度，比值越大表示曲線在該點(diǎn)處的彎曲程度越大，比值越小表示曲線在該點(diǎn)處的彎曲程度越小。這里以各自 的中位數(shù)作為參考值來說明本文的 *** ：如果 ，那么表明曲線在該點(diǎn)處彎曲程度較大，則選取該點(diǎn)作為曲線的一個(gè)特 征點(diǎn)；如果  ，那么表明曲線在該點(diǎn)處彎曲程 度較小，則不選取該點(diǎn)作為曲線的特征點(diǎn)；依次類推直至遍歷完曲線上 所有的特征點(diǎn)，ＡＢＣＤＥＦＧＨ為原折線，ＡＣＤＥＦＧＨ為本文算法自適應(yīng)后的折線見圖４。

在相同的參數(shù)條件下用兩種算法分別對(duì)道路和河流數(shù)據(jù)進(jìn)行化簡(jiǎn)，圖５和圖６分別截取了部分化簡(jiǎn)結(jié)果，在處理道路、河流等曲度較平緩、彎曲水平距離較大處的線群密集要素時(shí)，徑向約束D-P算法化簡(jiǎn)效率較高，但是在曲度較大處、彎曲水平距離較小處時(shí)化簡(jiǎn)結(jié)果顯得較粗糙，原因是由于垂距閾值和徑向約束閾值的隨機(jī)性，導(dǎo)致在曲度較大處一些重要特征點(diǎn)的丟失和彎曲水平距 離較小處一些非特征點(diǎn)的保留造成 的（圖５（ａ）Ａ、Ｂ 處及圖６（ａ）Ａ、Ｂ、Ｃ、Ｄ 處）。本文算法通過自 適應(yīng)來提取曲線的全局特征點(diǎn)，化簡(jiǎn)結(jié)果與原始數(shù)據(jù)貼合緊密，不僅精確地提取了曲度較大處的特征點(diǎn)，同時(shí)避免了彎曲水平距離較小處非特征 點(diǎn)的保留，保證了曲線原有的形狀特征不發(fā)生明 顯變化（圖５（ｂ）及圖６（ｂ））。對(duì)比道路、河流兩幅圖的化簡(jiǎn)結(jié)果，當(dāng)線要素曲度平緩而彎 曲水平距離較大時(shí)，改進(jìn)的效果并不明顯，而對(duì)于曲度較大同時(shí)彎曲水平 距離較小的線要素區(qū)域，本文算法的化簡(jiǎn)效果明顯優(yōu)于徑向約束D-P算 法，在保證了 曲線壓縮的同時(shí)，以更大限度保留了曲線原來的形狀特征。

１）以道路曲線進(jìn)行實(shí)驗(yàn)效果圖對(duì)比。圖５為分 別依據(jù)徑向約束D-P算法和本文 *** 提取道路曲線全局特征點(diǎn)的結(jié)果。用D-P算法提取曲線全局特征點(diǎn)的局部效果見圖５（ａ）；用本文算法提取 曲 線全局特征點(diǎn)的局部效果，見圖５（ｂ）。

統(tǒng)計(jì)兩種壓縮 *** 下道路曲線簡(jiǎn)前后保留點(diǎn)的個(gè)數(shù)、特征點(diǎn)個(gè)數(shù)、壓縮 率、面積位移總和以及平均偏移差[19-22]的對(duì)比情況，見表２。由圖５（ａ）和表２可知該道路曲線共有1475個(gè)點(diǎn)，當(dāng)使用徑向約束D-P 算法進(jìn)行曲線全局特征 點(diǎn)提取后，道路曲線全局保留點(diǎn)的數(shù)量為351個(gè)， 被化簡(jiǎn)的點(diǎn)的數(shù)量為1124個(gè)，壓縮率達(dá)到76.2％，盡管壓縮率很高，但是提取曲線全局的特征點(diǎn)數(shù)量僅為105個(gè)，數(shù)量明顯偏少，曲線上一 些重要的特 征點(diǎn)沒有被保留下來，原因是在提取的過程中曲度較大處的一些特征點(diǎn)被忽略掉，同時(shí)面積位移總和為97962.37 ｍ2、平均偏移差為 23.75ｍ2都明顯偏大，導(dǎo)致化簡(jiǎn)后相對(duì)位置發(fā)生較大變化，主要是由于垂距閾值的隨 機(jī)性導(dǎo)致曲線在曲度較大處造成一些重要特征點(diǎn)缺失，在彎曲的水平距離較短處造成非特征點(diǎn)的保留造成的。由圖５（ｂ）和表２可知在使用本文算法進(jìn)行曲線全局特征點(diǎn)提取時(shí)，道路曲線全局保留點(diǎn)的數(shù)量為527個(gè)，被化簡(jiǎn) 的點(diǎn)的數(shù)量為948個(gè)，壓縮率為 64.3％，提取曲線全局特征點(diǎn)的數(shù)量為167個(gè)，不論是保留點(diǎn)的個(gè)數(shù)還是特征點(diǎn)的個(gè)數(shù)均明顯多于徑向約束D-P算法提取的數(shù)量，壓縮率也超過了一半，同時(shí)面積位移總和為65024.83m2、平均位移差為12.53ｍ，都明顯低于傳統(tǒng) *** ，本文 *** 通過比較各自的 標(biāo)準(zhǔn)差，選取各自更優(yōu)的平均 數(shù)或中位數(shù)作為能否保留曲線特征點(diǎn)的參考值， 然后判斷曲線上每個(gè)點(diǎn)的彎曲程度與曲線整體彎曲程度的大小，用自適應(yīng)來提取曲線的全局特征點(diǎn)。

２）以河流曲線進(jìn)行實(shí)驗(yàn)效果圖對(duì)比。圖６為 分別依據(jù)徑向約束D-P算法和本文 *** 提取河流曲線全局特征點(diǎn)的結(jié)果 。用D-P算法提取 河流曲線全局特征點(diǎn)的局部效果見圖６（ａ）；用 本文算法提取曲線全局特征點(diǎn)的局部效果， 見 圖６（ｂ）。

統(tǒng)計(jì)兩種壓縮 *** 下河流曲線化簡(jiǎn)前后保留點(diǎn)的數(shù)量、特征點(diǎn)數(shù)量、壓縮率、面積位移總和、以及平均偏移差[19-22]的對(duì)比情況，見表３。

由圖6(a)和表３可知該河流曲線共有6654個(gè)點(diǎn)， 當(dāng)使用徑向約D-P算法進(jìn)行曲線全局特征點(diǎn)提 取后，河流曲線全局保留點(diǎn)的數(shù)量為1710個(gè)，被化簡(jiǎn)的點(diǎn)的數(shù)量為4944個(gè)，壓縮率為74.3％，壓 縮率很高，但是提取曲線全局的特征點(diǎn)個(gè)數(shù)僅為480個(gè)， 數(shù)量明顯偏少， 同時(shí)面積位移總和為 231962.37m2、平均偏移差為25.47m都明顯偏大，導(dǎo)致一些交叉口處[22]、曲度較大處以及曲線 彎曲水平距離較短處的特征點(diǎn)化簡(jiǎn)之后與原曲線 的相對(duì)位置誤差可能非常大，主要是由于垂距閾值的隨機(jī)性導(dǎo)致曲線在曲度較大處造成一些重要特征點(diǎn)缺 失，在彎曲的水平距離較短處造成非特 征點(diǎn)的保留造成的。由 圖6(b)和表３可知在使用本文算法進(jìn)行曲線全局特征 點(diǎn)提取時(shí)，河流曲線全局保留點(diǎn)的數(shù)量為2522個(gè)，被化簡(jiǎn)的點(diǎn)的數(shù)量 為4132個(gè)，壓縮率為62.1％，提取曲線全局特征 點(diǎn)的數(shù)量為800個(gè)，不論是保留點(diǎn)的個(gè)數(shù)還是特征 點(diǎn)的個(gè)數(shù)均明顯多于徑向約束D-P算法提取的 數(shù)量，壓縮率也超過了50％，同時(shí)面積位移總和為65924.83ｍ2、平均位移 差 為9.62ｍ都明顯低于傳統(tǒng) *** ，因?yàn)楸疚耐ㄟ^標(biāo)準(zhǔn)差分別計(jì)算出間隔點(diǎn)連線 的參考值和中間點(diǎn)到該線垂線的參考值，通過比較曲線上每個(gè)點(diǎn)的彎曲程度與曲線整體彎 曲程度的大小，通過自適應(yīng)來提取曲線的全局特征點(diǎn)。

曲線特征點(diǎn)的識(shí)別被廣泛用于反映河流等級(jí)化簡(jiǎn)、道路化簡(jiǎn)以及等高 線的化簡(jiǎn)。線要素化簡(jiǎn)算法的核心思想是在盡可能保持曲線形狀特征的前提下，盡量減少其節(jié)點(diǎn)的數(shù)量，所以準(zhǔn)確提取特征點(diǎn)十分重要。對(duì)于道路、河流等曲線進(jìn)行全局特征點(diǎn)提取時(shí)，傳統(tǒng)的徑向約束D-P算法提取的結(jié)果與原曲線誤差可能較大，主要是由于垂距 閾值的隨機(jī)性導(dǎo)致在曲度較大處易造成一些重要特征點(diǎn)缺失，在彎曲的水平距離較小處造成非特征點(diǎn)的保留。本文通過判斷曲線上每個(gè)點(diǎn)的彎曲程度，設(shè)計(jì)實(shí)現(xiàn)了一種改進(jìn)的曲線特征點(diǎn)提取 *** ，通過比較曲線上每個(gè)點(diǎn)的彎曲程度與曲線整 體彎曲程度的大小，通過自適應(yīng)來提取曲線的全局特征點(diǎn)，能夠較好地提取曲度較大處的一些重要特征點(diǎn)，同時(shí)能夠避免彎曲水平距離較小處一些非特征點(diǎn)的保留，從而更大可能保持與原曲線 形狀特征一致，所以本文算法更加符合實(shí)際的應(yīng)用需求。