In many situations of interest the degradation an image has suffered is unknown prior to the restoration process. For this reason the point-spread function of the degrading system has to be estimated directly from the available noisy blurred image. We present a maximum likelihood approach to this image identification problem, and employ the computationally efficient and flexible EM-algorithm to solve the resulting highly nonlinear optimization problem. This approach results in an efficient iterative algorithm, which simultaneously identifies and restores noisy blurred images.

In this paper fast adaptive iterative image restoration algorithms are proposed. These algorithms are based on a class of nonadaptive restoration algorithms ihich exhibit a first or higher order of convergence and some of them consist of an on-line and an off-line -computational part. Since only the linear algorithm can take a computationally feasible adaptive formulation, an iterative algorithm which combines the linear adaptive and the higher order nonadaptive algorithms is proposed. An adaptive window size method is followed in the implementation of the linear adaptive algorithm, rithm, which improves the restoration results. A method to update the computation of the measure of the bcal activity only in the near edge areas is also proposed, thus resulting in great computational savings. Finally, experimental results are presented.

Images in real life are inhomogeneous while the transmission channels are time varying, hence, adaptive schemes are suitable for tracking slow variations on system identification and inverse filtering. In this paper we report theoretical and experimental study of the application of adaptive filtering to two dimensional signals. In particular, we focus on the recursive least square transversal filter applied to image restoration. A multichannel extension of the well known one dimensional recursive least square (RLS) algorithm is presented. Finally simulation results on real world images are given.

This paper presents several aspects of the application of Regularization Theory in image restoration. This is accomplished by extending the applicability of the stabilizing functional approach to 2-D ill-posed inverse problems. Image restoration is formulated as the constrained minimization of a stabilizing functional. The analytical study of this optimization problem results in a variety of regularized solutions. A relationship between these regularized solutions and optimal Wiener estimation is identified. The resulting algorithms are evaluated through experimental results.

This study presents a summary of application of non-linear filters in signal processing, based on robust estimation theory. Non-linear filters are used in many applications including speech and image processing, mainly because of their ability to suppress noise and preserve signal features such as edges. This is a property that linear filters do not have. In the past several years, many types of non-linear filters have been propsed. However, each of these filters shows optimal smoothing efficiency only for a specific type of noise or a specific type of image. In order to further apply these filters in speech and image processing properly, it is important to conduct a review and analysis of all these filters and give an objective evaluation of their performance. Based upon the point estimation theory, three classes of estimations can be distinguished, namely L-estimators, which are based on linear combination of order statistics; R-estimators, which are derived from rank tests; and M-estimators - maximum likelyhood estimators. The first part of the work carried out in this study is classification of various approaches of non-linear filters in these three types of estimators according to the behavior of the filter itself. The second part is the computer implementation of all the filters discussed. Finally the summary of experimental results are presented.

Binary image sometimes shows the random noisy dots and blobs, which are independent of the input data, depending on the illumination condition of the input data and characteristic of an image scanner itself. We propose the binary image enhancement algorithm that smooths out the noise element while preserving thin contours. The proposed algorithm is fast enough to be applicable to nearly real-time services. Computer simulation shows that the proposed method gives better performance than the existing methods in terms of the computational complexity and the effectiveness of the noise reduction with preserving thin contours. It also increases the data compression ratio of the image data based on the G4 facsimile encoding schemes.

It is well known that Fourier-phase is sufficient for image representation and reconstruction within a scale factor, under a variety of conditions. For a finite length sequence, i.e., a sampled signal, a finite number of Fourier coefficients suffices to reconstruct the sequence. Several algorithms exist for this purpose. A close form solution involves solving a large set of linear equations. Another approach is an iterative technique which involves repeated transformation between the frequency and the spatial domains. The application of these techniques to image reconstruction from global (Fourier) phase is, however rather limited in practice due to the computational complexity. In this paper we present a new approach to image representation by means of which, similarly to the biological processing at the level of the cortex, the partial information is defined by localized phase. Also, like processing in vision, dc is first extracted from the signal and signaled separately. Computational results and theoretical analysis indicate that image reconstruction from localized phase-only is more efficient than image reconstruction from global (Fourier) phase. It also lends itself to hardware implementation of fast algorithms using highly parallel architecture.

This paper describes the generalization of the Radix method of finding the median to Weighted Median (WM), Order Statistic (OS) and Weighted Order Statistic (WOS) filters. The method requires that input signal is discretized to 2M possible magnitude levels. Supposing that N is the filter window width the time complexities for different one-dimensional filters are O(M) for Standard Median (SM) filters, 0(NM) for WM filters, O(M) for OS filters and 0(NM) for WOS filters. Comparison of time complexities with other methods is performed.

Fractals and related mathematical models of chaotic phenomena have become active areas in research and applications in many diverse fields. These include weather forecasting, structural analysis, mapping, entertainment, biology, and many others. These fields appear to be a significant part of an emerging interdisciplinary science of complexity and complex systems. The uses of these models in the rapidly developing field of visual computing (i.e., the computational aspects of image sciences: image processing, analysis, and synthesis) are leading to many innovations. This paper will describe a range of activities at TASC and elsewhere illustrating significant new developments, and it describes a trend toward unification in visual computing using these techniques.

This paper addresses some uses of fractals, fuzzy sets and image representation as it pertains to robotic grip planning and autonomous vehicle navigation AVN. The robot/vehicle is assumed to be equipped with multimodal sensors including ultrashort pulse imaging laser rangefinder. With a temporal resolution of 50 femtoseconds a time of flight laser rangefinder can resolve distances within approximately half an inch or 1.25 centimeters. (Fujimoto88)

In several fields of Image Processing (e.g. geography, histology, 2-D electrophoretic gels), the space turns out to be partitioned into zones whose neighborhood relationships are of interest. More generally, a great number of phenomena may be modelled by graphs. Now, a graph being a lattice, it can be approached by Mathematical Morphology. This is the purpose of the present study: after introducing the theoretical framework, it deals with various graphs that can be defined on a given set of objects, depending on the intensity of the desirable relationships (e.g. Delaunay triangulations., Gabriel graphs, Relative neighborhood graphs...). The computational aspect is especially emphasized and new digital algorithms, based on Euclidean zones of influence, are introduced. The main operators. of Mathematical Morphology are then defined and implemented for graphs (erosions and dilations, morphological. filters, distance function, skeletons, labelling, geodesic operators, reconstruction, etc...) in both binary and decimal cases. A series of fast computational algorithms is developed, leading to a complete software package.

In this paper it is shown that many composite morphological systems, such as morphological edge detection, peak/valley extraction, skeletonization, and shape-size distributions obey a weak linear super-position, called threshold-linear superposition: Namely, the output graytone image is the sum of outputs due to input binary images, which result from thresholding the input graytone image at all levels. Then these results are generalized to a vector space formulation, e.g., to any linear combination of simple morphological systems such as erosion, dilation, rank-order filters, and their cascade or max/min combinations. Thus many such systems processing graytone images are reduced to corresponding binary image processing systems, which are easier to analyze and implement.

The holographic transform H is thought of as the sesquilinear mapping which assigns to the elements of the tensor product vector space L2(R) @ L2(R) the matrix coefficient function of the linear Schrodinger representation of the three-dimensional real Heisenberg nil-potent Lie group. - It is the purpose of the present paper to study the quantum mechanical approach to optical holography including optical phase conjugation, electron holography, and computerized tomographic methods in high resolution imaging radar, for instance synthetic-aperture imaging radar like side-looking airborne SAR, and space shuttle SAR. The aspect common to these techniques is the geometric encoding of the two-wave mixing u @ v by the interference pattern H(u,v;.,.) in the holographic plane R @ R performed simultaneously for the amplitude and the phase by the holographic transform H.

A new fractal technique for the analysis and compression of digital images is presented. It is shown that a family of contours extracted from an image can be modelled geometrically as a single entity, based on the theory of recurrent iterated function systems (RIFS). RIFS structures are a rich source for deterministic images, including curves which cannot be generated by standard techniques. Control and stability properties are investigated. We state a control theorem - the recurrent collage theorem - and show how to use it to constrain a recurrent IFS structure so that its attractor is close to a given family of contours. This closeness is not only perceptual; it is measured by means of a min-max distance, for which shape and geometry is important but slight shifts are not. It is therefore the right distance to use for geometric modeling. We show how a very intricate geometric structure, at all scales, is inherently encoded in a few parameters that describe entirely the recurrent structures. Very high data compression ratios can be obtained. The decoding phase is achieved through a simple and fast reconstruction algorithm. Finally, we suggest how higher dimensional structures could be designed to model a wide range of digital textures, thus leading our research towards a complete image compression system that will take its input from some low-level image segmenter.

Nonparametric techniques for estimating fractal dimension are discussed. These techniques are shown to be more robust and efficient when compared with the standard least-squares estimation techniques currently in use. In particular, two alternative nonparametric schemes are presented and their use in image modeling applications is discussed. Theoretical and practical reasons are given to indicate why nonparametric methods lead to improved dimension estimation algorithms. Test results are provided that demonstrate the potential of these methods for use in dimension estimation problems, such as image modeling, where small sample sizes are necessary.

In this paper we investigate the computational performance of a number of morphological skeletons. We also develop the reduced-cardinality geometric-step morphological skeleton which is shown to achieve logarithmic computational complexity, compared to the linear computational complexity of the uniform-step morphological skeleton, when implemented on a large neighborhood pipelined morphological processor. Furthermore, an upper bound on the skeleton cardinality is derived.

This paper presents an interpolation technique emphasizing the preservation of- the original geometric impression. The algorithm is based on the concept of distance function defined between a point in a connected set and its neighboring sets. It is shown that the distance function for any given point in a set to its neighbor can be evaluated by successive morphological operations, typically a dilation followed by a set intersection. an application of this algorithm to a simaple example is discussed.

Morphological algorithms for the analysis of the microstructure and estimation of the physical properties of volcanic geological specimens are described. Various properties of materials, such as bulk viscosity, rigidity, tensile and compressive strengths, etc., depend on the microstructure of the material, which is typically composed of a mosaic of interlocking particles of different phases. The images of the geological microstructure are first separated into their constituent phases. The phase images can then be processed to estimate the percentage contribution of each phase, the total boundary per phase, phase-phase contact boundaries, particle size distributions for each phase and angle of contact between particles. These morphological image measurements can then be used to characterize the physical properties of magma.

The transmission of video information through a narrow band channel requires a significant degree of image compression. In addition to the actual coding procedure, the frame rate is reduced, the spatial sample rate is lowered and the color components are further filtered. Via the review of a practical and flexible image compression configuration, the important technical aspects of videocoding is presented. The complexity of the currently developed system is discussed for the operation over a 64 kbit/sec communication channel. The specific and primary considerations include the following: After a reduction of temporal and spatial resolution, the luminance and color difference signals are divided in pixel blocks of 16 x 16 and 8 x 8, respectively. Then, they are passed on to a motion compensated DPCM coding system with a subsequent discrete cosine transform of the prediction error. The appropriate quantization is performed via several Huffman tables.

Region based image representation is a very promising approach in the class of second generation image coding techniques. In this paper we describe a new approach that is based on a spectral description of the texture signals instead of polynomial approximation which has been proposed by other authors. The fundamental problems in transforming arbitrarily shaped regions due to the window effect are overcome using the algorithm of Selective Deconvolution [FRA87a]. Spectral representation of the texture signals and the used polygonal approximation of the region contours enable a hierarchical organization of the image description. Utilizing the linearity of the generated data structure our scheme combines very high data compression ratios (if the reconstruction of the most important image content is required only) with the option of image reconstruction with increasing resolution up to high quality, if detail information is transmitted.

Non-separable filter banks are studied for general two-dimensional sub-band coding. The developed results are valid for any sub-sampling pattern. A synthesis structure is given which enables cascade-structure design of all two-dimensional paraunitary perfect reconstruction filter banks. The resulting structure is evaluated with regard to free variables and computational complexity. The synthesis structure is also extended to embrace non-paraunitary perfect reconstruction systems. Finally, conditions are derived to test filter banks for linear phase in the polyphase domain.

The hybrid coding technique developed here involves a function of two concepts: progressive interactive image transmission coupled with transform differential coding. There are two notable features in this approach. First, a local average of an mxm (typically 5 x 5) pixel array is formed, quantized and transmitted to the receiver for a preliminary display. This initial pass provides a crude but recognizable image before any further processing or encoding. Upon request from the receiver, the technique then switches to an iterative transform differential encoding scheme. Each iteration progressively provides more image detail at the receiver as requested. Secondly, this hybrid coding technique uses a computationally efficient, real, orthogonal transform, called the Modified Hermite Transform(MHT) [1], to encode the difference image. This MHT is then compared with the Discrete Cosine Transform(DCT) [2] for the same hybrid algorithm. For the standard images tested, we found that the progressive differential coding method per-forms comparably to the well-known direct transform coding methods. The DCT was used as the standard in this traditional approach. This hybrid technique was within 5% of SNR peak-to-peak for the "LENA" image. Comparisons between MHT and DCT as the transform vehicle for the hybrid technique were also conducted. For a transform block size N=8, the DCT requires 50% more multiplications than the MHT. The price paid for this efficiency is modest. For the example tested ("LENA"), the DCT performance gain was 4.2 dB while the MHT was 3.8 dB.

A neural-network clustering algorithm proposed by Kohonen is used to design a codebook for the vector quantization of images. This neural-network clustering algorithm, which is better known as the Kohonen Self-Organizing Feature Maps is a two-dimensional extensively interconnected nodes or unit of processors. The synaptic strengths between the input and the output nodes represent the centroid of the clusters after the network has been adapted to the input vector patterns. Input vectors are presented one at a time, and the weights connecting the input signals to the neurons are adaptively updated such that the point density function of the weights tend to approximate the probability density function of the input vector. Results are presented for a number of coded images using the codebook designed by the Self-Organization Feature Maps. The results are compared with coded images when the codebook is designed by the well known Linde-Buzo-Gray (LBG) algorithm.

Memoryless vector quantizers exploit the high correlation and the spatial redundancy between neighboring pixels, but they totally ignore the spatial redundancy between the blocks. In this paper a new vector quantization scheme called the Address-Vector Quantizer (A-VQ) is proposed. It is based on exploiting the inter-block correlation to encode a group of blocks together by using an address-codebook. The address-codebook consists of a set of address codevectors where each represents a combination of blocks, with each of its element being the address of a LBG-codebook entry representing a vector quantized block. The address-codebook consists of two regions, one is the active (addressable) region, and the other is the inactive (non-addressable) region. During the encoding process the codevectors in the address-codebook are reordered adaptively in order to bring the most probable address codevectors into the active region. When encoding an address combination the active region of the address-codebook is checked, if such an address combination exists its index is transmitted to the receiver, otherwise the address of each block is transmitted individually. The performance (SNR value) of the proposed A-VQ method is the same as that of a memoryless vector quantizer, but the bit rate would be reduced by a factor of two when compared with a memoryless vector quantizer.

This paper describes a system for the transmission of American Sign Language (ASL) over standard telephone lines. Video quality digital images require a transmission bandwidth at least 4000 times wider than that allowable by the standard voice telephone network. This study presents compression, segmentation and coding techniques that reduce the information content of visual images while preserving the meaning of the transmitted message. The resulting processed information can be transmitted at digital rates within the range of the commercially available 9600 baud modems. The simulated real-time animations of the decoded cartoon images used for the experimental data represent ASL and finger spelling with an intelligibility approximating 85%. This result is within the range of the intelligibility provided by speech communication over telephone lines.

A model is presented which describes and codes the regions within a segmented image by means of quad-tree analysis of each region. A simple criterion is used to determine the importance of any node in the tree as a function of its perceptual relevance. This approach is an improvement on the parametric model which is frequently applied, by preserving textures at high compression. Chromaticity quantisation involves supplying only an average in each region. The additional use of dynamic entropy coding further improves the compression without additional distortion. In this way, compression to 0.5 bits/pel is achievable for colour images.

A hybrid coding method based on estimation and detection of local features and classification of image data is presented in this paper. The local edge-orientations as well as the statistical properties are detected and estimated prior to the vector and the scalar quantization of the DCT coefficients. In a specific "feature prediction" process, both the local average grey-level which determines the DC coefficient and the local variance which contributes the ac energy distribution are estimated for each 8x8 image block by using the surrounding pixels of the block. In this way, the nonstationary image data are locally classified into sub-sources with each sub-source containing its own specific characteristics. The generally existent statistical dependences between the neighboring transform blocks are also exploited due to the feature prediction operation. The classification information which contains the local edge orientation and the local variance, determines the ac-energy distribution and consequently the vector forming of the ac coefficients in the vector quantization process. An adaptive scalar quantizer which is controlled by both the classification information and the channel buffer is then followed and clearly, the properties of the human visual system can be incorporated with this supplementary scalar quantization process to improve the coding performance. At a bit-rate round 1 bit/pixel, very good image quality can be observed with high signal-noise-ratio (up to 40dB).

Pattern recognition by a computer assumes that there is a correct answer in classifying the objects to which we can make reference for correctness of recognition. Classification of a set of objects may have absolutely correct answers when the objects are artifacts (e.g. bolts vs nuts) or highly evolved biological species. However, classification of many other objects is arbitrary (e.g. color, clouds), and is frequently a subject of cultural bias. For instance, traffic lights consist of red, yellow and green in the U.S.A.; they are perceived as red, yellow and blue by Japanese. When human bias is involved in classification, a natural solution is to set a panel of human "experts" and concensus of the panel is assumed to be the correct classification. For instance, expert interior decorators can define classification of different colors and hues, and performance of a machine is tested against the reference set by human experts.

This manuscript demonstrates that X-ray CT image can be modeled by a finite normal mixture. The number of image classes in the observed image is detected by the information criteria (AIC or MDL). Parameters of the model are estimated by a modified K-mean algorithm and Bayesian decision criterion is the basis for this image segmentation approach. The use of simulated and real image data demonstrate the very promising results of this proposed technique.

In this paper, an algorithm for segmenting chest radiographs is presented where the left and right lungs are analysed separately. For each lung, a minimum rectangular frame is first determined, which completely encloses the object to be processed. The vertical edges of the minimum rectangular frame are determined by using the horizontal signature. The horizontal edges of the rectangular frame are determined by exploiting both the vertical signatures and the maximum vertical gradient sums. The image enclosed within the rectangular frame is called the subimage and its histogram is calculated. Segmentation into two classes is based upon grey level histogram thresholding, where the pixels less than a prefixed threshold are set to the background and those above to the foreground. The choice of threshold value is based upon a priori knowledge about the chest radiograph. Finally, a noise removal process is applied to smooth the boundaries: the top borders are refined by parabolas and the side borders by straight lines. Simulations are carried out on several chest radiographs and demonstrate the effectiveness of the proposed segmentation algorithm.

We present the results of a study of error free compression of digitized medical x-ray images. This study used high resolution (2048 x 1684), high quality (8 to 11 bits per pixel) images, each approximately 5 Mbytes before compression. Since the medical community is very reluctant to introduce unnecessary noise into their imaging, we require error-free compression or, equivalently, perfect reconstruction. In particular, we investigated the following error free methods: Huffman coding, arithmetic coding, Lempel-Ziv coding, runlength coding, ordinary quadtree coding, and a new quadtree method, multi-window quadtree.

Digital Subtraction Angiography (DSA) is a medical imaging modality used to study the blood vessels and the cardiac chambers. The primary signal processing goal in DSA is the removal of interfering effects from secondary structures in the image in order to enhance clinically significant details. A combination of various image processing techniques including, image subtractions, contrast enhancements and matched filtering, are currently used in DSA systems. In this paper we mainly investigate the applicability of noncausal zero phase parametric two-dimensional (2-D) modeling to the restoration of angiograms.

Subcellular localization of multiple biochemical markers is readily achieved through their characteristic autofluorescence or through use of appropriately labelled antibodies. Recent development of specific probes has permitted elegant studies in calcium and pH in living cells. However, each of these methods measured fluorescence at one wavelength; precise quantitation of multiple fluorophores at individual sites within a cell has not been possible. Using DIFM, we have achieved spectral analysis of discrete subcellular particles 1-2 gm in diameter. The fluorescence emission is broken into narrow bands by an interference monochromator and visualized through the combined use of a silicon intensified target (SIT) camera, a microcomputer based framegrabber with 8 bit resolution, and a color video monitor. Image acquisition, processing, analysis and display are under software control. The digitized image can be corrected for the spectral distortions induced by the wavelength dependent sensitivity of the camera, and the displayed image can be enhanced or presented in pseudocolor to facilitate discrimination of variation in pixel intensity of individual particles. For rapid comparison of the fluorophore composition of granules, a ratio image is produced by dividing the image captured at one wavelength by that captured at another. In the resultant ratio image, a granule which has a fluorophore composition different from the majority is selectively colored. This powerful system has been utilized to obtain spectra of endogenous autofluorescent compounds in discrete cellular organelles of human retinal pigment epithelium, and to measure immunohistochemically labelled components of the extracellular matrix associated with the human optic nerve.

This paper describes a vision guided endoscopic computer system applied in the analysis of static vocal fold images of patients. The system comprises a flexible nasal-endoscope and a PC compatible compatible computer supported by a fully interactive menu-driven software environment which performs the analysis tasks. It is the intention of this paper to present the philosophy of the approach, the construction of the prototype, the results of the investigation and the merits and drawbacks of the prototype at this stage of development. The cost effectiveness of such system being used in private clinics and general hospitals as an expert adviser to the examining doctor will also be discussed.

A relaxation labelling model was implemented to detect 3-d endo- and epicardial surfaces in ECG gated single photon emission computed tomographic perfusion studies of the heart. The model was tested using studies from normal volunteers and from patients with coronary artery disease. LV volumes calculated from the abnormal patient studies correlated well with those from contrast ventriculography, r=0.82 and r=0.89 for end systole and end diastole, respectively. The ejection fractions correlated well with those from radionuclide ventriculograms (r=0.93.) For normal volunteers, left ventricular endocardial volumes calculated using relaxation labelling correlated to those computed from user-traced surfaces with r-0.98. The correlation between epicardial volumes computed using relaxation labelling and hand-traced edges was also 0.98.

Requirements for the transmission and automatic compaction of complex imagery on local area networks is a rapidly developing field, driven by the needs of industry, commerce and medicine who require image based data on existing LAN computing systems. This paper describes a prototype workstation/server architecture and the algorithm used to code, store in archive and present pictorial data is described using representative real images. The data is derived from on-line endoscopic examination of subjects from Ear,Nose and Throat (ENT) clinics.

The concept of an ophthalmic workstation will be presented. A Scanning Laser Ophthalmoscope was developed as a recording device for its superior retinal imaging characteristics. The system architecture provides general electronic image acquisition and analysis. The software includes digital image archiving and development tools for image analysis. Applications will be discussed.

A method for optimizing image-recovery algorithms is presented that is based on how well a specified visual task can be performed using the reconstructed images. Visual task performance is numerically assessed by a Monte Carlo simulation of the complete imaging process including the generation of scenes appropriate to the desired application, subsequent data taking, image recovery, and performance of the stated task based on the final image. This method is used to optimize the Algebraic Reconstruction Technique (ART), which reconstructs images from their projections, by varying the relaxation factor employed in the updating procedure. In some of the imaging situations studied, it is found that the optimization of constrained ART, in which a nonnegativity constraint is invoked, can vastly increase the detectability of objects. There is little improvement attained for unconstrained ART.

This paper proposes an unidirectional ring systolic architecture for implementing the hidden Markov models (HMMs). This array architecture maximizes the strength of VLSI in terms of intensive and pipelined computing and yet circumvents the limitation on communication. Both the scoring and learning phases of an HMM are formulated as a consecutive matrix-vector multiplication problem, which can be executed in a fully pipelined fashion (100% utilization effi-ciency) by using an unidirectional ring systolic architecture. By appropriately scheduling the algorithm, which combines both the operations of the backward evaluation procedure and reestimation algorithm at the same time, we can use this systolic HMM in a most efficient manner. The systolic HMM can also be easily adapted to the left-to-right HMM by using bidirectional semi-global links with significant time saving. This architecture can also incorporate the scaling scheme with little extra effort in the computations of forward and backward evaluation variables to prevent the frequently encountered mathematical undertow problems. We also discuss a possible implementation of this proposed architecture using Inmos transputer (T-800) as the building block.

In this paper, we present two algorithms for vector quantization of images and an architecture to implement these algorithms. In vector quantization (VQ), the image vectors are usually coded with an "universal" codebook, however, for a given image, only a subset of the codewords in the universal codebook may be needed. This means that effectively a smaller label size can be employed at the expense of a small overhead information to indicate to the receiver the codewords used. Simulation results demonstrate the superior coding performance of this technique. VQ using an universal codebook (VQUC) is computationally less demanding but its performance is poor for images outside the training sequence. Image adaptive techniques, where new codebooks are generated, for each input image (VQIAC) can improve the performance but at the cost of increased computational complexity. A technique which combines the advantages of VQUC and VQIAC is presented in this paper. Simulation results demonstrate that the technique gives a coding performance close to that obtained with image adaptive VQ at a substantially reduced computational complextiy. A systolic array architecture to implement the algorithms in real-time is also presented. The regular and iterable structure makes possible the VLSI implementation of the architecture.

This paper describes a method for computing Gaussian and mean curvature maps from range data and a modification to this method aimed at facilitating its implementation as a VLSI circuit. The curvature computations constitute a surface characterization step in range-data processing. A comparison of the performance of the original and modified algorithms on artificial range images is presented. Results of applying the modified algorithm to real range data is also presented.

This paper describes the problem of 2-D state-space filter algorithms and presents some high speed VLSI implementations. The state-space filters are known to be capable of minimizing the finite-word-length effects, but the computations will be increased. By exploiting concurrency in two-dimensional state-space systems, the following speed up architectures are obtained. The local speed-up processors realize the matrix-vector multiplications and decrease the processing time for each pixel. The global speed-up structures in addition use the inherent spatial concurrency and decrease the total processing time in a global sense. These architectures feature a high degree of parallelism and pipelining. They can work on multiple columns or multiple lines of images concurrently. The throughput rate can be up to one column or one line of images per clock time. Another high speed architecture, based on the 2-D block-state update technique, is then presented. It is shown that the throughput rate can be adjusted by varying the block size. Finally, comparisons among the different architectures are given in terms of hardware complexity, throughput rate, latency and efficiency.

This paper reports the architecture, design and test results of a CMOS single chip programmable video linestore system which has 16-bit data words with 1024 bit depth. The delay is fully programmable from 9 to 1033 samples by a 10 bit binary control word. The large 16 bit data word width makes the chip useful for a wide variety of digital video signal processing applications such as DPCM coding, High-Definition TV, and Video scramblers/descramblers etc. For those applications, the conventional large fixed-length shift register or static RAM scheme is not very popular because of its lack of versatility, high power consumption, and required support circuitry. The very high throughput of 50Mbit/sec is made possible by a highly parallel, pipelined dynamic memory architecture implemented in a 2-um N-well CMOS technology. The basic cell of the programmable video linestore chip is an four transistor dynamic RAM element. This cell comprises the majority of the chip's real estate, consumes no static power, and gives good noise immunity to the simply designed sense amplifier. The chip design was done using Bellcore's version of the MULGA virtual grid symbolic layout system. The chip contains approximately 90,000 transistors in an area of 6.5 x 7.5 square mm and the I/Os are TTL compatible. The chip is packaged in a 68-pin leadless ceramic chip carrier package.

The application of high-speed GaAs processors in a parallel system matches the demanding computational requirements of image processing. The architecture of the McDonnell Douglas Astronautics Company (MDAC) vector processor is described along with the algorithms and language translator. Most image and signal processing algorithms can utilize parallel processing and show a significant performance improvement over sequential versions. The parallelization performed by this system is within each vector instruction. Since each vector has many elements, each requiring some computation, useful concurrent arithmetic operations can easily be performed. Balancing the memory bandwidth with the computation rate of the processors is an important design consideration for high efficiency and utilization. The architecture features a bus-based execution unit consisting of four to eight 32-bit GaAs RISC microprocessors running at a 200 MHz clock rate for a peak performance of 1.6 BOPS. The execution unit is connected to a vector memory with three buses capable of transferring two input words and one output word every 10 nsec. The address generators inside the vector memory perform different vector addressing modes and feed the data to the execution unit. The functions discussed in this paper include basic MATRIX OPERATIONS, 2-D SPATIAL CONVOLUTION, HISTOGRAM, and FFT. For each of these algorithms, assembly language programs were run on a behavioral model of the system to obtain performance figures.

This paper presents methods to concurrently exploit AND and OR parallelism in logic programs. The execution sequence of the system is driven by the demand to reduce complexity. The concept of environment copying is applied to achieve modularity when OR parallelism is exploited. As a result, multiple independent structures can be dynamically constructed according to the data dependency to solve various systolic algorithms.

Starloc (Sandia TARget LOcation Computer) is a special-purpose computer designed for target location in an image. It is based on a generalized correlation filter algorithm. Correlation of the input image and a small number (10-20) of specially-designed filter kernels is performed in the Fourier domain. The correlation of the input image with the filter set produces an encoding at each input image pixel location; targets are located at pixels with specific codes. This target signature is not sensitive to target variations such as rotation, range, brightness, and angle of view. Starloc is now under development and when completed will process two 256 pixel by 256 pixel input images per second. Starloc's basic architecture consists of ten pipelined processing stages (eight for Fast Fourier Transform operations and two for pixel by pixel operations) arranged in a ring-like structure. Within each stage are a controller, image memory, address generator, and register file with parallel floating-point processors. Starloc is designed to be fault tolerant by including two hot standby stages that can be switched into the data path when other stages fail and by incorporating a comprehensive set of error checkers. Using currently available floating-point processors, Starloc will run at a sustained rate of 188 MFLOPS (million floating-point operations per second). At this rate, it is performing 36 complex 256 pixel by 256 pixel two-dimensional Fast Fourier Transforms per second.

With the emergence of high speed packet networks as proposed in CCITT Study Group XVIII, metropolitan area networks as defined in IEEE 802.6, and multimedia, high capacity storage such as CDROMs, there is renewed interest among image processing specialists in achieving high bit rate compressions without severe compromises in image quality. Advances in signal processing techniques and their implementation in VLSI have lead to the point where it is now possible to digitally encode full motion video sequences at less than 1.5 Mbps with a spatial and temporal resolution comparable to that commonly viewed on a standard VHS video tape recorder. Work at the David Sarnoff Labs on DVI encoding for CD-ROMs has demonstrated impressive image quality for scenes compressed to an average of l.SMbps. Lippman and his colleagues at MIT Media Lab, also are making significant progress in improving the image quality while maintaining the same 1.5 Mbps rate (important because it is the transfer rate of CD-ROMs). Recently, work at Bellcore analyzed a broad spectrum of video material and determined the feasibility of achieving 1.5Mbps while maintaining near VCR quality.

The influence of eye movements on the perception of spatiotemporal impairments and their relevance for the encoding of video sequences is discussed comprehensively. Two simple experiments show that it is neither permissable to generally blur the video signal in moving areas, nor is it justified to introduce more noise in moving areas. Eye movements slant the spatiotemporal frequency response of the HVS. The influence of eye movements on spatial and temporal masking is demonstrated by a computational model of visual perception. Smooth pursuit eye movements reduce or eliminate temporal masking, but they increase spatial masking effects. A coding system is considered, that utilizes an eye tracker to pick up the point of regard of a single viewer. Such a system has an enormous potential for data compression, but the usefulness of the approach is limited because of the delay introduced by encoding and transmission.

The advent of packet-switched networks has renewed interest in variable rate video coding schemes which can deliver a specified level of image quality. This paper describes one such scheme, using a variable rate Finite State Vector Quantizer (FSVQ). The codec alternates between an intraframe mode, for encoding foreground (moving) areas, and an interframe mode, for background areas. Separate FSVQs are used for the two modes, each with its own set of super-codebooks. Background blocks having low residual energies are conditionally replenished. The codec maintains a fixed SNR by using sub-codebooks having various numbers of codevectors and dimensions, making it an adaptive multi-rate FSVQ. Image quality is controlled by a set of SNR status variables which dynamically select classes of sub-codebooks. Each status variable is a temporally filtered measure of the SNR in a pre-assigned region of the frame that is updated each frame time. The codec may also be configured to include a rate buffer so that image quality can be degraded in a controlled fashion, should the attached network become congested. Distortion during non-congested operation is maintained to within about 1 dB of the desired value over a range of SNRs up to about 45 dB, with rates as high as 1.5 bpp.

A novel method for adaptive vector quantization has been proposed to address the problem of edge degradation in image coding. This technique utilizes variable block size, in our example, 4x4 and 2x2. The basic idea is to partition the image into two parts: non-active and active. For the non-active area, a large block size is used, whereas for the active area a small block size is employed. The quality of the reconstructed images is improved using this algorithm because the bits saved in the non-active areas are allocated to the active areas where the edges may exist. To decrease the complexity of the encoder and decoder, one codebook is used for both active and non-active areas. First, both non-active blocks (large block size) and active blocks (small block size) undergo a two-dimensional cosine transform. The same number of coefficients are retained in both cases; for the large size blocks this could tend to be the lower order coefficients, whereas for the small size blocks, some of the higher order coefficients are retained. A single codebook is then generated. The experimental results show that good quality of reconstructed images by this algorithm is obtained at bit rates as low as 0.8 bits/pixel.

One way to achieve image compression is to use predictive coding schemes. Furthermore, as the signal to process is not stationary, such schemes can even be improved by adopting adaptive strategies. In this paper, it will be proven that it is possible to use a continuous adaptation. The coding protocol can thus be simplified because there is no need to transmit any signal other than the prediction error. The predictor used is a transversal filter with continuously adapted coefficients. To arrive at this, one-dimensional Least Mean Square and adaptive Least Squares are generalized to the special case of digital image processing. The methods described are of great interest and could be applied to many fields other than image coding. A method of adapting the levels of a quantizer to the dynamic range of the two-dimensional signal will also be developed. This is based on a 2D backward estimation of the prediction error variance. The practical implementation of these algorithms will then be analyzed for intraframe and interframe cases. Comparison with a fixed encoder, clearly shows the interest of such techniques. With no excessive computational complexity, we obtain a 40 percent improvement for the distortion by using an LMS -adapted predictor and a three-level adaptive quantizer. The numerous simulations made also give good visual results.

In this paper, we propose the local motion-adaptive interpolation technique which can be used in the codec using MCC-BMA (motion compensated coding-block matching algorithm) and the simple four-region segmentation algorithm. In addition, we propose the new BMA using integral projections to make it easy for real-time processing, and simulate the proposed local motion-adaptive interpolation techniques combined with the conventional three-step search algorithm and the fast BMA using integral projections.

Fast pipelined CMOS integrated circuit implementation of the FIR Median Hybrid filter has been designed. The filter structure combines linear averaging subfilters to a median operation in a way that leads to a very efficient implementation. The filter removes noise while preserving sharp edges in the signals. The circuit can operate up to 80 MHz clock rates and it is capable of filtering real time video signals including future HDTV applications. The window size is adjustable from 3 to 257 samples.

This paper proposes a VLSI architecture for the parallel processing of the generalized 2-D convolution. The processor consists of a shift-buffer pipeline, an array of multipliers and a tree of adders. The image data enter the processor in a raster scan format and are stroed and shifted in the pipeline. The multiplier array takes data from the pipeline and does the mulitiplication in parallel, and then sends the partial products to the adder tree to complete the computation. The simple architecture and control strategy makes the proposed scheme suitable for VLSI implementation.

Novel image processor architectures are presented. The architectures are designed to take advantage of the advanced concepts of Adaptive Sensitivity and Intelligent Scan, and, in particular, of the new sensors described in the companion paper. The processors are capable of manipulating selective visual data sets, which are generated by Intelligent Scan sensors. They are organized in feedback adaptive forms, exhibiting performance superior to conventional, feedforward architectures.

CMOS VLSI imaging sensors are described, which employ a novel approach to image acquisition and processing. Principles of biological visual systems, such as adaptation and selective attention, are applied to achieve a high performance imaging system. The Adaptive Sensitivity mechanism enables the acquisition of extremely wide dynamic range, much wider than that of conventional semiconductor sensors, while preserving image details and while dynamically adapting to the image contents. The Intelligent Scan mechanism filters in only the areas of interest, thus reducing the amount of transmitted visual data in an intelligent, image-dependent, adaptive manner, The sensor are complemented with an image processing system, described in a companion paper.

This paper summarizes the design of a convolution processor card that is very low in cost, easy to use and most importantly, performs a 9x9 convolution in less than a second. Its high-performance is attributed to a VLSI systolic convolution cell which has been designed in our laboratories and to an efficient supporting data path architecture. The new Intel 82258 Advanced DMA Controller is used to perform each pixel transfer to and from the host computer's memory. Due to the DMA's software programmability, pictures of any size can be processed. The circuit is assembled on a 36 column MULTIBUS bus card and is installed on an Intel System 310 running iRMX 286 real-time multitasking operating system.