The Alan Turing Institute is the UK's newly-created national centre for data science, headquartered at the British Library in the heart of London's vibrant Knowledge Quarter. Our vision is to become a world leader in data science research and innovation. This lecture will take a whistle-stop tour through the Institute's scientific and innovation programme. It tackles challenges of social and economic importance, from engineering to finance, from health and well-being to cloud computing and smart cities. The Institute aims to make unique contributions, focussing on work that is complementary to what can be done in universities. In particular, we aim to act as a national hub, attracting a diversity of talent, interest and influence. We emphasise engineering and the ability to build high quality prototypes. We encompass, in one connected physical space, a sweep of disciplines from pure mathematics, through statistics and machine learning, to social science.

We describe two new approaches to human pose estimation. Both can quickly and accurately predict the 3D positions of body joints from a single depth image without using any temporal information. The key to both approaches is the use of a large, realistic, and highly varied synthetic set of training images. This allows us to learn models that are largely invariant to factors such as pose, body shape, field-of-view cropping, and clothing. Our first approach employs an intermediate body parts representation, designed so that an accurate per-pixel classification of the parts will localize the joints of the body. The second approach instead directly regresses the positions of body joints. By using simple depth pixel comparison features and parallelizable decision forests, both approaches can run super-real time on consumer hardware. Our evaluation investigates many aspects of our methods, and compares the approaches to each other and to the state of the art. Results on silhouettes suggest broader applicability to other imaging modalities.

We propose a new method to quickly and accurately predict 3D positions of body joints from a single depth image, using no temporal information. We take an object recognition approach, designing an intermediate body parts representation that maps the difficult pose estimation problem into a simpler per-pixel classification problem. Our large and highly varied training dataset allows the classifier to estimate body parts invariant to pose, body shape, clothing, etc. Finally we generate confidence-scored 3D proposals of several body joints by reprojecting the classification result and finding local modes. The system runs at 200 frames per second on consumer hardware. Our evaluation shows high accuracy on both synthetic and real test sets, and investigates the effect of several training parameters. We achieve state of the art accuracy in our comparison with related work and demonstrate improved generalization over exact whole-skeleton nearest neighbor matching.

In this paper we introduce a new shape constraint for interactive image segmentation. It is an extension of Veksler's star-convexity prior, in two ways: from a single star to multiple stars and from Euclidean rays to Geodesic paths. Global minima of the energy function are obtained subject to these new constraints. We also introduce Geodesic Forests, which exploit the structure of shortest paths in implementing the extended constraints. The star-convexity prior is used here in an interactive setting and this is demonstrated in a practical system. The system is evaluated by means of a “robot user” to measure the amount of interaction required in a precise way. We also introduce a new and harder dataset which augments the existing Grabcut dataset with images and ground truth taken from the PASCAL VOC segmentation challenge.

Stereo matching algorithms conventionally match over a range of disparities sufficient to encompass all visible 3D scene points. Human vision, however, works over a narrow band of disparities-Panum's fusional band-whose typical range may be as little as 1/20 of the full range of disparities for visible points. Only points inside the band are fused visually; the remainder of points are seen diplopically. A probabilistic approach is presented for dense stereo matching under the Panum band restriction. It is shown that existing dense stereo algorithms are inadequate in this problem setting and the main problem is segmentation, marking the image into the areas that fall inside the band. An approximation is derived that makes up for missing out-of-band information with a "proxy" based on image autocorrelation. It is shown that the Panum Proxy algorithm achieves accuracy close to what can be obtained when the full disparity band is available, and with gains of between one and two orders of magnitude in computation time. There are also substantial gains in computation space. Panum band processing is also demonstrated in an active stereopsis framework.

The efficient application of graph cuts to Markov Random Fields (MRFs) with multiple discrete or continuous labels remains an open question. In this paper, we demonstrate one possible way of achieving this by using graph cuts to combine pairs of suboptimal labelings or solutions. We call this combination process the fusion move. By employing recently developed graph-cut-based algorithms (so-called QPBO-graph cut), the fusion move can efficiently combine two proposal labelings in a theoretically sound way, which is in practice often globally optimal. We demonstrate that fusion moves generalize many previous graph-cut approaches, which allows them to be used as building blocks within a broader variety of optimization schemes than were considered before. In particular, we propose new optimization schemes for computer vision MRFs with applications to image restoration, stereo, and optical flow, among others. Within these schemes the fusion moves are used 1) for the parallelization of MRF optimization into several threads, 2) for fast MRF optimization by combining cheap-to-compute solutions, and 3) for the optimization of highly nonconvex continuous-labeled MRFs with 2D labels. Our final example is a nonvision MRF concerned with cartographic label placement, where fusion moves can be used to improve the performance of a standard inference method (loopy belief propagation).

Efficient and accurate fitting of active appearance models (AAM) is a key requirement for many applications. The most efficient fitting algorithm today is inverse compositional image alignment (ICIA). While ICIA is extremely fast, it is also known to have a small convergence radius. Convergence is especially bad when training and testing images differ strongly, as in multi-person AAMs. We describe “forward” compositional image alignment in a consistent framework which also incorporates methods previously termed “inverse” compositional, and use it to develop two novel fitting methods. The first method, compositional gradient descent (CoDe), is approximately four times slower than ICIA, while having a convergence radius which is even larger than that achievable by direct quasi-Newton descent. An intermediate convergence range with the same speed as ICIA is achieved by LinCoDe, the second new method. The success rate of the novel methods is 10 to 20 times higher than that of the original ICIA method.

This paper proposes an efficient fusion of contour and texture cues for im-age categorization and object detection. Our work confirms and strengthens recent results that combining complementary feature types improves perfor-mance. We obtain a similar improvement in accuracy and additionally an improvement in efficiency. We use a boosting algorithm to learn models that use contour and texture features. Our main contributions are (i) the use of dense generic texture features to complement contour fragments, and (ii) a simple feature selection mechanism that includes the computational costs of features in order to learn a run-time efficient model. Our evaluation on 17 challenging and varied object classes confirms that the synergy of the two feature types performs significantly better than either alone, and that computational efficiency is substantially improved using our feature selection mechanism. An investigation of the boosted features shows a fascinating emergent property: the absence of certain textures often con-tributes towards object detection. Comparison with recent work shows that performance is state of the art. 1

Computational color constancy is the task of estimating the true reflectances of visible surfaces in an image. In this paper we follow a line of research that assumes uniform illumination of a scene, and that the principal step in estimating reflectances is the estimation of the scene illuminant. We review recent approaches to illuminant estimation, firstly those based on formulae for normalisation of the reflectance distribution in an image - so-called grey-world algorithms, and those based on a Bayesian formulation of image formation. In evaluating these previous approaches we introduce a new tool in the form of a database of 568 high-quality, indoor and outdoor images, accurately labelled with illuminant, and preserved in their raw form, free of correction or normalisation. This has enabled us to establish several properties experimentally. Firstly automatic selection of grey-world algorithms according to image properties is not nearly so effective as has been thought. Secondly, it is shown that Bayesian illuminant estimation is significantly improved by the improved accuracy of priors for illuminant and reflectance that are obtained from the new dataset.

Modern probabilistic modeling has revolutionized the design and implementation of machine vision systems. There are now numerous instances of systems that can see stereoscopically in depth, or separate foreground from background, or accurately excise objects of a particular class, all in real time. Each of those three vision functionalities will be demonstrated in the lecture. The underlying advances in system design and performance owe much to probabilistic frameworks for inference in images. In particular, the Markov Random Field (MRF), which first appeared in image processing in the 70s, has staged a resounding comeback in the last decade. The MRF is a mechanism, borrowed from statistical physics, for expressing prior properties of images, such as smoothness and spatial coherence. Despite its considerable generality, the MRF has proved nonetheless to be remarkably tractable when used in inference systems, as the lecture will explain.

Psychophysical studies [9], [17] show that we can recognize objects using fragments of outline contour alone. This paper proposes a new automatic visual recognition system based only on local contour features, capable of localizing objects in space and scale. The system first builds a class-specific codebook of local fragments of contour using a novel formulation of chamfer matching. These local fragments allow recognition that is robust to within-class variation, pose changes, and articulation. Boosting combines these fragments into a cascaded sliding-window classifier, and mean shift is used to select strong responses as a final set of detections. We show how learning can be performed iteratively on both training and test sets to boot-strap an improved classifier. We compare with other methods based on contour and local descriptors in our detailed evaluation over 17 challenging categories, and obtain highly competitive results. The results confirm that contour is indeed a powerful cue for multi-scale and multi-class visual object recognition.

I will describe models and algorithms for the real-time segmentation of foreground from background layers in stereo video sequences. Automatic separation of layers from color/contrast or from stereo alone is known to be error-prone. Here, color, contrast and stereo matching information are fused to infer layers accurately and efficiently. The stereo-match likelihood is then fused with a contrast-sensitive color model that is learned on the fly, and stereo disparities are obtained by dynamic programming. Our "layered graph cut" (LGC) algorithm, does not directly solve stereo. Instead the stereo match likelihood is marginalized over disparities to evaluate foreground and background hypotheses, and then fused with a contrast-sensitive color model. Segmentation is solved efficiently by graph cut optimization. In a recent development, this segmentation procedure has been used, in turn, to improve the efficiency of stereo matching, by exploiting Panum fusional bands that are well known to operate in human stereo vision.

We present a novel model based stereo system, which accurately extracts the 3D shape and pose of faces from multiple images taken simultaneously. Extracting the 3D shape from images is important in areas such as pose-invariant face recognition and image manipulation. The method is based on a 3D morphable face model learned from a database of facial scans. The use of a strong face prior allows us to extract high precision surfaces from stereo data of faces, where traditional correlation based stereo methods fail because of the mostly textureless input images. The method uses two or more uncalibrated images of arbitrary baseline, estimating calibration and shape simultaneously. Results using two and three input images are presented. We replace the lighting and albedo estimation of a monocular method with the use of stereo information, making the system more accurate and robust. We evaluate the method using ground truth data and the standard PIE image dataset. A comparison with the state of the art monocular system shows that the new method has a significantly higher accuracy.

Online camera recalibration is necessary for long-term deployment of computer vision systems. Existing algorithms assume that the source of recalibration information is a set of features in a general 3D scene; and that enough features are observed that the calibration problem is well-constrained. However; these assumptions are frequently invalid outside the laboratory. Real-world scenes often lack texture, contain repeated texture, or are mostly planar, making calibration difficult or impossible. In this paper we consider the calibration of families of stereo cameras, where each camera is assumed to have parameters drawn from a common but unknown prior distribution. We show how estimation of this prior using a small-number of offline-calibrated cameras (e.g. from the same production line) allows online calibration of additional cameras using a small number of point correspondences; and that using the estimated prior significantly increases the accuracy and robustness of stereo camera calibration.

Markov Random Fields (MRFs) are ubiquitous in low- level computer vision. In this paper, we propose a new approach to the optimization of multi-labeled MRFs. Similarly to a-expansion it is based on iterative application of binary graph cut. However, the number of binary graph cuts required to compute a labelling grows only logarithmically with the size of label space, instead of linearly. We demonstrate that for applications such as optical flow, image restoration, and high resolution stereo, this gives an order of magnitude speed-up, for comparable energies. Iterations are performed by "fusion" of solutions, done with QPBO which is related to graph cut but can deal with non-submodularity. At convergence, the method achieves optima on a par with the best competitors, and sometimes even exceeds them.

Stereo matching algorithms conventionally match over a range of disparities sufficient to encompass all visible 3D scene points. Human vision however does not do this. It works over a narrow band of disparities - Panum’s fusional band - whose typical range may be as little as 1/20 of the full range of disparities for visible points. Points inside the band are fused visually and the remainder of points are seen as "diplopic" - that is with double vision. The Panum band restriction is important also in machine vision, both with active (pan/tilt) cameras, and with high resolution cameras and digital pan/tilt.

This paper presents an algorithm capable of real-time separation of foreground from background in monocular video sequences. Automatic segmentation of layers from colour/contrast or from motion alone is known to be error-prone. Here motion, colour and contrast cues are probabilistically fused together with spatial and temporal priors to infer layers accurately and efficiently. Central to our algorithm is the fact that pixel velocities are not needed, thus removing the need for optical flow estimation, with its tendency to error and computational expense. Instead, an efficient motion vs nonmotion classifier is trained to operate directly and jointly on intensity-change and contrast. Its output is then fused with colour information. The prior on segmentation is represented by a second order, temporal, Hidden Markov Model, together with a spatial MRF favouring coherence except where contrast is high. Finally, accurate layer segmentation and explicit occlusion detection are efficiently achieved by binary graph cut. The segmentation accuracy of the proposed algorithm is quantitatively evaluated with respect to existing groundtruth data and found to be comparable to the accuracy of a state of the art stereo segmentation algorithm. Foreground/ background segmentation is demonstrated in the application of live background substitution and shown to generate convincingly good quality composite video.

We introduce the term cosegmentation which denotes the task of segmenting simultaneously the common parts of an image pair. A generative model for cosegmentation is presented. Inference in the model leads to minimizing an energy with an MRF term encoding spatial coherency and a global constraint which attempts to match the appearance histograms of the common parts. This energy has not been proposed previously and its optimization is challenging and NP-hard. For this problem a novel optimization scheme which we call trust region graph cuts is presented. We demonstrate that this framework has the potential to improve a wide range of research: Object driven image retrieval, video tracking and segmentation, and interactive image editing. The power of the framework lies in its generality, the common part can be a rigid/non-rigid object (or scene), observed from different viewpoints or even similar objects of the same class.

This paper is about mapping images to continuous output spaces using powerful Bayesian learning techniques. A sparse, semi-supervised Gaussian process regression model (S3GP) is introduced which learns a mapping using only partially labelled training data. We show that sparsity bestows efficiency on the S3GP which requires minimal CPU utilization for real-time operation; the predictions of uncertainty made by the S3GP are more accurate than those of other models leading to considerable performance improvements when combined with a probabilistic filter; and the ability to learn from semi-supervised data simplifies the process of collecting training data. The S3GP uses a mixture of different image features: this is also shown to improve the accuracy and consistency of the mapping. A major application of this work is its use as a gaze tracking system in which images of a human eye are mapped to screen coordinates: in this capacity our approach is efficient, accurate and versatile.

This paper describes models and algorithms for the real-time segmentation of foreground from background layers in stereo video sequences. Automatic separation of layers from color/contrast or from stereo alone is known to be error-prone. Here, color, contrast, and stereo matching information are fused to infer layers accurately and efficiently. The first algorithm, Layered Dynamic Programming (LDP), solves stereo in an extended six-state space that represents both foreground/background layers and occluded regions. The stereo-match likelihood is then fused with a contrast-sensitive color model that is learned on-the-fly and stereo disparities are obtained by dynamic programming. The second algorithm, Layered Graph Cut (LGC), does not directly solve stereo. Instead, the stereo match likelihood is marginalized over disparities to evaluate foreground and background hypotheses and then fused with a contrast-sensitive color model like the one used in LDP. Segmentation is solved efficiently by ternary graph cut. Both algorithms are evaluated with respect to ground truth data and found to have similar performance, substantially better than either stereo or color/ contrast alone. However, their characteristics with respect to computational efficiency are rather different. The algorithms are demonstrated in the application of background substitution and shown to give good quality composite video output.

The paper defines an automatic procedure for constructing a visually appealing collage from a collection of input images. The aim is that the resulting collage should be representative of the collection, summarising its main themes. It is also assembled largely seamlessly, using graph-cut, Poisson blending of alpha-masks, to hide the joins between input images. This paper makes several new contributions. Firstly, we show how energy terms can be included that: encourage the selection of a representative set of images; that are sensitive to particular object classes; that encourage a spatially efficient and seamless layout. Secondly the resulting optimization poses a search problem that, on the face of it, is computationally in-feasible. Rather than attempt an expensive, integrated optimization procedure, we have developed a sequence of optimization steps, from static ranking of images, through region of interest optimization, optimal packing by constraint satisfaction, and lastly graph-cut alpha-expansion. To illustrate the power of AutoCollage, we have used it to create collages of many home photo sets; we also conducted a user study in which AutoCollage outperformed competitive methods.

This paper describes two algorithms capable of real-time segmentation of foreground from background layers in stereo video sequences. Automatic separation of layers from colour/contrast or from stereo alone is known to be error-prone. Here, colour, contrast and stereo matching information are fused to infer layers accurately and efficiently. The first algorithm, layered dynamic programming (LDP), solves stereo in an extended 6-state space that represents both foreground/background layers and occluded regions. The stereo-match likelihood is then fused with a contrast-sensitive colour model that is learned on the fly, and stereo disparities are obtained by dynamic programming. The second algorithm, layered graph cut (LGC), does not directly solve stereo. Instead the stereo match likelihood is marginalised over foreground and background hypotheses, and fused with a contrast-sensitive colour model like the one used in LDP. Segmentation is solved efficiently by ternary graph cut. Both algorithms are evaluated with respect to ground truth data and found to have similar p performance, substantially better than stereo or colour/contrast alone. However, their characteristics with respect to computational efficiency are rather different. The algorithms are demonstrated in the application of background substitution and shown to give good quality composite video output.

This paper demonstrates the high quality, real-time segmentation techniques. We achieve real-time segmentation of foreground from background layers in stereo video sequences. Automatic separation of layers from colour/contrast or from stereo alone is known to be error-prone. Here, colour, contrast and stereo matching information are fused to infer layers accurately and efficiently. The first algorithm, layered dynamic programming (LDP), solves stereo in an extended 6-state space that represents both foreground/background layers and occluded regions. The stereo-match likelihood is then fused with a contrast-sensitive colour model that is learned on the fly, and stereo disparities are obtained by dynamic programming. The second algorithm, layered graph cut (LGC), does not directly solve stereo. Instead the stereo match likelihood is marginalised over foreground and background hypotheses, and fused with a contrast-sensitive colour model like the one used in LDP. Segmentation is solved efficiently by ternary graph cut. Both algorithms are evaluated with respect to ground truth data and found to have similar performance, substantially better than stereo or colour/contrast alone. However, their characteristics with respect to computational efficiency are rather different. The algorithms are demonstrated in the application of background substitution and shown to give good quality composite video output.

This paper addresses the novel problem of automatically synthesizing an output image from a large collection of different input images. The synthesized image, called a digital tapestry, can be viewed as a visual summary or a virtual 'thumbnail' of all the images in the input collection. The problem of creating the tapestry is cast as a multi-class labeling problem such that each region in the tapestry is constructed from input image blocks that are salient and such that neighboring blocks satisfy spatial compatibility. This is formulated using a Markov random field and optimized via the graph cut based expansion move algorithm. The standard expansion move algorithm can only handle energies with metric terms, while our energy contains non-metric (soft and hard) constraints. Therefore we propose two novel contributions. First, we extend the expansion move algorithm for energy functions with non-metric hard constraints. Secondly, we modify it for functions with "almost" metric soft terms, and show that it gives good results in practice. The proposed framework was tested on several consumer photograph collections, and the results are presented.

We present a novel categorical object detection scheme that uses only local contour-based features. A two-stage, partially supervised learning architecture is proposed: a rudimentary detector is learned from a very small set of segmented images and applied to a larger training set of un-segmented images; the second stage bootstraps these detections to learn an improved classifier while explicitly training against clutter. The detectors are learned with a boosting algorithm which creates a location-sensitive classifier using a discriminative set of features from a randomly chosen dictionary of contour fragments. We present results that are very competitive with other state-of-the-art object detection schemes and show robustness to object articulations, clutter, and occlusion. Our major contributions are the application of boosted local contour-based features for object detection in a partially supervised learning framework, and an efficient new boosting procedure for simultaneously selecting features and estimating per-feature parameters.

This paper extends the use of statistical learning algorithms for object localization. It has been shown that object recognizers using kernel-SVMs can be elegantly adapted to localization by means of spatial perturbation of the SVM. While this SVM applies to each frame of a video independently of other frames, the benefits of temporal fusion of data are well-known. This is addressed here by using a fully probabilistic Relevance Vector Machine (RVM) to generate observations with Gaussian distributions that can be fused over time. Rather than adapting a recognizer, we build a displacement expert which directly estimates displacement from the target region. An object detector is used in tandem, for object verification, providing the capability for automatic initialization and recovery. This approach is demonstrated in real-time tracking systems where the sparsity of the RVM means that only a fraction of CPU time is required to track at frame rate. An experimental evaluation compares this approach to the state of the art showing it to be a viable method for long-term region tracking.

There has been substantial progress in the past decade in the development of object classifiers for images, for example of faces, humans and vehi- cles. Here we address the problem of contaminations (e.g. occlusion, shadows) in test images which have not explicitly been encountered in training data. The Variational Ising Classifier (VIC) algorithm models contamination as a mask (a field of binary variables) with a strong spa- tial coherence prior. Variational inference is used to marginalize over contamination and obtain robust classification. In this way the VIC ap- proach can turn a kernel classifier for clean data into one that can tolerate contamination, without any specific training on contaminated positives. 1 Introduction Recent progress in discriminative object detection, especially for faces, has yielded good performance and efficiency [1, 2, 3, 4]. Such systems are capable of classifying those positives that can be generalized from positive training data. This is restrictive in practice in that test data may contain distortions that take it outside the strict ambit of the training positives. One example would be lighting changes (to a face) but this can be addressed reasonably effectively by a normalizing transformation applied to training and test images; doing so is common practice in face classification. Other sorts of disruption are not so easily factored out. A prime example is partial occlusion. The aim of this paper is to extend a classifier trained on clean positives to accept also partially occluded positives, without further training. The approach is to capture some of the regularity inherent in a typical pattern of contamination, namely its spatial coherence. This can be thought of as extending the generalizing capability of a classifier to tolerate the sorts of image distortion that occur as a result of contamination. As done previously in one-dimension, for image contours [5], the Variational Ising Classi- fier (VIC) models contamination explicitly as switches with a strong coherence prior in the form of an Ising model, but here over the full two-dimensional image array. In addition, the Ising model is loaded with a bias towards non-contamination. The aim is to incorporate these hidden contamination variables into a kernel classifier such as [1, 3]. In fact the Rel- evance Vector Machine (RVM) is particularly suitable [6] as it is explicitly probabilistic, so that contamination variables can be incorporated as a hidden layer of random variables. edge neighbours of i i Figure 1: The 2D Ising model is applied over a graph with edges e between neigh- bouring pixels (connected 4-wise). Classification is done by marginalization over all possible configurations of the hidden vari- able array, and this is made tractable by variational (mean field) inference. The inference scheme makes use of "hallucination" to fill in parts of the object that are unobserved due to occlusion. Results of VIC are given for face detection. First we show that the classifier performance is not significantly damaged by the inclusion of contamination variables. Then a contam- inated test set is generated using real test images and computer generated contaminations. Over this test data the VIC algorithm does indeed perform significantly better than a con- ventional classifier (similar to [4]). The hidden variable layer is shown to operate effec- tively, successfully inferring areas of contamination. Finally, inference of contamination is shown working on real images with real contaminations. 2 Bayesian modelling of contamination Classification requires P (F |I), the posterior for the proposition F that an object is present given the image data intensity array I. This can be computed in terms of likelihoods P (F | I) = P (I | F )P (F )/ P (I | F )P (F ) + P (I | F )P (F ) (1) so then the test P (F | I) > 1 becomes 2 log P (I | F ) - log P (I | F ) > t (2) where t is a prior-dependent threshold that controls the tradeoff between positive and neg- ative classification errors. Suppose we are given a likelihood P (I|, F ) for the presence of a face given contamination , an array of binary "observation" variables corresponding to each pixel Ij of I, such that j = 0 indicates contamination at that pixel, whereas j = 1 indicates a successfully observed pixel. Then, in principle, P (I|F ) = P (I|, F )P (), (3) (making the reasonable assumption P (|F ) = P (), that the pattern of contamination is object independent) and similarly for log P (I | F ). The marginalization itself is intractable, requiring a summation over all 2N possible configurations of , for images with N pixels. Approximating that marginalization is dealt with in the next section. In the meantime, there are two other problems to deal with: specifying the prior P (); and specifying the likeli- hood under contamination P (I|, F ) given only training data for the unoccluded object. 2.1 Prior over contaminations The prior contains two terms: the first expresses the belief that contamination will occur in coherent regions of a subimage. This takes the form of an Ising model [7] with energy UI() that penalizes adjacent pixels which differ in their labelling (see Figure 1); the second term UC biases generally against contamination a priori and its balance with the first term is mediated by the constant . The total prior energy is then U () = UI() + UC() = [1 - (e - )] + ( 1 e2 j ), (4) e j where (x) = 1 if x = 0 and 0 otherwise, and e1, e2 are the indices of the pixels at either end of edge e (figure 1). The prior energy determines a probability via a temperature constant 1/T0 [7]: P () e-U()/T0 = e-UI()/T0e-UC()/T0 (5) 2.2 Relevance vector machine An unoccluded classifier P (F |I, = 0) can be learned from training data using a Rele- vance Vector Machine (RVM) [6], trained on a database of frontal face and non-face im- ages [8] (see Section 4 for details). The probabilistic properties of the RVM make it a good choice when (later) it comes to marginalising over . For now we consider how to construct the likelihood itself. First the conventional, unoccluded case is considered for which the posterior P (F |I) is learned from positive and negative examples. Kernel functions [9] are computed between a candidate image I and a subset of relevance vectors {xk}, retained from the training set. Gaussian kernels are used here to compute y(I) = wk exp - (Ij - xkj)2 . (6) k j where wk are learned weights, and xkj is the jth pixel of the kth relevance vector. Then the posterior is computed via the logistic sigmoid function as 1 P (F |I, = 1) = (y(I)) = . (7) 1 + e-y(I) and finally the unoccluded data-likelihood would be P (I|F, = 1) (y(I))/P (F ). (8) 2.3 Hallucinating appearance The aim now is to derive the occluded likelihood from the unoccluded case, where the con- tamination mask is known, without any further training. To do this, (8) must be extended to give P (I|F, ) for arbitrary masks , despite the fact the pixels Ij from the object are not observed wherever j = 0. In principle one should take into account all possible (or at least probable) values for the occluded pixels. Here, for simplicity, a single fixed hallu- cination is substituted for occluded pixels, then we proceed as if those values had actually been observed. This gives P (I|F, ) (~ y(I, ))/P (F ) (9)

We present an extension to the Jojic and Frey (2001) layered sprite model which allows for layers to undergo affine transformations. This extension allows for affine object pose to be inferred whilst simultaneously learn- ing the object shape and appearance. Learning is carried out by applying an augmented variational inference algorithm which includes a global search over a discretised transform space followed by a local optimisa- tion. To aid correct convergence, we use bottom-up cues to restrict the space of possible affine transformations. We present results on a number of video sequences and show how the model can be extended to track an object whose appearance changes throughout the sequence.

The effectiveness of probabilistic tracking of objects in image sequences has been revolutionized by the development of particle filtering. Whereas Kalman filters are restricted to Gaussian distributions, particle filters can propagate more general distributions, albeit only approximately. This is of particular benefit in visual tracking because of the inherent ambiguity of the visual world that stems from its richness and complexity. One important advantage of the particle filtering framework is that it allows the information from different measurement sources to be fused in a principled manner. Although this fact has been acknowledged before, it has not been fully exploited within a visual tracking context. Here we introduce generic importance sampling mechanisms for data fusion and discuss them for fusing color with either stereo sound, for teleconferencing, or with motion, for surveillance with a still camera. We show how each of the three cues can be modeled by an appropriate data likelihood function, and how the intermittent cues (sound or motion) are best handled by generating proposal distributions from their likelihood functions. Finally, the effective fusion of the cues by particle filtering is demonstrated on real teleconference and surveillance data.

The problem of efficient, interactive foreground/background segmentation in still images is of great practical importance in image editing. Classical image segmentation tools use either texture (colour) information, e.g. Magic Wand, or edge (contrast) information, e.g. Intelligent Scissors. Recently, an approach based on optimization by graph-cut has been developed which successfully combines both types of information. In this paper we extend the graph-cut approach in three respects. First, we have developed a more powerful, iterative version of the optimisation. Secondly, the power of the iterative algorithm is used to simplify substantially the user interaction needed for a given quality of result. Thirdly, a robust algorithm for "border matting" has been developed to estimate simultaneously the alpha-matte around an object boundary and the colours of foreground pixels. We show that for moderately difficult examples the proposed method outperforms competitive tools.

A new algorithm is proposed for novel view generation in one-to-one teleconferencing applications. Given the video streams acquired by two cameras placed on either side of a computer monitor, the proposed algorithm synthesizes images from a virtual camera in arbitrary position (typically located within the monitor) to facilitate eye contact. Our technique is based on an improved, dynamic-programming, stereo algorithm for efficient novel-view generation. The two main contributions are: i) a new type of three-plane graph for dense-stereo dynamic-programming, that encourages correct occlusion labeling; ii) a compact geometric derivation for novel-view synthesis by direct projection of the minimum-cost surface. Furthermore, we present a novel algorithm for the temporal maintenance of a background model to enhance the rendering of occlusions and reduce temporal artefacts (flicker); and a cost aggregation algorithm that acts directly on our three-dimensional matching cost space. Examples are given that demonstrate the robustness of the new algorithm to spatial and temporal artefacts for long stereo video streams. These include demonstrations of synthesis of cyclopean views of extended conversational sequences. We further demonstrate synthesis from a freely translating virtual camera.

We address the problem of applying powerful pattern recognition algorithms based on kernels to efficient visual tracking. Recently S. Avidan, (2001) has shown that object recognizers using kernel-SVMs can be elegantly adapted to localization by means of spatial perturbation of the SVM, using optic flow. Whereas Avidan's SVM applies to each frame of a video independently of other frames, the benefits of temporal fusion of data are well known. Using a fully probabilistic 'relevance vector machine' (RVM) to generate observations with Gaussian distributions that can be fused over time is addressed. To improve performance further, rather than adapting a recognizer, we build a localizer directly using the regression form of the RVM. A classification SVM is used in tandem, for object verification, and this provides the capability of automatic initialization and recovery. The approach is demonstrated in real-time face and vehicle tracking systems. The 'sparsity' of the RVMs means that only a fraction of CPU time is required to track at frame rate. Tracker output is demonstrated in a camera management task in which zoom and pan are controlled in response to speaker/vehicle position and orientation, over an extended period. The advantages of temporal fusion in this system are demonstrated.

Using generic interpolation machinery based on solving Poisson equations, a variety of novel tools are introduced for seamless editing of image regions. The first set of tools permits the seamless importation of both opaque and transparent source image regions into a destination region. The second set is based on similar mathematical ideas and allows the user to modify the appearance of the image seamlessly, within a selected region. These changes can be arranged to affect the texture, the illumination, and the color of objects lying in the region, or to make tileable a rectangular selection.

This paper presents a strategy for rapid summarisation and browsing of video sequences. The input video is first transformed into a sequence of representative feature vectors. Using this representation a utility function is designed that assigns high reward to subsequences of keyframes that are maximally distinct and individually carry the most information. For a specified level of detail and endpoints the keyframe sequence that maximises this utility function can be obtained by a non-iterative Dynamic Programming procedure, thus allowing the user to efficiently zoom in on any part or all of the video sequence. For the sake of compactness and clarity the working of the algorithm is illustrated on a television commercial. 1

This paper proposes a novel framework to construct a geometric and photometric model of a viewed object that can be used for visualisation in arbitrary pose and illumination. The method is solely based on images and does not require any specialised equipment. We assume that the object has a piece-wise smooth surface and that its reflectance can be modelled using a parametric bidirectional reflectance distribution function. Without assuming any prior knowledge on the object, geometry and reflectance have to be estimated simultaneously and occlusion and shadows have to be treated consistently. We exploit the geometric and photometric consistency using the fact that surface orientation and reflectance are local invariants. In a first implementation, we demonstrate the method using a Lambertian object placed on a turn-table and illuminated by a number of unknown point light-sources. A discrete voxel model is initialised to the visual hull and voxels identified as inconsistent with the invariants are removed iteratively. The resulting model is used to render images in novel pose and illumination.

Shadows of moving objects often obstruct robust visual tracking. We propose an HMM-based segmentation method which classifies in real time each pixel or region into three categories: shadows, foreground, and background objects. In the case of traffic monitoring movies, the effectiveness of the proposed method has been proven through experimental results.

This paper addresses the problem of speaker tracking in a noisy and reverberant environment using time delay of arrival (TDOA) measurements at spatially distributed microphone pairs. The tracking problem is posed within a state-space estimation framework, and models are developed for the speaker motion and the likelihood of the speaker location in the light of the TDOA measurements. The resulting state-space model is nonlinear and nonGaussian, and consequently no closed-form solutions exist for the filtering distributions required to perform tracking. Here sequential Monte Carlo (SMC) methods are applied to approximate the true filtering distribution with a set of samples. The resulting tracking algorithm requires no triangulation, is computationally efficient, and can straightforwardly be extended to track multiple speakers.

The problem of extracting continuous structures from noisy or cluttered images is a difficult one. Successful extraction depends critically on the ability to balance prior constraints on continuity and smoothness against evidence garnered from image analysis. Exact, deterministic optimisation algorithms, based on discretized functionals, suffer from severe limitations on the form of prior constraint that can be imposed tractably. This paper proposes a sequential Monte-Carlo technique, termed JetStream, that enables constraints on curvature, corners, and contour parallelism. To be mobilized, all of which are infeasible under exact optimization. The power of JetStream is demonstrated in two contexts: (1) interactive cut-out in photo-editing applications, and (2) the recovery of roads in aerial photographs.

This paper describes an algorithm for finding faces within an image. The basis of the algorithm is to run an observation window at all possible positions, scales and orientation within the image. A non-linear support vector machine is used to determine whether or not a face is contained within the observation window. The non-linear support vector machine operates by comparing the input patch to a set of support vectors (which can be thought of as face and anti-face templates). Each support vector is scored by some nonlinear function against the observation window and if the resulting sum is over some threshold a face is indicated. Because of the huge search space that is considered, it is imperative to investigate ways to speed up the support vector machine. Within this paper we suggest a method of speeding up the non-linear support vector machine. A set of reduced set vectors (RVs) are calculated from the support vectors. By considering the RV's sequentially, and if at any point a face is deemed too unlikely to cease the sequential evaluation, obviating the need to evaluate the remaining RVs. The idea being that we only need to apply a subset of the RVs to eliminate things that are obviously not a face (thus reducing the computation). The key then is to explore the RVs in the right order and a method for this is proposed.

A new exemplar-based, probabilistic paradigm for visual tracking is presented. Probabilistic mechanisms are attractive because they handle fusion of information, especially temporal fusion, in a principled manner. Exemplars are selected representatives of raw training data, used here to represent probabilistic mixture distributions of object configurations. Their use avoids tedious hand-construction of object models and problems with changes of topology. Using exemplars in place of a parameterized model poses several challenges, addressed here with what we call the "Metric Mixture" (M/sup 2/) approach. The M/sup 2/ model has several valuable properties. Principally, it provides alternatives to standard learning algorithms by allowing the use of metrics that are not embedded in a vector space. Secondly, it uses a noise model that is learned from training data. Lastly, it eliminates any need for an assumption of probabilistic pixelwise independence. Experiments demonstrate the effectiveness of the M/sup 2/ model in two domains tracking walking people using chamfer distances on binary edge images and tracking mouth movements by means of a shuffle distance.

The main challenge in articulated body motion tracking is the large number of degrees of freedom (around 30) to be recovered. Search algorithms, either deterministic or stochastic, that search such a space without constraint, fall foul of exponential computational complexity. One approach is to introduce constraints: either labelling using markers or colour coding, prior assumptions about motion trajectories or view restrictions. Another is to relax constraints arising from articulation, and track limbs as if their motions were independent. In contrast, we aim for general tracking without special preparation of objects or restrictive assumptions. The principal contribution of the paper is the development of a modified particle filter for search in high dimensional configuration spaces. It uses a continuation principle based on annealing to introduce the influence of narrow peaks in the fitness function, gradually. The new algorithm, termed annealed particle filtering, is shown to be capable of recovering full articulated body motion efficiently.

Standard, exact techniques based on likelihood maximization are available for learning auto-regressive process models of dynamical processes. The uncertainty of observations obtained from real sensors means that dynamics can be observed only approximately. Learning can still be achieved via "EM-K"-expectation-maximization (EM) based on Kalman filtering. This cannot handle more complex dynamics, however, involving multiple classes of motion. A problem arises also in the case of dynamical processes observed visually: background clutter arising for example, in camouflage, produces non-Gaussian observation noise. Even with a single dynamical class, non-Gaussian observations put the learning problem beyond the scope of EM-K. For those cases, we show here how "EM-C"-based on the CONDENSATION algorithm which propagates random "particle-sets," can solve the learning problem. Here, learning in clutter is studied experimentally using visual observations of a hand moving over a desktop. The resulting learned dynamical model is shown to have considerable predictive value: when used as a prior for estimation of motion, the burden of computation in visual observation is significantly reduced. Multiclass dynamics are studied via visually observed juggling; plausible dynamical models have been found to emerge from the learning process, and accurate classification of motion has resulted. In practice, EM-C learning is computationally burdensome and the paper concludes with some discussion of computational complexity.

Some issues in markerless tracking of human body motion are addressed. Extended Kalman filters have commonly been applied to kinematic variables, to combine predictions consistent with plausible motion, with the incoming stream of visual measurements. Kalman filtering is applicable only when the underlying distribution is approximately Gaussian. Often this assumption proves remarkably robust. There are two pervasive circumstances under which the Gaussianity assumption can break down. The first is kinematic singularity and the second is at joint endstops. Failure of Kalman filtering under these circumstances is illustrated. The non-Gaussian nature of the distributions is demonstrated experimentally by means of Monte Carlo simulation. Random simulation (particle filtering or Condensation) proves to provide a robust alternative algorithm for tracking that can also deal with these difficult conditions.

Tracking multiple targets whose models are indistinguishable is a challenging problem. Simply instantiating several independent I-body trackers is not an adequate solution, because the independent trackers can coalesce onto the best-fitting target. This paper presents an observation density for tracking which solves this problem by exhibiting a probabilistic exclusion principle. Exclusion arises naturally from a systematic derivation of the observation density, without relying on heuristics. Another important contribution of the paper is the presentation of partitioned sampling, a new sampling method for multiple object tracking. Partitioned sampling avoids the high computational load associated with fully coupled trackers, while retaining the desirable properties of coupling.

The classification of human body motion is a difficult problem. In particular, the automatic segmentation of image sequences containing more than one class of motion is challenging. An effective approach is to use mixed discrete/continuous states to couple perception with classification. A spline contour is used to track the outline of the person. We show that, for a quasi-periodic human body motion, an autoregressive process is a suitable model for the contour dynamics. This can then be used as a dynamical model for mixed-state "condensation" filtering, switching automatically between different motion classes. We have developed "partial importance sampling" to enhance the efficiency of the mixed-state condensation filter. It is also shown that the importance sampling can be done in linear time, instead of the previous quadratic algorithm. "Tying" of discrete states is used to obtain further efficiency improvements. Automatic segmentation is demonstrated on video sequences of aerobic exercises. The performance is promising, but there remains a residual misclassification rate, and possible explanations for this are discussed.

Maximisation of cross correlation is a commonly used principle for intensity based object localization that gives a single estimate of location. However, to facilitate sequential inference (e.g. over time or scale) and to allow the representation of ambiguity, it is desirable to represent an entire probability distribution for object location. Although the cross correlation itself (or some function of it) has sometimes been treated as a probability distribution, this is not generally justifiable. Bayesian correlation achieves a consistent probabilistic treatment by combining several developments. The first is the interpretation of correlation matching functions in probabilistic terms, as observation likelihoods. Second, probability distributions of filter bank responses are learned from training examples. Inescapably, response learning also demands statistical modelling of background intensities, and there are links here with image coding and Independent Component Analysis. Lastly, multi scale processing is achieved in a Bayesian context by means of a new algorithm, layered sampling, for which asymptotic properties are derived.

We explore the application of facial tracking to automated re-animation. To this end, it is necessary to recover both head-pose and facial expression from the facial movement of a performer. However, both effects are coupled. This is a serious problem, which previous studies haven't fully considered. The solution to this interaction problem proposed here is to solve explicitly, at each timestep, for pose and expression variables. In principle this is a nonlinear inverse problem. However, appropriate parameterisation of pose in terms of affine transformations with parallax, and of expression in terms of key-frames, reduces the problem to a bilinear one. This can then be solved directly by Singular Value Decomposition. Thus actor-driven animation has ben implemented in real-time, at video field-rate, using two Indy desktop workstations.

This paper describes an efficient method to calculate, from an image of an object, configurations of a two-fingered robot gripper that form a "cage" to contain that object. Closing the fingers on the object from these configurations is guaranteed to reach a given desired grasp. This builds on the visual grasping theory of A. Blake et al. (1993), which describes how to find optimal grasps. It extends the results of E. Rimon and A. Blake (1996) which show how to construct such cages, in two ways. First, a more efficient algorithm for computing the cage is described. Second, a further development deals with occlusion by solving the caging problem within a restricted image window. The new methods greatly reduce the complexity of the visual caging problem, making it feasible in a real time computer vision system.

There is considerable interest in the computer vision community in representing and modelling motion. Motion models are used as predictors to increase the robustness and accuracy of visual trackers, and as classifiers for gesture recognition. This paper presents a significant development of random sampling methods to allow automatic switching between multiple motion models as a natural extension of the tracking process. The Bayesian mixed-state framework is described in its generality, and the example of a bouncing ball is used to demonstrate that a mixed-state model can significantly improve tracking performance in heavy clutter. The relevance of the approach to the problem of gesture recognition is then investigated using a tracker which is able to follow the natural drawing action of a hand holding a pen, and switches state according to the hand's motion.

Human speech is inherently multi-modal, consisting of both audio and visual components. Recently researchers have shown that the incorporation of information about the position of the lips into acoustic speech recognisers enables robust recognition of noisy speech. In the case of Hidden Markov Model-recognition, we show that this happens because the visual signal stabilises the alignment of states. It is also shown, that unadorned lips, both the inner and outer contours, can be robustly tracked in real time on general-purpose workstations. To accomplish this, efficient algorithms are employed which contain three key components: shape models, motion models, and focused colour feature detectors-all of which are learnt from examples.

A method of localising objects in images is proposed. Possible configurations are evaluated using the contour discriminant, a likelihood ratio which is derived from a probabilistic model of the feature detection process. We treat each step in this process probabilistically, including the occurrence of clutter features, and derive the observation densities for both correct "target" configurations and incorrect "clutter" configurations. The contour discriminant distinguishes target objects from the background even in heavy clutter, making only the most general assumptions about the form that clutter might take. The method generates samples stochastically to avoid the cost of processing an entire image, and promises to be particularly suited to the task of initialising contour trackers based on sampling methods.

Tracking with deformable contours in a filtering framework requires a dynamical model for prediction. For any given application, tracking is improved by having an accurate model, learned from training data. We develop a method for learning dynamical models from training sequences, explicitly taking account of the fact that training data are noisy measurements and not true states. By introducing an 'augmented-state smoothing filter' we show how the technique of Expectation-Maximisation can be applied to this problem, and show that the resulting algorithm produces more robust and accurate tracking.

This paper extends the caging theory of Rimon and Blake (1996) for one-parameter two-finger grippers to one-parameter three-finger grippers. The caging theory describes how the fingers of a robot gripper can be placed around an object so that it cannot escape. As the fingers close from such a configuration, the freedom of the object to move is gradually restricted, until, in the absence of friction, it is completely immobilized by the fingers at an immobilizing grasp. The extension of the caging theory to three-fingered grippers is important because convex objects cannot be caged by two-finger grippers. The computation of the set of caging formations requires the identification of both the two- and three-finger frictionless grasps. These grasps correspond to critical points of the opening parameter in the gripper's configuration space. There are two main problems here. Firstly, a method is needed to compute the critical points of the opening parameter in the three-finger contact space. This is complicated by the fact that this space may have more that one connected component. The second problem is how to associate the immobilizing grasps with punctures. In this paper we solve both these problems, presenting efficient algorithmic solutions.

This paper is concerned with the following caging problem. One wishes to surround an object B by a multi-fingered hand such that B has some freedom to move but still cannot escape the "cage" formed by the fingers. The authors introduce a new notion of caging set, which is based on the configuration-space representation of the free motions of the hand-system with respect to B. Using stratified Morse theory, the authors show that the hand's configuration at which the cage is broken corresponds to a frictionless equilibrium grasp. This allows the authors to formulate a technique for computing the caging set of a 2-fingered hand whose opening is controlled by a single parameter. The technique generalizes to 1-parameter gripping systems having higher number of fingers.

A method of robust feature-detection is proposed for visual tracking with a pan-tilt head. Even with good foreground models, the tracking process is liable to be disrupted by strong features in the background. Previous researchers have shown that the disruption can be somewhat suppressed by the use of image-subtraction. Building on this idea, a more powerful statistical model of background intensity is proposed in which a Gaussian mixture distribution is fitted to each of the pixels on a "virtual" image plane. A fitting algorithm of the "Expectation-Maximisation" type proves to be particularly effective here. Practical tests with contour tracking show marked improvement over image subtraction methods. Since the burden of computation is off-line, the online tracking process can run in real-time, at video field-rate. 1

Methods developed in the Computer Vision community for tracking moving shapes are showing great potential for applications in real-time graphics. Tracking techniques allow graphical entities such as curves to be superimposed on a video data-stream, marking out certain objects and following their motions. The techniques have been demonstrated on a variety of moving objects including human hands, heads, lips both from the side and the front, various vehicles, cabbages viewed from a moving tractor and even a pig in its pen. The output from such trackers can be taken in the form of motion signals which could then be used to drive a remote animation.>

We suggest an approach to describing and tracking the deformation of facial features. We concentrate on the mouth since its shape is important in detecting emotion. However, we believe that our system could be extended to deal with other facial features. In our system, the mouth is described by a valley contour which is based between the lips. This contour is shown to exist independently of illumination, viewpoint, identity, and expression. We present a real time mouth tracking system that follows this valley. It is shown to be robust to changes in identity, illumination and viewpoint. A simple classification algorithm was found to be sufficient to discriminate between 5 different mouth shapes, with a 100% recognition rate.>

Autonomous vehicles could benefit greatly from visual-motion sensors of sufficiently low cost that 10 or 20 of them could be distributed around the vehicle's periphery. A design is outlined here that builds on well-known schemes using gratings. The grating principle is illustrated by the fact that a man with a torch, walking at night behind a railing, seems to flash. The frequency of flashing is proportional to his velocity. A major drawback is that backward and forward motion are not distinguished. The key development here is the use of commutation as a means of modulating the grating output signal. This is equivalent, in the illustration above, to simulating stroboscopic motion of the railing. Thus, when the man is stationary, there is flashing at a resting frequency. When he moves one way the frequency increases, and for motion the opposite way, frequency decreases. Results from an analogue implementation of the visual motion transducer are presented. The current transducer measures translational motion across the grating. The design is also shown to be capable of extension to direct measurement of the divergence and curl of the flow field.>

At Oxford University much research has recently been focused on active vision, and in particular dynamic contours. These deformable model curves are able to track objects in an image using dynamic models of the behaviour of the target which can be learnt over time. It seems natural to extend these methodologies to investigate the problem of measuring surfaces (rather than contours) undergoing motion. The range sensor developed by the authors allows them to measure moving scenes, by requiring just a single image to measure depth unambiguously even in the presence of occlusion. By acquiring range data at frame rates from the sensor, they can develop real time 3D surface trackers. Their work looks at several key areas of dynamic model based tracking. The aim is to apply this to the tracking of a flexing hand. Already the surface contour is capable of tracking continuous surfaces in real time, such as a piece of paper as it flexes.< >

This paper addresses the problem of planning two fingered grasps of unmodelled 3D objects using visual information. A family of simultaneous, interacting contour trackers is used to pick the top object off a pile, viewed from a camera on the end of a robot arm. Then a closed contour localises the silhouette of the chosen object. Geometric information is obtained from the analysis of image motion as the robot executes deliberate world motions around its vantage point. This is used to guide the selection of new vantage points in search of a view that contains a more favourable grasp on the new rim (the surface curve that projects to the silhouette). In this way, costly global reconstruction of object surfaces is avoided and planning is coupled with sensing in an efficient manner.>

Recent developments in video-tracking allow the outlines of moving, natural objects in a video-camera input stream to be tracked live, at full video-rate. Previous systems have been available to do this for specially illuminated objects or for naturally illuminated but polyhedral objects. Other systems have been able to track nonpolyhedral objects in motion, in some cases from live video, but following only centroids or key-points rather than tracking whole curves. The system described here can track accurately the curved silhouettes of moving non-polyhedral objects at frame-rate, for example hands, lips, legs, vehicles, fruit, and without any special hardware beyond a desktop workstation and a video-camera and framestore.

Traffic statistics desired by road engineers and planners, and "traffic warning" systems demand real-time performance which precludes the use of batch processing. We apply recent real-time trading techniques along with scene specific tuning of the dynamics to enable the tracker to accurately predict target location and thus reduce the amount of search and/or image processing required. The benefits of learning dynamics for accurate prediction are speed-our tracker operates at frame rate-and smoothing of vibration. Initial calibration of the projective relationship between the image and ground planes enables metric information to be derived from the image positions and velocities without full camera calibration. Results are presented on real-world traffic scenes showing the tracker to be both fast and robust to vibrations which are inevitable in traffic locations.>

This paper presents an algorithm for transforming closed planar curves into a canonical form, independent of the viewpoint from which the original image of the contour was taken. The transformation that takes the contour to its canonical form is a member of the projective group PGL(2), chosen because PGL(2) contains all possible transformations of a plane curve under central projection onto another plane. The scheme relies on solving computationally an "isoperimetric" problem in which a transformation is sought which maximises the area of a curve given unit perimeter. In the case that the transformation is restricted to the affine subgroup there is a unique extremising transformation for any piecewise smooth closed curve. Uniqueness holds, almost always, even for curves that are not closed. In the full projective case, isoperimetric normalization is well-defined only for closed curves. We have found computational counterexamples for which there is more than one extremal transformation. Numerical algorithms are described and demonstrated both for the affine and the projective cases. Once a canonical curve is obtained, its isoperimetric area can be regarded as an invariant descriptor of shape.>

A framework for visual tracking of contours is presented, based on a synthesis of elastic models, stochastic filtering, and geometric invariance. Flexibly coupled curve templates implement soft prior assumptions about shape. Affine invariance, built into the flexible coupling, ensures that the affine deformations that arise naturally from image projection are favored. The stochastic basis of the framework is shown to result naturally in an automatic mechanism for the control of spatiotemporal scale.>

A design that builds on well-known schemes using gratings is outlined. The key development here is the use of commutation as a means of modulating the grating output signal. This enables backwards and forwards motion to be distinguished. Results from an analog implementation of the visual motion transducer are presented. The current transducer measures translational motion across the grating. The design is also shown to be capable of extension to direct measurement of the divergence and curl of the flow field.>

The authors discuss establishing a relationship between symmetry and two-fingered grasping of planar contours. Visual representations are chosen to meet the requirements of specified tasks such as object recognition or stereoscopic matching. When vision is regarded as a haptic sense, a new operational description is called for in support of dextrous manipulation. In the context of two-fingered grasp, an appropriate description can be constructed in terms of local reflectional and rotational symmetry. Related to symmetry-based representatons that have been used in pattern and object recognition, its structure is determined not heuristically, but precisely, by the nature of the grasping task. Its value is demonstrated by its incorporation into the control of a robot that can manipulate objects under visual guidance.>

A family of qualitative methods is described that determines structure of curves in a scene from their image projections in two or more views. For example, plane curves are distinguished from space curves, and space curves from contour generators. The novelty of the approach is that first, it is unaffected by camera intrinsic parameters, so calibration is not required; second, it is also unaffected by camera motion, so viewer motion need not be known; and third, curves need not be matched point by point. Qualitative scene descriptions can be determined using relative measurements, and affine or projective properties alone. The practical power of this family of methods is demonstrated using a real-time vision system based on B-spline snake-tracking.>

Trinocular active devices have the advantage of freedom from mechanical scanning and rapid image capture compared with more conventional active designs based on scanning laser stripes. Their efficient operation relies, however, on a good solution to the correspondence problem. This requires careful geometric design to take account of epipolar geometry and thorough modeling of image-measurement error. A design that, involves setting up the projector-camera geometry to be degenerate-so that depth computation is ill-conditioned-and then backing off a little is presented. This is called near-degenerate epipolar alignment. The result is that unambiguous stereo matching can, in principle, be guaranteed within a given working volume. This is in marked contrast with passive stereo in which ambiguity cannot be guaranteed, merely minimized statistically. The principles have proved to work well in laboratory tests, achieving unambiguous operation over a working volume of a 50-mm cube with a depth resolution of around 0.2 mm.>

A robot vehicle moving under visual guidance needs to compute approximate geometry of obstacles in its environment. It is unreasonable to assume that egomotion is known to the sort of precision that is available for a camera mounted on a high quality robot arm. Generally a nominal estimate for egomotion is available. One possibility is to refine this estimate using optic flow data (Harris, 1987). Alternatively, the problem can be turned on its head: what geometric information remains stable under perturbation of assumed egomotion? This question has been addressed by Koenderink and van Doom (1977), Nelson and Aloimonos (1988) and Verri et al. (1989), in the case of continuous motion fields and, in the domain of stereoscopic vision, by Weinshall (1990). Part of the answer, we claim, lies in the use of motion parallax as a geometric cue. Motion parallax, which is a relative measure of the positions of two points, can be very much more robust as a cue than the absolute position of a single point. This is true for computation of relative depth, curvature on specular surfaces and curvature on extremal boundaries.

of these for certain types of scene, so we hope to be able to label lines and nodes successfully without any type of coding. We investigate recent ideas in the design of irinocular active range-sensors. Such devices have the advantage of freedom from mechanical scanning, and rapid image capture. The main technical problem is overcoming the correspondence problem. This requires careful geometric design to take account of epipolar geometry and thorough modelling of image-measurement error. We present a novel design that, so far, seems to work well. Curiously it involves setting up the projectorcamera geometry to be degenerate — so that depth computation is ill-conditioned — and then backing off a little.

This paper aims to develop a simple algorithm for determining the direction of ego-motion of a monocular observer in a static environment. Rather than returning a single direction the algorithm returns a set of motion directions known to contain the true direct tion. Translational motion can be arbitrary. The algorithm is based on one invented by Horn and Weldon [1]. It uses only normal components of optical flow at discrete image locations and is only intended to function when the the contribution of rotation to the apparent motion is small. The algorithm uses the fact that imaged points must be at some positive distance from the viewer. No implicit assumptions are made about the scene being viewed. The algorithm is illustrated on an artificially generated set of normal components.

The authors develop previous theories of the analysis of deformation of apparent contours under viewer motion. Earlier results showing how surface curvature can be inferred from acceleration of image features are generalized for arbitrary viewer motion and perspective projection. It is shown that relative image acceleration, based on parallax measurements, is robust to uncertainties in robot motion. The theory has been implemented and extensively tested in a real-time (15 frames per second) tracking system based on deformable contours (snakes). It is shown that focusing attention by means of snakes allows rapid, robust computation of surface curvature, including discrimination of extremal and occluding contours.>

The authors show how a maximum likelihood estimator can be constructed for homogeneous texture. The estimator turns out to be strikingly simple. It simply enforces, iteratively, coincidence of the centroid of the observed elements with the centroid of the imaging window. Whereas the estimator is based on first moments, error bounds are obtained, the authors show, from second moments. Experiments indicate that, for real textures, orientation estimates fall well inside predicted bounds.>

Piecewise continuous reconstruction of real-valued data can be formulated in terms of nonconvex optimization problems. Both stochastic and deterministic algorithms have been devised to solve them. The simplest such reconstruction process is the weak string. Exact solutions can be obtained for it and are used to determine the success or failure of the algorithms under precisely controlled conditions. It is concluded that the deterministic algorithm (graduated nonconvexity) outstrips stochastic (simulated annealing) algorithms both in computational efficiency and in problem-solving power.>

Specularities-briglit image regions formed by specular reflectioir-are likely to be mistalien for genuine surface ma,rking.j by processes that perform photometric analysis, derive motion fields from optical flow or estimate depth from binocular stereo. In addit8iori they can be uscd to infer surface geometry. This paper describes a scheme for detecting specularities based 011 a cliaracterisatioil of Larnbertian surfaces. Real surfaces are not simple composites of Lambertiaii and specular sur- faces hut evidence suggests that away from specrilnrities they do not deviate from the Lainbertian model by more than a factor of 3 or so. This proves adequate to serve as a constraint for specularity detection. Two independent tests identify iinage regions where tlie constraint is violated. Tlie detector is shown to performs well on a varicty of real images. Applications: improving binocular stereo and inferring surface geometry are described using specularities produced by the detector. ACI(NOWLEI)GEI\IENTS: Work done at:L)ept. Conip. Sci, TJniv. Edin- burgh; Studenthip: (gjh) IDM UKSC & SERC; Grant Pics: AIVRU Sliefield; IIelp: A.Zisserinan&C.hlarinos.

Parallel array processors hold great promise for fast image processing applications. This paper contains an analysis of the convergence of some recursive parallel array processes in boolean arrays. The analysis involves looking for a fixed point solution to the recursion relation and ensuring that the fixed point is indeed accessible. A condition for stability is found for one potentially unstable recursive operation. Implementation of the recursive processes on a CLIP4 parallel array processor is also discussed.