Benefiting from Duplicates of Compressed Data: Shift-Based Holographic Compression of Images

Abstract

Storage systems often rely on multiple copies of the same compressed data, enabling recovery in case of binary data errors, of course, at the expense of a higher storage cost. In this paper, we show that a wiser method of duplication entails great potential benefits for data types tolerating approximate representations, like images and videos. We propose a method to produce a set of distinct compressed representations for a given signal, such that any subset of them allows reconstruction of the signal at a quality depending only on the number of compressed representations utilized. Essentially, we implement the holographic representation idea, where all the representations are equally important in refining the reconstruction. Here, we propose to exploit the shift sensitivity of common compression processes and generate holographic representations via compression of various shifts of the signal. Two implementations for the idea, based on standard compression methods, are presented: the first is a simple, optimization-free design. The second approach originates in a challenging rate-distortion optimization, mitigated by the alternating direction method of multipliers (ADMM), leading to a process of repeatedly applying standard compression techniques. Evaluation of the approach, in conjunction with the JPEG2000 image compression standard, shows the effectiveness of the optimization in providing compressed holographic representations that, by means of an elementary reconstruction process, enable impressive gains of several dBs in PSNR over exact duplications.

1 Introduction

Any digital system involving storage or transmission of signals (e.g., images, videos and other multimedia data) fundamentally relies on lossy compression processes to meet storage-space or transmission bandwidth limitations, incurring acceptable reductions in the eventual recovered signal quality. Contemporary storage and content distribution services implement processes where a binary compressed representation of a particular signal is exactly duplicated for the purpose of storage reliability, or for delivery to multiple users in a network. Clearly, subsequent access to several identical copies of the compressed signal cannot provide a reconstruction quality better than that achieved using a single copy. Hence, there is an inefficiency in the joint bit-cost of several copies versus the reconstruction quality they provide together. In this paper, we address this type of inefficiency, as will be explained next.

Holographic representations [1,2,3] of a signal are a set of data packets designed so that its subsets enable signal approximation at a quality depending only on the number of packets utilized, and independent on the particular packets included in the subset. The holographic representations concept is closely related to the multiple description coding approach (see, e.g., [4,5,6]) as, indeed, both methods aim at reconstruction refinement when increasing the size of the subset of packets used for approximation. However, the two approaches differ in the following aspect: when using holographic representations, increasing the number of packets used for approximation leads to a quality gain (approximately) independent of the particular packets added at the expense of considerable higher bit-cost. In contrast, in the common designs of multiple description coding, adding various packets may lead to considerably different quality gains due to serious concerns about keeping the bit-cost as low as possible [4, 5]. Inherently, the property of holographic representations implies that some amount of redundancy remains among the packets and, therefore, the packet bit-costs may be higher than in the multiple description coding approach. Nevertheless, the special properties of the holographic representations can significantly contribute to storage system designs.

Here we emphasize that, in the context of storage systems, the holographic representations are intended for improving settings where several identical copies of compressed data are stored and their individual usefulness for recovery is more important than achieving the best possible reduction in their joint bit-cost. A well-known case where single copy usefulness in reconstruction is crucial is in duplication-based reliable storage systems, where multiple identical versions of the data are stored for enabling recovery in case of errors in the binary form of the data. This approach is realized by the redundant array of independent disks (RAID) [7] data storage technology in mirroring-based settings that are of interest when retrieval speed is a significant concern. Other approaches, which are more common, do not necessarily store multiple exact copies of the data (see examples in [7]) and, accordingly, are not related to the framework proposed in this paper.

In this paper, we focus on visual signals that are commonly represented and processed jointly with lossy compression. Using the principles of holographic representations, we establish a methodology to store a signal in several non-identical copies that are individually equally descriptive (with respect to a distortion metric such as the mean squared error). The important aspect of the proposed idea is that subsets of the stored, non-identical duplicates allow us to improve the quality of the recovered signal via a simple reconstruction procedure. Hence, the storage cost increase on the duplicates is exploited for significant quality improvement in the retrieved signals.

We design the framework for production of holographic representations employing binary compressed data. Since many compression processes are shift sensitive (e.g., due to block-based designs), we create holographic representations based on various shifts of the input signal. Then, in the reconstruction stage the signal is approximated via averaging the available subset of properly back-shifted representations. The reconstruction quality improves as the subset of available representations gets larger.

We further improve our idea by formulating the problem as a rate-distortion optimization, minimizing a Lagrangian cost including the total bit-cost of all the representations and two distortion penalties: one expresses the distortion averaged over all the m-packet reconstructions (for a specific $m > 1$), and the second reflects the average distortion of individual packets. Then, we apply our general optimization approach for intricate compression problems (established in [8,9,10,11] for various settings). Specifically, using the alternating direction method of multipliers (ADMM) we develop an iterative process relying on repeated applications of standard compression techniques (that consider squared-error metrics but no holographic representations aspects). Accordingly, our iterative approach decouples the holographic-related distortion terms from the actual compression stage, leading to holographic compressed representations compatible to an existing compression standard.

We present experimental results evaluating the proposed methodology for image compression in conjunction with the JPEG2000 standard. The results are analyzed using empirical quantities reflecting the holographic properties of similar usefulness of packets added to the reconstruction, as well as progressive refinement. Impressive PSNR gains are achieved by the proposed methods over the approach of exact duplications. For instance, we evaluate the case of four packets compatible with the JPEG2000 standard at a compression ratio of 1:50 and show that using four packets the proposed optimization framework improves the PSNR of the reconstructed image by about 5 dB over the PSNR obtained with exact duplications.

2 Problem Definition

2.1 Holographic Compression and Decompression

Fig. 1

General description of holographic compression and decompression processes

In this paper, we propose a lossy compression framework with holographic representation properties (see Fig.1). Given a signal $\mathbf {x} \in \mathbb {R}^N$, by definition, a holographic compression algorithm produces K binary representations (packets) $b_1 , \ldots , b_K \in \mathcal {B}$, where $\mathcal {B}$ is a discrete set of binary compressed representations of possibly different lengths. The set of packets fulfill holographic properties either exactly or approximately (as will be described below). Accordingly, the holographic compression process can be described as a function $C_H : \mathbb {R}^N \rightarrow \mathcal {B}^K$, mapping the source signal domain, $\mathbb {R}^N$, to the K-tuples from the domain $\mathcal {B}$ of binary compressed representations.

By definition, the holographic decompression process can get any subset of $m \in \left\{ 1, \ldots ,K \right\}$ packets from the overall set of packets, a subset denoted here as

$$\begin{aligned} \left\{ b_{i_1} , \dots , b_{i_m} \right\} \subset \left\{ b_1 , \dots , b_K \right\} \end{aligned}$$

where $\left\{ {i_1}, \dots , {i_m} \right\} \subset \left\{ 1 , \dots , K \right\}$ are the indices of the packets taken from the range of integers from 1 to K without repetitions. For each $m=1, \ldots ,K$ there is a holographic decompression function, $F_H^{(m)} : \mathcal {B}^m \rightarrow \mathbb {R}^N$, mapping the given subset of m packets into a reconstructed signal, namely,

$$\begin{aligned} \mathbf {v} \triangleq F_H^{(m)} \left( b_{i_1} , \ldots , b_{i_m} \right) \end{aligned}$$

(1)

where $\mathbf {v} \in \mathbb {R}^N$.

We evaluate the fidelity of the reconstructed signal using the mean squared error (MSE) criterion. Accordingly, the distortion of the reconstruction from the m packets corresponding to the indices $i_1, \ldots ,i_m$ is formulated as

$$\begin{aligned} \tilde{D}^{(m)} \left( \mathbf {x}; {i_1} , \ldots , {i_m} \right) \triangleq \frac{1}{N} \left\| { \mathbf {x} - F_H^{(m)} \left( b_{i_1} , \ldots , b_{i_m} \right) } \right\| _2^2 . \end{aligned}$$

(2)

In the sequel, we will use the following notations. The sequence of integers from 1 to K is denoted as $[[{K} ]] \triangleq \lbrace 1, \ldots ,K \rbrace$. For $m \in [[{K} ]]$, an m-combination of the set $[[{K} ]]$ is a subset of m distinct numbers from $[[{K} ]]$. We denote the set of all m-combinations of $[[{K} ]]$ as $[[{K} ]] \atopwithdelims ()m$, where the latter contains $K \atopwithdelims ()m$ elements.

2.2 The Ideal Holographic Properties in Deterministic Settings

The desired holographic properties, in their idealistic forms, can be described as follows.

2.2.1 Equivalent Usefulness of Individual Packets

Each of the individual packets, $\lbrace b_i \rbrace _{i=1}^K$, should enable the approximation of $\mathbf {x}$ at the same level of MSE. More generally, given $m\in \lbrace 1,\dots , K \rbrace$ packets, denoted as $\lbrace {b}_{i_1} , \dots , {b}_{i_m} \rbrace$, one can construct an estimate for $\mathbf {x}$ using the function $F_H^{(m)} \left( b_{i_1} , \ldots , b_{i_m} \right)$ such that any subset of packets leads to a reconstruction that approximates $\mathbf {x}$ at the same MSE level, i.e., this ideal property is formulated as

$$\begin{aligned} \tilde{D}^{(m)} \left( \mathbf {x}; {i_1} , \ldots , {i_m} \right) = \tilde{D}^{(m)} \left( \mathbf {x}; {l_1} , \ldots , {l_m} \right) \end{aligned}$$

(3)

for any $\left( i_1, \ldots , i_m \right)$ and $\left( l_1, \ldots , l_m \right)$ in ${ [[{K} ]] \atopwithdelims ()m }$.

2.2.2 Progressive Refinement

The approximation $F_H^{(m)} \left( b_{i_1} , \ldots , b_{i_m} \right)$ of $\mathbf {x}$ using any $m\in \lbrace 2, \ldots , K \rbrace$ packets attains a lower MSE than the approximation $F_H^{(\bar{m})} \left( b_{i_1} , \ldots , b_{i_l} \right)$ constructed using any $\bar{m} < m$ packets. It is important to add the progressive refinement property to the equivalent usefulness concept or, otherwise, exact duplications of the input data would be a trivial solution to achieve equivalent usefulness of representations. The union of the above two properties can be formulated as follows: for $m=1, \ldots ,K$,

$$\begin{aligned} \tilde{D}^{(m)} \left( \mathbf {x}; {i_1} , \ldots , {i_m} \right) = \mathcal {E}_m ~~~~ \forall \left( i_1, \ldots , i_m \right) \in { [[{K} ]] \atopwithdelims ()m } ~~~~~~~ \end{aligned}$$

(4)

where $\mathcal {E}_{\bar{m}} > \mathcal {E}_{m}$ for any $\bar{m} < m$ in $[[{K} ]]$.

2.3 Feasible Holographic Properties in Deterministic Settings

In general (in the deterministic settings), the ideal holographic properties presented above cannot be precisely achieved. Hence, let us define a feasible version of the holographic principles.

First let us define the average MSE of the m-packet reconstructions as

$$\begin{aligned}&\text {mean}^{\left( {m}\right) }_D \left( \mathbf {x}; b_{1} , \ldots , b_{K} \right) \triangleq \nonumber \\&\frac{1}{ {K \atopwithdelims ()m } } \sum _{ \left( i_1, \ldots , i_m \right) \in { [[{K} ]] \atopwithdelims ()m } } \tilde{D}^{(m)} \left( \mathbf {x}; {i_1} , \ldots , {i_m} \right) \end{aligned}$$

(5)

Furthermore, the empirical variance of the m-packet reconstruction MSE is defined via

$$\begin{aligned}&\text {var}^{\left( {m}\right) }_D \left( \mathbf {x}; b_{1} , \ldots , b_{K} \right) \triangleq \frac{1}{ {K \atopwithdelims ()m } } \times \nonumber \\&\sum _{ \begin{array}{c} \left( i_1, \ldots , i_m \right) \\ \in { [[{K} ]] \atopwithdelims ()m } \end{array} } \left( \tilde{D}^{(m)} \left( \mathbf {x}; {i_1} , \ldots , {i_m} \right) - \text {mean}^{\left( {m}\right) }_D \left( \mathbf {x}; b_{1} , \ldots , b_{K} \right) \right) ^2 \end{aligned}$$

(6)

The definitions of average and variance of the reconstruction MSE allow us to formulate softened versions of the strict holographic properties defined in the former subsection. These practical features are

2.3.1 $\sigma$-Similar usefulness of individual packets

Consider the task of reconstructions based on subsets of $m\in \lbrace 2, \ldots , K \rbrace$ packets. A set of K packets, $\lbrace b_i \rbrace _{i=1}^K$, will be considered to satisfy the property of $\sigma$-similar usefulness of packets for m-packet reconstructions, if it obeys

$$\begin{aligned} \text {var}^{\left( {m}\right) }_D \left( \mathbf {x}; b_{1} , \ldots , b_{K} \right) \le \sigma ^2 . \end{aligned}$$

(7)

Namely, the variance of the reconstruction MSE, empirically considering all the m-combinations of subsets, does not exceed the value $\sigma ^2$. Clearly, for $\sigma = 0$ the property defined here reduces to the strict equivalence of packet usefulness presented in (3).

2.3.2 Progressive Refinement on Average

This property is implemented by a set of K packets where the approximations of $\mathbf {x}$ using $m\in \lbrace 2, \ldots , K \rbrace$ packets yield a lower average MSE than the approximations constructed using $\bar{m} < m$ packets. Namely,

$$\begin{aligned} \text {mean}^{\left( {m}\right) }_D \left( \mathbf {x}; b_{1} , \ldots , b_{K} \right) = {\mathcal {E}}_m \end{aligned}$$

(8)

where $\mathcal {E}_{\bar{m}} > \mathcal {E}_{m}$ for any $\bar{m} < m$ in $[[{K} ]]$. It is again worth noting the significance of demanding progressive refinement (on average) in conjunction with the similar-usefulness concept, or else exact duplications of the input data would trivially provide equivalent usefulness of representations.

3 Shift-Based Holographic Compression: A Baseline Approach

Fig. 2

The baseline unoptimized process for holographic compression and decompression

We next describe an elementary, yet effective, design for holographic compression. The simplicity of this baseline architecture stems from the utilization of shift operators in conjunction with standard compression methods that are inherently shift-sensitive. Specifically, the regular compression of the various shifts of the given signal will produce different compressed representations that are, in principle, of about the same usefulness for reconstruction. The progressive refinement ability is also immediate here due to the collection of different decompressed signals that, together, can provide a reconstruction with a lower distortion and reduced amount of compression artifacts.

First, let us formulate a process of regular (non-holographic) lossy compression as a mapping $C: \mathbb {R}^N \rightarrow \mathcal {B}$ from the N-dimensional signal domain to a discrete set $\mathcal {B}$ of binary compressed representations (of possibly different lengths) supported by the compression architecture. The compression of the signal $\mathbf {w} \in \mathbb {R}^N$ provides the compressed binary data $\textit{b} = C \left( \mathbf {w} \right)$ that can be decompressed to form the signal $\mathbf {y} = F \left( \textit{b} \right)$, where $F: \mathcal {B} \rightarrow \mathcal {S}$ represents the decompression mapping between the binary compressed representations in $\mathcal {B}$ to the corresponding decompressed signals in the discrete set $\mathcal {S} \subset \mathbb {R}^N$. Accordingly, we consider the pair of sets $\mathcal {B}$ and $\mathcal {S}$ as a description of a standard non-holographic compression architecture.

Note that we intentionally associated the holographic compression design in Sect. 2.1 with the standard compression definition given here, by referring to the same set $\mathcal {B}$ of binary compressed representations. Indeed, this means that the holographic decompression process should start with individual standard decompression of the obtained packets, namely,

$$\begin{aligned} \mathbf {y}_{j} = F\left( b_j \right) \text {~~for~~} j=i_1, \ldots ,i_m \end{aligned}$$

(9)

where $\mathbf {y}_{j}$ is the decompressed signal associated with the $j^{th}$ packet. We will refer to $\mathbf {y}_{i_1}, \ldots , \mathbf {y}_{i_m}$ as decompressed packets. Since the holographic decompression, associated with the function $F_H^{(m)}$ defined in (1), starts with standard decompression of the individual packets, we can define the relation

$$\begin{aligned} G_H^{(m)} \left( \mathbf {y}_{i_1} , \ldots , \mathbf {y}_{i_m} \right) \triangleq F_H^{(m)} \left( b_{i_1} , \ldots , b_{i_m} \right) \end{aligned}$$

(10)

i.e., $G_H^{(m)}: \mathcal {S}^m \rightarrow \mathbb {R}^N$ is the holographic reconstruction function, receiving m decompressed packets and returning the decompressed signal $\mathbf {v} \in \mathbb {R}^N$. For simplicity of notations, the developments in this paper mainly refer to the holographic decompression function $G_H^{(m)}$ having inputs and outputs in the signal domain $\mathbb {R}^N$.

Signal compression methods usually rely on various block-based vector quantization designs that inherently make them shift sensitive. Accordingly, we consider in this paper the creation of holographic compressed representations based on shift operators coupled with standard compression techniques. For this purpose, we define the operator of a cyclic shift, to cyclically move components of an N-length column vector in one place upward, via the $N\times N$ matrix

$$\begin{aligned} \mathbf {S} \triangleq \begin{bmatrix} 0 &{} 1 &{} 0 &{} \cdots &{} 0 \\ 0 &{} 0 &{} 1 &{} \cdots &{} 0 \\ \vdots &{} \vdots &{} \vdots &{} \ddots &{} \vdots \\ 0 &{} 0 &{} 0 &{} \cdots &{} 1 \\ 1 &{} 0 &{} 0 &{} \cdots &{} 0 \end{bmatrix} \end{aligned}$$

(11)

and the corresponding inverse shift can be applied using $\mathbf {S}^T$ since $\mathbf {S}^T \mathbf {S} = \mathbf {I}$. The cyclic shift in an amount of l places is obtained via $\mathbf {S}^l$, which is the product of l basic matrices $\mathbf {S}$, and its inverse is accordingly defined as the transpose of $\mathbf {S}^l$.

As a baseline unoptimized design let us consider the following implementations of the holographic compression and decompression processes (see Fig. 2). The holographic compression procedure $C_H \left( \mathbf {x} \right)$ produces the K binary compressed representations via

$$\begin{aligned} b_{i} = C\left( \mathbf {S}_i \mathbf {x} \right) \text {~~for~~} i=1, \ldots ,K \end{aligned}$$

(12)

where $\mathbf {S}_1, \ldots ,\mathbf {S}_K$ are K different cyclic shift operators in the forms of $N \times N$ matrices. Accordingly, in this baseline architecture, the $i ^{th}$ holographic compressed representation is formed by a standard compression of a (cyclically) shifted version of the input $\mathbf {x}$ (where the amount of shift is defined by the matrix $\mathbf {S}_i$). The holographic decompression based on a subset of m packets is defined as

$$\begin{aligned} F_H^{(m)} \left( b_{i_1} , \ldots , b_{i_m} \right) = \frac{1}{m} \sum \limits _{j=1}^{m} \mathbf {S}_{i_j}^T F\left( b_{i_j} \right) \end{aligned}$$

(13)

or, alternatively, by describing the reconstruction given the decompressed packets as

$$\begin{aligned} G_H^{(m)} \left( \mathbf {y}_{i_1} , \ldots , \mathbf {y}_{i_m} \right) = \frac{1}{m} \sum \limits _{j=1}^{m} \mathbf {S}_{i_j}^T \mathbf {y}_{i_j} \end{aligned}$$

(14)

The MSE of the reconstruction from the m packets corresponding to the indices $i_1, \ldots ,i_m$ is

$$\begin{aligned} D^{(m)} \left( \mathbf {x}; \mathbf {y}_{i_1} , \ldots , \mathbf {y}_{i_m} \right) \triangleq \frac{1}{N} \left\| { \mathbf {x} - \frac{1}{m} \sum \limits _{ j=1}^{m} \mathbf {S}_{i_j}^T \mathbf {y}_{i_j} } \right\| _2^2 , \end{aligned}$$

(15)

where we use a simplified notation assuming that the indices of the packets (i.e., ${i_1} , \ldots , {i_m}$) are available to the distortion function in order to associate the shift operators corresponding to the decompressed packets.

4 An Optimization-Based Approach for Holographic Compression

Returning to the baseline implementation described in (12)–(14) clearly shows that while the baseline design is a new and intriguing compression approach, it is not designed to optimize the output quality. The main goal of this section is to present an optimized design for holographic compression based on the same, relatively simple, reconstruction procedures in (13)–(14),while replacing the encoding process of (12) by our optimization-induced procedure.

The mathematical developments in this section require the definition of a bit-cost evaluation function associated with the standard (non-holographic) compression architecture described by C, F, $\mathcal {B}$ and $\mathcal {S}$ at the beginning of Sect. 3. A decompressed signal $\mathbf {y}\in \mathcal {S}$ is associated with a single binary compressed representation $b=F^{-1}\left( {\mathbf {y}}\right) \in \mathcal {B}$. Accordingly, the bit-cost evaluation function $R\left( {\mathbf {y}}\right)$, defined for $\mathbf {y}\in \mathcal {S}$, returns the length of the binary representation $F^{-1}\left( {\mathbf {y}}\right) \in \mathcal {B}$. Namely, $R\left( {\mathbf {y}}\right)$ evaluates the bit-cost of the compressed representation matching to a decompressed signal $\mathbf {y}\in \mathcal {S}$.

We now turn to define the holographic compression problem in the form of a rate-distortion optimization, posed for improving the average quality of m-packet reconstructions for a specific $m \in \lbrace 2, \ldots ,K\rbrace$. Our initial problem formulation is inspired by the rate-distortion Lagrangian optimization that is commonly used in the state-of-the-art image and video compression methods (see, for examples, [12,13,14,15]). Here, we formulate the task as the minimization of an extended rate-distortion Lagrangian cost, including three main terms: the total compression bit-cost of the packets, the average MSE of m-packet reconstructions (defined for a particular $m \in \lbrace 2, \ldots ,K\rbrace$), and the average MSE of reconstructions from individual packets. This optimization is formulated as

$$\begin{aligned} \lbrace \hat{\mathbf {y}}_i \rbrace _{i=1}^{K}&= \underset{ { \lbrace \mathbf {y}_i \rbrace _{i=1}^{K} \in \mathcal {S} } }{\text {argmin}} ~ \Bigg \{ { \sum \limits _{i=1 }^{K} R\left( \mathbf {y}_i \right) } \nonumber \\&\quad + \mu \frac{1}{ {K \atopwithdelims ()m } } \sum _{ \left( i_1, \ldots , i_m \right) \in { [[{K} ]] \atopwithdelims ()m } } D^{(m)} \left( \mathbf {x}; \mathbf {y}_{i_1} , \ldots , \mathbf {y}_{i_m} \right) \nonumber \\&\quad + \lambda \frac{1}{K} \sum \limits _{i=1}^{K} D^{(1)} \left( \mathbf {x}; \mathbf {y}_i \right) \Bigg \} \end{aligned}$$

(16)

where $\mu$ and $\lambda$ are Lagrange multipliers corresponding to some trade-off among the bit-cost and the distortion quantities. It is important to note that the reduction in the average MSE of m-packet reconstructions usually leads to increase in the average MSE of individual-packet reconstructions. Naturally, reducing the average MSE of m-packet reconstructions means that the individual packets are adapted for their participation in reconstructions with additional $m-1$ packets and, therefore, such a goal imposes (structural) constraints on the individual packets that prevent them from providing the best quality when individually used for 1-packet reconstructions. Therefore, in our experiments (see Sect. 5) we will set the values of $\mu$ and $\lambda$ such that the average MSE of m-packet reconstructions will be the desired distortion value to minimize, and the inclusion of the average MSE of individual-packet reconstructions is for regularization purposes, namely to limit the degradation introduced to single-packet representations. This aspect of the optimization is clearly exhibited in the empirical demonstrations provided in Sect. 5.

We suggest to address the optimization in (16) using the alternating direction method of multipliers (ADMM) approach [16]. For a start, we apply variable splitting on the optimization in (16), translating the problem to

$$\begin{aligned}&\left( \lbrace \hat{\mathbf {y}}_i \rbrace _{i=1}^{K} , \lbrace \hat{\mathbf {z}}_i \rbrace _{i=1}^{K} \right) = \underset{ \begin{array}{c} { \lbrace \mathbf {y}_i \rbrace _{i=1}^{K} \in \mathcal {S} ,}\\ { \lbrace \mathbf {z}_i \rbrace _{i=1}^{K} \in \mathbb {R}^N } \end{array} }{\text {argmin}} \Bigg \{ { \sum \limits _{i=1 }^{K} R\left( \mathbf {y}_i \right) } \nonumber \\&\qquad \qquad + \mu \frac{1}{ {K \atopwithdelims ()m } } \sum _{ \left( i_1, \ldots , i_m \right) \in { [[{K} ]] \atopwithdelims ()m } } D^{(m)} \left( \mathbf {x}; \mathbf {z}_{i_1} , \ldots , \mathbf {z}_{i_m} \right) \nonumber \\&\qquad \qquad + \lambda \frac{1}{K} \sum \limits _{i=1}^{K} D^{(1)} \left( \mathbf {x}; \mathbf {z}_i \right) \Bigg \}\nonumber \\&\text {subject to} ~~ \mathbf {z}_i = \mathbf {y}_i ~~ \forall ~ i \in [[{K} ]] \end{aligned}$$

(17)

where $\mathbf {z}_1, \ldots , \mathbf {z}_K$ are auxiliary variables, which are not directly restricted to the discrete set $\mathcal {S}$. Then, the augmented Lagrangian and the method of multipliers [16] provide an iterative form of the problem where its $t^{th}$ iteration is formulated as

$$\begin{aligned}&\left( \lbrace \hat{\mathbf {y}}_i^{[t]} \rbrace _{i=1}^{K} , \lbrace \hat{\mathbf {z}}_i^{[t]} \rbrace _{i=1}^{K} \right) = \underset{ \begin{array}{c} { \lbrace \mathbf {y}_i \rbrace _{i=1}^{K} \in \mathcal {S} ,}\\ { \lbrace \mathbf {z}_i \rbrace _{i=1}^{K} \in \mathbb {R}^N } \end{array} }{\text {argmin}} \Bigg \{ { \sum \limits _{i=1 }^{K} R\left( \mathbf {y}_i \right) } + \nonumber \\&\quad + \mu \frac{1}{ {K \atopwithdelims ()m } } \sum _{ \left( i_1, \ldots , i_m \right) \in { [[{K} ]] \atopwithdelims ()m } } D^{(m)} \left( \mathbf {x}; \mathbf {z}_{i_1} , \ldots , \mathbf {z}_{i_m} \right) \nonumber \\&\quad + \lambda \frac{1}{K} \sum \limits _{i=1}^{K} D^{(1)} \left( \mathbf {x}; \mathbf {z}_i \right) \nonumber \\&\quad + \beta \sum \limits _{i=1}^{K} \left\| { \mathbf {y}_i - \mathbf {z}_i + \mathbf {u}_i^{[t]} }\right\| _2^2 \Bigg \} \end{aligned}$$

(18)

$$\begin{aligned}&\mathbf {u}_i^{[t+1]} = \mathbf {u}_i^{[t]} + \left( \hat{\mathbf {y}}_i^{[t]} - \hat{\mathbf {z}}_i^{[t]} \right) ~~\forall ~ i \in [[{K} ]] \end{aligned}$$

(19)

where $\beta$ is a parameter originating in the augmented Lagrangian, and $\mathbf {u}_1^{[t]}, \ldots , \mathbf {u}_K^{[t]}$ are scaled dual variables. We denote correspondence to specific iterations using superscript square-brackets, whereas other types of superscripts (e.g., including round brackets) correspond to former definitions given above.

Addressing the optimization in (18) using one iteration of alternating minimization establishes the following ADMM form of the problem, where its $t^{th}$ iteration is

$$\begin{aligned} \hat{\mathbf {y}}_i^{[t]}= & {} \underset{ \mathbf {y}_i \in \mathcal {S} }{\text {argmin}} ~ { R\left( \mathbf {y}_i \right) } + \beta \left\| { \mathbf {y}_i - \tilde{\mathbf {z}}_i^{[t]} }\right\| _2^2 ~~\forall ~ i \in [[{K} ]] \end{aligned}$$

(20)

$$\begin{aligned} \hat{\mathbf {z}}_i^{[t]}= & {} \underset{ \mathbf {z}_i }{\text {argmin}} ~ \Bigg \{ \frac{\mu }{ {K \atopwithdelims ()m } } \times \nonumber \\&\sum _{ \left( i_1, \ldots , i_m \right) \in {\mathcal {I}_i^{(m)}}} D^{(m)} \left( \mathbf {x}; \lbrace \hat{\mathbf {z}}_{i_j}^{[t]} \rbrace _{ \begin{array}{c} {i_j < i} \\ {j\in [[{m} ]] } \end{array} } , \mathbf {z}_{i} , \lbrace \hat{\mathbf {z}}_{i_j}^{[t-1]} \rbrace _{ \begin{array}{c} {i_j > i} \\ {j\in [[{m} ]] } \end{array} } \right) \nonumber \\&+ \frac{\lambda }{K} D^{(1)} \left( \mathbf {x}; \mathbf {z}_i \right) + \beta \left\| { \mathbf {z}_i - \tilde{\mathbf {y}}_i^{[t]} }\right\| _2^2 \Bigg \} ~~\forall ~ i \in [[{K} ]] \end{aligned}$$

(21)

$$\begin{aligned} \mathbf {u}_i^{[t+1]}= & {} \mathbf {u}_i^{[t]} + \left( \hat{\mathbf {y}}_i^{[t]} - \hat{\mathbf {z}}_i^{[t]} \right) ~~\forall ~ i \in [[{K} ]] \end{aligned}$$

(22)

where $\tilde{\mathbf {z}}_i^{[t]} \triangleq \hat{\mathbf {z}}_i^{[t-1]} - \mathbf {u}_i^{[t]}$ and $\tilde{\mathbf {y}}_i^{[t]} \triangleq \hat{\mathbf {y}}_i^{[t]} + \mathbf {u}_i^{[t]}$. Moreover, the optimization of $\mathbf {z}_i$ in (21) considers the average reconstruction MSE corresponding to all the m-combinations of packets including the $i^{th}$ packet —the set of these m-combinations is denoted as $\mathcal {I}_i^{(m)}$. Note also that the size of this set is $|\mathcal {I}_i^{(m)} |= {K-1 \atopwithdelims ()m-1}$.

The tasks in (20) are standard rate-distortion optimizations with respect to a squared error metric, considering the individual compression of $\tilde{\mathbf {z}}_i^{[t]}$ for each $i=1, \ldots ,K$. Therefore, we suggest to replace the optimizations in (20) with applications of standard compression and decompression (codec) operated based on a parameter $\theta \left( \beta \right)$ determining the bit-rate (see stage 8 of Algorithm 1). We do not require the utilized codec to accurately solve the optimization form in (20) and, in turn, this provides us a practical, generic algorithm. While any reasonable codec should aim to balance the trade-off in (20), there are no guarantees on the performance induced by an arbitrarily chosen codec. In our experiments in Sect. 5, we establish the suitability of the JPEG2000 compression technique (applied using a compression-ratio parameter) in conjunction with our method. Interestingly, in our experiments we find it sufficient to set $\theta \left( \beta \right)$ to a constant value (heuristically determined based on the $\beta$ value) and kept fixed throughout the iterations (i.e., $\theta \left( \beta \right)$ is considered to be independent of t). Our decision to keep the value of $\theta \left( \beta \right)$ fixed along the iterations is motivated by the general, common ADMM settings [16] that keep their $\beta$ parameters constant throughout the iterative process.

The second optimization stage, Eq. (21), can be analytically solved with respect to the explicit expressions provided in (15) for the distortion measures, showing that

$$\begin{aligned} \hat{\mathbf {z}}_i^{[t]} = \frac{ N \beta \tilde{\mathbf {y}}_i^{[t]} + \frac{\lambda }{K} \mathbf {S}_i \mathbf {x} + \frac{\mu }{ m^2 \cdot {K \atopwithdelims ()m } } \mathbf {S}_i \mathbf {w}_i^{(m)} }{N \beta + \frac{\lambda }{K} + \frac{\mu }{ m^2 \cdot {K \atopwithdelims ()m } } \cdot {|\mathcal {I}_i^{(m)} |} } \end{aligned}$$

(23)

where

$$\begin{aligned}&\mathbf {w}_i^{(m)} \triangleq \nonumber \\&\sum _{ \left( i_1, \ldots , i_m \right) \in {\mathcal {I}_i^{(m)}}} \left( m \mathbf {x} - \sum \limits _{{ \begin{array}{c} {i_j < i} \\ {j\in [[{m} ]] } \end{array} }} \mathbf {S}_{i_j}^T \hat{\mathbf {z}}_{i_j}^{[t]} - \sum \limits _{{ \begin{array}{c} {i_j > i} \\ {j\in [[{m} ]] } \end{array} }} \mathbf {S}_{i_j}^T \hat{\mathbf {z}}_{i_j}^{[t-1]} \right) . \end{aligned}$$

(24)

The expression in (23) exhibits $\hat{\mathbf {z}}_i^{[t]}$ as a linear combination of the corresponding decompressed packet $\tilde{\mathbf {y}}_i^{[t]}$, the shifted input signal $\mathbf {x}$, and the shifted residual between $\mathbf {x}$ and its m-packet approximations excluding the $i^{th}$ packet. Note that in the case of $m=K$ (namely, optimizing the reconstruction using all the packets), the expression in (24) is somewhat simplified to

$$\begin{aligned} \mathbf {w}_i^{(K)} = K \mathbf {x} - \sum \limits _{j=1}^{i-1} \mathbf {S}_j^T \hat{\mathbf {z}}_j^{[t]} - \sum \limits _{j=i+1}^{K} \mathbf {S}_j^T \hat{\mathbf {z}}_j^{[t-1]} . \end{aligned}$$

(25)

The method developed in this section is summarized in Algorithm 1, where the processing of packets in each iteration is done sequentially. This reordering of computations is allowed due to the formation of dependencies obtained in Eq. (20)–(22).

5 Experimental Results

In this section, we present experimental results for the implementation of the proposed method for holographic compressed representations of images in conjunction with the JPEG2000 compression technique (available in Matlab). In the presented evaluation, we consider several settings for the storage of a given image using four copies (that are not necessarily identical) or packets. Each packet/copy is a compressed image in a binary form obtained from the JPEG2000 compression method operated at the same compression ratio. Therefore, all the individual copies and packets are of about the same bit-rate, allowing to evaluate reconstruction quality as the function of the number of packets/copies utilized. The four approaches examined here are:

• Exact duplication where all the stored copies are exactly the same binary data, obtained from the JPEG2000 compression of the given image.

• The baseline (unoptimized) design, as presented in Sect. 3, relying on JPEG2000 compression of different shifts of the input image.

• The shift-based holographic compression approach optimized for 2-packet reconstructions as developed in Sect. 4 for optimizing the quality of m-packet reconstructions. This design also relies on the JPEG2000 compression standard. The parameters for this mode are $\mu = 25\cdot \frac{K^2}{m}$, $\beta = \frac{90}{N}$, $\lambda = 5\cdot K^2$, and a run of 35 iterations.

• The shift-based holographic compression approach optimized for K -packet reconstructions, namely, the case of optimizing the reconstruction using all the packets. The parameters for this mode are $\mu = 125\cdot \frac{K^2}{m}$, $\beta = \frac{50}{N}$, $\lambda = 2.5 \cdot K^2$, and a run of 35 iterations.

In the above specified settings, we use $\lambda$ values that are significantly lower than the utilized $\mu$ values. This is in accordance with our goal of minimizing the average MSE of m-packet reconstructions (that its importance is expressed by the value of $\mu$) while the average MSE of individual-packet reconstructions is considered for regularization purposes (that their strength is determined by the value of $\lambda$). As in many contemporary proof-of-concept algorithms that rely on ADMM (or other iterative optimization methods), we set the parameter values based on empirical observations of the resulting performance. The problem of automatic tuning of parameters in ADMM optimization forms is a general topic of contemporary interest (for example, in the context of inverse problems, see [17]).

The first evaluation is based on JPEG2000 compression at a compression ratio of 1:50 that in practice creates packets at bit-rates of 0.160 bits per pixel (bpp), with the addition of some overhead bit-rate due to syntax of JPEG2000 [18] (note that the overhead bit-rate due to JPEG2000 bit-stream headers, see [18], is smaller for larger images). The baseline and the two optimized modes produce their four holographic packets based on the following offsets of the upper-left coordinate of the image by (0, 0), (3, 0), (0, 3), (3, 3) pixels. Namely, in practice, the shifts are not cyclic and implemented by appending a suitable number of duplicated rows and columns at the upper and left sides of the image, respectively. Our choice in non-cyclic shifts is due to the significant discontinuities in pixel values that occur in cyclically shifted versions of natural images, which may affect the JPEG2000 performance due to its transform coding of big blocks of pixels. The utilized shifts are induced by non-adaptive offsets that are predefined in the compression and decompression processes. Therefore, there is no bit-rate overhead for encoding the shift offsets. The evolution of the optimization cost (formulated in Eq. (16)) and its components is demonstrated in Figs. 3, showing the reduction in the optimization cost (the blue curve) and a convergence behavior.

Fig. 3

The evolution of the optimization cost and its components throughout the proposed iterative optimization. The demonstration here is for the Cameraman image and the optimization of 4-packet reconstruction composed of JPEG2000 packets having compression ratio of 1:50. The presented values of the cost-components include the multiplication by the respective parameters

In Fig. 4, we demonstrate the reconstructions obtained using the proposed holographic compression method optimized for 4-packet reconstructions. First, in Fig. 4a–4d, we present the reconstructions retrieved from each of the single packets alone: while the PSNR values are relatively similar, the approximations are clearly distinct and each of them suffers differently from compression artifacts. This observation explains the benefits from jointly using several packets for reconstruction. Then, in Fig. 4e–g, several examples for approximations using an increasing number of packets show the significance of the obtained improvements in PSNR and visual quality.

Figure 5 allows to compare the examined methods through their corresponding curves of PSNR versus number of packets utilized for reconstruction. The results provided here are for the Cameraman (256$\times$ 256 pixels), Lena (512$\times$ 512 pixels) and Barbara (512$\times$ 512 pixels) grayscale images. We also considered the House (256$\times$ 256 pixels) grayscale image, see summary in Table 1. Each of the four examined methods is associated in Fig. 5 with a group of curves having the same color (which is method specific). The curves corresponding to a particular method differ by the order of appending packets for the reconstruction (and, therefore, the number of curves corresponding to each method is $K! = 4! = 24$). A good implementation of the holographic property of similar usefulness (see Sect. 2) means here that the diversity in PSNR values using the various combinations of m packets should be relatively small–we quantify this in Table 1 using the standard deviation of the PSNR obtained using the various subsets of m packets. The second important property is the progressive refinement (see Sect. 2) that can be observed in the PSNR curves of all the shift-based holographic compression methods (see Fig. 5) and is completely absent in the exact duplication approach. It is also evident that our optimization framework improves the average PSNR of the m-packet reconstructions for the specific m set to be optimized (see Table 1 and Fig. 5). For instance, our optimization for 4-packet reconstructions achieved a PSNR gain of about 5 dB over the method of exact duplications, and a PSNR improvement around 3 dB over the baseline (unoptimized) shift-based approach.

Fig. 4

Examples for m-packet reconstructions of the ’Cameraman’ image using multiple packets from the set of 4 holographic representations. Demonstration of m-packet reconstructions obtained from a set of 4 holographic packets optimized by the proposed framework for a 4-packet reconstruction. The utilized compression is JPEG2000 at a compression ratio of 1:50. The cyan-colored boxes show zoomed-in blocks of the respective results. a–d The 1-packet reconstructions using each of the individual packets. e–g Examples for the m-packet reconstructions for $m=2,3,4$

Fig. 5

PSNR versus the number of packets used for the reconstructions. The complete set contains 4 packets, each obtained from JPEG2000 compression at 1:50 compression ratio. The black, red, green and blue curves, respectively, represent the methods of exact duplications, baseline (unoptimized), optimized for reconstruction from pairs of packets, and optimized for reconstruction from 4 packets

The presented comparison also demonstrates the fundamental, intuitive, trade-off in the average quality of m-packet reconstructions among the various subset sizes m. For example, the significant increase in the 4-packet reconstruction quality is at the expense of the qualities of the 1-packet reconstructions. Nonetheless, the optimizations for reconstructions using 4 or 2 packets indirectly led to significant improvement in the average quality of the 3-packet reconstructions in addition to the explicit optimization goal.

Table 1 Evaluation of quality and diversity in the reconstructions from a set of 4 packets (the mean and SD values refer to PSNR values in dB units): the results are based on JPEG2000 compression at 1:50 compression ratio

Fig. 6

PSNR versus the number of packets used for the reconstructions. The complete set contains 4 packets, each obtained from JPEG2000 compression at 1:25 compression ratio. The black, red, green and blue curves, respectively, represent the methods of exact duplications, baseline (unoptimized), optimized for reconstruction from pairs of packets, and optimized for reconstruction from 4 packets

Table 2 Evaluation of quality and diversity in the reconstructions from a set of 4 packets (the mean and SD values refer to PSNR values in dB units): the results are based on JPEG2000 compression at 1:25 compression ratio

Fig. 7

PSNR versus the number of packets used for the reconstructions. The complete set contains 9 packets, each obtained from JPEG2000 compression at 1:50 compression ratio. The black, red, green and blue curves, respectively, represent the methods of exact duplications, baseline (unoptimized), optimized for reconstruction from pairs of packets, and optimized for reconstruction from 9 packets

Table 3 Evaluation of quality and diversity in the reconstructions from a set of 9 packets (the mean and SD values refer to PSNR values in dB units): the results are based on JPEG2000 compression at 1:50 compression ratio.   This table presents the mean and standard deviation for reconstructions using 1, 2, 3 and 9 packets. The corresponding properties for reconstructions based on 4, 5, 7 and 8 packets can be coarsely examined using the curves in Fig. 7

Fig. 8

Examples for m-packet reconstructions of the ’Barbara’ image using multiple packets from the set of 9 holographic representations. Demonstration of m-packet reconstructions obtained from a set of 9 holographic packets optimized by the proposed framework for a 9-packet reconstruction. The utilized compression is JPEG2000 at a compression ratio of 1:50. The cyan-colored boxes show zoomed-in blocks of the respective results

We repeat the experiment but for JPEG2000 compression at a ratio of 1:25, namely a higher bit-rate of approximately 0.320 bits per pixel. The formulas for setting the parameters are as in the first setting described above, except for the $\beta$ parameter, set in the 4-packet optimization mode to $\frac{65}{N}$, and in the 2-packet optimization mode to $\frac{120}{N}$. The results are presented in Table 2 and Fig.6. Evidently, our framework consistently provides improved qualities of the reconstructions specified in the optimization task.

In addition, we also examine the case where the complete set of representations includes 9 packets (and the JPEG2000 compression ratio is 1:50). In this case, the shifts are based on offsets of the upper-left coordinate of the image by $(3\Delta _x,3\Delta _y)$ pixels for all $\Delta _x,\Delta _y \in \left\{ 0,1,2 \right\}$. The formulas for setting the parameters are as in the first setting described above, except for the $\lambda$ parameter in the 2-packet optimization mode that is now set to $K^2$. The comparison presented in Fig. 7 and Table 3 demonstrates the improvements in PSNR achievable using the proposed optimization framework. In Fig. 8, we visually demonstrate the progressive refinement when increasing the number of packets utilized.

All the methods compared in Tables 1, 2, 3 are based on multiple compressed packets with the same individual bit-rate. Obviously, compression methods that are not intended for distributed representations are likely to outperform the approach proposed in this paper. As an example for such (unfair) comparison, consider JPEG2000 compression results of the Cameraman image at a bit-rate equivalent to the total bit-rate of the multiple packets in distributed settings: 25.66 dB at 1:50 compression ratio (which corresponds to an equivalent bit-rate of 1 packet in Table 1), 28.86 dB at 1:25 compression ratio (which corresponds to a bit-rate equivalent to using 2 packets in Table 1), 30.91 dB at 1:16.7 compression ratio (which corresponds to a bit-rate equivalent to using 3 packets in Table 1), and 32.50 dB at 1:12.5 compression ratio (which corresponds to a bit-rate equivalent to using 4 packets in Table 1).

6 Conclusion

In this paper, we proposed a new methodology for signal and image compression, intended for systems where compressed data are often trivially duplicated in exact forms. Our idea relies on the concept of holographic representations that are equally descriptive and useful for progressive refinement of the reconstructed signal. Based on the shift-sensitivity of signal compression techniques, we developed a baseline and an ADMM-based optimized framework for the construction of binary compressed representations compatible with standard compression techniques. Our experiments clearly demonstrate the effectiveness of the proposed framework, reaching remarkable improvements in the reconstruction quality over the approach of using exact duplications. Future work can further develop the proposed approach to simultaneously optimize several (more than two) sizes of packet subsets. More general future directions can extend the proposed framework for optimizing holographic compression based on projection operators other than shifts. Moreover, the guidelines established here for optimized holographic compression can be generalized further to holographic representations using various regularization types, replacing the role of the bit-cost measures in this paper. While we demonstrated our idea for image compression, one can explore the adaptation of our framework for other signal types (such as audio and video) also used in conjunction with lossy compression.