Efficient Compression of Encrypted Binary Images Using the Markov Random Field

Similar to conventional compression with the original, unencrypted image as the input, the recently emerged compression on encrypted images generally exploits statistical correlation of natural images to improve compression efficiency. Most of these compression schemes in the literature leverage statistical correlation at the content-owner or service-provider side, which would either increase the computational burden on the content-owner or disclose statistical distributions to the service-provider and thus probably hinder their practical applications. Through analysis on properties of the compression system for encrypted data, we believe that it is more preferable to exploit statistical correlation of natural images at the receiver side with both encryption key and sufficient computational capability, which in turn would improve compression efficiency while achieving low computational complexity and sufficient security for the content owner and the service provider. In light of this, we use the Markov random field (MRF) to characterize binary images in the spatial domain and represent it with a factor graph. The constructed MRF representation of the binary image in the factor graph is then integrated seamlessly with the factor graph for low-density parity check (LDPC)-based decompression, yielding a joint factor graph for binary image reconstruction. By deriving message update equations for the joint factor graph, we develop a new lossless compression scheme for encrypted binary images, which involves stream-cipher-based encryption, LDPC-based compression, and factor-graph-based image reconstruction. Preferable parameters for the proposed scheme are first determined numerically on a specific binary image and then applied to other binary images. Extensive simulations show that significant improvements in terms of compression bit rate over the state of the art are achieved, demonstrating the feasibility and effectiveness of the proposed scheme.