基于馬爾可夫隨機場的加密二值圖像有損壓縮算法

李添正，王春桃

（華南農業大學數學與信息學院，廣州510642）

（?通信作者電子郵箱wangct@scau.edu.cn）

0 引言

實際應用中，為了節省帶寬并保證圖像在傳輸過程的安全，發送方在傳輸圖像至公共信道前通常會先對圖像進行壓縮，然后再進行加密，但在云計算、分布式計算等環境中，由于計算資源有限（如傳感器）或無利益驅動進行壓縮，發送方通常不會在加密前先進行壓縮，僅將圖像進行加密后發送至云端。而云端為了節省存儲空間或傳輸帶寬，往往需要在無法獲取加密密鑰的情況下對加密圖像進行壓縮。接收方則在獲得加密密鑰及加密壓縮圖像的情況下，通過聯合解壓縮解密來重構原始圖像。這種應用場景發展的系統通常稱為先加密后壓縮（Encryption-Then-Compression，ETC）系統。

盡管直覺上加密信號是無法壓縮的，但Johnson等［1］通過把加密信號的壓縮問題表征為帶邊信息的分布式信源編碼問題，用信息論證明了加密圖像壓縮的可行性，且其理論壓縮效率及安全性與先壓縮后加密的系統性能一致；Schonberg等［2］通過引入馬爾可夫信源模型，進一步提高了加密圖像的壓縮性能；Lazzeretti等［3］通過在加密前利用灰度或彩色圖像空域、位平面間及不同色彩通道間的相關性，進一步提高了加密圖像的壓縮效率。通過先產生預測誤差然后再進行加密及壓縮的方式，Kumar等［4］較為顯著地提升了無損壓縮的性能；Liu等［5］借助截斷Turbo碼以及在接收方以分辨率演進的方式來提升加密圖像壓縮的性能；Zhou等［6］對預測誤差進行聚類及隨機置亂加密，獲得接近以原始未加密圖像作為輸入的最優壓縮算法的性能；Wang等［7］利用二維馬爾可夫隨機場（Markov Random Field，MRF）表征二值圖像空域特征，并構建重構因子圖來進行聯合解壓縮和解密，較大幅度地提高了二值圖像的壓縮效率。隨后，他們將此思想推廣到加密灰度圖像的壓縮［8］。

為了在一定質量損失的情況下獲得更大的壓縮率，研究人員也開展了加密圖像的有損壓縮算法研究。根據所采用的壓縮技術，這些算法大致可以分為三類：第一類采用壓縮傳感技術［9-11］，即利用傳統的壓縮傳感測量矩陣［9］、梯度投影矩陣［10］或者學習得到的詞典［11］作為測量矩陣利用壓縮傳感技術來實施壓縮，并用改進的基追蹤（Basis Pursuit，BP）算法進行重構；第二類采用量化技術［12-18］進行壓縮，即利用標量量化器對加密信號進行量化來進行壓縮，其中量化步長通過多種策略進行優化，接收方通過解密和反量化方式來重構原圖像；第三類利用均勻下抽樣技術［5，19-21］來進行壓縮，并在接收方利用內容自適應插值算法重構圖像。

當前加密圖像壓縮算法可分有損壓縮及無損壓縮兩類。由上述的文獻分析可知，當前已有針對加密二值［1-2，7］、灰圖［2-6，8］及彩色像［4］的無損壓縮與重構算法，但所有相關的加密圖像有損壓縮算法都是針對灰度或彩色圖像的，并沒有針對加密二值圖像的壓縮與重構算法。而諸如簽名、合同、指紋圖像、黑白圖像等二值圖像在日常生活中仍舊有大量的應用，盡管當前有眾多二值圖像的壓縮算法，但這些算法并不能直接用于加密二值圖像的壓縮。因此，開展針對加密二值圖像的壓縮與重構仍然具有重要的理論和實踐意義，當前仍鮮有這方面的研究。針對此情況，并考慮MRF在表征二值圖像空域統計特性方面的優勢［7］，本文提出針一種基于MRF的加密二值圖像的有損壓縮算法。具體而言，發送端利用流密碼對二值圖像進行加密；云端對加密圖像分塊后用隨機抽樣方式進行下抽樣，對下抽樣后留下的像素進一步用低密度奇偶校驗（Low-Density Parity-Check，LDPC）碼進行壓縮；最后在接收端聯合MRF因子圖、加解密復用因子圖和LDPC解碼因子圖形成聯合的重構因子圖，以有損重構二值圖像。實驗仿真時，本文算法與針對原始未加密二值圖像的、具有優秀壓縮性能的國際通用標準JBIG2方法進行性能比較。這是因為根據對文獻盡可能的掌握，當前并未發現針對加密二值圖像的有損壓縮算法；且根據Johnson等［1］的研究，先加密后壓縮系統的壓縮及安全性能與先壓縮后加密系統的一致，因此可以通過與傳統壓縮方法性能的比較來等價地評估加密圖像壓縮算法的性能。實驗結果表明，本文算法獲得了較高的加密二值圖像壓縮效率，并與JBIG2算法壓縮性能相當。考慮到JBIG2是針對原始未加密二值圖像進行壓縮的，而本算法則是針對加密二值圖像的壓縮算法，上述實驗結果印證了Johnson等［1］的理論證明，與JBIG2壓縮性能相當也充分表明了本文算法的可行性和有效性。

本文主要貢獻：1）針對基于MRF的重構方法特點，提出了一種基于分塊隨機抽樣的下抽樣方法，既能使下抽樣后的序列盡可能均勻分布，又能方便實現任意的下抽樣率；2）構造了包含LDPC解碼、解密及MRF重構因子圖的聯合重構因子圖及相應的和-積算法，以實現加密壓縮二值圖像的有損重構；3）提出一種新的加密二值圖像壓縮算法，獲得較高的壓縮效率，且跟以原始未加密二值圖為輸入的JBIG2算法壓縮性能相當甚至更好。

1 背景知識

1.1 因子圖及和-積算法

因子圖［22］是用來表示全局函數f(x1，x2，…，xn)和局部函數fj(X j)的圖模型，其中，X j是集合｛x1，x2，…，xn｝的真子集，索引j用于區分不同子集。

設全局函數可分解為若干局部函數的積，即有：

對于式（1），若用圓圈表示變量節點xi，用小正方形表示因子節點fj，且每個fj都與其對應的自變量集合Xj內的變量節點xi有連接邊，就構成了因子圖，如圖1所示。

圖1 消息更新示意圖Fig.1 Schematic diagramof messageupdate

因子圖中，對于每一個變量節點xi，都有與之對應的邊緣函數f i(xi)，定義為：

其中～{xi}表示除變量xi以外的所有變量集合。對于邊緣函數，可以用和-積算法進行高效計算。該算法可高效同時地計算從變量節點到因子節點的消息（記作vx→f(x)），并更新從因子節點到變量節點的消息（記作μf→x(x)）。其中，vx→f(x)用“積”方式計算，即有：

其中，h∈N（x）f代表x除f外的所有相鄰節點。μf→x(x)用“和”方式計算，即有：

然后，將所有傳給變量節點x的消息進行累乘，即可得到該節點的邊緣函數，即：

1.2 MRF及其因子圖

馬爾可夫隨機場（MRF）具有良好的圖像空間統計特性表征能力，并獲得了廣泛應用［23-24］。首先介紹隨機場的概念。設I(x，y)是像素深度為Q、大小為W×H的圖像，其每一個位于s∈L(L={(x，y)|x∈ [1，W]，y∈ [1，H]})的像素都對應一個隨機變量Fs，取值空間為Φ(Φ={0，1，…，2Q-1})，則這些隨機變量的集合就是隨機場?，即有：

設I(x，y)在坐標集合L上的鄰域為δ(s)={s'|‖ ‖ss'≤d，s≠s'，{s，s'}?L}，則鄰域系統表示滿足圖像I(x，y)上任一點到坐標s的距離小于或等于d的點的集合，但不包括點s。圖2示例了二維空間中到參考點(a，b)距離小于等于5的所有集合，方格數字代表到參考點的距離。

圖2 鄰域系統Fig.2 Neighborhood system

如果隨機場?滿足下面兩個條件：

1）非負性：

2）馬爾可夫性：

則該隨機場稱為馬爾可夫隨機場。文獻［25-27］發現馬爾可夫隨機場與吉布斯（Gibbs）隨機場等價，因此可得到MRF的具體計算公式，即有：

其中：E(X)為能量函數，U是鄰域內所有基團的集合，Vu(?)是通過給定基團的簇勢函數，Ω={F=(F1=f1，F2=f2，…，FWH=f WH|fs∈Φ}。勢函數的階為n時，則MRF的階為n-1。

根據式（10）可得出MRF條件轉移概率：

因此，勢函數對MRF的構建起到了決定性作用。換言之，可以通過對勢函數研究來代替對MRF的研究。

2 本文算法

為在保證一定圖像質量的前提下進一步提高壓縮率，本文設計一種針對加密二值圖像的有損壓縮算法。鑒于云端實際上無法獲取加密密鑰，因此本文采用了下抽樣方式來對加密二值圖像進行壓縮。為了充分利用載體信號間的統計依賴關系，抽樣后留下來的像素要盡可能在空間上呈現均勻分布；為了方便實現任意的下抽樣率，每一塊內采用隨機抽樣。為此，本文設計了一種適應各種壓縮率的分塊隨機下抽樣方法。對于下抽樣后的序列，利用LDPC進一步進行壓縮。接收方收到加密壓縮序列后，構造包含LDPC解碼、解密及MRF重構部分的重構因子圖，實現原始圖像的有損重構，其中，下抽樣后的序列可以無誤地進行重構，但下抽樣過程中被丟棄的像素則需要通過其他輔助手段來進行有損重構。最直接的方式是利用插值法來重構下抽樣過程中被丟棄的像素，但此法重構性能較差。考慮到MRF能很好地表征圖像的空域統計分布，因此若能在無誤重構的下抽樣序列基礎上進一步借助MRF，則將能更好地實現其他像素的有損重構。鑒于MRF能良好地表征圖像的空域統計特性，上述方法將能在一定的壓縮率下獲得較好的重構質量。

圖3給出了本文提出的基于MRF的加密二值圖像有損重構算法。本文算法包含3個部分，即發送方的加密操作，云端的分塊隨機下抽樣，以及接收方的聯合解壓、解密和有損重構操作。各部分的具體細節分別描述如下。

圖3 本文算法流程Fig.3 Flowchart of the proposed algorithm

2.1 載體圖像加密

設二值圖像I(x，y)的大小為W×H，按逐行掃描的方式得到一維二值序列I={I i|i=1，2，…，WH}，然后用流密碼對I進行加密，具體如下。

偽隨機數發生器通過密鑰種子KEY1生成長度為WH的一串隨機密鑰K={K i|i=1，2，…，WH}。為了保證加密的安全，每次加密一幅二值圖像時，都生成不同的密鑰K，以實現“一次一密”。根據香農的理論證明，“一次一密”的加密方法具有可保障的安全性。產生密鑰后，采用異或運算對二值圖像進行加密，即有：

加密后，得到加密二值圖像序列C={C i|i=1，2，…，WH}。該加密二值圖像看上去是一幅隨機二值圖像，隨后，加密圖像序列C通過公共信道傳給云端，密鑰種子KEY1則通過安全信道傳給接收方。

2.2 基于分塊隨機下抽樣的壓縮

為了節省存儲空間或者傳輸帶寬，云端需要在無法獲得加密密鑰的情況下對接收到的加密圖像進行壓縮。如前所述，為了便于盡可能高質量重構，云端采用下抽樣的方式進行壓縮，且下抽樣后的像素盡可能在空間上進行均勻分布。為此，本文采用基于分塊的隨機下抽樣方法，具體介紹如下。

云端把加密二值圖像序列C重新構成W×H的加密二值圖像I'(x，y)。為了能在盡可能均勻的情況還易于操作，本算法采用基于分塊的隨機下抽樣。即把I'(x，y)劃分成互不重疊的塊，每塊的大小為B×B。對于每一塊，按下抽樣率P(P∈[0，1])進行隨機抽取，抽取位置由種子密鑰KEY2控制下生成的隨機數來確定。因此每塊下抽樣后得到長度為B2P長的序列，其中?代表向上取整函數。這樣I'(x，y)下抽樣后得到長度為N=WHP的序列，2，…，N}。

為了進一步提高壓縮率，本文基于Johnson的ETC框架［1］，對下抽樣序列Cˉ利用LDPC進行壓縮。設LDPC的碼率為R(R∈[0，1])，碼長為N，對應的校驗矩陣為N(1-R)×N大小的A，則基于LDPC的壓縮［28］為：

根據式（12），密鑰K與加密序列C是相關的，因此可以把密鑰K作為C的邊信息；類似地，下抽樣密鑰Kˉ與Cˉ也是相關的。如果原始二值圖像中非零比特較多，則Kˉ與Cˉ的相關性變小，有可能會導致LDPC解碼失敗。此時，需利用位摻雜技術來應對。

所謂摻雜技術，即是云端向接收方提供未壓縮的加密比特消息。這樣接收方利用該摻雜比特直接重構相應的像素，從而可以提高邊信息的質量而提高解碼成功率。由于發送1個未壓縮的加密比特，就等價于校驗矩陣A中增加一個度為1的行，這樣就可以把比特摻雜與校驗矩陣進行等效處理。即設摻雜率為dp_rate，則重新構造校驗矩陣如下：

其中，矩陣D的大小為(dp_rate?N?(1-R))?N，且每行有且只有一個1。

當采用摻雜技術時，云端用新構造的Aˉ壓縮Cˉ，即：

S=Aˉ?Cˉ （15）

采用上述方法壓縮后，得到加密壓縮序列S={S i|i=1，2，…，M'}，其中M'=(1+dp_rate)?N?(1-R)。基于此，壓縮率可以計算為：

云端完成分塊抽樣和編碼后，將聯合壓縮后的加密序列S及密鑰種子KEY2發送到接收方。

2.3 構造聯合二值圖像解密解碼因子圖

當接收方收到壓縮加密序列S、加密種子密鑰KEY1、隨機下抽樣種子密鑰KEY2后，進行聯合解壓縮、解密及基于MRF的重構。為了能充分地利用邊信息以提升重構質量，本文利用因子圖理論［22］把基于LDPC解碼的解壓縮、解密及基于MRF的重構操作都表征成因子圖，并將這些因子圖無縫整合在一起形成一個在聯合解壓縮、解密及MRF的重構用因子圖（Joint Factor Graph for Decompression，Decryption，and MRF-based reconstruction，JFG-DDM）。設計好JFG-DDM后，通過在該重構因子圖上運行和-積算法而實現有損重構。

圖4給出了JFG-DDM的示意圖，包含LDPC解碼因子圖、加解密復用因子圖及MRF因子圖，其中，LDPC解碼因子圖實現LDPC解碼，即根據校正子S還原下抽樣后的加密序列Cˉ；加解密復用因子圖用于在迭代解碼過程中，對傳遞的LLR（Log-Likelihood Ratio）消息進行明文狀態和密文狀態的轉換，其中在MRF因子圖下傳遞的是明文狀態下的消息，在LDPC解碼因子圖中傳遞的是密文狀態下的消息；MRF因子圖用于為LDPC的迭代解碼過程中，間接地、動態地提供額外的邊信息，且用于重構那些因下抽樣而丟失的像素。下面分別給出這3個因子圖的具體設計及針對JFG-DDM的和-積算法。

1）LDPC解碼因子圖。

設S j(j=1，2，…，M，…，M')為接收到的校正子元素，其中S k(k=M+1，M+2，…，M')為摻雜比特（即只加密未壓縮的比特），可根據加密特點直接確定該比特的原始未加密未壓縮時的值，故可以在迭代譯碼開始時提供高質量的邊信息；Y?i(i=1，2，…，N)為LDPC解碼過程中得到的加密下抽樣序列；A j為校驗矩陣A的第j行。那么，基于LDPC的壓縮可以表示為：

為 經 LDPC 解 碼 但 未 解 密 的序列。

圖4 JFG-DDM示意圖Fig.4 Schematic diagram of JFG-DDM

根據因子圖理論，若用圓圈代表S j和Y?i，用方框代表式（17）的函數約束關系，則可構造圖5所示的LDPC解碼因子圖。其中，只要A j的第i列為1，就與因子節點gj連線。對于摻雜比特，根據其特點可知，S j和Y?i都只有一條線連接至對應的因子節點gj，即有Y?i=S j，這樣就能在解碼初始化時提供高質量的邊信息，促進解碼的收斂。摻雜比特對應的變量節點與常規變量/因子節點一樣，無需區別對待。

圖5 LDPC解碼因子圖Fig.5 Factor graph of LDPCdecoding

根據LDPC解碼原理，對于此LDPC解碼因子圖，和-積算的消息更新方式如下：

其中，消息μ?→Y?i表示其他因子圖中因子節點向LDPC因子圖中傳遞的消息。

2）加解密復用因子圖。

加解密復用因子圖用于迭代解碼過程中，轉換LLR消息在明文域與密文域之間的狀態。

發送端采用流密碼的方式對二值圖像進行加密，因此流密碼加/解密復用的全局函數可構造如下：

圖6 本算法加解密復用因子圖Fig.6 Multiplexingfactor graph of encryption and decryption

針對此因子圖，加密過程消息更新為：

解密過程消息更新為：

此外，由于接收端已知密鑰Kˉi，因此無需向Kˉi節點更新消息。

3）MRF因子圖。

為了在復雜性和便利性間取得折中，本文采用一階的MRF來表征二值圖像的空域統計特性。后續的實驗結果表明，采用一階MRF是可行的。

具體來說，由于加密操作掩蓋了二值圖像原有的相關性，在不知道密鑰的情況下，加密序列可以看成是離散無記憶信源。但是由于接收方已知密鑰，而實際上圖像像素間是存在統計依賴關系的，因此可以借助于加解密復用因子圖的消息轉換作用，構建MRF因子圖來表達加密序列隱含的內在關系。MRF因子圖有助于在LDPC迭代解碼過程起到正反饋作用，加速解碼收斂。即利用MRF表征的圖像的統計依賴關系，來修正LDPC解碼因子圖中每次迭代解碼結束時的消息，間接地、動態地為下一次迭代解碼提供高質量的邊信息。

由于本算法引入隨機下抽樣方法對圖像進行有損壓縮，因此存在兩類像素，第一類對應加密下抽樣序列經過LDPC解壓及解密后得到的像素，第二類對應下抽樣過程中被丟棄掉的像素。由此構造兩種MRF因子圖，分別如圖7和圖8所示，其中，圖7表示MRF因子圖會與相鄰的加解密復用因子圖進行連接，但圖8表示MRF因子圖不會與加解密復用因子圖進行連接，以此對應下抽樣后的二類像素的重構特點。

圖7所示為第一類像素對應的因子圖，此MRF因子圖模型中的變量節點與文獻［7］中的類似。以中間變量節點F?x，y為例，其他第一類像素類似于此情況。在圖7所示的MRF因子圖中，方框Px，y代表像素的先驗概率約束，ti代表相鄰加解密復用因子圖中的因子節點，Mx，y和Nx，y分別代表水平及垂直方向相鄰像素之間的勢函數約束。

圖8為第二類像素對應的因子圖，以中心變量節點F?x，y為例，其他第二類像素類似于此情況。由于不與加解密復用因子圖進行連接，因此與圖7的最大不同之處是不與因子節點ti相連。圖8是針對本文算法特有的MRF因子圖。

圖7 一般二值圖像的MRF因子圖Fig.7 Conventional factor graph for MRFof abinary image

圖8 本文算法MRF因子圖Fig.8 Factor graph for MRFof the proposed algorithm

對于本文MRF因子圖中的第二類變量節點，因其未與相鄰加解密復用因子圖相連，因此只要把式（23）中的、來自于加解密復用因子圖的消息μt(i)→F?x，y去掉即可，得到下列的消息更新規則：

此外，v F?x，y→Mx，y、v F?x，y→Nx，y+1及v F?x，y→Nx，y可類似處理。

對于消息μMx，y+1→F?x，y、μMx，y→F?x，y、μNx，y+1→F?x，y及μNx，y→F?x，y，則無需改變。

2.4 適用于因子圖JFG-DDM的和-積算法

將2.3節中的LDPC解碼因子圖、加解密復用因子圖及MRF因子圖中相同的變量節點進行合并，即可得到本文算法用于加密二值圖像有損重構的因子圖JFG-DDM。在此因子圖上運行和-積算法即可實現二值圖像的有損重構。

基于和-積算法思想，針對本文算法重構因子圖JFGDDM的和-積算法流程如圖9所示。

圖9 針對JFG-DDM的和-積算法流程Fig.9 Flowchart of sum-product algorithmfor JFG-DDM

具體描述如下。

1）初始化變量節點發出的消息。

結合分布式信源編碼理論，利用加密密鑰以及云端提供的摻雜比特信息，為解碼初始化提供高質量的邊信息，并初始化JFG-DDM中變量節點發出的消息。

當不采用摻雜比特時，用對應下抽樣序列的加密密鑰Kˉi直接生成邊信息。此時在LDPC解碼因子圖中，變量節點Y?i(i=1，2，…，N)向因子節點gj(j=1，2，…，M)發出的消息初始化方式如下：

若采用摻雜比特，因子圖中的Y?i與摻雜比特S k對應，其對應關系由前面KEY2決定，可得Y?i=S k。摻雜比特S k作用在于，用于為解碼開始時，進一步提高邊信息質量。對于此部分由KEY2決定的關系，進而可知v Y?i→gj的值為：

LDPC解碼因子圖中，變量節點Y?i向加解密復用因子圖發出的消息v Y?i→ti可類似于v Y?i→gj的初始化方式進行初始化。

若能確定S j為摻雜比特，可以確定=S j，進一步可以確定 像 素的 值 為在 這 種 情 況 下 ，消 息νF?x，y→Mx，y可初始化為：

νF?x，y→Mx，y+1、νF?x，y→Nx+1，y、νF?x，y→Nx，y和νF?x，y→ti亦可類似地初始化。若Y?i的值無法確定，則根據先驗概率經驗值Px，y進行初始化。例如，νF?x，y→Mx，y可初始化為：

其他消息νF?x，y→Mx，y+1、νF?x，y→Nx+1，y、νF?x，y→Nx，y和νF?x，y→ti也可以類似地初始化。

2）更新因子節點向變量節點發出的消息。

前面已經計算出變量節點發出的消息，此步利用和-積算法中的“和”操作更新因子節點（Factor Node，FN）到變量節點（Variable Node，VN）的消息。

MRF因子圖中，FN向VN的更新公式參考2.3節的式（24）。加解密復用因子圖中，FN向VN的更新公式參考2.3節的式（21）和（22）。對于LDPC解碼因子圖，FN向VN的更新公式參考2.3節的式（19）。

3）更新變量節點向因子節點發出的消息。

接下來應用和-積算法更新變量節點VN到因子節點FN的消息。對于MRF因子圖，因子圖內部的VN向FN的更新消息參考式（23）和（25）。對于LDPC解碼因子圖，因子圖內部的VN向FN的更新消息參考式（18）。

在加解密復用因子圖中，當消息由LDPC解碼因子圖中的變量節點流向加解密因子節點ti時，ν?更新方法為：

Y i→ti

當消息由MRF因子圖中的變量節點F?x，y流向加解密復用因子節點ti時，更新方法如下：

4）Y?的最佳估計。

經過新一輪的迭代（即FN向VN更新以及VN向FN更新）后，為了判斷LDPC解碼是否收斂，需要對LDPC解碼因子圖中變量節點Y?i的邊緣概率進行軟判決。即首先累加各個變量節點Y?i的所有消息，即：

考慮到消息傳遞采用了對數似然率（Log Likelihood Ratio，LLR），然后再進行如下的軟判決，即：

5）判斷迭代是否繼續。

獲得軟判決的重構序列?后，計算校正子S完全等于云端發送到接收方的校正子序列S，則表明LDPC解碼成功，因此迭代重構算法結束。否則，繼續進行前述的步驟2）～步驟4），直到LDPC解碼成功或者達到最大的預設迭代次數為止。

6）重構估計圖像。

若LDPC解碼成功，則MRF因子圖的第一類變量節點（即下抽樣后被保留下來的像素節點）重構值為：

對于第二類變量節點（即下抽樣過程中被丟棄的像素節點），首先類似于式（32）計算傳到該變量節點的所有消息之和，然后再按照式（33）進行軟判決。值得指出的是，盡管第一類節點也可以按照第二類節點進行重構，但可能存在因MRF因子圖中更新的消息不甚準確而導致軟判決錯誤的可能性。

3 實驗仿真與分析

3.1 實驗參數設置

實驗仿真中采用了6幅大小為100×100、具有不同紋理特性的二值圖像Baboon、Barb、Boat、F16、Lena和Tree作為測試圖像，如圖10所示。

圖10 實驗測試圖像Fig.10 Test imagesfor experiments

考慮到本文算法為加密二值圖像的有損重構算法，因此實驗中采用bpp（bit per pixel）和BER（Bit Error Rate）作為算法性能的評估指標，其中，bpp表示每個像素壓縮后的比特數，用壓縮后的總比特數除以總像素來計算；BER為重構的二值圖像與原始二值圖像間的比特誤差率，用兩圖像不相同比特的數量除于總像素數量來進行計算。在同等bpp情況下，BER越小表明重構質量越好；反之亦然。值得指出的是，根據BER可以計算得到相應的峰值信噪比（Peak Signal-to-Noise Ratio，PSNR），但BER的數值能更具體地反映重構圖像的誤差情況，故本文采用BER。

本文算法是在前期加密二值圖像無損壓縮研究［7］的基礎上，進一步提出的針對加密二值圖像的有損壓縮方法。根據對文獻盡可能全面的掌握，當前有為數眾多的二值圖像無損及有損壓縮方法，但尚未發現加密二值圖像的有損壓縮方法。因此為了評估本文算法的bpp-BER性能，根據Johnson等［1］的先加密后壓縮系統壓縮及安全性能與先壓縮后加密系統的壓縮及安全性能一致的理論研究，本文主要與前期的加密二值圖像無損壓縮算法以及加密原始二值圖像作為輸入的JBIG2（Joint Bi-level Image Experts Group version 2）有損壓縮算法進行性能比較，以此等價地評估本文算法的性能。下面分別給出本文算法及JBIG2算法的參數設置。

1）本文參數設置。

為了進一步探究均勻性與隨機性間之間的關系，本節采用分塊隨機抽樣（參考2.2節）、整幅加密二值圖像隨機抽樣及均勻抽樣三種抽樣方式，然后在相同實驗參數設置下比較它們的壓縮性能。對于分塊隨機下抽樣，為了盡可能保留二值圖像在空域上的局部特征，分塊的大小不應設置過大；本文根據實驗情況折中設置分塊大小為B=10。對于整幅圖像隨機抽樣，利用偽隨機序列確定抽取位置；對于整幅圖像的均勻抽樣，則根據抽樣率確定抽樣步長，然后根據步長均勻地抽取像素。

不論采用哪種抽樣方式，當不采用比特摻雜方法（即dp_rate=0）時 ，MRF的 參 數 設 置 為δ=45、P=0.35和T=0.000 49；當采用比特摻雜方法時，MRF的參數設置為δ=45、P=0.5和T=0.000 49。根據前期的研究工作［7］，這些是較優的參數。另最優摻雜率dp_rate通過折半搜索獲得。

實驗仿真時，通過Matlab與C結合的方式實現本文算法。bpp用式（16）進行計算。

2）JBIG2參數設置。

JBIG2是一種針對未加密二值圖像的、支持無損及有損壓縮的國際標準［29-30］。雖然JBIG2允許進行有損壓縮，但并未規定有損壓縮的具體方法，而是通過在無損壓縮前額外增加有損壓縮預處理模塊來實現。為了與本文的加密二值圖像有損壓縮算法進行比較，實驗仿真中采用了JPEG作為有損壓縮預處理模塊。具體而言，實驗仿真中先對二值圖像進行灰度化預處理，即首先把二值圖像的0和1分別映射成取值為0和255的灰度圖像；然后對此灰度化圖像實施量化因子為QF的有損壓縮，得到相應的JPG圖像；最后再以此有損壓縮后的灰度圖像作為JBIG2編碼器（內置圖像二值化功能）的真正輸入。當該JPG圖像輸入JBIG2后，首先進行閾值為128的二值化，然后獲得JBIG2壓縮后的JB2文件數據流，以此實現有損壓縮。

對于JBIG2算法，bpp計算方式如下：

其中：FileSize表示使用JBIG2算法得到的壓縮文件的大小；W和H表示圖像的寬度和高度。

3.2 重構過程演示

為了演示本文算法的重構過程，本節以二值Lena圖為例，該圖大小為100×100，像素值為1的百分比為50.6%。實驗仿真時，采用碼率R=0.525的LDPC碼，并經折半搜索得到最優摻雜比特率。根據實驗結果，采用最優摻雜比特率時對應的壓縮率為0.507。圖11（a）～（f）展示了二值Lena原圖、流密碼加密圖以及迭代11、21、41和51次時的重構二值圖。其中，迭代到51次時LDPC能無誤解碼，獲得有損重構后的Lena，相應的BER為0.006。由圖11可知，在近一半壓縮率的情況下，無論是BER還是視覺效果，有損重構圖像11（f）幾乎逼近原始二值圖像11（a）。

圖11 Lena重構過程演示圖Fig.11 Schematic diagramof reconstruction processof Lena

3.3 算法性能評估

3.3.1 抽樣方式對壓縮性能的影響

為評估本文算法性能，本節比較3.1節中設置的3種不同抽樣方式時本文算法的性能，其中，采用分塊隨機抽樣的本文算法記作MRF_BlkRnd，采用整幅圖像隨機抽樣和均勻抽樣的本文算法分別記作RANDOM和EVEN。

實驗仿真時，采用具有不同紋理特征的二值圖像Tree、Lena、Baboon和F16作為測試圖像。對于步長為10%的每一個 下 抽 樣 率P∈[30%，100%]，分 別 采 用 分 塊 隨 機（MRF_BlkRnd）、整幅圖像隨機（RANDOM）、整幅圖像均勻抽樣（EVEN）方式進行抽樣；接收方在接收到加密壓縮序列后，利用JF-DDM進行重構。對于每一個下抽樣率P，都遍歷LDPC的碼率范圍R∈[0.425，0.725]以找到最小的壓縮率，遍歷時的碼率步長為0.025。對于所獲得的三組實驗數據，為便于比較，將壓縮率bpp以0.025為間隔進行劃分，并挑選每一區間內最小的BER值。基于此，得到圖12所示的針對三種抽樣方式的bpp-BER性能曲線。值得指出的是，當P=100%時，本文算法就等價于針對加密二值圖像的無損壓縮算法［7］，此時可以獲得BER=0的結果。

圖12 三種算法在不同圖像間的bpp-BER性能比較Fig.12 Comparison of bpp-BER performance of three algorithms between different images

圖12所示的實驗仿真結果表明，MRF_BlkRnd總體上優于EVEN和RANDOM。這是因為MRF_BlkRnd采用了均勻分塊而塊內隨機的下抽樣方法，能較好地在均勻性和隨機性間保持較好的折中，從而有利于借助解壓解密重構的像素及MRF推斷其他在下抽樣過程中被丟棄的像素，重構性能較為穩定。然而，RANDOM的隨機性較強，解壓解密重構的像素有可能堆在一個局部而不利于借助MRF推斷其他下抽樣時被丟棄的像素；EVEN的均勻性雖然非常好，但有可能會因邊緣紋理區域下抽樣的像素數量少而影響重構質量。因此，采用分塊隨機進行下抽樣是一種較好的選擇。

3.3.2 與相關算法的性能比較

為進一步評估本文算法性能，本節比較本文算法（即MRF_BlkRnd）與有損JBIG2算法，其中，有損JBIG2算法借助于JPEG壓縮方法來實現有損壓縮，具體見3.1節描述。實驗仿真中，JPEG壓縮的QF設置為［1：100］，步長為1。若相鄰QF導致相同的bpp，則取BER較小的那個結果。

考慮到本文算法是針對加密二值圖像的壓縮，而JBIG2是針對原始未加密二值圖像的壓縮，本節還分別以原始未加密二值圖像以及對應的加密二值圖像作為有損JBIG2算法的輸入，以便更好地評估各算法的bpp-BER性能。為簡便起見，這兩種情形分別記作ORI_JBIG2和ENC_JBIG2。

利用3.1節及上述的實驗參數設置，對6幅測試圖像開展實驗。首先評估不同方法的重構質量，圖13中給出了MRF_BlkRnd和ORI_JBIG2在近似壓縮率情況時的有損重構圖像；但因ENC_JBIG2的壓縮率大于1，難于進行比較，故圖13中并未給出該方法的重構圖像。鑒于篇幅限制，圖13中以Barb和F16為例，除Baboon外的其他圖像有類似情況；對Baboon而言，MRF_BlkRnd的壓縮率都比ORI_JBIG2的低，因此難于進行同等壓縮率下的重構質量比較。由圖13可知，MRF_BlkRnd和ORI_JBIG2的重構圖像都具有較好的視覺效果，且與原始圖像相近；MRF_BlkRnd與ORI_JBIG2間的重構圖像質量近似一致，差別不明顯。考慮到ORI_JBIG2是針對原始未加密二值圖像的壓縮方法，而本文是針對加密二值圖像的壓縮算法，這就表明了本文算法的可行性。

圖13 重構圖像質量評估Fig.13 Evaluation of reconstructed images

其次評估算法MRF_BlkRnd、ORI_JBIG2和ENC_JBIG2針對6幅二值圖像的bpp-BER性能，如圖14所示。由圖可知，MRF_BlkRnd算法的BER隨著bpp的增加而逐漸減小，這是因為bpp的增大意味著壓縮率的減小，從而使得重構誤差也相應地減小。不過，MRF_BlkRnd的變化趨勢并不是非常平滑，主要是因為分塊內進行不同的隨機抽樣時，會呈現波動，如圖14中Boat和F16的情況。此外，圖14也表明，測試圖像的壓縮率落在0.2～0.4 bpp范圍內，BER最多不超過0.05，這表明本文算法具有良好的率失真性能。

由圖14可知，在相同BER情況下，MRF_BlkRnd相比ORI_JBIG2和ENC_JBIG2普遍具有更低的bpp。這主要是因為本文算法借助于MRF更好地利用了像素間的統計依賴關系，能更好地重構因壓縮而丟失的像素，進而獲得更高的壓縮效率。

圖14 MRF_BlkRnd、ENC_JBIG2和ORI_JBIG2的bpp-BER性能比較Fig.14 Performance comparison in bpp-BERbetween MRF_BlkRnd，ENC_JBIG2 and ORI_JBIG2

根據圖14，ENC_JBIG2算法的性能遠差于ORI_JBIG2和MRF_BlkRnd。這是因為ENC_JBIG2的輸入圖像是加密后的二值圖像，JBIG2算法無法利用圖像的統計特性進行壓縮，自然沒有辦法獲得好的壓縮性能，從而比ORI_JBIG2和MRF_BlkRnd的性能差。

此外，對于ORI_JBIG2，在不同JPEGQF時的壓縮率差別不大，BER通常隨著QF的增加而減小。這是因為將原始二值圖映射成取值為0和255的灰度圖并經過JPEGQF有損壓縮預處理后，無論采用什么樣的QF，經過這些操作后的像素值大多數仍然分布在0或255的附近。這樣當把JPEG壓縮后的圖輸入到JBIG2壓縮算法中，并以128作為閾值處理得到的二值圖IJPEG(x，y)，與原始二值圖I(x，y)差別較小，從而使得經過JBIG2壓縮后的bpp相差不大。但當QF變小時，IJPEG(x，y)與I(x，y)的差別相對增大，導致解碼后的BER也相應地增大。

再者，對于ENC_JBIG2中的加密二值圖像，采用與ORI_JBIG2相同的處理流程。由于加密操作掩蓋了載體圖像的統計特性，因此JBIG2算法根本無法發揮其壓縮優勢，從而基本上無法進行壓縮。再加上在JBIG2編碼前進行了JPEG壓縮，在編碼后生成的jb2文件尚需要保存一部分輔助信息，導致壓縮率略大于1.0 bpp。綜合上述分析可知，相較于ORI_JBIG2，本文算法在不同bpp時的性能有好有差，但總體上性能相當甚至略好，即本算法壓縮加密二值圖像的壓縮效率，能夠達到JBIG2算法壓縮常規二值圖像的壓縮效率。

由于ORI_JBIG2是以未加密圖像作為輸入進行壓縮的，而本文算法是針對加密二值圖像進行壓縮的，因此本文算法是可行的和有效的。

4 結語

本文提出了一種基于MRF的加密二值圖像有損壓縮算法。其中，發送方用流密碼進行加密；云端采用基于分塊隨機下抽樣方法進行壓縮，分塊的目的在于令下抽樣后的序列在空域中盡可能均勻分布，隨機的目的在于方便實現任意的下抽樣率；下抽樣后的序列進一步利用LDPC校正子編碼進行壓縮；接收方構造包含LDPC解碼、解密及MRF重構的重構因子圖，以便在運行經適配的和-積算法時能實現加密二值圖像的有損重構。實驗仿真結果表明，本文算法具有較好的加密二值圖像壓縮效率，且bpp-BER性能總體上與以未加密原始二值圖作為輸入的JBIG2算法性能相當甚至更好。這就充分表明了本文算法的有效性和可行性。

本文算法設計的分塊隨機下抽樣方法，雖然基本上是可行的，但在不同隨機抽樣情形下，bpp-BER性能卻會有一定的波動，因此，后續研究中需進一步設計更好的下抽樣方式。