nils-herrmann/clean_scirepeval huggingface dataset:
Quadtrees for embedded surface visualization: constraints and efficient data structures

The quadtree data structure is widely used in digital image processing and computer graphics for modeling spatial segmentation of images and surfaces. A quadtree is a tree in which each node has four descendants. Since most algorithms based on quadtrees require complex navigation between nodes, efficient traversal methods as well as efficient storage techniques are of great interest. In this paper we first propose an efficient indexing scheme for a linear (pointerless) quadtree data structure. Such a quadtree is stored using a unidimensional array of nodes. Our indexing scheme has the property that the navigation between any pair of nodes can be computed in constant time. Moreover the navigation across multiple quadtrees can be achieved at the same cost. We illustrate our results on applications in computer graphics. We first show how the problem of computing a so-called restricted quadtree can be solved at optimal cost, e.g. with a computational complexity having the order of magnitude of the problem size. Then, we explain how this problem can be solved in the case of surfaces modeled using multiple quadtrees. Finally, we show how a tessellated sphere can be implemented and navigated using our data structure.
High order balanced multiwavelets

We study the issue of regularity for multiwavelets. We generalize here the concept of balancing for higher degree discrete-time polynomial signals and link it to a very natural factorization of the lowpass refinement mask that is the counterpart of the well-known zeros at /spl pi/ condition for wavelets. This enables us to clarify the subtle relations between approximation power, smoothness and balancing order. Using these new results, we are also able to construct a family of orthogonal multiwavelets with symmetries and compact support that is indexed by the order of balancing.
From acoustic room reconstruction to slam

Recent works on reconstruction of room geometry from echoes assume that the geometry of the sensor array is known. In this paper, we show that such an assumption is not essential; echoes provide sufficient clues to reconstruct the room's and the array's geometries jointly, even from a single acoustic event. Rather than focusing on the combinatorial problem of matching the walls and the recorded echoes, we provide algorithms for solving the joint estimation problem in practical cases when this matching is known and the number of microphones is small. We then explore intriguing connections between this problem and simultaneous localization and mapping (SLAM), and show that SLAM can be solved by the same methods. Finally, we demonstrate how effective the proposed methods are by numerical simulations and experiments with real measured room impulse responses.
Lossy compression of individual signals based on string matching and one pass codebook design

This paper describes an effort to extend the Lempel-Ziv algorithm to a practical universal lossy compression algorithm. It is based on the idea of approximate string matching with a rate-distortion (R-D) criterion, and is addressed within the framework of vector quantization (VQ). A practical one pass algorithm for VQ codebook construction and adaptation for individual signals is developed which assumes no prior knowledge of the source statistics and involves no iteration. We call this technique rate-distortion Lempel-Ziv (RDLZ). As in the case of the Lempel-Ziv algorithm, the encoded bit stream consists of codebook (dictionary) updates as well as indices (pointers) to the codebook. The idea of "trading" bits for distortion in modifying the codebook will be introduced. Experimental results show that, for Gaussian sources as well as real images, RDLZ performs comparably, sometimes favorably, to static codebook VQ trained on the corresponding sources or images.
DASS: Distributed Adaptive Sparse Sensing

Wireless sensor networks are often designed to perform two tasks: sensing a physical field and transmitting the data to end-users. A crucial design aspect of a WSN is the minimization of the overall energy consumption. Previous researchers aim at optimizing the energy spent for the communication, while mostly ignoring the energy cost of sensing. Recently, it has been shown that considering the sensing energy cost can be beneficial for further improving the overall energy efficiency. More precisely, sparse sensing techniques were proposed to reduce the amount of collected samples and recover the missing data using data statistics. While the majority of these techniques use fixed or random sampling patterns, we propose adaptively learning the signal model from the measurements and using the model to schedule when and where to sample the physical field. The proposed method requires minimal on-board computation, no inter-node communications, and achieves appealing reconstruction performance. With experiments on real-world datasets, we demonstrate significant improvements over both traditional sensing schemes and the state-of-the-art sparse sensing schemes, particularly when the measured data is characterized by a strong intra-sensor (temporal) or inter-sensors (spatial) correlation.
Sampling and Reconstruction of Spatial Fields Using Mobile Sensors

Spatial sampling is traditionally studied in a static setting where static sensors scattered around space take measurements of the spatial field at their locations. In this paper, we study the emerging paradigm of sampling and reconstructing spatial fields using sensors that move through space. We show that mobile sensing offers some unique advantages over static sensing in sensing bandlimited spatial fields. Since a moving sensor encounters such a spatial field along its path as a time-domain signal, a time-domain anti-aliasing filter can be employed prior to sampling the signal received at the sensor. Such a filtering procedure, when used by a configuration of sensors moving at constant speeds along equispaced parallel lines, leads to a complete suppression of spatial aliasing in the direction of motion of the sensors. We analytically quantify the advantage of using such a sampling scheme over a static sampling scheme by computing the reduction in sampling noise due to the filter. We also analyze the effects of nonuniform sensor speeds on the reconstruction accuracy. Using simulation examples, we demonstrate the advantages of mobile sampling over static sampling in practical problems. We extend our analysis to sampling and reconstruction schemes for monitoring time-varying bandlimited fields using mobile sensors. We demonstrate that in some situations we require a lower density of sensors when using a mobile sensing scheme instead of the conventional static sensing scheme. The exact advantage is quantified for a problem of sampling and reconstructing an audio field.
Adaptive transforms for image coding using spatially varying wavelet packets

We introduce a novel, adaptive image representation using spatially varying wavelet packets (WPs), Our adaptive representation uses the fast double-tree algorithm introduced previously (Herley et al., 1993) to optimize an operational rate-distortion (R-D) cost function, as is appropriate for the lossy image compression framework. This involves jointly determining which filter bank tree (WP frequency decomposition) to use, and when to change the filter bank tree (spatial segmentation). For optimality, the spatial and frequency segmentations must be done jointly, not sequentially. Due to computational complexity constraints, we consider quadtree spatial segmentations and binary WP frequency decompositions (corresponding to two-channel filter banks) for application to image coding. We present results verifying the usefulness and versatility of this adaptive representation for image coding using both a first-order entropy rate-measure-based coder as well as a powerful space-frequency quantization-based (SPQ-based) wavelet coder introduced by Xiong et al. (1993).
Group Testing With Probabilistic Tests: Theory, Design and Application

Identification of defective members of large populations has been widely studied in the statistics community under the name of group testing. It involves grouping subsets of items into different pools and detecting defective members based on the set of test results obtained for each pool. In a classical noiseless group testing setup, it is assumed that the sampling procedure is fully known to the reconstruction algorithm, in the sense that the existence of a defective member in a pool results in the test outcome of that pool to be positive. However, this may not be always a valid assumption in some cases of interest. In particular, we consider the case where the defective items in a pool can become independently inactive with a certain probability. Hence, one may obtain a negative test result in a pool despite containing some defective items. As a result, any sampling and reconstruction method should be able to cope with two different types of uncertainty, i.e., the unknown set of defective items and the partially unknown, probabilistic testing procedure. In this work, motivated by the application of detecting infected people in viral epidemics, we design nonadaptive sampling procedures that allow successful identification of the defective items through a set of probabilistic tests. Our design requires only a small number of tests to single out the defective items. In particular, for a population of size N and at most K defective items with activation probability p, our results show that M = O(K2 log (N/K)/p3) tests is sufficient if the sampling procedure should work for all possible sets of defective items, while M = O(K log (N)/p3) tests is enough to be successful for any single set of defective items. Moreover, we show that the defective members can be recovered using a simple reconstruction algorithm with complexity of O(MN).
From local to global parameter estimation in panoramic photographic reconstruction

This paper addresses a key issue in the problem of reconstructing a panoramic view from several pictures taken with a hand-held camera, namely the estimation of some ill-posed parameters using an external constraint. For many practical reasons, a panoramic reconstruction has to be performed in several independent steps, resulting in a set of different measurements of the same reality. For example, the focal length can be estimated with each pair of overlapping images. The idea is to introduce some a priori knowledge about the world by means of a constraint on the parameter set. In the former example, the constraint would impose equality on all the focal length estimates. This paper describes the appropriate correction that needs to be applied to the parameters in order to obtain a coherent result. It also suggests a way to evaluate if a constraint is plausible given a set of initial estimates. The basic idea behind the method is to modify the parameters without significantly changing the overlapping part of the images. The method is evaluated using two different experimental setups. The first aims at improving the quality of a full panoramic image. The second measures independently the positions in space of two planes using two pictures. The latter experiment shows that the two computed motions can be considered as a single one with two different planes in space.
Image coding with windowed modulated filter banks

Lapped orthogonal transforms (LOT) have been introduced to provide a solution to the problem of blocking that occurs with transform coding at low bit rate. For the purpose of image coding, a more general class of exact reconstruction filter banks, that provides an additional degree of freedom in controlling ringing while relaxing the symmetry constraints of LOTs, is introduced. It is shown that windowed modulated filter banks are a very attractive candidate for image coding, since by allowing almost arbitrary selection of the window, they provide a control of the impulse response of the filters in the filter bank. The outputs of the windowed, modulated filter bank are quantized and entropy-coded in a way analogous to DCT (discrete cosine transform) coefficients. Comparisons are made between the filter bank and the DCT from the point of view of mean square error and subjective quality.<<ETX>>
Wavelets and recursive filter banks

It is shown that infinite impulse response (IIR) filters lead to more general wavelets of infinite support than finite impulse response (FIR) filters. A complete constructive method that yields all orthogonal two channel filter banks, where the filters have rational transfer functions, is given, and it is shown how these can be used to generate orthonormal wavelet bases. A family of orthonormal wavelets that have a maximum number of disappearing moments is shown to be generated by the halfband Butterworth filters. When there is an odd number of zeros at pi it is shown that closed forms for the filters are available without need for factorization. A still larger class of orthonormal wavelet bases having the same moment properties and containing the Daubechies and Butterworth filters as the limiting cases is presented. It is shown that it is possible to have both linear phase and orthogonality in the infinite impulse response case, and a constructive method is given. It is also shown how compactly supported bases may be orthogonalized, and bases for the spline function spaces are constructed.
Arbitrary orthogonal tilings of the time-frequency plane

Expansions which give arbitrarily orthonormal tilings of the time-frequency plane are considered. These differ from the short-time Fourier transform, wavelet transform, and wavelet packets tilings in that they change over time. It is shown how orthonormal tilings can be achieved using time-varying orthogonal tree structures, which preserve orthogonality, even across transitions. One method is based on lapped orthogonal transforms, which makes it possible to change the number of channels in the transform. A second method is based on the construction of boundary filters and gives arbitrary tilings. An algorithm is presented which for a given signal decides on the best binary segmentation and which tree split to use for each segment. It is optimal in a rate-distortion sense. The results of experiments on test signals are presented.<<ETX>>
Perceptually hidden data transmission over audio signals

A data transmission framework is proposed to embed digital data into an audio signal in a perceptually undetectable or almost undetectable way. The resulting signal can be reproduced as is with no loss of acoustic quality; the embedded data can be exactly retrieved at the decoder. The transmission process exploits the perceptual redundancy of the audio signal to conceal the acoustic impact of the embedded data; encoding of side information is used to inform the receiver of the time-varying structure of the masking properties of the audio signal. A sample implementation is described with a throughput of the order of 30 kbit/sec over CD-quality audio.
On the capacity of wireless networks: the relay case

Gupta and Kumar  2000) determined the capacity of wireless networks under certain assumptions, among them point-to-point coding, which excludes for example multi-access and broadcast codes. We consider essentially the same physical model of a wireless network under a different traffic pattern, namely the relay traffic pattern, but we allow for arbitrarily complex network coding. In our model, there is only one active source/destination pair, while all other nodes assist this transmission. We show code constructions leading to achievable rates and derive upper bounds from the max-flow min-cut theorem. It is shown that lower and upper bounds meet asymptotically as the number of nodes in the network goes to infinity, thus proving that the capacity of the wireless network with n nodes under the relay traffic pattern behaves like log n bits per second. This demonstrates also that network coding is essential: under the point-to-point coding assumption considered by Gupta et al., the achievable rate is constant, independent of the number of nodes. Moreover, the result of this paper has implications' and extensions to fading channels and to sensor networks.
Sequences with minimal time-frequency spreads

For a given time or frequency spread, one can always find continuous-time signals, which achieve the Heisenberg uncertainty principle bound. This is known, however, not to be the case for discrete-time sequences; only widely spread sequences asymptotically achieve this bound. We provide a constructive method for designing sequences that are maximally compact in time for a given frequency spread. By formulating the problem as a semidefinite program, we show that maximally compact sequences do not achieve the classic Heisenberg bound. We further provide analytic lower bounds on the time-frequency spread of such signals.
Wavelets and filter banks: theory and design

The wavelet transform is compared with the more classical short-time Fourier transform approach to signal analysis. Then the relations between wavelets, filter banks, and multiresolution signal processing are explored. A brief review is given of perfect reconstruction filter banks, which can be used both for computing the discrete wavelet transform, and for deriving continuous wavelet bases, provided that the filters meet a constraint known as regularity. Given a low-pass filter, necessary and sufficient conditions for the existence of a complementary high-pass filter that will permit perfect reconstruction are derived. The perfect reconstruction condition is posed as a Bezout identity, and it is shown how it is possible to find all higher-degree complementary filters based on an analogy with the theory of Diophantine equations. An alternative approach based on the theory of continued fractions is also given. These results are used to design highly regular filter banks, which generate biorthogonal continuous wavelet bases with symmetries.
Teaching signal processing online: A report from the trenches

After years of experimentation, online teaching has gone through a phase transition with the appearance of massive open online courses (MOOCs), following the model pioneered by Salman Khan with short videos and the use of tablets. Dozens of university-level courses are now available, and followed by hundreds of thousands of online students. We report on early experiences with teaching “Fundamentals of Electrical Engineering” and “Digital Signal Processing” on an open online platform (Coursera). We address in particular: (i) suitability of online platforms for signal processing oriented topics; (ii) structuring of material for the online format; (iii) quizzes and exercises for large classes; (iv) grading methods and possible certification issues; (v) learning from teaching, forums, and data mining of students feedback.
Interpolative multiresolution coding of advance television with compatible subchannels

A multiresolution representation for video signals is introduced. A three-dimensional spatiotemporal pyramid algorithms for high-quality compression of advanced television sequences is presented. The scheme utilizes a finite memory structure and is robust to channel errors, provides compatible subchannels, and can handle different scan formats, making it well suited for the broadcast environment. Additional features such as fast random access and reverse playback make it suitable for digital storage as well. Model-based processing is used both over space and time, where motion-based interpolation is used. Interpolation in an FIR (finite impulse response) scheme solves uncovered area problems, considerably improving the temporal prediction. The complexity is comparable to that of previous recursive schemes. Computer simulations indicate that high compression factors (about an order of magnitude) are easily achieved with no apparent loss of quality. The scheme also has a number of commonalities with the emerging MPEG standard.
Orthogonal Hilbert transform filter banks and wavelets

Complex wavelet transforms offer the opportunity to perform directional and coherent processing based on the local magnitude and phase of signals and images. Although denoising, segmentation, and image enhancement are significantly improved using complex wavelets, the redundancy of most current transforms hinders their application in compression and related problems. In this paper we introduce a new orthonormal complex wavelet transform with no redundancy for both real- and complex-valued signals. The transform's filter bank features a real low pass filter and two complex high pass filters arranged in a critically sampled three-band structure. Placing symmetry and orthogonality constraints on these filters, we find that each high-pass filter can be factored into a real high pass filter followed by an approximate Hilbert transform filter.
Sensor networks for diffusion fields: Detection of sources in space and time

We consider the problem of reconstructing a diffusion field, such as temperature, from samples collected by a sensor network. Motivated by the fast decay of the eigenvalues of the diffusion equation, we approximate the field by a truncated series. We show that the approximation error decays rapidly with time. On the other hand, the information content in the field also decays with time, suggesting the need for a proper choice of the sampling strategy. We propose two algorithms for sampling and reconstruction of the field. The first one reconstructs the distribution of point sources appearing at known times using the finite rate of innovation (FRI) framework. The second algorithm addresses a more difficult problem of estimating the unknown times at which the point sources appear, in addition to their locations and magnitudes. It relies on the assumption that the sources appear at distinct times. We verify that the algorithms are capable of reconstructing the field accurately through a set of numerical experiments. Specifically, we show that the second algorithm successfully recovers an arbitrary number of sources with unknown release times, satisfying the assumption. For simplicity, we develop the 1-D theory, noting the possibility of extending the framework to more general domains.
Accurate recovery of a specularity from a few samples of the reflectance function

We present a new technique for estimating the specular peak of the bidirectional reflectance distribution function (BRDF) based on finite rate of innovation (FRI) sampling. The specular component of the BRDF varies rapidly, so it is challenging to acquire it by point-wise sampling. Yet, the knowledge of its precise location is key to render realistically complex materials. We show how to adapt the FRI framework to accurately determine the location of a single pulse when the sampling kernel is unknown. We use this result to determine the position of the specularity, and then estimate its shape by non-linear optimization. We demonstrate the feasibility of our approach in simulations and via a practical experiment using a custom-built BRDF acquisition device.
Groebner basis techniques in multidimensional multirate systems

The Euclidean algorithm is a frequently used tool in the analysis of one-dimensional (1D) multirate systems. This tool is however not available for multidimensional (MD) multirate systems. The authors discus how Groebner basis techniques can fill this gap. After presenting the relevant facts about Groebner bases, they show in a few examples how this technique can contribute to MD multirate systems theory.