姚鵬鵬， 樊 臻， 張森林

(浙江大學(xué) 電氣工程學(xué)院，浙江 杭州 310007)

改進(jìn)的Potrace提花織物圖像矢量化算法*

姚鵬鵬， 樊 臻， 張森林

(浙江大學(xué) 電氣工程學(xué)院，浙江 杭州 310007)

為了對提花織物圖像進(jìn)行矢量化，針對其顏色少、色塊大的特點，提出了改進(jìn)的Potrace圖像矢量化算法。原始的Potrace算法只能實現(xiàn)對二值圖像的矢量化，改進(jìn)后的算法將位圖中的色塊逐個分解生成一個個的閉合路徑，之后將這些閉合路徑按照其各自分布拼接成樹狀結(jié)構(gòu)并矢量化，最終生成一個完整的矢量圖形。該算法在實際的應(yīng)用中取得較好效果。

提花織物； Potrace 算法； 圖像矢量化； 路徑分解

0 引 言

圖像的矢量化尤其是彩色圖像的矢量化一直是圖像處理的難點。而國內(nèi)外現(xiàn)有的有名的矢量化軟件的普遍缺點是抗噪聲性差矢量化的精度和速度都不高，而且這些軟件的應(yīng)用偏向于工程圖紙領(lǐng)域地理信息系統(tǒng)和計算機(jī)輔助制造等[1]。

提花織物圖像不同于普通的彩色圖像，它是由一個個的色塊組成[2]，理論上更容易進(jìn)行矢量化。將圖像矢量化后，有利于圖像的再利用和再創(chuàng)造。圖像矢量化對于提花織物圖案的處理還有其他重要的意義，例如:可用于提花織物的圖像識別和圖片壓縮[3,4]。本文提出了改進(jìn)的Potrace矢量化算法，在處理提花織物圖像時，取得了很好的效果。

1 總體方案

本文主要是對Potrace矢量化算法的改進(jìn)。Potrace位圖矢量化算法只可以處理二值圖像(即黑白圖像)，改進(jìn)后的Potrace算法能夠支持K種顏色的位圖圖像。首先將K種顏色的位圖分解為K張二值圖片，分別對這些圖片進(jìn)行路徑搜索，之后根據(jù)這些路徑的位置關(guān)系，拼接成一顆路徑樹，最后調(diào)用Potrace的路徑矢量化算法，生成矢量圖像。提花織物圖像一般不超過16種顏色，非常適合使用此方法。

2 Potrace位圖矢量化算法

Potrace矢量算法是加拿大教授Selinger Peter提出并實現(xiàn)的二值位圖(即黑白圖片)矢量化算法。該算法可以將一個位圖轉(zhuǎn)化為一個光滑的，放縮無鋸齒化的矢量圖。Potrace算法主要分為5步：1)位圖被分解成劃分黑白區(qū)域之間邊界的一系列路徑；2)每一個路徑被一個最優(yōu)的多邊形擬合；3)每一個多邊形被轉(zhuǎn)化為一條光滑的輪廓線；4)此步為可選的，如果可能的話，合成的曲線通過加入連續(xù)的貝塞爾曲線段進(jìn)行最優(yōu)化處理；5)輸出被調(diào)整成需要的格式。

Potrace矢量化算法計算速度快，效果好，支持的輸出格式豐富，但是存在一個嚴(yán)重的缺點，它只可以對二值圖像進(jìn)行矢量化。為了使Potrace更具使用價值，需要對其進(jìn)行改進(jìn)，以使它能夠?qū)λ饕珗D像進(jìn)行矢量化[5,6]。

3 Potrace算法的改進(jìn)

對Potrace算法的改進(jìn)主要集中在對路徑分解的改進(jìn)上。對于一張二值圖片，想象將該圖片放置于一個坐標(biāo)系里面，每個像素角落的坐標(biāo)值為整數(shù)值。假設(shè)該圖片的背景色是白色，前景色是黑色并假設(shè)超過圖片邊界的顏色都是白色。如果點p擁有一個整數(shù)值坐標(biāo)，這個點必然是4個像素的交接點。如果這4個像素的顏色不完全相同，就稱這個點為頂點(vertex)。如果2個頂點v和w的歐幾里得距離是1，稱從v到w有一個邊緣(edge)。如果從v到w的邊緣將黑白像素分開，并且黑像素在邊緣的左邊，白像素在邊緣的右邊，稱邊緣的方向為從v到w。路徑(path)是由一個序列的頂點{v0,…,vn}組成,如果v0=vn，則稱這條路徑是閉合路徑。路徑分解的目的就是將一幅圖片G分解成許多的閉合路徑。

二值圖像路徑分解流程如圖1所示。首先尋找1對顏色不一樣的鄰接像素，比如可以尋找最左出現(xiàn)的黑色像素的那一列。這2個像素將會形成一個邊緣，將黑色像素在左邊白色像素在右邊的方向定義為正方向。這是一個長度為一的路徑。沿著這條路徑方向接著向下尋找，保證黑色的像素在左邊白色的像素在右邊。一直尋找，直到來到起點，就可以定義一個閉合的路徑了。每當(dāng)搜索完成一條路徑的時候，將這條路徑移走，并且將其內(nèi)部的像素置反。這樣就定義了一個新的圖，然后再一次使用這個方法，直到所有的像素都是白色為止。之后的工作就是對每個路徑進(jìn)行獨立的操作。

圖1 二值圖像分解流程圖Fig 1 Flow chart of binary image decomposition

在Potrace算法中，矢量圖在內(nèi)存中用樹的結(jié)構(gòu)表示。如圖2(a)所示的二值圖像，將會生成圖2(b)所示的A，B，C，D，E，F(xiàn)，H，I8條路徑。其中,A路徑包含B路徑，那么，B就是A的孩子；而A路徑跟F路徑?jīng)]有包含與被包含的關(guān)系，那么，路徑A跟F就是兄弟關(guān)系。圖2(a)將最終生成如圖2(c)的樹的結(jié)構(gòu)。

圖2 二值圖像矢量化Fig 2 Binary image vectorization

彩色圖像的路徑搜索流程如圖3所示，依次取出每個顏色，生成一個新的空白二值圖像。生成的二值圖像與彩圖長寬相等。遍歷彩色圖像，如果坐標(biāo)原圖中坐標(biāo)(i，j)像素的顏色是當(dāng)前取出的顏色，就將二值圖中(i，j)所在的顏色置為黑色，其他的位置為白色。對于新生成的二值圖像再進(jìn)行路徑搜索，每搜索完一條路徑，就將其插入已有的路徑中。插入的時候需要注意父節(jié)點一定要在其子孫節(jié)點之前。然后再調(diào)用Potrace的里面的鏈表轉(zhuǎn)換為樹的函數(shù)，將鏈表生成一顆樹。

圖3 彩色圖像路徑搜索流程圖Fig 3 Flow chart of color image path searching

在路徑搜索的時候會發(fā)現(xiàn)，大多數(shù)的路徑會搜索2次。如圖4(a)中的路徑B，在對搜索的紅色二值圖片的時候，搜索了一次，在搜索藍(lán)色二值圖片的時候，又搜索了一次,顯然重復(fù)了。解決的方法是在路徑搜索的過程中為每個路徑加上一個符號域，在圖4(a)搜索紅色二值圖像的時候，會生成圖4(b)所示的二值圖像，搜索到路徑A則將其符號設(shè)為‘+’，然后找到路徑B，由于B包含在路徑A里面將其符號設(shè)為‘-’，再然后找到路徑C，將其路徑設(shè)為‘+’，就這樣不斷重復(fù)，最后在插入鏈表的時候只將符號域為‘+’的路徑插入，其他路徑丟棄即可。這樣如果沒有剔除符號域為‘-’這一步，圖4(b)會生成A→B→這樣的鏈表，而在加入了剔除符號域為‘-’這一步之后，得到的鏈表將是A→C。

對圖4(a)中的圖像進(jìn)行路徑分解，紅色的部分會首先生成一個A→C的鏈表。藍(lán)色部分會生成一個B→D的鏈表。然后將藍(lán)色部分的鏈表插入紅色部分的鏈表，最終的鏈表是A→B→C→D.生成的樹如圖4(c)所示。

4 實驗結(jié)果

圖5是一組矢量化效果的展示，圖5(b)對圖5(a)進(jìn)行了矢量化，圖5(c)將其背景色去除。比較圖5，可以看到，通過該方法能準(zhǔn)確地檢測出原圖的輪廓，生成的矢量圖光滑整齊，與原圖差別小。

利用矢量化描述提花織物圖像有如下優(yōu)點：1)絲綢織物多為大色塊，使用矢量方式存儲可以有效地減小存儲大小，節(jié)省存儲空間；2)矢量化后的圖稿易于修改，如圖5(c)所示，只要一步簡單的操作就能將其背景色去除或替換；3)以矢量形式描述的圖稿易于提取花紋,有利于圖像的再創(chuàng)作；4)矢量圖像描述的是絲綢圖像的圖形信息，這些信息是CAD設(shè)計的主要信息，進(jìn)行矢量描述后可以更方便地應(yīng)用于圖像的匹配與檢索。

圖5 矢量化效果圖示Fig 5 Diagram of vecotorization effect

5 結(jié) 論

本文改進(jìn)了Potrace算法的路徑分解部分，使原來只能處理單色圖片的Potrace算法支持了彩色圖像的處理。尤其在對提花織物圖像的處理中，該算法取得了很好的效果。但是，此算法依舊存在一些不足，比如：在處理顏色數(shù)量多的時候，該算法的處理速度很慢，因此，還需要繼續(xù)地深入研究。

[1] 李文慶，鄭秋華，張坤龍.基于用戶交互的光柵圖像局部矢量化方法[J].杭州電子科技大學(xué)學(xué)報,2011,31(6):91-94.

[2] 劉妹琴,程紅梅.基于擴(kuò)展“變球法”的顏色量化分析[J].工程設(shè)計學(xué)報,2006,13(3):175-178.

[3] 程紅梅，顏鋼鋒.紋織圖像的矢量化方法[J].紡織學(xué)報，2006,27(3)：33-35.

[4] 李文慶.針對維吾爾族圖案重組設(shè)計的關(guān)鍵技術(shù)研究[D].杭州：杭州電子科技大學(xué)，2011.

[5] Selinger Peter.Potrace:A polygon-based tracing algorithm[2009—07—01].http:∥potrace.sourceforge.net/potrace.pdf.

[6] Selinger Peter.Potrace Library API[2009—07—01].http:∥potrace.sourceforge.net/potracelib.pdf.

Improved Potrace algorithm for vectorization of image of jacquard*

YAO Peng-peng, FAN Zhen, ZHANG Sen-lin

(College of Electrical Engineering,Zhejiang University,Hangzhou 310007,China)

In order to vectorize jacquard image,aiming at small amount of color and large color blocks,propose an improved Potrace algorithm for vectorization of image .The original Potrace algorithm can only realize vectorization of binary image and the improved algorithm decompose color blocks of bitmap one by one to closed paths which are combined to a tree structure later and merged to a vector graphic at last.This algorithm achieves good effect in practical use.

jacquard; Potrace algorithm; vectorization of image； path decomposition

2013—09—15

國家科技支撐計劃資助項目(2013BAH58F02)

TP 391

A

1000—9787(2014)04—0125—03

姚鵬鵬(1989-)，男，江蘇如皋人，碩士研究生，主要研究方向為數(shù)字圖像處理，人工智能。