基于圖割和顯著性的圖像結構表示方法研究

摘 要:通過分析現有基于內容的圖像結構表示方法，存在魯棒性不強和結構多樣性易增加分類的復雜性并降低分類正確率的問題，研究了基于圖割的二叉樹和基于顯著性的多叉樹圖像結構表示方法，并與基于區域相似性的二叉樹和改進深度的多叉樹表示進行比較。實驗表明，基于圖割和顯著性的表示方法能有效提高結構樹的語義性和分類性能。

關鍵詞:圖像結構; 圖割; 顯著性; 二叉樹

中圖分類號:TP391文獻標志碼:A

文章編號:1001-3695(2009)09-3589-04

doi:10.3969/j.issn.1001-3695.2009.09.114

Image structure representation based on graph-cut and saliency

CHEN Jun， WANG Qing

(School of Computer Science Engineering， Northwestern Polytechnical University， Xi’an 710072， China )

Abstract:Image classification performance was influenced by the diversity of structures accroding to the analysis of content-based image structure representations. Therefore， building tree structures robustly was in great demand. This paper investigated the graph-cut and saliency-based image structure representations. Experimental results show that these two tree structures are efficient and semantic in image representation comparing to the region-based binary tree and low depth tree representations.

Key words:image structure; graph-cut; saliency; binary tree

0 引言

隨著計算技術的發展，基于內容的圖像檢索技術(content-based image retrieval，CBIR)成為圖像檢索技術的主流，利用從圖像上客觀提取出來的底層視覺特征，包括顏色、紋理等，進行圖像的相似性匹配，進而得到特征相似的圖像作為檢索結果。然而，在高維特征向量空間使用距離計算得到的可視特征的相似性，與其表示的圖像真實內容的相似性并不總是一致的。同時，生理學和心理學方面的研究表明，人類是以結構的方式感知現實世界的，即對象及其相互間的結構關系對人類的認知都起到了作用，那么對圖像相似性的判斷不能僅僅依賴于圖像視覺特征上的相似，更多地包含了對圖像內容的感知和理解，這些感知和理解是圖像視覺特征無法表達的，即存在語義鴻溝問題。因此，必須讓圖像表示包含語義在內的更高層的內容信息，才能使基于圖像內容的表示更符合人類的思維。

在圖像領域，圖像區域或對象間的空間結構關系在描述圖像內容時擔當了重要角色。這種空間關系特征相對低層視覺特征而言，包含了更多的語義信息。通過將圖像中的有意義區域按照某種規則組織成樹型結構，圖像內容便能更有層次、更清楚地表現出來，有益于圖像分類和圖像檢索。例如，區域間的空間關系具有平移和旋轉不變性，同時，這種表示方法可以避免系統使用高維向量來描述圖像的視覺特征。文獻[1~3]對基于分割區域的圖像結構表示進行了研究，采用了根據圖像區域間的相似性構造二叉樹或者多叉樹的方法。實驗表明，這種圖像內容的層次表示較好地表征了圖像的語義信息，但是產生了二叉樹深度大和多叉樹的多樣性問題。因此，從圖像分割結果中構造魯棒性強的結構數據是一個急需解決的問題。

本文研究的重點是結構信息的表示和處理，因此直接采用了UC Berkeley的圖像庫及其圖像分割結果。圖像庫中每幅圖像對應的分割結果均以分割文件的形式給出。由于圖像分割塊數過多，會增加結構表示的復雜度，即對應的生成樹的節點數和深度過大而增加問題的復雜性，而且大多數時候小區域包含的語義信息較少。為了減少小區域的影響，采用了一種小區域預處理策略，定義面積小于圖像面積1/100的區域為小區域，將與其鄰近的最相似區域預先合并。雖然進行了部分區域合并操作，但僅是作為一種預處理，該操作能在不減少區域語義信息的情況下縮小分割區域的數目，有效簡化圖像的結構表示。在此基礎上分別研究了基于圖割和顯著性的圖像結構表示方法，并進行了實驗比較。

1 圖像結構表示

Salembier等人[1]討論了基于區域的圖像二叉樹結構表示方法。文獻[2]中的實驗結果表明，基于區域的圖像表示優于四叉樹結構，能達到較好的分類結果。但是，需要比較不同分割結果構造的結構樹，并從中選擇較符合人類思維的結構。

文獻[1，2]均采用的是在圖像分割后，通過合并最相似的兩個鄰接區域，構造結構二叉樹的表示。

a)計算所有鄰接區域的相似性定義為

Dij=0.299×|Ri-Rj|+0.587×|Gi-Gj|+0.114×|Bi-Bj|(1)

其中:(R，G，B)表示區域的平均顏色。

b)選擇最相似的一對區域進行合并。

c)更新鄰接區域和相似性，判斷是否整幅圖像僅剩一個區域，若不是則轉a)，否則停止操作。

為了降低生成樹的深度，Wang等人[3]修改了上述二叉樹的構造方法，提出了一種構建低深度樹型結構LD-tree的方法。其關鍵在于在每次區域合并之前，計算所有相鄰似性值小于該平均值，則合并鄰接區域，如圖1所示。因此，對于每一個樹的節點，它的孩子節點不再局限于兩個，相應地，樹的深度將顯著降低。但是，孩子節點的增多將增加神經網絡的參數和訓練復雜度，同時，這種構造樹的方法增加了樹的多樣性。

2 基于圖割的結構表示

網絡流量定理中有兩個引人關注的問題:a)尋找從一個節點到另一個節點的最大流量;b)尋找每對節點之間的最大流量。利用無向圖的下列屬性，Gomory等人[4]解決了無向圖中尋找每對節點之間的最大流的問題。

給定一個圖G=(V，A)，其中圖的頂點集V={v1，v2，…，vm}，圖的邊集A={aij}，aij表示了節點i和節點j之間的連接，且對于每條邊aij存在一個流量值cij。

定理1 兩節點(s，t)之間的最大流等于它們之間的最小割。

圖的一個割(V0→V1)是一組邊集，刪除這些邊便將圖分為了不相交的兩部分，且s屬于V0，t屬于V1。這個割的代價定義為F(V0→V1)=∑aij∈(V0→V1)cij

。s與t之間的最小割是具有最小代價的一組邊集。

定理2 給定(Vs→Vt)是從源點s到匯點t之間的最小割，r和r′分別是Vs(或者Vt)內的任意兩個節點，那么r和r′之間的最大流的計算可將Vt(或者Vs)內的所有節點濃縮為單個節點vi (或者vj)。

定理2表明，如果(s，t)間存在最小割(Vs→Vt)，那么Vs(或者Vt)內的任意兩個節點間不存在會劃分Vt(或者Vs)的最小割。

定理3 假設圖G=(V，A)是一個完全圖，其與圖G具有相同的節點集，每對節點之間邊的流量值與該對節點間的最大流值相等。給定T是圖G的最大生成樹，那么T流量等價于圖G。

流量等價意味著G和T中節點的最小割或者最大流值是相等的，T被稱為等價樹。若構造了T，那么任意節點對(s，t)之間的最大流值與在T中惟一連接s和t的路徑上所有邊的流量值的最小值相等。并且，如果這條路徑上存在邊的流量值與(s，t)之間的最大流值相等，那么刪除該邊便得到(s，t)的一個最小割。

圖像的區域鄰接圖表示為G=(V，A)。其中V=(v1，v2，…，vm)表示一個分割區域，A={aij}表示區域vi與vj之間的連接邊當且僅當區域vi與vj相鄰，邊上的權值cij表示區域vi與vj的相似性，而且cij越大意味著區域vi與vj越相似。由上述可知，通過刪除一些邊，可將G劃分為多個不連接的子圖。假設需要將G劃分為兩個子圖，并且這兩個子圖間的相似性要盡可能地小，一個好的標準是使這兩個子圖之間的最大流最小。

根據定理1，計算G中所有節點對之間最小割組成的割集，通過刪除該割集中的最小割對應的邊集，可以得到一個最優劃分。任何其他的割都將只能得到兩個子圖間一個更大或者相等的最大流。由定理3知，等價樹的連接邊與節點間的最大流相等。因此，可以容易地通過刪除等價樹中的最大流值的連接邊來得到任意個數的子圖。Wu等人[5]通過刪除等價樹中流量最小的k-1條邊來得到無向圖G的k個子圖，達到將節點聚成類的目的。

由上述可知，每次刪除等價樹中的一條邊，便可以將節點分為兩類。按照流量遞增的形式，逐次刪除流量最小的邊，直到將所有的邊都刪除，將得到單個獨立的節點。可按照該過程來構造一個二叉樹，即將整幅圖像的所有區域逐次二分，直到等價樹中不存在邊。

由圖2可以看出，刪除等價樹中第一條邊之后，區域2、3聚為一類，同時區域6、7、8也聚為一類，進一步將區域8與區域6、7區分為兩類，得到結構樹。該方法與自動二叉樹的生成方法有如下區別:

a)自動二叉樹進行區域合并時僅以欲合并的兩區域的相似性為判斷標準，圖割中兩區域間流量的計算考慮到了相鄰區域的影響。

b)自動二叉樹的兩區域合并后，需要多次重新計算新區域的特征并將新特征用于后續的操作中，圖割中不需要，僅需要一次性生成等價樹，直接利用等價樹中的流量值。

3 基于顯著性的結構表示

在實際應用中，圖像的使用者往往只對圖像的某一部分感興趣，這部分區域被稱為感興趣區域或者顯著性區域(region of interest，ROI)。它可以被認為是圖像中最顯著的像素集合，這些像素稱為顯著點或者興趣點，因此確定ROI的關鍵在于尋找圖像中的顯著點。

Ltti等人[7]提出了一個模擬生物體視覺注意機制的選擇性注意模型，該模型特別適合于處理自然圖像。模型中使用圖像金字塔分解亮度、顏色和方向特征。金字塔共有九層，定義金字塔的中心層c是{2，3，4}層，外周層s是c+δ，其中δ={3，4}，利用“中心—外周”機制抽取各個特征的對比信息。在計算時首先用濾波器對金字塔中每層的圖像進行濾波，然后按照六種計算組合:{2-5，2-6，3-6，3-7，4-7，4-8}將中心層和外周層之間像素值對應相減，計算得到的結果稱為對比映射圖。

模型中分別對三種初級視覺特征進行處理。定義Θ表示中心層與外層之間的減操作。亮度特征有一個量，表示圖像的亮度對比。如果處理真彩色圖像，則先用公式I=(r+g+b)/3將其轉換成灰度圖像，其中r、g、b分別表示圖像的紅、綠、藍通道。亮度對比映射圖的計算公式為I(c，s)=|I(c)ΘI(s)|。顏色特征有兩個量，分別表示紅/綠和藍/黃色彩通道的對比。定義為R=r-(g+b)/2，G=g-(r+b)/2，B=b-(g+b)/2和Y=(r+g)/2-|r-g|/2四個顏色協調通道。顏色對比映射圖的計算公式為

RG(c，s)=|(R(c)-G(c))Θ(G(s)-R(s))|

BY(c，s)=|(B(c)-Y(c))Θ(Y(s)-B(s))|

方向特征有四個量，分別表示四個局部方向{0°，45°，90°，135°}。方向對比映射圖的計算公式為

O(c，s，θ)=|O(c，θ)ΘO(s，θ)|

這些初級視覺特征分解結束后共生成42個對比映射圖，其中亮度特征6個、顏色特征12個、方向特征24個。

顯著性映射圖是由所有對比映射圖合成的，大小定義為輸入圖像的1/24。為了生成顯著性映射圖，42個對比映射圖首先全部歸一化為特征映射圖并調整自身大小;然后將6幅亮度特征映射圖之間的像素值對應相加并歸一化后生成亮度特征顯著性映射圖I，同理可以生成顏色和方向特征顯著性映射圖C和O;最后將各特征顯著性映射圖乘以對應的權值，它們的線性組合即為顯著性映射圖S。

將顯著性映射圖進行線性插值，調整大小與圖像大小相同。計算分割區域內所有像素點的顯著值的和，用該和值近似表示區域的顯著性大小。根據顯著性構造樹型結構時采用了如下原則:

a)顯著性越大的區域，在樹中的深度越小;

b)顯著性相似的區域，在樹中位于同一層。

構造樹時首先將所有區域按照顯著性的大小聚類，計算聚類中心的值，將聚類中心值最小的類別中的區域合并，若該類別中只有一個區域，則不進行合并;將操作后得到的區域歸入聚類中心值次大的類別中。重復上述過程直至只有一個區域，如圖3所示。

在進行區域聚類時，采用了最鄰近規則聚類，在兩區域顯著性差異小于某閾值時，聚為一類。

4 自適應處理結構數據

Sperdutia等人[9]提出了用神經網絡處理結構數據的方法，網絡結構如圖4所示。其算法叫做結構反傳算法(BPTS)，其自適應處理結構數據的統一編碼公式是

x=Fn(Aq-1y+Bu)(2)

y=Fp(Cx+Du)(3)

其中:x、u和y分別代表隱層神經元的輸出向量、輸入層神經元的輸入向量和輸出層神經元的輸出向量;q-1表示來自孩子節點的輸入;Fn是一個非線性函數，如Sigmoid函數;參數矩陣A、B、C和D，矩陣A=[A1A2…Ac]，這里c是樹的孩子節點的最大個數。

訓練過程就是通過最小化代價原則從輸入樣本中得到參數矩陣A、B、C和D:

J=1/2∑i=1N‖di-yi‖2(4)

其中:yi和di分別表示第i個樣本的實際輸出和理想輸出，N表示樣本個數。

5 實驗結果及分析

本文以UC Berkeley圖像庫為實驗對象，將圖像庫分為了動物類和風景類，如圖5所示。從圖像庫中選擇40幅圖像中各20幅分別作為兩類訓練樣本。采用Berkeley分割圖像庫中的分割結果文件對圖像進行分割，為了減少節點數和深度，分割結果選擇了分割塊數較少的類別，并對圖像分割結果進行小區域先合并的處理。實驗中每個節點有四個屬性，分別為區域的顯著性、區域的平均顏色、標準方差和三次根非對稱性。

迭代神經網絡的參數是(I4，C5，S2，O2)，即四個輸入特征，最多五個孩子，四個隱層節點和兩個輸出節點。迭代網絡處理樹型結構的某一節點時，如果是葉子節點，節點的孩子屬性的初始狀態為0;如果是非葉子節點，則節點的孩子屬性是其孩子節點的輸出。以自適應處理整個樹型結構時，以自底向上的方式先處理葉子節點，在處理完所有葉子節點后，再處理其父節點，重復這個過程直至到達樹的根節點。由于隱層節點數的不同，影響了網絡對不同結構樹的訓練性能，實驗中分別取了10、12、15和18五種不同的隱層節點數，表1列出了各類結構中的正確率。

從表1可以看出，最好的分類正確率97.5%是由LD-tree結構在隱層節點數為15時達到的，基于圖割和基于顯著性的結構樹的正確率均未達到期望值。值得注意的是，實驗中構造LD-tree的過程時對區域相似性計算加入了顯著性，將式(1)更新為式(5)，即顏色相似性和顯著性相似性的加權和，加入了顯著性后構造的樹型結構提高了分類性能。

D′ij=c1×Dij+c2×(Si-Sj)(5)

其中:Si表示區域i的顯著性;c1和c2表示權值，這里取0.5。

基于圖割的結構樹在構造時僅采用了二叉樹的形式，相較于LD-tree增加了樹的深度，進而增加了訓練的復雜度。但是與一般二叉樹相比，它的訓練正確率有了明顯提高。這說明考慮到了相鄰區域影響因素的基于圖割的表示方法具有較強的語義性。

從隱層節點數的變化可以看出，基于顯著性的結構樹在隱層節點數較少時即能達到較好的分類性能，而基于圖割的結構數需要較多的隱層節點。這是由于基于圖割的樹型結構具有較大的樹深度，基于顯著性的結構樹在閾值選擇越大時，聚類數越少，樹深度越小。因此，基于圖割的結構樹在訓練時需要較多的隱層節點和網絡參數。

雖然基于圖割和基于顯著性的結構樹在分類性能上并沒有明顯提高，但是為原來僅基于相似性合并的結構樹構造方法引入了新的思路，即圖割和顯著性，并且實驗證明構造的結構樹具有較好的語義性，能用于圖像分類。實驗中的分類性能還受到分割結果的影響，即分割結果的不同可能導致不同的區域劃分，從而直接影響生成樹的結構。

6 結束語

本文在圖像分割的基礎上，提出了基于圖割和基于顯著性的圖像結構表示方法，并與一般二叉樹和LD-tree進行了比較。實驗表明，基于圖割的表示方法含較多的語義性，顯著性特征和多叉樹結構表示使得語義相似的區域能出現在結構樹的同一層中，增加了結構樹的語義信息，能有效提高結構樹的語義性和分類性能。因此，在基于圖割的二叉結構樹的基礎上研究基于圖割的多叉樹的構造方法是進一步要研究的工作。

參考文獻:

[1]SALEMBIER P， GARRIDO L. Binary partition tree as an efficient representation for image processing segmentation and information retrieval[J].IEEE Trans on Image Processing， 2000， 9(4):561-576.

[2]WANG Zhui-yong， FENG D. Region-based binary tree representation for imge classification[C]// Proc of International Conference on Neural Network and Signal Processing. 2003:232-235.

[3]WANG Zhui-yong， FENG D. Comparison of image partition methods for adaptive image categorization based on structural image representation[C]// Proc of the 8th Control Automation Robotics and Vision Conference. 2004:376-680.

[4]GOMORY R E， HU T C. Multi-terminal network flows[J]. Society for Industrial and Applied Mathematics， 1961(4): 551-570.

[5]WU Z， LEAHY R. An optimal graph theoretic approach to data clustering: theory and its application to image segmentation[J].IEEE Trans on Pattern Analysis and Machine Intelligence，1993， 15(11):1101-1113.

[6]MARCIALIS G L， ROLI F， SERRAU A.Graph-based and structural methods for fingerprint classification[M]// Applied graph theory in vomputer vision and pattern recognition.Berlin:Springer，2007:205-226.

[7]LTTI L， KOCH C， NIEBUR E. A model of saliency-based visual attention for rapid scene analysis[J].IEEE Trans on Pattern Analysis and Machine Intelligence，1998， 20(11):1254-1259.

[8]ZHANG Hui， RAHMANI R， CHOLLETI S R， et al. Local image representations using pruned salien points with applications to CBIR[C]// Proc of International Multimedia Conference. 2006:287-296.

[9]SPERDUTIA，STARITA A. Supervised neural networks for the classification of structures[J]. IEEE Trans on Neural Networks， 1997， 8(3):714-735.