Error Correction and Concealment of Block Based, Motion-Compensated Temporal Prediction, Transform Coded Video David L. Robie 133 Pages Directed by Dr. Russell M. Mersereau The use of the Internet and wireless networks to bring multimedia to the consumer continues to expand. The transmission of these products is always subject to corruption due to errors such as bit errors or lost and ill-timed packets; however, in many cases, such as real time video transmission, retransmission request (ARQ) is not practical. Therefore receivers must be capable of recovering from corrupted data. Errors can be mitigated using forward error correction in the encoder or error concealment techniques in the decoder. This thesis investigates the use of forward error correction (FEC) techniques in the encoder and error concealment in the decoder in block-based, motion-compensated, temporal prediction, transform codecs. It will show improvement over standard FEC applications and improvements in error concealment relative to the Motion Picture Experts Group (MPEG) standard. To this end, this dissertation will describe the following contributions and proofs-of-concept in the area of error concealment and correction in block-based video transmission. A temporal error concealment algorithm which uses motion-compensated macroblocks from previous frames. A spatial error concealment algorithm which uses the Hough transform to detect edges in both foreground and background colors and using directional interpolation or directional filtering to provide improved edge reproduction. A codec which uses data hiding to transmit error correction information. An enhanced codec which builds upon the last by improving the performance of the codec in the error-free environment while maintaining excellent error recovery capabilities. A method to allocate Reed-Solomon (R-S) packet-based forward error correction that will decrease distortion (using a PSNR metric) at the receiver compared to standard FEC techniques. Finally, under the constraints of a constant bit rate, the tradeoff between traditional R-S FEC and alternate forward concealment information (FCI) is evaluated. Each of these developments is compared and contrasted to state of the art techniques and are able to show improvements using widely accepted metrics. The dissertation concludes with a discussion of future work.

<p>The aim of source coding is to represent information as accurately as possible using as few bits as possible and in order to do so redundancy from the source needs to be removed. The aim of channel coding is in some sense the contrary, namely to introduce redundancy that can be exploited to protect the information when being transmitted over a nonideal channel. Combining these two techniques leads to the area of joint source–channel coding which in general makes it possible to achieve a better performance when designing a communication system than in the case when source and channel codes are designed separately. In this thesis two particular areas in joint source–channel coding are studied: multiple description coding (MDC) and soft decoding. Two new MDC schemes are proposed and investigated. The first is based on sorting a frame of samples and transmitting, as side-information/redundancy, an index that describes the resulting permutation. In case that some of the transmitted descriptors are lost during transmission this side information (if received) can be used to estimate the lost descriptors based on the received ones. The second scheme uses permutation codes to produce different descriptions of a block of source data. These descriptions can be used jointly to estimate the original source data. Finally, also the MDC method multiple description coding using pairwise correlating transforms as introduced by Wang et al is studied. A modification of the quantization in this method is proposed which yields a performance gain. A well known result in joint source–channel coding is that the performance of a communication system can be improved by using soft decoding of the channel output at the cost of a higher decoding complexity. An alternative to this is to quantize the soft information and store the pre-calculated soft decision values in a lookup table. In this thesis we propose new methods for quantizing soft channel information, to be used in conjunction with soft-decision source decoding. The issue on how to best construct finite-bandwidth representations of soft information is also studied.</p>

Linear programming (LP) decoding of low-density parity-check codes was introduced by Feldman et al. in [1]. In his formulation it is assumed that communication takes place over a memoryless channel and that the source is uniform. Here, we extend the LP decoding paradigm by studying its application to scenarios with source non-uniformity and to decoding over channels with memory. We develop two decoders for the scenario of non-uniform memoryless sources transmitted over memoryless channels. The first decoder uses a modified linear cost function which incorporates the a-priori source information and works with systematic codes. The second decoder differs by using non-systematic codes obtained by puncturing lower rate systematic codes and using an “extended decoding polytope.” Simulations show that the modified decoders yield gains over the standard LP decoder. Next, LP decoding is considered for two channels with memory: the binary additive Markov noise channel and the infinite-memory non-ergodic Polya-contagion channel. For the Markov channel, no linear cost function corresponding to maximum likelihood (ML) decoding could be obtained and hence it is unclear how to proceed. For the Polya channel, two LP-based decoders are developed. The first is derived in a straightforward manner from the ML decoding rule of [2]. The second decoder relies on a simplification of the same ML decoding rule which holds for codes containing the all-ones codeword. Simulations are performed for both decoders with regular and irregular LDPC codes and demonstrate relatively good performance with respect to the channel epsilon-capacity. / Thesis (Master, Mathematics & Statistics) -- Queen's University, 2008-12-08 16:24:43.358

This thesis studies cooperative sensing and transmission in the context ofwireless sensor networks (WSNs). We especially focus on two means of cooperative sensing and transmission, namely, distributed source coding and relaying. We consider systems where the usefulness of the measured data is dependent on how old the data is and we therefore need low-delay transmission schemes. At first sight, the low-delay criterion may seem to be of little relevance, but it is this aspect in particular that distinguishes this thesis from many of the existing communication theoretic results, which often are asymptotic in the block lengths. The thesis is composed of an introductory part, discussing the fundamentals of communication theory and how these are related to the requirements of WSNs, followed by a part where the results of the thesis are reported in Papers A-H. Papers A-D study different scenarios for distributed source-channel coding. In Paper A, we consider transmission of correlated continuous sources and propose an iterative algorithm for designing simple and energy-efficient sensor nodes. In particular the cases of the binary symmetric channel as well as the additive white Gaussian noise channel are studied. In Paper B, the work is extended to channels with interference and it is shown that also in this case there can be significant power savings by performing a joint optimization of the system.Papers C and D use a more structured approach and propose side-information-aware source-channel coding strategies using lattices and sinusoids. In Paper E, we apply the methods we have used in joint source-channel coding to the famous Witsenhausen counterexample. By using a relatively simple iterative algorithm, we are able to demonstrate the best numerical performance known to date. For the case of systems with relays, we study the transmission of a continuous Gaussian source and the transmission of an uniformly distributed discrete source. In both situations, we propose algorithms to design low-delay source-channel and relay mappings. By studying the structure of the optimized source-channel and relay mappings, we provide useful insights into how the optimized systems work. These results are reported in Papers F and G. In Paper H, we finally consider sum-MSE minimization for the Gaussian multiple-input, multiple-output broadcast channel. By using recently discovered properties of this problem, we derive a closed-form expression for the optimal power allocation in the two-user scenario and propose a conceptually simple and efficient algorithm that handles an arbitrary number of users. Throughout the thesis we show that there are significant gains if the parts of the system are jointly optimized for the source and channel statistics. All methods that are considered in this thesis yield very low coding and decoding delays. In general, nonlinear mappings outperform linear mappings for problems where there is side-information available. Another contribution of this thesis is visualization of numerically optimized systems that can be used as inspiration when structured low-delay systems are designed. / The author changed name from Johannes Karlsson to Johannes Kron in January 2011. QC 20110512

The aim of source coding is to represent information as accurately as possible using as few bits as possible and in order to do so redundancy from the source needs to be removed. The aim of channel coding is in some sense the contrary, namely to introduce redundancy that can be exploited to protect the information when being transmitted over a nonideal channel. Combining these two techniques leads to the area of joint source–channel coding which in general makes it possible to achieve a better performance when designing a communication system than in the case when source and channel codes are designed separately. In this thesis two particular areas in joint source–channel coding are studied: multiple description coding (MDC) and soft decoding. Two new MDC schemes are proposed and investigated. The first is based on sorting a frame of samples and transmitting, as side-information/redundancy, an index that describes the resulting permutation. In case that some of the transmitted descriptors are lost during transmission this side information (if received) can be used to estimate the lost descriptors based on the received ones. The second scheme uses permutation codes to produce different descriptions of a block of source data. These descriptions can be used jointly to estimate the original source data. Finally, also the MDC method multiple description coding using pairwise correlating transforms as introduced by Wang et al is studied. A modification of the quantization in this method is proposed which yields a performance gain. A well known result in joint source–channel coding is that the performance of a communication system can be improved by using soft decoding of the channel output at the cost of a higher decoding complexity. An alternative to this is to quantize the soft information and store the pre-calculated soft decision values in a lookup table. In this thesis we propose new methods for quantizing soft channel information, to be used in conjunction with soft-decision source decoding. The issue on how to best construct finite-bandwidth representations of soft information is also studied. / QC 20101124

[pt] Este trabalho apresenta um estudo sobre compressão de imagens de sensoriamento remoto para serem transmitidas através de um canal com ruído. As imagens são capturadas por um satélite de sensoriamento remoto e transmitidas a uma estação terrestre. A compreensão das imagens é necessária para se economizar banda e potência de transmissão. Algumas técnicas muito boas de compressão de imagens apresentam sérios problemas quando na presença de ruído. Assim, a técnica de quantização vetorial foi escolhida para ser utilizada neste trabalho. Utilizando-se a idéia de quantização vetorial multi-estágios, propões-se um esquema de compressão com remoção de médias, onde separa-se a informação contida na imagem para tratá-la de forma diferenciada, de acordo com a sua importância. É feita então uma análise sobre o projeto do enlace do satélite do sensoriamento remoto comparando-se o esquema utilizado atualmente com o esquema proposto. / [en] This thesis presents a study of remote sensing image compression to be transmitted over a noisy channel. The images are obtained by a remote sensing satellite and transmitting to an earth station. The compression is due to savings in bandwidth and transmitting power. Some of the most efficient image codecs presents serious problems in the presence of noise. So, the vector quantization technique was chosen to be used. Using the multi-stage vector quantization idea, a compression scheme with mean remove is proposed as a manner to separate and treat unequally the image information as its importance. An analysis on the design of the remote sensing satellite link is done with a comparison between the current scheme used the proposed one.

[pt] Este trabalho estuda o problema de compressão de imagens de sensoriamento remoto segundo a ótica da codificação conjunta fonte-canal. É analisado o desempenho de métodos baseados em quantização vetorial segundo o algoritmo LBG, principalmente o COVQ (Channel Optimized Vector Quantizer) bem como a quantização vetorial estruturada em árvore. Dentro desse contexto, são propostos 2 novos métodos para a resolução do problema: (1)Uma quantização vetorial estruturada em árvores que leva em conta a transmissão através de canais ruidosos, solução denominada COTSVQ (Channel-Design Tree Strutured Vecotr Quantizer), bem como (2) uma classe de métodos que se utiliza de códigos corretores de erro sobre a estrutura progressiva do TSVQ, de forma a proteger os dados de forma ativa durante a transmissão. Os dois métodos propostos podem ser combinados no mesmo compressor, de forma a originar uma classe ampla de compressores adaptados à transmissão por canais com ruído. São apresentados resultados que comparam os desempenhos dos métodos propostos com aqueles já existentes para uma análise de desempenho, na situação de transmissão via satélite de imagens captadas e comprimidas para uma taxa de 1,5bpp. Os resultados mostram que os métodos propostos são muito menos complexos que os já existentes, porém conseguindo atingir uma qualidade de imagem equivalente, ou, em alguns casos, superior. / [en] This work studies the problem of remote sensorng image compression by joint source-channel coding. The vector quantizer methods evaluated are those designed with the LBG algorithm, the COVQ (channel-optimized vector quantizer) algorithm as well as tree-structured vector quantizer. The noisy channel is modelled as a BSC. In this context, two news methods are proposed: (1) A tree- structures vector quantizer that considers the transmission through noisy channels (denominated CD-TSVQ), and (2) a new class of compressors that uses forward error- correcting codes over the TSVQ structure, as a way to actively protect data during the transmission. The twoproposed methods can be combined on the same compressor architecture, resulting in a vast class of compressors well-adapted to the transmission through noisy channels. Results allowing the comparision of the proposed methods with existing ones are presented. Performance evaluated in a scenery where images are compressed to be transmited at a rate of 1.5bpp. Results yield to the conclusion that the porposed methods are much less complex than the existing methods, yet achieve equivalent or, in some situations, improved performance.

In this thesis, novel progressive scalable region-of-interest (ROI) image coding schemes with rate-distortion-complexity trade-off based on residual vector quantization (RVQ) and matching pursuit (MP) are developed. RVQ and MP provide the encoder with multi-resolution signal analysis tools, which are useful for rate-distortion trade-off and can be used to render a selected region of an image with a specific quality. An image quality refinement strategy is presented in this thesis, which improves the quality of the ROI in a progressive manner. The reconstructed image can mimic foveated images in perceptual image coding context. The systems are unbalanced in the sense that the decoders have less computational requirements than the encoders. The methods also provide interactive way of information refinement for regions of image with receiver 's higher priority. The receiver is free to select multiple regions of interest and change his/her mind and choose alternative regions in the middle of signal transmission. The proposed RVQ and MP based image coding methods in this thesis raise a couple of issues and reveal some capabilities in image coding and communication. In RVQ based image coding, the effects of dictionary size, number of RVQ stages and the size of image blocks on the reconstructed image quality, the resulting bit rate, and the computational complexity are investigated. The progressive nature of the resulting bit-stream makes RVQ and MP based image coding methods suitable platforms for unequal error protection. Researchers have paid lots of attention to joint source-channel ( JSC) coding in recent years. In this popular framework, JSC decoding based on residual redundancy exploitation of a source coder output bit-stream is an interesting bandwidth efficient approach for signal reconstruction. In this thesis, we also addressed JSC decoding and error concealment problem for matching pursuit based coded images transmitted over a noisy memoryless channel. The problem is solved on minimum mean squared error (MMSE) estimation foundation and a suboptimal solution is devised, which yields high quality error concealment with different levels of computational complexity. The proposed decoding and error concealment solution takes advantage of the residual redundancy, which exists in neighboring image blocks as well as neighboring MP analysis stages, to improve the quality of the images with no increase in the required bandwidth. The effects of different parameters such as MP dictionary size and number of analysis stages on the performance of the proposed soft decoding method have also been investigated. / Thesis / Doctor of Philosophy (PhD)

This research is concerned with the reliable delivery of scalable compressed data over lossy communication channels. Recent works proposed several strategies for assigning optimal code redundancies to elements of scalable data, which form a linear structure of dependency, under the assumption that all source elements are encoded onto a common group of network packets. Given large data and small network packets, such schemes require very long channel codes with high computational complexity. In networks with high loss, small packets are more desirable than long packets. The first contribution of this thesis is to propose a strategy for optimally assigning elements of the scalable data to clusters of packets, subject to constraints on packet size and code complexity. Given a packet cluster arrangement, the scheme then assigns optimal code redundancies to the source elements, subject to a constraint on transmission length. Experimental results show that the proposed strategy can outperform the previous code assignment schemes subject to the above-mentioned constraints, particularly at high channel loss rates. Secondly, we modify these schemes to accommodate complex structures of dependency. Source elements are allocated to clusters of packets according to their dependency structure, subject to constraints on packet size and channel codeword length. Given a packet cluster arrangement, the proposed schemes assign optimal code redundancies to the source elements, subject to a constraint on transmission length. Experimental results demonstrate the superiority of the proposed strategies for correctly modelling the dependency structure. The last contribution of this thesis is to propose a scheme for optimizing protection of scalable data where limited retransmission is possible. Previous work assumed that retransmission is not possible. For most real-time or interactive applications, however, retransmission of lost data may be possible up to some limit. In the present work we restrict our attention to streaming sources (e.g., video) where each source element can be transmitted in one or both of two time slots. An optimization algorithm determines the transmission and level of protection for each source element, using information about the success of earlier transmissions. Experimental results confirm the benefit of limited retransmission.

Networked embedded control systems are present almost everywhere. A recent trendis to introduce radio communication in these systems to increase mobility and flex-ibility. Network nodes, such as the sensors, are often simple devices with limitedcomputing and transmission power and low storage capacity, so an important prob-lem concerns how to optimize the use of resources to provide sustained overall sys-tem performance. The approach to this problem taken in the thesis is to analyzeand design the communication and control application layers in an integrated man-ner. We focus in particular on cross-layer design techniques for closed-loop controlover non-ideal communication channels, motivated by future control systems withvery low-rate and highly quantized sensor communication over noisy links. Severalfundamental problems in the design of source–channel coding and optimal controlfor these systems are discussed.The thesis consists of three parts. The first and main part is devoted to the jointdesign of the coding and control for linear plants, whose state feedback is trans-mitted over a finite-rate noisy channel. The system performance is measured by afinite-horizon linear quadratic cost. We discuss equivalence and separation proper-ties of the system, and conclude that although certainty equivalence does not holdin general it can still be utilized, under certain conditions, to simplify the overalldesign by separating the estimation and the control problems. An iterative opti-mization algorithm for training the encoder–controller pairs, taking channel errorsinto account in the quantizer design, is proposed. Monte Carlo simulations demon-strate promising improvements in performance compared to traditional approaches.In the second part of the thesis, we study the rate allocation problem for statefeedback control of a linear plant over a noisy channel. Optimizing a time-varyingcommunication rate, subject to a maximum average-rate constraint, can be viewedas a method to overcome the limited bandwidth and energy resources and to achievebetter overall performance. The basic idea is to allow the sensor and the controllerto communicate with a higher data rate when it is required. One general obstacle ofoptimal rate allocation is that it often leads to a non-convex and non-linear problem.We deal with this challenge by using high-rate theory and Lagrange duality. It isshown that the proposed method gives a good performance compared to some otherrate allocation schemes.In the third part, encoder–controller design for Gaussian channels is addressed.Optimizing for the Gaussian channel increases the controller complexity substan-tially because the channel output alphabet is now infinite. We show that an efficientcontroller can be implemented using Hadamard techniques. Thereafter, we proposea practical controller that makes use of both soft and hard channel outputs. / QC 20100623