图像纹理合成及纹理传输算法学习（附源码）。
? ? 有2到3年沒有逛CodeProject了，上班一時(shí)無(wú)聊，就翻翻這個(gè)比較有名的國(guó)外網(wǎng)站，在其Articles???Multimedia???General Graphics???Graphics一欄看到exture Transfer using Efros & Freeman's Image Quilting Algorithm頓感興趣，其效果很有特色，又激起了我好久沒寫代碼的心，想想在這個(gè)算法上大概前前后后思索了1個(gè)多星期，雖然最終還是沒有得到我想要的結(jié)果，但并不全無(wú)收獲，至此國(guó)慶佳節(jié)加班之際抽空總結(jié)一下，以便慰藉我孤獨(dú)的心靈。
? ? 紋理圖像的合成算法在早期的Photoshop中我記得是有一個(gè)單獨(dú)的功能的，在后來(lái)的版本中不知道為什么被取消了，印象中他能將只有幾顆小草的圖片生長(zhǎng)成很多小草，并且基本看不出什么瑕疵和不自然的地方，那么CodeProject上的這個(gè)Quilting算法也有類似的能力，首先貼幾張?zhí)幚淼慕Y(jié)果圖欣賞一下。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
??? ??
?
? ? ????
原始紋理圖像 ? ? ? ? 由小紋理合成的大紋理圖像
? ? 那么簡(jiǎn)單的描述下這篇文章所使用的算法的過(guò)程吧。
? ? 算法需要的輸入：原始的紋理圖像(W * H)，塊的大小TileSize，重疊部分的大小Overlap。
?第一步：我們從原始的紋理圖像中一個(gè)隨機(jī)的抽取一個(gè)小塊，放到目標(biāo)圖像的左上角。
? ? ? ? ? ?
? ? 無(wú)需解釋，其中黑色的部分表示目標(biāo)圖像尚未處理的部分。
? ??第二步：按照從左到右，從上到下，抽取出塊重疊的部分的數(shù)據(jù)，并計(jì)算這部分?jǐn)?shù)據(jù)和原始紋理圖像中各塊的相似度。
? ? ? ?? ? ?? ? ??
? ? ? ? ? ? ? ? 水平重疊 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 垂直重疊 ? ? ? ? ? ? ? ? ? ? ? ? 水平和垂直部分具有重疊
要達(dá)到合成自然，在有了第一個(gè)塊之后，其周邊的塊應(yīng)該從原圖中選擇和其最相似的部位， 因此 ，我們從已經(jīng)合成的塊中抽取部分重疊的數(shù)據(jù)，如上圖所示，紅色方框內(nèi)，沒有紅色網(wǎng)格線的部分即為重疊的內(nèi)容，在整個(gè)的處理過(guò)程中，會(huì)有三種情況出現(xiàn)，分別如上圖所示,即（1）只有垂直方向有部分重疊；（2）只有水平發(fā)方向有部分重疊；（3）水平和垂直方向都有重疊。
? ? 為了選擇合適的下一個(gè)塊，我們結(jié)算這些重疊的塊和原圖中的所有塊的相似度，塊和塊之間的相似度可以有很多準(zhǔn)則計(jì)算，最常用的莫過(guò)于SSD(Sum of Squared Distance)，這里我們也采用這種準(zhǔn)則。
對(duì)于第一種只有垂直方向有部分重疊的情況，塊的可能性有 （W - Overlap）* （H - TileSize）種，而只有水平發(fā)方向有部分重疊時(shí)，塊的可能性有（W - TileSize)* (H - Overlap)種，當(dāng)水平和垂直方向都有重疊時(shí)，只有（W - TileSize）* （H - TileSize）種塊的選擇方案。
? ? 對(duì)于水平和垂直有交叉的情況，需要分別計(jì)算水平重疊的相似性A，垂直重疊的相似性B以及交叉部位的相似性AB，最終的相似性由A + B - AB決定。
? ? 計(jì)算完相似性后，一般情況下，我們可取相似度最小的塊為下一個(gè)塊，當(dāng)然為了隨機(jī)性更強(qiáng)，也可以取相似性序列中前N個(gè)最小值種的某個(gè)塊為選中的塊。
? ??第三步：如果對(duì)選中的塊直接進(jìn)行拼貼到目標(biāo)圖中，則很明顯兩個(gè)塊之間由過(guò)渡不會(huì)太自然，一種較好的方式就是在選中的塊和重疊的部分找到一條路徑，在該路徑的兩側(cè)像素的距離和最小，如果使用暴力的方式去尋找這條路徑，則是非常耗時(shí)和不必要的，文章介紹使用了貪心算法來(lái)尋找這條路徑。
? ? 我們拿水平重疊的塊來(lái)說(shuō)明問(wèn)題，首先找到第一行最小距離和的像素的位置，假定為(x,1),接著我們搜索第二行的（x - 1, 2),?（x, 2),?（x + 1, 2)三個(gè)位置的距離和的最小值，假定是?（x - 1, 2)是第二行的最小值，則第三行需要搜索的位置為（x - 2, 3),?（x - 1, 3),?（x, 3)，依類類推直到最后一行。
? ? 其實(shí)路徑必然是連續(xù)的，因此這種只搜索向下的三領(lǐng)域的做法是完全合理的。
? ? 一般情況下，做圖像算法會(huì)按照從左到右，從上到下的順序進(jìn)行處理，這樣能夠充分利用cache line的優(yōu)勢(shì)，如果按照從上到下，然后在從左到右的方式來(lái)處理，雖然邏輯和結(jié)果是一樣的，通常會(huì)需要更多的時(shí)間，因此，在計(jì)算垂直的塊的路徑時(shí)，我們可以借用水平塊的算法，只要對(duì)垂直的塊的數(shù)據(jù)先進(jìn)行轉(zhuǎn)置，處理轉(zhuǎn)置的數(shù)據(jù)得到對(duì)應(yīng)的數(shù)據(jù)，然后在把這個(gè)數(shù)據(jù)轉(zhuǎn)置就得到了垂直塊的結(jié)果。注意這里是用的轉(zhuǎn)置，而不是旋轉(zhuǎn)，因?yàn)樾D(zhuǎn)對(duì)于該問(wèn)題是的到的結(jié)果是鏡像的，所以必須注意。
? ? 在水平和垂直部分具有重疊的塊的計(jì)算時(shí)，我們是分別計(jì)算垂直和水平的路徑，然后取兩個(gè)路徑的交集，計(jì)算過(guò)程分別如下圖。
??
? ??第四步：?按照路徑的位置貼入新的數(shù)據(jù)。
? ? 編程技巧：
? ? （1） 在整個(gè)的計(jì)算中，計(jì)算SSD是最為耗時(shí)的，因此對(duì)其優(yōu)化是調(diào)高程序效率的關(guān)鍵。
? 我們看一段matlab的代碼，如下所示：
%function Z = ssd(X, Y) %Computes the sum of squared distances between X and Y for each possible % overlap of Y on X. Y is thus smaller than X % %Inputs: % X - larger image % Y - smaller image % %Outputs: % Each pixel of Z contains the ssd for Y overlaid on X at that pixelfunction Z = ssd(X, Y)K = ones(size(Y,1), size(Y,2));for k=1:size(X,3),A = X(:,:,k);B = Y(:,:,k);a2 = filter2(K, A.^2, 'valid');b2 = sum(sum(B.^2));ab = filter2(B, A, 'valid').*2;if( k == 1 )Z = ((a2 - ab) + b2);elseZ = Z + ((a2 - ab) + b2);end; end;這里的優(yōu)化時(shí)通過(guò)卷積實(shí)現(xiàn)的，因?yàn)镾SD的計(jì)算就是(a-b)^2的累積和，展開為a^2 + b^2 - 2ab，其中a為固定的圖像，那么a^2則為一定值，b^2是不斷變化的，但是也可以用積分圖之類的算法實(shí)現(xiàn)快速效果，唯一的耗時(shí)時(shí)2ab項(xiàng)，可以用卷積來(lái)實(shí)現(xiàn)。
? ? ?快速的卷積算法可以通過(guò)FFT來(lái)實(shí)現(xiàn)，也可以借鑒我在圖像處理中任意核卷積(matlab中conv2函數(shù))的快速實(shí)現(xiàn)?一文中提到的用SSE的方式實(shí)現(xiàn)，鑒于這里的卷積更有其特殊性，他是2幅圖像之間的卷積，因此參與計(jì)算的都是byte類型，則可以通過(guò)選擇更為合適的SSE函數(shù)來(lái)進(jìn)一步提高效率，這里要感謝有關(guān)高手提供的一段SSE代碼。
/// <summary> /// 基于SSE的字節(jié)數(shù)據(jù)的乘法。 /// </summary> /// <param name="Kernel">需要卷積的核矩陣。</param> /// <param name="Conv">卷積矩陣。</param> /// <param name="Length">矩陣所有元素的長(zhǎng)度。</param> /// <remarks> 1: 使用了SSE優(yōu)化。 /// <remarks> 2: 感謝采石工（544617183）提供的SSE代碼<。</remarks> /// https://msdn.microsoft.com/zh-cn/library/t5h7783k(v=vs.90).aspxint MultiplySSE(unsigned char* Kernel, unsigned char * Conv, int Length) {int Y, Sum;__m128i vsum = _mm_set1_epi32(0);__m128i vk0 = _mm_set1_epi8(0);for (Y = 0; Y <= Length - 16; Y += 16){__m128i v0 = _mm_loadu_si128((__m128i*)(Kernel + Y)); // 對(duì)應(yīng)movdqu指令,不需要16字節(jié)對(duì)齊__m128i v0l = _mm_unpacklo_epi8(v0, vk0); __m128i v0h = _mm_unpackhi_epi8(v0, vk0); // 此兩句的作用是把他們分別加載到兩個(gè)128位寄存器中，供下面的_mm_madd_epi16的16位SSE函數(shù)調(diào)用（vk0的作用主要是把高8位置0） __m128i v1 = _mm_loadu_si128((__m128i*)(Conv + Y));__m128i v1l = _mm_unpacklo_epi8(v1, vk0);__m128i v1h = _mm_unpackhi_epi8(v1, vk0);vsum = _mm_add_epi32(vsum, _mm_madd_epi16(v0l, v1l)); // _mm_madd_epi16 可以一次性進(jìn)行8個(gè)16位數(shù)的乘法，然后把兩個(gè)16的結(jié)果在加起來(lái)，放到一個(gè)32數(shù)中， r0 := (a0 * b0) + (a1 * b1)，詳見 https://msdn.microsoft.com/zh-cn/library/yht36sa6(v=vs.90).aspxvsum = _mm_add_epi32(vsum, _mm_madd_epi16(v0h, v1h));}for (; Y <= Length - 8; Y += 8){__m128i v0 = _mm_loadl_epi64((__m128i*)(Kernel + Y));__m128i v0l = _mm_unpacklo_epi8(v0, vk0);__m128i v1 = _mm_loadl_epi64((__m128i*)(Conv + Y));__m128i v1l = _mm_unpacklo_epi8(v1, vk0);vsum = _mm_add_epi32(vsum, _mm_madd_epi16(v0l, v1l));}vsum = _mm_add_epi32(vsum, _mm_srli_si128(vsum, 8));vsum = _mm_add_epi32(vsum, _mm_srli_si128(vsum, 4));Sum = _mm_cvtsi128_si32(vsum); // MOVD函數(shù)，Moves the least significant 32 bits of a to a 32-bit integer： r := a0for ( ; Y < Length; Y++){Sum += Kernel[Y] * Conv[Y];}return Sum; }? ??? 以上代碼在大數(shù)據(jù)量時(shí)可以一次性完成16個(gè)字節(jié)數(shù)據(jù)的乘法及累加，大大的提高了效率。
? ? ? 以上計(jì)算SSD的方式也可以幫助提高標(biāo)準(zhǔn)的模板匹配算法的速度，這個(gè)我想有心的人應(yīng)該不難實(shí)現(xiàn)。
? ? ??但是即使采用了這種快速的計(jì)算，整個(gè)紋理合成的速度還是相當(dāng)?shù)穆?#xff0c;要使得該算法具有實(shí)際的實(shí)用價(jià)值，還的尋找快速的塊相似度平價(jià)方法。
? ? ? 由于程序速度問(wèn)題，我對(duì)紋理傳輸?shù)木帉懸呀?jīng)失去了信心，紋理傳輸過(guò)程總的和紋理合成和類似，只是在計(jì)算相似度時(shí)還要考慮目標(biāo)的諸如亮度或者模糊只方面的信息，速度會(huì)比這個(gè)紋理合成還要慢，有興趣的朋友可以看看我提供的一些鏈接，里面基本都有參考代碼。
不過(guò)紋理傳輸產(chǎn)生的效果有的時(shí)候確實(shí)比較酷：
? ? ??
? ??
? ? ? 那天心血來(lái)潮我還是去實(shí)現(xiàn)下這個(gè)效果吧。
? ? ? 紋理合成完整的工程下載：
? ? ??http://files.cnblogs.com/files/Imageshop/ImageQuilting.rar
?
?參考資料：
http://web.engr.illinois.edu/~vrgsslv2/cs498dwh/proj2/
http://www.codeproject.com/Articles/24172/Texture-Transfer-using-Efros-Freeman-s-Image-Quilt
http://mesh.brown.edu/dlanman/courses.html
?
?
****************************作者： laviewpbt ? 時(shí)間： 2015.10.1 ? ?聯(lián)系QQ: ?33184777 轉(zhuǎn)載請(qǐng)保留本行信息**********************
?
轉(zhuǎn)載于:https://www.cnblogs.com/Imageshop/p/4851969.html
總結(jié)
以上是生活随笔為你收集整理的图像纹理合成及纹理传输算法学习（附源码）。的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： table的分页打印
- 下一篇： Web APi之过滤器执行过程原理解析【