譚云蘭，譚 彬

基于互信息圖割的風景圖片美學測度

譚云蘭1,2，*譚 彬1,2

（1. 井岡山大學電子與信息工程學院，江西 吉安 343009；2．同濟大學電子與信息工程學院，上海 201804)

提出了一種基于最大互信息圖割的攝影照片可計算美學測度算法。該方法按照信息理論元素將彩色圖像R/G/B三通道信源空間進行壓縮，根據(jù)圖像鄰近位置顏色分布相似的原理，進行區(qū)域Bins合并。然后采用逐像素掃描方式，用貪心法以最大信息熵為優(yōu)化目標，找出區(qū)域的分割位置。接著采用二叉分割樹進行存儲優(yōu)化分割節(jié)點，用大頂堆獲取當互信息值最大的節(jié)點，對區(qū)域反復進行垂直或水平分割，以給定的分割區(qū)域塊數(shù)為終止條件。最后累加分割過程中互信息值最大的節(jié)點之和作為照片最終的美學測度值。分割過程中，對算法進行加速，將R/G/B三通道的各像素直方圖由16777216個Bins壓縮成64個Bins。實驗結(jié)果表明，這種算法測量的美學值與Ground truth一致，能有效地表現(xiàn)原圖像的豐富細節(jié)，是一種將信息理論元素在圖像微觀美學測度的一種嘗試。

最大互信息；可計算美學；圖像分割；二叉分割樹；大頂堆

0 引言

為了使計算機能模擬人類自主地理解、推導和計算“美”的可計算方法，并在相關(guān)應(yīng)用中做出可行性的美學決策，近年來國外興起了圖像可計算美學( computational aesthetics)的研究。Birkhoff[1]最早提出了圖像的美學測度是圖像的秩序(Order)和復雜度(Complexity)之比的粗糙估計原型，即Measure= Order/ Complexity，但并沒有給出具體的數(shù)學計算模型。Machado等人[2]通過心理學TDA實驗驗證了他所提出了美學公式Measure=IC/PC，認為圖像的美學度量與圖像本身的復雜性( IC)成正比，與人腦處理圖像信息的復雜度( PC)成反比。Rigau等人[3]利用信息論的觀點和思路拓展了Birkhoff的美學信息度量，給出了結(jié)合信息論和Kolmogorov復雜度[4]的美學量化方法，包括利用色彩分布信息計算圖像的香農(nóng)熵來定義的美學測度。目前大部分與圖像復雜度相關(guān)的美學研究，主要集中在美學測度的直接推導，試圖研究利用公式直接對整幅圖像計算圖像美學測度。Romero[5]統(tǒng)一圖像維度和格式，在統(tǒng)一HSV顏色空間V(亮度)通道上抽取圖像邊緣特征，使用圖像JPEG和分形壓縮方法估計了圖像的復雜度，取得較好的美學測度和分類排序結(jié)果，由于計算復雜，并沒有在圖像的H(色相)，S(飽和度)通道中開展美學測度研究。Marchesotti[6]抽取圖像梯度和彩色特征對攝影照片進行美學評估，注重攝影照片的彩色逼真度、色飽和度、彩色平衡、彩色反差等特征抽取，開發(fā)了一個通用的基于內(nèi)容的美學預(yù)測描述器，為攝影照片的美學評估提供有益的思路。

互信息量的概念源于信息論，它是兩個隨機變量統(tǒng)計相關(guān)性的一種測度。將互信息應(yīng)用用于圖像分割方面，國內(nèi)外的學者開展了一些研究。Rigau等人[7]將輸入圖像X與輸出圖像Y的分割處理過程看成是一個Markov鏈過程，以每次分割損失最小MI(Mutual Information)也就是獲得最大MI為目標，自頂向下，自左向右逐步處理在亮度通道將圖像空間合并成同質(zhì)區(qū)域，設(shè)計了一種基于圖像亮度通道直方圖的圖像區(qū)域分割方法。呂慶文等人[8]采用基于模擬退火算法和互信息量方法，以互信息熵差作為一種新的分類類數(shù)判據(jù)為基礎(chǔ)，構(gòu)造了一種新的最大互信息量閾值分割算法。盧振泰等[9]提出了一種新的基于K均值算法與互信息技術(shù)相結(jié)合的醫(yī)學圖像分割算法，創(chuàng)新性嘗試將圖像配準方法用于灰度圖像分割領(lǐng)域。這三種方法是將灰度圖像中在同一范圍內(nèi)的像素灰度值歸屬于同一類，用一個或幾個灰度閾值將圖像分割成若干個類，從而實現(xiàn)分割效果，這些研究也僅僅是闡述了在灰度圖像上的分割，沒有針對彩色圖像進行分割。

目前國內(nèi)中文文獻除了文獻[10]綜述了可計算美學的研究進展，還未見相關(guān)論文闡述該領(lǐng)域的研究成果。本文提出了一種基于互信息圖割的風景照可計算美學測度算法，利用色彩信息分布合并來計算圖像分區(qū)的互信息，從而加快了分割速度。分割過程中利用公式計算每個待分割區(qū)域的互信息，采用貪心法選出當前分割狀態(tài)下的最大互信息區(qū)域，利用大頂堆找出當前分割過程中互信息值最大區(qū)域的分割位置，最后將二叉分割樹中的內(nèi)部節(jié)點的互信息值進行相加，從而獲得圖像的美學測度。

1 基于互信息圖割問題描述

1.1 信息理論

1.2 圖像分割問題描述

其中C為第K個分割區(qū)域類別，X為分割方式，C為第K個區(qū)域第i個類別，X為水平或垂直分割。

2 分割算法

以上述信道作為出發(fā)點，根據(jù)圖像鄰近位置顏色分布相似的原理，進行區(qū)域Bins像素聚類合并。以最大互信息為優(yōu)化目標，使用貪心算法獲取最佳分割位置，以給定的分割區(qū)域塊數(shù)為終止條件進行反復分割。

2.1 統(tǒng)計Bins

對于彩色圖像進行分割，其本質(zhì)就是按照信息理論元素將信源空間進行壓縮，將某些位置鄰近、大小相近的像素值進行合并，合并后的像素值概率等于合并前各像素值相應(yīng)概率之和。由于彩色圖像R/G/B三通道各像素取值為0-255共256個Bins等級，如果逐個像素的進行三個通道等級統(tǒng)計，則需要統(tǒng)計的等級為256^3= 16777216。為了加快計算速度，得到較佳的合并效果，本算法將0-255區(qū)間壓縮為4個Bins等級，即取值1,2,3,4。壓縮之后三通道的像素取值等級為4^3=64，壓縮方法如圖1(a)所示，圖1(b)是ID.3041056的三通道各bins柱狀統(tǒng)計圖。

(a) Bins區(qū)間壓縮圖 (b) 壓縮后ID.3041056的三通道各bins統(tǒng)計圖

(a)Compression of bins for R/G/B channels (b) Bins numbers for R/G/B channels after being compressed over ID.3041056

Fig.1 Bins compression and the corresponding numbers for R/G/B channels

2.2 區(qū)域分割信息熵的計算

2.3 貪心法分割與二叉分割樹構(gòu)建

整個分割過程中，最重要的就是找出某區(qū)域的分割位置。采用逐像素掃描方式，對某分割區(qū)域采用水平或垂直方向，計算當前掃描位置左右或上下兩部分的信息熵，采用貪心方法找出最大信息熵時位置，作為該區(qū)域的分割位置。此外，選出互信息值最大的待分割節(jié)點也很重要。由于已分割和未分割的節(jié)點都存儲在二叉分割樹中，若在二叉分割樹中查找值最大的未分割節(jié)點則比較耗時，而用堆(heap)卻可以高效地解決。因此，在每次分割后，將互信息值最大的節(jié)點插入大頂堆中，而大頂堆總是存放關(guān)鍵字值最大的未分割節(jié)點。在下一次分割時，只取當前堆頂?shù)脑刈鳛榉指罟?jié)點，因此用大頂堆非常容易獲取當前分割位置，從而節(jié)省了運行時間。

分割開始時，構(gòu)建空的二叉分割樹和堆。分割過程中，首先將根節(jié)點Root插入到二叉樹和堆中，接下來對根節(jié)點進行分割，將分割后的2個節(jié)點存貯到二叉分割樹中，將互信息最大的節(jié)點存儲到大頂堆中。下一次分割時從大頂堆中取出當前節(jié)點進行分割，分割之后存儲到二叉分割樹中，同時將互信息最大的節(jié)點存儲到大頂堆中。反復執(zhí)行這個過程，直到滿足指定的分割區(qū)域數(shù)為止。圖2(a)是ID.3041056分割區(qū)域為10的空間二叉分割樹，圖像的分辨率為369*277。分割過程是先對根節(jié)點進行第一次分割，根節(jié)點Root的分割位置SeperationPosition=105，分割方式SeperationMode=’Horizontal’；接下來從分割后得到的2個節(jié)點0.1265和0.1130中選擇值最大的進行分割；以后每次都從當前未分割節(jié)點中選擇值最大的節(jié)點進行分割，經(jīng)過9次分割之后(分割順序標識為①-⑨)，分割出10個區(qū)域，每個葉子節(jié)點代表一個分割區(qū)域。圖2(b)是按照圖2(a)分割過程得到對應(yīng)的分割位置及互信息值分布效果圖。圖3是分割塊數(shù)為100,300,600的分割效果圖，設(shè)置的分割塊數(shù)越多，越能擬合原圖A細節(jié)，從信息論角度來說，這是一種微觀美學度描述。

圖2 (a) 分割區(qū)域為10 的空間二叉分割樹 (b) 分割區(qū)域為10的分割位置及互信息

圖3 A為ID.3041056的原圖，B、C、D分別為分割終止條件為100塊區(qū)域，300塊區(qū)域和600塊區(qū)域的分割效果圖。

2.4 互信息圖割美學測度算法描述

算法1. 互信息圖割美學測度算法

輸入：待分割的原圖像分割的終止條件——分割區(qū)域塊數(shù)

輸出：分割效果圖，分割圖的美學測度值

算法描述：

Step 1 首先統(tǒng)計待分割的圖像的壓縮成柱狀bins。對每個像素，計算其Slot_red, Slot_green, Slot_blue值，根據(jù)公式bins(i,j,l,m,n)=bins(i-1,j,l,m,n)+(bins(i,j-1,l,m,n)-bins(i-1,j-1,l,m,n))+1，計算，其中l(wèi),m,n=1,2,3,4；

Step 2 構(gòu)建大頂堆(MaxHeap)和二叉分割樹(BinarySeperationTree)。將壓縮成柱狀bins作為第一個節(jié)點，放置在MaxHeap堆頂以及BinarySeperationTree根節(jié)點；

Step 6 最后一次分割后，所累加的InformationGain值定義為該圖像的美學測度值，同時顯示分割效果圖。

2.5 時間復雜度分析

根據(jù)算法中的各個步驟，算法總的時間復雜度為O(HLength*VLength*Bins^3)+ O(nlogn)+ (n-1)*O(HLength*VLength*Bins^3)，總的空間復雜度為3*n-1+ Bins^3，其中Bins為單通道顏色分段數(shù)，n為預(yù)設(shè)的分割區(qū)域塊數(shù)。Bins統(tǒng)計階段的時間復雜度為O(HLength*VLength *Bins^3)，所需的存儲空間為Bins^3；n個區(qū)域分割時構(gòu)建二叉樹分割樹的時間復雜度為(n-1)*O(HLength*VLength*Bins^3)，所需存儲空間為2*n-1；堆操作階段的時間復雜度為O(nlogn)，所需存儲空間為n。

3 實驗結(jié)果與分析

本實驗數(shù)據(jù)集采用美國公共攝影照片集網(wǎng)站http://www.photo.net/和dpchallenge網(wǎng)站http://www.dpchallenge.com/中的照片。采用Ritendra Datta[14-15]的Avg. Aesthetics為照片集網(wǎng)站http://www.photo.net/中照片的參考Groundtruth。為了獲得更真實有效的美學評估值作為對應(yīng)ID編號照片的參考Groundtruth，在dpchallenge網(wǎng)站上大量在線照片中，設(shè)置下載過濾條件Votes>120。本實驗遴選200張照片，由于版面有限，選取其中4副照片的分割效果圖，如圖4~圖7所示。實驗硬件環(huán)境為內(nèi)存2M+Duo CPU 2.8GHz的PC機，軟件環(huán)境為Matlab2011a+C+ Windows7。

3.1 分割效果圖

為了體現(xiàn)分割算法的魯棒性，遴選不同分辨率且All Votes >120的照片進行算法實驗。圖4~圖7中的A為原始照片，B為分割區(qū)域終止條件為600塊的分割效果圖，C為Felzenszwalb[16]的算法分割效果圖。

圖4 ID.892180的原圖及分割效果圖

圖5 ID.505281的原圖及分割效果圖

圖6 ID.772103的原圖及分割效果圖

圖7 ID.1218468的原圖及分割效果圖

3.2 實驗結(jié)果分析

圖像分割視為圖像的一種退化，本實驗以給定的分割區(qū)塊數(shù)為終止條件，在分割過程中以最大互信息量為優(yōu)化目標，所以可認為所獲得的分割是含有最多原圖像信息的分割。圖4~圖7的B都能將照片中的顯著性組成部分分割出來。分割過程撲捉了圖像的空間要素，分割效果反應(yīng)了整張照片的各個景觀要素。圖4~圖7的C是Felzenszwalb P F所提出的分割算法效果圖，從視覺效果上看，在反應(yīng)原圖的色彩逼真度方面還需要做較多改進，此外在反應(yīng)原圖的細節(jié)方面，圖4(c)主體對象完整的分割出來。

圖4~圖6的參考Groundtruth是根據(jù)網(wǎng)站注冊用戶投票各評分等級的加權(quán)平均。圖4投票數(shù)為122，圖5投票數(shù)為167, 圖6照片的投票人數(shù)達到504。本文算法的美學測度取值范圍為[0-3]，而圖4~圖6的美學測度取值范圍為[1-10]，圖7的美學測度取值范圍為[1-7]。從圖像分割效果來看，所求出的區(qū)域和原圖像中顯著性區(qū)域相吻合，這種算法能有效地表現(xiàn)原圖像的豐富細節(jié)和彩色逼真度。從表1中可以看出，盡管測量尺度不一致，但每幅圖所評估的美學測度值大小與Groundtruth一致。分割后圖像的信息熵值越大，說明從原圖中得到的信息量越大，所獲得的最優(yōu)分割結(jié)果包含有原圖像的信息量最多，越能體現(xiàn)攝影照片圖像的微觀美學測度。

表1 美學評估值

4 結(jié)束語

由于圖像美學度量的主觀性和復雜性，且可計算美學測度圖像的研究還處于初步探索和萌芽階段，有大量的問題有待研究，目前為止并沒有成熟的方法。本文按照信息理論元素將彩色圖像R/G/B三通道信源空間進行壓縮，采用圖像色彩空間自相似原理，將攝影照片分割成均勻像素區(qū)塊，采用貪心法以最大互信息量為優(yōu)化目標，多個實驗圖片結(jié)果表明，所獲得的最優(yōu)分割結(jié)果包含有原圖像的信息量最多，擬合了原圖像的豐富細節(jié)，是一種獲得含有原圖像最多信息的分割,是利用最大互信息在攝影照片可計算微觀美學測度領(lǐng)域的一種嘗試。今后將進一步研究其它度量攝影照片美學值的方法，但本文算法所計算的值將作為照片的可計算美學度量值之一。

[1] Birkhoff G D. Aesthetic measure[M]. Cambridge, Mass., 1933．

[2] Machado P, Cardoso A. Computing aesthetics[M]. Advances in Artificial Intelligence. Springer Berlin Heidelberg, 1998: 219-228.

[3] Rigau J, Feixas M, Sbert M. Informational aesthetics measures[J]. Computer Graphics and Applications, IEEE, 2008, 28(2): 24-34.

[4] Rigau J,Feixas M,Sbert M. Conceptualizing birkhoff's aesthetic measure using shannon entropy and kolmogorov complexity[C].Proceedings of the Third Eurographics conference on Computational Aesthetics in Graphics, Visualization and Imaging. Eurographics Association, 2007: 105-112.

[5] Romero J, Machado P, Carballal A, et al. Aesthetic classification and sorting based on image compression[M]. Applications of Evolutionary Computation. Springer Berlin Heidelberg, 2011: 394-403.

[6] Marchesotti L,Perronnin F,Larlus D,et al. Assessing the aesthetic quality of photographs using generic image descriptors[C]. Computer Vision (ICCV), 2011 IEEE International Conference on. IEEE, 2011: 1784-1791.

[7] Rigau J, Feixas M, Sbert S. An information theoretic framework for image segmentation[C]. Image Processing, 2004. ICIP'04. 2004 International Conference on. IEEE, 2004, 2: 1193-1196.

[8] 呂慶文,陳武凡. 基于互信息量的圖像分割[J].計算機學報,2006,29(2):296-301.

[9] 盧振泰,呂慶文,陳武凡. 基于最大互信息量的圖像自動優(yōu)化分割[J].中國圖象圖形學報,2008,13(4):658-661.

[10] 王偉凝,蟻靜緘,賀前華. 可計算圖像美學研究進展[J].中國圖象圖形學報,2012,17(8):893-901.

[11] Cover T M, Thomas J A. Elements of information theory[M]. John Wiley & Sons, 1991.

[12] Shannon C E. A mathematical theory of communication[J]. ACM SIGMOBILE Mobile Computing and Communications Review, 2001, 5(1): 3-55.

[13] Sethi I K, Sarvarayudu G P R. Hierarchical classifier design using mutual information[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 1982 (4): 441-445.

[14] Datta R, Joshi D, Li J, et al. Studying aesthetics in photographic images using a computational approach[M]. Computer Vision–ECCV 2006. Springer Berlin Heidelberg, 2006: 288-301.

[15] Datta R, Wang J Z. ACQUINE: aesthetic quality inference engine-real-time automatic rating of photo aesthetics[C]//Proceedings of the international conference on Multimedia information retrieval. ACM, 2010: 421-424.

[16] Felzenszwalb P F, Huttenlocher D P. Efficient graph-based image segmentation[J]. International Journal of Computer Vision, 2004, 59(2): 167-181.

COMPUTATIONAL AESTHETICS MEASURE FOR LANDSCAPE IMAGES BASED ON IMAGE SEGMENTATION OF MUTUAL INFORMATION

TAN Yun-lan1,2，*TAN Bin1,2

(1. College of Electronic Information and Engineering,Tongji University,Shanghai 201804,China;2. School of Electronic Information and Engineering,Jinggangshan University,Ji’an,Jiangxi 343009,China)

An algorithm for computational aesthetics measure of photographs based on image segmentation of mutual information is proposed. Using the information theory elements, information source space (ISS) of the color image R/G/B channels is compressed. Regional bins are combined according to the principle of the image colors spatial self-similarity distribution to the neighboring location. During the partitioning, the maximum mutual information of all the nonterminal nodes stored into the binary partitioning tree is calculated, which is added as the aesthetics measure value for photographs. Also, the algorithm is accelerated. Each pixel R/G/B three-channel histogram of 16,777,216 Bins is compressed into 64 Bins and the operation of getting the split position of the current node with max-heap is executed. Experimental results show that the values ??of aesthetic quantified by the algorithm are consistent with the Ground-truth and the segment result can effectively represent the rich detail from the original image.

the maximization of the mutual information; computational aesthetics measure; image segmentation; binary space partition tree; maxheap

TN911.73

A

10.3969/j.issn.1674-8085.2014.06.012

1674-8085(2014)06-0054-07

2014-08-12；

2014-10-27

十二五國家科技支撐計劃項目子課題(2012BAC11B01-04)

譚云蘭(1972-），女，江西新干人，副教授，博士生，主要從事虛擬現(xiàn)實、圖形圖像處理研究(E-mail:tanyunlan@163.com);

*譚 彬(1982-），女，湖南常寧人，講師，博士生，主要從事信號處理，圖像處理研究(jatanbin@163.com).