Two important issues of shape from contour research are addressed in this paper. The first is the imperfection of input data and the second is the completeness of output 3D object models. We present a solution that is based on: (1) the analysis of imperfect line drawing configurations, especially the properties of L junctions and (2) the implementation of a rule based system. Constraints imposed by line labeling, 2D and 3D geometry, and Gestalt principles of human visual perception are formulated into production rules, and the system control mechanism is designed so that these rules can work interactively. Perfect line drawings are treated as special cases in this system. Complete 3D object models, including invisible faces, that are consistent with human perception can be reconstructed. A nonmonotonic forward reasoning mechanism is realized by using the truth maintenance system (TMS). The TMS is used to maintain a dependency network of currently active facts for reasoning in hypothetical situations. It also leads to an effective way to backtrack an assumption to resolve contradictions which is called dependency directed backtracking (DDB).

Localizing boundaries between textured image regions without sacrificing the labeling accuracy of interior regions remains a problem in segmentation. Difficulties arise because of the conflicting requirements of localization and labeling. Boundary localization usually demands observing the features over small neighborhoods, whereas labeling accuracy increases with the size of the observation neighborhood. This problem is further exacerbated in texture segmentation by the spatially distributed nature of texture features. In this correspondence, we develop a multiresolution approach that combines localized and distributed features to directly address boundary localization in texture segmentation. Maximum localization is achieved by using the gray-level discontinuities at the boundary between textures to define the boundary. The properties that characterize the gray-level discontinuity at texture boundaries are developed and an algorithm is designed to localize the boundary using these discontinuities. This segmentation algorithm is implemented and successfully tested on a set of Brodatz texture mosaics and AVHRR satellite imagery.

Quantitative autoradiography is a powerful radioisotopic-imaging method for neuroscientists to study local cerebral blood flow and glucose-metabolic rate at rest, in response to physiologic activation of the visual, auditory, somatosensory, and motor systems, and in pathologic conditions. Most autoradiographic studies analyze glucose utilization and blood flow in two-dimensional (2D) coronal sections. With modern digital computer and image-processing techniques, a large number of closely spaced coronal sections can be stacked appropriately to form a three-dimensional (3D) image. 3D autoradiography allows investigators to observe cerebral sections and surfaces from any viewing angle. A fundamental problem in 3D reconstruction is the alignment (registration) of the coronal sections. A new alignment method based on disparity analysis is presented, which can overcome many of the difficulties encountered by previous methods. The disparity analysis method can deal with asymmetric, damaged, or tilted coronal sections under the same general framework, and it can be used to match coronal sections of different sizes and shapes. Experimental results on alignment and 3D reconstruction are presented.

A solution to the labeling of the drawings using a neural network approach is presented. Line-labeling constraints are designed into a modified Hopfield networks. The design of the energy function and the updating equation is described. The energy function includes higher order terms than in the usual quadratic Hopfield model to accommodate the higher-order interactions required by the labeling constraints. The physical model is modified accordingly. An additional layer of neurons is used to synthesize a realizable circuit. The resulting network combines the standard Hopfield-network neurons with neurons performing two- and three-way Boolean AND operations. Simulation of network behavior for various trihedral scenes produced successful results.>

The authors introduce a texture segmentation algorithm that combines texture information at a low resolution level and local edge information at a high resolution to obtain an accurate segmentation. An entropy-based criterion for determining an optimum segmentation scale is proposed. A set of features consistent with the scaling model is described. It is used with a neural network to perform a low-resolution segmentation. Also described is a procedure for resolving the ambiguity in the boundary location resulting from the low-resolution segmentation process. This procedure makes use of a set of morphological filters and edges extracted at a higher resolution. The utility and accuracy of the method are demonstrated with a relatively complex example. The major limitation of the method is that the training time of the neural network classifier increases with the number of nodes in the network.>

A parallel tree search procedure and multilevel array architectures are presented for scene labeling problems. In the scene labeling problem, when the number of variables is not large, e.g. less than 100, its solutions and search space are not expected to greatly increase with problem size. The multilevel arrays only use a polynomial number of processors at each level and a bus or mesh connection for interlevel communication. This approach is very efficient compared to the binary-tree machine if the number of nodes in the search tree of labeling problem increases polynomially with the number of variables. Because of its regular structure, the multilevel array is particularly suitable for VLSI implementation.>

VLSI computing arrays for matrix multiplication and covariance matrix inversion have applications in many fields. Under the constraint of limited I/O bandwidth of the host system or the computing array, three configurations for the interfacing and controlling of a multiplication array to achieve optimal performance under different adverse situations are examined. The three configurations are multiplexing loading, processor row loading, and processor column group loading. A properly chosen configuration can significantly reduce the computing time of the multiplication array.

A mathematical model using an operator formulation for a moving object in a sequence of images is presented. Time-varying translation and rotation operators are derived to describe the motion. A variational estimation algorithm is developed to track the dynamic parameters of the operators. The occlusion problem is alleviated by using a predictive Kalman filter to keep the tracking on course during severe occlusion. The tracking algorithm (variational estimation in conjunction with Kalman filter) is implemented to track moving objects with occasional occlusion in computer-simulated binary images.

Binary random variables are regarded as random vectors in a binary-field (modulo-2) linear vector space. A characteristic function is defined and related results derived using this formulation. Minimax estimation of probability distributions using an entropy criterion is investigated, which leads to an A-distribution and bilinear discriminant functions. Nonparametric classification approaches using Hamming distances and their asymptotic properties are discussed. Experimental results are presented.

The paper is concerned with the reduction of overhead storage, i.e., the stored compression/decompression (C/D) table, in field-level data file compression. A large C/D table can occupy a lage fraction of maim memory space during compression and decompression, and may cause excessve page swapping in virtual memory systems. A two-stage approach is studied, including the reuired additional C/D table decompression time. It appears that the approach has limitations and is not completely satisfactory.

For the compression of data fields in the records of a data file, the fixed-length minimum bit (FLMB) method is commonly used. The scheme re quires a compression/decompression (C/D) table which could be very large in size. A large C/D table can occupy a large fraction of the main memory space, and it may cause excessive page swaping in virtual memory systems. To reduce the C/D table overhead storage, a two-stage data compression approach is studied in which several methods are used to further compress the C/D table itself. The resulting C/D table decompression time during the regular data decompression process is also examined.

A nonsingular linear transformation of binary-valued random vectorsy = xAwhich minimizes a mutual information criterion I(y) is considered. It is shown that a nonsingular A exists such thatI(y) = 0if and only ifxhas a generalized binomial distribution. Computational algorithms for seeking an optimalAare developed, and dimensionality reduction is discussed briefly. This linear transformation is useful in improving the approximation of probability distributions. Numerical examples are presented.

Stochastic approximation is applied to the design of a frequency-shift-keying (FSK) feedback scheme. FSK signals are transmitted over a channel with additive white Gaussian noise (AWGN) and the frequency estimate is fed back to the transmitter. A signaling scheme similar to the Schalkwijk-Kailath amplitude-shift-keying (ASK) scheme is derived and performance curves are presented. The scheme performs much better than ASK or FSK without feedback; however, under the average-power limitation, its performance is, in general, inferior to that of ASK feedback schemes.

A decision-directed scheme for estimating the mean is expressed as a stochastic approximation algorithm. The algorithm is shown to converge, but not to the true value, by means of the theory of stochastic approximation. A modification of the algorithm that converges to the true value is presented.

This correspondence is concerned with a stochastic approximation algorithm having a nonstationary regression function. Convergence conditions and a mean-square error bound are presented. Its possible application to feedback communication is discussed briefly.

This paper introduces the concepts of capacity and reliability of a linear feature extractor. The relationship between the capacity introduced here and the channel capacity in information theory is discussed in some detail. The reliability is associated with the least favorable distributions and gives us a measure of the effectiveness for the worst possible case. It is of particular importance in pattern recognition problems because we have no control over the distributions of the patterns. It is shown that for the family of probability distributions with covariance matrix S, the most reliable (i.e., minimax) feature extractor is the Karhunan-Loève expansion. The concept of reliability is extended to the two-class pattern recognition problem and is discussed in terms of the Bhattacharyya distance.

This correspondence is concerned with the estimation and resolution of overlapping random signals in additive noise. Two resolution schemes are presented; one is optimal and the other has computational advantages. It is shown that the overlapping signals are not resolvable if the eigenfunctions constitute a complete basis.

This paper is concerned with stochastic-approximation algorithms for estimating signal parameters. Emphasis will be on the performance of the algorithm for a finite number of observations as opposed to the asymptotic convergence rate. We use as an upper bound a result due to Dvoretzky. A lower bound on the average mean-square error is derived. This new bound is based on the Cramér-Rao inequality. The conventional Cramér-Rao bound is not directly applicable, because it requires the knowledge of the bias function, which is difficult to find in a recursive estimation scheme. To avoid this difficulty, we introduce the concept of most favorable bias function and use the calculus of variations to derive the lower bound. The new bound also serves as a standard to judge the merits of the stochastic-estimation algorithm, since under some general conditions no estimate can yield smaller error. It is shown that under some conditions the two bounds are nearly equal, and hence the algorithm is near optimal. The asymptotic efficiency of the algorithm is compared with Sakrison's result. A stochastic-estimation algorithm is derived for estimating Doppler frequency, and performance curves in terms of the error bounds are presented.

A stochastic approximation algorithm is developed for estimating a mixture of normal density functions with unknown means and unknown variances. The algorithm minimizes an information criterion that has interesting properties for density approximations. The conditions on the convergence of this nonlinear estimation algorithm are discussed, and a numerical example is presented.

This paper presents a method for resolving signals closely spaced in parameter space in the sense that the parameters of the signals being measured (i.e., time of arrival, frequency, etc.) are close together. A maximum-likelihood method is used to resolveMsignals inK-dimensional space, whereMmay be unknown. The resulting procedure first generates aK-dimensional cross-ambiguity function and then passes this function through aK-dimensional linear filter. The procedure effectively reduces the problem from its original form of optimally searching for a maximum in the(M \times K)-dimensional space to searching forMmaxima in theK-dimensional parameter space. The method is obviously sub-optimal; its advantage lies in the relatively simple form of the detection scheme.

This paper discusses a set of polynomials, {φ r ( s )}, orthogonal over a discrete range, with binomial distribution, b ( s ; n , p ), as the weighting function. Two recurrence relations are derived. One expresses φ r in terms of φ r -1 and Δφ r -1 , while the other relates φ r with φ r -1 and φ r -2 . It is shown that these polynomials are solutions of a finite difference equation. Also considered are two special cases. The first is the set of Hermite polynomials derived as a limiting case of the binomial-weighted orthogonal polynomials. The second deals with the Poisson distribution used as the weighting function.