State of the art unimodal dialogue agents lack some core aspects of peer-to-peer communication—the nonverbal and visual cues that are a fundamental aspect of human interaction. To facilitate true peer-to-peer communication with a computer, we present Diana, a situated multimodal agent who exists in a mixed-reality environment with a human interlocutor, is situation- and context-aware, and responds to the human's language, gesture, and affect to complete collaborative tasks.

Multi-channel architectures are becoming increasingly common, setting the state-of-the-art for performance in gesture recognition challenges. Unfortunately, we lack a clear explanation of why multi-channel architectures outperform single channel ones. This paper considers two hypotheses. The Bagging hypothesis says that multi-channel architectures succeed because they average the result of multiple unbiased weak estimators in the form of different channels. The Society of Experts (SoE) hypothesis suggests that multi-channel architectures succeed because the channels differentiate themselves, developing expertise with regard to different aspects of the data.(/p)(/p)To distinguish between these hypotheses, this paper reports on two experiments. The first measures the drop in individual channel performance when the input is degraded by removing high frequency, color, or motion information. The second looks at fusion weights relative to gesture properties. Both experiments support the SoE hypothesis, suggesting multi-channel architectures succeed because of channel specialization.

Gesture recognition is an important task with the potential to revolutionize human/computer interfaces (HCI). Gestures, however, are dynamic. While a few gestures may be static poses, most gestures are complex temporal sequences of motions. For most HCI applications, gestures must be recognized in real-time in streaming data. Therefore, most recognition systems analyze each frame as it comes in, fusing data across time to detect gestures. This paper presents results of the first systematic study of temporal fusion techniques for streaming gesture recognition. These results show that the choice of the best fusion strategy depends on whether the input is global (i.e. full-frame) or a spatially focused window, and on whether the input is unprocessed RGB or depth depth versus a flow field.This conclusion is then used to extend a state-of-the-art architecture for isolated gesture recognition, FOANet [24], to continuous gesture recognition. The result is a system that established a new state-of-the-art for recognition performance on the ChaLearn ConGD data set, with a mean Jaccard Index of 0.77 compared to the previous best result of 0.61. This paper also establishes a baseline of performance for the newer, continuous version of the NVIDIA dataset.

New depth sensors, like the Microsoft Kinect, produce streams of human pose data. These discrete pose streams can be viewed as noisy samples of an underlying continuous ideal curve that describes a trajectory through high-dimensional pose space. This paper introduces a technique for generalized curvature analysis (GCA) that determines features along the trajectory which can be used to characterize change and segment motion. Tools are developed for approximating generalized curvatures at mean points along a curve in terms of the singular values of local mean-centered data balls. The features of the GCA algorithm are illustrated on both synthetic and real examples, including data collected from a Kinect II sensor. We also applied GCA to the Carnegie Mellon University Motion Capture (MoCaP) database. Given that GCA scales linearly with the length of the time series we are able to analyze large data sets without down sampling. It is demonstrated that the generalized curvature approximations can be used to segment pose streams into motions and transitions between motions. The GCA algorithm can identify 94.2 percent of the transitions between motions without knowing the set of possible motions in advance, even though the subjects do not stop or pause between motions.

Gestures are a common form of human communication and important for human computer interfaces (HCI). Recent approaches to gesture recognition use deep learning methods, including multi-channel methods. We show that when spatial channels are focused on the hands, gesture recognition improves significantly, particularly when the channels are fused using a sparse network. Using this technique, we improve performance on the ChaLearn IsoGD dataset from a previous best of 67.71% to 82.07%, and on the NVIDIA dataset from 83.8% to 91.28%.

Video annotation is a vital part of research examining gestural and multimodal interaction as well as computer vision, machine learning, and interface design. However, annotation is a difficult, time-consuming task that requires high cognitive effort. Existing tools for labeling and annotation still require users to manually label most of the data, limiting the tools helpfulness. In this paper, we present the Easy Automatic Segmentation Event Labeler (EASEL), a tool supporting gesture analysis. EASEL streamlines the annotation process by introducing assisted annotation, using automatic gesture segmentation and recognition to automatically annotate gestures. To evaluate the efficacy of assisted annotation, we conducted a user study with 24 participants and found that assisted annotation decreased the time needed to annotate videos with no difference in accuracy compared with manual annotation. The results of our study demonstrate the benefit of adding computational intelligence to video and audio annotation tasks.

People, cars and other moving objects in videos generate time series data that can be labeled in many ways. For example, classifiers can label motion tracks according to the object type, the action being performed, or the trajectory of the motion. These labels can be generated for every frame as long as the object stays in view, so object tracks can be modeled as Markov processes with multiple noisy observation streams. A challenge in video recognition is to recover the true state of the track (i.e. its class, action and trajectory) using Markov models without (a) counter-factually assuming that the streams are independent or (b) creating a fully coupled Hidden Markov Model (FCHMM) with an infeasibly large state space. This paper introduces a new method for labeling sequences of hidden states. The method exploits external consistency constraints among streams without modeling complex joint distributions between them. For example, common sense semantics suggest that trees cannot walk. This is an example of an external constraint between an object label (“tree”) and an action label (“walk”). The key to exploiting external constraints is a new variation of the Viterbi algorithm which we call the Viterbi–Segre (VS) algorithm. VS restricts the solution spaces of factorized HMMs to marginal distributions that are compatible with joint distributions satisfying sets of external constraints. Experiments on synthetic data show that VS does a better job of estimating true states with the given observations than the traditional Viterbi algorithm applied to (a) factorized HMMs, (b) FCHMMs, or (c) partially-coupled HMMs that model pairwise dependencies. We then show that VS outperforms factorized and pairwise HMMs on real video data sets for which FCHMMs cannot feasibly be trained.

Multi-concept visual classification is emerging as a common environment perception technique, with applications in autonomous mobile robot navigation. Supervised visual classifiers are typically trained with large sets of images, hand annotated by humans with region boundary outlines followed by label assignment. This annotation is time consuming, and unfortunately, a change in environment requires new or additional labeling to adapt visual perception. The time is takes for a human to label new data is what we call adaptation latency. High adaptation latency is not simply undesirable but may be infeasible for scenarios with limited labeling time and resources. In this paper, we introduce a labeling framework to the environment perception domain that significantly reduces adaptation latency using unsupervised learning in exchange for a small amount of label noise. Using two real-world datasets we demonstrate the speed of our labeling framework, and its ability to collect environment labels that train high performing multi-concept classifiers. Finally, we demonstrate the relevance of this label collection process for visual perception as it applies to navigation in outdoor environments.

Visual classifiers are part of many applications including surveillance, autonomous navigation and scene understanding. The raw data used to train these classifiers is abundant and easy to collect but lacks labels. Labels are necessary for training supervised classifiers, but the labeling process requires significant human effort. Techniques like active learning and group-based labeling have emerged to help reduce the labeling workload. However, the possibility of collecting label noise affects either the efficiency of these systems or the performance of the trained classifiers. Further, many introduce latency by iteratively retraining classifiers or re-clustering data. We introduce a technique that searches for structural change in hierarchically clustered data to identify a set of clusters that span a spectrum of visual concept granularities. This allows us to efficiently label clusters with less label noise and produce high performing classifiers. The data is hierarchically clustered only once, eliminating latency during the labeling process. Using benchmark data we show that collecting labels with our approach is more efficient than existing labeling techniques, and achieves higher classification accuracy. Finally, we demonstrate the speed and efficiency of our system using real-world data collected for an autonomous navigation task.

Many computer vision algorithms employ subspace models to represent data. Many of these approaches benefit from the ability to create an average or prototype for a set of subspaces. The most popular method in these situations is the Karcher mean, also known as the Riemannian center of mass. The prevalence of the Karcher mean may lead some to assume that it provides the best average in all scenarios. However, other subspace averages that appear less frequently in the literature may be more appropriate for certain tasks. The extrinsic manifold mean, the L2-median, and the flag mean are alternative averages that can be substituted directly for the Karcher mean in many applications. This paper evaluates the characteristics and performance of these four averages on synthetic and real-world data. While the Karcher mean generalizes the Euclidean mean to the Grassman manifold, we show that the extrinsic manifold mean, the L2-median, and the flag mean behave more like medians and are therefore more robust to the presence of outliers among the subspaces being averaged. We also show that while the Karcher mean and L2-median are computed using iterative algorithms, the extrinsic manifold mean and flag mean can be found analytically and are thus orders of magnitude faster in practice. Finally, we show that the flag mean is a generalization of the extrinsic manifold mean that permits subspaces with different numbers of dimensions to be averaged. The result is a "cookbook" that maps algorithm constraints and data properties to the most appropriate subspace mean for a given application.

A new algorithm for learning binary codes is presented using randomized initial assignments of bit labels to classes followed by iterative refinement to minimize intraclass Hamming distance. This Randomized Intraclass-Distance Minimizing Binary Codes (RIDMBC) algorithm is introduced in the context of face recognition, an area of biometrics where binary codes have rarely been used (unlike iris recognition). A cross-database experiment is presented training RIDMBC on the Labeled Faces in the Wild (LFW) and testing it on the Point-and-Shoot Challenge (PaSC). The RIDMBC algorithm performs better than both PaSC baselines. RIDMBC is compared with the Predictable Discriminative Binary Codes (DBC) algorithm developed by Rastegari et al. The DBC algorithm has an upper bound on the number of bits in a binary code; RIDMBC does not. RIDMBC outperforms DBC when using the same bit code length as DBC's upper bound and RIDMBC further improves when more bits/features are added.

Handheld videos include unintentional motion (jitter) and often intentional motion (pan and/or zoom). Human viewers prefer to see jitter removed, creating a smoothly moving camera. For video analysis, in contrast, aligning to a fixed stable background is sometimes preferable. This paper presents an algorithm that removes both forms of motion using a novel and efficient way of tracking background points while ignoring moving foreground points. The approach is related to image mosaicing, but the result is a video rather than an enlarged still image. It is also related to multiple object tracking approaches, but simpler since moving objects need not be explicitly tracked. The algorithm presented takes as input a video and returns one or several stabilized videos. Videos are broken into parts when the algorithm detects the background changing and it becomes necessary to fix upon a new background. Our approach assumes the person holding the camera is standing in one place and that objects in motion do not dominate the image. Our algorithm performs better than several previously published approaches when compared on 1,401 handheld videos from the recently released Point-and-Shoot Face Recognition Challenge (PASC). The source code for this algorithm is being made available.

Labeling data to train visual concept classifiers requires significant human effort. Active learning addresses labeling overhead by selecting a meaningful subset of data, but often these approaches assume that the set of visual concepts is known in advance. Clustering approaches perform bottom-up discovery of concepts, and reduce labeling effort by moving from instance-based to group-based labeling. Unfortunately, clustering techniques assume a one-to-one mapping between clusters and visual concepts even though learned groups are often not coherent and fail to represent all concepts. We introduce Selective Guidance, a technique that hierarchically clusters data and selectively queries labels of coherent clusters representing different visual concepts. Unlike most active learning and clustering techniques, Selective Guidance does not require any a priori knowledge. Using benchmark data sets we show that Selective Guidance achieves classification accuracy better than active learning and clustering approaches with fewer labeling queries.

Many computer vision tasks such as large-scale image retrieval and nearest-neighbor classification perform similarity searches using Approximate Nearest Neighbor (ANN) indexes. These applications rely on the quality of ANN retrieval for success. Popular indexing methods for ANN queries include forests of kd-trees (KDT) and hierarchical k-means (HKM). The dominance of these two methods has led to implementations in many popular computer vision tool kits, perhaps leading some to assume that ANN indexing is a solved problem. This paper introduces a new method, the Proximity Forest, which is based on a forest of randomized metric trees. We present evidence that forests of metric trees significantly outperform KDT and HKM when evaluated on real-world data, controlling for dimensionality, data set size, distance function, and the number of neighbors returned by the query. Randomized metric trees are simple to implement, are generic in regards to the chosen distance function, and can be applied to a wider class of data representations.

We present a novel structure, called a Subspace Forest, designed to provide an efficient approximate nearest neighbor query of subspaces represented as points on Grassmann manifolds. We apply this structure to action recognition by representing actions as subspaces spanning a sequence of thumbnail image tiles extracted from a tracked entity. The Subspace Forest lifts the concept of randomized decision forests from classifying vectors to classifying subspaces, and employs a splitting method that respects the underlying manifold geometry. The Subspace Forest is an inherently parallel structure and is highly scalable due to O(log N) recognition time complexity. Our experimental results demonstrate state-of-the-art classification accuracies on the well-known KTH Actions and UCF Sports benchmarks, and a competitive score on Cambridge Gestures. In addition to being both highly accurate and scalable, the Subspace Forest is built without supervision and requires no extensive validation stage for model selection. Conceptually, the Subspace Forest could be used anywhere set-to-set feature matching is desired.

This paper presents a completely unsupervised mechanism for learning micro-actions in continuous video streams. Unlike other works, our method requires no prior knowledge of an expected number of labels (classes), requires no silhouette extraction, is tolerant to minor tracking errors and jitter, and can operate at near real time speed. We show how to construct a set of training “tracklets,” how to cluster them using a recently introduced Product Manifold distance measure, and how to perform detection using exemplars learned from the clusters. Further, we show that the system is amenable to incremental learning as anomalous activities are detected in the video stream. We demonstrate performance using the publicly-available ETHZ Livingroom data set.

In face recognition, quality is typically thought of as a property of individual images, not image pairs. The implicit assumption is that high-quality images should be easy to match to each other, while low quality images should be hard to match. This paper presents a relational graph-based evaluation technique that uses match scores produced by face recognition algorithms to determine the “quality” of images. The resulting analysis demonstrates that only a small fraction of the images in a well-studied data set (FRVT 2006) are low-quality images. It is much more common to find relationships in which two images that are hard to match to each other can be easily matched with other images of the same person. In other words, these images are simultaneously both high and low quality. The existence of such contrary images represents a fundamental challenge for approaches to biometric quality that cast quality as an intrinsic property of a single image. Instead it indicates that quality should be associated with pairs of images. In exploring these contrary images, we find a surprising dependence on whether elements of an image pair are acquired at the same location, even in circumstances where one would be tempted to think of the locations as interchangeable. The results presented have important implications for anyone designing face recognition evaluations as well as those developing new algorithms.

This paper analyzes completely unsupervised clustering of human expressions, gestures, and actions in video. Lacking any supervision, there is nothing except the inherent biases of a given technique to guide grouping of video clips along semantically meaningful partitions. This paper evaluates two contemporary behavior recognition methods, Bag of Features (BOF) and Product Manifolds (PM), for clustering video clips of human facial expressions, hand gestures, and full-body actions. Our goal is to better understand how well these very different approaches to behavior recognition produce semantically useful clustering of relevant data. We show that PM yields superior results when measuring the alignment between the generated clusters over a range of K-values (number of clusters) and the nominal class labelling of the data set. A key result is that unsupervised clustering with PM yields accuracy comparable to state-of-the-art supervised classification methods on KTH Actions. At the same time, BOF experiences a substantial drop in performance between unsupervised and supervised implementations on the same data sets, indicating a greater reliance on supervision for achieving high performance. We also found that while gross motions were easily clustered by both methods, the lack of preservation of structural information inherent to the BOF representation leads to limitations that are not easily overcome without supervised training. This was evidenced by the poor separation of shape labels in the hand gestures data by BOF, and the overall poor performance on full-body actions.

The Good, the Bad, & the Ugly Face Challenge Problem was created to encourage the development of algorithms that are robust to recognition across changes that occur in still frontal faces. The Good, the Bad, & the Ugly consists of three partitions. The Good partition contains pairs of images that are considered easy to recognize. On the Good partition, the base verification rate (VR) is 0.98 at a false accept rate (FAR) of 0.001. The Bad partition contains pairs of images of average difficulty to recognize. For the Bad partition, the VR is 0.80 at a FAR of 0.001. The Ugly partition contains pairs of images considered difficult to recognize, with a VR of 0.15 at a FAR of 0.001. The base performance is from fusing the output of three of the top performers in the FRVT 2006. The design of the Good, the Bad, & the Ugly controls for pose variation, subject aging, and subject “recognizability.” Subject recognizability is controlled by having the same number of images of each subject in every partition. This implies that the differences in performance among the partitions are result of how a face is presented in each image.

Several studies have shown the existence of biometric zoos. The premise is that in biometric systems people fall into distinct categories, labeled with animal names, indicating recognition difficulty. Different combinations of excessive false accepts or rejects correspond to labels such as: Goat, Lamb, Wolf, etc. Previous work on biometric zoos has investigated the existence of zoos for the results of an algorithm on a data set. This work investigates biometric zoos generalization across algorithms and data sets. For example, if a subject is a Goat for algorithm A on data set X, is that subject also a Goat for algorithm B on data set Y? This paper introduces a theoretical framework for generalizing biometric zoos. Based on our framework, we develop an experimental methodology for determining if biometric zoos generalize across algorithms and data sets, and we conduct a series of experiments to investigate the existence of zoos on two algorithms in FRVT 2006.

Although not commonly used, correlation filters can track complex objects through rotations, occlusions and other distractions at over 20 times the rate of current state-of-the-art techniques. The oldest and simplest correlation filters use simple templates and generally fail when applied to tracking. More modern approaches such as ASEF and UMACE perform better, but their training needs are poorly suited to tracking. Visual tracking requires robust filters to be trained from a single frame and dynamically adapted as the appearance of the target object changes. This paper presents a new type of correlation filter, a Minimum Output Sum of Squared Error (MOSSE) filter, which produces stable correlation filters when initialized using a single frame. A tracker based upon MOSSE filters is robust to variations in lighting, scale, pose, and nonrigid deformations while operating at 669 frames per second. Occlusion is detected based upon the peak-to-sidelobe ratio, which enables the tracker to pause and resume where it left off when the object reappears.

This paper introduces a class of correlation filters called average of synthetic exact filters (ASEF). For ASEF, the correlation output is completely specified for each training image. This is in marked contrast to prior methods such as synthetic discriminant functions (SDFs) which only specify a single output value per training image. Advantages of ASEF training include: insensitivity to over-fitting, greater flexibility with regard to training images, and more robust behavior in the presence of structured backgrounds. The theory and design of ASEF filters is presented using eye localization on the FERET database as an example task. ASEF is compared to other popular correlation filters including SDF, MACE, OTF, and UMACE, and with other eye localization methods including Gabor Jets and the OpenCV cascade classifier. ASEF is shown to outperform all these methods, locating the eye to within the radius of the iris approximately 98.5% of the time.

The theory of illumination subspaces is well developed and has been tested extensively on the Yale Face Database B (YDB) and CMU-PIE (PIE) data sets. This paper shows that if face recognition under varying illumination is cast as a problem of matching sets of images to sets of images, then the minimal principal angle between subspaces is sufficient to perfectly separate matching pairs of image sets from nonmatching pairs of image sets sampled from YDB and PIE. This is true even for subspaces estimated from as few as six images and when one of the subspaces is estimated from as few as three images if the second subspace is estimated from a larger set (10 or more). This suggests that variation under illumination may be thought of as useful discriminating information rather than unwanted noise.

This paper summarizes a study carried out on data from the Face Recognition Vendor Test 2006 (FRVT 2006). The finding of greatest practical importance is the discovery of a strong connection between a relatively simple measure of image quality and performance of state-of-the-art vendor algorithms in FRVT 2006. The image quality measure quantifies edge density and likely relates to focus. This effect is part of a larger four-way interaction observed between edge density, face size and whether images are acquired indoors our outdoors. This finding illustrates the broader potential for statistical modeling of empirical data to play an important role in finding and codifying biometric quality measures.

An image-set based face recognition algorithm is proposed that exploits the full geometrical interpretation of Canonical Correlation Analysis (CCA). CCA maximizes the correlation between two linear subspaces associated with image-sets, where an image-set is assumed to contain multiple images of a person's face. When these linear subspaces are viewed as points on a Grassmann manifold, then geodesic distance on the manifold becomes the natural way to compare image-sets. The proposed method is tested on the ORL data set where it achieves a rank one identification rate of 98.75%. The proposed method is also tested on a subset of the Face Recognition Grand Challenge Experiment 4 data. Specifically, 82 probe and 230 gallery subjects with 32 images per probe and gallery image-set. Our algorithm achieves a rank one identification rate of 87% and a verification rate of 81% at a false accept rate of 1/1;000. These results on FRGC are significantly better than the well-known image-set matching algorithm, Mutual Subspace Method (MSM), which does not use geodesic distance. Another important finding is that cohort normalization boosts verification performance by 50% when used in conjunction with image-set matching. These results suggest that excellent levels of face recognition performance are possible when using image-sets, geodesic distance and cohort normalization. Finally, the proposed approach is generic in the sense that no training is required.

This paper develops a weakly supervised algorithm that learns to segment rigid multi-colored objects from a set of training images and key points. The approach uses congealing to learn a probabilistic spatial model of the multi-colored object class and graph-cut to separate the foreground from the background. The result is a novel approach which can segment heterogeneous objects, in contrast to other recent approaches which are better at segmenting uniform but possibly flexible objects.

Eigendecomposition is a common technique that is performed on sets of correlated images in a number of computer vision and robotics applications. Unfortunately, the computation of an eigendecomposition can become prohibitively expensive when dealing with very high-resolution images. While reducing the resolution of the images will reduce the computational expense, it is not known a priori how this will affect the quality of the resulting eigendecomposition. The work presented here provides an analysis of how different resolution reduction techniques affect the eigendecomposition. A computationally efficient algorithm for calculating the eigendecomposition based on this analysis is proposed. Examples show that this algorithm performs well on arbitrary video sequences.

This paper considers fitting a mixture of Gaussians model to high-dimensional data in scenarios where there are fewer data samples than feature dimensions. Issues that arise when using principal component analysis (PCA) to represent Gaussian distributions inside Expectation-Maximization (EM) are addressed, and a practical algorithm results. Unlike other algorithms that have been proposed, this algorithm does not try to compress the data to fit low-dimensional models. Instead, it models Gaussian distributions in the (N - 1)-dimensional space spanned by the N data samples. We are able to show that this algorithm converges on data sets where low-dimensional techniques do not.

The Cameron project has developed a language called single assignment C (SA-C), and a compiler for mapping image-based applications written in SA-C to field programmable gate arrays (FPGAs). The paper tests this technology by implementing several applications in SA-C and compiling them to an Annapolis Microsystems (AMS) WildStar board with a Xilinx XV2000E FPGA. The performance of these applications on the FPGA is compared to the performance of the same applications written in assembly code or C for an 800 MHz Pentium III. (Although no comparison across processors is perfect, these chips were the first of their respective classes fabricated at 0.18 microns, and are therefore of comparable ages.) We find that applications written in SA-C and compiled to FPGAs are between 8 and 800 times faster than the equivalent program run on the Pentium III.

This paper describes the implementation of an automatic target recognition (ATR) Probing algorithm on a reconfigurable system, using the SA-C programming language and optimizing compiler. The reconfigurable system is 800 times faster than a comparable Pentium running a C implementation of the same probing task. The reasons for this are analyzed.

The FERET evaluation compared recognition rates for different semi-automated and automated face recognition algorithms. We extend FERET by considering when differences in recognition rates are statistically distinguishable subject to changes in test imagery. Nearest Neighbor classifiers using principal component and linear discriminant subspaces are compared using different choices of distance metric. Probability distributions for algorithm recognition rates and pairwise differences in recognition rates are determined using a permutation methodology. The principal component subspace with Mahalanobis distance is the best combination; using L2 is second best. Choice of distance measure for the linear discriminant subspace matters little, and performance is always worse than the principal components classifier using either Mahalanobis or L1 distance. We make the source code for the algorithms, scoring procedures and Monte Carlo study available in the hopes others will extend this comparison to newer algorithms.

The number of features that can be completed over an image is, for practical purposes, limitless. Unfortunately, the number of features that can be computed and exploited by most computer vision systems is considerably less. As a result, it is important to develop techniques for selecting features from very large data sets that include many irrelevant or redundant features. This work addresses the feature selection problem by proposing a three-step algorithm. The first step uses a variation of the well known Relief algorithm to remove irrelevance; the second step clusters features using K-means to remove redundancy; and the third step is a standard combinatorial feature selection algorithm. This three-step combination is shown to be more effective than standard feature selection algorithms for large data sets with lots of irrelevant and redundant features. It is also shown to he no worse than standard techniques for data sets that do not have these properties. Finally, we show a third experiment in which a data set with 4096 features is reduced to 5% of its original size with very little information loss.

This paper describes a course in image computation that is designed to follow and build up an established course in computer graphics. The course is centered on images: how they are generated, manipulated, matched and symbolically described. It builds on the student's knowledge of coordinate systems and the perspective projection pipeline. It covers image generation techniques not covered by the computer graphics course, most notably ray tracing. It introduces students to basic image processing concepts such as Fourier analysis and then to basic computer vision topics such as principal components analysis, edge detection and symbolic feature matching. The goal is to prepare students for advanced work in either computer vision or computer graphics.

This paper describes the compilation of high-level language programs written in a single-assignment language called SA-C into the binary codes used for programming reconfigurable hardware. The primary application domain is image processing. The paper describes the SA-C language, the compiler and the optimizations it performs, the process of converting the intermediate form called dataflow graphs into VHDL, and the generation of hardware configuration codes. Performance data on a typical image processing program, written in SA-C and executed on a reconfigurable computing system, is presented and compared to a hand-written VHDL version and a C version running on conventional processors.

In recent years, increasing effort has gone into evaluating computer vision algorithms in general, and edge detection algorithms in particular. Most of the evaluation techniques use only a few test images, leaving open the question of how broadly their results can be interpreted. Our research tests the consistency of the receiver operating characteristic (ROC) curve, and demonstrates why consistent edge detector evaluation is difficult to achieve. We show how easily the framework can be manipulated to rank any of three modern edge detectors in any order by making minor changes to the test imagery. We also note that at least some of the inconsistency is the result of the erratic nature of the algorithms themselves, suggesting that it is still possible to create better edge detectors.

Color is a powerful cue for determining the pose of 3D objects viewed by a single camera. We present a method based on hue histograms for locating multiple objects with respect to a fixed camera. The algorithm is tested on controlled blocks-world scenes and an indoor office scene. On these examples, a pose refinement algorithm performs better when guided by color than when guided by more traditional edge information.

Previous research has shown that aggregated predictors improve the performance of non-parametric function approximation techniques. This paper presents the results of applying aggregated predictors to a computer vision problem, and shows that the method of bagging significantly improves performance. In fact, the results are better than those previously reported on other domains. This paper explains this performance in terms of the variance and bias.

The color associated with an object in machine vision images is not constant; under varying illuminating and viewing conditions (such as in outdoor images), the perceived color of an object can vary significantly, thus making color-based recognition difficult. Existing methods in color-based recognition have been applied mostly to indoor and/or constrained imagery, but not to realistic outdoor data. This work analyzes the variation of object color in outdoor images with respect to existing models of daylight illumination and surface reflectance. Two approaches for color recognition are then proposed: the first develops context-based models of daylight illumination and hybrid surface reflectance, and predicts the color of objects based on scene context. The second method shows that object color can be nonparametrically "learned" through classification methods such as Neural Networks and Multivariate Decision Trees. The methods have been successfully tested in domains such as road/highway scenes, off-road navigation and military target detection.

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

The field of computer vision has made significant advances over the past twenty years, yet we still have not developed a theoretical or practical understanding of how the many components of vision are combined into coherent, functioning systems. As a result, there are few applications of computer vision technology in the real world, even though the library of available computer vision techniques keeps growing. This paper models the control of visual procedures as a Markov decision problem, and presents a version of the schema learning system (SLS) that uses this model to assemble object recognition programs from existing computer vision algorithms. An example of SLS learning to recognize rooftops in aerial images is presented.

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 model registration system capable of tracking an object through distinct aspects in real-time is presented. The system integrates tracking, pose determination, and aspect graph indexing. The tracking combines steerable filters with normalized cross-correlation, compensates for rotation in 2D and is adaptive. Robust statistical methods are used in the pose estimation to detect and remove mismatches. The aspect graph is used to determine when features will disappear or become difficult to trade and to predict when and where new features will become trackable. The overall system is stable and is amenable to real-time performance.

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

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

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

Recent work in feature-based classification has focused on nonparametric techniques that can classify instances even when the underlying feature distributions are unknown. The inference algorithms for training these techniques, however, are designed to maximize the accuracy of the classifier, with all errors weighted equally. In many applications, certain errors are far more costly than others, and the need arises for nonparametric classification techniques that can be trained to optimize task-specific cost functions. This correspondence reviews the linear machine decision tree (LMDT) algorithm for inducing multivariate decision trees, and shows how LMDT can be altered to induce decision trees that minimize arbitrary misclassification cost functions (MCF's). Demonstrations of pixel classification in outdoor scenes show how MCF's can optimize the performance of embedded classifiers within the context of larger image understanding systems.>

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

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

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