洪慶飛，李亞娟，鄧重陽

(杭州電子科技大學理學院，浙江 杭州 310018)

0 引 言

圖像矢量化是將位圖轉化為矢量圖的過程。位圖色彩豐富，占據(jù)大量的存儲空間，放大時產(chǎn)生鋸齒。矢量圖主要通過直線和曲線來描述圖形，具有易于編輯、放大時不變形和占據(jù)存儲空間小等優(yōu)點，廣泛應用于logos、卡通人物等剪貼畫領域，具有巨大的市場需求。據(jù)調(diào)查，美國每年花費在圖像矢量化上的工時超過700萬小時[1]。在商業(yè)領域中，針對圖像矢量化也有大量研究，并開發(fā)出實用的商業(yè)軟件，比較著名的有Adobe Illustrator，Corel CorelDRAW和Vector Magic等。這些軟件大多只是針對某一特定領域，且存在一些缺點，如抗噪音效果比較差和精度不夠等。在典型的矢量化過程中，輪廓擬合引入特定的先驗知識，結合這些先驗知識來解決模糊問題，且通過進一步約束解空間來獲得更好的矢量化結果。但是，先驗知識方面的學術研究較少，文獻[1]中提出的曲線先驗知識既不能直接應用于輪廓擬合，也不能專門應用于矢量化。文獻[2]采用哈爾小波和先驗能量優(yōu)化貝塞爾擬合曲線的輪廓，得到很好的效果。圖像矢量化研究中比較常見的方法是提取圖像的輪廓數(shù)據(jù)點后使用樣條函數(shù)進行擬合。B樣條曲線具有高階可導和優(yōu)良的局部性質(zhì)，在輪廓擬合中應用廣泛。齊東旭等[3]研究了非均勻3次B樣條曲線，Deng等[4]提出了最小二乘漸進迭代逼近(Least Square Progressive and Iterative Approximation，LSPIA)，對規(guī)則的輪廓數(shù)據(jù)點進行擬合，得到較好的矢量圖輪廓。李莎莎等[5]提出數(shù)據(jù)點加權的最小二乘漸進迭代逼近算法(Data-Weighted Least Square Progressive and Iterative Approximation，DW-LSPIA)，使得矢量圖輪廓具有保形性。常清俊等[6]提出分塊高斯-賽德爾迭代曲線擬合方法，節(jié)省了大量計算時間。在LSPIA的基礎上，本文引入長度優(yōu)先、避免自相交和避免對尖角光滑處理這3種先驗知識，通過優(yōu)化非均勻B樣條控制頂點消除不合理現(xiàn)象并確保由此產(chǎn)生的輪廓是合理和美觀的。

1 先驗能量的構造

LSPIA將擬合曲線上數(shù)據(jù)點和對應點之間的誤差定義為控制點的誤差向量，通過最小二乘算法調(diào)整非均勻B樣條控制頂點來構造擬合曲線。LSPIA算法應用非均勻B樣條擬合低分辨率圖像輪廓時，可能會出現(xiàn)以下不合理輪廓結果，分別為曲線扭曲、自相交、光滑角。這3種結果在合理的矢量圖中很少出現(xiàn)，以自相交為例，剪貼畫庫[7]的矢量圖中的輪廓很少有自相交現(xiàn)象。從美學方面來講，這些結果都被認為是不合理的。本文在LSPIA算法基礎上引入長度優(yōu)先(本文簡稱LPT)、避免自相交(本文簡稱SPT)和避免對尖角光滑處理3種先驗知識，構造了ELPT，ESPT能量函數(shù)和分段擬合來調(diào)整LSPIA中非均勻B樣條控制頂點，進而獲得合理矢量圖輪廓。

1.1 先驗能量的幾何參數(shù)

(1)

(2)

式中，j∈[1,m]，m為B樣條曲線的數(shù)量。(xi,yi)為LSPIA方法獲得的控制頂點坐標，k為B樣條基函數(shù)的次數(shù)，取k=3，Ni,3(u)(i=0,…,n)為k次規(guī)范B樣條基函數(shù)。非遞減的參數(shù)u的序列U∶u0≤u1≤…≤un+k+1為節(jié)點矢量。

1.2 曲線長度優(yōu)先

根據(jù)經(jīng)驗可知，除非有強有力的證據(jù)表明曲線應該收縮或扭曲，矢量圖的輪廓曲線應盡可能伸展[2]。當矢量圖的輪廓出現(xiàn)高度扭曲時，如果沒有證據(jù)支持這種扭曲，就需要消除這種扭曲現(xiàn)象。使用這種先驗知識，定義ELPT能量函數(shù)，通過非線性優(yōu)化矢量圖輪廓長度，保證曲線盡可能伸展。

(3)

1.3 自相交

圖1展示發(fā)生自相交的矢量圖輪廓。圖1中，交點為自相交點，每個這樣的交點把輪廓分為2個部分。較短部分為自相交部分，通過計算這部分長度來獲得自相交發(fā)生的程度。

圖1 自相交圖[7]

一種直觀的避免自相交的方法是通過強化一組高度耦合的非線性不等式約束，使用原對偶內(nèi)點法[8]進行優(yōu)化，這種方法需要花費大量的計算時間，并不適合矢量圖輪廓的優(yōu)化。本文通過對自相交程度進行分析估量，采用一種有效的正則化方法來避免產(chǎn)生自相交的矢量圖輪廓，本文方法的主要優(yōu)點是消除了自相交現(xiàn)象并節(jié)省了計算時間。

定義ESPT為能量函數(shù)，通過最小化自相交部分長度占矢量圖輪廓長度的比例來消除自相交現(xiàn)象。

(4)

式中，M={(d1,d2)|d1

(5)

自相交部分的長度越接近矢量圖輪廓其他部分的長度，自相交現(xiàn)象越嚴重，能量函數(shù)越大。當沒有自相交時，ESPT為0。

1.4 避免光滑角

由于B樣條曲線具有高階可導性質(zhì)，使用LSPIA方法擬合矢量圖的輪廓時，圖像原本存在的尖角會被非均勻三次B樣條擬合成光滑角?？梢圆捎靡韵路椒▉斫鉀Q這個問題。

(6)

然后，滿足條件(6)的3個數(shù)據(jù)點在原始矢量圖輪廓中組成的角是尖角，B樣條曲線具有高階可導性，非均勻B樣條進行擬合時自動進行光滑處理。選取尖角處數(shù)據(jù)點作為分段擬合的起始點。最后，使用LSPIA方法對輪廓進行分段擬合從而得到圖像原本存在的尖角。

2 實驗結果與分析

圖像矢量化過程中，提取的輪廓點列是規(guī)則的，但在曲線擬合過程中出現(xiàn)不合理輪廓，如圖2(a)所示。輸入的光柵圖嘈雜或者低分辨率，提取的輪廓數(shù)據(jù)點不規(guī)則，導致出現(xiàn)不合理輪廓，如圖3(a)圓圈標記部分所示。

本文選取文獻[9]提出的非線性優(yōu)化算法L-BFGS對能量函數(shù)進行非線性優(yōu)化，得到新的B樣條曲線控制頂點，最終消除矢量圖輪廓曲線扭曲和自相交現(xiàn)象，結果如圖2(b)和圖3(c)所示。

圖2(a)是LSPA方法擬合結果，曲線擬合過程中出現(xiàn)扭曲，對能量函數(shù)進行非線性優(yōu)化，把優(yōu)化后得到的控制頂點作為LSPIA方法的初始控制頂點進行二次擬合得到圖2(b)。圖3(b)是使用LSPIA方法對圖3(a)陰影部分不規(guī)則輪廓數(shù)據(jù)點的擬合，出現(xiàn)明顯扭曲現(xiàn)象。對能量函數(shù)進行非線性優(yōu)化得到圖3(c)。通過圖2和圖3可以看出，與LSPIA方法相比，經(jīng)過能量函數(shù)優(yōu)化處理后，矢量圖輪廓扭曲部分變成了光滑曲線。

圖2 ELPT先驗能量處理效果

圖3 Elpt先驗能量處理效果

對發(fā)生自相交的矢量圖輪廓的非線性優(yōu)化結果如圖4所示。圖4(c)是對圖4(a)陰影部分不規(guī)則輪廓數(shù)據(jù)點的擬合。使用L-BFGS算法對能量函數(shù)進行非線性優(yōu)化，得到新的B樣條控制頂點，優(yōu)化后的矢量圖輪廓沒有自相交現(xiàn)象，如圖4(c)所示。

圖4 先驗能量對自相交處理效果圖

圖5 光滑角處理效果圖

3 結束語

在LSPIA方法的基礎之上，本文引入基于先驗知識的能量優(yōu)化算法，用于處理一些不能被自動化方法精確矢量化的剪貼畫圖像，很好地解決了使用B樣條曲線進行矢量圖輪廓擬合時出現(xiàn)的曲線扭曲、自相交等缺陷。下一步將探索更多的先驗知識，更好地解決矢量化過程中產(chǎn)生的各種問題，以獲得效果更好的矢量圖。