基于直方圖匹配的藝術(shù)Mosaic圖像并行拼貼

宋 磊，朱曉強，葉翰辰，史 璇，朱夢堯，王向陽

(上海大學a.通信與信息工程學院；b.智慧城市研究院，上海200444)

對于由若干子圖拼貼生成的新圖，若從遠、近觀察可分別看出Mosaic效果圖像和內(nèi)容豐富的子圖像，則稱該類圖像為藝術(shù)Mosaic圖像。藝術(shù)Mosaic是最古老的裝飾藝術(shù)之一，教堂常用瓦礫、玻璃等拼貼藝術(shù)Mosaic[1]。目前藝術(shù)Mosaic拼貼技術(shù)已廣泛用于廣告宣傳、繪畫藝術(shù)、視頻影像等行業(yè)，如采用藝術(shù)Mosaic拼貼技術(shù)拼貼裝飾性瓦片藝術(shù)品[2]，基于統(tǒng)拼貼風格[3-6]或數(shù)字蒙太奇風格[7-10]拼貼照片集錦等。1996年Robert[11]第一次提出藝術(shù)Mosiac圖像智能拼貼，后有學者對其改進，如Finkelstein等[12]使用平移及縮放規(guī)則基于顏色均值法對拼貼圖像進行顏色校正，但算法中使用傳統(tǒng)半色調(diào)法，易產(chǎn)生人工周期紋理，且整體拼貼耗時較長；Zhang[13]用兩種不同顏色空間的顏色匹配方法對其Mosaic圖像拼貼效果進行了對比分析，認為可采用其他更佳方法挑選匹配的子圖像，而現(xiàn)多數(shù)學者采用顏色均值法完成原圖像與子圖像的匹配[14-15]；Fujisawa等[16]構(gòu)建基于GPU(graphic processing unit，圖形處理器)的藝術(shù)Mosaic拼貼交互系統(tǒng)，拼貼時長從數(shù)分鐘縮短至0.05 s，且實現(xiàn)了可交互的圖像遞歸式拼貼，但使用的顏色匹配法導(dǎo)致遠觀藝術(shù)Mosaic圖像具有明顯的顆粒感。

直方圖包含比顏色均值更豐富的顏色分布信息，其更適合用于藝術(shù)Mosaic拼貼的顏色校正，可實現(xiàn)圖像灰度的重新排列，使指定圖像色調(diào)擬合目標圖像，從而獲得子圖像在原圖中和諧融入的效果。鑒于此，筆者提出基于直方圖匹配的藝術(shù)Mosaic并行拼貼算法，采用直方圖匹配的方法選擇最佳圖像并進行顏色校正，使拼貼子圖像之間過渡自然，獲得高質(zhì)量的藝術(shù)Mosaic拼貼視覺效果。另借鑒文獻[16]，拼貼過程多處采用CUDA并行運算[17-18]，以期提高拼貼效率并實現(xiàn)交互式藝術(shù)Mosaic圖像遞歸拼貼。

1 藝術(shù)Mosaic圖像并行拼貼

提出的藝術(shù)Mosaic圖像并行拼貼算法流程如圖1。首先，對原圖像基于四叉樹結(jié)構(gòu)進行分割，并分別計算各分割圖像的RGB(red green blue，紅綠藍)直方圖，同時根據(jù)分割布局生成原圖像的分割索引表；其次，讀取子圖像庫中的所有圖像，且生成各自RGB直方圖；然后，在GPU上基于直方圖距離比較各分割圖像與子圖像的相似度，獲取與各分割圖像最相似的子圖；最后，基于直方圖匹配法對該子圖像進行顏色校正以擬合分割圖像，再根據(jù)分割索引表填充至原圖像相應(yīng)位置，生成藝術(shù)Mosaic拼貼圖像。該拼貼算法中，原圖像分割、直方圖比較、顏色校正及子圖像填充過程均使用CUDA并行計算。

1.1 分割索引表的并行生成

對圖像進行藝術(shù)Mosaic拼貼，需分析整體圖像分割布局并制作一張作為填充依據(jù)的分割索引表，以減少實時匹配計算量。首先，根據(jù)顏色分布對原圖像基于四叉樹多層分割，顏色變化緩慢區(qū)域用少量或單張子圖像填充，細節(jié)豐富區(qū)域需多層細分并填充多張匹配子圖像。拼貼細分過程中，根據(jù)用戶定義最小分割尺寸對原圖像統(tǒng)一分割，并將該分割結(jié)果作為第一層，即四叉樹的葉子結(jié)點。然后，計算第一層每塊圖像顏色值，并從第二層開始逐層根據(jù)前一層的田字格計算當前層對應(yīng)區(qū)域塊的顏色均值，將其作為該田字格是否需合并的依據(jù)，從而得到原圖像分割布局。如圖2所示，其中圖2(c)(d)分別為圖2(a)(b)框出區(qū)域的第一、二層，圖2(d)中每一塊等同于圖2(c)中4個相應(yīng)位置的田字塊。設(shè)第一層某田字格每塊的顏色值為ci(i=1,2,3,4)，第二層對應(yīng)格顏色值為C，判斷顏色距離di=|C-ci|(i=1,2,3,4)是否大于指定閾值T，若di均小于T，則該塊缺少顏色細節(jié)，將其合并為下一層的一整格，由此得到的分割結(jié)果如圖2(b)。

圖2 圖像分割Fig.2 Image segmentation

為便于后續(xù)子圖像填充，制作一張二維分割索引表作為填充依據(jù)。該表中每個值都用二進制表示，其中二進制值(1111)2表示不可合并原圖塊，0表示可合并，整張索引表可表示原圖像的分割情況。制作索引表步驟如下。

1)制作一張與第一層分割塊數(shù)相同的表，并初始化為0，表示該格待合并為下一層。

2)若顏色距離di(i=1,2,3,4)至少有一項大于閾值T，則將下一層對應(yīng)格設(shè)為(1111)2，表示該格顏色細節(jié)較豐富，需細分；若4項都小于閾值T，則設(shè)下一層對應(yīng)格的值為0，表示可合并，如圖3。

圖3 分割索引表Fig.3 Index table of segmentation

3)根據(jù)前一層索引表所得二進制值，再次合并田字格得到下一層索引表，如圖4。田字格中，左上角的格子位置由二進制值(0001)2表示，右上角由(0010)2表示，左下角由(0100)2表示，右下角由(1000)2表示。其中n表示第n層，n∈[1,N]，N為分割層數(shù)。下一層對應(yīng)格的值為上一層四格中值為0的二進制求和，如式(1)。

圖4 索引表合并Fig.4 Merging of index table

1.2 基于直方圖的子圖像并行匹配

通過計算直方圖距離檢索與分割圖像最相似的子圖像，較顏色均值法更能體現(xiàn)顏色分布，不易受極端顏色變化影響。

1.2.1 直方圖的計算

為方便比較直方圖，將子圖像尺寸預(yù)先歸一化為s×s（綜合考慮到效率和子圖像清晰度，文中選取子圖像尺寸為512×512）。然后分別計算分割圖像與各子圖像的RGB直方圖，并按序存入顯存中，便于CUDA運算。

1.2.2直方圖的比較

將每塊分割圖像與所有子圖像進行RGB直方圖對比，選取與分割塊最相似的子圖像，并將該子圖像的編號填充至索引表中，從而得到子圖像填充編號表，如圖5，該表的生成規(guī)則如下。

1)設(shè)原圖像總層數(shù)為N，當前層為n。當n≠N時，根據(jù)該層對應(yīng)的分割索引表，若某格值為(1111)2，表示需細分，則根據(jù)式(2)分別計算該格對應(yīng)四格直方圖與所有子圖像直方圖的距離h。h值越小則圖像越相似，選取最相似的圖像編號填入子圖像填充編號表相應(yīng)位置，如圖5。

其中：b為直方圖計算設(shè)定的圖像灰度區(qū)間數(shù)，較大的區(qū)間數(shù)表示灰度越細、匹配越好，但計算量也越大；分別表示分割圖像在R(red，紅)、G(green，綠)、B(blue，藍)顏色通道第i個灰度區(qū)間中的像素個數(shù)；則分別表示子圖像在R、G、B顏色通道第i個灰度區(qū)間中的像素個數(shù)。

2)若分割索引表中某格值為(1110)2，(1101)2等非零值，則該格對應(yīng)田字格中存在已填充子圖像，只需填充剩余未填充子圖像，計算子圖像填充編號方法同規(guī)則1)。

3)當n=N時，若該層索引表中某格值為0，則表示該位置需填充第N層分割大小的圖像，子圖像填充編號計算方法同規(guī)則1)。

圖5 子圖像填充編號表Fig.5 Table of sub-image filling numbers

1.3 子圖像的顏色校正與并行填充

直接填充匹配子圖像會產(chǎn)生子圖像間的明顯邊界，使原圖像輪廓和細節(jié)過于模糊，因此需校正子圖像顏色，使其色調(diào)盡可能擬合原圖像。文中采用直方圖匹配法進行顏色校正，將待填充子圖像直方圖調(diào)整至與目標圖像塊直方圖基本一致，此時兩幅圖像色調(diào)也基本一致。直方圖匹配的主要步驟如下：

1)計算子圖像的累積直方圖H；

2)計算分割圖像的累積直方圖M；

3)求H中每一個值在M中距離最小的位置j；

4)將子圖像直方圖通過索引j映射到相應(yīng)分割后原圖像的直方圖。

相較于統(tǒng)計直方圖，累積直方圖不易受顏色變化與分布的影響，能更好地反映兩幅圖像之間的顏色差別。最后將經(jīng)顏色校正的子圖像填充到其相應(yīng)位置。由于子圖像均已調(diào)整為統(tǒng)一大小，填充時可根據(jù)目標填充大小均勻選取子圖像像素填入。若子圖像填充編號表中某格不為0，則選取子圖像填入；反之則等待下一層填充，如圖6。所有子圖像填充完畢后，即為一幅完整的藝術(shù)Mosaic圖像。

圖6 子圖像填充過程Fig.6 Process of sub-image filling

2 實驗分析與應(yīng)用擴展

通過實驗對比分析基于直方圖匹配法與顏色均值法的藝術(shù)Mosaic圖像拼貼結(jié)果，并將單幅圖像的單次藝術(shù)Mosaic拼貼擴展至遞歸式拼貼進行實驗。實驗中采用GeForce GTX 750 Ti顯卡，RGB直方圖的灰度區(qū)間數(shù)b設(shè)為10，子圖像集數(shù)量為150張。

2.1 藝術(shù)Mosaic圖像拼貼

圖7，8分別為基于直方圖匹配法與顏色均值法[12，17]的實驗結(jié)果。其中原圖像尺寸均為450×450，最小分割尺寸為9，拼貼層數(shù)設(shè)為2。

圖7 基于直方圖匹配的藝術(shù)Mosaic拼貼Fig.7 Artistic Mosaic collage based on histogram matching

圖8 基于顏色均值法的藝術(shù)Mosaic拼貼Fig.8 Artistic Mosaic collage based on mean color method

比較圖7，8可知：未進行顏色校正情況下，采用顏色均值法進行圖像匹配的效果略優(yōu)于直方圖法，直方圖法實驗中為盡量減少計算時間，僅將直方圖分為10個灰度區(qū)間，同一區(qū)間灰度值跨越度較大，因此直方圖法的視覺差異較明顯；顏色校正之后，基于直方圖匹配的方法明顯優(yōu)于基于顏色均值的顏色校正，使用直方圖匹配進行顏色校正更好地貼近原圖像視覺效果，邊界平滑過渡；顏色均值法的結(jié)果中，雖大部分顏色與原圖像顏色接近，但普遍存在顏色突變現(xiàn)象，且子圖像邊界較明顯，存在顆粒感，這主要源于直方圖能體現(xiàn)顏色分布情況，可根據(jù)顏色分布對圖像進行顏色調(diào)度；而顏色均值法對于顏色分布極端的情況不能很好地體現(xiàn)圖像給人的印象色，顏色校正時也只能對所有像素整體加減灰度值，因此處于RGB通道極端灰度級區(qū)間的顏色易受顏色均值影響，視覺差異較大。此外，比較圖7(b)(c)可見，通過離散化避免相同子圖像相鄰，有效減少了大面積區(qū)域塊。

圖9為未進行顏色校正時，用戶設(shè)定不同分割層數(shù)的藝術(shù)Mosaic拼貼。原圖像大小為512×512，最小分割尺寸為8。由圖9可看出：分割層數(shù)設(shè)為多層時，對于顏色值相近區(qū)域，單張子圖像即可良好表達該區(qū)域信息，細節(jié)部分則通過細分填充多張子圖像展現(xiàn)。

圖9 多層藝術(shù)Mosaic拼貼Fig.9 Artistic Mosaic collage with multiple layers

通過用戶評測進一步驗證本文算法的有效性。對50張原圖像分別采用基于直方圖和顏色均值的方法生成兩組藝術(shù)Mosaic拼貼圖片，同時加入原圖像比較兩種方法的拼貼效果。30名用戶根據(jù)視覺效果選擇心儀的拼貼效果圖像。結(jié)果顯示，平均每位用戶選擇基于直方圖法的拼貼圖像占總圖像的比例是40.3/50=80.6%，由此可見用戶更傾向于本文算法得到的結(jié)果。

選用20張相同尺寸原圖像，統(tǒng)計基于CUDA的不同情況下算法的平均運行時間，結(jié)果見表1，2。表1為基于顏色均值且未顏色校正算法（簡稱A算法）的運行效率，表2為分割2層時不同算法的運行效率。其中：B表示基于顏色均值且使用顏色校正的算法；C表示基于直方圖且未顏色校正的算法；D表示基于直方圖且使用顏色校正的算法。由表1可見，A算法運行效率與原圖像尺寸、子圖像數(shù)量及用戶所設(shè)層數(shù)密切相關(guān)。由表2可見：采用顏色校正比未顏色校正算法分別慢0.06，2 s；基于顏色均值比基于直方圖算法快5～10 s，主要原因在于基于直方圖算法中計算直方圖較為耗時。藝術(shù)Mosaic拼貼過程具有較高的并行度，因此使用CUDA可加速本文算法，有效縮減處理時長。

表1 基于CUDA的A算法運行效率Tab.1 Efficiency of Algorithm Abased on CUDA

表2 二層拼貼各算法運行效率Tab.2 Efficiency of 2-layercollage with different algorithms

基于顏色均值算法的拼貼效率高于基于直方圖算法，但對于子圖像收集時的效率，其比基于直方圖算法低很多。實驗過程中，基于顏色均值算法收集子圖像每次均耗時15 s左右，而基于直方圖算法僅需2 s左右。因為基于顏色均值算法需在子圖像收集時計算每張子圖像每個通道的最大最小灰度值，用于后續(xù)顏色校正。因此，針對單張藝術(shù)Mosaic圖像無需顏色校正的拼貼過程，基于顏色均值法較快；有顏色校正需求時，基于直方圖法效率更高。

2.2 藝術(shù)Mosaic圖像的遞歸式拼貼

借鑒文獻[16]，對基于直方圖的藝術(shù)Mosaic圖像進行遞歸拼貼，即藝術(shù)Mosaic圖像中子圖像的放大與二次拼貼。此時子圖像庫不變，因此當原圖像變化時，可直接使用顯存中子圖像及其直方圖矩陣，節(jié)省大量計算時間。

圖10(a)為已拼貼藝術(shù)Mosaic圖像，當鼠標選中其中某一子圖像后，該子圖像平移至距離最近的窗口一角，如圖10(b)，開始放大，如圖10(c)。盡管圖像放大會變模糊，但放大到預(yù)設(shè)閾值時，可將更清晰圖像的像素并行填充至顯示區(qū)域，此時圖像會恢復(fù)至其未顏色校正狀態(tài)，如圖10(c)(d)。再次放大直到充滿整個窗口，如圖10(e)，對圖像重新進行拼貼得到圖10(f)，該過程可無限次執(zhí)行。本文藝術(shù)Mosaic圖像拼貼充分利用了顯存中緩存的子圖像庫，提供交互式藝術(shù)Mosaic圖像生成，滿足用戶以子圖庫任一張圖作為原圖遞歸生成新的藝術(shù)Mosaic圖像。

圖10 子圖像放大再拼貼Fig.10 Enlargement and re-collage of sub-images

3 結(jié) 論

提出一種基于直方圖匹配的藝術(shù)Mosaic圖像拼貼算法，根據(jù)預(yù)設(shè)的分割層數(shù)及最小分割尺寸，基于四叉樹對原圖像進行分割。通過計算直方圖距離檢索與分割圖像最相似的子圖像，并采用直方圖匹配法對子圖像進行顏色校正和拼貼。相比于傳統(tǒng)顏色均值法，基于直方圖的子圖像匹配和顏色校正生成的拼貼結(jié)果與原圖像視覺上更相似，且平滑了子圖像相接邊緣，顏色細節(jié)更清晰，整體更和諧。使用CUDA對本文算法并行加速，可有效縮減拼貼處理時間，實現(xiàn)了遞歸式藝術(shù)Mosaic圖像拼貼。

本文方法仍存在待改進之處，整體算法效率有待提高，雖可用于圖像的交互式拼貼，但對于藝術(shù)Mosaic視頻拼貼的實時性要求，依然存在較大差距。可從如下幾個方面展開本文相關(guān)的下一步工作：增加拼貼子圖像多樣性，如方向角的改變、提取子圖像顯著性區(qū)域后拼貼[21]等；在圖像分割與子圖像匹配過程加入紋理、形狀信息等。