nils-herrmann/clean_scirepeval huggingface dataset:
Wavelet packets-based image coding using joint space-frequency quantization

A novel quantization scheme targeted at jointly optimizing the spatial and frequency characterization of the wavelet representation of images was introduced in Xiong et al. (1993) for image compression applications. The present authors extend the concept of joint space-frequency quantization (SFQ) to the more flexible class of wavelet packet representations (Coifman and Wickerhauser, 1992), which are a generalization of the multiresolution decomposition using the wavelet transform. They propose a fast algorithm to jointly search for the best wavelet packet basis and space-frequency quantizer, presenting empirical evidence of its high performance (e.g., for the "Barbara" image coded at 0.5 b/p, they get a 0.7 dB gain in PSNR over the fixed-wavelet based SFQ of Xiong et al. and 1.5 dB over Shapiro's embedded wavelet coder (Shapiro, 1993)).<<ETX>>
A simple algorithm for removing blocking artifacts in block-transform coded images

Despite their widespread popularity, the JPEG and MPEG compression standards can lead to noticeable "blocking" artifacts-artifical rectangular discontinuities in the decoded image. Powerful postprocessing algorithms have been developed to remove blocking artifacts without destroying key image information. However, all but the simplest algorithms can be too complex for real-time applications such as video and still image decoding. We introduce a fast, easy-to-implement algorithm that removes blockiness by performing a simple nonlinear smoothing of pixels. This approach significantly improves visual quality and achieves subjective and objective (PSNR) gains that are competitive with the best deblocking algorithms reported in the literature at much reduced computational complexity.
Compressed sensing using sparse-graph codes for the continuous-alphabet setting

In this paper, we consider the compressive sensing (CS) problem in the presence of noise. The problem is to recover a K-sparse signal s ∈ ℝn from noisy linear measurements y = As + w. We propose a fast recovery algorithm that can reconstruct any K-sparse signal s with time complexity that grows linearly in K and sublinearly in n. Specifically, with high probability, our algorithm is able to recover an arbitrarily large fraction of the support of the sparse signal using Θ(K log(n) log log(n)) samples and Θ(K log1+r(n)) computational cost, where r > 0 is an arbitrarily small constant. The sample and time complexities are near order-optimal. Further, our algorithm is able to recover the exact support with Θ(K log(K) log(n) log log(n)) measurements and time complexity of Θ(K log(K) log1+r(n)). With a mild technical assumption on the existence of a code with universal decoding algorithm and small decoding complexity, our algorithm can achieve Θ(K log(n)) sample and time complexities for the large fraction recovery, and furthermore, Θ(K log(K) log(n)) sample and time complexities for the full support recovery. The design of measurements and the recovery algorithm are based on sparse graph codes. We also justify our theoretical results with numerical experiments.
Decentralized erasure codes for distributed networked storage

In this correspondence, we consider the problem of constructing an erasure code for storage over a network when the data sources are distributed. Specifically, we assume that there are n storage nodes with limited memory and k<n sources generating the data. We want a data collector, who can appear anywhere in the network, to query any k storage nodes and be able to retrieve the data. We introduce decentralized erasure codes, which are linear codes with a specific randomized structure inspired by network coding on random bipartite graphs. We show that decentralized erasure codes are optimally sparse, and lead to reduced communication, storage and computation cost over random linear coding.
Analysis of denoising by sparse approximation with random frame asymptotics

If a signal x is known to have a sparse representation with respect to a frame, the signal can be estimated from a noise-corrupted observation y by finding the best sparse approximation to y. This paper analyzes the mean squared error (MSE) of this denoising scheme and the probability that the estimate has the same sparsity pattern as the original signal. The first main result is an MSE bound that depends on a new bound on approximating a Gaussian signal as a linear combination of elements of an overcomplete dictionary. This bound may be of independent interest for source coding. Further analyses are for dictionaries generated randomly according to a spherically-symmetric distribution and signals expressible with single dictionary elements. Easily-computed approximations for the probability of selecting the correct dictionary element and the MSE are given. In the limit of large dimension, these approximations have simple forms. The asymptotic expressions reveal a critical input signal-to-noise ratio (SNR) for signal recovery
Exact-Repair MDS Code Construction Using Interference Alignment

The high repair cost of (n, k) Maximum Distance Separable (MDS) erasure codes has recently motivated a new class of MDS codes, called Repair MDS codes, that can significantly reduce repair bandwidth over conventional MDS codes. In this paper, we describe (n, k, d) Exact-Repair MDS codes, which allow for any failed node to be repaired exactly with access to d survivor nodes, where k ≤ d ≤ n-1. We construct Exact-Repair MDS codes that are optimal in repair bandwidth for the cases of: (α) k/n ≤ 1/2 and d ≥ 2k - 11; (b) k ≤ 3. Our codes are deterministic and require a finite-field size of at most 2(n - k). Our constructive codes are based on interference alignment techniques.
Distributed data storage in sensor networks using decentralized erasure codes

We assume a large-scale wireless sensor network of n nodes, measuring a physical quantity of interest (e.g. temperature). Most of the sensors are used as storage devices and relays while only a fraction (k out of n) is gathering data. We assume that each node can store at most one data packet. We are interested in storing these k data packets in the n nodes using redundancy so that we can reconstruct the original measurements by asking any k storage nodes in the network (with high probability). We show how this problem is closely related with the distributed construction of an erasure code. To solve this problem, we introduce a new class of erasure codes that can be created without gathering all data at one central location and show that by using these decentralized erasure codes, it is possible to diffuse the data by "pre-routing" only O(ln n) packets per data node to randomly selected storage nodes.
Joint thresholding and quantizer selection for transform image coding: entropy-constrained analysis and applications to baseline JPEG

Striving to maximize baseline (Joint Photographers Expert Group-JPEG) image quality without compromising compatibility of current JPEG decoders, we develop an image-adaptive JPEG encoding algorithm that jointly optimizes quantizer selection, coefficient "thresholding", and Huffman coding within a rate-distortion (R-D) framework. Practically speaking, our algorithm unifies two previous approaches to image-adaptive JPEG encoding: R-D optimized quantizer selection and R-D optimal thresholding. Conceptually speaking, our algorithm is a logical consequence of entropy-constrained vector quantization (ECVQ) design principles in the severely constrained instance of JPEG-compatible encoding. We explore both viewpoints: the practical, to concretely derive our algorithm, and the conceptual, to justify the claim that our algorithm approaches the best performance that a JPEG encoder can achieve. This performance includes significant objective peak signal-to-noise ratio (PSNR) improvement over previous work and at high rates gives results comparable to state-of-the-art image coders. For example, coding the Lena image at 1.0 b/pixel, our JPEG encoder achieves a PSNR performance of 39.6 dB that slightly exceeds the quoted PSNR results of Shapiro's wavelet-based zero-tree coder. Using a visually based distortion metric, we can achieve noticeable subjective improvement as well. Furthermore, our algorithm may be applied to other systems that use run-length encoding, including intraframe MPEG and subband or wavelet coding.
Critically-sampled perfect-reconstruction spline-wavelet filterbanks for graph signals

Inspired by first-order spline wavelets in classical signal processing, we introduce two-channel (low-pass and high-pass), critically-sampled, perfect-reconstruction filterbanks for signals defined on circulant graphs, which accommodate linear shift-invariant filtering. We then generalize to filters that process signals defined on noncirculant graphs. We apply these filters, which can be tuned to approximate desired frequency responses, to signals defined on synthetic graphs and examine their performance.
An optimal and efficient soft caching algorithm for network image retrieval

This paper addresses optimizing cache allocation in a distributed image database system over computer networks. We consider progressive image file formats, and "soft" caching strategies, in which each image is allocated a variable amount of cache memory, in an effort to minimize the expected image transmission delay time. A simple and efficient optimization algorithm is proposed, and is generalized to include multiple proxies and clients in a network scenario. With optimality proven, our algorithm is surprisingly simple, and is based on sorting the images according to a special priority index. We also present an adaptive real-time cache allocation/replacement strategy that can be incorporated into Web browsers with minimum computational overhead. Simulation results are presented to validate our algorithm.
Computationally efficient optimal power allocation algorithms for multicarrier communication systems

We present an optimal, computationally efficient, integer-bit power allocation algorithm for discrete multitone modulation. Using efficient lookup table searches and a Lagrange-multiplier bisection search, our algorithm converges faster to the optimal solution than existing techniques and can replace the use of suboptimal methods because of its low computational complexity. Fast algorithms are developed for the data rate and performance margin maximization problems.
Exact-repair MDS codes for distributed storage using interference alignment

The high repair cost of (n, k) Maximum Distance Separable (MDS) erasure codes has recently motivated a new class of codes, called Regenerating Codes, that optimally trade off storage cost for repair bandwidth. In this paper, we address bandwidth-optimal (n, k, d) Exact-Repair MDS codes, which allow for any failed node to be repaired exactly with access to arbitrary d survivor nodes, where k ≤ d ≤ n − 1. Under scalar-linear codes which do not permit symbol-splitting, we construct Exact-Repair MDS codes that are optimal in repair bandwidth for the case of k/n ≤ 1/2 and d ≥ 2k − 1. Our codes are deterministic and require a finite-field size of at most 2(n − k). Under vector-linear codes which allow for the break-up of stored symbols into arbitrarily small subsymbols, we show the existence of optimal Exact-Repair codes for the entire admissible range of possible (n, k, d), i.e., k < n and k ≤ d ≤ n − 1. That is, we establish the existence of vector-linear Exact-Repair MDS codes that match the fundamental cutset lower bound. Our approach for both the constructive scalar-linear code design and for the existence of vector-linear codes is based on interference alignment techniques.
On functional duality in multiuser source and channel coding problems with one-sided collaboration

In this paper, we address duality in a variety of multiuser source and channel coding problems under different scenarios of "one-sided" inter-terminal collaboration at either the transmitter or at the receiver. First we consider duality between broadcast channel coding and distributed source coding problems. We also consider a new source coding problem in this paper, which we refer to as distributed reconstruction source coding. This problem is closely related to the multiple description source coding problem. We then consider duality between this problem and the multiple access channel coding problem. Our notion of duality in this paper is in a functional sense, where the optimal encoder mapping for a multiuser source coding problem becomes identical to the optimal decoder mapping for the dual multiuser channel coding problem, and vice versa. For ease of illustration we give the formulation only for systems which involve either two encoders or two decoders. Our formulation can be easily extended to the multiuser (more than two noncollaborating terminals) case. We present the precise mathematical conditions under which these encoder-decoder mappings are swappable in the two dual multiuser communication problems, identifying the key roles played by the source distortion and channel cost measures respectively in the multiuser source and channel coding problems in capturing this duality.
Rate efficient remote video file synchronization

Video file synchronization between remote users is an important task in many applications. Re-transmission of a video that has been only slightly modified is expensive, wasteful and avoidable. We propose a scheme that automatically detects and sends only modified content according to some user defined distortion constraint to enable rate savings under a wide range of video edits. Through the use of a low-rate hierarchical hashing scheme, we can detect modifications with some spatial granularity. We also apply distributed source coding techniques to exploit correlation between remote copies for a further rate rebate. Experimental results show that the proposed approach achieves up to 7× rate reduction when compared to re-transmitting.
A characterization of functional duality between source and channel coding

Source coding under a rate-distortion (R-D) constraint and channel coding under a channel cost constraint have long been considered as duals of each other starting from Shannon (1959). We address this duality with the objective of providing a mathematical characterization of it in a functional sense. To be specific, given an optimal source (channel) coding scheme, we detail the conditions under which such a scheme is a functional dual to a channel (respectively source) coding scheme. We show that this functional duality is enabled through appropriate choices of metrics and constraints for the dual source (or channel) coding problem. We then extend this duality formulation to source and channel coding with side information.
Dither-based secure image hashing using distributed coding

We propose an image hashing algorithm that is based on distributed compression principles. The algorithm assumes the availability of a robust feature vector extracted from the image. Then a suitable dither sequence is added to this feature vector, and the resulting dithered feature vector is compressed using distributed compression principles. We prove that the dither sequence can be used to guarantee information-theoretic security. Applications of our proposed secure image hashing scheme include video watermarking, image authentication, and image database management.
Overcoming untuned radios in wireless networks with network coding

The drive toward the implementation and massive deployment of wireless sensor networks calls for ultralow-cost and low-power nodes. While the digital subsystems of the nodes are still following Moore's Law, there is no such trend regarding the performance of analog components. This work proposes a fully integrated architecture of both digital and analog components (including local oscillator) that offers significant reduction in cost, size, and overall power consumption of the node. Even though such a radical architecture cannot offer the reliable tuning of standard designs, it is shown that by using random network coding, a dense network of such nodes can achieve throughput linear in the number of channels available for communication. Moreover, the ratio of the achievable throughput of the untuned network to the throughput of a tuned network with perfect coordination is shown to be close to 1/e. This work uses network coding to leverage the fact that throughput equal to the max-flow in a graph is achievable even if the topology is not know a priori. However, the challenge here is finding the max-flow of the random graph corresponding to the network.
A low-power multimedia communication system for indoor wireless applications

A low-power multimedia communication system is proposed. Power reductions are achieved by employing dynamic algorithm transforms and joint source-channel coding to reconfigure the system in the presence of variabilities in source and channel data. Configuration parameters are source rate, error correction capability of the channel encoder/decoder, number of powered-up fingers in the RAKE receiver and transmit power of the power amplifier. Energy-optimum configurations are obtained by minimizing energy consumption under the constraints of end-to-end distortion and total transmission rate. The proposed system is tested over a variety of images, distances (ranging from 2 to 100 meters) and multipath channels. Simulation results using 0.18 /spl mu/m, 2.5 V CMOS parameters show that the reconfigurable system can achieve average energy savings of 59% as compared to a fixed system designed for the worst case. Also, the proposed system consumes 16% less energy as compared to a transmit-power-controlled system.
The role of game theory in key agreement over a public channel

In this work we study the problem of key agreement over a public noiseless channel when Alice, Bob and Charlie observe discrete memoryless sources of an unknown distribution. Alice and Bob want to agree on a key KAB that is protected from Charlie. At the same time, Alice and Charlie want to agree on a key KAC that is protected from Bob. In order to construct codebooks for the key agreement, Alice has to know how the sources are distributed. Therefore, she requests Bob and Charlie to send her sufficient information about their observations. We also assume that Bob and Charlie, besides agreeing with Alice on the keys, want to learn as much as possible about the other user's key: we call this quantity the leakage. We model these reports by having Bob and Charlie select discrete memoryless channels and passing their true observations through them. We approach this problem from a game-theoretic point of view. For a class of Bob and Charlie's objective functions which are linear in the key rate and the leakage rate, we characterize a Nash equilibrium. Also, we propose a strategy that Alice can apply in order to ensure that Bob and Charlie's honest reporting is a Nash equilibrium.
High-dimensional coded matrix multiplication

Coded computation is a framework for providing redundancy in distributed computing systems to make them robust to slower nodes, or stragglers. In , the authors propose a coded computation scheme based on maximum distance separable (MDS) codes for computing the product ATB, and this scheme is suitable for the case where one of the matrices is small enough to fit into a single compute node. In this work, we study coded computation involving large matrix multiplication where both matrices are large, and propose a new coded computation scheme, which we call product-coded matrix multiplication. Our analysis reveals interesting insights into which schemes perform best in which regimes. When the number of backup nodes scales sub-linearly in the size of the product, the product-coded scheme achieves the best run-time performance. On the other hand, when the number of backup nodes scales linearly in the size of the product, the MDS-coded scheme achieves the fundamental limit on the run-time performance. Further, we propose a novel application of low-density-parity-check (LDPC) codes to achieve linear-time decoding complexity, thus allowing our proposed solutions to scale gracefully.
Robust turbo-based data hiding for image and video sources

Channel coding with side information (CCSI) provides a powerful framework for constructing data embedding codes. As a result, there has been a considerable amount of work done in trying to apply these CCSI codes to the field of image and video watermarking. The CCSI codes that exist in the literature however, are relatively far from theoretical bounds. Furthermore, these codes, by themselves, are not well-suited for dealing with geometrical distortions which often appear in watermarking attacks. In this paper we propose a CCSI code that is closer to the theoretical bounds (within 2.0 dB) than the codes that exist in the literature. In addition, we show how this code construction can be combined with a synchronization code to deal with geometrical distortions.
Frequency-shift-invariant orthonormal wavelet packet representations

It is commonly known that the dyadic structure of wavelet expansions results in both time- and frequency-translation sensitivity of an input signal. We develop the first efficient method to reduce frequency alignment sensitivity by introducing a wavelet packet decomposition that is invariant to frequency shifts of a signal. A frequency-shifted wavelet packet library is presented, and an efficient best-basis algorithm is developed to determine the best signal representation among all frequency shifts of a signal. The algorithm computes all frequency-shifted coefficients in O(N/sup 2/) operations, followed by an efficient depth-first tree search of the same complexity.
Image coding based on mixture modeling of wavelet coefficients and a fast estimation-quantization framework

We introduce a new image compression paradigm that combines compression efficiency with speed, and is based on an independent "infinite" mixture model which accurately captures the space-frequency characterization of the wavelet image representation. Specifically, we model image wavelet coefficients as being drawn from an independent generalized Gaussian distribution field, of fixed unknown shape for each subband, having zero mean and unknown slowly spatially-varying variances. Based on this model, we develop a powerful "on the fly" estimation-quantization (EQ) framework that consists of: (i) first finding the maximum-likelihood estimate of the individual spatially-varying coefficient field variances based on causal and quantized spatial neighborhood contexts; and (ii) then applying an off-line rate-distortion (R-D) optimized quantization/entropy coding strategy, implemented as a fast lookup table, that is optimally matched to the derived variance estimates. A distinctive feature of our paradigm is the dynamic switching between forward and backward adaptation modes based on the reliability of causal prediction contexts. The performance of our coder is extremely competitive with the best published results in the literature across diverse classes of images and target bitrates of interest, in both compression efficiency and processing speed. For example, our coder exceeds the objective performance of the best zerotree-based wavelet coder based on space-frequency-quantization at all bit rates for all tested images at a fraction of its complexity.