In an effort to enhance the practical applicability of information theory, to image processing, various findings regarding the entropy rate of two-dimensional random fields are presented. In particular, equivalent representations of the entropy rate of a random field are given, and the entropy rates of various random fields including the Ising model are mentioned.

A Gibbsian probability measure is defined on the set of possible shapes of simple (i.e., not self-intersecting) and closed curves on a discretized lattice. Expressions have been derived for such quantifies as the entropy, average perimeter length, and area in terms of the model parameters, and an iterative procedure has been devised for generating sample objects according to this distribution.

In order to apply the results of information theory to the efficient storage or transmission of images, it is necessary to model the image source distribution and specify an appropriate fidelity criterion. One useful source model results from separating the log intensity random field of a typical image into the sum of two nearly independent random fields with a simpler description. It has also been found that under certain conditions a frequency-weighted squared-error fidelity criterion is satisfactory for evaluating the images. Thus it is important to consider the situation in which the source output is the sum of two independent random entities with known rate-distortion functions with respect to a (perhaps frequency-weighted) squared-error criterion. These rate-distortion functions are used to provide new bounds to the rate-distortion function of the additive source with respect to the same criterion. In one example considered, the new bounds are the tightest known in certain distortion regions. Examples from image coding are given, including a comparison of the performances of various encoding schemes.

This paper considers the characteristics of the human visual system as they are related to sensitivity to encoding errors in still achromatic images. The starting point is a discussion in Section I of the role of a numerical measure of distortion in the determination of optimum encoding. Section II then discusses several ways of determining properties of the human observer and discusses the methodology of psychophysical experiments. Section III then discusses the results of a number of pertinent experiments and presents a model based on these experiments for detecting perturbations of an image. Section IV concludes by discussing how this model can be incorporated into a distortion measure and how this distortion measure might be used. Since the model of the human observer is quite complicated, the mathematical model is not tractable analytically, and results in this last section are as yet fragmentary.

In this paper we describe a code for grey-scale still images which separates the intensity function into two components: a discontinuous one representing intensity variations due to distinct objects and a continuous component due to such effects as texture. Each component is encoded separately and the two decoded components combined at the receiver. The code produces images with notably sharper detail and more pleasing appearance than a whole raster Fourier Transform code operating at the same rate.

It has long been known that for a mean-square error distortion measure the Gaussian distribution requires the largest rate of all sources of a given variance. It has also been stated that a code designed for the Gaussian source and yielding distortiondwhen used with a Gaussian source will yield distortion\leq dwhen used with any independent-letter source of the same variance. In this paper, we extend these results in two directions: a) instead of assuming that the source has a fixed variance, we fix an arbitrary moment; b) instead of mean-square error distortion measures, we consider nearly arbitrary continuous difference distortion measures. For each moment constraint, we show that there is a given distribution that has the largest rate for (nearly) any difference distortion measure and that a code designed for this source yielding distortiondyields distortion\leq dfor any ergodic source satisfying the same moment constraint. Furthermore, digital encoding of the output of this encoder may yield a lower rate when this encoder is used with a source for which it was not designed. We also extend these results to the case of a random process or random field of known correlation function under a difference distortion measure.

Shannon's rate-distortion function provides a potentially useful lower bound against which to compare the rate-versus-distortion performance of practical encoding-transmission systems. However, this bound is not applicable unless one can arrive at a numerically-valued measure of distortion which is in reasonable correspondence with the subjective evaluation of the observer or interpreter. We have attempted to investigate this choice of distortion measure for monochrome still images. This investigation has considered a class of distortion measures for which it is possible to simulate the optimum (in a rate-distortion sense) encoding. Such simulation was performed at a fixed rate for various measures in the class and the results compared subjectively by observers. For several choices of transmission rate and original images, one distortion measure was fairly consistently rated as yielding the most satisfactory appearing encoded images.

Most methods of encoding images require complicated implementation. Thus it is of interest to compare the transmission rates that can be achieved by classes of encoding methods of different complexity. We consider two classes of encoding operations. The first class allows any possible operation on the two-dimensional image source output. The second class allows only certain restricted operations on the image. In acquisition of images by electronic means, the image intensity is in general scanned line by line, resulting in data that appear as a sequence of ordinary time series. In encoding, a simpler implementation results if one accepts the time series from a single scan line and encodes it independently of adjacent scan lines. This limits storage requirements to a single scan line and limits processing to operations on a one-parameter time series instead of operations on a two-dimensional field. This is the second class of encoding operations that we consider. We choose a distortion measure and discuss the rate-distortion function, which represents the minimum rate required by any encoding method in the first (arbitrary complex encoding). We then derive the minimum rate that can be achieved by any encoder from the second class. These rates are compared for a specific example.

The Berkeley array processor is a special-purpose computer designed to perform the operations of correlation, convolution, recursive filtering, matrix multiplication, as well as a variant of the Cooley-Tukey algorithm, and others. This note describes the logical organization and performance of this device.

In certain situations, a single transmission system must be designed to function satisfactorily when used for any source from a classaof sources. In this situation, the rate-distortion functionR_a (d)is the minimum capacity required by any transmission system that can transmit each source fromawith average distortion\leq d. One of the most interesting classes of sources is a class of random processes. Here we consider a weighted-square error-distortion measure and the class of all stationary random processes that satisfy a certain strong mixing property, that have zero mean, known power, and a bounded fourth moment, and that satisfy one of the following alternative specifications on the spectrum: 1) the spectrum is known exactly; 2) the amount of power within the band0 \leq f \leq f_kis known forN -- 1frequenciesf_1 \le f_2 \le \cdots \le f_{N-1}; or 3) the fraction of power outside some frequencyf_lis\leq 1 -- \gamma. For the class of sources determined by each of the above three cases and for an arbitrary error-weighting function we evaluate the rate-distortion function.

The theorem of Kac, Murdock, and Szegö is useful in evaluating the capacity of a time-continuous channel or the rate distortion function of a random process. Here we prove anN-dimensional version of the theorem which is useful for evaluating the rate distortion function of a random field.

In a previous correspondence we derived parametric expressions for the rate distortion function of a Gaussian process under a weighted-square error criterion. Our prior formulation had two deficiencies: one, of a physical orientation, was that transient effects were ignored; the second relates to analytical tractability in applying the results. In this correspondence we correct these shortcomings.

This paper gives a geometric treatment of the source encoding of a Gaussian random variable for minimum mean-square error. The first section is expository, giving a geometric derivation of Shannon's classic result [1] which explicitly shows the steps in source encoding and the properties that a near optimum code must possess. The second section makes use of the geometric insight gained in the first section to bound the performance that can be obtained with a finite block length ofLrandom variables. It is shown that a code can be found whose performance approaches that of the rate distortion function as1/Lin mean-square error and(\ln L)/Lin rate.

Rate distortion function for Gaussian random process with weighted mean square error distortion measure criterion

In radar or radio astronomy we observe a signal whose covariance function depends on some target parameters of interest. We consider here the problem of estimating the values of these parameters from our observation of the signal. One possible procedure is to use the method of maximum likelihood estimation. This method has the advantage that, as the duration of the observation interval becomes long, the mean square error in the maximum likelihood estimate approaches the minimum given by the Cramér-Rao bound. However, the maximum likelihood estimate is usually difficult to compute. We present here a recursive estimation procedure which divides the observation interval up into subintervals of short length; on each subinterval the signal is processed quadratically and the resulting calculation used to improve our estimate. This method has many computational advantages and, under certain conditions, we can show that the error in the resulting sequence of estimates approaches the Cramér-Rao bound. We begin by giving brief consideration to the problem of determining the functional dependence of the covariance function of the received signal on the target parameters. We then present expressions for the terms that appear in the Cramér-Rao inequality. Lastly, we describe the recursive estimation method and state conditions under which it is applicable.

In an earlier paper,^{1}the design of filters by means of an iterative adjustment scheme was described. The filter was assumed to be of a fixed form but to containkvariable parameters. The problem is to find the parameter setting that minimizes the expectation of some weighted value of the error. The adjustment scheme was proposed because it has two advantages over present analytic techniques: 1) the error-weighting function may be any convex function rather than being restricted to the square: 2) the method does not require preliminary measurement of correlation functions or other statistics. The work presented in the previous paper was deficient in two respects: 1) it required that the adjustable parameters take on only quantized values rather than being continuously variable; 2) the rate of convergence presented there was slower than that actually obtainable. Section II of this paper presents the results of work that has eliminated both of these difficulties. Section III presents a scheme for continuously adjusting the filter parameters and proves that, under reasonable conditions, the parameter setting converges to the optimum. The advantage of this continuous-adjustment scheme over the one previously described is that it may be realized with only simple analog equipment.