nils-herrmann/clean_scirepeval huggingface dataset:
Arithmetic encoding of Markov random fields

This paper introduces methods for losslessly encoding a Markov random field (MRF) with arithmetic coding. The issues are how to choose the pixel scan order and how to produce coding distributions to accompany the pixels. For an MRF based on an acyclic graph, we choose a scan consistent with the graph and use Belief Propagation (BP) to efficiently compute the optimal coding distributions. For an MRF based on a cyclic graph, we use Local Conditioning (LC) to losslessly encode an appropriately chosen scan of a loop cutset, whose removal leaves an acyclic graph whose pixels can be encoded by the previous method. The results include BP-like formulas for LC in an undirected graph and a formula for the complexity of LC in a cyclic graph. As a first application of the methods, preliminary results of applying the method to an Ising model are given.
An adaptive lighting correction method for matched-texture coding

Matched-Texture Coding is a novel image coder that utilizes the self-similarity of natural images that include textures, in order to achieve structurally lossless compression. The key to a high compression ratio is replacing large image blocks with previously encoded blocks with similar structure. Adjusting the lighting of the replaced block is critical for eliminating illumination artifacts and increasing the number of matches. We propose a new adaptive lighting correction method that is based on the Poisson equation with incomplete boundary conditions. In order to fully exploit the benefits of the adaptive Poisson lighting correction, we also propose modifications of the side-matching (SM) algorithm and structural texture similarity metric. We show that the resulting matched-texture algorithm achieves better coding performance.
Reliability and efficiency of flexibly decodable distributed coding strategies

Distributed lossless coding of correlated sources offers the potential for sizable reductions in coding rates in comparison to independent coding. However, it is more sensitive to encoder failures as the loss of one encoder may cause the decoding of many sources to fail. Strategies for increasing the reliability of lossless distributed coding were first considered by Marco and Neuhoff. This paper introduces and analyzes several new strategies based on flexible decoding, in contrast to the rigid decoding strategies considered previously. The new flexible schemes are found to offer significant gains over the prior rigid schemes.
Hierarchical bilevel image compression based on cutset sampling

We propose a hierarchical lossy bilevel image compression method that relies on adaptive cutset sampling (along lines of a rectangular grid with variable block size) and Markov Random Field based reconstruction. It is an efficient encoding scheme that preserves image structure by using a coarser grid in smooth areas of the image and a finer grid in areas with more detail. Experimental results demonstrate that the proposed method performs as well as or better than the fixed-grid approach, and outperforms other lossy bilevel compression methods in its rate-distortion performance.
Uniform scalar quantizers-distortion and the additive noise model

High-resolution infinite level uniform scalar quantizers are considered for the two cases when cell midpoints and cell centroids are used as reconstruction levels. First, it is shown that asymptotically, as the cell size goes to zero, midpoints induce the same MSE as centroids. Hence, they are asymptotically MSE optimal. Secondly, sufficient conditions are found under which the commonly used additive noise model, when midpoints are used, is asymptotically correct. It is also shown that for input probability density functions (pdf's) that have a single jump discontinuity not at the origin, such a model is not well defined and consequently incorrect.
Least-squares model-based halftoning

A least-squares model-based (LSMB) approach to digital halftoning is proposed. It exploits both a printer model and a model for visual perception. It attempts to produce an optimal halftoned reproduction, by minimizing the squared error between the response of the cascade of the printer and visual models to the binary image and the response of the visual model to the original gray-scale image. It has been shown that the one-dimensional (1-D) least-squares problem, in which each row or column of the image is halftoned independently, can be implemented using the Viterbi algorithm to obtain the globally optimal solution. Unfortunately, the Viterbi algorithm cannot be used in two dimensions. In this paper, the two-dimensional (2-D) least-squares solution is obtained by iterative techniques, which are only guaranteed to produce a total optimum. Experiments show that LSMB halftoning produces better textures and higher spatial and gray-scale resolution than conventional techniques. We also show that the least-squares approach eliminates most of the problems associated with error diffusion. We investigate the performance of the LSMB algorithms over a range of viewing distances, or equivalently, printer resolutions. We also show that the LSMB approach gives us precise control of image sharpness.
Source-channel coding strategies: tandem coding vs. channel-optimized quantization

Two source-channel coding strategies, tandem coding and channel-optimized quantization, are compared on the basis of distortion vs. complexity. For each, formulas for the mean-squared error and complexity used to minimize distortion subject to a complexity constraint. The results suggest there is a threshold such that tandem coding is better than channel-optimized quantization when and only when the complexity constraint is larger than the threshold.
A rate and distortion analysis of chain codes for line drawings

The performance of chain codes for line drawings in the framework of source coding with a fidelity criterion is investigated. A formal characterization is given for a broad class of chain codes that includes the generalized chain codes of Freeman and the convex quantizers of Koplowitz. Measures of distortion (fidelity) and rate (efficiency) are introduced. The distortion and rate are calculated for several types of chain codes applied to straight and slowly curving lines. Several statistical models for straight lines are introduced and the average performance of chain codes for these models is investigated.
A Coding Theorem for Low-Rate Transform Codes

Transform codes are used to study low-rate quantization of stationary Gaussian sources. The transform decorrelates the source samples and then scalar quantization is applied to the vector of transform coefficients. Two bit allocations are considered: the first permits only zero or one bit to be allocated to each transform coefficient (i.e., the scalar quantizers have only one or two levels), and the second is an optimal bit allocation. For the transform codes with the "0-1" bit allocation, a closed-form, parametric expression is derived for the asymptotic (with dimension) rate vs. distortion performance. This expression is compared to the rate-distortion function, as well as to the performance of transform codes with optimal bit allocations. The principal result is that there is a critical rate, determined by the power spectral density, below which (and only below which) 0-1 allocations are optimal. This is a unique result in that it determines optimal theoretical performance for an important class of vector quantizes at low rates. Quantitative results are presented for Gauss-Markov sources.
Rate-distortion behavior at low distortion for densely sampled Gaussian data

It is well known that for discrete-time, stationary sources, most lossy source coding techniques have operational rate-distortion functions that approach the Shannon ratedistortion function with respect to squared error to within an additive constant as distortion approaches zero. With the goal of investigating similar phenomena for continuous-time sources, this paper investigates the low-distortion performance of distributed coding of continuous-time, stationary, Gaussian sources based on high-rate sampling. It is found that for bandlimited sources and nonbandlimited sources whose spectra have sufficiently light, e.g., exponentially decreasing, tails, distributed source coding is asymptotically as good as centralized coding in the small distortion regime. On the other hand, for spectra with tails that decay as a power (greater than one) of frequency, it is found that for small distortions the distributed rate-distortion function is a constant times larger than the Shannon rate-distortion, where the constant decreases as the power increases. For example, it is approximately 1.2 when the power is 2. The conclusion is that for a stationary Gaussian source and asymptotically small distortion, the ratio of the distributed to centralized rate-distortion function is a function of the weight of the tail of the source spectrum. In the process of finding the ratio, the low distortion form of the centralized rate-distortion function is found for sources whose spectra have exponential and power law tails.
Coding by selective prediction: a new scheme for predictive vector quantization

Typically, predictive vector quantization is performed by making a prediction of upcoming data based on previously coded samples, then, using a residual quantizer to code the prediction errors. We take in alternative approach, and introduce coding by selective prediction (CSP). In CSP, there is no residual quantizer - the codebook consists only of a collection of predictors. The encoder selects the predictor that best describes a source block, then transmits the index of that predictor. We give a framework for CSP, then propose a training method for codebook design, similar to the generalized Lloyd algorithm. Using fixed-rate coding, performance results for CSP as an image coder indicate a 0.5 dB improvement over conventional predictive vector quantization at equal rates.
Periodic prefix-synchronized codes: A generating function approach

A generating function method is developed in order to select synchronization markers that maximize the timing span of period-2 periodic prefix-synchronized (PPS) sync-timing coding with small delay. Sync-timing codes are used in situations where conventional data synchronization is required, and data time stamps or time indices are also needed. A PPS code is a sync-timing code in which each encoded block of data is preceded by a synchronization marker, with the markers preceding successive blocks forming a periodic sequence with some period p. Since only PPS codes with small periods can have good rates at small delays, and since codes with p=1 are simply Gilbert's prefix-synchronized codes which have been studied previously in the literature, this paper focuses on p=2 codes. The generating function method, which extends that used by Guibas and Odlyzko to analyze p=1 codes, enables one to find PPS codes with the largest possible timing span among codes with a given delay and rate. It is found that at low delays such optimized PPS codes offer significant advantages over cascaded and natural marker PPS codes. They also compare favorably with embedded-index codes. Finally, for asymptotically large delays, it is shown that the best p=2 PPS codes operate at approximately the same rate and delay, but twice the timing span, of the best p=1 codes.
A new quadtree predictive image coder

A new quadtree-based lossy image compression algorithm is introduced. One new feature is that one pixel in each quadtree block is predictively encoded while the remaining pixels are linearly predicted from this one and from pixels of previous blocks. Another is that the criteria for subdividing a block involves the reproduction error in each pixel, as opposed to the error energy for the entire block. Though the algorithm has very low complexity, its predictive nature gives it good rate/distortion performance and suppresses blocking artifacts. This paper describes the algorithm, shows the results of coding at .5 and .25 bits per pixel, and compares its peak signal-to-noise ratio with other methods.
Local Conditioning on undirected graphs

This paper proposes Local Conditioning as a truly distributed exact version of Belief Propagation for cyclic undirected graphical models. It is shown how to derive explicit recursive updates for messages and beliefs that are truly distributed in the sense that messages are passed between individual nodes of the graph rather than between clustered nodes. Such a distributed algorithm is especially relevant for problems that require a distributed implementation, for example sensor networks. In order to compare its complexity and ease of implementation with a clustered version of Belief Propagation, we illustrate both in a Min-Sum block interpolation problem within the context of an Ising model.
When is overload distortion negligible in uniform scalar quantization?

This paper studies the asymptotic characteristics of optimal fixed-rate uniform scalar quantizers for source densities with infinite support. Asymptotic formulas for the optimal step size and the resulting minimum mean-squared error are given. It is found that the asymptotic significance of overload distortion is directly related to the limit of y/sup -1/E[X|X>y] as y tends to infinity.
Centralized and Distributed Lossy Source Coding of Densely Sampled Gaussian Data, with and without Transforms

With mean-squared error D as a goal, it is well known that one may approach the rate-distortion function R(D) of a spatially nonbandlimited, time IID, continuous- space, discrete-time Gaussian source by spatially sampling at a sufficiently high rate, applying the Karhunen-Loeve transform to sufficiently long blocks, and independently coding transform coefficients of each type at the first-order rate-distortion function of that type, with a distortion target chosen appropriately for that type. This paper compares and contrasts this classical result with several recently explored alternative schemes for encoding source samples taken at a high rate. The first scheme, which scalar quantizes the samples and then losslessly encodes the quantized samples at their entropy-rate, is known to have rate approaching infinity when distortion is held at D. Is such catastrophic behavior due to the scalar quantizer or to the distributed nature of the quantization? Recent results show that even without a transform, but with distributed vector quantization, it is possible to attain performance that differs from the rate-distortion function by only a finite constant. This suggests it was the scalar quantizer that caused the catastrophic behavior. The final recent result suggests the situation is more nuanced, because it shows that if in the classical scheme scalar quantizers with entropy coding replace the ideal coding of the coefficients at their first-order rate-distortion functions, then again performance differs from the rate-distortion function by a finite constant.
An Asymptotic Analysis Of Two-stage Vector Quantization

Two-stage vector quantization is a structured quantization technique having much less complexity and somewhat larger distortion than conventional unstructured single-stage vector quantization. In this paper, we present an asymptotic analysis that quantifies how much larger is its distortion than single-stage VQ, when the first and second stage codebooks are large. summarv Two-stage vector quantization [l] (abbreviated 2VQ applies a kdimensional fiist-stage quantizer to a source vector X = (XI, ...&). producing Ql(X), and then applies a kdimensional second stage quantizer to the error U = X - Ql(x), producing &(U). The final quantized output is Y = Qi(W + Q(W. The encoded rate is the sum of those of the two stages, i.e. RI+ R2 = (loglNl)/k + (log2 N2)k where N1 and N2 denote, respectively, the number of code points in the first and second sta The mean squared error (MSE) resulting from 2VQ is D = IIX-YII2 = EHIUQ(U)II2, where Ilx-yll denotes Euclidean distance. Using a generalized form of Bennett's integral [2] and an asymptotic formula for the probability density of the error from a vector quantizer [3], an approximate formula for the MSE of 2VQ was given in . However, it did not clearly show the effect of the size, NI, of the first-stage quantizer, nor did it show how much larger is the distortion of 2VQ than that attainable with single-stage VQ. To remedy this, we consider two-stage quantization in which the first stage Q1 is characterized by a point density hl(x). a shape profile gl(x,r), an inertial profile ml(x) (derivable from gl) and a size N1 . The second stage is a scaled version of a "template" quantizer Qt . (The point density hl(x) is a function that approximately equals the reciprocal of N1 times the volume of the quantizing cells in the vicinity of x; for fixed x, the shape profile gl(x,r) is a function that partially characterizes the shape of the cells in the vicinity of x; and the inertial profile ml(x) is the normalized moment of inertia of the cells in the vicinity of x.) Specifically, Q2(u) = 6 Qt(uX>, where Qt is a template quantizer with size N2, point density ht(x) and inertial profile mt(x). and where 1 gr
The Best Binary Linear Block Codes for Scalar Source-Channel Coding

This paper finds the best binary linear block codes to use when an IID uniform source is uniform scalar quantized for transmission over a binary symmetric channel, with performance measured by mean squared error (MSE). The best code is found by optimizing the source-channel rate allocation, the linear code, and the assignment of its codewords to quantization indices. A table shows the maximum attained SNR, together with a code that achieves it, for a range of channel transition probabilities and transmission rates. When optimized, the performance of such systems comes within 1 ~ 2 dB of that of the best nonlinear codes found by an iterative algorithm.
Information Rates of Densely Sampled Data: Distributed Vector Quantization and Scalar Quantization With Transforms for Gaussian Sources

This paper establishes rates attainable by several lossy schemes for coding a continuous parameter source to a specified mean-squared-error distortion based on sampling at asymptotically large rates. First, a densely sampled, spatiotemporal, stationary Gaussian source is distributively encoded. The Berger-Tung bound to the distributed rate-distortion function and three convergence theorems are used to obtain an upper bound, expressed in terms of the source spectral density, to the smallest attainable rate at asymptotically large sampling rates. The bound is tighter than that recently obtained by Kashyap Both indicate that with ideal distributed lossy coding, dense sensor networks can efficiently sense and convey a field, in contrast to the negative result obtained by Marco for encoders based on scalar quantization and Slepian-Wolf distributed lossless coding. The second scheme is transform coding with scalar coefficient quantization. A new generalized transform coding analysis, as well as the aforementioned convergence theorems, is used to find the smallest attainable rate at asymptotically large sampling rates in terms of the source spectral density and the operational rate-distortion function of the family of quantizers, which in contrast to previous analyses need not be convex. The result shows that when a transform is used, scalar quantization need not cause the poor performance found by Marco As a corollary, the final result pursues an approach, originally proposed by Berger, to show that the inverse water-pouring formula for the rate-distortion function can be attained at high sampling rates by transform coding with ideal vector quantization to encode the coefficients. Also established in the paper are relations between operational rate-distortion and distortion-rate functions for a continuous parameter source and those for the discrete parameter source that results from sampling.
Energy efficient source localization on a Manhattan grid wireless sensor network

For wireless sensor networks, many decentralized algorithms have been developed to address the problem of locating a source that emits acoustic or electromagnetic waves based on received signal strength. Among the motivations for decentralized algorithms is that they reduce the number of transmissions between sensors, thereby increasing sensor battery life. Whereas most such algorithms are designed for arbitrary sensor placements, such as random placements, this paper focuses on applications that permit a choice of sensor placement. In particular, to make communications costs small, it is proposed to place sensors uniformly along evenly spaced rows and columns, i.e., a Manhattan grid. For such a placement, the Midpoint Algorithm is proposed, which is a simple noniterative decentralized algorithm. The results of this paper show that Manhattan grid networks offer improved accuracy vs. energy tradeoff over randomly distributed networks. Results also show the proposed Midpoint Algorithm offers further energy savings over the recent POCS algorithm.
Process definitions of distortion-rate functions and source coding theorems

The standard definition of the distortion-rate function involves a limit of information-tbeoretic minimizations over distributions of random vectors. Several alternative definitions, each involving a single minimization over random processes, are presented here and verified. These definitions parallel Khinchine's process definition of channel capacity, provide a new interpretation of block and nonblock source coding (with a fidelity criterion) theorems in terms of optimal stochastic codes, and provide a comparison between the optimal performance theoretically attainable (OPTA) using block and nonblock source codes. Coupling the process definitions with recently developed bounding techniques provides a new and simple proof of the block source coding theorem for ergodic sources.
A sampling theorem for Manhattan grids

This paper presents a sampling theorem for Manhattan-grid sampling, which is a sampling scheme in which data is taken along evenly spaced rows and columns. Given the spacing between the rows, the columns, and the samples along the rows and columns, the theorem shows that an image can be perfectly reconstructed from Manhattan-grid sampling if its spectrum is bandlimited to a cross-shaped region whose arm lengths and widths are determined by the aforementioned sample spacings. The nature of such cross-bandlimited images is demonstrated by filtering an image with a cross-bandlimiting filter for several choices of sampling parameters.