夏靜

摘要

本文針對曲線曲面重構(gòu)問題中的基于平面有序離散點的特征點檢測方法進(jìn)行了研究。曲線的特征點選取的個數(shù)和準(zhǔn)確性直接決定擬合曲線的連續(xù)性和精確性。通過對擬二分法和貪心算法的MATLAB程序?qū)崿F(xiàn)，分析了兩種不同算法在選取特征點上的算法優(yōu)劣及在不同數(shù)量的樣本點上的結(jié)果展現(xiàn)，為工程上進(jìn)行曲線重構(gòu)提供了很好的實踐基礎(chǔ)。

【關(guān)鍵詞】有序離散點 擬二分法 貪心算法 曲線重構(gòu)

逆向工程技術(shù)是隨著計算機(jī)技術(shù)的發(fā)展和成熟以及數(shù)據(jù)測量技術(shù)的進(jìn)步而迅速發(fā)展起來的一門新興學(xué)科與技術(shù)。它改變了CAD從圖紙到實物的設(shè)計模式，為產(chǎn)品的設(shè)計提供了一條新的途徑。離散點的曲線曲面重構(gòu)是逆向工程中的重要問題，是研究曲線和曲面性質(zhì)的重要途徑。然而，在某些情況下，測量所得的數(shù)據(jù)本身可能并不精確，使得所得到的采樣點集并非完全落在原物體上，這時要求構(gòu)造一條曲線嚴(yán)格通過給定的數(shù)據(jù)點就沒有意義。因此，在容許誤差范圍內(nèi)給出一條最為逼近的數(shù)據(jù)點顯得更為合理，即曲線逼近方法。

傳統(tǒng)的曲線逼近方法是在給定數(shù)據(jù)點的基礎(chǔ)上分別通過參數(shù)化、插值或者擬合來生成初始曲線，然后計算曲率大小檢測曲線的特征點，在保證誤差條件下移除一些點以得到最少的曲線段數(shù)，使得加工效率得到提高，但這種方法由于初始所用數(shù)據(jù)點很多，導(dǎo)致在求解擬合曲線時系數(shù)矩陣太大，運(yùn)行效率低下；或者直接根據(jù)各種離散曲率計算方法，計算各數(shù)據(jù)點的曲率以得到一些特征點，然后再進(jìn)行樣條曲線求解，這種方法雖然較前一種方法有其優(yōu)越性，但是在計算曲率階段仍然具有一定的復(fù)雜度。

而另一種方法是跳過參數(shù)化，直接根據(jù)所給的離散點信息檢測曲線的特征點檢測方法。事實上，曲線圖形的信息主要集中在曲線的特征點上，而特征點多發(fā)生在轉(zhuǎn)角大的地方，如何快速有效的檢測出這些點并記錄下它們的位置，就能在后續(xù)的處理中保證圖形的拓?fù)湫再|(zhì)不變。本文就是通過研究兩種不同的特征點檢測方法，通過不同數(shù)量的樣本點的特征點檢測實現(xiàn)，分析不同的檢測方法在面對不同體量的樣本點時對特征點檢測的運(yùn)行效率和精確性。

1 核心概念

1.1 曲線重構(gòu)

曲線重構(gòu)問題歸根到底是對曲線進(jìn)行逼近問題。而曲線逼近問題是曲線插值與擬合的統(tǒng)稱。

根據(jù)給定一組有序的數(shù)據(jù)點，

，這些點可以是從某個形狀上測量得到的，也可以是設(shè)計人員給出的，構(gòu)造出一條曲線順序通過這些數(shù)據(jù)點，所構(gòu)造的曲線稱為插值曲線。

但是在實際應(yīng)用中，往往拿到的數(shù)據(jù)本身是有偏差的，這時就要求所得到的近似函數(shù)與原數(shù)據(jù)點的偏差按某種標(biāo)準(zhǔn)最小，以反映所給數(shù)據(jù)的總體趨勢，消除局部波動的影響，這就是曲線擬合問題。

基于所處理的是具有微小噪聲的離散數(shù)據(jù)，因此是一個擬合問題。在實際應(yīng)用中，最小二乘法是度量逼近程度的最常用的一種方法。

1.2 數(shù)據(jù)多邊形

介紹具體特征點檢測算法前，需要先了解數(shù)據(jù)多邊形的概念。

數(shù)據(jù)多邊形，是由檢測到的特征點為節(jié)點進(jìn)行分段線性插值得到的折線多邊形，艮P：若檢測到的特征點記為：

，則數(shù)據(jù)多邊形為

，其中，

分割每一直線段

，使其數(shù)據(jù)點數(shù)目與同一區(qū)間的原數(shù)據(jù)點數(shù)目相同。在此基礎(chǔ)上，我們考慮以兩點之間歐幾里得距離為判定逼近好壞的標(biāo)準(zhǔn)，并尋找出相應(yīng)的特征點，也就是：給定容許誤差ε，對每一直線段

，若直線段上的每一點與其相應(yīng)區(qū)間上的原數(shù)據(jù)點的歐幾里得距離≤ε，那么就稱Di+1為特征點。

2 特征點檢測方法

2.1 擬二分法

擬二分法基于二分法的原理。

二分法的原理為，在己知參數(shù)曲線的表達(dá)式的前提下，基于曲線的凸包性質(zhì).如果曲線上任意一點到其弦線的距離小于等于給定的誤差，就把弦線作為該曲線的逼近，否則按照參數(shù)區(qū)間把曲線一分為二，直到得到的子曲線段都滿足到其弦線的距離不超過給定的誤差為止。

而擬二分法是基于離散點，未知曲線表達(dá)式的前提下，不斷計算逼近直線與對應(yīng)樣本點兩點之間的歐幾里得距離，通過無限逼近誤差的方法檢測特征點。詳細(xì)算法如表1所示。

2.2 貪心算法

貪心算法主要基于實際生產(chǎn)加工中提高加工速度的考慮。在生產(chǎn)加工中，為了提高生產(chǎn)效率，需要減少逼近參數(shù)曲線的線段數(shù)量，從這一方面來說，自然是段數(shù)越少越好。實際上，在己知參數(shù)曲線的表達(dá)式的前提下，人們是基于參數(shù)，把曲線按照參數(shù)區(qū)間平均分段，每條子曲線段由其弦線逼近，直到得到的子曲線段都滿足到其弦線的距離不超過給定的誤差為止。其基本思想為：

曲線參數(shù)域[0，1]，對于給定的誤差s，曲線平均分為n段，每段的參數(shù)區(qū)間長度為

其中，M是曲線二階導(dǎo)數(shù)的上界。這是一個非常簡單的方法，并且當(dāng)誤差較大時這種方法工作地非常好，但是該方法有下列缺點：

（1）這種方法依賴參數(shù)，曲線不同，參數(shù)導(dǎo)數(shù)值不同，因而分解的段數(shù)不同；

（2）計算二階導(dǎo)數(shù)精確的界不容易；

對于有序離散點，直接考慮應(yīng)用型值點的值進(jìn)行數(shù)據(jù)多邊形逼近，并且保證多邊形與采樣點的最大偏移量，盡可能的等于逼近精度，這樣就減少了特征點的數(shù)量，就就是所謂的“貪心”。如表2所示。

3 算例比較及分析

為驗證兩種方法的優(yōu)劣，以sin（l/x），區(qū)間為[0.1，2]為對象進(jìn)行對比實驗，采樣點數(shù)分別為：381及939，在最大容許無法范圍內(nèi)，結(jié)果如表3所示。

通過表3，可以看出，對于初始數(shù)據(jù)點相對較少的情況，擬二分法的運(yùn)行速度相對于貪心算法比較快，耗時較少，效率比較高，并且對于特征點的檢測與貪心算法持平。但是對于初始數(shù)據(jù)點比較多的情況，擬二分法的運(yùn)行的時間比較長，并且所檢測得到的特征點要多于貪心算法，這是由于每一次該算法都是把區(qū)間分成兩個小區(qū)間，在計算的過程中一直處于添加特征點的狀態(tài)，使得它所得到的很多特征點實際并非我們所要的特征點，也就是說通過擬二分法得到的特征點，在去掉其中的某些特征點后，利用剩下的特征點所得到的逼近曲線仍然滿足所給的容許誤差，因此，從特征點最少最優(yōu)的角度來說，貪心算法要優(yōu)于擬二分法。

如表4所示，從誤差角度分析，樣本點較少的情況下，低于500時，擬二分法計算效率較快，但誤差略遜于貪心算法；樣本點一旦增多，貪心算法的優(yōu)勢明顯，無論是計算效率還是誤差方面，都勝過擬二分法，且其特征點數(shù)相對于擬二分法較少。

4 結(jié)論

本文針對實際工程應(yīng)用中有序離散點的擬合曲線的特征點檢測方法進(jìn)行研究，通過對擬二分法及貪心算法的理論分析和實例比較，得出：

（1）在樣本點較少的情況下，一般少于500個樣本點的情況下，采用擬二分法檢測特征點的方法速率較快，且特征點個數(shù)及誤差范圍都可接受；

（2）在樣本點個數(shù)超過500個情況下，貪心算法無論是特征點個數(shù)，精度及運(yùn)算效率都略優(yōu)于擬二分法。

因此，兩者比較，在工程上更要求精度的前提下，本文的結(jié)論是貪心算法更優(yōu)。當(dāng)然，在理論和實際工作中，尚有諸多特征點的檢測方法及后續(xù)的曲線逼近方法，筆者將繼續(xù)深入研究，希望能給出一個更快速、更精確、更適用于工程實現(xiàn)的檢測和重構(gòu)方法。

參考文獻(xiàn)

[1]孟高峰.基于散亂數(shù)據(jù)的曲線曲面重構(gòu)研究[D].南開：天津大學(xué)，2005.

[2]蘇步青.計算幾何[M].北京：人民教育出版社，1985-32-101.

[3]李雅青.列表輪廓零件數(shù)控自動編程技術(shù)自適應(yīng)算法[J].華北工學(xué)院學(xué)報，2000.