DSP Laboratory - DIEI

In this paper, we propose a family of low-complexity adaptive filtering algorithms based on dichotomous coordinate descent (DCD) iterations for identification of sparse systems. The proposed algorithms are appealing for practical designs as they operate at the bit level, resulting in stable hardware implementations. We introduce a general approach for developing adaptive filters with different penalties and specify it for exponential and sliding window RLS. We then propose low-complexity DCD-based RLS adaptive filters with the lasso, ridge-regression, elastic net, and $ell_0$ penalties that attract sparsity. We also propose a simple recursive reweighting of the penalties and incorporate the reweighting into the proposed adaptive algorithms to further improve the performance. For general regressors, the proposed algorithms have a complexity of ${cal O}(N^2)$ operations per sample, where $N$ is the filter length. For transversal adaptive filters, the algorithms require only ${cal O}(N)$ operations per sample. A unique feature of the proposed algorithms is that they are well suited for implementation in finite precision, e.g., on FPGAs. We demonstrate by simulation that the proposed algorithms have performance close to the oracle RLS performance.

An important sensing operation is to detect the presence of specific signals with unknown transmission parameters. This task, referred to as “link acquisition,” is typically a sequential search over the transmitted signal space. Recently, the use of sparsity in similar estimation or detection problems has received considerable attention. These works typically focus on the benefits of compressed sensing, but not generally on the cost brought by sparse recovery. Our goal is to examine the tradeoff in complexity and performance when using sparse recovery with compressed or uncompressed samples. To do so, we propose a compressive sparsity aware (CSA) acquisition scheme, where a compressive multichannel sampling (CMS) front-end is followed by a sparsity regularized likelihood ratio test (SR-LRT) module. The CSA scheme borrows insights from the models studied in sub-Nyquist sampling and finite rate of innovation (FRI) signals. We further optimize the CMS front-end by maximizing the average Kullback–Leibler distance of all the hypotheses in the SR-LRT. We compare the CSA scheme vis-à-vis other popular alternatives in terms of performance and complexity. Simulations suggest that one can use the CSA scheme to scale down the implementation cost with greater flexibility than other alternatives. However, we find that they both have overall complexities that scale linearly with the search space. Furthermore, it is shown that compressive measurements used in the SR-LRT lead to a performance loss when noise prevails, while providing better performance in spite of the compression when noise is mild.

In this paper, we address the problem of minimizing the energy cost of positioning nodes in a wireless sensor network, using time of arrival measurements. A sensor needs to receive at least three distance measurements to known anchors in order to position itself. The accuracy of its position estimation depends on the signal to noise ratio of the beacons from the anchor nodes, whose power levels are to be selected according to a two-fold criterion: minimum power level and desired positioning quality for users, determined by the error covariance metric. We derive a solution based on modeling the positioning problem as a non-cooperative game. We show that the resulting game is supermodular and that it possesses a unique Nash equilibrium, which can be quickly reached with best response dynamics. Finally, in the numerical results we find the price of anarchy of our game.

In this paper, we consider the problem of locating multiple active spectrum subbands in a wide range of frequency bands. A major challenge associated with such wideband spectrum sensing is that it is either infeasible or too expensive to perform Nyquist sampling on the wideband signal. In this paper, we propose a sensing scheme based on a sub-Nyquist sampling method called multicoset sampling, which is similar to the polyphase implementation of the Nyquist sampling, but requires less A/D converters. In contrast to the traditional sub-Nquist approaches where the wideband signal is first reconstructed from the sub-Nyquist samples, we develop a method that directly estimates the power spectrum of the wideband signal of interest using the sub-Nyquist samples, by exploiting its statistical properties. We also characterize the statistical distribution of the proposed power spectrum estimator, based on which we obtain a constant-false-alarm energy detector for the frequency bins. Simulation results are provided to demonstrate the effectiveness of the proposed multiband spectrum sensing method based on sub-Nyquist sampling.

Formulations of the turbo equalization approach to iterative equalization and decoding vary greatly when channel knowledge is either partially or completely unknown. Maximum aposteriori probability (MAP) and minimum mean-square error (MMSE) approaches leverage channel knowledge to make explicit use of soft information (priors over the transmitted data bits) in a manner that is distinctly nonlinear, appearing either in a trellis formulation (MAP) or inside an inverted matrix (MMSE). To date, nearly all adaptive turbo equalization methods either estimate the channel or use a direct adaptation equalizer in which estimates of the transmitted data are formed from an expressly linear function of the received data and soft information, with this latter formulation being most common. We study a class of direct adaptation turbo equalizers that are both adaptive and nonlinear functions of the soft information from the decoder. We introduce piecewise linear models based on context trees that can adaptively approximate the nonlinear dependence of the equalizer on the soft information such that it can choose both the partition regions as well as the locally linear equalizer coefficients in each region independently, with computational complexity that remains of the order of a traditional direct adaptive linear equalizer. This approach is guaranteed to asymptotically achieve the performance of the best piecewise linear equalizer, and we quantify the MSE performance of the resulting algorithm and the convergence of its MSE to that of the linear minimum MSE estimator as the depth of the context tree and the data length increase.

The full potential of multi-input multi-output (MIMO) communication systems relies on exploiting channel state information at the transmitter (CSIT), which is, however, often subject to some uncertainty. In this paper, following the worst-case robust philosophy, we consider a robust MIMO precoding design with deterministic imperfect CSIT, formulated as a maximin problem, to maximize the worst-case received signal-to-noise ratio or minimize the worst-case error probability. Given different types of imperfect CSIT in practice, a unified framework is lacking in the literature to tackle various channel uncertainty. In this paper, we address this open problem by considering several classes of uncertainty sets that include most deterministic imperfect CSIT as special cases. We show that, for general convex uncertainty sets, the robust precoder, as the solution to the maximin problem, can be efficiently computed by solving a single convex optimization problem. Furthermore, when it comes to unitarily-invariant convex uncertainty sets, we prove the optimality of a channel-diagonalizing structure and simplify the complex-matrix problem to a real-vector power allocation problem, which is then analytically solved in a waterfilling manner. Finally, for uncertainty sets defined by a generic matrix norm, called the Schatten norm, we provide a fully closed-form solution to the robust precoding design, based on which the robustness of beamforming and uniform-power transmission is investigated.

Using multicast probes to infer network topologies and internal link/node characteristics is an attractive approach due to its bandwidth efficiency and suitability for large-scale measurements. In this paper, we propose a new approach to tree topologies inference by exploiting dependence among end-point receivers. We first show that under the assumption of independent failure of intermediate nodes or links, inferring tree topology is a special instance of the more general problem of binary independent component analysis (bICA), and thus is amiable to existing analytical results and algorithms for bICA. Then, we propose the seqBICA algorithm that is tailored for tree topology inference. Evaluation study shows that the proposed algorithm outperforms existing approaches in convergence speed and accuracy even when the number of measurements is small.

A mathematical characterization of serially pruned permutations (SPPs) employed in variable-length permuters and their associated fast pruning algorithms and architectures are proposed. Permuters are used in many signal processing systems for shuffling data and in communication systems as an adjunct to coding for error correction. Typically, only a small set of discrete permuter lengths are supported. Serial pruning is a simple technique to alter the length of a permutation to support a wider range of lengths, but results in a serial processing bottleneck. In this paper, parallelizing SPPs is formulated in terms of recursively computing sums involving integer floor functions using integer operations, in a fashion analogous to evaluating Dedekind sums. A mathematical treatment for bit-reversal permutations (BRPs) is presented, and closed-form expressions for BRP statistics including descents/ascents, major index, excedances/descedances, inversions, and serial correlations are derived. It is shown that BRP sequences have weak correlation properties. Moreover, a new statistic called permutation inliers that characterizes the pruning gap of pruned interleavers is proposed. Using this statistic, a recursive algorithm that computes the minimum inliers count of a pruned BR interleaver (PBRI) in logarithmic time is presented. This algorithm enables parallelizing a serial PBRI algorithm by any desired parallelism factor by computing the pruning gap in lookahead rather than a serial fashion, resulting in significant reduction in interleaving latency and memory overhead. Extensions to 2-D block and stream interleavers, as well as applications to pruned fast Fourier transforms and LTE turbo interleavers, are also presented. Moreover, hardware-efficient architectures for the proposed algorithms are developed. Simulation results of interleavers employed in modern communication standards demonstrate three to four orders of magnitude improvement in interleaving time compared to ex- sting approaches.

Even though parallel multiple-input multiple-output (MIMO) broadcast channels are known to be separable from an information theoretic point of view, performing separate encoding and decoding on each of the parallel channels has been shown to be potentially suboptimal in broadcast channels with linear transceivers. In this paper, we show that suboptimality of such a carrier-noncooperative transmission also occurs in broadcast channels with zero-forcing and quality of service constraints if time-sharing is not allowed. The proof is given by constructing a minimal example and identifying a rate tuple that is achievable using carrier-cooperative zero-forcing with a certain sum power but requires a higher sum power with carrier-noncooperative zero-forcing. This observation is of practical relevance since zero-forcing without time-sharing is a popular assumption in the design of low-complexity optimization algorithms.

This paper presents, for the first time, a unified blind method for multi-image super-resolution (MISR or SR), single-image blur deconvolution (SIBD), and multi-image blur deconvolution (MIBD) of low-resolution (LR) images degraded by linear space-invariant (LSI) blur, aliasing, and additive white Gaussian noise (AWGN). The proposed approach is based on alternating minimization (AM) of a new cost function with respect to the unknown high-resolution (HR) image and blurs. The regularization term for the HR image is based upon the Huber-Markov random field (HMRF) model, which is a type of variational integral that exploits the piecewise smooth nature of the HR image. The blur estimation process is supported by an edge-emphasizing smoothing operation, which improves the quality of blur estimates by enhancing strong soft edges toward step edges, while filtering out weak structures. The parameters are updated gradually so that the number of salient edges used for blur estimation increases at each iteration. For better performance, the blur estimation is done in the filter domain rather than the pixel domain, i.e., using the gradients of the LR and HR images. The regularization term for the blur is Gaussian (L2 norm), which allows for fast noniterative optimization in the frequency domain. We accelerate the processing time of SR reconstruction by separating the upsampling and registration processes from the optimization procedure. Simulation results on both synthetic and real-life images (from a novel computational imager) confirm the robustness and effectiveness of the proposed method.

We study state-based video communication where a client simultaneously informs the server about the presence status of various packets in its buffer. In sender-driven transmission, the client periodically sends to the server a single acknowledgement packet that provides information about all packets that have arrived at the client by the time the acknowledgment is sent. In receiver-driven streaming, the client periodically sends to the server a single request packet that comprises a transmission schedule for sending missing data to the client over a horizon of time. We develop a comprehensive optimization framework that enables computing packet transmission decisions that maximize the end-to-end video quality for the given bandwidth resources, in both prospective scenarios. The core step of the optimization comprises computing the probability that a single packet will be communicated in error as a function of the expected transmission redundancy (or cost) used to communicate the packet. Through comprehensive simulation experiments, we carefully examine the performance advances that our framework enables relative to state-of-the-art scheduling systems that employ regular acknowledgement or request packets. Consistent gains in video quality of up to 2B are demonstrated across a variety of content types. We show that there is a direct analogy between the error-cost efficiency of streaming a single packet and the overall rate-distortion performance of streaming the whole content. In the case of sender-driven transmission, we develop an effective modeling approach that accurately characterizes the end-to-end performance as a function of the packet loss rate on the backward channel and the source encoding characteristics.

Complexities of dynamic volumetric imaging challenge the available computer vision techniques on a number of different fronts. This paper examines the relationship between the estimation accuracy and required amount of smoothness for a general solution from a robust statistics perspective. We show that a (surprisingly) small amount of local smoothing is required to satisfy both the necessary and sufficient conditions for accurate optic flow estimation. This notion is called “just enough” smoothing, and its proper implementation has a profound effect on the preservation of local information in processing 3D dynamic scans. To demonstrate the effect of “just enough” smoothing, a robust 3D optic flow method with quantized local smoothing is presented, and the effect of local smoothing on the accuracy of motion estimation in dynamic lung CT images is examined using both synthetic and real image sequences with ground truth.

Exploiting a priori known structural information lies at the core of many image reconstruction methods that can be stated as inverse problems. The synthesis model, which assumes that images can be decomposed into a linear combination of very few atoms of some dictionary, is now a well established tool for the design of image reconstruction algorithms. An interesting alternative is the analysis model, where the signal is multiplied by an analysis operator and the outcome is assumed to be sparse. This approach has only recently gained increasing interest. The quality of reconstruction methods based on an analysis model severely depends on the right choice of the suitable operator. In this paper, we present an algorithm for learning an analysis operator from training images. Our method is based on $ell_{p}$-norm minimization on the set of full rank matrices with normalized columns. We carefully introduce the employed conjugate gradient method on manifolds, and explain the underlying geometry of the constraints. Moreover, we compare our approach to state-of-the-art methods for image denoising, inpainting, and single image super-resolution. Our numerical results show competitive performance of our general approach in all presented applications compared to the specialized state-of-the-art techniques.

Many computational models of visual attention performing well in predicting salient areas of 2D images have been proposed in the literature. The emerging applications of stereoscopic 3D display bring an additional depth of information affecting the human viewing behavior, and require extensions of the efforts made in 2D visual modeling. In this paper, we propose a new computational model of visual attention for stereoscopic 3D still images. Apart from detecting salient areas based on 2D visual features, the proposed model takes depth as an additional visual dimension. The measure of depth saliency is derived from the eye movement data obtained from an eye-tracking experiment using synthetic stimuli. Two different ways of integrating depth information in the modeling of 3D visual attention are then proposed and examined. For the performance evaluation of 3D visual attention models, we have created an eye-tracking database, which contains stereoscopic images of natural content and is publicly available, along with this paper. The proposed model gives a good performance, compared to that of state-of-the-art 2D models on 2D images. The results also suggest that a better performance is obtained when depth information is taken into account through the creation of a depth saliency map, rather than when it is integrated by a weighting method.

In this paper, we present an approach that simultaneously clusters images and learns dictionaries from the clusters. The method learns dictionaries and clusters images in the radon transform domain. The main feature of the proposed approach is that it provides both in-plane rotation and scale invariant clustering, which is useful in numerous applications, including content-based image retrieval (CBIR). We demonstrate the effectiveness of our rotation and scale invariant clustering method on a series of CBIR experiments. Experiments are performed on the Smithsonian isolated leaf, Kimia shape, and Brodatz texture datasets. Our method provides both good retrieval performance and greater robustness compared to standard Gabor-based and three state-of-the-art shape-based methods that have similar objectives.

Histogram shifting (HS) is a useful technique of reversible data hiding (RDH). With HS-based RDH, high capacity and low distortion can be achieved efficiently. In this paper, we revisit the HS technique and present a general framework to construct HS-based RDH. By the proposed framework, one can get a RDH algorithm by simply designing the so-called shifting and embedding functions. Moreover, by taking specific shifting and embedding functions, we show that several RDH algorithms reported in the literature are special cases of this general construction. In addition, two novel and efficient RDH algorithms are also introduced to further demonstrate the universality and applicability of our framework. It is expected that more efficient RDH algorithms can be devised according to the proposed framework by carefully designing the shifting and embedding functions.

In this paper, the properties of a new class of causal Markov random fields, named symmetric Markov mesh random field, are initially discussed. It is shown that the symmetric Markov mesh random fields from the upper corners are equivalent to the symmetric Markov mesh random fields from the lower corners. Based on this new random field, a symmetric, corner-independent, and isotropic image model is then derived which incorporates the dependency of a pixel on all its neighbors. The introduced image model comprises the product of several local 1D density and 2D joint density functions of pixels in an image thus making it computationally tractable and practically feasible by allowing the use of histogram and joint histogram approximations to estimate the model parameters. An image restoration application is also presented to confirm the effectiveness of the model developed. The experimental results demonstrate that this new model provides an improved tool for image modeling purposes compared to the conventional Markov random field models.

Ellipse fitting is widely applied in the fields of computer vision and automatic industry control, in which the procedure of ellipse fitting often follows the preprocessing step of edge detection in the original image. Therefore, the ellipse fitting method also depends on the accuracy of edge detection besides their own performance, especially due to the introduced outliers and edge point errors from edge detection which will cause severe performance degradation. In this paper, we develop a robust ellipse fitting method to alleviate the influence of outliers. The proposed algorithm solves ellipse parameters by linearly combining a subset of (“more accurate”) data points (formed from edge points) rather than all data points (which contain possible outliers). In addition, considering that squaring the fitting residuals can magnify the contributions of these extreme data points, our algorithm replaces it with the absolute residuals to reduce this influence. Moreover, the norm of data point errors is bounded, and the worst case performance optimization is formed to be robust against data point errors. The resulting mixed $l1hbox{--}l2$ optimization problem is further derived as a second-order cone programming one and solved by the computationally efficient interior-point methods. Note that the fitting approach developed in this paper specifically deals with the overdetermined system, whereas the current sparse representation theory is only applied to underdetermined systems. Therefore, the proposed algorithm can be looked upon as an extended application and development of the sparse representation theory. Some simulated and experimental examples are presented to illustrate the effectiveness of the proposed ellipse fitting approach.

Using shape information has gained increasing concerns in the task of image labeling. In this paper, we present a dynamic hybrid Markov random field (DHMRF), which explicitly captures middle-level object shape and low-level visual appearance (e.g., texture and color) for image labeling. Each node in DHMRF is described by either a deformable template or an appearance model as visual prototype. On the other hand, the edges encode two types of intersections: co-occurrence and spatial layered context, with respect to the labels and prototypes of connected nodes. To learn the DHMRF model, an iterative algorithm is designed to automatically select the most informative features and estimate model parameters. The algorithm achieves high computational efficiency since a branch-and-bound schema is introduced to estimate model parameters. Compared with previous methods, which usually employ implicit shape cues, our DHMRF model seamlessly integrates color, texture, and shape cues to inference labeling output, and thus produces more accurate and reliable results. Extensive experiments validate its superiority over other state-of-the-art methods in terms of recognition accuracy and implementation efficiency on: 1) the MSRC 21-class dataset, and 2) the lotus hill institute 15-class dataset.

In this paper, we develop a decomposition model to restore blurred images with missing pixels. Our assumption is that the underlying image is the superposition of cartoon and texture components. We use the total variation norm and its dual norm to regularize the cartoon and texture, respectively. We recommend an efficient numerical algorithm based on the splitting versions of augmented Lagrangian method to solve the problem. Theoretically, the existence of a minimizer to the energy function and the convergence of the algorithm are guaranteed. In contrast to recently developed methods for deblurring images, the proposed algorithm not only gives the restored image, but also gives a decomposition of cartoon and texture parts. These two parts can be further used in segmentation and inpainting problems. Numerical comparisons between this algorithm and some state-of-the-art methods are also reported.