[發明專利]一種基于遺傳粒子群算法的NURBS曲線擬合方法

在審

• 申請號: 202010554815.X
• 申請日: 2020-06-17
• 公開（公告）號: CN111738397A
• 公開（公告）日: 2020-10-02
• 發明（設計）人: 李軒宇;張兆軍;許釗雄
• 申請（專利權）人: 江蘇師范大學
• 主分類號: G06N3/00
• 分類號: G06N3/00;G06F17/16;G06F17/10;G06F16/904
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于遺傳粒子群算法的NURBS曲線擬合方法，其特征在于，包括步驟：

S1：輸入待擬合數據d_i及其對應法向；

S2：數據點參數化，以及建立有效的適應度函數；

S3：設置遺傳粒子群算法的相關參數，包括種群規模pop，終止條件，終止條件即最大迭代次數maxgen；

S4：初始化粒子位置及速度，這里每一個粒子代表一個節點向量；

S5：根據粒子的位置，通過最小二乘法計算控制頂點，計算每個粒子的適應度值；

S6：對每個粒子，比較其當前位置和它經歷過的最好位置pbest，如果當前位置更好，則更新個體極值pbest；

S7：對每個粒子，比較其當前位置和群體中所有粒子所經歷過的最好位置gbest，如果這個粒子的位置更好，則更新全局極值gbest；

S8：更新粒子的位置和速度；

S9：對子代中的優秀個體進行交叉和變異操作，得到新的子代個體；

S10:判斷迭代終止的條件,如果滿足條件,則輸出最優節點向量和控制頂點并計算重構曲線,否則轉到步驟S5。

2.根據權利要求1所述的一種基于遺傳粒子群算法的NURBS曲線擬合方法，其特征在于，所述步驟S1中，數據擬合的數學模型如下：

一條p次B樣條曲線可以表示為：

其中，p表示B樣條次數，{P_i},i＝0,1,K,n是曲線的控制頂點，N_i,p(u)表示p次B樣條在節點向量U上的基函數，其定義由de Boor-Cox遞推公式給出：

由于公式(3)中可能出現分子、分母同時為0的情況，因此規定u_i為節點向量U{u_i},i＝0,1,K,n+p+1中的元素，u的取值范圍除非另外說明，通常取[0,1]；

給定m+1個數據點Q₀,Q₁,L,Q_m，在p≥1的前提下，讓逼近曲線經過首末兩點需要滿足的條件是：

Q₀＝C(0),Q_m＝C(1) (4)

對其余m-1個離散數據點Q_k,k＝1,K,m-1進行最小二乘擬合，確保曲線誤差最小即公式(5)最小：

該公式是最小二乘法近似擬合曲線的數學模型，這條曲線并不是精確地通過所有數據點，為了求解這條近似曲線，令

構造函數并推導如下：

函數f是一個關于變量P₁,K,P_n-1的標量函數，為了得到f的最小值，需要對其求偏導：

令偏導數為0，可得：

當l＝1,2,K,n-1時，上式成立，可得線性方程組：

N^TR＝(N^TN)P (10)

為了保證方程有且僅有唯一的最小二乘解，對矩陣N求Moore-Penrose廣義逆；對于帶法向約束的問題，只需在原有模型的基礎上添加法向約束條件如下：

其中d_i表示數據點對應的參數值，法向約束的幾何意義為參數化后的數據點在曲線上的切線矢量與對應的法向約束矢量l_i垂直。

3.根據權利要求1所述的一種基于遺傳粒子群算法的NURBS曲線擬合方法，其特征在于，所述步驟S2中，數據點的參數化方式為向心參數化。

4.根據權利要求1所述的一種基于遺傳粒子群算法的NURBS曲線擬合方法，其特征在于，所述步驟S4中，粒子的初始化方式為隨機初始化。