Home TOSCA Research Publications Lectures Teaching Collaborators Personalia Journal Conference Book Chapters Reports Patents Misc M. M. Bronstein, A. M. Bronstein, "Analysis of diffusion geometry methods for shape recognition", IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI), submitted. Abstract: Recent works have shown the use of diffusion geometry for various pattern recognition applications, including non-rigid shape analysis. In this paper, we analyze two recent methods for shape similarity due to Rustamov and Mahmoudi & Sapiro. We show the relations between the methods and propose a new shape similarity criterion combining the advantages of both methods. M. M. Bronstein, "Lazy sliding window implementation of the bilateral filter on parallel architectures", IEEE Trans. Image Processing, submitted. 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. R. Kimmel, C. Zhang, A. M. Bronstein, M. M. Bronstein, "Are MSER features really interesting?", IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI), submitted. 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. G. Rosman, M. M. Bronstein, A. M. Bronstein, R. Kimmel, "Nonlinear dimensionality reduction by topologically constrained isometric embedding", Intl. Journal of Computer Vision (IJCV), in press (Springer OnlineFirst). 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), in press (Springer OnlineFirst). 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, 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), in press (Springer OnlineFirst). 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. 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. Resources: 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. 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 (TOG), Vol. 27/4, October 2008. 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. Resources: SSE2 code | GPU code (by Ofir Weber) | 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. Resources: 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. Resources: Multigrid MDS code (MATLAB) | Tutorial (MATLAB) 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.