摘 要：位圖圖像的矢量化是計(jì)算機(jī)圖形學(xué)的熱點(diǎn)問題。圖像的矢量化解決了速度和空間上的問題，為圖像進(jìn)一步的輸出與管理提供了便利。因此，他也是無紙動(dòng)漫領(lǐng)域所面臨的基礎(chǔ)問題之一。通過對(duì)位圖矢量化課題的深入研究，針對(duì)矢量化過程中的幾個(gè)關(guān)鍵點(diǎn)技術(shù)，特別針對(duì)圖像輪廓的提取，跟蹤及關(guān)鍵特征點(diǎn)提取和曲線擬合，提出行之有效的解決算法。最后在VC 6.0環(huán)境下對(duì)算法進(jìn)行實(shí)現(xiàn)。其處理速度快、曲線擬合光滑、失真小，驗(yàn)證了算法的可行性，為其在一個(gè)無紙動(dòng)漫系統(tǒng)中的初步應(yīng)用奠定了基礎(chǔ)。

關(guān)鍵詞：位圖；圖像輪廓；曲線擬合；矢量化

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1004-373X(2008)06-064-03

Algorithmic Study on the Vectorization of Bitmap in Paperless Cartoon Filed

CHEN Qixiang，YUAN Xiaoxue

(Hubei University of Technology，Wuhan，430068，China)

Abstract：Vectorization of bitmap is a hot issue of the computer graphics.It not only resolves problems of the velocity and space，but also provides some advantages for the further output and the management of images.Therefore，it is also one of the basic problems facing the paperless cartoon.Thorough the in-depth study of the vectorization of Bitmap，this paper puts forward the effective algorithm of myself which aims at the several key technical points，especially in the extraction of image contour，the contour tracking，the extraction of key characteristic points and the curve fitting.Finally，the arithmetic has been programmed based on Visual C⁺⁺ 6.0 and been applied in a system of paperless cartoon.It proves the high speed and feasibility because he curve is smooth and the distortion of the image is very small.It establishes the foundation for the elementary application in a paperless cartoon system.

Keywords：bitmap；image contour；curve fitting；vectorization

隨著世界動(dòng)漫技術(shù)的無紙化發(fā)展，以及動(dòng)漫產(chǎn)業(yè)無論是從質(zhì)還是量的發(fā)展要求，無紙動(dòng)漫勢(shì)在必行。無紙動(dòng)漫系統(tǒng)一般采用分布式設(shè)計(jì)，動(dòng)畫美工通過在圖板上繪圖產(chǎn)生電信號(hào)，客戶端將電信號(hào)轉(zhuǎn)換成真正的圖片文件并上傳至服務(wù)器經(jīng)過進(jìn)一步的處理形成最終的動(dòng)畫片，導(dǎo)演則可以方便地通過客戶端服務(wù)直接觀看動(dòng)畫片，提出各種意見和建議。電信號(hào)文件轉(zhuǎn)化成圖片文件的過程一般需要較大的計(jì)算量，由于位圖圖像的數(shù)據(jù)量十分巨大，對(duì)于圖片的海量存儲(chǔ)、網(wǎng)絡(luò)上的傳輸即緩解網(wǎng)絡(luò)容量和傳輸率不足的矛盾，以節(jié)約存儲(chǔ)資源和網(wǎng)絡(luò)資源，都是不得不考慮的問題。除了尋找更佳的壓縮算法對(duì)圖像進(jìn)行進(jìn)一步的壓縮以外，對(duì)圖像進(jìn)行矢量化存儲(chǔ)成了一種主要的趨勢(shì)。矢量圖也有利于處理邊界噪聲，修正量化誤差，以提高編輯效率和實(shí)際效果。矢量化可以用多種形式實(shí)現(xiàn)，諸如直線，圓弧，B樣條曲線，貝賽爾曲線等，根據(jù)不同的應(yīng)用選用相應(yīng)的矢量化形式，以求達(dá)到最佳的利用效果。由于本算法對(duì)特征點(diǎn)集進(jìn)行了優(yōu)化，采取的是貝賽爾曲線，得到的線條已經(jīng)非常非常均勻和光滑。

1 相關(guān)理論

1.1 象素的8鄰域

對(duì)象素(x，y)將其上下左右4個(gè)象素點(diǎn)及其對(duì)角線上的 4個(gè)象素點(diǎn)構(gòu)成的集合稱為象素(x，y)8鄰域：

圖1 象素的8領(lǐng)域

在位圖處理時(shí)，由于位圖圖像是點(diǎn)陣結(jié)構(gòu)，尋找輪廓線是從當(dāng)前點(diǎn)出發(fā)尋找其相鄰輪廓點(diǎn)，如上圖1所示，每一個(gè)點(diǎn)周圍都有8個(gè)點(diǎn)，事先準(zhǔn)備好8個(gè)方向，在搜索過程中，在8個(gè)方向上試探可否前進(jìn)，用矩陣元素下標(biāo)(，)表示當(dāng)前輪廓點(diǎn)坐標(biāo)，對(duì)每一個(gè)象素點(diǎn)用3×3的模板，也叫8鄰域圖進(jìn)行處理。

1.2 位圖的矢量化過程

位圖的矢量化過程如圖2所示。

圖2 位圖的矢量化過程

二值位圖 由于掃描后的圖像以不同灰度級(jí)存儲(chǔ)，為了進(jìn)行數(shù)據(jù)矢量化的轉(zhuǎn)換，需壓縮為2級(jí)(0和1)，這就稱為二值化。

圖像預(yù)處理 對(duì)于掃描輸入的圖幅，由于原稿不干凈等原因，總是會(huì)出現(xiàn)一些飛白、污點(diǎn)、線劃邊緣凹凸不平等。除了依靠圖像編輯功能進(jìn)行人機(jī)交互處理外，還可以通過一些算法來進(jìn)行處理，經(jīng)過預(yù)處理后的圖像對(duì)矢量化的過程的影響會(huì)減小

輪廓提取 圖像經(jīng)過預(yù)處理后，還需要從二值圖象區(qū)域中產(chǎn)生出區(qū)域邊界點(diǎn)序列，輪廓提取即可以完成這一功能，為后續(xù)的輪廓跟蹤做好準(zhǔn)備。

輪廓跟蹤 圖像經(jīng)過輪廓提取后得到的點(diǎn)的序列并不是有序的，輪廓跟蹤用來將這些點(diǎn)有序化、從而將這些有序坐標(biāo)點(diǎn)進(jìn)行曲線擬合而實(shí)現(xiàn)矢量化。

曲線擬合 通過輪廓跟蹤后，得到了對(duì)于封閉區(qū)域的有序的連通分量，通過對(duì)這些有序點(diǎn)的重新篩選后，采用高次Bezier曲線將其進(jìn)行擬合成一條光滑的，可任意縮放的矢量曲線，即實(shí)現(xiàn)了位圖到矢量圖像的轉(zhuǎn)換。

下面，將對(duì)矢量化過程中的幾個(gè)關(guān)鍵點(diǎn)技術(shù)的處理方法進(jìn)行詳細(xì)的介紹。

2 幾個(gè)關(guān)鍵技術(shù)的改進(jìn)算法

2.1 四領(lǐng)域輪廓提取

本文提出的4鄰域輪廓提取的算法原理是查找一個(gè)目標(biāo)黑點(diǎn)的上下左右4個(gè)方向的非白點(diǎn)，只要這4個(gè)方向上存在非白點(diǎn)，則認(rèn)為該黑點(diǎn)為輪廓點(diǎn)。該算法與現(xiàn)有的8鄰域掏空算法相比，輪廓的提取更準(zhǔn)確，對(duì)于復(fù)雜圖像的某些連接處不會(huì)有重復(fù)黑點(diǎn)的情況，從而對(duì)輪廓的跟蹤影響也減小許多，同時(shí)也減小了后續(xù)的矢量化效果。經(jīng)過輪廓提取后，圖像的邊緣輪廓就會(huì)突顯出來。在VC 6.0下的算法過程如下：

(1) 水平掃描整副圖像，搜尋象素值為0的點(diǎn)，即黑點(diǎn)。

(2) 如果該黑點(diǎn)是邊界點(diǎn)，將其確定為輪廓點(diǎn)，并將數(shù)組outline 的該點(diǎn)象素值(outline+y×lHeight+x)置為0；

(3) 如果該黑點(diǎn)不是邊界點(diǎn)，則在該點(diǎn)上下左右4個(gè)方向判斷是否存在非白點(diǎn)，如果其上，下，左，右有一個(gè)方向點(diǎn)的象素值不為0，則找到一個(gè)輪廓點(diǎn)，并將數(shù)組outline 的該點(diǎn)象素值(outline+y×lHeight+x)置為0；

(4) 重復(fù)執(zhí)行(2)和(3)，直至找到所有輪廓點(diǎn)。

2.2 雙向輪廓跟蹤

圖像經(jīng)過輪廓提取后得到的點(diǎn)的序列并不是有序的，這些輪廓點(diǎn)是離散、獨(dú)立、互不相關(guān)的無序集合，要想進(jìn)行矢量化，必須得到這些邊界點(diǎn)的有序集合，把一幅圖象分割成一段段點(diǎn)的系列，使這些象素點(diǎn)之間用曲線連接起來，為此必須要進(jìn)行輪廓跟蹤。

而如何快速，準(zhǔn)確的跟蹤到輪廓序列點(diǎn)，這就是這里的研究目的，是進(jìn)行有效矢量化的最關(guān)鍵的一步。一般在單區(qū)域內(nèi)進(jìn)行輪廓跟蹤方法比較多，對(duì)于多區(qū)域內(nèi)的輪廓跟蹤則比較復(fù)雜，本文提出了一種更為簡(jiǎn)單的雙向輪廓跟蹤算法，算法流程圖如圖3所示。

在算法中，所使用到的數(shù)據(jù)結(jié)構(gòu)如下：數(shù)組outline，存放輪廓提取點(diǎn)，同時(shí)可標(biāo)志在輪廓跟蹤是該數(shù)組中的點(diǎn)是否遍歷過。vector < vector > gvCircle； 向量gvCircle：用來存放多個(gè)閉區(qū)域通過輪廓跟蹤之后產(chǎn)生的結(jié)果；vector vCircle；向量vCircle用來存入單個(gè)閉區(qū)域通過輪廓跟蹤之后產(chǎn)生的結(jié)果。

圖3 跟蹤算法流程圖

在VC 6.0下的算法實(shí)現(xiàn)步驟如下：

(1) 利用水平行掃描，將搜索到的第一個(gè)黑點(diǎn)確定為第一個(gè)跟蹤起點(diǎn)，記下其坐標(biāo)，將其加入到閉區(qū)域結(jié)果向量vCircle中，，并將數(shù)組outline 的該點(diǎn)象素值(outline+y×lHeight+x)置為1，即標(biāo)記為已遍歷。

(2) 接著對(duì)該點(diǎn)的8鄰域方向的點(diǎn)進(jìn)行掃描。8個(gè)方向和起始掃描方向的數(shù)據(jù)結(jié)構(gòu)為：int Direction [8][2] = {{1，0}，{1，1}，{0，1}，{-1，1}，{-1，0}，{-1，-1}，{0，-1}，{1，-1}}，Direction的方向變化值如下：

Direction[0，0]=1； [WB]Direction[0，1]=0；

Direction[1，0]=1；Direction[1，1]=1；

Direction[2，0]=0；Direction[2，1]=1；

Direction[3，0]=-1；Direction[3，1]=1；

Direction[4，0]=-1；Direction[4，1]=0；

Direction[5，0]=-1；Direction[5，1]=-1；

Direction[6，0]=0；Direction[6，1]=-1；

Direction[7，0]=1；Direction[7，1]=-1；

以此確定的點(diǎn)為中心，分別按照0， 1， 2， 3， 4和0， 7， 6， 5， 4兩個(gè)方向依次掃描，若遇到的下一點(diǎn)為黑點(diǎn)，根據(jù)Direction的方向變化便可計(jì)算出下一點(diǎn)的坐標(biāo)值x，y，將該點(diǎn)加入到閉區(qū)域結(jié)果向量vCircle中，并將數(shù)組outline 的該點(diǎn)象素值(outline+y×lHeight+x)置為1，即標(biāo)記為已遍歷，跳出循環(huán)，再重復(fù)第(2)步直至兩個(gè)方向均未遇到黑點(diǎn)，則進(jìn)入第(3)步。

(3) 第一個(gè)封閉區(qū)域跟蹤完畢，將該閉區(qū)域結(jié)果向量vCircle加入到全局結(jié)果向量gvCircle中。并進(jìn)入到第(1)步繼續(xù)搜索下一個(gè)封閉區(qū)域跟蹤起點(diǎn)。

(4) 重復(fù)執(zhí)行(1)，(2)和(3)步，直至所有的閉區(qū)域跟蹤完畢。

2.3 輪廓特征點(diǎn)提取

通過輪廓跟蹤后，得到閉區(qū)域的有序的連通分量。由于所得的每一輪廓線的序列點(diǎn)是從點(diǎn)陣圖像中所得，相鄰2點(diǎn)差值為l，數(shù)據(jù)很密，特別是劇齒比較大的圖形。因此，需要對(duì)已找到的輪廓點(diǎn)進(jìn)行刪除和其他處理。

(1) 將一條輪廓線起點(diǎn)A0坐標(biāo)送到變量Ai中；

(2) 將點(diǎn)Ai和點(diǎn)Ai+2連成一條直線，求出點(diǎn)Ai+1到這條直線之間的垂直距離，如果其距離大于某一固定允許誤差值。則點(diǎn)Ai+1保留，不能刪除，將點(diǎn)Ai+1置為當(dāng)前點(diǎn)，轉(zhuǎn)(2)頭繼續(xù)處理；如果其距離小于某一固定允許誤差值。將點(diǎn)Ai+1從輪廓線序列點(diǎn)中刪除，將點(diǎn)Ai和點(diǎn)Ai+3連成1條直線，計(jì)算點(diǎn)Ai+2和這條直線之間關(guān)系，一直循環(huán)找到1個(gè)中間點(diǎn)Ak其垂直距離大于某一固定允許誤差值，將點(diǎn)Ak置為當(dāng)前點(diǎn)Ai，刪除Ai和Ak之間所有點(diǎn)，轉(zhuǎn)b頭繼續(xù)處理；當(dāng)點(diǎn)Ak等于此條輪廓線的終點(diǎn)時(shí)，刪除多余點(diǎn)過程結(jié)束；

(3) 將刪除多余點(diǎn)后得到的輪廓序列點(diǎn).再從頭向后判斷，如果相鄰2點(diǎn)之間相隔不超過3個(gè)點(diǎn)，則取2 點(diǎn)的平均值作為序列點(diǎn)，將此2點(diǎn)刪除。

(4) 轉(zhuǎn)(1)繼續(xù)處理下1條輪廓線，直到所有輪廓線處理完畢。處理完后的輪廓線序列點(diǎn)就可以進(jìn)行曲線擬合。

2.4 Bezier曲線擬合

若給定空間n+1個(gè)點(diǎn)的位置矢量[WTHX]P[WTBX]i，則n次Bezier曲線的矢量方程是：

其中，[WTHX]P[WTBX]i構(gòu)成Bezier曲線的控制點(diǎn)即輪廓線上連續(xù)序列點(diǎn)，他們構(gòu)成Bezier曲線的特征多邊形Bi，n(t)是Bernstein基函數(shù)，也是曲線上個(gè)點(diǎn)位置矢量的調(diào)和函數(shù)：

由于采用了Bezier曲線擬合，只要對(duì)掃描圖像得到的輪廓序列點(diǎn)進(jìn)行放大或縮小后再擬合，就可以對(duì)原圖進(jìn)行無級(jí)放大或縮小而不變形，仍然得到的是光滑的輪廓曲線。根據(jù)Bezier曲線基本原理，利用GDI+，并依據(jù)輪廓跟蹤特征點(diǎn)的坐標(biāo)，將各封閉向量的點(diǎn)坐標(biāo)代入Graphics.DrawBeziers(Pen* pen，PointF* points，INT count)，(其中，pen，畫Bezier曲線所用的畫筆，points，輪廓線上連續(xù)序列控制點(diǎn)類型，count，每一個(gè)跟蹤序列向量數(shù)組的點(diǎn)個(gè)數(shù))便可得到比較光滑的矢量線條，同時(shí)將其保存為.vtr矢量格式文件。

3 結(jié) 語

通過深入研究圖像矢量化算法，特別針對(duì)矢量化過程幾個(gè)關(guān)鍵處理點(diǎn)提出了自己的處理算法： 輪廓提取、輪廓跟蹤、特征點(diǎn)提取以及采用Bezier曲線進(jìn)行矢量線條的擬合，并在VC6環(huán)境下對(duì)算法進(jìn)行了實(shí)現(xiàn)，最后成功應(yīng)用在一個(gè)無紙動(dòng)漫平臺(tái)動(dòng)畫軟件系統(tǒng)中，驗(yàn)證了算法的可行性與實(shí)用性。矢量化工作仍在繼續(xù)研究和完善中，通過進(jìn)一步的研究，會(huì)使這一算法更加有效和高效。

參考文獻(xiàn)

[1]Arcelli C.Pattern Thinning by Contour Tracing\\[J\\].Computer Graphics and Image Processing，1981，17(1)：130-144.

[2]Kasturi R，F(xiàn)ernandez R，Amlani M L，et al.Map Data Processing in Geographic Information Systems\\[J\\].Computer，1989，22(12)：10-21.

[3]Nagasamy V，Langrana N A.Engineering Drawing Processing and Vectorization System\\[J\\].Computer Vision，Graphics，and Image Processing，1990，(49)：379-397.

[4]Parker J R.Extracting Vectors From Raster Images\\[J\\].Computer Graphics，1988，12(1)：75-79.

[5]孫家廣，楊長(zhǎng)貴.計(jì)算機(jī)圖形學(xué)[M].北京：清華大學(xué)出版社，1997.

[6]孫圣和，陸哲明.矢量量化技術(shù)及應(yīng)用\\[M\\].北京：科學(xué)出版社，2002.

[7]童若鋒，汪國(guó)昭，金通.輪廓跟蹤的TN方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2003，15(5)：579-582.

作者簡(jiǎn)介

陳啟祥 男，1966年出生，湖北漢川人， 湖北工業(yè)大學(xué)副教授。研究方向?yàn)槎嗝襟w網(wǎng)絡(luò)通信、網(wǎng)絡(luò)軟件開發(fā)。

袁小雪 女，1982年出生，湖北人，碩士研究生。研究方向?yàn)槎嗝襟w圖形圖像技術(shù)。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。