基于PSO的B樣條曲線光順重構(gòu)算法

劉武飛 張旭

關(guān)鍵詞：B樣條;曲線光順;曲率變化;粒子群優(yōu)化算法

摘要：針對(duì)工程實(shí)踐中存在的曲線重構(gòu)技術(shù)很難同時(shí)考慮曲線誤差和曲線光順性的問題，提出了一種基于粒子群優(yōu)化（PSO）的B樣條曲線光順重構(gòu)算法.該算法利用PSO算法同時(shí)調(diào)整影響曲率壞點(diǎn)、壞區(qū)，以及最壞點(diǎn)處的主、副等多個(gè)控制頂點(diǎn)，找出控制點(diǎn)位置的最優(yōu)解，優(yōu)先對(duì)曲線上曲率符號(hào)不一致的壞點(diǎn)或壞區(qū)進(jìn)行光順，以避免曲線上出現(xiàn)多余拐點(diǎn)，而后對(duì)曲率變化劇烈的區(qū)域進(jìn)行光順，迭代更新生成最優(yōu)曲線.實(shí)驗(yàn)結(jié)果表明，該算法有效地提升了光順效率，得到了更好的光順效果，且能夠滿足任意給定的誤差精度，驗(yàn)證了其應(yīng)用于工程實(shí)踐的可行性.

Abstract：In order to solve the problem that the curve reconstruction technology existing in engineering practice was difficult to consider both curve error and curve smoothness， a fairing reconstruction algorithm of B-spline curve was proposed based on particle swarm optimization （PSO）.The algorithm used PSO to adjust the main and secondary control vertices which affect the curvature bad points， bad region andthe main control and subcontrol points of the worst points at the same time， so as to find the optimal solution for the position of the control points.The bad points or bad region with inconsistent curvature symbols on the curve were faired first to avoid the occurrence of redundant inflection points on the curve.Then the region with sharp curvature changes were faired and the optimal curve was generated iteratively.The experimental results showed that the algorithm effectively improved the fairing efficiency， obtained better fairing effect， and could satisfy any given error accuracy， which proved its feasibility in engineering practice.

0 引言

曲線重構(gòu)工作經(jīng)常出現(xiàn)在計(jì)算機(jī)輔助設(shè)計(jì)（CAD）、計(jì)算機(jī)輔助制造（CAM）等領(lǐng)域，工程技術(shù)人員一般通過插值的方法進(jìn)行曲線重構(gòu)得到高精度的曲線.但在數(shù)據(jù)獲取階段，人工或設(shè)備因素會(huì)導(dǎo)致原始數(shù)據(jù)點(diǎn)摻雜了一些誤差和噪聲，使得通過插值方法構(gòu)造的高精度曲線難有較好的光順性，無法滿足目前航空、造船、模具等工業(yè)領(lǐng)域?qū)Ξa(chǎn)品外觀、產(chǎn)品功能等方面越來越高的光順要求，因此國內(nèi)外業(yè)內(nèi)技術(shù)人員對(duì)曲線光順方法展開了深入研究.

龍小平[1]根據(jù)型值點(diǎn)信息篩選壞型值點(diǎn)，遵循最優(yōu)化原則，通過每次調(diào)整1個(gè)控制點(diǎn)來調(diào)整局部的控制頂點(diǎn)，得到局部能量最小的光順曲線.局部光順?biāo)惴m然計(jì)算速度較快，但很難保證光順后曲線的整體效果.因此，羅衛(wèi)蘭等[2]通過增加權(quán)重規(guī)定控制頂點(diǎn)的擾動(dòng)量，利用最小化原則求出新的控制頂點(diǎn)，進(jìn)而對(duì)曲線進(jìn)行光順;張莉等[3]建立了廣義B樣條曲線的對(duì)偶基，用最佳逼近的方法求出新的曲線控制頂點(diǎn)，以實(shí)現(xiàn)曲線光順.全局光順?biāo)惴ú恍枰x點(diǎn)，但當(dāng)數(shù)據(jù)點(diǎn)過于復(fù)雜時(shí)，運(yùn)算速度較慢，且優(yōu)化方程可能無解.為了提高光順效率和重構(gòu)質(zhì)量，研究人員引進(jìn)了小波分析，A.Ceruti等[4]基于二進(jìn)小波光順，把多分辨分析應(yīng)用在A級(jí)曲線曲面上，對(duì)壞控制頂點(diǎn)進(jìn)行調(diào)整，得到了較好的光順效果.A.Z.Wang等[5-6]提出了光順性指標(biāo)的概念，發(fā)現(xiàn)經(jīng)典的二進(jìn)小波光順?biāo)惴ǖ氖褂脮?huì)受控制頂點(diǎn)數(shù)目的約束.為滿足任意控制頂點(diǎn)數(shù)目曲線曲面的光順要求，潘洋宇等[7]通過增加控制頂點(diǎn)的數(shù)目使其得以實(shí)現(xiàn)，給出了基于第2代小波變換的多分辨率光順?biāo)惴?R.Pan等[8]通過節(jié)點(diǎn)插入構(gòu)造出雙正交非均勻B樣條小波.紀(jì)小剛等[9]提出了一種新的能在任何二進(jìn)尺度下進(jìn)行連續(xù)小波變換的光順?biāo)惴?該類算法生成的曲線光順性較好，但隨著光順的進(jìn)行，控制頂點(diǎn)的減少會(huì)導(dǎo)致曲線產(chǎn)生很大的誤差.

隨著人工智能算法的興起，基于人工智能的曲線光順研究日益受到重視.E.Ulker等[10]采用人工免疫系統(tǒng)來優(yōu)化節(jié)點(diǎn)矢量，對(duì)曲線進(jìn)行光順，使曲線有較好的光順性;X.Y.Zhao等[11]基于改進(jìn)的k-means算法，建立節(jié)點(diǎn)的高斯混合模型，再根據(jù)其高斯概率求解新節(jié)點(diǎn)位置光順曲線，但該方法只適用于閉曲線;A.Galvez等[12]提出粒子群光順?biāo)惴?，該算法?duì)于具有奇點(diǎn)、尖點(diǎn)的曲線也能生成較好的結(jié)果;H.M.Kang等[13]采用稀疏優(yōu)化的模型求解節(jié)點(diǎn)向量，這會(huì)產(chǎn)生較少數(shù)量的節(jié)點(diǎn)，使曲線擁有較好的光順性;胡良臣等[14]使用帶有法向約束的粒子群優(yōu)化（PSO）算法迭代求解曲線的節(jié)點(diǎn)向量.這類算法由于參數(shù)的設(shè)定不同，使得算法有可能收斂于局部最優(yōu)解，導(dǎo)致曲線的光順效果不理想.但由于人工智能算法對(duì)復(fù)雜、非線性、多目標(biāo)問題可以獲得全局最優(yōu)解，且不同的智能算法還有各自獨(dú)到的優(yōu)點(diǎn)，所以基于人工智能算法的曲線光順重構(gòu)，依舊是業(yè)界當(dāng)前的研究熱點(diǎn).

在實(shí)際建模過程中，設(shè)計(jì)人員根據(jù)點(diǎn)云數(shù)據(jù)來生成曲線，再逐一調(diào)整單個(gè)控制點(diǎn)，以改變曲線與點(diǎn)云之間的偏差，使得生成的曲線與點(diǎn)云貼合;畫出曲線的曲率梳，再逐一調(diào)整單個(gè)控制點(diǎn)，以控制曲線曲率的變化波動(dòng)，使得曲率變化平緩，曲線光順.但曲線諸多控制點(diǎn)的位置變動(dòng)又會(huì)導(dǎo)致曲線誤差發(fā)生改變，需再進(jìn)行曲線誤差的調(diào)整，確保曲線誤差在允許范圍內(nèi)，如此循環(huán)往復(fù)，需要不停地反復(fù)操作，直到在給定的誤差范圍內(nèi)，得到一條曲率變化平緩、光順性較好的曲線.但當(dāng)面對(duì)數(shù)據(jù)量較大且包含信息復(fù)雜的點(diǎn)云數(shù)據(jù)時(shí)，這種人工操作需要很長時(shí)間，會(huì)耗費(fèi)大量的人力物力，且不能保證得到最好的結(jié)果.

針對(duì)現(xiàn)有算法對(duì)曲線曲面光順效果不夠理想和實(shí)際建模過程中手動(dòng)調(diào)整曲線曲面光順會(huì)耗費(fèi)大量人力物力的問題，本文擬以目前普遍使用的3次B樣條曲線為研究對(duì)象，提出在給定誤差約束下、基于PSO的B樣條曲線光順重構(gòu)算法，以期提高B樣條曲線的光順效果，有效控制光順后生成曲線的誤差，以滿足工程需求.

1 曲線光順性影響因素分析

1.1 曲線的表示

根據(jù)式①和B樣條曲線控制多邊形的性質(zhì)，通過直接修改B樣條曲線控制頂點(diǎn)位置進(jìn)行曲線光順，可使光順過程更加直接.3次B樣條曲線上每個(gè)點(diǎn)的值由4個(gè)控制頂點(diǎn)和4個(gè)B樣條基函數(shù)決定，其中最大的B樣條基函數(shù)值所對(duì)應(yīng)的控制點(diǎn)，稱之為主控制頂點(diǎn).將與主控制頂點(diǎn)相鄰的兩個(gè)控制頂點(diǎn)稱為副控制頂點(diǎn)，當(dāng)主控制頂點(diǎn)為4個(gè)控制頂點(diǎn)中的第一個(gè)或最后一個(gè)時(shí)，只有1個(gè)副控制頂點(diǎn).

基于通用的光順準(zhǔn)則[15-16]，本文通過觀察曲線曲率變化來評(píng)價(jià)曲線的光順性.如果曲線光順性比較好，那么曲線的曲率梳應(yīng)是連續(xù)的，且曲率梳由盡可能少的單調(diào)曲線組成[17-18].3次B樣條曲線的曲率可由下式求得：

1.2 曲率壞點(diǎn)調(diào)整

越簡單的曲線光順性越好，復(fù)雜的曲線可以拆分成簡單的曲線進(jìn)行光順.

光順性良好的曲線上每點(diǎn)的曲率符號(hào)應(yīng)該保持一致，與相鄰點(diǎn)曲率符號(hào)不一致的點(diǎn)可通過下式找出：

這些點(diǎn)稱為曲率壞點(diǎn)，與其下標(biāo)對(duì)應(yīng)的曲線上的投影點(diǎn)稱為曲線壞點(diǎn).將曲線壞點(diǎn)提取出來，根據(jù)下標(biāo)由小到大重新排列組成序列{Qi1，Qi2，…，Qis}，其中s是壞點(diǎn)的總個(gè)數(shù)，給出與之對(duì)應(yīng)的主控制頂點(diǎn)的序列對(duì)主控制頂點(diǎn)序列中具有相同下標(biāo)的控制頂點(diǎn)進(jìn)行處理，使其只出現(xiàn)1次，進(jìn)而構(gòu)造新的主控制頂點(diǎn)序列本文通過調(diào)整主控制頂點(diǎn)序列中出現(xiàn)的控制頂點(diǎn)來處理曲線壞點(diǎn).

1.3 曲率壞區(qū)調(diào)整

對(duì)提取的曲線壞點(diǎn)進(jìn)行曲率符號(hào)調(diào)整后，曲線的曲率符號(hào)可能仍不一致.根據(jù)式②得到的曲線曲率符號(hào)一般分為兩種情況：一種是曲線曲率經(jīng)過一次變號(hào)，小部分曲線上點(diǎn)的曲率符號(hào)與其他曲線上點(diǎn)的曲率符號(hào)相反，呈現(xiàn)“正負(fù)”或“負(fù)正”的趨勢;另一種是曲線的曲率經(jīng)過兩次變號(hào)，呈現(xiàn)“正負(fù)正”或“負(fù)正負(fù)”的趨勢.曲率符號(hào)多變的曲線可以

簡單

劃分為這兩種情況進(jìn)行處理.

統(tǒng)計(jì)曲率符號(hào)為正的投影點(diǎn)個(gè)數(shù)，若數(shù)量多于曲線符號(hào)為負(fù)的投影點(diǎn)數(shù)量，就將曲率符號(hào)為正的區(qū)域稱為曲率壞區(qū);反之，就將曲率符號(hào)為負(fù)的區(qū)域稱為曲率壞區(qū).

與曲率壞區(qū)對(duì)應(yīng)曲線上的點(diǎn)構(gòu)成的區(qū)域是曲線壞區(qū).提取出給定數(shù)據(jù)點(diǎn)在曲線壞區(qū)上的所有投影點(diǎn)，根據(jù)其下標(biāo)，由小到大地重新排列組成序列{Qj1，Qj2，…，Qjl}，其中l(wèi)是曲線壞區(qū)包含投影點(diǎn)的總個(gè)數(shù)，推出與其下標(biāo)對(duì)應(yīng)的主控制頂點(diǎn)的序列{Pi1，Pi2，…，Pil}.對(duì)具有相同下標(biāo)的控制頂點(diǎn)進(jìn)行同樣處理，得到新的主控制頂點(diǎn)序列{Pi1，…，Pim}，m≤l，對(duì)其中的控制頂點(diǎn)位置進(jìn)行優(yōu)化調(diào)整以使曲線各點(diǎn)曲率符號(hào)相同.

1.4 曲率變化調(diào)整

光順準(zhǔn)則中要求曲率變化較均勻，設(shè)曲線上第i個(gè)內(nèi)部點(diǎn)左右曲率變化率差為從上式可知，Δki小，表示該點(diǎn)左右曲率變化率相差不大，也表示該處曲線曲率變化平緩;當(dāng)Δki=0時(shí)，表示曲線上該點(diǎn)和相鄰兩點(diǎn)（第i-1，i，i+1個(gè)數(shù)據(jù)點(diǎn)處）的曲率變化均勻，曲線光順.以Δki最大值作為光順性指標(biāo)會(huì)使曲率高的區(qū)域光順次數(shù)較多，曲率低的區(qū)域光順次數(shù)較少.為彌補(bǔ)這種不足，選用Δdi作為光順性指標(biāo)：

其中，分母是曲線上該點(diǎn)和相鄰兩點(diǎn)曲率絕對(duì)值中的最大值.計(jì)算所有內(nèi)部點(diǎn)的Δdi，將Δdi值最大的點(diǎn)作為待光順的最壞點(diǎn).

曲線上某點(diǎn)處的B樣條基函數(shù)值的大小，決定了對(duì)應(yīng)控制頂點(diǎn)對(duì)該點(diǎn)的影響程度.一般是選擇移動(dòng)影響程度最大的控制頂點(diǎn)來光順曲線，即通過調(diào)整最壞點(diǎn)處主控制頂點(diǎn)的位置來光順曲線，使得該點(diǎn)處曲率變化比之前平緩.然而，在實(shí)際光順過程中，往往會(huì)出現(xiàn)一些特殊的情況，譬如最壞點(diǎn)處的B樣條基函數(shù)的最大值與次大值之間相差不大，這就表示與之對(duì)應(yīng)的控制頂點(diǎn)對(duì)最壞點(diǎn)的影響程度相當(dāng)，在這種情況下，采取只移動(dòng)主控制頂點(diǎn)的光順策略可能得不到理想的光順結(jié)果，光順效率也不高;又因?yàn)锽樣條基函數(shù)中的最小值都遠(yuǎn)小于最大值，所以與之對(duì)應(yīng)的控制頂點(diǎn)對(duì)最壞點(diǎn)的影響程度遠(yuǎn)小于主控制頂點(diǎn)，導(dǎo)致調(diào)整全部控制頂點(diǎn)的光順策略也可能得不到理想的光順結(jié)果.因此，本文同時(shí)調(diào)整主控制頂點(diǎn)和副控制頂點(diǎn)位置對(duì)最壞點(diǎn)進(jìn)行光順，這樣同時(shí)調(diào)整兩個(gè)或者三個(gè)控制頂點(diǎn)的位置可以大大提升曲線光順的效率，縮短光順時(shí)間.

2 光順重構(gòu)算法設(shè)計(jì)

針對(duì)上文分析得出的導(dǎo)致重構(gòu)曲線光順性差的3個(gè)原因（曲率壞點(diǎn);曲率壞區(qū);曲率變化劇烈），分別通過式③和④，以及曲率符號(hào)變化情況，找出曲線光順性差的點(diǎn)或區(qū)域，在光順過程中不斷調(diào)整影響該點(diǎn)或區(qū)域的多個(gè)控制頂點(diǎn)位置，找出控制點(diǎn)位置最優(yōu)解，完成曲線光順.由于PSO算法采用實(shí)數(shù)編碼，相對(duì)于其他智能算法來說，PSO算法更易于操作和實(shí)現(xiàn)，且算法中的參數(shù)可以根據(jù)經(jīng)驗(yàn)值來設(shè)定，不需要過多的人為干預(yù).因此，本文基于PSO進(jìn)行光順?biāo)惴ㄔO(shè)計(jì).

2.1 PSO算法

PSO算法[19]，簡單來說，就是模擬一群鳥在一片區(qū)域內(nèi)找尋唯一一塊食物的過程，給出了每只鳥到食物的距離，搜索與食物距離最近的那只鳥附近的區(qū)域，即為這群鳥找到食物的最佳辦法.該算法將優(yōu)化問題可能的解都表示成搜索空間中不計(jì)重量和體積、具有一定飛行速度的微粒，相當(dāng)于區(qū)域中飛行的鳥，優(yōu)化問題的最優(yōu)解就是區(qū)域中唯一的那塊食物，由目標(biāo)函數(shù)計(jì)算得到的適應(yīng)度值就是鳥到食物的距離.

PSO算法流程[20]如下：

步驟1 初始化種群，設(shè)定初始位置和速度.

步驟2 計(jì)算每個(gè)微粒的適應(yīng)度，并初始化pbest和gbest.

步驟3 按照式⑤和式⑥更新微粒的速度和位置.

步驟4 計(jì)算更新后各微粒的適應(yīng)度，更新pbest和gbest.

步驟5 如果滿足終止條件（最大迭代次數(shù)或滿意的適應(yīng)度），則結(jié)束，輸出當(dāng)前最優(yōu)解;否則，返回步驟3.

計(jì)算各點(diǎn)離曲線的最近距離，再取其最大值作為曲線的誤差，考慮到光順進(jìn)程會(huì)增大曲線的誤差，可以將給定的誤差精度作為PSO算法的約束條件，限定種群中微粒的飛行空間，能確保光順后輸出的曲線滿足誤差精度要求，而誤差精度可以根據(jù)設(shè)計(jì)的需求進(jìn)行設(shè)定.

2.2 光順性量化標(biāo)準(zhǔn)

通過曲率圖只能得到曲線光順性的定性評(píng)價(jià)，為了更好地進(jìn)行數(shù)據(jù)分析，還需要對(duì)曲線光順性進(jìn)行量化評(píng)價(jià).通常是將能量函數(shù)的值作為評(píng)判光順性的標(biāo)準(zhǔn)，但是這種方法不一定能對(duì)曲線整體的光順性給出準(zhǔn)確的評(píng)價(jià)，例如半徑相同但圓心角不同的兩條弧，其光順程度相當(dāng)，但圓心角大的弧能量更大.因此，本文基于光順性指標(biāo)Δdi量化曲線的光順性，設(shè)光順性度量為.

其中，ΔD表示曲線上所有內(nèi)部數(shù)據(jù)點(diǎn)Δdi之和，將ΔD作為PSO算法的適應(yīng)度函數(shù)進(jìn)行種群的更新.隨著曲線光順次數(shù)的增多，ΔD一般會(huì)減少直至不再變化，中間偶爾會(huì)出現(xiàn)增大再減少的情況.為避免過早收斂，現(xiàn)在一般的做法是連續(xù)記錄4次曲線光順后的ΔD值，當(dāng)其中最小值與最大值的比值大于某個(gè)固定值時(shí)停止光順進(jìn)程.在本文算法中，根據(jù)參考文獻(xiàn)[2]和經(jīng)驗(yàn)，設(shè)定固定值為0.995.

2.3 光順重構(gòu)算法流程

針對(duì)前述影響曲線光順性的3個(gè)原因，分別給出對(duì)應(yīng)的曲率光順方法：曲率壞點(diǎn)光順?biāo)惴?、曲率壞區(qū)光順?biāo)惴ê颓首兓忭標(biāo)惴?考慮實(shí)現(xiàn)這3種光順方法的先后順序?qū)η€完成光順進(jìn)程效率和質(zhì)量的影響，本文光順重構(gòu)算法的流程如圖1所示.

光順重構(gòu)算法具體步驟如下.

步驟1 對(duì)于給定數(shù)據(jù)點(diǎn)，首先利用最小二乘法重構(gòu)得到一條3次B樣條曲線，及其給出的一系列控制頂點(diǎn)Pi，計(jì)算曲線上各點(diǎn)的曲率k.

步驟2 通過式③找出曲線上的所有壞點(diǎn)，構(gòu)造相應(yīng)的主控制頂點(diǎn)序列{Pj1，Pj2，…，Pjn}.

步驟3 將主控制頂點(diǎn)序列{Pj1，Pj2，…，Pjn}作為PSO算法的初始種群，通過迭代重新計(jì)算曲線的誤差、曲率和曲線的光順性度量ΔD.當(dāng)滿足給定的誤差且曲線無壞點(diǎn)時(shí)，輸出曲線新的控制頂點(diǎn)序列和曲線曲率k，進(jìn)入下一步，否則重復(fù)步驟3.

步驟4 確定曲線上的壞區(qū)，得到主控制頂點(diǎn)序列{Pi1，Pi2，…，Pim}

步驟5 將主控制頂點(diǎn)序列{Pi1，

作為PSO算法的初始種群，通過迭代重新計(jì)算曲線的誤差、曲率和曲線的光順性度量ΔD.當(dāng)滿足給定的誤差和曲線無壞區(qū)（曲線曲率符號(hào)相同），輸出曲線新的控制頂點(diǎn)序列曲線曲率k，否則重復(fù)步驟5.

步驟6 通過式④確定曲線上的最壞點(diǎn)，得到需要調(diào)整的控制頂點(diǎn)序列 {Pi-1，Pi，Pi+1}.

步驟7 將控制頂點(diǎn)序列{Pi-1，Pi，Pi+1}作為PSO算法的初始種群，通過迭代重新計(jì)算曲線的誤差、曲率和曲線的光順性度量ΔD.

步驟8 若滿足PSO算法終止條件，且不再滿足給定的誤差精度或達(dá)到最大迭代次數(shù)時(shí)，輸出新的控制頂點(diǎn)，記錄ΔD值，ΔD值不足4個(gè)時(shí)，返回步驟6，不少于4個(gè)時(shí)，進(jìn)入下一步;否則返回步驟7.

步驟9 檢查光順進(jìn)程的終止條件，當(dāng)連續(xù)的4個(gè)ΔD值中最小值與最大值的比值大于0.995時(shí)，停止光順進(jìn)程，輸出控制頂點(diǎn)構(gòu)造曲線;否則返回步驟6.

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

3.1 相同誤差精度光順結(jié)果與分析

為驗(yàn)證本文光順重構(gòu)算法的性能，在給定相同誤差精度（E=0.15 mm）的條件下，基于Matlab（2016b）軟件，使用傳統(tǒng)選點(diǎn)光順?biāo)惴ㄅc本文算法，對(duì)給定的數(shù)據(jù)點(diǎn)分別進(jìn)行10次光順重構(gòu)，對(duì)比這兩種算法輸出曲線的曲率梳.對(duì)某模型底部輪廓線的部分?jǐn)?shù)據(jù)點(diǎn)（431個(gè)）進(jìn)行擬合，得到的原始曲線及其原始曲率如圖2所示.

從圖2b）可以看出，原始曲線存在兩處曲率波動(dòng)較劇烈的區(qū)域，需要進(jìn)行光順處理.另外，在原始曲率的后半部分還存在曲率符號(hào)不一致的區(qū)域（圖中圈出部分），這表示原始曲線上存在多余拐點(diǎn)，需要先進(jìn)行曲率符號(hào)調(diào)整.本文提出的曲率壞點(diǎn)、壞區(qū)光順?biāo)惴ü忭樓昂蟮那蕦?duì)比見圖3.由圖3可以看出，光順之前原始曲率上的兩處壞區(qū)于光順之后都得到了調(diào)整，現(xiàn)在整條曲線的曲率符號(hào)保持一致，即曲線上不存在拐點(diǎn)，且曲線的曲率波動(dòng)也較之前有所減少.

在同等誤差精度（E=0.15 mm）的約束下，傳統(tǒng)選點(diǎn)光順?biāo)惴ê捅疚墓忭樦貥?gòu)算法的比較結(jié)果見圖4.由圖4可以看出，在原始曲率劇烈波動(dòng)的區(qū)域，本文算法的變化波動(dòng)較傳統(tǒng)選點(diǎn)光順?biāo)惴ㄒ〉枚啵冶疚乃惴ㄉ傻那€要更光順一些.將圖4中曲線尾部的第二處曲率壞區(qū)（圖中圈出部分）放大得到圖5.由圖5可以看出，經(jīng)本文算法光順后的曲線不存在曲率壞區(qū)，而采用傳統(tǒng)選點(diǎn)光順法光順后的曲線上仍存在多余的拐點(diǎn)，即存有曲率壞區(qū)，這進(jìn)一步說明本文算法的光順效果要優(yōu)于傳統(tǒng)算法.

曲線內(nèi)部數(shù)據(jù)點(diǎn)Δd值的變化情況可以反映曲率變化情況的好壞：Δd值變化越大，表示曲線的曲率變化越劇烈，曲線越不光順.選擇原始曲率劇烈波動(dòng)的第30—55個(gè)數(shù)據(jù)點(diǎn)，本文算法、原始曲率和傳統(tǒng)算法的內(nèi)部數(shù)據(jù)點(diǎn)Δd值見圖6.由圖6可以看出，本文算法和傳統(tǒng)算法光順后的曲線曲率變化率都較原曲線大幅下降，且本文算法的曲率變化更平緩.表1為傳統(tǒng)算法與本文算法的光順性評(píng)價(jià)數(shù)據(jù).由表1可知，本文算法的光順性度量ΔD值最小，表明曲率變化最平緩，雖然傳統(tǒng)算法與本文算法基于能量標(biāo)準(zhǔn)的曲率積分和十分相近，但是本文算法完成整個(gè)曲線光順過程所需次數(shù)要少于傳統(tǒng)算法.綜上說明，在同等誤差精度約束下，本文算法比傳統(tǒng)算法光順效果更好，即生成的曲線更光順，且能顯著提高曲線的光順效率.

3.2 不同誤差精度光順結(jié)果與分析

在不同誤差精度的條件下，驗(yàn)證本文光順重構(gòu)算法的光順效果.圖7是某葉片橫截面輪廓原始曲線及其原始曲率.在誤差精度分別為E=0.20 mm，E=0.15 mm，E=0.10 mm的條件下，采用本文算法對(duì)原始曲線進(jìn)行18次光順，結(jié)果如圖8所示.本文算法在不同誤差精度下的光順性評(píng)價(jià)見表2.

由圖8可見，在允許的誤差范圍內(nèi)，經(jīng)本文算法光順后的曲線都較原曲線更光順，光順后曲線的曲率變化也都較原曲線的曲率更平緩，且給定的誤差精度值越大，光順效果越好，輸出的曲線越光順.這是因?yàn)榻o定的誤差精度作為PSO算法中種群更新的約束條件，限制了種群中粒子的飛行空間，從而有效控制了算法輸出曲線的誤差.由表2可知，經(jīng)本文算法光順后的曲線誤差均處于允許的誤差范圍內(nèi)，說明本文算法實(shí)現(xiàn)了對(duì)光順后生成的曲線誤差的有效控制;較原始曲線，本文算法的光順性度量ΔD值和基于能量標(biāo)準(zhǔn)的曲率積分和更優(yōu).綜上可知，本文算法在不同誤差精度條件下都能獲得更好的光順效果，且可有效控制光順后生成曲線的曲線誤差.

4 結(jié)語

本文提出了一種基于PSO的B樣條曲線光順重構(gòu)算法.該算法提出了利用PSO算法同時(shí)調(diào)整多個(gè)控制點(diǎn)的策略，首先對(duì)曲線上曲率符號(hào)不一致的點(diǎn)和區(qū)域進(jìn)行了預(yù)處理，使得曲線上點(diǎn)的曲率符號(hào)保持一致，以避免出現(xiàn)冗余的拐點(diǎn).而后對(duì)曲率變化劇烈區(qū)域進(jìn)行光順，迭代更新生成最優(yōu)曲線.實(shí)驗(yàn)結(jié)果表明，本文算法擁有較好的光順效果，提升了光順效率，縮短了光順進(jìn)程，能很好地滿足工程上對(duì)曲線光順性的要求，且算法對(duì)生成曲線誤差的控制在工程上也將極大地降低建模工作所需耗費(fèi)的人力物力.本文算法針對(duì)的是平面B樣條曲線的光順重構(gòu)，而將其推廣到空間曲線或曲面的光順重構(gòu)，是未來工作的一部分.

參考文獻(xiàn)：

[1] 龍小平.局部能量最優(yōu)法與曲線曲面的光順[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)， 2002， 14（12）：1109.

[2] 羅衛(wèi)蘭，楊勛年，鄭建民.B樣條曲線的約束光順?biāo)惴╗J].浙江大學(xué)學(xué)報(bào)（理學(xué)版），2004，31（1）：51.

[3] 張莉，葛先玉，檀結(jié)慶.廣義B樣條曲線的節(jié)點(diǎn)去除與光順?biāo)惴╗J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)報(bào)，2016，28（4）：540.

[4] CERUTI A， LIVERANI A， CALIGIANA G.Fairing with neighbourhood LOD filtering to upgrade interactively B-Spline into Class-A curve[J].IJIDeM： International Journal on Interactive Design and Manufacturing， 2014， 8（2）：67.

[5] WANG A Z， ZHAO G， LI Y D.Fairness degree based fairness criterion and fairing algorithm[J].Applied Mathematics and Computation，2015，253：184.

[6] 王愛增，趙罡，穆國旺.基于數(shù)字化光順性指標(biāo)的NURBS曲線自適應(yīng)光順[J].計(jì)算機(jī)學(xué)報(bào)，2011，34（8）：1548.

[7] 潘洋宇，姜福祥.任意控制點(diǎn)曲線小波光順方法研究[J].機(jī)械設(shè)計(jì)，2009，26（11）：12.

[8] PAN R， YAO Z.Biorthogonal nonuniform B-spline wavelets based on a discrete norm[J].Com-puter Aided Geometric Design， 2009， 26（4）：480.

[9] 紀(jì)小剛，楊艷，薛杰.基于多分辨技術(shù)的任意控制頂點(diǎn)曲面光順[J].機(jī)械工程學(xué)報(bào)，2015，51（11）：159.

[10]ULKER E， ARSLAN A.Automatic knot adjustment using an artificial immune system for B-spline curve approximation[J].Information Sciences：An International Journal， 2009， 179（10）：1483.

[11]ZHAO X Y，YANG B，ZHANG C M，et al.Adaptive knot placement using a GMM-based continuous optimization algorithm in B-spline curve approximation[J].Computer-Aided Design， 2011， 43（6）：598.

[12]GALVEZ A， IGLESIAS A.Efficient particle swarm optimization approach for data fitting with free knot B-splines[J].Computer-Aided Design， 2011， 43（12）：1683.

[13]KANG H M， CHEN F L，LI Y S， et al.Knot calculation for spline fitting via sparse optimization[J].Computer-Aided Design， 2015， 58：179.

[14]胡良臣，壽華好.PSO求解帶法向約束的B樣條曲線逼近問題[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2016，28（9）：1443.

[15]蘇步青，劉鼎元.計(jì)算幾何[M].上海：上海科學(xué)技術(shù)出版社，1981：297.

[16]王士瑋，劉利剛，張舉勇，等.基于稀疏模型的曲線光順?biāo)惴╗J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2016，28（12）：2043.

[17]章虎冬.基于局部能量的三次B樣條曲線自動(dòng)光順?biāo)惴╗J].西安航空學(xué)院學(xué)報(bào)，2016，34（1）：79.

[18]王愛增，何川，趙罡，等.基于幾何方法的曲率單調(diào)Bézier曲線的一個(gè)充分必要準(zhǔn)則[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2019，31（9）：1617.

[19]鄭曉月.用快速收斂粒子群優(yōu)化算法解決函數(shù)優(yōu)化問題[J].輕工學(xué)報(bào)，2016，31（3）：89.

[20]李巧燕，全海燕.基于改進(jìn)粒子群的獨(dú)立分量分析算法研究[J].輕工學(xué)報(bào)，2016，31（2）：103.