10-10-2012, 04:01 PM
ON COMPRESSION OF ENCRYPTED IMAGES
COMPRESSION.pdf (Size: 214.66 KB / Downloads: 37)
ABSTRACT
Coding schemes for secure and efficient communication over
noiseless public channels traditionally compress and then encrypt
the source data. In some cases reversing the ordering
of compression and encryption would be useful, e.g., in enabling
the efficient distribution of protected media content.
Indeed, not only is it possible to reverse the order, but under
some conditions neither security nor compression efficiency
need be sacrificed. In earlier work on this problem we have
assumed that the source data is either memoryless or has a
1-D Markov structure. Such models are poor matches for the
2-D structure of images. In this work, we use a 2-D source
model, and develop a scheme to compress encrypted images
based on LDPC codes. We present practical simulation results
for compressing bi-level images. In tests, we are able
to compress an encrypted 10; 000 bit bi-level image to 4; 299
bits and successfully recover the image exactly. In previous
works, the best analogous 1-D model (operating on a raster
scanned data sequence of the same source) could only compress
the image to 7; 710 bits.
INTRODUCTION
In [1] it was shown that it is theoretically possible to compress
encrypted1 data to the entropy rate of the unencrypted source.
Since good encryption makes a source look completely random,
traditional algorithms are unable to compress encrypted
data. For this reason, traditional systems make sure to compress
before they encrypt. Johnson et al. [1] show that the
problem of compressing encrypted data is related to source
coding with side information. It was shown that neither compression
performance nor security need be impacted under
some reasonable conditions. A block diagram of this system
structure is in Fig. 1
SOURCE MODEL
In this section, we discuss our model for spatially correlated
sources. We consider binary images, wherein each pixel xi;j
takes on one of two values, i.e., xi;j 2 f0; 1g. Images are
sampled on a rectangular grid with Nh rows and Nv columns.
In order to model this source, in prior work [4], the bits were
raster scanned and only the correlation between successive
bits in the scan were considered. This forces a 1-D model on
the data. In this paper, we consider the correlation between
each pixel and its 4 nearest neighbors; up & down, left &
right. We consider here a Markov field model for spatially
dependant sources instead of a Markov chain.
We illustrate the model by way of factor graphs [6]. Factor
graphs are bipartite graphs consisting of variables (represented
by circles) and constraints on those variables (represented
by squares). A section of the factor graph for the 2-D
Markov field model for binary images is presented in Fig. 3.
In the graph in Fig. 3, the circles labeled xi;j represent the bits
of the image and the squares labeled fthi;j and ftvi;j represent
the dependance between pixels.
ENCODER AND DECODER
In this section we present a practical encoder and decoder
for compressing encrypted images. We begin by assuming
that full knowledge of the source statistics (p; h0; h1; v0; v1)
is available to both encoder and decoder, and then relax this
assumption. We compress the encrypted source using a sparse
linear transformation implemented with a matrix multiplication.
A detailed description of the design of the linear transformation
matrix (and the basis for this codec) can be found
in [7]. In particular, the design of the transform matrix is
based (with a modification discussed below) on LDPC codes [8].
The decoder operates by running belief propagation over
the factor graph [6]. We thus proceed by describing the appropriate
factor graph. The graphical model consists of three
components connected together; the models for the source,
the encryption, and the code. Details of the source graphical
model were described in Section 2 and shown in Fig. 3.
RESULTS
As a demonstration, we compress the encrypted version of the
binary image leftmost in Fig. 2. The unencrypted 100x100
binary image (10; 000 bits) is a binary map of the globe. We
use the doped bits in order to calculate the source statistics
for use in the sum-product algorithm run at the decoder. This
image is encrypted (right image in Fig. 2) by adding a pseudorandom
Bernoulli-1=2 string (center image in Fig. 2).
In this example, our method compresses the encrypted
data to 4; 299 bits, of which 2; 019 are doped bits. The decoder
empirically estimates (p; h0; h1; v0; v1)=(0:3935; 0:0594;
0:9132; 0:0420; 0:9295) and then reconstructs the original image
using 81 iterations. The compressed bits and the reconstruction
are presented in Fig. 5. For comparison, we present
the 1-D memory model used in [4], where the encrypted image
could only be compressed to 7; 710 bits. In that simulation,
the image was reconstructed in 27 iterations4. The 2-D
source model allows for greater compressibility.
CONCLUSIONS & FUTURE DIRECTIONS
In this paper we have used a 2-D source model for spatially
correlated data sources. We have leveraged this algorithm to
allow us to efficiently compress encrypted images. Further,
we presented the results of compressing an encrypted binary
image without access to the source statistics at the decoder.
We showed how the 2-D source model allows greater compression
gains than the 1-D source model.
This work naturally suggests an extension to gray-scale
and other larger-alphabet images. A first approach is to break
an image up into a series of bit-planes where each bit-plane
represents all the bits of equal significance in the binary expansion
of the pixel values. Image structure is typically highly
concentrated in the most significant bit-planes though. As a
result, little compression gain is available with this approach.
Accurate image models are necessary to be able to achieve
significant gains when compressing encrypted data.