一種基于偏微分方程的數(shù)值解的圖像矢量化方法

(杭州電子科技大學(xué)圖形圖像研究所，浙江 杭州310018)

0 引 言

計(jì)算機(jī)中的圖像分為兩大類:柵格圖像和矢量圖像。矢量圖像用少量的點(diǎn)、直線、多邊形等幾何圖元表示，所占存儲(chǔ)空間小，并且易于對(duì)其進(jìn)行操作[1]，在現(xiàn)代計(jì)算機(jī)系統(tǒng)中得到廣泛的應(yīng)用。圖像矢量化方法有很多，其中比較經(jīng)典的矢量化方法有基于優(yōu)化梯度網(wǎng)格的圖像矢量化[2]，以及其改進(jìn)方法一種拓?fù)浔３值奶荻染W(wǎng)格表示圖像的方法[3]。偏微分方法將曲面看作橢圓型偏微分方程在邊界條件下的解，由于偏微分方法只需少量邊界條件即可表示復(fù)雜的三維曲面，所需存儲(chǔ)量少因而非常高效。近年來(lái)國(guó)外學(xué)者研究了采用橢圓型偏微分方程作為曲面模型，將從未知曲面提取出的輪廓線作為邊界條件，通過(guò)偏微分方法擬合曲面的基本原理和應(yīng)用[4]。本文在偏微分方法構(gòu)造曲面的基礎(chǔ)之上，提出了利用偏微分?jǐn)?shù)值解進(jìn)行圖像矢量化方法，提取圖像的輪廓線作為邊界條件，通過(guò)求解非線性方程組，有效的將處理圖形的方法來(lái)處理圖像。

1 求解偏微分方程的有限差分方法

有限差分法是數(shù)值求解偏微分方程的一種有效的方法，將偏微分方程的解轉(zhuǎn)化為一組代數(shù)方程方程組，容易在計(jì)算機(jī)中實(shí)現(xiàn)[5]。有限差分方法在節(jié)點(diǎn)很多的情況下將偏微分方程求解問(wèn)題歸結(jié)為解大型的線性方程組的問(wèn)題，此時(shí)的系數(shù)矩陣常是對(duì)3 對(duì)角或塊狀3 對(duì)角，其中非零元素占的比例很小(稱為稀疏矩陣)，分布也有一定的規(guī)律，迭代法可以比較充分地利用這些特點(diǎn)，因此它是解代數(shù)方程組的一種重要方法。用迭代法解方程的優(yōu)點(diǎn)是:程序簡(jiǎn)單，對(duì)于稀疏矩陣存儲(chǔ)量可以大為減少，而且收斂的迭代過(guò)程是一個(gè)不斷修正誤差的漸進(jìn)過(guò)程，因此數(shù)值解的精度就相對(duì)比較高。

假設(shè)所求曲面X=X(u，v)滿足如下的偏微分方程:

式中，u，v為給定的參數(shù)，及給定邊界線Ci(i=0，1，2，3)，邊界條件為:

采用有限差分法求解偏微分方程曲面，首先對(duì)參數(shù)區(qū)域圍成的矩形網(wǎng)格剖分，然后把偏微分方程中的所有偏導(dǎo)數(shù)用它們的離散逼近采樣點(diǎn)替換。對(duì)矩形網(wǎng)格區(qū)域用兩組平行于坐標(biāo)軸的直線ui=ih，vj=jh 進(jìn)行剖分，假定給定的步長(zhǎng)為:h=1/M，則共有M-1個(gè)內(nèi)結(jié)點(diǎn)，在每個(gè)內(nèi)結(jié)點(diǎn)(i，j)上，用二階中心差分格式代替式中二階偏導(dǎo)數(shù)，得到:

2 基于偏微分方程數(shù)值解的圖像矢量化方法

2.1 初始邊界條件

對(duì)于一幅輸入的彩色圖像，如圖1(a)，(c)所示，為初始輸入圖像peeper，圖1(b)，(d)為初始輸入圖像lemon，可以采樣得到邊界象素信息，然后通過(guò)B樣條擬合得到初始的邊界條件。本文采用的是3次均勻B樣條來(lái)擬合邊界曲線。

圖1 初始邊界條件

3次均勻B樣條曲線段得矩陣表示為:

式中，Bj，3(u)，j=0，1，2，3為3次B樣條基函數(shù)，Pi(u)表達(dá)式為:

以上矩陣表達(dá)式寫成:A=BC。用正交方程組的形式表示:BTA=BTBC。

令BTA=E，BTB=F，C為所要求的矩陣，用X 矩陣表示，則:FX =E;其中E，F(xiàn) 都是已知的矩陣，可以直接求出X 矩陣，即為控制頂點(diǎn)矩陣。如圖1(b)為圖1(a)pepper 初始的邊界條件。

2.2 雙線性插值方法

通過(guò)雙線性插值方法得到最終的輸出圖像如圖2所示。

圖2 雙線性插值

圖2中，Q11，Q12，Q21，Q22為已知點(diǎn)，分別在x方向和y方向進(jìn)行雙線性插值，得到:

圖1經(jīng)過(guò)雙線性插值得到最終的輸出圖像如圖3所示:

圖3 雙線性插值效果圖

從圖3可以看出通過(guò)以上步驟進(jìn)行矢量化后的輸出結(jié)果并不理想，最終生成的圖像邊界不明顯，出現(xiàn)模糊的現(xiàn)象，可見(jiàn)此種方法對(duì)于形狀以及顏色比較復(fù)雜的物體的矢量化的效果并不理想，接下來(lái)考慮一些改進(jìn)的方法，可以將圖像首先進(jìn)行分割，然后針對(duì)每個(gè)子對(duì)象來(lái)進(jìn)行矢量化。做這樣的處理時(shí)，僅僅需要對(duì)圖像進(jìn)行預(yù)處理，分割出來(lái)的子對(duì)象的邊界比較清晰，且顏色單一，矢量化的其他步驟和我們之前處理整幅圖像的步驟一樣。

如圖4所示，圖4(a)，(c)為初始輸入圖像，圖4(b)，(d)為采用僅對(duì)子對(duì)象實(shí)現(xiàn)矢量化的改進(jìn)方法以后的輸出結(jié)果，從輸出結(jié)果可以看出，做這樣的處理之后的矢量化結(jié)果是比較理想的，能如實(shí)反映原始輸入圖像。

圖4 圖像分割后的處理效果圖

3 結(jié)束語(yǔ)

偏微分方程的數(shù)值解法主要采用的是有限差分的方法，具體實(shí)現(xiàn)時(shí)采用5點(diǎn)差分的格式，得到采樣點(diǎn)鄰近象素點(diǎn)的信息，但是這樣處理并不能得到圖像上所有象素點(diǎn)的信息，接下來(lái)采用雙線性插值的方法，將未知的象素點(diǎn)信息求出來(lái)，得到最終的輸出圖像。對(duì)于整幅圖像進(jìn)行這樣的處理后，矢量化的效果并不理想，做了進(jìn)一步的改進(jìn)，只針對(duì)圖像區(qū)域進(jìn)行矢量化，先將圖像分割，對(duì)具體的圖像子對(duì)象來(lái)實(shí)現(xiàn)矢量化過(guò)程，得到矢量化結(jié)果。

[1]彭容杰.圖像矢量化方法研究與英語(yǔ)[M].武漢:華中科技大學(xué)，2006:35-45.

[2]Sun J，Liang L.Image vectorization using optimized gradient meshes[J].ACM Transactions on Graphics，2007，3(11):1-7.

[3]Lai Yu-Kun，Hu Shi-Min.Automatic and Topology-Preserving Gradient Mesh Generation for Image Vectorization[J].ACM Transactions on Graphics，2009，28(3):1-7.

[4]Ugail H，Kirmani S.Shape Reconstruction using Partial Differential Equations[J].WSEAS Transactions on Computers，2006，10 (5):2 156-2 161.

[5]李瑞遐，何志慶.微分方程數(shù)值方法[M].上海:華東理工大學(xué)出版社，2005:70-76.