Graph-based image segmentation is popular, because graphs can naturally represent image parts and the relationships between them. Whilst many single-scale approaches exist, significant interest has been shown in segmentation hierarchies, which represent image objects at different scales. However, segmenting arbitrary images automatically remains elusive: segmentation is under-specified, with different users expecting different outcomes. Hierarchical segmentation compounds this, since it is unclear where in the hierarchy objects should appear. Users can easily edit flat segmentations to influence the outcome, but editing hierarchical segmentations is harder: indeed, many existing interactive editing techniques make only small, local hierarchy changes. In this paper, we address this by introducing ‘zipping’ operations for segmentation hierarchies to facilitate user interaction. We use these operations to implement algorithms for non-sibling node merging and parent switching, and perform experiments on both 2D and 3D images to show that these latter algorithms can significantly reduce the interaction burden on the user.

An autonomous robot photographer should move around a crowd, avoiding collisions while taking reasonable pictures of the subjects within it. We present a system based on a low-cost Turtlebot platform, the Kinect sensor, and a consumer-grade stills camera, that fulfills this task while applying several rules of general photograph composition. The subsumption control system was built using the ROS platform, and novel software components include the crowd head detection, the photograph composition procedures, the subject-interface, and uploading the photographs to a social media website. The result is a system that shows good performance in a public environment, as evaluated by independent human judges; performing a statistical analysis of these results against other published work verified the quality of the resulting photographs.

For the Oxford Aerial Tracking System (OATS) we are developing a robot helicopter that can track moving ground objects. Here we describe algorithms for the device to perform path planning and trajectory prediction. The path planner uses superquadratic potential fields and incorporates a height change mechanism that is triggered where necessary and in order to avoid local minima traps. The goal of the trajectory prediction system is to reliably predict the target trajectory during occlusion caused by ground obstacles. For this we use two artificial neural networks in parallel whose retraining is automatically triggered if major changes in the target behaviour pattern are detected. Simulation results for both systems are presented.

This paper presents the Resection Filter, which is a new filter for fusing bearings to known landmarks with a prior Gaussian pose estimate. The filter calculates a robot's pose based on noisy bearings independently from any prior pose estimate and then fuses this value with a prior pose estimate. Implementations of the Extended Kalman Filter and Unscented Kalman Filter are described and several experiments are conducted comparing the proposed filter with these two benchmarks. The results show that the new filter outperforms both benchmarks in nearly all the areas we considered, at least for problems in which bearing information is readily available.

Proximity queries include topics such as computation of the distance between modelled objects, and static and dynamic collision detection. They are useful for object and assembly design, and are proving to be a vital ingredient in accurate animation and simulation. This paper summarises current directions in the computation and use of proximity queries, and gives a description of our work-in-progress towards making the solution of these queries faster by using specialised hardware.

High-speed assembly makes strict demands on path and trajectory planning systems. In such systems the stages of path planning, trajectory planning, and 'low-level' control are normally separated, which admits functional simplicity but may not produce the most useful trajectories. Our active motion planner merges these levels by building a low-level controller into a potential-field planning loop. The input to the planner is a coarse set of via-points; the planner incorporates a goal that moves between these via-points, as in our previous work. The active motion planner produces relatively smooth paths; furthermore, by adjusting the relative gains of the active force (i.e., internal controller) and potential field terms the planner is able to avoid many of the local minima traps that bedevil potential field techniques. The combined planner is illustrated using a (simulated) PUMA robot arm.

Collision detection and distance calculation are two examples of proximity queries between modelled objects. They are interesting both in their own right, and as useful tools to solve other problems (e.g., robot path planning). They also form useful abstractions away from the underlying representation of a geometric model. This paper considers the solution and use of such problems in geometric modeling and robotics, gives examples from our own work, and discusses the possible future of the technology.

Given two sculptured objects, described by a collection of rational Bezier patches, we propose an algorithm that provides the distance between them if the objects are not intersecting, or a measure of penetration otherwise. The algorithm extends the upper-lower bound subdivision approach to the computation of the nearest points by considering the relative orientations between the subdivided patches. All required geometric constructions can be described as rational Bezier patches so that their control points can be precomputed from those of the original patches. Additional operations have been designed to exhibit linear complexity with the total number of involved control points.

Using rational motions it is possible to apply many fundamental Bezier spline (or B-spline) techniques to the designs of motion. The paper develops and tests a simple automatic algorithm for representing C/sup 1/ smooth motion of a rigid triangle /spl Delta/ in R/sup 3/, by means of piecewise parametric rational curves of degree 2m/2m for some m, when measurements of the positions of the vertices of the triangle /spl Delta/ at a sequence of times t/sub i/, i=0, 1, ..., n, in R/sup 3/ are given. The method presented in the paper can be applied to various problems in computer animation as well as in robotics.

Computing the distance between modelled objects is proving to be a fundamental operation for solving many problems in robotics and elsewhere. Most of the previous work in this area has focused on computing the distance between polyhedra, as the problem is easier to solve than the general case and the answer is sufficient for many problems. Here we focus on computing the distance between convex objects defined by NURBS curves or patches, for which the critical step is the evaluation of the support mapping. Experimental results are given for the two-dimensional case.

The problem of tracking the distance between two convex polyhedra is finding applications in many areas of robotics, including intersection detection, collision detection, and path planning. We present new results that confirm an almost-constant time complexity for an enhanced version of Gilbert, Johnson and Keerthi's (GJK) algorithm, and also describe modifications to the algorithm to compute measures of penetration distance.

Djinn is an API for solid modelling which is defined in the language of point-sets and is thus independent of any particular modelling data-structure (e.g. boundary representations or CSG trees). In designing this API, several significant and interesting questions have arisen, including: the basic feasibility of the approach; deciding how to support cellular models; providing facilities for navigation without traditional data-structures; addressing the problems of 'tweaks' and blends; ensuring that labels are preserved under geometric operations; permitting regions in which changes to a model have taken place to be identified; coping with approximate models; deciding whether to support variational models; keeping sweeps and transforms within a reasonable domain; and providing facilities to handle the many types of parametric surface. These questions are not all fully answered, but progress continues towards a published interface and C++ language binding.

The problem of tracking the distance between two convex polyhedra is finding applications in many areas of robotics. The algorithm of Lin and Canny (1991) is a well-known fast solution to this problem, but by recasting the algorithms into configuration space, we show that a minor modification to the earlier algorithm of Gilbert, Johnson, and Keerthi (1988) also gives this algorithm the same expected cost.

The application of autonomous guided vehicles to well-structured industrial sites requires considerably more than a path planning algorithm onboard each vehicle. Issues such as task planning, vehicle routing and vehicle-vehicle interactions predominate in determining the overall system ability. We exhibit a mathematical model of a multiple vehicle system, which has similarities to the Timed Traces models developed to reason about parallel processes. A denotational semantics is derived from this model, ascribing meaning to a simple language of service operations and concurrent path planning. This semantics captures a complete description of vehicles' behaviour, which can provide a global planning strategy guaranteeing both satisfiability and liveness.>

In constructive solid geometry, geometric solids are represented as trees whose leaves are labeled by primitive solids and whose internal nodes are labeled by set-theoretic operations. A bounding function in this context is an upper or lower estimate on the extent of the constituent sets; such bounds are commonly used to speed up algorithms based on such trees. We introduce the class of totally consistent bounding functions , which have the desirable properties of allowing surprisingly good bounds to be built quickly. Both outer and inner bounds can be refined using a set of rewrite rules, for which we give some complexity and convergence results. We have implemented the refinement rules for outer bounds within a solid modeling system, where they have proved especially useful for intersection testing in three and four dimensions. Our implementations have used boxes as bounds, but different classes (shapes) of bounds are also explored. The rewrite rules are also applicable to relatively slow, exact operations, which we explore for their theoretical insight, and to general Boolean algebras. Results concerning the relationship between these bounds and active zones are also noted.

The problem of planning collision free motions for industrial robot vehicles is considered. The systems presently in use are rather inflexible, the vehicle being rigidly constrained to follow a set of manually derived paths. Such systems are not easily or quickly reconfigurable, nor are they equipped to respond to the presence of unexpected obstacles or variations in object locations. In the hybrid motion control system presented, paths are computed from a routemap of the environment, automatically derived from geometric data. These paths are then followed by the vehicle under the control of a path execution module which utilises an artificial potential field based approach to avoid unexpected obstacles.>

A simple algorithm based on the artificial potential field paradigm and capable of planning translational motions for a convex polygonal object among polygonal obstacles is outlined. A heuristic based on the concept of taking moments is introduced. It allows this algorithm to be extended to include a rotational degree of freedom. It is then shown that this method can be used form the basis of a local obstacle avoidance algorithm for a robot vehicle following a corridor. It is observed that the lines of minimum potential which the moving object is made to follow correspond to the Voronoi diagram of the environment. It is also observed that the form of the Voronoi diagram under the Euclidean (L/sub 2/) metric is not necessarily ideal for path planning and that the minimum distance function upon which the potential field approach relies may be calculated more swiftly under the L/sub 1/ and L/sub infinity / metrics. For these reasons the form of the Voronoi diagram under those metrics is investigated.>

The collision-detection problem is to decide, given two objects and desired motions, whether the objects will come into collision over a given time span. The solution of this problem is useful, both in robotics and in other problem domains. A method is described for solving collision detection that involves transforming the problem into an intersection-detection problem over space time. The theoretical basis for the solution is given and an efficient implementation described based on describing the objects and motions constructively. The related problems of describing the collision region and detecting collisions when there are more than two moving objects are also described.>

A geometric engine called ROBMOD is described that has been designed specifically for intelligent robotics applications. ROBMOD is usable both as a geometric modelling system, based on the constructive solid geometry paradigm, and as a geometry engine that can be interrogated by programs that are reasoning about space. ROBMOD is thus able to reduce the geometric sophistication required in such spatial reasoning programs.>

To solve the clash detection problem we must decide whether a collision will occur between any pair of objects from a set of objects with known shapes and motions. We have considered three methods for performing clash detection: in the first we sample the motion at a finite number of times and perform interference detection at each time; in the second we create models of the shapes and their motions in space-time, and look for intersections between these four-dimensional entities; and in the third we create models of the volumes swept out by the objects. This paper is a brief, comparative study of these three methods, and includes some details of our experiments with the first two methods as implemented in a geometric modelling system.