


M. M. Bronstein, K. Glashoff, T. A. Loring,
"Making Laplacians commute: multimodal spectral geometry using closest commuting operators", SIAM Journal on Imaging Sciences (SIIS), submitted.
Abstract:
In this paper, we construct multimodal spectral geometry by finding a pair of closest commuting operators (CCO) to a given pair of Laplacians. The CCOs are jointly diagonalizable and hence have the same eigenbasis. Our construction 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 applications in dimensionality reduction, shape analysis, and clustering, demonstrating that our method better captures the inherent structure of multimodal data.




I. Kokkinos, M. M. Bronstein, A. Yuille,
"Dense scaleinvariant descriptors for images and surfaces", IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI), submitted.
Abstract:
Local descriptors are ubiquitous in image and shape analysis, allowing the compact and robust description of the local content of a signal (image or 3D shape). A common problem that emerges in the computation of local descriptors is the variability of the signal scale.
The standard approach to cope with this is scale selection, which consists in estimating a characteristic scale around the few image or shape points where scale estimation can be performed reliably. However, it is often desired to have a scaleinvariant descriptor that can be constructed at every point of the image or 3D shape.
In this work, we construct scaleinvariant signal descriptors by introducing a method that does not rely on scale selection.
This allows us to apply our method densely at any point instead of operating with a
small set of 'interesting' points.
Our method relies on a combination of logarithmic sampling with multiscale signal processing that turns scaling in the original signal domain into a translation in the new domain. Scale invariance can then be guaranteed by computing the Fourier transform magnitude (FTM) which is unaffected by signal translations.
We apply our technique to the construction of scale and rotation invariant local dense descriptors for images and scale and isometryinvariant for 3D surfaces, and demonstrate that our constructed descriptors outperform stateoftheart descriptors on standard datasets.
SID Code 
SIHKS Code




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), submitted.
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 multimodal 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. Eynard, A. Kovnatsky, M. M. Bronstein,
"Laplacian colormaps: a framework
for structurepreserving color transformations", Computer Graphics Forum (EUROGRAPHICS), Vol. 33/2, pp. 215224, 2014.
Abstract:
Mappings between color spaces are ubiquitous in image processing problems such as gamut mapping, decolorization,
and image optimization for colorblind people. Simple color transformations often result in information
loss and ambiguities, and one wishes to find an imagespecific 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 structurepreserving 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 colortogray conversion, gamut mapping, multispectral image fusion, and image optimization for color
deficient viewers.




J. Masci, M. M. Bronstein, A. M. Bronstein, J. Schmidhuber,
"Multimodal similaritypreserving hashing", IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI), Vol. 36/4, pp. 824830, 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 intermodality similarity learning. Unlike existing crossmodality 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 stateoftheart hashing approaches on multimedia retrieval tasks.




D. Raviv, A. M. Bronstein, M. M. Bronstein, D. Weisman, N. Sochen, R. Kimmel,
"Equiaffine invariant geometry for shape analysis", Journal of Mathematical Imaging and Vision (JMIV), in press.
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 equiaffine 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, equiaffineinvariant intrinsic geometries of
ten outperform their Euclideanbased 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 equiaffine 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. 25032513, 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
almostcommuting 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 (EUROGRAPHICS), Vol. 32, pp. 459468, 2013.
Abstract:
We present a novel sparse modeling approach to nonrigid 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 nontrivial 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 quasiharmonic bases", Computer Graphics Forum (EUROGRAPHICS), Vol. 32, pp. 439448, 2013.
Abstract:
The use of Laplacian eigenbases has been shown to be fruitful in many computer graphics applications. Today,
stateoftheart 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 pointwise correspondence", Numerical Mathematics: Theory, Methods and Applications, Vol. 6/1, pp. 223244, 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 nonrigid 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 pointwise nonbijective correspondence between the two, taking into account possibly different parts. In this paper, we introduce an alternative correspondenceless approach to matching fragments to an entire shape undergoing a nonrigid 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 MumfordShah functional. We show an efficient discretization based on the AmbrosioTortorelli 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 nonrigid shape analysis", Numerical Mathematics: Theory, Methods and Applications, Vol. 6/1, pp. 199222, 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 highdimensional 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,
"Motionbased mesh segmentation using augmented silhouettes", Graphical Models, Vol. 74/4, pp. 164172, 2012.
Abstract:
Motionbased segmentation, the problem of detecting rigid parts of an articulated threedimensional 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 twodimensional projections of the different shape poses with respect to a number of different view points, we derive a set of onedimensional 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 motionbased segmentation of the shape.




R. Litman, A. M. Bronstein, M. M. Bronstein,
"Stable volumetric features in deformable shapes", Computers & Graphics, Vol. 36/3, pp. 569576, 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 nonrigid
deformations. In this paper, we formulate a diffusiongeometric 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 highquality 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. 6678, January 2012.
Abstract:
SIFTlike local feature descriptors are ubiquitously employed in such computer vision applications as contentbased retrieval, video analysis, copy detection, object recognition, phototourism, 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 highdimensional (e.g. SIFT is represented as a 128dimensional vector). In largescale 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. 23162320, November 2011.
Abstract:
Detection and description of affineinvariant 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,
"Diffusiongeometric maximally stable component detection in deformable shapes", Computers & Graphics, Vol. 35/3, pp. 549560, 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 featurebased methods in geometric shape analysis, there is significant interest in finding analogous approaches in the 3D world.
In this paper, we formulate a diffusiongeometric framework for stable component detection in nonrigid 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 highquality features.
Code




D. Raviv, A. M. Bronstein, M. M. Bronstein, R. Kimmel, N. Sochen,
"Affineinvariant geodesic geometry of deformable 3D shapes", Computers & Graphics, Vol. 35/3, pp. 692697, 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 nonrigid shape analysis tools.
In fact, we show that by redefining the surface metric as its equiaffine
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. 17511756, June 2011.
Abstract:
Bilateral filter is one of the stateoftheart 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 realtime implementation a challenging task. Presented here is a highlyparallel version of the bilateral filter using a lazy sliding window, suitable for SIMDtype architectures.




M. M. Bronstein, A. M. Bronstein,
"Shape recognition with spectral distances", IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI), Vol. 33/5, pp. 10651071, May 2011.
Abstract:
Recent works have shown the use of diffusion geometry for various pattern recognition applications, including nonrigid
shape analysis. In this paper, we introduce spectral shape distance as a general framework for distributionbased 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 (TOG), Vol. 30/1, pp. 120, January 2011. TOG cover
Abstract:
The computer vision and pattern recognition communities have recently witnessed a surge of featurebased 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 nonrigid 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 spatiallysensitive 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 stateoftheart results on the SHREC 2010 largescale shape retrieval benchmark.




A. M. Bronstein, M. M. Bronstein, R. Kimmel, M. Mahmoudi, G. Sapiro,
"A GromovHausdorff framework with diffusion geometry for topologicallyrobust nonrigid shape matching", Intl. Journal of Computer Vision (IJCV), Vol. 89/23, pp. 266286, September 2010.
Abstract:
In this paper, the problem of nonrigid shape recognition is viewed from the
perspective of metric geometry, and the applicability of diffusion distances within the
GromovHausdorff 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 nonrigid 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 nonrigid 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. 5668, 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 nonconvexity. Distortions resulting from using long geodesics indiscriminantly lead to a known limitation of the Isomap algorithm when used to map nonconvex 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 nonlocal 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 nonrigid shapes", Intl. Journal of Computer Vision (IJCV), Vol. 89/1, pp. 1839, August 2010.
Abstract:
Symmetry and selfsimilarity 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 nonrigid 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 nonrigid 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. 163183, 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 nonrigid geometric objects, images, and analyzing text sequences.
3D nonrigid 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. 105114, 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 multicriterion
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 pointwise significance density using a statistical weighting
approach similar to the term frequencyinverse 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,
"Topologyinvariant similarity of nonrigid shapes", Intl. Journal of Computer Vision (IJCV), Vol. 81/3, pp. 281301, 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 topologyinvariant 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 setvalued
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 firstorder 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 stateoftheart algorithms.
GPU code  SIGGRAPH'08 trailer




A. M. Bronstein, M. M. Bronstein, A. M. Bruckstein, R. Kimmel,
"Analysis of twodimensional nonrigid shapes", Intl. Journal of Computer Vision (IJCV), Vol. 78/1, pp. 6788, June 2008.
Abstract:
Analysis of deformable twodimensional 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 nonrigid shapes: similarity, partial similarity, and correspondence.We present an axiomatic construction of similarity criteria for deformationinvariant shape comparison, based on intrinsic geometric properties of the shapes, and show that such criteria are related to the GromovHausdorff 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 setvalued distances, based on the notion of Pareto optimality. Finally, we show that the correspondence between nonrigid shapes can be obtained as a byproduct of the nonrigid 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 threedimensional manifolds", Journal of Computational Physics, Vol. 255/1, pp. 771784, July 2007.
Abstract:
We propose an effcient computational solver for the eikonal equations on parametric threedimensional 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 nonrigid surfaces for geometry and texture manipulation", IEEE Trans. Visualization and Computer Graphics, Vol 13/5, pp. 902913, SeptemberOctober 2007.
Abstract:
We present a geometric framework for automatically finding intrinsic correspondence between threedimensional nonrigid objects. We model object deformation as near isometries and find the correspondence as the minimumdistortion 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 expressioninvariant texture mapping onto an animated threedimensional face, expression exaggeration, morphing between faces, and virtual body painting.




A. M. Bronstein, M. M. Bronstein, R. Kimmel,
"Expressioninvariant representation of faces", IEEE Trans. Image Processing, Vol. 16/1, pp. 188197, January 2007.
Abstract:
Addressed here is the problem of constructing and analyzing expressioninvariant 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 expressioninvariant representation of a face involves embedding of the facial intrinsic geometric structure into some convenient lowdimensional 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 isometryinvariant distances between surfaces", SIAM J. Scientific Computing, Vol. 28/5, pp. 18121836, 2006.
Abstract:
We present an efficient computational framework for isometryinvariant comparison
of smooth surfaces. We formulate the GromovHausdorff 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
isometryinvariant 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 minimumdistortion 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/23, pp. 149171, MarchApril 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 interpoint distances measured in some other metric space. Largescale 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 largescale 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 isometryinvariant partial surface matching", Proc. National Academy of Sciences (PNAS), Vol. 103/5, pp. 11681172, January 2006.
Abstract:
An efficient algorithm for isometryinvariant matching of surfaces
is presented. The key idea is computing the minimumdistortion
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 threedimensional face recognition.




A. M. Bronstein, M. M. Bronstein, R. Kimmel,
"Threedimensional face recognition",
Intl. Journal of Computer Vision (IJCV), Vol. 64/1, pp. 530, August 2005.
Abstract:
An expressioninvariant 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 expressioninvariant 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 expressioninvariant 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. 8491, 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 subGaussianity versus consistency",
IEEE Trans. Signal Processing, Vol. 53/7, pp. 25762579, 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 subGaussian 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. 20182026, 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 fastconvergent 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 nonlinear functions suitable for
deconvolution of super and subGaussian 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. 726736, 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 fastconvergent 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 nonlinear functions suitable for
deconvolution of super and subGaussian 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 blockcoordinate relative Newton method",
Signal Processing, Vol. 84/8, pp. 14471459, 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 blockcoordinate 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 lineofflight estimation in positron emission tomography",
IEEE Trans. Nuclear Science, Vol. 50/3, pp. 421426, June 2003.
Abstract:
We consider detection of highenergy 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. MonteCarlo
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 nonuniform FFT",
IEEE Trans. Medical Imaging, Vol. 21/11, pp. 13951401, November 2002.
Abstract:
We show an iterative reconstruction framework
for diffraction ultrasound tomography. The use of broadband
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 NUFFTbased reconstruction is comparable to the frequencydomain
interpolation (gridding) algorithm, whereas the reconstruction
accuracy (in sense of the L2 and the Linf norm) is better.



