In robot and sensor networks, one of the key challenges is to decide when and where to deploy sensory resources to gather information of optimal value. The problem is essentially one of planning, scheduling and controlling the sensors in the network to acquire data from an environment that is constantly varying. The dynamic nature of the problem precludes the use of traditional rule-based strategies that can handle only quasi-static context changes. Automatic context derivation procedures are thus essential for providing fault recovery and fault pre-emption in such systems. We posit that the quality of a sensor network configuration depends on sensor coverage and geometry, sensor allocation policies, and the dynamic processes in the environment. In this paper, we show how these factors can be manipulated in an adaptive framework for robust run-time resource management. We demonstrate our ideas in a people tracking application using a network of multiple cameras. The task specification for our multi-camera network is one of allocating a camera pair that can best localize a human subject given the current context. The system automatically derives policies for switching between camera pairs that enable robust tracking while being attentive to performance measures. Our approach is unique in that we do not make any a priori assumptions about the scene or the activities that take place in the scene. Models of motion dynamics in the scene and the camera network configuration steer the policies to provide robust tracking.

In large scale surveillance applications, coherent presentation of data coming from myriad sensors becomes a problem. For example, tasks such as "locate an intruder" are no longer easy when the user is facing a room of monitors connected to hundreds of cameras. Therefore, there is a need for a system that allows the user to easily navigate the data space. Due to the scale of the application, such systems should also be robust with respect to hardware and software failures, as well as to varying bandwidth conditions. Our strategy is to first build software units that provide sensor abstractions (e.g., location of a person, noise level of a predefined region) to lessen the burden of dealing with individual sensors from the user. Second, we project this abstract sensor information into an augmented virtual reality interface for presentation to the user. The AVR interface offers a common medium to display abstract information constructed from multiple sensors, as well as allowing access to raw sensor information such as video streams, or a mixture of both. Also, the AVR interface can synthesize views not serviced by the physical cameras. The sensor abstraction and the smooth transition between sensors enable the user to intuitively navigate the data space. Further more, through this interface, the user can dynamically reconfigure the system resources. We will demonstrate three scenarios highlighting the above mentioned features.

In this paper, we present a new method for automatically and efficiently generating stereoscopic mosaics by seamless registration of images collected by a video camera mounted on an airborne platform. Using a parallel-perspective representation, a pair of geometrically registered stereo mosaics can be precisely constructed under quite general motion. A novel parallel ray interpolation for stereo mosaicing (PRISM) approach is proposed to make stereo mosaics seamless in the presence of obvious motion parallax and for rather arbitrary scenes. Parallel-perspective stereo mosaics generated with the PRISM method have better depth resolution than perspective stereo due to the adaptive baseline geometry. Moreover, unlike previous results showing that parallel-perspective stereo has a constant depth error, we conclude that the depth estimation error of stereo mosaics is in fact a linear function of the absolute depths of a scene. Experimental results on long video sequences are given.

This paper presents a control structure for a general-purpose image understanding system. It addresses the high level of uncertainty in local hypotheses and the computational complexity of image interpretation. The control of vision algorithms is done by an independent subsystem that uses Bayesian networks and utility theory to compute marginal value of information and selects the algorithm with the highest value of information. It is shown that the knowledge base can be acquired using learning techniques and the value-driven approach to the selection of vision algorithms leads to performance gains.

As the threat of terrorism becomes more prevalent, the need for technological innovations for tighter security rises. Some of the areas where security needs to be increased are at border customs stations, airports, federal buildings, embassies, sporting events, and the like where checkpoints are being set up to inspect vehicles coming onto the premises. The proposed vehicle inspection system uses an at-ray of cameras and mosaicing techniques to generate different perspective views that provide a 3D representation of a vehicle's undercarriage. These mosaics allow a complete inspection of the undercarriage using a graphical user interface without requiring the use of inspection mirrors or the vehicle to drive over a manned inspection bay. The system is designed for simplicity so that operators will not require long training periods.

This paper presents a control structure for general purpose image understanding that addresses both the high level of uncertainty in local hypotheses and the computational complexity of image interpretation. The control of vision algorithms is performed by an independent subsystem that uses Bayesian networks and utility theory to compute the marginal value of information provided by alternative operators and selects the ones with the highest value. We have implemented and tested this control structure with several aerial image datasets. The results show that the knowledge base used by the system can be acquired using standard learning techniques and that the value-driven approach to the selection of vision algorithms leads to performance gains. Moreover, the modular system architecture simplifies the addition of both control knowledge and new vision algorithms.

The ability to efficiently and robustly recover accurate 3D terrain models from sets of stereoscopic images is important to many civilian and military applications. Our long-term goal is to develop an automatic, multi-image 3D reconstruction algorithm that can be applied to these domains. To develop an effective and practical terrain modeling system, methods must be found for detecting unreliable elevations in digital elevation maps (DEMs), and for fusing several DEMs from multiple sources into an accurate and reliable result. This paper focuses on two key factors for generating robust 3D terrain models, (1) the ability to detect unreliable elevations estimates, and (2) to fuse the reliable elevations into a single optimal terrain model. The techniques discussed in this paper are based on the concept of using self-consistency to identify potentially unreliable points. We apply the self-consistency methodology to both the two-image and multi-image scenarios. We demonstrate that the recently developed concept of self-consistency can be effectively employed to determine the reliability of values in a DEM. Estimates with a reliability below an error threshold can be excluded from further processing. We test the effectiveness of the methodology, as well as the relationship between error rate and scene geometry by processing both real and photo-realistic simulations.

For typical classification tasks, all training data are prepared in advance and are supplied to the classifier all at once. This is unnecessarily expensive and incurs overfitting problems, since the individual contributions of the training instances to the classifier are not known. We address this by proposing an interactive incremental framework for image classifier construction, where small numbers of training examples are supplied at each user interaction. After incorporating new training instances, the classifier immediately reclassifies the image to provide the user with instant feedback. This allows the user to choose additional informative training pixels from among the currently misclassified ones. Using a realistic terrain classification task, we demonstrate the potential of our method to generate small and accurate decision tree classifiers from surprisingly few training examples while avoiding overspecialization. We also briefly discuss the novel concept of hierarchical classification, where higher-level classifiers take as input the output of lower-level classifiers. We present preliminary results indicating that within our interactive framework, this is a practical approach to exploiting spatial relationships for classification.

A robust system is proposed to automatically detect and extract text in images from different sources, including video, newspapers, advertisements, stock certificates, photographs, and checks. Text is first detected using multiscale texture segmentation and spatial cohesion constraints, then cleaned up and extracted using a histogram-based binarization algorithm. An automatic performance evaluation scheme is also proposed.

We describe a solution to the problem of indexing images of flowers for searching a flower patents database by color. We use a natural language color classification derived from the ISCC-NBS color system and the X Window color names to effectively use the domain knowledge available, provide perceptually correct retrieval and allow natural language queries. We have developed an automatic iterative segmentation algorithm with knowledge-driven feedback to isolate a flower region from the background. The color of the flower is defined by the color names present in the flower region and their relative proportions. The database can be queried by example and by color names. We demonstrate the effectiveness of the strategy on a test database.

We study the reliability of a set of stereo-based 3-D textural features in classification in response to different training data. Two types of training data, "labeling-based" and "chip-based," are investigated. Experiments have been carried out to compare the 3-D features with a set of 2-D features based on co-occurrence analysis. Results show that the 3-D features consistently outperform the 2-D features in terms of classification accuracy under various configurations of training data.

We describe a new multi-phase, color-based image retrieval system, FOCUS (Fast Object Color-based qUery System), with an online user interface which is capable of identifying multi-colored query objects in an image in the presence of significant, interfering backgrounds. The query object may occur in arbitrary sizes, orientations and locations in the database images. The color features used to describe an image have been developed based on the need for speed in matching and ease of computation on complex images while maintaining the scale and rotation invariance properties. The first phase matches the color content of an image computed as the peaks in the color histogram of the image, with the query object colors using an efficient indexing mechanism. The second phase matches the spatial relationships between color regions in the image with the query using a spatial proximity graph (SPG) structure designed for the purpose. The method is fast and has low storage overhead. Test results with multi-colored query objects from artificial and natural domains show that FOCUS is quite effective in handling interfering backgrounds and large variations in scale. The experimental results on a database of diverse images highlights the capabilities of the system.

A technique is introduced for extracting and reconstructing a wide class of building types from a registered range image and optical image. An attentional focus stage, followed by model indexing, allows top-down robust surface fitting to reconstruct the 3D nature of the buildings in the data. Because of the effectiveness of model selection, top-down processing of noisy range data still succeeds and the algorithm is capable of detecting and reconstructing several different building roof classes, including flat single level, flat multi-leveled, peaked, and curved rooftops. The algorithm is applicable to range data that may have been collected from several different range sensor types. We demonstrate reconstructions of different buildings classes in the presence of large amounts of noise. Our results underline the usefulness of range data when processed in the context of a focus-of-attention area derived from the monocular optical image.

Texture has long been regarded as spatial distributions of gray-level variation, and texture analysis has generally been confined to the 2-D image domain. Introducing the concept of "3-D world feature", this paper considers texture as a function of 3-D structures and proposes a set of "3-D textural features". The proposed 3-D features appear to have a great potential in terrain classification. Experiments have been carried out to compare the 3-D features with a popular traditional 2-D feature set. The results show that the 3-D features significantly outperform the 2-D features in terms of classification accuracy.

Local search is a well established and highly effective method for solving complex combinatorial optimization problems. Here, local search is adapted to solve difficult geometric matching problems. Matching is posed as the problem of finding the optimal many-to-many correspondence mapping between a line segment model and image line segments. Image data is assumed to be fragmented, noisy, and cluttered. The algorithms presented have been used for robot navigation, photo interpretation, and scene understanding. This paper explores how local search performs as model complexity increases, image clutter increases, and additional model instances are added to the image data. Expected run-times to find optimal matches with 95 percent confidence are determined for 48 distinct problems involving six models. Nonlinear regression is used to estimate run-time growth as a function of problem size. Both polynomial and exponential growth models are fit to the run-time data. For problems with random clutter, the polynomial model fits better and growth is comparable to that for tree search. For problems involving symmetric models and multiple model instances, where tree search is exponential, the polynomial growth model is superior to the exponential growth model for one search algorithm and comparable for another.

There are many historical manuscripts written in a single hand which it would be useful to index. Examples include the W.B. DuBois collection at the University of Massachusetts and the early Presidential libraries at the Library of Congress. Since Optical Character Recognition (OCR) does not work well on handwriting, an alternative scheme based on matching the images of the words is proposed for indexing such texts. The current paper deals with the matching aspects of this process. Two different techniques for matching words are discussed. The first method matches words assuming that the transformation between the words may be modelled by a translation (shift). The second method matches words assuming that the transformation between the words may be modelled by an affine transform. Experiments are shown demonstrating the feasibility of the approach for indexing handwriting. The method should also be applicable to retrieving previously stored material from personal digital assistants (PDAs).

The knowledge-directed approach to image interpretation popular in the 1980's, sought to identify objects in unconstrained two-dimensional (2-D) images and to determine the three-dimensional (3-D) relationships between these objects and the camera by applying large amounts of object- and domain-specific knowledge to the interpretation problem. Among the primary issues faced by these systems were variations among instances of an object class and differences in how object classes were defined in terms of shape, color, function, texture, size, and/or substructures. This paper argues that knowledge-directed vision systems typically failed for two reasons. The first is that the low- and mid-level vision procedures that were relied upon to perform the basic tasks a vision were too immature at the time to support the ambitious interpretation goals of these systems. This problem, we conjecture, has been largely solved by recent advances in the field of 3-D computer vision particularly in stereo and shape reconstruction from multiple views. The other impediment was that the control problem for vision procedures was never properly addressed as an independent problem. This paper reviews the issues confronted by knowledge-directed vision systems, and concludes that inadequate vision procedures and the lack of a control formalism blocked their further development. We then briefly introduce several new projects which, although still in the early stage of development, are addressing the complex control issues that continue to obstruct the development of robust knowledge-directed vision systems.

A system has been developed to acquire, extend and refine 3D geometric site models from aerial imagery. This system hypothesizes potential building roofs in an image, automatically locates supporting geometric evidence in other images, and determines the precise shape and position of the new buildings via multiimage triangulation. Model-to-image registration techniques are applied to align new, incoming images against the site model. Model extension and refinement procedures are then performed to add previously unseen buildings and to improve the geometric accuracy of the existing 3D building models.>

Complex problems, such as driving, can be solved more easily by decomposing them into smaller subproblems, solving each sub-problem, and then integrating the solutions. In the case of an autonomous vehicle, the integrated system should be able to react in real time to a changing environment and to reason about ways to achieve its goals. This paper describes the approach taken on the UMass Mobile Perception Laboratory (MPL) to integrate independent processes (each solving a particular aspect of the navigation problem) into a fully capable autonomous vehicle. >

Computer vision researchers working in mobile robotics and other real-time domains are forced to confront issues not normally addressed in the computer vision literature. Among these are: communications or how to get data from one process to another; data storage and retrieval (primarily for transient image-based data); and database management for maps, object model and other permanent (typically 3D) data. This paper reviews efforts at CMU, SRI and UMass to build real-time computer vision systems for mobile robotics, and presents a new tool, called ISR3, for communications, data storage/retrieval and database management on the UMass Mobile Perception Laboratory (MPL), a NAVLAB-like autonomous vehicle.

The goal of image understanding by computer is to identify objects in visual images and (if necessary) to determine their location and orientation. Objects are identified by comparing data extracted from images to an a priori description of the object or object class in memory. It is a generally accepted premise that, in many domains, the timely and appropriate use of knowledge can substantially reduce the complexity of matching image data to object descriptions. Because of the variety and scope of knowledge relevant to different object classes, contexts and viewing conditions, blackboard architectures are well suited to the task of selecting and applying the relevant knowledge to each situation as it is encountered. This paper reviews ten years of work on the UMass VISIONS system and its blackboard-based high-level component, the schema system. The schema system could interpret complex natural scenes when given carefully crafted knowledge bases describing the domain, but its application in practice was limited by the problem of model (knowledge base) acquisition. Experience with the schema system convinced us that learning techniques must be embedded in vision systems of the future to reduce or eliminate the knowledge engineering aspects of system construction. The Schema Learning System (SLS) is a supervised learning system for acquiring knowledge-directed object recognition (control) strategies from training images. The recognition strategies are precompiled reactive sequences of knowledge source invocations that replace the dynamic scheduler found in most blackboard systems. Each strategy is specialized to recognize instances of a specific object class within a specific context. Since the strategies are learned automatically, the knowledge base contains only general-purpose knowledge sources rather than problem-specific control heuristics or sequencing information.

The variation, with respect to view, of 2D features defined for projections of 3D point sets and line segments is studied. It is established that general-case view-invariants do not exist for any number of points, given true perspective, weak perspective, or orthographic projection models. Feature variation under the weak perspective approximation is then addressed. Though there are no general-case weak-perspective invariants, there are special-case invariants of practical importance. Those cited in the literature are derived from linear dependence relations and the invariance of this type of relation to linear transformation. The variation with respect to view is studied for an important set of 2D line segment features: the relative orientation, size, and position of one line segment with respect to another. The analysis includes an evaluation criterion for feature utility in terms of view-variation. This relationship is a function of both the feature and the particular configuration of 3D line segments. The use of this information in objection recognition is demonstrated for difficult discrimination tasks.>

The findings of a workshop, the goals of which were to identify applications, research problems, and designs of high performance computing and communications (HPCC) systems for supporting applications are discussed. In computer vision, the main scientific issues are machine learning, surface reconstruction, inverse optics and integration, model acquisition, and perception and action. In speech and natural language processing (SNLP), issues were identified statistical analysis in corpus-based speech and language understanding, search strategies for language analysis, auditory and vocal-tract modeling, integration of multiple levels of speech and language analyses, and connectionist systems. In AI, important issues that need immediate attention include the development of efficient machine learning and heuristic search methods that can adapt to different architectural configurations, and the design and construction of scalable and verifiable knowledge bases, active memories, and artificial neural networks.>

Full-perspective mappings between 3-D objects and 2-D images are more complicated than weak-perspective mappings, which consider only rotation, translation, and scaling. Therefore, in 3-D model-based robot navigation, it is important to understand how and when full-perspective must be taken into account. A probabilistic combinatorial optimization algorithm is used to search for an optimal match between 3-D landmarks and 2-D image features. Three variations are considered. A weak-perspective algorithm rotates, translates, and scales an initial 2-D projection of the 3-D landmark. A full perspective selects a most promising alternative, but then updates the pose and reprojects the landmark. Like the full-perspective algorithm, the hybrid algorithm reliably recovers the true pose of the robot, and like the weak-perspective algorithm, it runs 5 to 10 faster than the full-perspective algorithm.>

The effective matching of a single 2D image of a cluttered scene to a library of multiple polyhedral models is achieved by organizing the 3D models into a network of descriptions of their 2D projections from expected views. The process of efficiently searching for image-model matches via a view description network is presented and demonstrated on images containing multiple objects and outdoor scenes. The experiments show that a recognition system based on view description networks is capable finding the correct matches to 3D objects in complex images with a potentially high level of efficiency.>

A computational framework for computing curvilinear structure on the edge data of images is presented. The method is symbolic, operating on geometric entities/tokens. It is also constructive, hierarchical, parallel, and locally distributed. Computation proceeds independently at each token and at each stage interleaves the discovery of structure with its careful description. The process yields a hierarchy of descriptions at multiple scales. These multiscale descriptions provide efficient feature indexing both for the grouping process itself as well as for subsequent recognition processes. Experimental results are presented to demonstrate the effectiveness of the approach with respect to curvilinear structure, and its application to more general grouping problems is discussed.>

A target location is represented by compressing a 360 degrees image from a spherical mirror into a circular waveform. Navigation tasks are specified as a sequence of homing tasks on target locations. This is accomplished by matching landmarks from the current view with the next target view. A method is provided for matching using qualitative geometric features of each of the waveforms. In addition, a geometric analysis allows one to do 3-D reasoning about the environment, which is sufficient for computing the rotation and translation between the current location and the target location. It eventually may allow acquisition of a 3-D model of the environment.>

A system that allows a robot to acquire a model of its environment and to use this model to navigate is described. The system maps the environment as a set of snapshots of the world taken at target locations. The robot uses an image-based local homing algorithm to navigate between neighboring target locations. Features of the approach include an imaging system that acquires a compact, 360 degrees representation of the environment and an image-based, qualitative homing algorithm that allows the robot to navigate without explicitly inferring three-dimensional structure from the image. The results of an experiment in a typical indoor environment are described, and its argued that image-based navigation is a feasible alternative to approaches using three-dimensional models.>

The problem of automatically learning knowledge-directed control strategies is considered. In particular, the authors address the problem of learning object-specific recognition strategies from object descriptions and sets of interpreted training images. A separate recognition strategy is developed for every object in the domain. The goal of each recognition strategy is to identify any and all instances of the object in an image, and give the 3-D position (relative to the camera) of each instance. The goal of the learning process is to build a strategy that minimizes the expected cost of recognition, subject to accuracy constraints imposed by the user.>

A local search optimization procedure, subset-convergent local search, is developed for identifying known 2D models in broken and skewed line data. Due to fragmentation in the data, the mapping between model and data line segments may be one-to-many. The proposed algorithm starts with a model-data mapping selected at random and refines it until it is locally optimal. Results are presented in which the algorithm frequency converges upon the globally optimal match. This best match can be found with greater confidence by independently running the algorithm several times. The match error being minimized has two basic components, a spatial fit error and an omission error. Spatial fit is a function of the integrated squared perpendicular distance between model lines and data line segments. This measure is minimized, subject to rotation, translation, and scaling, for every set of correspondences tested. The closed-form equation solving for this optimal transform is second order. Although the matching system itself is 2D, results are presented in which the matcher, in conjunction with a 3D robot navigation system, correctly updates estimates of robot position.>

Architectural research in support of knowledge-based computer vision is described. Efforts are focused on two major areas: the development of the image understanding architecture (IUA) and the benchmarking of parallel processors for vision. Two aspects of the IUA research are discussed. One is the development of the low-level processor chip, which integrates 64 one-bit (serial) processors, data caches, a communication network, and parallel interfaces to image input/output (I/O) hardware and the intermediate-level processors. The other is the ICAP, which is designed to manipulate tokens (symbolic descriptions of extracted image events and their associated attributes) at the intermediate level and to support database functions that allow access to these tokens. Work on an image understanding work bench is briefly described.>

There are two basic ways to improve the speed of a low-level vision algorithm: careful code optimization and selective processing. Reducing the computational effort expended on each pixel reduces the time required to process an image by a constant factor. Selective processing on a limited portion of an image using a focus of attention can decrease overall computation by orders of magnitude. A fast pixel-based algorithm is developed that uses these principles to achieve fast extraction of lines for use in vision-guided mobile robot navigation. It builds upon an algorithm for extracting lines by grouping pixels with similar gradient orientation. It allows parametric control of computational resources required to extract lines with particular characteristics.>

Given two parallel lines in a plane, their images formed by central projection onto the viewing plane intersect at a vanishing point, which provides a constraint on the orientation of the plane. Two such independent constraints define a vanishing line and thereby determine the orientation of the plane uniquely. In order to effectively use this information, an estimate of its accuracy must be incorporated. In the approach suggested, line directions and surface normal vectors are represented as points on a Gaussian sphere, and the error bounds are computed as regions on the sphere. Information from multiple vanishing points and surfaces is combined by intersecting the corresponding regions. In addition, constraints based on real-world knowledge can be introduced to improve the accuracy. Some experimental results on natural images re presented to illustrate this method.>

The authors report on the system and methods used by UMass Mobile Robot Project. Model-based processing of the visual sensory data is the primary mechanism used for controlling movement of an autonomous land vehicle through the environment, measuring progress towards a given goal, and avoiding obstacles. Goal-oriented navigation takes place through a partially modeled, unchanging environment that contains no unmodeled obstacles; this simplified environment provides a foundation for research in more complicated domains. The navigation system integrates perception, planning, and execution of actions. Of particular importance is that the planning processes are reactive and reason about landmarks that should be perceived at various stages of task execution. Correspondence between image features and expected landmark locations are used at several abstraction levels to ensure proper plan execution. The system and some experiments that demonstrate the performance of its components is described.>

The collection of image sequences for quantitative experiments in motion analysis is discussed. To assess the effectiveness of a motion algorithm it is necessary to obtain motion data with ground truth of known accuracy. The authors describe motion data collected using the imaging facilities provided by the autonomous land vehicle (ALV). A total of eight sequences of about 30 frames each were collected at five different outdoor sites using move-and-shoot and stop-and-shoot methods. For all the sequences accurate ground truth of environmental objects were determined using theodolites and a laser range finder. The camera egomotion parameters (this included both translation and rotation) were determined using a land navigation system on the ALV. Example images of the data set collected and an analysis of one of the sequences are presented.>

The authors present a computational approach to the extraction of straight lines based on the principles of perceptual organization. In particular, they consider how local information that is spatially distributed can be organized into a large-scale geometric structure in a computationally efficient manner. Symbolic tokens representing line segments and relations which are primarily geometric in nature and used to control a hierarchical grouping process. The relational measures on pairs of lines are based on collinearity, proximity, and similarity in contrast. The algorithm is implemented within a local, parallel, hierarchical framework for symbolic grouping that involves a cycle of linking, optimization, and replacement steps. Experimental results on a variety of natural scene images demonstrate effectiveness of the filtering and optimization stages in the extraction of straight lines. Issues in the development of a more general framework for symbolic grouping are also discussed.>

The VISIONS schema system provides a framework for building a general interpretation system as a distributed network of many small special-purpose interpretation systems. Each scheme is an 'expert' at recognizing one type of object. A discussion is presented of the problems of knowledge representation in a distributed A1 environments and the scheme system approach to those problems. A series of interpretation experiments have been performed on nine images from two natural scene domains; results from three images are presented.>

A benchmark is presented that was designed to evaluate the merits of various parallel architectures as applied to image understanding (IU). This benchmark exercise addresses the issue of system performance on an integrated set of tasks, where the task interactions that are typical of complex vision application are present. The goal of this exercise is to gain a better understanding of vision architecture requirements, which can be used to guide the development of the next generation of vision architectures.>

The process for fast extraction is divided into two steps: first, it looks for the areas where there might be ellipses by using heuristic function and a pyramid structure; then it finds the parameters of the ellipses in each area searched by a method that combines transformation of the feature space, projection, and optimum approximation approaches. Experiments indicate that both fast processing speed and suitable ellipse parameters are obtained.>

This paper presents a new approach to the extraction of straight lines in intensity images. Pixels are grouped into line-support regions of similar gradient orientation, and then the structure of the associated intensity surface is used to determine the location and properties of the edge. The resulting regions and extracted edge parameters form a low-level representation of the intensity variations in the image that can be used for a variety of purposes. The algorithm appears to be more effective than previous techniques for two key reasons: 1) the gradient orientation (rather than gradient magnitude) is used as the initial organizing criterion prior to the extraction of straight lines, and 2) the global context of the intensity variations associated with a straight line is determined prior to any local decisions about participating edge elements.

An algorithm that computes the best matching of two trees is described. The degree of mismatch, i.e., the distance, is measured in terms of the number of node splitting and merging operations required. The proposed tree distance is a more appropriate measurement of structural defonnation than the tree distance measure in terms of the number of insertions, deletions, and substitutions of tree nodes, as defined in previous studies. An algorithm that uses a divide-and-conquer strategy is presented. The analysis shows that the time complexity is O(NM2) where N and Al are the number of nodes of the two trees, respectively. The algorithm has been implemented on a VAX 11/780.

An image segmentation algorithm based on histogram clustering and probabilistic relaxation labeling is explored. The algorithm is evaluated by means of a set of artificially generated test images with known parameters. Two sources of pixel labeling errors are revealed. The first derives from distribution overlap in the histogram and leads to fragmented or missing regions in a segmentation. The second derives from the gloal nature of the compatibility coefficients used in the relaxation process. The coefficients are shown to be insufficient to correct certain labeling errors and can even cause the destruction of fine image details during the course of the relaxation updating process. A potential solution to these problems is shown to be obtainable by using orientation dependent compatibility coefficients and localizing the scope of the algorithm to small subimages followed by a merging of the segmented subimages.

Recently, while considering the connection of a 48 bit word computer to a 16 bit computer, we felt the need for a fast and inexpensive device that would multiply a binary address by a factor of three. Since 3N = N + 2N, there is an obvious solution of providing a normal adder circuit and presenting one set of inputs with N and the other with N-shifted left one place. But, there is a great deal of redundancy here since knowing one input we have complete knowledge of the other.

A conceptual framework for applying artificial intelligence (AI) techniques in computer-assisted instruction (CAI) is described. The student progresses through four phases (``faces'') of interaction with the computer acting as ``benevolent mentor,'' ``cognizant tool,'' ``problem-solving partner,'' and ``learner.'' The first phase serves to introduce the problem space, with the computer initiating as well as responding to inquiries. In the second phase, the computer provides the student with a set of tools which amplify his problem-solving ability. The third phase employs the computer as a partner, supporting a joint problem-solving endeavor. Finally, the computer plays the role of a learner, and the student learns by teaching it how to solve new problems. Each phase has an analog in general problem-solving techniques, namely, problem representation, heuristic search, directed search, and formal algorithmic expression. Taken together, the four phases comprise an integrated educational system for using AI in CAI. The system is illustrated within the problem space of cryptography, and applications to several other subject areas are cited.

The effectiveness of various forms of contextual information in a postprocessing system for detection and correction of errors in words is examined. Various algorithms utilizing context are considered, from a dictionary algorithm which has available the maximum amount of information, to a set of contextual algorithms utilizing positional binary n-gram statistics. The latter information differs from the usual n-gram letter statistics in that the probabilities are position-dependent and each is quantized to 1 or 0, depending upon whether or not it is nonzero. This type of information is extremely compact and the computation for error correction is orders of magnitude less than that required by the dictionary algorithm.

This note investigates the increase in parallel execution rate as a function of the size of an instruction dispatch stack with lookahead hardware. Under the constraint that instructions are not dispatched until all preceding conditional branches are resolved, stack sizes as small as 2 or 4 achieve most of the parallelism that a hypothetically infinite stack would.

This note reports the results of an examination of seven programs originally written for execution on a conventional computer (CDC-3600). We postulate an infinite machine, one with an infinite memory and instruction stack, infinite registers and memory, and an infinite number of functional units. This machine wiU exectite a program in parallel at maximum speed by executing each instruction at the earliest possible moment.

The static and dynamic utilization of a set of machine op-codes is examined. Two measures of the effective use of machine instructions are discussed and applied to samples of hand-coded programs and object code.

This paper describes a special-purpose character recognition system which uses contextual information for the recognition of words from any given dictionary of words. Previous techniques that utilized context involved letter transition probabilities of digrams and trigrams. This research introduces the concept of binary digrams which overcomes some of the problems of past approaches. They can be used to extract offectively the "syntax" of the dictionary while requiring very modest amounts of storage. A computationally feasible procedure is described which allows the accuracy requirements of the character recognizer to be relaxed if it is followed by a contextual postprocessor. The modified recognition system is allowed to output several alternatives for each character, while the postprocessor selects the proper string of characters by having access to both the dictionary and the dictionary syntax. A theoretical estimate of the recognition rate is derived, and experimental results demonstrate the ability of the system to achieve low error and rejection rates.

The extraction of features for the purpose of reconstituting a pattern set may be particularly useful in those cases where a large number of patterns can be decomposed into a relatively small set of sub-patterns. By the representation of pattern and feature sets as matrices, the concept of feature determination has been extended to multilevel features and the hierarchical organization of logical networks employing these features. An algorithm is presented to sequentially generate features by an adaptive process of altering weights in a network of thresholdlike logical elements. Experimental results indicate the potential of the algorithm in organizing a recognition network to correspond to the information structure of the pattern set.

A modification of Akers' method of realizing Boolean functions with three-input majority gates is presented. One of the fundamental parts in Akers' procedure is the construction of a logically passive self-dual, or LPSD. This paper presents a more precise construction of the LPSD. In addition, a procedure is described to adapt the method to minimization of the number of delay elements. A delay element table is introduced to aid in the selection of majority gates. A second factor in reducing delay elements is limiting the number of levels of logic in the realization. Examples illustrate the substantial reduction in delay elements when these methods are employed.