Publications by Year: 2009

2009
Y. M. Lu, M. N. Do, and R. Laugesen, “Computable Fourier conditions for alias-free sampling and critical sampling.” in Proc. Int. Conf. Sampling Theory and applications (SampTA), Marseille, France, 2009.Abstract

We propose a Fourier analytical approach to the problems of alias-free sampling and critical sampling. Central to this approach are two Fourier conditions linking the above sam- pling criteria with the Fourier transform of the indicator function defined on the underlying frequency support. We present several examples to demonstrate the usefulness of the proposed Fourier conditions in the design of critically sampled multidimensional filter banks. In particular, we show that it is impossible to implement any cone-shaped fre- quency partitioning by a nonredundant filter bank, except for the 2-D case.

sampling_lattices_sampta.pdf
A. Hormati, O. Roy, Y. M. Lu, and M. Vetterli, “Distributed sensing of signals under a sparse filtering model,” in Proc. 8th International Conference on Sampling Theory and Applications (SampTA), Marseille, France, 2009.Abstract

We consider the task of recovering correlated vectors at a central decoder based on fixed linear measurements ob- tained by distributed sensors. Two different scenarios are considered: In the case of universal reconstruction, we look for a sensing and recovery mechanism that works for all possible signals, whereas in the case of almost sure recon- struction, we allow to have a small set (with measure zero) of unrecoverable signals. We provide achievability bounds on the number of samples needed for both scenarios. The bounds show that only in the almost sure setup can we ef- fectively exploit the signal correlations to achieve effective gains in sampling efficiency. In addition, we propose an efficient and robust distributed sensing and reconstruction algorithm based on annihilating filters.

sparse_filtering_sampta.pdf
Y. M. Lu, C. Fredembach, M. Vetterli, and S. Süsstrunk, “Designing color filter arrays for the joint capture of visible and near-infrared images,” in Proc. IEEE International Conference on Image Processing, Cairo, Egypt, 2009.Abstract

Digital camera sensors are inherently sensitive to the near- infrared (NIR) part of the light spectrum. In this paper, we propose a general design for color filter arrays that allow the joint capture of visible/NIR images using a single sensor. We pose the CFA design as a novel spatial domain optimization problem, and provide an efficient iterative procedure that finds (locally) optimal solutions. Numerical experiments confirm the effectiveness of the proposed CFA design, which can simultane- ously capture high quality visible and NIR image pairs.

cfa_visnir.pdf
C. Carneiro, M. Karzand, F. Golay, Y. M. Lu, and M. Vetterli, “Assessment of digital surface models for the study of shadowing and radiation over the built environment using wireless sensor network data,” in Proc. 6th International Symposium on Spatial Data Quality, Newfoundland, 2009.
Y. M. Lu and M. Vetterli, “Optimal color filter array design: Quantitative conditions and an efficient search procedure,” in Proc. SPIE Electronic Imaging, Digital Photography V, 2009.Abstract

Most digital cameras employ a spatial subsampling process, implemented as a color filter array (CFA), to capture color images. The choice of CFA patterns has a great impact on the performance of subsequent reconstruction (demosaicking) algorithms. In this work, we propose a quantitative theory for optimal CFA design. We view the CFA sampling process as an encoding (low-dimensional approximation) operation and, correspondingly, demosaicking as the best decoding (reconstruction) operation. Finding the optimal CFA is thus equivalent to finding the optimal approximation scheme for the original signals with minimum information loss. We present several quantitative conditions for optimal CFA design, and propose an efficient computational procedure to search for the best CFAs that satisfy these conditions. Numerical experiments show that the optimal CFA patterns designed from the proposed procedure can effectively retain the information of the original full-color images. In particular, with the designed CFA patterns, high quality demosaicking can be achieved by using simple and efficient linear filtering operations in the polyphase domain. The visual qualities of the reconstructed images are competitive to those obtained by the state-of-the-art adaptive demosaicking algorithms based on the Bayer pattern.

optimal_cfa_ei09.pdf
Y. M. Lu, M. N. Do, and R. S. Laugesen, “A Computable Fourier Condition Generating Alias-Free Sampling Lattices,” IEEE Transactions on Signal Processing, vol. 57, no. 5, pp. 1768–1782, 2009.Abstract

We propose a Fourier analytical condition linking alias-free sampling with the Fourier transform of the indicator function defined on the given frequency support. Our discussions center around how to develop practical computation algorithms based on the proposed analytical condition. We address several issues along this line, including the derivation of simple closed-form expressions for the Fourier transforms of the indicator functions defined on arbitrary polygonal and polyhedral domains; a complete and nonredundant enumeration of all quantized sampling lattices via the Hermite normal forms of integer matrices; and a quantitative analysis of the approximation of the original infinite Fourier condition by using finite computations. Combining these results, we propose a computational testing procedure that can efficiently search for the optimal alias-free sampling lattices for a given polygonal or polyhedral shaped frequency domain. Several examples are presented to show the potential of the proposed algorithm in multidimensional filter bank design, as well as in applications involving the design of efficient sampling patterns for multidimensional band-limited signals.

sampling_lattices.pdf
Y. M. Lu and M. Vetterli, “Distributed spatio-temporal sampling of diffusion fields from sparse instantaneous sources,” in Proc. 3rd International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), Aruba, 2009.Abstract

We study the spatio-temporal sampling of a diffusion field driven by K unknown instantaneous source distributions. Exploiting the spatio-temporal correlation offered by the diffusion model, we show that it is possible to compensate for insufficient spatial sampling densities (i.e. sub-Nyquist sampling) by increasing the temporal sampling rate, as long as their product remains roughly a constant. Combining a distributed sparse sampling scheme and an adaptive feedback mechanism, the proposed sampling algorithm can accurately and efficiently estimate the unknown sources and reconstruct the field. The total number of samples to be transmitted through the network is roughly equal to the number of degrees of freedom of the field, plus some additional costs for in-network averaging.

sparse_diffusion.pdf
Y. M. Lu and M. Vetterli, “Spatial super-resolution of a diffusion field by temporal oversampling in sensor networks,” in Proc. IEEE International Conference on Acoustics, Speech and Signal Processing, Taiwan, 2009.Abstract

We study the spatial-temporal sampling of a linear diffusion field, and show that it is possible to compensate for insufficient spatial sampling densities by oversampling in time. Our work is motivated by the following issue often encountered in sensor network sampling, namely increasing the temporal sampling density is often easier and less expensive than increasing the spatial sampling density of the network. For the case of sampling a diffusion field, we show that, to achieve trade-off between spatial and temporal sampling, the spatial arrangement of the sensors must satisfy certain conditions. We provide in this paper the precise relationships between the achievable reduction of spatial sampling density, the required temporal oversampling rate, the spatial arrangement of the sensors, and the bound for the condition numbers of the resulting sampling and reconstruction procedures.

diffusion_sampling_icassp09.pdf
O. Roy, A. Hormati, Y. M. Lu, and M. Vetterli, “Distributed sensing of signals linked by sparse filtering,” in Proc. IEEE International Conference on Acoustics, Speech and Signal Processing, Taipei, 2009.Abstract

We consider the task of recovering correlated vectors at a central decoder based on fixed linear measurements obtained by distributed sensors. A general formulation of the problem is proposed, under both a universal and an almost sure reconstruction requirement. We then study a specific correlation model which involves a filter that is sparse in the time domain. While this sparsity assumption does not allow reducing the description cost in the universal case, we show that large gains can be achieved in the almost sure scenario by means of a novel distributed scheme based on annihilating filters. The robustness of the proposed method is also investigated.

sparse_filtering_icassp09.pdf
Y. M. Lu, M. Karzand, and M. Vetterli, “Iterative demosaicking accelerated: Theory and fast noniterative implementations,” in Proc. SPIE Conf. Computational Imaging VI, San Jose, USA, 2009.Abstract

Color image demosaicking is a key process in the digital imaging pipeline. In this paper, we present a rigorous treatment of a classical demosaicking algorithm based on alternating projections (AP). Since its publication, the AP algorithm has been widely cited and served as a benchmark in a flurry of papers in the demosaicking literature. Despite its impressive performances, a relative weakness of the AP algorithm is its high computational complexity. In our work, we provide a rigorous analysis of the convergence of the AP algorithm based on the concept of contraction mapping. Furthermore, we propose an efficient noniterative implementation of the AP algorithm in the polyphase domain. Numerical experiments show that the proposed noniterative implementation achieves the same results obtained by the original AP algorithm at convergence, but is about an order of magnitude faster than the latter.

iterative_demosaicking_ei09.pdf