基于遺傳算法的以線段和圓弧為基元的曲線擬合

1、第 14卷 第 2期 2002年 2月計算機輔助設(shè)計與圖形學(xué)學(xué)報JOU RNAL O F COM PU T ER 2A I D ED D ES IGN &COM PU T ER GRA PH I CSV o l . 14,N o. 2Feb . , 2002基于遺傳算法的以線段和圓弧為基元的曲線擬合張習(xí)文 1 李佐1 蔡士杰1歐宗瑛21 (南京大學(xué)計算機軟件新技術(shù)國家重點實驗室南京 2100932(大連理工大學(xué)機械工程學(xué)院 CAD &CG 研究所大連 116024摘 要 采用線段和圓弧作逼近基元是數(shù)字曲線擬合中的一個難點 , 文中給出一種基于改進遺傳算法的擬合方法 . 通過對點列進行二進制編碼

2、 , 以擬合段數(shù)較少和擬合誤差較小為優(yōu)化目標(biāo) , 變異概率和交叉概率自適應(yīng)生成 , 并根 據(jù)相關(guān)知識控制分界點間隙 , 所得最優(yōu)解中值為 1的基因?qū)?yīng)數(shù)字曲線的分界點 . 對線段與圓弧相交和相切以及具 有噪聲等多種情況進行檢測 , 可同時提取尖點和切點 , 還可得到逼近基元及其之間關(guān)系 , 較好地解決了用線段和圓 弧擬合曲線問題 .關(guān)鍵詞 遺傳算法 , 曲線擬合 , 分界點檢測 中圖法分類號 T P 391. 72Segm en ti ng Planar Curves i n to Stra ight C Segm en tsUsi ng 1L i Cai Sh ijie 1 O u Zong

3、ying21(S te K tory of S of t w a re T echnology , N anj ing U n iversity , N anj ing 2100932(CA D S of M echan ica l E ng ineering , D a lian U n iversity of T echnology , D a lian 116024Abstract D em arcati on po ints from a curve w ith least num ber of segm ents (lines and arcs are extracted , and

4、 each of them can be fitted into a line o r arc w ith least erro r . Ch romo som es are encoded into binary strings . M utati on p robabilities and cro ssover p robabilities are calculated adap tively . T he gap s betw een dem arcati on po ints are restrict 2ed . Po ints of a curve co rresponding to

5、 genes of a ch romo som e w h ich are 1s , are dem arcati on ones. T he algo rithm can deal w ith m any cases including a line is intersecting o r tangent to an arc , an arc is tangent to an arc , and som e po ints are no isy ones , and can detect cusp and tangent po ints . T he m ethod can rep rese

6、nt w ell a curve w ith lines and arcs , the algo rithm is effective and robust .Key words genetic algo rithm , curve fitting , dem arcati on po int detecti on原稿收到日期 :2000212213; 修改稿收到日期 :2001207230. 張習(xí)文 , 男 , 1971年生 , 博士后研究人員 , 主要研究方向為人工智能 、 模式識別和 圖像理解 . 李佐 , 男 , 1967年生 , 博士 , 主要研究方向為模式識別和文檔識別與理解 .

7、蔡士杰 , 男 , 1944年生 , 教授 , 博士生導(dǎo)師 , 主要研究方向 為 CAD &CG 、 人機交互 、 文檔分析和理解等 . 歐宗瑛 , 男 , 1936年生 , 教授 , 博士生導(dǎo)師 , 主要研究方向為 CAD 、 分形幾何 、 小波變換 、 人工智能 和圖像理解等 .1引言在計算機視覺和模式識別中 , 數(shù)字曲線擬合是一個重點 和難點 1. 數(shù)字曲線通常可看作由線段和圓弧組成 , 各個組 成圖元之間的連接點稱為分界點 . 分界點包括尖點 (線段與 線段和圓弧的交點 , 圓弧與圓弧的交點 和切點 (圓弧與線段 和圓弧的切點 . 分界點是曲線的基本特征 , 為曲線的進一步 識別提供基

8、礎(chǔ)信息 .實際提取的數(shù)字曲線難免存在噪聲 , 而且具有多種逼近基元 (線段 、 圓弧和橢圓弧等 , 它們之間還會相交或相切 . 現(xiàn) 有分界點檢測方法對這些問題缺乏綜合考慮 224, 已有的基 于遺傳算法提取分界點的方法只是以線段為逼近基元 526. 本文以線段和圓弧為逼近基元 , 對遺傳算法進行改進 , 實現(xiàn) 數(shù)字曲線擬合 .2相關(guān)工作回顧數(shù)字曲線擬合采用基本圖元 (線段 、 圓弧和橢圓弧等 來擬合點列 , 實現(xiàn)方法很多 , 可以分為兩類 :一是先抽取基元之 間的分界點 , 即分割優(yōu)先的方法 ; 二是先抽取輪廓上的基元 , 即恢復(fù)優(yōu)先的方法 . 分界點是人類認知形狀的重要內(nèi)容 , 可 以用來描

9、述 、 識別和匹配形狀 . 經(jīng)過多年研究 , 已經(jīng)提出多種 分界點檢測方法 :(1 曲率計算 2. 根據(jù)曲率 (夾角 來提取分界點 , 計算 量較小 , 但抗噪性差 .(2 小波變換 7. 基于小波變換檢測角點 , 抗干擾能力 強 , 但計算較為復(fù)雜 .(3 模糊推理 1. 根據(jù)人對局部圖形特征的認知 , 用模 糊推理來檢測角點 .(4 優(yōu)化方法 526. 基于遺傳算法來擬合曲線 , 但只是進 行線性擬合 .曲線擬合可以采用線段 、 圓弧和橢圓弧等多種基元 . 從 采用的基元來看 , 曲線擬合方法可分為三種 :(1 線段 326. 采用多邊形逼近 , 如果需要得到圓弧的表 達 , 還需對線段進

10、行圓弧擬合 .(2 線段和圓弧 8. 先自適應(yīng)光順曲線切線方向 , 然后 對其求導(dǎo) , 從中取出峰值點 , 得到曲線尖點 ; 再用動態(tài)聚焦擬 合技術(shù)粗略定位切點 , 最后要精確調(diào)整 .(3 線段和橢圓弧 9. , 作精確分割 , .3遺傳算法 (m , GA 簡介Ho lland 在 1975年首次提出 GA 10. 經(jīng)過多年研究和應(yīng) 用 , GA 吸引了大批的研究者 , 已經(jīng)推廣到優(yōu)化 、 搜索和機器 學(xué)習(xí)等諸多方面 , 奠定了堅實的理論基礎(chǔ) , 具有良好的應(yīng)用 前景 . GA 是一種嶄新的全局優(yōu)化算法 , 借用生物遺傳學(xué)觀 點 , 體現(xiàn)自然界中 “物競天擇 、 適者生存” 的進化過程 ,

11、通過選 擇 、 交叉和變異等作用機制 , 使問題的解在競爭中得以改進 , 實現(xiàn)各個染色體的適應(yīng)性提高 , 以求得問題的滿意解 .GA 把適者生存與結(jié)構(gòu)化和隨機化的信息交換結(jié)合在 一起 , 形成一種嶄新的求解算法 , 同基于微分 、 枚舉和隨機等 傳統(tǒng)優(yōu)化方法相比 , 主要有 4個方面的不同 :(1 直接使用問題解集編碼 , 而不是解集本身 .(2 從解組成的種群中搜索最優(yōu)解 , 而不是單個解 .(3 使用適應(yīng)度函數(shù)指導(dǎo)搜索 , 而不考慮它的數(shù)學(xué)特性 .(4 概率地使用三種遺傳操作 , 而不用確定的狀態(tài)轉(zhuǎn)移 規(guī)則 .GA 具有多種運行方式 , 基本的實現(xiàn)過程可概括為 :(1 隨機初始化種群 X

12、(0 =x 1, x 2, , x n .(2 對種群迭代執(zhí)行遺傳操作 , 直到滿足運行結(jié)束條件 為 止 . 計算當(dāng)前種群 X (t 中每個染色體 x i 的適應(yīng)度 F it (x i , 應(yīng)用下述操作產(chǎn)生新的種群 .選擇 . 把現(xiàn)有染色體選擇到新一代種群中 .交叉 . 重組兩個染色體 , 產(chǎn)生兩個新的染色體 .變異 . 改變?nèi)旧w某個基因 , 產(chǎn)生一個新的染色體 . (3 當(dāng)滿足運行結(jié)束條件時 , 后代中適應(yīng)度最高的染色 體為問題的滿意解 .GA 提高染色體適應(yīng)度和產(chǎn)生全局最優(yōu)解主要是通過 遺傳操作來實現(xiàn) , 常用遺傳算子為 :a . 選擇 . 從種群中按某一選擇概率 P s 選擇染色體 ,

13、 染 色體 x i 被選擇的概率與其適應(yīng)度成正比 .b . 交叉 . 將按交叉概率 P c 選擇的兩個染色體進行交 叉 , 生成兩個新的染色體 . 交叉是 GA 的主要搜索手段 , 有單 點 、 兩點和均勻等多種交叉方式 .c . 變異 . 將被選中的染色體的各個基因按變異概率 P m 進行變異 , 生成新的染色體 . 變異是 GA 跳出局部域?qū)で笕?局最優(yōu)解的主要手段 .4采用線段和圓弧為基元的擬合算法本文采用線段和圓弧作為逼近基元 , 對線段與圓弧相連 和相切等情況進行研究 . , 得到點列 , 設(shè)共有 N 個點 , 記為 P =p (, i -1 , p (i , p (i +1 , ,

14、 (N ,p (i +(i , p (i -1 是 p (i . 遺傳算法(1. 點分為分界點和連續(xù)點兩種 , 采用二進 , 當(dāng)點 i 為分界點時 , 染色體基因為 1; 否則為 0. 在曲 線擬合中 , 連續(xù)和較近 (本文取 15個象素 的兩個分界點是 不存在的 , 要稀疏化 . 在變異和交叉時 , 進行稀疏處理 .(2 適應(yīng)函數(shù) . 對染色體的每段進行直線和圓擬合 11, 取兩個擬合誤差中較小的一個誤差作為該段的擬合誤差 . 設(shè) 染色體中所有段的擬合誤差之和為 E rr (i , 設(shè) S n 為線段和 圓弧的段數(shù) , m 為調(diào)整系數(shù) , 調(diào)整擬合誤差和段數(shù)的作用 , 則染色體 i 的適應(yīng)函

15、數(shù)為 5F it (i =E rr (i S n m,其中 m =0. 5, 可以根據(jù)需要進行修改 .(3 算法的控制參數(shù)和變量 :染色體長度 L . 點的總個數(shù) (N .種群規(guī)模 M . 點總個數(shù)的一半 (N 2 .選擇概率 P s . 設(shè)染色體 j 的選擇概率為其適應(yīng)度占 種群適應(yīng)度總和的百分比 , 則染色體 j 選擇概率定義為 P s (j = Ni =1F it (i .交叉概率 P c . 根據(jù)選擇的兩個染色體之間的差距而 確定 5, 差距越大 , P c 越大 ; 反之 , P c 越小 . 設(shè) Gen (i , l 和 Gen (j , l 是被選擇的兩個染色體 i 和 j 上的

16、基因 l (l =1, , L , 染色體之間的距離為 D is ij =Ll =1Gen (i , l -Gen (j , l , 則染色體 i 和 j 的交叉概率為P c (i , j =1+e -D is ij.變異概率 P m . P m 隨適應(yīng)度自動改變 12, 當(dāng)種群染色 體適應(yīng)度趨于一致時 , P m 增加 ; 反之 , P m 減小 . 設(shè)染色體 i 的適應(yīng)度為 F it (i , 種群的最大適應(yīng)度為 F it m ax , 平均適應(yīng)度 5412期 張習(xí)文等 :基于遺傳算法的以線段和圓弧為基元的曲線擬合為 F it . 則染色體 i 的變異概率為P m = k F it m a

17、x -F it, if F it (i F it k , else,其中 k =0. 5, 可以根據(jù)需要進行修改 .(4 結(jié)束條件 . 迭代的結(jié)束條件是連續(xù) 5代最優(yōu)染色體 適應(yīng)度沒有改變 . 這個數(shù)據(jù)用戶也可根據(jù)需要交互輸入 . 在設(shè)定上述參數(shù)后 , 算法運行步驟如下 :Step 1. 初始化種群 . 隨機選取分界點 , 按照染色體長度生成染 色體 , 并進行稀疏化 , 按照種群規(guī)模生成第一代種群 .Step 2. 迭代運行下列步驟 , 直到結(jié)束條件滿足 .(A 計算每代種群染色體的適應(yīng)度 .(B 采用輪盤式來選擇染色體 , 應(yīng)用下列算子進行遺傳操作 : (i 選擇 . 最優(yōu)染色體直接復(fù)制到

18、下一代中 , 這可保存上 一代中最優(yōu)染色體 , 避免丟失可能的最優(yōu)解 .(ii 交叉 . 隨機選定一個交叉點和相應(yīng)的交叉長度 , 重組 兩個染色體的子串 , 生成兩個新的染色體 , 交叉時進行稀疏限制 . 對 交叉后的后代染色體還要和父代染色體進行適應(yīng)度比較 , 如果高于 父代適應(yīng)度 , 則復(fù)制到新的一代中 ; 否則 , 將父代染色體直接復(fù)制到 新的一代中 , 以保證種群進化 6.(iii 變異 . 隨機選定一個變異點 , 改變?nèi)旧w的某個基 因 , 增刪分界點 , 生成一個新的染色體 , .應(yīng)度 , 則復(fù)制到新的一代中 ; 否則 ,代中 , 6Step 3. .在最優(yōu)染色體中 , 的基因?qū)?yīng)

19、曲線的分界點 . 分界 點之間的圖形是線段或圓弧 . 圖形類型可從各段最小擬合誤 差對應(yīng)的圖形來獲取 . 如果某段圖形的線段擬合誤差小于圓 的擬合誤差 , 則該段圖形就是線段 ; 否則 , 該段圖形就是圓弧 . 這些圖形之間的關(guān)系可能是相交或相切 , 圖形之間的關(guān) 系以及分界點類型可以通過下列規(guī)則來確定 :(1 如果相鄰兩個圖形都是線段 , 則它們是線段與線段 的相交 , 分界點是線段與線段相交的尖點 .(2 如果相鄰兩個圖形是圓弧 , 兩個圓弧的圓心距離等 于兩個圓弧的半徑之和 (差 , 則它們是圓弧和圓弧的外切 (內(nèi)切 , 分界點是圓弧和圓弧的外 (內(nèi) 切點 ; 否則 , 為圓弧和 圓弧的

20、相交 , 分界點是圓弧和圓弧的交點 .(3 如果相鄰兩個圖形一個是線段 , 而另一個是圓弧 , 圓弧圓心到線段的距離等于圓弧的半徑 , 則它們是圓弧和線 段的相切 , 分界點是圓弧和線段的切點 ; 否則 , 為圓弧和線段 的相交 , 分界點是圓弧和線段的交點 .5分界點提取性能分析圖 1a 是用來驗證本文算法的測試圖像 , 圖 1b 是它的 骨架 . 它共有 736個點 . 該曲線包括了線段與線段和圓弧的 相交 、 圓弧與線段和圓弧的相交和相切 , 有的邊界點有噪聲 干擾 .根據(jù)數(shù)字曲線的點數(shù) , 設(shè)染色體長度為 736, 種群規(guī)模 為 368, 初始種群的最優(yōu)染色體如圖 2a 所示 , 運行

21、到 15代 后適應(yīng)度連續(xù) 5代沒有改進 , 認為收斂 , 圖 2b 為輸出結(jié)果 . 從圖 2b 可以看出 , 提取的特征點定位較為準(zhǔn)確 .對圖 1進行基于遺傳算法的線性擬合 , 結(jié)果如圖 4所示 . 對數(shù)字曲線中的尖點提取得較好 , 但對切點則難以提取 , 提取 的分界點有的既不是尖點 , 也不是切點 , 還需進一步處理 .表 1給出本文算法與已有 4種數(shù)字曲線擬合算法的性 能比較 .641計算機輔助設(shè)計與圖形學(xué)學(xué)報 2002年表 1幾種數(shù)字曲線擬合方法的性能比較性能方法 計算曲率法 小波變換法 模糊推理法 線性擬合法 (GA 本文方法 提取的分界點 尖點和切點 尖點和切點 尖點和切點 尖點

22、尖點和切點 誤識點 較少 較少 較少 較多 較少 漏識點 較少 較少 較少 較多 較少 計算量 較小 較大 較小 較小 較小 抗噪性 較差 較強 較強 較強 較強6結(jié)束語本文以線段和圓弧為逼近基元 , 研究基于改進遺傳算法 的曲線擬合 , 以較少線段和圓弧與較小逼近誤差為優(yōu)化目 標(biāo) . 實現(xiàn)遺傳算法時 , 圍繞著提高算法自適應(yīng)性 , 改進了變異 和交叉操作 、 自適應(yīng)生成變異概率和交叉概率 . 收斂速度明顯 加快 , 計算時間大大縮短 , 而且取得了較好的擬合效果 .曲線采用線段和圓弧來逼近 , 不但可以提高表達基元的 層次 , 還可增強逼近質(zhì)量 . 本文所給算法已在 PC 上采用 V i 2

23、 sual C +編程實現(xiàn) . 本文算法具有較強的基元提取能力 , 為 識別圖形和文字的骨架表達等提供了一種較好的方法 . 遺傳算法的曲線擬合還應(yīng)進一步完善 , , 計算量 .1L iL iyuan , Chen W ennan . Co rner detecti on and interp retati on on p lanar curves using fuzzy reasoning J . IEEE T ransac 2 ti ons on Pattern A nalysis M ach ine Intelligence , 1999, 21 (11 :120412102Zhang W

24、 enjing , Xu X iaom ing , D ing Guo jun , et a l . A p 2 p roach to extract feature po ints on boundary based on curva 2 ture J . Journal of Shanghai J iao tong U niversity , 1999, 33 (5 :592595(in Ch inese (張文景 , 許曉鳴 , 丁國駿 , 等 . 一種基于曲率提取輪廓特征點 的方法 J. 上海交通大學(xué)學(xué)報 , 1999, 33(5 :592595 3Zhou H ui, L i T a

25、o, X ing Q ijiang, et a l . Identificati on and segm entati on of digital curves J . Journal of D alian U niver 2 sity of T echno logy , 1997, 37(5 :576580(in Ch inese (周輝 , 李濤 , 邢啟江 , 等 . 數(shù)字曲線的線性逼近和分段識 別 J . 大連理工大學(xué)學(xué)報 , 1997, 37(5 :5765804W ang M ingjiang , T ang Pushan . A p iecew ise linear app ro

26、xi 2 m ati on based on vecto r slope J . Journal of Softw are , 1999, 10(2 :165169(in Ch inese (王明江 , 唐璞山 . 基于矢量斜率的分段線性擬合 J . 軟件 學(xué)報 , 1999, 10(2 :1651695Guo Zihua , Zhuang Zhenquan . M ap vecto rizati on algo rithm based on Gas J . Journal of Ch ina U niversity of Science and T echno logy , 1998, 28

27、(4 :476481(in Ch inese (郭子華 , 莊鎮(zhèn)泉 . 基于遺傳算法的地圖矢量化算法 J . 中國 科學(xué)技術(shù)大學(xué)學(xué)報 , 1998, 28(4 :4764816H uang Shuch ien , Sun Yungnien . Po lygonal app roxi m ati on using genetic algo rithm s J . Pattern R ecogniti on , 1999, 32 (8 :140914207W ang Zhan , H uang Fukan , J ei , et a l . M ultiscale w avelet detecti

28、 on J . Journal of of D T echno logy , 1999, 21(2 : 49(, , 萬建偉 , 等 . 基于多尺度小波變換的二維圖 像角點檢測技術(shù) J. 國防科技大學(xué)學(xué)報 , 1999, 21(2 :46 498Robert Bergevin , M arielle M okh tari . M ultiscale contour segm entati on and app roxi m ati on :A n algo rithm based on the geom etry of regular inscribed po lygons J . Computer V isi on and I m age U nderst