基于矢量化方法的套色圖光滑變換算法

1、基于矢量化方法的套色圖光滑變換算法*湯鋒1 王章野1 劉鋼1 許端清2 彭群生11浙江大學(xué)CAD&CG國(guó)家重點(diǎn)實(shí)驗(yàn)室 浙江杭州 3100272浙江大學(xué)計(jì)算機(jī)學(xué)院 浙江杭州 310027 摘要：圖像的光滑變換一直是圖象處理領(lǐng)域中的一個(gè)難點(diǎn)，目前已有的算法中沒(méi)有一種能很好適用于所有紡織行業(yè)中的套色圖象。本文中提出了一種新的算法，該算法首先進(jìn)行圖象的矢量化，用多邊形逼近輪廓，然后再用基于拐點(diǎn)和彎曲角的方法對(duì)邊界點(diǎn)集合進(jìn)行精簡(jiǎn)，最后進(jìn)行變換和重構(gòu)。這樣在保持原來(lái)形狀的基礎(chǔ)上減少了變換過(guò)程中產(chǎn)生的毛刺。實(shí)驗(yàn)表明本算法能魯棒地處理各種套色圖象。關(guān)鍵詞：輪廓跟蹤 毛刺剔除 邊界簡(jiǎn)化 圖象重構(gòu)。中圖法

2、分類(lèi)號(hào):TP 391 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1006-8961(2003)spec-Vector Method Based Few-color Image Smooth TransformationFeng Tang1, Zhangye Wang1, Gang Liu1, Duanqing Xu2 and Qunsheng Peng11State Key Lab. CAD&CG, Zhejiang University, Hangzhou 3100272College of Computer Science, Zhejiang University, Hangzhou 310027

3、Abstract Image transformation is a frequently used operation in CAD systems, but how to keep the image smooth in the transformation is a difficult problem, current methods cannot process very well for few color images in textile industry. In this paper we propose a new algorithm for this, first the

4、image is vectorized, using a polygon to approximate the contours of different colors, then we use a dominate point based approach to reduce the number of contour points, then the transformation is applied on the reduced contour points, finally we fill the transformed polygon to reconstruct the final

5、 image. Experiments show that this approach can deal with most few color images.Keywords contour tracing, blur elimination, contour simplification, image reconstruction1.引言數(shù)字圖象可被分為灰度圖象，彩色圖象，套色圖象和二值圖象1。其中套色圖像是指由某幾種顏色的均勻色塊構(gòu)成的圖象，不同色塊間具有明顯的分界線(xiàn)，已被廣泛的應(yīng)用于紡織、印染等工業(yè)中。以簡(jiǎn)單的圖象旋轉(zhuǎn)為例，經(jīng)過(guò)旋轉(zhuǎn)變換，象素點(diǎn)的坐標(biāo)總要乘以一個(gè)旋轉(zhuǎn)矩陣，這樣產(chǎn)生的浮點(diǎn)

6、數(shù)在重采樣的時(shí)候要取整，產(chǎn)生了許多偏離正常位置的點(diǎn)，當(dāng)這種偏離大于一定的值時(shí)，我們稱(chēng)這種點(diǎn)為毛刺點(diǎn)，即使圖像看上去不光滑的點(diǎn)。提到光滑，我們很容易想到B樣條的光滑的特性，所以就有了基于B樣條曲線(xiàn)擬和法2的光滑變換處理。其思想是：從原圖象中抽取能夠代表圖象輪廓的控制點(diǎn)，將圖象變換作用于這些控制點(diǎn)，然后用B樣條進(jìn)行擬和，得到新圖象的輪廓。最后，用某種填充算法對(duì)新圖象的輪廓進(jìn)行填充，從而得到變換后的新圖象。 這種算法雖然可以在某種程度上保持圖象的光滑性，但卻不能很好的保持圖形的原狀，在圖2中的1，2處的色塊變細(xì)了，3處的色塊改變了形狀。這個(gè)缺點(diǎn)產(chǎn)生的原因是高階B樣條的形狀難于控制，以致不能很好的保持

7、圖像原來(lái)的形狀。 圖1 原圖 圖 2 原圖旋轉(zhuǎn)30度（基于B樣條算法）2.基于線(xiàn)性變換的圖象光滑變換處理針對(duì)高階的B樣條擬和法的缺陷，我們這里采用了線(xiàn)性的直線(xiàn)擬和的方法，用多邊形去擬和邊界，然后對(duì)多邊形的頂點(diǎn)（即輪廓的控制點(diǎn)）進(jìn)行變換，之后再通過(guò)處理過(guò)的輪廓的控制點(diǎn)重構(gòu)出完整的圖像。大多數(shù)工業(yè)中使用的圖像有很強(qiáng)的規(guī)律性：第一、這些圖像大多由一些簡(jiǎn)單的色塊組成，顏色數(shù)不會(huì)太多（一般在256色以下）；第二、這些圖像的邊界一般都是由某幾種曲線(xiàn)組合而成（這是由軟件工具所決定的），除去少量的拐點(diǎn)，圖像的邊界是光滑的。從實(shí)現(xiàn)上說(shuō), 整個(gè)方法的可分為如下幾步：1)圖象的矢量化;2)基于矢量的圖象變換;3)圖

8、象的重構(gòu).圖象的矢量化是將各種顏色的色塊的邊界輪廓找出來(lái)，在它們中尋找控制點(diǎn)?；谑噶康膱D象變換就是對(duì)控制點(diǎn)進(jìn)行相應(yīng)的旋轉(zhuǎn)、放大等變換圖象的重構(gòu)是根據(jù)基于矢量的圖象變換的基礎(chǔ)上得到的點(diǎn)來(lái)對(duì)新得到的邊界進(jìn)行填充，得到目標(biāo)圖象。3 圖象的矢量化圖象的矢量化34是用輪廓跟蹤的方法將各種顏色的色塊的邊界輪廓找出來(lái)，在它們中尋找控制點(diǎn)，從而用很少的信息表達(dá)光柵圖。31 輪廓跟蹤 ：得到圖象中所有色塊的輪廓，輪廓跟蹤算法比較成熟，具體算法參見(jiàn)132基于候選點(diǎn)夾角的拐點(diǎn)尋找算法：定義1： 拐點(diǎn)-圖象輪廓上的轉(zhuǎn)折點(diǎn)，在拐點(diǎn)兩側(cè)，輪廓的走向有明顯的不同。在本文中，拐點(diǎn)被認(rèn)為是特征夾角(見(jiàn)定義5)小于某一閾值的候

9、選點(diǎn)(定義4)。拐點(diǎn)是描述圖象輪廓的重要信息。也就是在變換的過(guò)程中需要保持的信息。定義2: 尖點(diǎn)如果在輪廓上存在某一象素點(diǎn)A，滿(mǎn)足：A的0-近鄰和2-近鄰(或者2-近鄰和4-近鄰或者4-近鄰和6-近鄰或者0-近鄰和6-近鄰)是輪廓點(diǎn)，而其它近鄰不是輪廓點(diǎn)；我們稱(chēng)A為尖點(diǎn)。定義3：輪廓段在兩個(gè)候選點(diǎn)之間的輪廓線(xiàn)。在一個(gè)輪廓段，最多只能夠存在兩種不同的鏈碼值。定義4：候選點(diǎn)設(shè)lc1和lc2是當(dāng)前輪廓段的兩種鏈碼值，P點(diǎn)是當(dāng)前點(diǎn)，Q點(diǎn)是P點(diǎn)的后繼點(diǎn)。lc3是Q點(diǎn)的鏈碼值。如果：1)是尖點(diǎn)，那么，P是候選點(diǎn)；2)如果lc1!=lc2時(shí),lc3!=lc1并且lc3!=lc2，那么，P是候選點(diǎn)。3) 如果

10、lc1=lc2時(shí),如果|lc3-lc2|>1，P是候選點(diǎn)。定義5：特征夾角設(shè)A，B，C是三個(gè)候選點(diǎn)，夾角是B點(diǎn)的特征夾角。算法描述：符號(hào) : listcode是鏈碼的集合，lc1和lc2是當(dāng)前輪廓段的兩種鏈碼值，B點(diǎn)是當(dāng)前候選點(diǎn)，A點(diǎn)和C點(diǎn)分別是B的前一個(gè)和后繼候選點(diǎn)，lc3是B點(diǎn)的鏈碼值。INF-ANGLE是特征夾角的閾值。i表示當(dāng)前輪廓點(diǎn),num表示輪廓點(diǎn)的數(shù)量，bp表示輪廓點(diǎn)的集合。Dis表示前一個(gè)候選點(diǎn)和當(dāng)前點(diǎn)的序列距離,dif函數(shù)計(jì)算兩個(gè)鏈碼值之差的絕對(duì)值。算法分為9個(gè)步驟：Lc1=listcode1,lc2=listcode2;把起始象素點(diǎn)添加到候選點(diǎn)列表中，dis=0;Fo

11、r(i=2;i<num;i+)If bpi是尖點(diǎn) 把bpi添加到候選點(diǎn)列表中,lc1=listcodei+1,dis=0,continue;Else if (lc2=lc1 | dis=0) Lc2=listcodei;lc3=listcodei+1;If(lc3=lc1 | lc3=lc2) /當(dāng)前點(diǎn)bpi不是候選點(diǎn)Dis+;Continue;else if(lc1!=lc2 | dif(lc3,lc2)>1 ) / bpi是候選點(diǎn)把bpi添加到候選點(diǎn)列表中,lc1=listcodei+1,dis=0; 遍歷候選點(diǎn)集合。對(duì)于候選點(diǎn)B，如果B是尖點(diǎn)，那么，將B添加到拐點(diǎn)列表中;否則

12、，計(jì)算夾角ABC，如果夾角ABC小于某一給定值INF-ANGLE，那么，將B添加到拐點(diǎn)列表中，同時(shí)記錄下夾角ABC;33 基于控制點(diǎn)彎曲角的特殊的控制點(diǎn)尋找法控制點(diǎn)是指描述輪廓內(nèi)容的一般的輪廓點(diǎn)，也就是逼近原輪廓的多邊形的頂點(diǎn)。主要包括多邊形擬和得到的點(diǎn)，上面的拐點(diǎn)，和下面要特殊處理的特殊的控制點(diǎn)。本文采用了基于聚合的最小均誤差線(xiàn)段逼近法得到逼近多邊形。具體算法參照25用上面的方法對(duì)很多的圖象處理的結(jié)果都很好，但是對(duì)于實(shí)際應(yīng)用中的套色圖象，經(jīng)常會(huì)有很細(xì)的線(xiàn)條（一般是3個(gè)象素寬）如圖3這樣的圖像用上面的方法會(huì)出現(xiàn)什么問(wèn)題呢？通過(guò)上面的方法得到的控制點(diǎn)如圖5。 圖 3 圖4 圖5可以看到，對(duì)于伸出

13、來(lái)的枝狀的線(xiàn)條得到的控制點(diǎn)是線(xiàn)條的頂點(diǎn)，這樣，其前后的兩個(gè)控制點(diǎn)都連到該點(diǎn)，這樣，伸出來(lái)的線(xiàn)條經(jīng)過(guò)處理放大2倍就會(huì)產(chǎn)生如圖5所示的結(jié)果，使線(xiàn)條很尖，不能保持原來(lái)的形狀。針對(duì)這種情況，我們采用了基于控制點(diǎn)彎曲角6的特殊的控制點(diǎn)尋找法來(lái)將相鄰的前后兩點(diǎn)也選為控制點(diǎn)。這樣就能避免這種常見(jiàn)現(xiàn)象的出現(xiàn)。從輪廓中提取曲率較大的點(diǎn)（控制點(diǎn)），并將它們用直線(xiàn)連接起來(lái)就可以很好的勾畫(huà)出原圖的邊界。根據(jù)曲率大的點(diǎn)具有更有價(jià)值的信息，我們對(duì)得到的控制點(diǎn)進(jìn)行遍歷，如果發(fā)現(xiàn)某個(gè)控制點(diǎn)相對(duì)于其相鄰點(diǎn)有較大的曲率我們就在這個(gè)點(diǎn)周?chē)x擇一些點(diǎn)作為完善的控制點(diǎn)加入控制點(diǎn)列表。首先，我們要給出離散型曲線(xiàn)的曲率的精確的定義。而對(duì)數(shù)

14、字圖象中的曲線(xiàn)，由于切線(xiàn)斜率變化不是任意小，不能用=d/dl描述。在Freeman鏈碼中，相鄰的斜率變化只能是45°的整數(shù)倍。我們可以用(Yi+k Yi)/(Xi+k-Xi)來(lái)表示在Pi點(diǎn)的斜率（其中k>1）。對(duì)于任意一個(gè)輪廓上的點(diǎn)pi，與它相關(guān)的上下文可定義為一個(gè)對(duì)稱(chēng)的點(diǎn)的集合S(Pi) = Pi-k,Pi-1,Pi,Pi+1,Pi+k，我們可用它來(lái)度量輪廓上點(diǎn)的曲率。k是半徑（以Pi為中心的前后對(duì)稱(chēng)點(diǎn)對(duì)的數(shù)目）。定義6：k-彎曲角(k-angular bending)：定義Pa，Pb 分別為給定點(diǎn)Pi前后的兩個(gè)點(diǎn)，它們的坐標(biāo)為Pi前后k個(gè)點(diǎn)的坐標(biāo)的平均值6。Pa的坐標(biāo): X

15、a = , Ya = Pb的坐標(biāo)為：Xb = Yb = 根據(jù)這些值，k-矢量可定義為：ki = (Xa Xi, Ya Yi). ki = (Xi Xb,Yi Yb),在Pi點(diǎn)的k-彎曲角定義為兩個(gè)矢量的夾角k(Pi) = 圖6 定義：1-彎曲角1的直觀描述圖 7這些定義中，符號(hào)的正負(fù)代表了曲線(xiàn)在點(diǎn)Pi的凹(>0)凹(<0)。在實(shí)際應(yīng)用中，我們用的是1-彎曲角的定義。我們對(duì)控制點(diǎn)集合中的所有點(diǎn)進(jìn)行遍歷，當(dāng)發(fā)現(xiàn)當(dāng)前點(diǎn)的1-彎曲角大于某個(gè)值時(shí)，就將該點(diǎn)的前后兩點(diǎn)也選為控制點(diǎn)。經(jīng)過(guò)測(cè)試，將閾值設(shè)為120度效果較好。上圖是圖7通過(guò)上面的方法的到的放大2倍的結(jié)果，可見(jiàn)該方法對(duì)于消除尖點(diǎn)是很有效

16、的。4.基于矢量的圖象變換和圖象重構(gòu)通過(guò)上面的矢量化，圖象可以有很少的邊界的控制點(diǎn)來(lái)表示了，基于矢量的圖象變換就是將變換矩陣（旋轉(zhuǎn)、縮放）作用到控制點(diǎn)上。將相同色塊的輪廓的控制點(diǎn)連起來(lái)就生成了變換后的目標(biāo)圖象的輪廓，對(duì)得到的輪廓進(jìn)行多邊形填充就可以得到目標(biāo)圖象。5.實(shí)驗(yàn)結(jié)果及結(jié)論圖8是原始圖，圖9是原圖旋轉(zhuǎn)30度得到的結(jié)果，圖10是原圖放大1.2倍得到的結(jié)果，可以看出，得到的結(jié)果和B樣條算法相比能在保持光滑性的同時(shí)保持了圖象的原來(lái)的特征形狀。圖象的光滑處理是一個(gè)一直沒(méi)能得到徹底解決的問(wèn)題，特別是套色圖象的光滑變換中一直沒(méi)有一個(gè)令人滿(mǎn)意的解決方法。如何能在圖象變換過(guò)程中既能保持原有的形狀又能保證

17、邊界的光滑是一個(gè)非常困難的問(wèn)題。本文提出的基于矢量化的方法通過(guò)減少變換矩陣作用的象素?cái)?shù)和在變換中保持圖象原有的特征的方法，快速而簡(jiǎn)單的解決了該問(wèn)題。實(shí)驗(yàn)表明本算法能魯棒地處理各種套色圖象。圖 8 原始圖象圖10 放大1.2倍的結(jié)果圖 9 旋轉(zhuǎn)30度的結(jié)果 參 考 文獻(xiàn)1Pavlids, T., Algorithms for Graphics and Image Processing M, Computer Science Press, 1982.2吳良武,保持輪廓清晰光滑的灰度圖象放大算法, 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)J,2002, 14(4):306-3093沈立,張晨曦，黑白圖像得矢量化J

18、，計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào).2000, 12(3):170-1734董海衛(wèi)，江早，王永軍，基于矢量化二值工程圖得符號(hào)提取算法J，計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào).2000, 12(4):294-2985Shu Chien Huang ,Yung Nien Sun Polygonal approximation using genetic algorithmsC Proceedings of CAIP'99, Ljubljana, Slovenia, 1-3 September, 1999, pp. 175-1826Vincent Beau,Mark Singer, Reduced resolution and scale space for dominant feature de