This article introduces the notion of carelessness level into robot action planners such that the safety and efficiency are optimized. The core idea is to make the robot’s plan less sensitive to the behavior of careless humans who may inattentively violate safety constraints and degrade efficiency. More precisely, our planner reduces the opportunities given to the careless humans to put themselves in danger and hamper the efficiency of the robot’s plan. The effectiveness of the proposed planner is demonstrated through simulation studies on a packaging line and on a collaborative assembly line. Results show that the proposed scheme can improve efficiency and safety in both examples.

This work introduces an affordance characterization employing mechanical wrenches as a metric for predicting and planning with workspace affordances. Although affordances are a commonly used high-level paradigm for robotic task-level planning and learning, the literature has been sparse regarding how to characterize the agent in this object-agent-environment framework. In this work, we propose decomposing a behavior into a vocabulary of characteristic requirements and capabilities that are suitable to predict the affordances of various parts of the workspace. Specifically, we investigate mechanical wrenches as a viable representation of these affordance requirements and capabilities. We then use this vocabulary in a planning system to compose complex motions from simple behavior types in continuous space. The utility of the framework for complex planning is demonstrated on example scenarios both in simulation and with real-world industrial manipulators.

We address the problem of predicting the physical state of a an agent performing a known activity. In particular we are interested in predicting human movement during complex composite activities. Our proposed framework combines a graphical model that extends the Sequential Interval Network (SIN) [1] for modeling global temporal structure of activities with a low level dynamic system for modeling the dynamics of the physical state. Specifically, two sets of new hidden state variables are added: one with respect to the temporal structure and one with respect to time. A mapping factor is defined to ensure these variables values remain consistent and hence allows fusing the two sources of information. We then derive an inference algorithm for computing the posterior densities of the hidden variables. The system can run in an on-line predictive mode to recognize on-going activity and make predictions arbitrarily far in the future during execution of the activity. Experiments illustrate that the long term prediction performance benefits from the knowledge about the temporal structure of the activity while short term prediction performance is improved by incorporating the dynamics of physical state.

We propose a probabilistic method for parsing a temporal sequence such as a complex activity defined as composition of sub-activities/actions. The temporal structure of the high-level activity is represented by a string-length limited stochastic context-free grammar. Given the grammar, a Bayes network, which we term Sequential Interval Network (SIN), is generated where the variable nodes correspond to the start and end times of component actions. The network integrates information about the duration of each primitive action, visual detection results for each primitive action, and the activity's temporal structure. At any moment in time during the activity, message passing is used to perform exact inference yielding the posterior probabilities of the start and end times for each different activity/action. We provide demonstrations of this framework being applied to vision tasks such as action prediction, classification of the high-level activities or temporal segmentation of a test sequence, the method is also applicable in Human Robot Interaction domain where continual prediction of human action is needed.

A representation for structured activities is developed that allows a robot to probabilistically infer which task actions a human is currently performing and to predict which future actions will be executed and when they will occur. The goal is to enable a robot to anticipate collaborative actions in the presence of uncertain sensing and task ambiguity. The system can represent multi-path tasks where the task variations may contain partially ordered actions or even optional actions that may be skipped altogether. The task is represented by an AND-OR tree structure from which a probabilistic graphical model is constructed. Inference methods for that model are derived that support a planning and execution system for the robot which attempts to minimize a cost function based upon expected human idle time. We demonstrate the theory in both simulation and actual human-robot performance of a two-way-branch assembly task. In particular we show that the inference model can robustly anticipate the actions of the human even in the presence of unreliable or noisy detections because of its integration of all its sensing information along with knowledge of task structure.

A novel behavior representation is introduced that permits a robot to systematically explore the best methods by which to successfully execute an affordance-based behavior for a particular object. The approach decomposes affordance-based behaviors into three components. We first define controllers that specify how to achieve a desired change in object state through changes in the agent's state. For each controller we develop at least one behavior primitive that determines how the controller outputs translate to specific movements of the agent. Additionally we provide multiple perceptual proxies that define the representation of the object that is to be computed as input to the controller during execution. A variety of proxies may be selected for a given controller and a given proxy may provide input for more than one controller. When developing an appropriate affordance-based behavior strategy for a given object, the robot can systematically vary these elements as well as note the impact of additional task variables such as location in the workspace. We demonstrate the approach using a PR2 robot that explores different combinations of controller, behavior primitive, and proxy to perform a push or pull positioning behavior on a selection of household objects, learning which methods best work for each object.

We propose a novel method for a robot to separate and segment objects in a cluttered tabletop environment. The method leverages the fact that external object boundaries produce visible edges within an object cluster. We achieve this singulation of objects by using the robot arm to perform pushing actions specifically selected to test whether particular visible edges correspond to object boundaries. We verify the separation of objects after a push by examining the clusters formed by geometric segmentation of regions residing on the table surface. To avoid explicitly representing and tracking edges across push behaviors we aggregate over all edges in a given orientation by representing the push-history as an orientation histogram. By tracking the history of directions pushed for each object cluster we can build evidence that a cluster cannot be further separated. We present quantitative and qualitative experimental results performed in a real home environment by a mobile manipulator using input from an RGB-D camera mounted on the robot's head. We show that our pushing strategy can more reliably obtain singulation in fewer pushes than an approach, that does not explicitly reason about boundary information.

We present a method to locate animals in video based on their reported positions using noisy and biased measurements from a radio frequency identification (RFID) system. The system uses a kernel regression method to learn a mapping from reported X, Y, Z locations in the environment to X, Y pixel locations in video with minimal calibration and training data. Our goal is for this system to facilitate animal behavior research by enabling automatic identification of interactions between animals and then providing the location of the animals in video so that the details of each interaction can be examined more closely by either humans or machines. The primary contribution of this work is achieving efficient and reliable 3D to 2D projective mapping in a non-parametric way while also overcoming challenges that would otherwise affect accuracy. Our system successfully addresses issues regarding noisy positional data, position bias, occlusion of RFID tags, and wide angle lens distortion. We validate the system experimentally indoors as well as in the field and compare the accuracy of our system with the standard camera projection model-based procedure.

We present a novel method for the visual detection of a contingent response by a human to the stimulus of a robot action. Contingency is defined as a change in an agent's behavior within a specific time window in direct response to a signal from another agent; detection of such responses is essential to assess the willingness and interest of a human in interacting with the robot. Using motion-based features to describe the possible contingent action, our approach assesses the visual self-similarity of video subsequences captured before the robot exhibits its signaling behavior and statistically models the typical graph-partitioning cost of separating an arbitrary subsequence of frames from the others. After the behavioral signal, the video is similarly analyzed and the cost of separating the after-signal frames from the before-signal sequences is computed; a lower than typical cost indicates likely contingent reaction. We present a preliminary study in which data were captured and analyzed for algorithmic performance.

Summary form only given. An analytical expression for the uniform midrise quantizer function can be written as a sum of the input and a residual sawtooth wave. We propose an equivalent but alternate approach. Although it is well known that no clever mathematical manipulation can yield extra information, nevertheless, an alternate form of expression can and has on several occassions proven useful.

In this paper, we propose a real time, robust contour tracker for vehicles in IR images captured from an aerial moving camera. Lack of a background model, lack of a motion model and lack of any training data make the job challenging, but realistic. We compare a standard approach of contour evolution using energy minimization in the snakes algorithm with our Harris corner based Elliptical Fourier contour representation. We show that our approach produces better results and is robust to different initialization strategies.

In this paper, we discuss methods to enable robust surveillance on compressed video. We show that if the particular surveillance algorithm that is likely to be run on the compressed video is known a priori, then steps can be taken during the encoding process to facilitate the performance of the algorithm. We show that by performing signal processing on the input video signal before it is encoded, or by adaptively changing the parameters of the encoding process, we can make the resulting signal more robust to degradations in the encoding process. The result is better and more consistent tracking on the compressed video from high to low bitrates, but with some loss in PSNR. We demonstrate the validity of this approach for mean shift tracking running on MPEG-4 coded video.

In this paper, our goal is to understand what needs to be done to enable computer vision algorithms running on uncompressed image sequences to run as well on image sequences that have undergone compression and then decompression. The central conflict of context based computer vision algorithms versus the structured block based approach of today's codecs means that more has to be done than to simply create a divide between coding foreground preferentially and giving less importance to background. We take as example, a single computer vision algorithm, the mean shift tracker and see that its performance can be improved substantially in low bit rate scenarios, albeit some tradeoffs.

In a Robot Learning from Demonstration framework involving environments with many objects, one of the key problems is to decide which objects are relevant to a given task. In this paper, we analyze this problem and propose a biologically-inspired computational model that enables the robot to focus on the task-relevant objects. To filter out incompatible task models, we compute a Task Relevance Value (TRV) for each object, which shows a human demonstrator's implicit indication of the relevance to the task. By combining an intentional action representation with ‘motionese’ [2], our model exhibits recognition capabilities compatible with the way that humans demonstrate. We evaluate the system on demonstrations from five different human subjects, showing its ability to correctly focus on the appropriate objects in these demonstrations.

Models of activity structure for unconstrained environments are generally not available a priori. Recent representational approaches to this end are limited by their computational complexity, and ability to capture activity structure only up to some fixed temporal scale. In this work, we propose Suffix Trees as an activity representation to efficiently extract structure of activities by analyzing their constituent event-subsequences over multiple temporal scales. We empirically compare Suffix Trees with some of the previous approaches in terms of feature cardinality, discriminative prowess, noise sensitivity and activity-class discovery. Finally, exploiting properties of Suffix Trees, we present a novel perspective on anomalous subsequences of activities, and propose an algorithm to detect them in linear-time. We present comparative results over experimental data, collected from a kitchen environment to demonstrate the competence of our proposed framework.

This paper presents a novel multiscale shape representation and segmentation algorithm based on the spherical wavelet transform. This work is motivated by the need to compactly and accurately encode variations at multiple scales in the shape representation in order to drive the segmentation and shape analysis of deep brain structures, such as the caudate nucleus or the hippocampus. Our proposed shape representation can be optimized to compactly encode shape variations in a population at the needed scale and spatial locations, enabling the construction of more descriptive, nonglobal, nonuniform shape probability priors to be included in the segmentation and shape analysis framework. In particular, this representation addresses the shortcomings of techniques that learn a global shape prior at a single scale of analysis and cannot represent fine, local variations in a population of shapes in the presence of a limited dataset. Specifically, our technique defines a multiscale parametric model of surfaces belonging to the same population using a compact set of spherical wavelets targeted to that population. We further refine the shape representation by separating into groups wavelet coefficients that describe independent global and/or local biological variations in the population, using spectral graph partitioning. We then learn a prior probability distribution induced over each group to explicitly encode these variations at different scales and spatial locations. Based on this representation, we derive a parametric active surface evolution using the multiscale prior coefficients as parameters for our optimization procedure to naturally include the prior for segmentation. Additionally, the optimization method can be applied in a coarse-to-fine manner. We apply our algorithm to two different brain structures, the caudate nucleus and the hippocampus, of interest in the study of schizophrenia. We show: 1) a reconstruction task of a test set to validate the expressiveness of our multiscale prior and 2) a segmentation task. In the reconstruction task, our results show that for a given training set size, our algorithm significantly improves the approximation of shapes in a testing set over the Point Distribution Model, which tends to oversmooth data. In the segmentation task, our validation shows our algorithm is computationally efficient and outperforms the Active Shape Model algorithm, by capturing finer shape details.

Graphical models are often used to represent and recognize activities. Purely unsupervised methods (such as HMMs) can be trained automatically but yield models whose internal structure - the nodes - are difficult to interpret semantically. Manually constructed networks typically have nodes corresponding to sub-events, but the programming and training of these networks is tedious and requires extensive domain expertise. In this paper, we propose a semi-supervised approach in which a manually structured, Propagation Network (a form of a DBN) is initialized from a small amount of fully annotated data, and then refined by an EM-based learning method in an unsupervised fashion. During node refinement (the M step) a boosting-based algorithm is employed to train the evidence detectors of individual nodes. Experiments on a variety of data types - vision and inertial measurements - in several tasks demonstrate the ability to learn from as little as one fully annotated example accompanied by a small number of positive but non-annotated training examples. The system is applied to both recognition and anomaly detection tasks.

Estimating the traversability of terrain in an unstructured outdoor environment is a core functionality for autonomous robot navigation. While general-purpose sensing can be used to identify the existence of terrain features such as vegetation and sloping ground, the traversability of these regions is a complex function of the terrain characteristics and vehicle capabilities, which makes it extremely difficult to characterize a priori. Moreover, it is difficult to find general rules which work for a wide variety of terrain types such as trees, rocks, tall grass, logs, and bushes. As a result, methods which provide traversability estimates based on predefined terrain properties such as height or shape will be unlikely to work reliably in unknown outdoor environments. Our approach is based on the observation that traversability in the most general sense is an affordance which is jointly determined by the vehicle and its environment. We describe a novel on-line learning method which can make accurate predictions of the traversability properties of complex terrain. Our method is based on autonomous training data collection which exploits the robot's experience in navigating its environment to train classifiers without human intervention. This is in contrast to other learning methods in which training data is collected manually. We have implemented and tested our traversability learning method on an unmanned ground vehicle (UGV) and evaluated its performance in several realistic outdoor environments. The experiments quantify the benefit of our on-line traversability learning approach

We present a novel representation and method for detecting and explaining anomalous activities in a video stream. Drawing from natural language processing, we introduce a representation of activities as bags of event n-grams, where we analyze the global structural information of activities using their local event statistics. We demonstrate how maximal cliques in an undirected edge-weighted graph of activities, can be used in an unsupervised manner, to discover regular sub-classes of an activity class. Based on these discovered sub-classes, we formulate a definition of anomalous activities and present a way to detect them. Finally, we characterize each discovered sub-class in terms of its "most representative member" and present an information-theoretic method to explain the detected anomalies in a human-interpretable form.

We present a novel technique for texture synthesis using optimization. We define a Markov Random Field (MRF)-based similarity metric for measuring the quality of synthesized texture with respect to a given input sample. This allows us to formulate the synthesis problem as minimization of an energy function, which is optimized using an Expectation Maximization (EM)-like algorithm. In contrast to most example-based techniques that do region-growing, ours is a joint optimization approach that progressively refines the entire texture. Additionally, our approach is ideally suited to allow for controllable synthesis of textures. Specifically, we demonstrate controllability by animating image textures using flow fields. We allow for general two-dimensional flow fields that may dynamically change over time. Applications of this technique include dynamic texturing of fluid animations and texture-based flow visualization.

Just as a motion field is associated to a moving object, an audio field can be associated to an object that can behave as a sound source. The flow field of such a sound source which moves over time would not only have an optical component, but also an audio component; something we call audio-visual flow. In this paper we present a common structure tensor based variational framework for dense audiovisual flow-field estimation. The proposed scheme improves the rank of the local structure tensor by incorporating an audio information channel which is substantially uncorrelated from the complementing visual information channel. The scheme allows ascribing weights to individual sensor modalities based on the confidence in their corresponding measurements. Results are presented to demonstrate how combining multiple modalities in our proposed framework can provide a possible solution to temporary full visual occlusions.

In this paper we introduce a new algorithm for image and video texture synthesis. In our approach, patch regions from a sample image or video are transformed and copied to the output and then stitched together along optimal seams to generate a new (and typically larger) output. In contrast to other techniques, the size of the patch is not chosen a-priori , but instead a graph cut technique is used to determine the optimal patch region for any given offset between the input and output texture. Unlike dynamic programming, our graph cut technique for seam optimization is applicable in any dimension. We specifically explore it in 2D and 3D to perform video texture synthesis in addition to regular image synthesis. We present approximative offset search techniques that work well in conjunction with the presented patch size optimization. We show results for synthesizing regular, random, and natural images and videos. We also demonstrate how this method can be used to interactively merge different images to generate new scenes.

A gait-recognition technique that recovers static body and stride parameters of subjects as they walk is presented. This approach is an example of an activity-specific biometric: a method of extracting identifying properties of an individual or of an individual's behavior that is applicable only when a person is performing that specific action. To evaluate our parameters, we derive an expected confusion metric (related to mutual information), as opposed to reporting a percent correct with a limited database. This metric predicts how well a given feature vector will filter identity in a large population. We test the utility of a variety of body and stride parameters recovered in different viewing conditions on a database consisting of 15 to 20 subjects walking at both an angled and frontal-parallel view with respect to the camera, both indoors and out. We also analyze motion-capture data of the subjects to discover whether confusion in the parameters is inherently a physical or a visual measurement error property.

A method for temporally integrating appearance-based body-part labelling is presented. We begin by modifying the silhouette labelling method of Ghost (Haritaoglu, Harwood, and Davis. 1998); that system first determines which posture best describes the person currently and then uses posture-specific heuristics to generate labels for head, hands, and feet. Our approach is to assign a posture probability and then estimate body part locations for all possible postures. Next we temporally integrate these estimates by finding a best path through the posture-time lattice. A density-sampling propagation approach is used that allows us to model the multiple hypotheses resulting from consideration of different postures. We show quantitative and qualitative results where the temporal integration solution improves the instantaneous estimates. This method can be applied to any system that inherently has multiple methods of asserting instantaneous properties but from which a temporally coherent interpretation is desired.

This paper demonstrates gait recognition using only the trajectories of lower body joint angles projected into the walking plane. For this work, we begin with the position of 3D markers as projected into the sagittal or walking plane. We show a simple method for estimating the planar offsets between the markers and the underlying skeleton and joints; given these offsets we compute the joint angle trajectories. To compensate for systematic temporal variations from one instance to the next-predominantly distance and speed of walk-we fix the number of footsteps and time-normalize the trajectories by a variance compensated time warping. We perform recognition on two walking databases of 18 people (over 150 walk instances) using simple nearest neighbor algorithm with Euclidean distance as a measurement criteria. We also use the expected confusion metric as a means to estimate how well joint-angle signals will perform in a larger population.

Conventional application of hidden Markov models to the task of recognizing human gesture may suffer from multiple sources of systematic variation in the sensor outputs. We present two frameworks based on hidden Markov models which are designed to model and recognize gestures that vary in systematic ways. In the first, the systematic variation is assumed to be communicative in nature, and the input gesture is assumed to belong to gesture family. The variation across the family is modeled explicitly by the parametric hidden Markov model (PHMM). In the second framework, variation in the signal is overcome by relying on online learning rather than conventional offline, batch learning.

A view-based approach to the representation and recognition of human movement is presented. The basis of the representation is a temporal template-a static vector-image where the vector value at each point is a function of the motion properties at the corresponding spatial location in an image sequence. Using aerobics exercises as a test domain, we explore the representational power of a simple, two component version of the templates: The first value is a binary value indicating the presence of motion and the second value is a function of the recency of motion in a sequence. We then develop a recognition method matching temporal templates against stored instances of views of known actions. The method automatically performs temporal segmentation, is invariant to linear changes in speed, and runs in real-time on standard platforms.

Many communicative behaviors in the animal kingdom consist of performing and recognizing specialized patterns of oscillatory motion. Here we present an approach to the representation and recognition of these oscillatory motions based on the categorical organization of a simple sinusoidal model having very specific and limited parameter values. This characterization is used to specify the types and layout of computation for recognizing the patterns. Results of the method are demonstrated with real oscillatory motions showing the viability of a structured categorical framework.

We introduce an online adaptive algorithm for learning gesture models. By learning gesture models in an online fashion, the gesture recognition process is made more robust, and the need to train on a large training ensemble is obviated. Hidden Markov models are used to represent the spatial and temporal structure of the gesture. The usual output probability distributions-typically representing appearance-are trained at runtime exploiting the temporal structure (Markov model) that is either trained off-line or is explicitly hand-coded. In the early stages of runtime adaptation, contextural information derived from the application is used to bias the expectation as to which Markov state the system is in at any given time. We describe the Watch and Learn system, a computer vision system which is able to learn simple gestures online for interactive control.

This paper describes a probabilistic syntactic approach to the detection and recognition of temporally extended activities and interactions between multiple agents. The fundamental idea is to divide the recognition problem into two levels. The lower level detections are performed using standard independent probabilistic event detectors to propose candidate detections of low-level features. The outputs of these detectors provide the input stream for a stochastic context-free grammar parsing mechanism. The grammar and parser provide longer range temporal constraints, disambiguate uncertain low-level detections, and allow the inclusion of a priori knowledge about the structure of temporal events in a given domain. We develop a real-time system and demonstrate the approach in several experiments on gesture recognition and in video surveillance. In the surveillance application, we show how the system correctly interprets activities of multiple interacting objects.

We introduce the concept of a sympathetic inter$ace for controlling an animated synthetic character in a 3D virtual environment. A plush doll embedded with wireless sensors is used to manipulate the virtual character in an iconic and intentional manner. The interface extends from the novel physical input device through interpretation of sensor data to the behavioral brain of the virtual character. We discuss the design of the interface and focus on its latest instantiation in the Swamped! exhibit at SIGGRAPH 98. We also present what we learned from hundreds of casual users, who ranged from young children to adults.

A probabilistic framework for representing and visually recognizing complex multi-agent action is presented. Motivated by work in model-based object recognition and designed for the recognition of action from visual evidence, the representation has three components: (1) temporal structure descriptions representing the temporal relationships between agent goals, (2) belief networks for probabilistically representing and recognizing individual agent goals from visual evidence, and (3) belief networks automatically generated from the temporal structure descriptions that support the recognition of the complex action. We describe our current work on recognizing American football plays from noisy trajectory data.

This paper describes a probabilistic syntactic approach to the detection and recognition of temporally extended activities and interactions between multiple agents. A complete system consisting of an adaptive tracker, an event generator and the parser performs segmentation and labelling of a surveillance video of a parking lot; the system correctly identifies activities such as pick-up and drop-off, which involve person-vehicle interactions. The main contributions of this paper are extending the parsing algorithm to handle multi-agent interactions within a single parser, providing a general mechanism for consistency-based pruning, and developing an efficient incremental parsing algorithm.

A method for the representation, recognition, and interpretation of parameterized gesture is presented. By parameterized gesture we mean gestures that exhibit a systematic spatial variation; one example is a point gesture where the relevant parameter is the two-dimensional direction. Our approach is to extend the standard hidden Markov model method of gesture recognition by including a global parametric variation in the output probabilities of the HMM states. Using a linear model of dependence, we formulate an expectation-maximization (EM) method for training the parametric HMM. During testing, a similar EM algorithm simultaneously maximizes the output likelihood of the PHMM for the given sequence and estimates the quantifying parameters. Using visually derived and directly measured three-dimensional hand position measurements as input, we present results that demonstrate the recognition superiority of the PHMM over standard HMM techniques, as well as greater robustness in parameter estimation with respect to noise in the input features. Finally, we extend the PHMM to handle arbitrary smooth (nonlinear) dependencies. The nonlinear formulation requires the use of a generalized expectation-maximization (GEM) algorithm for both training and the simultaneous recognition of the gesture and estimation of the value of the parameter. We present results on a pointing gesture, where the nonlinear approach permits the natural spherical coordinate parameterization of pointing direction.

A new approach to the recognition of temporal behaviours and activities is presented. The fundamental idea, inspired by work in speech recognition, is to divide the inference problem into two levels. The lower level is performed using standard independent probabilistic temporal event detectors such as hidden Markov models (HMMs) to propose candidate detections of low level temporal features. The outputs of these detectors provide the input stream for a stochastic context-free grammar parsing mechanism. The grammar and parser provide longer range temporal constraints, disambiguate uncertain low level detections, and allow the inclusion of a priori knowledge about the structure of temporal events in a given domain. To achieve such a system we provide techniques for generating a discrete symbol stream from continuous low level detectors and for enforcing temporal exclusion constraints during parsing. We demonstrate the approach in several experiments using both visual and other sensing data.

In this paper we develop a representation for the temporal structure inherent in human actions and demonstrate an effective method for using that representation to detect the occurrence of actions. The temporal structure of the action, sub-actions, events, and sensor information is described using a constraint network based on Allen's interval algebra. We map these networks onto a simpler, S-valued domain (past, now, fut) network-a PNF-network-to allow fast detection of actions and sub-actions. The occurrence of an action is computed by considering the minimal domain of its PNF-network, under constraints imposed by the current state of the sensors and the previous states of the network. We illustrate the approach with examples, showing that a major advantage of PNF propagation is the detection and removal of in-consistent situations.

Recently we modified the hidden Markov model (HMM) framework to incorporate a global parametric variation in the output probabilities of the states of the HMM. Development of the parametric hidden Markov model (PHMM) was motivated by the task of simultaneously recognizing and interpreting gestures that exhibit meaningful variation. With standard HMMs, such global variation confounds the recognition process. The original PHMM approach assumes a linear dependence of output density means on the global parameter. In this paper we extend the PHMM to handle arbitrary smooth (nonlinear) dependencies. We show a generalized expectation-maximization (GEM) algorithm for training the PHMM and a GEM algorithm to simultaneously recognize the gesture and estimate the value of the parameter. We present results on a pointing gesture, where the nonlinear approach permits the natural azimuth/elevation parameterization of pointing direction.

A new method for the representation, recognition, and interpretation of parameterized gesture is presented. By parameterized gesture. We mean gestures that exhibit a meaningful variation; one example is a point gesture where the important parameter is the 2-dimensional direction. Our approach is to extend the standard hidden Markov model method of gesture recognition by including a global parametric variation in the output probabilities of the states of the HMM. Using a linear model to derive the theory, we formulated an expectation-maximization (EM) method for training the parametric HMM. During testing, the parametric HMM simultaneously recognizes the gesture and estimates the quantifying parameters. Using visually derived and directly measured 3-dimensional hand position measurements as input, we present results on two. Different movements-a size gesture and a point gesture-and show robustness with respect to noise in the input features.

A system to manage human interaction in immersive environments was designed and implemented.The interaction is defined by an interval scripi which describes the relationships between the time intervals which command actuators or gather information from sensors.With this formalism, reactive, linear, and tree-like interaction can be equally described, as well as less regular story and interaction patterns.Control of actuators and sensors is accomplished using PNF-restriction, a calculus which propagates the sensed information through the interval script determining which intervals are or should be happening at each moment.The prototype was used in an immersive, story-based interactive environment called SingSong where a user or a performer tries to conduct four computer character singers in spite of the hostility of one of them.

Most view-based vision algorithms are based on strong assumptions about the disposition of the objects in the image. To safely apply those algorithms in real world image sequences, we propose that a vision system should be divided into two components. The first component contains an approximate world model of the scene-a low accuracy, coarse description of the objects and actions in the world. Approximate world models are constructed and updated by simple vision routines and by the use of action information provided by an external source. The second component employs view-based algorithms to perform required perceptual tasks; the selection and control of the view-based methods are determined by the information provided by the approximate world model. We demonstrate the approximate world model approach in a project to control cameras in a TV studio where the external context is provided by a script.

A new view-based approach to the representation and recognition of action is presented. The basis of the representation is a temporal template-a static vector-image where the vector value at each point is a function of the motion properties at the corresponding spatial location in an image sequence. Using 18 aerobics exercises as a test domain, we explore the representational power of a simple, two component version of the templates: the first value is a binary value indicating the presence of motion, and the second value is a function of the recency of motion in a sequence. We then develop a recognition method which matches these temporal templates against stored instances of views of known actions. The method automatically performs temporal segmentation, is invariant to linear changes in speed, and runs in real-time on a standard platform. We recently incorporated this technique into the KIDSROOM: an interactive, narrative play-space for children.

A real-time tracking algorithm that uses contextual information is described. The method is capable of simultaneously tracking multiple, non-rigid objects when erratic movement and object collisions are common. A closed-world assumption is used to adaptively select and weight image features used for correspondence. Results of algorithm testing and the limitations of the method are discussed. The algorithm has been used to track children in an interactive, narrative playspace.

A method for the temporal classification of natural gesture from video imagery is presented. The work is motivated by recent developments in the theory of natural gesture which have identified several key temporal aspects of gesture important to communication. In particular gesticulation during conversation can be coarsely characterized as periods of bi-phasic or tri-phasic gesture separated by a rest state. We first present an automatic procedure for hypothesizing plausible rest state configurations of a speaker. Second, we develop a state-based parsing algorithm used to both select among candidate rest states and to parse an incoming video stream into bi-phasic and tri-phasic gestures. Finally, we demonstrate the use of the bi-phasic/tri-phasic labeling to select semantically significant static images for low bandwidth coding of video of story-telling speakers.

A state-based technique for the representation and recognition of gesture is presented. We define a gesture to be a sequence of states in a measurement or configuration space. For a given gesture, these states are used to capture both the repeatability and variability evidenced in a training set of example trajectories. Using techniques for computing a prototype trajectory of an ensemble of trajectories, we develop methods for defining configuration states along the prototype and for recognizing gestures from an unsegmented, continuous stream of sensor data. The approach is illustrated by application to a range of gesture-related sensory data: the two-dimensional movements of a mouse input device, the movement of the hand measured by a magnetic spatial position and orientation sensor, and, lastly, the changing eigenvector projection coefficients computed from an image sequence.

As research in computer vision has shifted from only processing single, static images to the manipulation of video sequences, the concept of action recognition has become important. Fundamental to understanding action is reasoning about time, in either an implicit or explicit framework. In this paper I describe several specific examples of incorporating time into representations of action and how those representations are used to recognize actions. The approaches differ on whether variation over time is considered a continuous mapping, a state-based trajectory, or a qualitative, semantically labeled sequence. For two of the domains --- whole body actions and hand gestures --- I describe the approaches in detail while two others --- constrained semantic domains (e.g. watching someone cooking) and labeling dynamic events (e.g. American football) --- are briefly mentioned. 1 Seeing Action Understanding video sequences is different than conventional image understanding in that one is int...

Ten different feature vectors are tested in a gesture recognition task which utilizes 3D data gathered in real-time from stereo video cameras, and HMMs for learning and recognition of gestures. Results indicate velocity features are superior to positional features, and partial rotational invariance is sufficient for good performance.

A method for the recovery of the temporal structure and phases in natural gesture is presented. The work is motivated by recent developments in the theory of natural gesture which have identified several key aspects of gesture important to communication. In particular, gesticulation during conversation can be coarsely characterized as periods of bi-phasic or tri-phasic gesture separated by a rest state. We first present an automatic procedure for hypothesizing plausible rest state configurations of a speaker; the method uses the repetition of subsequences to indicate potential rest states. Second, we develop a state-based parsing algorithm used to both select among candidate rest stares and to parse an incoming video stream into bi-phasic and multi-phasic gestures. We present results from examples of story-telling speakers.

A new view-based approach to the representation of action is presented. Our underlying representations are view-based descriptions of the coarse image motion associated with viewing given actions from particular directions. Using these descriptions, we propose an appearance-based action-recognition strategy comprised of two stages: 1) a motion energy image (MEI) is computed that grossly describes the spatial distribution of motion energy for a given view of a given action, and the input MEI is matched against stored models which span the range of views of known actions; 2) any models that plausibly match the input are tested for a coarse, categorical agreement between a stored motion model of the action and a parametrization of the input motion. Using a "sitting" action as an example, and using a manually placed stick model, we develop a representation and verification technique that collapses the temporal variations of the motion parameters into a single, low-order vector.

A new view based approach to the representation and recognition of action is presented. The basis of the representation is a motion history image (MHI)-a static image where intensity is a function of the recency of motion in a sequence. We develop a recognition method which uses both binary and scalar valued versions of the MHI as temporal templates to match against stored instances of actions. The method automatically performs temporal segmentation, as invariant to linear changes in speed, and runs in real time on a standard platform. The applications we have begun to develop include simple room monitoring and an interactive game.

A new method for representing and recognizing human body movements is presented. The basic idea is to identify sets of constraints that are diagnostic of a movement: expressed using body-centered coordinates such as joint angles and in force only during a particular movement. Assuming the availability of Cartesian tracking data, we develop techniques for a representation of movements defined by space curves in subspaces of a "phase space." The phase space has axes of joint angles and torso location and attitude, and the axes of the subspaces are subsets of the axes of the phase space. Using this representation we develop a system for learning new movements from ground truth data by searching for constraints. We then use the learned representation for recognizing movements in unsegmented data. We train and test the system on nine fundamental steps from classical ballet performed by two dancers; the system accurately recognizes the movements in the unsegmented stream of motion.>

A new approach to tracking weakly modeled objects in a semantically rich domain is presented. We define a closed-world as a space-time region of an image sequence in which the complete taxonomy of objects is known, and in which each pixel should be explained as belonging to one of those objects. Given contextual object information, context-specific features can be dynamically selected as the basis for tracking. A context-specific feature is one that has been chosen based upon the context to maximize the chance of successful tracking between frames. Our work is motivated by the goal of video annotation-the semi-automatic generation of symbolic descriptions of action taking place in a contextually-rich dynamic scene. We describe how contextual knowledge in the "football domain" can be applied to closed-world football player tracking and present the details of our implementation. We include tracking results based on hundreds of images that demonstrate the wide range of tracking situations the algorithm successfully handles as well as a few examples of where the algorithm fails.>

We define a gesture to be a sequence of states in a measurement or configuration space. For a given gesture, these states are used to capture both the repeatability and variability evidenced in a training set of example trajectories. The states are positioned along a prototype of the gesture, and shaped such that they are narrow in the directions in which the ensemble of examples is tightly constrained, and wide in directions in which a great deal of variability is observed. We develop techniques for computing a prototype trajectory of an ensemble of trajectories, for defining configuration states along the prototype, and for recognizing gestures from an unsegmented, continuous stream of sensor data. The approach is illustrated by application to a range of gesture-related sensory data: the two-dimensional movements of a mouse input device, the movement of the hand measured by a magnetic spatial position and orientation sensor, and, lastly, the changing eigenvector projection coefficients computed from an image sequence.>

A method for incorporating intensity edge information into the recovery of occlusion regions using a pixel-based stereo algorithm is presented. The authors review the construction of disparity space images and their use to solve the stereo occlusion problem. The authors show the relationship between intensity edges and the disparity space images, and extend their stereo technique to use information about intensity discontinuities at occlusion edges. The combination of ground control points and edge information yields excellent occlusion regions.

A method is presented for validating low level optic flow computations in an image sequence by a simple analysis of the stability of the three-dimensional interpretation of the scene. Given computed optic flow and known egomotion, a viewer centered depth image is computed. By warping a finite history of previous depth images to the current viewer-centered system, the stability of the depth estimate at each point is analysed. Regions of low stability indicate image regions where the low level optic flow computation is unreliable. It is proposed that this approach is an example of performing verification mode vision, i.e., simple low-level computations are adequate when the interpretation provided is consistent with respect to the current scene interpretation. >

A representation paradigm for instantiating and refining multiple, concurrent descriptions of an object from a sequence of imagery is presented. It is designed for the perception system of an autonomous robot that needs to describe many types of objects, initially detects objects at a distance and gradually acquires higher resolution data, and continuously collects sensory input. Since the data change significantly over time, the paradigm supports the evolution of descriptions, progressing from crude 2-D 'blob' descriptions to complete semantic models. To control this accumulation of new descriptions, the authors introduce the idea of representation space, a lattice of representations that specifies the order in which they should be considered for describing an object. A system, TraX, that constructs and refines models of outdoor objects detected in sequences of range data is described.>

A method for recovering shape from shading that solves directly for the surface height is presented. By using a discrete formulation of the problem, it is possible to achieve good convergence behavior by employing numerical solution techniques more powerful than gradient descent methods derived from variational calculus. Because this method solves directly for height, it avoids the problem of finding an integrable surface maximally consistent with surface orientation. Furthermore, since additional constraints are not needed to make the problem well posed, a smoothness constraint is used only to drive the system towards a good solution; the weight of the smoothness term is eventually reduced to near zero. By solving directly for height, stereo processing may be used to provide initial and boundary conditions. The shape from shading technique, as well as its relation to stereo, is demonstrated on both synthetic and real imagery.>

An approach to representing objects viewed over long periods of time and with changing resolutions is presented. The basic strategy is to apply different representations as they become appropriate. As a result, the model of an object typically goes through a sequence of representation as new data are gathered and processed. One of these sequences might start with a crude blob description of an initially detected object, include a detailed structural model derived from a set of high-resolution images, and end with a semantic label based on the object's description and the sensor system's task. This evolution in representation is guided by a structure referred to as representation space: a lattice or representation that is traversed as new information about an object becomes available. One of the representations is associated with an object only after it has been judged to be valid. One approach for evaluating the validity of an object's description is described, based on the temporal stability of the description. These ideas are illustrated with results from a system which constructs and refines models of outdoor objects detected in sequences of range data.>

A technique for building reliable scene descriptions by evaluating the temporal stability of detected objects is presented. The approach is designed to avoid mistakes and to increase the competence of the sensing system by tracking objects from image to image and evaluating the stability of their descriptions over time. Since the information available about an object can change significantly over time, the authors introduce the idea of a representation space, which is a lattice of representations progressing from crude blob descriptions to complete semantic models, such as bush, rock, and tree. One of these representations is associated with an object only after the object has been described multiple times in the representation and the parameters of the representation are stable in a statistical sense enhanced by a set of explanations describing valid reasons for deviations. To illustrate the power of these ideas, the authors have implemented a system, called TraX, that constructs and refines models of outdoor objects detected in sequences of range data.>