[發(fā)明專利]一種誤差可控的細(xì)分曲面圖像矢量化方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201710304102.6
• 申請(qǐng)日: 2017-05-03
• 公開(kāi)（公告）號(hào): CN107256557B
• 公開(kāi)（公告）日: 2020-05-22
• 發(fā)明（設(shè)計(jì)）人: 陳愛(ài)芬;李桂清;王宇攀;聶勇偉
• 申請(qǐng)（專利權(quán)）人: 華南理工大學(xué)
• 主分類號(hào): G06T7/13
• 分類號(hào): G06T7/13;G06T5/00;H04N19/94
• 代理公司: 廣州市華學(xué)知識(shí)產(chǎn)權(quán)代理有限公司 44245
• 代理人: 羅觀祥

1.一種誤差可控的細(xì)分曲面圖像矢量化方法，其特征在于，包括以下步驟：

1)檢測(cè)圖像邊緣特征

圖像邊緣是最顯著的圖像特征，為了在構(gòu)造保持圖像特征的基網(wǎng)格，使用圖像邊緣線段檢測(cè)方法來(lái)提取圖像的一個(gè)像素寬的特征線，其步驟為：

①高斯濾波：用高斯核卷積圖像來(lái)抑制圖像噪聲和平滑圖像；

②計(jì)算梯度幅值和邊緣方向圖：首先使用梯度算子分別計(jì)算出像素點(diǎn)的水平和垂直梯度，然后算出圖像梯度幅值圖，與此同時(shí)，比較像素水平和垂直梯度的大小，確定該像素點(diǎn)的邊緣方向，如果水平梯度較大，則認(rèn)為通過(guò)該像素是個(gè)垂直方向邊緣，反之亦然；

③提取錨點(diǎn)：錨點(diǎn)被認(rèn)為是邊緣結(jié)束的地方，即在水平和垂直方向特征變化劇烈的像素點(diǎn)，這里選擇局部梯度極值作為錨點(diǎn)，通過(guò)比較像素點(diǎn)與其相鄰像素點(diǎn)的梯度值來(lái)判斷該像素點(diǎn)是否是錨點(diǎn)，對(duì)于一個(gè)水平方向的像素點(diǎn)，將其與左右相鄰的像素點(diǎn)比較，如果該像素點(diǎn)的梯度值比左右相鄰像素梯度值大指定閾值，則認(rèn)為該像素點(diǎn)為錨點(diǎn)；

④連接錨點(diǎn)形成線段：根據(jù)梯度幅值和邊緣方向圖來(lái)連接相鄰錨點(diǎn)，每次從還未被檢測(cè)過(guò)的錨點(diǎn)開(kāi)始，觀察穿過(guò)該錨點(diǎn)的邊緣方向，如果是水平邊緣，通過(guò)向左和向右行進(jìn)開(kāi)始連接過(guò)程，如果垂直邊緣通過(guò)錨點(diǎn)，通過(guò)向上和向下行進(jìn)進(jìn)行連接過(guò)程，在移動(dòng)期間，僅考慮三個(gè)直接鄰居像素，并且選擇具有最大梯度值的那個(gè)鄰居像素，當(dāng)遇到梯度幅值為0的像素點(diǎn)或遇到之前已經(jīng)檢測(cè)過(guò)的邊緣像素時(shí)，該次處理過(guò)程停止；

2)構(gòu)造基于圖像特征的初始網(wǎng)格，并在網(wǎng)格中標(biāo)記圖像特征

在2D圖像平面上建立像素分辨率的初始三角網(wǎng)格M：首先，建立初始網(wǎng)格頂點(diǎn)，圖像中的每個(gè)像素點(diǎn)對(duì)應(yīng)網(wǎng)格中的一個(gè)頂點(diǎn)，并在頂點(diǎn)的屬性中記錄像素點(diǎn)的顏色值，然后以行和列的方式連接網(wǎng)格頂點(diǎn)形成矩形網(wǎng)格，根據(jù)圖像特征線將網(wǎng)格中的每個(gè)矩形網(wǎng)格劃分成兩個(gè)三角網(wǎng)格；

圖像顏色不連續(xù)性與至少兩個(gè)具有非常不同顏色強(qiáng)度的相鄰像素相關(guān)聯(lián)，單獨(dú)的圖像邊緣線不足以表示圖像顏色的不連續(xù)性，因此，提出使用雙特征線來(lái)表示圖像顏色的不連續(xù)，首先使用等值線追蹤算法找出圖像特征線兩側(cè)的距離一像素的平行線段，然后通過(guò)比較兩側(cè)的圖像梯度選擇平均梯度大的線段作為另一特征線，并對(duì)受影響的三角網(wǎng)格進(jìn)行重新三角化；

接下來(lái)，對(duì)初始網(wǎng)格的邊和頂點(diǎn)的類型進(jìn)行標(biāo)記，從而在后續(xù)的網(wǎng)格簡(jiǎn)化、細(xì)分操作中對(duì)不同的類型進(jìn)行不同的處理以保持重要的圖像特征；將網(wǎng)格的邊分為三種類型：邊界邊、平滑邊、折痕邊，將網(wǎng)格的頂點(diǎn)分為四種類型：邊界點(diǎn)、平滑點(diǎn)、折痕點(diǎn)、角點(diǎn)；將圖像的雙特征線標(biāo)記為折痕邊，將圖像矩陣邊界的邊標(biāo)記為邊界邊，其他邊為平滑邊；對(duì)于網(wǎng)格頂點(diǎn)，如果頂點(diǎn)只與平滑邊緣連接，則該頂點(diǎn)標(biāo)記為平滑點(diǎn)；折痕頂點(diǎn)與兩條鄰接的折痕邊連接；邊界點(diǎn)與兩條鄰接的邊界邊連接；圖像特征線端點(diǎn)、特征線交叉點(diǎn)標(biāo)記為角點(diǎn)；為了固定矩形圖像邊界，四個(gè)角被標(biāo)記為角點(diǎn)；

3)簡(jiǎn)化初始網(wǎng)格，構(gòu)造保持圖像特征的基網(wǎng)格

采用QEM簡(jiǎn)化算法來(lái)簡(jiǎn)化圖像初始網(wǎng)格，得到基網(wǎng)格M_B，將網(wǎng)格的顏色屬性看成高度場(chǎng)來(lái)計(jì)算二次誤差代價(jià)，并且在簡(jiǎn)化過(guò)程中使用細(xì)分曲線來(lái)擬合圖像特征線段來(lái)保持圖像特征；

在上一步驟中，根據(jù)圖像特征對(duì)網(wǎng)格的頂點(diǎn)和邊做了分類，為了保持圖像的形狀和特征，對(duì)于不同的特征采取不同的處理方式：①角點(diǎn)不允許被折疊；②邊界點(diǎn)只能與其鄰接的同邊界的兩個(gè)邊界點(diǎn)折疊；③折痕點(diǎn)只能與其鄰接的同折痕邊的兩個(gè)折痕點(diǎn)折疊；④平滑點(diǎn)可以折疊到特征點(diǎn)；

此外，為了得到一個(gè)高質(zhì)量的保持圖像特征的基網(wǎng)格，改進(jìn)QEM算法的邊折疊代價(jià)，在邊折疊代價(jià)中加入特征邊形變代價(jià)Q_feature、三角形正則性代價(jià)Q_re、面積代價(jià)Q_area，并賦予它們相應(yīng)的權(quán)重，用Q_qem表示QEM代價(jià)，則能夠把邊折疊的代價(jià)表示為：

Cost(v₁,v₂)＝αQ_qem(v₁,v₂)+βQ_feature(v₁,v₂)+γQ_re(v₁,v₂)+δQ_area(v₁,v₂) (1)

式中，權(quán)重α,β,γ,δ由用戶指定，邊折疊順序按照Cost(v₁,v₂)從小到大進(jìn)行；需要特別說(shuō)明的是，為了保證簡(jiǎn)化后二維網(wǎng)格的質(zhì)量，除了在計(jì)算QEM代價(jià)時(shí)，將網(wǎng)格M的顏色屬性看成高度場(chǎng)，在計(jì)算其他代價(jià)時(shí)，考慮的都只是二維圖像網(wǎng)格，不考慮顏色屬性，其中QEM代價(jià)Q_qem、特征邊形變代價(jià)Q_feature、三角形正則性代價(jià)Q_re、面積代價(jià)Q_area的定義如下：

QEM代價(jià)Q_qem：用二次誤差代價(jià)來(lái)計(jì)算邊的二次誤差代價(jià)，其衡量的是三維空間點(diǎn)到平面的距離，而網(wǎng)格M是個(gè)二維網(wǎng)格，所以將網(wǎng)格M的顏色屬性看成高度場(chǎng)，分別用RGB的值作為高度，則每條邊可計(jì)算出三個(gè)代價(jià)，將其和作為該邊的二次誤差代價(jià)Q_qem；

特征邊形變代價(jià)Q_feature：QEM代價(jià)沒(méi)有考慮到模型的尖銳特征，不能反映圖像的特征，定義Q_feature為折疊前的特征點(diǎn)到其鄰接的兩個(gè)特征點(diǎn)連線的距離，用來(lái)衡量特征邊折疊結(jié)果與折疊點(diǎn)的偏離程度，Q_feature值越小，表明偏離越小，如果折疊的邊是非特征邊，則Q_feature值為0；

三角形正則性代價(jià)Q_re：在邊折疊代價(jià)中加入三角形正則性代價(jià)是為了減少狹長(zhǎng)的三角面片的出現(xiàn)，三角形的正則性被用來(lái)表示其接近正三角形的程度，能夠用R(t)＝cos(∠A)+cos(∠B)+cos(∠C)來(lái)度量三角形t＝ΔABC的正則性，令Re(t)＝3-2R(t)，則0≤Re(t)≤1，Re(t)的值越小，表明該三角形的正則性越高，則定義三角面片集合T的正則性為：

Re(T)＝max{Re(t)|t∈T} (2)

把Q_re定義為邊折疊前后，相關(guān)三角面片的正則性增量，則邊折疊的正則性代價(jià)定義為：

式中，表示頂點(diǎn)的鄰接三角面片；

面積代價(jià)Q_area：三角形正則性代價(jià)Q_re反映了三角面片的形狀，沒(méi)有反映面片大小，因此，在總代價(jià)中加入面積代價(jià)來(lái)約束面片的面積，把面積代價(jià)Q_area定義為邊折疊后新頂點(diǎn)所有鄰接面的面積總和，則邊折疊的面積代價(jià)定義為：

式中，area(t)表示三角形t的面積；

其中，網(wǎng)格簡(jiǎn)化算法的步驟如下：

①設(shè)置邊折疊代價(jià)公式(1)中的各項(xiàng)權(quán)值；

②將網(wǎng)格M的顏色屬性看成高度場(chǎng)，計(jì)算網(wǎng)格所有邊的QEM代價(jià)Q_qem；

③計(jì)算所有可折疊邊的折疊代價(jià)，根據(jù)折疊代價(jià)將其放入最小堆中，根據(jù)公式(1)計(jì)算出每條邊對(duì)應(yīng)的兩條半邊的折疊代價(jià)，則邊的折疊代價(jià)取兩個(gè)半邊代價(jià)的小值，并記錄折疊方向；

④從堆中取出最小折疊代價(jià)的邊，判斷其折疊后相關(guān)面是否會(huì)反生翻轉(zhuǎn)，若會(huì)，則給該邊的代價(jià)加一個(gè)懲罰值，更新其在堆中的位置；若不會(huì)反生翻轉(zhuǎn)，則判斷該邊是否是特征邊，若是特征邊，擬合調(diào)整特征點(diǎn)的位置并判斷其折疊后擬合誤差是否符合要求，若不符合，則不折疊該邊，將其從堆中刪除；否則就完成該邊的折疊操作，重新計(jì)算相關(guān)邊的折疊代價(jià)并更新它們?cè)诙阎械奈恢茫?/p>

⑤若達(dá)到簡(jiǎn)化的要求或最小堆為空，則轉(zhuǎn)到⑥，否則轉(zhuǎn)到④；

⑥刪除網(wǎng)格中的獨(dú)立頂點(diǎn)，更新網(wǎng)格，輸出基網(wǎng)格；

雖然在網(wǎng)格簡(jiǎn)化過(guò)程中考慮了面片正則性、面積因素，但是仍不能保證能得到一個(gè)高質(zhì)量基網(wǎng)格，因此使用Laplacian算子對(duì)網(wǎng)格進(jìn)行幾何優(yōu)化：

其中N(v)和|N(v)|分別表示頂點(diǎn)v的1鄰域的所有頂點(diǎn)集合和個(gè)數(shù)；網(wǎng)格中頂點(diǎn)的新位置由v^new＝v+λΔv迭代式給出，其中λ取值為0.3；

為了保持圖像的特征，對(duì)網(wǎng)格特征頂點(diǎn)進(jìn)行特殊處理：首先，角點(diǎn)不進(jìn)行移動(dòng)，對(duì)于邊界頂點(diǎn)和特征點(diǎn)v，設(shè)(v_a,v)和(v,v_b)為v所在的兩條特征邊，則v只根據(jù)v_a和v_b的位置進(jìn)行調(diào)整，即Laplacian算子定義為：

需要說(shuō)明的是，網(wǎng)格優(yōu)化能夠在網(wǎng)格簡(jiǎn)化的過(guò)程中進(jìn)行，也能夠在網(wǎng)格簡(jiǎn)化結(jié)束后進(jìn)行，如果網(wǎng)格優(yōu)化會(huì)造成面片翻轉(zhuǎn)，則暫時(shí)不進(jìn)行優(yōu)化；

4)誤差可控的Loop細(xì)分曲面擬合求得控制網(wǎng)格

經(jīng)過(guò)網(wǎng)格的簡(jiǎn)化和優(yōu)化得到反映圖像特征的基網(wǎng)格后，提出帶誤差控制的Loop細(xì)分曲面擬合來(lái)對(duì)圖像顏色進(jìn)行擬合，在計(jì)算控制網(wǎng)格的過(guò)程中進(jìn)行誤差控制，用戶能夠通過(guò)指定重構(gòu)圖像的誤差來(lái)獲得滿足需求的矢量圖像，該過(guò)程包括三個(gè)部分：控制網(wǎng)格的計(jì)算、誤差控制以及自適應(yīng)細(xì)分，具體如下：

4.1)控制網(wǎng)格的計(jì)算

為了增加擬合目標(biāo)的數(shù)據(jù)量，首先對(duì)基網(wǎng)格M_B進(jìn)行一次1-4細(xì)分得到網(wǎng)格然后使用網(wǎng)格對(duì)原圖像進(jìn)行采樣得到M_R，將M_R作為擬合的目標(biāo)；像素點(diǎn)的顏色值在圖像特征區(qū)域有著顯著的變化，為了采樣到準(zhǔn)確的顏色值，對(duì)不同的網(wǎng)格特征采用不同的采樣方式得到頂點(diǎn)的顏色值：對(duì)于折痕頂點(diǎn)，它的目標(biāo)顏色為它所在的圖像特征線上和它位置最接近的像素點(diǎn)的顏色值；對(duì)于角點(diǎn)，它在簡(jiǎn)化過(guò)程和細(xì)分過(guò)程中的位置都沒(méi)有移動(dòng)，所以它的目標(biāo)顏色為頂點(diǎn)坐標(biāo)確定的圖像像素點(diǎn)的顏色值；對(duì)于平滑頂點(diǎn)，其顏色由其周圍的像素點(diǎn)進(jìn)行雙線性插值得到；

在網(wǎng)格簡(jiǎn)化過(guò)程中已經(jīng)擬合了網(wǎng)格的特征頂點(diǎn)位置，為了計(jì)算方便，這里只擬合網(wǎng)格頂點(diǎn)的顏色，因此所要計(jì)算的控制網(wǎng)格M_C和基網(wǎng)格M_B具有相同的拓?fù)浣Y(jié)構(gòu)，對(duì)控制網(wǎng)格M_C進(jìn)行一次Loop細(xì)分后獲得的網(wǎng)格和M_R具有相同的拓?fù)潢P(guān)系；根據(jù)Loop極限模版求網(wǎng)格的極限得到細(xì)分極限曲面M_S，擬合目標(biāo)就是：

M_R＝M_S (7)

設(shè)基網(wǎng)格M_B和目標(biāo)網(wǎng)格M_C的頂點(diǎn)數(shù)分別為n和m，分別用表示網(wǎng)格M_C、M_R、M_S的頂點(diǎn)顏色構(gòu)成的向量，則根據(jù)帶尖銳特征的Loop細(xì)分模版和極限模版，存在有細(xì)分矩陣S_m×n和極限矩陣L_m×m使得：所以可以將Loop細(xì)分?jǐn)M合方程(7)表示為：

令Z_m×n＝L_m×mS_m×n，方程組(8)變換為：

通過(guò)求解線性方程組(9)就能夠得到控制網(wǎng)格M_C，因?yàn)檫@里擬合的是網(wǎng)格頂點(diǎn)的顏色，所以和的大小分別為n×3和m×3，RGB三種顏色能夠分開(kāi)求解；

4.2)誤差控制

將每個(gè)像素點(diǎn)的重構(gòu)誤差定義為重構(gòu)圖像與原圖像對(duì)應(yīng)像素點(diǎn)顏色值的歐式距離，而將整個(gè)圖像的重構(gòu)誤差e定義為所有像素點(diǎn)重構(gòu)誤差的均值，每個(gè)基網(wǎng)格面片的重構(gòu)誤差e^f定義為該面片光柵化后所對(duì)應(yīng)的所有像素點(diǎn)重構(gòu)誤差的均值；

在上一步驟中，通過(guò)Loop細(xì)分曲面擬合求得控制網(wǎng)格，使其對(duì)應(yīng)的細(xì)分曲面盡可能接近原圖像，但是控制網(wǎng)格的頂點(diǎn)數(shù)目依賴于網(wǎng)格簡(jiǎn)化，如果簡(jiǎn)化過(guò)度，使得控制網(wǎng)格頂點(diǎn)數(shù)目過(guò)少，自由度過(guò)大，就可能導(dǎo)致重構(gòu)圖像與原圖像在某些區(qū)域存在較大的重構(gòu)誤差，因此通過(guò)對(duì)誤差較大的區(qū)域進(jìn)行自適應(yīng)細(xì)分來(lái)控制圖像的重構(gòu)誤差，使得用戶能夠得到指定誤差的重構(gòu)圖像；

對(duì)于重構(gòu)誤差的計(jì)算，首先根據(jù)帶尖銳特征的Loop細(xì)分規(guī)則和極限規(guī)則估計(jì)控制網(wǎng)格的極限曲面，計(jì)算出極限曲面上每個(gè)像素點(diǎn)的顏色值，即光柵化矢量表示，然后根據(jù)每個(gè)像素點(diǎn)所在的基網(wǎng)格面片，計(jì)算基網(wǎng)格每個(gè)面片的重構(gòu)誤差e^f，最后計(jì)算整個(gè)重構(gòu)圖像的誤差e；通過(guò)以上分析，誤差可控的控制網(wǎng)格的求取的流程如下：

①備份基網(wǎng)格M_B，使用Loop曲面擬合方法計(jì)算控制網(wǎng)格M_C；

②根據(jù)細(xì)Loop分規(guī)則和極限規(guī)則估計(jì)控制網(wǎng)格M_C的極限曲面M_S；

③對(duì)于原光柵圖像每個(gè)像素點(diǎn)的顏色值I(i)，根據(jù)重心坐標(biāo)計(jì)算出極限曲面M_S上對(duì)應(yīng)像素點(diǎn)的顏色值I′(i)，計(jì)算像素點(diǎn)誤差e_i，并找到該像素點(diǎn)對(duì)應(yīng)的基網(wǎng)格面片，然后計(jì)算基網(wǎng)格M_B每個(gè)面片內(nèi)所有像素點(diǎn)的平均誤差e^f，最后計(jì)算整個(gè)圖像的平均重構(gòu)誤差e；

④如果平均重構(gòu)誤差e小于用戶指定的平均誤差閾值ε，則終止算法，輸出控制網(wǎng)格M_C；否則找出基網(wǎng)格中M_B前k個(gè)最大平均誤差的面片集合，并標(biāo)記這些面片為需要進(jìn)行自適應(yīng)細(xì)分；其中k≥1由用戶指定，k越大，平均誤差下降越快；

⑤對(duì)被標(biāo)記的基網(wǎng)格面片進(jìn)行自適應(yīng)細(xì)化求得新的基網(wǎng)格M_B，然后再轉(zhuǎn)到步驟①，繼續(xù)整個(gè)過(guò)程，直到得到指定誤差的重構(gòu)圖像；

4.3)自適應(yīng)細(xì)分

自適應(yīng)細(xì)分允許只對(duì)感興趣的區(qū)域進(jìn)行細(xì)分，在誤差控制中，需要對(duì)被標(biāo)記為不滿足誤差要求的面片進(jìn)行自適應(yīng)細(xì)分來(lái)局部增加控制頂點(diǎn)的數(shù)目，從而減少誤差；為了避免新網(wǎng)格產(chǎn)生裂縫，必須對(duì)被標(biāo)記的面片和其鄰面都進(jìn)行細(xì)分；對(duì)于被標(biāo)記的網(wǎng)格面片，對(duì)其進(jìn)行1-4細(xì)分，對(duì)于沒(méi)被標(biāo)記的面片，根據(jù)其鄰面被標(biāo)記的情況來(lái)進(jìn)行細(xì)分：①如果該面片具有0個(gè)被標(biāo)記的鄰面，則不對(duì)其進(jìn)行細(xì)分；②如果該面片具有1個(gè)被標(biāo)記的鄰面，則對(duì)其進(jìn)行1-2細(xì)分；③如果該面片具有2個(gè)被標(biāo)記的鄰面，則對(duì)其進(jìn)行1-3細(xì)分；④如果該面片具有3個(gè)被標(biāo)記的鄰面，則對(duì)其進(jìn)行1-4細(xì)分；對(duì)基網(wǎng)格的所有面片用上述細(xì)分模式進(jìn)行細(xì)分后，就完成一次自適應(yīng)細(xì)分，形成新的基網(wǎng)格；

5)光柵化矢量表示

為了在顯示設(shè)備中顯示前面步驟得到的矢量表示需要渲染控制網(wǎng)格M_C面片和它們相關(guān)的顏色信息到一個(gè)離散的光柵圖像，也將該過(guò)程稱為矢量表示光柵化；

矢量表示是基于細(xì)分曲面，所以要先求得對(duì)應(yīng)的細(xì)分曲面，再將其離散化成光柵圖像，其中，光柵化流程為：

①根據(jù)帶尖銳特征的Loop細(xì)分規(guī)則對(duì)控制網(wǎng)格M_C做r次細(xì)分得一個(gè)細(xì)化的網(wǎng)格M_r，r＝2,3…；

②根據(jù)帶尖銳特征的Loop極限規(guī)則將M_r的頂點(diǎn)都移到對(duì)應(yīng)的極限位置，從而得到逼近的分段細(xì)分曲面M_S；

③由于M_S是個(gè)分段線性曲面，曲面上的任一點(diǎn)顏色值都能夠用該點(diǎn)所在三角面片的三個(gè)頂點(diǎn)顏色值進(jìn)行線性表示；使用重心坐標(biāo)來(lái)計(jì)算三個(gè)頂點(diǎn)的權(quán)重，對(duì)于整個(gè)極限曲面網(wǎng)格M_S，其渲染流程：循環(huán)遍歷M_S的每個(gè)面片，對(duì)于每個(gè)三角面片，找出這個(gè)面片的包圍盒，對(duì)于包圍盒里面的每個(gè)整數(shù)像素點(diǎn)，判斷該點(diǎn)是否屬于該三角面片，如果是，求出它的重心坐標(biāo)，最后根據(jù)重心坐標(biāo)算該像素點(diǎn)的顏色值；在遍歷網(wǎng)格全部三角面之后，即能夠?qū)?duì)應(yīng)的光柵圖像素點(diǎn)的顏色全部填滿，從而實(shí)現(xiàn)光柵圖像的生成。