Summary form only given. The increased information content of hyperspectral imagery over multispectral data has attracted significant interest from the defense and remote sensing communities. We develop a mechanism for compressing hyperspectral imagery with no loss of information. The challenge of hyperspectral image compression lies in the non-isotropy and non-stationarity that is displayed across the spectral channels. Short-range dependence is exhibited over the spatial axes due to the finite extent of objects/texture on the imaged area, while long-range dependence is shown by the spectral axis due to the spectral response of the imaged pixel and transmission medium. A secondary, though critical, challenge is one of speed. In order to be of practical interest, a good solution must be able to scale up to speeds of the order of 20 MByte/s. We use an integerizable eigendecomposition along the spectral channel to optimally extract spectral redundancies. Subsequently, we apply wavelet-based encoding to transmit the residuals of eigendecomposition. We use contextual arithmetic encoding implemented with several innovations that guarantee speed and performance. Our implementation attains operating speeds of 550 kBytes of raw imagery per second, and achieves a compression ratio of around 2.7:1 on typical AVIRIS data. This demonstrates the utility and applicability of our algorithm towards realizing a deployable hyperspectral image compression system.

Different ways of representing probabilistic relationships among the attributes of a domain ar examined, and it is shown that the nature of domain relationships used in a representation affects the types of reasoning objectives that can be achieved. Two well-known formalisms for representing the probabilistic among attributes of a domain. These are the dependence tree formalism presented by C.K. Chow and C.N. Liu (1968) and the Bayesian networks methodology presented by J. Pearl (1986). An example is used to illustrate the nature of the relationships and the difference in the types of reasoning performed by these two representations. An abductive type of reasoning objective that requires use of the known qualitative relationships of the domain is demonstrated. A suitable way to represent such qualitative relationships along with the probabilistic knowledge is given, and how an explanation for a set of observed events may be constituted is discussed. An algorithm for learning the qualitative relationships from empirical data using an algorithm based on the minimization of conditional entropy is presented.>

Relative motion between a camera and the objects generates a time-varying optical array of changing intensities. Several algorithms have been proposed in the recent past to compute image motion from an image sequence. The primary difficulty with these approaches is that in the presence of multiple objects crossing each other in a scene, the accuracy of velocity estimates computed by these algorithms at locations near the boundaries of the objects is far from satisfactory. The authors present a robust technique to overcome this difficulty which preserves discontinuities in image motion across boundaries in a graceful manner. One of the major advantages of this algorithm is its ability to precisely detect points of discontinuity in image velocity.>

A knapsack packing neural network of 4n units with both low-order and conjunctive asymmetric synapses is derived from a non-Hamiltonian energy function. Parallel simulations of randomly generated problems of size n in {5, 10, 20} are used to compare network solutions with those of simple greedy fast parallel enumerative algorithms.

A prior probability estimator, a candidate for asymptotic efficiency, from within the class of recursive estimators proposed by the authors (1990) is synthesized. The authors prove asymptotic efficiency and convergence with probability one by involving a stochastic approximation theorem. The estimator can be implemented in practice for continuous, discrete, and mixed class conditional density functions, although continuous and mixed densities generally require repeated evaluation of expectations of certain functions through numerical techniques. Results of a simulation. experiment with discrete densities are included. Variations of the estimator, for computational simplicity, are discussed.>

Hopfield-type thermodynamic networks composed of functionally homogeneous visible units have been applied to a variety of structurally simple NP-hard optimization problems. A fundamental obstacle to the application of neural networks to difficult problems is that these problems must first be reduced to 0-1 Hamiltonian minimization problems. It has been shown that certain optimization problems cannot be embedded in networks composed entirely of visible units. A method for defining necessary hidden units together with their best features is presented. A knapsack-packing network ofO(n) units with standard and conjunctive synapses is derived, and simulation results are presented

The problem of estimating prior probabilities in a mixture of M classes with known class conditional distributions is studied. The observation is a sequence of n independent, identically distributed mixture random variables. The first moments of appropriately formulated functions of observations are used to facilitate estimation. The complexity of these functions may vary from linear functions of the observations (in some cases) to complex functions of class conditional density functions of observations, depending on the desired balance between computational simplicity and theoretical properties. A closed-form, recursive, unbiased, convergent estimator using the density function is presented: the result is valid for any problem in which prior probabilities are identifiable. Discrete and mixed densities require a minor modification. Three application examples are described. The class conditional expectations of density functions, required for the initialization of the estimator algorithm, are analytically evaluated for Gaussian and exponential densities.>

An edge model is developed along with the associated edge detection and contour determination algorithms. An edge point along any scan direction is defined as a sufficient jump in the mean of a time series that is assumed to be white Gaussian around the edge point with the same variance on either side. An edge contour is defined as a sequence of such edge points, each point denoted by the two coordinates of the image plane. Each coordinate sequence is modeled as first-order autoregressive Gaussian over and above a straight line sequence of arbitrary, finite slope and intercept. The first stage of the overall algorithm examines the time series along each row and each column, forms a window around each potential edge point, detects the location and estimates the variance of the error in the location of the edge point, by pattern recognition techniques. The second stage forms noisy edge contours by graph searching techniques. The third stage is smoothing of an edge contour, formulated as a well-defined Kalman smoothing problem. It is shown that the parameters of the system and noise can all be estimated from the data itself. Experimental results on a simple image are discussed.>

A new scheduling problem, which is called the insert-idle-time scheduling problem, is proposed which concerns scheduling N jobs on one machine when some of the machine time is unschedulable due to pre-scheduled maintenance time, lunch time or the time devoted to the jobs with higher priority or any other activities. An best-first branch-and-bound algorithm which takes “schedule improvement” approach is presented and the experimental results are reported.

Develops an edge model in images and the associated edge detection and contour determination algorithms based on statistical signal processing approaches. An edge point along any scan direction is defined as a sufficient jump in the mean of a time series which is assumed to be white Gaussian around the edge point with the same variance on either side. An edge contour is defined as a sequence of such edge points, each point denoted by the two coordinates of the image plane. Each coordinate sequence is modeled as first order auto regressive Gaussian over and above a straight line sequence of arbitrary, finite slope and intercept. The first stage of our overall algorithm examines the time series along each row and each column, forms a window around each potential edge point, detects the location and estimates the variance of the error in the location of the edge point, by pattern recognition techniques. The second stage forms noisy edge contours by graph searching techniques. The third stage smoothing of an edge contour is formulated as a well defined Kalman smoothing problem. It is shown that the parameters of the system and noise can all be estimated from the data itself. Experimental results on a simple image are discussed.>

We discuss some points on which we agree, and others on which we disagree, with Cheeseman's target article. Particular agreements include the need for an eclectic approach; disagreements include the misleading distinction between probabilistic and logical reasoning regarding the notion of truth, and also some matters of nonmonotonicity.

Pattern recognition with unknown costs of classification is formulated as a problem of adaptively learning the optimal scheme starting from an ad hoc decision scheme. It is shown that unsupervised learning is adequate to compute converging estimates of the mean values of the MN random classification costs, one for each combination of M classes and N decisions. The quantities required for estimation are 1) the decision taken, 2) the outcome of the cost random variable corresponding to the unknown class and the implemented decision, and 3) the a posteriori probabilities of all the classes. Some of the variations of the above learning scheme are discussed. An application of the proposed methodology for adaptively improving the performance of pattern-recognition trees is presented along with simulation results.

This paper briefly describes IRRIS-100TM, a machine vision system shown in operation at four recent exhibitions sponsored by the Society for Manufacturing Engineers. A gray level vision system combining Artificial Intelligence methods with statistical and structural pattern recognition techniques, IRRIS-100TMcan rapidly determine the location and orientation of touching and overlapping objects that are randomly positioned within the camera's field of view, without special lighting, and without having to find connected components in the image. With the gray level image registered in a standard orientation in memory, customized algorithms can examine specific details in the image. Based on a Motorola 68000 processor, the system communicates location and orientation coordinates and other information for pick and place, de-palletizing, assembly, recognition, and inspection applications, over two RS232 ports and one 16 bit parallel port.

This paper discusses two general schemes for performing branch-and-bound (B&B) search in parallel. These schemes are applicable in principle to most of the problems which can be solved by B&B. The schemes are implemented for SSS*, a versatile algorithm having applications in game tree search, structural pattern analysis, and AND/OR graph search. The performance of parallel SSS* is studied in the context of AND/OR tree and game tree search. The paper concludes with comments on potential applications of these parallel implementations of SSS* in structural pattern analysis and game playing.

This paper shows how the nondirectional structural analysis of pattern data can be performed by matching a problem reduction representation (PRR) of pattern structure with sample data, using a best-first state space search algorithm called SSS*. The end result of the matching algorithm is a tree whose nodes represent recognized structures in the data. Tip nodes of the tree structure correspond to primitives which are recognized in the raw data by curve fitting routines. The operators of the algorithm allow the tree to be constructed with a combination of top-down or bottom-up steps. The matching of the structure tree to waveform segments need not be done in a left-right sequence. Moreover ambiguous matches are pursued in a best first order by using state space search with partial parse trees as states. A software system called WAPSYS (for waveform parsing system) is described, which implements this structural analysis paradigm. Experience using WAPSYS to analyze carotid pulse waves is also discussed.

Noting the major limitations of multivariate statistical classification and syntactic pattern recognition models, this paper presents an overview of some recent work using alternate representations for multistage and nearest neighbor multiclass classification, and for structural analysis and feature extraction. These alternate representations are based on generalizations of state-space and AND/OR graph models and search strategies developed in artificial intelligence (AI). The paper also briefly touches on other current interactions and differences between artificial intelligence and pattern recognition.

On most real channels hybrid error control schemes are expected to provide a throughput higher than that of automatic repeatrequest (ARQ) systems and a reliability better than forward error correction (FEC) systems. On compound channels, channels with a mixture of random and burst errors, generalized burst-trapping (GBT) codes seem to be quite effective for FEC. In this paper, a hybrid scheme with Go BackNARQ as the retransmission component and GBT code as the FEC component, is described. Its performance is analyzed in terms of throughput efficiency and undetected error probability and is compared with that of a forward-acting GBT code. Numerical calculations of the parameters are presented to illustrate the performance.

Tight upper and lower bounds on the average probability of error are obtained for the nonlinear optimum sequential detector with zero look ahead. A linear upper bound is obtained that is very tight over a wide range of signal-to-noise ratios and a wide range of values of the intersymbol interference. The structure of the linear detector whose performance is given by the linear bound is determined and shown to take the form of a semi-infinite transversal equalizer. The tap values of the equalizer are related to the channel impulse response and the performance of realizable truncated equalizers is obtained in the form of the average probability of error versus equalizer length.

This paper selectively surveys contributions to major topics in pattern recognition since 1968. Representative books and surveys pattern recognition published during this period are listed. Theoretical models for automatic pattern recognition are contrasted with practical,, design methodology. Research contributions to statistical and structural pattern recognition are selectively discussed, including contributions to error estimation and the experimental design of pattern classifiers. The survey concludes with a representative set of applications of pattern recognition technology.

We present a new descriptive statistic for channels with memory and show its utility a) in evaluating and comparing existing models for such channels and b) as a theoretical tool in defining the error-gap distribution characteristics of real channels. We demonstrate that certain kinds of real channel behavior cannot be adequately described by previously proposed models and offer an example of a better model that includes many of the earlier models as special cases.

In various pattern-recognition problems such as classification of photographic data, preprocessing operations result in a two-dimensional array of binary random variables. An optimal recipe for classifying such patterns is described. It combines the use of an orthonormal expansion for the logarithm of probability functions, with the generation of a joint probability distribution from lower-order marginals. The unwieldy nature of the optimal recipe leads to the consideration of dependence represented by a Markov chain and a two-dimensional analog called a Markov mesh. The Markov chain has a "reflecting" property in that therth order nonstationary chain implies that a point depends on itsrnearest neighbors on each side. By scanning along a grid-filling curve so that the2rneighbors of a point are geometrically close to it, certain spatial dependencies are obtained. The grid-filling curves are sequences of functions which have Hilbert "space-filling" curves as their limit. This simple approach does not provide for many of the spatial dependencies that should be considered. A novel extension of Markov chain methods into two dimensions leads to the Markov mesh which economically takes care of a much larger class of spatial dependencies. Likelihood ratio classification based on Markov chain and Markov mesh assumptions requires the estimation of a much smaller number of parameters than the general case. The development presented in this paper is new and need not be restricted to binary variables.