We propose a novel audio watermarking system that is robust to the distortion due to the indoor acoustic propagation channel between the loudspeaker and the receiving microphone. The system utilizes a set of new algorithms that effectively mitigate the impact of room reverberation and interfering sound sources without using derever- beration procedures. The decoder has low-latency and it operates asynchronously, which alleviates the need for explicit synchroniza- tion with the encoder. It is also robust to standard audio processing operations in legacy watermarking systems, e.g., compression and volume change. The effectiveness of the system is established with a real-time system under general room conditions.

This work addresses the fundamental issue of online channel learning in indoor localization systems. We describe a novel algorithm for unsupervised channel learning where the path loss exponent in the Non-Line-Of-Sight (NLOS) region is adapted online while positioning. The algorithm has scalable complexity and is shown to provide significant improvement over non-adaptive systems.

We present a new iterative quantization procedure for oversampled frames with guaranteed convergence and stability. The procedure uses similar concepts to that of turbo decoding in the context of error control coding. The quantization process is modeled as a quadratic integer-programming problem. A trellis structure is introduced to solve the problem, where the quantized coefficients represent a path through the trellis diagram. The quantization metric is iteratively improved through turbo iterations by exchanging quantization extrinsic information. The proposed procedure is shown to provide significant improvement over prior art in quantization and integer programming.

In this work, we study the design of polar codes for high-order constellations. We propose a new methodology for selecting polar codes rates in multilevel coding scenarios in order to optimize the overall error performance. We also propose a novel method for the design of polar codes based on the second order statistics of the bit error performance of the equivalent bit channels. This new code design is applied to the proposed multilevel coding scheme as well as to the standard quadrature amplitude modulation (QAM) constellations. We establish the effectiveness of the proposed algorithms through several practical examples.

We present a new method to accommodate the unobserved access points in indoor positioning systems that use the Received Signal Strength (RSS). We formulate a probabilistic framework, and derive the estimation bounds that quantify the advantage of incorporating unobserved data. Further, we describe a realization for the maximum-likelihood estimator and establish its effectiveness in a typical indoor positioning scenario.

We describe novel algorithms to enable the use of hexagonal constellations in practical high-rate communication systems. The first algorithm aims at optimizing the codewords assignment to the constellation points of a hexagonal grid to minimize the average Hamming distance between adjacent codewords. This codeword assignment is critical for the bit error rate performance that is usually more relevant than symbol error rate in coded schemes. We describe an efficient dynamic programming algorithm to solve this assignment problem. Then, we study the construction of the hexagonal grid that exploits the inherent redundancy in the hexagonal grid where the available constellation points for a given peak power are usually more than the grid size. Finally, we describe computationally efficient procedures for hard and soft decoding of hexagonal constellations. The proposed algorithms are shown to provide significant improvement for the bit error rate performance for both coded and uncoded schemes.

We present a novel scanning algorithm to enable mobile units to obtain measurements from surrounding access points for indoor positioning using the wireless local area network (WLAN) infrastructure. Our scanning algorithm adapts to minimize its impact on network throughput and battery power consumption while meeting a target positioning accuracy. This is achieved by using a learning procedure that dynamically adapts the parameters of the WLAN scanning procedure. Further, we show static algorithms that do not consider high-traffic scenarios will not only fail to meet positioning accuracy targets, but they also severely degrade network throughput.

We describe a procedure for designing compactly supported orthonormal wavelets for finite-length wavelet transform. The designed wavelets yield perfect reconstruction with a more general class of signal extensions, including symmetric extension and zero-padding, rather than the common periodic extension. This combines the compact representation from orthonormal wavelets with the good behaviour at the borders from smooth extensions, which enables their use in signal coding. We show few examples that illustrate the improvement for coding finite-length signals.

We describe an iterative algorithm for quantizing overcomplete frames that achieves more than 18 dB/Octave improvement in the reconstruction error due to quantization. It starts with the trellis quantization path then successively refines the estimation with monotonically improving quantization through turbo iterations. We call the procedure turbo quantization because it resembles turbo coding in the error control coding literature.

We describe a method for incorporating map information to the Kalman filter that is commonly used in indoor and outdoor navigation systems. The map information is provided as a measurement to the Kalman filter to ensure the consistency of the Kalman estimate. The proposed method provides huge computational saving over common map matching algorithms that use the more computationally expensive particle filter. We show indoor navigation examples that highlight the efficiency of the proposed algorithm.

We study the non-cooperative game when many WLAN stations compete for responses from WLAN access points in order to find their positions. The main objective of the WLAN stations, which are the players in our game, is to minimize the positioning error under various constraints on power consumption and network throughput. We provide a rigorous and general formulation of the game model where we use the Cramer-Rao bound of the WLAN positioning error so that the analysis is independent of the underlying positioning algorithm. The strategies for each player are combinations of the frequency of probe requests within the network and the corresponding listening time. We compute the Nash Equilibrium for the game under different practical network scenarios.

We derive a new set of necessary and sufficient conditions for the filter coefficients of the two-scale difference equation to yield an orthogonal wavelet of compact support. The conditions constitute a linear set of equations of an arbitrary decision vector of half the filter size. The vector of the filter coefficients is a differentiable function of the decision vector. The formulation enables the optimization of the filter design under any regular objective function. The proposed parametrization is used to design customized orthonormal wavelets and to reproduce the classical orthogonal wavelets as a solution of a nonlinear optimization problem.

We describe a turbo coding scheme with nonsystematic recursive convolutional codes for channels that exhibit insertions and deletions along with substitution errors. The scheme uses the MAP decoding algorithm for this channel and a special codeword arrangement to simplify the synchronization process. The decoder uses a special trellis structure to extract synchronization extrinsic information that is exchanged between the two constituent decoders. The proposed scheme is shown to provide improvement over earlier channel coding approaches for this channel model.

We describe an efficient implementation for converting MPEG-2/MPEG-4 Advanced Audio Coding (AAC) encoded data to Dolby Digital AC-3. We describe many techniques to exploit the information in the AAC bitstream to simplify the AC-3 encoder. These techniques can be straightforwardly used in other transcoding schemes between different multimedia standards.

We describe a time-domain procedure for designing the synthesis filters of perfect-reconstruction oversampled filter banks. A condition matrix is derived from the basic magnitude distortion and aliasing canceling conditions and we derive the necessary and sufficient conditions for perfect reconstruction. The formulation is general for any decimation scenario, but it is particularly useful with nonuniform decimation. Further, the condition matrix in the proposed design model is in general rectangular and has a nonzero null-space which allows for design optimization.

We develop new algorithms for designing matched wavelets and matched scaling functions using a new parametrization of compactly supported orthonormal wavelets that is developed in [4]. The parametrization specifies the wavelet filter coefficients as a continuous function of an arbitrary vector of half its length. Therefore, the wavelets and the scaling functions are also continuous functions of this vector through the use of the cascade algorithm. Hence, standard minimization procedures can be employed for wavelet design. In the case of matched scaling function we propose a new optimization algorithm that significantly reduces the problem complexity. We provide several design examples that illustrate the effectiveness of the proposed algorithm.

We derive compact systolic structures for the transcoding of critically sampled modulated lapped transforms (MLT's) of equal and rational sizes. The structures include two modules for DCT-IV computation and an intermediate module for all windowing/reordering operations. The proposed structure is highly regular and provides theoretical and practical insights for this transcoding problem.

We address the optimization of the quantization of overcomplete frames. The optimization problem is formulated as a quadratic integer programming problem. We develop a suboptimal dynamic programming solution that uses a scalable trellis expansion. The proposed solution offers significant improvement of the quantization error and it can be combined with projection-based quantization, e.g., sigma-delta quantization. The effectiveness of the algorithm is established using harmonic tight frames.

We describe the operation of common convolutional decoding algorithms in the presence of insertions, deletions, as well as substitutions in the received message. We first propose a trellis description that can handle the existence of insertions and deletions. Then, we use this trellis diagram to develop the Viterbi algorithm and the Log-MAP algorithm in the presence of synchronization errors. The proposed techniques are presented in the most general form where standard convolutional codes are used and no change to the encoder is required. We establish the effectiveness of the proposed algorithms using standard convolutional codes at different rates.

We study the reuse of the bit allocation information in audio transcoding by exploiting the similarity in subband audio coding schemes. We show that important information can be deduced to reduce the encoder complexity even if the two coders employ different psychoacoustic model. We give a case study on MPEG AAC/Dolby AC-3 transcoding. The proposed algorithms can be extended to other audio transcoding schemes.

We describe an efficient algorithm for Huffman decoding using table lookup. The algorithm is optimized for ROM-based Huffman decoding. It is a two-step process of prefix template matching followed by a direct table access. We propose an efficient algorithm for choosing the prefix templates according to different optimization criteria. Also, we propose different implementations for the prefix template procedure.

We use the general formula of the synthesis window of the oversampled discrete Fourier transform filter bank in terms of the minimum-norm solution and the null space of the perfect reconstruction condition matrix to optimize the window design. We give closed-form solutions to different optimization criteria, e.g., minimum out-of-band power, minimum quantization-error, and minimum window order

A new framework for data embedding in audio is proposed. The basic idea of the algorithm is to change the length of the intervals between salient points of the audio signal to embed data. The intervals are quantized and the data is embedded in the quantization indices. In our particular implementation, we use the wavelet extrema of the signal envelope as the salient points. We propose novel ideas for practical implementation that can be used by other data embedding schemes as well. The algorithm is robust to common audio processing operations, e.g., mp3 lossy compression, low pass filtering, sampling rate conversion, and time-scale modification (TSM). The perceptual quality of the audio signal after embedding the data depends on the technique used for TSM.

We propose a turbo decoding framework in the presence of insertions and deletions as well as substitutions in the received sequence. The decoding algorithm is based on the Viterbi algorithm for this special channel. The synchronization information is exchanged between decoders in the proposed structure and extrinsic information is used, as is commonly done in turbo decoders. Simulation results indicate that the proposed turbo structure does indeed improve the performance of the Viterbi algorithm, particularly at high code rates.

We propose a new structure for polyphase synthesis in the MPEG-1 audio standard. The algorithm is based on factorizing the DCT matrix in a way similar to FFT factorization. The proposed algorithm reduces the memory requirement significantly even with direct implementation. With optimized implementation, the computational requirement can be reduced considerably as well.

We introduce modifications to common convolutional decoders to accommodate channels with Insertions and deletions. For the Viterbi decoder, new states are added to the trellis diagram to represent the new situation and the expansion algorithm is modified accordingly. For sequential decoding, we provide modifications to the stack algorithm and a new metric is introduced. Also, we developed a systematic way for convolutional code construction using Simulated Annealing so as to maximize the distance between codewords In the presence of insertions and deletions. The proposed techniques are shown to be superior to previous approaches for this problem, and have no additional code overhead.

In this work, we propose a new channel model that is suited for systems with irregular sampling, e.g. selective data embedding in digital media. The channel model accounts for the possible occurrence of false alarms, i.e. extra data bits, in the received sequence. We propose modifications to the common decoding schemes of the convolutional codes namely, the Viterbi and the sequential decoding to compensate for these false alarms. The simulation results establish the effectiveness of the proposed algorithms in detecting false alarms with high rates.

In this paper we will address the problem of constructing a nonparameteric decision boundary for watermark detection. Most current watermarking algorithms have a parametric decision boundary that can be undone if the pirate has unlimited access to the detector. In this work we propose a fractal decision boundary which can not be estimated. That boundary is obtained by processing the decision boundary corresponding to the underlying watermarking algorithm. The performance of the new technique is essentially similar to any watermarking algorithm from which it is derived.

Providing quality-of-service (QoS) guarantees over wireless packet networks requires a thorough understanding and quantification of the interactions among the traffic source, the wireless channel characteristics, the underlying link-layer error control mechanisms, and the various packet dropping policies adopted by the upper network layers. We explore the idea of cooperation among some of these different aspects to assist the packet level error recovery. First, we revise UDP to tolerate a certain amount of channel error and to allow the delivery of partially corrupted packets. Secondly, we propose a novel technique to resolve the problem of missed bits without the need to identify their exact locations. It is based on modifying the stack algorithm for convolutional decoding. Simulation results establish the effectiveness of the proposed approach for detecting and correcting missed bits, which have direct impact on packet loss and on the overall system performance.

We describe a generalized attack on image watermarking schemes when the decoder is publicly available. The attack applies to most common watermarking schemes. In particular, we describe in detail the implementation of the attack against correlator-based watermark detectors using the least mean square (LMS) algorithm. We establish the effectiveness of the attack in removing the watermark with least distortion. Also, we describe a counterattack to avoid this problem by using nonparametric decision boundaries at the detector.

A new algorithm for audio watermarking is proposed. The basic idea of the algorithm is to change the length of the intervals between salient points of the audio signal to embed data. We propose several novel ideas for practical implementations that can be used by other watermarking schemes as well. The algorithm is robust to common audio processing operations e.g. MP3 lossy compression, low pass filtering, and time-scale modification. The watermarked signal has very high perceptual quality and is indistinguishable from the original signal.

We propose a novel algorithm for high-quality data embedding in audio. The algorithm is based on changing the relative length of the middle segment between two successive maximum and minimum peaks to embed data. Spline interpolation is used to change the lengths. To ensure smooth monotonic behavior between peaks, a hybrid orthogonal and nonorthogonal wavelet decomposition is used prior to data embedding. The possible data embedding rates are between 20 and 30 bps. However, for practical purposes, we use repetition codes, and the effective embedding data rate is around 5 bps. The algorithm is invariant after time-scale modification, time shift, and time cropping. It gives high-quality output and is robust to mp3 compression.

We treat the problem of recovering the correct message if extra bits (false alarms) are added to the body of the message at random locations. This situation is common for some watermarking systems with selective embedding which is typical when the human visual (or audio) system is incorporated to enhance the quality of the watermarking system. We propose an efficient decoding scheme for convolutional codes using some modifications of the Viterbi algorithm. Extra states are added to represent the possible false alarms and a new expansion algorithm of the modified trellis diagram is proposed. The simulation results show the high efficiency of our algorithm in detecting random false alarms with high rates.

We present a novel algorithm for high capacity data embedding. The proposed algorithm gives high hiding ratios up to 1/13 (1 embedded bit out of 13 raw image pixels) subject to JPEG compression with quality factor equals 75. With such high capacity, one can easily embed some important regions of an image inside the image itself with very small perceptual distortion. In the proposed algorithm, the DCT coefficients of 8/spl times/8 blocks are first rearranged using Hilbert curves. Data is embedded using projections on a random orthogonal set. The algorithm recovers the embedded data without any reference to the original image, with very low BER (around 0.1%). Finally, the proposed algorithm shows robustness to JPEG compression.