基于多類標決策樹和區域匹配的多源圖像修復算法

王嵩，肖娟

（湘南學院計算機與人工智能學院，郴州 423000）

0 引言

圖像修復是數字圖像處理技術的一項重要內容，核心思想是利用圖像中的現有信息來填補破損區域，使修復后的圖像滿足人眼視覺要求［1］?；诩y理合成的圖像修復算法，主要應用于填補待修復圖像中存在的較大面積破損，此類算法中比較有代表性的是Criminis等提出的融合紋理合成和Inpainting技術于一體的基于樣本塊紋理合成的修復技術［2］。在破損區域覆蓋多類物體時，此算法修復后往往出現結構失真。很多學者針對此不足，從不同角度提出了一些改進算法［3-5］。

圖像修復的過程主要是以圖像已知區域的像素信息為參考，恢復出破損區域的信息。前段提及的兩類經典修復算法，都需要根據一定的假設前提依靠鄰域信息來進行修復。而在信息量缺失過多的情況下，僅依靠圖像自身內容進行修復的算法均難以達到理想的效果。針對此類情形，若能找到與待修復圖像風格相似的圖像，就能夠獲取額外的信息量，為修復提供指導。因此，多源圖像修復將是一個非常有實用價值的研究方向。

本文提出一種基于多類標決策樹和區域匹配的圖像修復算法。將一幅包含若干內容對象的圖像看作具有多個類標的集合，圖像中的每個對象歸屬于一個類標。選取多幅源圖像進行均勻劃分，得到的每一個圖像塊作為訓練樣本，將每一個圖像塊的顏色和紋理特征提取出來作為樣本的屬性集，并通過K均值聚類獲取每個樣本的多類標集，構建具有源圖像顏色及紋理信息的多類標決策樹；將破損圖像中的圖像場景塊用于測試，提取均勻劃分后各圖像塊的顏色及紋理特征，利用建立的多類標決策樹進行分類判定，得到破損圖像的類標集；在各個源圖像中選擇類標集一致的，列為修復的參考源，逐一進行移位區域匹配，篩選最優的內容映射進破損區域；最后修正其色彩信息，使修復后區域與周圍環境協調一致。

1 本文算法描述

為了應對具有豐富內容圖像的修復問題，利用其他圖像作為參考源為修復提供指導已成為必需的手段。一幅圖像的內容可分解成多個不同的對象，以風景圖像為例，它可能由天空、沙灘、海洋、草地、樹木、高山等景物構成。要判斷一幅圖像的內容，從決策樹的角度可以看做是一個多類標問題。由于決策樹在這種多類標問題的處理方面的優勢，因此可以從多類標的角度出發建立多源圖像的多類標決策樹。

1.1 多類標決策樹的建立

從建立決策樹的角度出發，需要提取供訓練的樣本數據，樣本數據的獲取及處理可分為以下2個步驟。第一步，確定訓練樣本集；第二步，確定特征向量。

1.1.1 訓練樣本集的確定

根據建立決策樹算法原理要求訓練樣本的數量必須超過一定的數值，并且類標要已知同時考慮到多源圖像修復的出發點是同種風格圖像間場景的互補，由此確立了樣本集的基本選取準則：

（1）源圖像的選取。選取圖像分類檢索庫中的一些典型的圖像，里面包含了風景圖像典型景物的組合，滿足其類標的合集包含的所有類標，為后續的修復提供指導。

（2）樣本圖像集的形成。出于算法及實驗的需求，為獲得足夠數量的訓練樣本，對選取的源圖像在橫縱方向上進行了均勻的5×5的分割，具體效果如圖1和圖2所示。最后選取1500個訓練樣本圖像，一部分用于訓練，其余的用作測試決策樹的預測準確率。

圖1 樣本圖像

圖2 5×5區域分割的圖像

（3）樣本類標的確定。為了確定類標，對上一步得到的1500個訓練樣本，確定其標準質心，并通過K均值聚類的方法實現計算機自動賦予類標。

在樣本類標生成時，如果只考慮圖象的lαβ三個分量，通過K均值聚類來確定類標，那么將面臨以下問題：海洋和天空均為藍色，可能會錯誤的判定為同一類，將會對后續進行修復造成填充異常，所以在決策樹樣本的訓練數據部分還要加入樣本的紋理特征，區分相似顏色的不同場景，實施的操作如下：

（1）在顏色信息方面，首先將圖像從RGB空間轉化到lαβ空間，然后算出經過分塊劃分后各樣本3個分量的均值和方差。

（2）在紋理信息方面，利用灰度共生矩陣提?。?/p>

設k（x，y）是大小為M×N的一幅圖像，Wg為其灰度級別，其滿足一定空間關系的灰度共生矩陣為：

式中，#x代表集合x中元素的個數，H代表Wg×Wg的矩陣，如（x1,y1）到（x2,y2）間的距離為d，兩者與橫坐標軸的夾角為θ，設?=(d,θ)，則可通過各種間距及角度的灰度共生矩陣H（i，j），計算下面的4個特征值：

（1）對比度：

公式（2）表示圖像的全部像素的灰度差（|i-j|)的平均值，灰度差即對比度大的像素越多，這個值就越大。

（2）紋理一致性：

由公式（3）可知，當H?(i,j)中有少數值大時，上式的值也大，反映出特定的像素對較多時一致性好。

（3）像素對灰度的相關性：

其中vp和σp表示p的均值與方差。公式（4）的計算結果取值范圍在-1～1之間，與?相關的像素對的灰度值成比例地增大，是描述?的周期性的模式。

（4）熵：

H?(i,j)的值分布越均勻，公式（5）的結果值就越大，此式反映的是紋理均衡性的逆性質。

灰度共生矩陣是在灰度圖像上進行操作，要確定Wg和d，θ三個參數值，Wg與程序的運算量有關，d,θ與提取特征的有效性有關，一般取d=1，θ以45°為間隔。

以下介紹本算法的具體操作步驟。

第一步，將樣本圖像灰度化處理，設得到的灰度圖像大小為M×N，初始灰度級別為O1；

第二步，將灰度級Wg設定為16，將原始圖像轉化為16級灰度；

第三步，設d=1，夾角θ=0°,45°,90°,135°，通過公式（1）計算，得到4個方向上Wg×Wg的矩陣H1，H2，H3，H4；

第四步：根據公式（2）—（5）對H1，H2，H3，H4計算上述相應的值，可得到16個特征值。

經過以上四步的計算，將獲取每個樣本的16個紋理特征值，再與顏色的6個特征值相加，合計共得22個特征值。為便于處理，對得到的這些特征值進行預處理，將其轉化為離散數據，并使得其取值為［1，10］的整數值，用作決策樹的訓練樣本數據。

1.1.2 樣本類標的確定

彩色圖像的任一像素點都可以用三維的顏色矢量lαβ來表示。因此，對圖像進行分割可以轉化為對顏色矢量集的聚類劃分，出于建樹的需要對源圖像中像素點進行聚類劃分，是為了給圖像的對應區域確定類標。為保證每幅源圖像相似區域賦予相同的類標，采用了如下的K均值聚類算法：

（1）對涉及的各個類標的單一景物圖像進行統計分析，提取各個類標的lαβ三個分量特征均值，作為K均值聚類質心的參考。

（2）依據每幅源圖像的景物數目確定K值進行聚類，聚類公式采用lαβ三個分量之間的歐氏距離。對于得到聚類區域，根據步驟（1）中的參考參數，根據距離最小準則，對相應的區域賦予類標。

（3）保存聚類后的圖像各像素點的類標結果。

1.1.3 多類標決策樹算法

針對本文需求要建一棵單值屬性的多類標決策樹，程序實現部分采用深度遍歷的方式，相關的各種關鍵建樹的規則依據SCC_SP算法中的方案SCC_SP_1［6］，在程序調試的時候人機交互調整和修正類標號的支持度Sup（Ci），類標號支持度閥值Supmin，類標號支持度距離閥值Diffmin以及記錄最小個數Nummin。調整和修正的原則是需保證樹的簡潔及預測準確率高。

決策樹算法包括構造和預測兩個階段［7］，下面是建立多類標決策樹的算法：

●構造階段：

Constructing（）

輸入：訓練數據集Train-D。輸出：決策樹T。

步驟1 初始化樹T，將Train-D賦給根結點；

步驟2 如果T的葉子結點都為需要停止的結點，則返回T；

步驟3 對T中不需要停止的結點進行屬性選擇，并根據選擇的屬性對該結點進行后繼結點的生成；

步驟4 判斷后繼結點是否需要停止，對需要停止的結點標記其類標集，否則以自身為Train-D，返回步驟2。

●預測階段：

Predicting（）

輸入：測試數據集Test-D。輸出：預測準確率P和預測類標集合L。

初始化i＝1，Test-D的記錄條數為N。

步驟1 從根節點開始，對于Test-D的第i條記錄，按照其對應節點的屬性取值，進行樹T的遍歷，到達葉子節點后，得到該記錄的預測類標集，并記錄下來；

步驟2 判斷i，若i大于N則轉至步驟3，否則i++，轉至步驟1；

步驟3 計算所獲得的全部預測類標集與真實類標集之間的相似度，其相似度的均值即為預測準確率P。輸出P和預測類標集合L。

1.2 破損圖像類標預測

多源圖像的圖像修復通?；谌缦录僭O，多幅源圖像與目標圖像的形狀風格基本一致，目標圖像中任一對象都可以在參考源圖像中找到類似的場景。利用源圖像樣本塊訓練得到的多類標決策樹對目標圖像進行分類決策，得到的結果一方面可以確定目標圖像中各圖像塊的類標，另一方面可以確定目標圖像與參考源圖像之間的場景匹配程度，后續完成對目標圖像空白內容的場景修復。

具體的做法是：將破損圖像同樣均勻分割成5×5的區域，提取每一區域的顏色和紋理特征值（破損處的信息不予考慮），作為目標圖像樣本的屬性集。利用多類標決策樹，對各個區域進行決策，確定其類標。將各個區域的類標集匯總，與各個源圖像進行比較，類標集完全一致的即可看做為修復的源圖像。

1.3 區域匹配

搜索到類標完全一致的源圖像后，將破損邊界線靠外20個象素點寬的區間定義為匹配帶，將整個破損區域連同匹配帶區間整體作為掩模，在源圖像中進行移位匹配，匹配公式如下：

其中F表示的是掩模內的已知像素點，F′對應源圖像中與F掩?？臻g位置相對應的像素點，M為已知像素點的數目。

將移位匹配計算得出的最小距離所對應的源圖像掩模所覆蓋的場景整塊填充完成修復。

1.4 色彩修正技術

在完成區域匹配修補之后，新填充的內容與原始場景在色彩上可能會有差異。為了使修復結果更加自然，采用一種基于聚類的色彩修正算法。

基于聚類的色彩修正算法步驟如下：

第1步，提取修復區域所有像素點的lαβ值利用K均值算法聚成M類（根據修復區域面積的大小及場景色彩豐富程度，M可取值3，4，5，6）。

第2步，分別計算M類中各包含所有象素點的α、β均值和方差，記為μ1α（m），μ1β（m），δ1α（m），δ1β（m），其中m=1～M，并統計各類別中象素點的個數，記為num1～numM。

第3步，以聚類結果建立分類器，對破損圖片原有場景象素點進行K近鄰分類，并統計各類別中象素點個數,記為num21～num2M。以及各類別中,α、β均值和方差μ2α（m），μ2β（m），δ2α（m），δ2β（m），其中m=1～M。

第4步，對新填充場景中屬于第m類的象素點進行色彩映射，映射公式如下，其中m=1～M。

2 實驗結果分析

為驗證本文算法的有效性，在Intel i3-4150 CPU和4 G內存的PC上，以Matlab 2012為平臺進行仿真實驗。實驗的圖片是從文獻［8］提供的網址鏈接下載，共下載了2700幅256×256像素的各類自然圖像。選擇了其中的300幅圖像作為參考源圖像。并另選擇了60幅圖像隨機構造了大面積的破損。每幅圖像的平均修復時間為37秒。包含了多類標決策，區域匹配及色彩修正。

2.1 建立決策樹的結果

根據SCC_SP算法建立的多類標決策樹，樹的規模和精確度得到合適的控制。實驗結果表明：樹的節點在5～8個時運算效率高。

2.2 修復結果與分析

圖3為山巖樹葉圖，圖3（a）為其原始圖像，圖像中有藍天，黃綠樹枝葉和灰白山巖及樹陰影。圖3（b）為破損圖像，其破損區域為圖像中最復雜的三景交匯處，在破損的區域里即有藍天、灰白山巖又有黃綠樹枝葉。圖3（c）為與破損區域的類標集相近的源圖像。圖4為油菜花田圖，圖4（a）為其原始圖像，圖像中有天空，綠樹，大片黃色油菜花田。圖4（b）為破損圖像，其破損區域為天空與油菜花田的交匯處，場景包括天空，綠樹與黃色油菜花田。圖4（c）為與原始圖像破損區域的類標集相近的源圖像。圖5為樹林圖，圖5（a）為其原始圖像，圖像中色調比較單一綠色的大樹與綠色的草地。圖5（b）為破損圖像，其破損區域為一部分綠樹與草地。圖5（c）為與原始圖像的類標集相近的源圖像，其主要場景也是綠樹與草地。圖6為海面圖，圖6（a）為其原始圖像，圖像中有灰藍色的天空，海岸及大片藍色海面。圖6（b）為破損圖像，其破損區域為天空與海面交匯處，主要破損的區域是海岸部分，與圖3、圖4、圖5矩形破損區域比較其破損區域為不規則破損。圖6（c）為與原始圖像破損區域的類標集相近的源圖像，其主要場景也是天空與海岸及海面，色調也與原始圖像相近。

圖3 山巖樹葉修復圖

圖4 油菜花田修復圖

圖5 樹林修復圖

圖6 海面修復圖

圖3（d）、圖4（d）、圖5（d）、圖6（d）都是將各圖中（c）源圖像中與破損區域類標集最接近的區域塊位移填充進（b）破損圖像中的結果，從各圖（d）區域匹配結果可以看出，圖像色調及場景大致匹配但是在破損區域的邊緣都存在一定的不協調。

針對各圖（d）中區域匹配不協調的結果，利用基于聚類的區域顏色映射算法對填充后不一致的色彩進一步的修正，修正后的結果如圖3（e）、圖4（e）、圖5（e）、圖6（e），從色彩修正結果可以看出各圖修復后的色彩與場景都比較自然，符號人眼視覺要求，修復效果佳。

3 結語

以源圖像中的圖像塊作為訓練，提取其顏色、紋理特征，建立多類標決策樹；利用多類標決策樹對破損圖像進行分類，找到修復源圖像來實現對目標圖像的修復。該算法對于包含復雜對象物體的目標圖像具有較好的修復效果，彌補了單源圖像修復算法參考信息不足的缺點，同時為同風格圖像的批量修復提供了新的借鑒和參考。下一步的工作考慮建立具有同風格類型圖像的類標庫，增加類標的多樣性，從而建立基于該風格特征圖像的多類標決策樹，提高決策樹對圖像的分類精度，增強圖像修復后結果圖像的細節部分修復效果等。