图像纹理合成及纹理传输算法学习（附源码）。
? ? 有2到3年沒有逛CodeProject了，上班一時無聊，就翻翻這個比較有名的國外網站，在其Articles???Multimedia???General Graphics???Graphics一欄看到exture Transfer using Efros & Freeman's Image Quilting Algorithm頓感興趣，其效果很有特色，又激起了我好久沒寫代碼的心，想想在這個算法上大概前前后后思索了1個多星期，雖然最終還是沒有得到我想要的結果，但并不全無收獲，至此國慶佳節加班之際抽空總結一下，以便慰藉我孤獨的心靈。
? ? 紋理圖像的合成算法在早期的Photoshop中我記得是有一個單獨的功能的，在后來的版本中不知道為什么被取消了，印象中他能將只有幾顆小草的圖片生長成很多小草，并且基本看不出什么瑕疵和不自然的地方，那么CodeProject上的這個Quilting算法也有類似的能力，首先貼幾張處理的結果圖欣賞一下。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
??? ??
?
? ? ????
原始紋理圖像 ? ? ? ? 由小紋理合成的大紋理圖像
? ? 那么簡單的描述下這篇文章所使用的算法的過程吧。
? ? 算法需要的輸入：原始的紋理圖像(W * H)，塊的大小TileSize，重疊部分的大小Overlap。
?第一步：我們從原始的紋理圖像中一個隨機的抽取一個小塊，放到目標圖像的左上角。
? ? ? ? ? ?
? ? 無需解釋，其中黑色的部分表示目標圖像尚未處理的部分。
? ??第二步：按照從左到右，從上到下，抽取出塊重疊的部分的數據，并計算這部分數據和原始紋理圖像中各塊的相似度。
? ? ? ?? ? ?? ? ??
? ? ? ? ? ? ? ? 水平重疊 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 垂直重疊 ? ? ? ? ? ? ? ? ? ? ? ? 水平和垂直部分具有重疊
要達到合成自然，在有了第一個塊之后，其周邊的塊應該從原圖中選擇和其最相似的部位， 因此 ，我們從已經合成的塊中抽取部分重疊的數據，如上圖所示，紅色方框內，沒有紅色網格線的部分即為重疊的內容，在整個的處理過程中，會有三種情況出現，分別如上圖所示,即（1）只有垂直方向有部分重疊；（2）只有水平發方向有部分重疊；（3）水平和垂直方向都有重疊。
? ? 為了選擇合適的下一個塊，我們結算這些重疊的塊和原圖中的所有塊的相似度，塊和塊之間的相似度可以有很多準則計算，最常用的莫過于SSD(Sum of Squared Distance)，這里我們也采用這種準則。
對于第一種只有垂直方向有部分重疊的情況，塊的可能性有 （W - Overlap）* （H - TileSize）種，而只有水平發方向有部分重疊時，塊的可能性有（W - TileSize)* (H - Overlap)種，當水平和垂直方向都有重疊時，只有（W - TileSize）* （H - TileSize）種塊的選擇方案。
? ? 對于水平和垂直有交叉的情況，需要分別計算水平重疊的相似性A，垂直重疊的相似性B以及交叉部位的相似性AB，最終的相似性由A + B - AB決定。
? ? 計算完相似性后，一般情況下，我們可取相似度最小的塊為下一個塊，當然為了隨機性更強，也可以取相似性序列中前N個最小值種的某個塊為選中的塊。
? ??第三步：如果對選中的塊直接進行拼貼到目標圖中，則很明顯兩個塊之間由過渡不會太自然，一種較好的方式就是在選中的塊和重疊的部分找到一條路徑，在該路徑的兩側像素的距離和最小，如果使用暴力的方式去尋找這條路徑，則是非常耗時和不必要的，文章介紹使用了貪心算法來尋找這條路徑。
? ? 我們拿水平重疊的塊來說明問題，首先找到第一行最小距離和的像素的位置，假定為(x,1),接著我們搜索第二行的（x - 1, 2),?（x, 2),?（x + 1, 2)三個位置的距離和的最小值，假定是?（x - 1, 2)是第二行的最小值，則第三行需要搜索的位置為（x - 2, 3),?（x - 1, 3),?（x, 3)，依類類推直到最后一行。
? ? 其實路徑必然是連續的，因此這種只搜索向下的三領域的做法是完全合理的。
? ? 一般情況下，做圖像算法會按照從左到右，從上到下的順序進行處理，這樣能夠充分利用cache line的優勢，如果按照從上到下，然后在從左到右的方式來處理，雖然邏輯和結果是一樣的，通常會需要更多的時間，因此，在計算垂直的塊的路徑時，我們可以借用水平塊的算法，只要對垂直的塊的數據先進行轉置，處理轉置的數據得到對應的數據，然后在把這個數據轉置就得到了垂直塊的結果。注意這里是用的轉置，而不是旋轉，因為旋轉對于該問題是的到的結果是鏡像的，所以必須注意。
? ? 在水平和垂直部分具有重疊的塊的計算時，我們是分別計算垂直和水平的路徑，然后取兩個路徑的交集，計算過程分別如下圖。
??
? ??第四步：?按照路徑的位置貼入新的數據。
? ? 編程技巧：
? ? （1） 在整個的計算中，計算SSD是最為耗時的，因此對其優化是調高程序效率的關鍵。
? 我們看一段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;這里的優化時通過卷積實現的，因為SSD的計算就是(a-b)^2的累積和，展開為a^2 + b^2 - 2ab，其中a為固定的圖像，那么a^2則為一定值，b^2是不斷變化的，但是也可以用積分圖之類的算法實現快速效果，唯一的耗時時2ab項，可以用卷積來實現。
? ? ?快速的卷積算法可以通過FFT來實現，也可以借鑒我在圖像處理中任意核卷積(matlab中conv2函數)的快速實現?一文中提到的用SSE的方式實現，鑒于這里的卷積更有其特殊性，他是2幅圖像之間的卷積，因此參與計算的都是byte類型，則可以通過選擇更為合適的SSE函數來進一步提高效率，這里要感謝有關高手提供的一段SSE代碼。
/// <summary> /// 基于SSE的字節數據的乘法。 /// </summary> /// <param name="Kernel">需要卷積的核矩陣。</param> /// <param name="Conv">卷積矩陣。</param> /// <param name="Length">矩陣所有元素的長度。</param> /// <remarks> 1: 使用了SSE優化。 /// <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)); // 對應movdqu指令,不需要16字節對齊__m128i v0l = _mm_unpacklo_epi8(v0, vk0); __m128i v0h = _mm_unpackhi_epi8(v0, vk0); // 此兩句的作用是把他們分別加載到兩個128位寄存器中，供下面的_mm_madd_epi16的16位SSE函數調用（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 可以一次性進行8個16位數的乘法，然后把兩個16的結果在加起來，放到一個32數中， 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函數，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; }? ??? 以上代碼在大數據量時可以一次性完成16個字節數據的乘法及累加，大大的提高了效率。
? ? ? 以上計算SSD的方式也可以幫助提高標準的模板匹配算法的速度，這個我想有心的人應該不難實現。
? ? ??但是即使采用了這種快速的計算，整個紋理合成的速度還是相當的慢，要使得該算法具有實際的實用價值，還的尋找快速的塊相似度平價方法。
? ? ? 由于程序速度問題，我對紋理傳輸的編寫已經失去了信心，紋理傳輸過程總的和紋理合成和類似，只是在計算相似度時還要考慮目標的諸如亮度或者模糊只方面的信息，速度會比這個紋理合成還要慢，有興趣的朋友可以看看我提供的一些鏈接，里面基本都有參考代碼。
不過紋理傳輸產生的效果有的時候確實比較酷：
? ? ??
? ??
? ? ? 那天心血來潮我還是去實現下這個效果吧。
? ? ? 紋理合成完整的工程下載：
? ? ??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 ? 時間： 2015.10.1 ? ?聯系QQ: ?33184777 轉載請保留本行信息**********************
?
轉載于:https://www.cnblogs.com/Imageshop/p/4851969.html
總結
以上是生活随笔為你收集整理的图像纹理合成及纹理传输算法学习（附源码）。的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： table的分页打印
- 下一篇： Web APi之过滤器执行过程原理解析【