基于偏微分方程解析求解的圖像矢量化方法

張靖磊，余正生，樊志華，朱婧

(1.杭州電子科技大學(xué)圖形圖像研究所，浙江杭州310018;2.杭州電子科技大學(xué)機(jī)械工程學(xué)院，浙江 杭州310018)

0 引言

在科學(xué)工程領(lǐng)域中，圖像矢量化技術(shù)有著非常廣泛的應(yīng)用，圖像矢量化是將光柵圖像轉(zhuǎn)換為矢量圖形。矢量圖形體積小，可擴(kuò)展，易于編輯，最大的優(yōu)點(diǎn)在于無論放大、縮小或旋轉(zhuǎn)等不會失真。不同于光柵圖形，矢量圖用點(diǎn)、直線或者多邊形等基于數(shù)學(xué)方程的幾何圖元來表示圖像，便于圖像的處理［1］?；谑噶繄D的這些優(yōu)點(diǎn)，在大量領(lǐng)域中都用到了矢量圖形。由于圖像復(fù)雜性和多樣性，圖像矢量化的方法也有所不同，比較有代表性有基于細(xì)化的矢量化方法［2］，抽取圖像輪廓線并進(jìn)行矢量化的方法［3］，用給定的正方形網(wǎng)格分割圖像［4］。偏微分方程(Partial Differential Equation，PDE)曲面［5］是一種新出現(xiàn)的強(qiáng)有力的曲面造型工具。PDE方法將曲面看作橢圓型偏微分方程在邊界條件下的解，由于PDE方法只需少量邊界條件即可表示復(fù)雜的三維曲面，所需存儲量少因而高效。近年來國外學(xué)者研究了采用橢圓型偏微分方程作為曲面模型，將從未知曲面提取出的輪廓線作為邊界條件，通過PDE方法擬合曲面的基本原理和應(yīng)用［6］。本文利用偏微分方法構(gòu)造曲面的原理，提出了利用偏微分解析求解進(jìn)行圖像矢量化方法，提取圖像的輪廓線作為邊界條件，通過求解析解法進(jìn)行擬合，能有效的將處理圖形的方法來處理圖像。

1 PDE方法圖像矢量化

這一部分介紹利用偏微分方程構(gòu)造曲面的原理以及如何使用解析解法進(jìn)行圖像矢量化。

1.1 PDE法構(gòu)造曲面的原理

在應(yīng)用中，通常將曲面表示為含有參數(shù)的形式:X(u，v)。設(shè) X(u，v)=(x(u，v)，y(u，v)，z(u，v))表示曲面上的點(diǎn)，參數(shù)u，v看作是在從平面區(qū)域Ω到物理空間上的映射，記為:Ω→R3。PDE曲面是一個參數(shù)曲面 X=X(u，v)，通常采用橢圓偏微分方程［7］。設(shè) Ω ={0≤u≤1，0≤v≤2}，給定類雙調(diào)和方程:

將取待生成的偏微分方程曲面的4條輪廓線作為4個邊界條件，給定方程1的4個傅里葉級數(shù)表示的周邊邊界條件:

式中，P0(v)，P1(v)分別定義了曲面在u=0，1上的邊界曲線;Ps(v)，Pt(v)分別定義了曲面在內(nèi)部u=s，t上的邊界曲線。X(u，0)=X(u，2)表示邊界條件是周期的，即曲線為閉曲線。通過分離變量法得到式1、2的解:

由式2、4得知:

方程組中，未知數(shù)和方程個數(shù)都是為 4 個，可以求出 aa0，sa0，ta0，pa0，aan，san，tan，pan，abn，sbn，tbn，pbn。若假設(shè) s=0.333 33，t=0.666 67 給定邊界條件:

由式6可知傅里葉級數(shù)的最高項cosv和sinv，最高項決定了n的取值上限，即n最大為1。則式3演化為:

將 u=0，s，t，1 代入 A0(u)，An(u)，Bn(u)中，解得:a00=0.000 00，a00=3.000 13，a00= －0.000 40，a00=0.000 27。同理可解 a10，a11，a12，a13，b10，b11，b12，b13。則曲面為:邊界曲線如圖1所示，生成的PDE曲面如圖2所示:

圖1 由(6)生成的四條邊界曲線

圖2 由圖1生成的PDE曲面

1.2 基于PDE法的圖像矢量化

通過偏微分方程實(shí)現(xiàn)圖像矢量化，一張圖片有很多個象素點(diǎn)，每一個都有一個特定的坐標(biāo)、象素值，記為P(x，y，r，g，b)，為了確定邊界條件，由式2可知邊界條件需擬合成傅里葉形式的曲線，對這些散亂點(diǎn)按特定的要求，求其離散最小二乘逼近［8］來擬合出一條傅里葉級數(shù)曲線。如圖3所示:

圖3 一個雞蛋的例子

例如圖3(a)的一點(diǎn)為 P(139，31，0.949，0.922，0.859)，為了達(dá)到一定的擬合效果，取n=20，例如圖3中第一條被擬合成的曲線系數(shù)如下所示(系數(shù)形式(ak，bk)):(303.000，0.000)(－ 10.512，0.636)(0.000，0.000)(－1.145，0.210)(0.000，－0.000)(－0.396，0.123)(0.000，0.000)(－0.190，0.085)(－0.000，－0.000)(－0.105，0.064)(－0.000，－0.000)(－0.063，0.049)(－0.000，0.000)(－0.038，0.038)(0.000，－ 0.000)(－ 0.024，0.030)(0.000，－0.000)(－0.014，0.023)(－0.000，0.000)(－0.008，0.017)。依據(jù)這些系數(shù)，得到邊界條件。依據(jù)邊界條件，可知:X(0，v)=P0(v)，X(s，v)=Ps(v)，X(t，v)=Pt(v)，X(1，v)=P1(v)，X(u，0)=X(u，2)。

每4條邊界條件生成一個PDE曲面，相鄰2個曲面片之間共用1條邊界曲線，如圖4所示:

圖4 7條邊界曲線構(gòu)成2個PDE曲面片

若曲面由n個曲面片組成，則邊界曲線共有3n+1條。因此每一個圖像塊等同于是一張PDE曲∞面，圖像塊滿足 X(u，v)=A0(u)+n∑－1(An(u)cos nv+Bn(u)sin nv)，圖 3(b)顯示了(a)圖經(jīng)過圖像矢量化后的圖像。

2 基于PDE方法圖像矢量化的例子

依據(jù)前面的方法，這一部分展示了兩個例子。如圖5所示:

圖5 一個紅椒的例子

圖5 (a)是掃描出來的圖像，圖5(b)顯示了圖5(a)經(jīng)過圖像矢量化后的圖片。對原圖的象素點(diǎn)進(jìn)行最小二乘逼近，擬合成207條傅里葉曲線作為邊界條件。

依據(jù)每4條邊界條件生成一個PDE曲面，相鄰2個曲面片之間共用1條邊界曲線，則共有130個曲面片，每個曲面片通過4條邊界曲線唯一的確定。

3 結(jié)束語

根據(jù)橢圓偏微分方程的表示，本文首先介紹了PDE方法構(gòu)造曲面的基本原理;然后對提取出來的圖像的離散點(diǎn)進(jìn)行最小二乘擬合，以圖像的輪廓線作為邊界條件，劃分圖像塊，運(yùn)用PDE解析解方法高效的重構(gòu)一張圖像;PDE方法簡單易行、速度快，并由于邊界條件生成的圖像塊保留了原始圖像的基本特征，能高效的重構(gòu)圖像。本文所提出的方法對于圖像不是很復(fù)雜的情況下還是十分高效和方便的。

［1］ 彭容杰.圖像矢量化方法研究與英語［D］.武漢:華中科技大學(xué)，2006.

［2］ Pavilidis T.An asynchronous thinning algorithm［J］.Computer graphics and Image Processing，1982，20(2):133 －157.

［3］ Hori O，Tanigawa S.Raster－to－Vector Conversion by Line Fitting Based on Contours and Skeletons［C］.Tsukuba Science City:Document Analysis and Recognition，1993:353－358.

［4］ Vaxiviere P，Tombre K.CAD Conversion of Mechanical Drawings［J］.IEEE Computer，1992，25(7):46 －54.

［5］ Bloor M I G，Wilson M J.Generating blend surfaces using partial differential equations［J］.Computer－ Aided Design，1989，21(3):165 －171.

［6］ Ugail H，Kirmani S.Shape Reconstruction using Partial Differential Equations［J］.WSEAS Transactions on Computers，2006，10(5):2 156 －2 161.

［7］ 朱心雄.自由曲線曲面造型技術(shù)［M］.北京:科學(xué)出版社，2008:250－271.

［8］ Richard L Burden，Douglas J Faires.數(shù)值分析［M］.北京:高等教育出版社，2005:420－445.