In moving camera videos, motion segmentation is commonly performed using the image plane motion of pixels, or optical flow. However, objects that are at different depths from the camera can exhibit different optical flows even if they share the same real-world motion. This can cause a depth-dependent segmentation of the scene. Our goal is to develop a segmentation algorithm that clusters pixels that have similar real-world motion irrespective of their depth in the scene. Our solution uses optical flow orientations instead of the complete vectors and exploits the well-known property that under camera translation, optical flow orientations are independent of object depth. We introduce a probabilistic model that automatically estimates the number of observed independent motions and results in a labeling that is consistent with real-world motion in the scene. The result of our system is that static objects are correctly identified as one segment, even if they are at different depths. Color features and information from previous frames in the video sequence are used to correct occasional errors due to the orientation-based segmentation. We present results on more than thirty videos from different benchmarks. The system is particularly robust on complex background scenes containing objects at significantly different depths.

In many algorithms for background modeling, a distribution over feature values is modeled at each pixel. These models, however, do not account for the dependencies that may exist among nearby pixels. The joint domain-range kernel density estimate (KDE) model by Sheikh and Shah [7], which is not a pixel-wise model, represents the background and foreground processes by combining the three color dimensions and two spatial dimensions into a five-dimensional joint space. The Sheikh and Shah model, as we will show, has a peculiar dependence on the size of the image. In contrast, we build three-dimensional color distributions at each pixel and allow neighboring pixels to influence each other’s distributions. Our model is easy to interpret, does not exhibit the dependency on image size, and results in higher accuracy. Also, unlike Sheikh and Shah, we build an explicit model of the prior probability of the background and the foreground at each pixel. Finally, we use the adaptive kernel variance method of Narayana et al. [5] to adapt the KDE covariance at each pixel. With a simpler and more intuitive model, we can better interpret and visualize the effects of the adaptive kernel variance method, while achieving accuracy comparable to state-of-the-art on a standard backgrounding benchmark. 1

Recent work on background subtraction has shown developments on two major fronts. In one, there has been increasing sophistication of probabilistic models, from mixtures of Gaussians at each pixel [7], to kernel density estimates at each pixel [1], and more recently to joint domainrange density estimates that incorporate spatial information [6]. Another line of work has shown the benefits of increasingly complex feature representations, including the use of texture information, local binary patterns, and recently scale-invariant local ternary patterns [4]. In this work, we use joint domain-range based estimates for background and foreground scores and show that dynamically choosing kernel variances in our kernel estimates at each individual pixel can significantly improve results. We give a heuristic method for selectively applying the adaptive kernel calculations which is nearly as accurate as the full procedure but runs much faster. We combine these modeling improvements with recently developed complex features [4] and show significant improvements on a standard backgrounding benchmark.

In this paper, a multi-agent search scheme is presented that supports the recognition of activities and, thus, learning methods for cooperative human-robot interaction. In our approach, stochastic models of human search activity are used to estimate state for HRI. The robot updates a Probabilistic Distribution Function of the target object using the observations and the estimated state of human peers. By this means the robot can choose places to search to compensate the behavior of human peers. This paper also presents an implicit interface design for robot assisted tasks, which allows the robot to infer the intention of the user and to provide assistance autonomously. It reduces the cognitive workload of the user and therefore is useful for elder care applications. The effectiveness and the efficiency of the proposed approaches are demonstrated in the experimental results.

This paper describes our experiences with the first partial deployment of Presentations Automatically Organized from Lectures (PAOL), a lecture recording system developed and tested at the University of Massachusetts Amherst. PAOL automatically records all information presented during lectures using any combination of computer, whiteboard, and overhead presentation and compiles the captured lectures into indexed presentations. We discuss lessons learned from this deployment that have application in lecture recording specifically and classroom technology in general. We also discuss our initial evaluation of created presentations as determined by a small focus group study.

In this paper we present the design of a decentralized vision-based object search system that can be used for elder care in a smart environment. In our approach, each autonomous search agent maintains separate estimates of the probability density function (PDF) of the object location and makes independent decisions about its search process. Asynchronous cooperative search is achieved by transmitting perceptual information among the agents. Our work also investigates how context such as the detection history and density of activity by people influence the estimation of the prior PDF of the target and the use of this information to improve the search efficiency. Our experimental results demonstrate that the proposed cooperative search strategy is efficient and the methods we use to incorporate contextual information into the target's posterior PDF can improve the efficiency further.

Scene text recognition (STR) is the recognition of text anywhere in the environment, such as signs and storefronts. Relative to document recognition, it is challenging because of font variability, minimal language context, and uncontrolled conditions. Much information available to solve this problem is frequently ignored or used sequentially. Similarity between character images is often overlooked as useful information. Because of language priors, a recognizer may assign different labels to identical characters. Directly comparing characters to each other, rather than only a model, helps ensure that similar instances receive the same label. Lexicons improve recognition accuracy but are used post hoc. We introduce a probabilistic model for STR that integrates similarity, language properties, and lexical decision. Inference is accelerated with sparse belief propagation, a bottom-up method for shortening messages by reducing the dependency between weakly supported hypotheses. By fusing information sources in one model, we eliminate unrecoverable errors that result from sequential processing, improving accuracy. In experimental results recognizing text from images of signs in outdoor scenes, incorporating similarity reduces character recognition error by 19 percent, the lexicon reduces word recognition error by 35 percent, and sparse belief propagation reduces the lexicon words considered by 99.9 percent with a 12X speedup and no loss in accuracy.

We present a semi-Markov model for recognizing scene text that integrates character and word segmentation with recognition. Using wavelet features, it requires only approximate location of the text baseline and font size; no binarization or prior word segmentation is necessary. Our system is aided by a lexicon, yet it also allows non-lexicon words. To facilitate inference with a large lexicon, we use an approximate Viterbi beam search. Our system performs robustly on low-resolution images of signs containing text in fonts atypical of documents.

This paper presents the design and implementation of a dual-camera sensor network that can be used as a memory assistant tool for assisted living. Our system performs energy-efficient object detection and recognition of commonly misplaced objects. The novelty in our approach is the ability to tradeoff between recognition accuracy and computational efficiency by employing a combination of low complexity but less precise color histogram-based image recognition together with more complex image recognition using SIFT descriptors. In addition, our system can seamlessly integrate feedback from the user to improve the robustness of object recognition. Experimental results reveal that our system is computation-efficient and adaptive to slow changes of environmental conditions.

We describe whiteboard content capture system from Presentations Automatically Organized from Lectures(PAOL) that captures content within the setting of a classroom environment. The system acquires a sequence of images from high-resolution, fixed view cameras and extracts a series of content-rich key frames. The key frames are derived by analyzing the camera images of the front of the room, selecting images that show the progression of the presented material (writing, projected images), digitally removing the speaker's image, and enhancing the images for greater legibility. These images can be distributed in real time or stored and later synchronized with other content (video, computer capture). The system requires no specialized hardware other than fixed-field-of-view cameras, is transparent to the lecturer, and handles both whiteboard and projected presentations. The system extracts on average approximately 70 key frames from roughly 70000 images captured during a 75-minute presentation and runs at close to real time.

This paper describes a system designed to automatically capture classroom events as videos and images. This content is delivered in several ways, most commonly as indexed multimedia presentations but also in real time as notes of classroom events. This content creation system identifies when significant events occur, e.g., material presented by computer and projected on a screen or written on a standard whiteboard, and saves these events as enhanced images. In parallel with the whiteboard capture, a digitally-zoomed video of the speaker is created. The significant event images (from cameras and computers) are used to create an index into the video and the images, video and index are complied into a Flash presentation. These presentations are used by on-campus or distance students. The event images can also be stored and exported to a Ubiquitous Presenter-style server that provides students with real-time, in-class access. The event images and video are recorded transparently to the lecturer. The lecturer need not make any modifications to teaching style or modality (whiteboard, computer-based presentation, or a combination). The primary focus of this paper is on event image and video capture techniques. The lecture capture system has great benefits for education and we report some initial experience using it in support of computer science curricula.

Using a lexicon can often improve character recognition under challenging conditions, such as poor image quality or unusual fonts. We propose a flexible probabilistic model for character recognition that integrates local language properties, such as bigrams, with lexical decision, having open and closed vocabulary modes that operate simultaneously. Lexical processing is accelerated by performing inference with sparse belief propagation, a bottom-up method for hypothesis pruning. We give experimental results on recognizing text from images of signs in outdoor scenes. Incorporating the lexicon reduces word recognition error by 42% and sparse belief propagation reduces the number of lexicon words considered by 97%.

This paper presents the design, implementation and evaluation of a distributed network of smart cameras whose function is to detect and localize falls, an important application in elderly living environments. A network of overlapping smart cameras uses a decentralized procedure for computing inter-image homographies that allows the location of a fall to be reported in 2D world coordinates by calibrating only one camera. Also, we propose a joint routing and homography transformation scheme for multi-hop localization that yields localization errors of less than 2 feet using very low resolution images. Our goal is to demonstrate that such a distributed low-power system can perform adequately in this and related applications. A prototype implementation is given for low-power Agilent/UCLA Cyclops cameras running on the Crossbow MICAz platform. We demonstrate the effectiveness of the fall detection as well as the precision of the localization using a simulation of our sample implementation.

We describe an automatic classroom capture system that detects and records significant (stable) points in lectures by sampling and analyzing a sequence of screen capture frames from a PC used for presentations, application demonstrations, etc. The system uses visual inspection techniques to scan the screen capture stream to identify points to store. Unlike systems that only detect and store slide presentation transitions, this system detects and stores significant frames in any style of lecture using any program. The system is transparent to the lecturer and requires no software or training. It has been tested extensively on lectures with multiple applications and pen-based annotations and has successfully identified "significant" frames (frames that represent stable events such as a new slide, bullet, figure, inked comment, drawing, code entry, application entry etc.). The system can analyze over 20000 frames and typically identifies and stores about 100 significant frames within minutes of the end of a lecture. A time stamp for each saved frame is recorded and will in the future be used to compile these frames into a jMANIC multimedia record of the class

In this paper we address the problem of fusing images from many video cameras or a moving video camera. The captured images have obvious motion parallax, but they will be aligned and integrated into a few mosaics with a large field-of-view (FOV) that preserve 3D information. We have developed a geometric representation that can re-organize the original perspective images into a set of parallel projections with different oblique viewing angles. In addition to providing a wide field of view, mosaics with various oblique views well represent occlusion regions that cannot be seen in a usual nadir view. Stereo pair(s) can be formed from a pair of mosaics with different oblique viewing angles and thus image-based 3D viewing can be achieved. This representation can be used as both an advanced video interface and a pre-processing step for 3D reconstruction.

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 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.

In this paper a compact representation, 3D Layered, Adaptive-resolution and Multi-perspective Panorama (LAMP), is proposed for representing large scale and 3D scenes with occlusion. Two kinds of 3D LAMP representations are constructed, i.e. the relief-like LAMP and the image-based LAMP, both of which concisely represent almost all the information from a long image sequence. The relief-like LAMP is basically a single extended multi-perspective panoramic view image with both texture and depth values, but each pixel has multiple values to represent results of occlusion recovery and resolution enhancement. The image-based LAMP, on the other hand, consists of a set of multi-perspective layers, each of which has both texture and depth maps, with adaptive time-sampling scales depending on depths of scene points. Several examples of 3D LAMP construction for real image sequences are given. The 3D LAMP is a concise and powerful representation for image-based rendering.

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.

We propose an elevation-based approach to parking lot structure analysis from aerial imagery. In contrast to image-based methods, the new approach treats parked vehicles as 3-D microstructures and attempts to locate them in the elevation domain. The STME (Surface Texture and Microstructure Extraction) system is applied to the elevation map to extract the 3-D microstructures. A hybrid application of this system to both intensity and elevation maps results in a complete extraction of individual vehicles. Based on a comparison of texture exploitation techniques, a WCC (weighted combination criterion) algorithm is presented to generate a clean parking lot ground surface, which facilitates visualization and simulation of parking lot activities with a high degree of visual realism.

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.

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.

We present a surface texture and microstructure extraction system to provide added realism in visualization and virtual reality applications. The system uses multiple images, 3-D models and camera information, in addition to knowledge about man-made structures, to cope with problems such as perspective distortion, data deficiency, and corruption caused by shadows and occlusions. Combined with the Ascender site modeling system and scene rendering algorithms, the system is typically useful for urban site model refinement and visualization.

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.

Three different algorithms for mobile robot vision-based obstacle detection are presented in this paper each based on different assumptions The first two algorithms are qualitative in that they return only yes/no answers regarding the presence of obstacles in the field of view; no 3D reconstruction is performed. They have the advantage of fast determination of the existence of obstacles in a scene based on the solvability of a linear system. The first algorithm uses information about the ground plane, while the second only assumes that the ground is planar. The third algorithm is quantitative in that it continuously estimates the ground plane and reconstructs partial 3D structures by determining the height above the ground plane of each point in the scene. Experimental results are presented for real and simulated data, and the performance of the three algorithms under different noise levels is compared in simulation. We conclude that in terms of the robustness of performance, the third algorithm is superior to the other two.

This paper addresses the general 3-D rigid motion problem, where the point correspondences and the motion parameters between two sets of 3-D points are to be recovered. The existence of missing points in the two sets is the most difficult problem. We first show a mathematical symmetry in the solutions of rotation parameters and point correspondences. A closed-form solution based on the correlation matrix eigenstructure decomposition is proposed for correspondence recovery with no missing points. Using a heuristic measure of point pair affinity derived from the eigenstructure, a weighted bipartite matching algorithm is developed to determine the correspondences in general cases where missing points occur. The use of the affinity heuristic also leads to a fast outlier removal algorithm, which can be run iteratively to refine the correspondence recovery. Simulation results and experiments on real images are shown in both ideal and general cases.

The Art Gallery Problem is the problem of determining the number of observers necessary to cover an art gallery room such that every point is seen by at least one observer. This problem is well known and has a linear solution for the 2 dimensional case, but little is known in the 3-D case. In this paper we present a polynomial time solution for the 3-D version of the Art Gallery problem. Because the problem is NP-hard, the solution presented is an approximation, and we present the bounds to our solution. Our solution uses techniques from computational geometry, graph coloring and set coverage. A complexity analysis is presented for each step and an analysis of the overall quality of the solution is given.

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. >

Researchers in computer vision have primarily studied the problem of visual reconstruction of environmental structure that is plainly visible. In this paper, the conventional goals of visual reconstruction are generalized to include both visible and occluded forward facing surfaces. This larger fraction of the environment is termed the anterior surfaces. In this paper, we show that the boundaries of the anterior surfaces can be represented in viewer-centered coordinates as a labeled knot diagram. Where boundaries are not occluded and where surface reflectance is distinct from that of the background, boundaries will be marked by image contours. However, where boundaries are occluded, or where surface reflectance matches background reflectance, there will be no detectable luminance change in the image. Deducing the complete image trace of the boundaries of the anterior surfaces under these circumstances is termed the figural completion problem. The second half of this paper describes a computational theory of figural completion. A working model is demonstrated on a variety of illusory contour displays. The experimental system employs a two stage process of completion hypothesis and combinatorial optimization. The labeling scheme is enforced by integer linear inequalities so that the optimal feasible solution of an integer linear program defines a typologically valid surface organization.>

Three different algorithms for qualitative obstacle detection are presented in this paper. Each one is based on different assumptions. The first two algorithms are aimed at yes/no obstacle detection without indicating which points are obstacles. They have the advantage of fast determination of the existence of obstacles in a scene based on the solvability of a linear system. The first algorithm uses information about the ground plane, while the second algorithm only assumes that the ground is planar. The third algorithm continuously estimates the ground plane, and based on that determines the height of each matched point in the scene. Experimental results are presented for real and simulated data, and performances of the three algorithms under different noise levels are compared in simulation. We conclude that in terms of the robustness of performance, the third one works best.>

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.

Complex problems, such as driving, can be solved by decomposing them into simpler sub-problems, 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.

A practical real-time system for passive obstacle detection and avoidance is presented. Range information is obtained from stereo images by first computing a disparity picture from the image pair and extracting points above the ground plane. Then these points are projected onto the ground plane and an Instantaneous Obstacle Map (IOM) is obtained. The IOM is transformed into a one dimensional steering vector that represents the hindrance associated with steering in a particular direction and then a one dimensional search is performed on the steering vector for an angle with least hindrance. The steering direction and hindrance value are used to set the speed of the vehicle. This system has been implemented on the Mobile Perception Lab (MPL) at University of Massachusetts at Amherst with considerable success, running at 2 Hz for 256/spl times/240 sized images.>

In structure from motion algorithms, the error in the estimated motion affects each reconstructed 3-D point in a systematic way. The authors attempt to isolate the effect of the motion error as correlations in the structure error and show theoretically that these correlations can improve existing multi-frame structure from motion techniques. Experimental results and previously reported work confirm the theoretical predictions.>

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.

A new technique for reconstructing the 3-D structure and motion of a scene undergoing relative rotational motion with respect to the camera is discussed. Given image correspondences of point features tracked over many frames, a two-stage technique for reconstruction is presented. A grouping algorithm that exploits spatio-temporal constraints of the common motion to achieve a reliable description of discrete point correspondences as curved trajectories in the image plane is developed. In contrast, trajectories fitted to points independent of each other lead to arbitrary image descriptions and very inaccurate 3-D parameters. A new closed-form solution, under perspective projection, for the 3-D motion and location of points from the computed image trajectories is also presented. Both stages are applied to real image sequences with good results. This approach represents a first step in a longer-term research effort examining the role of explicit spatio-temporal organization in the interpretation of scenes from dynamic images.>

Automatic building 3D models of objects and scenes from a sequence of 2D monocular images is approached by first building a partial model (possibly noisy) and then extending and refining it. The initial model is built by tracking and reconstructing shallow structures over a sequence of images using the constraint of affine trackability. This model is subsequently used to compute the pose that relates the model coordinate system and the camera coordinate system of the image frames in the sequence. The unmodeled 3D features (those not recovered by the shallow structure reconstruction) are tracked over the image sequence and their 3D locations recovered by a pseudotriangulation process. The triangulation process is also used to make new 3D measurements of the initial model points. These measurements are then fused with the previous estimates to refine the set of initial model points.>

The history of the image understanding environment (IUE) project, a five-year program to develop a common software environment for the development of algorithms and application systems, is reviewed. An overview of some of the data structures that are currently evolving as a specification for the IUE is provided. The ultimate goal of the project is to provide the basic data structures and algorithms that are required to carry state-of-the-art research in image understanding.>

Potential obstacles in the path of a mobile robot that can often be characterized as shallow (i.e., their extent in depth is small compared to their distance from the camera) are considered. The constraint of affine trackability is applied to automatic identification and 3-D reconstruction of shallow structures in realistic scenes. It is shown how this approach can handle independent object motion, occlusion, and motion discontinuity. Although the reconstructed structure is only a frontal plane approximation to the corresponding real structure, the robustness of depth of the approximation might be useful for obstacle avoidance, where the exact shape of an object may not be of consequence so long as collisions with it can be avoided.>

A framework is presented for segmenting shallow structures from their background over a sequence of images. Shallowness is first quantified as affine describability. This is embedded in a tracking system within which hypothesized model structures undergo a cycle of prediction and model-matching. Structures emerge either as shallow or non-shallow based on their affine trackability. This paper rejects continuity heuristics for purely image motion in favor of temporal continuity defined as the consistency of generic 3-D models, namely shallow structures.>

A study is made of the effect of errors in estimates of the image center and focal length on pose refinement and other related (3-D inference from 2-D images) problems/algorithms. The authors show that for 'small' field of view imaging systems, incorrect knowledge of the camera center does not affect the determination of the location of the camera significantly. Incorrect estimates of the focal length only significantly affect the determination of the z-component (i.e. parallel to the optical axis) of the translation in camera coordinates. The output of the pose refinement algorithm is used to calculate the relative orientation between the coordinate frames of the same camera in two or more different positions as a prelude to computation of 3-D depths of new points by pseudo-triangulation. A model of error for this depth based on the amount of error in placing the image center conforms to the errors obtained for experiments with synthetic and real data. New points are located to an average accuracy of 1.5 mm and 0.3 ft for the two real image sequences respectively.>

A novel technique is presented for reconstructing the 3-D structure, and motion, of a scene undergoing relative rotational motion with respect to the camera. Given image correspondences of point features tracked over many frames, first, a grouping algorithm developed which exploits spatio-temporal constraints of the common motion to achieve a reliable description of discrete point correspondences as curved trajectories (general conics in the case of rotational motion) in the image plane. In contrast, trajectories fitted to points independent of each other lead to arbitrary image descriptions and very inaccurate 3-D parameters. Second, a novel closed-form solution, under perspective projection, for the 3-D motion and location of points from the computed image trajectories is presented. Both stages are applied to real image sequences with good results.>

The problem of goal-oriented navigation of an autonomous robot vehicle through a partially modeled unchanging environment which contains no unmodeled obstacles is discussed. This simplified environment provides a foundation for research in more complicated domains. Perception, planning, and execution of actions are integrated into a reactive system which reasons about landmarks that should be perceived at various stages of task execution. Perceptual servoing uses correspondences between image features and expected landmark locations to ensure proper plan execution and to maintain the relationship between the system's internal model and the environment. This system is described, and experimental results which demonstrate the efficacy of perceptual servoing are presented.>

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.>

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 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.>

MOTION IN THE ENVIRONMENT MANIFESTS ITSELF IN CHANGES OF MANY KINDS, NOT JUST IMAGE PLANE VELOCITIES, YET THESE ARE ALL THAT AN OPTICAL FLOW FIELD MAKES EXPLICIT. WE VIEW OPTICAL FLOW AS A USEFUL LOW-LEVEL REPRESENTATION FROM WHICH A SYMBOLIC DESCRIPTION OF CHANGE, IN THE FORM OF TOKEN MATCHES, CAN BE COMPUTED. THE TOKENS OF INTEREST TO US ARE THOSE PRODUCED BY PERCEPTUAL ORGANIZATION PROCESSES, AND ARE MORE ABSTRACT THAN EDGES OR INTEREST POINTS. WE DEMONSTRATE A WORKING SYSTEM FOR MATCHING LINE TOKENS WHICH USES THE OPTICAL FLOW FIELD IN A HEURISTIC MANNER TO LIMIT THE SEARCH FOR THE `MINIMAL BIPARTITE COVER'' OF THE SET OF TOKENS FROM EACH FRAME. AS AN EXAMPLE APPLICATION, WE DEMONSTRATE A TECHNIQUE FOR COMPUTING DISTANCE TO ENVIRONMENTAL SURFACES SUITABLE FOR OBSTACLE RECOGNITION BY A MOBILE ROBOT. ACCURATE KNOWLEDGE OF THE CAMERA MOTION PARAMETERS IS NOT REQUIRED. WE DESCRIBE HOW MOTION IN DEPTH MANIFESTS ITSELF IN THE PROJECTED LENGTHS AND AREAS OF ENVIRONMENTAL SURFACES WHOSE EXTENT IN DEPTH IS SMALL RELATIVE TO THEIR DISTANCE FROM THE CAMERA. RESULTS ON TWO SEQUENCES TAKEN BY A MOBILE ROBOT ARE PRESENTED TO DEMONSTRATE THE ACCURACY OF THE METHOD.

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.

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.