Publications

Topics:
  1. P. Sprechmann, A. M. Bronstein, G. Sapiro, Real-time online singing voice separation from monaural recordings using robust low-rank modeling, Proc. Annual Conference of the Int'l Society for Music Information Retrieval (ISMIR), 2012 (Best poster presentation award) details

    Real-time online singing voice separation from monaural recordings using robust low-rank modeling

    P. Sprechmann, A. M. Bronstein, G. Sapiro
    Proc. Annual Conference of the Int'l Society for Music Information Retrieval (ISMIR), 2012 (Best poster presentation award)

    Separating the leading vocals from the musical accompaniment is a challenging task that appears naturally in several music processing applications. Robust principal component analysis (RPCA) has been recently employed to this problem producing very successful results. The method decomposes the signal into a low-rank component corresponding to the accompaniment with its repetitive structure, and a sparse component corresponding to the voice with its quasi-harmonic structure. In this paper, we first introduce a non-negative variant of RPCA, termed as robust low-rank non-negative matrix factorization (RNMF). This new framework better suits audio applications. We then propose two efficient feed-forward architectures that approximate the RPCA and RNMF with low latency and a fraction of the complexity of the original optimization method. These approximants allow incorporating elements of unsupervised, semi- and fully-supervised learning into the RPCA and RNMF frameworks. Our basic implementation shows several orders of magnitude speedup compared to the exact solvers with no performance degradation, and allows online and faster-than-real-time processing. Evaluation on the MIR-1K dataset demonstrates state-of-the-art performance.

    O. Litany, A. M. Bronstein, M. M. Bronstein, Putting the pieces together: regularized multi-shape partial matching, Proc. Workshop on Nonrigid Shape Analysis and Deformable Image Alignment (NORDIA), 2012 details

    Putting the pieces together: regularized multi-shape partial matching

    O. Litany, A. M. Bronstein, M. M. Bronstein
    Proc. Workshop on Nonrigid Shape Analysis and Deformable Image Alignment (NORDIA), 2012

    Multi-part shape matching in an important class of problems, arising in many fields such as computational archaeology, biology, geometry processing, computer graphics and vision. In this paper, we address the problem of simultaneous matching and segmentation of multiple shapes. We assume to be given a reference shape and multiple parts partially matching the reference. Each of these parts can have additional clutter, have overlap with other parts, or there might be missing parts. We show experimental results of efficient and accurate assembly of fractured synthetic and real objects.

    A. Kovnatsky, A. M. Bronstein, M. M. Bronstein, Stable spectral mesh filtering, Proc. Workshop on Nonrigid Shape Analysis and Deformable Image Alignment (NORDIA), 2012 details

    Stable spectral mesh filtering

    A. Kovnatsky, A. M. Bronstein, M. M. Bronstein
    Proc. Workshop on Nonrigid Shape Analysis and Deformable Image Alignment (NORDIA), 2012

    The rapid development of 3D acquisition technology has brought with itself the need to perform standard signal processing operations such as filters on 3D data. It has been shown that the eigenfunctions of the Laplace-Beltrami operator (manifold harmonics) of a surface play the role of the Fourier basis in the Euclidean space; it is thus possible to formulate signal analysis and synthesis in the manifold harmonics basis. In particular, geometry filtering can be carried out in the manifold harmonics domain by decomposing the embedding coordinates of the shape in this basis. However, since the basis functions depend on the shape itself, such filtering is valid only for weak (near all-pass) filters, and produces severe artifacts otherwise. In this paper, we analyze this problem and propose the fractional filtering approach, wherein we apply iteratively weak fractional powers of the filter, followed by the update of the basis functions. Experimental results show that such a process produces more plausible and meaningful results.

    I. Kokkinos, M. M. Bronstein, R. Litman, A. M. Bronstein, Intrinsic shape context descriptors for deformable shapes, Proc. Computer Vision and Pattern Recognition (CVPR), 2012 details

    Intrinsic shape context descriptors for deformable shapes

    I. Kokkinos, M. M. Bronstein, R. Litman, A. M. Bronstein
    Proc. Computer Vision and Pattern Recognition (CVPR), 2012

    In this work, we present intrinsic shape context (ISC) descriptors for 3D shapes. We generalize to surfaces the polar sampling of the image domain used in shape contexts; for this purpose, we chart the surface by shooting geodesic outwards from the point being analyzed; ‘angle’ is treated as tantamount to geodesic shooting direction, and radius as geodesic distance. To deal with orientation ambiguity, we exploit properties of the Fourier transform. Our charting method is intrinsic, i.e., invariant to isometric shape transformations. The resulting descriptor is a meta-descriptor that can be applied to any photometric or geometric property field defined on the shape, in particular, we can leverage recent developments in intrinsic shape analysis and construct ISC based on state-of-the-art dense shape descriptors such as heat kernel signatures. Our experiments demonstrate a notable improvement in shape matching on standard benchmarks.

    E. Rodolà, A. M. Bronstein, A. Albarelli, F. Bergamasco, A. Torsello, A game-theoretic approach to deformable shape matching, Proc. Computer Vision and Pattern Recognition (CVPR), 2012 details

    A game-theoretic approach to deformable shape matching

    E. Rodolà, A. M. Bronstein, A. Albarelli, F. Bergamasco, A. Torsello
    Proc. Computer Vision and Pattern Recognition (CVPR), 2012

    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 L1 relaxation 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.

    M. Spagnuolo, M. M. Bronstein, A. M. Bronstein, A. Ferreira (Eds.), Eurographics Workshop on 3D Object Retrieval, Eurographics Association, 2012, ISBN: 978-3-905674-36-1 details

    Eurographics Workshop on 3D Object Retrieval

    M. Spagnuolo, M. M. Bronstein, A. M. Bronstein, A. Ferreira (Eds.)
    Eurographics Association, 2012, ISBN: 978-3-905674-36-1

    This book contains the research work presented at fifth Eurographics Workshop on 3D Object Retrieval (3DOR) held in Cagliari, Italy on May 13, 2012. The 3DOR workshop series was started in Crete (2008), and then held in Munich (2009), Norrkoping (2010) and Llandudno (2011), always as a co-event of the Annual Conference of the European Association for Computer Graphics (Eurographics). All five such workshops are successful examples of international cooperation and the attendance demonstrates the relevance of focused topics. Demonstrating the increasing importance of the workshop, a record number of 23 papers were submitted this year. These papers were reviewed by an international Program Committee of 35 external experts in the area. Based on their recommendations, a selection of nine long papers was accepted for presentation at the workshop, giving an acceptance rate below 40%. Additionally, six poster presentations describing timely research results of high quality were included in the workshop program. Similarly to the previous editions of the 3DOR workshop, this year’s event hosted the seventh Shape Retrieval Contest (SHREC’12). The goal of the contest is to evaluate the effectiveness of 3D-shape retrieval algorithms, thus playing an important role in the evolution of 3D Object Retrieval research. SHREC’12 contributes to the proceedings with four additional papers that detail the results of the competition. We are grateful to the Eurographics association for their support, and to all reviewers for ensuring a high-quality program despite the tight schedule. Special thanks are also to Stefanie Behnke for her constant and timely attention. Finally, we hope that this workshop proves useful to all participants and sets the ground for long-term interaction, collaboration, and identification of future directions and potential problems in the field.

    R. Litman, A. M. Bronstein, M. M. Bronstein, Stable volumetric features in deformable shapes, Computers and Graphics (CAG), Vol. 36(5), 2012 details

    Stable volumetric features in deformable shapes

    R. Litman, A. M. Bronstein, M. M. Bronstein
    Computers and Graphics (CAG), Vol. 36(5), 2012

    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.

    G. Rosman, A. M. Bronstein, M. M. Bronstein, X.-C. Tai, R. Kimmel, Group-valued regularization for analysis of articulated motion, Proc. Workshop on Nonrigid Shape Analysis and Deformable Image Alignment (NORDIA), 2012 details

    Group-valued regularization for analysis of articulated motion

    G. Rosman, A. M. Bronstein, M. M. Bronstein, X.-C. Tai, R. Kimmel
    Proc. Workshop on Nonrigid Shape Analysis and Deformable Image Alignment (NORDIA), 2012

    We present a novel method for estimation of articulated motion in depth scans. The method is based on a framework for regularization of vector- and matrix- valued functions on parametric surfaces. We extend augmented-Lagrangian total variation regularization to smooth rigid motion cues on the scanned 3D surface obtained from a range scanner. We demonstrate the resulting smoothed motion maps to be a powerful tool in articulated scene understanding, providing a basis for rigid parts segmentation, with little prior assumptions on the scene, despite the noisy depth measurements that often appear in commodity depth scanners.

    P. Sprechmann, A. M. Bronstein, G. Sapiro, Learning efficient structured sparse models, Proc. Int'l Conf. on Machine Learning (ICML), 2012 details

    Learning efficient structured sparse models

    P. Sprechmann, A. M. Bronstein, G. Sapiro
    Proc. Int'l Conf. on Machine Learning (ICML), 2012

    We present a comprehensive framework for structured sparse coding and modeling extending the recent ideas of using learnable fast regressors to approximate exact sparse codes. For this purpose, we propose an efficient feed forward architecture derived from the iteration of the block-coordinate algorithm. This architecture approximates the exact structured sparse codes with a fraction of the complexity of the standard optimization methods. We also show that by using different training objective functions, the proposed learnable sparse encoders are not only restricted to be approximants of the exact sparse code for a pre-given dictionary, but can be rather used as full-featured sparse encoders or even modelers. A simple implementation shows several orders of magnitude speedup compared to the state-of-the-art exact optimization algorithms at minimal performance degradation, making the proposed framework suitable for real time and large-scale applications.

    A. Zabatani, A. M. Bronstein, Parallelized algorithms for rigid surface alignment on GPU, Proc. EUROGRAPHICS Workshop on 3D Object Retrieval (3DOR), 2012 details

    Parallelized algorithms for rigid surface alignment on GPU

    A. Zabatani, A. M. Bronstein
    Proc. EUROGRAPHICS Workshop on 3D Object Retrieval (3DOR), 2012

    Alignment and registration of rigid surfaces is a fundamental computational geometric problem with applications ranging from medical imaging, automated target recognition, and robot navigation just to mention a few. The family of the iterative closest point (ICP) algorithms introduced by Chen and Medioni and Besl and McKey and improved over the three decades that followed constitute a classical to the problem. However, with the advent of geometry acquisition technologies and applications they enable, it has become necessary to align in real time dense surfaces containing millions of points. The classical ICP algorithms, being essentially sequential procedures, are unable to address the need. In this study, we follow the recent work by Mitra et al. considering ICP from the point of view of point-to-surface Euclidean distance map approximation. We propose a variant of a k-d tree data structure to store the approximation, and show its efficient parallelization on modern graphics processors. The flexibility of our implementation allows using different distance approximation schemes with controllable trade-off between accuracy and complexity. It also allows almost straightforward adaptation to richer transformation groups. Experimental evaluation of the proposed approaches on a state-of-the-art GPU on very large datasets containing around 106 vertices shows real-time performance superior by up to three orders of magnitude compared to an efficient CPU-based version.

    G. Rosman, A. M. Bronstein, M. M. Bronstein, R. Kimmel, Articulated motion segmentation of point clouds by group-valued regularization, Proc. EUROGRAPHICS Workshop on 3D Object Retrieval (3DOR), 2012 details

    Articulated motion segmentation of point clouds by group-valued regularization

    G. Rosman, A. M. Bronstein, M. M. Bronstein, R. Kimmel
    Proc. EUROGRAPHICS Workshop on 3D Object Retrieval (3DOR), 2012

    Motion segmentation for articulated objects is an important topic of research. Yet such a segmentation should be as free as possible from underlying assumptions so as to fit general scenes and objects. In this paper we demonstrate an algorithm for articulated motion segmentation of 3D point clouds, free of any assumptions on the underlying model and yet firmly set in a well-defined variational framework. Results on scanned images show the generality of the proposed technique and its robustness to scanning artifacts and noise.

    A. Kovnatsky, M. M. Bronstein, A. M. Bronstein, D. Raviv, R. Kimmel, Affine-invariant photometric heat kernel signatures, Proc. EUROGRAPHICS Workshop on 3D Object Retrieval (3DOR), 2012 details

    Affine-invariant photometric heat kernel signatures

    A. Kovnatsky, M. M. Bronstein, A. M. Bronstein, D. Raviv, R. Kimmel
    Proc. EUROGRAPHICS Workshop on 3D Object Retrieval (3DOR), 2012

    In this paper, we explore the use of the diffusion geometry framework for the fusion of geometric and photometric information in local shape descriptors. Our construction is based on the definition of a modified metric, which combines geometric and photometric information, and then the diffusion process on the shape manifold is simulated. Experimental results show that such data fusion is useful in coping with shape retrieval experiments, where pure geometric and pure photometric methods fail. Apart from retrieval task the proposed diffusion process may be employed in other applications.

    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), 2012 details

    LDAHash: improved matching with smaller descriptors

    C. Strecha, A. M. Bronstein, M. M. Bronstein, P. Fua
    IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI), Vol. 34(1), 2012

    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.

    B. M. Bruckstein, B. ter haar Romeny, A. M. Bronstein, M. M. Bronstein (Eds.), Scale Space and Variational Methods in Computer Vision, Lecture Notes in Computer Science (LNCS) No. 6667, Springer, 2012, ISBN: 978-3-642-24784-2 details

    Scale Space and Variational Methods in Computer Vision

    B. M. Bruckstein, B. ter haar Romeny, A. M. Bronstein, M. M. Bronstein (Eds.)
    Lecture Notes in Computer Science (LNCS) No. 6667, Springer, 2012, ISBN: 978-3-642-24784-2

    The International Conference on Scale Space and Variational Methods in Computer Vision (SSVM 2011) is the third issue of the conference born in 2007 as the joint edition of the Scale-Space Conferences (since 1997, Utrecht) and the Workshop on Variational, Geometric, and Level set Methods (VLSM) that first took place in Vancouver in 2001. Previous issues in Ischia, Italy (2007) and Voss, Norway (2009) were very successful, materializing the hope of the first SSVM organizers, Prof. Sgallari, Murli and Paragios, that the conference would ‘become a reference in the domain’. This year, SSVM was held in Kibbutz Ein-Gedi, Israel – a unique place on the shores of the Dead Sea, the global minimum on earth. Despite its small size, Israel plays an important role on the worldwide scientific arena, and in particular in the fields on computer vision and image processing. Following the tradition of the previous SSVM conferences, we invited outstanding scientists to give keynote presentations. This year, it was our pleasure to welcome Prof. Haim Brezis (Université Pierre et Marie Curie, France), Dr. Remco Duits, (Eindhoven University, The Netherlands), Prof. Stèphane Mallat (École Polytechnique, France), and Prof. Joachim Weickert (Saarland University, Germany). Additionally, we had six review lectures on topics of broad interest, given by experts in the field, Profs. Philip Rosenau (Tel Aviv University, Israel), Jing Yuan (University of Western Ontario, Canada), Patrizio Frosini (University of Bologna, Italy), Radu Horaud (INRIA, France), Gérard Medioni (University of Southern California, USA), and Elisabetta Carlini (La Sapienza, Italy). Out of 78 submitted papers, 24 were selected to be presented orally and 44 as posters. Over 100 people attended the conference, representing countries from all over the world, including Austria, China, France, Germany, Hong-Kong, Israel, Italy, Japan, Korea, the Netherlands, Norway, Singapore, Slovakia, Switzerland, Turkey, and USA. We would like to thank the authors for their contributions, the members of the Program Committee for their dedication and timely review process, and to Yana Katz and Boris Princ for local arrangements and organization without which this conference would not be possible. Finally, our special thanks to the Technion Department of Computer Science, HP Laboratories Israel, Haifa, Rafael Ltd., Israel, BBK Technologies Ltd., Israel, and the European Community’s FP7 ERC/FIRST programs for their generous sponsorship.

    R. Litman, A. M. Bronstein, M. M. Bronstein, Stable semi-local features for non-rigid shapes, Chapter in Innovations for Shape Analysis: Models and Algorithms (M. Breuss, A. M. Bruckstein, P. Maragos Eds.), Springer, 2012 details

    Stable semi-local features for non-rigid shapes

    R. Litman, A. M. Bronstein, M. M. Bronstein
    Chapter in Innovations for Shape Analysis: Models and Algorithms (M. Breuss, A. M. Bruckstein, P. Maragos Eds.), Springer, 2012

    Feature-based analysis is becoming a very popular approach for geometric shape analysis. Following the success of this approach in image analysis, there is a growing interest in finding analogous methods in the 3D world. Maximally stable component detection is a low computation cost and high repeatability method for feature detection in images. In this study, a diffusion-geometry based framework for stable component detection is presented, which can be used for geometric feature detection in deformable shapes. The vast majority of studies of deformable 3D shapes models them as the two-dimensional boundary of the volume of the shape. Recent works have shown that a volumetric shape model is advantageous in numerous ways as it better captures the natural behavior of non-rigid deformations. We show that our framework easily adapts to this volumetric approach, and even demonstrates superior performance. A quantitative evaluation of our methods on the SHREC’10 and SHREC’11 feature detection benchmarks as well as qualitative tests on the SCAPE dataset show 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.

    G. Rosman, M. M. Bronstein, A. M. Bronstein, A. Wolf, R. Kimmel, Group-valued regularization for motion segmentation of articulated shapes, Chapter in Innovations for Shape Analysis: Models and Algorithms (M. Breuss, A. M. Bruckstein, P. Maragos Eds.), Springer, 2012 details

    Group-valued regularization for motion segmentation of articulated shapes

    G. Rosman, M. M. Bronstein, A. M. Bronstein, A. Wolf, R. Kimmel
    Chapter in Innovations for Shape Analysis: Models and Algorithms (M. Breuss, A. M. Bruckstein, P. Maragos Eds.), Springer, 2012

    Motion-based segmentation is an important tool for the analysis of articulated shapes. As such, it plays an important role in mechanical engineering, computer graphics, and computer vision. In this chapter, we study motion-based segmentation of 3D articulated shapes. We formulate motion-based surface segmentation as a piecewise-smooth regularization problem for the transformations between several poses. Using Lie-group representation for the transformation at each surface point, we obtain a simple regularized fitting problem. An Ambrosio-Tortorelli scheme of a generalized Mumford-Shah model gives us the segmentation functional without assuming prior knowledge on the number of parts or even the articulated nature of the object. Experiments on several standard datasets compare the results of the proposed method to state-of-the-art algorithms.

    A. M. Bronstein, M. M. Bronstein, M. Ovsjanikov, 3D features, surface descriptors, and object descriptors, Chapter in 3D Imaging, Analysis and Applications (N. Pears, Y. Liu, P. Bunting, Eds.), Springer, 2012. details

    3D features, surface descriptors, and object descriptors

    A. M. Bronstein, M. M. Bronstein, M. Ovsjanikov
    Chapter in 3D Imaging, Analysis and Applications (N. Pears, Y. Liu, P. Bunting, Eds.), Springer, 2012.

    The computer vision and pattern recognition communities have recently witnessed a surge of feature-based methods in numerous applications including object recognition and image retrieval. Similar concepts and analogous approaches are penetrating the world of 3D shape analysis, in a variety of areas including non-rigid shape retrieval and matching. In this chapter, we present the state-of-the-art of feature-based approaches in 3D shape analysis.