基于多類標(biāo)決策樹和區(qū)域匹配的多源圖像修復(fù)算法

王嵩，肖娟

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

0 引言

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

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

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

1 本文算法描述

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

1.1 多類標(biāo)決策樹的建立

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

1.1.1 訓(xùn)練樣本集的確定

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

（1）源圖像的選取。選取圖像分類檢索庫中的一些典型的圖像，里面包含了風(fēng)景圖像典型景物的組合，滿足其類標(biāo)的合集包含的所有類標(biāo)，為后續(xù)的修復(fù)提供指導(dǎo)。

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

圖1 樣本圖像

圖2 5×5區(qū)域分割的圖像

（3）樣本類標(biāo)的確定。為了確定類標(biāo)，對上一步得到的1500個訓(xùn)練樣本，確定其標(biāo)準(zhǔn)質(zhì)心，并通過K均值聚類的方法實現(xiàn)計算機自動賦予類標(biāo)。

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

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

（2）在紋理信息方面，利用灰度共生矩陣提取：

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

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

（1）對比度：

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

（2）紋理一致性：

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

（3）像素對灰度的相關(guān)性：

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

（4）熵：

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

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

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

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

第二步，將灰度級Wg設(shè)定為16，將原始圖像轉(zhuǎn)化為16級灰度；

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

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

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

1.1.2 樣本類標(biāo)的確定

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

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

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

（3）保存聚類后的圖像各像素點的類標(biāo)結(jié)果。

1.1.3 多類標(biāo)決策樹算法

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

決策樹算法包括構(gòu)造和預(yù)測兩個階段［7］，下面是建立多類標(biāo)決策樹的算法：

●構(gòu)造階段：

Constructing（）

輸入：訓(xùn)練數(shù)據(jù)集Train-D。輸出：決策樹T。

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

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

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

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

●預(yù)測階段：

Predicting（）

輸入：測試數(shù)據(jù)集Test-D。輸出：預(yù)測準(zhǔn)確率P和預(yù)測類標(biāo)集合L。

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

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

步驟2 判斷i，若i大于N則轉(zhuǎn)至步驟3，否則i++，轉(zhuǎn)至步驟1；

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

1.2 破損圖像類標(biāo)預(yù)測

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

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

1.3 區(qū)域匹配

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

其中F表示的是掩模內(nèi)的已知像素點，F(xiàn)′對應(yīng)源圖像中與F掩?？臻g位置相對應(yīng)的像素點，M為已知像素點的數(shù)目。

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

1.4 色彩修正技術(shù)

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

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

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

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

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

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

2 實驗結(jié)果分析

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

2.1 建立決策樹的結(jié)果

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

2.2 修復(fù)結(jié)果與分析

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

圖3 山巖樹葉修復(fù)圖

圖4 油菜花田修復(fù)圖

圖5 樹林修復(fù)圖

圖6 海面修復(fù)圖

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

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

3 結(jié)語

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