A high-speed Radon transform computer (RTC) has been designed and simulated that operates on the principles of the parallel projection pipeline engine (PPPE) processor suggested by J.L.C. Sanz, et al. (1988). The computer consists of an array of identical processing elements with fast communication links to each of its neighbors and uses forward- and back-projection formulas tests linear interpolation. Simulation and experimental timing tests have been performed on both a systolic array of 64 transputer processors and on arrays of commercial DSP (digital signal processor) chips. A custom VLSI implementation is currently under design which is expected to perform forward and inverse transforms of 512 by 512 images at or near video rates.>

A new architecture for contour tracing of black-and-white images is described. This architecture uses parallelism and pipelining to achieve a significant increase in processing speed over previous tracers. An array of identical processors suitable for VLSI implementation is used. The array approach facilitates expansion to handle arbitrarily large images. The processors trace independently, thereby providing fully parallel, high-speed operation. A postprocessor links the partial contours created by the subdivision of the input image. Simulation results for compression ratio and number of operations are presented.>

A unified discrete cosine transform/inverse discrete cosine transform (DCT/IDCT) architecture suitable for VLSI implementation is presented. A single VLSI NMOS chip design and layout for realizing this architecture is described. Algorithm simulations and experimental performance of integrated test subcircuits indicate that this chip would be capable of real-time processing of 10-MHz video signals. It is considered that circuits of this type could be very useful in real-time image data compression.>

The authors investigate the use of a priori knowledge about a scene to coordinate and control bilevel image segmentation, interpretation, and shape inspection of different objects in the scene. The approach is composed of two main steps. The first step consists of proper segmentation and labeling of individual regions in the image for subsequent ease in interpretation. General as well as scene-specific knowledge is used to improve the segmentation and interpretation processes. Once every region in the image has been identified, the second step proceeds by testing different regions to ensure they meet the design requirements, which are formalized by a set of rules. Morphological techniques are used to extract certain features from the previously processed image for rule verification purposes. As a specific example, results for detecting defects in printed circuit boards are presented.>

An algorithm for object recognition which is based on translation and rotation invariant signatures is presented. The Radon transform is used as a tool for efficient implementation of the algorithm. Good classification results where obtained even with objects having similar shapes.

A common architecture, which is based on the Cooley-Tukey[1] algorithm, is developed for the Fourier, Hadamard, and forward and inverse Cosine transforms. The theory to implement the first three transforms in this architecture is well known. However, the existing algorithms for the inverse Cosine transform (IDCT) would disqualify it from the unified architecture and this led us to develop a new IDCT algorithm which falls within the unified architecture if we allow ourselves the luxury of double length processing. Details of the unified architecture and the new algorithm for the IDCT will be given in this paper.

The concept of fast KL transform coding introduced earlier [7], [8] for first-order Markov processes and certain random fields has been extended to higher order autoregressive (AR) sequences and practical images yielding what we call recursive block coding (RBC) algorithms. In general, the rate-distortion performance for these algorithms is significantly superior to that of the conventional block KL transform algorithm. Moreover, these algorithms permit the use of small size transforms, thereby removing the need for fast transforms and making the hardware implementation of such coders more appealing. This improved performance has been verified for practical image data and results in suppression of the block-boundary effect commonly observed in traditional transform coding techniques. This is illustrated by comparing RBC with cosine transform coding using both one- and twodimensional algorithms. Examples of RBC encoded images at various rates are given.

There are several methods available for representing boundaries in two dimensions. The more widely known ones involve boundary modeling with run-length codes, chain codes and polygons, AR model coefficients, Fourier descriptors (FD's) and B-spline control points (CP's). In this paper, we present results showing the usefulness of CP's in boundary representation. CP's can yield large compression of the boundary data and they exercise local control over boundary shape. Because they can be normalized with respect to scale, translation and rotation, they are valuable in boundary matching applications. Finally, being the series coefficients of spline basis functions, CP's are useful features for boundaries detected in noisy environments.

In this paper we present some new results on Radon transform theory for stationary random fields. In particular we present a new projection theorem which gives the relation between the power spectrum density of one dimensional projections of a stationary random field and its two dimensional power spectrum density. This result yields the optimum mean square reconstruction filter from noisy projections and is useful in other problems such as multidimensional spectral estimation from one dimensional projections, noise analysis in computed tomography, etc. Example are given to demonstrate the usefulness of these results.

In this paper, we consider application of 2-D stochastic models discussed in [1] to develop noncausal FIR filters for restoration of images degraded by additive white noise. The semicausal model of [1] is used to design masks for edge extraction from the noisy images. The results presented here indicate that good restorations and robust edge detection are possible using relatively simple algorithms.

In this paper we consider an application of spectral estimation to adaptive restoration of images degraded by additive white noise. Three adaptive techniques of restoration are compared with a non-adaptive technique. In the non-adaptive technique, the whole image is Wiener filtered by assuming a correlation model for the signal. In the adaptive methods, a) the spectral shape of the signal is kept constant, but the variance is adaptively estimated, b) the power spectrum of each block is adaptively estimated, c) the data is adaptively decorrelated in one dimension and filtered along the other.

A new technique for estimating interframe displacement of small blocks with minimum mean square error is presented. An efficient algorithm for searching the direction of displacement has been described. The results of applying the technique to two sets of images are presented which show 8-10 dB improvement in interframe variance reduction due to motion compensation. The motion compensation is applied for analysis and design of a hybrid coding scheme and the results show a factor of two gain at low bit rates.

A new method of image coding by autoregressive (AR) synthesis is presented. The physics of image formation suggests that an image may be considered as a power spectrum. Using this formulation a Cosine transform of the sampled image is shown to yield a set of autocorrelations. These are used to find an equivalent AR model whose parameters are encoded for transmission. Compared to conventional Cosine transform coding, this method is shown to give superior resolution and is shown to suppress the "block-effects" present in block-by-block transform coding methods. Distinction between this method and linear predictive coding (LPC) used for speech data compression is made. Extensions and examples for two dimensional images are given.

A new family of unitary transforms is introduced. It is shown that the well-known discrete Fourier, cosine, sine, and the Karhunen-Loeve (KL) (for first-order stationary Markov processes) transforms are members of this family. All the member transforms of this family are sinusoidal sequences that are asymptotically equivalent. For finite-length data, these transforms provide different approximations to the KL transform of the said data. From the theory of these transforms some well-known facts about orthogonal transforms are easily explained and some widely misunderstood concepts are brought to light. For example, the near-optimal behavior of the even discrete cosine transform to the KL transform of first-order Markov processes is explained and, at the same time, it is shown that this transform is not always such a good (or near-optimal) approximation to the above-mentioned KL transform. It is also shown that each member of the sinusoidal family is the KL transform of a unique, first-order, non-stationary (in general), Markov process. Asymptotic equivalence and other interesting properties of these transforms can be studied by analyzing the underlying Markov processes.

Speech signal is considered as a two dimensional pseudo-image by segmenting it into blocks of N sample points. Successive segments are placed adjacently thereby forming a sequence of columns or a two dimensional image. Image data compression techniques can now be applied to exploit inter-segment redundancies. We present a hybrid coding scheme for speech. Each segment is first unitarily transformed. This is followed by a DPCM which operates on each of the N transformed samples from one segment to the next. Thus, we perform transform coding in one dimension and DPCM in the other. Results on a 30 second long conversation are presented.

A two-dimensional discrete stochastic model for representing images is developed. This representation has lower mean square error, compared to a standard autoregressive Markov representation. Application of the model to linear filtering of images degraded by white noise leads to scalar recursive filtering equations requiring only 0(N2log2N) computations for N x N images. The filter algorithm is a hybrid algorithm where the image is transformed along one dimension and spatially filtered, recursively, in the other. Examples on a 255 X 255 image are given.

The Karhunen-Loeve (KL) transform is known to have certain properties which make it "optimal" for many "mean-square" signal processing applications [1]-[4]. Recently, it has been shown that a class of digital images may be represented by a set of boundary value stochastic difference equations in two dimensions [5]-[7]. If the boundary conditions of this class of images are fixed, then these equations lead to a fast KL transform algorithm. Here this fast KL transform is used for Wiener filtering of images degraded by white or colored noise. Comparisons with "Generalized Wiener Filtering" [1] and conventional Fourier domain filtering are made. It is shown that the two-dimensional Wiener filter is nonseparable so that two-dimensional generalized Wiener filtering is more elaborate than reported in [1]. It is also shown that certain fast KL filters give better signal-to-noise ratio than the conventional Fourier domain Wiener filter and enable determination of an easily computable performance bound. Recursive filtering equations for implementing the fast KL filter on two-dimensional images including both white and colored noise cases are given. These results show that recursive filtering algorithms for images are faster than the transform-domain algorithms and the one-step interpolator algorithm performs very close to the smoothing filter and can be implemented online by introducing a one-step delay.

A problem of restoration of images blurred by space-invariant point-spread functions (SIPSF) is considered. The SIPSF operator is factorized as a sum of two matrices. The first term is a polynomial of a noncirculant operator P and the second term is a Hankel matrix which affects only the boundary observations. The image covariance matrix is also factorized into two terms; the covariance of the first term is a polynomial in P and the second term depends on the boundary values of the image. Thus, by modifying the image matrix by its boundary terms and the observations by the boundary observations, it is shown that the wieWir filter equation is a function of the operator P and can be solved exactly via the eigenvector expansion of P. The eigenvectors of the noncirculant matrix P are a set of orthronormal harmonic sinusoids called the sine transform, and the eigenvector expansion of the Wiener filter equation can be numerically achieved via a fast-sine-transform algorithm which is related to the fast-Fourier-transform (FFT) algorithm. The factorization therefore provides a fast Wiener restoration scheme for images and other random processes. Examples on 255 X 255 images are given.

The Karhunen-Loeve transform for a class of signals is proven to be a set of periodic sine functions and this Karhunen-Loeve series expansion can be obtained via an FFT algorithm. This fast algorithm obtained could be useful in data compression and other mean-square signal processing applications.

A two-dimensional interpolative model for coding of images is presented. It is shown that this model leads to three different coding algorithms, each algorithm defining a specific transmitter-receiver architecture. Simulation examples on a 255 × 255 image are given. Computational aspects and possible extensions are discussed.

Recursive restoration of two-dimensional noisy images gives dimensionality problems leading to large storage and computation time requirements on a digital computer. This paper shows a two-dimensional second-order Markov process representation can be used for fast recursive restoration of images with small storage requirements. Advantages of this method over existing techniques are illustrated by means of examples.