一種基于數(shù)字簽名的二值圖像認(rèn)證算法

摘 要:為了實(shí)現(xiàn)對(duì)二值文本圖像內(nèi)容的全面保護(hù)，提出一種新的基于數(shù)字簽名的二值圖像認(rèn)證算法。算法用數(shù)字簽名實(shí)現(xiàn)對(duì)均勻塊的認(rèn)證，用歸一化預(yù)處理實(shí)現(xiàn)對(duì)非均勻塊的認(rèn)證，通過(guò)兩者聯(lián)合認(rèn)證來(lái)消除虛警。理論分析和實(shí)驗(yàn)結(jié)果表明，該算法僅需要附加極短的簽名信息，就可以實(shí)現(xiàn)對(duì)二值文本圖像內(nèi)容的全面保護(hù)，在保證良好視覺(jué)效果的前提下，具有良好的竄改檢測(cè)和竄改定位能力。

關(guān)鍵詞:二值圖像; 認(rèn)證; 數(shù)字簽名; 竄改定位

中圖分類號(hào):TP391文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1001-3695(2010)06-2348-04

doi:10.3969/j.issn.10013695.2010.06.101

Binary image authentication algorithm based on digital signature

DU Min， GAO Bao-jian， DONG Jian-e

(School of Information Science Technology， Northwest University， Xi’an 710127， China)

Abstract:This paper proposed a new binary image authentication algorithm based on digital signature for protecting binary image completely. It used the digital signature to certificate the uniform blocks and used the normalization pretreatment to certificate the nonuniform blocks. False alarms could be eliminated by joint certification. The experiments and the analysis show that the content of binary text images can be protected completely by appending very short digital signature to the original image. With fine visual effect， the algorithm has high performance in detecting and locating tampers.

Key words:binary image; certification; digital signature; tamper locating

0 引言

近年來(lái)，隨著網(wǎng)絡(luò)和信息技術(shù)的高速發(fā)展，人們?cè)诟憬莸孬@取數(shù)字作品信息的同時(shí)，也更容易受到竄改和偽造數(shù)字作品等行為的侵?jǐn)_。因此，如何更高效、更可靠地對(duì)數(shù)字作品的版權(quán)、內(nèi)容等進(jìn)行認(rèn)證保護(hù)已成為當(dāng)前的研究熱點(diǎn)。二值圖像作為一類特殊的數(shù)字作品，具有廣泛的實(shí)際應(yīng)用背景，如一些商業(yè)合同、票據(jù)、法庭資料和資格證書等重要文件經(jīng)常需要被掃描成圖片的形式用做憑證，并通過(guò)各種途徑來(lái)存儲(chǔ)或傳播。而利用當(dāng)前市面上流行的一些圖像處理軟件，則可以很容易地對(duì)這些電子圖片進(jìn)行有目的的竄改和偽造。這種未經(jīng)授權(quán)的偽造和竄改行為，將會(huì)帶來(lái)嚴(yán)重的后果，如偽造的商業(yè)合同終將引發(fā)法律糾紛，偽造的資格證書將使相關(guān)領(lǐng)域的社會(huì)評(píng)價(jià)顯失公平。因此，就有了對(duì)二值圖像進(jìn)行認(rèn)證保護(hù)的技術(shù)需求[1，2]。

早期的圖像認(rèn)證研究是從灰度圖像領(lǐng)域開始的，當(dāng)時(shí)主要的研究方法有基于數(shù)字簽名和基于數(shù)字水印的認(rèn)證兩類。但是灰度圖像具有較大的信息冗余度，嵌入大量水印信息后，圖像的視覺(jué)效果改變不明顯，因此，基于數(shù)字水印認(rèn)證算法取得了較好的實(shí)驗(yàn)結(jié)果，并且有逐步取代基于數(shù)字簽名的認(rèn)證算法的趨勢(shì)。目前，灰度圖像的認(rèn)證算法多是基于數(shù)字水印的。相對(duì)于灰度圖像認(rèn)證，二值圖像認(rèn)證的研究起步稍晚一些，因此，灰度圖像認(rèn)證領(lǐng)域的許多研究成果被借鑒到了二值圖像認(rèn)證領(lǐng)域中來(lái)，從公開發(fā)表的文獻(xiàn)來(lái)看，當(dāng)前二值圖像的認(rèn)證算法也多是基于數(shù)字水印的。但是，二值圖像與灰度圖像相比具有其特殊性，即二值圖像只包含兩種像素值，不是0就是1，信息冗余度小，所以，二值圖像嵌入水印后引起的視覺(jué)質(zhì)量的下降也比灰度圖像要明顯得多。采用基于數(shù)字水印的方法來(lái)認(rèn)證二值圖像，出于對(duì)嵌入水印后圖像視覺(jué)效果的考慮，水印的嵌入量就必然會(huì)有一個(gè)上限值，從而限制了算法的竄改檢測(cè)概率(一般只有50%左右)[3，4]。此外，在二值圖像的均勻區(qū)(全白或全黑區(qū)域)嵌入水印信息很容易被察覺(jué)，因此，現(xiàn)有的水印算法在二值圖像的均勻區(qū)是無(wú)法嵌入水印的，當(dāng)用全白的圖像塊代替原圖像塊時(shí)，水印認(rèn)證算法對(duì)竄改的檢測(cè)失效[3];李趙紅等人[5]提出一種基于等級(jí)結(jié)構(gòu)的二值文本圖像認(rèn)證水印算法，該算法采取了分級(jí)分層次的嵌入和提取水印的方法，可以解決二值圖像均勻區(qū)竄改認(rèn)證的問(wèn)題，但是該算法的實(shí)現(xiàn)復(fù)雜度高、實(shí)時(shí)性較差，不利于實(shí)用推廣。總體來(lái)看，當(dāng)前絕大多數(shù)基于水印的二值圖像認(rèn)證算法難以簡(jiǎn)單、有效地對(duì)二值圖像的均勻區(qū)進(jìn)行保護(hù)。

綜上所述，目前基于水印的二值圖像認(rèn)證算法普遍存在以下兩個(gè)問(wèn)題:a)竄改檢測(cè)概率低;b)難以簡(jiǎn)單、有效地實(shí)現(xiàn)對(duì)圖像均勻區(qū)的認(rèn)證保護(hù)。這是由二值圖像本身的結(jié)構(gòu)特點(diǎn)所決定的。鑒于當(dāng)前基于水印的方法無(wú)法很好地解決這兩個(gè)問(wèn)題，本文從圖像認(rèn)證的另一個(gè)研究方向出發(fā)，提出了一種基于數(shù)字簽名的二值圖像認(rèn)證算法，從而有效地回避了水印復(fù)雜的嵌入和提取過(guò)程，僅通過(guò)對(duì)圖像作簡(jiǎn)單的預(yù)處理，提取長(zhǎng)度很短的數(shù)字簽名就能達(dá)到較好的認(rèn)證效果。

1 圖像認(rèn)證算法原理和實(shí)現(xiàn)

1.1 算法結(jié)構(gòu)

圖1為對(duì)原始二值圖像I預(yù)處理和提取數(shù)字簽名的流程圖，圖2為對(duì)接收到圖像Ig進(jìn)行認(rèn)證的流程圖。

發(fā)送方先對(duì)圖像I分塊，同時(shí)把子塊大小作為密鑰K1，按子塊內(nèi)像素是否一致把圖像分為兩類，即均勻子塊和非均勻子塊。對(duì)非均勻子塊進(jìn)行預(yù)處理，使得每個(gè)非均勻子塊滿足歸一化特征，從而產(chǎn)生預(yù)處理后的圖像Ig;利用均勻子塊在整個(gè)圖像中的分布信息以及密鑰K2提取數(shù)字簽名S，把簽名S和Ig一并發(fā)送。接收方對(duì)收到的圖像Ig按密鑰K1再次分塊，并分成兩類子塊。先對(duì)非均勻子塊按是否滿足歸一化特征進(jìn)行非均勻認(rèn)證;再利用密鑰K2對(duì)均勻子塊二次提取數(shù)字簽名Sg，通過(guò)比較S和Sg，實(shí)現(xiàn)均勻區(qū)認(rèn)證;最后，由聯(lián)合認(rèn)證環(huán)節(jié)排除了均勻區(qū)認(rèn)證環(huán)節(jié)可能出現(xiàn)的虛警，最終確定出圖像被竄改的位置。

1.2 圖像非均勻塊的預(yù)處理 

為了實(shí)現(xiàn)對(duì)圖像非均勻區(qū)的保護(hù)，算法在對(duì)圖像分塊后，對(duì)圖像的非均勻區(qū)作了如下預(yù)處理:確定歸一化特征，判斷每個(gè)非均勻子塊是否滿足該特征;滿足歸一化特征的子塊不作任何改動(dòng);不滿足歸一化特征的子塊，翻轉(zhuǎn)部分像素點(diǎn)，使其具有歸一化特征。 

1.2.1 可翻轉(zhuǎn)像素位置的選擇

目前，評(píng)價(jià)二值圖像像素點(diǎn)翻轉(zhuǎn)對(duì)圖像視覺(jué)質(zhì)量的影響有三種評(píng)分方案，即Min Wu評(píng)分準(zhǔn)則[2]、基于LSPB(最不明顯像素塊) 的評(píng)分準(zhǔn)則[3]和基于PSD(像素?cái)U(kuò)展差)的評(píng)分準(zhǔn)則[5]。這三種評(píng)分方案均能有效地衡量像素的可翻轉(zhuǎn)性，但是，基于PSD的評(píng)分準(zhǔn)則在考慮像素周圍分布的擴(kuò)展性上明顯優(yōu)于前兩種評(píng)分方法，剛好滿足本算法中圖像分塊大小靈活的特點(diǎn)，因此，圖像非均勻區(qū)的預(yù)處理采用基于PSD的評(píng)分準(zhǔn)則來(lái)選取可翻轉(zhuǎn)點(diǎn)。按文獻(xiàn)[5]的描述，PSD求法如下:

首先考察一個(gè)以d為中心，大小為ω×ω的圖像塊B。其中ω要求為奇數(shù)，圖像塊B中所有像素點(diǎn)的值記為B(m，n)，(m，n)為像素點(diǎn)的坐標(biāo)(m=n=1，2，…，ω)。那么點(diǎn)d坐標(biāo)為(m0，n0)，m0=n0=(ω+1)/2。假設(shè)圖像塊B的均值為μ，那么像素點(diǎn)B(m，n)的偏差為δ(m，n)=|B(m，n)-μ|。于是，定義圖像塊B的像素?cái)U(kuò)展差 (pixel spread，PS)如下:

PS=∑ωm=1∑ωn=1δ(m，n)#8226;W(m，n)(1)

其中:W(m，n)=1 m=m0，n=n01(m-m0)2+(n-n0)2其他

如果圖像塊B的中心點(diǎn)d翻轉(zhuǎn)以后的像素?cái)U(kuò)展為PS′，那么點(diǎn)d的可翻轉(zhuǎn)性由其翻轉(zhuǎn)前后圖像塊的像素?cái)U(kuò)展差(pixel spread deviation，PSD)來(lái)衡量，表示如下:

PSD=|PS-PS′|(2)

利用式(2)計(jì)算出每個(gè)像素點(diǎn)的PSD值。選定合適的閾值τ，PSD≤τ的像素點(diǎn)定為可翻轉(zhuǎn)，PSD>τ的像素點(diǎn)定為不可翻轉(zhuǎn)。像素點(diǎn)的PSD值越小，說(shuō)明該點(diǎn)的可翻轉(zhuǎn)性越好。

1.2.2 歸一化特征的選取及性能分析

選取歸一化特征時(shí)應(yīng)考慮兩個(gè)指標(biāo):a)實(shí)現(xiàn)歸一化特征平均每個(gè)非均勻子塊需要翻動(dòng)像素點(diǎn)的數(shù)目(turned number， TN);b)未經(jīng)預(yù)處理就滿足歸一化特征的非均勻子塊個(gè)數(shù)占非均勻子塊總數(shù)的百分比(separation generation rate， SGR)。TN關(guān)系到預(yù)處理后圖像的視覺(jué)質(zhì)量，TN越小，預(yù)處理后圖像視覺(jué)效果越好。SGR關(guān)系到算法的認(rèn)證能力，SGR越小，任意一個(gè)非均勻子塊未經(jīng)預(yù)處理就滿足歸一化特征的概率就越小，算法的認(rèn)證能力就越強(qiáng)。由于SGR和TN存在間接反比關(guān)系，出于對(duì)預(yù)處理后圖像質(zhì)量和算法認(rèn)證能力雙重要求，需要在選擇歸一化特征時(shí)考慮在TN與SGR之間進(jìn)行折中。

本文算法規(guī)定每個(gè)子塊包含的像素點(diǎn)個(gè)數(shù)N為奇數(shù)，即N=N1+N0，N1為子塊內(nèi)1的個(gè)數(shù)，N0為子塊內(nèi)0的個(gè)數(shù)，在此前提下，對(duì)非均勻塊選取的歸一化特征:N1為奇數(shù)，N0/2」為偶數(shù)(其中:*」表示對(duì)*的下取整值)。

由于N=N1+N0，N1和N0的奇偶性是互不獨(dú)立的， 但是N1和N0/2」的奇偶性卻是互相獨(dú)立的，這樣，其奇偶性組合共有四種情況，分別為(奇數(shù)，偶數(shù))、(奇數(shù)，奇數(shù))、(偶數(shù)，奇數(shù))、(偶數(shù)，偶數(shù))。本文歸一化的做法就是通過(guò)跳轉(zhuǎn)塊內(nèi)像素點(diǎn)將后三種情況統(tǒng)一到第一種情況，由于在假設(shè)圖像的0、1分布為均勻分布的情況下，上述四種情況是等概率出現(xiàn)的，任選一個(gè)組合作為歸一化特征時(shí)，SGR均為25%，而歸一化后的非均勻塊如果被竄改，這種竄改能被正確檢測(cè)的概率為1-25%=75%。

同時(shí)，當(dāng)選第一種組合情況為歸一化特征時(shí)，任意一個(gè)非均勻子塊向歸一化特征跳變的可能情況如表1所示。

表1 任意非均勻子塊歸一化可能翻轉(zhuǎn)的像素個(gè)數(shù)

N1N0/2」出現(xiàn)概率需要翻轉(zhuǎn)像素點(diǎn)數(shù)N1N0/2」出現(xiàn)概率需要翻轉(zhuǎn)像素點(diǎn)數(shù)

奇數(shù)偶數(shù)0.250偶數(shù)奇數(shù)0.251

奇數(shù)奇數(shù)0.252偶數(shù)偶數(shù)0.251

由于子塊內(nèi) 0、1分布具有隨機(jī)性，出現(xiàn)上述任意一種情況的概率都是相等的，根據(jù)概率理論，任意一個(gè)非均勻子塊在向歸一化特征跳變時(shí)平均需要修改的像素點(diǎn)數(shù)為

TN=0.25×0+0.25×2+0.25×1+0.25×1=1(3)

由以上分析可得出結(jié)論:選取N1為奇數(shù)、N0/2」為偶數(shù)作為預(yù)處理的歸一化特征，平均每個(gè)非均勻子塊只需修改一個(gè)像素點(diǎn)就可以實(shí)現(xiàn)預(yù)處理，這樣不僅可以有效保證圖像視覺(jué)質(zhì)量，而且可以保證對(duì)非均勻塊75%的竄改檢測(cè)概率。

1.2.3 圖像非均勻區(qū)預(yù)處理

圖像非均勻區(qū)預(yù)處理的步驟如下:

a)計(jì)算原始圖像Im×n每個(gè)像素點(diǎn)的像素?cái)U(kuò)展差，則全圖的像素?cái)U(kuò)展差記為PSDm×n。

b)將圖像分成M×N個(gè)大小相等的子塊，各子塊標(biāo)號(hào)記為Kij(i=1，2，…，M;j=1，2，…，N)，每個(gè)子塊含有ω×ω個(gè)像素點(diǎn)，要求ω為奇數(shù)，并把ω作為密鑰K1。

c)檢測(cè)出所有圖像非均勻子塊(即各像素值不全相同的子塊)，統(tǒng)計(jì)每個(gè)非均勻子塊內(nèi)0、1 像素點(diǎn)的個(gè)數(shù)，記0 的個(gè)數(shù)為N0，1的個(gè)數(shù)為N1。若N0、N1滿足如下歸一化特征:N1為奇數(shù)，N0/2」為偶數(shù)，則該塊不作修改;如果不滿足，則根據(jù)該塊內(nèi)各像素的PSD值，翻動(dòng)PSD值最小的n個(gè)像素點(diǎn)(n≤2)，使得該子塊內(nèi)N0、N1滿足歸一化特征，從而產(chǎn)生預(yù)處理后的圖像Igm×n。

1.3 提取數(shù)字簽名

為了對(duì)圖像的均勻區(qū)進(jìn)行保護(hù)，算法先提取了圖像所有均勻塊的分布信息，然后通過(guò)混沌迭代運(yùn)算產(chǎn)生一列定長(zhǎng)的數(shù)字簽名。

1.3.1 Logistic混沌映射原理

Logistic映射是一類簡(jiǎn)單卻被廣泛研究的混沌動(dòng)力系統(tǒng)，可用如下非線性差分方程來(lái)描述:

xn+1=λxn(1-xn)(4)

其中:λ∈[0，4]，xn∈[0，1]。

研究發(fā)現(xiàn)，Logistic映射的混沌區(qū)域?yàn)棣恕蔥λ∞，4](λ∞=3.569 945 672…)。理論上已經(jīng)證明了由兩個(gè)不同初值x0和y0生成的兩個(gè)混沌序列的互相關(guān)函數(shù)為零，這體現(xiàn)了Logistic混沌映射對(duì)初值的極度敏感性。當(dāng)λ=4時(shí)，Logistic混沌序列的均值為0.5，所以可以通過(guò)門限函數(shù)n0(x)把實(shí)值混沌序列x0，x1…，xn轉(zhuǎn)換為二進(jìn)制“0”和“1”序列b0，b1…，bn。

n0(x)=1x≥0.50x<0.5(5)

由于Logistic混沌映射對(duì)迭代初值的極度敏感性，計(jì)算相對(duì)于hash函數(shù)也更為簡(jiǎn)單，工程上常用混沌映射來(lái)單向提取特征摘要。本文算法提取簽名的過(guò)程中就采用了Logistie混沌映射，從而實(shí)現(xiàn)了從一個(gè)定長(zhǎng)的二值序列到一位二進(jìn)制數(shù)的有效映射。

1.3.2 提取數(shù)字簽名

提取數(shù)字簽名的步驟如下:

a)建立一個(gè)與Im×n各子塊對(duì)應(yīng)的映射矩陣YSM×N，YSM×N的各元素對(duì)應(yīng)于各個(gè)子塊Kij。當(dāng)Kij 為均勻區(qū)時(shí)，YSij=1;當(dāng)Kij為非均勻區(qū)時(shí)，YSij=0(其中:i=1，2，…，M;j=1，2，…，N)。

b)把矩陣YSM×N每行的N個(gè)元素當(dāng)成一個(gè)N位二進(jìn)制小數(shù)序列，然后將其變成對(duì)應(yīng)的十進(jìn)制小數(shù)(以N=3為例:“111”對(duì)應(yīng)的小數(shù)是0.875，“000” 對(duì)應(yīng)的小數(shù)是0.0，“101”對(duì)應(yīng)的小數(shù)是0.625)。因此，YSM×N的M行對(duì)應(yīng)有M個(gè)[0，1]范圍內(nèi)的十進(jìn)制小數(shù):c1，c2，…，cM。

c)以ci作為初值(i=1，2，…，M)，進(jìn)行λ=4、迭代次數(shù)為T(可任意選取，選定后作為密鑰K2)的Logistic混沌迭代映射，最終得到一個(gè)N位的二進(jìn)制序列，對(duì)這個(gè)序列的各個(gè)元素進(jìn)行模2加求和得到一位二進(jìn)制數(shù)hj，因此，由YSM×N的M行可以得到一個(gè)二值序列h1，h1…，hM。

d)對(duì)YSM×N的N列按b)c)進(jìn)行操作，也可以得到一個(gè)二值序列l(wèi)1，l2…，lN。

e)把h1，h2…，hM與l1，l2…，lN合并，得到原始圖像Im×n的一個(gè)長(zhǎng)度為M+N位的二進(jìn)制數(shù)字簽名S。

1.4 圖像認(rèn)證和竄改定位

由圖2認(rèn)證流程圖可以看出，算法對(duì)圖像的認(rèn)證是由兩個(gè)環(huán)節(jié)(均勻區(qū)認(rèn)證和非均勻區(qū)認(rèn)證)聯(lián)合判斷來(lái)竄改定位的。其中，均勻區(qū)認(rèn)證通過(guò)比較簽名S和二次簽名Sg來(lái)實(shí)現(xiàn)，非均勻區(qū)認(rèn)證通過(guò)檢測(cè)Ig是否滿足歸一化特征來(lái)判斷。以下是算法圖像認(rèn)證的一般步驟:

a)分塊。由密鑰K1確定分塊大小ω，對(duì)預(yù)處理后的圖像Igm×n進(jìn)行ω×ω的分塊，產(chǎn)生M×N個(gè)子塊，塊標(biāo)號(hào)為K′ij(i=1，2，…，M;j=1，2，…，N)。

b)非均勻區(qū)認(rèn)證。檢測(cè)Ig所有非均勻區(qū)子塊，如果子塊內(nèi)0和1的個(gè)數(shù)N0和N1滿足歸一化特征:N1為奇數(shù)，N0/2」為偶數(shù)，則該子塊被判為未發(fā)生竄改;否則，該子塊被判為發(fā)生竄改。

c)均勻區(qū)認(rèn)證。按1.3.2節(jié)中提取簽名的方法對(duì)Ig再次進(jìn)行均勻區(qū)分布映射，用密鑰K2再次進(jìn)行混沌迭代運(yùn)算，得到新的簽名Sg:h1，h2…，hM和l′1，l′2…，l′N，并與簽名S的h1，h2…，hM和l1，l2…，lN進(jìn)行比較:如果hi≠h′i，則說(shuō)明第i行有子塊被竄改;如果lj≠l′j，則說(shuō)明第j列有子塊被竄改;由i ，j行列交叉定位，可將K′ij定為由c)環(huán)節(jié)判為竄改的子塊。

d)聯(lián)合認(rèn)證。由于c)采用的交叉定位的方法，在發(fā)生多區(qū)域竄改時(shí)會(huì)出現(xiàn)虛警，在聯(lián)合認(rèn)證環(huán)節(jié)，需要對(duì)c)環(huán)節(jié)判為竄改塊的進(jìn)行進(jìn)一步判斷:

(a)如果c)判為竄改的塊屬于均勻塊，則該子塊最終被判為竄改塊;

(b)如果c)判為竄改的塊屬于非均勻塊，則聯(lián)合b)中非均勻塊認(rèn)證的結(jié)果，再次進(jìn)行判斷:如果b)也認(rèn)定該塊為竄改塊，則該塊最終被判斷為竄改塊;如果b)認(rèn)為該塊未發(fā)生竄改，則該子塊最終被認(rèn)為未發(fā)生竄改。

2 實(shí)驗(yàn)結(jié)果及分析

本算法的實(shí)驗(yàn)是在MATLAB 7.0 平臺(tái)上進(jìn)行的，為了檢驗(yàn)算法性能，筆者進(jìn)行了大量實(shí)驗(yàn)，但是限于篇幅，以下僅對(duì)部分實(shí)驗(yàn)結(jié)果進(jìn)行羅列和分析。

2.1 不可見性實(shí)驗(yàn)

本文算法的非均勻區(qū)預(yù)處理環(huán)節(jié)需要翻轉(zhuǎn)部分像素點(diǎn)，因此會(huì)對(duì)圖像的視覺(jué)效果造成一定的影響，按式(3)的分析結(jié)果，本文算法中需要翻轉(zhuǎn)的像素點(diǎn)數(shù)約等于非均勻塊的個(gè)數(shù)。

為了客觀評(píng)價(jià)翻轉(zhuǎn)像素點(diǎn)對(duì)視覺(jué)效果的影響，Yang[7]中提出一種評(píng)價(jià)翻轉(zhuǎn)后圖像視覺(jué)改變情況的標(biāo)準(zhǔn)，即扭曲度DS。假如圖像中第i個(gè)像素3×3鄰域的可翻轉(zhuǎn)性的得分是FC(i)(FC(i)的查找表見文獻(xiàn)[2]的圖16)，那么這個(gè)像素翻轉(zhuǎn)后引起圖像的扭曲度定義為

DS(i)=1-FC(i)(6)

可見，扭曲度越小，水印圖像的視覺(jué)效果越好，總的扭曲度TD和平均扭曲度APPD可定義為

TD=∑ni=1DS(i)(7)

APPD=TD/n(8)

APPD值越小，說(shuō)明算法不可見性越好。實(shí)驗(yàn)選取了180×120的圖3作為原始圖像，對(duì)其按15×15大小分塊，分別用Yang[6]、Wu[1，2]、 Tseng[7]、Lu[8]、YangKot[9]、本文算法對(duì)圖3進(jìn)行處理，圖4~9依次為各算法對(duì)圖3翻轉(zhuǎn)部分像素點(diǎn)后的圖像，圖10為本文算法對(duì)圖3進(jìn)行預(yù)處理時(shí)需要翻轉(zhuǎn)的像素點(diǎn)的位置。

表2列出了本次實(shí)驗(yàn)各算法與本文算法的APPD值，由此可見:本文算法的非均勻子塊預(yù)處理的不可見性優(yōu)于Tseng、Lu算法，略差于Yang、Wu的算法，不可見性在所列算法中屬于中等水平。但是本文的預(yù)處理算法比文獻(xiàn)算法更簡(jiǎn)單、并且沒(méi)有文獻(xiàn)算法提取水印時(shí)的同步問(wèn)題。在本次實(shí)驗(yàn)中，采用本文算法對(duì)圖3 進(jìn)行全面的認(rèn)證保護(hù)需要提取的數(shù)字簽名信息長(zhǎng)度僅為20 bit。

表2 算法不可見性比較

APPD

算法

YangWuTsengLuYangKot本文算法

值 0.440.390.860.730.430.58

2.2 非均勻區(qū)竄改定位實(shí)驗(yàn)

以下是對(duì)一幅大小為225×225的二值圖像(分塊大小為15×15)進(jìn)行認(rèn)證的實(shí)驗(yàn)。圖11為原始圖像，圖 12 為預(yù)處理后的圖像，圖13是對(duì)圖12進(jìn)行了竄改后的圖像，圖14是竄改檢測(cè)結(jié)果。本次實(shí)驗(yàn)共對(duì)18個(gè)圖像子塊進(jìn)行了竄改，共檢測(cè)到15塊，實(shí)際檢測(cè)概率為15/18=83.3%，與1.2.2節(jié)理論分析的竄改檢測(cè)率75% 相符。本次實(shí)驗(yàn)中，采用本文算法對(duì)圖11進(jìn)行全面的認(rèn)證保護(hù)需要提取的數(shù)字簽名信息長(zhǎng)度僅為30 bit。

2.3 均勻區(qū)竄改定位實(shí)驗(yàn)

由提取數(shù)字簽名的過(guò)程可知，算法是通過(guò)行列交叉定位的方法來(lái)對(duì)均勻區(qū)進(jìn)行保護(hù)的，每行每列均提取1 bit的信息，由概率論可知，每行正確判斷的概率為50%，每列正確判斷的概率為50%，某個(gè)子塊所在行和列同時(shí)被正確判斷的概率為

Pe=50%×50%=25%(9)

因此，理論上每個(gè)圖像均勻子塊的正確判斷率為25%。但是，在本文算法中，圖像分塊的大小是可以調(diào)整的，假設(shè)分塊后每個(gè)漢字涵蓋n個(gè)圖像子塊的像素，那么每對(duì)圖像的均勻區(qū)域進(jìn)行一個(gè)漢字大小的修改，就相當(dāng)于對(duì)n個(gè)圖像子塊作了竄改。根據(jù)式(9)，每個(gè)子塊竄改不能被正確檢測(cè)到的概率就是1-25%=75%，依據(jù)概率論，整個(gè)漢字不能被檢測(cè)到的概率為(75%)n ，那么，算法對(duì)在均勻區(qū)竄改一個(gè)漢字被檢測(cè)到的概率就是

Pc=1-(75%)n(10)

下面是對(duì)一幅大小為273×273的二值圖像進(jìn)行均勻區(qū)竄改認(rèn)證的實(shí)驗(yàn)，圖中每個(gè)漢字的尺寸為20×20，圖像分塊大小為13×13，每個(gè)漢字包含至少4個(gè)、至多9個(gè)圖像子塊中的像素，即4≤n≤9。由式(10)得:1-(75%)4≤Pc≤1-(75%)9 ，即竄改檢測(cè)率Pc的范圍是:0.685 9≤Pc≤0.924 9 。圖15是原始圖像，圖16為對(duì)圖15進(jìn)行預(yù)處理后的圖像，圖17為發(fā)生均勻區(qū)竄改后的圖像，圖18為非均勻區(qū)認(rèn)證的結(jié)果，圖19為均勻區(qū)認(rèn)證的結(jié)果，圖20為聯(lián)合認(rèn)證的結(jié)果。

本次實(shí)驗(yàn)中，共對(duì)圖15中20個(gè)圖像均勻子塊作了修改，圖19顯示能正確檢測(cè)到的均勻區(qū)竄改塊為7塊，竄改檢測(cè)率為7/20=35%，與理論分析值25%相符;但是，圖19顯示出現(xiàn)了部分虛警塊，這是由于發(fā)生多區(qū)域竄改時(shí)進(jìn)行交叉定位產(chǎn)生的。針對(duì)這種虛警，聯(lián)合認(rèn)證環(huán)節(jié)可以有效地去除這種虛警，如圖20所示。本次實(shí)驗(yàn)共對(duì)四處漢字進(jìn)行了竄改，最終四處竄改的漢字均可以被檢測(cè)到，漢字的實(shí)際竄改檢測(cè)率為 100%，與理論分析值0.685 9≤Pc≤0.924 9相差不大。本次實(shí)驗(yàn)中，采用本文算法對(duì)圖15 進(jìn)行全面的認(rèn)證保護(hù)需要提取的數(shù)字簽名信息長(zhǎng)度僅為42 bit。

2.4 本文算法與其他算法性能比較

表3從圖像認(rèn)證算法的重要特性，如竄改定位能力、能否對(duì)均勻進(jìn)行保護(hù)等方面闡述了文獻(xiàn)[3，4]與本文算法的性能差異。由2.1節(jié)的實(shí)驗(yàn)結(jié)果可以看出，本文算法具有較好的不可見性;表3進(jìn)一步說(shuō)明本文算法在不可見性與所列文獻(xiàn)算法相當(dāng)?shù)那闆r下，竄改定位能力和對(duì)均勻區(qū)的認(rèn)證保護(hù)能力均有所提高。此外，本文算法還具有實(shí)現(xiàn)簡(jiǎn)單、附加信息少量小、定位精度靈活等優(yōu)點(diǎn)。

表3 算法認(rèn)證能力比較

算法非均勻區(qū)竄改檢測(cè)率/%能否對(duì)均勻區(qū)保護(hù)

文獻(xiàn)[3]50不能保護(hù)

文獻(xiàn)[4]50能保護(hù)，圖像分成m×n個(gè)子塊時(shí)，最長(zhǎng)附加信息長(zhǎng)度為m×n×log2(m×n)bit

本文算法75能保護(hù)，圖像分成m×n個(gè)子塊時(shí)，附加簽名信息長(zhǎng)度為m+n bit

3 結(jié)束語(yǔ)

本文提出了一種基于數(shù)字簽名的二值圖像認(rèn)證算法。經(jīng)理論分析和實(shí)驗(yàn)驗(yàn)證，該算法具有良好的不可見性和較強(qiáng)的竄改定位能力，并可實(shí)現(xiàn)對(duì)圖像均勻區(qū)的保護(hù)。該算法的不足之處在于:對(duì)圖像的認(rèn)證是像素級(jí)的，即任何輕微的變動(dòng)都會(huì)被認(rèn)為是對(duì)文檔內(nèi)容的竄改。而在實(shí)際中，某些像素的變化有可能對(duì)圖像內(nèi)容的正確理解沒(méi)有造成任何障礙。因此，如何提高二值文本圖像認(rèn)證算法的魯棒性，使其認(rèn)證能力提升到內(nèi)容認(rèn)證的級(jí)別，甚至進(jìn)一步將其應(yīng)用到紙張形式上，實(shí)現(xiàn)對(duì)打印、復(fù)印、掃描文檔的認(rèn)證保護(hù)，將是筆者接下來(lái)研究的目標(biāo)。

參考文獻(xiàn):

[1]WU M， TANG E， LIU B. Data hiding in digital binary image[C]//Proc of IEEE International Conference on Multimedia and Expo. 2000: 393-396.

[2]WU M， LIU B. Data hiding in binary images for authentication and annotation[J]. IEEE Trans on Multimedia，2004，6(4):528-538.

[3]朱從旭，陳志剛.一種靈敏的文本圖像認(rèn)證混沌脆弱水印技術(shù)[J].小型微型計(jì)算機(jī)系統(tǒng)，2006， 27(1): 151-154.

[4]張小華.基于數(shù)字水印的圖像認(rèn)證技術(shù)研究[D]. 西安:西安電子科技大學(xué)，2004.

[5]李趙紅，侯建軍.基于等級(jí)結(jié)構(gòu)的二值文本圖像認(rèn)證水印算法[J]. 自動(dòng)化學(xué)報(bào)，2008，34(8):841-848.

[6]YANG Hui-juan， KOT A C. Pattern-based data hiding for binary image authentication by connectivitypreserving [J]. IEEE Trans on Multimedia， 2007， 9(3): 475-485.

[7]TSENG Y C， PAN H K. Data hiding in 2color images[J].IEEE Trans on Comput， 2002，51(7): 873-878.

[8]LU H， KOT A C， CHENG J. Secure data hiding in binary images for authentication[C]//Proc of IEEE International Symposium on Circuits and Systems. 2003:806-809.

[9]YANG H， KOT A C. Data hiding for bilevel documents using smoothing techniques[C]//Proc of IEEE International Symposium on Circuits and Systems. 2004:692-695.