朱　濤　羅仕鑒

摘要：紋理合成是當(dāng)前計(jì)算機(jī)圖形學(xué)、計(jì)算機(jī)視覺和圖像處理領(lǐng)域的研究熱點(diǎn)之一。文章對(duì)基于樣圖的二維紋理合成技術(shù)進(jìn)行了研究，有機(jī)結(jié)合了前人的一些觀點(diǎn)，在此基礎(chǔ)上提出了一種新的算法：在Efros和Liang提出的塊拼接紋理合成算法的基礎(chǔ)上融入Ashikhmin提出的基于位置相對(duì)性的合成技術(shù)，并加入與視覺相關(guān)的權(quán)值，得到了很好的視覺效果。

關(guān)鍵詞：紋理合成；紋理連貫性；MRF模型；塊拼接

0引言

紋理映射是繪制復(fù)雜場(chǎng)景真實(shí)感圖形最為常用的技術(shù)，但由于采樣區(qū)域的局限，所獲取的紋理樣本通常為小塊紋理，若將小塊紋理直接映射到大的曲面上，它將導(dǎo)致映射后表面紋理模糊不清，若采用重復(fù)映射技術(shù)，則可能出現(xiàn)表面紋理接縫走樣等問題。

基于樣圖的紋理合成，是近幾年迅速發(fā)展起來的一種新的紋理合成技術(shù)。它基于給定的小區(qū)域紋理樣本，按照表面的幾何形狀，拼合生成整個(gè)曲面的紋理，紋理在視覺上是相似而連續(xù)的。基于樣圖的紋理合成技術(shù)不僅可以克服傳統(tǒng)紋理映射方法的缺點(diǎn)，而且避免了過程紋理合成調(diào)整參數(shù)的繁瑣，因而受到越來越多的研究人員的關(guān)注，成為計(jì)算機(jī)圖形學(xué)、計(jì)算機(jī)視覺和圖像處理領(lǐng)域的研究熱點(diǎn)之一。本文的算法就是基于Ashi-khmin提出的基于位置相對(duì)性的合成技術(shù)和Efros和Liang同時(shí)分別提出的基于MRF模型和塊拼接的紋理合成算法。

早期紋理合成技術(shù)有金字塔模型、多分辨率模型、MRF模型、層次法表示等，但效果均不太理想。在1999年的ICCV會(huì)議上，Efros基于MRF模型，提出了以鄰近點(diǎn)相關(guān)為基本準(zhǔn)則的非參數(shù)采樣合成算法，取得了很好的合成效果。緊接著，在2000年的SIGGRAPH會(huì)議上，Wei和Levoy提出了一種改進(jìn)的算法：鄰域改為L形狀，而非矩形。這種改進(jìn)大大減小了計(jì)算量，加快了合成速度。在2001年，Ashikhmin利用相關(guān)性原理，根據(jù)位置的相對(duì)關(guān)系，在待選點(diǎn)中尋找最佳匹配點(diǎn)，這種方法對(duì)絕大多數(shù)的自然紋理合成都能取得很好的效果，而且速度比文獻(xiàn)[11]還要快；同樣是2001年，Efros和Liang同時(shí)分別提出了基于MRF模型和塊拼接的紋理合成算法，在紋理的合成質(zhì)量和合成速度上比以前的算法都有顯著提升。這些使得紋理合成技術(shù)發(fā)展到了一個(gè)新的高度。

本文提出了一種新的紋理合成算法。算法思想與文獻(xiàn)[2-3]類似，但加入了文獻(xiàn)[1]的特點(diǎn)，在搜索匹配塊時(shí)采用了新的搜索規(guī)則，加速了匹配過程；同時(shí)在邊界重疊區(qū)的匹配誤差計(jì)算時(shí)采用了與視覺相關(guān)的權(quán)值，使合成結(jié)果更符合視覺要求。

1相關(guān)工作

在2001年，Ashikhmin提出了一種新的簡(jiǎn)單有效的搜索匹配方法，該方法對(duì)于合成自然紋理有著非常理想的效果。與Wei和Levoy的算法在整個(gè)樣本圖中搜索匹配點(diǎn)不同，Ashikhmin利用相關(guān)性原理，根據(jù)輸出圖像中當(dāng)前點(diǎn)的L鄰域中的點(diǎn)(如圖1輸出圖像所示)，找到與其匹配的輸入圖像中對(duì)應(yīng)點(diǎn)的位置(如圖1中的箭頭所指點(diǎn))，然后偏移相應(yīng)量后獲得待選點(diǎn)(如圖1輸入圖像中的黑塊)。以輸出圖像中當(dāng)前點(diǎn)P的右上角鄰點(diǎn)A為例，A是已合成的點(diǎn)，其在輸入圖像中的匹配位置為A′，由于輸出圖像中，當(dāng)前點(diǎn)P與A在x方向相差-1，在y方向相差1，即P＝A＋(－1，1)，對(duì)應(yīng)地，在樣本圖中，待選點(diǎn)A″由A′＋(－1，1)獲得。其它待選點(diǎn)的計(jì)算類似。圖1中輸入圖像中的黑點(diǎn)為當(dāng)前點(diǎn)P的所有待選點(diǎn)，比較各待選點(diǎn)與P點(diǎn)的L鄰域的誤差，選取誤差最小的點(diǎn)作為P點(diǎn)的匹配點(diǎn)。

在2001年的SIGGRAPH會(huì)議上，Efros提出一種基于塊拼接的紋理合成算法。比起以往的算法，該算法使用紋理塊作為紋理合成的單元，這是在文獻(xiàn)[10]基礎(chǔ)上的一個(gè)拓展。該算法在紋理合成的時(shí)間、合成紋理的視覺效果方面都得到了很大的提高，避免了以往的算法容易引起的模糊，紋元錯(cuò)位嚴(yán)重等問題。如圖2所示，該方法按掃描線順序從左至右、從上至下逐塊合成紋理(圖2演示了合成順序)，其中陰影塊為當(dāng)前待合成紋理塊，其他正方形塊為已合成紋理塊，紅色輪廓線區(qū)域不僅是當(dāng)前待合成紋理塊的邊界，而且也是與已合成部分的重疊區(qū)域。在合成過程中，所謂重疊區(qū)域匹配是指重疊區(qū)域的誤差小于某給定的閥值。重疊區(qū)域的誤差指它們重疊區(qū)域中對(duì)應(yīng)像素的RGB值誤差之和。這里RGB值誤差定義為它們間的L₂距離。例如，N₁，N₂若為重疊區(qū)域，則它們的誤差為：其中函數(shù)R(pixel),G(pixel),B(pixel)分別表示紋理圖像的紅、綠、藍(lán)三原色。

為了使重疊區(qū)域平滑過渡，文章還提出了裁剪線的概念。在匹配的重疊區(qū)域每一行中，找到偏差最小的像素點(diǎn)，由這些像素點(diǎn)就構(gòu)成了裁剪線。如圖3所示，把裁剪線作為B₂的邊緣，把B₂貼入合成圖中，反復(fù)重復(fù)以上過程，就獲得了合成紋理圖。此算法雖然簡(jiǎn)單，但合成效果很好。該算法存在的問題是有時(shí)紋理出現(xiàn)過多的重復(fù)，有些邊界不匹配。

2本文的算法

Ashikhmin巧妙地運(yùn)用了如下事實(shí)：對(duì)當(dāng)前待合成點(diǎn)的鄰域內(nèi)的已知點(diǎn)在樣本圖中的匹配點(diǎn)做相應(yīng)的平移變換可導(dǎo)出當(dāng)前待合成的點(diǎn)。這種性質(zhì)可稱之為“紋理的連貫性”。Efros和Liang提出的塊拼接合成算法中，沒有利用這個(gè)性質(zhì)。同時(shí)，由于L₂距離并不是衡量?jī)蓚€(gè)紋理塊之間視覺相似性的最好的手段，我們根據(jù)人的視覺系統(tǒng)對(duì)圖像中顏色變化尖銳的地方反應(yīng)敏感，對(duì)顏色變化平緩的地方反應(yīng)較為遲鈍的特點(diǎn)，對(duì)L(sub)2(/sub)距離給出了相應(yīng)的視覺權(quán)值，進(jìn)一步提高了合成效果。本文基于[1—2]提出了一種新的紋理合成算法，它有以下特點(diǎn)：

(1)根據(jù)當(dāng)前待合成紋理塊的L鄰域(將Wei中像素的L鄰域概念中的像素推廣成像素塊)內(nèi)的已合成紋理塊在樣本圖中的位置找到相應(yīng)的待選紋理塊(類似文獻(xiàn)[1]方法)，將待選塊先進(jìn)行匹配檢查，加速匹配搜索。

(2)采用部分的MRF模型。如果搜索過程中找到邊界誤差小于閥值的紋理塊，則馬上停止搜索，將其作為當(dāng)前待合成紋理塊；如果沒有發(fā)現(xiàn)誤差小于閥值的紋理塊，則采用MRF模型，得到當(dāng)前待合成紋理塊。

(3)在計(jì)算兩個(gè)紋理塊邊界重迭區(qū)的誤差時(shí)，引入與視覺相關(guān)的權(quán)值，使合成結(jié)果更符合視覺特性。

本文算法可簡(jiǎn)述如下：首先確定當(dāng)前要合成的紋理塊，確定其L鄰域，根據(jù)L鄰域中已合成紋理塊的位置搜索記錄匹配紋理塊位置的數(shù)組，找到匹配塊，偏移相應(yīng)位置后，得到當(dāng)前待選紋理塊。然后比較待選紋理塊的邊界匹配誤差，如果誤差小于給定閥值，則直接選擇它作為當(dāng)前待合成紋理塊；否則搜索整個(gè)樣本圖中的紋理塊，直到找到邊界誤差小于閥值的紋理塊，或者根據(jù)邊界誤差最小的紋理塊“估計(jì)”匹配紋理塊。同時(shí)在計(jì)算誤差的時(shí)候加入視覺相關(guān)的權(quán)值。

下面我們對(duì)算法作詳細(xì)介紹。

2.1搜索匹配紋理塊

搜索匹配紋理塊的過程吸收了算法[1]和[2]的特點(diǎn)，具體來說分為兩步：

(1)由當(dāng)前待合成紋理塊P確定其L鄰域N(p)中的紋理塊，得到在樣本圖中所對(duì)應(yīng)的待選紋理塊集合T(p)，在T(p)中搜索。

(2)在樣本圖中所有紋理塊集合T(all)中搜索。

先討論第一步搜索過程。為了提高合成速度，通常采用3×3的L鄰域(這里以一個(gè)紋理塊長度為一個(gè)單位)。此時(shí)鄰域紋理塊集合N(p)最多包含當(dāng)前待合成紋理塊P的正左邊、左上角、正上方、右上角四個(gè)相鄰紋理塊(即圖4左邊綠色輪廓線所包含的紋理塊)。查找匹配紋理塊位置數(shù)組，得到這四個(gè)鄰域紋理塊在樣本圖像中的匹配位置(如圖4右邊綠色填充的紋理塊)，偏移相應(yīng)量后即為當(dāng)前待選紋理塊。以輸出圖像中當(dāng)前待合成紋理塊P的左上角鄰域紋理塊A為例，A在樣本圖中的匹配紋理塊為A′，指定紋理塊大小為Wpatch×Wpatch，邊界重迭區(qū)寬度為Woverlap，A′左上角的坐標(biāo)為(x，Y)，則由A產(chǎn)生的待選紋理塊A′的左上角的坐標(biāo)為(X＋Wpatch－Woverlap，Y＋Wpatch－Woverlap)。其它待選紋理塊的計(jì)算類似。如圖4所示，輸入圖像中的粗邊方塊即為待選紋理塊。得到T(p)后，比較其中各待選紋理塊與當(dāng)前待合成紋理塊L鄰域的邊界誤差，如果存在誤差小于給定閾值得的待選紋理塊Tmatch，則選擇它作為當(dāng)前待合成的紋理塊。

如果沒有找到Tmatch，才進(jìn)行第二步搜索。此時(shí)計(jì)算樣本圖中所有紋理塊的邊界誤差，并記錄誤差值。如果存在邊界誤差值小于給定閾值的紋理塊Pmatch，則停止搜索，將Pmatch作為當(dāng)前待合成紋理塊；如果搜索完整個(gè)樣本圖，都沒有找到邊界誤差小于閾值的紋理塊，則選擇邊界誤差最小的紋理塊作為當(dāng)前待合成的紋理塊。經(jīng)過上述兩步搜索得到的紋理塊，我們可以按[2]中提到的圖像縫合方式或[3]中提到的顏色混合方式合成到結(jié)果圖中。

2.2與視覺相關(guān)的權(quán)值計(jì)算

已有算法在計(jì)算兩個(gè)邊界區(qū)的誤差時(shí)，用到了距離L₂，這種誤差度量方法將每個(gè)像素置于同等的地位對(duì)待，并不恰當(dāng)。從視覺的角度觀察圖像，每個(gè)像素對(duì)人眼睛和心理的刺激是不同的，人往往對(duì)圖像中顏色變化尖銳的地方反應(yīng)敏感，而對(duì)顏色變化平緩的地方反應(yīng)相對(duì)遲鈍。基于這一點(diǎn)，本文提出給樣本圖和邊界區(qū)中的像素設(shè)定權(quán)值，來搜索更符合視覺要求的匹配紋理塊。圖5中：(a)是一張圖像；(b)是像素權(quán)值的示意圖，其中像素顏色深的地方權(quán)值較大。

下面介紹權(quán)值的計(jì)算方法。對(duì)圖像中的某像素點(diǎn)P，我們給定以該點(diǎn)為中心的窗口M_w×N_w，對(duì)于窗口中的任一點(diǎn)Q，我們定義P和Q的RGB顏色誤差為：

這里N是窗口中除P點(diǎn)以外的像素個(gè)數(shù)，γ是用來控制像素點(diǎn)的權(quán)值受周圍像素影響程度的因子。在合成前，首先對(duì)樣本紋理中每一個(gè)像素計(jì)算其權(quán)值，把結(jié)果保存在權(quán)值數(shù)組中。在合成紋理塊時(shí)，對(duì)當(dāng)前合成邊界區(qū)的像素計(jì)算權(quán)值，再用如下方法計(jì)算邊界區(qū)誤差：

這里B_in指邊界重迭區(qū)在樣本圖中的部分，B_out指邊界重迭區(qū)在合成圖中的部分，B_in是B_in中的第i個(gè)像素，B_out是B_out中的第i個(gè)像素，W_inj指像素B_in的權(quán)值，W_outj指像素B_out的權(quán)值，N指邊界重迭區(qū)的像素總數(shù)。值得注意的是：加入了像素權(quán)值以后，如果兩個(gè)像素的顏色相同，但權(quán)值不同，那么這兩個(gè)像素之間也將產(chǎn)生相似性誤差。

3結(jié)果和分析

我們用PC機(jī)(PⅢ667/256M)對(duì)一些紋理進(jìn)行合成。圖6是本算法與[2]算法合成結(jié)果的對(duì)比。圖6中左邊一列為樣本圖，按從上至下其分辨率分別為108×108像素、108×108像素和138×138像素；中間一列是用本算法合成的結(jié)果圖，大小為164×164像素；右邊一列為用[2]算法合成的結(jié)果圖，大小為164×164像素。從圖6我們可以看到用本算法合成的結(jié)果比用[2]算法合成的結(jié)果視覺效果要好。同時(shí)本文算法的合成速度也得到了很大的提高。表1列出圖中各紋理合成的一些實(shí)驗(yàn)數(shù)據(jù)，可以看出，在合成所用紋理塊大小相同的情況下，本算法的合成時(shí)間比[2]算法要短20％到30％大小。

在實(shí)驗(yàn)中我們發(fā)現(xiàn)如下規(guī)律：

(1)紋理塊越大，合成時(shí)間越短，紋理塊越小，合成時(shí)間越長；但紋理塊的大小與樣本圖相關(guān)，通常情況下，紋理塊要比“紋元”略大。如果紋理塊過大，塊與塊之間的接縫較明顯；如果紋理塊過小，則有可能引起紋理特征變形。

(2)邊界區(qū)的寬度一般取紋理塊寬度的1/4到1/6較為合適。本文取紋理塊寬度的1/6。

(3)γ是用來控制像素點(diǎn)的權(quán)值大小的可調(diào)節(jié)變量，過大或過小都會(huì)降低合成質(zhì)量。本文所用的γ大小為0.05。

(4)對(duì)于確定當(dāng)前待合成紋理塊的誤差閾值，一般取為0，即要求紋理塊邊界完全吻合，但實(shí)驗(yàn)中發(fā)現(xiàn)取閾值為20以下對(duì)合成質(zhì)量影響不大。本文所用的閾值為10。

4結(jié)束語

本文提出了一種新的紋理合成算法。算法吸收了文獻(xiàn)[1—3]等多個(gè)算法的特點(diǎn)；利用“紋理塊的連貫性”，加快了紋理合成的速度；同時(shí)算法在進(jìn)行紋理塊邊界誤差的計(jì)算時(shí)對(duì)每個(gè)像素加入了與視覺相關(guān)的權(quán)值，得到了較好的合成結(jié)果。由此可以看出，每個(gè)像素的重要性確實(shí)是不一樣的。

紋理合成是當(dāng)前計(jì)算機(jī)圖形學(xué)和計(jì)算機(jī)視覺領(lǐng)域的研究熱點(diǎn)。其潛在的應(yīng)用包括高維紋理合成、紋理的壓縮和解壓縮、視頻的合成和編輯、幾何紋理的建模和合成、網(wǎng)格紋理直接合成、網(wǎng)絡(luò)數(shù)據(jù)的快速傳輸、計(jì)算機(jī)動(dòng)畫、影視特技和虛擬現(xiàn)實(shí)等方面。