We present an approach to capture the 3D motion of a group of people engaged in a social interaction. The core challenges in capturing social interactions are: (1) occlusion is functional and frequent; (2) subtle motion needs to be measured over a space large enough to host a social group; (3) human appearance and configuration variation is immense; and (4) attaching markers to the body may prime the nature of interactions. The Panoptic Studio is a system organized around the thesis that social interactions should be measured through the integration of perceptual analyses over a large variety of view points. We present a modularized system designed around this principle, consisting of integrated structural, hardware, and software innovations. The system takes, as input, 480 synchronized video streams of multiple people engaged in social activities, and produces, as output, the labeled time-varying 3D structure of anatomical landmarks on individuals in the space. Our algorithm is designed to fuse the "weak" perceptual processes in the large number of views by progressively generating skeletal proposals from low-level appearance cues, and a framework for temporal refinement is also presented by associating body parts to reconstructed dense 3D trajectory stream. Our system and method are the first in reconstructing full body motion of more than five people engaged in social interactions without using markers. We also empirically demonstrate the impact of the number of views in achieving this goal.

The papers in this special section examine the concept of automated face analysis (AFA). AFA has received special attention from the computer vision and pattern recognition communities. Research progress often gives the impression that problems such as face recognition and face detection are solved, at least for some scenarios. Several aspects of face analysis remain open problems, including the implementation of large scale face recognition/detection methods for in the wild images, emotion recognition, micro-expression analysis, and others. The community keeps making rapid progress on these topics, with continual improvement of current methods and creation of new ones that push the state-of-the-art. Applications are countless, including security and video surveillance, human computer/robot interaction, communication, entertainment, and commerce, while having an important social impact in assistive technologies for education and health. The importance of face analysis, together with the vast amount of work on the subject and the latest developments in the field, motivated us to organize a special section on this theme. The scope of the compilation comprises all aspects of face analysis from a computer vision perspective. Including, but not limited to: recognition, detection, alignment, reconstruction of faces, pose estimation of faces, gaze analysis, age, emotion, gender, and facial attributes estimation, and applications among others.

Pose Machines provide a sequential prediction framework for learning rich implicit spatial models. In this work we show a systematic design for how convolutional networks can be incorporated into the pose machine framework for learning image features and image-dependent spatial models for the task of pose estimation. The contribution of this paper is to implicitly model long-range dependencies between variables in structured prediction tasks such as articulated pose estimation. We achieve this by designing a sequential architecture composed of convolutional networks that directly operate on belief maps from previous stages, producing increasingly refined estimates for part locations, without the need for explicit graphical model-style inference. Our approach addresses the characteristic difficulty of vanishing gradients during training by providing a natural learning objective function that enforces intermediate supervision, thereby replenishing back-propagated gradients and conditioning the learning procedure. We demonstrate state-of-the-art performance and outperform competing methods on standard benchmarks including the MPII, LSP, and FLIC datasets.

A projector manipulates outgoing light rays, while a camera records incoming ones. Combining these optically inverse devices, especially in a coaxial manner, creates the possibility of a new computer-vision technology. The "Smart Headlight," currently under development at Carnegie Mellon's Robotics Institute, is one example: a device that can "erase" raindrops or snowflakes from a driver's sight, allowing for continuous use of the "high beams" mode while not causing glare against oncoming drivers, and enhance the appearance of important objects, such as pedestrians. In that sense, it constitutes a "genuine" augmented reality, manipulating the reality for how it appears to a viewer, rather than merely overlaying objects on the image of the reality. This talk will present the state of the Smart Headlight project and discuss further possible applications of projector-camera systems.

Automatic cell segmentation can hardly be flawless due to the complexity of image data particularly when time-lapse experiments last for a long time without biomarkers. To address this issue, we propose an interactive cell segmentation method by classifying feature-homogeneous superpixels into specific classes, which is guided by human interventions. Specifically, we propose to actively select the most informative superpixels by minimizing the expected prediction error which is upper bounded by the transductive Rademacher complexity, and then query for human annotations. After propagating the user-specified labels to the remaining unlabeled superpixels via an affinity graph, the error-prone superpixels are selected automatically and request for human verification on them; once erroneous segmentation is detected and subsequently corrected, the information is propagated efficiently over a gradually-augmented graph to un-labeled superpixels such that the analogous errors are fixed meanwhile. The correction propagation step is efficiently conducted by introducing a verification propagation matrix rather than rebuilding the affinity graph and re-performing the label propagation from the beginning. We repeat this procedure until most superpixels are classified into a specific category with high confidence. Experimental results performed on three types of cell populations validate that our interactive cell segmentation algorithm quickly reaches high quality results with minimal human interventions and is significantly more efficient than alternative methods, since the most informative samples are selected for human annotation/verification early.

We consider the problem of designing a scene-specific pedestrian detector in a scenario where we have zero instances of real pedestrian data (i.e., no labeled real data or unsupervised real data). This scenario may arise when a new surveillance system is installed in a novel location and a scene-specific pedestrian detector must be trained prior to any observations of pedestrians. The key idea of our approach is to infer the potential appearance of pedestrians using geometric scene data and a customizable database of virtual simulations of pedestrian motion. We propose an efficient discriminative learning method that generates a spatially-varying pedestrian appearance model that takes into the account the perspective geometry of the scene. As a result, our method is able to learn a unique pedestrian classifier customized for every possible location in the scene. Our experimental results show that our proposed approach outperforms classical pedestrian detection models and hybrid synthetic-real models. Our results also yield a surprising result, that our method using purely synthetic data is able to outperform models trained on real scene-specific data when data is limited.

In this paper, we propose a novel algorithm that infers the 3D layout of building facades from a single 2D image of an urban scene. Different from existing methods that only yield coarse orientation labels or qualitative block approximations, our algorithm quantitatively reconstructs building facades in 3D space using a set of planes mutually related by 3D geometric constraints. Each plane is characterized by a continuous orientation vector and a depth distribution. An optimal solution is reached through inter-planar interactions. Due to the quantitative and plane-based nature of our geometric reasoning, our model is more expressive and informative than existing approaches. Experiments show that our method compares competitively with the state of the art on both 2D and 3D measures, while yielding a richer interpretation of the 3D scene behind the image.

When data have a complex manifold structure or the characteristics of data evolve over time, it is unrealistic to expect a graph-based semi-supervised learning method to achieve flawless classification given a small number of initial annotations. To address this issue with minimal human interventions, we propose (i) a sample selection criterion used for active query of informative samples by minimizing the expected prediction error, and (ii) an efficient correction propagation method that propagates human correction on selected samples over a gradually-augmented graph to unlabeled samples without rebuilding the affinity graph. Experimental results conducted on three real world datasets validate that our active sample selection and correction propagation algorithm quickly reaches high quality classification results with minimal human interventions.

We present an approach to capture the 3D structure and motion of a group of people engaged in a social interaction. The core challenges in capturing social interactions are: (1) occlusion is functional and frequent, (2) subtle motion needs to be measured over a space large enough to host a social group, and (3) human appearance and configuration variation is immense. The Panoptic Studio is a system organized around the thesis that social interactions should be measured through the perceptual integration of a large variety of view points. We present a modularized system designed around this principle, consisting of integrated structural, hardware, and software innovations. The system takes, as input, 480 synchronized video streams of multiple people engaged in social activities, and produces, as output, the labeled time-varying 3D structure of anatomical landmarks on individuals in the space. The algorithmic contributions include a hierarchical approach for generating skeletal trajectory proposals, and an optimization framework for skeletal reconstruction with trajectory re-association.

Achieving sub-pixel accuracy with face alignment algorithms is a difficult task given the diversity of appearance in real world facial profiles. To capture variations in perspective, occlusion, and illumination with adequate precision, current face alignment approaches rely on detecting facial landmarks and iteratively adjusting deformable models that encode prior knowledge of facial structure. However, these methods involve optimization in latent sub-spaces, where user-specific face shape information is easily lost after dimensionality reduction. Attempting to retain this information to capture this wide range of variation requires a large training distribution, which is difficult to obtain without high computational complexity. Subsequently, many face alignment methods lack the pixel-level accuracy necessary to satisfy the aesthetic requirements of tasks such as face deidentification, face swapping, and face modeling. In many such applications, the primary source of aesthetic inadequacy is a misaligned jaw line or facial contour. In this work, we explore the idea of an image-based refinement method to fix the landmark points of a misaligned facial contour. We propose an efficient two stage process - an intuitively constructed edge detection based algorithm to actively adjust facial contour landmark points, and a data driven validation system to filter out erroneous adjustments. Experimental results show that state-of-the-art face alignment combined with our proposed post-processing method yields improved overall performance over multiple face image datasets.

We propose a data-driven approach to estimate the likelihood that an image segment corresponds to a scene object (its "objectness") by comparing it to a large collection of example object regions. We demonstrate that when the application domain is known, for example, in our case activity of daily living (ADL), we can capture the regularity of the domain specific objects using millions of exemplar object regions. Our approach to estimating the objectness of an image region proceeds in two steps: 1) finding the exemplar regions that are the most similar to the input image segment; 2) calculating the objectness of the image segment by combining segment properties, mutual consistency across the nearest exemplar regions, and the prior probability of each exemplar region. In previous work, parametric objectness models were built from a small number of manually annotated objects regions, instead, our data-driven approach uses 5 million object regions along with their metadata information. Results on multiple data sets demonstrates our data-driven approach compared to the existing model based techniques. We also show the application of our approach in improving the performance of object discovery algorithms.

Summary form only given. Detailed analysis of a human body in video, especially precise alignment of body parts, is a key technology for advanced surveillance that requires genuine understanding of people's behavior. The problem is far more difficult than whole-body detection and tracking because it has to deal with the high degree of freedom and self occlusion. This talk will discuss some recent progress in this important topic, and suggest further research.

Object representation is useful for many computer vision tasks, such as object detection, recognition, and tracking. Computer vision tasks must handle situations where unknown objects appear and must detect and track some object which is not in the trained database. In such cases, the system must learn or, otherwise derive, descriptions of new objects. In this paper, we investigate creating a representation of previously unknown objects that newly appear in the scene. The representation creates a viewpoint-invariant and scale-normalized model approximately describing an unknown object with multimodal sensors. Those properties of the representation facilitate 3D tracking of the object using 2D-to-2D image matching. The representation has both benefits of an implicit model (referred to as a view-based model) and an explicit model (referred to as a shape-based model). Experimental results demonstrate the viability of the proposed representation and outperform the existing approaches for 3D-pose estimation.

We present Marvin, a system that can search physical objects using a mobile or wearable device. It integrates HOG-based object recognition, SURF-based localization information, automatic speech recognition, and user feedback information with a probabilistic model to recognize the “object of interest” at high accuracy and at interactive speeds. Once the object of interest is recognized, the information that the user is querying, e.g. reviews, options, etc., is displayed on the user's mobile or wearable device. We tested this prototype in a real-world retail store during business hours, with varied degree of background noise and clutter. We show that this multi-modal approach achieves superior recognition accuracy compared to using a vision system alone, especially in cluttered scenes where a vision system would be unable to distinguish which object is of interest to the user without additional input. It is computationally able to scale to large numbers of objects by focusing compute-intensive resources on the objects most likely to be of interest, inferred from user speech and implicit localization information. We present the system architecture, the probabilistic model that integrates the multi-modal information, and empirical results showing the benefits of multi-modal integration.

Alignment of 3D objects from 2D images is one of the most important and well studied problems in computer vision. A typical object alignment system consists of a landmark appearance model which is used to obtain an initial shape and a shape model which refines this initial shape by correcting the initialization errors. Since errors in landmark initialization from the appearance model propagate through the shape model, it is critical to have a robust landmark appearance model. While there has been much progress in designing sophisticated and robust shape models, there has been relatively less progress in designing robust landmark detection models. In this paper we present an efficient and robust landmark detection model which is designed specifically to minimize localization errors thereby leading to state-of-the-art object alignment performance. We demonstrate the efficacy and speed of the proposed approach on the challenging task of multi-view car alignment.

The human body is structurally symmetric. Tracking by detection approaches for human pose suffer from double counting, where the same image evidence is used to explain two separate but symmetric parts, such as the left and right feet. Double counting, if left unaddressed can critically affect subsequent processes, such as action recognition, affordance estimation, and pose reconstruction. In this work, we present an occlusion aware algorithm for tracking human pose in an image sequence, that addresses the problem of double counting. Our key insight is that tracking human pose can be cast as a multi-target tracking problem where the ”targets” are related by an underlying articulated structure. The human body is modeled as a combination of singleton parts (such as the head and neck) and symmetric pairs of parts (such as the shoulders, knees, and feet). Symmetric body parts are jointly tracked with mutual exclusion constraints to prevent double counting by reasoning about occlusion. We evaluate our algorithm on an outdoor dataset with natural background clutter, a standard indoor dataset (HumanEva-I), and compare against a state of the art pose estimation algorithm.

Objects in a real world image cannot have arbitrary appearance, sizes and locations due to geometric constraints in 3D space. Such a 3D geometric context plays an important role in resolving visual ambiguities and achieving coherent object detection. In this paper, we develop a RANSAC-CRF framework to detect objects that are geometrically coherent in the 3D world. Different from existing methods, we propose a novel generalized RANSAC algorithm to generate global 3D geometry hypotheses from local entities such that outlier suppression and noise reduction is achieved simultaneously. In addition, we evaluate those hypotheses using a CRF which considers both the compatibility of individual objects under global 3D geometric context and the compatibility between adjacent objects under local 3D geometric context. Experiment results show that our approach compares favorably with the state of the art.

An urban operation of unmanned aerial vehicles (UAVs) demands a high level of autonomy for tasks presented in a cluttered environment. While fixed-wing UAVs have been well suited for long-endurance missions at a high altitude, their navigation inside an urban area brings more challenges in motion planning and control. The inability to hover and low agility in motion cause more difficulties on planning a feasible path in a compact region, and a limited payload allows only low-grade sensors for state estimation and control.

Wearable devices with gaze tracking can assist users in many daily-life tasks. When used for extended periods of time, it is desirable that such devices do not employ active illumination for safety reasons and to minimize interference from other light sources such as the sun. Most non active-illumination methods for gaze tracking attempt to locate the iris contour by fitting an ellipse. Although the camera projection causes the iris to appear as an ellipse in the eye image, it is actually a circle on the eye surface. Instead of searching for an ellipse in the eye image, the method proposed in this paper searches for a circle on the eye surface. To this end, the method calibrates a three-dimensional eye model based on the location of the corners of the eye. Using the 3D eye model, an input image is first transformed so that the eye's spherical surface is warped into a plane, thus “unwrapping” the eye. The iris circle is then detected on the unwrapped image by a three-step robust circle-fitting procedure. The location of the circle corresponds to the gaze orientation on the outside image. The method is fast to calibrate and runs in realtime. Extensive experimentation on embedded hardware and comparisons with alternative methods demonstrate the effectiveness of the proposed solution.

This paper presents a convenient self-calibration method for an inertial measurement unit (IMU) using matrix factorization. Using limited information about applied loads (accelerations or angular rates) available from natural references, the proposed method can linearly solve all the parameters of an IMU in any configuration of its inertial components. Our factorization-based calibration method exploits the bilinear form of an IMU measurement, which is the product of intrinsic calibration parameters and exerted loads. For a redundant IMU, we prove that partial knowledge of the loads, such as magnitude, can produce a linear solution space for a proper decomposition of the measurement. Theoretical analysis on this linear space reveals that a 1-D null space should be considered when load magnitudes are all equal (e.g., gravity loads). Degenerate load distributions are also geometrically identified to avoid singular measurement collection. Since a triad IMU has a lower number of sensor components than a 4-D parameter space, we propose an iterative factorization in which only initial bias is required. A wide convergence region of the bias can provide an automatic setting of the initial bias as the mean of the measurements. Performance of the proposed method is evaluated with respect to various noise levels and constraint types. Self-calibration capability is demonstrated using natural references, which are gravity for accelerometers and image stream from an attached camera for gyroscopes. Calibration results are globally optimal and identical to those of nonlinear optimization.

A wearable gaze tracking device can work with users in daily-life. For long time of use, a non-active method that does not employ an infrared illumination system is desirable from safety standpoint. It is well known that the eye model constraints substantially improve the accuracy and robustness of gaze estimation. However, the eye model needs to be calibrated for each person and each device. We propose a method to automatically build the eye model for a wearable gaze tracking device. The key idea is that the eye model, which includes the eye structure and eye-camera relationship, impose constraints on image analysis even when it is incomplete, so we adopt an iterative eye model building process with gradually increasing eye model constraints. Performance of the proposed method is evaluated in various situations, including different eye colors of users and camera configurations. We have confirmed that the gaze tracking system using our eye model works well under general situations: indoor, outdoor and driving scene.

During low-light conditions, drivers rely mainly on headlights to improve visibility. But in the presence of rain and snow, headlights can paradoxically reduce visibility due to light reflected off of precipitation back towards the driver. Precipitation also scatters light across a wide range of angles that disrupts the vision of drivers in oncoming vehicles. In contrast to recent computer vision methods that digitally remove rain and snow streaks from captured images, we present a system that will directly improve driver visibility by controlling illumination in response to detected precipitation. The motion of precipitation is tracked and only the space around particles is illuminated using fast dynamic control. Using a physics-based simulator, we show how such a system would perform under a variety of weather conditions. We build and evaluate a proof-of-concept system that can avoid water drops generated in the laboratory.

Autonomous vehicles must be capable of localizing even in GPS denied situations. In this paper, we propose a real-time method to localize a vehicle along a route using visual imagery or range information. Our approach is an implementation of topometric localization, which combines the robustness of topological localization with the geometric accuracy of metric methods. We construct a map by navigating the route using a GPS-equipped vehicle and building a compact database of simple visual and 3D features. We then localize using a Bayesian filter to match sequences of visual or range measurements to the database. The algorithm is reliable across wide environmental changes, including lighting differences, seasonal variations, and occlusions, achieving an average localization accuracy of 1 m over an 8 km route. The method converges correctly even with wrong initial position estimates solving the kidnapped robot problem.

We address the problem of 6D pose estimation of a textureless and shiny object from single-view 2D images, for a bin-picking task. For a textureless object like a mechanical part, conventional visual feature matching usually fails due to the absence of rich texture features. Hierarchical template matching assumes that few templates can cover all object appearances. However, the appearance of a shiny object largely depends on its pose and illumination. Furthermore, in a bin-picking task, we must cope with partial occlusions, shadows, and inter-reflections.

The articles in this special issue focus on advancements in quality of life technology, or QoLT. This is defined as intelligent systems that augment body and mind functions for self-determination for older adults and people with disabilities. QoLT systems can take many forms: they could be a device that a person carries or wears, a mobile system that accompanies a person, or a technology-embedded environment in which a person lives.

For understanding the behavior, intent, and environment of a person, the surveillance metaphor is traditional; that is, install cameras and observe the subject, and his/her interaction with other people and the environment. Instead, we argue that the first-person vision (FPV), which senses the environment and the subject's activities from a wearable sensor, is more advantageous with images about the subject's environment as taken from his/her view points, and with readily available information about head motion and gaze through eye tracking. In this paper, we review key research challenges that need to be addressed to develop such FPV systems, and describe our ongoing work to address them using examples from our prototype systems.

We propose a semi-Markov model trained in a max-margin learning framework for mitosis event segmentation in large-scale time-lapse phase contrast microscopy image sequences of stem cell populations. Our method consists of three steps. First, we apply a constrained optimization based microscopy image segmentation method that exploits phase contrast optics to extract candidate subsequences in the input image sequence that contains mitosis events. Then, we apply a max-margin hidden conditional random field (MM-HCRF) classifier learned from human-annotated mitotic and nonmitotic sequences to classify each candidate subsequence as a mitosis or not. Finally, a max-margin semi-Markov model (MM-SMM) trained on manually-segmented mitotic sequences is utilized to reinforce the mitosis classification results, and to further segment each mitosis into four predefined temporal stages. The proposed method outperforms the event-detection CRF model recently reported by Huh as well as several other competing methods in very challenging image sequences of multipolar-shaped C3H10T1/2 mesenchymal stem cells. For mitosis detection, an overall precision of 95.8% and a recall of 88.1% were achieved. For mitosis segmentation, the mean and standard deviation for the localization errors of the start and end points of all mitosis stages were well below 1 and 2 frames, respectively. In particular, an overall temporal location error of 0.73 ± 1.29 frames was achieved for locating daughter cell birth events.

In this paper we present an approach to robustly align facial features to a face image even when the face is partially occluded. Previous methods are vulnerable to partial occlusion of the face, since it is assumed, explicitly or implicitly, that there is no significant occlusion. In order to cope with this difficulty, our approach relies on two schemes: one is explicit multi-modal representation of the response from each of the face feature detectors, and the other is RANSAC hypothesize-and-test search for the correct alignment over subset samplings of those in the feature response modes. We evaluated the proposed method on a large number of facial images, occluded and non-occluded. The results demonstrated that the alignment is accurate and stable over a wide range of degrees and variations of occlusion.

We propose an approach to identify and segment objects from scenes that a person (or robot) encounters in Activities of Daily Living (ADL). Images collected in those cluttered scenes contain multiple objects. Each image provides only a partial, possibly very different view of each object. An object instance discovery program must be able to link pieces of visual information from multiple images and extract the consistent patterns.

The saliency of regions or objects in an image can be significantly boosted if they recur in multiple images. Leveraging this idea, cosegmentation jointly segments common regions from multiple images. In this paper, we propose CoSand, a distributed cosegmentation approach for a highly variable large-scale image collection. The segmentation task is modeled by temperature maximization on anisotropic heat diffusion, of which the temperature maximization with finite K heat sources corresponds to a K-way segmentation that maximizes the segmentation confidence of every pixel in an image. We show that our method takes advantage of a strong theoretic property in that the temperature under linear anisotropic diffusion is a submodular function; therefore, a greedy algorithm guarantees at least a constant factor approximation to the optimal solution for temperature maximization. Our theoretic result is successfully applied to scalable cosegmentation as well as diversity ranking and single-image segmentation. We evaluate CoSand on MSRC and ImageNet datasets, and show its competence both in competitive performance over previous work, and in much superior scalability.

The fast and accurate computation of surface normals from a point cloud is a critical step for many 3D robotics and automotive problems, including terrain estimation, mapping, navigation, object segmentation, and object recognition. To obtain the tangent plane to the surface at a point, the traditional approach applies total least squares to its small neighborhood. However, least squares becomes computationally very expensive when applied to the millions of measurements per second that current range sensors can generate. We reformulate the traditional least squares solution to allow the fast computation of surface normals, and propose a new approach that obtains the normals by calculating the derivatives of the surface from a spherical range image. Furthermore, we show that the traditional least squares problem is very sensitive to range noise and must be normalized to obtain accurate results. Experimental results with synthetic and real data demonstrate that our proposed method is not only more efficienThe fast and accurate computation of surface normals from a point cloud is a critical step for many 3D robotics and automotive problems, including terrain estimation, mapping, navigation, object segmentation, and object recognition. To obtain the tangent plane to the surface at a point, the traditional approach applies total least squares to its small neighborhood. However, least squares becomes computationally very expensive when applied to the millions of measurements per second that current range sensors can generate. We reformulate the traditional least squares solution to allow the fast computation of surface normals, and propose a new approach that obtains the normals by calculating the derivatives of the surface from a spherical range image. Furthermore, we show that the traditional least squares problem is very sensitive to range noise and must be normalized to obtain accurate results. Experimental results with synthetic and real data demonstrate that our proposed method is not only more efficient by up to two orders of magnitude, but provides better accuracy than the traditional least squares for practical neighborhood sizes.t by up to two orders of magnitude, but provides better accuracy than the traditional least squares for practical neighborhood sizes.

We present a drift-free attitude estimation method that uses image line segments for the correction of accumulated errors in integrated gyro rates when an unmanned aerial vehicle (UAV) operates in urban areas. Since man-made environments generally exhibit strong regularity in structure, a set of line segments that are either parallel or orthogonal to the gravitational direction can provide visual measurements for the absolute attitude from a calibrated camera. Line segments are robustly classified with the assumption that a single vertical vanishing point or multiple horizontal vanishing points exist. In the fusion with gyro angles, we introduce a new Kalman update step that directly uses line segments rather than vanishing points. The simulation and experiment based on urban images at distant views are provided to demonstrate that our method can serve as a robust visual attitude sensor for aerial robot navigation.

In robotic hands design tendon driven systems have been considered for years. The main advantage is a small end effector inertia e.g. a light, small hand with high dynamics due to remote actuators. To protect the actuators from impact in unknown environments a compliant mechanism can be used. It absorbs energy during an impact or saves energy to enhance the joint dynamics. In this paper an antagonistic tendon mechanism is presented. It fits 38 times in the DLR Hand Arm System forearm and enables is adapted to the different finger joints and different tendon lengths. A magnetic sensor was developed for the force measurement of the tendons. Finally, the calibration and the robustness are demonstrated through a set of experiments.

One of the fundamental requirements of an autonomous vehicle is the ability to determine its location on a map. Frequently, solutions to this localization problem rely on GPS information or use expensive three dimensional (3D) sensors. In this paper, we describe a method for long-term vehicle localization based on visual features alone. Our approach utilizes a combination of topological and metric mapping, which we call topometric localization, to encode the coarse topology of the route as well as detailed metric information required for accurate localization. A topometric map is created by driving the route once and recording a database of visual features. The vehicle then localizes by matching features to this database at runtime. Since individual feature matches are unreliable, we employ a discrete Bayes filter to estimate the most likely vehicle position using evidence from a sequence of images along the route. We illustrate the approach using an 8.8 km route through an urban and suburban environment. The method achieves an average localization error of 2.7 m over this route, with isolated worst case errors on the order of 10 m.

We present several algorithms for cell image analysis including microscopy image restoration, cell event detection and cell tracking in a large population. The algorithms are integrated into an automated system capable of quantifying cell proliferation metrics in vitro in real-time. This offers unique opportunities for biological applications such as efficient cell behavior discovery in response to different cell culturing conditions and adaptive experiment control. We quantitatively evaluated our system's performance on 16 microscopy image sequences with satisfactory accuracy for biologists' need. We have also developed a public website compatible to the system's local user interface, thereby allowing biologists to conveniently check their experiment progress online. The website will serve as a community resource that allows other research groups to upload their cell images for analysis and comparison.

In this paper we propose an image indexing and matching algorithm that relies on selecting distinctive high dimensional features. In contrast with conventional techniques that treated all features equally, we claim that one can benefit significantly from focusing on distinctive features. We propose a bag-of-words algorithm that combines the feature distinctiveness in visual vocabulary generation. Our approach compares favorably with the state of the art in image matching tasks on the University of Kentucky Recognition Benchmark dataset and on an indoor localization dataset. We also show that our approach scales up more gracefully on a large scale Flickr dataset.

Existing approaches to nonrigid structure from motion assume that the instantaneous 3D shape of a deforming object is a linear combination of basis shapes. These bases are object dependent and therefore have to be estimated anew for each video sequence. In contrast, we propose a dual approach to describe the evolving 3D structure in trajectory space by a linear combination of basis trajectories. We describe the dual relationship between the two approaches, showing that they both have equal power for representing 3D structure. We further show that the temporal smoothness in 3D trajectories alone can be used for recovering nonrigid structure from a moving camera. The principal advantage of expressing deforming 3D structure in trajectory space is that we can define an object independent basis. This results in a significant reduction in unknowns and corresponding stability in estimation. We propose the use of the Discrete Cosine Transform (DCT) as the object independent basis and empirically demonstrate that it approaches Principal Component Analysis (PCA) for natural motions. We report the performance of the proposed method, quantitatively using motion capture data, and qualitatively on several video sequences exhibiting nonrigid motions, including piecewise rigid motion, partially nonrigid motion (such as a facial expressions), and highly nonrigid motion (such as a person walking or dancing).

In this paper, we describe the explicit application of articulation constraints for estimating the motion of a system of articulated planes. We relate articulations to the relative homography between planes and show that these articulations translate into linearized equality constraints on a linear least-squares system, which can be solved efficiently using a Karush-Kuhn-Tucker system. The articulation constraints can be applied for both gradient-based and feature-based motion estimation algorithms and to illustrate this, we describe a gradient-based motion estimation algorithm for an affine camera and a feature-based motion estimation algorithm for a projective camera that explicitly enforces articulation constraints. We show that explicit application of articulation constraints leads to numerically stable estimates of motion. The simultaneous computation of motion estimates for all of the articulated planes in a scene allows us to handle scene areas where there is limited texture information and areas that leave the field of view. Our results demonstrate the wide applicability of the algorithm in a variety of challenging real-world cases such as human body tracking, motion estimation of rigid, piecewise planar scenes, and motion estimation of triangulated meshes.

Precisely localizing in an image a set of feature points that form a shape of an object, such as car or face, is called alignment. Previous shape alignment methods attempted to fit a whole shape model to the observed data, based on the assumption of Gaussian observation noise and the associated regularization process. However, such an approach, though able to deal with Gaussian noise in feature detection, turns out not to be robust or precise because it is vulnerable to gross feature detection errors or outliers resulting from partial occlusions or spurious features from the background or neighboring objects. We address this problem by adopting a randomized hypothesis-and-test approach. First, a Bayesian inference algorithm is developed to generate a shape-and-pose hypothesis of the object from a partial shape or a subset of feature points. For alignment, a large number of hypotheses are generated by randomly sampling subsets of feature points, and then evaluated to find the one that minimizes the shape prediction error. This method of randomized subset-based matching can effectively handle outliers and recover the correct object shape. We apply this approach on a challenging data set of over 5,000 different-posed car images, spanning a wide variety of car types, lighting, background scenes, and partial occlusions. Experimental results demonstrate favorable improvements over previous methods on both accuracy and robustness.

Due to the enormous potential and impact that stem cells may have on regenerative medicine, there has been a rapidly growing interest for tools to analyze and characterize the behaviors of these cells in vitro in an automated and high throughput fashion. Among these behaviors, mitosis, or cell division, is important since stem cells proliferate and renew themselves through mitosis. However, current automated systems for measuring cell proliferation often require destructive or sacrificial methods of cell manipulation such as cell lysis or in vitro staining. In this paper, we propose an effective approach for automated mitosis detection using phase-contrast time-lapse microscopy, which is a nondestructive imaging modality, thereby allowing continuous monitoring of cells in culture. In our approach, we present a probabilistic model for event detection, which can simultaneously 1) identify spatio-temporal patch sequences that contain a mitotic event and 2) localize a birth event, defined as the time and location at which cell division is completed and two daughter cells are born. Our approach significantly outperforms previous approaches in terms of both detection accuracy and computational efficiency, when applied to multipotent C3H10T1/2 mesenchymal and C2C12 myoblastic stem cell populations.

Detecting and segmenting cell regions in microscopic images is a challenging task, because cells typically do not have rich features, and their shapes and appearances are highly irregular and flexible. Furthermore, cells often form clusters, rendering the existing joint detection and segmentation algorithms unable to segment out individual cells. We address these difficulties by proposing a Heterogeneous Conditional Random Field (HCRF), in which different nodes have different state sets. The state sets are designed in such a way that the resulting HCRF model could encode all possible detection/segmentation cases while keeping its identifiability and compactness. Attributed to the provably optimal design of the state sets, the proposed model successfully realizes joint detection and segmentation of the cell regions into individual cells whether the cells are separate or touch one another. Experiments on two different types of cell images show that the HCRF outperforms several recently proposed methods.

High-throughput automated analysis of cell population behaviors in vitro is of great importance to biological research. In particular, automated quantification of cellular mitosis in time-lapse microscopy video is useful for multiple applications such as tissue engineering, cancer research, and developmental biology. Accurate localization and counting of mitosis are challenging since cells undergo drastic morphological and appearance changes during mitosis. To tackle this challenge, we propose a fully-automated detection method for cells imaged with phase contrast microscopy. The method consists of three stages: image preconditioning, spatiotemporal volume extraction and SVM - based mitosis event detection. First, the input images are transformed based on physics of phase contrast image formation such that potential mitosis regions are assigned high values. Second, volumetric region grow was performed on the transformed images to extract candidate mitosis regions. Third, mitosis events are detected in the candidates using a Support Vector Machine (SVM) classifier. The proposed method does not depend on empirical parameters, ad hoc image processing, or explicit cell tracking; and can be straightforwardly adapted to different cell types. It was validated with 10 image sequences consisting of 8000 images, and achieved excellent performance with 90.6% average precision and 95.6% average recall.

Detecting the boundaries of objects is a key step in separating foreground objects from the background, which is useful for robotics and computer vision applications, such as object detection, recognition, and tracking. We propose a new method for detecting object boundaries using planar laser scanners (LIDARs) and, optionally, co-registered imagery. We formulate boundary detection as a classification problem, in which we estimate whether a boundary exists in the gap between two consecutive range measurements. Features derived from the LIDAR and imagery are used to train a support vector machine (SVM) classifier to label pairs of range measurements as boundary or non-boundary. We compare this approach to an existing boundary detection algorithm that uses dynamically adjusted thresholds. Experiments show that the new method performs better even when only LIDAR features are used, and additional improvement occurs when image-based features are included, too. The new algorithm performs better on difficult boundary cases, such as obliquely viewed objects.

This paper evaluates the dynamic and kinematic properties of a prismatic mechanism and shows its capabilities in performing home manipulation tasks when integrated into a robotic arm. Our design is motivated from the observation that human hand motions often follow a linear trajectory when manipulating everyday objects. We present the mechanical design for a light-weight, energy-efficient robot named PRISM that emphasizes translational motion. By simulating the dynamics equations and comparing the structure of commonly used anthropomorphic arms and our proposed arm, we verify that translational motion is more energy efficient with PRISM, and the robot can maneuver itself in narrower places. Through simulation experiments using state of the art manipulation planning algorithms, we analyze the success rates of PRISM and an anthropomorphic robot arm in performing basic tasks. The simulation experiments center on pick-and-place tasks in cluttered kitchen scenes. We show a real-world prototype of PRISM and perform several manipulation experiments with it.

We propose a singularity-based mechanism (SBM) to exploit the singular configuration that improves the angular acceleration instead of constraining the movement. The tradeoff between the responsiveness and the range of motion is achieved by varying a length of linkage in the SBM. In this paper, we clarify the responsiveness of the SBM using the dynamics analysis. For the demonstration, we build an experimental SBM system with the high responsiveness, a practical range of motion, and a size comparable to a human arm. In the experiment, the effectiveness of the SBM is shown in a vertical lifting task. The characteristic of the SBM that generates a large acceleration at start is similar to the human arm moved by a muscle. The similarity between the SBM and the human arm is analyzed in terms of the static torque.

This paper discusses the advantages of singular configurations of a two-link robot arm in achieving tasks of pulling or lifting a heavy object. Optimal base location and arm motion for minimizing the joint torques are examined by numerical simulations, and the base location where the robot arm is near a singular configuration at the start time of task is optimal. It is shown analytically that joint torques can supply energy to the system composed of the robot arm and the object efficiently near singular configurations of the arm. The energy supply rates at two singular configurations are derived based on the equations of motion of the system.

We address the problem of interactive search for a target of interest in surveillance imagery. Our solution consists of iteratively learning a distance metric for retrieval, based on user feedback. The approach employs (retrieval) rank based constraints and convex optimization to efficiently learn the distance metric. The algorithm uses both user labeled and unlabeled examples in the learning process. The method is fast enough for a new metric to be learned interactively for each target query. In order to reduce the burden on the user, a model-independent active learning method is used to select key examples, for response solicitation. This leads to a significant reduction in the number of user-interactions required for retrieving the target of interest. The proposed method is evaluated on challenging pedestrian and vehicle data sets, and compares favorably to the state of the art in target re-acquisition algorithms.

There has been a recent push in extraction of 3D spatial layout of scenes. However, none of these approaches model the 3D interaction between objects and the spatial layout. In this paper, we argue for a parametric representation of objects in 3D, which allows us to incorporate volumetric constraints of the physical world. We show that augmenting current structured prediction techniques with volumetric reasoning significantly improves the performance of the state-of-the-art.

We present a multi-layered display that uses water drops as voxels. Water drops refract most incident light, making them excellent wide-angle lenses. Each 2D layer of our display can exhibit arbitrary visual content, creating a layered-depth (2.5D) display. Our system consists of a single projector-camera system and a set of linear drop generator manifolds that are tightly synchronized and controlled using a computer. Following the principles of fluid mechanics, we are able to accurately generate and control drops so that, at any time instant, no two drops occupy the same projector pixel's line-of-sight. This drop control is combined with an algorithm for space-time division of projector light rays. Our prototype system has up to four layers, with each layer consisting of an row of 50 drops that can be generated at up to 60 Hz. The effective resolution of the display is 50x projector vertical-resolution x number of layers. We show how this water drop display can be used for text, videos, and interactive games.

We study the problem of generating plausible interpretations of a scene from a collection of line segments automatically extracted from a single indoor image. We show that we can recognize the three dimensional structure of the interior of a building, even in the presence of occluding objects. Several physically valid structure hypotheses are proposed by geometric reasoning and verified to find the best fitting model to line segments, which is then converted to a full 3D model. Our experiments demonstrate that our structure recovery from line segments is comparable with methods using full image appearance. Our approach shows how a set of rules describing geometric constraints between groups of segments can be used to prune scene interpretation hypotheses and to generate the most plausible interpretation.

We present a robust shape model for localizing a set of feature points on a 2D image. Previous shape alignment models assume Gaussian observation noise and attempt to fit a regularized shape using all the observed data. However, such an assumption is vulnerable to gross feature detection errors resulted from partial occlusions or spurious background features. We address this problem by using a hypothesis-and-test approach. First, a Bayesian inference algorithm is developed to generate object shape and pose hypotheses from randomly sampled partial shapes - subsets of feature points. The hypotheses are then evaluated to find the one that minimizes the shape prediction error. The proposed model can effectively handle outliers and recover the object shape. We evaluate our approach on a challenging dataset which contains over 2,000 multi-view car images and spans a wide variety of types, lightings, background scenes, and partial occlusions. Experimental results demonstrate favorable improvements over previous methods on both accuracy and robustness.

This paper presents a target tracking framework for unstructured crowded scenes. Unstructured crowded scenes are defined as those scenes where the motion of a crowd appears to be random with different participants moving in different directions over time. This means each spatial location in such scenes supports more than one, or multi-modal, crowd behavior. The case of tracking in structured crowded scenes, where the crowd moves coherently in a common direction, and the direction of motion does not vary over time, was previously handled in. In this work, we propose to model various crowd behavior (or motion) modalities at different locations of the scene by employing Correlated Topic Model (CTM) of. In our construction, words correspond to low level quantized motion features and topics correspond to crowd behaviors. It is then assumed that motion at each location in an unstructured crowd scene is generated by a set of behavior proportions, where behaviors represent distributions over low-level motion features. This way any one location in the scene may support multiple crowd behavior modalities and can be used as prior information for tracking. Our approach enables us to model a diverse set of unstructured crowd domains, which range from cluttered time-lapse microscopy videos of cell populations in vitro, to footage of crowded sporting events.

Background subtraction algorithms define the background as parts of a scene that are at rest. Traditionally, these algorithms assume a stationary camera, and identify moving objects by detecting areas in a video that change over time. In this paper, we extend the concept of `subtracting' areas at rest to apply to video captured from a freely moving camera. We do not assume that the background is well-approximated by a plane or that the camera center remains stationary during motion. The method operates entirely using 2D image measurements without requiring an explicit 3D reconstruction of the scene. A sparse model of background is built by robustly estimating a compact trajectory basis from trajectories of salient features across the video, and the background is `subtracted' by removing trajectories that lie within the space spanned by the basis. Foreground and background appearance models are then built, and an optimal pixel-wise foreground/background labeling is obtained by efficiently maximizing a posterior function.

We propose a novel inertial-aided KLT feature tracking method robust to camera ego-motions. The conventional KLT uses images only and its working condition is inherently limited to small appearance change between images. When big optical flows are induced by a camera-ego motion, an inertial sensor attached to the camera can provide a good prediction to preserve the tracking performance. We use a low-grade MEMS-based gyroscope to refine an initial condition of the nonlinear optimization in the KLT. It increases the possibility for warping parameters to be in the convergence region of the KLT. For longer tracking with less drift, we use the affine photometric model and it can effectively deal with camera rolling and outdoor illumination change. Extra computational cost caused by this higher-order motion model is alleviated by restraining the Hessian update and GPU acceleration. Experimental results are provided for both indoor and outdoor scenes and GPU implementation issues are discussed.

This paper presents a study on the optimal base location and arm motion of a mobile manipulator for door opening task. Numerical simulation results show that the base location where the manipulability of the two-link arm is almost degenerated at the start and end points of door opening is optimal.We show by analysis that the location has an advantage in supplying kinetic energy to the door by using torques at the joints of arm. In order to represent properly the arm motion near a singular point of manipulability, the rotational motion of the door is parameterized by piecewise fifth order polynomials of time, and the parameters of polynomials are optimized to minimize the joint torques.

This paper presents a method to create an illusion of seeing moving objects through occluding surfaces in a video. This illusion is achieved by transferring information from a camera viewing the occluded area. In typical view interpolation approaches for 3D scenes, some form of correspondence across views is required. For occluded areas, establishing direct correspondence is impossible as information is missing in one of the views. Instead, we use a 2D projective invariant to capture information about occluded objects (which may be moving). Since invariants are quantities that do not change across views, a visually compelling rendering of hidden areas is achieved without the need for explicit correspondences. A piece-wise planar model of the scene allows the entire rendering process to take place without any 3D reconstruction, while still producing visual parallax. Because of the simplicity and robustness of the 2D invariant, we are able to transfer both static backgrounds and moving objects in real time. A complete working system has been implemented that runs live at 5Hz. Applications for this technology include the ability to look through corners at tight intersections for automobile safety, concurrent visualization of a surveillance camera network, and monitoring systems for patients/elderly/children.

In this paper, we describe the explicit application of articulation constraints for estimating the motion of a system of planes. We relate articulations to the relative homography between planes and show that for affine cameras, these articulations translate into linear equality constraints on a linear least squares system, yielding accurate and numerically stable estimates of motion. The global nature of motion estimation allows us to handle areas where there is limited texture information and areas that leave the field of view. Our results demonstrate the accuracy of the algorithm in a variety of cases such as human body tracking, motion estimation of rigid, piecewise planar scenes and motion estimation of triangulated meshes.

In this paper, we present a robust face alignment system that is capable of dealing with exaggerating expressions, large occlusions, and a wide variety of image noises. The robustness comes from our shape regularization model, which incorporates constrained nonlinear shape prior, geometric transformation, and likelihood of multiple candidate landmarks in a three-layered generative model. The inference algorithm iteratively examines the best candidate positions and updates face shape and pose. This model can effectively recover sufficient shape details from very noisy observations. We demonstrate the performance of this approach on two public domain databases and a large collection of real-world face photographs.

A close relationship exists between the advancement of face recognition algorithms and the availability of face databases varying factors that affect facial appearance in a controlled manner. The CMU PIE database has been very influential in advancing research in face recognition across pose and illumination. Despite its success the PIE database has several shortcomings: a limited number of subjects, a single recording session and only few expressions captured. To address these issues we collected the CMU Multi-PIE database. It contains 337 subjects, imaged under 15 view points and 19 illumination conditions in up to four recording sessions. In this paper we introduce the database and describe the recording procedure. We furthermore present results from baseline experiments using PCA and LDA classifiers to highlight similarities and differences between PIE and Multi-PIE.

In this paper, we propose a method for predicting typical operations performed by vehicle drivers such as ldquopushing a navigation buttonrdquo, ldquoadjusting the rear-view mirrorrdquo, or ldquoopening the console boxrdquo, before the driver actually reaches the target position. The prediction method uses the image position of anatomical landmarks (shoulders, elbows, and wrists) as they move over time. The difference of configurations among operations is modeled by a combination of clustering and discriminant analysis. The proposed method was applied to predict nine frequently executed operations inside a vehicle, running at over 150 frames per second. For five subjects, the method achieved an average prediction accuracy of 90% with a false positive rate of 1.4% at half the operation duration.

In this paper, we propose an algorithm for sustained tracking of humans, where we combine frame-to-frame articulated motion estimation with a per-frame body detection algorithm. The proposed approach can automatically recover from tracking error and drift. The frame-to-frame motion estimation algorithm replaces traditional dynamic models within a filtering framework. Stable and accurate per-frame motion is estimated via an image-gradient based algorithm that solves a linear constrained least squares system. The per-frame detector learns appearance of different body parts and dasiasketchespsila expected gradient maps to detect discriminant pose configurations in images. The resulting online algorithm is computationally efficient and has been widely tested on a large dataset of sequences of drivers in vehicles. It shows stability and sustained accuracy over thousands of frames.

Nighttime images of a scene from a surveillance camera have lower contrast and higher noise than their corresponding daytime images of the same scene due to low illumination. Denighting is an image enhancement method for improving nighttime images, so that they are closer to those that would have been taken during daytime. The method exploits the fact that background images of the same scene have been captured all day long with a much higher quality. We present several results of the enhancement of low quality nighttime images using denighting.

This paper presents a method for detecting people based on the co-occurrence of appearance and spatiotemporal features. Histograms of oriented gradients(HOG) are used as appearance features, and the results of pixel state analysis are used as spatiotemporal features. The pixel state analysis classifies foreground pixels as either stationary or transient. The appearance and spatiotemporal features are projected into subspaces in order to reduce the dimensions of the vectors by principal component analysis(PCA). The cascade AdaBoost classifier is used to represent the co-occurrence of the appearance and spatiotemporal features. The use of feature co-occurrence, which captures the similarity of appearance, motion, and spatial information within the people class, makes it an effective detector. Experimental results show that the performance of our method is about 29% better than that of the conventional method.

We present an easy-to-use calibration method for MEMS inertial sensor units based on the Factorization method which was originally invented for shape-and-motion recovery in computer vision. Our method requires no explicit knowledge of individual motions applied during calibration procedure. Instead a set of motion constraints in the form of an inner-product is used to factorize sensor measurements into a calibration matrix (that represents intrinsic sensor parameters) and a motion matrix (that represents acceleration or angular velocity). These motion constraints can be collected quickly from a low-cost calibration apparatus. Our method is not limited to just triad configurations but also applicable to any coordination of more than three sensor elements. A redundant configuration has the benefit that all the calibration parameters including biases are estimated at once. Simulation and experiments are provided to verify the proposed method.

An imaging sensor made of multiple light-weight non-overlapping cameras is an effective sensor for a small unmanned aerial vehicle that has strong payload limitation. This paper presents a method for motion estimation by assuming that such a multi-camera system is a spherical imaging system (that is, the cameras share a single optical center). We derive analytically and empirically a condition for a multi-camera system to be modeled as a spherical camera. Interestingly, not only does the spherical assumption simplify the algorithms and calibration procedure, but also motion estimation based on that assumption becomes more accurate.

Existing approaches to nonrigid structure from motion assume that the instantaneous 3D shape of a deforming object is a linear combination of basis shapes, which have to be estimated anew for each video sequence. In contrast, we propose that the evolving 3D structure be described by a linear combination of basis trajectories. The principal advantage of this lateral approach is that we do not need to estimate any basis vectors during computation. Instead, we show that generic bases over trajectories, such as the Discrete Cosine Transform (DCT) bases, can be used to effectively describe most real motions. This results in a significant reduction in unknowns, and corresponding stability, in estimation. We report empirical performance, quantitatively using motion capture data and qualitatively on several video sequences exhibiting nonrigid motions including piece-wise rigid motion, articulated motion, partially nonrigid motion (such as a facial expression), and highly nonrigid motion (such as a person dancing).

We present a novel feature representation for categorical object detection. Unlike previous approaches that have concentrated on generic interest-point detectors, we construct object-specific features directly from the training images. Our feature is represented by a collection of Flexible Edge Arrangement Templates (FEATs). We propose a two-stage semi-supervised learning approach to feature selection. A subset of frequent templates are first selected from a large template pool. In the second stage, we formulate feature selection as a regression problem and use LASSO method to find the most discriminative templates from the preselected ones. FEATs adaptively capture the image structure and naturally accommodate local shape variations. We show that this feature can be complemented by the traditional holistic patch method, thus achieving both efficiency and accuracy. We evaluate our method on three well-known car datasets, showing performance competitive with existing methods.

The goal of this paper is to find sparse and representative spatial priors that can be applied to part-based object localization. Assuming a GMRF prior over part configurations, we construct the graph structure of the prior by regressing the position of each part on all other parts, and selecting the neighboring edges using a Lasso-based method. This approach produces a prior structure which is not only sparse, but also faithful to the spatial dependencies that are observed in training data. We evaluate the representation power of the learned prior structure in two ways: first is drawing samples from the prior, and comparing them with the samples produced by the GMRF priors of other structures; second is comparing the results when applying different priors to a facial components localization task. We show that the learned graph captures meaningful geometrical variations with significantly sparser structure and leads to better parts localization results.

In this paper, an easy calibration method for projector is proposed. The calibration handled in this paper is projective relation between 3D space and 2D pattern, and is not correction of trapezoid distortion in projected pattern. In projector-camera systems, especially for 3D measurement, such calibration is the basis of process. The projection from projector can be modeled as inverse projection of the pinhole camera, which is generally considered as perspective projection. In the existing systems, some special objects or devices are often used to calibrate projector, so that 3D-2D projection map can be measured for typical camera calibration methods. The proposed method utilizes projective geometry between camera and projector, so that it requires only pre-calibrated camera and a plane. It is easy to practice, easy to calculate, and reasonably accurate.

This paper proposes a method of automated individualization of eye region model. The eye region model has been proposed in past research that parameterizes both the structure and the motion of the eye region. Without any prior knowledge, one can never determine a given appearance of eye region to be either neutral to any expression, i.e., the inherent structure of the eye region, or the result of motion by a facial expression. The past method manually individualized the model with respect to the structure parameters in the initial frame and tracks the motion parameters automatically across the rest of the image sequence, assuming the initial frame contains only neutral faces. Under the same assumption, we automatically determine the structure parameters for the given eye region image. We train active appearance models (AAMs) for parameterizing the variance of individuality. The system projects a given eye region image onto the low dimensional subspace spanned by the AAM and retrieves the structure parameters of the nearest training sample and initializes the eye region model using them. The AAMs are trained in the subregions, i.e., the upper eyelid region, the palpebral fissure (the eye aperture) region, and the lower eyelid region, respectively. It enables each AAM to effectively represent fine structures. Experimental results show the proposed method gives as nice initialization as manual labor and allows comparative tracking results for a comprehensive set of eye motions.

Appearance models (AM) are commonly used to model appearance and shape variation of objects in images. In particular, they have proven useful to detection, tracking, and synthesis of people's faces from video. While AM have numerous advantages relative to alternative approaches, they have at least two important drawbacks. First, they are especially prone to local minima in fitting; this problem becomes increasingly problematic as the number of parameters to estimate grows. Second, often few if any of the local minima correspond to the correct location of the model error. To address these problems, we propose filtered component analysis (FCA), an extension of traditional principal component analysis (PCA). FCA learns an optimal set of filters with which to build a multi-band representation of the object. FCA representations were found to be more robust than either grayscale or Gabor filters to problems of local minima. The effectiveness and robustness of the proposed algorithm is demonstrated in both synthetic and real data.

We present a nonparametric mode-seeking algorithm, called medoidshift, based on approximating the local gradient using a weighted estimate of medoids. Like meanshift, medoidshift clustering automatically computes the number of clusters and the data does not have to be linearly separable. Unlike meanshift, the proposed algorithm does not require the definition of a mean. This property allows medoidshift to find modes even when only a distance measure between samples is defined. In this sense, the relationship between the medoidshift algorithm and the meanshift algorithm is similar to the relationship between the k-medoids and the k-means algorithms. We show that medoidshifts can also be used for incremental clustering of growing datasets by recycling previous computations. We present experimental results using medoidshift for image segmentation, incremental clustering for shot segmentation and clustering on nonlinearly separable data.

Acquiring 3D models of intricate objects (like tree branches, bicycles and insects) is a hard problem due to severe self-occlusions, repeated thin structures and surface discontinuities. In theory, a shape-from-silhouettes (SFS) approach can overcome these difficulties and use many views to reconstruct visual hulls that are close to the actual shapes. In practice, however, SFS is highly sensitive to errors in silhouette contours and the calibration of the imaging system, and therefore not suitable for obtaining reliable shapes with a large number of views. We present a practical approach to SFS using a novel technique called coplanar shadowgram imaging, that allows us to use dozens to even hundreds of views for visual hull reconstruction. Here, a point light source is moved around an object and the shadows (silhouettes) cast onto a single background plane are observed. We characterize this imaging system in terms of image projection, reconstruction ambiguity, epipolar geometry, and shape and source recovery. The coplanarity of the shadowgrams yields novel geometric properties that are not possible in traditional multi-view camera- based imaging systems. These properties allow us to derive a robust and automatic algorithm to recover the visual hull of an object and the 3D positions of light source simultaneously, regardless of the complexity of the object. We demonstrate the acquisition of several intricate shapes with severe occlusions and thin structures, using 50 to 120 views.

We present an efficient two-phase approach to motion planning for small fixed-wing unmanned aerial vehicles (UAVs) navigating in complex 3D air slalom environments. A coarse global motion planner first computes a kinematically feasible obstacle-free path in a discretized 3D workspace which roughly satisfies the kinematic constraints of the UAV. Given a coarse global path, a fine local motion planner is used to compute a more accurate trajectory for the UAV at a higher level of detail. The local planner is iterated as the vehicle traverses and refines the global path as needed up to its planning horizon. We also introduce a new planning heuristic for 3D motions of fixed-wing UAVs based on 2D Dubins curves, along with precomputed sets of motion primitives derived from the vehicle dynamics model in order to achieve high efficiency.

We have equipped a Honda ASIMO humanoid with the ability to navigate autonomously in obstacle-filled environments. In addition to finding its way through known, fixed obstacle configurations, the planning system can reason about the future state of the world to locomote through challenging environments when the obstacle motions can be inferred from observation. This video presents work using a vision system to predict the velocities of objects in the scene, allowing ASIMO to safely navigate autonomously through a dynamic environment. Neither obstacle positions nor velocities are known at the start of the trial, but are estimated online as the robot walks. The planner constantly adjusts the footstep path with the latest estimates of ASIMO’s position and the obstacle trajectories, allowing the robot to successfully circumnavigate the moving obstacles.

For humanoid robots to fully realize their biped potential in a three-dimensional world and step over, around or onto obstacles such as stairs, appropriate and efficient approaches to execution, planning and perception are required. To this end, we have accelerated a robust model-based three-dimensional tracking system by programmable graphics hardware to operate online at frame-rate during locomotion of a humanoid robot. The tracker recovers the full 6 degree-of- freedom pose of viewable objects relative to the robot. Leveraging the computational resources of the GPU for perception has enabled us to increase our tracker's robustness to the significant camera displacement and camera shake typically encountered during humanoid navigation. We have combined our approach with a footstep planner and a controller capable of adaptively adjusting the height of swing leg trajectories. The resulting integrated perception-planning-action system has allowed an HRP-2 humanoid robot to successfully and rapidly localize, approach and climb stairs, as well as to avoid obstacles during walking.

One of the problems in developing a humanoid robot is caused by the fact that intermediate results, such as what the robot perceives the environment, and how it plans its moving path are hard to be observed online in the physical environment. What developers can see is only the behavior. Therefore, they usually investigate logged data afterwards, to analyze how well each component worked, or which component was wrong in the total system. In this paper, we present a novel environment for robot development, in which intermediate results of the system are overlaid on physical space using mixed reality technology. Real-time observation enables the developers to see intuitively, in what situation the specific intermediate results are generated, and to understand how results of a component affected the total system. This feature makes the development efficient and precise. This environment also gives a human-robot interface that shows the robot internal state intuitively, not only in development, but also in operation.

Most image registration problems are formulated in an asymmetric fashion. Given a pair of images, one is implicitly or explicitly regarded as a template and warped onto the other to match as well as possible. In this paper, we focus on this seemingly arbitrary choice of the roles and reveal how it may lead to biased warp estimates in the presence of relative scaling. We present a principled way of selecting the template and explain why only the correct asymmetric form, with the potential inclusion of a blurring step, can yield an unbiased estimator. We validate our analysis in the domain of model-based face tracking. We show how the usual Active Appearance Model (AAM) formulation overlooks the asymmetry issue, causing the fitting accuracy to degrade quickly when the observed objects are smaller than their model. We formulate a novel, "resolution-aware fitting" (RAF) algorithm that respects the asymmetry and incorporates an explicit model of the blur caused by the camera's sensing elements into the fitting formulation. We compare the RAF algorithm against a state-of-the-art tracker across a variety of resolutions and AAM complexity levels. Experimental results show that RAF significantly improves the estimation accuracy of both shape and appearance parameters when fitting to low-resolution data. Recognizing and accounting for the asymmetry of image registration leads to tangible accuracy improvements in analyzing low-resolution imagery.

Geometric reconstruction problems in computer vision are often solved by minimizing a cost function that combines the reprojection errors in the 2D images. In this paper, we show that, for various geometric reconstruction problems, their reprojection error functions share a common and quasiconvex formulation. Based on the quasiconvexity, we present a novel quasiconvex optimization framework in which the geometric reconstruction problems are formulated as a small number of small-scale convex programs that are ready to solve. Our final reconstruction algorithm is simple and has intuitive geometric interpretation. In contrast to existing local minimization approaches, our algorithm is deterministic and guarantees a predefined accuracy of the minimization result. The quasiconvexity also provides an intuitive method to handle directional uncertainties and outliers in measurements. When there are outliers in the measurements, our method provides a mechanism to locate the global minimum of a robust error function. For large scale problems and when computational resources are constrained, we provide an efficient approximation that gives a good upper bound (but not global minimum) on the reconstruction error. We demonstrate the effectiveness of our algorithm by experiments on both synthetic and real data.

This paper deals with part-based object recognition. We present a statistical shape model that characterizes both variations intrinsic to an object class and perturbations unique to each observation. Object parts, constrained by the learned shape model, are efficiently localized using the max-product algorithm on a triangulated Markov random field (TMRF). As a combination of both techniques, our system is able to recognize objects with large deformations and locate their parts accurately. We test our method on standard databases. The recognition performance is compared to the state of the art and favorable results are reported. 1

We present an approach for aligning a 3D deformable model to a single face image. The model consists of a set of sparse 3D points and the view-based patches associated with every point. Assuming a weak perspective projection model, our algorithm iteratively deforms the model and ad- justs the 3D pose to fit the image. As opposed to previous approaches, our algorithm starts the fitting without resort- ing to manual labeling of key facial points. And it makes no assumptions about global illumination or surface prop- erties, so it can be applied to a wide range of imaging con- ditions. Experiments demonstrate that our approach can effectively handle unseen faces with a variety of pose and illumination variations.

Geometric reconstruction problems in computer vision can be solved by minimizing the maximum of reprojection errors, i.e., the L\infty-norm. Unlike L2-norm (sum of squared reprojection errors), the global minimum of L\infty-norm can be efficiently achieved by quasiconvex optimization. However, the maximum of reprojection errors is the meaningful measure to minimize only when the measurement noises are independent and identically distributed at every 2D feature point and in both directions in the image. This is rarely the case in real data, where the positional noise not only varies at different features, but also has strong directionality. In this paper, we incorporate the directional uncertainty model into a quasiconvex optimization framework, in which global minimum of meaningful errors can be efficiently achieved, and accurate geometric reconstructions can be obtained from feature points that contain high directional uncertainty.

Many natural objects vary the shapes as linear combinations of certain bases. The measurement of such deformable shapes is coupling of rigid similarity transformations between the objects and the measuring systems and non-rigid deformations controlled by the linear bases. Thus registration and modeling of deformable shapes are coupled problems, where registration is to compute the rigid transformations and modeling is to construct the linear bases. The previous methods [3, 2] separate the solution into two steps. The first step registers the measurements regarding the shapes as rigid and the deformations as random noise. The second step constructs the linear model using the registered shapes. Since the deformable shapes do not vary randomly but are constrained by the underlying model, such separate steps result in registration biased by nonrigid deformations and shape models involving improper rigid transformations. We for the first time present this bias problem and formulate that, the coupled registration and modeling problems are essentially a single factorization problem and thus require a simultaneous solution. We then propose the Direct Factorization method that extends a structure from motion method [16]. It yields a linear closedform solution that simultaneously registers the deformable shapes at arbitrary dimensions (2D \to 2D, 3D \to 3D, . . .) and constructs the linear bases. The accuracy and robustness of the proposed approach are demonstrated quantitatively on synthetic data and qualitatively on real shapes.

Meetings are an integral part of business life for any organization. In previous work, we have developed a physical awareness system called CAMEO (camera assisted meeting event observer) to record and process the audio/visual information of a meeting. An important task in meeting understanding is to know who and how many people are attending the meeting. In this paper, we present an automatic approach to detect, track, and cluster people's faces in long video sequences. This is a challenging problem due to the appearance variability of people's faces (illumination, expression, pose,...). Two main novelties are presented: a robust real-time adaptive subspace face tracker which combines color and appearance. A temporal subspace clustering algorithm. The effectiveness and robustness of the proposed system is demonstrated over a data set of long videos (i.e. 1 hour).

Clustering is one of the most widely used statistical tools for data analysis. Among all existing clustering techniques, k-means is a very popular method because of its ease of programming and because it accomplishes a good trade-off between achieved performance and computational complexity. However, k-means is prone to local minima problems, and it does not scale too well with high dimensional data sets. A common approach to dealing with high dimensional data is to cluster in the space spanned by the principal components (PC). In this paper, we show the benefits of clustering in a low dimensional discriminative space rather than in the PC space (generative). In particular, we propose a new clustering algorithm called Discriminative Cluster Analysis (DCA). DCA jointly performs dimensionality reduction and clustering. Several toy and real examples show the benefits of DCA versus traditional PCA+k-means clustering. Additionally, a new matrix formulation is proposed and connections with related techniques such as spectral graph methods and linear discriminant analysis are provided.

As navigation autonomy becomes an increasingly important research topic for biped humanoid robots, efficient approaches to perception and mapping that are suited to the unique characteristics of humanoids and their typical operating environments are required. This paper presents a system for online environment reconstruction that utilizes both external sensors for global localization, and on-body sensors for detailed local mapping. An external optical motion capture system is used to accurately localize on-board sensors that integrate successive 2D views of a calibrated camera and range measurements from a SwissRanger SR-2 time-of-flight sensor to construct global environment maps in real-time. Environment obstacle geometry is encoded in 2D occupancy grids and 2.5D height maps for navigation planning. We present an on-body implementation for the HRP-2 humanoid robot that, combined with a footstep planner, enables the robot to autonomously traverse dynamic environments containing unpredictably moving obstacles

We propose a system that is capable of detailed analysis of eye region images in terms of the position of the iris, degree of eyelid opening, and the shape, complexity, and texture of the eyelids. The system uses a generative eye region model that parameterizes the fine structure and motion of an eye. The structure parameters represent structural individuality of the eye, including the size and color of the iris, the width, boldness, and complexity of the eyelids, the width of the bulge below the eye, and the width of the illumination reflection on the bulge. The motion parameters represent movement of the eye, including the up-down position of the upper and lower eyelids and the 2D position of the iris. The system first registers the eye model to the input in a particular frame and individualizes it by adjusting the structure parameters. The system then tracks motion of the eye by estimating the motion parameters across the entire image sequence. Combined with image stabilization to compensate for appearance changes due to head motion, the system achieves accurate registration and motion recovery of eyes.

Matrix factorization has many applications in computer vision. Singular value decomposition (SVD) is the standard algorithm for factorization. When there are outliers and missing data, which often happen in real measurements, SVD is no longer applicable. For robustness iteratively re-weighted least squares (IRLS) is often used for factorization by assigning a weight to each element in the measurements. Because it uses L/sub 2/ norm, good initialization in IRLS is critical for success, but is nontrivial. In this paper, we formulate matrix factorization as a L/sub 1/ norm minimization problem that is solved efficiently by alternative convex programming. Our formulation 1) is robust without requiring initial weighting, 2) handles missing data straightforwardly, and 3) provides a framework in which constraints and prior knowledge (if available) can be conveniently incorporated. In the experiments we apply our approach to factorization-based structure from motion. It is shown that our approach achieves better results than other approaches (including IRLS) on both synthetic and real data.

Object detection is challenging partly due to the limited discriminative power of local feature descriptors. We amend this limitation by incorporating spatial constraints among neighboring features. We propose a two-step algorithm. First, a feature together with its spatial neighbors forms a flexible feature template. Two feature templates can be compared more informatively than two individual features without knowing the 3D object model. A large portion of false matches can be excluded after the first step. In a second global matching step, object detection is formulated as a graph-matching problem. A model graph is constructed by applying Delaunay triangulation on the surviving features. The best matching graph in an input image is computed by finding the maximum a posterior (MAP) estimate of a binary Markov random field with triangular maximal clique. The optimization is solved by the max-product algorithm (a.k.a. belief propagation). Experiments on both rigid and non-rigid objects demonstrate the generality and efficacy of the proposed methods.

Object detection is challenging partly due to the limited discriminative power of local feature descriptors. We propose a two-step algorithm. First, a feature together with its spatial neighbors forms a flexible feature template. Two feature templates can be compared more informatively than two individual features without knowing the 3D object model. A large portion of false matches can be excluded after the first step. In a second global matching step, object detection is formulated as a graph-matching problem. A model graph is constructed by applying Delaunay triangulation on the surviving features. The best matching graph in an input image is computed by finding the maximum a posterior (MAP) estimate of a binary Markov random field with triangular maximal clique. The optimization is solved by the max-product algorithm (a.k.a. belief propagation). Experiments on both rigid and nonrigid objects demonstrate the generality and efficacy of the proposed methods.

Geometric reconstruction problems in computer vision are often solved by minimizing a cost function that combines the reprojection errors in the 2D images. In this paper, we show that, for various geometric reconstruction problems, their reprojection error functions share a common and quasiconvex formulation. Based on the quasiconvexity, we present a novel quasiconvex optimization framework in which the geometric reconstruction problems are formulated as a small number of small-scale convex programs that are ready to solve. Our final reconstruction algorithm is simple and has intuitive geometric interpretation. In contrast to existing random sampling or local minimization approaches. Our algorithm is deterministic and guarantees a predefined accuracy of the minimization result. We demonstrate the effectiveness of our algorithm by experiments on both synthetic and real data.

In this paper, we study the relationship between multi-view active appearance model (AAM) fitting and camera calibration. In the first part of the paper we propose an algorithm to calibrate the relative orientation of a set of N > 1 cameras by fitting an AAM to sets of N images. In essence, we use the human face as a (non-rigid) calibration grid. Our algorithm calibrates a set of 2 /spl times/ 3 weak-perspective camera projection matrices, protections of the world coordinate system origin into the images, depths of the world coordinate system origin, and focal lengths. We demonstrate that the performance of this algorithm is comparable to a standard algorithm using a calibration grid. In the second part of the paper, we show how calibrating the cameras improves tile performance of multi-view AAM fitting.

Reconstruction of 3D structures from uncalibrated image sequences has a wealthy history. Most work has been focused on rigid objects or static scenes. This paper studies the problem of perspective reconstruction of deformable structures such as dynamic scenes from an uncalibrated image sequence. The task requires decomposing the image measurements into a composition of three factors: 3D deformable structures, rigid rotations and translations, and intrinsic camera parameters. We develop a factorization algorithm that consists of two steps. In the first step we recover the protective depths iteratively using the sub-space constraints embedded in the image measurements of the deformable structures. In the second step, we scale the image measurements by the reconstructed projective depths. We then extend the linear closed-form solution for weak-perspective reconstruction by J. Xiao, et al. (2004) to factorize the scaled measurements and simultaneously reconstruct the deformable shapes and underlying shape model, the rigid motions, and the varying camera parameters such as focal lengths. The accuracy and robustness of the proposed method is demonstrated quantitatively on synthetic data and qualitatively on real image sequences.

We propose a new “ content-free” image retrieval method which attempts to exploit certain common tendencies that exist among people’s interpretation of images from user feedbacks. The system simply accumulates records of user feedback and recycles them in the form of collaborative filtering. We discuss various issues of image retrieval, argue for the idea of content-free, and present results of experiment. The results indicate that the performance of content-free image retrieval improves with the number of accumulated feedbacks, outperforming a basic but typical conventional content-based image retrieval system.

Linear discriminant analysis (LDA) has been an active topic of research during the last century. However, the existing algorithms have several limitations when applied to visual data. LDA is only optimal for Gaussian distributed classes with equal covariance matrices, and only classes-1 features can be extracted. On the other hand, LDA does not scale well to high dimensional data (overfitting), and it cannot handle optimally multimodal distributions. In this paper, we introduce Multimodal Oriented Discriminant Analysis (MODA), a LDA extension which can overcome these drawbacks. A new formulation and several novelties are proposed:• An optimal dimensionality reduction for multimodal Gaussian classes with different covariances is derived. The new criteria allows for extracting more than classes-1 features.• A covariance approximation is introduced to improve generalization and avoid over-fitting when dealing with high dimensional data.• A linear time iterative majorization method is suggested in order to find a local optimum.Several synthetic and real experiments on face recognition show that MODA outperform existing linear techniques.

Despite the recent achievements in stable dynamic walking for many humanoid robots, relatively little navigation autonomy has been achieved. In particular, the ability to autonomously select foot placement positions to avoid obstacles while walking is an important step towards improved navigation autonomy for humanoids. We present a footstep planner for the Honda ASIMO humanoid robot that plans a sequence of footstep positions to navigate toward a goal location while avoiding obstacles. The possible future foot placement positions are dependent on the current state of the robot. Using a finite set of state-dependent actions, we use an A* search to compute optimal sequences of footstep locations up to a time-limited planning horizon. We present experimental results demonstrating the robot navigating through both static and dynamic known environments that include obstacles moving on predictable trajectories.

Meetings are a very important part of everyday life for professionals working in universities, companies or governmental institutions. We have designed a physical awareness system called CAMEO (Camera Assisted Meeting Event Observer), a hardware/software system to record and monitor people's activities in meetings. CAMEO captures a high resolution omnidirectional view of the meeting by stitching images coming from almost concentric cameras. Besides recording capability, CAMEO automatically detects people and learns a person-specific facial appearance model (PS-FAM) for each of the participants. The PSFAMs allow more robust/reliable tracking and identification. In this paper, we describe the video-capturing device, photometric/geometric autocalibration process, and the multiple people tracking system. The effectiveness and robustness of the proposed system is demonstrated over several real-time experiments and a large data set of videos.

This paper describes an online 3D reconstruction system from stereo image sequences to obtain a dense local world model for robot navigation. The proposed method consists of three components: 1) stereo depth map calculation, 2) correspondence calculation in time sequential images by tracking raw image features, 3) 6DOF camera motion estimation by RANSAC and integrate depth map into 3D reconstructed model. We examined and evaluated our method in a motion capture environment for comparison. Finally experimental results of a humanoid robot H7 are denoted.

This paper presents a newly designed and developed MR-compatible three-axis force sensor: its principle, structure and performance. It employs a new MR-compatible optical micrometry based on differential measure of light intensity. This technology enables highly accurate and sensitive two degrees-of-freedom displacement sensing by using optoelectronic devices and pair of fiber optics. In order to realize three-axis force sensitivity, two micrometers are aligned in orthogonal directions. The accuracy of this force sensor is better than 3.0% and the maximum displacement of the detector is about 40 /spl mu/m under the applied force ranging from 0 to 15 N in vertical, and -8 to 8 N in horizontal directions. The loss of homogeneity of the magnetic field and signal-to-noise ratio of the MR image caused by this sensor are observed to be 0.49 ppm and 0.49 to 7.30% that show the sufficient MR compatibility of this sensor.

Just as optical flow is the two-dimensional motion of points in an image, scene flow is the three-dimensional motion of points in the world. The fundamental difficulty with optical flow is that only the normal flow can be computed directly from the image measurements, without some form of smoothing or regularization. In this paper, we begin by showing that the same fundamental limitation applies to scene flow; however, many cameras are used to image the scene. There are then two choices when computing scene flow: 1) perform the regularization in the images or 2) perform the regularization on the surface of the object in the scene. In this paper, we choose to compute scene flow using regularization in the images. We describe three algorithms, the first two for computing scene flow from optical flows and the third for constraining scene tructure from the inconsistencies in multiple optical flows.

We present an approach for modeling and rendering a dynamic, real-world event from an arbitrary viewpoint, and at any time, using images captured from multiple video cameras. The event is modeled as a nonrigidly varying dynamic scene, captured by many images from different viewpoints, at discrete times. First, the spatio-temporal geometric properties (shape and instantaneous motion) are computed. The view synthesis problem is then solved using a reverse mapping algorithm, ray-casting across space and time, to compute a novel image from any viewpoint in the 4D space of position and time. Results are shown on real-world events captured in the CMU 3D Room, by creating synthetic renderings of the event from novel, arbitrary positions in space and time. Multiple such recreated renderings can be put together to create retimed fly-by movies of the event, with the resulting visual experience richer than that of a regular video clip, or switching between images from multiple cameras.

Active Appearance Models (AAMs) are a well studied 2D deformable model. One recently proposed extension of AAMs to multiple images is the Coupled-View AAM. Coupled-View AAMs model the 2D shape and appearance of a face in two or more views simultaneously. The major limitation of Coupled-View AAMs, however, is that they are specific to a particular set of cameras, both in geometry and the photometric responses. In this paper, we describe how a single AAM can be fit to multiple images, captured simultaneously by cameras with arbitrary geometry and response functions. Our algorithm retains the major benefits of Coupled-View AAMs: the integration of information from multiple images into a single model, and improved fitting robustness. 1

A surface is often modeled as a triangulated mesh of 3D points and textures associated with faces of the mesh. The 3D points could be either sampled from range data or derived from a set of images using a stereo or Structurefrom- Motion algorithm. When the points do not lie at critical points of maximum curvature or discontinuities of the real surface, faces of the mesh do not lie close to the modeled surface. This results in textural artifacts, and the model is not perfectly coherent with a set of actual images—the ones that are used to texture-map its mesh. This paper presents a technique for perfecting the 3D surface model by repositioning its vertices so that it is coherent with a set of observed images of the object. The textural artifacts and incoherence with images are due to the non-planarity of a surface patch being approximated by a planar face, as observed from multiple viewpoints. Image areas from the viewpoints are used to represent texture for the patch in eigenspace. The eigenspace representation captures variations of texture, which we seek to minimize. A coherence measure based on the difference between the face textures reconstructed from eigenspace and the actual images is used to reposition the vertices so that the model is improved or faired. We refer to this technique of model refinement as EigenFairing, by which the model is faired, both geometrically and texturally, to better approximate the real surface.

This work describes two circular microphone arrays and a square microphone array which can be used for sound localization and sound capture. Sound capture by microphone array is achieved by sum and delay beam former (SDBF). A dedicated PCI 128-channel simultaneous input analog-to-digital (AD) board is developed for a 128 ch microphone array with a maximum sampling rate of 22. 7 /spl mu/s/sample. Simulation of sound pressure distribution of 24 and 128 ch circular microphone array and 128 ch square microphone array are shown. Then a 24 ch circular microphone array and a 128 ch square microphone array have been developed. The 24 ch circular microphone array can capture sound from an arbitrary direction. The 128 ch square microphone array can capture sound from a specific point. Both systems are evaluated by using frequency components of the sound. The circular type system can be used on a mobile robot including humanoid robot and square type can be extended towards room coverage type application.

Summary form only given. X-ray computerized tomography (CT) and related imaging modalities (e.g., PET) are notorious for their excessive computational demands, especially when noise-resistant probabilistic methods such as regularized tomography are used. The basic idea of regularized tomography is to compute a smooth image whose simulated projections (line integrals) approximate the observed, noisy X-ray projections. The computational expense in previous methods stems from explicitly applying a large sparse projection matrix to enforce these smoothness and data fidelity constraints during each of many iterations of the algorithm. Here we review our recent work in regularized tomography in which the smoothness constraint is analytically transformed from the image to the projection domain, before any computations begin. As a result, iterations take place entirely in the projection domain, avoiding the repeated sparse matrix-vector products. A more surprising benefit is the decoupling of a large system of regularization equations into many small systems of simpler independent equations, whose solution requires an "embarassingly parallel" computation. Here, we demonstrate that this method provides linear speedup of regularized tomography for up to 20 compute nodes (Pentium 4, 1.5 GHz) on a 100 Mb/s network using a Matlab MPI implementation.

We have designed a physical awareness system called CAMEO, the camera assisted meeting event observer, which consists of a multi-camera omnidirectional vision system designed to be used in meeting environments. CAMEO is designed to monitor the activities of people in meetings so that it can generate a semantically-indexed summary of what occurred in the meeting. In this paper, we describe CAMEO's fast people detection and tracking module. This module makes use of a combination of frame differencing, face detection, and adaptive color blob tracking based on mean shift analysis to detect and track people in the panoramic image. We describe this algorithm and present experimental results from captured meeting logs.

This paper describes a method for robustly detecting and efficiently recognizing daily human behavior in the real world. The proposed method involves real-world sensorization using ultrasonic tags to robustly observe behavior, real-world virtualization to create a virtual environment by modeling real objects using a stereovision system, and virtual sensorization of virtualized objects in order to quickly register the handling of objects in the real world and efficiently recognizing specific human behavior. A behavior-to-speech system created based on this recognition method is also presented as a new application of this technology.

This paper proposes a system for quickly realizing a function for robustly detecting daily human activity events in handling objects in the real world. The system has three functions: 1) robustly measuring 3D positions of the objects; 2) quickly calibrating a system for measuring 3D positions of the objects; 3) quickly registering target activity events; and 4) robustly detecting the registered events in real time. As for 1), the system realizes robust measurement of 3D positions of the objects using an ultrasonic 3D tag system, which is a kind of a location sensor, and robust estimation algorithm known as random sample consensus (RANSAC). The paper evaluates the robustness by comparing RANSAC with a least-squares optimization method. As for 2), the system realizes quick calibration by a calibrating device having three or more ultrasonic transmitters. Quick calibration enables the system to be portable. As for 3), quick registration of target activity events is realized by a stereoscopic camera with ultrasonic 3D tags and interactive software for creating 3D shape model, creating virtual sensors based on the 3D shape model, and associating the virtual sensors with the target events. The system makes it possible to quickly create object-shaped sensors to which a new function for detecting activity events are added while maintaining the original functions of the objects.

This paper presents an algorithm for interactive character animation with kinematic constraints with limited computational time. In order to reduce necessary computation, the animation is not created by procedural algorithm but synthesized by deforming and concatenating short motion examples, each consisting of a sequence of postures. A keyframe placed between two consecutive motion examples is deformed by using inverse kinematics so that it satisfies given constraints. The motion examples between the keyframes are deformed to ensure continuity of postures in position and velocity. We parameterize each posture as a set of particles in an orthogonal coordinate system. The inverse kinematics method with the particle representation realizes fast and stable deformation of keyframe postures, and the deformation of motion examples are calculated on a frame-by-frame basis by decomposing a whole-body deformation into per-particle deformations. We present some examples of character animations synthesized at an interactive rate by this algorithm.

Shape-from-silhouette (SFS), also known as visual hull (VH) construction, is a popular 3D reconstruction method, which estimates the shape of an object from multiple silhouette images. The original SFS formulation assumes that the entire silhouette images are captured either at the same time or while the object is static. This assumption is violated when the object moves or changes shape. Hence the use of SFS with moving objects has been restricted to treating each time instant sequentially and independently. Recently we have successfully extended the traditional SFS formulation to refine the shape of a rigidly moving object over time. We further extend SFS to apply to dynamic articulated objects. Given silhouettes of a moving articulated object, the process of recovering the shape and motion requires two steps: (1) correctly segmenting (points on the boundary of) the silhouettes to each articulated part of the object, (2) estimating the motion of each individual part using the segmented silhouette. In this paper, we propose an iterative algorithm to solve this simultaneous assignment and alignment problem. Once we have estimated the shape and motion of each part of the object, the articulation points between each pair of rigid parts are obtained by solving a simple motion constraint between the connected parts. To validate our algorithm, we first apply it to segment the different body parts and estimate the joint positions of a person. The acquired kinematic (shape and joint) information is then used to track the motion of the person in new video sequences.

Visual hull (VH) construction from silhouette images is a popular method of shape estimation. The method, also known as shape-from-silhouette (SFS), is used in many applications such as non-invasive 3D model acquisition, obstacle avoidance, and more recently human motion tracking and analysis. One of the limitations of SFS, however, is that the approximated shape can be very coarse when there are only a few cameras. In this paper, we propose an algorithm to improve the shape approximation by combining multiple silhouette images captured across time. The improvement is achieved by first estimating the rigid motion between the visual hulls formed at different time instants (visual hull alignment) and then combining them (visual hull refinement) to get a tighter bound on the object's shape. Our algorithm first constructs a representation of the VHs called the bounding edge representation. Utilizing a fundamental property of visual hulls, which states that each bounding edge must touch the object at at least one point, we use multi-view stereo to extract points called colored surface points (CSP) on the surface of the object. These CSPs are then used in a 3D image alignment algorithm to find the 6 DOF rigid motion between two visual hulls. Once the rigid motion across time is known, all of the silhouette images are treated as being captured at the same time instant and the shape of the object is refined. We validate our algorithm on both synthetic and real data and compare it with space carving.

This paper presents a robust method to solve two coupled problems, ground-layer detection and vehicle ego-motion estimation, which appear in visual navigation. We virtually rotate the camera to the downward-looking pose in order to exploit the fact that the vehicle motion is roughly constrained to be planar motion on the ground. This camera geometry transformation together with the planar motion constraint will: 1) eliminate the ambiguity between rotational and translation ego-motion parameters, and 2) improve the Hessian matrix condition in the direct motion estimation process. The virtual downward-looking camera enables us to estimate the planar ego-motions even for small image patches. Such local measurements are then combined together, by a robust weighting scheme based on both ground plane geometry and motion compensated intensity residuals, for a global ego-motion estimation and ground plane detection. We demonstrate the effectiveness of our method by experiments on both synthetic and real data.

To accomplish successfully the complex future mission in civilian and military scenarios, robotic helicopters need to have controllers that exploit their full dynamic capabilities. The absence of high-fidelity simulation models has prevented the use of well established multivariable control techniques for the design of high-bandwidth full-flight-envelope control systems. Existing model-based controllers are of low bandwidth and cover only small portions of the vehicle's flight envelope. In this paper we present the results of the synergistic use of high-fidelity integrated modeling strategies, robust multivariable control techniques, and classical gain scheduling for the rapid and reliable design of high-bandwidth full-flight envelope controllers for robotic helicopters. We implemented and flight tested a gain-scheduled H/sub /spl infin// loop-shaping controller on the Carnegie Mellon University (CMU) Yamaha R-50 robotic helicopter. During the flight tests, the CMU R-50 flew several high-speed maneuvers. We believe that our modeling/control approach quickly delivers controllers that exploit the full dynamic capabilities of the airframe and thus are ready to be used by higher level navigation systems for complex autonomous missions.

An autonomous blimp for a surveillance system, which is circling around a specified target with only one camera, is designed in this paper. For this purpose, an extension of Lucas-Kanade algorithm for detection and tracking of features with rotation and scaling is provided, and a simplified structure-from-motion algorithm is applied to improve the accuracy of state estimation. A tracking controller is designed for the blimp which is an underactuated system. The desired path of the blimp is also generated from image information of a target. The blimp flies around the target automatically, after a commander sets it. Some experiments are performed indoors by using an aerial blimp.

This paper describes an ultrasonic tagging system developed for robustly observing human activity in a living area. Using ultrasonic transmitter tags with unique identifiers, the system is shown through experimental application to be able to track the three-dimensional motion of tagged objects in real time with high accuracy, resolution and robustness to occlusion. The use of an ultrasonic system is desirable because of its low cost and use of commercial components, and the proposed system achieves high accuracy and robustness through the use of many redundant sensors. The system employs multilateration to locate tagged objects using one of two estimation algorithms, a least-squares optimization method or a random sample consensus method.

This paper presents a position estimation method for multiple ultrasonic emitters which are activated simultaneously. Locations of ultrasonic emitters are generally calculated from distance data obtained at receivers, but the emitters must be activated one after another to avoid crosstalk. Thus, the sampling rate for each emitter decreases as the number of emitters increases. The authors solved this problem by activating multiple emitters simultaneously and applying a newly developed position estimation algorithm. This paper presents the theoretical analysis and the results of simulations and experiments.

The complete set of measurements that could ever be used by a passive 3D vision algorithm is the plenoptic function or light-field. We give a concise characterization of when the light-field of a Lambertian scene uniquely determines its shape and, conversely, when the shape is inherently ambiguous. In particular, we show that stereo computed from the light-field is ambiguous if and only if the scene is radiating light of a constant intensity (and color, etc.) over an extended region.

In this paper, we describe a reconstruction method for multiple motion scenes, which are scenes containing multiple moving objects, from uncalibrated views. Assuming that the objects are moving with constant velocities, the method recovers the scene structure, the trajectories of the moving objects, the camera motion, and the camera intrinsic parameters (except skews) simultaneously. We focus on the case where the cameras have unknown and varying focal lengths while the other intrinsic parameters are known. The number of the moving objects is automatically detected without prior motion segmentation. The method is based on a unified geometrical representation of the static scene and the moving objects. It first performs a projective reconstruction using a bilinear factorization algorithm and, then, converts the projective solution to a Euclidean one by enforcing metric constraints. Experimental results on synthetic and real images are presented.

We present an appearance-based virtual view generation method that allows viewers to fly through a real dynamic scene. The scene is captured by multiple synchronized cameras. Arbitrary views are generated by interpolating two original camera-views near the given viewpoint. The quality of the generated synthetic view is determined by the precision, consistency and density of correspondences between the two images. All or most of previous work that uses interpolation extracts the correspondences from these two images. However, not only is it difficult to do so reliably (the task requires a good stereo algorithm), but also the two images alone sometimes do not have enough information, due to problems such as occlusion. Instead, we take advantage of the fact that we have many views, from which we can extract much more reliable and comprehensive 3D geometry of the scene as a 3D model. Dense and precise correspondences between the two images, to be used for interpolation, are obtained using this constructed 3D model.

Differential interference contrast (DIC) microscopy is a powerful visualization tool used to study live biological cells. Its use, however, has been limited to qualitative observations. The inherent nonlinear relationship between the object properties and the image intensity makes quantitative analysis difficult. Toward quantitatively measuring optical properties of objects from DIC images, we develop a method to reconstruct the specimen's optical properties over a three-dimensional (3-D) volume. The method is a nonlinear optimization which uses hierarchical representations of the specimen and data. As a necessary tool, we have developed and validated a computational model for the DIC image formation process. We test our algorithm by reconstructing the optical properties of known specimens.

A system is described for acquiring multi-view video of a person moving through the environment. A real-time tracking algorithm adjusts the pan, tilt, zoom and focus parameters of multiple active cameras to keep the moving person centered in each view. The output of the system is a set of synchronized, time-stamped video streams, showing the person simultaneously from several viewpoints.

Abstract Structure from motion (SFM), which is recovering camera motion and scene structure from image sequences, has various applications, such as scene modelling, robot navigation, object recognition and virtual reality. Most of previous research on SFM requires the use of intrinsically calibrated cameras. In this paper we describe a factorization‐based method to recover Euclidean structure from multiple perspective views with uncalibrated cameras. The method first performs a projective reconstruction using a bilinear factorization algorithm, and then converts the projective solution to a Euclidean one by enforcing metric constraints. The process of updating a projective solution to a full metric one is referred as normalization in most factorization‐based SFM methods. We present three normalization algorithms which enforce Euclidean constraints on camera calibration parameters to recover the scene structure and the camera calibration simultaneously, assuming zero skew cameras. The first two algorithms are linear, one for dealing with the case that only the focal lengths are unknown, and another for the case that the focal lengths and the constant principal point are unknown. The third algorithm is bilinear, dealing with the case that the focal lengths, the principal points and the aspect ratios are all unknown. The results of experiments are presented. Copyright © 2002 John Wiley & Sons, Ltd.

Nearly all super-resolution algorithms are based on the fundamental constraints that the super-resolution image should generate low resolution input images when appropriately warped and down-sampled to model the image formation process. (These reconstruction constraints are normally combined with some form of smoothness prior to regularize their solution.) We derive a sequence of analytical results which show that the reconstruction constraints provide less and less useful information as the magnification factor increases. We also validate these results empirically and show that, for large enough magnification factors, any smoothness prior leads to overly smooth results with very little high-frequency content. Next, we propose a super-resolution algorithm that uses a different kind of constraint in addition to the reconstruction constraints. The algorithm attempts to recognize local features in the low-resolution images and then enhances their resolution in an appropriate manner. We call such a super-resolution algorithm a hallucination or reconstruction algorithm. We tried our hallucination algorithm on two different data sets, frontal images of faces and printed Roman text. We obtained significantly better results than existing reconstruction-based algorithms, both qualitatively and in terms of RMS pixel error.

Representing images with layers has many important applications, such as video compression, motion analysis, and 3D scene analysis. This paper presents an approach to reliably extracting layers from images by taking advantages of the fact that homographies induced by planar patches in the scene form a low dimensional linear subspace. Layers in the input images will be mapped in the subspace, where it is proven that they form well-defined clusters and can be reliably identified by a simple mean-shift based clustering algorithm. Global optimality is achieved since all valid regions are simultaneously taken into account, and noise can be effectively reduced by enforcing the subspace constraint. Good layer descriptions are shown to be extracted in the experimental results.

Computer vision techniques can estimate 3D shape from images, but usually only up to a scale factor. The scale factor must be obtained by a physical measurement of the scene or the camera motion. Using gauge theory, we show that how this scale factor is determined can significantly affect the accuracy of the estimated shape. And yet these considerations have been ignored in previous works where 3D shape accuracy is optimized. We investigate how scale fixing influences the accuracy of 3D reconstruction and determine what measurement should be made to maximize the shape accuracy.

Outdoor scene classification is challenging due to irregular geometry, uncontrolled illumination, and noisy reflectance distributions. This paper discusses a Bayesian approach to classifying a color image of an outdoor scene. A likelihood model factors in the physics of the image formation process, sensor noise distribution, and prior distributions over geometry, material types, and illuminant spectrum parameters. These prior distributions are learned through a training process that uses color observations of planar scene patches over time. An iterative linear algorithm estimates the maximum likelihood reflectance, spectrum, geometry, and object class labels for a new image. Experiments on images taken by outdoor surveillance cameras classify known material types and shadow regions correctly, and flag as outliers material types that were not seen previously.

Most automatic expression analysis systems attempt to recognize a small set of prototypic expressions, such as happiness, anger, surprise, and fear. Such prototypic expressions, however, occur rather infrequently. Human emotions and intentions are more often communicated by changes in one or a few discrete facial features. In this paper, we develop an Automatic Face Analysis (AFA) system to analyze facial expressions based on both permanent facial features (brows, eyes, mouth) and transient facial features (deepening of facial furrows) in a nearly frontal-view face image sequence. The AFA system recognizes fine-grained changes in facial expression into action units (AUs) of the Facial Action Coding System (FACS), instead of a few prototypic expressions. Multistate face and facial component models are proposed for tracking and modeling the various facial features, including lips, eyes, brows, cheeks, and furrows. During tracking, detailed parametric descriptions of the facial features are extracted. With these parameters as the inputs, a group of action units (neutral expression, six upper face AUs and 10 lower face AUs) are recognized whether they occur alone or in combinations. The system has achieved average recognition rates of 96.4 percent (95.4 percent if neutral expressions are excluded) for upper face AUs and 96.7 percent (95.6 percent with neutral expressions excluded) for lower face AUs. The generalizability of the system has been tested by using independent image databases collected and FACS-coded for ground-truth by different research teams.

The Video Surveillance and Monitoring (VSAM) team at Carnegie Mellon University (CMU) has developed an end-to-end, multicamera surveillance system that allows a single human operator to monitor activities in a cluttered environment using a distributed network of active video sensors. Video understanding algorithms have been developed to automatically detect people and vehicles, seamlessly track them using a network of cooperating active sensors, determine their three-dimensional locations with respect to a geospatial site model, and present this information to a human operator who controls the system through a graphical user interface. The goal is to automatically collect and disseminate real-time information to improve the situational awareness of security providers and decision makers. The feasibility of real-time video surveillance has been demonstrated within a multicamera testbed system developed on the campus of CMU. This paper presents an overview of the issues and algorithms involved in creating this semiautonomous, multicamera surveillance system.

Differential Interference Contrast (DIC) microscopy is a powerful visualization tool used to study live biological cells. Its use, however, has been limited to qualitative observations. The inherent nonlinear relationship between the object properties and the image intensity makes quantitative analysis difficult. Towards quantitatively measuring optical properties of objects from DIC images, the authors develop a method to reconstruct the specimen's optical properties over a three-dimensional volume. The method is a nonlinear optimization which uses hierarchical representations of the specimen and data. As a necessary tool, the authors have developed and validated a computational model for the DIC image formation process. They test their algorithm by reconstructing the optical properties of known specimens.

We analyze the super-resolution reconstruction constraints. In particular we derive a sequence of results which all show that the constraints provide far less useful information as the magnification factor increases. It is well established that the use of a smoothness prior may help somewhat, however for large enough magnification factors any smoothness prior leads to overly smooth results. We therefore propose an algorithm that learns recognition-based priors for specific classes of scenes, the use of which gives far better super-resolution results for both faces and text.

We present a multi-PC/camera system that can perform 3D reconstruction and ellipsoid fitting of moving humans in real time. The system consists of five cameras. Each camera is connected to a PC which locally extracts the silhouettes of the moving person in the image captured by the camera. The five silhouette images are then sent, via local network, to a host computer to perform 3D voxel-based reconstruction by an algorithm called SPOT. Ellipsoids are then used to fit the reconstructed data. By using a simple and user-friendly interface, the user can display and observe, in real time and from any view-point, the 3D models of the moving human body. With a rate of higher than 15 frames per second, the system is able to capture non-intrusively, a sequence of human motions.

We describe an algorithm for reconstructing a scene containing multiple moving objects. Given a monocular image sequence, we recover the scene structure, the trajectories of the moving objects and the camera motion simultaneously. The number of the moving objects is automatically detected without prior motion segmentation. Assuming that the objects are moving linearly with constant speeds, we propose a unified geometrical representation of the static scene and the moving objects. This representation enables the embedding of the motion constraints into the scene structure, which leads to a factorization-based algorithm. Experimental results on synthetic and real images are presented.

Given a set of 3D points that we know lie on the surface of an object, we can define many possible surfaces that pass through all of these points. Even when we consider only surface triangulations, there are still an exponential number of valid triangulations that all fit the data. Each triangulation will produce a different faceted surface connecting the points. Our goal is to overcome this ambiguity and find the particular surface that is closest to the true object surface. We do not know the true surface but instead we assume that we have a set of images of the object. We propose selecting a triangulation based on its consistency with this set of images of the object. We present an algorithm that starts with an initial rough triangulation and refines the triangulation until it obtains a surface that best accounts for the images of the object. Our method is thus able to overcome the surface ambiguity problem and at the same time capture sharp corners and handle concave regions and occlusions. We show results for a few real objects.

In this paper, we describe a statistical method for 3D object detection. We represent the statistics of both object appearance and "non-object" appearance using a product of histograms. Each histogram represents the joint statistics of a subset of wavelet coefficients and their position on the object. Our approach is to use many such histograms representing a wide variety of visual attributes. Using this method, we have developed the first algorithm that can reliably detect human faces with out-of-plane rotation and the first algorithm that can reliably detect passenger cars over a wide range of viewpoints.

We develop an automatic system to analyze subtle changes in upper face expressions based on both permanent facial features (brows, eyes, mouth) and transient facial features (deepening of facial furrows) in a nearly frontal image sequence. Our system recognizes fine-grained changes in facial expression based on Facial Action Coding System (FACS) action units (AUs). Multi-state facial component models are proposed for tracting and modeling different facial features, including eyes, brews, cheeks, and furrows. Then we convert the results of tracking to detailed parametric descriptions of the facial features. These feature parameters are fed to a neural network which recognizes 7 upper face action units. A recognition rate of 95% is obtained for the test data that include both single action units and AU combinations.

The motion of a non-rigid scene over time imposes more constraints on its structure than those derived from images at a single time instant alone. An algorithm is presented for simultaneously recovering dense scene shape and scene flow (i.e. the instantaneous 3D motion at every point in the scene). The algorithm operates by carving away hexels, or points in the 6D space of all possible shapes and flows that are inconsistent with the images captures at either time instant, or across time. The recovered shape is demonstrated to be more accurate than that recovered using images at a single time instant. Applications of the combined scene shape and flow include motion capture for animation, retiming of videos, and non-rigid motion analysis.

Faces often appear very small in surveillance imagery because of the wide fields of view that are typically used and the relatively large distance between the cameras and the scene. For tasks such as face recognition, resolution enhancement techniques are therefore generally needed. Although numerous resolution enhancement algorithms have been proposed in the literature, most of them are limited by the fact that they make weak, if any, assumptions about the scene. We propose an algorithm to learn a prior on the spatial distribution of the image gradient for frontal images of faces. We proceed to show how such a prior can be incorporated into a resolution enhancement algorithm to yield 4- to 8-fold improvements in resolution (i.e., 16 to 64 times as many pixels). The additional pixels are, in effect, hallucinated.

Within the past decade, significant effort has occurred in developing methods of facial expression analysis. Because most investigators have used relatively limited data sets, the generalizability of these various methods remains unknown. We describe the problem space for facial expression analysis, which includes level of description, transitions among expressions, eliciting conditions, reliability and validity of training and test data, individual differences in subjects, head orientation and scene complexity image characteristics, and relation to non-verbal behavior. We then present the CMU-Pittsburgh AU-Coded Face Expression Image Database, which currently includes 2105 digitized image sequences from 182 adult subjects of varying ethnicity, performing multiple tokens of most primary FACS action units. This database is the most comprehensive testbed to date for comparative studies of facial expression analysis.

Most eye trackers work well for open eyes. However blinking is a physiological necessity for humans. More over, for applications such as facial expression analysis and driver awareness systems, we need to do more than tracking of the locations of the person's eyes but obtain their detailed description. We need to recover the state of the eyes (i.e., whether they are open or closed), and the parameters of an eye model (e.g., the location and radius of the iris, and the corners and height of the eye opening). We develop a dual-state model-based system for tracking eye features that uses convergent tracking techniques and show how it can be used to detect whether the eyes are open or closed, and to recover the parameters of the eye model. Processing speed on a Pentium II 400 MHz PC is approximately 3 frames/second. In experimental tests on 500 image sequences from child and adult subjects with varying colors of skin and eye, accurate tracking results are obtained in 98% of image sequences.

Most automatic expression analysis systems attempt to recognize a small set of prototypic expressions (e.g., happiness and anger). Such prototypic expressions, however, occur infrequently. Human emotions and intentions are communicated more often by changes in one or two discrete facial features. We develop an automatic system to analyze subtle changes in facial expressions based on both permanent (e.g., mouth, eye, and brow) and transient (e.g., furrows and wrinkles) facial features in a nearly frontal image sequence. Multi-state facial component models are proposed for tracking and modeling different facial features. Based on these multi-state models, and without artificial enhancement, we detect and track the facial features, including mouth, eyes, brow, cheeks, and their related wrinkles and facial furrows. Moreover we recover detailed parametric descriptions of the facial features. With these features as the inputs, 11 individual action units or action unit combinations are recognized by a neural network algorithm. A recognition rate of 96.7% is obtained. The recognition results indicate that our system can identify action units regardless of whether they occur singly or in combinations.

We describe a statistical method for 3D object detection. We represent the statistics of both object appearance and non-object appearance using a product of histograms. Each histogram represents the joint statistics of a subset of wavelet coefficients and their position on the object. Our approach is to use many such histograms representing a wide variety of visual attributes. Using this method, we have developed the first algorithm that can reliably detect human faces that vary from frontal view to full profile view and the first algorithm that can reliably detect cars over a wide range of viewpoints.

Registration of medical images enables quantitative study of anatomical differences between populations, as well as detection of abnormal variations indicative of pathologies. However inherent anatomical variabilities between individuals and possible pathologies make registration difficult. This paper presents a bootstrap strategy for characterizing non-pathological variations in human brain anatomy, as well its application to achieve accurate 3-D deformable registration. Inherent anatomical variations are initially extracted by deformably registering training data with an expert-segmented 3-D image, a digital brain atlas. Statistical properties of the density and geometric variations in brain anatomy are extracted and encoded into the atlas to build a statistical atlas. These statistics are then used as prior knowledge to guide the deformation process. A bootstrap loop is formed by registering the statistical atlas to larger training sets as more data becomes available, so as to ensure more robust knowledge extraction, and to achieve more precise registration. Compared to an algorithm with no knowledge guidance, registration using the statistical atlas reduces the overall error by 34%.

We describe a factorization-based method to recover 3D models from multiple perspective views with uncalibrated cameras. The method first performs a projective reconstruction using a bilinear factorization algorithm, and then converts the projective solution to a Euclidean one by enforcing metric constraints. We present three factorization-based normalization algorithms to generate the Euclidean reconstruction and the intrinsic parameters, assuming zero skews. The first two algorithms are linear, one for dealing with the case that only the focal lengths are unknown, and another for the case that the focal lengths and the constant principal point are unknown. The third algorithm is bilinear dealing with the case that the focal lengths, the principal points and the aspect ratios are all unknown. We present the results of applying this method to building modeling, terrain recovery and multi-camera calibration.

UTOMATED video surveillance addresses real-time observation of people and vehicles within a busy environment, leading to a description of their actions and interactions. The technical issues include moving object detection and tracking, object classification, human motion analysis, and activity understanding, touching on many of the core topics of computer vision, pattern analysis, and aritificial intelligence. Video surveillance has spawned large research projects in the United States, Europe, and Japan, and has been the topic of several international conferences and workshops in recent years. There are immediate needs for automated surveillance systems in commercial, law enforcement, and military applications. Mounting video cameras is cheap, but finding available human resources to observe the output is expensive. Although surveillance cameras are already prevalent in banks, stores, and parking lots, video data currently is used only “after the fact” as a forensic tool, thus losing its primary benefit as an active, real-time medium. What is needed is continuous 24-hour monitoring of surveillance video to alert security officers to a burglary in progress or to a suspicious individual loitering in the parking lot, while there is still time to prevent the crime. In addition to the obvious security applications, video surveillance technology has been proposed to measure traffic flow, detect accidents on highways, monitor pedestrian congestion in public spaces, compile consumer demographics in shopping malls and amusement parks, log routine maintainence tasks at nuclear facilities, and count endangered species. The numerous military applications include patrolling national borders, measuring the flow of refugees in troubled areas, monitoring peace treaties, and providing secure perimeters around bases and embassies. The 11 papers in this special section illustrate topics and techniques at the forefront of video surveillance research. These papers can be loosely organized into three categories. Detection and tracking involves real-time extraction of moving objects from video and continuous tracking over time to form persistent object trajectories. C. Stauffer and W.E.L. Grimson introduce unsupervised statistical learning techniques to cluster object trajectories produced by adaptive background subtraction into descriptions of normal scene activity. Viewpoint-specific trajectory descriptions from multiple cameras are combined into a common scene coordinate system using a calibration technique described by L. Lee, R. Romano, and G. Stein, who automatically determine the relative exterior orientation of overlapping camera views by observing a sparse set of moving objects on flat terrain. Two papers address the accumulation of noisy motion evidence over time. R. Pless, T. Brodský, and Y. Aloimonos detect and track small objects in aerial video sequences by first compensating for the self-motion of the aircraft, then accumulating residual normal flow to acquire evidence of independent object motion. L. Wixson notes that motion in the image does not always signify purposeful travel by an independently moving object (examples of such “motion clutter” are wind-blown tree branches and sun reflections off rippling water) and devises a flow-based salience measure to highlight objects that tend to move in a consistent direction over time. Human motion analysis is concerned with detecting periodic motion signifying a human gait and acquiring descriptions of human body pose over time. R. Cutler and L.S. Davis plot an object’s self-similarity across all pairs of frames to form distinctive patterns that classify bipedal, quadripedal, and rigid object motion. Y. Ricquebourg and P. Bouthemy track apparent contours in XT slices of an XYT sequence volume to robustly delineate and track articulated human body structure. I. Haritaoglu, D. Harwood, and L.S. Davis present W4, a surveillance system specialized to the task of looking at people. The W4 system can locate people and segment their body parts, build simple appearance models for tracking, disambiguate between and separately track multiple individuals in a group, and detect carried objects such as boxes and backpacks. Activity analysis deals with parsing temporal sequences of object observations to produce high-level descriptions of agent actions and multiagent interactions. In our opinion, this will be the most important area of future research in video surveillance. N.M. Oliver, B. Rosario, and A.P. Pentland introduce Coupled Hidden Markov Models (CHMMs) to detect and classify interactions consisting of two interleaved agent action streams and present a training method based on synthetic agents to address the problem of parameter estimation from limited real-world training examples. M. Brand and V. Kettnaker present an entropyminimization approach to estimating HMM topology and

Presents a stereo algorithm for obtaining disparity maps with occlusion explicitly detected. To produce smooth and detailed disparity maps, two assumptions that were originally proposed by Marr and Poggio (1976, 1979) are adopted: uniqueness and continuity. That is, the disparity maps have a unique value per pixel and are continuous almost everywhere. These assumptions are enforced within a three-dimensional array of match values in disparity space. Each match value corresponds to a pixel in an image and a disparity relative to another image. An iterative algorithm updates the match values by diffusing support among neighboring values and inhibiting others along similar lines of sight. By applying the uniqueness assumption, occluded regions can be explicitly identified. To demonstrate the effectiveness of the algorithm, we present the processing results from synthetic and real image pairs, including ones with ground-truth values for quantitative comparison with other methods.

This paper proposes a new scheme for multi-image projective reconstruction based on a projective grid space. The projective grid space is defined by two basis views and the fundamental matrix relating these views. Given fundamental matrices relating other views to each of the two basis views, this projective grid space can be related to any view. In the projective grid space as a general space that is related to all images, a projective shape can be reconstructed from all the images of weakly calibrated cameras. The projective reconstruction is one way to reduce the effort of the calibration because it does not need Euclid metric information, but rather only correspondences of several points between the images. For demonstrating the effectiveness of the proposed projective grid definition, we modify the voxel coloring algorithm for the projective voxel scheme. The quality of the virtual view images re-synthesized from the projective shape demonstrates the effectiveness of our proposed scheme for projective reconstruction from a large number of images.

Scene flow is the three-dimensional motion field of points in the world, just as optical flow is the two-dimensional motion field of points in an image. Any optical flow is simply the projection of the scene flow onto the image plane of a camera. We present a framework for the computation of dense, non-rigid scene flow from optical flow. Our approach leads to straightforward linear algorithms and a classification of the task into three major scenarios: complete instantaneous knowledge of the scene structure; knowledge only of correspondence information; and no knowledge of the scene structure. We also show that multiple estimates of the normal flow cannot be used to estimate dense scene flow directly without some form of smoothing or regularization.

Presents a new intensity-to-time processing paradigm suitable for very large scale integration (VLSI) computational sensor implementation of global operations over sensed images. Global image quantities usually describe images with fewer data. When computed at the point of sensing, global quantities result in a low-latency performance due to the reduced data transfer requirements between an image sensor and a processor. The global quantities also help global top-down adaptation: the quantities are continuously computed on-chip, and are readily available to sensing for adaptation. As an example, we have developed a sorting image computational sensor-a VLSI chip which senses an image and sorts all pixel by their intensities. The first sorting sensor prototype is a 21/spl times/26 array of cells. It receives an image optically, senses it, and computes the image's cumulative histogram-a global quantity which can be quickly routed off chip via one pin. In addition, the global cumulative histogram is used internally on-chip in a top-down fashion to adapt the values in individual pixel so as to reflect the index of the incoming light, thus computing an "image of indices". The image of indices never saturates and has a uniform histogram.

We study an application of image registration in the medical domain. Based on a 3-D hierarchical deformable registration algorithm, we have developed a prototype system which automatically aligns a standard atlas to a subject's data to create a customized atlas. Combined with domain knowledge, the registration algorithm can also detect asymmetries and abnormal variations in the subject's data that indicate the existence and location of pathologies. We have conducted tests on 106 MRI scans of normal brains, 3 MRI and 1 CT scan of brains with pathologies, with results qualitatively comparable to manual segmentation.

We have developed a computer vision system, including both facial feature extraction and recognition, that automatically discriminates among subtly different facial expressions. Expression classification is based on Facial Action Coding System (FACS) action units (AUs), and discrimination is performed using Hidden Markov Models (HMMs). Three methods are developed to extract facial expression information for automatic recognition. The first method is facial feature point tracking using a coarse-to-fine pyramid method. This method is sensitive to subtle feature motion and is capable of handling large displacements with sub-pixel accuracy. The second method is dense flow tracking together with principal component analysis (PCA) where the entire facial motion information per frame is compressed to a low-dimensional weight vector. The third method is high gradient component (i.e., furrow) analysis in the spatio-temporal domain, which exploits the transient variation associated with the facial expression. Upon extraction of the facial information, non-rigid facial expression is separated from the rigid head motion component, and the face images are automatically aligned and normalized using an affine transformation. This system also provides expression intensity estimation, which has significant effect on the actual meaning of the expression.

In this paper, we present a neural network-based face detection system. Unlike similar systems which are limited to detecting upright, frontal faces, this system detects faces at any degree of rotation in the image plane. The system employs multiple networks; a "router" network first processes each input window to determine its orientation and then uses this information to prepare the window for one or more "detector" networks. We present the training methods for both types of networks. We also perform sensitivity analysis on the networks, and present empirical results on a large test set. Finally, we present preliminary results for detecting faces rotated out of the image plane, such as profiles and semi-profiles.

In this paper, we present a neural network-based face detection system. Unlike similar systems which are limited to detecting upright, frontal faces, this system detects faces at any degree of rotation in the image plane. The system employs multiple networks; a "router" network first processes each input window to determine its orientation and then uses this information to prepare the window for one or more "detector" networks. We present the training methods for both types of networks. We also perform sensitivity analysis on the networks, and present empirical results on a large test set. Finally, we present preliminary results for detecting faces rotated out of the image plane, such as profiles and semi-profiles. 1. Introduction In our observations of face detector demonstrations, we have found that users expect faces to be detected at any angle, as shown in Figure 1. In this paper, we present a neural network-based algorithm to detect faces in gray-scale images. Unlike similar pre...

In this paper, we describe an algorithm for object recognition that explicitly models and estimated the posterior probability function, P(object/image). We have chosen a functional form of the posterior probability function that captures the joint statistics of local appearance and position on the object as well as the statistics of local appearance in the visual world at large. We use a discrete representation of local appearance consisting of approximately 10/sup 6/ patterns. We compute an estimate of P(object/image) in closed form by counting the frequency of occurrence of these patterns over various sets of training images. We have used this method for detecting human faces from frontal and profile views. The algorithm for frontal views has shown a detection rate of 93.0% with 88 false alarms on a set of 125 images containing 483 faces combining the MIT test set of Sung and Poggio with the CMU test sets of Rowley, Baluja, and Kanade. The algorithm for detection of profile views has also demonstrated promising results.

In this paper we present a unified factorization algorithm for recovering structure and motion from image sequences by using point features, line segments and planes. This new formulation is based on directional uncertainty model for features. Points and line segments are both described by the same probabilistic models and so can be recovered in the same way. Prior information on the coplanarity of features is shown to fit naturally into the new factorization formulation and provides additional constraints for the shape recovery. This formulation leads to a weighted least squares motion and shape recovery problem which is solved by an efficient quasi-linear algorithm. The statistical uncertainty model also enables us to recover uncertainty estimates for the reconstructed three dimensional feature locations.

We present Virtualized Reality, a technique to create virtual worlds out of dynamic events using densely distributed stereo views. The intensity image and depth map for each camera view at each time instant are combined to form a Visible Surface Model. Immersive interaction with the virtualized event is possible using a dense collection of such models. Additionally, a Complete Surface Model of each instant can be built by merging the depth maps from different cameras into a common volumetric space. The corresponding model is compatible with traditional virtual models and can be interacted with immersively using standard tools. Because both VSMs and CSMs are fully three-dimensional, virtualized models can also be combined and modified to build larger, more complex environments, an important capability for many non-trivial applications. We present results from 3D Dome, our facility to create virtualized models.

A motion estimation algorithm using wavelet approximation as an optical flow model has been developed to estimate accurate dense optical flow from an image sequence. This wavelet motion model is particularly useful in estimating optical flows with large displacement. Traditional pyramid methods which use the coarse-to-fine image pyramid by image burring in estimating optical flow often produce incorrect results when the coarse-level estimates contain large errors that cannot be corrected at the subsequent finer levels. This happens when regions of low texture become flat or certain patterns result in spatial aliasing due to image blurring. Our method, in contrast, uses large-to-small full-resolution regions without blurring images, and simultaneously optimizes the coarser and finer parts of optical flow so that the large and small motion can be estimated correctly. We compare results obtained by using our method with those obtained by using one of the leading optical flow methods, the Szeliski pyramid spline-based method. The experiments include cases of small displacement (less than 4 pixels under 128/spl times/128 image size or equivalent displacement under other image sizes), and those of large displacement (10 pixels). While both methods produce comparable results when the displacements are small, our method outperforms pyramid spline-based method when the displacements are large.

We present a neural network-based upright frontal face detection system. A retinally connected neural network examines small windows of an image and decides whether each window contains a face. The system arbitrates between multiple networks to improve performance over a single network. We present a straightforward procedure for aligning positive face examples for training. To collect negative examples, we use a bootstrap algorithm, which adds false detections into the training set as training progresses. This eliminates the difficult task of manually selecting nonface training examples, which must be chosen to span the entire space of nonface images. Simple heuristics, such as using the fact that faces rarely overlap in images, can further improve the accuracy. Comparisons with several other state-of-the-art face detection systems are presented, showing that our system has comparable performance in terms of detection and false-positive rates.

We present the concept that for uniformly rotated images, the optimal approximation of the images can be obtained by computing the basis vectors for the discrete cosine transform (DCT) of the original image in polar coordinates, and that the images can be represented as linear combinations of the basis vectors.

This paper proposes a novel approach to extract meaningful content information from video by collaborative integration of image understanding and natural language processing. As an actual example, we developed a system that associates faces and names in videos, called Name-It, which is given news videos as a knowledge source, then automatically extracts face and name association as content information. The system can infer the name of a given unknown face image, or guess faces which are likely to have the name given to the system. This paper explains the method with several successful matching results which reveal effectiveness in integrating heterogeneous techniques as well as the importance of real content information extraction from video, especially face-name association.

Spotting by Associationmethod for video analysis is a novel method to detect video segments with typical semantics.Video data contains various kinds of information through continuous images, natural language, and sound.For videos to be stored and retrieved in a Digital Libmry, it is essential to segment the video data into meaningful pieces.To detect meaningful segments, we need to identify the segment in each modality (video, language, and sound) that corresponds to the same story.For this purpose, we propose a new method for making correspondences between image clues detected by image analysis and language clues detected by natural language analysis.As a result, relevant video segments with sufficient information from every modality are obtained.We applied our method to closed-captioned CNN Headline News.Video segments with important events, such as a public speech, meeting, or visit, are detected fairly well.'For example, a close-up of a policeman's face and the name of the criminal.

Virtualized reality is a modeling technique that constructs full 3D virtual representations of dynamic events from multiple video streams. Image-based stereo is used to compute a range image corresponding to each intensity image in each video stream. Each range and intensity image pair encodes the scene structure and appearance of the scene visible to the camera at that moment, and is therefore called a visible surface model (VSM). A single time instant of the dynamic event can be modeled as a collection of VSMs from different viewpoints, and the full event can be modeled as a sequence of static scenes-the 3D equivalent of video. Alternatively, the collection of VSMs at a single time can be fused into a global 3D surface model, thus creating a traditional virtual representation out of real world events. Global modeling has the added benefit of eliminating the need to hand-edit the range images to correct errors made in stereo, a drawback of previous techniques. Like image-based rendering models, these virtual representations can be used to synthesize nearly any view of the virtualized event. For this reason, the paper includes a detailed comparison of existing view synthesis techniques with the authors' own approach. In the virtualized representations, however, scene structure is explicitly represented and therefore easily manipulated, for example by adding virtual objects to (or removing virtualized objects from) the model without interfering with real event. Virtualized reality, then, is a platform not only for image-based rendering but also for 3D scene manipulation.

We present a sequential factorization method for recovering the three-dimensional shape of an object and the motion of the camera from a sequence of images, using tracked features. The factorization method originally proposed by Tomasi and Kanade (1992) produces robust and accurate results incorporating the singular value decomposition. However, it is still difficult to apply the method to real-time applications, since it is based on a batch-type operation and the cost of the singular value decomposition is large. We develop the factorization method into a sequential method by regarding the feature positions as a vector time series. The new method produces estimates of shape and motion at each frame. The singular value decomposition is replaced with an updating computation of only three dominant eigenvectors, which can be performed in O(P/sup 2/) time, while the complete singular value decomposition requires O(FP/sup 2/) operations for an F/spl times/P matrix. Also, the method is able to handle infinite sequences, since it does not store any increasingly large matrices. Experiments using synthetic and real images illustrate that the method has nearly the same accuracy and robustness as the original method.

The factorization method, first developed by Tomasi and Kanade (1992), recovers both the shape of an object and its motion from a sequence of images, using many images and tracking many feature points to obtain highly redundant feature position information. The method robustly processes the feature trajectory information using singular value decomposition (SVD), taking advantage of the linear algebraic properties of orthographic projection. However, an orthographic formulation limits the range of motions the method can accommodate. Paraperspective projection, first introduced by Ohta et al. (1981), is a projection model that closely approximates perspective projection by modeling several effects not modeled under orthographic projection, while retaining linear algebraic properties. Our paraperspective factorization method can be applied to a much wider range of motion scenarios, including image sequences containing motion toward the camera and aerial image sequences of terrain taken from a low-altitude airplane.

This paper presents a linear algorithm for recovering 3D affine shape and motion from line correspondences with uncalibrated affine cameras. The algorithm requires a minimum of seven line correspondences over three views. The key idea is the introduction of a one-dimensional projective camera. This converts 3D affine reconstruction of "line directions" into 2D projective reconstruction of "points". In addition, a line-based factorization method is also proposed to handle redundant views. Experimental results both on simulated and real image sequences validate the robustness and the accuracy of the algorithm.

We present a fast pattern matching algorithm with a large set of templates. The algorithm is based on the typical template matching speeded up by the dual decomposition; the Fourier transform and the Karhunen-Loeve transform. The proposed algorithm is appropriate for the search of an object with unknown distortion within a short period. Patterns with different distortion differ slightly from each other and are highly correlated. The image vector subspace required for effective representation can be defined by a small number of eigenvectors derived by the Karhunen-Loeve transform. A vector subspace spanned by the eigenvectors is generated, and any image vector in the subspace is considered as a pattern to be recognized. The pattern matching of objects with unknown distortion is formulated as the process to extract the portion of the input image, find the pattern most similar to the extracted portion in the subspace, compute normalized correlation between them at each location in the input image, and find the location with the best score. Searching for objects with unknown distortion requires vast computation. The formulation above makes it possible to decompose highly correlated reference images into eigenvectors, as well as to decompose images in frequency domain, and to speed up the process significantly.

We have developed a video-rate stereo machine that has the capability of generating a dense depth map at the video rate. The performance bench marks of the CMU video-rate stereo machine are: 1) multi-image input of up to 6 cameras; 2) throughput of 30 million point/spl times/disparity measurement per second; 3) frame rate of 30 frame/sec; 4) a dense depth map of up to 256/spl times/240 pixels; 5) disparity search range of up to 60 pixels; 6) high precision of depth output up to 8 bits (with interpolation). The capability of passively producing such a dense depth map (3D representation) of a scene at the video rate can open up a new class of applications of 3D vision: merging real and virtual worlds in real time.

A family of structure from motion algorithms called the factorization method has been recently developed from the orthographic projection model to the affine camera model. All these algorithms are limited to handling only point features of the image stream. We propose in this paper an algorithm for the recovery of shape and motion from line correspondences by the factorization method with the affine camera. Instead of one step factorization for points, a multi-step factorization method is developed for lines based on the decomposition of the whole shape and motion into three separate substructures. Each of these substructures can then be linearly solved by factorizing the appropriate measurement matrices. It is also established that affine shape and motion with uncalibrated affine cameras can be achieved with at least seven lines over three views, which extends the previous results of Koenderink and Van Doorn (1989) for points to lines.

We present a neural network-based face detection system. A retinally connected neural network examines small windows of an image and decides whether each window contains a face. The system arbitrates between multiple networks to improve performance over a single network. We use a bootstrap algorithm for training the networks, which adds false detections into the training set as training progresses. This eliminates the difficult task of manually selecting non-face training examples, which must be chosen to span the entire space of non-face images. Comparisons with other state-of-the-art face detection systems are presented; our system has better performance in terms of detection and false-positive rates.

The need for low-latency vision systems is growing: high speed visual servoing and vision-based human computer interface. In this paper we present a new intensity-to-time processing paradigm suitable for low-latency massively parallel global computation over fine-grained data such as images. As an example of a low-latency global computation, we have developed a VLSI sorting computational sensor-a sensor which sorts all pixels of an input image by their intensities, as the image is being sensed. The first sorting sensor prototype is a 21 by 26 array of cells. It detects an image focused thereon and computes the image of indices as well as the image's cumulative histogram, before the intensity data are readout. The image of indices never saturates and has uniform histogram. Under user's control, the chip can perform other operations including simple segmentation and labeling.

We have been working on developing a visual/haptic interface for virtual environments. The authors have previously (1996) proposed a WYSIWYF (What You See Is What You Feel) concept which ensures a correct visual/haptic registration so that what the user can see via a visual interface is consistent with what he/she can feel through a haptic interface. The key components of the WYSIWYF display are (i) vision-based tracking, (ii) video keying, and (iii) physically-based simulation. The first prototype has been built and the proposed concept was demonstrated. It turned out, however, that the original system had a bottleneck in the vision tracking component and the performance was not satisfactory (slow frame rate and large latency). To solve the problem of our first prototype, we have implemented a fast tracker which can track more than 100 markers in video-rate. In this paper, new experimental results are shown followed by the improvements of the vision-based tracking component.

The structure from motion problem has been extensively studied in the field of computer vision. Yet, the bulk of the existing work assumes that the scene contains only a single moving object. The more realistic case where an unknown number of objects move in the scene has received little attention, especially for its theoretical treatment. We present a new method for separating and recovering the motion and shape of multiple independently moving objects in a sequence of images. The method does not require prior knowledge of the number of objects, nor is dependent on any grouping of features into an object at the image level. For this purpose, we introduce a mathematical construct of object shapes, called the shape interaction matrix, which is invariant to both the object motions and the selection of coordinate systems. This invariant structure is computable solely from the observed trajectories of image features without grouping them into individual objects. Once the structure is computed, it allows for segmenting features into objects by the process of transforming it into a canonical form, as well as recovering the shape and motion of each object.>

We describe our implementation of a parallel depth recovery scheme for a four-camera multibaseline stereo in a convergent configuration. Our system is capable of image capture at video rate. This is critical in applications that require three-dimensional tracking. We obtain dense stereo depth data by projecting a light pattern of frequency modulated sinusoidally varying intensity onto the scene, thus increasing the local discriminability at each pixel and facilitating matches. In addition, we make most of the camera view areas by converging them at a volume of interest. Results show that we are able to extract stereo depth data that are, on the average, less than 1 mm in error at distances between 1.5 to 3.5 m away from the cameras.>

Computer sensing of hand and limb motion is an important problem for applications in human computer interaction and computer graphics. We describe a framework for local trading of self occluding motion, in which one part of an object obstructs the visibility of another. Our approach uses a kinematic model to predict occlusions and windowed templates to track partially occluded objects. We present offline 3D tracking results for hand motion with significant self occlusion.>

A video-rate stereo machine has been developed at CMU with the capability of generating a dense range map, aligned with an intensity image, at the video rate. The target performance of the CMU video-rate stereo machine is: 1) multi-image input of 6 cameras; 2) high throughput of 30 million point/spl times/disparity measurement per second; 3) high frame rate of 30 frame/sec; 4) a dense depth map of 256/spl times/240 pixels; 5) disparity search range of up to 60 pixels; 6) high precision of up to 7 bits (with interpolation); and 7) uncertainty estimation available for each pixel.

The pose (position and orientation) of a polyhedral object can be determined by using a set of simple light-stripe range sensors. Data from these sensors, however, inherently contains errors which result in pose uncertainty. Therefore, in addition to calculating the pose itself, it is often desirable to estimate how certain the pose determination is. This paper presents a method for estimating the uncertainty in determining the pose of an arbitrarily positioned object with three light-stripe range finders. We analyze the perturbation of a least squares fit of sensed 3D segments to object faces, and obtain a relationship between the sensing error and the object pose error. Experiments demonstrate that the method provides the estimate of accuracy in pose determination.>

This paper describes a system which can perform full 3-D pose estimation of a single arbitrarily shaped, rigid object at rates up to 10 Hz. A triangular mesh model of the object to be tracked is generated offline using conventional range sensors. Real-time range data of the object is sensed by the CMU high speed VLSI range sensor. Pose estimation is performed by registering the real-time range data to the triangular mesh model using an enhanced implementation of the Iterative Closest Point (ICP) Algorithm introduced by Besl and McKay (1992). The method does not require explicit feature extraction or specification of correspondence. Pose estimation accuracies of the order of 1% of the object size in translation, and 1 degree in rotation have been measured.>

The pose (position and orientation) of a polyhedral object can be determined with range data obtained from simple light-stripe range finders. However, localization results are sensitive to where those range finders are placed in the workspace, that is, sensor placement. It is advantageous for vision tasks in a factory environment to plan optimal sensing positions off-line all at once rather than online sequentially. This paper presents a method for finding an optimal sensor placement off-line to accurately determine the pose of an object when using three light-stripe range finders. We evaluate a sensor placement on the basis of average performance measures such as an error rate of object recognition, recognition speed and pose uncertainty over the state space of object pose by a Monte Carlo method. An optimal sensor placement which is given a maximal score by a scalar function of the performance measures is selected by another Monte Carlo method. We emphasize that the expected performance of our system under an optimal sensor placement can be characterized completely via simulation.>

Presents a fast computation method of the normalized correlation for multiple rotated templates by using multiresolution eigenimages. This method allows the authors to accurately detect both location and orientation of the object in a scene at faster rate than applying conventional template matching to the rotated object. Since the correlation among slightly rotated templates is high, the authors first apply the Karhunen-Loeve expansion to a set of rotated templates and extract "eigenimages" from them. Each template in this set can be approximated by a linear combination of these eigenimages and it substitute for the template in computing the normalized correlation. The number of eigenimages is smaller than that of original templates and computation cost becomes small. Second, the authors employ a multiresolution image structure to reduce the number of rotated templates and location search area. For the lower resolution image, the position and angle are coarsely obtained in a wide region. Then not only searching area for the position but also the range of rotation angle of templates at the next layer can be limited to the neighbor of the prior results. The authors implemented the proposed algorithm on a vision system and realized computation time around 600 msec and achieved sub pixel resolution for translation and 0.3 degree maximum error for 360 degree rotation on the 512 by 480 gray scale image. Experimental results are shown to demonstrate the accuracy, efficiency and feasibility of the proposed method.>

A central problem in stereo matching by computing correlation or sum of squared differences (SSD) lies in selecting an appropriate window size. The window size must be large enough to include enough intensity variation for reliable matching, but small enough to avoid the effects of projective distortion. If the window is too small and does not cover enough intensity variation, it gives a poor disparity estimate, because the signal (intensity variation) to noise ratio is low. If, on the other hand, the window is too large and covers a region in which the depth of scene points (i.e., disparity) varies, then the position of maximum correlation or minimum SSD may not represent correct matching due to different projective distortions in the left and right images. For this reason, a window size must be selected adaptively depending on local variations of intensity and disparity. The authors present a method to select an appropriate window by evaluating the local variation of the intensity and the disparity. The authors employ a statistical model of the disparity distribution within the window. This modeling enables the authors to assess how disparity variation, as well as intensity variation, within a window affects the uncertainty of disparity estimate at the center point of the window. As a result, the authors devise a method which searches for a window that produces the estimate of disparity with the least uncertainty for each pixel of an image: the method controls not only the size but also the shape (rectangle) of the window. The authors have embedded this adaptive-window method in an iterative stereo matching algorithm: starting with an initial estimate of the disparity map, the algorithm iteratively updates the disparity estimate for each point by choosing the size and shape of a window till it converges. The stereo matching algorithm has been tested on both synthetic and real images, and the quality of the disparity maps obtained demonstrates the effectiveness of the adaptive window method.>

A stereo matching method that uses multiple stereo pairs with various baselines generated by a lateral displacement of a camera to obtain precise distance estimates without suffering from ambiguity is presented. Matching is performed simply by computing the sum of squared-difference (SSD) values. The SSD functions for individual stereo pairs are represented with respect to the inverse distance and are then added to produce the sum of SSDs. This resulting function is called the SSSD-in-inverse-distance. It is shown that the SSSD-in-inverse-distance function exhibits a unique and clear minimum at the correct matching position, even when the underlying intensity patterns of the scene include ambiguities or repetitive patterns. The authors first define a stereo algorithm based on the SSSD-in-inverse-distance and present a mathematical analysis to show how the algorithm can remove ambiguity and increase precision. Experimental results with real stereo images are presented to demonstrate the effectiveness of the algorithm.>

The authors present algorithms for robotic (eye-in-hand configuration) real-time visual tracking of arbitrary 3D objects traveling at unknown velocities in a 2D space (depth is given as known). Visual tracking is formulated as a problem of combining control with computer vision. A mathematical formulation of the control problem that includes information from a novel feedback vision sensor and represents everything with respect to the camera frame is presented. The sum-of-squared differences (SSD) optical flow is used to compute the vector of discrete displacements each instant of time. These displacements can be fed either directly to a PI (proportional-integral) controller or to a pole assignment controller or discrete steady-state Kalman filter. In the latter case, the Kalman filter calculates the estimated values of the system's states and the exogenous disturbances, and a discrete LQG (linear-quadratic Gaussian) controller computes the desired motion of the robotic system. The outputs of the controllers are sent to the Cartesian robotic controller. Performance results are presented.>

Self-Mobile Space Manipulator (SM/sup 2/) is a simple, 5-DOF (degree-of-freedom), 1/3-scale, laboratory version of a robot designed to walk on the trusswork and other exterior surfaces of Space Station Freedom. It will be capable of routine tasks such as inspection, parts transportation, and simple maintenance procedures. The authors have designed and built the robot and gravity compensation system to permit simulated zero-gravity experiments. They have developed the control system for the SM/sup 2/ including control hardware architecture and operating system, control station with various interfaces, hierarchical control structure, multiphase control strategy for step motion, and various low-level controllers. The system provides operator-friendly real-time monitoring, and robust control for 3D locomotion movements of the flexible robot.>

The authors discuss adaptive control of a space robot system with an attitude-controlled base on which the robot is attached. An adaptive control scheme in joint space is proposed. Since most tasks are specified in inertia space, instead of joint space, the authors discuss the issues associated to adaptive control in inertia space and identify two potential problems, unavailability of the joint trajectory (since mapping from inertia space trajectory is dynamics-dependent and subject to uncertainty), and nonlinear parameterization in inertia space. For a planar system, the linear parameterization problem is investigated, the design procedure of the controller is illustrated, and the validity and effectiveness of the proposed control scheme are demonstrated.>

VLSI technology makes possible a powerful new sensing methodology--the smart sensor. In a smart sensor, transducers are integrated with processing circuitry so that desired information can be intelligently extracted at the point of sensing. Physical limitations force traditional systems to artificially partition sensing and processing functions. By eliminating such partitioning, VLSI smart sensing adds a new dimension to the design of both sensors and sensing algorithms. In this research, a high-performance VLSI range-image sensor has been built using the smart sensing methodology. This sensor measures range via light-stripe triangulation, a mature technology widely used in robotic systems. VLSI-based smart sensing made practical a cell-parallel implementation of the light-stripe method. Experiments with the cell-parallel sensor show that its performance is substantially better than that of traditional light-stripe systems. Range image acquisition time is decreased by two orders of magnitude. Furthermore, the range measurement process is qualitatively different, providing more robust and more accurate 3-D measurements. The success of the cell-parallel sensor can be attributed directly to the use of smart sensing and convincingly demonstrates the power of the technique. One of the most distinguishing features of this work is that it is not just a re-implementation of established algorithms using VLSI. Rather, this thesis demonstrates that intelligent data acquisition makes possible new approaches to sensing that can significantly improve sensor performance.

We have developed a light-weight space manipulator, Self-Mobile Space Manipulator (SM'), in the Robotics Institute at Carnegie Mellon University. SM' is a 7-degreeof-freedom (DOF), 1/3-scale, laboratory version of a robot designed to walk on the trusswork and other exterior surfaces of Space Station Freedom, and to perform manipulation tasks that are required for inspection, maintenance, and construction. Combining the mobility and manip ulation functions in one body as a mobile manipulator, SM2 is capable of routine tasks such as inspection, parts transportation, object lighting, and simple assembly procedures. The system will provide assistance to astronauts and greatly reduce the need for astronaut extra-vehicular activity (EVA). This paper discusses the robot hardware development, gravity compensation system, control structure and teleoperation functions of the SM2 system, and demonstrates its capabilities of locomotion and manipulation in space applications.

The authors present 3-D vision techniques for incrementally building an accurate 3-D representation of rugged terrain using multiple sensors. They have developed the locus method to model the rugged terrain. The locus method exploits sensor geometry to efficiently build a terrain representation from multiple sensor data. The locus method is used to estimate the vehicle position in the digital elevation map (DEM) by matching a sequence of range images with the DEM. Experimental results from large-scale real and synthetic terrains demonstrate the feasibility and power of the 3-D mapping techniques for rugged terrain. In real world experiments, a composite terrain map was built by merging 125 real range images. Using synthetic range images, a composite map of 150 m was produced from 159 images. With the proposed system, mobile robots operating in rugged environments can build accurate terrain models from multiple sensor data.>

A stereo matching method is presented which uses multiple stereo pairs with various baselines to obtain precise depth estimates without suffering from ambiguity. The stereo matching method uses multiple stereo pairs with different baselines generated by a lateral displacement of a camera. Matching is performed by computing the sum of squared-difference (SSD) values. The SSD functions for individual stereo pairs are represented with respect to the inverse depth (rather than the disparity, as is usually done), and then are simply added to produce the sum of SSDs. This resulting function is called the SSSD-in-inverse-depth. The authors define a stereo algorithm, based on the SSSD-in-inverse-depth and then present a mathematical analysis to show how the algorithm can remove ambiguity and increase precision. Experimental results for stereo images are presented to demonstrate the effectiveness of the algorithm.>

The authors present a very fast lightstripe rangefinder based on an IC array of photoreceptor and analog signal processor cells which acquires 1000 frames of range image per second-two orders of magnitude faster than currently available rangefinding methods. Unlike a conventional lightstripe range-finder, which obtains a frame of range image by the step-and-repeat process of projecting a stripe and grabbing and analyzing a camera image, the VLSI sensor array of this rangefinder gathers range data in parallel as a scene is swept continuously by a moving stripe. Each cell continuously monitors the output of its photoreceptor, and detects and remembers the time at which it observed the peak incident light intensity during the sweep of the stripe. Prototype rangefinding systems have been built using a 28*32 array of these sensing elements.>

Methods are presented for building high-level terrain descriptions, referred as topographic maps, by extracting terrain features like peaks, pits, ridges, and ravines from the contour map. The resulting topographic map contains the location and type of terrain features as well as the ground topography. The authors develop new definitions for those topographic features based on the contour map. They build a contour map from an elevation map and generate the connectivity tree of all regions separated by the contours. The authors use this connectivity tree, called a topographic change tree, to extract the topographic features. Experimental results on a digital elevation model support the definitions for topographic features and the approach.>

An algorithm for recovering the shape and reflectance of Lambertian surfaces in the presence of interreflections is presented. The surfaces may be of arbitrary but continuous shape, and with possibly varying and unknown reflectance. The actual shape and reflectance are recovered from the pseudoshape and pseudoreflectance estimated by a local shape-from-intensity method (e.g., photometric stereo). Thus, the algorithm enhances the performance and the utility of existing shape-from-intensity methods. From the results reported, two observations can be made that are pertinent to machine vision: interreflections can cause vision algorithms to produce unacceptably erroneous results and hence should not be ignored; and at least some interreflection problems are tractable and solvable.>

Algorithms for robotic real-time visual tracking of arbitrary 3-D objects traveling at unknown velocities in a 2-D space are presented. The problem of visual tracking is formulated as a problem of combining control with computer vision. A mathematical formulation that is general enough to be extended to the problem of tracking 3-D objects in 3-D space is presented. The authors propose the use of sum-of-squared differences optical flow for the computation of the vector of discrete displacements each instant of time. These displacements can be fed either directly to a PI controller, a pole assignment controller, or a discrete steady-state Kalman filter. In the latter case, the Kalman filter calculates the estimated values of the system's states and exogenous disturbances, and a discrete LQG controller computes the desired motion of the robotic system. The outputs of the controllers are sent to a Cartesian robotic controller that drives the robot.>

Reflectance models based on physical optics and geometrical optics are studied. Specifically, the authors consider the Beckmann-Spizzichino (physical optics) model and the Torrance-Sparrow (geometrical optics) model. These two models were chosen because they have been reported to fit experimental data well. Each model is described in detail, and the conditions that determine the validity of the model are clearly stated. By studying reflectance curves predicted by the two models, the authors propose a reflectance framework comprising three components: the diffuse lobe, the specular lobe, and the specular spike. The effects of surface roughness on the three primary components are analyzed in detail.>

An iterative algorithm is presented that simultaneously recovers the actual shape and the actual reflectance from the pseudo estimates. The recovery algorithm works on Lambertian surfaces of arbitrary shape with possibly varying and unknown reflectance. The general behavior of the algorithm and its convergence properties are discussed. Both simulation and experimental results are included to demonstrate the accuracy and stability of the algorithm.>

The authors presents a signal matching algorithm that can select an appropriate window size adaptively so as to obtain both precise and stable estimation of correspondences. A statistical model is presented for disparity variation within a window, and it is used to establish a link between the window size and the uncertainty of the computed disparity. This makes it possible to choose the window size that minimizes uncertainty in the disparity computed at each point. A theory is presented for the model and the resultant algorithm, together with analytical and experimental results that demonstrate their effectiveness.>

Inferring the depth and shape of remote objects and the camera motion from a sequence of images is possible in principle, but is an ill-conditioned problem when the objects are distant with respect to their size. This problem is overcome by inferring shape and motion without computing depth as an intermediate step. On a single epipolar plane, an image sequence can be represented by the F*P matrix of the image coordinates of P points tracked through F frames. It is shown that under orthographic projection this matrix is of rank three. Using this result, the authors develop a shape-and-motion algorithm based on singular value decomposition. The algorithm gives accurate results, without relying on any smoothness assumption for either shape or motion.>

A two-step procedure that finds natural clusters in geometric point data is described. The first step computes a hierarchical cluster tree minimizing an entropy objective function. The second step recursively explores the tree for a level clustering having minimum description length. Together, these two steps find natural clusters without requiring a user to specify threshold parameters or so-called magic numbers. In particular, the method automatically determines the number of clusters in the input data. The first step exploits a new hierarchical clustering procedure called numerical iterative hierarchical clustering (NIHC). The output of NIHC is a cluster tree. The second step in the procedure searches the tree for a minimum-description-length (MDL) level clustering. The MDL formulation, equivalent to maximizing the posterior probability, is suited to the clustering problem because it defines a natural prior distribution.>

A method is presented for determining the shapes of hybrid surfaces without prior knowledge of the relative strengths of the Lambertian and specular components of reflection. The object surface is illuminated using extended light sources and is viewed from a single direction. Surface illumination using extended sources makes it possible to ensure the detection of both Lambertian and specular reflections. Uniformly distributed source directions are used to obtain an image sequence of the object. This method of obtaining photometric measurements is called photometric sampling. An extraction algorithm uses the set of image intensity values measured at each surface point to compute orientation as well as relative strengths of the Lambertian and specular reflection components. The simultaneous recovery of shape and reflectance parameters enables the method to adapt to variations in reflectance properties from one scene point to another. Experiments were conducted on Lambertian surfaces, specular surfaces, and hybrid surfaces.>

The authors are prototyping a legged vehicle, the Ambler, for an exploratory mission on another planet, conceivably Mars, where it is to traverse uncharted areas and collect material samples. They describe how the rover can construct from range imagery a geometric terrain representation, i.e., elevation map that includes uncertainty, unknown areas, and local features. First, they present an algorithm for constructing an elevation map from a single range image. By virtue of working in spherical-polar space, the algorithm is independent of the desired map resolution and the orientation of the sensor, unlike algorithms that work in Cartesian space. Secondly, the authors present a two-stage matching technique (feature matching followed by iconic matching) that identifies the transformation T corresponding to the vehicle displacement between two viewing positions. Thirdly, to support legged locomotion over rough terrain, they describe methods for evaluating regions of the constructed elevation maps as footholds.>

The authors present a method for determining the shapes of surfaces whose reflectance properties may vary from Lambertian to specular, without prior knowledge of the relative strengths of the Lambertian and specular components of reflection. The object surface is illuminated using extended light sources and is viewed from a single direction. Surface illumination using extended sources makes it possible to ensure the detection of both Lambertian and specular reflections. Multiple source directions are used to obtain an image sequence of the object. An extraction algorithm uses the set of image intensity values measured at each surface point to compute orientation as well as relative strengths of the Lambertian and specular reflection components. The proposed method is called photometric sampling, as it uses samples of photometric function that relates image intensity to surface orientation, reflectance, and light source characteristics. Experiments were conducted on Lambertian surfaces, specular surfaces, and hybrid surfaces, whose reflectance models are composed of both Lambertian and specular components. The results show high accuracy in measured orientations and estimated reflectance parameters.>

CHIMERA is a real-time computing environment used in the Reconfigurable Modular Manipulator System project. CHIMERA, which is both a hardware and software environment, allows rapid development and implementation of real-time control programs. It provides a C/Unix-flavored concurrent programming environment for a Motorola 68020 multiprocessor hardware configuration connected to a Sun workstation. CHIMERA has been implemented using commercial hardware in conjunction with a sophisticated, locally developed software package, resulting in a reliable, reasonably priced, and easily duplicated system. CHIMERA is currently being ported for real-time control of the CMU Direct Drive Arm II. The authors describe the implementation and capabilities of the CHIMERA environment and illustrate how these features are used in robot control applications.>

Experimental results on the real-time performance of model-based control algorithms are presented. The computed-torque scheme which utilizes the complete dynamics model of the manipulator was compared to the independent joint control scheme, which assumes a decoupled and linear model of the manipulator dynamics. The two manipulator control schemes have been implemented on the Carnegie-Mellon University DD (direct-drive) Arm II with a sampling period of 2 ms. The authors discuss the design of controller gains for both the computed-torque and the independent joint control schemes and establish a framework for comparing their trajectory-tracking performances. It is shown that the computed-torque scheme outperforms the independent joint control scheme as long as there is not torque saturation in the actuators. Based on the experimental results, the authors conclusively establish the importance of compensating for the nonlinear Coriolis and centrifugal forces even at low speeds of operation.>

The authors introduce a novel pixel-based (iconic) algorithm that estimates depth and depth uncertainty at each pixel and incrementally refines these estimates over time. They describe the algorithm for translations parallel to the image plane and contrast its formulation and performance to that of a feature-based Kalman filtering algorithm. They compare the performance of the two approaches by analyzing their theoretical convergence rates, by conducting quantitative experiments with images of a flat poster, and by conducting qualitative experiments with images of a realistic outdoor scene model. The results show that the method is an effective way to extract depth from lateral camera translations and suggest that it will play an important role in low-level vision.>

One of the most important and systematic methods to build modelbased vision systems is that to generate object recognition programs automatically from given geometric models. Automatic generation of object recognition programs requires several key components to be developed: object models to describe the geometric and photometric properties of an object to be recognized, sensor models to predict object appearances from the object model under a given sensor, strategy generation using the pred,icted appearances to produce an recognition strategy, and program generation converting the recognition strategy into an executable code. This paper concentrates on sensor modeling and its relationship with strategy generation, because we regard it as the bottle neck to automatic generation of object recognition programs. We consider two aspects of sensor characteristics: sensor detectability and sensor reliability. Sensor detectability specifies what kinds of features can be detected and in what condition the features are detected; sensor reliability is a confidence for the detected features. We define the configuration space to represent sensor characteristics. We propose a representation method for sensor detectability and rcliability in the configuration space. Finally, we investigate how to use the proposed sensor modcl in automatic generation of an objcct recognition program.

In this paper, we present an approach to color image understanding that can be used to segment and analyze surfaces with color variations due to highlights and shading. We begin with a theory - the Dichromatic Reflection Model - that relates the reflected light from dielectric materials, such as plastic, to fundamental physical reflection processes, and describes the color of the reflected light as a linear combination of the color of the light due to surface reflection (highlights) and body reflection (object color). This dichromatic theory is used in an algorithm that separates a color image into two parts: an image of just the highlights, and the original image with the highlights removed. In the past, we have applied this method to handsegmented images. This paper shows how to perform automatic segmentation by applying this theory in stages to identify the object and highlight colors. The result is a combination of segmentation and reflection analysis that is better than traditional heuristic segmentation methods and provides important physical information about the surface geometry and material properties at the same time. This line of research can lead to physics-based image understanding methods that are both more reliable and more useful than traditional methods.

Geometric camera calibration is the process of determining a mapping between points in world coordinates and the corresponding image locations of the points. In previous methods, calibration typically involved the iterative solution to a system of nonlinear equations. A method is presented for performing camera calibration that provides a complete, accurate solution, using only linear systems of equations. By using two calibration planes, a line-of-sight vector is defined for each pixel in the image. The effective focal point of a camera can be obtained by solving the system that defines the intersection point of the line-of-sight vectors. Once the focal point has been determined, a complete camera model can be obtained with a straightforward least-squares procedure. This method of geometric camera calibration has the advantages of being accurate, efficient, and practical for a wide variety of applications.>

Issues and techniques are discussed to automatically compile object and sensor models into a visual recognition strategy for recognizing and locating an object in three-dimensional space from visual data. Automatic generation of recognition programs by compilation, in an attempt to automate this process, is described. An object model describes geometric and photometric properties of an object to be recognized. A sensor model specifies the sensor characteristics in predicting object appearances and variations of feature values. It is emphasized that the sensors, as well as objects, must be explicitly modeled to achieve the goal of automatic generation of reliable and efficient recognition programs. Actual creation of interpretation trees for two objects and their execution for recognition from a bin of parts are demonstrated.>

This paper presents the experimental results of the real-time performance of model-based control algorithms. We compare the computed-torque scheme which utilizes the complete dynamics model of the manipulator with the independent joint control scheme which assumes a decoupled and linear model of the manipulator dynamics. The two manipulator control schemes have been implemented on the CMU DD Arm II with a sampling period of 2 ms. Our initial investigation shows that the computed-torque scheme outperforms the independent joint control scheme as long as there is no torque saturation in the actuators.

We report progress in visual road following by autonomous robot vehicles. We present results and work in progress in the areas of system architecture, image rectification and camera calibration, oriented edge tracking, color classification and road-region segmentation, extracting geometric structure, and the use of a map. In test runs of an outdoor robot vehicle, the Terregator, under control of the Warp computer, we have demonstrated continuous motion vision-guided road-following at speeds up to 1.08 km/hour with image processing and steering servo loop times of 3 sec.

This paper presents a stereo matching algorithm using the dynamic programming technique. The stereo matching problem, that is, obtaining a correspondence between right and left images, can be cast as a search problem. When a pair of stereo images is rectified, pairs of corresponding points can be searched for within the same scanlines. We call this search intra-scanline search. This intra-scanline search can be treated as the problem of finding a matching path on a two-dimensional (2D) search plane whose axes are the right and left scanlines. Vertically connected edges in the images provide consistency constraints across the 2D search planes. Inter-scanline search in a three-dimensional (3D) search space, which is a stack of the 2D search planes, is needed to utilize this constraint. Our stereo matching algorithm uses edge-delimited intervals as elements to be matched, and employs the above mentioned two searches: one is inter-scanline search for possible correspondences of connected edges in right and left images and the other is intra-scanline search for correspondences of edge-delimited intervals on each scanline pair. Dynamic programming is used for both searches which proceed simultaneously: the former supplies the consistency constraint to the latter while the latter supplies the matching score to the former. An interval-based similarity metric is used to compute the score. The algorithm has been tested with different types of images including urban aerial images, synthesized images, and block scenes, and its computational requirement has been discussed.

We describe the current state of the 3-D Mosaic project, whose goal is to incrementally acquire a 3-D model of a complex urban scene from images. The notion of incremental acquisition arises from the observations that 1) single images contain only parfial information about a scene, 2) complex images are difficult to fully interpret, and 3) different features of a given scene tend to be easier to extract in different images because of differences in viewpoint and lighting conditions. In our approach, multiple images of the scene are sequentially analyzed so as to incrementaly construct the model. Each new image provides information which refines the model. We describe some experiments toward this end. Our method of extracting 3-D shape information from the images is stereo analysis. Because we are dealing with urban scenes, a junction-based matching technique proves very useful. This technique produces rather sparse wire-frame descriptions of the scene. A reasoning system that relies on task-specific knowledge generates an approximate model of the scene from the stereo output. Gray scale information is also acquired for the faces in the model. Finally, we describe an experiment in combining two views of the scene to obtain a rermed model.

Recursive segmentation of an image into regions using histograms is one of the most widely used techniques for image segmentation. At CMU, several versions of a region segmentation program have been developed based on this technique (Ohlander, Price, Shafer and Kanade). Based on these experiences, this paper discusses issues of recursive region segmentation in the context of PHOENIX, the newest version of region segmentation program, running on a VAX 11/780 under UNIX. The issues discussed in this paper include: Image features to be used in histogramming; comparison of the algorithm with other techniques; important improvements made in PHOENIX over its predecessor (Ohlander and Price); and some inherent problems in histogram-based segmentation together with suggestions for minimizing them. PHOENIX is being incorporated into the ARPA Image Understanding Testbed, under construction at SRI International.