A New MRF-Based Lossy Compression for Encrypted Binary Images

Abstract

Although there exist many researches on the compression of original non-encrypted binary images, few approaches focus on the compression of encrypted binary images. As binary images like contract, signature, halftone images are still used widely in practice, how to compress efficiently encrypted binary images in a lossy way deserves further exploration. To this end, this paper develops a lossy compression scheme for encrypted binary images by exploiting the Markov random field (MRF) model. Considering that the third-party in scenarios of cloud or distributed computing cannot access to the encryption key, we develop the concatenated down-sampling and LDPC-based encoding to perform the compression, in which four different down-sampling methods are designed to facilitate improving the quality of reconstructed image. In reconstruction, we first formulate the lossy reconstruction from the encrypted and compressed binary image as an optimization problem, and then build a joint factor graph involving the LDPC-decoding, decryption, and MRF to solve this optimization problem, in which the MRF is exploited to well infer pixels discarded in the down-sampling process. By adapting the sum-product algorithm (SPA) to the constructed joint factor graph for lossy reconstruction (JFG-LR) and running the adapted SPA on the JFG-LR, we thus recover the original binary image in a lossy way. By integrating the stream-cipher-based encryption, the down-sampling and LDPC-based compression, and the JFG-LR-involved reconstruction, we thus propose a new lossy compression scheme for encrypted binary images. Experimental results show that the proposed scheme achieves desirable compression efficiency, which is comparable to or even better than that of the JBIG2 with the original unencrypted binary image as input.

Keywords

• Compression of encrypted binary images
• lossy compression
• Markov random field
• factor graph
• LDPC