| ||||||||||||||||||||
|
 |
L. Wang, A. Gehre, M. M. Bronstein, J. Solomon,
"Kernel functional maps",
Computer Graphics Forum, 2018. (conditionally accepted) Abstract: Functional maps provide a means of extracting correspondences between surfaces using linear-algebraic machinery. While the functional framework suggests efficient algorithms for map computation, the basic technique does not incorporate the intuition that pointwise modifications of a descriptor function (e.g. composition of a descriptor and a nonlinearity) should be preserved under the mapping; the end result is that the basic functional maps problem can be underdetermined without regularization or additional assumptions on the map. In this paper, we show how this problem can be addressed through kernelization, in which descriptors are lifted to higher-dimensional vectors or even infinite-length sequences of values. The key observation is that optimization problems for functional maps only depend on inner products between descriptors rather than descriptor values themselves. These inner products can be evaluated efficiently through use of kernel functions. In addition to deriving a kernelized version of functional maps including a recent extension in terms of pointwise multiplication operators, we provide an efficient conjugate gradient algorithm for optimizing our generalized problem as well as a strategy for low-rank estimation of kernel matrices through the Nyström approximation. |
||||||||||||||||||
|
|
A. Gehre, M. M. Bronstein, L. Kobbelt, J. Solomon,
"Interactive curve constrained functional maps",
Computer Graphics Forum, 2018. (conditionally accepted) Abstract: Functional maps have gained popularity as a versatile framework for representing intrinsic correspondence between 3D shapes using algebraic machinery. A key ingredient for this framework is the ability to find pairs of corresponding functions (typically, feature descriptors) across the shapes. This is a challenging problem on its own, and when the shapes are strongly non-isometric, nearly impossible to solve automatically. In this paper, we use feature curve correspondences to provide flexible abstractions of semantically similar parts of non-isometric shapes. We design a user interface implementing an interactive process for constructing shape correspondence, allowing the user to update the functional map at interactive rates by introducing feature curve correspondences. We add feature curve preservation constraints to the functional map framework and propose an efficient numerical method to optimize the map with immediate feedback. Experimental results show that our approach establishes correspondences between geometrically diverse shapes with just a few clicks. |
||||||||||||||||||
|
|
D. Nongeng, S. Melzi, E. Rodolà, U. Castellani, M. M. Bronstein, M. Ovsjanikov,
"Improved functional mappings via product preservation",
Computer Graphics Forum, Vol. 37(2), 2018. Abstract: functional map representation. Our main observation is that in addition to the vector space structure of the functional spaces, which has been heavily exploited in the functional map framework, the functional algebra (i.e., the ability to take pointwise products of functions) can significantly extend the power of this framework. Equipped with this observation, we show how to improve one of the key applications of functional maps, namely transferring real-valued functions without conversion to point-to-point correspondences. We demonstrate through extensive experiments that by decomposing a given function into a linear combination consisting not only of basis functions but also of their pointwise products, both the representation power and the quality of the function transfer can be improved significantly. Our modification, while computationally simple, allows us to achieve higher transfer accuracy while keeping the size of the basis and the functional map fixed. We also analyze the computational complexity of optimally representing functions through linear combinations of products in a given basis and prove NP-completeness in some general cases. Finally, we argue that the use of function products can have a wide-reaching effect in extending the power of functional maps in a variety of applications, in particular by enabling the transfer of high frequency functions without changing the representation size or complexity. |
||||||||||||||||||
|
|
S. Melzi, E. Rodolà, U. Castellani, M. M. Bronstein,
"Localized manifold harmonics for spectral shape analysis",
Computer Graphics Forum, 2017. Abstract: The use of Laplacian eigenfunctions is ubiquitous in a wide range of computer graphics and geometry processing applications. In particular, Laplacian eigenbases allow generalizing the classical Fourier analysis to manifolds. A key drawback of such bases is their inherently global nature, as the Laplacian eigenfunctions carry geometric and topological structure of the entire manifold. In this paper, we introduce a new framework for local spectral shape analysis. We show how to efficiently construct localized orthogonal bases by solving an optimization problem that in turn can be posed as the eigendecomposition of a new operator obtained by a modification of the standard Laplacian. We study the theoretical and computational aspects of the proposed framework and showcase our new construction on the classical problems of shape approximation and correspondence. We obtain significant improvement compared to classical Laplacian eigenbases as well as other alternatives for constructing localized bases. Code |
||||||||||||||||||
|
|
M. M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, P. Vandergheynst,
"Geometric deep learning: going beyond Euclidean data",
IEEE Signal Processing Magazine, Vol. 34(4), pp. 18-42, 2017. Abstract: Many scientific fields study data with an underlying structure that is a non-Euclidean space. Some examples include social networks in computational social sciences, sensor networks in communications, functional networks in brain imaging, regulatory networks in genetics, and meshed surfaces in computer graphics. In many applications, such geometric data are large and complex (in the case of social networks, on the scale of billions), and are natural targets for machine learning techniques. In particular, we would like to use deep neural networks, which have recently proven to be powerful tools for a broad range of problems from computer vision, natural language processing, and audio analysis. However, these tools have been most successful on data with an underlying Euclidean or grid-like structure, and in cases where the invariances of these structures are built into networks used to model them. Geometric deep learning is an umbrella term for emerging techniques attempting to generalize (structured) deep neural models to non-Euclidean domains such as graphs and manifolds. The purpose of this paper is to overview different examples of geometric deep learning problems and present available solutions, key difficulties, applications, and future research directions in this nascent field. |
||||||||||||||||||
|
|
O. Litany, E. Rodolà, A. M. Bronstein, M. M. Bronstein,
"Fully spectral partial shape matching",
Computer Graphics Forum, Vol. 36(2), 2017. Presented at EUROGRAPHICS. Abstract: We propose an efficient procedure for calculating partial dense intrinsic correspondence between deformable shapes performed entirely in the spectral domain. Our technique relies on the recently introduced partial functional maps formalism and on the joint approximate diagonalization (JAD) of the Laplace-Beltrami operators previously introduced for matching non-isometric shapes. We show that a variant of the JAD problem with an appropriately modified coupling term (surprisingly) allows to construct quasi-harmonic bases localized on the latent corresponding parts. This circumvents the need to explicitly compute the unknown parts by means of the cumbersome alternating minimization used in the previous approaches, and allows performing all the calculations in the spectral domain with constant complexity independent of the number of shape vertices. We provide an extensive evaluation of the proposed technique on standard non-rigid correspondence benchmarks and show state-of-the-art performance in various settings, including partiality and the presence of topological noise. Code |
||||||||||||||||||
|
|
O. Litany, E. Rodolà, A. M. Bronstein, M. M. Bronstein, D. Cremers,
"Non-rigid puzzles",
Computer Graphics Forum, Vol. 35(5), pp. 135-143, 2016. Presented at SGP. Best Paper Award Abstract: Shape correspondence is a fundamental problem in computer graphics and vision, with applications in various problems including animation, texture mapping, robotic vision, medical imaging, archaeology and many more. In settings where the shapes are allowed to undergo non-rigid deformations and only partial views are available, the problem becomes very challenging. To this end, we present a non-rigid multi-part shape matching algorithm. We assume to be given a reference shape and its multiple parts undergoing a non-rigid deformation. Each of these query parts can be additionally contaminated by clutter, may overlap with other parts, and there might be missing parts or redundant ones. Our method simultaneously solves for the segmentation of the reference model, and for a dense correspondence to (subsets of) the parts. Experimental results on synthetic as well as real scans demonstrate the effectiveness of our method in dealing with this challenging matching scenario. Code |
||||||||||||||||||
|
|
D. Boscaini, J. Masci, E. Rodolà, M. M. Bronstein, D. Cremers,
"Anisotropic diffusion descriptors",
Computer Graphics Forum 35(2), pp. 431-441, 2016. Presented at EUROGRAPHICS Abstract: Spectral geometric structures are intrinsic and thus invariant to isometric deformations, are efficiently computed, and can be constructed on shapes in different representations. A notable drawback of these constructions, however, is that they are isotropic, i.e., insensitive to direction. In this paper, we show how to construct direction-sensitive spectral feature descriptors using anisotropic diffusion on meshes and point clouds. The core of our construction are directed local kernels acting similarly to steerable filters, which are learned in a task-specific manner. Remarkably, while being intrinsic, our descriptors allow to disambiguate reflection symmetries. We show the application of anisotropic descriptors for problems of shape correspondence on meshes and point clouds, achieving results significantly better than state-of-the-art methods. |
||||||||||||||||||
|
|
E. Rodolà, L. Cosmo, M. M. Bronstein, A. Torsello, D. Cremers,
"Partial functional correspondence", Computer Graphics Forum, Vol. 36(1), 2017. Presented at SGP 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. |
||||||||||||||||||
|
|
D. Pickup, X. Sun, P. L. Rosin, R. R. Martin, Z. Cheng, Z. Lian, M. Aono, A. Ben Hamza, A. M. Bronstein, M. M. Bronstein, S. Bu, U. Castellani, S. Cheng, V. Garro, A. Giachetti, A. Godil, J. Han, H. Johan, L. Lai, B. Li, C. Li, H. Li, R. Litman, X. Liu, Z. Liu, Y. Lu, A. Tatsuma, J. Ye,
"Shape retrieval of non-rigid 3D human models",
Intl. Journal of Computer Vision (IJCV), Vol. 120(2), pp. 169-193, 2016. Abstract: 3D models of humans are commonly used within computer graphics and vision, and so the ability to distinguish between body shapes is an important shape retrieval problem. We extend our recent paper which provided a benchmark for testing non-rigid 3D shape retrieval algorithms on 3D human models. This benchmark provided a far stricter challenge than previous shape benchmarks.We have added 145 new models for use as a separate training set, in order to standardise the training data used and provide a fairer comparison. We have also included experiments with the FAUST dataset of human scans. All participants of the previous benchmark study have taken part in the new tests reported here, many providing updated results using the new data. In addition, further participants have also taken part, and we provide extra analysis of the retrieval results. A total of 25 different shape retrieval methods are compared. |
||||||||||||||||||
|
|
S. Biasotti, A. Cerri, A. M. Bronstein, M. M. Bronstein,
"Recent trends, applications, and perspectives in 3D shape similarity assessment", Computer Graphics Forum, Vol. 35(6), pp. 87-119, 2016. Abstract: The recent introduction of 3D shape analysis frameworks able to quantify the deformation of a shape into another in terms of the variation of real functions yields a new interpretation of the 3D shape similarity assessment and opens new perspectives. Indeed, while the classical approaches to similarity mainly quantify it as a numerical score, map based methods also define (dense) shape correspondences. After presenting in detail the theoretical foundations underlying these approaches, we classify them by looking at their most salient features, including the kind of structure and invariance properties they capture, as well as the distances and the output modalities according to which the similarity between shapes is assessed and returned. We also review the usage of these methods in a number of 3D shape application domains, ranging from matching and retrieval to annotation and segmentation. Finally, the most promising directions for future research developments are discussed. |
||||||||||||||||||
|
|
D. Eynard, A. Kovnatsky, M. M. Bronstein, K. Glashoff, A. M. Bronstein,
"Multimodal manifold analysis using simultaneous diagonalization of Laplacians", IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI), Vol. 37/12, pp. 2505-2517, 2015. Abstract: We construct an extension of spectral and diffusion geometry to multiple modalities through simultaneous diagonalization of Laplacian matrices. This naturally extends classical data analysis tools based on spectral geometry, such as diffusion maps and spectral clustering. We provide several synthetic and real examples of manifold learning, retrieval, and clustering demonstrating that the joint spectral geometry frequently better captures the inherent structure of multi-modal data. We also show the relation of many previous approaches to multimodal manifold analysis to our framework, of which the can be seen as particular cases. |
||||||||||||||||||
|
|
D. Boscaini, J. Masci, S. Melzi, M. M. Bronstein, U. Castellani, P. Vandergheynst,
"Learning class-specific descriptors for deformable shapes
using localized spectral convolutional networks", Computer Graphics Forum, Vol. 34/5, pp. 13-23, 2015. Presented at SGP Abstract: In this paper, we propose a generalization of convolutional neural networks (CNN) to non-Euclidean domains for the analysis of deformable shapes. Our construction is based on localized frequency analysis (a generalization of the windowed Fourier transform to manifolds) that is used to extract the local behavior of some dense intrinsic descriptor, roughly acting as an analogy to patches in images. The resulting local frequency representations are then passed through a bank of filters whose coefficient are determined by a learning procedure minimizing a task-specific cost. Our approach generalizes several previous methods such as HKS, WKS, spectral CNN, and GPS embeddings. Experimental results show that the proposed approach allows learning class-specific shape descriptors significantly outperforming recent state-of-the-art methods on standard benchmarks. |
||||||||||||||||||
|
|
D. Boscaini, D. Eynard, D. Kourounis, M. M. Bronstein,
"Shape-from-Operator: recovering shapes from intrinsic operators", Computer Graphics Forum, Vol. 34/2, pp. 265-274, 2015. Presented at EUROGRAPHICS Abstract: We formulate the problem of shape-from-operator (SfO), recovering an embedding of a mesh from intrinsic operators defined through the discrete metric (edge lengths). Particularly interesting instances of our SfO problem include: shape-from-Laplacian, allowing to transfer style between shapes; shape-from-difference operator, used to synthesize shape analogies; and shape-from-eigenvectors, allowing to generate "intrinsic averages" of shape collections. Numerically, we approach the SfO problem by splitting it into two optimization sub-problems: metric-from-operator (reconstruction of the discrete metric from the intrinsic operator) and embedding-from-metric (finding a shape embedding that would realize a given metric, a setting of the multidimensional scaling problem). We study numerical properties of our problem, exemplify it on several applications, and discuss its imitations. |
||||||||||||||||||
|
|
R. Litman, A. M. Bronstein, M. M. Bronstein, U. Castellani,
"Supervised learning of bag-of-features shape descriptors using sparse coding", Computer Graphics Forum, Vol. 33/5, pp. 127-136, 2014. Presented at SGP Abstract: We present a method for supervised learning of shape descriptors for shape retrieval applications. Many content-based shape retrieval approaches follow the bag-of-features (BoF) paradigm commonly used in text and image retrieval by first computing local shape descriptors, and then representing them in a `geometric dictionary' using vector quantization. A major drawback of such approaches is that the dictionary is constructed in an unsupervised manner using clustering, unaware of the last stage of the process (pooling of the local descriptors into a BoF, and comparison of the latter using some metric). In this paper, we replace the clustering with dictionary learning, where every atom acts as a feature, followed by sparse coding and pooling to get the final BoF descriptor. Both the dictionary and the sparse codes can be learned in the supervised regime via bi-level optimization using a task-specific objective that promotes invariance desired in the specific application. We show signficant performance improvement on several standard shape retrieval benchmarks. |
||||||||||||||||||
|
|
D. Eynard, A. Kovnatsky, M. M. Bronstein,
"Laplacian colormaps: a framework
for structure-preserving color transformations", Computer Graphics Forum, Vol. 33/2, pp. 215-224, 2014. Presented at EUROGRAPHICS Abstract: Mappings between color spaces are ubiquitous in image processing problems such as gamut mapping, decolorization, and image optimization for color-blind people. Simple color transformations often result in information loss and ambiguities, and one wishes to find an image-specific transformation that would preserve as much as possible the structure of the original image in the target color space. In this paper, we propose Laplacian colormaps, a generic framework for structure-preserving color transformations between images. We use the image Laplacian to capture the structural information, and show that if the color transformation between two images preserves the structure, the respective Laplacians have similar eigenvectors, or in other words, are approximately jointly diagonalizable. Employing the relation between joint diagonalizability and commutativity of matrices, we use Laplacians commutativity as a criterion of color mapping quality and minimize it w.r.t. the parameters of a color transformation to achieve optimal structure preservation. We show numerous applications of our approach, including color-to-gray conversion, gamut mapping, multispectral image fusion, and image optimization for color deficient viewers. |
||||||||||||||||||
|
|
J. Masci, M. M. Bronstein, A. M. Bronstein, J. Schmidhuber,
"Multimodal similarity-preserving hashing", IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI), Vol. 36/4, pp. 824-830, April 2014. Abstract: We introduce an efficient computational framework for hashing data belonging to multiple modalities into a single representation space where they become mutually comparable. The proposed approach is based on a novel coupled siamese neural network architecture and allows unified treatment of intra- and inter-modality similarity learning. Unlike existing cross-modality similarity learning approaches, our hashing functions are not limited to binarized linear projections and can assume arbitrarily complex forms. We show experimentally that our method significantly outperforms state-of-the-art hashing approaches on multimedia retrieval tasks. |
||||||||||||||||||
|
|
D. Raviv, A. M. Bronstein, M. M. Bronstein, D. Weisman, N. Sochen, R. Kimmel,
"Equi-affine invariant geometry for shape analysis", Journal of Mathematical Imaging and Vision (JMIV), Vol. 50, pp. 144-163, 2014. Abstract: Traditional models of bendable surfaces are based on the exact or approximate invariance to deformations that do not tear or stretch the shape, leaving intact an intrinsic geometry associated with it. These geometries are typically defined using either the shortest path length (geodesic distance), or properties of heat diffusion (diffusion distance) on the surface. Both measures are implicitly derived from the metric induced by the ambient Euclidean space. In this paper, we depart from this restrictive assumption by observing that a different choice of the metric results in a richer set of geometric invariants. We apply equi-affine geometry for analyzing arbitrary shapes with effective Gaussian curvature. The potential of the proposed framework is explored in a range of applications such as shape matching and retrieval, symmetry detection, and computation of Voroni tessellation. We show that in some shape analysis tasks, equi-affine-invariant intrinsic geometries of- ten outperform their Euclidean-based counterparts. We further explore the potential of this metric in facial anthropometry of newborns. We show that intrinsic properties of this homogeneous group are better captured using the equi-affine metric. |
||||||||||||||||||
|
|
K. Glashoff, M. M. Bronstein,
"Matrix commutators: their asymptotic metric properties
and relation to approximate joint diagonalization", Linear Algebra and its Applications, Vol. 439/8, pp. 2503-2513, October 2013. Abstract: We analyze the properties of the norm of the commutator of two Hermitian matrices, showing that asymptotically it behaves like a metric, and establish its relation to joint approximate diagonalization of matrices, showing that almost-commuting matrices are almost jointly diagonalizable, and vice versa. We show an application of our results in the field of 3D shape analysis. |
||||||||||||||||||
|
|
J. Pokrass, A. M. Bronstein, M. M. Bronstein, P. Sprechmann, G. Sapiro,
"Sparse modeling of intrinsic correspondences", Computer Graphics Forum, Vol. 32, pp. 459-468, 2013. Presented at EUROGRAPHICS Abstract: We present a novel sparse modeling approach to non-rigid shape matching using only the ability to detect repeatable regions. As the input to our algorithm, we are given only two sets of regions in two shapes; no descriptors are provided so the correspondence between the regions is not know, nor we know how many regions correspond in the two shapes. We show that even with such scarce information, it is possible to establish very accurate correspondence between the shapes by using methods from the eld of sparse modeling, being this, the first non-trivial use of sparse models in shape correspondence. We formulate the problem of per- muted sparse coding, in which we solve simultaneously for an unknown permutation ordering the regions on two shapes and for an unknown correspondence in functional representation. We also propose a robust vari- ant capable of handling incomplete matches. Numerically, the problem is solved efficiently by alternating the solution of a linear assignment and a sparse coding problem. The proposed methods are evaluated qualitatively and quantitatively on standard benchmarks containing both synthetic and scanned objects. |
||||||||||||||||||
|
|
A. Kovnatsky, M. M. Bronstein, A. M. Bronstein, K. Glashoff, R. Kimmel,
"Coupled quasi-harmonic bases", Computer Graphics Forum, Vol. 32, pp. 439-448, 2013. Presented at EUROGRAPHICS Abstract: The use of Laplacian eigenbases has been shown to be fruitful in many computer graphics applications. Today, state-of-the-art approaches to shape analysis, synthesis, and correspondence rely on these natural harmonic bases that allow using classical tools from harmonic analysis on manifolds. However, many applications involving multiple shapes are obstacled by the fact that Laplacian eigenbases computed independently on different shapes are often incompatible with each other. In this paper, we propose the construction of common approximate eigenbases for multiple shapes using approximate joint diagonalization algorithms. We illustrate the benefits of the proposed approach on tasks from shape editing, pose transfer, correspondence, and similarity. |
||||||||||||||||||
|
|
J. Pokrass, A. M. Bronstein, M. M. Bronstein,
"Partial shape matching without point-wise correspondence", Numerical Mathematics: Theory, Methods and Applications, Vol. 6/1, pp. 223-244, 2013. Abstract: Partial similarity of shapes in a challenging problem arising in many important applications in computer vision, shape analysis, and graphics, e.g. when one has to deal with partial information and acquisition artifacts. The problem is especially hard when the underlying shapes are non-rigid and are given up to a deformation. Partial matching is usually approached by computing local descriptors on a pair of shapes and then establishing a point-wise non-bijective correspondence between the two, taking into account possibly different parts. In this paper, we introduce an alternative correspondence-less approach to matching fragments to an entire shape undergoing a non-rigid deformation. We use diffusion geometric descriptors and optimize over the integration domains on which the integral descriptors of the two parts match. The problem is regularized using the Mumford-Shah functional. We show an efficient discretization based on the Ambrosio-Tortorelli approximation generalized to triangular meshes and point clouds, and present experiments demonstrating the success of the proposed method. |
||||||||||||||||||
|
|
A. Kovnatsky, D. Raviv, M. M. Bronstein, A. M. Bronstein, R. Kimmel,
"Geometric and photometric data fusion in non-rigid shape analysis", Numerical Mathematics: Theory, Methods and Applications, Vol. 6/1, pp. 199-222, 2013. Abstract: In this paper, we explore the use of the diffusion geometry framework for the fusion of geometric and photometric information in local and global shape descriptors. Our construction is based on the definition of a diffusion process on the shape manifold embedded into a high-dimensional space where the embedding coordinates represent the photometric information. Experimental results show that such data fusion is useful in coping with different challenges of shape analysis where pure geometric and pure photometric methods fail. |
||||||||||||||||||
|
|
S. Marras, K. Hormann, M. M. Bronstein, R. Scateni, R. Scorpigno,
"Motion-based mesh segmentation using augmented silhouettes", Graphical Models, Vol. 74/4, pp. 164-172, 2012. Abstract: Motion-based segmentation, the problem of detecting rigid parts of an articulated three-dimensional shape, is an open challenge that has several applications in mesh animation, compression, and interpolation. We present a novel approach that uses the visual perception of the shape and its motion to distinguish the rigid from the deformable parts of the object. Using two-dimensional projections of the different shape poses with respect to a number of different view points, we derive a set of one-dimensional curves, which form a superset of the mesh silhouettes. Analysing these augmented silhouettes, we identify the vertices of the mesh that correspond to the deformable parts, and a subsequent clustering approach, which is based on the diffusion distance, yields a motion-based segmentation of the shape. |
||||||||||||||||||
|
|
R. Litman, A. M. Bronstein, M. M. Bronstein,
"Stable volumetric features in deformable shapes", Computers & Graphics, Vol. 36/3, pp. 569-576, 2012. Abstract: Region feature detectors and descriptors have become a successful and popular alternative to point descriptors in image analysis due to their high robustness and repeatability, leading to a significant interest in the shape analysis community in finding analogous approaches in the 3D world. Recent works have successfully extended the maximally stable extremal region (MSER) detection algorithm to surfaces. In many applications, however, a volumetric shape model is more appropriate, and modeling shape deformations as approximate isometries of the volume of an object, rather than its boundary, better captures natural behavior of non-rigid deformations. In this paper, we formulate a diffusion-geometric framework for volumetric stable component detection and description in deformable shapes. An evaluation of our method on the SHREC'11 feature detection benchmark and SCAPE human body scans shows its potential as a source of high-quality features. Examples demonstrating the drawbacks of surface stable components and the advantage of their volumetric counterparts are also presented. |
||||||||||||||||||
|
|
C. Strecha, A. M. Bronstein, M. M. Bronstein, P. Fua,
"LDAHash: improved matching with smaller descriptors", IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI), Vol. 34/1, pp. 66-78, January 2012. Abstract: SIFT-like local feature descriptors are ubiquitously employed in such computer vision applications as content-based retrieval, video analysis, copy detection, object recognition, photo-tourism, and 3D reconstruction from multiple views. Feature descriptors can be designed to be invariant to certain classes of photometric and geometric transformations, in particular, affine and intensity scale transformations. However, real transformations that an image can undergo can only be approximately modeled in this way, and thus most descriptors are only approximately invariant in practice. Secondly, descriptors are usually high-dimensional (e.g. SIFT is represented as a 128-dimensional vector). In large-scale retrieval and matching problems, this can pose challenges in storing and retrieving descriptor data. We propose mapping the descriptor vectors into the Hamming space, in which the Hamming metric is used to compare the resulting representations. This way, we reduce the size of the descriptors by representing them as short binary strings and learn descriptor invariance from examples. We show extensive experimental validation, demonstrating the advantage of the proposed approach. Code | Data |
||||||||||||||||||
|
|
R. Kimmel, C. Zhang, A. M. Bronstein, M. M. Bronstein,
"Are MSER features really interesting?", IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI), Vol. 33/11, pp. 2316-2320, November 2011. Abstract: Detection and description of affine-invariant features is a cornerstone component in numerous computer vision applications. In this note, we analyze the notion of maximally stable extremal regions (MSER) through the prism of the curvature scale space, and conclude that in its original definition, MSER prefers regular (round) regions. Arguing that interesting features in natural images usually have irregular shapes, we propose alternative definitions of MSER which are free of this bias, yet maintain their invariance properties. |
||||||||||||||||||
|
|
R. Litman, A. M. Bronstein, M. M. Bronstein,
"Diffusion-geometric maximally stable component detection in deformable shapes", Computers & Graphics, Vol. 35/3, pp. 549-560, June 2011. Abstract: Maximally stable component detection is a very popular method for feature analysis in images, mainly due to its low computation cost and high repeatability. With the recent advance of feature-based methods in geometric shape analysis, there is significant interest in finding analogous approaches in the 3D world. In this paper, we formulate a diffusion-geometric framework for stable component detection in non-rigid 3D shapes, which can be used for geometric feature detection and description. A quantitative evaluation of our method on the SHREC'10 feature detection benchmark shows its potential as a source of high-quality features. Code |
||||||||||||||||||
|
|
D. Raviv, A. M. Bronstein, M. M. Bronstein, R. Kimmel, N. Sochen,
"Affine-invariant geodesic geometry of deformable 3D shapes", Computers & Graphics, Vol. 35/3, pp. 692-697, June 2011. Abstract: Natural objects can be subject to various transformations yet still preserve properties that we refer to as invariants. Here, we use definitions of affine invariant arclength for surfaces in R3 in order to extend the set of existing non-rigid shape analysis tools. In fact, we show that by re-defining the surface metric as its equi-affine version, the surface with its modified metric tensor can be treated as a canonical Euclidean object on which most classical Euclidean processing and analysis tools can be applied. The new definition of a metric is used to extend the fast marching method technique for computing geodesic distances on surfaces, where now, the distances are defined with respect to an affine invariant arclength. Applications of the proposed framework demonstrate its invariance, efficiency, and accuracy in shape analysis. |
||||||||||||||||||
|
|
M. M. Bronstein,
"Lazy sliding window implementation of the bilateral filter on parallel architectures", IEEE Trans. Image Processing, Vol. 20/6, pp. 1751-1756, June 2011. Abstract: Bilateral filter is one of the state-of-the-art methods for noise reduction in images. The plausible visual result the filter produces makes it a common choice for image and video processing applications, yet, its high computational complexity makes a real-time implementation a challenging task. Presented here is a highly-parallel version of the bilateral filter using a lazy sliding window, suitable for SIMD-type architectures. |
||||||||||||||||||
|
|
M. M. Bronstein, A. M. Bronstein,
"Shape recognition with spectral distances", IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI), Vol. 33/5, pp. 1065-1071, May 2011. Abstract: Recent works have shown the use of diffusion geometry for various pattern recognition applications, including non-rigid shape analysis. In this paper, we introduce spectral shape distance as a general framework for distribution-based shape similarity and show that two recent methods for shape similarity due to Rustamov and Mahmoudi & Sapiro are particular cases thereof. |
||||||||||||||||||
|
|
A. M. Bronstein, M. M. Bronstein, M. Ovsjanikov, L. J. Guibas,
"Shape Google: geometric words and expressions for invariant shape retrieval", ACM Trans. Graphics, Vol. 30/1, pp. 1-20, January 2011. Presented at SIGGRAPH TOG cover Abstract: The computer vision and pattern recognition communities have recently witnessed a surge of feature-based methods in object recognition and image retrieval applications. These methods allow representing images as collections of "visual words" and treat them using text search approaches following the "bag of features" paradigm. In this paper, we explore analogous approaches in the 3D world applied to the problem of non-rigid shape retrieval in large databases. Using multiscale diffusion heat kernels as "geometric words", we construct compact and informative shape descriptors by means of the "bag of features" approach. We also show that considering pairs of geometric words ("geometric expressions") allows creating spatially-sensitive bags of features with better discriminativity. Finally, adopting metric learning approaches, we show that shapes can be efficiently represented as binary codes. Our approach achieves state-of-the-art results on the SHREC 2010 large-scale shape retrieval benchmark. |
||||||||||||||||||
|
|
A. M. Bronstein, M. M. Bronstein, R. Kimmel, M. Mahmoudi, G. Sapiro,
"A Gromov-Hausdorff framework with diffusion geometry for topologically-robust non-rigid shape matching", Intl. Journal of Computer Vision (IJCV), Vol. 89/2-3, pp. 266-286, September 2010. Abstract: In this paper, the problem of non-rigid shape recognition is viewed from the perspective of metric geometry, and the applicability of diffusion distances within the Gromov-Hausdorff framework is explored. While the commonly used geodesic distance exploits the shortest path between points on the surface, the diffusion distance averages all paths connecting between the points. The diffusion distance provides an intrinsic distance measure which is robust, in particular to topological changes. Such changes may be a result of natural non-rigid deformations, as well as acquisition noise, in the form of holes or missing data, and representation noise due to inaccurate mesh construction. The presentation of the proposed framework is complemented with numerous examples demonstrating that in addition to the relatively low complexity involved in the computation of the diffusion distances between surface points, its recognition and matching performances favorably compare to the classical geodesic distances in the presence of topological changes between the non-rigid shapes. |
||||||||||||||||||
|
|
G. Rosman, M. M. Bronstein, A. M. Bronstein, R. Kimmel,
"Nonlinear dimensionality reduction by topologically constrained isometric embedding",
Intl. Journal of Computer Vision (IJCV), Vol. 89/1, pp. 56-68, August 2010. Abstract: Many manifold learning procedures try to embed a given feature data into a flat space of low dimensionality while preserving as much as possible the metric in the natural feature space. The embedding process usually relies on distances between neighboring features, mainly since distances between features that are far apart from each other often provide an unreliable estimation of the true distance on the feature manifold due to its non-convexity. Distortions resulting from using long geodesics indiscriminantly lead to a known limitation of the Isomap algorithm when used to map non-convex manifolds. Presented is a framework for nonlinear dimensionality reduction that uses both local and global distances in order to learn the intrinsic geometry of flat manifolds with boundaries. The resulting algorithm filters out potentially problematic distances between distant feature points based on the properties of the geodesics connecting those points and their relative distance to the boundary of the feature manifold, thus avoiding an inherent limitation of the Isomap algorithm. Since the proposed algorithm matches non-local structures, it is robust to strong noise. We show experimental results demonstrating the advantages of the proposed approach over conventional dimensionality reduction techniques, both global and local in nature. |
||||||||||||||||||
|
|
D. Raviv, A. M. Bronstein, M. M. Bronstein, R. Kimmel,
"Full and partial symmetries of non-rigid shapes", Intl. Journal of Computer Vision (IJCV), Vol. 89/1, pp. 18-39, August 2010. Abstract: Symmetry and self-similarity is the cornerstone of Nature, exhibiting itself through the shapes of natural creations and ubiquitous laws of physics. Since many natural objects are symmetric, the absence of symmetry can often be an indication of some anomaly or abnormal behavior. Therefore, detection of asymmetries is important in numerous practical applications, including crystallography, medical imaging, and face recognition, to mention a few. Conversely, the assumption of underlying shape symmetry can facilitate solutions to many problems in shape reconstruction and analysis. Traditionally, symmetries are described as extrinsic geometric properties of the shape. While being adequate for rigid shapes, such a description is inappropriate for non-rigid ones. Extrinsic symmetry can be broken as a result of shape deformations, while its intrinsic symmetry is preserved. In this paper, we present a generalization of symmetries for non-rigid shapes and a numerical framework for their analysis. More specifically, we address the problems of symmetry detection and symmetry classification. |
||||||||||||||||||
|
|
A. M. Bronstein, M. M. Bronstein, A. M. Bruckstein, R. Kimmel,
"Partial similarity of objects, or how to compare a centaur to a horse", Intl. Journal of Computer Vision (IJCV), Vol. 84/2, pp. 163-183, 2009. Abstract: Similarity is one of the most important abstract concepts in human perception of the world. In computer vision, numerous applications deal with comparing objects observed in a scene with some a priori known patterns. Often, it happens that while two objects are not similar, they have large similar parts, that is, they are partially similar. Here, we present a novel approach to quantify partial similarity using the notion of Pareto optimality. We exemplify our approach on the problems of recognizing non-rigid geometric objects, images, and analyzing text sequences. 3D non-rigid shapes dataset |
||||||||||||||||||
|
|
A. M. Bronstein, M. M. Bronstein, Y. Carmon, R. Kimmel,
"Partial similarity of shapes using a statistical
significance measure", IPSJ Trans. Computer Vision and Application, Vol. 1, pp. 105-114, 2009. Invited paper Abstract: Partial matching of geometric structures is important in computer vision, pattern recognition and shape analysis applications. The problem consists of matching similar parts of shapes that may be dissimilar as a whole. Recently, it was proposed to consider partial similarity as a multi-criterion optimization problem trying to simultaneously maximize the similarity and the significance of the matching parts. A major challenge in that framework is providing a quantitative measure of the significance of a part of an object. Here, we define the significance of a part of a shape by its discriminative power with respect do a given shape database—that is, the uniqueness of the part. We define a point-wise significance density using a statistical weighting approach similar to the term frequency-inverse document frequency (tfidf) weighting employed in search engines. The significance measure of a given part is obtained by integrating over this density. Numerical experiments show that the proposed approach produces intuitive significant parts, and demonstrate an improvement in the performance of partial matching between shapes. |
||||||||||||||||||
|
|
A. M. Bronstein, M. M. Bronstein, R. Kimmel,
"Topology-invariant similarity of nonrigid shapes", Intl. Journal of Computer Vision (IJCV), Vol. 81/3, pp. 281-301, March 2009. Abstract: This paper explores the problem of similarity criteria between nonrigid shapes. Broadly speaking, such criteria are divided into intrinsic and extrinsic, the first referring to the metric structure of the object and the latter to how it is laid out in the Euclidean space. Both criteria have their advantages and disadvantages: extrinsic similarity is sensitive to nonrigid deformations, while intrinsic similarity is sensitive to topological noise. In this paper, we approach the problem from the perspective of metric geometry. We show that by unifying the extrinsic and intrinsic similarity criteria, it is possible to obtain a stronger topology-invariant similarity, suitable for comparing deformed shapes with different topology. We construct this new joint criterion as a tradeoff between the extrinsic and intrinsic similarity and use it as a set-valued distance. Numerical results demonstrate the efficiency of our approach in cases where using either extrinsic or intrinsic criteria alone would fail. |
||||||||||||||||||
|
|
O. Weber, Y. Devir, A. M. Bronstein, M. M. Bronstein, R. Kimmel,
"Parallel algorithms for approximation of distance maps on parametric surfaces", ACM Trans. Graphics, Vol. 27/4, October 2008. Presented at SIGGRAPH Abstract: We present an efficient O(n) numerical algorithm for first-order approximation of geodesic distances on geometry images, where n is the number of points on the surface. The structure of our algorithm allows efficient implementation on parallel architectures. Two implementations on a SIMD processor and on a GPU are discussed. Numerical results demonstrate up to four orders of magnitude improvement in execution time compared to the state-of-the-art algorithms. GPU code | SIGGRAPH'08 trailer |
||||||||||||||||||
|
|
A. M. Bronstein, M. M. Bronstein, A. M. Bruckstein, R. Kimmel,
"Analysis of two-dimensional non-rigid shapes", Intl. Journal of Computer Vision (IJCV), Vol. 78/1, pp. 67-88, June 2008. Abstract: Analysis of deformable two-dimensional shapes is an important problem, encountered in numerous pattern recognition, computer vision and computer graphics applications. In this paper, we address three major problems in the analysis of non-rigid shapes: similarity, partial similarity, and correspondence.We present an axiomatic construction of similarity criteria for deformation-invariant shape comparison, based on intrinsic geometric properties of the shapes, and show that such criteria are related to the Gromov-Hausdorff distance. Next, we extend the problem of similarity computation to shapes which have similar parts but are dissimilar when considered as a whole, and present a construction of set-valued distances, based on the notion of Pareto optimality. Finally, we show that the correspondence between non-rigid shapes can be obtained as a byproduct of the non-rigid similarity problem. As a numerical framework, we use the generalized multidimensional scaling (GMDS) method, which is the numerical core of the three problems addressed in this paper. 2D mythological creatures dataset |
||||||||||||||||||
|
|
A. M. Bronstein, M. M. Bronstein, R. Kimmel,
"Weighted distance maps computation on parametric three-dimensional manifolds", Journal of Computational Physics, Vol. 255/1, pp. 771-784, July 2007. Abstract: We propose an effcient computational solver for the eikonal equations on parametric three-dimensional manifolds. Our approach is based on the fast marching method for solving the eikonal equation in O(n log n) steps by numerically simulating wavefront propagation. The obtuse angle splitting problem is reformulated as a set of small integer linear programs, that can be solved in O(n). Numerical simulations demonstrate the accuracy of the proposed algorithm. |
||||||||||||||||||
|
|
A. M. Bronstein, M. M. Bronstein, R. Kimmel,
"Calculus of non-rigid surfaces for geometry and texture manipulation", IEEE Trans. Visualization and Computer Graphics, Vol 13/5, pp. 902-913, September-October 2007. Abstract: We present a geometric framework for automatically finding intrinsic correspondence between three-dimensional nonrigid objects. We model object deformation as near isometries and find the correspondence as the minimum-distortion mapping. A generalization of multidimensional scaling is used as the numerical core of our approach. As a result, we obtain the possibility to manipulate the extrinsic geometry and the texture of the objects as vectors in a linear space. We demonstrate our method on the problems of expression-invariant texture mapping onto an animated three-dimensional face, expression exaggeration, morphing between faces, and virtual body painting. |
||||||||||||||||||
|
|
A. M. Bronstein, M. M. Bronstein, R. Kimmel,
"Expression-invariant representation of faces", IEEE Trans. Image Processing, Vol. 16/1, pp. 188-197, January 2007. Abstract: Addressed here is the problem of constructing and analyzing expression-invariant representations of human faces. We demonstrate and justify experimentally a simple geometric model that allows to describe facial expressions as isometric deformations of the facial surface. The main step in the construction of expression-invariant representation of a face involves embedding of the facial intrinsic geometric structure into some convenient low-dimensional space. We study the influence of the embedding space geometry and dimensionality choice on the representation accuracy and argue that compared to its Euclidean counterpart, spherical embedding leads to notably smaller metric distortions. We experimentally support our claim showing that a smaller embedding error leads to better recognition. |
||||||||||||||||||
|
|
A. M. Bronstein, M. M. Bronstein, R. Kimmel,
"Efficient computation of isometry-invariant distances between surfaces", SIAM J. Scientific Computing, Vol. 28/5, pp. 1812-1836, 2006. Abstract: We present an efficient computational framework for isometry-invariant comparison of smooth surfaces. We formulate the Gromov-Hausdorff distance as a multidimensional scaling (MDS)-like continuous optimization problem. In order to construct an efficient optimization scheme, we develop a numerical tool for interpolating geodesic distances on a sampled surface from precomputed geodesic distances between the samples. For isometry-invariant comparison of surfaces in the case of partially missing data, we present the partial embedding distance, which is computed using a similar scheme. The main idea is finding a minimum-distortion mapping from one surface to another, while considering only relevant geodesic distances. We discuss numerical implementation issues and present experimental results that demonstrate its accuracy and efficiency. |
||||||||||||||||||
|
|
M. M. Bronstein, A. M. Bronstein, R. Kimmel, I. Yavneh, "Multigrid multidimensional scaling",
Numerical Linear Algebra with Applications (NLAA), Special issue on multigrid methods, Vol. 13/2-3, pp. 149-171, March-April 2006. Abstract: Multidimensional scaling (MDS) is a generic name for a family of algorithms that construct a configuration of points in a target metric space from information about inter-point distances measured in some other metric space. Large-scale MDS problems often occur in data analysis, representation and visualization. Solving such problems efficiently is of key importance in many applications. In this paper we present a multigrid framework for MDS problems. We demonstrate the performance of our algorithm on dimensionality reduction and isometric embedding problems, two classical problems requiring efficient large-scale MDS. Simulation results show that the proposed approach significantly outperforms conventional MDS algorithms. Multigrid MDS code | Tutorial |
||||||||||||||||||
|
|
A. M. Bronstein, M. M. Bronstein, R. Kimmel,
"Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching", Proc. National Academy of Sciences (PNAS), Vol. 103/5, pp. 1168-1172, January 2006. Abstract: An efficient algorithm for isometry-invariant matching of surfaces is presented. The key idea is computing the minimum-distortion mapping between two surfaces. For this purpose, we introduce the generalized multidimensional scaling, a computationally efficient continuous optimization algorithm for finding the least distortion embedding of one surface into another. The generalized multidimensional scaling algorithm allows for both full and partial surface matching. As an example, it is applied to the problem of expression- invariant three-dimensional face recognition. |
||||||||||||||||||
|
|
A. M. Bronstein, M. M. Bronstein, R. Kimmel,
"Three-dimensional face recognition",
Intl. Journal of Computer Vision (IJCV), Vol. 64/1, pp. 5-30, August 2005. Abstract: An expression-invariant 3D face recognition approach is presented. Our basic assumption is that facial expressions can be modelled as isometries of the facial surface. This allows to construct expression-invariant representations of faces using the canonical forms approach. The result is an efficient and accurate face recognition algorithm, robust to facial expressions that can distinguish between identical twins (the first two authors). We demonstrate a prototype system based on the proposed algorithm and compare its performance to classical face recognition methods. The numerical methods employed by our approach do not require the facial surface explicitly. The surface gradients field, or the surface metric, are sufficient for constructing the expression-invariant representation of any given face. It allows us to perform the 3D face recognition task while avoiding the surface reconstruction stage. |
||||||||||||||||||
|
|
A. M. Bronstein, M. M. Bronstein, M. Zibulevsky, Y. Y. Zeevi,
"Sparse ICA for blind separation of transmitted and reflected images",
Intl. Journal of Imaging Science and Technology (IJIST), Vol. 15/1, pp. 84-91, 2005. Abstract: We address the problem of recovering a scene recorded through a semireflecting medium (i.e. planar lens), with a virtual reflected image being superimposed on the image of the scene transmitted through the semirefelecting lens. Recent studies propose imaging through a linear polarizer at several orientations to estimate the reflected and the transmitted components in the scene. In this study we extend the sparse ICA (SPICA) technique and apply it to the problem of separating the image of the scene without having any a priori knowledge about its structure or statistics. Recent novel advances in the SPICA approach are discussed. Simulation and experimental results demonstrate the efficacy of the proposed methods. |
||||||||||||||||||
|
|
A. M. Bronstein, M. M. Bronstein, M. Zibulevsky,
"Quasi maximum likelihood blind deconvolution: super- an sub-Gaussianity versus consistency",
IEEE Trans. Signal Processing, Vol. 53/7, pp. 2576-2579, July 2005. Abstract: In this note we consider the problem of MIMO quasi maximum likelihood (QML) blind deconvolution. We examine two classes of estimators, which are commonly believed to be suitable for super- and sub-Gaussian sources. We state the consistency conditions and demonstrate a distribution, for which the studied estimators are unsuitable, in the sense that they are asymptotically unstable. |
||||||||||||||||||
|
|
A. M. Bronstein, M. M. Bronstein, M. Zibulevsky,
"Relative optimization for blind deconvolution", IEEE Trans. Signal Processing, Vol. 53/6, pp. 2018-2026, June 2005. Abstract: We propose a relative optimization framework for quasi maximum likelihood (QML) blind deconvolution and the relative Newton method as its particular instance. Special Hessian structure allows fast Newton system construction and solution, resulting in a fast-convergent algorithm with iteration complexity comparable to that of gradient methods. We also propose the use of rational IIR restoration kernels, which constitute a richer family of filters than the traditionally used FIR kernels. We discuss different choices of non-linear functions suitable for deconvolution of super- and sub-Gaussian sources, and formulate the conditions, under which the QML estimation is stable. Simulation results demonstrate the efficiency of the proposed methods. |
||||||||||||||||||
|
|
M. M. Bronstein, A. M. Bronstein, M. Zibulevsky, Y. Y. Zeevi,
"Blind deconvolution of images using optimal sparse representations",
IEEE Trans. Image Processing, Vol. 14/6, pp. 726-736, June 2005. Abstract: We propose a relative optimization framework for quasi maximum likelihood (QML) blind deconvolution and the relative Newton method as its particular instance. Special Hessian structure allows fast Newton system construction and solution, resulting in a fast-convergent algorithm with iteration complexity comparable to that of gradient methods. We also propose the use of rational IIR restoration kernels, which constitute a richer family of filters than the traditionally used FIR kernels. We discuss different choices of non-linear functions suitable for deconvolution of super- and sub-Gaussian sources, and formulate the conditions, under which the QML estimation is stable. Simulation results demonstrate the efficiency of the proposed methods. |
||||||||||||||||||
|
|
A. M. Bronstein, M. M. Bronstein, M. Zibulevsky,
"Blind source separation using block-coordinate relative Newton method",
Signal Processing, Vol. 84/8, pp. 1447-1459, August 2004. Abstract: Presented here is a generalization of the relative Newton method, recently proposed for quasi maximum likelihood blind source separation. Special structure of the Hessian matrix allows performing block-coordinate Newton descent, which significantly reduces the algorithm computational complexity and boosts its performance. Simulations based on artificial and real data showed that the separation quality using the proposed algorithm is superior compared to other accepted blind source separation methods. |
||||||||||||||||||
|
|
A. M. Bronstein, M. M. Bronstein, M. Zibulevsky, Y. Y. Zeevi,
"Optimal nonlinear line-of-flight estimation in positron emission tomography",
IEEE Trans. Nuclear Science, Vol. 50/3, pp. 421-426, June 2003. Abstract: We consider detection of high-energy photons in PET using thick scintillation crystals. Parallax effect and multiple Compton interactions such crystals significantly reduce the accuracy of conventional detection methods. In order to estimate the photon line of flight based on photomultiplier responses, we use asymptotically optimal nonlinear techniques, implemented by feedforward and radial basis function (RBF) neural networks. Incorporation of information about angles of incidence of photons, significantly improves accuracy of estimation. The proposed estimators are fast enough to perform detection, using conventional computers. Monte-Carlo simulation results show that our approach significantly outperforms the conventional Anger algorithm. |
||||||||||||||||||
|
|
M. M. Bronstein, A. M. Bronstein, M. Zibulevsky, H. Azhari,
"Reconstruction in ultrasound diffraction tomography using non-uniform FFT",
IEEE Trans. Medical Imaging, Vol. 21/11, pp. 1395-1401, November 2002. Abstract: We show an iterative reconstruction framework for diffraction ultrasound tomography. The use of broad-band illumination allows significant reduction of the number of projections compared to straight ray tomography. The proposed algorithm makes use of forward nonuniform fast Fourier transform (NUFFT) for iterative Fourier inversion. Incorporation of total variation regularization allows the reduction of noise and Gibbs phenomena while preserving the edges. The complexity of the NUFFT-based reconstruction is comparable to the frequencydomain interpolation (gridding) algorithm, whereas the reconstruction accuracy (in sense of the L2 and the Linf norm) is better. |
||||||||||||||||||
|
| ||||||||||||||||||||