Manifold learning algorithms rely on a neighbourhood graph to provide an estimate of the data’s local topology. Unfortunately, current methods for estimating local topology assume local Euclidean geometry and locally uniform data density, which often leads to poor data embeddings. We address these shortcomings by proposing a framework that combines local learning with parametric density estimation for local topology estimation. Given a data set \mathcalD ⊂\mathcalX, we first estimate a new metric space (\mathbbX,d_\mathbbX) that characterizes the varying sample density of \mathcalX in \mathbbX, then use (\mathbbX,d_\mathbbX) as a new (pilot) input space for the graph construction step of the manifold learning process. The proposed framework results in significantly improved embeddings, which we demonstrated objectively by assessing clustering accuracy.

We present a novel method to upsample mobile LiDAR data using panoramic images collected in urban environments. Our method differs from existing methods in the following aspects: First, we consider point visibility with respect to a given viewpoint, and use only visible points for interpolation; second, we present a multi-resolution depth map based visibility computation method; third, we present ray casting methods for upsampling mobile LiDAR data incorporating constraints from color information of spherical images. The experiments show the effectiveness of the proposed approach.

We present an automatic approach to window and façade detection from LiDAR (Light Detection And Ranging) data collected from a moving vehicle along streets in urban environments. The proposed method combines bottom-up with top-down strategies to extract façade planes from noisy LiDAR point clouds. The window detection is achieved through a two-step approach: potential window point detection and window localization. The facade pattern is automatically inferred to enhance the robustness of the window detection. Experimental results on six datasets result in 71.2% and 88.9% in the first two datasets, 100% for the rest four datasets in terms of completeness rate, and 100% correctness rate for all the tested datasets, which demonstrate the effectiveness of the proposed solution. The application potential includes generation of building facade models with street-level details and texture synthesis for producing realistic occlusion-free façade texture.

One major challenge for traffic management systems is the inference of traffic flow in regions of the network for which there are little data. In this paper, Global-Positioning-System (GPS)-based vehicle locator data from a fleet of 40–60 roving ambulances are used to predict the most likely ambulance speeds in a network of 20 000 streets in the city of Ottawa, ON, Canada. First, the road network is represented as a directed graph data structure. Then, we compare two algorithms, i.e., relaxation labeling and belief propagation, that interpolate the sparse and noisy measurements from the fleet to obtain dense locally consistent ambulance speeds. Unlike several other systems in the literature, we model all of the city's freeways and surface streets, and both road types are treated with equal importance. Furthermore, the data structure and algorithms described in this paper are not only extended to real-world needs such as road closures and the incorporation of live data with historical data but are also computationally efficient, providing updates in intervals of less than 5 min on commodity hardware. Presented experimental results address the key issue of validating the performance and reliability of the system.

Linear Discriminant Analysis (LDA) is a popular tool for multiclass discriminative dimensionality reduction. However, LDA suffers from two major problems: (1) It only optimizes the Bayes error for the case of unimodal Gaussian classes with equal covariances (assuming full rank matrices) and, (2) The multiclass extension maximizes the sum of pairwise distances between the classes, and does not “simultaneously” maximize each pairwise distance between the classes. This typically results in serious overlapping in the projected space between classes that are “close” in the input space. To solve these two problems, this paper proposes Pareto Discriminant Analysis (PARDA). Firstly, PARDA explicitly models each of the classes as a multidimensional Gaussian with a sample covariance. Secondly, PARDA decomposes the multiclass problem to a set of pairwise objective functions representing the pairwise distance between different classes. Unlike existing extensions of Fisher discriminant analysis (FDA) to multiclass problems, that typically maximize the sum of pairwise distances between classes, PARDA simultaneously maximizes each pairwise distance, thus encouraging the case that all classes are equidistant from each other in the lower dimensional space. Solving PARDA is a multiobjective optimization problem - simultaneously optimizing more than one, possibly conflicting, objective functions - and the resulting solution is known to be “Pareto Optimal”. Experimental results on synthetic data, several image data sets and data sets from the UCI repository show positive and encouraging results in favor of PARDA when compared with standard and state-of-the-art multiclass extensions of LDA.

We present a bimodal information analysis system for automatic emotion recognition. Our approach is based on the analysis of video sequences which combines facial expressions observed visually with acoustic features to automatically recognize five universal emotion classes: anger, disgust, happiness, sadness and surprise. We address the challenges posed during the temporal analysis of the bimodal data and introduce a novel technique for combining the best features of instantaneous and temporal based visual recognition systems. We obtain robust appearance-based visual features which we classify instantaneously and aggregate it temporally to improve the recognition rates when compared to single-frame based instantaneous classification. The performance of the system is further boosted by using the complementary audio information for the bimodal emotion recognition. We combine the two modalities at both feature and score level to compare the respective joint emotion recognition rates. The emotions are instantaneously classified using a support vector machine and sequentially aggregated based on their classification probabilities. This approach is validated on a posed audio-visual database and a natural interactive database. The experiments performed on these databases provide encouraging results with the best combined recognition rate being 82%.

This paper presents a novel method for detection of image interest regions called Structure Guided Salient Regions (SGSR). Following the information theoretic route to saliency detection, we extend Kadir et al.’s Salient Region detector by exploiting image structure information. The detected SGSRs are highly distinct and very selective. For planar scenes, their performance on repeatability tests under viewpoint changes is comparable to the state of the art. For 3D scenes, SGSRs are more likely to be repeatably detected under viewpoint change. Their usefulness for wide baseline matching is demonstrated with a real-world example, where their comparative advantages are shown. 1

We are interested in learning an adaptive local metric on a lower dimensional manifold for query--based operations.We combine the concept underlying manifold learning algorithms and the minimum volume ellipsoid metric to find the nearest neighbouring points to a query point on the manifold on which the query point is lying. Extensive experiments on various standard benchmark data sets in the context of classification showed very promising results when compared to state of the art metric learning algorithms.

To learn a metric for query-based operations, we combine the concept underlying manifold learning algorithms and the minimum volume ellipsoid metric in a unified algorithm to find the nearest neighbouring points on the manifold on which the query point is lying. Extensive experiments on standard benchmark data sets in the context of classification showed promising and interesting results with regard to our proposed algorithm.

This paper addresses the problem of super-resolving a single image and recovering the characteristics of the sensor using a learning-based approach. In particular, the point spread function (PSF) of the camera is sought by minimizing the mean Euclidean distance function between patches from the input frame and from degraded versions of high-resolution training images. Once an estimate of the PSF is obtained, a supervised learning algorithm can then be used as is. Results are compared with another method for blind super-resolution by using a series of quality measures.

A novel procedure is presented to construct image-domain filters (receptive fields) that directly recover local motion and shape parameters. These receptive fields are derived from training on image deformations that best discriminate between different shape and motion parameters. Beginning with the construction of 1D receptive fields that detect local surface shape and motion parameters within cross sections, we show how the recovered shape and motion model parameters are sufficient to produce local estimates of time to collision. In general, filter pairs (receptive fields) can be synthesized to perform or detect specific image deformations. At the heart of the method is the use of a matrix to represent image deformation correspondence between individual pixels of two views of a surface. The image correspondence matrix can be decomposed using singular value decomposition to yield a pair of corresponding receptive fields that detect image changes due to the deformation of interest.

This paper presents a novel image-based approach for updating the geometry of 3D models. The technique can cope with large-scale models, using a single imaging sensor to which an arbitrary motion is applied. Current approaches usually do not fully take advantage of strong prior information, often available in the form of an initial model. The approach is thus novel in that geometric anomalies are quickly detected, significantly reducing problem complexity. Hence, given a geometric model and known camera motion, the image warping can be calculated and intensity patterns can be predicted. If predictions do not match observations, the model is assumed to be incorrect.

A road sign (RS) recognition system poses a real challenge for machine vision. It must recognize a wide variety of RSs under considerable variations in illumination and imaging geometry-all in real-time. Such a system is presented, with emphasis on the system architecture and specific model-based techniques used in the different processing steps. Central to this are a unique physics-based color detection approach and a novel template matching scheme for planar objects. Since the approach strongly relies on modelling for both detection and recognition, it offers the advantage of being reconfigurable by changing only a few parameters. The system is modular with respect to the sensor and the recognition data structure is simple to extend and maintain, and is easily adaptable to different regulations, e.g. North American vs European RSs. The data needed for recognition is computed automatically by modelling image formation with a few geometrical parameters. Experimental results are presented which demonstrate the performance of the system in a real task environment with high overall performance.

In this paper we propose a paradigm called the Interactive Visual Dialog (IVD) as a means of facilitating a system’s ability to recognize objects p-resented to it by a human. The presentation centers around a supermarket checkout scenario in which an operator presents an item to be tallied to a sta-tionary television camera. An active vision approach is used to provide feed-back to the operator in the form of an image (or images) depicting what the system thinks the operator is most likely holding, shown in a viewpoint that suggests how the object should next be presented to improve the certainty of interpretation. Interaction proceeds iteratively until the system converges on the correct interpretation. We show how the IVD can be implemented using an entropy-based gaze planning strategy and a sequential Bayes recognition system using optical flow as input. Experimental results show that the system does, in practice, improve recognition accuracy, leading to convergence to a correct solution in a minimal number of iterations. 1

This paper introduces an object recognition strategy based on the following premises: i) an object can be identified on the basis of the optical flow it induces on a stationary observer, and ii) a basis for recognition can be built on the appearance of flow corresponding to local curvilinear motion. Unlike other approaches that seek to recognize particular motions, ours focuses on the problem of recognizing objects by training on an expected set of motions. A sequential estimation framework is used to solve the implicit factorization problem, which is itself simplified in that the task is to discriminate between different objects as opposed to recovering motion or structure. Training is accomplished automatically using a robot mounted camera system to induce a set of canonical motions at different locations on a viewsphere. Experimen-tal results are presented to support our contention that the resulting motion basis can generalize to a fairly wide range of motions, leading to a practical method for recognizing moving objects. 1

The hand-eye problem consists in determining the relative pose between two coordinate frames fixed to the same rigid body from measurements of the poses attained by these two frames, as the body moves. In robotics this problem arises when two frames are attached to the end-effector (EE), one of these at the gripper, the other to a sensor such as a camera or a laser range-finder. Various procedures have been proposed to solve this problem when perfect pose measurements are available at a pair of EE poses, the treatment of noisy measurements being a current research topic. Solutions proposed for the case of perfect measurements require an iterative procedure based on the singular-value decomposition, which itself relies on iterative procedures. The treatment of noisy measurements has led to offline least-square solutions. It is shown in this paper that, based on an invariant formulation of the problem at hand, a solution is possible that relies on recursive linear least squares. Thus, the procedure lends itself to an online implementation, as demonstrated here with experimental results. A major difference between the proposed procedure and those reported in the literature is that the latter are iterative; ours is recursive.

In this paper, we show how entropy maps can be used to guide an active observer along an optimal trajectory, by which the identity and pose of objects in the world can be inferred with confidence, while minimizing the amount of data that must be gathered. Specifically we consider the case of active object recognition where entropy maps are used to encode prior knowledge about the discriminability of objects as a function of viewing position. The paper describes how these maps are computed using optical flow signatures as a case study, and how a gaze-planning strategy can be formulated by using entropy minimization as a basis for choosing a next best view. Experimental results are presented which show the strategy's effectiveness for active object recognition using a single monochrome television camera.

This paper addresses the question of how to integrate local and global information-the goal being a stable mechanism to partition parametric data into meaningful classes without injecting a priori information about the data. To do this we introduce a novel framework to represent both local and global information and their interactions. Where both types of information are represented together in parameter space and together define a self-organisation or warping of the data. An unsupervised clustering analysis is then performed to extract from the parametric data classes that are stable and meaningful. As an example of this paradigm we consider the problem of shape decomposition. Here we describe how image discontinuities (i.e. curves, edges or local curvature) can be integrated with global parametric models that represent the image. The resulting class clusters are then equivalent to the inferred part decomposition. An example of how this process can be used is demonstrated by applying it to the specific problem of determining the parts of 3-D objects. Results on real laser rangefinder images of complex objects are presented.

We propose a the use of a consistent Bayesian methodology for the analysis of the uncertainty associated with a pose estimation procedure. A novel model-based technique to estimate the pose of rigid 3D objects from laser range finder images is studied, and various sources of uncertainty are carried through the process using a Bayesian MAP treatment, yielding local, point-by-point estimates of position and predicted error. Promising experimental results on complex objects are presented and discussed.

Describes a system for automatically digitizing the surfaces of a completely unknown object to a prescribed sampling density. Unlike many available commercial systems (e.g. Cyberware), our system analyzes actively the data and computes sensor trajectories to achieve complete surface coverage taking into account the limitations of the sensor/manipulator. This represents in fact an active approach to the problem of complete object digitization, working directly at the measurement level, as opposed to existing off-line methods that perform post-processing on a fixed data set. We propose a theoretical framework to achieve this goal and we present preliminary results of a laboratory implementation.

Many relaxation based smoothing methods used in surface reconstruction algorithms filter out the effect of noise in image data, but result in the elimination of important discontinuity information as well. In this paper the inter-pixel interaction during relaxation is shown to be equivalent to a multiple measurement fusion problem which can be solved using optimal estimation theory. Pixels in a given neighbourhood act as noisy information sources, combining their information to update the state of that neighbourhood. By formulating discontinuities as another "noise" source in the image, and by using the so-called Curvature Consistency reconstruction algorithm on range images, it is shown that optimal estimation theory offers a method for the automatic and adaptive localization of discontinuities while providing a smooth piece wise continuous surface description.

Passively accepting measurements of the world is not enough, as the data we obtain is always incomplete, and the inferences made from it uncertain to a degree which is often unacceptable. If we are to build machines that operate autonomously, they will always be faced with this dilemma, and can only be successful if they play a much more active role. This paper presents such a machine. It deliberately seeks out those parts of the world which maximize the fidelity of its internal representations, and keeps searching until those representations are acceptable. We call this paradigm autonomous exploration, and the machine an autonomous explorer. This paper has two major contributions. The first is a theory that tells us how to explore, and which confirms the intuitive ideas we have put forward previously. The second is an implementation of that theory. In our laboratory, we have constructed a working autonomous explorer and here, for the first time, show it in action. The system is entirely bottom-up and does not depend on any a priori knowledge of the environment. To our knowledge, it is the first to have successfully closed the loop between gaze planning and the inference of complex 3D models.

Many strategies in computer vision assume the existence of general purpose models that can be used to characterize a scene or environment at various levels of abstraction. The usual assumptions are that a selected model is competent to describe a particular attribute and that the parameters of this model can be estimated by interpreting the input data in an appropriate manner (e.g., location of lines and edges, segmentation into parts or regions, etc.). This paper considers the problem of how to determine when those assumptions break down. The traditional approach is to use statistical misfit measures based on an assumed sensor noise model. The problem is that correct operation often depends critically on the correctness of the noise model. Instead, we show how this can be accomplished with a minimum of a priori knowledge and within the framework of an active approach which builds a description of environment structure and noise over several viewpoints.

Recognition ambiguity, due to noisy measurements and uncertain object models, can be quantified and actively used by an autonomous agent to efficiently gather new data and improve its information about the environment. In this work an information-based utility measure is used to derive from a learned classification of shape models an efficient data collection strategy, specifically aimed at increasing classification confidence when recognizing uncertain shapes. Promising simulation results are presented and discussed.

This paper deals with generic 3D shape modelling for the purposes of object recognition. Difficulties with many existing methods are that they either capture insufficient detailed structure or fail to provide sufficiently abstract descriptions. The approach presented here attempts to address this problem by building a composite representation of the data in terms of a superquadric augmented with multi-scale surface models. This is illustrated experimentally using laser range data. The superquadric that results in the best possible fit is expressed in terms of its position, size, shape and pose parameters. The residual of the fit is then modelled at several scales using multiple surface patches with uniform mean and Gaussian curvature. A hierarchical ranking of these patches is used to describe the residual based on geometric properties. These geometric properties are ranked according to criteria expressing their stability and utility. The most stable patches are selected as the description of the residual. The resulting representation can then be used for both pose estimation and object recognition.

This paper introduces a monocular optical flow algorithm that has been shown to perform well at nearly real-time frame rates (4 FPS on a 100 MHz SGI Indy workstation), using natural image sequences. The system is completely bottom-up, using pixel region-matching techniques. A coordinated gradient descent method is broken down into two stages: pixel region matching error measures are locally minimized and flow field consistency constraints apply nonlinear adaptive diffusion, causing confident measurements to influence their less confident neighbors. Convergence is usually accomplished with one iteration for an image frame pair. Temporal integration predicts upcoming flow fields. The algorithm is designed for flexibility: large displacements are tracked as easily as sub-pixel displacements, and higher-level information can feed flow field predictions into the measurement process.

Scene ambiguity, due to noisy measurements and uncertain object models, can be quantified and actively used by an autonomous agent to efficiently gather new data and improve its information about the environment. In this work an information-based utility measure is used to derive from a learned classification of shape models an efficient data collection strategy, specifically aimed at increasing classification confidence when recognizing uncertain shapes.

Passively accepting measurements of the world is not enough, as the data we obtain is always incomplete, and the inferences made from it are uncertain to a degree which is often unacceptable. If we are to build machines that operate autonomously they will always be faced with this dilemma, and can only be successful if they play a much more active role. This paper presents such a machine. It deliberately seeks out those parts of the world which maximize the fidelity of its internal representations, and keeps searching until those representations are acceptable. We call this paradigm autonomous exploration, and the machine an a autonomous explorer. This paper has two major contributions. The first is a theory that tells us how to explore, and which confirms the intuitive ideas we have put forward previously. The second is an implementation of that theory. The system is entirely bottom-up and does not depend on a priori knowledge of the environment. To our knowledge it is the first to have successfully closed the loop between gaze planning and the inference of complex 3D models.>

This paper describes a new framework for parametric shape recognition. The key result is a method for generating classifiers in the form of conditional probability densities for recognizing an unknown from a set of reference models. The authors' procedure is automatic. Off-line, it invokes an autonomous process to estimate reference model parameters and their statistics. On-line, during measurement, it combines these with a priori context-dependent information, as well as the parameters and statistics estimated for an unknown object, into a conditional probability density function, which represents the belief that the unknown is a particular reference model. The paper also describes the implementation of this procedure in a system for automatically generating and recognizing 3-D part-oriented models. The authors show that recognition performance is near perfect for cases in which complete surface information is accessible to the algorithm, and that it falls off gracefully when only partial information is available. This leads to the possibility of an active recognition strategy in which the belief measures associated with each classification can be used as feedback for the acquisition of further evidence as required.

A method is presented for partitioning a set of surface estimates obtained with a laser range finding system into subsets corresponding to parts of an object. The authors' strategy uses two complementary representations for surfaces, i.e., one which describes local structures in terms of differential properties (e.g., edges, lines, contours) and another which represents the surface as a collection of smooth patches at different scales. By enforcing a consistent interpretation between these two representations, it is possible to derive a partitioning algorithm that is both efficient and robust.>

Many strategies in computer vision assume the existence of general purpose models that can be used to characterize a scene or environment at various levels of abstraction. The usual assumptions are that a selected model is competent to describe a particular attribute and that the parameters of this model can be estimated by interpreting the input data in an appropriate manner. The authors consider the problem of determining when these assumptions break down so that an alternate model may be considered or further interpretation of data performed. Specifically, how this can be accomplished is analyzed within the framework of an approach that actively builds a description of the environment from several different viewpoints. It is shown that a gaze planning strategy used to minimize model parameter variance can also be used to decide whether the model itself provides an adequate description of the environment.>

A representational and a computational model for deriving 3-D articulated volumetric descriptions of objects from laser rangefinder data is described. This method is purely bottom up: it relies on general assumptions cast in terms of differential geometry. Darboux frames, snakes, and superquadrics form the basis of this representation, and curvature consistency provides the computational framework. The organization is hierarchical. Darboux frames are used to describe the local surface, whereas snakes are used to interpolate between features, particularly those that serve to partition a surface into its constituent parts. Superquadrics are used to characterize the 3-D shape of each surface partition. The result is a set of connected volumetric primitives that serve to describe the overall shape of an object. Examples that show how the approach performs on data acquired with a laser rangefinder are included.>

The possibility that what we do not know about the world can be used to guide the way in which they explore it is raised. The authors previously hypothesized that the spatial structure of uncertainty can be used to guide the acquisition of additional data in a way that significantly improves knowledge of a scene. An exploration strategy based on the hypothesis is constructed, and experimental results which verified that it works are presented. Conditions which cause it to break down are studied. The results indicate that there are inherent degeneracies in certain data configurations, but that the authors' strategy can navigate these areas successfully.>

The authors attempt to determine what can be inferred from ambiguity in processes of visual interpretation. They discuss this question in a specific context: the interpretation of scene geometry in the form of parametrized volumetric models. Ambiguity is described as a local probabilistic property of the misfit error surface in the parameter space of superellipsoid models, namely, as an ellipsoid of confidence in which there is a given probability that the true parameters can be found. The authors show how to project the ellipsoid of confidence back into 3D space to obtain the shell in which the true 3D surface most probably lies and introduce what they call the uncertainty as a local property of the fitted model's surface. They propose a technique that can use this information to plan a new direction of view that minimizes the ambiguity of subsequent interpretation.>

The question posed is what can be inferred from ambiguity in processes of visual interpretation? Much emphasis is naturally placed on the form of constraints used to minimize ambiguity, particularly as they pertain to such issues as perceptual acceptability. The authors feel that it is perhaps more instructive to consider what can be learned from situations where different interpretations of data are possible, i.e., the ambiguity of perception. This immediately raises a number of issues regarding the characterization of ambiguity, communicating it to other visual processes, and using ambiguity to further refine visual interpretation. The context in which the authors discuss these problems is the interpretation of scene geometry in the form of volumetric models. They describe a representation for ambiguity in terms of an ellipsoid of confidence in which there is a finite probability that the true parameters of the model can be found.>

The authors describe how a surface reconstruction algorithm based on minimizing the variation of surface curvature can be used to stabilize and correct the results of local shading analysis. The approach is viewpoint independent and applicable to any process that can provide estimates of local surface orientation. The assumptions used in formulating the minimization are derived from standard differential geometry. When applied as a second stage of processing after local shading analysis, the algorithm can recover a close approximation of the true surface orientation under realistic assumptions about image noise. Results are presented that show the performance of the algorithm on synthetic and real data. In particular, they demonstrate how this form of reconstruction can compensate for some of the shape distortion incurred in local shading analysis.>

An apparent contradiction in the shape-from-shading literature is examined. Although practical experience suggests that shape can be inferred from the local analysis of shading, mathematical analyses support the opposite. A criterion for exact surface recovery is derived, and it is shown that, as a result of surface geometry, elliptic, hyperbolic, and doubly curved surfaces could be recovered to reasonable accuracy provided that surface curvature and/or foreshortening were limited. In other words, by relaxing the requirement that surfaces be recovered exactly, it is found that local analysis of shading can provide useful descriptions of shape as evidenced by the results presented.>

Much of the emphasis in computer vision research has been on recognizing objects. However, in order to perform tasks such as manipulating and avoiding collisions with objects, one needs to consider how to derive appropriate three-dimensional descriptions of objects from available sensor data. A description is given of a computational approach that has been successful in deriving renditions of shaded images in terms of volumetric primitives such as ellipsoids and cylinders.>

This paper presents a model of motion suitable for cell tracking. It includes a representation for cell dynamics enabling it to maintain a correspondence between successive images of cells undergoing morphological changes. This model is based on a minimization problem whose computational solution is similar in form to a Newton-Rhapson iteration. The model is supported by experimental results from an actual tracking problem.