In order to manage the growing amount of video information efficiently, a video scene change detection method is necessary. Many advanced video applications such as video on demand (VOD) and digital library also require the scene change detection to organize the video content. In this paper, we present an effective scene change detection method using an unsupervised segmentation algorithm and the technique of object tracking based on the results of the segmentation. Our results have shown that this method can perform not only accurate scene change detection, but also obtain object level information of the video frames, which is very useful for video content indexing and analysis. 1.

As more information sources become available in multimedia systems, the development of abstract semantic models for video, audio, text, and image data is becoming very important. An abstract semantic model has two requirements: it should be rich enough to provide a friendly interface of multimedia presentation synchronization schedules to the users and it should be a good programming data structure for implementation in order to control multimedia playback. An abstract semantic model based on an augmented transition network (ATN) is presented. The inputs for ATNs are modeled by multimedia input strings. Multimedia input strings provide an efficient means for iconic indexing of the temporal/spatial relations of media streams and semantic objects. An ATN and its subnetworks are used to represent the appearing sequence of media streams and semantic objects. The arc label is a substring of a multimedia input string. In this design, a presentation is driven by a multimedia input string. Each subnetwork has its own multimedia input string. Database queries relative to text, image, and video can be answered via substring matching at subnetworks. Multimedia browsing allows users the flexibility to select any part of the presentation they prefer to see. This means that the ATN and its subnetworks can be included in multimedia database systems which are controlled by a database management system (DBMS). User interactions and loops are also provided in an ATN. Therefore, ATNs provide three major capabilities: multimedia presentations, temporal/spatial multimedia database searching, and multimedia browsing.

S.C. Chen et al. (1999) proposed a multimedia augmented transition network (ATN) model, together with its multimedia input strings, to model and structure video data. This multimedia ATN model was based on an ATN model that had been used within the artificial intelligence (AI) arena for natural-language understanding systems, and its inputs were modeled by multimedia input strings. The temporal and spatial relations of semantic objects were captured by an unsupervised video segmentation method called the SPCPE (simultaneous partitioning and class parameter estimation) algorithm, and they were modeled by the multimedia input strings. However, the segmentation method used was not able to identify objects that are overlapped together within video frames. The identification of overlapped objects is a great challenge. For this purpose, a backtrack-chain-update-split algorithm is developed in this paper that identifies the split segment (object) and uses this information in the current frame to update the previous frames in a backtrack-chain manner. The proposed split algorithm provides more accurate temporal and spatial information of the semantic objects for video indexing.

With the rapid proliferation of multimedia applications that require video data management, it is becoming more desirable to provide proper video data indexing techniques capable of representing the rich semantics in video data. In real-time applications, the need for efficient query processing is another reason for the use of such techniques. We present models that use the object motion information in order to characterize the events to allow subsequent retrieval. Algorithms for different spatiotemporal search cases in terms of spatial and temporal translation and scale invariance have been developed using various signal and image processing techniques. We have developed a prototype video search engine, PICTURESQUE (pictorial information and content transformation unified retrieval engine for spatiotemporal queries) to verify the proposed methods. Development of such technology will enable true multimedia search engines that will enable indexing and searching of the digital video data based on its true content.

Association rule mining has recently attracted strong attention and proven to be a highly successful technique for extracting useful information from very large databases. In this paper, we explore a generalized affinity-based association mining which discovers quasi-equivalent media objects in a distributed information-providing environment consisting of a network of heterogeneous databases which could be relational databases, hierarchical databases, object-oriented databases, multimedia databases, etc. Online databases, consisting of millions of media objects, have been used in business management, government administration, scientific and engineering data management, and many other applications owing to the recent advances in high-speed communication networks and large-capacity storage devices. Because of the navigational characteristic, queries in such an information-providing environment tend to traverse equivalent media objects residing in different databases for the related data records. As the number of databases increases, query processing efficiency depends heavily on the capability to discover the equivalence relationships of the media objects from the network of databases. Theoretical terms along with an empirical study of real databases are presented.

We have given a solution to the problem of unsupervised classification of multidimensional data. Our approach is based on Bayesian estimation which regards the number of classes, the data partition and the parameter vectors that describe the density of classes as unknowns. We compute their MAP estimates simultaneously by maximizing their joint posterior probability density given the data. The concept of partition as a variable to be estimated is a unique feature of our method. This formulation also solves the problem of validating clusters obtained from various methods. Our method can also incorporate any additional information about a class while assigning its probability density. It can also utilize any available training samples that arise from different classes. We provide a descent algorithm that starts with an arbitrary partition of the data and iteratively computes the MAP estimates. The proposed method is applied to target tracking data. The results obtained demonstrate the power of the Bayesian approach for unsupervised classification.

We present a solution to the problem of intensity image segmentation using Bayesian estimation in a multiscale set up. Our approach regards the number of regions, the data partition and the parameter vectors that describe the probability densities of the regions as unknowns. We compute their MAP estimates jointly by maximizing their joint posterior probability density given the data. Since the estimation of the number of regions is also included into the Bayesian formulation we have a fully automatic or unsupervised method of segmenting images. An important aspect of our formulation is to consider the data partition as a variable to be estimated. We provide a descent algorithm that starts with an arbitrary initial segmentation of the image when the number of regions is known and iteratively computes the MAP estimates of the data partition and the associated parameter vectors of the probability densities. Our method can incorporate any additional information about a region while assigning its probability density. It can also utilize any available training samples that arise from different regions.

In an interactive multimedia information system, users should have the flexibility to browse and choose various scenarios they want to see. This means that two-way communications should be captured by the conceptual model. Digital video has gained increasing popularity in many multimedia applications. Instead of sequential access to the video contents, the structuring and modeling of video data so that users can quickly and easily browse and retrieve interesting materials has become an important issue in designing multimedia information systems. An abstract semantic model called the augmented transition network (ATN), which can model video data and user interactions, is proposed in this paper. An ATN and its subnetworks can model video data based on different granularities, such as scenes, shots and key frames. Multimedia input strings are used as inputs for ATNs. The details of how to use multimedia input strings to model video data are also discussed. Key frame selection is based on the temporal and spatial relations of semantic objects in each shot. These relations are captured from our proposed unsupervised video segmentation method, which considers the problem of partitioning each frame as a joint estimation of the partition and class parameter variables. Unlike existing semantic models, which only model multimedia presentation, multimedia database searching or browsing, ATNs together with multimedia input strings can model these three in one framework.

In this paper a novel algorithm for adaptive signal expansion is presented. Here the main concern is to efficiently represent the natural images and audio signals. These signals are one or two dimensional signals with unknown or time-varying characteristics. For this type of signal, linear expansion with a fixed set of basis functions is not flexible enough to represent the data with the desired degree of sparseness. We introduce a new algorithm called segmented orthogonal matching pursuit (SOMP). Our experimental results show that the SOMP algorithm is more suitable than the existing signal expansion algorithms for efficient representation of audio and visual information.

In this paper, a novel algorithm for low bit-rate image compression is presented. In this technique, we use a new image representation algorithm called segmented orthogonal matching pursuit (SOMP) (Rabiee and Kashyap, 1998) to encode the subbands of an image. Our preliminary results show that our algorithm performs better than the segmentation based matching pursuit (QTMP) (Rabiee et al. 1996) and EZW (Shapiro 1993) encoders at lower bit rates, based on subjective image quality and peak signal-to-noise ratio (PSNR).

We consider recursive estimation of images modeled by non-Gaussian autoregressive (AR) models and corrupted by spatially white Gaussian noise. The goal is to find a recursive algorithm to compute a near minimum mean square error (MMSE) estimate of each pixel of the scene using a fixed lookahead of D rows and D columns of the observations. Our method is based on a simple approximation that makes possible the development of a useful suboptimal nonlinear estimator. The algorithm is first developed for a non-Gaussian AR time-series and then generalized to two dimensions. In the process, we draw on the well-known reduced update Kalman filter (KF) technique of Woods and Radewan to circumvent computational load problems. Several examples demonstrate the non-Gaussian nature of residuals for AR image models and that our algorithm compares favorably with the Kalman filtering techniques in such cases.

In our previous work, we introduced a new class of nonstationary stochastic processes whose spectral representation is associated with the wavelet transforms and established a mathematical framework for the analysis of such processes. We refer to these processes as affine stationary processes. These processes are indexed by the affine group, or ax+b group, which can be thought of as a group of shifts and scalings. Affine stationary processes are nonstationary in the classical sense. However, their second order statistical properties are invariant under the affine group composition law. We show that any physically realizable affine stationary process is a wavelet transform of the white noise process. As a result, we derive a spectral decomposition of the affine stationary processes using wavelet transform. Additionally, we apply the results to the fractional Brownian motion (fBm). We show that fBm is an affine stationary process and the filter associated with the fBm is a continuous time analyzing wavelet. Finally, we apply our results to choose an optimal wavelet filter in the development of a spectral representation of fBm via wavelet transforms.

A novel approach for de-blocking of block based image and video compression algorithms is presented. In our algorithm a blocky image is first decomposed into approximation and detail subspaces with a J-level multiresolution analysis (MRA). In the next step, the low-pass approximation image and the high-pass detail images are processed independently with spatially adaptive order statistic (OS) filters. The proposed algorithm can effectively eliminate or reduce the blocking artifacts and is computationally efficient.

We define a data structure called a "web" together with an algorithm to choose scale-space atoms for representing an image. The corresponding wavelet coefficients (of the atoms chosen using this method) have useful properties which lead to (i) the definition of a stochastic process for representing images and (ii) an efficient image compression algorithm. The advantage of our image compression algorithm is that the computational requirement is very low. The stochastic process is useful in a theoretical sense because it gives us a framework in which to understand images and certain image compression algorithms.

This paper presents two multiresolution segmentation-based algorithms for low bit rate image compression using hierarchical data structures. The segmentation is achieved with quadtree and binary space partitioning tree hierarchical data structures and the encoding is performed by using the projection pursuit (matching pursuit) with a finite dictionary of spline functions with various degrees of smoothness. Comparison with JPEG at rates below 0.5 bit/pixel shows superior performance both in terms of peak signal-to-noise ratio (PSNR) and subjective image quality.

In our previous work, we proposed two classes of self-similar models for 1/f processes which we referred to as scale stationary and p-self similar models. We introduced a new mathematical framework and several new concepts, such as periodicity, autocorrelation, and spectral density function to analyze scale stationary and p-self similar processes. In particular, we introduced a family of finite parameter scale stationary models, similar in spirit to ARMA models by which any scale stationary processes can be approximated. In this work, we utilized the framework of scale stationary processes and introduced novel methods of 1/f signal modeling and parameter estimation techniques. These include a sampling theorem, a mathematically consistent estimator for the self-similarity parameter, an unbiased estimator for the scale autocorrelation function and a maximum likelihood estimator for scale stationary autoregressive models. Results from our study suggest that scale stationary processes provide a powerful framework for practical 1/f signal processing problems.

There has been a growing interest in representation and compression of signals by using dictionaries of basis functions other than the traditional dictionary of sinusoids. These new set of dictionaries include cosine packets, chirplets, Gabor functions, wavelets, and wavelet packets. In this paper matching pursuit and basis pursuit with finite dictionaries of convolutional splines are used for adaptive multiresolution image compression. At the cost of computational complexity these algorithms outperform the DCT based JPEG both in terms of PSNR and subjective image quality at lower bit rates.

A novel approach for error concealment in block-based image and video coding systems over the ATM networks is presented. This new approach aims at reconstructing the lost pixels in the intra-coded frames by spatial interpolation of the nearest undamaged pixels with a recursive multi-directional nonlinear filtering scheme. The lost interframe information are also reconstructed by using robust nonlinear filtering of the adjacent and previous motion vector blocks. We assume that the important synchronization and header information of the compressed bit streams are packed into high priority ATM cells and an integral number of macroblocks are packed into normal cells for efficient transmission. Finally, simulation results are provided to illustrate the effectiveness of the proposed method.

In speech and image processing, many good algorithms do not perform well in noisy conditions. Recently, robust algorithms have been proposed to improve the performance and robustness of those algorithms. However, many of them are either computationally very expensive or break down quickly. A generalized maximum-likelihood-based robust algorithm called Subset Least Squares (SLS) has been proposed by Kashyap to deal with contaminated data with less complexity and higher breakdown. In this paper, we first illustrate the basic framework of SLS and the use of SLS for robust regression. We then present the use of SLS method in several image and speech applications. Finally, we discuss the possible use of SLS in future applications.

The processing of images for use in distributed multimedia systems gives rise to several new issues. In this paper, we identify and address some of these issues. We propose a new method of filtering that can be used to simultaneously compress and de-noise an image. We propose an image transmission scheme that uses the multiresolution structure based on multisplines. We show that this scheme is robust to network congestion and cell loss and also has low coding overhead. We include experimental results to demonstrate the effectiveness of our proposed de-noising algorithm and also of the transmission scheme.

We present real-time algorithms for the segmentation of binary images modeled by Markov mesh random fields (MMRFs) and corrupted by independent noise. The goal is to find a recursive algorithm to compute the maximum a posteriori (MAP) estimate of each pixel of the scene using a fixed lookahead of D rows and D columns of the observations. First, this MAP fixed-lag estimation problem is set up and the corresponding optimal recursive (but computationally complex) estimator is derived. Then, both hard and soft (conditional) decision feedbacks are introduced at appropriate stages of the optimal estimator to reduce the complexity. The algorithm is applied to several synthetic and real images. The results demonstrate the viability of the algorithm both complexity-wise and performance-wise, and show its subjective relevance to the image segmentation problem.

We present real-time algorithms for the segmentation of binary images modeled by Markov mesh random fields (MMRFs) and corrupted by independent noise. The goal is to find a recursive algorithm to compute the MAP estimate of each pixel of the scene using a fixed lookahead of D rows and D columns of the observations. The optimal algorithm for this is computationally expensive. Using both hard and soft (conditional) decision feedback, the complexity is reduced in a principled manner to allow a performance/complexity tradeoff. Simulation results demonstrate the viability of the algorithm and it's subjective relevance to the image segmentation problem.

We introduce a class of stochastic processes whose correlation function obeys a structure of the form, E[X(t)X(/spl lambda/t)]=t/sup 2H//spl lambda//sup H/R(/spl lambda/), /spl lambda/,t>0. We refer to these processes as second order self-similar processes. This class of processes include fractional Brownian motion as a special case. We define a concept of autocorrelation and develop a spectral analysis framework via generalized Mellin transform for the proposed class. Additionally, we establish a relationship between the proposed self-similar processes and generalized linear scale invariant system theory. We give specific models and demonstrate their ability to model 1/f phenomena.

A recent method of performing multiresolution analysis is the multispline approach. We extend that idea to two-dimensional functions and perform image compression. In doing so, we propose using a "web" rather than a tree to index the dilates and translates of the basis functions. The advantage is that this offers a richer choice of basis functions at each stage. We include experimental results that compare the performance of our algorithm to the DCT and wavelet methods.

This paper presents a new multiresolution segmentation-based algorithm for image compression. High quality low bit rate image compression is achieved by recursively coding the binary space partitioning (BSP) tree representation of images with multilevel block truncation coding (BTC). Comparison with JPEG at rates below 0.25 bit/pixel shows superior performance both in terms of power signal-to-noise ratio (PSNR) and subjective image quality.

We propose a new stochastic process that we use for modeling an image. We also propose a criterion for function estimation and derive the algorithm that yields the optimal estimate. The algorithm chooses scale-space atoms in an adaptive manner as opposed to the multiresolution approach, which uses all scale-space atoms at any given resolution. Experimental results of our technique are also included.>

The pre- and post-processing units for digital image filtering, are an essential part of any integrated vision or imaging system which uses an intensity image as input. These kinds of processing are normally multiple criteria optimization problems that may involve both restoration and enhancement of the degraded images. The most commonly used figures of merit for evaluating these filters are noise attenuation edge preservation, detail presentation and edge enhancement properties. In recent years, nonlinear techniques have been extensively used to achieve these tasks. However, none of these filters have shown to satisfy all of the above requirements. In this work we introduce a new nonparametric robust nonlinear filter based on generalized maximum likelihood reasoning and order statistics (GMLOS). A qualitative and quantitative comparison of GMLOS and other efficient nonlinear filters is presented to illustrate the capability of this filter in satisfying the desired requirements.>

We propose a new scheme involving autoregressive parameter estimation and pattern classification with maximum likelihood (ML) direction of arrival (DOA) estimation to track multiple targets moving in the far-field. The targets are sources of wideband signals which impinge on a uniform linear array of passive sensors. These wideband signals are modeled as vector autoregressive (AR) models so that the spectral densities of the targets are characterized by a finite number of parameters. Defining each target as a 'class', we use ML estimates of AR parameters and DOA as components to form a feature vector for a particular class. A Bayes classifier is employed to decide which DOA estimate should be associated with which target. Target tracking is achieved by the combined process of spectral density estimation, estimation of DOA and classification at regular time intervals. Experimental results illustrate performance of the proposed method.>

Multiresolution image decompositions (e.g., wavelets), in conjunction with a variety of quantization schemes, have been shown to be very effective for image compression. Recently, several promising tree-structured quantization schemes that exploit the correlation across scales have been proposed. In this paper, we present an image compression algorithm based on a multiresolution Markov random field model used to model the correlations of wavelet coefficients across the scales. We also present experimental results obtained using the algorithm.>

Most of the recent work in nonlinear order statistic filters has focused on smoothing and preserving the details in digital images. However, in many image analysis and computer vision applications, where edges are being used as primary features, edge enhancement becomes an essential attribute of preprocessing filters. Moreover, the human visual system is also very sensitive to this feature. Majority of the most frequently used filters, such as median and its extensions do not posses this property; median filters tend to preserve any monotonic degradation of the edge and therefore, are not capable of enhancing blurred or ramp edges. In this paper we present a variable length robust nonlinear filter which has the capability to both sharpen the edges and smoothing out the noise. Experimental results on real images are also provided.

A projected subset least squares method is presented as a new method for robust linear prediction of speech. The proposed algorithm combines conventional principal component analysis techniques with subset least squares method to perform robust linear regression. The subset least squares is a univariate estimator which applies the generalized maximum likelihood principles to obtain a proper set of inliers from contaminated data. We then use the chosen subset when performing least squares fit. In contrast, the conventional linear prediction procedure weights all prediction residuals equally. In comparison to conventional linear prediction algorithms, our method yields a more efficient estimate of the linear prediction coefficients for speech. Testing on natural human speech demonstrates that formant estimation from contaminated data can be greatly improved.

This paper is concerned with problems in automated visual inspection of manufactured (particularly machined) components based on their (CAD) design models. In order to achieve the integrated intelligent inspection goals, the authors address several interrelated problems. These problems include: (i) developing hierarchical representation mechanisms to effectively capture the knowledge about geometric entities, their relationships, sensors, and plans, (ii) reasoning mechanisms to determine the different attributes of the different features of an object to be inspected, and the alternative strategies which can be used for inspection of each attribute, (iii) strategies for automated generation of position and viewing angles of the cameras in an active vision system, and for determining the visible entities in each configuration, and (iv) optimization of the constructed plan including minimizing the number of sensor settings and the total distance traveled by an active visual sensor.>

This paper investigates the extraction of machining features from boundary descriptions of iso-oriented (having no inclined faces) polyhedrons. We prove that manufacturing the features proposed by our feature extractor results exactly in the desired part-in this respect, the approach is both sound and complete. Our method uses the adjacency information between faces to derive the features. This keeps the determination of isolated features in a part straightforward. However, interaction of features creates difficulties since the adjacency information between some faces is lost. We derive this lost information by considering faces that when extended intersect other faces to form concave edges. The derived face adjacencies are termed virtual links. Augmenting the virtual links to the cavity graph of the object leads to its feature graph, and subgraph matching of primitive graphs in this graph results in feature hypotheses. A feature hypothesis is considered valid if the volume corresponding to it is not shared with the part in question; therefore, we verify the feature hypotheses by checking the regularized intersection of the feature volume and the part. Thus, feature verification employs a constructive solid geometry approach. We have implemented a prototype of the system in the Smalltalk-80 environment.>

The Engineering Research Center for Intelligent Manufacturing Systerns, at Purdue University, was established in 1985 to focus attention on the task of creating a new generation of discrete products manufacturing capability. In addition to the direct technical objectives, the ERC was charged with creating a new cross-disciplinary research environment, new methods for working with industry to ensure bidirectional technology transfer, and new modes of engineering education. The first part of the paper will describe the vision of the center and its relation to industrial competitiveness, the translation of that vision into technical objectives, and the ten-year strategic plan that has guided the conduct of the work

This paper presents a visual query language called VQL for interacting with an object-oriented schema-intensive data model. VQL allows convenient access to the various types of knowledge captured by the semantic model. It consists of a set of "graphical primitives" along with a combination grammar for creating graphical queries. The visual language is internally supported by a prolog-like predicate based query language. The formal grammar underlying the predicate based language is also presented. Apart from being able to create simple queries that can be specified in SQL or QBE, VQL can be used for making queries on any object-oriented data model including the generalization of the E-R model. VQL also handles complicated, indirect queries, specially those that require a reasoning system for query interpretation and response generation. Further, recursive queries on graph structures such as finding transitive closures of graphs may be easily specified. Perhaps the most powerful feature of VQL is its ability to provide high semantic expressibility (in being able to specify highly complex queries) while maintaining simplicity in the user's query formulation process. VQL is embedded in an object-oriented graphical database interaction environment that supports schema creation and manipulation in addition to database querying and updation. The prototype has been implemented in Smalltalk-80 running on a Sun 3/60 workstation. All the illustrations of visual interaction presented are taken from actual interaction sessions.>

The research presented concentrates on bringing together case-based reasoning and expert knowledge-based reasoning in a planner called TOLTEC. The expert's domain-specific knowledge is modelled as dynamic memory structures and this representation is used to help the planner reason and control its planning process. TOLTEC uses a complex indexing of its cases, so as to allow incremental retrieval. The TOLTEC planner is applied to a highly constrained domain, and it is shown how the final plan is created by adding memory- and situation-selected chunks of subtask expansion to each subtask, until the problem is reduced to primitive (nonexpandable) tasks. It is also shown how the use of dynamic memory structures and dynamic, user-directed backtracking allows the planner to predict and discover failures, recover from them, and modify its knowledge according to them. Finally, it is shown how in a domain of multiple possible solutions for each goal the methodology developed allows the planner to slowly model itself to the preferences of the user. The paper also discusses some of the application domains where TOLTEC has been used, including process planning of cylindrical and prismatic parts, design checking, material selection, and design of communications systems.>

A two-level 3D rotational invariant classification is developed based on fractional differencing model. In first level, classification has been done with a fractal scale, and in second level, textures have been classified further in detail with the additional frequency parameters. Because of the properties of the fractal scale and multi-level procedure, the proposed 3D rotational invariant classification scheme reduces the processing time and gives enough accuracy of the classification simultaneously. As a result of a series of experiments involving the differently oriented samples of natural textures, it is concluded that these combined features make possible for this multi-level classification method to have a strong class separability power for arbitrary oriented 3D texture patterns.>

Describes a knowledge-based inspection planning system for solid objects. The goals of intelligent inspection planning include determining which entities (edges, etc.) of the object should be measured, what camera locations and viewing directions should be used to perform inspection, and how the search for these entities and their inspection can be robustly and efficiently done once the sensor data is obtained. An effective solution to this problem is clearly very important not only from the automation point of view but also in order to gather and use sensor information effectively given the volume and complexity of required information for adequate performance.>

The recognition of Korean characters by a syntactic method is considered. Korean characters are composed of phonetic symbols in two dimensions and contain very little redundancy. In addition, the phonetic symbols in each character are different in shape and number depending on how they are composed. Thus, attribute information is important. A Korean character recognition algorithm based on an attribute-dependent programmed grammar is presented. The preprocessing and primitive extraction algorithm is also described. The algorithm was implemented and tested with more than 9600 Korean characters in pages randomly selected from children's story books. The algorithm based on the attribute-dependent programmed grammar recognized characters reasonably quickly, with more than 95.1% accuracy.>

The self-organizing knowledge representation aspects in heterogeneous information environments involving object-oriented databases, relational databases, and rulebases are investigated. The authors consider a facet of self-organizability which sustains the structural semantic integrity of an integrated schemea regardless of the dynamic nature of local schemata. To achieve this objective, they propose an overall scheme for schema translation and schema integration with an object-oriented data model as common data model, and it is shown that integrated schemata can be maintained effortlessly by propagating updates in local schemata to integrated schemata unambiguously.>

Methods and an implemented system for automatic generation of process plans from the CAD boundary representation of a part are presented. Two problems are addressed: one is the machine understanding of the shape of a part from its low-level boundary representation, and the other is developing a plan based on this semantic information. The architecture of the system at the highest level consists of a solid modeler, a shape description system, an automatic process planner, and the interfaces between them. Cooperative reasoning and combining geometric evidences are used to automatically extract the shape primitives of a part and determine the relations between these primitives from the boundary representation CAD data, thus producing the higher-level semantic information. A case-based planner uses the information produced by the shape description system to construct a conceptual plan for machining the part. Examples illustrate the reasoning performed by the system and show its advantages.>

A new 3D texture model is developed by considering the scene image as the superposition of a random texture image on a smooth shaded image. The whole image is analyzed using a patch-by-patch process. Each patch is assumed to be a tilted and slanted texture plane. A modified reflectance map function is applied to describe the deterministic part, and the fractional differencing periodic model is chosen to describe the random texture because of its good performance in texture synthesis and its ability to represent the coarseness and the pattern of the surface at the same time. An orthographical projection technique is developed to deal with this particular random model, which has a nonisotropically distributed texture pattern. For estimating the parameter, a hybrid method that uses both the least square and the maximum-likelihood estimates is applied directly to the given intensity function. By using these parameters, the synthesized image is obtained and used to reconstruct the original image.>

The computational, i.e. architectural, algorithmic, and synchronization, issues related to competitive information integration in a distributed sensor network (DSN) are addressed. The proposed DSN architecture consists of a set of binary trees whose roots are fully connected. Each node of the tree has a processing element and one or more sensors associated with it. The information from each of the sensors has to be integrated in such a manner that the communication costs are low and that the real time needs are met. An information integration algorithm that has a low message cost (linear in the number of nodes of the network) and a low distributed computation cost is presented. The problems associated with synchronizing information to be integrated in the presence of imperfect clocks is considered. The fault tolerant features of the network and the integration algorithm are discussed.>

Fault-tolerance is an important issue in network design because sensor networks must function in a dynamic, uncertain world. A functional characterization of the fault-tolerant integration of abstract interval estimates is proposed. This model provides a preliminary version for a general framework that is hoped to develop to address the general problem of fault-tolerant integration of abstract sensor estimates. A scheme for narrowing the width of the sensor output in a specific failure model is proposed and given a functional representation. The main distinguishing feature of the model over the original model of K. Marzullo (1989) is in reducing the width of the output interval estimate significantly in most cases where the number of sensors involved is large.>

An object-oriented kernel that integrates design and process planning in the domain of mechanical parts is presented. The kernel has identified and separated the integral elements of its domain from the elements that are associated with a particular design/manufacturing environment. Consequently, it can be customized to a wide range of environments and be used as a rapid prototyping tool. A prototype has been developed and implemented in Smalltalk-80.

A novel 3-D shape model is developed to describe a 3-D surface image by considering the scene image as the superposition of a smooth shaded image and a random texture image. The modified reflectance map function is applied to describe the deterministic part, and the orthographically projected fractional differencing periodic model is chosen to describe the random texture, because of its ability to represent the coarseness of the surface and the texture pattern, which is nonisotropically distributed due to the 3-D rotation, at the same time. For estimating the surface orientation parameters, a hybrid method which uses both the least-squares and the maximum-likelihood estimates is applied directly to the given intensity values of the image. These techniques are illustrated by synthetic examples.>

A method for extracting manufacturing shape features from the boundary representation of a polyhedral object is presented. In this approach, the depressions of the part are represented as cavity graphs, which are in turn used as a basis for hypothesis generation-elimination. The proposed cavity graphs are an extended representation in which the links reflect the concavity of the intersection between two faces, and the node labels reflect the relative orientation of the faces comprising the depression. Because previous methods have limited success in handling interactions, emphasis is put on automatic analysis of depressions which are formed by the interactions of primitive features. It is shown that although there is a unique subgraph for each primitive feature, every cavity graph does not correspond to a unique set of primitive features. Consequently, since the cavity graph of a depression may not be the union of the representations for the involved primitives, the concept of virtual links for the formal analysis of the depressions based on cavity graphs is introduced. Finally, a suitable method for automatic determination of the virtual links is presented. This method is based on combining topologic and geometric evidences, and uses a combination of Dempster-Shafer decision theory and clustering techniques to reach its conclusions. Experimental results are presented for a number of examples.>

A pixel is regarded as an edge pixel if there is either a sharp change in the intensity values on either side of the pixel like a step function, yielding a so-called step edge or the texture on either side of the pixel is different, yielding a so-called texture edge. A two stage generate-and-confirm paradigm for detecting all the edge pixels in the scene is used. In the first stage, a directional derivatives approach for determining all potential edge pixels and the direction of the edge is employed. At this stage some of the edge pixels could be spurious, typically caused by either the noise in the image or the microedges inside a texture. In the second stage, each candidate pixel is subjected to two separate tests to confirm whether the edge pixel is a step edge or texture edge. The texture edge is confirmed by a likelihood-ratio test. The likelihood function is computed by fitting a nonsymmetric half-plane random-field model to the texture in a rectangular strip where the dominant direction is perpendicular to the estimated edge direction. Only the edge pixels that pass at least one of the two tests is accepted. The validity of the method is demonstrated by testing four different images.>

Belief propagation and belief combination procedures based on the Dempster-Shafer belief function for inference in rule-based systems is proposed. The belief combination procedure yields results identical to those of Dempster's rule when pieces of evidence are independent. Dempster's rule is shown to be nonrobust for combining evidence with a high degree of conflict. The cause of the nonrobustness is discussed, and an alternative belief combination procedure to remedy the deficiency is proposed. Although the proposed procedure yields results that are dependent on the interpretations of the rule, it is shown to be an interpolation between total ignorance and the uncertainty associated with the rule regardless of the interpretations. When the rule interpretation yields an associative belief propagation procedure, a corresponding chaining syllogism for it can be derived. The proposed inference procedures are applied to a lattice-structured inference network.>

A robust estimation method for frequencies of received signals is investigated. The received signals are represented as the sum of sinusoidal signals and an additive noise process. The additive noise is assumed to be a mixture of a Gaussian and an outlier process. The influence function of a robust estimate is derived for time-varying (sinusoidal) signals. The variance of the robust estimate is also derived, using the influence function, and found to be close to both the Cramer-Rao lower bounds, one of which is computed under the perfect Gaussian assumption and the other under the contaminated Gaussian assumption. It is proved that the robust estimate possesses high-resolution properties even when outliers exist.>

Current approaches to diagnosis cannot handle novel situations and are inefficient in that they require excessive amounts of test data to isolate a fault. This paper presents a problem-solving method that combines an experientially-based abnormal model of device operation with a functionality-based model of normal operation. The CONSOLIDATE system has been constructed in SMALLTALK-80, and an television diagnosis application has been developed.

No abstract available.

Associative evidential reasoning is the mechanism of combining evidence and evaluating hypotheses, which is the core of many computational systems. It is shown that under the generalized symmetry condition, that is, f(a,b)=neg (f(neg(a), neg(b))), where f is the combination operator satisfying common requirements like associativity and monotonicity, and neg maps positive elements to negative ones and vice versa, f is uniquely determined by a one-place mapping from the positive region to the set of positive reals. Furthermore, such combination formulas cannot be made robust, and quantizing the region will cause the loss of associativity or other inconsistencies. The implications on evidential reasoning system are: there exists often only one kind of formula for combining evidence; the quest for robust combination is often infeasible; and the attempt of converting numerical degrees of belief to linguistic quantifiers and vice versa is destined to be fruitless.>

The problem of detecting texture boundaries without assuming any knowledge on the number of regions or the types of textures is considered. Texture boundaries are often regarded as better features than intensity edges, because a large class of images can be considered a composite of several different texture regions. An algorithm is developed that detects texture boundaries at reasonably high resolution without assuming any prior knowledge on the texture composition of the image. The algorithm utilizes the long correlation texture model with a small number of parameters to characterize textures. The parameters of the model are estimated by a least-squares method in the frequency domain. The existence and the location of texture boundary is estimated by the maximum-likelihood method. The algorithm is applied to several different images, and its performance is shown by examples. Experimental results show that the algorithm successfully detects texture boundaries without knowing the number of types of textures in the image.>

The authors describe a character recognition algorithm for Korean characters that uses attribute-dependent regular programmed grammar (ADRPG). Each Korean character has more strokes than an English character. and the recognition of Korean characters is heavily dependent on the attributes of strokes. They implemented a syntactic algorithm based on the ADPRG, which easily incorporates attribute information such as position, angle, length, and branch points. The ADPRG-algorithm is implemented on a PC-AT compatible, and 377 production rules and 78 attribute test functions are derived from a printed document containing 4206 Korean characters and applied another document containing 3092 Korean characters having some defects. More than 95.1% of 3092 Korean characters are correctly recognized with an average speed of 1.15 characters/s.>

The authors consider impulse response estimation of linear time-invariant causal systems based on input-output measurements. In particular, their interest is in developing estimates that are robust against outliers and distributional uncertainties. They present a method which uses Huber's functions as the criterion for fitting a parametric model to the input-output observations. The estimates from this method are compared with the estimates from a similar parametric approach but which uses the conventional quadratic criterion, and also with the estimates from some nonparametric approaches. Results from simulation clearly show that the estimates from the parametric approach using Huber's function are most robust of all the estimates considered.>

A logic-oriented object base is defined to be a deductive database based on an object data model. Like conventional databases, logic-orientated object bases can be constructed on top of computer networks in such a way that the distribution of logical and physical components of the system is kept hidden from the users. Objects are organized hierarchically and are retrieved through customized methods. The problem of query optimization in such an environment is investigated.>

The authors present an intelligent manufacturing system that combines design with process planning. For the design stage they have implemented an experimental package that combines boundary representation, CSG, and models of manufacturing features in a simple graphics environment. This package, named XTWIN, was combined with an intelligent process planning system TOLTEC which uses cases of previous process plans stored as dynamic memory structures. This knowledge organization allows TOLTEC to rearrange its memory, thus learning from experience, and to also apply its experience to new cases.>

The authors consider the problem of terrain model acquisition by a roving point placed in an unknown terrain populated by stationary polyhedral obstacles in two/three dimensions. The motivation for this problem is that after the terrain model is completely acquired, navigation from a source point to a destination point can be achieved along the collision-free paths. This can be done without the usage of sensors by applying the existing techniques for the find-path problem. In the paper, the point robot autonomous machine (PRAM) is used as a simplified abstract model for real-life roving robots. An algorithm is presented that enables PRAM to autonomously acquire the model of an unexplored obstacle terrain composed of an unknown number of polyhedral obstacles in two/three dimensions. In this method, PRAM undertakes a systematic exploration of the obstacle terrain with its sensor that detects all the edges and vertices visible from the present location, and builds the complete obstacle terrain model.>

The binary-image-compression problem is analyzed using irreducible cover of maximal rectangles. A bound on the minimum-rectangular-cover problem for image compression is given under certain conditions that previously have not been analyzed. It is demonstrated that for a simply connected image, the irreducible cover proposed uses less than four times the number of the rectangles in a minimum cover. With n pixels in a square, the parallel algorithm for obtaining the irreducible cover uses (n/log n) concurrent-read-exclusive write (CREW) processors in O(log n) time.>

An abstract formalism for the representation of spatial knowledge is suggested. The focus is on the development of a comprehensive representation scheme for pictorial information in which the knowledge model of the given world has a high degree of perceptual similarity to a typical user's view of the same world. The model that has been developed uses the object-oriented method of knowledge representation. The intention is that with this model any user of the system will be equipped to depict pictorial information easily and will be able to portray spatial as well as conceptual abstractions, generalizations, and rules at various levels.>

The pseudolink concept for representing the tip position of a nonrigid link is developed. The pseudolink is defined as the line segment connecting the proximal and distal ends of the links. Pseudolink length and angle are determined online using joint encoder information together with strain measurements taken along the link. External sensors are not required and trajectory planning can be carried out a priori under a rigid-link assumption. A self-tuning control based on pseudolinks is discussed. Laboratory experiments on a rotating nonrigid link show the proposed control leads to improved performance over a control that ignores compliance.>

At the very abstract level, generative process planning is like any other planning problem. An analogy can be drawn between the process planning problem and the robot planning problem. At the top there are a set of goals to be achieved and a set of operations available, and the computer is asked to, starting from scratch, synthesize a sequence of operations to achieve the given set of goals. It can be shown that conjunctive goal planning problems in general are very diffcult to solve. One remedy that has been proposed to solve the robot programming problem, and apparently could be applied to the process planning problem, is to provide the users with very high level programming languages such that details to achieve a high level operation can be transparent to the users. In other words, the computer is used to fill in low-level details. Another possible remedy would be to generalize the family concept such that families can be defined precisely enough to eliminate human modification and broad enough to include most variations. In this paper we purpose the framework of object-oriented knowledge base to achieve these functions.

We present computer vision algorithms that recognize and locate partially occluded objects. The scene may contain unknown objects that may touch or overlap giving rise to partial occlusion. The algorithms revolve around a generate-test paradigm. The paradigm iteratively generates and tests hypotheses for compatibility with the scene until it identifies all the scene objects. Polygon representations of the object's boundary guide the hypothesis generation scheme. Choosing the polygon representation turns out to have powerful consequences in all phases of hypothesis generation and verification. Special vertices of the polygon called ``corners'' help detect and locate the model in the scene. Polygon moment calculations lead to estimates of the dissimilarity between scene and model corners, and determine the model corner location in the scene. An association graph represents the matches and compatibility constraints. Extraction of the largest set of mutually compatible matches from the association graph forms a model hypothesis. Using a coordinate transform that maps the model onto the scene, the hypothesis gives the proposed model's location and orientation. Hypothesis verification requires checking for region consistency. The union of two polygons and other polygon operations combine to measure the consistency of the hypothesis with the scene. Experimental results give examples of all phases of recognizing and locating the objects.

The problem of navigating an autonomous mobile robot through unexplored terrain of obstacles is discussed. The case when the obstacles are "known" has been extensively studied in literature. Completely unexplored obstacle terrain is considered. In this case, the process of navigation involves both learning the information about the obstacle terrain and path planning. An algorithm is presented to navigate a robot in an unexplored terrain that is arbitrarily populated with disjoint convex polygonal obstacles in the plane. The navigation process is constituted by a number of traversals; each traversal is from an arbitrary source point to an arbitrary destination point. The proposed algorithm is proven to yield a convergent solution to each path of traversal. Initially, the terrain is explored using a rather primitive sensor, and the paths of traversal made may be suboptimal. The visibility graph that models the obstacle terrain is incrementally constructed by integrating the information about the paths traversed so far. At any stage of learning, the partially learned terrain model is represented as a learned visibility graph, and it is updated after each traversal. It is proven that the learned visibility graph converges to the visibility graph with probability one when the source and destination points are chosen randomly. Ultimately, the availability of the complete visibility graph enables the robot to plan globally optimal paths and also obviates the further usage of sensors.

This paper presents a new model-based approach for texture classification which is rotation invariant, i.e., the recognition accuracy is not affected if the orientation of the test texture is different from the orientation of the training samples. The method uses three statistical features, two of which are obtained from a new parametric model of the image called a ``circular symmetric autoregressive model.'' Two of the proposed features have physical interpretation in terms of the roughness and directionality of the texture. The results of several classification experiments on differently oriented samples of natural textures including both microtextures and macrotextures are presented.

A vision system is presented that recognizes occluded industrial parts. The unknown image may contain multiple objects that may touch or overlap giving rise to partial occlusion. The vision system uses stored models to locate and identify the objects in the scene. The models are based on the boundary of the object, since we assume that the objects are rigid and planar. From the polygon approximation of the boundary, vertices of high curvature are identified as "corners." These corners are used as features in detecting the model in the image. A globally consistent coordinate transform that takes the model into the image is found by using a Hough like transform and the corner features.

An empirical study of many natural two dimensional textures with strong quasi periodicities show that their spectral density at the peak frequency behaves like (f-f1)-β, where 01)-2. We propose here a class of models whose spectral density behaves like (f-f1)-β, 0 < β < 1. We discuss the synthesis of two dimensional images obeying these models. We will display the synthesized images and note their resemblance to the natural textures.

Random field models have arisen in important applications in many diverse fields, including image synthesis and analysis. The automatic description and processing of images is limited by the types of underlying models that are hypothesized for the image. Hence, new random field models and associated techniques are developed. The new class of models includes the traditional simultaneous autoregressive and moving average models, but extends these to comprise a substantially larger new class. Thus, new image textures are representable with convenient small-order parameterizations. In particular, representations with significant correlations between distant locations are achieved. The algorithms for synthesis and estimation, however, require only about the same amount of time as the classical models. The development is facilitated by a new mathematical formulation suitable for problems involving high-dimensional transformations.

A class of finite-order two-dimensional autoregressive moving average (ARMA) is introduced that can represent any process with rational spectral density. In this model the driving noise is correlated and need not be Gaussian. Currently known classes of ARMA models or AR models are shown to be subsets of the above class. The three definitions of Markov property are discussed, and the class of ARMA models are precisely stated which have the noncausal and semicausal Markov property without imposing any specific boundary conditions. Next two approaches are considered to estimate the parameters of a model to fit a given image. The first method uses only the empirical correlations and involves the solution of linear equations. The second method is the likelihood approach. Since the exact likelihood function is difficult to compute, we resort to approximations suggested by the toroidal models. Numerical experiments compare the quality of the two estimation schemes. Finally the problem of synthesizing a texture obeying an ARMA model is considered.

A smoother version of a polygon ¿ is defined as a polygon which approximates ¿ according to a given criterion and which simultaneously has no more edges than ¿ itself. In this paper, a scale preserving smoothing algorithm is presented. The input to the algorithm is a polygon ¿ and the output is its smoothed version ¿. ¿, which contains all the scale information that ¿ contains, is called the linear minimum perimeter polygon (LMPP) of ¿ within a tolerance of. Using the quantity the degree of with ¿ approximates ¿ can be controlled. From the LMPP a representation for a polygon approximating ¿ can be procured, which is invariant to scale and translation changes. Examples of smoothing maps and characters have been presented.

Some aspects of statistical inference for a class of spatial-interaction models for finite images are presented: primarily the simultaneous autoregressive (SAR) models and conditional Markov (CM) models. Each of these models is characterized by a set of neighbors, a set of coefficients, and a noise sequence of specified characteristics. We are concerned with two problems: the estimation of the unknown parameters in both SAR and CM models and the choice of an appropriate model from a class of such competing models. Assuming Gaussian-distributed variables, we discuss maximum likelihood (ML) estimation methods. In general, the ML scheme leads to nonlinear optimization problems. To avoid excessive computation, an iterative scheme is given for SAR models, which gives approximate ML estimates in the Gaussian case and reasonably good estimates in some non-Gaussian situations as well. Likewise, for CM models, an easily computable consistent estimate is given. The asymptotic mean-squared error (mse) of this estimate for a four-neighbor CM model is shown tn be substantially less than the mse of the popular coding estimate. Asymptotically consistent decision rules are given for choosing an appropriate SAR or CM model. The usefulness of the estimation scheme and the decision rule for the choice of neighbors is illustrated by using synthetic patterns. Synthetic patterns obeying known SAR and CM models are generated, and the models corresponding to true and several competing neighbor sets are fitted. The estimation scheme yields estimates close to the parameters of the true models, and the decision rule for the choice of neighbors picks up the true model from the class of competing models.

Let T(U) be the set of words in the dictionary H which contains U as a substring. The problem considered here is the estimation of the set T(U) when U is not known, but Y, a noisy version of U is available. The suggested set estimate S*(Y) of T(U) is a proper subset of H such that its every element contains at least one substring which resembles Y most according to the Levenshtein metric. The proposed algorithm for-the computation of S*(Y) requires cubic time. The algorithm uses the recursively computable dissimilarity measure Dk(X, Y), termed as the kth distance between two strings X and Y which is a dissimilarity measure between Y and a certain subset of the set of contiguous substrings of X. Another estimate of T(U), namely SM(Y) is also suggested. The accuracy of SM(Y) is only slightly less than that of S*(Y), but the computation time of SM(Y) is substantially less than that of S*(Y). Experimental results involving 1900 noisy substrings and dictionaries which are subsets of 1023 most common English words [11] indicate that the accuracy of the estimate S*(Y) is around 99 percent and that of SM(Y) is about 98 percent.

This paper deals with the Bayesian method of choosing the best model for a given one-dimensional series among a finite number of candidates belonging to autoregressive (AR), moving average (MA), ARMA, and other families. The series could be either a sequence of observations in time as in speech applications, or a sequence of pixel intensities of a two-dimensional image. The observation set is not restricted to be Gaussian. We first derive an optimum decision rule for assigning the given observation set to one of the candidate models so as to minimize the average probability of error in the decision. We also derive an optimal decision rule so as to minimize the average value of the loss function. Then we simplify the decision rule when the candidate models are different Gaussian ARMA models of different orders. We discuss the consistency of the optimal decision rule and compare it with the other decision rules in the literature for comparing dynamical models.

Two geometrical measures have been proposed to quantify the dissimilarity between two irregular polygons. These measures capture the intuitive notion of the dissimilarity between shapes and are related to the minimum value of the intersecting area of the polygons on superposing one on the other in various configurations. A more easily computable measure of dissimilarity, referred to as the minimum integral square error between the polygons, has also been proposed, and using the latter measure pattern classification, has been performed. Experimental results involving the classification of the noisy boundaries of the four Great Lakes, Erie, Huron, Michigan, and Superior, using this measure, have been presented.

The analysis of closed boundaries of arbitrary shapes on a plane is discussed. Specifically, the problems of representation and reconstruction are considered. A one-to-one correspondence between the given closed boundary and a univariate or multivariate sequence of real numbers is set up. Univariate or multivariate circular autoregressive models are suggested for the representation of the sequence of numbers derived from the closed boundary. The stochastic model representing the closed boundary is invariant to transformations like sealing, translation, choice of starting point, and rotation over angles that are multiples of2\pi/N, whereNis the number of observations. Methods for estimating the unknown parameters of the model are given and a decision rule for choosing the appropriate number of coefficients is included. Constraints on the estimates are derived so that the estimates are invariant to the transformations of the boundaries. The stochastic model enables the reconstruction of a dosed boundary using FFT algorithms. Results of simulations are included and the application to contour coding is discussed.

To date, severat retationat database systems have been proposed that attempt to provide high level, non-proceduraL query languages for non programmer users. These languages, however, require the user to know the structure of the relational database and/or suffer from drawbacks like query ambiguity and lack of semantic integrity. For a large database, it is too much to expect the user to know the structure of the relational data base. In this paper, we deveLop a procedure for conveying onty the information content of a data base to the user, without involving the detaits of the retationaL schema, like the name of relation, attributes in it, etc. A retrieval scheme is proposed for a retational database system that seeks to overcome probLems of query ambiguity and lack of semantic integrity and that enables the user to specify his query without knowing the detaits of the relations in the database.

This study deals with the design of a syntactic decision rule for recognizing an unknown utterance from a set X. The decision rule is expressed as a function of the character string (CS) derived from the test utterance. To obtain the CS, the waveform of the utterance is divided into a large number of frames of roughly equal duration numbered 1, 2,...,n. The ith symbol in the CS is the phonemic symbol obtained by subjecting the ith frame of the waveform to a relatively simple phoneme decision rule, the number of symbols in the CS being n. All the available nonacoustic information such as the lexicon of words in the set X, the possibility of confusion between different phonemes as seen by the phoneme decision rule, etc. is used in the design of the decision rule. The syntactic decision rule can be implemented by a stochastic finite state automaton involving limited memory and computation. The decision rule can also be interpreted as yielding the phrase x which minimizes a distance measure D(x, z) between the phrase x X and the observed CS z. We wili compare this approach with the other approaches such as the Viterbi methods, the distance approaches involving various types of distances, etc.

We describe a method of recognizing isolated words and phrases from a given vocabulary spoken by any member in a given group of speakers, the identity of the speaker being unknown to the system. The word utterance is divided into 20-30 nearly equal frames, frame boundaries being aligned with glottal pulses for voiced speech. A constant number of pitch periods are included in each frame. Statistical decision rules are used to determine the phoneme in each frame. Using the string of phonemes from all the frames of the utterance, a word decision is obtained using (phonological) syntactic rules. The syntactic rules used here are of 2 types, namely, 1) those obtained from the theory of word construction from phonemes in English as applied to our vocabulary, 2) those used to correct possible errors in phonemic decisions obtained earlier based on the decisions of neighboring segments. In our experiment, the vocabulary had 40 words, consisting of many pairs of words which are phonemically close to each other. The number of speakers was 6. The identity of the speaker is not known to the system. In testing 400 words utterances, the recognition rate was about 80 percent for phonemes (for 11 phonemes) but the word recognition was 98.1 percent correct. Phonological-syntactic rules played an important role in upgrading the word recognition rate over the phoneme recognition rate.

The problem to be considered is that of classifying a given time seriesZ_{N} = (y(1), \cdots ,y(N))into one ofrclassesC_{i}, i= 1, \cdots ,r. The stochastic processy(\cdot)is assumed to obey an autoregressive structure involving a parameter vector\theta, whose probability densityp(\theta|C_{i})depends on the class to whichZory(\cdot)belongs. Assuming appropriate expressions forp(\theta|C_{i}), it is shown that the probability density ofZ_{N}characterizing each class, namelyp(Z_{N}|C_{i}), possesses a vector\bar{\theta}of sufficient statistics, i.e., all the information aboutZ_{N}needed for the discrimination between the various classes is contained in the vector\bar{\theta}=(\bar{\theta}_{1}(Z_{N}), \cdots , \bar{\theta}_{m+1}(Z_{N}))^{T}, where the functions\bar{\theta}_{i}(Z_{N}), i=1, \cdots ,m+1have the same structure for allN. Thus the best possible feature set for the problem is\bar{\theta}From this is deduced the optimal decision rule to minimize the average probability of error. The optimal feature set and the corresponding optimal decision rule are compared with other feature sets and decision rules mentioned in the literature on speech recognition.

The multiple-attribute-tree (MAT) data-base organization is modeled and analyzed. Average retrieval time per query is obtained using a statistical estimation procedure and computationally efficient cost equations are presented. These cost equations are validated using a small experimental data base. Several real-life and generated data bases are used to demonstrate the effectiveness of the multiple-attribute-tree organization in reducing the expected retrieval time per query over conventional methods.

In this paper we will present two methods for the reronstruction of a two-dimensional picture from its one-dimensional projections at various angles. The first method is recursive, and the second is nonrecursive. Both of these methods have potential applications in picture transmission, and offer valuable insight into the more general problem of reconstruction of three-dimensional objects from their two-dimensional projections. We will illustrate the numerical details of each method by considering the reconstruction of a picture discretized on a 32 X 32 grid, and compare their relative merits. These two methods will also be compared with other methods suggested in the literature.

The problem of statistical decision making under uncertainty is considered. A Bayes approach based upon prior probabilities which are found using an objective inference technique developed by Kashyap is proposed as the basic solution procedure. The problem is formulated in a statistical decision theory format and the general solution technique is outlined. Using this inference technique, it is possible to have different priors for different experiments. A general decision criterion is formulated to handle these situations. It is shown that in situations where the experimentation is fixed and the decision problem is faced repeatedly, but not necessarily an infinite number of times, this approach is justifiable. In situations where there is a choice of experiments, these arguments are not as conclusive; however, the approach still has practical merit as an objective alternative to the minimax approach.

Consider a stochastic system with outputYwhose probability density(pY \mid \Lambda)is a known function of the parameter\Lambdawhose true value is unknown. Our aim is to assign a prior probability densityb(\Lambda)for\Lambdausing all the available knowledge so that we can assess the probabilistic behavior ofYfrom the corresponding marginal densityq(Y). Usually the range of\Lambdais known. In addition, by considering the distribution of\Lambdain similar systems, we can define the densityf(\Lambda), about which we may have some knowledge such asE(\Lambda _ 1 ^ {2}) \geq 1/2, etc. We derive an expression for the uncertainty functional\phi(\cdot)involvingf(\Lambda)andb(\Lambda)to quantify the discrepancy between the actual behavior ofYand our assessment of its behavior. We pose a two-person zero-sum game with\phias the payoff function so thatb(\Lambda)is chosen by us to minimize\phi, whereasf(\Lambda)is chosen by nature to maximize\phi. We derive an asymptotic expression for the prior density, work out a few examples, and discuss the advantages of this method over others.

We consider the problem of recursively estimating the transition matrix of a regular Markov chain with a finite number of states using only noisy measurements of the state. The measurement noise sequence is assumed to be independent with known mean and unknown variance. We also discuss the convergence rates and computational aspects of the algorithms and the methods of accelerating them.

A coding scheme for an additive Gaussian channel is developed using a noisy feedback link andD-dimensional elementary signals with no bandwidth constraint. This allows error-free transmission at a rateR < R_{c}whereR_{c}is slightly less than the channel capacityC. When there is no noise in the feedback channel, the coding scheme reduces to aD-dimensional generalization of the coding scheme of Schalkwijk and Kailath. In addition, the expression for the probability of error is determined whenT, the time of transmission rate, is finite. The scheme is also compared with the best codes that use only the forward channel.

First- and second-order stochastic gradient algorithms are developed for suitably approximating the unknown density and distribution functions of a random vector from a sequence of independent samples. The mean-square-error criterion and the integral-square-error criterion are used in the approximations. The rates of convergence and the approximation error are also evaluated.

In this paper, two general methods of determining a separating surface f(x)= Σn-1i=0αiøi(x) = 0 will be developed for any switching problem in terms of threshold elements øi(x). First, a polynomial decision function f(x) is synthesized so that it has no more than N terms in it where N is the total number of pattern vectors of the switching problem. This decision function is easily amenable for mechanization since it needs the solution of a triangular system of N equations in N unknowns. In addition, a method of deriving aminimal polynomial solution f(x) will also be given. Second, a decision function f(x) involving general threshold elements øi(x) is derived from the polynomial solution so that it has fewer terms than the polynomial solution. Examples will be given to illustrate the methods and compare these results with those obtained by the traditional method of prime implicants.

An exponentially convergent and finite algorithm is presented for the determination of the solution α of the linear inequalities Aα>0 for a given matrix A, or for determining the non-existence of solution for Aα>0. This result is useful in threshold-switching theory and in pattern classification problems. Experiments indicate extremely rapid convergence of the method.