基于改進(jìn)Loop細(xì)分的二維圖像矢量化方法

鄧重陽，熊玉丹，鄭樂豪，曹晨妤，朱明超

(杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018)

0 引 言

矢量圖具有較好的擴(kuò)展性和可編輯性，廣泛應(yīng)用于建立圖像檔案數(shù)據(jù)庫、分析和編輯圖像等領(lǐng)域。L.Demaret等[1]基于Delaunay三角剖分矢量化原始圖像，但該方法未充分考慮圖像中的邊緣線等特征信息，從而得到的矢量圖不能充分地逼近原圖像[2]。Liao Z.C.等[3]采用分片光滑的細(xì)分曲面來表達(dá)原始圖像。該方法表達(dá)較為靈活，但需要存儲(chǔ)邊緣特征信息使得矢量圖縮放時(shí)計(jì)算不方便。本文采用改進(jìn)的Loop細(xì)分方法實(shí)現(xiàn)圖像矢量化，使得到的矢量圖在不失真且較好保持邊界輪廓的情況下，達(dá)到縮放自如的效果。

1 改進(jìn)的Loop細(xì)分方法框架

圖1 改進(jìn)的Loop細(xì)分方法框架圖

本文提出的改進(jìn)的Loop細(xì)分方法采用Douglas-Peucker算法提取圖像邊界，用Delaunay三角剖分算法得到三角網(wǎng)格，最后通過細(xì)分三角網(wǎng)格得到矢量圖。在對(duì)三角網(wǎng)格頂點(diǎn)進(jìn)行線性細(xì)分的過程中，對(duì)頂點(diǎn)的像素值進(jìn)行Loop細(xì)分，同時(shí)修改了網(wǎng)格邊界三角形內(nèi)部新點(diǎn)生成規(guī)則，具體框架如圖1所示。

2 邊界提取

改進(jìn)的Loop細(xì)分方法采用Douglas-Peucker算法提取圖像邊界。Douglas-Peucker算法通過多邊形來擬合曲線，能夠在一定程度上保持原有的形狀，并減少需提取的邊界點(diǎn)數(shù)。優(yōu)點(diǎn)在于平移和旋轉(zhuǎn)不變性，給定曲線與閾值后，抽樣結(jié)果一定，Douglas-Peucker算法通常用于線狀矢量數(shù)據(jù)壓縮、軌跡數(shù)據(jù)壓縮等[4]。在較好保持邊界輪廓的情況下，Douglas-Peucker算法能減少計(jì)算量，Douglas-Peucker算法擬合邊界輪廓的效果如圖2所示。

圖2 Douglas-Peucker算法邊界提取輪廓效果圖

3 Delaunay三角剖分

Delaunay三角剖分算法有許多優(yōu)異特性，如區(qū)域性(新增、刪除、移動(dòng)某一個(gè)頂點(diǎn)時(shí)只會(huì)影響臨近的三角形)、唯一性、具有凸多邊形的外殼等[5]。在網(wǎng)格生成中，Chew第二算法是Delaunay細(xì)化算法，用于創(chuàng)建質(zhì)量受限的Delaunay三角剖分。該算法采用分段線性系統(tǒng)(Piecewise-Linear System, PLS)并返回僅質(zhì)量三角形的約束Delaunay三角剖分，其中質(zhì)量由三角形中的最小角度定義。Chew第二算法保證終止并生成局部特征尺寸級(jí)別的網(wǎng)格，最小角度可達(dá)28.6°。本文采用Chew第二算法實(shí)現(xiàn)Delaunay三角剖分。

4 Loop細(xì)分

改進(jìn)的Loop細(xì)分方法對(duì)Delaunay三角剖分得到的三角網(wǎng)格進(jìn)行細(xì)分。記三角網(wǎng)格的頂點(diǎn)坐標(biāo)為(x,y)，并將每個(gè)頂點(diǎn)的像素值記為(r,g,b)。在整個(gè)細(xì)分過程中，對(duì)三角網(wǎng)格頂點(diǎn)進(jìn)行線性細(xì)分，即生成新點(diǎn)時(shí)，新點(diǎn)的坐標(biāo)值取左右兩頂點(diǎn)的中點(diǎn)；對(duì)該點(diǎn)的像素值(r,g,b)進(jìn)行Loop細(xì)分。同時(shí)，在原有Loop細(xì)分規(guī)則的基礎(chǔ)上，修改網(wǎng)格邊界上的三角形內(nèi)部新點(diǎn)生成規(guī)則。

4.1 Loop細(xì)分和線性細(xì)分規(guī)則

曲面細(xì)分本質(zhì)上是通過加入新點(diǎn)的方式把多邊形分解成更加細(xì)小的多邊形，從而提升對(duì)原始圖像的幾何逼真度。進(jìn)行曲面細(xì)分時(shí)，需要通過特定的幾何規(guī)則計(jì)算新頂點(diǎn)的坐標(biāo)，特定的拓?fù)湟?guī)則確定新頂點(diǎn)的連接關(guān)系。Loop細(xì)分方法以三角形網(wǎng)格為基礎(chǔ)，通過不斷地把三角網(wǎng)格細(xì)分成更密的三角網(wǎng)格，最后得到極限曲面是1個(gè)光滑曲面。Loop細(xì)分的拓?fù)湟?guī)則為1～4細(xì)分，即三角形的每條邊加入1個(gè)新點(diǎn)(稱為新邊點(diǎn))，并更新原來3個(gè)頂點(diǎn)的坐標(biāo)(稱為新頂點(diǎn))，再把新邊點(diǎn)與其附近2個(gè)新頂點(diǎn)、其它2個(gè)新邊點(diǎn)相連生成4個(gè)三角形。新頂點(diǎn)、新邊點(diǎn)的計(jì)算方法稱為幾何規(guī)則，具體系數(shù)如圖3所示。

圖3 標(biāo)準(zhǔn)Loop細(xì)分規(guī)則

圖4 線性細(xì)分規(guī)則

對(duì)三角網(wǎng)格頂點(diǎn)附加的像素值進(jìn)行Loop細(xì)分的具體實(shí)現(xiàn)步驟為：先通過圖3(b)和圖3(d)的新點(diǎn)生成規(guī)則產(chǎn)生新點(diǎn)，再根據(jù)圖3(a)和圖3(c)頂點(diǎn)更新規(guī)則更新舊點(diǎn)，產(chǎn)生新的點(diǎn)。

線性細(xì)分的規(guī)則如圖4所示。

4.2 改進(jìn)后的Loop細(xì)分規(guī)則

圖5 修改后Loop細(xì)分規(guī)則[6]

4.3 實(shí)驗(yàn)結(jié)果及分析

通過2個(gè)實(shí)例來驗(yàn)證采用本文提出的Loop細(xì)分方法提取矢量圖的效果。實(shí)驗(yàn)環(huán)境如下：CPU為酷睿I5-4200H，內(nèi)存為4 GB，硬盤大小為1 TB，軟件采用MATLAB2016。

實(shí)例1是一張二維彩色蘋果圖，圖2(a)為原始圖像，通過本文改進(jìn)方法提取的矢量圖及局部放大圖如圖6所示，實(shí)例2是一張二維彩色珍珠圖，原始圖與改進(jìn)方法提取的效果如圖7所示。

圖6 改進(jìn)方法提取圖像的效果圖——實(shí)例1

圖7 改進(jìn)方法提取圖像的效果圖——實(shí)例2

觀察圖6和圖7可以看出：矢量化后的圖像邊界輪廓幾乎沒有發(fā)生改變，說明本文提出的改進(jìn)的Loop細(xì)分方法能較好地保持圖像的邊界輪廓，并且矢量圖相對(duì)于原圖清晰度更高。圖6(b)和圖6(c)中，原始圖像放大后很模糊，出現(xiàn)馬賽克，而矢量效果圖放大后清晰光滑，說明矢量圖效果較好。

5 結(jié)束語

針對(duì)現(xiàn)有矢量化方法得到的矢量圖縮放不方便的問題，本文提出改進(jìn)的Loop細(xì)分方法，較好地實(shí)現(xiàn)了圖像矢量化，得到的矢量圖縮放較為方便。與其它圖像矢量化方法相比，本文方法操作簡(jiǎn)單，具有一定的應(yīng)用價(jià)值。但是，對(duì)于顏色較為復(fù)雜的圖像，需要根據(jù)顏色分區(qū)域進(jìn)行Loop細(xì)分，從而計(jì)算復(fù)雜度有所增加，這是下一步研究的方向。