In this paper, we present GGSD, a novel graph generative model based on 1) the spectral decomposition of the graph Laplacian matrix and 2) a diffusion process. Specifically, we propose to use a denoising model to sample eigenvectors and eigenvalues from which we can reconstruct the graph Laplacian and adjacency matrix. Using the Laplacian spectrum allows us to naturally capture the structural characteristics of the graph and work directly in the node space while avoiding the quadratic complexity bottleneck that limits the applicability of other diffusion-based methods. This, in turn, is accomplished by truncating the spectrum, which, as we show in our experiments, results in a faster yet accurate generative process, and by designing a novel transformer-based architecture linear in the number of nodes. Our permutation invariant model can also handle node features by concatenating them to the eigenvectors of each node. An extensive set of experiments on both synthetic and real-world graphs demonstrates the strengths of our model against state-of-the-art alternatives.

The convolution operator at the core of many modern neural architectures can effectively be seen as performing a dot product between an input matrix and a filter. While this is readily applicable to data such as images, which can be represented as regular grids in the Euclidean space, extending the convolution operator to work on graphs proves more challenging, due to their irregular structure. In this article, we propose to use graph kernels, i.e., kernel functions that compute an inner product on graphs, to extend the standard convolution operator to the graph domain. This allows us to define an entirely structural model that does not require computing the embedding of the input graph. Our architecture allows to plug-in any type of graph kernels and has the added benefit of providing some interpretability in terms of the structural masks that are learned during the training process, similar to what happens for convolutional masks in traditional convolutional neural networks (CNNs). We perform an extensive ablation study to investigate the model hyperparameters' impact and show that our model achieves competitive performance on standard graph classification and regression datasets.

Data augmentation is a widely adopted approach to solve the large-data requirements of modern deep learning techniques by generating new data instances from an existing dataset. While there is a huge literature and experience on augmentation for vectorial or image-based data, there is relatively little work on graph-based representations. This is largely due to complex, non-Euclidean structure of graphs, which limits our abilities to determine operations that do not modify the original semantic grouping. In this paper, we propose an alternative method for enlarging the graph set of graph neural network datasets by creating new graphs and keeping the properties of the originals. The proposal starts from the assumptions that the graphs compose a set of smaller motifs into larger structures. To this end, we extract modules by grouping nodes in an unsupervised way, and then swap similar modules between different graphs reconstructing the missing connectivity based on the original edge statistics and node similarity. We then test the performance of the proposed augmentation approach against state-of-the-art approaches, showing that on datasets, where the information is dominated by structure rather than node labels, we obtain a significant improvement with respect to alternatives.

The design of machines and algorithms capable of learning in a dynamically changing environment has become an increasingly topical problem with the increase of the size and heterogeneity of data available to learning systems. As a consequence, the key issue of Continual Learning has become that of addressing the stability-plasticity dilemma of connectionist systems, as they need to adapt their model without forgetting previously acquired knowledge. Within this context, rehearsal-based methods i.e., solutions in where the learner exploits memory to revisit past data, has proven to be very effective, leading to performance at state-of-the-art. In our study, we propose an analysis of the memory quantity/quality trade-off adopting various data reduction approaches to increase the number of instances storable in memory. In particular, we investigate complex instance compression techniques such as deep encoders, but also trivial approaches such as image resizing and linear dimensionality reduction. Our findings suggest that the optimal trade-off is severely skewed toward instance quantity, where rehearsal approaches with several heavily compressed instances easily outperform state-of-the-art approaches with the same amount of memory at their disposal. Further, in high memory configurations, deep approaches extracting spatial structure combined with extreme resizing (of the order of 8 × 8 images) yield the best results, while in memory-constrained configurations where deep approaches cannot be used due to their memory requirement in training, a variation of Extreme Learning Machines (ELM) offer a clear advantage. Code and experiments available at https://github.com/francesco-p/smaller-is-better

Abstract The Average Mixing Kernel Signature is a novel spectral signature for points on non-rigid three-dimensional shapes. It is based on a quantum exploration process of the shape surface, where the average transition probabilities between the points of the shape are summarised in the finite-time average mixing kernel. A band-filtered spectral analysis of this kernel then yields the AMKS. Crucially, we show that opting for a finite time-evolution allows the signature to account for a mixing of the Laplacian eigenspaces, similar to what is observed in the presence of noise, explaining the increased noise robustness of this signature when compared to alternative signatures. We perform an extensive experimental analysis of the AMKS under a wide range of problem scenarios, evaluating the performance of our descriptor under different sources of noise (vertex jitter and topological), shape representations (mesh and point clouds), as well as when only a partial view of the shape is available. Our experiments show that the AMKS consistently outperforms two of the most widely used spectral signatures, the Heat Kernel Signature and the Wave Kernel Signature, and suggest that the AMKS should be the signature of choice for various compute vision problems, including as input of deep convolutional architectures for shape analysis.

Polarisation Filter Array (PFA) cameras allow the analysis of light polarisation state in a simple and cost-effective manner. Such filter arrays work as the Bayer pattern for colour cameras, sharing similar advantages and drawbacks. Among the others, the raw image must be demosaiced considering the local variations of the PFA and the characteristics of the imaged scene. Non-linear effects, like the cross-talk among neighbouring pixels, are difficult to explicitly model and suggest the potential advantage of a data-driven learning approach. However, the PFA cannot be removed from the sensor, making it difficult to acquire the ground-truth polarization state for training. In this work we propose a novel CNN-based model which directly demosaics the raw camera image to a per-pixel Stokes vector. Our contribution is twofold. First, we propose a network architecture composed by a sequence ofMosaiced Convolutionsoperating coherently with the local arrangement of the different filters. Second, we introduce a new method, employing a consumer LCD screen, to effectively acquire real-world data for training. The process is designed to be invariant by monitor gamma and external lighting conditions. We extensively compared our method against algorithmic and learning-based demosaicing techniques, obtaining a consistently lower error especially in terms of polarisation angle.

Phase-shift is one of the most effective techniques in 3D structured-light scanning for its accuracy and noise resilience. However, the periodic nature of the signal causes a spatial ambiguity when the fringe periods are shorter than the projector resolution. To solve this, many techniques exploit multiple combined signals to unwrap the phases and thus recovering a unique consistent code. In this paper, we study the phase estimation and unwrapping problem in a stochastic context. Assuming the acquired fringe signal to be affected by additive white Gaussian noise, we start by modelling each estimated phase as a zero-mean Wrapped Normal distribution with variance σ ̄ 2 . Then, our contributions are twofolds. First, we show how to recover the best projector code given multiple phase observations by means of a ML estimation over the combined fringe distributions. Second, we exploit the Cramér-Rao bounds to relate the phase variance σ ̄ 2 to the variance of the observed signal, that can be easily estimated online during the fringe acquisition. An extensive set of experiments demonstrate that our approach outperforms other methods in terms of code recovery accuracy and ratio of faulty unwrappings.

The ubiquitous presence of cylindrical shapes in both natural and man-made environments makes their automated extraction a pivotal task for a broad range of applications such as robot manipulation, reverse engineering and automated industrial inspection. Albeit conceptually simple, the task of fitting cylinders from 3D data can quickly become challenging if performed "in-the-wild", when no prior is given to the number of primitives to find or when the point cloud is noisy and not oriented. In this paper we introduce a new robust approach to iteratively extract cylindrical primitives from a 3D point cloud by exploiting mutual consensus of different cylinder candidates. First, a set of possible axes is generated by slicing the point cloud with multiple random planes. Then, a game-theoretic inlier selection process is performed to extract a subset of axes maximizing the fitness against a payoff function based on the shortest geodesic path in SE(3) between pairs of corresponding 3D lines. Finally, the probability distribution resulting from the previous selection step is used to weight the input candidates and robustly obtain the final cylinder coefficients. Compared to other methods, our approach does not require point normals, offers superior resilience to noise and does not depend on delicate tuning of multiple parameters.

In the last decade, underwater wireless sensor networks (UWSNs) have attracted a lot of attention from the research community thanks to their wide range of applications that include seabed mining, military and environmental monitoring. With respect to terrestrial networks, UWSNs pose new research challenges such as the three-dimensional node deployment and the use of acoustic signals. Despite the large number of routing protocols that have been developed for UWSNs, there are very few analytical results that study their optimal configurations given the system's parameters (density of the nodes, frequency of transmission, etc.). In this paper, we make one of the first steps to cover this gap. We study an abstraction of an opportunistic routing protocol and derive its optimal working conditions based on the network characteristics. Specifically, we prove that using a depth threshold, i.e., the minimum length of one transmission hop to the surface, is crucial for the optimality of opportunistic protocols and we give a numerical method to compute it. Moreover, we show that there is a critical depth threshold above which no packet can be transmitted successfully to the surface sinks in large networks, which further highlights the importance of properly configuring the routing protocol. We discuss the implications of our results and validate them by means of stochastic simulations on NS3.

Functional representation is a well-established approach to represent dense correspondences between deformable shapes. The approach provides an efficient low rank representation of a continuous mapping between two shapes, however under that framework the correspondences are only intrinsically captured, which implies that the induced map is not guaranteed to map the whole surface, much less to form a continuous mapping. In this work, we define a novel approach to the computation of a continuous bijective map between two surfaces moving from the low rank spectral representation to a sparse spatial representation. Key to this is the observation that continuity and smoothness of the optimal map induces structure both on the spectral and the spatial domain, the former providing effective low rank approximations, while the latter exhibiting strong sparsity and locality that can be used in the solution of large-scale problems. We cast our approach in terms of the functional transfer through a fuzzy map between shapes satisfying infinitesimal mass transportation at each point. The result is that, not only the spatial map induces a sub-vertex correspondence between the surfaces, but also the transportation of the whole surface, and thus the bijectivity of the induced map is assured. The performance of the proposed method is assessed on several popular benchmarks.

At the core of many Computer Vision applications stands the need to define a mathematical model describing the imaging process. To this end, the pinhole model with radial distortion is probably the most commonly used, as it balances low complexity with a precision that is sufficient for most applications. On the other hand, unconstrained non-parametric models, despite being originally proposed to handle specialty cameras, have been shown to outperform the pinhole model, even with the simpler setups. Still, notwithstanding the higher accuracy, the inability of describing the imaging model by simple linear projective operators severely limits the use of standard algorithms with unconstrained models. In this paper we propose a parameter-free camera model where each imaging ray is constrained to a common optical center, forcing the camera to be central. Such model can be easily calibrated with a practical procedure which provides a convenient undistortion map that can be used to obtain a virtual pinhole camera. The proposed method can also be used to calibrate a stereo rig with a displacement map that simultaneously provides stereo rectification and corrects lens distortion.

Abstract In this paper, we propose a method for computing partial functional correspondence between non‐rigid shapes. We use perturbation analysis to show how removal of shape parts changes the Laplace–Beltrami eigenfunctions, and exploit it as a prior on the spectral representation of the correspondence. Corresponding parts are optimization variables in our problem and are used to weight the functional correspondence; we are looking for the largest and most regular (in the Mumford–Shah sense) parts that minimize correspondence distortion. We show that our approach can cope with very challenging correspondence settings.

We consider the problem of deformable object detection and dense correspondence in cluttered 3D scenes. Key ingredient to our method is the choice of representation: we formulate the problem in the spectral domain using the functional maps framework, where we seek for the most regular nearly-isometric parts in the model and the scene that minimize correspondence error. The problem is initialized by solving a sparse relaxation of a quadratic assignment problem on features obtained via data-driven metric learning. The resulting matching pipeline is solved efficiently, and yields accurate results in challenging settings that were previously left unexplored in the literature.

When a planar structure is observed from multiple views, the projections of its corresponding 3D points on each image are related by a homography. Its estimation is a key step in many computer vision tasks where either the rigid motion between views or a per-pixel image correspondence is sought. The vast majority of multi-view homography estimation techniques relies on matching a sparse set of point-to-point correspondences to establish a connected graph in the camera network. This track creation step is critical to ensure that the following bundle adjustment can estimate a globally optimal alignment in which the error is diffused coherently on each pairwise homography. On the other hand, erroneous or short tracks often cause misalignments among the views. We propose an optimization technique to simultaneously recover a transitively consistent network of planar homographies between multiple views together with a segmentation of the pixels comprising the observed plane (Fig. 1). Our method acts on a per-pixel basis to avoid a preliminary multi-view sparse feature matching step. Similarly to bundle adjustment, the error is diffused so that each homography in the view graph is transitively consistent with the others. The effectiveness of the proposed approach is evaluated in real-world scenarios and synthetically generated scenes.

Feature matching is a key step in most Computer Vision tasks involving several views of the same subject. In fact, it plays a crucial role for a successful reconstruction of 3D information of the corresponding material points. Typical approaches to construct stable feature tracks throughout a sequence of images operate via a two-step process: First, feature matches are extracted among all pairs of points of view; these matches are then given in input to a regularizer that provides a final, globally consistent solution. In this paper, we formulate this matching problem as a simultaneous optimization over the entire image collection, without requiring previously computed pairwise matches to be given as input. As our formulation operates directly in the space of feature across multiple images, the final matches are consistent by construction. Our matching problem has a natural interpretation as a non-cooperative game, which allows us to leverage tools and results from Game Theory. We performed a specially crafted set of experiments demonstrating that our approach compares favorably with the state of the art, while retaining a high computational efficiency.

We present a novel approach to the computation of dense correspondence maps between shapes in a non-rigid setting. The problem is defined in terms of functional correspondences. We deal with the non-injectivity of the solution of the functional map framework due to the under-determinedness of the original problem. Key to our approach is the injectivity constraint plugged directly into the problem to optimize, achieved casting it as an assignment problem. This leads to an iterative process which yields a high quality bijective map between the shapes. In the experimental section we present both quantitative and qualitative results, showing that the proposed approach is competitive with the current state-of-the-art on quasi-isometric shape matching benchmarks.

In this paper, we present a novel thermodynamic framework for graphs that can be used to analyze time evolving networks, relating the thermodynamics variables to macroscopic changes in network topology, and linking major structural transition to phase changes in the thermodynamic picture. We start from a recent quantum-mechanical characterization of the structure of a network relating the graph Laplacian to a density operator and resulting in a characterization of the network's entropy. Then we adopt a Schrödinger picture of the dynamics of the network, resulting in an estimation of a hidden time-varying Hamiltonian from the data, from which we derive a measure of Energy exchange. From these variables, using the thermodynamic identity, we obtain temperature under the assumption of constant volume of the system. Evaluation of real-world data shows that the thermodynamic variables thus extracted are effective in detecting critical events occurring during network evolution.

A number of critical factors arises when a complex 3D scene is to be reconstructed by means of a large sequence of different views. Some of them are related to the ability to recover the correct identity and the accurate projection of each observed feature. Other sources of error are tied to the reliability of the orientation estimate for each view. With this paper we propose a method that tries to solve both problems at the same time, while being also inherently resilient to outliers. At the core of the approach stands a widely adopted game-theoretical selection technique, which has already been successfully embraced to address similar tasks. The original inception, however, has been further refined to address a wider range of scenarios, as well as to offer a reduced memory consumption and computation complexity. By exploiting these enhancements, we were able to apply our technique to a large-scale setup involving several hundreds of view points and tens of thousands of independent observations.

Artificial markers are successfully adopted to solve several vision tasks, ranging from tracking to calibration. While most designs share the same working principles, many specialized approaches exist to address specific application domains. Some are specially crafted to boost pose recovery accuracy. Others are made robust to occlusion or easy to detect with minimal computational resources. The sheer amount of approaches available in recent literature is indeed a statement to the fact that no silver bullet exists. Furthermore, this is also a hint to the level of scholarly interest that still characterizes this research topic. With this paper we try to add a novel option to the offer, by introducing a general purpose fiducial marker which exhibits many useful properties while being easy to implement and fast to detect. The key ideas underlying our approach are three. The first one is to exploit the projective invariance of conics to jointly find the marker and set a reading frame for it. Moreover, the tag identity is assessed by a redundant cyclic coded sequence implemented using the same circular features used for detection. Finally, the specific design and feature organization of the marker are well suited for several practical tasks, ranging from camera calibration to information payload delivery.

Non-rigid 3D shape retrieval is an active and important research topic in content based object retrieval. This problem is often cast in terms of the shapes intrinsic geometry due to its invariance to a wide range of non-rigid deformations. In this paper, we devise a novel generative model for shape retrieval based on the spectral representation of the Laplacian of a mesh. Contrary to common use, our approach avoids the ubiquitous correspondence problem by transforming the eigenvectors of the Laplacian to a density in the spectral-embedding space which is estimated nonparametrically. We show that this model can efficiently be learned from a set of 3D meshes. The experimental results on the SHREC'14 benchmark show the effectiveness of the approach compared to the state-of-the-art.

Given the raising interest in light-field technology and the increasing availability of professional devices, a feasible and accurate calibration method is paramount to unleash practical applications. In this paper we propose to embrace a fully non-parametric model for the imaging and we show that it can be properly calibrated with little effort using a dense active target. This process produces a dense set of independent rays that cannot be directly used to produce a conventional image. However, they are an ideal tool for 3D reconstruction tasks, since they are highly redundant, very accurate and they cover a wide range of different baselines. The feasibility and convenience of the process and the accuracy of the obtained calibration are comprehensively evaluated through several experiments.

The analysis of deformable 3D shape is often cast in terms of the shape's intrinsic geometry due to its invariance to a wide range of non-rigid deformations. However, object's plasticity in non-rigid transformation often result in transformations that are not completely isometric in the surface's geometry and whose mode of deviation from isometry is an identifiable characteristic of the shape and its deformation modes. In this paper, we propose a novel generative model of the variations of the intrinsic metric of deformable shapes, based on the spectral decomposition of the Laplace-Beltrami operator. To this end, we assume two independent models for the eigenvectors and the eigenvalues of the graph-Laplacian of a 3D mesh which are learned in a supervised way from a set of shapes belonging to the same class. We show how this model can be efficiently learned given a set of 3D meshes, and evaluate the performance of the resulting generative model in shape classification and retrieval tasks. Comparison with state-of-the-art solutions for these problems confirm the validity of the approach.

Many 3D scanning techniques rely on two or more well calibrated imaging cameras and a structured light source. Within these setups the light source does not need any calibration. In fact the shape of the target surface can be inferred by the cameras geometry alone, while the structured light is only exploited to establish stereo correspondences. Unfortunately, this approach requires each reconstructed point to exhibit an unobstructed line of sight from three independent points of views. This requirement limits the amount of scene points that can be effectively captured with each shot. To overcome this restriction, several systems that combine a single camera with a calibrated projector have been proposed. However, this type of calibration is more complex to be performed and its accuracy is hindered by both the indirect measures involved and the lower precision of projector optics. In this paper we propose an online calibration method for structured light sources that computes the projector parameters concurrently with regular scanning shots. This results in an easier and seamless process that can be applied directly to most current scanning systems without modification. Moreover, we attain high accuracy by adopting an unconstrained imaging model that is able to handle well even less accurate optics. The improved surface coverage and the quality of the measurements are thoroughly assessed in the experimental section.

The estimation of camera intrinsic parameters plays a crucial role in all computer vision tasks for which the underlying model that drives the image formation process has to be known. As a consequence, a deluge set of different approaches has been proposed in literature over the last decades. Most of those lean on the observation of a known object (i.e. a calibration target) from different point of views, providing the necessary data to estimate the model through different optimization approaches. In this work, we exploit the projective properties of conics to estimate the focal length and optical center of a pinhole camera just by observing a set of coplanar circles, where neither the radius nor the reciprocal position of each circle has to be known a-priori. This make such method particularly interesting whenever the usage of a calibration target is not a feasible option. Our contribution is twofold. First, we propose a reliable method to locate coplanar circles from images by means of a non-cooperative evolutionary game. Second, we refine the estimation of camera parameters with a non-linear function minimization through a simple yet effective gradient descent. Performance of the proposed approach is assessed through an experimental section consisting on both quantitative and qualitative tests.

Traditional stereoscopic displays assume the viewer to be standing at a specific location, that is the same pose (relative to the screen) of the stereo camera pair that depicted the scene (physically or virtually). Even for basic applications, such as movies or games, this leads to visual inconsistencies as soon as the user moves his head. Moreover, with this premises, it is not possible at all to develop more sophisticated 3D applications, involving the freedom for the user to walk around objects or to interact with them. The most popular solution to these limitation is to track the user head in order to produce a scene rendering that can be seen correctly from his point of view. With this paper we propose a viewer-dependent system that is very easy to implement since it is based on a simple augmentation of basic shutter glasses used in standard stereoscopic setups. Furthermore, we introduce a practical and sound method to quantitatively assess the accuracy of any view-dependent display approach. This fills a clear shortcoming of the currently adopted evaluation methods, that are for the most part qualitative.

Traditional camera models are often the result of a compromise between the ability to account for non-linearities in the image formation model and the need for a feasible number of degrees of freedom in the estimation process. These considerations led to the definition of several ad hoc models that best adapt to different imaging devices, ranging from pinhole cameras with no radial distortion to the more complex catadioptric or polydioptric optics. In this paper we propose the use of an unconstrained model even in standard central camera settings dominated by the pinhole model, and introduce a novel calibration approach that can deal effectively with the huge number of free parameters associated with it, resulting in a higher precision calibration than what is possible with the standard pinhole model with correction for radial distortion. This effectively extends the use of general models to settings that traditionally have been ruled by parametric approaches out of practical considerations. The benefit of such an unconstrained model to quasi-pinhole central cameras is supported by an extensive experimental validation.

We consider a parametrized relaxation of the widely adopted quadratic assignment problem (QAP) formulation for minimum distortion correspondence between deformable shapes. In order to control the accuracy/sparsity trade-off we introduce a weighting parameter on the combination of two existing relaxations, namely spectral and game-theoretic. This leads to the introduction of the elastic net penalty function into shape matching problems. In combination with an efficient algorithm to project onto the elastic net ball, we obtain an approach for deformable shape matching with controllable sparsity. Experiments on a standard benchmark confirm the effectiveness of the approach.

We consider the problem of minimum distortion intrinsic correspondence between deformable shapes, many useful formulations of which give rise to the NP-hard quadratic assignment problem (QAP). Previous attempts to use the spectral relaxation have had limited success due to the lack of sparsity of the obtained “fuzzy” solution. In this paper, we adopt the recently introduced alternative L1relaxation of the QAP based on the principles of game theory. We relate it to the Gromov and Lipschitz metrics between metric spaces and demonstrate on state-of-the-art benchmarks that the proposed approach is capable of finding very accurate sparse correspondences between deformable shapes.

Over the last decades fiducial markers have provided widely adopted tools to add reliable model-based features into an otherwise general scene. Given their central role in many computer vision tasks, countless different solutions have been proposed in the literature. Some designs are focused on the accuracy of the recovered camera pose with respect to the tag; some other concentrate on reaching high detection speed or on recognizing a large number of distinct markers in the scene. In such a crowded area both the researcher and the practitioner are licensed to wonder if there is any need to introduce yet another approach. Nevertheless, with this paper, we would like to present a general purpose fiducial marker system that can be deemed to add some valuable features to the pack. Specifically, by exploiting the projective properties of a circular set of sizeable dots, we propose a detection algorithm that is highly accurate. Further, applying a dot pattern scheme derived from error-correcting codes, allows for robustness with respect to very large occlusions. In addition, the design of the marker itself is flexible enough to accommodate different requirements in terms of pose accuracy and number of patterns. The overall performance of the marker system is evaluated in an extensive experimental section, where a comparison with a well-known baseline technique is presented.

Surface registration is a fundamental step in the reconstruction of three-dimensional objects. While there are several fast and reliable methods to align two surfaces, the tools available to align multiple surfaces are relatively limited. In this paper we propose a novel multiview registration algorithm that projects several pairwise alignments onto a common reference frame. The projection is performed by representing the motions as dual quaternions, an algebraic structure that is related to the group of 3D rigid transformations, and by performing a diffusion along the graph of adjacent (i.e., pairwise alignable) views. The approach allows for a completely generic topology with which the pair-wise motions are diffused. An extensive set of experiments shows that the proposed approach is both orders of magnitude faster than the state of the art, and more robust to extreme positional noise and outliers. The dramatic speedup of the approach allows it to be alternated with pairwise alignment resulting in a smoother energy profile, reducing the risk of getting stuck at local minima.

Accurate intrinsic camera calibration is essential to any computer vision task that \ninvolves image based measurements. Given its crucial role with respect to precision, a \nlarge number of approaches have been proposed over the last decades. Despite this rich \nliterature, steady advancements in imaging hardware regularly push forward the need \nfor even more accurate techniques. Some authors suggest generalizations of the camera \nmodel itself, others propose novel designs for calibration targets or different optimization \nschemas. In this paper we take a completely different route by directly addressing one \nof the most overlooked problems in practical calibration scenarios. Specifically, we drop \nthe assumption that the target is known with enough precision and we adjust it in an \niterative way as part of the whole process. This is in fact the case with the typical target \nused in most of the calibration literature, which is usually printed on paper and stitched \non a flat surface. In the experimental section we show that even with such a cheaply \ncrafted target it is possible to obtain a very accurate camera calibration that outperforms \nthose obtained with well-known standard techniques.

Surface registration is a fundamental step in the reconstruction of three-dimensional objects. This is typically a two step process where an initial coarse motion estimation is followed by a refinement. Most coarse registration algorithms exploit some local point descriptor that is intrinsic to the shape and does not depend on the relative position of the surfaces. By contrast, refinement techniques iteratively minimize a distance function measured between pairs of selected neighboring points and are thus strongly dependent on initial alignment. In this paper we propose a novel technique that allows to obtain a fine surface registration in a single step, without the need of an initial motion estimation. The main idea of our approach is to cast the selection of correspondences between points on the surfaces in a game-theoretic framework, where a natural selection process allows mating points that satisfy a mutual rigidity constraint to thrive, eliminating all the other correspondences. This process yields a very robust inlier selection scheme that does not depend on any particular technique for selecting the initial strategies as it relies only on the global geometric compatibility between correspondences. The practical effectiveness of the proposed approach is confirmed by an extensive set of experiments and comparisons with state-of-the-art techniques.

Feature-based image matching relies on the assumption that the features contained in the model are distinctive enough. When both model and data present a sizeable amount of clutter, the signal-to-noise ratio falls and the detection becomes more challenging. If such clutter exhibits a coherent structure, as it is the case for textured background, matching becomes even harder. In fact, the large amount of repeatable features extracted from the texture dims the strength of the relatively few interesting points of the object itself. In this paper we introduce a game-theoretic approach that allows to distinguish foreground features from background ones. In addition the same technique can be used to deal with the object matching itself. The whole procedure is validated by applying it to a practical scenario and by comparing it with a standard point-pattern matching technique.

In this paper we introduce a robust matching technique that allows very accurate selection of corresponding feature points from multiple views. Robustness is achieved by enforcing global geometric consistency at an early stage of the matching process, without the need of subsequent verification through reprojection. The global consistency is reduced to a pairwise compatibility making use of the size and orientation information provided by common feature descriptors, thus projecting what is a high-order compatibility problem into a pairwise setting. Then a game-theoretic approach is used to select a maximally consistent set of candidate matches, where highly compatible matches are enforced while incompatible correspondences are driven to extinction.

With this paper we offer a game-theoretic perspective for the all-pervasive matching problem in computer vision. Specifically, we formulate the matching problem as a (population) non-cooperative game where the potential associations between the items to be matched correspond to (pure) strategies, while payoffs reflect the degree of compatibility between competing hypotheses. Within this formulation, the solutions of the matching problem correspond to evolutionary stable states (ESS's), a robust population-based generalization of the notion of a Nash equilibrium. In order to find ESS's of our matching game, we propose using a novel, fast evolutionary game dynamics motivated by Darwinian selection processes, which let the pure strategies play against each other until an equilibrium is reached. A distinguishing feature of the proposed framework is that it allows one to naturally deal with general many-to-many matching problems even in the presence of asymmetric compatibilities. The potential of the proposed approach is demonstrated via two sets of image matching experiments, both of which show that our results outperform those obtained using well-known domain-specific algorithms.

This paper addresses the problem of learning archetypal structural models from examples. This is done by providing a generative model for graphs where the distribution of observed nodes and edges is governed by a set of independent Bernoulli trials with parameters to be estimated, however, the correspondences between sample node and model nodes is not known and must be estimated from local structure. The parameters are estimated maximizing the likelihood of the observed graphs, marginalizing it over all possible node correspondences. This is done adopting an importance sampling approach to limit the exponential explosion of the set of correspondences. The approach is used to summarize the variation in two different structural abstraction of shape: Delaunay graph over a set of image features and shock graphs. The experiments show that the approach can be used to recognize structures belonging to a same class.

A problem commonly encountered in Computer Vision is the recovery of the transformation parameters between two affinely distorted images. In this paper, we propose a novel feature-based approach that casts the matching problem to the search of a maximum clique over an auxiliary hypergraph. We also introduce a continuous-based characterization of cliques in hypergraphs that allows us to handle the hard combinatorial problem using tools from the continuous domain. Finally, we present experimental result and comparisons with a state-of-the-art algorithm.

The field of pairwise clustering is currently dominated by the idea of dividing a set of objects into disjoints classes, thereby giving rise to (hard) partitions of the input data. However, in many computer vision and pattern recognition problems this approach is too restrictive as objects might reasonably belong to more than one class. In this paper, we adopt a game-theoretic perspective to the iterative extraction of possibly overlapping clusters: Game dynamics are used to locate individual groups, and after each extraction the similarity matrix is transformed in such a way as to make the located cluster unstable under the dynamics, without affecting the remaining groups.

This paper addresses the problem of learning archetypal structural models from examples. To this end we define a generative model for graphs where the distribution of observed nodes and edges is governed by a set of independent Bernoulli trials with parameters to be estimated from data in a situation where the correspondences between the nodes in the data graphs and the nodes in the model are not not known ab initio and must be estimated from local structure. This results in an EM-like approach where we alternate the estimation of the node correspondences with the estimation of the model parameters. Parameter estimation and model order selection is addressed within a Minimum Message Length (MML) framework. 1

Pairwise grouping and clustering approaches have traditionally worked under the assumption that the similarities or compatibilities between the elements to be grouped are symmetric. However, asymmetric compatibilities arise naturally in many areas of computer vision and pattern recognition. Hence, there is a need for a new generic approach to clustering and grouping that can deal with asymmetries in the compatibilities. In this paper, we present a generic framework for grouping and clustering derived from a game-theoretic formalization of the competition between the hypotheses of group membership, and apply it to perceptual grouping. In the proposed approach groups correspond to evolutionary stable strategies, a classic notion in evolutionary game theory. We also provide a combinatorial characterization of the stable strategies, and, hence, of the elements that belong to a group. Experiments show that our approach outperforms both state-of-the-art clustering-based perceptual grouping approacheswith symmetric compatibilities, and other approaches explicitly designed to make use of asymmetric compatibilities.

Evolutionary game-theoretic models and, in particular, the so-called replicator equations have recently proven to be remarkably effective at approximately solving the maximum clique and related problems. The approach is centered around a classic result from graph theory that formulates the maximum clique problem as a standard (continuous) quadratic program and exploits the dynamical properties of these models, which, under a certain symmetry assumption, possess a Lyapunov function. In this letter, we generalize previous work along these lines in several respects. We introduce a wide family of game-dynamic equations known as payoff-monotonic dynamics, of which replicator dynamics are a special instance, and show that they enjoy precisely the same dynamical properties as standard replicator equations. These properties make any member of this family a potential heuristic for solving standard quadratic programs and, in particular, the maximum clique problem. Extensive simulations, performed on random as well as DIMACS benchmark graphs, show that this class contains dynamics that are considerably faster than and at least as accurate as replicator equations. One problem associated with these models, however, relates to their inability to escape from poor local solutions. To overcome this drawback, we focus on a particular subclass of payoff-monotonic dynamics used to model the evolution of behavior via imitation processes and study the stability of their equilibria when a regularization parameter is allowed to take on negative values. A detailed analysis of these properties suggests a whole class of annealed imitation heuristics for the maximum clique problem, which are based on the idea of varying the parameter during the imitation optimization process in a principled way, so as to avoid unwanted inefficient solutions. Experiments show that the proposed annealing procedure does help to avoid poor local optima by initially driving the dynamics toward promising regions in state space. Furthermore, the models outperform state-of-the-art neural network algorithms for maximum clique, such as mean field annealing, and compare well with powerful continuous-based heuristics.

This paper poses the problem of tree-clustering as that of fitting a mixture of tree unions to a set of sample trees. The tree-unions are structures from which the individual data samples belonging to a cluster can be obtained by edit operations. The distribution of observed tree nodes in each cluster sample is assumed to be governed by a Bernoulli distribution. The clustering method is designed to operate when the correspondences between nodes are unknown and must be inferred as part of the learning process. We adopt a minimum description length approach to the problem of fitting the mixture model to data. We make maximum-likelihood estimates of the Bernoulli parameters. The tree-unions and the mixing proportions are sought so as to minimize the description length criterion. This is the sum of the negative logarithm of the Bernoulli distribution, and a message-length criterion that encodes both the complexity of the union-trees and the number of mixture components. We locate node correspondences by minimizing the edit distance with the current tree unions, and show that the edit distance is linked to the description length criterion. The method can be applied to both unweighted and weighted trees. We illustrate the utility of the resulting algorithm on the problem of classifying 2D shapes using a shock graph representation.

The Hamilton-Jacobi approach has proven to be a powerful and elegant method for extracting the skeleton of two-dimensional (2-D) shapes. The approach is based on the observation that the normalized flux associated with the inward evolution of the object boundary at nonskeletal points tends to zero as the size of the integration area tends to zero, while the flux is negative at the locations of skeletal points. Nonetheless, the error in calculating the flux on the image lattice is both limited by the pixel resolution and also proportional to the curvature of the boundary evolution front and, hence, unbounded near endpoints. This makes the exact location of endpoints difficult and renders the performance of the skeleton extraction algorithm dependent on a threshold parameter. This problem can be overcome by using interpolation techniques to calculate the flux with subpixel precision. However, here, we develop a method for 2-D skeleton extraction that circumvents the problem by eliminating the curvature contribution to the error. This is done by taking into account variations of density due to boundary curvature. This yields a skeletonization algorithm that gives both better localization and less susceptibility to boundary noise and parameter choice than the Hamilton-Jacobi method.

We address the problem of comparing attributed trees and propose four novel distance measures centered around the notion of a maximal similarity common subtree. The proposed measures are general and defined on trees endowed with either symbolic or continuous-valued attributes and can be applied to rooted as well as unrooted trees. We prove that our measures satisfy the metric constraints and provide a polynomial-time algorithm to compute them. This is a remarkable and attractive property, since the computation of traditional edit-distance-based metrics is, in general, NP-complete, at least in the unordered case. We experimentally validate the usefulness of our metrics on shape matching tasks and compare them with (an approximation of) edit-distance.

The Hamilton-Jacobi approach has proved to be a powerful and elegant method for extracting the skeleton of a shape. The approach is based on the fact that the inward evolving boundary flux is conservative everywhere except at skeletal points. Nonetheless this method appears to overlook the fact that the linear density of the evolving boundary front is not constant where the front is curved. In this paper we present an analysis, which takes into account variations of density due to boundary curvature. This yields a skeletonization algorithm that is both better localized and less susceptible to boundary noise than the Hamilton-Jacobi method.

The Hamilton-Jacobi approach has proved to be a powerful and elegant method for extracting the skeleton of a shape. The approach is based on the fact that the dynamics of the inward evolving boundary is conservative everywhere except at skeletal points. Nonetheless this method appears to overlook the fact that the linear density of the evolving boundary front is not constant where the front is curved. In this paper we present an analysis which takes into account variations of density due to boundary curvature. This yields a skeletonization algorithm that is both better localized and less susceptible to boundary noise than the Hamilton-Jacobi method.

The paper describes a probabilistic framework for graph clustering. We commence from a set of pairwise distances between graph structures. From this set of distances, we use a mixture model to characterize the pairwise affinity of the different graphs. We present an EM-like algorithm for clustering the graphs by iteratively updating the elements of the affinity matrix. In the M-step we apply eigendcomposition to the affinity matrix to locate the principal clusters. In the M-step we update the affinity probabilities. We apply the resulting unsupervised clustering algorithm to two practical problems. The first of these involves locating shape-categories using shock trees extracted from 2D silhouettes. The second problem involves finding the view structure of a polyhedral object using the Delaunay triangulation of corner features.

This paper investigates whether meaningful shape categories can be identified in an unsupervised way by clustering shock-trees. We commence by computing weighted and unweighted edit distances between shock-trees extracted from the Hamilton-Jacobi skeleton of 2D binary shapes. Next we use an EM-like algorithm to locate pairwise clusters in the pattern of edit-distances. We show that when the tree edit distance is weighted using the geometry of the skeleton, then the clustering method returns meaningful shape categories.