Secrecy by Design With Applications to Privacy and Compression

Secrecy by design is examined as an approach to information-theoretic secrecy. The main idea behind this approach is to design an information processing system from the ground up to be perfectly secure with respect to an explicit secrecy constraint. The principal technical contributions are decomposition bounds that allow the representation of a random variable X as a deterministic function of (S,Z) , where S is a given fixed random variable and Z is constructed to be independent of S . Using the problems of privacy and lossless compression as examples, the utility cost of applying secrecy by design is investigated. Privacy is studied in the setting of the privacy funnel function previously introduced in the literature and new bounds for the regime of zero information leakage are derived. For the problem of lossless compression, it is shown that strong information-theoretic guarantees can be achieved using a reduced secret key size and a quantifiable penalty on the compression rate. The fundamental limits for both problems are characterized with matching lower and upper bounds when the secret S is a deterministic function of the information source X .

Oligoquantization in low-rate lossy source coding

The theory of high rate lossy source coding is well developed both with respect to the practice of quantization and its fundamental rate distortion limits. But many modern compression systems for natural signals such as audio and images operate at lower rates, which are not covered by these theories. Often these systems are based on a signal transform followed by a nonlinear processing step that reduces the number of coefficients that are actually quantized. Both this nonlinearity and the non-Gaussianity of the involved signals rule out using the theory of (high rate) linear transform coding to analyze such compression algorithms. The lossy source coding theorem could be used, but it is not the right tool "to see what happens". Another way of getting a better understanding of these systems is to look at them as a form of nonlinear approximation of individual signals. While partly avoiding the need for statistical signal models that are hard to come by, this approach still relies on high rate results for the coefficient quantization. In this thesis we take a more information theoretic approach, whose main result is a new low-rate upper bound on the distortion rate function. In order to obtain that result, the problem had to be simplified substantially. To begin with, only i.i.d. memoryless sources with a mean square error distortion measure are considered. Instead of bounding the distortion rate function D(R) directly, we derive upper bounds on the optimum performance of a certain class of quantizers, which by definition upper bound also D(R). Inspired by the observation that many of those compression systems quantize only very few coefficients at low rates, we called this the class of oligoquantizers. In particular, if the coefficients have a peaked unimodal probability density, a simple magnitude thresholding operation is very effective at deciding which coefficients should be quantized. It turns out that peaked unimodal densities are also the most interesting ones, not just because they appear in many transform coding systems, but also because they have a D(R) behavior that is very different from a Gaussian. Thus the emphasis of this work will be on oligoquantization based on scalar thresholding. Actually we will show that the principle of oligoquantization does not generalize well to higher dimensions. On a more applied note, we analyze several models for sparse transform coefficients with the aid of the low rate bound. For the special case of sparse coefficient vectors and Hamming distortion measure, analytic expressions for R(D) are obtained. A high rate bound that complements its low rate counterpart is also derived. Finally, we show how these bounds can be computed directly from a set of source samples, without first estimating the underlying probability density. These empirical bounds can be a useful complement to the rate distortion function computed with Blahut's algorithm, since the latter is hard to use at very low or high rates.

EPFL2002

Visual feature analysis for audio-visual speech recognition

Ivana Arsic de Heras Ciechomska

Humans perceive their surrounding environment in a multimodal manner by using multi-sensory inputs combined in a coordinated way. Various studies in psychology and cognitive science indicate the multimodal nature of human speech production and perception. Such findings have motivated the development of a new and fast growing research field of audio-visual speech processing. Exhaustive research done so far shows that systems using both visual and acoustic data do perform better than their conventional "blind" counterparts. The choice of suitable visual cues is of paramount importance in such systems. The aim of this thesis is to analyze visual features and evaluate their relevance from an automatic speech recognition point of view. Speech pertinent information is mainly conveyed in the mouth area and a fundamental requirement is to obtain its representation in a parameterized form. The first objective of this work is to address the problem of visual front end design. This represents a challenging issue that involves complex computer vision tasks of face detection and facial feature tracking. After finding the speaker's face, it is important to accurately detect the mouth area and subsequently track it throughout a video sequence. In this thesis a method for nose and mouth region of interest tracking, has been developed for the application scenario restricted to audio-visual speech recognition. Nose tracking is accomplished by employing a template matching technique. Further on, the mouth region is localized taking into account knowledge of geometric properties of the human face. The next objective of this work is set upon the need for robust and accurate extraction of key lip points of interest. To accomplish such a task two novel algorithms are developed. The first one aims to find four key lip points that enable normalization of mouth images. The second algorithm provides additional mouth shape descriptors and the basis for fitting labial contours. The emphasis of this study is on audio-visual speech recognition which requires visual features suitable for classification. A question that immediately arises is what the most speech salient features are. To date different methods are proposed that mainly rely on some a priori defined rules. Area based features are selected based on criteria inherited from image compression, where geometric based methods use set of cues selected as meaningfull one for humans. There is no guarantee that such representations are optimal for automatic recognition of the uttered speech. The study done in this thesis aims to observe this problem from a different angle by including basic information theoretic concepts in visual feature analysis. The selection criteria employs Mutual Information as a measure of how informative visual cues are. The concept of mutual information eigenlips is introduced to reflect the most informative eigenfeatures. Visual features obtained using an information theoretic framework are further used for audio-visual speech recognition experiments. The obtained results indicate improved system performance when such visual cues are applied. In conclusion, the proposed information theoretic framework for visual feature selection can be applied in other audio-visual speech processing areas. The possible applications include audio-visual speaker detection and speaker localization.

EPFL2008

Selected topics on distributed video coding

Mourad Ouaret

Distributed Video Coding (DVC) is a new paradigm for video compression based on the information theoretical results of Slepian and Wolf (SW), and Wyner and Ziv (WZ). While conventional coding has a rigid complexity allocation as most of the complex tasks are performed at the encoder side, DVC enables a flexible complexity allocation between the encoder and the decoder. The most novel and interesting case is low complexity encoding and complex decoding, which is the opposite of conventional coding. While the latter is suitable for applications where the cost of the decoder is more critical than the encoder's one, DVC opens the door for a new range of applications where low complexity encoding is required and the decoder's complexity is not critical. This is interesting with the deployment of small and battery-powered multimedia mobile devices all around in our daily life. Further, since DVC operates as a reversed-complexity scheme when compared to conventional coding, DVC also enables the interesting scenario of low complexity encoding and decoding between two ends by transcoding between DVC and conventional coding. More specifically, low complexity encoding is possible by DVC at one end. Then, the resulting stream is decoded and conventionally re-encoded to enable low complexity decoding at the other end. Multiview video is attractive for a wide range of applications such as free viewpoint television, which is a system that allows viewing the scene from a viewpoint chosen by the viewer. Moreover, multiview can be beneficial for monitoring purposes in video surveillance. The increased use of multiview video systems is mainly due to the improvements in video technology and the reduced cost of cameras. While a multiview conventional codec will try to exploit the correlation among the different cameras at the encoder side, DVC allows for separate encoding of correlated video sources. Therefore, DVC requires no communication between the cameras in a multiview scenario. This is an advantage since communication is time consuming (i.e. more delay) and requires complex networking. Another appealing feature of DVC is the fact that it is based on a statistical framework. Moreover, DVC behaves as a natural joint source-channel coding solution. This results in an improved error resilience performance when compared to conventional coding. Further, DVC-based scalable codecs do not require a deterministic knowledge of the lower layers. In other words, the enhancement layers are completely independent from the base layer codec. This is called the codec-independent scalability feature, which offers a high flexibility in the way the various layers are distributed in a network. This thesis addresses the following topics: First, the theoretical foundations of DVC as well as the practical DVC scheme used in this research are presented. The potential applications for DVC are also outlined. DVC-based schemes use conventional coding to compress parts of the data, while the rest is compressed in a distributed fashion. Thus, different conventional codecs are studied in this research as they are compared in terms of compression efficiency for a rich set of sequences. This includes fine tuning the compression parameters such that the best performance is achieved for each codec. Further, DVC tools for improved Side Information (SI) and Error Concealment (EC) are introduced for monoview DVC using a partially decoded frame. The improved SI results in a significant gain in reconstruction quality for video with high activity and motion. This is done by re-estimating the erroneous motion vectors using the partially decoded frame to improve the SI quality. The latter is then used to enhance the reconstruction of the finally decoded frame. Further, the introduced spatio-temporal EC improves the quality of decoded video in the case of erroneously received packets, outperforming both spatial and temporal EC. Moreover, it also outperforms error-concealed conventional coding in different modes. Then, multiview DVC is studied in terms of SI generation, which differentiates it from the monoview case. More specifically, different multiview prediction techniques for SI generation are described and compared in terms of prediction quality, complexity and compression efficiency. Further, a technique for iterative multiview SI is introduced, where the final SI is used in an enhanced reconstruction process. The iterative SI outperforms the other SI generation techniques, especially for high motion video content. Finally, fusion techniques of temporal and inter-view side informations are introduced as well, which improves the performance of multiview DVC over monoview coding. DVC is also used to enable scalability for image and video coding. Since DVC is based on a statistical framework, the base and enhancement layers are completely independent, which is an interesting property called codec-independent scalability. Moreover, the introduced DVC scalable schemes show a good robustness to errors as the quality of decoded video steadily decreases with error rate increase. On the other hand, conventional coding exhibits a cliff effect as the performance drops dramatically after a certain error rate value. Further, the issue of privacy protection is addressed for DVC by transform domain scrambling, which is used to alter regions of interest in video such that the scene is still understood and privacy is preserved as well. The proposed scrambling techniques are shown to provide a good level of security without impairing the performance of the DVC scheme when compared to the one without scrambling. This is particularly attractive for video surveillance scenarios, which is one of the most promising applications for DVC. Finally, a practical DVC demonstrator built during this research is described, where the main requirements as well as the observed limitations are presented. Furthermore, it is defined in a setup being as close as possible to a complete real application scenario. This shows that it is actually possible to implement a complete end-to-end practical DVC system relying only on realistic assumptions. Even though DVC is inferior in terms of compression efficiency to the state of the art conventional coding for the moment, strengths of DVC reside in its good error resilience properties and the codec-independent scalability feature. Therefore, DVC offers promising possibilities for video compression with transmission over error-prone environments requirement as it significantly outperforms conventional coding in this case.

EPFL2008

Selected topics on distributed video coding

Mourad Ouaret

EPFL2008

Oligoquantization in low-rate lossy source coding

EPFL2002

Visual feature analysis for audio-visual speech recognition

Ivana Arsic de Heras Ciechomska

EPFL2008