基于平面有序離散點的特征點檢測方法比較

夏靜

摘要

本文針對曲線曲面重構問題中的基于平面有序離散點的特征點檢測方法進行了研究。曲線的特征點選取的個數和準確性直接決定擬合曲線的連續性和精確性。通過對擬二分法和貪心算法的MATLAB程序實現，分析了兩種不同算法在選取特征點上的算法優劣及在不同數量的樣本點上的結果展現，為工程上進行曲線重構提供了很好的實踐基礎。

【關鍵詞】有序離散點 擬二分法 貪心算法 曲線重構

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

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

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

1 核心概念

1.1 曲線重構

曲線重構問題歸根到底是對曲線進行逼近問題。而曲線逼近問題是曲線插值與擬合的統稱。

根據給定一組有序的數據點，

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

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

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

1.2 數據多邊形

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

數據多邊形，是由檢測到的特征點為節點進行分段線性插值得到的折線多邊形，艮P：若檢測到的特征點記為：

，則數據多邊形為

，其中，

分割每一直線段

，使其數據點數目與同一區間的原數據點數目相同。在此基礎上，我們考慮以兩點之間歐幾里得距離為判定逼近好壞的標準，并尋找出相應的特征點，也就是：給定容許誤差ε，對每一直線段

，若直線段上的每一點與其相應區間上的原數據點的歐幾里得距離≤ε，那么就稱Di+1為特征點。

2 特征點檢測方法

2.1 擬二分法

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

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

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

2.2 貪心算法

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

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

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

（1）這種方法依賴參數，曲線不同，參數導數值不同，因而分解的段數不同；

（2）計算二階導數精確的界不容易；

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

3 算例比較及分析

為驗證兩種方法的優劣，以sin（l/x），區間為[0.1，2]為對象進行對比實驗，采樣點數分別為：381及939，在最大容許無法范圍內，結果如表3所示。

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

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

4 結論

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

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

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

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

參考文獻

[1]孟高峰.基于散亂數據的曲線曲面重構研究[D].南開：天津大學，2005.

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

[3]李雅青.列表輪廓零件數控自動編程技術自適應算法[J].華北工學院學報，2000.