徐 國 天

(中國刑事警察學(xué)院 網(wǎng)絡(luò)犯罪偵查系， 沈陽 110854)E-mail ：xu_guo_tian888@163.com

1 引 言

與其它常見圖像格式相比，PNG是一種無損壓縮格式，能保證在不失真的情況下盡可能壓縮圖像文件大小，因此被廣泛應(yīng)用在各個(gè)領(lǐng)域，智能手機(jī)、個(gè)人計(jì)算機(jī)、云服務(wù)器內(nèi)通常存儲(chǔ)了大量PNG格式圖像.病毒破壞、人為操作或文件系統(tǒng)故障等諸多因素會(huì)造成PNG圖像文件電子數(shù)據(jù)局部受損，由于PNG圖像采用LZ77滑動(dòng)窗口和deflate編碼算法壓縮存儲(chǔ)，圖像數(shù)據(jù)之間存在緊密關(guān)聯(lián)，即使極少量數(shù)據(jù)破損，也會(huì)導(dǎo)致大面積解碼錯(cuò)誤，造成圖像內(nèi)容無法正常查看.因此，對局部受損圖像進(jìn)行修復(fù)，最大限度地還原圖像原始內(nèi)容有重要意義.

文獻(xiàn)[1]提出一種基于上下文語義分析的文件碎片識(shí)別重組方法，適合對文本文件進(jìn)行碎片重組[1].文獻(xiàn)[2]提出一種根據(jù)deflate編碼特征識(shí)別并修復(fù)受損壓縮文件的方法，適合對靜態(tài)編碼的壓縮數(shù)據(jù)進(jìn)行識(shí)別修復(fù)[2].文獻(xiàn)[3]通過計(jì)算文件碎片信息熵來確定文件碎片類型，可有效識(shí)別低熵值文件，但不能高效區(qū)分高熵值文件，例如JPEG和ZIP文件[3].文獻(xiàn)[4]針對高熵值文件分類精度較低問題，提出一種基于融合NIST隨機(jī)性檢測方法，采用SVM對缺少文件頭的碎片進(jìn)行分類，提高了高熵值文件分類精度[4].文獻(xiàn)[5]提出一種基于分層模型的文件碎片類型識(shí)別方法，通過分層聚類方式進(jìn)一步提升文件碎片類型識(shí)別精度[5].文獻(xiàn)[6]提出一種基于完全圖理論的JPEG圖像文件碎片加權(quán)重組算法，增強(qiáng)了圖像碎片重組效率，同時(shí)對受損JPEG圖像寬度進(jìn)行了準(zhǔn)確估算[6].目前現(xiàn)有研究主要集中在JPEG格式圖像碎片識(shí)別和修復(fù)領(lǐng)域，取得了較為豐碩的研究成果，而針對PNG格式圖像碎片識(shí)別、修復(fù)領(lǐng)域研究相對較少.

本文提出一種PNG圖像受損區(qū)域自動(dòng)修復(fù)方法.首先，在受損圖像數(shù)據(jù)區(qū)通過Huffman編碼特征識(shí)別全部圖像碎片，采用過濾類型為0或1的水平行像素將每塊圖像碎片分割為若干個(gè)顯示區(qū)域，從下至上逐個(gè)修復(fù)每塊區(qū)域.修復(fù)過程中通過計(jì)算像素點(diǎn)之間的加權(quán)空間歐氏距離來區(qū)分色彩差異性，采用滑動(dòng)位圖塊判斷圖像修復(fù)是否成功.

2 問題分析

PNG圖像由一系列Huffman編碼數(shù)據(jù)塊構(gòu)成[7]，圖像受損是指部分?jǐn)?shù)據(jù)塊內(nèi)容遭到破壞，例如圖1中的數(shù)據(jù)塊3.由于部分?jǐn)?shù)據(jù)塊受損，造成整幅圖像被分割為若干個(gè)碎片，對圖像進(jìn)行修復(fù)之前，需要先確定每塊圖像碎片的起始和結(jié)束位置.本文采用的方法是利用Huffman編碼特征識(shí)別符合嚴(yán)格匹配條件的數(shù)據(jù)塊，從嚴(yán)格匹配塊出發(fā)，向前向后關(guān)聯(lián)搜索其它數(shù)據(jù)塊，再利用數(shù)據(jù)塊首尾相連的特征將多個(gè)數(shù)據(jù)塊拼接為整塊圖像碎片.如圖1所示，這幅PNG圖像共包括7個(gè)數(shù)據(jù)塊，因塊3被覆蓋，導(dǎo)致圖像被分割為2個(gè)碎片，其中碎片1包含前兩個(gè)數(shù)據(jù)塊，碎片2包含4-7數(shù)據(jù)塊.

圖1 一種PNG圖像受損區(qū)域自動(dòng)修復(fù)方法

由于PNG原始圖像數(shù)據(jù)經(jīng)過LZ77滑動(dòng)窗口算法壓縮處理[8]，數(shù)據(jù)塊之間存在向前引用關(guān)系，例如數(shù)據(jù)塊3中的部分?jǐn)?shù)據(jù)為后續(xù)數(shù)據(jù)塊引用，緊隨其后的數(shù)據(jù)塊4引用量最大，此后引用量逐漸衰減，直至數(shù)據(jù)塊7，引用量降至為零.由PNG圖像的過濾方式可知，即使一個(gè)像素值出現(xiàn)解碼錯(cuò)誤，也會(huì)產(chǎn)生扇面輻射影響，造成大面積解碼錯(cuò)誤.如圖1所示，由于數(shù)據(jù)塊3的全部數(shù)據(jù)均被覆蓋，因此引用數(shù)據(jù)塊3相關(guān)數(shù)據(jù)的后續(xù)3個(gè)數(shù)據(jù)塊，即4-6塊均存在未知向前引用值，導(dǎo)致無法正常解碼顯示.

過濾類型為0或1的行像素解碼值與上一行像素解碼值無關(guān)，而過濾類型為2、3、4的行像素解碼值，與上一行像素的解碼值有直接關(guān)系.因此過濾類型為0或1的行像素相當(dāng)于一條水平分割線，全部水平分割線將整幅圖像分割為若干個(gè)相對獨(dú)立的顯示區(qū)域.兩條分割線之間的像素值如不存在解碼錯(cuò)誤，這組分割線之間的圖像就可以正常顯示.如圖1所示，分割線1以下的圖像和分割線5與6之間的圖像可以正常顯示；分割線4和5之間的圖像因數(shù)據(jù)塊3被完全覆蓋，缺失內(nèi)容過多，導(dǎo)致這部分圖像不可修復(fù)；分割線1和4之間共三塊顯示區(qū)域，這三塊區(qū)域內(nèi)均存在未知向前引用值，導(dǎo)致解碼異常，圖像無法正常顯示，這部分受損區(qū)域可以進(jìn)行修復(fù).

本文提出修復(fù)方法的基本思想是利用水平分割線將圖像碎片分割為若干區(qū)域，從下至上逐個(gè)進(jìn)行修復(fù).為每塊待修復(fù)區(qū)域中的未知引用值賦予一組探測值，利用這組探測值將待修復(fù)區(qū)域圖像數(shù)據(jù)解碼，還原為原始數(shù)值，再判斷這塊圖像中是否存在解碼異常區(qū)域，如不存在，說明探測值正確，否則繼續(xù)探測下一組數(shù)值，直至全部探測值測試完成，或發(fā)現(xiàn)正確探測值時(shí)結(jié)束當(dāng)前區(qū)域修復(fù).經(jīng)過大量實(shí)驗(yàn)，發(fā)現(xiàn)數(shù)據(jù)塊內(nèi)向前引用的數(shù)值通常位于[0，3]區(qū)間內(nèi)，這一狹小的取值區(qū)間保證未知引用值的探測空間較小，可以在有限步驟內(nèi)完成探測.例如待修復(fù)區(qū)域內(nèi)共有5個(gè)未知引用值，則需探測45個(gè)解碼值.由于塊間引用的最高概率數(shù)值為0，且塊間存在大量重復(fù)引用情況，隨著修復(fù)的進(jìn)行，各個(gè)待修復(fù)區(qū)域內(nèi)的未知值會(huì)逐步減少，實(shí)際探測速度會(huì)進(jìn)一步提高.例如圖1所示，分割線1和2之間圖像為第一組探測區(qū)域，有一個(gè)未知值，這一數(shù)值探測出來后，分割線3和2之間的未知值由4個(gè)降為3個(gè).

3 PNG圖像碎片識(shí)別方法

PNG圖像被刪除之后，數(shù)據(jù)區(qū)域極易遭到局部覆蓋，外來數(shù)據(jù)將一幅PNG圖像分割為若干個(gè)碎片，數(shù)據(jù)的缺失和外來數(shù)據(jù)的干擾造成圖像無法正常顯示.對圖像進(jìn)行修復(fù)，首先需要確定每個(gè)碎片的起始和結(jié)束位置.碎片由若干個(gè)Huffman編碼數(shù)據(jù)塊構(gòu)成，本文根據(jù)Huffman編碼特征[9]，提出一種Huffman編碼數(shù)據(jù)塊嚴(yán)格識(shí)別方法，可以識(shí)別出符合嚴(yán)格匹配條件的Huffman編碼數(shù)據(jù)塊，再根據(jù)這類數(shù)據(jù)塊向前、向后搜索，關(guān)聯(lián)識(shí)別其它相關(guān)數(shù)據(jù)塊，利用數(shù)據(jù)塊首尾相連的特征，確定每個(gè)碎片的起始和結(jié)束位置.

3.1 Huffman編碼數(shù)據(jù)塊嚴(yán)格識(shí)別方法

為了最大限度地節(jié)省碼樹存儲(chǔ)空間，PNG壓縮算法采用了一種最特殊的Huffman編碼樹，即deflate碼樹[10].Deflate碼樹結(jié)構(gòu)如圖2(c)所示，這類碼樹的特征是越靠近左邊越淺，越靠近右邊越深.Huffman編碼按照字符出現(xiàn)的次數(shù)進(jìn)行編碼，出現(xiàn)次數(shù)越多的字符，編碼長度越短，反之編碼長度越長，這一思想可以保證最終得到的編碼字符串總長度最短.Deflate碼樹中每個(gè)葉子結(jié)點(diǎn)對應(yīng)一個(gè)待編碼字符，出現(xiàn)次數(shù)多的字符，位于碼樹深度較淺的位置，出現(xiàn)次數(shù)少的字符位于碼樹較深的位置[11].由于結(jié)束字符endchar僅出現(xiàn)一次，因此其一定位于碼樹最深處.如圖2(c)所示，結(jié)束字符最常見的編碼形式為……1111110或……1111111，連續(xù)1的總個(gè)數(shù)不能確定，如圖片較大，待編碼字符較多，則deflate樹較深，連續(xù)1的個(gè)數(shù)較多，反之較少，通常連續(xù)1的總個(gè)數(shù)在10個(gè)以上[12].結(jié)束字符也存在其它編碼形態(tài)，如……1111100、……1111010，等等，但經(jīng)過實(shí)際測試發(fā)現(xiàn)，其他形態(tài)的結(jié)束字符編碼出現(xiàn)次數(shù)遠(yuǎn)少于前兩種編碼形態(tài).基于這一前提，本文提出一種Huffman編碼數(shù)據(jù)塊嚴(yán)格識(shí)別方法，描述如下：

首先在PNG圖像數(shù)據(jù)空間搜索二進(jìn)制模式字符串……111111*-001-*****-10111-1*11，其中……111111*為前一個(gè)壓縮塊結(jié)束字符編碼，001為當(dāng)前壓縮塊起始編碼，10111為最常見的HDIST長度值，1*11為HCLEN長度值.利用這一模式字符串定位一個(gè)壓縮塊之后，接下來需要進(jìn)行三個(gè)特征判斷.第一個(gè)特征是判斷CCL、CL1和CL2字段值能否組成三棵deflate碼樹，碼樹判斷公式如下：

Li+Bi<2i-1

(1)

其中Li是碼樹第i層葉子結(jié)點(diǎn)總個(gè)數(shù)，Bi是碼樹第i層分枝結(jié)點(diǎn)總個(gè)數(shù)，i為碼樹深度，初值為1.如圖2(a)所示，給定數(shù)值為(0 0 3 3 4 4)表示深度為3的葉子結(jié)點(diǎn)有2個(gè)，深度為4的葉子結(jié)點(diǎn)也是2個(gè)，這組數(shù)值符合碼樹判定條件.圖2(b)給定的數(shù)值表示深度為3的葉子結(jié)點(diǎn)有4個(gè)，深度為4的葉子結(jié)點(diǎn)有2個(gè)，這組數(shù)值違反公式(1)的判定條件，因此這組數(shù)據(jù)無法構(gòu)成一棵deflate編碼樹.

圖2 嚴(yán)格的Huffman編碼數(shù)據(jù)塊識(shí)別方法

第二個(gè)特征是判斷解碼后的數(shù)據(jù)塊長度是否為16KB或32KB字節(jié)，如長度不為上述數(shù)值，則判定識(shí)別錯(cuò)誤.第三個(gè)特征是判斷解碼結(jié)束位置是否出現(xiàn)結(jié)束字符，且其后是否出現(xiàn)新壓縮塊起始標(biāo)志.按照上述嚴(yán)格匹配方法可以準(zhǔn)確識(shí)別出符合判定條件的Huffman編碼數(shù)據(jù)塊，但是碎片中仍有很多數(shù)據(jù)塊并未識(shí)別，例如結(jié)束字符編碼不為……111111*模式的數(shù)據(jù)塊，或HDIST長度值不為10111的數(shù)據(jù)塊，等等.上述未識(shí)別數(shù)據(jù)塊需要通過關(guān)聯(lián)搜索方法進(jìn)一步識(shí)別.

3.2 Huffman編碼數(shù)據(jù)塊關(guān)聯(lián)識(shí)別方法

Huffman編碼數(shù)據(jù)塊關(guān)聯(lián)識(shí)別算法1主要功能是從嚴(yán)格識(shí)別數(shù)據(jù)塊出發(fā)，向前和向后搜索識(shí)別其它Huffman編碼數(shù)據(jù)塊.算法1流程如下：

輸入?yún)?shù)：全部嚴(yán)格識(shí)別數(shù)據(jù)塊的起始和結(jié)束位置.

輸出參數(shù)：全部碎片的起始和結(jié)束位置.

Step1.嚴(yán)格識(shí)別數(shù)據(jù)塊集合S={S1,S2,…，Sn}，其中n為嚴(yán)格識(shí)別數(shù)據(jù)塊總個(gè)數(shù)，集合S中的全部數(shù)據(jù)塊標(biāo)記為未處理狀態(tài)，設(shè)置整數(shù)變量j初值為1.

Step2.從集合S提取一個(gè)未處理數(shù)據(jù)塊Si.

Step3.設(shè)置關(guān)聯(lián)識(shí)別數(shù)據(jù)塊集合Uj={Si}，從Si出發(fā)，向前、向后搜索識(shí)別m個(gè)數(shù)據(jù)塊，將新識(shí)別數(shù)據(jù)塊加入U(xiǎn)j集合，更新后集合Uj={Ei1,Ei2，…，Si,…,Eim}，其中Eip為第p個(gè)新識(shí)別數(shù)據(jù)塊，Uj集合即為新識(shí)別的第j個(gè)數(shù)據(jù)碎片，將集合Uj中的全部數(shù)據(jù)塊標(biāo)記為已處理狀態(tài).

Step4.令j=j+1，如集合S中存在尚未處理數(shù)據(jù)塊，跳轉(zhuǎn)到Step 2，否則算法結(jié)束.

4 PNG圖像碎片修復(fù)方法

由于PNG圖像中只有第一個(gè)Huffman編碼數(shù)據(jù)塊不存在向前引用數(shù)據(jù)，圖像被局部覆蓋后，每塊碎片中均存在未知向前引用數(shù)值，這些未知值會(huì)造成圖像解碼失敗.圖像修復(fù)的基本思路是為這些未知引用數(shù)據(jù)提供一組測試值，再判斷圖像能否正常解碼顯示，如解碼錯(cuò)誤，則嘗試下一組探測值，直至解碼成功.圖像修復(fù)算法成功實(shí)施的前提條件是能夠自動(dòng)識(shí)別像素顏色相似度，能夠自動(dòng)判定圖像解碼是否成功.

4.1 像素點(diǎn)顏色相似度判斷

PNG圖像中每個(gè)像素點(diǎn)包括RGB(red、green、blue)三個(gè)顏色分量，通常每個(gè)顏色分量占1個(gè)字節(jié)，取值范圍是[0，255].將像素點(diǎn)放置到由RGB三種顏色分量組成的三維空間內(nèi)，通過計(jì)算像素點(diǎn)之間的加權(quán)空間歐氏距離可以判別出兩個(gè)像素點(diǎn)顏色是否相近[13].經(jīng)過實(shí)際檢測得到一組加權(quán)空間歐氏距離公式如下：

ED=

(2)

在上面加權(quán)空間歐氏距離公式中兩個(gè)像素點(diǎn)的顏色分量分別是(r1，g1，b1)和(r2，g2，b2)，經(jīng)過實(shí)際測量發(fā)現(xiàn)，如像素點(diǎn)之間的加權(quán)歐氏距離大于100，則兩個(gè)像素點(diǎn)視覺顏色區(qū)別明顯，如加權(quán)歐氏距離小于40，則兩個(gè)像素點(diǎn)視覺顏色相近.圖3(a)顯示的是從一幅PNG圖像內(nèi)提取的一個(gè)7*7位圖塊，其中第1行第4列像素點(diǎn)顏色1與第4行第4列像素點(diǎn)顏色2的加權(quán)空間歐氏距離為39.289722，這兩個(gè)像素點(diǎn)視覺顏色相近，第1行第4列像素點(diǎn)顏色1與第5行第2列像素點(diǎn)顏色4的加權(quán)空間歐氏距離為430.736578，這兩個(gè)像素點(diǎn)的視覺色彩差異明顯.

4.2 異常解碼位圖塊識(shí)別

圖3(a)顯示的是從一幅正常解碼圖像中提取出的一個(gè)7*7位圖塊，圖3(b)是這個(gè)位圖塊全部像素點(diǎn)在RGB三維顏色空間內(nèi)的分布情況，可見全部49個(gè)像素點(diǎn)散落在三維空間內(nèi)，沒有出現(xiàn)明顯的聚集現(xiàn)象.通過大量實(shí)驗(yàn)測試，發(fā)現(xiàn)在異常解碼圖像中通常存在圖4所示兩類位圖塊.第一類是圖4(a)顯示的中心高亮點(diǎn)位圖塊，這類位圖塊中心點(diǎn)(即第4行第4列的像素點(diǎn))與位圖塊中其它像素點(diǎn)顏色差異明顯，其它像素點(diǎn)視覺顏色相近，正常解碼圖像中不會(huì)出現(xiàn)此類位圖塊.圖4(b)是這個(gè)中心高亮點(diǎn)位圖塊全部像素點(diǎn)在RGB三維空間分布情況，可見全部像素點(diǎn)聚類分成四組，中心高亮點(diǎn)與其它三組像素點(diǎn)空間歐氏距離在300以上，其它三組像素點(diǎn)之間的歐氏距離較近，在60以內(nèi)，通過聚類分析計(jì)算像素點(diǎn)之間歐氏距離可以識(shí)別此類異常解碼位圖塊.

圖3 正常解碼位圖塊

第二類異常解碼位圖塊由大于5組視覺色彩差異明顯的像素點(diǎn)組成，每組像素點(diǎn)內(nèi)部視覺顏色相近，組間視覺顏色差異明顯，正常圖像不會(huì)出現(xiàn)此類位圖塊.圖4(c)是一個(gè)這種類型的異常解碼位圖塊，圖4(d)是這個(gè)位圖塊全部像素點(diǎn)在RGB三維顏色空間內(nèi)的分布情況，可見全部像素點(diǎn)聚類分為7組，每組像素點(diǎn)之間的空間歐氏距離均在300以上，組內(nèi)像素點(diǎn)之間的歐氏距離在40以內(nèi).當(dāng)一幅解碼圖像中出現(xiàn)圖4(a)或圖4(c)兩類位圖塊時(shí)，說明當(dāng)前圖像存在解碼異常.異常位圖塊可以通過基于空間歐氏距離聚類的異常解碼位圖塊識(shí)別算法2發(fā)現(xiàn)，下面對該算法進(jìn)行描述.

異常解碼位圖塊識(shí)別算法2的主要功能是判斷一個(gè)寬度為n像素，高度為n像素的位圖塊是否存在解碼錯(cuò)誤，算法2流程如下：

輸入?yún)?shù)：一個(gè)n×n圖像位圖塊，共包括n2個(gè)像素點(diǎn)，每個(gè)像素點(diǎn)包括RGB三種顏色分量.

輸出參數(shù)：輸出0表示當(dāng)前位圖塊為異常解碼塊，輸出1表示當(dāng)前位圖塊為正常解碼塊.

Step1.令集合S表示全部n2個(gè)像素點(diǎn)，即S={S1,S2，…，Sn2}，其中Si為第i個(gè)像素點(diǎn).

Step2.從集合S隨機(jī)選取一個(gè)像素點(diǎn)Si，計(jì)算Si與集合S中全部像素點(diǎn)的加權(quán)空間歐氏距離，并對計(jì)算結(jié)果按照升序排列.排序后的全部歐氏距離值組成集合D，即D={Din1,Din2,…,Dinm}，其中Dink表示像素點(diǎn)Si與Snk之間的加權(quán)空間歐氏距離值.

Step3.尋找集合D中元素值的突變點(diǎn)，即尋找首個(gè)滿足Dink-Dink-1≥ 100條件的位置，如果沒有符合條件的突變位置，則判定當(dāng)前位圖塊為正常解碼塊，算法結(jié)束，否則執(zhí)行Step 4.

Step4.令集合S′={Si,Sn1,Sn2，…，Snk-1}，判斷集合S′中任意兩個(gè)像素點(diǎn)之間的加權(quán)空間歐氏距離是否小于等于60，如集合S′中全部像素點(diǎn)符合判定條件，則令S=S-S′，執(zhí)行Step 5.

Step5.如集合S不為空，則執(zhí)行Step 2，否則判定這是一個(gè)異常解碼位圖塊，算法結(jié)束.

4.3 異常解碼圖像區(qū)域識(shí)別

如一幅PNG解碼圖像中存在圖4所示兩類異常解碼位圖塊，則認(rèn)定這幅圖像解碼錯(cuò)誤.本文提出一種基于滑動(dòng)窗口的異常解碼圖像識(shí)別方法，這一方法的基本思想是定義一個(gè)高度為n，寬度為n的滑動(dòng)窗口.如果n值設(shè)置過大，會(huì)使異常解碼判定速度減緩，n值設(shè)置過小，無法有效識(shí)別異常解碼圖像，經(jīng)過大量實(shí)際測試，將n值限定為7，即滑動(dòng)窗口寬度和高度均為7個(gè)像素.n的取值也可以根據(jù)圖像高度進(jìn)行動(dòng)態(tài)調(diào)整，例如圖像高度為6像素，則n可以設(shè)定為5.滑動(dòng)窗口的起始位置在PNG解碼圖像左上角，利用算法2判斷滑動(dòng)窗口所在區(qū)域位圖塊是否存在解碼異常，如未判定解碼異常，則窗口向右滑動(dòng)一列像素點(diǎn)，繼續(xù)判斷.如滑動(dòng)窗口移動(dòng)到圖像最右端，則將窗口重新移動(dòng)至圖像最左端，并向下移動(dòng)一行像素點(diǎn)繼續(xù)判斷.當(dāng)滑動(dòng)窗口識(shí)別出一個(gè)異常解碼位圖塊時(shí)，判定該幅PNG圖像解碼失敗；當(dāng)窗口移動(dòng)至圖像右下角位置，如仍未識(shí)別出異常解碼位圖塊，則判定該幅PNG圖像解碼正確.

圖4 異常解碼位圖塊

異常解碼圖像區(qū)域識(shí)別算法3的主要功能是判斷一幅PNG圖像是否存在解碼錯(cuò)誤，算法3流程如下：

輸入?yún)?shù)：PNG圖像的寬度為weight像素，高度為height像素，每像素字節(jié)個(gè)數(shù)為num.

輸出參數(shù)：輸出0表示當(dāng)前圖像解碼錯(cuò)誤，輸出1表示當(dāng)前圖像解碼正確.

Step1.令滑動(dòng)窗口寬度和高度均為n像素，其中n

Step2.利用算法2判斷滑動(dòng)窗口內(nèi)位圖塊是否存在解碼異常，如存在解碼異常，則判定當(dāng)前PNG圖像解碼錯(cuò)誤，算法結(jié)束，否則執(zhí)行Step 3.

Step3.如果(X+n)

Step4.如果(Y+n)

4.4 受損PNG圖像碎片修復(fù)

一幅被局部覆蓋的PNG圖像由多塊碎片組成，每塊碎片均存在未知向前引用數(shù)據(jù).碎片修復(fù)的基本思想是利用水平分割線將每塊碎片劃分為多組圖像區(qū)域，從下至上對每塊圖像區(qū)域逐個(gè)進(jìn)行修復(fù).修復(fù)方法是給定一組探測值，對圖像進(jìn)行逆向過濾還原，再利用算法3判斷還原后的圖像是否解碼成功，如解碼異常，則繼續(xù)探測下一組數(shù)值.這一探測過程持續(xù)循環(huán)執(zhí)行，直至當(dāng)前圖像區(qū)域解碼成功.

PNG圖像碎片修復(fù)算法4的主要功能是修復(fù)一幅局部受損的PNG圖像碎片，算法4流程如下：

輸入?yún)?shù)：圖像碎片的起始和結(jié)束位置，圖像的寬度和高度，以及每像素點(diǎn)的字節(jié)個(gè)數(shù).

輸出參數(shù)：輸出0表示當(dāng)前圖像修復(fù)失敗，輸出1表示當(dāng)前圖像修復(fù)成功.

Step1.集合S表示當(dāng)前待修復(fù)圖像碎片全部n個(gè)未知引用數(shù)值，即S={S1,S2，…，Sn}，其中Si為第i個(gè)未知引用數(shù)值，滿足0≤Si≤3條件.集合T表示全部已識(shí)別數(shù)值，初始狀態(tài)T={}.

Step2.當(dāng)前碎片被水平分割線劃分為m塊圖像區(qū)域，集合U表示每塊圖像區(qū)域中的未知引用數(shù)值集合，U={U1,U2，…，Um}，其中Ui為第i塊圖像區(qū)域未知引用數(shù)值集合，滿足Um∈Um-1∈Um-2...∈U2∈U1關(guān)系，其中U1=S.令整數(shù)變量j=m，k=1.

Step3.集合V表示第j個(gè)圖像塊待探測數(shù)值集合，V=Uj-T，即從集合Uj中去除已探測數(shù)值，V={Sn1,Sn2，…，Snt}，共t個(gè)待探測數(shù)值.集合V的全部可能探測值組成集合R，R={{0,0,…,0}，{0,0,…,1}，…,{3,3,…,3}}，集合R中共有4t個(gè)元素，集合R={R1,R2,…，Rq}，其中q=4t.

Step4.用Rk作為探測值對第j塊圖像進(jìn)行解碼，利用算法3判斷圖像解碼是否成功.如解碼成功，令T=Uj,j=j-1，執(zhí)行Step 5.如解碼異常，令k=k+1，執(zhí)行Step 6.

Step5.如果j≤0，則全部圖像區(qū)域修復(fù)完成，算法結(jié)束.否則，令k=1,執(zhí)行Step 3，繼續(xù)修復(fù)下一個(gè)圖像區(qū)域.

Step6.如果k>q，表示全部探測值測試完成，仍未探測到合法數(shù)值，解碼失敗，算法結(jié)束.否則執(zhí)行Step 4，繼續(xù)探測下一組數(shù)值.

5 實(shí)驗(yàn)測試分析

5.1 可行性分析

圖像碎片中絕大部分未知引用值位于[0，3]區(qū)間，這一結(jié)論保證PNG圖像碎片修復(fù)可以在有限步驟內(nèi)完成.針對這一結(jié)論，本文進(jìn)行了如下實(shí)驗(yàn)測試.選取120幅PNG圖像，圖像大小從2950KB到23127KB均勻分布，每幅圖像由大于200個(gè)數(shù)據(jù)塊構(gòu)成.對每幅圖像引用第一個(gè)數(shù)據(jù)塊值的情況進(jìn)行統(tǒng)計(jì)分析，將引用值分為兩類，一類位于[0，3]區(qū)間，一類位于[4，255]區(qū)間，實(shí)驗(yàn)分析結(jié)果如圖5(a)所示.圖中橫坐標(biāo)為圖片編號，縱坐標(biāo)為兩類引用值在全部引用值中所占百分比，可見絕大部分圖像[0，3]區(qū)間引用值占比在90%-100%，而[4，255]區(qū)間引用值占比在0%-10%，實(shí)驗(yàn)表明絕大部分引用值位于[0，3]區(qū)間.

圖5 實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)分析

第二組實(shí)驗(yàn)對每類引用值影響的數(shù)據(jù)塊個(gè)數(shù)進(jìn)行了統(tǒng)計(jì)分析，使用與上述實(shí)驗(yàn)相同的圖片集，實(shí)驗(yàn)結(jié)果如圖5(b)所示.圖中橫坐標(biāo)為圖片編號，縱坐標(biāo)為每類引用值平均影響的數(shù)據(jù)塊個(gè)數(shù)，結(jié)果顯示[0，3]區(qū)間引用值平均影響數(shù)據(jù)塊個(gè)數(shù)為10個(gè)-55個(gè)，[4，255]區(qū)間引用值平均影響數(shù)據(jù)塊個(gè)數(shù)為1個(gè)-3個(gè).實(shí)驗(yàn)結(jié)果表明[4，255]區(qū)間引用值只能影響碎片中最靠前的1個(gè)-3個(gè)數(shù)據(jù)塊，對后續(xù)大量數(shù)據(jù)塊沒有影響.這一實(shí)驗(yàn)結(jié)論進(jìn)一步表明將未知引用值探測空間設(shè)置為[0，3]區(qū)間的可行性.

5.2 定性分析

本文對大于100幅PNG圖像文件進(jìn)行了隨機(jī)覆蓋，對覆蓋后的圖像執(zhí)行碎片識(shí)別和修復(fù)測試，經(jīng)過修復(fù)，最大限度地還原了圖像數(shù)據(jù)，驗(yàn)證了本文提出方法的有效性和可行性.下面選擇lena.png圖像進(jìn)行修復(fù)比對測試，文件大小為353197字節(jié)，圖像寬度392像素，高度512像素，每像素占3字節(jié).圖像解壓之后，得到的原始圖像數(shù)據(jù)大小為(392×3+1)×512，即602624字節(jié).圖像共包括32個(gè)數(shù)據(jù)塊，每個(gè)數(shù)據(jù)塊平均存儲(chǔ)18832字節(jié)數(shù)據(jù)，即19行像素.使用winhex將lena.png圖像中第12個(gè)數(shù)據(jù)塊全部內(nèi)容和第13個(gè)數(shù)據(jù)塊部分內(nèi)容替換為0X00，模擬圖像遭到局部覆蓋，整個(gè)圖像文件被分割為兩個(gè)碎片，局部覆蓋之后的圖像如圖6(a)所示，被覆蓋區(qū)域顯示為黑色.由于引用了被覆蓋區(qū)域內(nèi)的部分?jǐn)?shù)據(jù)，導(dǎo)致后面的圖像解碼錯(cuò)誤，部分圖像顯示為亂碼.水平分割線以下的圖像未引用被覆蓋數(shù)據(jù)，因此可以正常顯示.應(yīng)用本文提出圖像碎片識(shí)別和修復(fù)方法從遭到覆蓋的lena.png圖像文件中識(shí)別出兩個(gè)碎片，對第二個(gè)碎片進(jìn)行修復(fù).修復(fù)結(jié)果如圖6(b)所示，兩條分割線之間的圖像數(shù)據(jù)修復(fù)后可以正常顯示，第13和第14個(gè)數(shù)據(jù)塊因未知引用值主要位于[4，255]區(qū)間，造成這兩個(gè)數(shù)據(jù)塊內(nèi)容不能正常修復(fù)，顯示為亂碼圖像.

圖6 修復(fù)前后圖像對比

5.3 定量分析

測試使用的lena.png圖像寬度392像素，高度512像素，每像素占3字節(jié)，共包括32個(gè)數(shù)據(jù)塊.以2個(gè)數(shù)據(jù)塊為單位，使用隨機(jī)字節(jié)對lena.png進(jìn)行覆蓋，模擬圖像數(shù)據(jù)受損，得到P1-P6共6幅受損圖像.以這6幅圖像作為測試對象，采用Criminisi算法和本文算法分別進(jìn)行修復(fù).選擇PSNR(Peak Signal to Noise Ratio)和SSIM(Structural SIMilarity)作為評價(jià)指標(biāo).PSNR峰值信噪比指標(biāo)通過比較圖像像素值差距來統(tǒng)計(jì)像素點(diǎn)誤差，進(jìn)而判斷修復(fù)效果.SSIM結(jié)構(gòu)相似性指標(biāo)從結(jié)構(gòu)、對比度和亮度三個(gè)方面衡量圖像相似度，這項(xiàng)指標(biāo)更多考慮了人眼的直觀視覺感受.以上兩個(gè)指標(biāo)也是目前衡量圖像修復(fù)效果的常用評價(jià)標(biāo)準(zhǔn).

表1顯示了Criminisi算法和本文算法在PSNR和SSIM指標(biāo)上的實(shí)驗(yàn)比較結(jié)果.如表1所示，在測試圖像集上，本文算法PSNR指標(biāo)優(yōu)于Criminisi算法，這表明本文算法在對圖像受損區(qū)域逐塊修復(fù)后，基本還原原始像素值，與Criminisi算法相比，可以更準(zhǔn)確地還原受損區(qū)域像素值，修復(fù)所得圖像紋理結(jié)構(gòu)更自然清晰.

表1 不同算法PSNR和SSIM值比較

如表1所示，本文算法在PSNR指標(biāo)對比上較優(yōu)秀，但是SSIM指標(biāo)比對上，僅P1、P4和P6圖像高于Criminisi算法.因?yàn)檫@三幅圖像內(nèi)受損數(shù)據(jù)塊影響范圍較大，應(yīng)用本文算法對受損區(qū)域修復(fù)效果較好，而另外三幅圖像受損數(shù)據(jù)塊影響范圍較小，Criminisi算法有更好的修復(fù)效果，圖像失真度更小.

6 結(jié) 語

本文提出一種PNG圖像受損區(qū)域自動(dòng)修復(fù)方法.首先，根據(jù)Huffman編碼特征識(shí)別符合嚴(yán)格匹配條件的數(shù)據(jù)塊，再根據(jù)這類數(shù)據(jù)塊向前、向后搜索，關(guān)聯(lián)識(shí)別其它相關(guān)數(shù)據(jù)塊，利用數(shù)據(jù)塊首尾相連的特征，確定每個(gè)碎片的起始和結(jié)束位置，再利用水平分割線將圖像碎片分割為若干個(gè)顯示區(qū)域，從下至上逐個(gè)修復(fù)每塊圖像區(qū)域，修復(fù)過程也是圖像區(qū)域內(nèi)未知引用值的探測過程.修復(fù)過程中應(yīng)用了滑動(dòng)位圖塊和空間歐氏距離聚類兩種方法識(shí)別解碼異常圖像.經(jīng)過大量實(shí)驗(yàn)測試，驗(yàn)證了本文提出方法的有效性和可行性.

本文將未知引用值的探測區(qū)域設(shè)置為[0，3]區(qū)間，當(dāng)未知數(shù)據(jù)較多時(shí)，探測消耗時(shí)間較大，接下來計(jì)劃研究根據(jù)未知引用值的衰減趨勢(即未知引用值影響的數(shù)據(jù)塊個(gè)數(shù))來快速判定未知引用值，進(jìn)一步提高修復(fù)速度.