We introduce state invariance - robustness to changes in an object’s structural form (as for a folded umbrella or for crumpled clothing) - complementing other common invariances to learn object representations for recognition and retrieval tasks. For this, we present ObjectsWithStateChange (OWSC), a novel dataset that captures variations in object appearance arising from state changes, along with pose, viewpoint, and illumination variations, to advance research in fine-grained 3D object recognition and retrieval. A key challenge is that objects within and across categories may look visually similar under certain state changes, making discrimination difficult. To address this, we propose a curriculum learning based mining strategy that progressively samples harder object pairs based on inter-object distances in the learned embedding space after each epoch, gradually sampling harder-to-distinguish examples of visually similar objects from within and across categories during training. Our ablation shows that this curriculum learning strategy enhances the model’s ability to learn discriminative invariant features for fine-grained tasks, improving object recognition accuracy by 7.9% and retrieval mAP by 9.2% over prior methods on our new OWSC dataset and three other multi-view datasets, such as ModelNet40, ObjectPI, FG3D. Our OWSC dataset is available at https://github.com/sarkar-rohan/ObjectsWithStateChange.

In the context of pose-invariant object recognition and retrieval, we demonstrate that it is possible to achieve significant improvements in performance if both the category-based and the object-identity-based embed-dings are learned simultaneously during training. In hind-sight, that sounds intuitive because learning about the cat-egories is more fundamental than learning about the indi-vidual objects that correspond to those categories. How-ever, to the best of what we know, no prior work in pose-invariant learning has demonstrated this effect. This paper presents an attention-based dual-encoder architecture with specially designed loss functions that optimize the inter-and intra-class distances simultaneously in two different embedding spaces, one for the category embeddings and the other for the object level embeddings. The loss functions we have proposed are pose-invariant ranking losses that are designed to minimize the intra-class distances and maximize the inter-class distances in the dual representation spaces. We demonstrate the power of our approach with three challenging multi-view datasets, Model Net-40, ObjectPI, and FG3D. With our dual approach, for single-view object recognition, we outperform the previous best by 20.0% on ModelNet40, 2.0% on ObjectPI, and 46.5% on FG3D. On the other hand, for single-view object retrieval, we outperform the previous best by 33.7% on ModelNet40, 18.8% on ObjectPI, and 56.9% on FG3D.

As a result of Shadow NeRF and Sat-NeRF, it is possible to take the solar angle into account in a NeRF-based framework for rendering a scene from a novel viewpoint using satellite images for training. Our work extends those contributions and shows how one can make the renderings season-specific. Our main challenge was creating a Neural Radiance Field (NeRF) that could render seasonal features independently of viewing angle and solar angle while still being able to render shadows. We teach our network to render seasonal features by introducing one more input variable - time of the year. However, the small training datasets typical of satellite imagery can introduce ambiguities in cases where shadows are present in the same location for every image of a particular season. We add additional terms to the loss function to discourage the network from using seasonal features for accounting for shadows. We show the performance of our network on eight Areas of Interest containing images captured by the Maxar WorldView-3 satellite. This evaluation includes tests measuring the ability of our framework to accurately render novel views, generate height maps, predict shadows, and specify seasonal features independently from shadows. Our ablation studies justify the choices made for network design parameters.

Hematoxylin and Eosin (H&E) staining is a widely used sample preparation procedure for enhancing the saturation of tissue sections and the contrast between nuclei and cytoplasm in histology images for medical diagnostics. However, various factors, such as the differences in the reagents used, result in high variability in the colors of the stains actually recorded. This variability poses a challenge in achieving generalization for machine-learning based computer-aided diagnostic tools. To desensitize the learned models to stain variations, we propose the Generative Stain Augmentation Network (G-SAN) - a GAN-based framework that augments a collection of cell images with simulated yet realistic stain variations. At its core, G-SAN uses a novel and highly computationally efficient Laplacian Pyramid (LP) based generator architecture, that is capable of disentangling stain from cell morphology. Through the task of patch classification and nucleus segmentation, we show that using G-SAN-augmented training data provides on average 15.7% improvement in F1 score and 7.3% improvement in panoptic quality, respectively. Our code is available at https://github.com/lifangda01/GSAN-Demo.

This paper reports on a large-scale comparative evaluation of IR-based tools for automatic bug localization. We have divided the tools in our evaluation into the following three generations: (1) The first-generation tools, now over a decade old, that are based purely on the Bag-of-Words (BoW) modeling of software libraries. (2) The somewhat more recent second-generation tools that augment BoW-based modeling with two additional pieces of information: historical data, such as change history, and structured information such as class names, method names, etc. And, finally, (3) The third-generation tools that are currently the focus of much research and that also exploit proximity, order, and semantic relationships between the terms. It is important to realize that the original authors of all these three generations of tools have mostly tested them on relatively small-sized datasets that typically consisted no more than a few thousand bug reports. Additionally, those evaluations only involved Java code libraries. The goal of the present paper is to present a comprehensive large-scale evaluation of all three generations of bug-localization tools with code libraries in multiple languages. Our study involves over 20,000 bug reports drawn from a diverse collection of Java, C/C++, and Python projects. Our results show that the third-generation tools are significantly superior to the older tools. We also show that the word embeddings generated using code files written in one language are effective for retrieval from code libraries in other languages.

One faces several challenges when tracking objects and events simultaneously in multi-camera environments - especially if the events associated with the object require precise knowledge of the pose of the object at each instant of time. To illustrate the challenges involved, we consider the problem of tracking bins and their contents at airport security checkpoints. The pose of each bin must be tracked with precision in order to minimize the errors associated with the detection of the various items that the passengers may place in the bins and/or take out of them. Unfortunately, pose estimation of the bins is made difficult by the fact that as a bin moves away from the camera's optic axis, its appearance changes nonlinearly. This paper presents a collaborative algorithmic framework to address this complexity: The framework includes simple and fast 2D trackers when such tracking can be carried out reliably, and more sophisticated 2.5D trackers when the bins move away from the cameras' optic axes. The system decides automatically as to which tracker to trust the most. We validate the framework with a ground-truth dataset.

Word embeddings produced by the word2vec algorithm provide us with a strong mechanism to discover relationships between the words based on the degree to which they are contextually related to one another. In and of itself, algorithms like word2vec do not give us a mechanism to impose ordering constraints on the embedded word representations. Our main goal in this paper is to exploit the semantic word vectors obtained from word2vec in such a way that allows for the ordering constraints to be invoked on them when comparing a sequence of words in a query with a sequence of words in a file for source code retrieval. These ordering constraints employ the logic of Markov Random Fields (MRF), a framework used previously to enhance the precision of the source-code retrieval engines based on the Bag-of-Words (BoW) assumption. The work we present here demonstrates that by combining word2vec with the power of MRF, it is possible to achieve improvements between 6% and 30% in retrieval accuracy over the best results that can be obtained with the more traditional applications of MRF to representations based on term and term-term frequencies. The performance improvement was 30% for the Java AspectJ repository using only the titles of the bug reports provided by iBUGS, and 6% for the case of the Eclipse repository using titles as well as descriptions of the bug reports provided by BUGLinks.

Abstract Practically all information retrieval based approaches developed to date for automatic bug localization are based on the bag‐of‐words assumption that ignores any positional and ordering relationships between the terms in a query. In this paper, we argue that bug reports are ill‐served by this assumption because such reports frequently contain various types of structural information whose terms must obey certain positional and ordering constraints. It therefore stands to reason that the quality of retrieval for bug localization would improve if these constraints could be taken into account when searching for the most relevant files. In this paper, we demonstrate that such is indeed the case. We show how the well‐known Markov Random Field based retrieval framework can be used for taking into account the term‐term proximity and ordering relationships in a query vis‐à‐vis the same relationships in the files of a source‐code library to greatly improve the quality of retrieval of the most relevant source files. We have carried out our experimental evaluations on popular large software projects using over 4000 bug reports. The results we present demonstrate unequivocally that the new proposed approach is far superior to the widely used bag‐of‐words based approaches. Copyright © 2016 John Wiley & Sons, Ltd.

Dormant pruning is one of the most costly and labor-intensive operations in specialty crop production. During winter, a large crew of trained seasonal workers has to carefully remove the branches from hundreds of trees using a set of pre-defined rules. The goal of automatic pruning is to reduce this dependence on a large work-force that is currently needed for the job. Automatically applying the pruning rules entails construction of 3D models of the trees in their dormant condition (that is, without foliage) and accurate estimation of the pruning points on the branches. This paper investigates the contribution of modeling the trunk and primary branches of a tree using semi-circles in a 3D reconstruction scheme. It involves three main steps; estimating the diameter-error, filtering the depth images, and semi-circle-based modeling which estimates the required pruning data. The obtained results demonstrate the effectiveness of the proposed framework for automatic reconstruction using only single depth image. We further propose a novel empirical model that estimates the diameter of the primary branches under varying depth values. Both qualitative and quantitative evaluations are performed on a new challenging apple trees dataset under various indoor and outdoor environments. Our results show that the proposed scheme provides a performance of 89% for correctly estimating the diameter of the primary branches.

Dormant pruning is one of the most expensive, labor-intensive, but, unavoidable procedure in the field of horticulture to ensure quality crop production. During winter, skilled farmers remove certain branches that are connected directly with the trunk of a tree carefully using a set of predefined rules. In order to reduce this dependence on a large manpower, our goal is to automate this pruning process by building 3D models of dormant apple trees, which eventually would be fed to an intelligent robotic system. In this paper, we present a semicircle fitting based robust 3D reconstruction scheme for modeling the trunk and primary branches of apple trees. The method involves estimating the diameter-error, creating semicircle fit model of the tree from a single depth image, and reconstructing the final 3D model of the tree by aligning a sequence of depth images. Analysis of the qualitative as well as the quantitative evaluations of our algorithm on five different dormant apple trees from our dataset under various indoor and outdoor environments demonstrate the effectiveness of the proposed framework for automatic 3D reconstruction. The results show that on an average, the proposed schemes provide a performance of 89.4% for correctly estimating the diameters of the primary branches with a tolerance of 5 mm and 100%c for correctly identifying the branches.

Abstract We present a new graph‐based approach for the detection and isolation of botnets in a computer network. Our approach depends primarily on the temporal co‐occurrences of malicious activities across the computers in a network and is independent of botnet architectures and the means used for their command and control. As practically all aspects of how a botnet manifests itself in a network—such as the online bot population, bot lifetimes, and the duration and the choice of malicious activities ordered by the bot master—can be expected to vary significantly with time, our approach includes mechanisms that allow the graph representing the infected computers to evolve with time. With regard to how such a graph varies with time, of particular importance are the edge weights that are derived from the temporal co‐occurrences of malicious activities at the endpoints of the edges. A unique advantage of our graph‐based representation of the infected computers is that it allows us to use graph‐partitioning algorithms to separate out the different botnets when a network is infected with multiple botnets at the same time. We have validated our approach by applying it to the isolation of simulated botnets, with the simulations based on a new unified temporal botnet model that incorporates the current best understanding about how botnets behave, about the lifetimes of bots, and about the growth and decay of botnets. We also validate our algorithm on real network traces. Our results indicate that our framework can isolate botnets in a network under varying conditions with a high degree of accuracy. Copyright © 2012 John Wiley & Sons, Ltd.

In this age of collaborative software development, the importance of usable APIs is well recognized. There already exists a rich body of literature that addresses issues ranging from how to design usable APIs to assessing qualitatively the usability of a given API. However, there does not yet exist a set of general-purpose metrics that can be pressed into service for a more quantitative assessment of API usability. The goal of this paper is to remedy this shortcoming in the literature. Our work presents a set of formulas that examine the API method declarations from the perspective of several commonly held beliefs regarding what makes APIs difficult to use. We validate the numerical characterizations of API usability as produced by our metrics through the APIs of several software systems. Copyright © 2013 John Wiley & Sons, Ltd.

We present a robot self-localization approach that is based on using a cascade of filters that increasingly refine a robot's guess regarding where it is in a hallway system. The location refinement carried out by each stage of the cascade compares a signature extracted from a stereo pair of camera images taken at the current location of the robot with a database of such signatures collected previously during a training phase. A central question in this approach to robot localization is what signatures to use for each stage of the cascade. An answer to this question must recognize the special importance of the first stage of the cascade — we refer to this as the prefiltering stage. The signature used for prefiltering must be significantly viewpoint invariant, while possessing sufficient locale uniqueness to yield a set of possible locations for the robot that includes the true location with a high probability. On the other hand, the signature(s) used for downstream filtering in the cascade must then prune away the inapplicable locales from the list yielded by the prefilter. What that implies is that the downstream filters must be increasingly viewpoint variant and locale specific. Although the framework we propose allows for an arbitrary number of filters to follow the prefiltering stage, the results we present in this paper are for a two-stage cascade consisting of a prefilter followed by one additional filter. The signatures we use in our experiments are based on 3D-JUDOCA features that can be extracted from stereo pairs of images. The proposed framework for choosing the best signatures for the prefiltering stage and the filtering stage that follows was tested in a large indoor hallway system with a total linear length of 1539 m. The validation results we show are based on a dataset of 6209 stereo images collected by a robot from the hallways during its training phase. The performance evaluation presented in this paper demonstrates that our framework can lead to high localization accuracy with good time performance by a robot.

We present a robust approach for tracking human subjects as their limbs and torso are engaged in large articulated movements while the entire body is executing a large translational motion with respect to the pointing angle of the camera. While the articulated movements can be handled by the recently proposed Component-Based Multiple Instance Learning (CMIL) tracker, the large translational motions by the target require that we also use a motion prediction framework to more accurately estimate the most probable positions of the target in the next frame of a video sequence. In the work we report here, this prediction is carried out with a particle filter. This coupling between CMIL based tracking and particle filtering yields a much more accurate estimate of candidate positions of the target in the next frame given the position of the target in the current frame. We validate this new approach by demonstrating results on videos of human subjects that are simultaneously executing large articulated movements with their limbs and torso while the subjects themselves are in some translational motions with respect to the pointing angle of the camera.

Energy efficiency dominates practically every aspect of the design of a wireless sensor network and duty cycling is an important tool for achieving high energy efficiencies. Duty cycling for wireless camera networks meant for tracking objects is made complex by the nodes having to anticipate the arrival of the objects in their field-of-view. The consequences of an object arriving in the view-region of a camera when it is sleeping need no elaboration. Our work presents a predictive framework to provide nodes with an ability to anticipate the arrival of objects in the field-of-view of their cameras. Our predictive framework differs from others in that the nodes whose duty cycles are increased are at least one step removed from the immediate neighborhood of the nodes where the objects are currently visible. By eliminating the need for the currently busiest nodes to also be in charge of informing their nonbusy immediate neighbors to get ready for object arrival, we end up with a more robust strategy for updating the duty cycle at the nodes where the objects are highly likely to appear soon. The proposed scheme works by using an existing MAC header bit that is already in the 802.15.4 protocol and, in that sense, our anticipatory approach for notifying the nodes about the current state of the object location entails no additional expenditure of energy. Our contribution includes evaluations based on large-scale simulations as well as real experiments with an Imote2-based wireless camera network.

Our work is about a new class of object trackers that are based on a boosted Multiple Instance Learning (MIL) algorithm to track an object in a video sequence. We show how the scope of such trackers can be expanded to the tracking of articulated movements by humans that frequently result in large frame-to-frame variations in the appearance of what needs to be tracked. To deal with the problems caused by such variations, our paper presents a component based version of the boosted MIL algorithm. Components are the output of an image segmentation algorithm applied to the pixels in the bounding box encapsulating the object to be tracked. The components give the boosted MIL the additional degrees of freedom that it needs in order to deal with the large frame-to-frame variations associated with articulated movements.

Estimating the head pose with RGBD data when the pose is allowed to vary over a large angle remains challenging. In this paper, we show that an appearance-based construction of a set of locally optimum subspaces provides a good (fast and accurate) solution to the problem. At training time, our algorithm partitions the set of all images obtained by applying pose transformations to the 3D point cloud for a frontal view into appearance based clusters and represents each cluster with a local PCA space. Given a test RGBD images, we first find the appearance cluster that it belongs to and, subsequently, we find its pose from the training image that is closest to the test image in that cluster. Our paper compares the appearance-based local-subspace method with the pose-based local-subspace approach and with a PCA-based global subspace method. This comparison establishes the superiority of the appearance-based local-subspace approach.

Our work provides a fast approach-path-independent framework for the problem of place recognition and robot localization in indoor environments. The approach-path independence is achieved by using highly viewpoint-invariant 3D junction features extracted from stereo pairs of images; these are based on stereo reconstructions of the JUDOCA junctions extracted from the individual images of a stereo pair. The speed in place-recognition and robot-localization is achieved by using a novel cylindrical data structure - we refer to it as the Feature Cylinder - for representing either all of the 3D junction features found in a hallway system during the learning phase of the robot or a set of locale signatures derived from the data. For the case when all data is placed on the Feature Cylinder, we can use the 3D-POLY polynomial-time in a hypothesize-and-verify approach to place recognition. On the other hand, in the locale signature based approach, we can use the same data structure for constant-time place recognition.

Source code retrieval plays an important role in many software engineering tasks. However, designing a query that can accurately retrieve the relevant software artifacts can be challenging for developers as it requires a certain level of knowledge and experience regarding the code base. This paper demonstrates how the difficulty of designing a proper query can be alleviated through automatic Query Reformulation (QR) - an under-the-hood operation for reformulating a user's query with no additional input from the user. The proposed QR framework works by enriching a user's search query with certain specific additional terms drawn from the highest-ranked artifacts retrieved in response to the initial query. The important point here is that these additional terms injected into a query are those that are deemed to be “close” to the original query terms in the source code on the basis of positional proximity. This similarity metric is based on the notion that terms that deal with the same concepts in source code are usually proximal to one another in the same files. We demonstrate the superiority of our QR framework in relation to the QR frameworks well-known in the natural language document retrieval by showing significant improvements in bug localization performance for two large software projects using more than 4,000 queries.

Our work presents solutions to two related vexing problems in feature-based localization of ground targets in Unmanned Aerial Vehicle (UAV) images: (i) A good initial guess at the pose estimate that would speed up the convergence to the final pose estimate for each image frame in a video sequence; and (ii)Time-bounded estimation of the position of the ground target. We address both these problems within the framework of the Iterative Closest Point (ICP) algorithm that now has a rich tradition of usage in computer vision and robotics applications. We solve the first of the two problems by frame-to-frame propagation of the computed pose estimates for the purpose of the initializations needed by ICP. The second problem is solved by terminating the iterative estimation process at the expiration of the available time for each image frame. We show that when frame-to-frame homography is factored into the iterative calculations, the accuracy of the position calculated at the time of bailing out of the iterations is nearly always sufficient for the goals of UAV vision.

Fast and accurate localization of software defects continues to be a difficult problem since defects can emanate from a large variety of sources and can often be intricate in nature. In this paper, we show how version histories of a software project can be used to estimate a prior probability distribution for defect proneness associated with the files in a given version of the project. Subsequently, these priors are used in an IR (Information Retrieval) framework to determine the posterior probability of a file being the cause of a bug. We first present two models to estimate the priors, one from the defect histories and the other from the modification histories, with both types of histories as stored in the versioning tools. Referring to these as the base models, we then extend them by incorporating a temporal decay into the estimation of the priors. We show that by just including the base models, the mean average precision (MAP) for bug localization improves by as much as 30%. And when we also factor in the time decay in the estimates of the priors, the improvements in MAP can be as large as 80%.

As the popularity of text-based source code search and analysis grows, the use of stemmers to strip suffixes has increased. Although widely investigated in the information retrieval community, the comparative effectiveness of stemmers in the domain of software is relatively unknown. In this paper, we investigate which of the well-known stemmers perform best in the domain of Java software for concern location and bug localization. For these two problems, we evaluate the use of stemming on over 500 search tasks for six different Java applications. Using MAP and Rank Measure, we conducted an overall qualitative study and a query-by-query quantitative study of the impact of stemming on retrieval effectiveness. As one might expect, our contribution demonstrates that how stemming affects retrieval performance is mediated by other factors, such as the use of tf-idf to filter commonly occurring terms and the precise nature of the queries. Specifically, we find that the extent to which stemming improves the retrieval performance relates to the degree of natural language content in a query.

From the standpoint of retrieval from large software libraries for the purpose of bug localization, we compare five generic text models and certain composite variations thereof. The generic models are: the Unigram Model (UM), the Vector Space Model (VSM), the Latent Semantic Analysis Model (LSA), the Latent Dirichlet Allocation Model (LDA), and the Cluster Based Document Model (CBDM). The task is to locate the files that are relevant to a bug reported in the form of a textual description by a software developer. We use for our study iBUGS, a benchmarked bug localization dataset with 75 KLOC and a large number of bugs (291). A major conclusion of our comparative study is that simple text models such as UM and VSM are more effective at correctly retrieving the relevant files from a library as compared to the more sophisticated models such as LDA. The retrieval effectiveness for the various models was measured using the following two metrics: (1) Mean Average Precision; and (2) Rank-based metrics. Using the SCORE metric, we also compare the retrieval effectiveness of the models in our study with some other bug localization tools.

Most tracking algorithms implicitly apply a coarse segmentation of each target object using a simple mask such as a rectangle or an ellipse. Although convenient, such coarse segmentation results in several problems in tracking - drift, switching of targets, poor target localization, to name a few - since it inherently includes extra non-target pixels if the mask is larger than the target or excludes some portion of target pixels if the mask is smaller than the target. In this paper, we propose a novel probabilistic framework for jointly solving segmentation and tracking. Starting from a joint Gaussian distribution over all the pixels, candidate target locations are evaluated by first computing a pixel-level segmentation and then explicitly including this segmentation in the probability model. The segmentation is also used to incrementally update the probability model based on a modified probabilistic principal component analysis (PPCA). Our experimental results show that the proposed method of explicitly considering pixel-level segmentation as a part of solving the tracking problem significantly improves the robustness and performance of tracking compared to other state-of-the-art trackers, particularly for tracking multiple overlapping targets.

In this paper, we present a distributed multicamera face tracking system suitable for large wired camera networks. Unlike previous multicamera face tracking systems, our system does not require a central server to coordinate the entire tracking effort. Instead, an efficient camera clustering protocol is used to dynamically form groups of cameras for in-network tracking of individual faces. The clustering protocol includes cluster propagation mechanisms that allow the computational load of face tracking to be transferred to different cameras as the target objects move. Furthermore, the dynamic election of cluster leaders provides robustness against system failures. Our experimental results show that our cluster-based distributed face tracker is capable of accurately tracking multiple faces in real-time. The overall performance of the distributed system is comparable to that of a centralized face tracker, while presenting the advantages of scalability and robustness.

The best of Kalman-filter-based frameworks reported in the literature for rigid object tracking work well only if the object motions are smooth (which allows for tight uncertainty bounds to be used for where to look for the object features to be tracked). In this contribution, we present a new Kalman-filter-based framework that carries out fast and accurate rigid object tracking even when the object motions are large and jerky. The new framework has several novel features, the most significant of which is as follows: the traditional backtracking consists of undoing one-at-a-time the model-to-scene matchings as the pose-acceptance criterion is violated. In our new framework, once a violation of the pose-acceptance criterion is detected, we seek the best largest subset of the candidate scene features that fulfill the criterion, and then continue the search until all the model features have been paired up with their scene correspondents (while, of course, allowing for nil-mapping for some of the model features). With the new backtracking framework, our Kalman filter is able to update on a real-time basis the pose of a typical industrial 3-D object moving at the rate of approximately 5 cm/s (typical for automobile assembly lines) using off-the-shelf PC hardware. Pose updating occurs at the rate of 7 frames per second and is immune to large jerks introduced manually as the object is in motion. The objects are tracked with an average translational accuracy of 4.8 mm and the average rotational accuracy of 0.27$^\circ$.

The metrics formulated to date for characterizing the modularization quality of object-oriented software have considered module and class to be synonymous concepts. But a typical class in object oriented programming exists at too low a level of granularity in large object-oriented software consisting of millions of lines of code. A typical module (sometimes referred to as a superpackage) in a large object-oriented software system will typically consist of a large number of classes. Even when the access discipline encoded in each class makes for "clean" class-level partitioning of the code, the intermodule dependencies created by associational, inheritance-based, and method invocations may still make it difficult to maintain and extend the software. The goal of this paper is to provide a set of metrics that characterize large object-oriented software systems with regard to such dependencies. Our metrics characterize the quality of modularization with respect to the APIs of the modules, on the one hand, and, on the other, with respect to such object-oriented inter-module dependencies as caused by inheritance, associational relationships, state access violations, fragile base-class design, etc. Using a two-pronged approach, we validate the metrics by applying them to popular open-source software systems.

We present a system for constructing 3D models of real-world objects with optically challenging surfaces. The system utilizes a new range imaging concept called multi-peak range imaging, which stores multiple candidates of range measurements for each point on the object surface. The multiple measurements include the erroneous range data caused by various surface properties that are not ideal for structured-light range sensing. False measurements generated by spurious reflections are eliminated by applying a series of constraint tests. The constraint tests based on local surface and local sensor visibility are applied first to individual range images. The constraint tests based on global consistency of coordinates and visibility are then applied to all range images acquired from different viewpoints. We show the effectiveness of our method by constructing 3D models of five different optically challenging objects. To evaluate the performance of the constraint tests and to examine the effects of the parameters used in the constraint tests, we acquired the ground truth data by painting those objects to suppress the surface-related properties that cause difficulties in range sensing. Experimental results indicate that our method significantly improves upon the traditional methods for constructing reliable 3D models of optically challenging objects.

By active stereo we mean a stereo vision system that allows for independent panning and tilting for each of the two cameras. One advantage of active stereo in relation to regular stereo is the former's wider effective field of view; if an object is too close to the camera baseline, the depth to the object can still be estimated accurately by panning the cameras appropriately. Another advantage of active stereo is that it can yield a larger number of depth measurements simultaneously for each position of the platform on which the camera system is mounted. Panning and tilting over a large angular range, while being the main reason for the advantages of active stereo, also make it more challenging to calibrate such systems. For a calibration procedure to be effective for active stereo, the estimated parameters must be valid over the entire range of the pan and tilt angles. This paper presents a new approach to the calibration of such vision systems. Our method is based on the rationale that an active stereo calibration procedure must explicitly estimate the locations and the orientations of the pan and tilt rotating axes for the cameras through a closed-form solution. When these estimates for the axes are combined with the homogeneous transform relationships that link the various coordinate frames, we end with a calibration that is valid over a large variation in the pan and tilt angles.

We present in this paper a new set of metrics that measure the quality of modularization of a non-object-oriented software system. We have proposed a set of design principles to capture the notion of modularity and defined metrics centered around these principles. These metrics characterize the software from a variety of perspectives: structural, architectural, and notions such as the similarity of purpose and commonality of goals. (By structural, we are referring to intermodule coupling-based notions, and by architectural, we mean the horizontal layering of modules in large software systems.) We employ the notion of API (application programming interface) as the basis for our structural metrics. The rest of the metrics we present are in support of those that are based on API. Some of the important support metrics include those that characterize each module on the basis of the similarity of purpose of the services offered by the module. These metrics are based on information-theoretic principles. We tested our metrics on some popular open-source systems and some large legacy-code business applications. To validate the metrics, we compared the results obtained on human-modularized versions of the software (as created by the developers of the software) with those obtained on randomized versions of the code. For randomized versions, the assignment of the individual functions to modules was randomized

This paper seeks to increase the efficiency of background subtraction algorithms for motion detection. Our method uses a quadtree-base hierarchical framework that samples a small portion of the pixels in each image and yet produces motion detection results that are very similar compared to the conventional methods that raster scan entire images. The hierarchical data structure presented in this paper can be used with any background subtraction algorithm that employs background modeling and motion detection on a per-pixel basis. We have tested our method using two common background subtraction algorithms: running average and mixture of Gaussian. Our experimental results show that the application of the hierarchical data structure significantly increases the processing speed for accurate motion detection. For example, the mixture of Gaussian method with our hierarchical data structure is able to process 1600 by 1200 images at 11~12 frames per second compared to 2~3 frames per second without using the hierarchical data structure.

The apparent pixel motion in an image sequence, called optical flow, is a useful primitive for automatic scene analysis and various other applications of computer vision. In general, however, the optical flow estimation suffers from two significant problems: the problem of illumination that varies with time and the problem of motion discontinuities induced by objects moving with respect to either other objects or with respect to the background. Various integrated approaches for solving these two problems simultaneously have been proposed. Of these, those that are based on the LMedS (Least Median of Squares) appear to be the most robust. The goal of this paper is to carry out an error analysis of two different LMedS-based approaches, one based on the standard LMedS regression and the other using a modification thereof as proposed by us recently. While it is to be expected that the estimation accuracy of any approach would decrease with increasing levels of noise, for LMedS-like methods, it is not always clear as to how much of that decrease in performance can be attributed to the fact that only a small number of randomly selected samples is used for forming temporary solutions. To answer this question, our study here includes a baseline implementation in which all of the image data is used for forming motion estimates. We then compare the estimation errors of the two LMedS-based methods with the baseline implementation. Our error analysis demonstrates that, for the case of Gaussian noise, our modified LMedS approach yields better estimates at moderate levels of noise, but is outperformed by the standard LMedS method as the level of noise increases. For the case of salt-and-pepper noise, the modified LMedS method consistently performs better than the standard LMedS method.

We present a new set of metrics for analyzing the interaction between the modules of a large software system. We believe that these metrics would be important to any automatic or semi-automatic code modularization algorithm. The metrics are based on the rationale that code partitioning should be based on the principle of similarity of service provided by the different functions encapsulated in a module. Although module interaction metrics are necessary for code modularization, in practice they must be accompanied by metrics that measure other important attributes of how the code is partitioned into modules. These other metrics, dealing with code properties such as the approximate uniformity of module sizes, conformance to any size constraints on the modules, etc., are also included in the work presented here. To give the reader some insight into the workings of our metrics, this paper also includes some results obtained by applying the metrics to the body of code that constitutes the open-source Apache HTTP server. We apply our metrics to this code as packaged by the developers of the software and to the other partially and fully randomized versions of the code.

This paper presents an efficient person tracking algorithm for a vision-based mobile robot using two independently moving cameras each of which is mounted on its own pan/tilt unit. Without calibrating these cameras, the goal of our proposed method is to estimate the distance to a target appearing in the image sequences captured by the cameras. The main contributions of our approach include: 1) establishing the correspondence between the control inputs to the pan/tilt units and the pixel displacement in the image plane without using the intrinsic parameters of the cameras; and 2) derivation of the distance information from the correspondence between the centers of masses of the segmented color-blobs from the left and the right images without stereo camera calibration. Our proposed approach has been successfully tested on a mobile robot for the task of person following in real environments.

This paper presents a robust model-based visual tracking algorithm that can give accurate 3D pose of a rigid object. Our tracking algorithm uses an incremental pose update scheme in a prediction-verification framework. Extended Kalman filter is used to update the pose of a target incrementally to minimize the error between the expected map of the target model and the corresponding gradient edge in the image space. The main contributions of this paper include: 1) A novel approach to how we use the two extremities of straight-lines as features. By taking into account the measurement uncertainties associated with the locations of the extracted extremities of the straight-line, our approach can compare correctly two straight-lines of different lengths. 2) Our use of a test of mean criterion for initiating backtracking and our use of a variable threshold on the output of this criterion that makes nil-matching more effective. We have tested our tracking algorithm with image sequences containing highly cluttered backgrounds. The system successfully tracks objects even when they are highly occluded.

The problem of motion estimation, in general, is made difficult by large illumination variations and by motion discontinuities. In recent papers, we and others have proposed global approaches to deal with both problems simultaneously within the regularization framework. A major drawback of such global methods is that several regularization parameters responsible for the integration of the illumination and motion components need to be determined in advance. This has reduced the applicability of global methods. In this paper, a parameter-free local approach, which solves a linear regression problem using a simple parametric model, is presented. To achieve robustness for the linear regression problem, we introduce a modified version of the least median of squares algorithm. We show quantitative error comparisons between the results obtained by our local approach and those produced by several global methods. Our results show that our local method is comparable to the best results obtained by the global approaches yet does not require any manual selection of parameters. 1

This paper presents two different algorithms for object tracking and pose estimation. Both methods are based on an appearance model technique called Active Appearance Model (AAM). The key idea of the first method is to utilize two instances of the AAM to track landmark points in a stereo pair of images and perform 3D reconstruction of the landmarks followed by 3 D pose estimation. The second method, the AAM matching algorithm is an extension of the original AAM that incorporates the full 6 DOF pose parameters as part of the minimization parameters. This extension allows for the estimation of the 3D pose of any object, without any restriction on its geometry. We compare both algorithms with a previously developed algorithm using a geometric-based approach [14]. The results show that the accuracy in pose estimation of our new appearance-based methods is better than using the geometric-based approach. Moreover, since appearance-based methods do not require customized feature extractions, the new methods present a more flexible alternative, especially in situations where extracting features is not simple due to cluttered background, complex and irregular features, etc.

We present a distributed vision-based architecture for smart robotics that is composed of multiple control loops, each with a specialized level of competence. Our architecture is subsumptive and hierarchical, in the sense that each control loop can add to the competence level of the loops below, and in the sense that the loops can present a coarse-to-fine gradation with respect to vision sensing. At the coarsest level, the processing of sensory information enables a robot to become aware of the approximate location of an object in its field of view. On the other hand, at the finest end, the processing of stereo information enables a robot to determine more precisely the position and orientation of an object in the coordinate frame of the robot. The processing in each module of the control loops is completely independent and it can be performed at its own rate. A control Arbitrator ranks the results of each loop according to certain confidence indices, which are derived solely from the sensory information. This architecture has clear advantages regarding overall performance of the system, which is not affected by the "slowest link," and regarding fault tolerance, since faults in one module does not affect the other modules. At this time we are able to demonstrate the utility of the architecture for stereoscopic visual servoing. The architecture has also been applied to mobile robot navigation and can easily be extended to tasks such as "assembly-on-the-fly."

This paper presents a human-computer interaction (HCI) framework for building vision models of three-dimensional (3-D) objects from their two-dimensional (2-D) images. Our framework is based on two guiding principles of HCI: 1) provide the human with as much visual assistance as possible to help the human make a correct input; and 2) verify each input provided by the human for its consistency with the inputs previously provided. For example, when stereo correspondence information is elicited from a human, his/her job is facilitated by superimposing epipolar lines on the images. Although that reduces the possibility of error in the human marked correspondences, such errors are not entirely eliminated because there can be multiple candidate points close together for complex objects. For another example, when pose-to-pose correspondence is sought from a human, his/her job is made easier by allowing the human to rotate the partial model constructed in the previous pose in relation to the partial model for the current pose. While this facility reduces the incidence of human-supplied pose-to-pose correspondence errors, such errors cannot be eliminated entirely because of confusion created when multiple candidate features exist close together. Each input provided by the human is therefore checked against the previous inputs by invoking situation-specific constraints. Different types of constraints (and different human-computer interaction protocols) are needed for the extraction of polygonal features and for the extraction of curved features. We will show results on both polygonal objects and object containing curved features.

One of the most difficult aspects of dealing with illumination effects in computer vision is accounting for specularity in the images of real objects. The specular regions in an image are often saturated - which creates problem for all image processing algorithms that use decision thresholds. Such algorithms include those for edge detection, region segmentation, etc. Detecting specularity and whenever possible compensating for it are obviously advantageous. Along these lines, this paper represents a new specularity detection and compensation method which is based on the notion of truncated least-squares approximation to the function that maps the color distribution between two images of an object under different illumination conditions. We also present a protocol for the evaluation of the current method for specularity detection. Our protocol as currently formulated uses human subjects to grade the specularity detection method.

This paper presents a fast tracking algorithm capable of estimating the complete pose (6DOF) of an industrial object by using its circular-shape features. Since the algorithm is part of a real-time visual servoing system designed for assembly of automotive parts on-the-fly, the main constraints in the design of the algorithm were: speed and accuracy. That is: close to frame-rate performance, and error in pose estimation smaller than a few millimeters. The algorithm proposed uses only three model features, and yet it is very accurate and robust. For that reason both constraints were satisfied: the algorithm runs at 60 fps (30 fps for each stereo image) on a PIII-800 MHz computer, and the pose of the object is calculated within an uncertainty of 2.4 mm in translation and 1.5 degree in rotation.

This paper describes a new hierarchical approach to content-based image retrieval called the "customized-queries" approach (CQA). Contrary to the single feature vector approach which tries to classify the query and retrieve similar images in one step, CQA uses multiple feature sets and a two-step approach to retrieval. The first step classifies the query according to the class labels of the images using the features that best discriminate the classes. The second step then retrieves the most similar images within the predicted class using the features customized to distinguish "subclasses" within that class. Needing to find the customized feature subset for each class led us to investigate feature selection for unsupervised learning. As a result, we developed a new algorithm called FSSEM (feature subset selection using expectation-maximization clustering). We applied our approach to a database of high resolution computed tomography lung images and show that CQA radically improves the retrieval precision over the single feature vector approach. To determine whether our CBIR system is helpful to physicians, we conducted an evaluation trial with eight radiologists. The results show that our system using CQA retrieval doubled the doctors' diagnostic accuracy.

Motion estimation in the presence of occlusion is a wide open research field. As such, a critical component of the research is formulating a computational framework. A distinguishing aspect of our motion estimation scheme for solving the occlusion problem is that it cleanly handles the situation where the tracked features appear in different frames and, as features become unobservable, new features may need to be incorporated. As opposed to employing a 2D parametric motion model which restricts the object to a planar surface, we use a 3D motion model to capture the object motion and shape vectors. The precise 3D contour of the tracked object is fine-tuned within a predicted potential field.

This article reports on an extensive database of American Sign Language (ASL) motions, handshapes, words and sentences. Research on automatic recognition of ASL requires a suitable database for the training and the testing of algorithms. The databases that are currently available do not allow for algorithmic development that requires a step-by-step approach to ASL recognition-from the recognition of individual handshapes, to the recognition of motion primitives, and finally, to the recognition of full sentences. We have sought to remove these deficiencies in a new database-the Purdue RVL-SLLL ASL database.

This paper describes an approach for calibrating active stereo heads for which no prior knowledge of the world coordinate system is required. During an automated procedure derived from this approach, the mobile robot can be loosely positioned in front of a calibration pattern. Through our procedure, both the camera calibration and the neck-eye calibration are obtained. With this set of calibration matrices, the XYZ coordinates of a landmark can be determined with respect to the robot coordinate frame. The so calculated XYZ coordinates are accurate regardless of the orientation of the stereo head, even for orientations that were not used for calibration. This paper validates our approach by presenting results as accurate as a few millimeters in the calculation of the XYZ coordinates of objects at 1.5m from the stereo head.

Surveys the developments of the last 20 years in the area of vision for mobile robot navigation. Two major components of the paper deal with indoor navigation and outdoor navigation. For each component, we have further subdivided our treatment of the subject on the basis of structured and unstructured environments. For indoor robots in structured environments, we have dealt separately with the cases of geometrical and topological models of space. For unstructured environments, we have discussed the cases of navigation using optical flows, using methods from the appearance-based paradigm, and by recognition of specific objects in the environment.

In visual servoing applications using a position-based approach and an end-effector-mounted camera, the position and orientation of the camera with respect to the end-effector must be known. This information is frequently represented in the form of a homogeneous transformation matrix (HTM). For special "noise-free" cases, a closed-form solution for this calibration problem can be determined. However, in the real world, such a solution is not adequate and a least-squares approach or an adaptive algorithm must be used. In this paper, we describe a new algorithm that can simultaneously calculate the base-world and the hand-eye (camera to end-effector) HTMs. This method is robust to noise, and converges to a valid solution very quickly.

Robotic systems and their software design are based on the same principles found in other computer applications. However, while many computer systems to date are deeply rooted in concepts such as multi-processing, multi-threads, modularity, etc., robotic systems are still limited by mono-processing, centralized designs. The paper addresses these limitations by proposing a new philosophy for robotic system software design - software infrastructure $that allows for the design of an efficient, modular, fault-tolerant, and distributed software architecture. Two examples of this infrastructure applied to mobile robot navigation are also discussed.

In the context of the appearance-based paradigm for object recognition, it is generally believed that algorithms based on LDA (linear discriminant analysis) are superior to those based on PCA (principal components analysis). In this communication, we show that this is not always the case. We present our case first by using intuitively plausible arguments and, then, by showing actual results on a face database. Our overall conclusion is that when the training data set is small, PCA can outperform LDA and, also, that PCA is less sensitive to different training data sets.

The above paper by Pan et al. (ibid. vol.6 (1998)) presents a rather complicated mechanism allowing fuzzy evidence to be aggregated when fuzzy inferences are made about the same fuzzy variable by different rules. The purpose of this comment is to present a simpler way to address this FuzzyCLIPS problem. In reply, the authors point out that the commenter's main conclusions about their work are ill founded. They believe that his erroneous conclusions were caused by his misunderstanding the difference between rule firing and evidence aggregation in their work.

This paper makes two contributions. The first contribution is an approach called the "customized-queries" approach (CQA) to content-based image retrieval. The second is an algorithm called FSSEM that performs feature selection and clustering simultaneously. The customized queries approach first classifies a query using the features that best differentiate the major classes and then customizes the query to that class by using the features that best distinguish the images within the chosen major class. This approach is motivated by the observation that the features that are most effective in discriminating among images from different classes may not be the most effective for retrieval of visually similar images within a class. This occurs for domains in which not all pairs of images within one class have equivalent visual similarity, i.e., subclasses exists. Because we are not given subclass labels, we must simultaneously find the features that best discriminate the subclasses and at the same time find these subclasses. We use FSSEM to find these features. We apply this approach to content-based retrieval of high-resolution tomographic images of patients with lung disease and show that this approach radically improves the retrieval precision over the traditional approach that performs retrieval using a single feature vector.

A new general-purpose color image segmentation editor (CISE) for the purpose of extracting a semantic object is designed, implemented and tested on a number of various natural scene images. Our editor integrates a deformable model and image statistics including intensity, color, gradient and texture. The editor starts with a coarse region segmentation which applies the Canny's operator followed by a low-complexity edge linking algorithm. This segmentation basically builds regions of smooth intensity by closing all dangling edges. Next, a topologically-based region labeling method makes full use of relationship among pixels and produces useful labeled image. Finally, to refine the extracted object of interest (O/sup 2/I), a deformable model based on energy minimization is applied by incorporating both the gradient and region criteria to the external constraint force. These processes are demonstrated through examples on natural scene color images. Experimental results suggest the efficiency and accuracy of the algorithm in its segmentation operations.

There exist in the literature today many contributions dealing with the incorporation of fuzzy logic in expert systems. However, unfortunately, much of what has been proposed can only be applied to small-scale expert systems; that is, when the number of rules is in the dozens as opposed to in the hundreds. The more traditional (nonfuzzy) expert systems are able to cope with large numbers of rules by using Rete networks for maintaining matches of all the rules and all the facts. (A Rete network obviates the need to match the rules with the facts on every cycle of the inference engine.) In this paper, we present a more general Rete network that is particularly suitable for reasoning with fuzzy logic. The generalized Rete network consists of a cascade of three networks: the pattern network, the join network, and the evidence aggregation network. The first two layers are modified versions of similar layers for the traditional Rete networks and the last, the aggregation layer, is a new concept that allows fuzzy evidence to be aggregated when fuzzy inferences are made about the same fuzzy variable by different rules.

This paper describes a vision-based navigation method in an indoor environment for an autonomous mobile robot which can avoid obstacles. In this method, the self-localization of the robot is achieved by a model-based vision system, and nonstop navigation is realized by a retroactive position correction system. Stationary obstacles are avoided with single-camera vision and moving obstacles are detected with ultrasonic sensors. We report on experiments in a hallway using the YAMABICO robot.

This paper describes a vision-based navigation method in an indoor environment for an autonomous mobile robot which can avoid obstacles. In this method, the self-localization of the robot is done with a mode-based vision system, and a non-stop navigation is realized by a retroactive position correction system. Stationary obstacles are avoided with single-camera vision and moving obstacles are detected with ultrasonic sensors. We report on experiments in a hallway using the YAMABICO robot.

This paper deals with enhancing the level of autonomy in a robotic work cell. With that mission in mind, the authors present an integrated framework for the sensing, the planning, and the execution aspects of assembly. In experimental demonstrations of this system on a PUMA762, the authors can now throw objects randomly into the workspace of the robot and the robot then automatically synthesizes a manipulation plan that includes the operations of sensing, grasping, and regrasping. Each operation is invoked only when it is deemed necessary for the successful execution of assembly.

This article presents a new theorem and an algorithm for fast synthesis of two-fingered force-closure grasps for arbitrary polygonal objects. The polygonal objects are allowed to be of arbitrary shape, in the sense that there is no restriction that the objects be convex. Moreover, each edge of the polygon is allowed to have different frictional characteristics. Our novel formulation results in a simple and efficient algorithm that finds grasps that tolerate the largest positioning errors for each of the fingertips at the contact points. The algorithm is both complete and correct, meaning that if any force-closure grasp exists for the object, the algorithm will find it; furthermore, all the grasps synthesized by the algorithm are guaranteed to be valid force-closure grasps.

This paper deals with the automatic programming of robots. We present here a method in which a robot can learn new assembly tasks by monitoring the performance of a human operator wearing a DataGlove. In particular, the system records the motions of the DataGlove as it is used to manipulate actual objects and, by using geometric reasoning, deduces the assembly task that is being performed. Subsequently, the assembly steps thus deduced are translated automatically by a task planner into a robot manipulation program. In experimental demonstrations of this system, the robot can now learn assembly tasks involving pickups, putdowns and various mating operations.

This paper discusses some representation issues and challenges involved in object recognition. It is intended as a step toward assessing current object representation schemes and proposing design and evaluation criteria for future ones.>

This paper deals with enhancing the level of autonomy in a robotic work cell. With that mission in mind, we present here an integrated framework for the sensing, the planning, and the execution aspects of assembly. In experimental demonstrations of this system on a PUMA 762, we can now throw objects randomly into the work space of the robot and the robot then automatically synthesizes a manipulation plan that includes the operations of sensing and regrasping only when these are deemed necessary for the successful execution of assembly.>

We discuss the model-acquisition and model-matching aspects of a model-based vision system for the bin-picking of twisted tubular parts. The system uses both 3-D structured-light vision and 2-D binary vision in a synergistic manner. Binary vision kicks in when the robot picks up a tube using a graspable fragment identified as such by the 3-D vision system; the tube thus picked up is placed on a backlit table so that its pose can be calculated from its 2D image with sufficient precision to allow its assembly with another object. The binary vision carries out pose calculation by affine matching the projected image with a small set of model projections, each corresponding to a separate stable pose of the object on a flat surface and each represented by the coordinates of only four points. This paper presents a heuristic algorithm for determining the placement of the four points for representing the model projections.>

Presents a simplified forward gait for a quadruped walking robot. The proposed gait is a straight line, periodic, monotonically forward (SLPMF) gait and can easily be used for adaptive gait control, requiring only simple modifications. The authors show that given a support pattern, meaning a polygon generated by connecting the feet positions that are in contact with the ground, only certain sequences of leg movements will generate the SLPMF gait. The authors also introduce a useful method to determine how to preserve stability of a quadruped robot during the motions called for by an SLPMF gait. The authors also discuss the leg design from a hardware standpoint; the design permits independent joint control.>

Both man-made and natural objects are described by both their geometric shapes and by their non-geometric attributes such as color. The objective of the proposed research is to create a system which integrates geometric and non-geometric attribute information for fast 3D model-based object recognition. Hashing is employed in a hypothesize and verify approach to the 3D model-based object recognition problem. Viewpoint independent attributes are used in the hypothesis generation stage to eliminate model objects from consideration during hypothesis formation. Utilizing more than one attribute in the proposed hashing scheme helps to ensure a reduction in the actual execution time for object recognition over a larger number of model bases. A nice feature of the system is that new object attributes can be added with relative ease. Issues concerning the ranking of attributes by their distinctiveness with respect to the objects in the model base are discussed. Current work on the use of an information theoretic measure in the design of an optimal multiple attribute hash table is presented.

This exposition is a tutorial on how object-oriented programming (OOP) in LISP can be used for programming a blackboard. Since we have used Common LISP and the Common LISP Object System (CLOS), the exposition demonstrates how object classes and the primary, before, and after methods associated with the classes can be used for this purpose. the reader should note that the different approaches to object-orient programming share considerable similarity and, therefore, the exposition should be helpful to even those who may not wish to use CLOS. We have used the radar tracking problem as a “medium” for explaining the concepts underlying blackboard programming the blackboard database is constructed solely of classes which act as data structures as well as method-bearing objects. Class instances form the nodes and the levels of the blackboard. the methods associated with these classes constitute a distributed monitor and support the knowledge sources in modifying the blackboard data. A rule-based planner is used to construct knowledge source activation records from the goals residing in the blackboard. These activation records are enqueued in a cyclic queueing system. A scheduler cycles through the queues and selects knowledge sources to fire. © John Wiley & Sons, Inc.

The authors discuss a system, called AMP-CAD, which develops assembly motion plans using CAD models of parts. They place an emphasis on the calculation of the potential fields used for motion planning. Potential fields can be thought of as a mechanism to interface CAD representations with plan development. AMP-CAD is a complete system that combines an assembly representation, a two-phase motion planner, and a execution unit into a single integrated package. Implementation and experimental results are discussed.>

The model-based vision system described in this thesis allows a mobile robot to navigate indoors at an average speed of 8 meters/minute using ordinary laboratory computing hardware of approximately 16 MIPS power. The navigation capabilities of the robot are not impaired by the presence of the stationary or moving obstacles. The vision system maintains a model of uncertainty and keeps track of the growth of uncertainty as the robot travels towards the goal position. The estimates of uncertainty are then used to predict bounds on the locations and orientations of landmarks expected to be seen in a monocular image. This greatly reduces the search for establishing correspondence between the features visible in the image and the landmarks. Given a sequence of image features and a sequence of landmarks derived from a geometric model of the environment, a special aspect of our vision system is the sequential reduction in the uncertainty as each image feature is matched successfully with a landmark, allowing subsequent features to be matched more easily, this being a natural byproduct of the manner in which we use Kalman-filter based updating. Strategies for path planning, path replanning and perception planning are introduced for the robot to navigate in the presence of obstacles. Finally, experimental results are presented.

The authors introduce a planning system that relies on a novel approach which converts geometrical descriptions of assembly parts into potential field representations and then translates assembly operations into equivalent operations on the potential field representations. As a consequence, the system is able to quickly compute a path for the assembly motions and isolate those regions of the path where force/torque guided motions must be introduced to cope with possible collisions that may be caused by the prevailing uncertainties in the positions/orientations of the parts and their dimensions. This system has been experimentally verified using a Cincinnati Milacron T/sup 3-/726 robot to assemble a gear box.>

The authors show how large efficiencies can be achieved in model-based 3-D vision by combining the notions of discrete relaxation and bipartite matching. The computational approach presented is capable of pruning large segments of search space-an indispensable step when the number of objects in the model library is large and when recognition of complex objects with a large number of surfaces is called for. Bipartite matching is used for quick wholesale rejection of inapplicable models and for the determination of compatibility of a scene surface with a potential model surface taking into account relational considerations. The time complexity function associated with those aspects of the procedure that are implemented via bipartite matching is provided. The algorithms do not take more than a couple of iterations, even for objects with more than 30 surfaces.>

A description is given of SPAR, a task planner that has been implemented on a PUMA 762. SPAR is capable of formulating manipulation plans to meet specified assembly goals; these manipulation plans include grasping and regrasping operations if they are deemed necessary for successful completion of assembly. SPAR goes beyond classical AI planners in the sense that SPAR is capable of solving geometric goals associated with high-level symbolic goals. Consequently, if a high-level symbolic goals. Consequently, if a high-level symbolic goal is on (A,B), SPAR can also entertain the geometric conditions associated with such a goal. Therefore, a simple goal such as on (A,B) may or may not be found to be feasible depending on the kinematic constraints implied by the associated geometric conditions. SPAR has available to it a user-defined repertoire of actions for solving goals and associated with each action is an uncertainty precondition that defines the maximum uncertainty in the world description that would guarantee the successful execution of that action. SPAR has been implemented as a nonlinear constraint posting planner.>

Generic shape recognition is the problem of determining the pose and dimensions of objects for which only topological models are available (that is, the shape of the object is known but the size is unknown). One such application domain is the handling and sorting of postal objects. Because metrical information relating object features to one another is not available, the more common model-based approaches are inadequate. The INGEN (inference engine for generic object recognition) system uses a data-driven approach to recognize objects with generic shapes, such as parallelepipeds and cylinders, when the dimensions of the objects are unknown. Size and pose estimation are facilitated by a geometric reasoning process which extends objects in the direction away from the sensor until they physically contact other objects in the scene. The results of experiments which use the INGEN system to guide a robot in the manipulation of postal objects are presented.>

Vision sensor output can be processed to yield a multitude of low-level measurements, where each is inherently uncertain, which must somehow be combined to verify the locations of an object. It is shown that this combination can be accomplished via Dempster-Shafer theory using binary frames of discernment (BFODs). A special advantage of BFODs is the computational ease with which they allow information from disparate sources to be combined, which is particularly significant in light of recent concerns about the exponential complexity of a brute-force implementation of this theory.>

An architecture for reasoning with uncertainty about the identities of objects in a scene is described. The main components of this architecture create and assign credibility to object hypotheses based on feature-match, object, relational, and aspect consistencies. The Dempster-Shafer formalism is used for representing uncertainty, so these credibilities are expressed as belief functions which are combined using Dempster's combination rule to yield the system's aggregate belief in each object hypothesis. One of the principal objections to the use of Dempster's rule is that its worst-case time complexity is exponential in the size of the hypothesis set. The structure of the hypothesis sets developed by this system allow for a polynomial implementation of the combination rule. Experimental results affirm the effectiveness of the method in assessing the credibility of candidate object hypotheses.>

An approach is presented for planning sensing strategies dynamically on the basis of the system's current best information about the world. The approach is for the system to propose a sensing operation automatically and then to determine the maximum ambiguity which might remain in the world description if that sensing operation were applied. The system then applies that sensing operation which minimizes this ambiguity. To do this, the system formulates object hypotheses and assesses its relative belief in those hypotheses to predict what features might be observed by a proposed sensing operation. Furthermore, since the number of sensing operations available to the system can be arbitrarily large, equivalent sensing operations are grouped together using a data structure that is based on the aspect graph. In order to measure the ambiguity in a set of hypotheses, the authors apply the concept of entropy from information theory. This allows them to determine the ambiguity in a hypothesis set in terms of the number of hypotheses and the system's distribution of belief among those hypotheses.>

The authors present 3D-POLY, a working system for recognizing objects in the presence of occlusion and against cluttered backgrounds. The time complexity of this system is only O(n/sup 2/) for single-object recognition, where n is the number of features on the project. The organisation of the feature data for the models is based on a data structure called the feature sphere. Efficient constant-time algorithms for assigning a feature to its proper place on a feature sphere and for extracting the neighbors of a given feature from the feature sphere representation are presented. For hypothesis generation, local feature sets are used. The combination of the feature sphere idea for streamlining verification and the local feature sets for hypothesis generation results in a system whose time complexity has a low-order polynomial bound.>

A method for the mating of tightly fitting parts in the presence of significant sensing, model, and control uncertainties is presented. Using this method randomly placed parts that were located using a three-dimensional laser range scanning system can be mated even when the clearance between them is only 0.001 in. The various sources of error introduced in the fine forced-guided motions used to execute assemblies are examined. Among these sources are noisy force/torque readings, mechanical vibrations, the presence of sliding and sticking frictions, and the possibility of eccentric oblique impacts. It is pointed out how most of these errors might be reduced or eliminated. Straight-line motion goals (SLMGs) are then processed by the basic building blocks of a dynamic planning strategy. By dynamically building an assembly plan out of SLMGs, it is possible to carry out robotic assemblies in the presence of sensing and model uncertainties while recognizing and recovering from errors introduced by control uncertainties. A specific instance of this approach is outlined.>

The authors present seldom-discussed sources of error in force-guided motions to execute assemblies. Among these sources are noisy F/T (force/torque) readings, the presence of sliding and sticking frictions, and the possibilities of eccentric oblique impacts. They point out how most of these errors might be reduced or eliminated. The authors introduce the notion of straight line motion goals (SLMGs) and show how SLMGs can be considered as the basic building blocks of a dynamic planning strategy. The steps required to carry out peg-in-hole experiments are examined. It is shown how the torque vector can be used to compute the direction in which the peg should be compliantly moved to align the axes of the peg and the hole. The authors present an error-detection-and-recovery algorithm for these experiments and show the dependence of the success rate on the number of error-detection-and-recovery cycles allowed.>

The authors present an approach to planning sensing strategies in a robot workcell with multisensor capabilities. The system first forms an initial set of object hypotheses by using one of the sensors. Subsequently, the system reasons over different possibilities for selecting the next sensing operation, this being done in a manner so as to maximally disambiguate the initial set of hypotheses. The 'next sensing operation' is characterized by both the choice of the sensor and the viewpoint to be used. Aspect graph representation of objects plays a central role in the selection of the viewpoint, these representations being derived automatically by a solid modelling program.>

A novel approach to solving the stereo correspondence problem in computer vision is described. Structural descriptions of two two-dimensional views of a scene are extracted by one of possibly several available low-level processes, and a new theory of inexact matching for such structures is derived. An entropy-based figure of merit for attribute selection and ordering is defined. Experimental results applying these techniques to real image pairs are presented. Some manipulation experiments are briefly presented.>

In this report we have used projectivity theory to model the process of structured light scanning for 3D robot vision. The projectivity formalism is used to derive a 4 × 3 transformation matrix that converts points in the image plane into their corresponding 3D world coordinates. Calibration of the scanner consists of computing the coefficient of this matrix by showing to the system a set of lines generated by suitable object edges. We end this paper by showing how the matrix can be used to convert image pixel locations into the world coordinates of the corresponding object points using two different scanning strategies.

World representation is obviously a most important part of the sensory intelligence required by a mobile robot in order to operate autonomously in a complex environment. In this paper, we will propose a taxonomy of robot intelligence based on the methods used for world representation and for the integration of sensory information with the representations. These methods of representation and sensory integration are currently being programmed into PETER, a mobile robot, in our lab.

A major hurdle in the development of intelligent robots is that we still do not possess efficient computational and representational methodologies for emulating knowledge and expectation driven behavior so basic to human cognition and problem solving. Even if we use techniques such as geometric modeling for representing objects in the robot world, we are still lacking in methods for linking such representations with sensory feedback. In this paper, we have proposed the use of intermediate representations - we call them sensor-tuned representations - for linking CSG based solid modeling with sensory information. We also discuss how sensor-tuned representations are constructed from range data and how object recognition can be done with sensor-tuned representations. Finally, we show results of manipulation experiments produced by the current implementation of the system.

In this paper, we discuss a novel strategy for rapid acquisition of the range map of a scene employing color-encoded structured light. This technique offers several potential advantages including increased speed and improved accuracy. In this approach we illuminate the scene with a single encoded grid of colored light stripes. The indexing problem, that of matching a detected image plane stripe with its position in the projection grid, is solved from a knowledge of the color grid encoding. In fact, the possibility exists for the first time to acquire high-resolution range data in real time for modest cost, since only a single projection and single color image are required. Grid to grid alignment problems associated with previous multistripe techniques are eliminated, as is the requirement for dark interstices between grid stripes. Scene illumination is more uniform, simplifying the stripe detection problem, and mechanical difficulties associated with the equipment design are significantly reduced.

In this paper, we present FProlog, a programming language designed to act as the top level in a robot assembly system. FProlog is a logic programming language, with the ability to interface with LISP. This allows the use of a logic programming environment to construct assembly plans, while using LISP programs to interface with vision systems, world modeling systems, robot manipulators, etc. FProlog differs from hybrid logic programming languages, such as LOGLISP, in that FProlog may invoke functional programs as goals, and functional programs may invoke FProlog's inference engine. Also, FProlog differs from traditional robot assembly languages, such as AUTOPASS, in its generality, and therefore its ability to interface with many different subsystems. As a demonstration of the applicability of FProlog, we also present an FProlog program which is used as the top level in a robot assembly system which performs a version of the blocks world experiment.

In a recent report [7], we proposed algorithms for segmenting out the visible part of the topmost object from a pile of planar and curved objects. Planar objects considered were of convex polyhedral type, such as prisms, boxes, wedges, etc; and the curved objects were of the type that could be recognized uniquely by using the Extended Gaussian Image, such object-types being cylinders, cones, spheres, ellipsoids, toruses, etc. For input these algorithms used 3-D vision data acquired with a structured light scanner. In this report, we will review some of the algorithms presented earlier and show our latest experimental results on scenes that are more complex than before. In our presentation at the conference, we also plan to show some manipulation experiments that for sensory feedback use 3-D vision data analyzed according to the algorithms presented here.