USC-SIPI REPORT #100 "Image Restoration and Speckle Suppression Using the Noise Updating Repeated Wiener Filter" by Shiaw Shiang Jiang January 1986 In recent years, the adaptive noise smoothing filter using local statistics, which is also referred to as the locally linear minimum mean square error (LLMMSE) filter, has been found to be an effective algorithm for image noise smoothing. The calculation of the local statistics is critical to the quality of the restored image. Various methods for calculating the local statistics are reviewed and their results are compared by computer simulation. Deriving an explicit updated noise variance expression for the LLMMSE filter, we develop a cascaded LLMMSE filter algorithm called the noise updating repeated Wiener (NURW) filter to improve the performance of the adaptive noise smoothing filter. These filters can be applied to images degraded by signal-uncorrelated noise sources without blur. Multiplicative and Poisson noise sources, which are inherently signal-dependent, can be shown to belong to the class of signal-uncorrelated noise. For images degraded by shift-invariant blur and noise, the restoration process is divided into two stages: deblurring and noise smoothing. A least square pseudoinverse (LSPI) filter is used for deblurring to avoid the ill-conditioning of an inverse filter. The effective noise, which is updated after applying the LSPI filter, becomes correlated and is treated as an uncorrelated one in approximation. The NURW filter is then applied to the output of the LSPI filter for noise smoothing to obtain the final restored image. Speckle noise is commonly observed in images with a coherent illumination, such as ultrasonic images, synthetic aperture radar (SAR) images and coherent optical images. The speckle can be approximated by a multiplicative noise, which is an element in the class of signal- uncorrelated noise. Thus, the NURW filter is directly applied on the speckle noise suppression problem. Experimental results show that the NURW filter is an effective algorithm for speckle noise suppression. Price: Domestic $15.00; International $22.50 USC-SIPI REPORT #101 "Image Data Base" by Allan G. Weber February 1986 The USC-SIPI image data base is maintained primarily to support research in image processing, image analysis, and machine vision. The data base is divided into categories based on the basic character of the pictures. Images in each category are of various sizes such as 256x256 pixels, 512x512 pixels, or 1024x1024 pixels. All images are 8 bits/pixel for black and white images, 24 bits/pixel for color images. The following categories are currently available: Textures, Aerial images (color), Aerial images (black and white), Miscellaneous (color), Miscellaneous (black and white), Motion picture sequences, and Military equipment. Price: No Charge USC-SIPI REPORT #102 "Semi-Markov Random Field Models for Nonstationary Signal Processing" by John Goutsias August 1986 With the increasing availability and decreasing cost of digital computers, it is desirable to develop sophisticated and accurate parametric models for the mathematical description of different measured signals. Often, a major characteristic of such signals is their nonstationary nature, a characteristic that is usually ignored in signal modeling. In this dissertation we focus our attention on modeling the nonstationary signal behavior, thus resulting in an accurate signal description. We develop a new class of nonstationary signals, the class of semi-Markov random fields. The likelihood function, which completely describes the statistical behavior of this class of random fields, is derived. Necessary and sufficient conditions are examined, for the statistical equivalence between a Markov random field and a semi-Markov random field. We argue that the semi-Markov random fields are appropriate for the statistical description of the structural representation of a two-dimensional lattice. We introduce the class of doubly stochastic Gaussian random fields and we examine their statistical properties. We develop a Bayesian procedure for the solution of the problem of detecting and estimating an observed, noisy and filtered version of a doubly stochastic Gaussian random field. We derive a separation principle indicating that the detection and estimation problem, for an observed doubly stochastic Gaussian random field, can be solved by first solving a detection problem, second solving an estimation problem, and, finally, combining their solutions in a natural fashion. A new likelihood detector, the integer most-likely search detector, is designed for the efficient solution of the signal detection problem. We develop an adaptive parameter estimation/signal detection algorithm for the solution of the previous problem. We argue that this algorithm is advantageous, since it allows the real time estimation of the unknown underlying parameters. We illustrate our models, and the performance of the proposed algorithms, by considering some synthetic and real data examples. The problems of signal segmentation (for the one-dimensional and the two-dimensional cases) and signal restoration (for the one-dimensional case) are illustrated. Finally, texture analysis and synthesis is considered based on the proposed model. Price: Domestic $27.00; International $40.50 USC-SIPI REPORT #103 "A Source Representation Space Approach to Digital Array Processing" by Kevin M. Buckley July 1986 This dissertation describes the development and application of a model for sources, as observed by a sensor array processing structure, which accounts for variation in source propagation and observation parameters. The source observation is a KL-dimensional vector which contains L delayed samples of the output of the elements of a generally configured array of K sensors. The model, termed a Source Representation Space, is an efficient 2nd order characterization of source observations. It is the subspace of the KL -dimensional observation vector space which, for the selected dimension and range of source parameter variation, contains the maximum observed source energy of any equal dimension subspace. It is defined as the span of the significant eigenvectors of a properly constructed Hermitian source sample covariance matrix. The model is generally formulated to represent sources over ranges of propagation and observation parameters. The principle application addressed in this dissertation is the representation of sources over ranges of location and frequency. The source representation space is used as a source model for spatial/spectral filtering. For this application, where beamformer response is naturally considered in terms of 2nd order characteristics, this representation is employed very effectively. The new representation is used in the control of portions of the response of a broadband linearly-constrained minimum variance beamformer. A class of eigenvector constraints are derived which, compared to existing response point and derivative constraints, is illustrated to provide better response control. Also, a deterministic beamformer design procedure is formulated based on the developed eigenvector constraints. With the procedure, beamformers for broadband and arbitrarily configured arrays can be effectively designed. To date, a general design procedure for broadband and arbitrarily configured array beamformers has not been presented. For application to broadband Source Location Estimation (SLE), several new broadband spatial spectra estimation algorithms are developed. For power spatial spectra estimation, deterministic and minimum variance beamformers are employed which are designed using eigenvector linear constraints. For eigenvector based high resolution methods, the source representation space is used: 1) to provide valuable insight for algorithm development; 2) as a model of sources for direct broadband data processing algorithms; and 3) to derive transformations which provide source focusing. Price: Domestic $22.00; International $33.00 USC-SIPI REPORT #104 "Signal Processing VIA Higher-Order Statistics" by Georgios B. Giannakis July 1986 Although spectral theory is a well established approach to any signal processing tasks, its applicability depends heavily upon the assumptions of linearity and Gaussianity of the signal, and/or the minimum phase assumption of the underlying ARMA model. Because 2nd-order statistics are "phase-blind," we introduce higher-order statistics that convey the complementary phase information required for realization and model reduction of non-minimum phase (NMP) systems. Identification of NMP stochastic systems, and signal phase reconstruction. The higher-order statistics that we use to replace or complement the auto-correlation information, are directly related to the ARMA parameters, and easy to handle mathematically. With the introduction of cumulants and their multidimensional Fourier transforms known as polyspectra, new insight is gained about the stationarity, whiteness and non-Gaussianity conditions required for correct phase realization of finite-dimensional parametric models. For high resolution polyspectrum estimation, a parametric approach is developed as a byproduct of our NMP identification algorithm. We also derive a maximum entropy polyspectral estimator which turns out to have an AR structure. The state-space and input-output methods that we propose for realization and model reduction of NMP models exploit higher-order output statistics to estimate the AR coefficients of the minimum phased part and higher-order statistics of the innovations to realize the all-pass part. By employing algorithms, we guarantee good numerical performance and a quantitative way of measuring the error of our approximate realization. Because successful identification depends on correct model order we also develop two methods for ARMA order determination using higher- order statistics. Statistical analysis is performed and confidence intervals are provided to display the AR and MA orders with high probability, and suggest the most reliable statistic for efficient parameter estimation. Our methods are robust with respect to additive, non-skewed, white output noise. Stability and consistency of our identification techniques are assured under mild conditions. Simulations verify our theoretical developments, and indicate that higher-order statistics will emerge as a powerful tool in various signal processing applications. Price: Domestic $23.00; International $34.50 USC-SIPI REPORT #105 "A Method for Enforcing Integrability in Shape from Shading Algorithms" by Robert Frankot and Rama Chellappa June 1987 Several recently developed techniques for reconstructing surface shape from shading information estimate surface slopes without ensuring that they are integrable. This paper presents an approach for enforcing integrability, a particular implementation of the approach, an example of its application is extending an existing shape from shading algorithm and experimental results showing the improvement that results from enforcing integrability. A possibly nonintegrable estimate of surface slopes is represented by a finite set of basis functions, and integrability is enforced by calculating the orthogonal projection onto a vector subspace spanning the set of integrable slopes. This projection maps closed convex sets onto closed convex sets and, hence, is attractive as a constraint. The special case of Fourier basis functions is formulated. This provides an intuitive frequency domain interpretation of shape from shading, a computationally efficient implementation using the FFT, and a convenient method for introducing low resolution information into the shape from shading solution. Reconstruction of surface height by integrating surface slope estimates is obtained as a byproduct of the integrability constraint. Other possible applications of this method to computer vision problems such as shape from texture and surface reconstruction from synthetic aperture radar imagery are discussed. Price: Domestic $2.50; International $3.75 USC-SIPI REPORT #106 "On ESD's In System Identification" by Ananthram Swami and Jerry M. Mendel May 1987 In this note, we review several important properties of Elliptically Symmetric Distributions (ESD's). ESD's are generalizations of the Gaussian distribution; they can be represented as scale mixtures of the Gaussian, are closed under linear transformations and have conditional expectations that are linear on the conditioning variable. Several results in estimation theory, such as parameter estimation, Kalman filtering theory etc. hold for ESD's. In several cases, the null distributions of certain invariant test statistics remain unchanged from the Gaussian case. ESD's are also Bussgang processes. Finally, we show that the zeros of an ARMA system cannot be resolved in two cases: a) when the system is excited by an unobservable ESD process and b) when the output process is Bussgang. Price: Domestic $2.50; International $3.75 USC-SIPI REPORT #107 "Optical Computing and Interconnections" by B. Keith Jenkins October 1985 This report describes research in digital optical computing and optical interconnections. It assesses the current state-of-the-art, discusses future prospects and worthwhile directions, and identifies areas that need further research in order to make digital optical computing feasible. Digital optical computing systems are compared to electronic systems, acousto-optics and integrated optics. Optical fixed and reconfigurable interconnections are considered for use in optical computers and electronic computers. Price: Domestic $3.50; International $5.25 USC-SIPI REPORT #108 "Robust Algorithms for Two-Dimensional Spectrum Estimation" by Richard R. Hansen, Jr., Rama Chellappa, and Govind Sharma June 1987 In this paper we investigate robust estimation of two-dimensional (2-D) power spectra of signals which are adequately represented by Gaussian random field models but for which we have imperfect observations. Two situations of particular interest occur when the contaminating noise is additive and when the contaminating noise appears in the innovations. In these cases the observed data is not Gaussian and conventional procedures are no longer efficient. To estimate the parameters of the signal model from the contaminated data we describe two new procedures which were originally proposed for estimation of scale and location from independent data and adapted to one-dimensional autoregressive parameter estimation by previous researchers. The first algorithm is a robustification of least squares and equivalent to an iterated weighted least squares problem where the weights are data dependent. Known as the generalized maximum-likelihood (GM) estimator its analysis is accomplished by the use of a so-called "influence function" or directional derivative of the estimator in the direction of the contamination. We compute expressions for relative efficiency of the estimator using the influence function and specify criteria for selection of the estimator's robustifying functions. The second algorithm is an iterative procedure known as a filter-cleaner. This procedure is shown to be approximately equivalent to an optimal minimization problem. Experiments using the robust procedures with synthetic data are reported and the results compared with a conventional method of model-based spectrum estimation, i.e., consistent least squares parameter estimation. Finally, we conclude with a summary of the utility and improved performance of the robust procedures over the conventional method and a discussion of the shortcomings of these heuristically derived robust methods. Price: Domestic $6.50; International $9.75 USC-SIPI REPORT #109 "A Unified Approach for Filtering and Edge Selection in Noisy Images" by Yi-Tong Zhou, Anand Rangarajan, and Rama Chellappa January 1988 We consider the problem of enhancement and edge detection on noisy, real images. A unified framework for smoothing and edge detection based on an autoagressive (AR) random field model is presented. An edge is detected, if the first and second directional derivatives and a local estimate of the variance at each point satisfy certain criteria. When noise is present we would like to estimate the directional derivatives from a restored version of the noisy image. We propose a Reduced Update Kalman Filter (RUKF) to perform the restoration. Then we can perform edge detection recursively using a small (4 x 4) window and still be fairly robust in the presence of noise. Since the edge detector operates on the restored image, it follows the RUKF by a fixed lag. A min-max replacement technique is introduced in between the RUKF and the edge detector to improve edge strength. The results compare favorably with those of other edge detectors. Price: Domestic $2.50; International $3.75 USC-SIPI REPORT #110 "Direct Analytical Methods for Solving Poisson Equations in Computer Vision Problems" by Tal Simchony and Rama Chellappa July 1987 The need to solve one or more Poisson equation of the general form: Du = f arises in several computer vision problems such as enforcing integrability in shape from shading, the lightness and optical flow problems equations are iterative. In this paper we first discuss direct analytical methods for solving these equations on a rectangular domain. We then suggest some embedding techniques that may be useful when boundary conditions (obtained from stereo, self shadowing and occluding boundary) are defined on arbitrary contours. The suggested algorithms are computationally efficient due to the use of fast orthogonal transforms. Application to lightness resulting from the direct analytical methods for the computation of optical flow are also discussed. The algorithm resulting from the direct analytical methods for the computation of optical flow is new. A proof for the existence and convergence of the flow estimates is also given. Price: Domestic $2.50; International $3.75 USC-SIPI REPORT #111 "Hierarchical Texture Segmentation Using Multiple Resolution Operators" by Allan G. Weber July 1987 Texture information can be used as a basis for segmenting an image into regions. Image texture is basically a local area phenomenon that is sensitive to the size of the area. What appears as a non-textured area at one resolution level can appear as a region with distinctive texture at a different resolution. The performance of texture segmentation schemes is often highly dependent on the size of the local area operator used to generate the classification features. The size of the operators has a major impact on the performance near the boundaries between texture regions. Features based on large operators perform better overall but are highly affected by the mixing of class statistics when the operator overlaps more than texture, such as near the texture boundaries. Features based on small operators show poorer overall performance but are more likely to maintain an acceptable performance level in the boundary areas. The trade-off is between statistical accuracy of the classification versus the final accuracy of the texture region boundaries. The problem being studied here is how to combine information from texture classifiers operating at different resolutions into a segmentation process that gives acceptable performance in all areas of an image. In this study, the nature of the mixing problem is examined and a solution is proposed based on using multiple resolution features in a hierarchical decision process. A key component of the solution is an analysis of the image data prior to performing any classification. From this analysis, we determine the expected location in the feature space of the mixture points. Three different methods of isolating the mixture points in the feature space are proposed and tested. During the initial classification phase, image points that are within the mixture areas are left unclassified. Spatial information is incorporated into the segmentation process by the use of a local area cohesion operation. The final segmentation is based on a hierarchical decision process that uses the classification choice at both resolutions and the spatial cohesion data. Several decision processes are tested that use the information in different ways. Price: Domestic $16.00; International $24.00 USC-SIPI REPORT #112 "Image Restoration Using a Neural Network" by Yi-Tong Zhou, B. Keith Jenkins, and Rama Chellappa A new approach for restoration of grey level images degraded by a known shift invariant blur function and additive noise is presented using a neural computational network. A neural network model is employed to represent a possibly nonstationary image whose gray level function is the simple sum of the neuron state variables. The restoration procedure consists of two stages: estimation of the parameters of the neural network model and reconstruction of images. During the first stage, the parameters are estimated by comparing the energy function of the neural network with a constrained error function. The nonlinear restoration method is then carried out iteratively in the second stage by using a dynamic algorithm to minimize the energy function of an appropriate neural network. Owing to the model's fault-tolerant nature and computation capability, a high quality image is obtained using this approach. A practical algorithm with reduced computational complexity is also presented. Several computer simulation examples involving synthetic and real images are given to illustrate the usefulness of our method. The choice of the boundary values to reduce the ringing effect is discussed and comparisons with other restoration methods such as the SVD pseudoinverse filter, minimum mean square error (MMSE) filter and modified MMSE filter using Gaussian Markov random field model are given. Price: Domestic $3.00; International $4.50 USC-SIPI REPORT #113 "New Algorithms for Reconstruction of a 3-D Depth Map from One or More Images" by Min Shao, Tal Simchony, and Rama Chellappa New algorithms are developed to recover the depth and orientation maps of a surface from its image intensities. They combine the advantages of stereo vision and shape-from-shading (SFS) methods. These algorithms generate dense surface depth and orientation maps accurately and unambiguously. Previous SFS algorithms can not be directly extended to combine stereo images because the recovery of surface depth and that of orientation are separated in these formulations. A new SFS algorithm is proposed to couple the generation of the depth and orientation maps. The new formulation also ensures that the reconstructed surface depth and its orientation are consistent. The SFS algorithm for a single image is next extended to utilize stereo images. The correspondence over stereo images is established simultaneously with the generation of surface depth and orientation. An alternative approach is also suggested for combining stereo and SFS techniques. This approach can be used to combine needle maps which are directly available from other sources such as photometric stereo. Finally, we discuss the use of embedding techniques to combine sparse depth measurements. Price: Domestic $2.00; International $3.75 USC-SIPI REPORT #114 "Textured Image Segmentation Using Feature Smoothing and Probabilistic Relaxation Techniques" by John Y.-H. Hsiao December 1987 The segmentation of textured imagery into homogeneous regions is an important and difficult task in scene analysis. A satisfactory segmentation result should possess not only good region interiors but also accurate boundaries. In response to these requirements, the main objective of this research is twofold. First, to improve textured image segmentation results; especially along the borders of regions. Second, to take into account the spatial relationship among pixels to improve the segmentation of region interiors. An improved method to extract textured energy features in the feature extraction stage is proposed. The proposed method is based upon an adaptive noise smoothing concept which takes the nonstationary nature of the problem into account. Texture energy features are first estimated using a window of small size to reduce the possibility of mixing statistics along region borders. The estimated texture energy feature values are then smoothed by a quadrant method which reduces the variability of the estimates while retaining the region border accuracy. For a supervised segmentation system, the estimated feature values of each pixel are used by the Bayes classifier to make an initial probabilistic labeling. The spatial constraints are then enforced through the use of a probabilistic relaxation algorithm. Two probabilistic relaxation algorithms have been investigated and their results are compared by computer simulation. For an unsupervised segmentation system, the estimated feature values of a set of subsampled pixels are used in a K-means clustering algorithm to estimate the class statistics. The estimated class statistics are then used by the Bayes classifier to make an initial probabilistic labeling. One of the selected relaxation algorithms is then applied to enforce the spatial constraints. Limiting the probability labels by probability threshold is proposed to make the relaxation iteration more efficient. The trade-off between efficiency and degradation of performance is studied. Finally, an overview of the proposed textured image segmentation system is provided and comparisons of overall performance are made. Price: Domestic $14.00; International $21.00 USC-SIPI REPORT #115 "The SCOOP Pyramid: An Object-Oriented Prototype of a Pyramid Architecture for Computer Vision" by Herbert S. Barad December 1987 This dissertation describes a working software prototype of a pyramid architecture, known as the SCOOP pyramid, to investigate its use and effectiveness in computer vision. The pyramid architecture is shown by simulation to be an effective architecture for a wide range of computer vision tasks from low level pixel-oriented operations to segmentation to high level symbolic operations. Results also show that processing overhead for a task can take more time than the task itself. This processing overhead includes the loading of convolution kernels and morphological look-up tables. An object-oriented methodology for modeling the individual processors and ports is used. The method for modeling and constructing the prototype is efficient and flexible. This encourages the fine-tuning of the architecture design. The prototype is used as a testbed for simulations of computer vision tasks and the results of these simulations are presented. The simulations include isolated tasks: convolution, edge detection, and segmentation. Also, a complete scenario to find bridges in LANDSAT aerial data is studied. This scenario is controlled by a simple knowledge base. The SCOOP architecture provides an environment to model architecture of arbitrary topology, complexity, and composition. Price: Domestic $17.00; International $25.50 USC-SIPI REPORT #116 "Computational Vision Algorithms for Synthetic Aperture Radar Imagery" by Robert T. Frankot October 1987 Two classes of models, computational vision models and stochastic models, are examined for synthetic aperture radar (SAR) images of natural terrain. Algorithms are developed for surface topography estimation, image registration, and texture synthesis. Shape from shading techniques are used for extracting topographic information. Previous numerical solutions to the shape from shading problem estimated the surface derivatives without ensuring that they are integrable, a serious drawback. The performance of a previously developed shape from shading technique is substantially improved using a fast least-squares algorithm to enforce integrability. The resulting algorithm is then applied to SAR by representing the terrain surface height relative to the "slant plane" (a plane parallel to the line-of-sight) and accounting for the radiometric properties of SAR imagery. For noisy imagery, such as SAR, low frequency surface information is difficult to recover from a single image. A fast Fourier transform implementation of the integrability projection provides an efficient method for combining low frequency surface information with the shading information. This technique may be suitable for combining the SAR imagery and the low resolution altimetry provided by Magellan to construct high resolution topographic maps of Venus. The resulting algorithm is applied to SIR-B SAR imagery and the surface reconstructions are compared with stereoscopically derived digital terrain models. The use of auxiliary low frequency information is tested, allowing estimation of reflectance map parameters and providing coarse surface structure to complement the surface details obtained from shading information. This simulates the Magellan scenario. An automatic registration algorithm is used for matching image intensity predictions with the observed images. This registration algorithm matches two SAR images made from nearly orthogonal flight paths and matches a SAR image with an aerial photograph without detailed a priori knowledge of the terrain, two very difficult problems for images of hilly terrain. Stochastic models for SAR image intensity based on nonlinear transformations of Gaussian random fields are introduced. Methods for selecting transformations to normality and model order are presented and tested on SAR imagery and synthesis of textures appearing in SAR imagery is demonstrated. Price: Domestic $17.00; International $25.50 USC-SIPI REPORT #117 "Estimating the Kinematics and Structure of a Moving Object from a Sequence of Images" by Theodore Broida The problem considered here involves the use of a sequence of monocular images of a three-dimensional (3-D) moving object to estimate both its structure and kinematics. The object is assumed to be rigid, and its motion is assumed to be "smooth." A set of object match points is assumed to be available, consisting of fixed features on the object, the image plane coordinates of which have been extracted from successive images in the sequence. The measured data are the noisy image plane coordinates of this set of object match points, taken from each image in the sequence. Structure is defined as the 3-D positions of these object feature points, relative to each other. Rotational motion occurs about the origin of an object-centered coordinate system, while translational motion is that of the origin of this coordinate system. A set of models is developed that decouples the object and its motion from the imaging process. This allows both translational and rotational motion to be modeled to any desired order (constant velocity, constant acceleration, constant jerk, etc.), independent of the nonlinearity of the central projection imaging process. Standard rectilinear models are used for translational motion. Quaternions are used to propagate the rotational motion via closed-form expressions for constant angular velocity and constant precession rate, and a well-behaved ordinary differential equation for higher order motion. The models allow the use of arbitrarily many image frames and feature points: additional data, as available, can be incorporated to improve the estimation accuracy, especially in high noise environments. The time intervals between images frames need not be constant, and there is no requirement that all feature points be visible in all frames, so the events of feature occlusion or disappearance can be accommodate. Object kinematics can be interpolated or extrapolated to any desired time, based on available data. Extrapolated kinematics have potential applications in any situation in which a vision system is used to aid a machine's interaction with its environment. For example, by predicting an object's trajectory to some future time, a video sequence could be used to direct a manipulator arm to meet and grasp the object at that time. Extrapolation of the image coordinates of object feature points to future images could also be used to aid in feature extraction, segmentation, and other image processing operations. Approximate Cramer-Rao lower bounds are derived, which can be used to predict estimation accuracy for any given situation. Both batch and recursive formulations are presented for estimation of the model parameters. Results using the batch approach are given for both simulated and real imagery, when translational motion has constant velocity and rotational motion has constant angular velocity, with unknown object structure. Recursive results are presented for the case of pure translation with known structure, based on simulated imagery. Image plane noise levels from .01% to 15% of the object image size are used. Price: Domestic $25.50; International $38.25 USC-SIPI REPORT #117-2 "Lattice Algorithms for Recursive Instrumental Variable Methods" by Ananthram Swami and Jerry M. Mendel December 1987 We develop a recursive lattice algorithm for the estimation of the parameters of an AR process, using a 1-D slice of the k-th order cumulant. The cumulant matrix can be viewed as the cross-correlation of the observed process, y(n), and an associated process, z(n), and, y(n) and the other by z(n), the lattices being coupled through order- and time-update equation-conventional orthogonality conditions. Extensions to ARMA processes are discussed. The joint-process estimation problem is also treated. Some statistical analysis is carried out and convergence results are given when y(n) and z(n) can be modeled as stationary processes. The only assumption that we make about z(n) the associated process, is that the cross-correlation of y(n) and z(n) suffices for the estimation of the AR parameters, i.e., we assume that z(n) is an instrumental process Consequently, our algorithm, in fact, provides an adaptive lattice version of the multichannel recursive instrumental variable method. Price: Domestic $6.00; International $9.00 USC-SIPI REPORT #118 "3-D Motion Estimation Using a Sequence of Noisy Stereo Images Part I: Models and Motion Estimation" by Gem-Sun Young and Rama Chellappa We discuss a kinematic model based approach for the estimation of 3-D motion parameters from a sequence of noisy stereo images. The approach is based on representing the constant acceleration translational motion, and constant angular velocity or constant precession rotational motion in the form of a bilinear state space model using standard rectilinear state for translational and quaternions for rotation. Closed form solutions of the state transition equations are obtained to propagate to quaternions in both constant angular velocity and constant precession models. The measurements are noisy perturbations of 3-D feature points represented in an inertial coordinate system. It is assumed that the 3-D feature points are extracted from the stereo images and matched over the frames. Owing to the nonlinearity in the state model, nonlinear filters are designed for the estimation of motion parameters. A performance bound for the motion parameters is calculated. Simulation results are included. In a companion report [19], uniqueness of motion parameter estimates is established. Price: Domestic $3.50; International $5.25 USC-SIPI REPORT #119 "3-D Estimation Using a Sequence of Noisy Stereo Images Part II: Uniqueness Results" by Gem-Sun Young and Rama Chellappa We discuss the uniqueness of motion parameter estimates in the kinematic model based approach presented in a companion report [3]. The kinematic model is designed for the estimation of 3-D motion parameters from a sequence of noisy stereo images. A constructive proof of uniqueness is established by separating the rotational parameters from the translational parameters. We show that with uniform sampling, three noncollinear feature points in two consecutive binicular image pairs and one feature point each in three binocular image pairs contain all the spatial and temporal information of the translational motion with constant acceleration and rotational motion with constant angular velocity. Some related issues such as sampling of image sequences and ambiguity in motion are also analyzed. Price: Domestic $3.00; International $4.50 USC-SIPI REPORT #121 "Time and Lag Recursive Computation of Cumulants from a State Space Models" by Ananthram Swami and Jerry M. Mendel July 1988 Time and lag recursive algorithms for the computation of the cumulants of the state vector and the output process of a multiple-input multiple- output (MIMO) time-varying state-space model (SSM) are derived by using a Kronecker product representation for the cumulants of vector processes. The noise processes are not assumed to be stationary. Elegant expressions are obtained when the SSM is time-invariant and in observable form. For MIMO linear processes, closed-form expressions relating the output cumulants to the SSM parameters and to the impulse response matrices are established. Symmetry relations for the cumulants of vector processes are also discussed. Computational aspects are discussed in detail; and some system identification issues are addressed. Price: Domestic $5.00; International $7.50 USC-SIPI REPORT #122 "Heuristically Constrained Estimation for Intelligent Signal Processing" by Robert F. Popoli and Jerry M. Mendel February 1988 The solution of many estimation problems can be greatly enhanced by the incorporation of inexact knowledge or vague human reasoning. For such estimation problems, two distinct forms of problem knowledge can be identified: statistical (objective) knowledge and heuristic (subjective) knowledge. This chapter discusses a systematic way of expressing and integrating these two forms of knowledge into the estimation processes. This work can be interpreted as a fuzzification of standard constrained optimization. Fuzzy set theory is used to form a fuzzy constraint which represents the domain-specific knowledge of human experts. This work may also be interpreted as a systematization of the use of subjective priors by Bayesians. Although our work is of general applicability, we demonstrate the use of heuristically constrained estimation to the particular problem of seismic deconvolution. These results show that the incorporation of heuristic knowledge (albeit vague) yields better results than if such knowledge is ignored. Price: Domestic $2.50; International $3.75 USC-SIPI REPORT #123 "Maximum Likelihood Method for 2-D Non-Causal Model Based Spectrum Estimation" by Richard Hansen, Jr. and Rama Chellappa March 1988 This report presents noncausal autoagressive (NCAR) plus additive noise model based spectrum estimation for planar array data typical of signals encountered in radar, sonar, seismology, radio astronomy, and other similar array processing applications. Previous research has shown that the maximum likelihood )ML) procedure provides consistent and efficient spectrum parameter estimates for NCAR models with noncausal neighbor sets. Here we show that these properties carry over to the approximate maximum likelihood estimates of parameters for Gaussian NCAR plus noise models. Since the likelihood function is nonlinear in the model parameters and is further complicated by the unknown variance parameter of the additive noise, computationally intensive gradient search algorithms are required for computing the estimates. By assuming a toroidal lattice the complexity of the approximate ML equation is significantly reduced without destroying the theoretical asymptotic properties of the estimates and with little impact on the observed accuracy of the estimated spectra. initial conditions for starting the toroidal ML computation are proposed. Experimental results which evaluate the signal plus noise approach and compare its performance to signal only methods are presented for Gaussian and simulated planar array data. Spectrum parameter estimate statistics are given and estimated spectra for signals with close spatial frequencies are shown. Price: Domestic $8.50; International $12.75 USC-SIPI REPORT #124 "Stereo Matching Using a Neural Network" by Yi-Tong Zhou and Rama Chellappa March 1988 A method for matching stereo images using a neural network is presented. Usually, the measurement primitives used for stereo matching are the intensity values, edges and linear features. Conventional methods based on such primitives suffer from amplitude bias, edge sparsity and noise distortion. We first fit a polynomial to find a smooth continuous intensity function in a window and estimate the first order intensity derivatives. Combination of smoothing and differentiation results in a window operator which functions very similar to the human eye in detecting the intensity changes. To give some insights into the resulting window operator, a theoretical analysis of the variances of the estimated derivatives is given. Since natural stereo images are usually digitized for the implementation on a digital computer, we consider the effect of spatial quantization on the estimation of the derivatives from natural images. A neural network is then employed to implement the matching procedure under the epipolar, photometric and smoothness constraints based on the estimated first order derivatives. Owing to the dense intensity derivatives a dense array of disparities is generated with only a few iterations. This method does not require surface interpolation. Experimental results using random dot stereograms and natural images pairs are presented to demonstrate the efficacy of our method. Price: Domestic $4.00; International $6.00 USC-SIPI REPORT #125 "Recursive Method for Computation of Cumulants" by Weizheng Wang and Jerry M. Mendel April 1988 Recursive formulas for diagonal-slice cumulant computations of a state-variable model are developed. The computation formulas can be used for both stationary and non-stationary systems. The connection between stationary and non-stationary cumulant computations is also considered; it depends upon the assumption of an asymptotic stable model. This report is divided into two parts. In Part I, a matrix formulation for third-order diagonal-slice cumulant computation is discussed. An ARMA model is given as an example which shows computation aspects of the methods. Results are also verified by analysis of AR and MA models. In Part II, the Kronecker product is used to derive third- and fourth-order cumulant recursive computation formulas. Vector representations for third- and fourth-order cumulants are given and elegant recursive cumulant computation formulas are obtained. Examples and simulations are given in both parts. Price: Domestic $5.50; International $8.25 USC-SIPI REPORT #126 "Pyramid Implementation of Optimal Step Conjugate Search Algorithms for Some Computer Vision Problems" by Tal Simchony, Rama Chellappa, H. Jinchi, and Zeev Lichtenstein Optimization of a cost function arises in several computer vision problems. The cost functions in these problems are usually derived from discretization of functionals obtained from regularization principles or stochastic estimation techniques using Markov random field models. In this paper we present a parallel implementation on a pyramid of the line search conjugate gradient algorithm for minimizing the cost functions mentioned above. By viewing the global cost function as a Gibbs energy function, we efficiently compute the gradients, inner products and the optimal step size using the pyramid. The global Gibbs energy of a given configuration is broken into its basic energy terms associated with different cliques. We let each low level processor sum the energies associated with its cliques. The local energy terms are added by the intermediate levels of the pyramid to the top, where the step size is determined by an efficient univariate search. Such implementation allows us to calculate the global energy in 0(log n) operations, where n is the number of grid points in each direction. Implementation of this algorithm to shape from shading results in a multiresolution conjugate gradient algorithm. Robustness and efficiency of the algorithm are also demonstrated on edge detection using graduated non convexity algorithm, and estimation of gray level images degraded by multiplicative noise. Price: Domestic $3.50; International $5.25 USC-SIPI REPORT #127 "A Spatio-Temporal Approach to Motion Understanding" by Min Shao and Rama Chellappa July 1988 Algorithms for the interpretation of optical flow are difficult to design due to the nonlinearity of constraint equations and the high dimensionality of the parameter space. Here we show that when two velocity fields from the same moving object are given, the rotational component of the motion parameters can be eliminated from the difference velocity field. Thus the translational component, or the focus of expansion (FOE) can be robustly found by solving a set of linear equations. This in turn facilitates closed-form solutions for the rotational component and environment depth. This approach can be applied to multi-object motion segmentation using the Hough transform. If a dense sequence of images is available, then the structure for the environment and the 3-D motion parameters can be recovered directly at every image point from the given velocity filed. In this approach both spatial and temporal information are used in a uniform way. The structure-from- motion (SFM) problem is then reduced to solving a quadratic equation. If the optical flow field is not available, the SFM problem based directly on the first-order derivatives of the image brightness is underdetermined. However, by exploiting the image brightness constancy constraint in both spatial and temporal domains we show that, given the first and second order spatio-temporal derivatives of image brightness, the SFM problem becomes overdetermined. Price: Domestic $2.50; International $3.75 USC-SIPI REPORT #128 "Graduated Nonconvexity Algorithm for Image Estimation Using Compound Gauss Markov Field Models" by Tal Simchony, Rama Chellappa, and Zeev Lichtenstein This paper is concerned with developing a deterministic algorithm for obtaining the global maximum a posteriori probability (MAP) estimate from an image corrupted by additive Gaussian noise. The MAP algorithm requires the probability density function of the original undegraded image and the probability density function of the corrupting noise. By assuming that the original image is represented by a compound model consisting of a 2-D noncausal Gaussian Markov random field (GMRK) to represent the homogeneous regions and a line process model to represent the discontinuities, the MAP algorithm is written in terms of the compound GMRF model parameters. The solution to the MAP equations is then realized by a deterministic relaxation algorithm. The deterministic algorithm which is an extension of the graduated non convexity (GNC) algorithm, is able to find the global MAP estimate. As a by product, the line process configuration determined by the MAP estimate produces an accurate edge map without any additional cost. Unlike the simulated annealing method, the deterministic algorithm converges in a small number. Due to the modeling assumption the restoration algorithm depends on the GMRF model parameters. We obtain estimates of the compound GMRF model parameters from the original image using a new expectation maximization (EM) estimation technique. The EM algorithm enables estimation of the GMRF model parameters without being affected by the edges present in the image. Experimental results are given to illustrate the usefulness of our method. Price: Domestic $2.50; International $3.75 USC-SIPI REPORT #129 "On the Hardware Requirement for 2-D Image Convolution in Electro-Optical Systems" by M. Eshaghian, D. K. Panda, and V. K. Prasanna Kumar August 1988 In this paper, we study the hardware requirement for 2-D image convolution on an electro-optical model. We identify the basic components of an Optical model of parallel computation using optical interconnects and their relationship with well known VLSI grid model from a computational perspective. We show a lower bound of W(nw) on the volume requirement of any electro-optical chip for 2-D image convolution using a w x w window and a n x n image. This bound also applies to the area requirement of a VLSI chip. Designs available in the literature for computing the 2-D image convolution are compared with respect to their hardware requirement. Price: Domestic $2.50; International $3.75 USC-SIPI REPORT #130 "A Generalized EM Algorithm for 3-D Bayesian Reconstruction from Poisson Data Using Gibbs Priors" by Tom Hebert and Richard Leahy June 1988 For independent Poisson observations having a complete/incomplete data representation, a generalized expectation-maximization (GEM) algorithm is developed for Bayesian reconstruction based upon locally correlated Markov random field priors in the form of Gibbs functions. For the M-step of the algorithm, a form of coordinate gradient ascent with an initial step-size resembling that of the EM likelihood algorithm is employed. Implementation closely follows that of the EM likelihood algorithm. In addition, as the prior tends towards a uniform distribution, this algorithm reduces to the EM likelihood algorithm. Three different Gibbs function priors are examined. The generalized EM Bayesian approach is applied to estimating the 3-D image parameters in the Poisson model of single photon emission computer tomography (SPECT). Price: Domestic $2.50; International $3.75 USC-SIPI REPORT #131 "Maximally Sparse Optimization for Array Beamforming and Other Applications" by Brian Jeffs and Richard Leahy September 1988 In this paper we introduce algorithms for finding optimally sparse solutions subject to linear and quadratic constraints. The problem of finding the maximally sparse solution, i.e. the vector with fewest non-zero terms, is shown to be closely related to l p optimization for 0 < p < 1. For linearly constrained problems, it is non linear simplex algorithm is presented for efficiently locating a local minimum on the connected graph of basic feasible solutions. By modifying the algorithm to include a stochastic search, it is shown that a global minimum of the problem may be found. For quadratic constraints, the maximally sparse solution is found by means of a convex transformation. The utility of these algorithms is demonstrated in the design of arbitrarily shaped, narrowband beamforming arrays. Using the maximally sparse criteria we are able to perform optimal array thinning and element placement for this problem for an arbitrary set of linear response constraints. The algorithms also have many other applications in signal processing, one such application considered in this paper is the recovery of sparse reflectivity sequences in seismic deconvolution. Price: Domestic $4.00; International $6.00 USC-SIPI REPORT #132 "Stochastic and Deterministic Networks for Texture Segmentation" by B. S. Manjunath, Tal Simchony, and Rama Chellappa September 1988 This paper describes several texture segmentation algorithms based on deterministic and stochastic relaxation principles. We are mainly interested in developing algorithms which can be implemented on highly parallel networks. the segmentation process is posed as an optimization problem and two different optimality criteria are considered. The first criterion involves maximizing the posterior distribution of the intensity array given the label array (Maximum a posteriori (MAP) estimate). The posterior distribution of the texture labels is derived by modeling the textures as Gauss Markov Random Fields (GMRF) and characterizing the distribution of different texture labels by an Ising model. Fast approximate solutions for MAP are obtained using deterministic relaxation techniques implemented on a standard Hopfield type neural network. For comparison purposes simulated annealing is used to obtain the global optimum of the MAP estimate. A stochastic algorithm is then proposed which introduces learning into the iterations of the Hopfield network. This iterated hill climbing algorithm combines the fast convergence of deterministic relaxation with the sustained exploration of the stochastic algorithms. However unlike simulated annealing, this is guaranteed to find only a local minimum. The second optimally criterion requires minimizing the expected percentage of missclassification per pixel by maximizing the posterior marginal distribution. We use the Maximum Posterior Marginal (MPM) algorithm to obtain the corresponding solution. All these methods implemented on parallel networks can be easily extended for hierarchical segmentation and we present results of the various schemes in classifying real textured images. Price: Domestic $2.50; International $3.75 USC-SIPI REPORT #133 "A Digital Optical Cellular Image Processor (DOCIP): Theory, Architecture and Implementation" by Kung-Shiuh Huang November 1988 Is there a simple unified complete theory of parallel binary digital image processing? Can this theory suggest new parallel algorithms and architectures for image processing and numerical computation? Can these algorithms and architectures be implemented by optical computing techniques? This thesis attempts to answer these questions. A binary image algebra (BIA), built from five elementary images and three fundamental operations, serves as a unified theory of parallel binary image processing and a spatial logic of parallel optical computing. It also leads to a formal parallel language approach to the design of parallel binary image processing and parallel binary arithmetic algorithms. Digital optical cellular image processors (DOCIPs), based on cellular automata and cellular logic architectures, implement parallel algorithms of BIA efficiently. An algebraic structure provides a link between the algorithms of BIA and architectures of DOCIP. Optical computing suggests an efficient and high-speed implementation of the DOCIP architectures because of its inherent parallelism and 3-D global interconnection capabilities. The use of optical interconnections permits a two-dimensional cellular hypercube (DOCIP-hypercube) topology to be implemented without paying a large penalty in chip area (the cellular hypercube interconnections are space-invariant which implies a low hologram complexity); it also enables images to be input to and output from the machine in parallel. A computer-controlled system has been constructed to fabricate multi-facet interconnection holograms for 3-D optical circuits. A prototype DOCIP system has been implemented to demonstrate the concept of the DOCIP architecture. Experimental results are presented. Price: Domestic $24.50; International $36.75 USC-SIPI REPORT #134 "Parametric Spectrum Estimation for Contaminated Random Fields" by Richard R. Hansen, Jr. December 1988 In this dissertation we propose and investigate new methods of parametric spectrum estimation for two-dimensional random fields which are adequately represented with spatial interaction models. The maximum likelihood (ML) estimator is considered optimal for strictly Gaussian fields and, because of its invariance property, yields the ML estimate of the spectrum. However, many observed fields do not conform to strict distributional assumptions because in inherent contamination (noise) or other isolated imperfections (outliers) resulting from the data measurement and recording processes. When the observed signal is Gaussian we show that a noncausal autoagressive signal plus noise model that accounts for possible contamination yields better spectrum estimates than conventional signal only models. The theoretical properties of the ML parameter estimates for noncausal autoagressive plus noise model are stated and proved, and the numerical properties are experimentally evaluated and compared with the conventional signal only model for direction of arrival estimation in planar array signal processing. When the Gaussian assumption is suspect we propose robust techniques for estimating the parameters of spatial interaction model spectra. First, we extend the time series generalized M-estimator to two-dimensional nonsymmetric half-plane and Gaussian-Markov random field models, and then we analyze this robust estimator's performance in series of parameter and spectrum estimation experiments. The generalized M-estimator will not perform well for noncausal autoagressive models. Additionally, the covariance and conditional probability structure of noncausal models preclude a solution to the optimal robust problem. Thus, we work directly from the observed data and propose empirical estimators for the noncausal autoagressive and Gaussian-Markov random field models. The robust empirical estimators performance in the contaminated situation is shown through a series of experiments to be better than the performance of optimal methods based on a strict Gaussian assumption. Price: Domestic $23.50; International $35.25 USC-SIPI REPORT #135 "Kronecker and Array Algebra for Parallel Image Processing" by Daniel G. Antzoulatos December 1988 This dissertation presents a mathematical framework for implementing highly concurrent tasks on three-dimensional multilayered massively parallel synchronous computing structures. The framework is an extension and unification of ideas and concepts found in signal processing, parallel processing and large scale computing. It takes advantage of the duality between Kronecker and array algebras. The former is matrix algebra augmented with Kronecker products and shuffle permutations. Array algebra--a derivative of sensor analysis--is extended for more flexibility. Useful identities and theorems for both algebras are presented/derived. Multilayered architectures are given new classifications. Closely examined are those architectures that consist of cascaded pairs of a global interplane communication structure and a regular array of processing elements--isoplanar homosyndetic architectures. Of particular interest are global interconnections of the shuffle permutation class. The primary example of such an architecture is an envisioned 2-D Omega processor--a 2-D processing extension of the Omega network. Canonical forms of 2-D shuffle/processing stages are derived. The computational tasks addressed are those which can be cast in the context of matrix algebra. Mappings of linear transformations are demonstrated including 2-D Hadamard transformations, matrix rotations and transposition. Potential optical implementation technologies are discussed and the applicability of Kronecker algebra in the implementation of shuffles using strategically located thin lenses is demonstrated. Price: Domestic $14.00; International $21.00 USC-SIPI REPORT #136 "Parallel Deterministic and Stochastic Optimization Algorithms for Computer Vision" by Tal Simchony December 1988 We investigate two types of models for problems in computer vision; mechanical and stochastic models. Using the calculus of variations on the former and maximum a posteriori (MAP) techniques on the latter, we reframe the problems in an optimization framework. Gibbs distributions are an excellent class of stochastic models. The equivalence between the stochastic and deterministic formulations is then straightforward as we equate the Hamiltonian in the Gibbs distribution formulations is the cost function in the deterministic setup. This equivalence allows us to show that the weak membrane (a mechanical model for interpolation) can be subsumed under a general class of compound Gauss-Markov random field (GMRF) models. Graduated Non-Convexity algorithms, (GNC) originating in the deterministic formulation are then extended to MAP image estimation in the presence of additive noise. Robust vision systems need to incorporate multiple sources of information. We suggest using Gibbs distributions in formulating a unified framework and then minimize the corresponding non-quadratic Hamiltonian using robust line search conjugate gradient (CG) algorithms. The special structure of the Hamiltonian is then used to derive a pyramid implementation for the algorithm. The variational approach transforms the optimization problem that arises in many early vision problems such as shape from shading (SFS), optical flow, the lightness problem, reconstruction of surface depth from orientation etc. into a set of linear or nonlinear Poisson equations. Direct methods and embedding techniques are used in deriving efficient Poisson solvers. We use this formulation to derive a new algorithm for SFS from stereo images. In the Bayesian framework, stochastic models allow us to experiment with different optimally criteria. We use the MAP and the minimum probability of error per pixel (MPM) criteria in the texture segmentation problem. For the sake of comparison, the deterministic Iterated Conditional Modes (ICM) algorithm is also implemented. This allows us to make the observations that these kinds of labeling problems are highly non-convex (this remark is supported by recent work on boundary detection with random neighborhoods and by the use of hill- climbing learning algorithms to texture segmentation). We also show that estimates that interpolate between MAP and MPM can be obtained. Price: Domestic $16.50; International $24.75 USC-SIPI REPORT #137 "Intelligent Interpretation of Aerial Images" by V. Venkateswar and R. Chellappa March 1989 The task of interpreting aerial images can be divided into two sub-tasks - low-level and high-level. The purpose of the low-level module is to abstract some primitives (e.g.: lines, regions) from the raw image data to be input to the high-level module. The high-level module then attempts to synthesize these input primitives into objects using various sources of knowledge. However, the output from the lower level module is frequently ambiguous, fragmented and insufficient. Consequently, there is a search space involved as in many other artificial intelligence problems. Purely algorithmic procedures, that make ad hoc choices when faced with alternatives, are bound to have limited practical use. Some kind of intelligent search mechanism needs to be employed. At the Signal and Image Processing Institute, USC, we are implementing a system for intelligent interpretation of aerial images. The lower-level module is a new line detector. An ATMS-type multiple context truth maintenance system (MCTMS) oversees search in multiple contexts. This search scheme is well suited to aerial image interpretation. Alternative paths can be simultaneously explored and competing contexts can be directly compared. The process of object synthesis is carried out in a hierarchical manner. An object is composed of faces, faces are formed by edge rings, edge rings are formed by edges, which are defined by their end vertices. Each element in this hierarchy is representation unit - a frame. Relations between these elements are also represented as frames. The frame paradigm permits us to perform expectation driven processing and also facilitates object oriented programming. The domain of interpretation is currently restricted to buildings that are compositions of rectangular parallelepipeds. Currently our system is only partially complete. The system is capable of composing edge rings and can detect closed edge rings. Price: Domestic $5.00; International $7.50 USC-SIPI REPORT #138 "Maximally Sparse Constrained Optimization for Signal Processing Applications" by Brian Dean Jeffs January 1989 A new approach for vector space optimization is presented which enables solution of a number of signal processing problems, otherwise solvable only in a suboptimal sense. The method seeks a maximally sparse solution vector to a system of linear or quadratic inequality constraints. An optimal solution (typically not unique) contains the fewest possible nonzero terms consistent with the constraints. The relationship between lp quasinorm minimization and sparse optimization is discussed, and it is proved that for some p, 0 < p < 1, the constrained lp minimum will be maximally sparse. The related l 1|q cost function is shown to be a superior objective functional for deterministic sparse optimization, and to yield maximum a-posterior estimates when random sources are distributed as generalized p-Gaussian. Three new algorithms based on the l 1|q cost are presented. The l 1|q simplex search algorithm achieves strong local optimality by searching the set of vertices of the convex polytope formed by linear constraints. The "basic" solutions corresponding to these vertices are proved to include the optimum. The stochastic search algorithm finds globally optimum results using techniques of simulated annealing to direct the simplex search. The convex transformation gradient search finds strong local optima of the quadratically constrained problem by transformation to a space where gradient search techniques are more successful. Three applications are presented as examples of problems best solved using the maximally sparse criterion. Neuromagnetic image reconstruction produces 3-D maps of brain neural currents by reconstruction from externally measured induced magnetic fields. Sparse optimization is shown to be superior to other reconstruction methods which obscure virtually all current dipole position detail. Seismic deconvolution of sparse reflectivity sequences is demonstrated using all three of the algorithms, and design of thinned beamforming arrays using the stochastic search algorithm is shown to yield great improvement over existing methods. The new algorithms provide the only available method for thinning of arbitrarily shaped arrays in an optimal sense. Price: Domestic $17.50; International $26.25 USC-SIPI REPORT #139 "Two-color Fourier Analysis of Iterative Algorithms for Elliptic Problems with Red/Black Ordering" by C.-C. Jay Kuo and Tony F. Chan April 1989 The red/black ordering scheme is often used to increase the parallelism of iteractive methods for solving elliptic PDEs. However, the convergence rates are also affected, often adversely. This paper provides a unified approach, called the two-color Fourier analysis, to study the convergence rates of iterative algorithms for elliptic problems with the red/black ordering. This Fourier tool is used to analyze different types of iterative algorithms, including the successive over-relaxation (SOR) method, symmetric successive over-relaxation (SSOR) method, preconditioned iterative methods with SSOR, ILU and MILU preconditioners and multigrid (MG) methods. By comparing the convergence rates of algorithms with the natural and red/black orderings, we show that although the red/black ordering does not affect the rate of convergence in the context of SOR and MG methods, it slows down the convergence significantly in the context of SSOR and preconditioned iterative methods. Price: Domestic $4.50; International $6.75 USC-SIPI REPORT #140 "System Identification Using Cumulants" by Ananthram Swami October 1988 Since second-order statistics are inadequate in describing non-Gaussian mixed phase linear process, certain higher-order statistics, namely cumulants, and their Fourier transforms, polyspectra, are used to estimate the parameters of linear processes. In the presence of additive (colored) Gaussian noise, cumulants are powerful analysis tools, because they effectively transform the data to a high signal-to-noise ratio domain. Several algorithms to estimate the MA parameters of an ARMA model are developed; in particular, one of these algorithms permits the simultaneous estimation of the AR parameters and the impulse response coefficients. These algorithms are extended to multi-channel, multi- dimensional and non-causal models. It is shown that consistent AT estimate may be obtained from the 'normal' equations based on a finite set of 1-D slices of the cumulant; based on this, an AR order determination algorithm is proposed. A Kronecker-product based approach is used to obtain a compact representation of the cumulants of vector processes; based on this, time-and lag recursive, as well as closed-form, expressions for the cumulants of the state and output processes of a time-varying, non-stationary, multiple output state-space model, are developed. A cumulant-based algorithm for the estimation of the matrices of the state-space model is developed. By introducing an unconventional orthogonality condition, a set of four linear prediction problems, leading to the cumulant-based 'normal' equations is proposed; time-and order-recursive estimates of the multichannel AR parameters are obtained via a double lattice being excited by the observed process, and the other lattice being excited by an instrumental process. Some convergence results are presented, and the joint- process estimation problem is also addressed. Cumulants of complex processes are defined, and a cumulant based approach to the harmonic retrieval and direction of arrival problems is proposed; techniques for detecting and quantifying quadratic and cubic phase coupling are developed. A viable definition for the cumulants of non-random signals is proposed, and the deterministic realization problem is addressed. Price: Domestic $12.50; International $18.75 USC-SIPI REPORT #141 "Algorithms/Applications/Architectures of Artificial Neural Nets" by Jenq-Neng Hwang December 1988 In the research field of artificial neural nets (ANNs), important contributions have come from cognitive science, neurobiology, physics, computer science, control, analog VLSI, and optics. This dissertation is intended to broaden the present scope so as to achieve an in-depth understanding of neural computing from the perspectives of parallel algorithm design, digital VLSI array architectures, digital signal processing, and numerical analysis. Therefore, in a broader sense, the aim of this dissertation has been to accomplish truly cross-disciplinary research. A variety of neural nets are considered, including single layer feedback neural nets (e.g., Hopfield neural nets, Rumelhart memory/learning modules, and Boltzmann machines), multilayer feed-forward nets (e.g., multilayer Perceptrons), and hidden Markov models (HMMs). Algorithmic studies based on algebraic projection (AP) analysis are presented to deal with two critical and important issues in back propagation (BP) learning: the selection of the optimal number of hidden units and the optimal learning rate. Potential applications of ANNs to two promising areas, computer vision and robotic processing, are discussed. A systematic algorithm mapping methodology is proposed for mapping neural algorithms in VLSI array architectures. This methodology derives array architectures for the algorithms via a two-stage design, i.e., dependence graph (DG) design and array processor design. Programmable ring systolic ANNs (linear and cascaded) are developed, which can exploit the strength of VLSI and offer intensive and pipelined computing. Both the retrieving and learning phases are integrated in the design. The proposed architectures are more versatile than other existing ANNs; therefore, they can accommodate the most widely used neural nets. A unifying viewpoint is proposed for multilayer Perceptrons and HMMs, and the ring systolic array architectures can further be extended to the application domain of implementing both the scoring and learning phases of HMMs. Finally, some mathematical aspects for ANNs worthy of further pursuit are also presented, which include expressibility and discrimination capabilities, generalization capability, convergence in the retrieving and learning phases, and merging of multilayer Perceptrons and HMMs. Price: Domestic $18.00; International $27.00 USC-SIPI REPORT #142 "Mapping/Matching Algorithms to Reconfigurable Mesh Arrays" by Shiann-Ning Jean December 1988 Due to the fast progress of VLSI technology, algorithm-oriented array architectures appear to be effective, feasible, and economic. In particular, a large class of regular computations, especially those for signal and image processing can be efficiently implemented on arrays of processors. these trends have necessitated a systematic methodology of mapping computations onto processor arrays. To facilitate the mapping, these regular computations can be represented in some computational graphs. In this dissertation (1) a canonical mapping methodology is introduced to map homogeneous computational graphs onto arrays; (2) a generalized mapping methodology is proposed to map heterogeneous computational graphs onto arrays; (3) algorithm matching techniques are developed to ensure the efficient execution of algorithms on a given array; and (4) a single-track switch model is proposed and a reconfiguration algorithm is developed for high yield implementation of mesh processor arrays. To unify these techniques, a set of programs are developed on a Sun workstation (Sun 3/60) with a color monitor. The resulting software is intended to be used as a CAD tool for designing a processor array. The input to the system is a description of the computation to be parallelized and executed on a processor array. The system accepts high-level behavior inputs in terms of dependence graphs (DGs) and generates array structures. The system provides graphic interface, criteria evaluator, and simulation tools to facilitate the designer. A designer can see the DG graphically displayed, modify the DG, simulate the DG, evaluate different optimally criteria, select an "optimal" design, and then do simulation to verify the correctness. Price: Domestic $20.50; International $30.75 USC-SIPI REPORT #143 "Transient Fault Recovery Techniques for the VLSI Processor Arrays" by Elias S. Manolakos May 1989 The high throughput rates necessary for real time signal/image processing applications can now be met cost effectively by VLSI technology. The VLSI processor arrays having a large number of regularly connected processing elements and using massive parallel processing provide a suitable form of supercomputing power in this application domain. Since most of the inevitable run time faults are of temporary nature transient fault recovery becomes a crucial issue, especially for arrays operating in a hostile environment that have to meet stringent time constraints. A new distributed retries mechanism called Neighbor Assisted Recovery (abbreviated as NEAR) is proposed. As opposed to the traditional Self Retries (SR) mechanism, by utilizing some knowledge about the data dependencies structure of the algorithm under execution, we can achieve better utilization of the neighbors of a temporary failed processor. So the array can continue to provide useful service in a degraded fashion, even in the presence of multiple clustered processor errors. The optimal dynamic assistant assignment policy that guarantees the minimum recovery time overhead for any error pattern in a linear array has been constructed. The optimal policy of NEAR can be efficiently implemented using localized decision -making and near neighbor communications. Using the OCCAM concurrent programming language and a board of Transputer processors a simulator of faulty tolerant linear arrays has been developed. After injecting an error pattern, the recovery time overheads imposed by NEAR or the traditional SR scheme can be measured and compared. For a large variety of error patterns, an average recovery speedup factor close to the theoretical value of two is observed. If extra time can detection and location. The Time Redundancy with Dependency Graphs Interleaving for fault tolerance (TRI-ft), is a methodology that allows the user to create different time redundancy schemes and evaluate their merits early in the design phase. Tradeoffs like the expected roll-back path length versus the permanent error location capability can be studied. In more general terms this dissertation is an attempt to unify the quest for fault tolerance with the mapping of regular algorithms to array architectures. Price: Domestic $13.50; International $20.25 USC-SIPI REPORT #144 "Structural Stability of Unsupervised Learning in Feedback Networks" by Bart Kosko April 1989 Structural stability is insensitivity to purturbations. Global stability, in contrast, is convergence to fixed points for all inputs and all parameters. Globally stable neural networks need not be structurally stable, need not be robust. Shaking can distort, destroy, or prevent equilibria. Then large-scale hardware implementation becomes dubious, and biological plausibility decreases. A large class of unsupervised nonlinear feedback neural networks, adaptive bidirectional associative memory (ABAM) models, is proven structurally stable. This is achieved by extending the ABAM models to the random-process domain as systems of stochastic differential equations, and appending scaled Brownian diffusions. This much larger family of models, random ABAM (RABAM) models, is then proved globally stable. Intuitively, RABAM equilibria are ABAM equilibria that randomly vibrate. Included in the ABAM family of structurally stable models are Hopfield circuits, Hodgkin-Huxley networks, competitive-learning networks, and ART-2 networks. All RABAM models permit Brownian annealing. The extent of RABAM system "vibration" is characterized by the RADAM Noise Suppression Theorem: The mean-squared activation and synaptic velocities, E[x2i], E[y2j], and E[m2i], decrease exponentially quickly to their lower bounds, the respective temperature-scaled noise "variances," Tis2i, Tjs2j, and Tijs2ij. This suggest that many feedback neural network models are more biologically "realistic" than they are often criticized as being. For, the many neuronal and synaptic parameters missing from such neural network models are now included, but as net random unmodeled effects. They simply do not affect the structure of realtime global computations. Price: Domestic: $2.50; International: $3.75 USC-SIPI REPORT #145 "Statistical Image Processing: Restoration and Reconstruction" by Thomas James Hebert April 1989 This dissertation develops statistical approaches to image restoration and reconstruction. A statistic-based stopping criterion for iterative least squares and maximum likelihood image reconstruction is developed to regularize the solution by effecting a trade-off between the maximum likelihood or least squares solution and a maximally smooth uniform image. Bayesian estimation is embraced as a probabilistic method of incorporating qualitative information regarding the local smoothness of images. Markov random field priors in the form of Gibbs distributions are formulated to incorporate local correlations and smoothness yet allow abrupt changes to occur across a boundary between two regions in an image. A computationally efficient algorithm for Bayesian image reconstruction based on Gibbs distribution priors is derived. This algorithm combines the complete/incomplete data formulation of the expectation - maximization approach, coordinate ascent, the optimal step-size of a maximum likelihood algorithm derived along parallel lines, and a method of adjusting the step size if necessary. A statistic-based approach to selection of the Gibbs prior parameter is developed and its potential for selecting the optimal parameter with respect to L1 and L2 restoration error is evaluated. The resulting solution is set in a control systems framework and a feedback algorithm for use in conjunction with any deterministic MAP algorithm for simultaneous parameter selection and image restoration or reconstruction is presented. Some problems in emission tomography are also addressed. An intermediate polar pixel representation for the unknown 3-D image is used to reduce the computational requirements of iterative reconstruction algorithms. An efficient method of directly including attenuation in iterative reconstruction algorithms is suggested. An experimental emission imaging system with a spatially varying point source response is examined. A probabilistically based factorization of the system matrix for the experimental system is introduced allowing the computational demands of a class of iterative algorithms to be reduced by several orders of magnitude. A modification to a well known maximum likelihood algorithm is introduced to increase the rate of convergence of the likelihood by a factor of five. Price: Domestic $20.00; International $30.00 USC-SIPI REPORT #146 "Artificial Neural Network Algorithms for Some Computer Vision Problems" by Yi-Tong Zhou June 1989 The problem considered here involves the use of an artificial neural network for solving some computer vision problems such as static and motion stereo, computation of optical flow, and image restoration. The network used in this research contains massive mutually interconnected and self-connected binary neurons. Two decision rules, deterministic and stochastic, are used. The stochastic decision rule guarantees convergence to a global minimum but computationally is very expensive, while the deterministic decision rule greatly reduces computing time, but only gives a local minimum. Two basic methods, static and motion stereo, for extracting 3-D information from more than one image are considered. The static stereo method is based on images taken by two cameras separated by a known baseline. The motion stereo method infers depth information from a sequence of monocular images. The derivatives of the intensity function are used for matching. A window operator which functions very similar to the human eye in detecting the intensity changes is proposed for estimating the derivatives. Under the epipolar, photometric and smoothness constraints the neural network is employed for the matching procedure. For motion stereo, two algorithms, batch and recursive, which allow the use of arbitrarily many image frames are presented. No surface interpolation step is involved in the algorithms because of the dense derivatives used. An algorithm using rotation invariant primitives extracted from successive monocular images is presented for computing optical flow. Under local rigidity assumption and a smoothness constraint, the neural network is used to compute optical flow. To locate motion discontinuities, the information about occluding elements is utilized by embedding it into the bias inputs of the network. A batch solution is also developed for the case of pure translation. An approach for the restoration of grey level images degraded by a known shift invariant blur function and additive noise is developed. The neural network is employed to represent a possibly nonstationary image whose grey level function is the simple sum of the neuron state variables. The nonlinear restoration method is carried out iteratively by using a dynamic algorithm to minimize the energy function of the network. Owing to the model's fault-tolerant nature and computational capability, a high quality image is obtained using this approach . A practical algorithm with reduced computational complexity is also presented. The choice of the boundary values to reduce the ringing effect is discussed and comparisons to other restoration methods such as the SVD pseudoinverse filter, minimum mean square error (MMSE) filter and modified MMSE filter using Gaussian Markov random field model are given. A schematic diagram of optical implementation of the restoration algorithm is described To demonstrate the efficacy of all these algorithms, experimental results using both synthetic and natural images are presented. Price: Domestic $17.00; International $25.50 USC-SIPI REPORT #147 "Modeling and Parameter Estimation of Multidimensional Non-Gaussian Processes Using Cumulants" by A. Swami, G.B. Giannakis and J.M. Mendel August 1989 Extending the notion of second-order correlations, we define the cumulants of stationary non-Gaussian random fields, and demonstrate their potential for modeling and reconstruction of multidimensional signals and systems. Cumulants and their Fourier transforms called polyspectra preserve complete amplitude and phase information of a multidimensional linear process, even when it is corrupted by additive colored Gaussian noise of unknown co-variance function. Relying on this property, phase reconstruction algorithms are developed using polyspectra, which can be computed via a 2-D FFT-based algorithm. Additionally, consistent ARMA parameter estimators are derived for identification of linear space-invariant multidimensional models which are driven by unobservable, i.i.d., non-Gaussian random fields. Contrary to autocorrelation based multidimensional modeling approaches, when cumulants are employed, the ARMA model is allowed to be non-minimum phase, asymmetric non-causal or non-separable. Price: Domestic $4.00; International $6.00 USC-SIPI REPORT #148 "Multilevel Filtering Elliptic Preconditioners" by C.-C. Jay Kuo, Tony F. Chan, and Charles Tong August 1989 We present a class of preconditioners for elliptic problems built on ideas borrowed from the digital filtering theory and implemented on a multilevel grid structure. They are designed to be both rapidly convergent and highly parallelizable. The digital filtering viewpoint allows us to use filter design techniques for constructing elliptic preconditioners and also provides an alternative framework for understanding several other recently proposed multilevel preconditioners. Numerical results are presented to assess the convergence behavior of the new methods and to compare them with other preconditioners of multilevel type, including the usual multigrid method as preconditioner, the hierarchical basis method and a recent proposed by Bramble-Pasciak-Xu. Price: Domestic: $4.50; International $6.75 USC-SIPI REPORT #149 "Generalized Graduated Non-Convexity Algorithm for Maximum A Posteriori Image Estimation" by Anand Rangarajan and Rama Chellappa December 1989 We are interested in restoring a degraded scene while preserving the edges. Edges are represented as line processes and are estimated along with the intensities in a Maximum a posteriori (MAP) framework. Assumptions regarding the prior and degradation distributions reduce the problem to one of energy function minimization. The energy function incorporates constraints on the restoration process like smoothness constraints, penalty for imposing a discontinuity and penalties on broken contours. This makes the energy function highly non-convex and finding the global minimum is a non-trivial problem. When constraints on the interactions between line processes are removed, the deterministic, Graduated Non-Convexity (GNC) algorithm has been shown to find close to optimum solutions. We have generalized the GNC model keeping some of its essentials. Any number of constraints on the line processes can now be added. This has been achieved by using the adiabatic approximation, a well known technique in synergetics. The adiabatic approximation also suggests the minimization scheme to be used. Our resulting algorithm is a combination of the completely deterministic. The algorithm was executed on two aerial images. Results are presented along with comparisons to the GNC algorithm. Price: Domestic $3.50; International $5.25 USC-SIPI REPORT #150 "Discretization and Solution of Elliptic PDEs - A Digital Signal Processing Approach" by C.-C. Jay Kuo and Bernard C. Levy December 1989 A digital signal processing (DSP) approach is used to study numerical methods for discretizing and solving linear elliptic partial differential equations (PDEs). Whereas conventional PDE analysis techniques rely on matrix analysis and on a space-domain point of view to study the performance of solution methods, the DSP approach described here relies on frequency domain analysis and on multidimensional DSP techniques. This tutorial paper discusses both discretization schemes and solution methods. In the area of discretization, mode-dependent finite-difference schemes for general second-order elliptic PDEs are examined, and are illustrated by considering the Poisson, Helmholtz and convection-diffusion equations as examples. In the area of solution methods, we focus on methods applicable to self-adjoint positive definite elliptic PDEs. Both direct and iterative methods are discussed, which include fast Poisson solvers, elementary and accelerated relaxation methods, multigrid methods, preconditioned conjugate gradient methods and domain decomposition techniques. In addition to describing these methods in a DSP setting, an up-to-date survey of recent developments is also provided. Price: Domestic $11.00; International $16.50 USC-SIPI REPORT #151 "Segmentation and Motion Estimation of Noisy Image Sequences" by Dimitrios Spiridon Kalivas February 1990 Two of the most important problems in image sequence are the segmentation of image frames into frames into moving parts. In this dissertation, we describe a method of solving these two problems. Our algorithm has two parts: segmentation and 2-D motion estimation. These two parts are interactively connected in a mutually beneficial way. The segmentation us performed by a statistical boundary estimation algorithm, which is based on the Minimum Mean Square Estimation criterion. The noise is assumed to be additive. The algorithm requires the a priori knowledge of the region where the boundary is expected to lie. This region is estimated for the rest of the frames. The algorithm does not use any a priori information about the shape of the objects. The 2-D motion estimation is performed by a region matching algorithm. This algorithm estimates accurately the linear 2-D motion and gives a very good linear approximation in the case of a nonlinear 2-D motion. It requires segmented images which are provided by the segmentation part. The performance of each part and the combined algorithm is examined using computer generated and real images corrupted by additive white Gaussian noise. The algorithm performs very well in a very noisy environment. The boundaries are estimated very accurately. The motion parameters estimates are approximate but robust. Finally, the application of the combined algorithm in the image sequence enhancement problem is examined. A motion compensated, edge preserving image sequence enhancement algorithm is presented and its performance is examined using computer generated and real images. The results are very satisfactory and they verify the efficiency of the combined segmentation and motion estimation algorithm. Price: Domestic $13.50; International $20.25 USC-SIPI REPORT #152 "VLSI Design of Adaptive Neural Systems" by Bang Won Lee May 1990 VLSI neural circuits play an important role in exploring and exploiting the rich properties of neural networks associated with massively parallel processing using analog neurons and synapses. The algorithms for artificial neural networks can be mapped to the VLSI neural systems if the building block exist. Novel techniques which find and eliminate the local minima in Hopfield networks have been developed. With modified Hopfield networks using these techniques, the local minima in Hopfield neural-based A/D converters and traveling salesman problems are successfully eliminated. A competitive Hopfield network, is very effective and efficient in finding a valid, near-optimal solution for the combinatorial optimization problem. The hardware annealing technique using the analogy between the annealing temperature and neuron gain is also described. Due to intrinsic continuity of the hardware annealing process, the computational time for searching the optimal solution is minimized. A compact and electrically programmable analog synapse cell in CMOS technologies is presented. Both DRAM-style and EEPROM-style weight storage mechanism are explored. By using the programmable synapses and gain-adjustable neurons, prototyping integrated-circuits which can operate in either asynchronous or synchronous modes are fabricated and evaluated. The neural-based A/D conversion and digital image restoration are used as system-level application examples. The VLSI neural chips can conduct network retrieving and learning processes concurrently. In the DRAM-style neural chips, weights of analog synapse cells are externally programmed and require dynamic refreshing. In the EEPROM-style neural chips, synapse weights are permanently stored in the floating gate. If the compact synapse and neuron cells are used in the industrial-level 1-mm VLSI technologies, a fully-connected general-purpose neural chip with 500 neurons can be achieved in 1 silicon area. Price: Domestic $19.50; International $29.25 USC-SIPI REPORT #153 "Integration of Technology-Based Design Systems for VLSI Circuits" by Chung-Ping Wan February 1990 Integration of technology-based design systems is strongly needed for the manufacturing of very-large-scale integrated circuits. The computer-aided design program PARGEN which provides accurate and efficient interface between the device simulator PISCES-IIB and the circuit simulator SPICE-3C1 in the technology-based design system is described. Algorithms to calculate parameter values for the built-in MOSFET and MESFET models have been developed and incorporated into this interface program. Only six device simulation results are required to extract a complete set of the popular Level-2 MOSFET model parameters and four device simulation results are needed for the MESFET model in the circuit simulator. This interface program, together with the process simulator, device simulator, and circuit simulator, form an integrated simulation environment for computer-integrated manufacturing of microelectronic chips. Such an integrated simulation environment greatly facilitates the designers to examine just how a microscope fabrication variable, such as the implantation dose, affects final device and circuit performance and product yield. A methodology for efficient circuit modeling and simulation in the integrated simulation environment is also described. A subset of circuit-level sensitive parameters which have large effects on simulated transistor output characteristics is used in this methodology. The sensitive model parameters are identified through a sensitivity analysis. This methodology has been applied to the temperature dependence modeling of the BSIM (Berkeley short-channel IGFET model) for MOS transistors in the circuit simulators. Updating of model parameter values for the sensitive parameter subset is performed prior to circuit simulation at each given temperature. For a 1.2-mm CMOS fabrication process, the sensitive parameter subset for temperature effects consists of only eight out of the sixty-seven BSIM parameters. Circuit simulation results using this sensitive model parameter subset approach agree with experimental data on transistor output characteristics, inverter transfer characteristics, and oscillation frequency of a 31-stage ring oscillator. Price: Domestic $17.00; International $25.50 USC-SIPI REPORT #154 "Multilevel Filtering Preconditioners: Extensions to More General Elliptic Problems" by Charles H. Tong, Tony F. Chan and C.C. Jay Kuo December 1990 We briefly review the concept of multilevel filtering (MF) preconditioners applied to second-order self-adjoint elliptic problems. We then show how to effectively apply this concept to other elliptic problems such as the second-order anisotropic problem, Helmholtz equation, convection-diffusion equation, biharmonic equation, equations on locally refined grids and interface operators arising from domain decomposition methods. Numerical results are given to show the effectiveness of the MF preconditioners on these problems. Price: Domestic $2.50; International $3.75 USC-SIPI REPORT #155 "Design and Analysis of Toeplitz Preconditioners" by Takang Ku and C.C. Jay Kuo May 1990 The solution of symmetric positive definite Toeplitz systems Ax = b by the preconditioned conjugate gradient (PCG) method was recently proposed by Strang [21] and analyzed by Strang and R. Chan [7]. The convergence rate of the PCG method heavily depends on the choice of preconditioners for given Toeplitz matrices. In this paper, we present a general approach to the design of Toeplitz preconditioners based on the idea to approximate a partially characterized linear deconvolution with circular deconvolutions. All resulting preconditioners can therefore be inverted via various fast transform algorithms with O(N log N) operations. For a wide class of problems, the PCG method converges in a finite number of iterations independent of N so that the computational complexity for solving these Toeplitz systems is O(N log N). Price: Domestic $4.50; International $6.75 USC-SIPI REPORT #156 "Adaptive Linearly-Constrained Filtering: Principles and Implementations" by Ching-Yih Tseng May 1990 Incorporating linear constraints in adaptive filters has arisen as a new trend to provide robust filtering operations in signal processing. The mechanism of this class of adaptive filter is to minimize the output power while constraining the weight values by a set of linear equations. The constraints are deliberately selected to confine the weights so that the signals of interest will not be canceled when minimizing the filter output power. Through this constrained power minimization process, the noise power is reduced without distorting the signals of interest and therefore it improves the signal to noise power ratio at the output. The basic requirement to utilize the adaptive linearly-constrained filter is to design the constraints. Appropriately setting up constraints requires the knowledge of the features regarding the particular signal of interest. Such features can be identified either through empirical methods, such as using a large set of training signals, or through theoretical methods, such as using the statistical information about the signals. After all, the resulting constraints have to effectively prevent the cancellation of signals of interest when the filter is applied. The second requirement is an adaptive algorithm to update the weights. To ensure implementation efficiency, it is desirable to develop implementation structures which are both computationally efficient and numerically stable. This dissertation presents some results from the study of the above two requirements in adaptive linearly-constrained filters. To develop procedures for constraint specification and performance evaluation, the understanding of the effect of the constraints on the steady-state behaviors of the filter is an essential. Such effect is studied here through examining the optimal weights, the signal-to-noise power ratios, and the addition of constraints. On the other hand, a model for implementation is established based on decoupling the weights into fixed and adaptive portions. By this decoupling, any unconstrained adaptive algorithm can be used to implement the adaptive-weight portion. Thus, only the fixed-weight implementation is studied in detailed in which the addressing issues include implementation structures and quantization effects. In the final part of this dissertation, a generalization of the adaptive linearly-constrained filters which allows the constraints to be adjustable is also discussed. Price: Domestic $15.00; International $22.50 USC-SIPI REPORT #157 "Unsupervised Hierarchical Segmentation of Textured Images Based on Homogeneity Testing" by Zhenyu Wu and Richard Leahy June 1990 A new unsupervised hierarchical segmentation scheme is presented and is applied to the problem of tissue classification of magnetic resonance (MR) images of the human brain. The images under study are modeled as a mosaic of 'homogeneous' subimages where each subimage is modeled as a first order Gauss-Markov random field (GMRF) with unknown parameters. The segmentation goal is to group the pixels into regions which, under a suitable hypothesis, are homogeneous GMRFs. An analysis of homogeneity testing for GMRF is presented and two tests are proposed: the hierarchical likelihood ratio test and the dispersion test. Useful analytic results are derived for the case of an uncorrelated random field. Based on the homogeneity tests a hierarchical segmentation approach is suggested. The image is represented by a quadtree, and a split and merge procedure is applied to find large homogeneous regions within the image. This is followed by a segmentation refinement step involving connected component labeling and region growing, in which most of the unclassified pixels will be attached to the neighboring regions to which they are most similar. Finally, a constrained maximum likelihood agglomerative clustering procedure is used to reduce the number of segmented regions. The idea here is to allow the algorithm to learn about the image by first clustering the 'easy' pixels while delaying decisions on the 'hard' pixels until more information has been gathered. One difficulty encountered in implementing the algorithm is evaluating the likelihood for irregularly shaped regions. A new highly accurate approximation for the determinant of the covariance matrix based on eigenanalysis is proposed to overcome this problem. Price: Domestic $3.00; International $4.50 USC-SIPI REPORT #158 "Computation of 3-D Velocity Fields from 3-D Cine CT Images of a Human Heart" by Samuel M. Song and Richard M. Leahy June 1990 The motion of a deforming body is completely characterized by the velocity field (with initial position) generated by the motion. A method of computing the 3-D velocity field from 3-D cine CTs of a beating heart is proposed. Continuum theory provides two constraints on the velocity field generated by a deforming body. Assuming that (1) the image is proportional to some conserved quantity and (2) the imaged medium is incompressible, the velocity field must satisfy the divergence-free constraint and the incompressibility constraint. Computation of the velocity field using these two constraints is an ill-posed problem which may be regularized using a smoothness term. We define a penalty function as a weighted sum of the two constraining terms and the smoothness term. Minimization of this function yields the desired velocity field. Via variational calculus, it can be shown that the solution minimizing the penalty satisfies the Euler-Lagrange equations for this problem. The solution of the Euler-Lagrange equation is a set of coupled elliptic partial differential equations (PDEs). For numerical implementation, the PDEs obtained are discretized resulting in a system of linear equations AX = b where x is the solution velocity field. The matrix equation is solved using the conjugate gradient algorithm. Examples of experiments using simulated images and a cine CT of a beating heart are presented. Price: Domestic $2.50; International $3.75 USC-SIPI REPORT #159 "A Robust Algorithm for Inferring Shape from Shading" by Qinfen Zheng and Rama Chellappa July 1990 A robust algorithm for inferring shape from shading in a single image is presented. Assuming uniform albedo and a Lambertian surface for the imaging model, we first present methods for the estimation of illumination direction and surface albedo. Two methods for estimating the tilt of the illuminant are presented. One is based on local estimates on a smooth patch. The other method uses shading information along image contours. Both the slant angle of the illuminant and surface albedo are estimated from image statistics, taking into consideration the effects of self shadowing. The estimated parameters are then used in a shape from shading algorithm that enforces an integrability constrain, and incorporates a linear approximation for the reflectance map. Detailed experimental results on synthetic and real images are given to illustrate the usefulness of the method. Price: Domestic $6.50; International $9.75 USC-SIPI REPORT #160 "Textured Image Segmentation Based on Multivariate Analysis" by Ruey-Cheng Cheng July 1990 A textured image segmentation system is developed systematically based on multivariate analysis. A likelihood ration called Wilks' criterion is proposed as a measure of discriminant information and as a substitute for error analysis. Feature extraction is based on the scaled Karhunen-Loeve transformation (KLT) which consists of the selected scaled eigenvectors by maximizing the Wilks' criterion, that make the segmentation system work in optimally with minimum classification error. In order to simplify the computational complexity, a feature reduction procedure based on a linear transformation is used to maximize Wilks' criterion in the classification space. The best linear transformation is composed of principal eigenvectors of a generalized eigenvalue problem. Isolated errors always exist in the initial labeling because of the imperfections of texture modeling. These errors can be removed by applying a spatial constraint since neighboring pixels are likely to be in the same class. A Bayesian segmentation formulation is proposed, then a stochastic relaxation scheme is applied to remove isolated errors and to preserve the boundary positions precisely. In unsupervised segmentation, the main problem is to determine how many clusters are present. The conventional criterion g2|W| developed from multivariate variance analysis is not reliable for textured image segmentation because the covariance matrices of textures are different. Hypothesis testing requires exact density functions that restricts its applications. Information theoretic criteria, AIC and MDL, are new approaches to estimate the number of Clusters. They are based on the mixture maximum likelihood function and subject to some constraints. These approaches are superior to conventional criterion because mixture maximum likelihood function reflects the nature of the data structure and the goodness of model fitting. Differences of parameter estimation between the K-means algorithms and the maximization of mixture likelihood are also discussed. Price: Domestic $21.00; International $31.50 USC-SIPI REPORT #161 "A Linearly Constrained Adaptive Algorithm for Constant Modulus Signal Processing" by Michael J. Rude August 1990 This dissertation introduces an adaptive technique that is suitable for signal processing tasks in severe co-channel interference and multipath environments. The new approach is based on the minimization of complex envelope variations at the processor output subject to a set of linear constraints on the processor coefficients. As a result, it does not require a training, reference or desired signal for adaptation. This Linearly Constrained Constant Modulus (LCCM) method combines two existing untrained adaptive techniques: linearly constrained minimization of output power and unconstrained minimization of complex envelope or modulus variations. LCCM addresses the signal cancellation problem that occurs when untrained adaptive processors are used in hostile signal environments; minimization of output power can lead to signal cancellation in multipath scenarios and unconstrained minimization of envelope variations can lead to signal cancellation in applications that include constant envelope co-channel interference. Analysis of a narrowband array application shows that the LCCM approach will eliminate the signal cancellation problem when appropriate a priori information is incorporated into the constraint set. An additional result is that the signal of interest does not necessarily need to have the constant envelope property. Adaptive implementation of the LCCM method is accomplished using the common technique of Stochastic Gradient Descent (SGD.) Stable adaptive recursions are derived via comparison with other SGD recursions that are used for existing adaptive approaches. In addition, the roles of convergence parameters are described and practical values are specified. For special cases, convergence in the mean is shown. In a typical signal processing scenario, LCCM is used for initial acquisition of a signal and then adaptive processing is switched to a decision directed mode. Simulation results for LCCM in the start-up or acquisition mode are presented for both single and multi-channel reception of a digitally modulated signal. The single channel experiment consists of a fractionally spaced LCCM equalizer with a signal subspace based linear constraint. The multi-channel experiment consists of a narrowband array with a look direction constraint. In both cases, the LCCM processor rejects the co-channel interference and compensates for the multipath distortion. Price: Domestic $17.50; International $26.25 USC-SIPI REPORT #162 "A Domain Decomposition Preconditioner Based on a Change to a Multilevel Nodal Basis" by Charles H. Tong, Tony F. Chan, and C.-C. Jay Kuo August 1990 We present a domain decomposition method based on a simple change of basis on the interfaces and vertices and we show that this leads to an effective preconditioner compared to the ones previously considered such as the preconditioner by Bramble, Pasciak and Schatz (BPS) [2], and the hierarchical basis domain decomposition (HBDD) preconditioner by Smith and Widlund [8]. Our domain-decomposed preconditioner is based on Bramble, Pasciak and Xu's method give the same order of condition number, namely, O(log2 ) for problems with smooth coefficients. Numerically our method is much more effective and it appears to be O(1) for the model problem. Price: Domestic $2.50; International $3.75 USC-SIPI REPORT #163 "Spectral Properties of Preconditioned Rational Toeplitz Matrices" by Takang Ku and C.-C. Jay Kuo September 1990 Various Toeplitz preconditioners PN have recently been proposed so that the N C N symmetric positive definite Toeplitz system TN x = b can be solved effectively by the preconditioned conjugate gradient (PCG) method. It was proved that, if TN is generated by a positive function in the Wiener class, the spectra of the preconditioned matrices PN-1TN are clustered between (1 - e, 1 + e) except a finite number of outliers. In this research, we characterize the spectra of PN-1TN more precisely for rational Toeplitz matrices TN with preconditioners proposed by Strang [19] and the authors [15]. We prove that the number of outliers depends on the order of the rational generating function, and the clustering radius v is proportional to the magnitude of the last element in the generating sequence used to construct these preconditioners. For the special case with TN generated by a geometric sequence, our approach can be used to determine the exact eigenvalue distribution of PN-1TN analytically. Price: Domestic $2.50; International $3.75 USC-SIPI REPORT #164 "On the Spectrum of a Family of Preconditioned Block Toeplitz Matrices" by Takang Ku and C.-C. Jay Kuo November 1990 Research on preconditioning Toeplitz matrices with circulant matrices has been active recently. The preconditioning technique can be easily generalized to block toeplitz matrices. That is, for a block Toeplitz matrix T consisting of N ¥ N blocks with M ¥ M elements per block, we can use a block circulant matrix R with the same block structure as its preconditioner. In this research, we examine the spectral clustering property of the preconditioned matrix R-1T with T generated by two-dimensional rational functions T(zx, zy) of order (px, qx, py, qy). We show that the eigenvalues of R-1T are clustered around unity except at most O(M gy + N gx) outliers, where gx = max(px, qx) and gy = max(py, qy). Furthermore, if T is separable, the outliers are clustered together such that R-1T has at most (2gx + 1) (2gy + 1) asymptotic distinct eigenvalues. The superior convergence behavior of the preconditioned conjugate gradient (PCG) method over the conjugate gradient (CG) method is explained by a smaller condition number and a better clustering property of the spectrum of the preconditioned matrix R-1T. Price: Domestic $2.50; International $3.75 USC-SIPI REPORT #165 "Multiple Dipole Modeling and Localization from Spatio-Temporal MEG Data" by John C. Mosher, Paul S. Lewis, and Richard Leahy May 22, 1991 An array of biomagnetometers may be used to measure the spatio-temporal neuromagnetic field or magnetoencephalogram (MEG) produced by neural activity in the brain. A popular model for the neural activity produced in response to a given sensory stimulus is a set of current dipoles, where each dipole represents the primary current associated with the combined activation of a large number of neurons located in a small volume of the brain. An important problem in the interpretation of MEG data from evoked response experiments is the localization of these neural current dipoles. We present here a linear algebraic framework for three common spatio-temporal dipole models: i) unconstrained dipoles, ii) dipoles with a fixed location, and iii) dipoles with a fixed orientation and location. In all cases, we assume that the location, orientation, and magnitude of the dipoles are unknown. With a common model, we show how the parameter estimation problem may be decomposed into the estimation of the time invariant parameters using nonlinear least-squares minimization, followed by linear estimation of the associated time varying parameters. A subspace formulation is presented and used to derive a suboptimal least-squares subspace scanning method. The resulting algorithm is a special case of the well-known MUltiple SIgnal Classification (MUSIC) method, in which the solution (multiple dipole locations) is found by scanning potential locations using a simple one dipole model. Principal components analysis (PCA) dipole fitting has also been used to individually fit single dipoles in a multiple dipole problem. Analysis is presented here to show why PCA dipole fitting will fail in general, whereas the subspace method presented here will generally succeed. Numerically efficient means of calculating the cost functions are presented, and problems of model order selection and missing moments are discussed. Results from a simulation and a somatosensory experiment are presented. Price: Domestic $3.00; International $4.50 USC-SIPI REPORT #166 "Subtraction in Optical Neural Nets" by Chein-Hsun Wang December 1990 To fully use the advantages of optics in optical neural networks, an incoherent optical neuron (ION) model is proposed. The main purpose of this model is to provide for the requisite subtraction of signals without phase sensitivity of a fully coherent system and without the cumbrance of photon-electron conversation and electronic subtraction. The ION model can subtract inhibitory from excitatory neuron inputs by using two device responses. Functionally it accommodates positive and negative weights, excitatory and inhibitory inputs, nonnegative neuron outputs, and can be used in a variety of neural network models. An extension is given to include bipolar neuron outputs in the case of fully connected networks. The features of the ION model include a bias that is essentially independent of input weights and signals, a dynamically and globally variable threshold, the capability of implementing a sigmoid or binary threshold function for different neuron models, cascadability and ease of implementation. For example, this technique can in principle implement conventional inner-product neuron units and Grossberg's mass action law neuron units. Some implementation considerations, such as the effect of nonlinearities in the device response, noise and fan-in/fan-out capability are discussed and simulated by computer. An experimental demonstration of optical excitation and inhibitation on a 2-D array of neuron units using a single Hughes liquid crystal light valve (LCLV) is also reported. The ION model, in conjunction with optical weighted interconnections, can be used to implement arbitrarily connected neural networks. We describe its use to implement a model of simple cells of the visual cortex. Such simple cells perform the operations of edge detection, orientation selection, and in the case of moving objects, direction and speed selection. Experiments are described that utilize two Hughes liquid crystal light valves to perform the functions of input transduction and optical neuron unit implementation via ION. A multiplexed dichromated gelatin hologram serves as a holographic optical element that forms space invariant (but otherwise arbitrary) point spread functions for the network interconnections. By changing the holographic interconnection pattern, different simple cells performing , for example, transient response, edge detection, orientation preference, and direction and speed preference, can be implemented. Experimental results of these operations are presented. We also present a learning algorithm, potential difference learning (PDL), based on temporal difference of membrane potential of the neuron for self-organizing neural networks. It is independent of the neuron nonlinearity, so it can be applied to analog or binary neurons. Two simulations for learning of weights are presented; a single layer fully-connected network and a 3-layer network with hidden units for a distributed semantic network. The results demonstrate that potential difference learning can be used with neural architectures for various applications. Finally, we also describe an optical architecture for PDL and the integration of ION model with PDL and the application of ION to PDL implementation. Price: Domestic $17.50; International $26.25 USC-SIPI REPORT #167 "A Unified Approach to Boundary Perception: Edges, Textures, and Illusory Contours" by B.S. Manjunath and Rama Chellappa January 1991 This paper presents a unified approach to boundary perception. The model consists of a multistage system which extracts and groups salient features in the image at different spatial scales (or frequencies). In the first stage a Gabor wavelet decomposition provides a representation of the image which is orientation selective and has optimal localization properties in space and frequency. This decomposition is useful in detecting significant features such as step and line edges at different scales and orientations in the image. Following the wavelet transformation, local competitive interactions are introduced which help in reducing the effects of noise and changes in illumination. Interscale interactions help in localizing the line ends and corners, and play a crucial role in boundary perception. The final stage groups similar features, aiding in boundary completion. This approach is consistent with some of the known neurophysiological observations regarding biological visual information processing, as the different stages can be identified with processing by simple, complex and hypercomplex cells in the visual cortex of mammals. Experimental results are provided to indicate the performance of this model in detecting boundaries (both real and illusory) in real and synthetic images. Price: Domestic $3.00; International $4.50 USC-SIPI REPORT #168 "Adaptive Minimum Prediction-Error Deconvolution and Source Wavelet Estimation Using Hopfield Neural Networks" by Li-Xin Wang and Jerry M. Mendel January 1991 In this report, three Hopfield neural networks are developed to realize a new Adaptive Minimum Prediction-Error Deconvolution procedure. The first neural network is developed to detect the reflectivity sequence. The second neural network is developed to determine the magnitudes of the detected reflections. The third neural network is developed to estimate the seismic wavelet. A Block-Component Method is proposed for simultaneous reflectivity estimation and wavelet extraction based on these three neural networks. These three neural networks and the Block- Component Method are simulated for broad-band and narrow-band wavelets. Real seismic data are processed using the Block-Component Method, and the results are compared with those using the MVD Filter and the maximum-likelihood based SMLR Detector [8,9]. Compared with existing deconvolution methods, the Neural Network Adaptive Minimum Prediction-Error Deconvolution method of this report has the following advantages: (1) it is totally realized by standard Hopfield neural networks which are suitable for hardware implementation; (2) the new Block-Component Method gives better results for real seismic data processing than the MLD-based Block Component Method; (3) the Neural Reflectivity Estimator gives much better results than the SMLR Detector in the case of a narrow-band wavelet and low signal-to- noise ratio; and, (4) it needs very weak assumptions about the wavelet and the reflectivity sequence, i.e., it is suitable for a nonminimum-phase wavelet, non-Gaussian or colored measurement noise, and, the reflectivity sequence can be random or deterministic. Price: Domestic $3.50; International $5.25 USC-SIPI REPORT #169 "Generating Fuzzy Rules from Numerical Data, with Applications" by Li-Xin Wang and Jerry M. Mendel January 1991 In this report, a general method is developed to generate fuzzy rules from numerical data. This new method consists of five steps: Step 1 divides the input and output spaces of the given numerical data into fuzzy regions; Step 2 generates fuzzy rules from the given data; Step 3 assigns a degree to each of the generated rules for the purpose of resolving conflicts among the generated rules; Step 4 creates a combined Fuzzy-Associative-Memory (FAM) Bank based on both the generated rules and linguistic rules of human experts; and, Step 5 determines a mapping from input space to output space based on the combined FAM Bank using a defuzzifying procedure. The mapping is proved to be capable of approximating any non-linear function on a compact set to arbitrary accuracy. Applications to truck backer-upper control [1] and time series prediction [2] problems are presented. For the truck control problem, the performance of this new method is compared with a neural network controller and a pure limited-rule fuzzy controller; the new method show the best performance. For the time series prediction problem, results are compared by using the new method, a neural network predictor, and a AR model predictor for real time series data and a chaotic time series. Price: Domestic $6.00; International $9.00 USC-SIPI REPORT #170 "A Two-Step Approach to Passive Navigation Using a Monocular Image Sequence" by S. Chandrashekhar and R. Chellappa February 1991 This paper discusses the design and application of estimation techniques to the problem of obtaining the kinematics of a moving vehicle and the structure of the external environment, based on a sequence of images taken by a camera attached rigidly to the vehicle. ``Structure'' refers to the 3-D locations of selected points of interest (landmarks) in the environment, expressed in an inertial, or ``world'' coordinate system. The (noisy) image plane trajectories of these feature points are assumed to be available, and the 3-D positions of a small number (typically 3 or 4) of them are assumed to be known. Using simple models for the motion of the vehicle it is possible to utilize effectively the information contained in image sequences of arbitrary length. Batch and recursive estimation techniques are developed to estimate the motion and structure parameters. In the first step, the batch estimation method is applied to obtain an initial estimate and its approximate error covariance, which is then used in the second step to initialize the recursive filter for tracking the parameters of interest. Experimental results on synthetic data and on one of the UMASS ALV image sequences are given. Price: Domestic $2.50; International $3.75 USC-SIPI REPORT #171 "A Minimum-Phase LU Factorization Preconditioner for Toeplitz Matrices" by Ta-Kang Ku and C.-C. Jay Kuo February 1991 A new preconditioner is proposed for the solution of an N x N Toeplitz system TN x=b, where TN can be symmetric indefinite or nonsymmetric, by preconditioned iterative methods. The preconditioner FN is obtained based on factorizing the generating function T(z) into the product of two terms corresponding, respectively, to minimum-phase causal and anticausal systems and therefore called the minimum- phase LU (MPLU) factorization preconditioner. Due to the minimum-phase property, ||FN-1|| is bounded. For rational Toeplitz TN with generating function T(z) = A(z-1)/B(z-1) + C(z)/D(z), where A(z), B(z), C(z) and D(z) are polynomials of orders p1, q1, p2, and q2, we show that the eigenvalues of FN-1TN are repeated exactly at 1 except at most aF outliers, where aF depends on p1, q1, p2, q2 and the number w of the roots of T(z) = A(z-1) D(z) + B(z-1) C(z) outside the unit circle. A preconditioner KN in circulant form generalized from the symmetric case is also presented for comparison. The MPLU preconditioner FN performs better than circulant preconditioner KN in our numerical experiments. Price: Domestic $2.50; International $3.75 USC-SIPI REPORT #172 "Shape from Shading with A Linear Triangular Element Surface Model" by Kyoung Mu Lee and C.-C. Jay Kuo February 1991 We propose to combine a triangular element surface model with the linearized reflectance map to formulate the shape from shading problem in this research. The key idea is to approximate a smooth surface by the union of triangular surface patches called triangular elements, and express the approximating surface as a linear combination of a set of nodal basis functions. Since the surface normal of a triangular element is uniquely determined by the heights of its three vertices (or nodes), the image brightness can be directly related to the nodal heights via a linearized reflectance map. The surface height can therefore be determined by minimizing a quadratic cost functional corresponding to the squares of the brightness error and solved effectively with the multigrid computational technique. The proposed method does not require any integrability constraint or artificial assumptions on boundary conditions. Simulation results for several synthetic and real images are demonstrated to show the performance and efficiency of our new method. Price: Domestic $3.50; International $5.25 USC-SIPI REPORT #173 "Photonic Implementations of Neural Networks" by B. Keith Jenkins and Armand R. Tanguay, Jr. March 1991 No Abstract Available. Price: Domestic $16.00; International $24.00 USC-SIPI REPORT #174 "Computational Study of Structured Networks for Linear Algebra" by Chung-Kuang Chu and Jerry M. Mendel April 1991 Structured networks based on the error back-propagation method can solve many linear algebra problems. In this report, the computational requirements for structured networks are analyzed in order to provide computation time information. With this data, we can roughly evaluate the performance of structured networks. First, computation counts are estimated for serial implementations. These counts are based on a computation schedule which is provided for each linear algebra problem. We also give results for the theoretical processing time (which is estimated from the computation counts) and the actual processing time. Finally, we estimate the processing time for parallel implementations by introducing the basic computing units, which perform the inner product operations. Computation schedules are also provided for the parallel implementations. Price: Domestic $3.50; International $5.25 USC-SIPI REPORT #175 "Spectral Properties of Preconditioned Rational Toeplitz Matrices: The Nonsymmetric Case" by Ta-Kang Ku and C.-C. Jay Kuo April 1991 Various preconditioners for symmetric positive-definite (SPD) Toeplitz matrices in circulant matrix form have recently been proposed. The spectral properties of the preconditioned PSD Toeplitz matrices have also been studied. In this research, we apply Strang's preconditioner SN and our preconditioner KN to an N x N nonsymmetric (or nonhermitian) Toeplitz system TNx=b. For a large class of Toeplitz matrices, we prove that the singular values of SN-1TN and KN-1TN are clustered around unity except a fixed number independent of N. If TN is additionally generated by a rational function, we are able to characterize the eigenvalues of SN-1TN and KN-1TN directly. Let the eigenvalues of SN-1TN and KN-1TN be classified into the outliers and the clustered eigenvalues depending on whether they converge to 1 asymptotically. Then, the number of outliers depends on the order of the rational generating function, and the clustering radius is proportional to the magnitude of the last elements in the generating sequence used to construct the preconditioner. Numerical experiments are provided to illustrate our theoretical study. Price: Domestic $2.50; International $3.75 USC-SIPI REPORT #176 "Neural Networks based on the Incoherent Optical Neuron Model" by Chein-Hsun Wang and B. Keith Jenkins April 1991 To fully use the advantages of optics in parallel implementations of neural networks, an incoherent optical neuron (ION) model can be used to optically implement neurons with both excitatory and inhibitory inputs. The main purpose of this model is t provide for the requisite subtraction of signals at each neuron unit without the phase sensitivity of a fully coherent optical system and without the cumbrance of photon-electron conversion and electronic subtraction. The ION model, in conjunction with coherent or incoherent optical weighted interconnections, can be used to implement arbitrarily connected neural networks. This chapter describes techniques for implementation of both analog and binary inner product neuron units as well as mass action law neuron units. Potential use of the ION model in implementing the neocognition model, multilayer networks, selective attention for winner-take-all networks, and simple cells of the visual cortex are discussed. In addition, experimental results on the optical implementation of a 2-D array of IONs and of sequential feature detection operations of the visual cortex, are reviewed. Price: Domestic $6.00; International $9.00 USC-SIPI REPORT #177 "Comparison between Correlation-Based and Cumulant-Based Approaches to the Harmonic Retrieval and Related Problems" by Dae C. Shin and Jerry M. Mendel April 1991 In signal processing, we frequently encounter the problem of estimating the number of harmonics, frequencies, and amplitudes in a sum of sinusoids. The observed signals are usually corrupted by spatially and/or temporally colored noise with unknown power spectral density. It has been shown by Swami and Mendel that a cumulant-based approach to this problem is very effective. In this report, we compare the use of biased and unbiased, segmented and unsegmented estimators for both correlation and 1-D diagonal slice of the fourth-order cumulant function. We suggest using accumulated singular values to determine the number of harmonics. We compare correlation-based and cumulant-based methods for determining the number of harmonics when the amplitude of one harmonic decreases and when the frequency of one harmonic approaches the other for the case of two sinusoids measured in colored Gaussian noise. We also compare the performance of the Pisarenko, MUSIC, and minimum-norm algorithms for frequency estimation, and the performance of least square (LS), total least square (TLS), and constrained total least square (CTLS) for amplitude estimation using either correlations or cumulants. Our studies: (1) provide further support for using cumulants over correlations when measurement noise is colored and Gaussian; (2) demonstrate that one should use unbiased unsegmented correlation or cumulant estimators; (3) indicate that high-resolution results are best obtained using cumulant-based MUSIC or minimum-norm algorithms; and (4) show that LS estimates of amplitudes suffice. Price: Domestic $8.00; International $12.00 USC-SIPI REPORT #178 "Hierarchical Representation, Matching, and Search for Some Computer Vision Problems" by Vadlamannati Venkateswar August 1991 Representation, matching, and search are central to the task of scene interpretation. Representation refers to how the scene and models are organized for subsequent interpretation tasks, like recognition. A hierarchical representation scheme for scenes and models allows for robust interpretation strategies that exploit the different levels of the hierarchy. In this scheme, features in the scene are composed into more complex objects based on physical and geometric properties and the models are similarly decomposed into simpler features. Such hierarchies are concisely represented using frames. For matching, we support a hierarchical strategy where features at the higher level of the hierarchy are matched first and those at the lowest level last. Higher level features are fewer in number and have more structure and so are easier to match. These matches constrain the matches at lower levels. The ambiguities involved in feature grouping and matching result in a search space. As an alternative to relaxation and tree search techniques, we advocate the use of a search scheme based on an Assumption based Truth Maintenance System (ATMS) for exploring this search space. The ATMS assists in simultaneous search in multiple contexts, enforces binary or higher order constraints, assists in symbolic uncertainty reasoning and carries out belief revisions necessitated by incremental additions, deletions and confirmations of feature and match hypotheses. We design three applications based on these general principles. These include building detection, stereo matching, and motion correspondence. An appropriate representation for these tasks is a hierarchy consisting of lines, vertices, edges, and surfaces. In building detection, a dynamic search scheme based on an ATMS assists in the integration of bottom-up and top-down information in the search for roofs. In stereo matching, a hierarchical matching strategy used for motion correspondence results in both point and line matches. This framework can be applied to other applications, like object recognition from 2D or 3D data using 3D models, multi-sensor fusion, etc. Price: Domestic $19.00; International $28.50 USC-SIPI REPORT #179 "A Robust Approach to Linearly-Constrained Adaptive Array Processing" by George Thomas Zunich May 1991 Minimum variance beamforming is a powerful technique in adaptive array processing that allows the reception of a signal of interest while nulling unwanted interfering signals. In the presence of a high input signal-to-noise ratio (SNR), however, the technique is very sensitive to amplitude and phase perturbations of the array processing system and the processor may attempt to null the signal of interest as if it were an interfering signal. The result is a substantial degradation of the output SNR of the beamformer over that achieved for the error-free system. This dissertation presents and analyzes robust constraints that protect a minimum variance beamformer from the effects of small phase anomalies resulting from factors such as random channel phase errors, array placement errors, steering errors, and/or frequency miscalibration. The use of robust constraints is shown to eliminate the need for precise phase calibration of the array. This is an important contribution because, in most practical applications, precise phase calibration is more difficult than is accurate amplitude calibration. The approach taken in this thesis is to first demonstrate that the robust constraints can be derived directly from an analysis of the beamformer output power. A critical parameter which depends on both the beamformer weighting coefficients and the phase errors is identified. It is shown that performance degradation will only occur when this parameter lies within a circular region in the complex plane. Robust constraints for the array weights are then identified which force the parameter value to be external to the circular region, regardless of the specific values of sufficiently small phase errors. An identical set of robust constraints is shown to arise when derivative constraints are placed on individual array elements. A closed-form solution for the weight coefficients achieved with robust constraints is derived for the specific case of a narrowband adaptive array processor. Equations are developed that predict SNR performance resulting from the use of the robust constraints. An adaptive processor for the robust system is developed using a modified Generalized Sidelobe Canceller structure. Performance of the robust system is illustrated using both simulation experiments with synthesized input data and computations on actual array data. The results obtained confirm the effectiveness of the constraints in phase-perturbed environments. Price: Domestic $12.50; International $18.75 USC-SIPI REPORT #180 "VLSI Neurocomputers: EE 599 Term Projects / 1990-1991" edited by Bing J. Sheu and Chia-Fen Chang May 1991 No Abstract Available Price: Domestic $20.50; International $30.75 USC-SIPI REPORT #181 "Preconditioned Iterative Methods for Solving Toeplitz-Plus-Hankel Systems" by Ta-Kang Ku and C.-C. Jay Kuo June 1991 The use of preconditioned iterative methods to solve a system of equations with a Toeplitz-plus-Hankel coefficient matrix is studied. We propose a new preconditioner suitable for Toeplitz-plus-Hankel matrices, and examine the spectral properties of preconditioned rational Toeplitz-plus-Hankel matrices. We show that the eigenvalues of the preconditioned matrix are clustered around unity except a finite number of outliers depending on the orders of the rational generating functions, and the clustering radius is proportional to the magnitude of the last elements in Toeplitz and Hankel matrices. With the spectral regularities, an N x N rational Toeplitz-plus-Hankel system can be solved by preconditioned iterative methods with O(N log N) operations. Numerical experiments are given to demonstrate the efficiency of the proposed preconditioner. Price: Domestic $2.50; International $3.75 USC-SIPI REPORT #182 "3-D Motion Estimation Using a Sequence of Noisy Images" by Gem-Sun Jason Young May 1991 In this dissertation we study several aspects of three dimensional (3-D) motion and structure estimation fro a sequence of noisy images. A high order motion model is proposed based on representing the constant acceleration translational motion and constant precession rational motion in the form of a bilinear state space model using standard rectilinear states for translation and quaternions for rotation. The measurements are noisy perturbations of 3-D feature points represented in an inertial coordinate system. The structure of the moving object is estimated from the stereo image pairs prior to the estimation of motion parameters. Owing to the nonlinearity in the state model, nonlinear filters are then designed for the estimation of motion parameters. The Cramer-Rao performance bounds for motion parameter estimates are computed. A constructive proof for the uniqueness of motion parameters is given. It is shown that with uniform sampling in time, three noncollinear feature points in five consecutive binocular image pairs contain all the spatial and temporal information required for motion estimation. If 3-D motion and structure are estimated simultaneously, we show that the standard 3 x 3 rotation matrix is more suitable for representing the rotational motion than quaternions. Using this representation, a new motion model for constant velocity translation and constant angular velocity rotation is given. Both monocular and binocular systems are considered. Batch and recursive algorithms are designed to search ad track, respectively, the moving rigid object. Occlusion among image frames as well as between each stereo pair in the binocular case is also dealt with. A nonlinear least squares method is used to formulate the batch estimation of motion and structure parameters. Nonlinear Kalman filters are used for the recursive algorithms. Owing to parameterization of translational motion using a time-invariant global normalization factor, linear plant models are used in the recursive filters to update the motion in closed form, and thus avoiding the time-consuming numerical integration, which commonly arises in nonlinear filtering problems. The optical flow field is another commonly used image measurement for motion estimation. However, flow fields generated by existing algorithms are noisy and thus induce ambiguities in motion parameters. In this work, the inherent ambiguities in recovering 3-D motion information from a single optical flow field are studied using a statistical model. These ambiguities are quantified using the Cramer-Rao lower bound (CRLB), which is a lower bound for the error variances of motion parameters estimates. This performance bound is independent of this motion estimation algorithms, and can always be computed for any arbitrary 3-D motion of a rigid surface by inverting a 5 x 5 matrix. As a special case, the performance bound for the motion of 3-D rigid planar surfaces is studied in detail. For the general motion of an arbitrary surface, it turns out that not every pixel gives information regarding 3-D motion estimation. It is shown that the aperture problem in computing optical flow restricts the nontrivial information about the 3-D motion to a sparse set of pixels at which both components of the flow velocity are observable. Effects of two smoothing schemes on estimation accuracy are analyzed. It is shown that by introducing a smoothness constraint by fitting local patches to 3-D depths gives lower CRLB's. Surprisingly, this reduction in CRLB's is very small. Further, fitting local patches also relaxes the aperture problem since the motion information is not restricted to points at which both optical flow components are observable. In contrast, imposing smoothness on the optical flow by regularization does not lower the CRLB's. Although these results are all derived using a simple Gaussian noise model and should be interpreted with caution, they nevertheless give some new insights in analyzing inherent ambiguities. Price: Domestic $19.50; International $29.25 USC-SIPI REPORT #183 "Digital Motion Estimation and Image Restoration on VLSI" by Ji-Chien Lee July 1991 The processing of video signals often requires a tremendous computational capability which can only be achieved by using highly parallel processing architectures. The inherent massive parallelism of artificial neural network architecture for flexible information processing provides a new paradigm of video signal processing. This dissertation describes the computational needs of supercomputing neurocomputers for flexible information processing. Two neural network architectures and the efficient VLSI implementation of video signal processors are presented. In the first VLSI architecture, the motion information from a sequence of image data can be estimated through a two-dimensional multiprocessor array in which each processing element consists of an analog neuroprocessor. Massively parallel neurocomputing is done by compact and efficient neuroprocessors. Local data transfer between the neuroprocessors are performed by using analog point-to-point interconnection scheme. Global data communication between the host computer and neuroprocessors is carried out in the digital common bus. A mixed-signal VLSI neural chip that includes multiple neuroprocessors for fast video motion estimation has been designed. Measured results of the programmable synapse, summing neuron, and associated winner-take-all circuitry are presented. Based on the measurement data, system-level analysis on a sequence of real images were conducted. The device mismatch effect of analog synapse cells has been included during system-level analysis. A 1.5 x 2.8-cm2 chip in a 1.2-mm CMOS technology can accommodate 64 velocity-selective neuroprocessors and achieve 83.2 Giga connections per second. The speed-up factor over a Sun-4/75 SPARC-2 workstation is 24,242 for a system with 128 motion estimation chips. In the second architecture, an analog systolic multiprocessor for high-speed image restoration has been developed. For a two-dimensional image, parallel processing is performed in the row direction and pipelined processing is performed in the column direction. The mixed analog/digital design approach is also used for the implementation of the neural-based image restoration system. Local data computation is executed by analog circuitry to achieve full parallelism and to conserve power dissipation. Inter-processor communication is carried out in the digital format to maintain adequate signal strength across the chips boundary and achieve direct scalability in neural network size. A compact and efficient VLSI neural chip which includes multiple neuroprocessors for real-time digital image restoration has been designed. To use output of neuron as an increment/decrement information to control the pixel register, each neuron can process multiple- bit image information. A 8.0 x 6.0-mm2 chip from a 1.2-mm CMOS technology can accommodate 5 neuroprocessors and the speed-up factor over the Sun-4/75 SPARC-2 workstation is 475. This chip achieves 21.6 Giga connections per second. The future powerful and cheap supercomputing workstations will include flexible information processing capability for our daily lives and scientific applications. Price: Domestic $17.50; International $26.25 USC-SIPI REPORT #184 "Analysis and Design of Fuzzy Logic Controller" by Li-Xin Wang and Jerry M. Mendel August 1991 In this report, the fuzzy logic controller (FLC) with product inference, centroid defuzzification, and Gaussian membership function is proven to be capable of approximating any real continuous function on a compact set to arbitrary accuracy. The Stone-Weierstrass Theorem is used as a principal tool for the analysis. Design parameters of FLC are defined, and a parallel implementation architecture for FLC is proposed. An optimal multi-input-single-output FLC is designed which can match N given input-output data pairs to arbitrary accuracy using N fuzzy rules. In order to overcome the high complexity weakpoint of the optimal FLC, a sub-optimal design method is developed. Based on the parallel architecture of FLC, the sub-optimal FLC is designed by using a new back-propagation training algorithm. This report shows that the new back-propagation FLC (BP FLC) can utilize both numerical data and linguistic rules; specifically, the BP FLC is first trained to match the given input-output data pairs using the back-propagation algorithm, then linguistic rules from human experts are added to the trained BP FLC to form the final FLC. A method of choosing the initial parameters of the BP FLC is proposed which is based on the optimal FLC; this method is shown to be very effective and makes the training for the BP FLC very fast. The BP FLC is finally applied to approximate a controller for a non-linear system. By comparing the BP FLC with the back-propagation feedforward neural network (BP FNN), this report shows that: (1) the BP FLC can be applied to any problem which is suited for the BP FNN; (2) the BP FLC can utilize both numerical and linguistic information, while the BP FNN can only utilize numerical information; and, (3) the training for the BP FLC is much faster than that for the BP FNN. Price: Domestic $4.00; International $6.00 USC-SIPI REPORT #185 "Preconditioned Iterative Methods for Solving Toeplitz Systems" by Ta-Kang Ku August 1991 In the dissertation, we study the use of preconditioned iterative methods to solve linear systems of equations associated with Toeplitz, block Toeplitz and Toeplitz-plus-Hankel coefficient matrices. Two main issues are considered: the design of preconditioners and the convergence rate of preconditioned iterative methods. A systematic approach to the design of Toeplitz preconditioners with circulant matrices is proposed. This preconditioning scheme is then generalized to block Toeplitz and Toeplitz-plus-Hankel matrices. All resulting preconditioners of size N can be inverted with O(N log N) operations via various fast transform algorithms. Another novel scheme to design Toeplitz preconditioners baseon the minimum-phase LU (MPLU) factorization is also examined. The MPLU preconditioner can be inverted with O(N) operations. The convergence rate of preconditioned iterative methods depends on the eigenvalue or singular value distribution of preconditioned matrices. We perform spectral analysis for a large class of symmetric and nonsymmetric Toeplitz in general, and rational Toeplitz in particular. For rational Toeplitz, we classify the eigenvalues into outlying and clustered eigenvalues, and show that the number of outliers depends on the order of the rational generating function, and the clustering radius is proportional to the magnitude of the last elements in the generating sequence used to construct the preconditioner. Similar spectral results are obtained for Toeplitz-plus-Hankel systems. A direct consequence of the analysis is that preconditioned iterative methods converge in a fixed number of iterations independent of the problem size. The computational complexity of preconditioned iterative methods for solving an N x N Toeplitz system is therefore proportional to O(N log N). Compared to direct methods, preconditioned iterative methods provide three advantages: low computational complexity, ease of parallel implementation and stable numerical property. Price: Domestic $16.00; International $24.00 USC-SIPI REPORT #186 "Digital Image Processing on VLSI" by Bing J. Sheu and Oscal T.-C. Chen August 1991 An efficient processing element for data/image processing has been designed. Detailed communication networks, instruction sets and circuit blocks are created for ring-connected and mesh-connected systolic arrays for the retrieving and learning phases of the neural network operations. 800 processing elements can be implemented in 3.75 cm x 3.75 cm chip by using the 0.5 mm CMOS technology from TRW, Inc. This digital neuroprocessor can also be extended to support fuzzy logic inference. Price: Domestic $17.50; International $25.25 USC-SIPI REPORT #187 "Design and Reliability Simulation of VLSI Computing Circuits" by Wen-Jay Hsu August 1991 Design of very large-scale integration (VLSI) computing circuits require good means to assess circuit reliability in order to utilize the full potential of advanced submicron fabrication technologies. An integrated circuit may fail due to the degradation of some critical transistors or interconnection wires. This dissertation presents the integration of reliability modeling into the developed circuit simulator, RELY, which can predict circuit performance degradation due to progressive physical failure mechanisms. Modeling requirements and implementation of hot-carrier effects and electromigration including transistor modeling, stress monitors and degradation models for reliability simulation are addressed. Two simulation schemes for circuit reliability analysis are presented. Quick identification of weakest devices within a circuit can be achieved by the one-cycle simulation scheme. The repetitive simulation scheme provides the information on the impact of the progressive device degradation on circuit performance to account for the gradually changing stress condition in actual circuit operation. A systematic approach to include the first-order AC degradation effects in the quasi-static simulation is also described. Strategies for use in a hierarchical reliability simulation environment covering various levels of VLSI circuit design are presented. The degradation information is propagated through the design hierarchy starting from the circuit-cell level, the circuit-block level to the complete chip level. Reliability simulation using the RELY program can not only predict the degraded performance of the whole circuit, but also identify the most critical devices for improvement. Circuit topology changes can be applied to achieve high failure-tolerance in the computing circuits. Design examples of computing circuits and the associated performance degradation are presented. Example circuits including inverters, NAND gates, memory circuits, operational amplifiers and data converters have been studied using the industrial 0.8 mm and 0.5 mm CMOS technologies. By using these techniques on the design of CMOS components, high-speed circuits can be achieved with excellent long-term reliability. By adding a common-gate buffering transistor in the critical output stage of an operational amplifier, circuit lifetime is found to be improved by more than four times. Price: Domestic $22.00; International $32.00 USC-SIPI REPORT #188 "Perceptual Grouping and Segmentation Using Neural Networks" by B.S. Manjunath December 1991 Grouping and segmentation occur at all levels in the visual information processing hierarchy. We address here their relevance during the early stages in vision, using neural networks as the computing paradigm. Neural networks provide a fresh perspective in solving many of the early vision problems: they provide a parallel and distributed computing environment with the associated fault tolerance; a homogeneous architecture which might help in integrating different visual cues, and in incorporating active interactions between different processing stages; and their ability to learn and self-organize in a continuously changing environment. Besides, they help in bridging the gap between computer vision and human vision research. We first investigate the use of neural networks from a parallel computing perspective. Most low level vision problems such as model based texture segmentation can be formulated in an optimization framework. In the context of texture segmentation, we show how models based on Markov random fields naturally map onto networks for optimization. We develop a stochastic learning system which combines the speed of deterministic relaxation algorithms with the sustained exploration of search space, a characteristic of stochastic algorithms. We discuss extensions to unsupervised segmentation and the advantages of keeping estimation of parameters and segmentation separate. While model based approaches to segmentation incorporate knowledge about the textures to obtain fairly accurate results, they do not provide much intuition about human texture perception. The second half of this research is biologically motivated and we try to model some of the early processing stages in vision. We study the problem of pre-attentive texture perception in a more general framework of boundary detection, and develop a unified approach to detecting intensity as well as texture edges, in addition to illusory contours. We clearly demonstrate the role of end-inhibition, modeled by using local scale interactions, in texture boundary perception and in perceiving subjective contours. Visual illusions are a consequence of wired-in assumptions about the real world, which biological systems make full use of in order to process the enormous amount of visual data in real time. We suggest that the role of end-inhibited cells in the detection of illusory contours is not accidental. End-inhibition provides a robust model for feature detection and representation, and could be used in representing shape information. We demonstrate this in our development of a simple face recognition system, where object recognition is formulated as an inexact graph matching problem. Extensive experimental results are provided to illustrate the performance of the various algorithms. Price: Domestic $13.00; International $19.50 USC-SIPI REPORT #189 "Automated Synthesis of Analog MOS VLSI Circuit Modules" by David Jan-Chia Chen December 1991 Recent advances in VLSI technologies have allowed the integration of information processing subsystems on one chip, including both analog and digital parts. In addition to the conventional telecommunications and computer networking applications, new applications of mixed analog-digital VLSI are being unveiled in the fields of image processing and neural-based flexible information processing. The need for computer-aided design tools to reduce the dominant analog circuit design time and cost for such processor chips has become imminent. This thesis presents advanced methods for automatic synthesis of analog MOS VLSI circuit modules. A design system that consists of a knowledge- based synthesis tool and a constraint-based layout generator has been developed to automate the design of key analog MOS circuit modules. An expert system has been developed to assist in an iterative analog design process. This integrated-circuit design expert system, which interfaces with a circuit simulator, is capable of optimizing circuit topologies as well as circuit element geometries to better satisfy a given set of performance specifications. The constraint-based layout generator uses analog circuit recognition and critical-net analysis techniques to identify crucial portions of an analog circuit and systematically derive proper layout constraints for analog circuit performance optimization. Constraint-driven floorplanning and routing techniques are developed to generate high-quality full-custom analog circuit layouts which incorporate the layout constraints. This layout tool is capable of quickly generating a correct and high-performance custom layout with a selectable aspect ratio for a wide variety of analog circuit modules. Extensions to higher-level subsystem layout synthesis using hierarchical floorplanning and module generation techniques are also described. Automatic layout generation techniques for single- and multi-layer neural networks have been developed. Experimental results on several CMOS Op-Amps, a voltage comparator, and a 16-neuron Hopfield neural network are described. These results indicate that this new analog circuit synthesis approach provides two advantages: it is quite general and yet effective, and can be used by system designers who are inexperienced in analog circuit design. Price: Domestic $29.00; International $42.50 USC-SIPI REPORT #190 "Bispectra for Sonar" by Jerry M. Mendel October 1991 The usefulness of polyspectra, and mixed moments of both integer and rational orders, in detecting and quantifying various kinds of frequency and phase couplings is studied. Both the deterministic and random cases are considered. Several interesting issues regarding frequency coupling in deterministic signals, and detection of phase coupling in the absence of frequency coupling are addressed. In particular, the problem of estimating rational phase-coupling in sonar signal processing is considered. One approach first estimates the frequencies, amplitudes and phases, and then performs a rational phase-coupling hypothesis test on whether the estimated phases bear the same ratios as their corresponding frequencies. Although high-resolution estimates of the frequencies can be obtained using the fourth-order cumulants, the estimated phase have to be "unwrapped" owing to the modulo-2¼ problem. It is not clear how this can be done. Hence, this approach for unraveling rational phase-coupling seems to be infeasible. Another approach using higher-order mixed moment functions and fractional moments is introduced and studied. It is shown that this approach can detect unconventional types of frequency and phase coupling. Price: Domestic $8.50; International $12.00 USC-SIPI REPORT #191 "Forward and Inverse Problem Studies For Electrocardiography Based on a Reconstructed Realistic Canine Model From CT-scan Sections" by Shan Gao and Chrysostomos L. Nikias October 1991 A realistic canine anatomy model with high resolution has been reconstructed from CT-scan sections by means of digital image signal processing technique. Based on this model, the forward transfer coefficient matrix ZMH has been computed using the surface integral method, and the inverse solutions in the presence of measurement noise on torso surface from the SVD method have been tested. For the consideration of clinical utility, the internal organs of canine were included and a set of real canine ECG signals were used in this study. Results from the forward problem using surface integral method and the inverse problem using regularization, SVD and recursive methods based on a homogeneous sphere model were also presented in this thesis. Price: Domestic $14.50; International $21.00 USC-SIPI REPORT #192 "Moving-Average-System Identification Using High-Order Spectra: A Simulation Comparison of Four Methods" by Wendy Huang and Jerry M. Mendel October 1991 Four methods of identification of nonminimum phase systems with finite impulse response are compared in this project. Via Monte Carlo simulation, the following four methods are compared: (1) GM+T method - Giannakis and Mendel (2) Bicepstrum method - Pan and Nikias (3) MU method - Matsuoka and Ulrych (4) RG method - Rangoussi and Giannakis Different zero locations, noise types, signal-to-noise ratios and data lengths, resulted in 48 cases. Zeros move-close to the unit circle with one located inside it and the other one located outside it. Additive noise is Gaussian, white or colored. Signals are non-Gaussian distributed. The simulation study suggests that estimation of the IT coefficients, the bicepstrum method is the preferred method. GM+T method shows very good stability at estimating the magnitude of IT coefficients. Both MU and RG methods are stable at estimating the phase of IR coefficients, but poor at estimating the magnitude. Price: Domestic $7.50; International $10.50 USC-SIPI REPORT #193 "Recovery of 3-D Motion from 3-D Density Images" by Samuel Moon-Ho Song December 1991 The motion of a deforming body is completely characterized by the velocity field (with initial position) generated by the motion. A method of computing the 3-D velocity field from 3-D cine CTs of a beating heart is proposed. Continuum theory provides two constraints on the velocity field generated by a deforming body. Assuming that (1) the image intensity is proportional to some conserved quantity and (2) the imaged medium is incompressible, the velocity field must satisfy the divergence-free constraint and the incompressibility constraint. Computation of the velocity field using these two constraints is an ill-posed problem which may be regularized using a smoothness term. We define a penalty function as a weighted sum of the two constraining terms and the smoothness term. Minimization of this function yields the desired velocity field. It is shown that, under certain conditions on the image, a unique minimizer of the penalty exists. Via variational calculus, it can be shown that the solution minimizing the penalty satisfies the Euler-Lagrange equations for this problem. The solution of the Euler-Lagrange equation is a set of coupled elliptic partial differential equations (PDEs). For numerical implementation, the PDEs obtained are discretized resulting in a system of linear equations A x = b where x is the solution velocity field. The matrix equation is solved using the conjugate gradient algorithm. Examples of experiments using simulated images and a cine CT of a beating heart are presented. The traditional regularization method does not provide a rigorous approach for obtaining the so-called regularization parameters. For this reason, we reformulate the problem as a constrained minimization. Here, instead of the regularization parameters, we require knowledge of the mean-squared errors of the constraints, which is physically and intuitively more appealing. A solution (and the numerical algorithm) is obtained by the dual space method. Price: Domestic $14.50; International $21.00 USC-SIPI REPORT #194 "VLSI Programmable Processor Design" by Bing J. Sheu and Min Chen January 1992 By combining the technologies of Complementary Pass-Transistor Logic (CPL) and CMOS Logic, the response time of the 32-bit carry lookahead adder can be reduced to 2.35 ns. At the same time, the constant height can be maintained under 200 l. Price: Domestic $32.00; International $46.75 USC-SIPI REPORT #195 "Cumulant-Based Blind Optimum Beamforming" by Mithat C. Dogan and Jerry M. Mendel January 1992 Sensor response, location uncertainty and use of sample statistics can severely degrade the performance of optimum beamformers. In this report, we propose blind estimation of the source steering vector in the presence of multiple, directional, correlated or coherent Gaussian interferers via higher-order-statistics. In this way, we employ the statistical characteristics of the desired signal to make the necessary discrimination, without any a-priori knowledge of array manifold and direction-of-arrival information about the desired signal. We then improve our method to utilize the data in a more efficient manner. In any application, only sample statistics are available, so we propose a robust beamforming approach that employs the steering vector estimate obtained by cumulant-based signal processing. We further propose a method that employs both covariance and cumulant information to combat finite sample effects. We analyze the effects of multipath propagation on the reception of the desired signal. We show that even in the presence of coherence, cumulant-based beamformer still behaves as the optimum beamformer that maximizes the Signal to Interference plus Noise Ratio (SINR). Finally, we propose an adaptive version of our algorithm. Simulations demonstrate the excellent performance of our approach in a wide variety of situations. Price: Domestic $7.50; International $10.50 USC-SIPI REPORT #196 "Cumulant-Based Adaptive Analysis of Speech Signals" by Mithat C. Dogan and Jerry M. Mendel January 1992 This report describes a speech processing method consisting of an adaptive predictor, a voicing decision (V/UV), and a pitch period estimator. The focus of this report is on robust detection of speech state and estimation of pitch period. This is accomplished by observing the behavior of an adaptive predictor which processes the speech signal. Higher-order-statistical analysis is proposed for discrimination of speech states. Comparing the energy of the original speech signal with that of the prediction-error residual yields the decision method. Both covariance and cumulant-based prediction methods are investigated and the latter is shown to be a more robust way of making (V/UV) decision. Pitch estimation is accomplished by using correlation-based approaches that operate on the energy estimate of the cumulant-based prediction residual rather than the original speech signal. Pitch estimation by our method yields better performance than currently existing batch procedures. Price: Domestic $4.50; International $6.00 USC-SIPI REPORT #197 "Shape Reconstruction From Photometric Stereo" by Kyoung Mu Lee and C.-C. Jay Kuo February 1992 Two new iterative algorithms for shape reconstruction based on multiple images taken under different lighting conditions known as photometric stereo are proposed. In our previous work, an iterative SFS (Shape From Shading) algorithm using a single image was developed by combining a triangular element surface model with a linearized reflectance map. It is shown in this research that all single-image SFS algorithms share an inherent problem, i.e. the accuracy of the reconstructed surface height is related to the slope of the reflectance map function defined on the gradient space. This observation motivates us to generalize the single-image SFS algorithm to two photometric stereo SFS algorithms aiming at more accurate surface reconstruction. The two algorithms directly determine the surface height by minimizing a quadratic cost functional, which is defined to be the squares of the brightness error obtained from each individual image in a parallel or cascade manner. The optimal illumination condition which leads to best shape reconstruction is also derived. Simulation results for several test images are given to demonstrate the performance of our new algorithms. Price: Domestic $5.00; International $6.75 USC-SIPI REPORT #198 "Texture Analysis and Classification with Tree-Structured Wavelet Transform" by Tianhorng Chang and C.-C. Jay Kuo February 1992 Although textures have been studied for more than thirty years, research on texture analysis is still active. The main difficulty of the problem is due to the lack of an adequate tool which characterizes different scales of textures effectively. Traditional methods based on the second-order statistics or the Gaussian Markov Random Field (GMRF) model share one common weakness. That is, they primarily focus on the coupling of pixels in a single scale. Recent developments in multiresolution analysis such as the Gabor and wavelet transforms help to overcome this difficulty. In this research, we propose a multiresolution approach based on a tree-structured wavelet transform for texture classification. The development of tree-structured wavelet transform is motivated by the observation that textures are quasi-periodic signals whose dominant frequencies are located in the middle frequency channels. With the transform, we are able to zoom into desired frequency channels and perform further decomposition. In contrast, the conventional wavelet transform only decomposes subsignals in low frequency channels. We also develop a progressive texture classification algorithm which is not only computationally attractive but also has excellent performance. Price: Domestic $4.50; International $6.00 USC-SIPI REPORT #199 "Hierarchical and Graph Theoretic Approaches to Image Segmentation and Pattern Classification" by Zhenyu Wu May 1992 This dissertation addresses the problems of image segmentation and pattern classification. Two new image segmentation schemes are proposed: hierarchical and graph theoretic. The later scheme is based on a novel graph theoretic approach to data clustering, also developed in this research work. These segmentation methods are applied to the problem of tissue classification of magnetic resonance (MR) images of the human brain. The hierarchical segmentation scheme uses an unsupervised, region based approach. The images under study are modeled as a mosaic of homogeneous subimages where the pixel intensities in each subimage are characterized by a homogeneous Gauss-Markov random field (GMRF) with unknown parameters. The segmentation seeks to group the pixels into regions which, under a suitable hypothesis, are homogeneous. An analysis of homogeneity testing for GMRFs is presented and two tests are proposed: the hierarchical likelihood ratio test and the dispersion test. Based on the homogeneity tests a hierarchical segmentation approach is suggested. The image is represented by a quadtree, and a split and merge procedure is applied to find large homogeneous regions within the image. This is followed by a segmentation refinement step involving connected component labeling and region growing, in which most of the unclassified pixels will be attached to the neighboring regions to which they are most similar. The idea here is to allow the algorithm to learn about the image by first clustering the `easy' pixels while delaying decisions on the `hard' pixels until more information has been gathered. Finally, a clustering procedure, either a constrained maximum likelihood agglomerative approach or a graph theoretic approach, is used to reduce the number of segmented regions. One difficulty encountered in implementing the algorithm is evaluating the likelihood for irregularly shaped regions when the GMRF model is used. A new highly accurate approximation for the determinant of the covariance matrix based on eigenanalysis is proposed to overcome this problem. This hierarchical scheme may be applied to segment either textured or non-textured images. A novel graph theoretic approach for data clustering is developed using network flow theory. The data to be clustered are represented by an undirected adjacency graph G with arc capacities assigned to reflect the similarity between the linked vertices. Clustering is achieved by removing arcs of selected minimum cuts in G to form mutually exclusive subgraphs such that the largest inter-subgraph maximum flow is minimized. For graphs of moderate size ~ 1000 vertices), the optimal solution is obtained through partitioning a flow and cut equivalent tree of G, which can be efficiently constructed using the Gomory-Hu algorithm. However for larger graphs this approach is impractical. New theorems for subgraph condensation are derived and are then used to develop a fast algorithm which hierarchically constructs and partitions a partially equivalent tree of much reduced size. This algorithm results in an optimal solution equivalent to that obtained by partitioning the complete equivalent tree and is able to handle very large graphs with several hundred thousand vertices. Using this clustering algorithm, an edge based image segmentation is developed. Each pixel of the image corresponds to a vertex of an undirected graph G and the segmentation is achieved by effectively searching for closed contours of edge elements (equivalent to minimum cuts in G), which consist mostly of strong edges, while rejecting contours containing isolated strong edges. This method is able to accurately locate region boundaries and at the same time guarantees the formation of closed edge contours. Price: Domestic $15.00; International $21.75 35