nils-herrmann/clean_scirepeval huggingface dataset:
Lossless Reduced Cutset Coding of Markov Random Fields

This paper presents Reduced Cutset Coding, a new Arithmetic Coding (AC) based approach tolossless compression of Markov random fields. In recent work\cite{reye:09a}, the authors presented an efficient AC based approachto encoding acyclic MRFs and described a Local Conditioning (LC)based approach to encoding cyclic MRFs. In the present work, weintroduce an algorithm for AC encoding of a cyclic MRF for which thecomplexity of the LC method of \cite{reye:09a}, or the acyclicMRF algorithm of \cite{reye:09a} combined with the Junction Tree(JT) algorithm, is too large. For encoding an MRF based on acyclic graph $G=(V,E)$, a cutset $U\subset V$ is selected such thatthe subgraph $G_U$ induced by $U$, and each of the components of$G\setminus U$, are tractable to either LC or JT. Then, the cutsetvariables $X_U$ are AC encoded with coding distributions based on areduced MRF defined on $G_U$, and the remaining components$X_{V\setminus U}$ of $X_V$ are optimally AC encoded conditioned on$X_U$. The increase in rate over optimal encoding of $X_V$ is thenormalized divergence between the marginal distribution of $X_U$ and thereduced MRF on $G_U$ used for the AC encoding. We show this follows aPythagorean decomposition and, additionally, that the optimalexponential parameter for the reduced MRF on $G_U$ is the one thatpreserves the moments from the marginal distribution. We also showthat the rate of encoding $X_U$ with this moment-matchingexponential parameter is equal to the entropy of the reduced MRFwith this moment-matching parameter. We illustrate the concepts ofour approach by encoding a typical image from an Ising model with acutset consisting of evenly spaced rows. The performance on this image issimilar to that of JBIG.
Theory of lattice-based fine-coarse vector quantization

The performance of a lattice-based fast vector quantization (VQ) method, which yields rate-distortion performance to that of an optimal VQ, is analyzed. The method, which is a special case of fine-coarse vector quantization (FCVQ), uses the cascade of a fine lattice quantizer and a coarse optimal VQ to encode a given source vector. The second stage is implemented in the form of a lookup table, which needs to be stored at the encoder. The arithmetic complexity of this method is essentially that of lattice VQ. Its distortion can be made arbitrarily close to that of an optimal VQ, provided sufficient storage for the table is available. It is shown that the distortion of lattice-based FCVQ is larger than that of full search quantization by an amount that decreases as the square of the diameter of the lattice cells, and it provides exact formulas for the asymptotic constant of proportionality in terms of the properties of the lattice, coarse codebook, and source density. It is shown that the excess distortion asymptotically equals that of the fine quantizer. Simulation results indicate how small the lattice cells must be in order for the asymptotic formulas to be applicable.
Image reconstruction from a Manhattan grid via piecewise plane fitting and Gaussian Markov random fields

This paper builds upon previous work for image reconstruction problems in which samples are taken on evenly spaced rows and columns, i.e., a Manhattan grid. A new reconstruction method is proposed that uses three steps to interpolate the interior of each block under the model that an image can be decomposed into piecewise planar regions plus noise. First, the K-planes algorithm is developed in order to fit several planes to the observed pixel values on the border. Second, one of theK planes is assigned to each pixel of the block interior, by a process of partitioning the block with polygons, thereby creating a piecewise planar approximation. Third, the interior pixels are interpolated by modeling them as a Gauss Markov random field whose mean is the piecewise planar approximation just obtained. The new method is shown to improve significantly upon previous methods, especially in the preservation of “soft” image edges.
Simplistic Universal Coding.

A conceptually simple coding method may be described as follows. The source sequence is parsed into fixed-length blocks and a list of these blocks is placed in a dictionary. In the lossless case, the dictionary is transmitted and each successive block is encoded by giving its dictionary location. In the lossy case, the smallest collection of blocks such that every member of the dictionary is within distortion /spl delta/ of the collection is determined, this codebook is transmitted, and each successive block is encoded by giving the location of a member of the code within /spl delta/ of it. We show that by optimizing on the block length, this method is universal, that is, for any ergodic process it achieves entropy in the limit in the lossless case and the rate-distortion function R(/spl delta/) in the lossy case.
Asymptotic analysis of optimum uniform scalar quantizers for generalized Gaussian distributions

This paper studies the asymptotic characteristics of optimum uniform scalar quantizers as N, the number of levels, becomes large. It is shown that the length of the support region increases as (ln N)/sup 1//spl alpha//, when applied to a random variable with a generalized Gaussian density of the form p(x)=ae(-b|x|/sup /spl alpha//). Moreover, the mean-squared error is asymptotically well approximated by /spl Delta//sup 2//12, where /spl Delta/ is the step size, and decreases as (ln N)/sup 2//spl alpha///N/sup 2/.<<ETX>>
Fixed-rate universal codes for Markov sources

The existence of a fixed-rate block source code whose performance for each source in a class of Markov sources is uniformly close to the distortion-rate function of that source is investigated. Such a code is called strong universal. It is found that strong universal codes of all rates exist for the class of all binary first-order Markov sources. But for a larger alphabet or for the class of all n th-order Markov sources with n > 2 , there is a critical rate R\ast such that strong universal codes exist for rates greater than or equal to R\ast , but not for rates less than R\ast .
Source-channel coding for digital magnetic recording

The authors explore the possibility of dedicating a disk to store the binary representation of analog data samples and using source-channel codes both to compress the data and to protect it from the increased error rate that results from higher bit density. To determine what gains are possible using this approach, a system was simulated consisting of an IID Gaussian data source, a tree structured vector quantizer for source-channel coding, a channel model similar to that of C.A. French and J.K. Wolf (1988), and two kinds of detector/demodulators. For IID Gaussian data, for which only modest compression is possible, it was found that gains on the order of three to four in data density were achievable with this approach.<<ETX>>
On scanning techniques for lossless image coding with limited context supports

The authors have previously analyzed the performance of context-based lossless image coding techniques in conjunction with the Hilbert and raster scans. The analysis revealed that, under certain reasonable assumptions, the raster scan is indeed better than the Hilbert scan, thereby dispelling the popular notion that using a Hilbert scan would always lead to improved performance. In this paper they apply similar techniques to analyze a random scan as well as a progressive scan (closely based on the commonly used HINT scan). They demonstrate that the progressive scan outperforms the raster scan, but that the expected performance of a random scan is inferior to the other three systematic scans considered so far.
Quantized predictive coding

A new form of predictive quantization, dubbed quantized predictive coding (QPC), is presented. One version uses variable-length coding and another uses fixed-length coding. For autoregressive sources, it is shown both analytically and experimentally that the performance of QPC with (without) entropy-coding is, essentially, the same as that of DPCM (differential pulse code modulation) with uniform quantization with (without) entropy-coding. The principal advantage of QPC is that, unlike DPCM, it is a priori designed for digital implementation. As a result, its digital implementation is simpler than DPCM and suffers no loss in performance due to round-off errors.<<ETX>>
On the Convexity of the MSE Distortion of Symmetric Uniform Scalar Quantization

This paper investigates the convexity of the mean squared-error distortion of symmetric uniform scalar quantization with respect to step size. The principal results include proofs for odd numbers of levels that distortion is not convex for any symmetric density and that it is convex for even numbers of levels for densities, such as Gaussian, Laplacian, and gamma, but is not, in general for two-sided Rayleigh. For the latter case, an interval is derived that includes the optimal step size and over which the distortion is convex. The proofs of convexity use the Euler–Maclaurin formula applied to the second derivative of distortion, with upper bounds on the remainder term. These results imply that a zero of the derivative of the distortion for these densities, which has been previously conjectured optimal, is indeed the optimal step size, because the distortion is convex either globally or locally over a sufficiently wide interval to ensure a global minimizer.
Why vector quantizers outperform scalar quantizers on stationary memoryless sources

This question is frequently asked by newcomers to vector quantization (VQ), who recognize that, in this case, its ability to exploit correlation is of no use. An interesting approach is to a compare k-dimensional VQ with rate R to the k-dimensional product quantizer (PQ) induced by applying a scalar quantizer (SQ) with rate R to k successive source samples. It is then evident that one advantage of VQ is that its cells are more spherical than those of the PQ, which are rectangular. Another is that the points of the VQ are better distributed. Indeed, it is often thought that the PQ distributes points in a "cubic" fashion, whereas the VQ matches its point distribution to the source; e.g. spherical for a Gaussian density. Using asymptotic quantization theory, we show that aside from the rectangularity of the induced PQ's cells, the shortcoming of SQ's is not that they are incapable of inducing a PQ with an optimal point density. Rather, the structure of the PQ links the point density and cell shapes in a way that causes the best SQ to be a compromise between that which induces the best point density and that which induces the best cell shapes. Consequently, the optimum SQ suffers a point density loss and a cell shape loss. For large rates, we find formulas for these and evaluate them in the Gaussian and Laplacian cases. For example, in the Gaussian case, relative to high-dimensional VQ, an SQ has a 1.88 dB "point density" loss, a 1.53 dB "cubic" loss and a 0.94 dB "oblongitis" loss.
Convergence of the projection method for an autoregressive process and a matched DPCM code

The key step in the analysis of differential pulse code modulation (DPCM) is to find the steady-state probability distribution of a random process in terms of which the code distortion can be evaluated. For the case of an autoregressive source and a matched DPCM code, a well-known approximation technique has been used for the evaluation of the steady-state distribution of the prediction error process. However, the validity of this approximation method has not been justified before. A framework in which this approximation technique can be viewed as the projection method for the solution of integral equations is established. Sufficient conditions under which the approximation method can be rigorously justified are obtained.
Structural texture similarity metrics for retrieval applications

Traditional image similarity metrics compare two images on a point-by-point basis. On the other hand, structural similarity metrics (SSIM) attempt to base image similarity on "structural" information. We evaluate the performance of SSIM metrics in the context of texture similarity, and propose new metrics that incorporate the best features of SSIM and eliminate the most serious drawbacks. We show that the proposed new texture similarity metrics outperform SSIM and its variations, as well as PSNR and other traditional metrics. We demonstrate the advantages of the new metrics on a carefully selected set of 39 texture pairs and comparisons with informal subjective test results.
Optimal binary index assignments for a class of equiprobable scalar and vector quantizers

The problem of scalar and vector quantization in conjunction with a noisy binary symmetric channel is considered. The issue is the assignment of the shortest possible distinct binary sequences to quantization levels or vectors so as to minimize the mean-squared error caused by channel errors. By formulating the assignment as a matrix (or vector in the scalar case) and showing that the mean-squared error due to channel errors is determined by the projections of its columns onto the eigenspaces of the multidimensional channel transition matrix, a class of source/quantizer pairs is identified for which the optimal index assignment has a simple and natural form. Among other things, this provides a simpler and more accessible proof of the result of Crimmins et al. (1969) that the natural binary code is an optimal index assignment for the uniform scalar quantizer and uniform source. It also provides a potentially useful approach to further developments in source-channel coding.
Low Rate Scalar Quantization for Gaussian Sources and Absolute Error

This paper considers low resolution scalar quantization for a memoryless Gaussian source with respect to absolute error distortion. It shows that slope of the operational rate-distortion function of scalar quantization is infinite at the point Dmax where the rate becomes zero. Thus, unlike the situation for squared error distortion, or for Laplacian and exponential sources with squared or absolute error distortion, for a Gaussian source and absolute error, scalar quantization at low rates is far from the Shannon rate-distortion function, i.e. far from the performance of the best lossy coding technique
Optimal Linear Assignment of a Binary Group Code to Integer Vectors for Source-Channel Coding

This paper considers the source-channel coding problem of optimally assigning the codewords of an [n, k] binary linear code to the ^-dimensional vectors produced by an IID, uniformly distributed, integer-valued source with alphabet {0,1,..., 2k/n-1} when overall distortion is measured by mean squared error (MSE). It finds explicit formulas for the optimal encoding rule, minimum MSE decoding rule, and resulting distortion. This extends to the vector case the 1974 analysis by Wolf and Redinbo  of the optimal assignment of binary linear codes to integers. As in , , the main tool is abstract Fourier analysis for functions defined on groups. The optimal linear assignment found for vectors can be interpreted as applying the optimal assignment found in  to the integer in {0,1,..., 2k-1} formed by multiplexing the binary representations of the nmiddot integers in the vector being encoded in such a way that more significants bits of each integer come before less significant bits of all integers.
Performance of low rate entropy-constrained scalar quantizers

The operational rate-distortion function of entropy-constrained scalar quantizers in the asymptotic low resolution regime, for memoryless Gaussian sources, is investigated. It is shown that asymptotically, as distortion tends to variance, or equivalently as rate tends to zero, the operational rate-distortion function matches the Shannon rate-distortion function. This implies that scalar quantization is asymptotically optimal, a fact not previously known.
A simplistic, universal lossy source code

A conceptually simple lossy source code, achieving distortion at most D, may be described as follows. A source sequence of length n from a finite alphabet A is parsed into blocks of some length k<n, which are placed in a dictionary. Among all potential codebooks containing source sequences of length k, one selects the smallest one such that every member of the dictionary is within distortion D of some member of the codebook. The codebook is then encoded and used to encode the blocks of the source sequence in the usual manner; i.e., each block is represented by the index of the closest codeword in the codebook. We show that if the block length k is chosen to minimize the encoding rate for the given source sequence, then this coding method is universal in the sense that for any stationary, ergodic source with the alphabet A, the encoding rate approaches the source rate-distortion function, R(D), as n increases.
Bennett's integral for vector quantizers

This paper extends Bennett's (1948) integral from scalar to vector quantizers, giving a simple formula that expresses the rth-power distortion of a many-point vector quantizer in terms of the number of points, point density function, inertial profile, and the distribution of the source. The inertial profile specifies the normalized moment of inertia of quantization cells as a function of location. The extension is formulated in terms of a sequence of quantizers whose point density and inertial profile approach known functions as the number of points increase. Precise conditions are given for the convergence of distortion (suitably normalized) to Bennett's integral. Previous extensions did not include the inertial profile and, consequently, provided only bounds or applied only to quantizers with congruent cells, such as lattice and optimal quantizers. The new version of Bennett's integral provides a framework for the analysis of suboptimal structured vector quantizers. It is shown how the loss in performance of such quantizers, relative to optimal unstructured ones, can be decomposed into point density and cell shape losses. As examples, these losses are computed for product quantizers and used to gain further understanding of the performance of scalar quantizers applied to stationary, memoryless sources and of transform codes applied to Gaussian sources with memory. It is shown that the short-coming of such quantizers is that they must compromise between point density and cell shapes.
Estimating the optimal support and the rate of convergence to the Panter-Dite formula for a Laplacian source

For a Laplacian source, we estimate the support threshold for a minimum mean-squared error (MSE), fixed-rate scalar quantizer. We provide upper and lower bounds to the support threshold as a function of the number of quantization levels N and observe that the optimal support threshold grows as 3//spl radic/2 log (N/2)+O/sub N/ (1). An upper bound is given by the support threshold for a nonuniform scalar quantizer designed around the asymptotically optimal companding function c(x). A lower bound is constructed by examining the decay rate of the smallest lower half step as a function of N. Using these bounds, we derive an upper bound to the convergence rate of N/sup 2/D*/sub N/ to the Panter-Dite constant, where D*/sub N/ is the least MSE of any even, N-level scalar quantizer.
Asymptotic Quantuzation for Noisy Channels

We consider the problem of asymptotic quantization in conjunction with a noisy binary symmetric channel. For a noiseless channel, Bennett's integral is a formula for the distortion of a scalar quantizer given in terms of the source density, the number of quantization points (assumed to be large), and the distribution of quantization points, or point density. In the paper we extend Bennett's integral to the case where the quantizer is used in conjunction with a noisy binary symmetric channel, assuming that channel codewords are assigned randomly. We also derive an expression for the optimum noisy channel point density.
Rotation-invariant local radius index: A compact texture similarity feature for classification

This paper proposes a new rotation-invariant texture similarity feature, called Rotation-Invariant Local Radius Index (RI-LRI). Whereas the original LRI was designed for applications that are sensitive to rotation and aimed to penalize rotation monotonically, the new rotation-invariant LRI is well suited to texture classification. When combined with frequency domain contrast information and the well known Local Binary Patterns (LBP) feature, the proposed metric has comparable texture classification accuracy to state-of-the-art metrics, when tested on the Outex and CUReT databases. Moreover, it has an approximately ten times lower dimensional feature vector and requires substantially less computation than other state-of-the-art texture features, such as those based on LBP.
Subjective and objective texture similarity for image compression

We focus on the evaluation of texture similarity metrics for structurally lossless or nearly structurally lossless image compression. By structurally lossless we mean that the original and compressed images, while they may have visible differences in a side-by-side comparison, they have similar quality so that one cannot tell which is the original. This is particularly important for textured regions, which can have significant point-by-point differences, even though to the human eye they appear to be the same. As in traditional metrics, texture similarity metrics are expected to provide a monotonic relationship between measured and perceived distortion. To evaluate metric performance according to this criterion, we introduce a systematic approach for generating synthetic texture distortions that model variations that occur in natural textures. Based on such distortions, we conducted subjective experiments with a variety of original texture images and different types and degrees of distortions. Our results indicate that recently proposed structural texture similarity metrics provide the best performance.
Codes for data synchronization with timing

This paper investigates the design and analysis of data synchronization codes whose decoders have the property that, in addition to reestablishing correct decoding after encoded data is lost or afflicted with errors, they produce the original time index of each decoded data symbol modulo some integer T. The motivation for such data synchronization with timing is that in many situations where data must be encoded, it is not sufficient for the decoder to present a sequence of correct data symbols. Instead, the user also needs to know the position in the original source sequence of the symbols being presented. With this goal in mind, periodic prefix-synchronized (PPS) codes are introduced and analyzed on the basis of their synchronization delay D, rate R, and timing span T. Introduced are two specific PPS designs called natural marker and cascaded codes. A principal result is that when coding binary data with rate R, the largest possible timing span attainable with PPS codes grows exponentially with delay D, with exponent D(1-R). Thus, a large timing span can be attained with little redundancy and moderate values of delay.