- Information Theory
- Multimedia Compression
- Distributed Source Coding
- Digital Watermarking and Information Hiding
- Interactive Encoding-Decoding
Information theory is generally considered to have been founded in 1948 by Claude Shannon in his seminal work, "A Mathematical Theory of Communication.", which is a branch of applied mathematics and electrical engineering involving the quantification of information. Applications of fundamental topics of information theory include lossless data compression, lossy data compression, and channel coding. In multicom research lab, we are focus on the following research areas: Data Compression, Distributed Source Coding, Interactive Encoding and Decoding, and Digital Watermarking and Information Hiding.
Coming soon ....
Current Researchers: Krzysztof Hebel
[Research Top]
In conventional multimedia coding algorithms, as standardized by MPEG, the
encoder exploits the statistics of the source signal. This principle seems so
fundamental that it has been rarely questioned until the recent emergence of
wireless sensor networking technology. Wireless sensors, which are usually
mission driven and application specific, are expected to operate under severe
life energy limit in contrast to many prevailing wireless devises, such as
mobile phones, PDAs and laptops, in which energy can be recharged from time to
time. This energy constraint of wireless sensors also limits their information
processing capability, which gives rise to the research efforts to shift the
computation burden at conventional source encoder to decoder. The key technology
enabling this shift is distributed source coding (DSC).
In a DSC system, multiple correlated sources are encoded independently, while
efficient compression can also be achieved by exploiting source statistics
solely at the decoder. Although Slepian and Wolf, Wyner and Ziv established the
information-theoretic analysis for distributed lossless coding and lossy coding
respectively in the 1970s, it was only in the last few years that practical
coding schemes are attempted. Most DSC techniques today are derived from proven
channel coding ideas. Specifically, state-of-the-art Slepian-Wolf coding schemes
mainly employ sophisticated channel codes, such as turbo codes and LDPC codes,
to model the source correlations; and state-of-the-art Wyner-Ziv coding schemes
focus on the joint design of quantizer and Slepian-Wolf encoder.
Although channel codes-based approaches are shown to achieve compression
performance near theoretic limits for both Slepian-Wolf coding and Wyner-Ziv
coding, their code design relies on the correlation model, which is usually
unknown at the encoder, or even at the decoder, in practice. Very recently, Yang
et.al. proposed the initial work on universal DSC. In order to drop the
assumption of knowing the correlation model a prior, a feedback channel is
constructed from decoder to encoder, so that they could cooperate in string
matching based on a shared random database, which is independent of all sources.
The compression ratio goes to the theoretical limit as if the encoder knows the
correlation model beforehand asymptotically, and the feedback rate goes to 0
asymptotically. Germinated by this work, we are currently investigating issues
in the DSC paradigm as follows.
-
Universal scheme that uses a feedback channel to guide the encoding decisions is not suitable for encoder-alone applications where the source signals are encoded and stored for future use. Can we come up with a universal coding scheme that has no communication with the decoder?
-
Although it's proved that the universal scheme applies to a large class of sources, its performance on real-life multimedia signals needs to be further obtained and analyzed. And to put this work in a source coding scenario, can we design other efficient universal algorithms that have less redundancy? This reminds us the dual development history of traditional source coding algorithms in the past half century, in which Huffman codes, Lempel-Ziv codes, arithmetic codes and Grammer-based codes came in a line.
-
Universal distributed lossless codes can certainly be incorporated in lossy coding cases with quantization schemes, like LDPC-based Slepian-Wolf coding already did. And consequently, joint design of universal distributed lossless coding algorithms and quantization needs to be conducted, and the comparison of these two approaches should be addressed.
All in all, DSC is a brand new research area and its applications offer a unique opportunity to revisit and extend techniques of conventional source coding under the new paradigm.
Current Researchers: Jin Meng, Lin Zheng
Digital Watermarking and Information Hiding
As digital multimedia works (video, audio and images) become available for retransmission, reproduction, and publishing over the Internet, a real need for protection against unauthorized copy and distribution is increased. These concerns motivate researchers to find ways to forbid copyright violation. The most promising solution for this challenging problem seems to lie in information hiding techniques. Information hiding is the process of embedding a message into digital media. The embedded message should be imperceptible; in addition to that the fidelity of digital media must be maintained. Information hiding is unlike cryptography. In cryptographic techniques significant information is encrypted so that only the key holder has access to that information, once the information is decrypted the security is lost. In information hiding, message is embedded into digital media, which can be distributed and used normally. Information hiding does not limit the use of digital data. In digital watermarking, one embeds a watermark into a host signal, resulting in a watermarked signal. The watermark is in general embedded in such a way that it is robust to certain distortion caused by either standard data processing in a friendly environment or malicious attacks in an unfriendly environment. In addition to the robustness, there are two other conflicting requirements a good watermarking system should meet: on one hand, the watermarked signal should be perceptually similar to the original signal, that is, the distortion incurred to the original signal should be small; and on the other hand, the amount of information embedded - the embedding rate - should be as high as possible. To a large extent, digital watermarking is a science and/or art aiming to design watermarking systems meeting these three conflicting requirements. Germinated by the current applications, we are investigating issues in watermarking as follows:
- In most applications, watermarked signals will be likely stored and/or transmitted in compressed format. So instead of treating watermarking and compression separately, we now focus on joint design of watermarking and compression schemes i.e. joint design of watermarking with current compression standards.
- From an information theoretic viewpoint, a joint compression and watermarking system against malicious attackers, is usually modeled as a game between hider and attacker. So a major research problem on digital watermarking is to determine best tradeoffs among the distortion between the covertext and stegotext, the distortion between the stegotext and forgery, the watermark embedding rate, the compression rate and the robustness of the stegotext using game theory. Along this direction, some information theoretic results, such as watermarking capacities and watermarking error exponents and joint compression and watermarking rate regions, need to be determined.
Current Researchers: Yuhan Zhou,
Interactive Encoding and Decoding
The Communication is interactive in essence. This fact is not only seen in all kinds of communications between people, but also many communication protocols like TCP-IP.
Interactive communication for lossless compression with side information only at encoder was first considered by Orlitsky. In his setup, the decoder with side information Y tries to learn X available at encoder in two-way transmission, where X has to be reconstructed at decoder with no probability of error. Note that the requirement of reconstruction is stricter than Slepian Wolf case, where probability of error goes to 0 asymptotically with block length. Therefore, the rate in this setup is higher than Slepian Wolf case. Meanwhile, the idea of incremental encoding is introduced into asymmetrical SW coding by Feder and Shulman, where they consider the scenario that one common source is broadcast to several receivers with different side information. Coupling incremental encoding with universal fix-rate SW coding scheme proposed by Csiszar and Korner, Draper built a universal SW coding scheme. However, as the universal coding scheme by Csiszar and Korner is only for memoryless source pairs, so is the Draper's scheme.
Recently, the concept of interactive encoding and decoding (IED) was formalized by Professor Yang and Doctor He. A special case of IED for (near) lossless one way learning (or in other words, lossless source coding) with decoder only side information is presented here, where X denotes a finite alphabet source to be learned at the decoder, Y denotes another finite alphabet source that is correlated with X and is only available to the decoder as the side information, and R denotes the average number bits per symbol exchanged between the encoder and the decoder measuring the performance of the IED scheme used. In view of the description, we see that the main difference between IED and non-interactive Slepian-Wolf coding lies in that IED allows the encoder and the decoder to interact until the learning (or source coding) task is accomplished.
Several important results concerning IED for (near) lossless source coding with decoder only side information were established by Professor Yang and Doctor He. Specifically, in comparison to non-interactive Slepian-Wolf coding, it was shown that IED not only delivers better first-order (asymptotic) performance for general stationary, non-ergodic source-side information pairs, but also achieves better second-order performance for memoryless pairs with known statistics. Furthermore, in contrast to the well known fact that universal Slepian-Wolf coding does not exist, it was shown that coupled with classical universal lossless codes, one can build IED schemes that are truly universal in the sense that they are asymptotical optimal with respect to the class of all stationary, ergodic sources-side information pairs.
Inspired by the fundamental result above, a natural question is how to design a practical IED scheme to achieve the performance promised by those results. Moreover, how about lossy data compression cases? Therefore this part of research will focus on:
- How to design a practical IED scheme with low complexity of both encoding and decoding, and universal for any statistics of sources?
- How to extend the IED scheme to lossy data compression case like Wyner-Ziv problem?
Current Researchers: Jin Meng,
Copyright 2004-2010 Multicom Research Lab.
Currently Maintained by Jin Meng
Design by Marta Sitek
Last updated on May 20, 2010
