徐 國 天

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

1 引 言

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

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

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

2 問題分析

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

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

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

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

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

3 PNG圖像碎片識別方法

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

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

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

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

Li+Bi<2i-1

(1)

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

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

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

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

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

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

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

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

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

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

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

4 PNG圖像碎片修復方法

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

4.1 像素點顏色相似度判斷

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

ED=

(2)

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

4.2 異常解碼位圖塊識別

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

圖3 正常解碼位圖塊

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

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

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

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

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

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

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

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

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

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

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

圖4 異常解碼位圖塊

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

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

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

Step1.令滑動窗口寬度和高度均為n像素，其中n

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

Step3.如果(X+n)

Step4.如果(Y+n)

4.4 受損PNG圖像碎片修復

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

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

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

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

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

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

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

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

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

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

5 實驗測試分析

5.1 可行性分析

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

圖5 實驗結(jié)果統(tǒng)計分析

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

5.2 定性分析

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

圖6 修復前后圖像對比

5.3 定量分析

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

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

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

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

6 結(jié) 語

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

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