基于樣塊改進(jìn)的圖像修復(fù)算法*

王一卜，白艷萍（中北大學(xué)理學(xué)院，太原 030051）

基于樣塊改進(jìn)的圖像修復(fù)算法*

王一卜，白艷萍
（中北大學(xué)理學(xué)院，太原 030051）

圖像修復(fù)是指對(duì)圖像破損區(qū)域進(jìn)行填充或者將圖像中多余物體進(jìn)行移除。在Criminisi算法的基礎(chǔ)上進(jìn)行改進(jìn)，在待修復(fù)塊優(yōu)先權(quán)的計(jì)算過(guò)程中，由于等照度線的曲率可以反映圖像的局部特征，塊與塊之間的方差值可以反映圖像的邊緣信息，因此，將二者考慮進(jìn)來(lái)，確保修復(fù)過(guò)程能夠準(zhǔn)確有序地進(jìn)行。在尋找最佳匹配塊時(shí)，將等照度線的曲率也作為一個(gè)因素增加進(jìn)來(lái)，有效地提高了最佳匹配塊搜索的精確性。經(jīng)過(guò)仿真實(shí)驗(yàn)證明，改進(jìn)后的算法不僅在PSNR值上比原算法有所提高，而且修復(fù)結(jié)果也比原算法更加準(zhǔn)確可靠。

圖像修復(fù)，優(yōu)先權(quán)，等照度線曲率，最佳匹配塊

0 引言

圖像修復(fù)是圖像處理的一個(gè)重要分支，主要用于修復(fù)破損圖像，移除圖像中的多余物體等。Bertalmio等［1］第一次提出數(shù)字圖像修復(fù)技術(shù)這個(gè)術(shù)語(yǔ)是在2000年的一次學(xué)術(shù)會(huì)議上。目前，圖像修復(fù)技術(shù)主要有以下兩種:一種是基于非紋理結(jié)構(gòu)圖像的修復(fù)算法，主要用于破損面積比較小的修復(fù)，代表模型有BSCB模型，TV模型［2］和CDD［3］模型。Kangshun Li等［4］也提出了TV模型和進(jìn)化算法結(jié)合方法。另一種是基于紋理結(jié)構(gòu)的修復(fù)算法，主要用于大面積破損區(qū)域的修復(fù)。比如Iddo等［5］提出的一種基于碎片的修復(fù)方法，利用自相似原理，采用迭代方式修復(fù)破損區(qū)域。后來(lái)，Criminisi等［6］提出了一種基于樣本的修復(fù)算法，該算法直接將結(jié)構(gòu)傳輸和紋理合成二者結(jié)合起來(lái)，利用已知的圖像信息對(duì)破損的區(qū)域進(jìn)行修復(fù)，取得了較好的修復(fù)結(jié)果。這種基于紋理合成的修復(fù)方法主要由3部分構(gòu)成:優(yōu)先權(quán)的計(jì)算、搜索和復(fù)制。

由于Criminisi算法具有較好的修復(fù)效果，使得其一直被廣泛使用。但是該算法其自身也有一些缺點(diǎn):首先，它對(duì)優(yōu)先權(quán)的計(jì)算不是很準(zhǔn)確。在修復(fù)過(guò)程中，隨著修復(fù)的進(jìn)行，置信度值會(huì)迅速下降，并且逐漸逼近于零，這個(gè)特性會(huì)導(dǎo)致修復(fù)塊的優(yōu)先級(jí)次序產(chǎn)生錯(cuò)誤，從而影響到最終的修復(fù)效果；其次，此算法對(duì)最佳匹配塊進(jìn)行選取時(shí)，只考慮到待修復(fù)塊和匹配塊之間已知點(diǎn)像素值的影響，沒(méi)有把圖像的結(jié)構(gòu)信息考慮進(jìn)來(lái)，導(dǎo)致通過(guò)原始相似性度量函數(shù)計(jì)算出來(lái)的最佳匹配塊對(duì)待修復(fù)區(qū)域進(jìn)行填補(bǔ)時(shí)，所生成的修復(fù)效果不能很好地滿足人們的視覺(jué)效果。

本文針對(duì)Criminisi算法的不足進(jìn)行了改進(jìn)，在計(jì)算優(yōu)先權(quán)的過(guò)程中，考慮到等照度線的曲率可以反映出圖像的局部特征，塊與塊之間的方差值可以體現(xiàn)出圖像的邊緣信息，因此，將二者也考慮到優(yōu)先權(quán)的計(jì)算中，避免出現(xiàn)優(yōu)先級(jí)次序錯(cuò)誤；在尋找最佳匹配塊時(shí)，同樣考慮到等照度線曲率的作用，提高了最佳匹配塊選取的準(zhǔn)確性，通過(guò)上述改進(jìn)，使得算法的修復(fù)結(jié)果更加準(zhǔn)確可靠。

1 Criminisi算法簡(jiǎn)介

原始Criminisi算法由3部分構(gòu)成:待修復(fù)塊優(yōu)先權(quán)的計(jì)算，最佳匹配塊的搜索和復(fù)制［8］。接下來(lái)對(duì)這3步分別進(jìn)行介紹。

1.1 計(jì)算待修復(fù)塊的優(yōu)先權(quán)

Criminisi算法對(duì)于待修復(fù)塊優(yōu)先權(quán)確定的基本思想如圖1所示:

圖1 Criminisi算法說(shuō)明

在圖1中，各個(gè)符合表示如下:

I:整個(gè)圖像；

Ω:待修復(fù)區(qū)域；

?Ω:待修復(fù)區(qū)域輪廓；

Φ:已知像素區(qū)域，并且有Φ=I-Ω。

對(duì)于以輪廓上的點(diǎn)p為中心的目標(biāo)塊，定義其優(yōu)先權(quán)為:

其中:C（p）稱為置信度項(xiàng)，用來(lái)衡量目標(biāo)塊Ψp中可靠信息的數(shù)量，且

D（p）為數(shù)據(jù)項(xiàng)，表示的是每次迭代輪廓?Ω前沿的等照度強(qiáng)度函數(shù):

np表示的是?Ω的單位外法線方向，α表示歸一化因子，取值255。

1.2 最佳匹配塊的搜索

1.3 紋理信息的填充與置信度的更新

2 改進(jìn)后的Crinminisi算法

2.1 定義新的優(yōu)先權(quán)

優(yōu)先權(quán)是用來(lái)決定目標(biāo)塊的填充次序的，是整個(gè)算法的核心，因此，優(yōu)先權(quán)的選擇十分重要。文獻(xiàn)［7］指出，等照度線的曲率能夠反映出圖像的一些局部特征，因此，把它也作為一個(gè)考慮指標(biāo)引入進(jìn)來(lái)。又由于塊與塊之間的方差值可以較好地區(qū)別圖像破損區(qū)域的邊緣、紋理以及平滑區(qū)域的結(jié)構(gòu)特征，因此，將待修復(fù)塊沿np方向分割為塊1和塊2，分別計(jì)算出塊1和塊2的方差S2（1）和S2（2），則方差差值為:

其中，α為歸一化參數(shù)，取α=255。

綜合以上因素，定義出新的優(yōu)先權(quán)函數(shù):

2.2 對(duì)相似性度量函數(shù)進(jìn)行改進(jìn)

原算法中通過(guò)計(jì)算目標(biāo)塊與匹配塊的像素值的方差來(lái)確定最優(yōu)解，這種方法的弊端就是沒(méi)有考慮圖像的內(nèi)部結(jié)構(gòu)信息，可以將等照度線的曲率考慮進(jìn)來(lái)，增加最佳匹配塊選取的準(zhǔn)確性。因此，在原算法的基礎(chǔ)上，改進(jìn)相似性度量函數(shù):

式中，Kp對(duì)應(yīng)塊p中通過(guò)已知像素點(diǎn)的等照度線的曲率，同樣的Kq對(duì)應(yīng)q塊中通過(guò)已知像素點(diǎn)的等照度線的曲率，重新定義相似度函數(shù)以后，考慮到了圖像的內(nèi)部結(jié)構(gòu)信息，可以提高算法選取最佳匹配塊時(shí)的準(zhǔn)確性。

2.3 改進(jìn)以后的算法流程

改進(jìn)以后的算法流程如下:

步驟1把待修復(fù)圖像的受損部分提取出來(lái)，并且將其涂成指定的顏色，本文選取的黑色；

步驟2初始化待修復(fù)塊的邊界，并且記作?Ω；

步驟3將以輪廓點(diǎn)為中心的待修復(fù)塊的優(yōu)先權(quán)計(jì)算出來(lái)，通過(guò)比較，選出優(yōu)先權(quán)最高的待修復(fù)塊；

步驟4在已知區(qū)域內(nèi)搜索上述待修復(fù)塊的最佳匹配塊，然后將最佳匹配塊中的像素信息復(fù)制到待修復(fù)塊相應(yīng)的地方；

步驟5更新置信度，然后尋找下一個(gè)具有最高優(yōu)先權(quán)的待修復(fù)塊；

步驟6重復(fù)上述過(guò)程中的步驟3～步驟5，直至受損區(qū)域被完全修復(fù)，即?Ω=φ。

3 實(shí)驗(yàn)

峰值信噪比［9］是廣泛應(yīng)用于評(píng)價(jià)圖像修復(fù)質(zhì)量的客觀標(biāo)準(zhǔn)，它代表原圖像和處理圖像之間的均方誤差相對(duì)于（2n-1）2的對(duì)數(shù)值，其中n表示每個(gè)采樣值的比特?cái)?shù)。為了能夠評(píng)價(jià)修復(fù)圖像的效果，通常會(huì)參考PSNR值來(lái)衡量算法的修復(fù)性能。PSNR的單位是dB，PSNR值越大的話代表圖像失真程度越小，即算法修復(fù)性能越好。峰值信噪比的計(jì)算公式如下:

本文將PSNR值作為評(píng)價(jià)圖像修復(fù)效果的客觀標(biāo)準(zhǔn)。

首先針對(duì)有小面積破損的圖像進(jìn)行修復(fù)，圖2 （a）是原圖，由于本圖的圖像比較平滑，紋理相對(duì)簡(jiǎn)單，因此，取=0.8，==0.1；圖2（b）是被黑色線條破壞的圖像；圖2（c）是原算法修復(fù)后的圖像；圖2 （d）是本文改進(jìn)后算法的修復(fù)圖。

圖2 修復(fù)紅葉對(duì)比

由圖2可以看出，從修復(fù)的視覺(jué)效果上來(lái)說(shuō)，原算法修復(fù)后的黑色橫線條那里還可以稍微看出一些痕跡，而本文改進(jìn)后的算法幾乎不存在這樣的問(wèn)題，因此，修復(fù)效果更好一些。

接下來(lái)再通過(guò)修復(fù)大面積破損的圖像和移除圖像中的某些物體來(lái)看一下改進(jìn)算法的修復(fù)效果。

圖3 修復(fù)實(shí)驗(yàn)對(duì)比

圖4（a）是一個(gè)男孩蹦極的圖片，本實(shí)驗(yàn)打算將男孩和蹦極繩從圖片中移除出去，由于圖的結(jié)構(gòu)信息復(fù)雜，因此，取=0.1，==0.45；圖4（b）是標(biāo)注了待去除區(qū)域的圖片，即把男孩和蹦極繩標(biāo)記成白色；圖4（c）是原算法修復(fù)出來(lái)的圖像；圖4（d）是改進(jìn)后算法修復(fù)的圖像。從c圖中可以看出，原算法在修復(fù)屋頂時(shí)有一小部分沒(méi)有修復(fù)成功，在樹(shù)與水的交界處，原本是水的地方也修復(fù)成了樹(shù)的樣子，但本文改進(jìn)的算法則較好地還原了屋頂和水面，因此，改進(jìn)后算法的修復(fù)效果比原算法更好。

圖4 移除實(shí)驗(yàn)對(duì)比

為了能夠通過(guò)數(shù)據(jù)更加客觀地對(duì)比改進(jìn)前后算法的修復(fù)效果，給出圖2和圖3的算法改進(jìn)前后的峰值信噪比（PSNR）對(duì)比表，如表1所示，由于圖4是去除實(shí)驗(yàn)，因此，修復(fù)圖與原圖的相似程度（即PSNR值）對(duì)修復(fù)結(jié)果沒(méi)有什么參考意義，故不給出。

表1 算法改進(jìn)前后的PSNR值對(duì)比

由上表可以看出，對(duì)于圖2和圖3，改進(jìn)后算法的PSNR值較原算法有所提高，表明圖像的修復(fù)效果更好。

因此，無(wú)論是從視覺(jué)效果上來(lái)看，還是從PSNR值來(lái)說(shuō)，改進(jìn)后的算法比原算法修復(fù)結(jié)果更加準(zhǔn)確。

5 結(jié)論

本文針對(duì)Criminisi算法的不足進(jìn)行了改進(jìn):首先，在優(yōu)先權(quán)的選取上加入了等照度線的曲率以及塊與塊之間的方差值，并根據(jù)圖像的不同分別賦予不同的權(quán)值，使得待修復(fù)塊的優(yōu)先權(quán)計(jì)算更加準(zhǔn)確，保證修復(fù)任務(wù)準(zhǔn)確有序地進(jìn)行；其次，在相似性度量函數(shù)的計(jì)算上進(jìn)行了改進(jìn)，加入了反映圖像局部特征的等照度線的曲率，使得選取最佳匹配塊時(shí)能夠考慮到圖像的內(nèi)部結(jié)構(gòu)變化；最后，通過(guò)對(duì)不同類型的圖像進(jìn)行修復(fù)，仿真實(shí)驗(yàn)結(jié)果表明，改進(jìn)后算法的PSNR值比原算法大，修復(fù)結(jié)果也更符合人們視覺(jué)的主觀感受，因此，修復(fù)效果更加準(zhǔn)確可靠。

［1］BERTALMIO M，SAPIRO G，CASELLES V，et al.Image inpainting［C］//Proceedings of ACM SIGGRAPH，New York: ACM Press，2000:417-424.

［2］CHAN T F，SHEN J H.Mathematical models for local nontextureinpainting［J］.SIAM J APPl Math，2002，62:1019-1043.

［3］CHAN T F，SHEN J H.Non-texture inpainting by Curvature Driven Diffusions（CDD）［J］.Journal of Visual Communication and Image Representation，2001，12（4）:436-449.

［4］LI K S，WEI Y S，YANG Z，et al.Image inpainting algorithm based on TV model and evolutionary algorithm［J］.Methodologies and application，2016，20:885-893.

［5］IDDO D，DANIEL C，HEZY Y.Fragment based image completion［J］.ACM Transactions on Graphics，2003，22（3）: 303-312.

［6］CRIMINISI A，PEREZ P，TOYAMA K.Region filling and object removal by exemplar-based image inpainting［J］. IEEE Transactions on Image Processing，2004，13（9）: 1200-1212.

［7］吳亞?wèn)|，張紅英，吳斌.數(shù)字圖像修復(fù)技術(shù)［M］.北京:科學(xué)出版社，2010.

［8］祝軒，周明全.曲率驅(qū)動(dòng)與邊緣停止相結(jié)合的非線性擴(kuò)散及其在圖像去噪中的應(yīng)用［J］.光子學(xué)報(bào)，2008，37（3）: 609-612.

［9］SHIH T K，CHANG R C，LU LC，et al.Adaptive digital image inpainting［C］//Proceedings of the 18th International Conference on Advanced Information Networking and Application.Fukuoka，Japan:IEEE Press，2004:71-76.

Image Restoration Algorithm Based on Sample Block

WANG Yi-bo，BAI Yan-ping
（School of Science，North University of China，Taiyuan 030051，China）

Image inpainting refers to filling the damaged areas of the image or removing the redundant objects from the image.Conduct some improvements on the basis of Criminisi algorithm.As the curvature of equal illumination can reflect the internal characteristics of the image，variance value between the block and block can reflect the image edge information，adding them to the calculation of the priority of the repair block to ensure the inpainting can conduct accurately and orderly.When searching for the best matching block，the curvature of the equal illumination is added as a factor.The accuracy of searching for the best matching block is effectively improved.After the simulation experiment，the improved algorithm not only prove the PSNR value than the original algorithm，but also the obtained results are more accurate and reliable than the original algorithm.

image inpainting，priority，curvature of equal illumination，the best matching block

TP181

A

1002-0640（2017）03-0055-04

2016-02-09

2016-03-08

國(guó)家自然科學(xué)基金資助項(xiàng)目（61275120）

王一卜（1991- ），男，山西運(yùn)城人，碩士研究生。研究方向：數(shù)字圖像處理、神經(jīng)網(wǎng)絡(luò)算法及其應(yīng)用。