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

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

2、分類號:TP 391 文獻標(biāo)識碼:A 文章編號: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)成的圖象，不同色塊間具有明顯的分界線，已被廣泛的應(yīng)用于紡織、印染等工業(yè)中。以簡單的圖象旋轉(zhuǎn)為例，經(jīng)過旋轉(zhuǎn)變換，象素點的坐標(biāo)總要乘以一個旋轉(zhuǎn)矩陣，這樣產(chǎn)生的浮點

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

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

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

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

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

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

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

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

14、字圖象中的曲線，由于切線斜率變化不是任意小，不能用=d/dl描述。在Freeman鏈碼中，相鄰的斜率變化只能是45°的整數(shù)倍。我們可以用(Yi+k Yi)/(Xi+k-Xi)來表示在Pi點的斜率（其中k>1）。對于任意一個輪廓上的點pi，與它相關(guān)的上下文可定義為一個對稱的點的集合S(Pi) = Pi-k,Pi-1,Pi,Pi+1,Pi+k，我們可用它來度量輪廓上點的曲率。k是半徑（以Pi為中心的前后對稱點對的數(shù)目）。定義6：k-彎曲角(k-angular bending)：定義Pa，Pb 分別為給定點Pi前后的兩個點，它們的坐標(biāo)為Pi前后k個點的坐標(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點的k-彎曲角定義為兩個矢量的夾角k(Pi) = 圖6 定義：1-彎曲角1的直觀描述圖 7這些定義中，符號的正負代表了曲線在點Pi的凹(>0)凹(<0)。在實際應(yīng)用中，我們用的是1-彎曲角的定義。我們對控制點集合中的所有點進行遍歷，當(dāng)發(fā)現(xiàn)當(dāng)前點的1-彎曲角大于某個值時，就將該點的前后兩點也選為控制點。經(jīng)過測試，將閾值設(shè)為120度效果較好。上圖是圖7通過上面的方法的到的放大2倍的結(jié)果，可見該方法對于消除尖點是很有效

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

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

18、，計算機輔助設(shè)計與圖形學(xué)學(xué)報.2000, 12(3):170-1734董海衛(wèi)，江早，王永軍，基于矢量化二值工程圖得符號提取算法J，計算機輔助設(shè)計與圖形學(xué)學(xué)報.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