基于互信息圖割的風(fēng)景圖片美學(xué)測度

譚云蘭，譚 彬

基于互信息圖割的風(fēng)景圖片美學(xué)測度

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

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

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

最大互信息；可計(jì)算美學(xué)；圖像分割；二叉分割樹；大頂堆

0 引言

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

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

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

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

1.1 信息理論

1.2 圖像分割問題描述

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

2 分割算法

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

2.1 統(tǒng)計(jì)Bins

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

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

(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ū)域分割信息熵的計(jì)算

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

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

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

圖2 (a) 分割區(qū)域?yàn)?0 的空間二叉分割樹 (b) 分割區(qū)域?yàn)?0的分割位置及互信息

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

2.4 互信息圖割美學(xué)測度算法描述

算法1. 互信息圖割美學(xué)測度算法

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

輸出：分割效果圖，分割圖的美學(xué)測度值

算法描述：

Step 1 首先統(tǒng)計(jì)待分割的圖像的壓縮成柱狀bins。對(duì)每個(gè)像素，計(jì)算其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，計(jì)算，其中l(wèi),m,n=1,2,3,4；

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

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

2.5 時(shí)間復(fù)雜度分析

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

3 實(shí)驗(yàn)結(jié)果與分析

本實(shí)驗(yàn)數(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。為了獲得更真實(shí)有效的美學(xué)評(píng)估值作為對(duì)應(yīng)ID編號(hào)照片的參考Groundtruth，在dpchallenge網(wǎng)站上大量在線照片中，設(shè)置下載過濾條件Votes>120。本實(shí)驗(yàn)遴選200張照片，由于版面有限，選取其中4副照片的分割效果圖，如圖4~圖7所示。實(shí)驗(yàn)硬件環(huán)境為內(nèi)存2M+Duo CPU 2.8GHz的PC機(jī)，軟件環(huán)境為Matlab2011a+C+ Windows7。

3.1 分割效果圖

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

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果分析

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

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

表1 美學(xué)評(píng)估值

4 結(jié)束語

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

[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].計(jì)算機(jī)學(xué)報(bào),2006,29(2):296-301.

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

[10] 王偉凝,蟻靜緘,賀前華. 可計(jì)算圖像美學(xué)研究進(jìn)展[J].中國圖象圖形學(xué)報(bào),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

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

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

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