Art (Artiom) Kovnatsky Home   |   Research  

I am interested in application of mathematics (optimization, statistics, probability, calculus of variations, differential equations, etc.) to real life problems.

Publications

Klematis

MADMM: a generic algorithm for non-smooth optimization on manifolds

A. Kovnatsky, K. Glashoff, and M. M. Bronstein

European Conference on Computer Vision (ECCV), 2016 (accepted).

Numerous problems in machine learning are formulated as optimization with manifold constraints. In this paper, we propose the Manifold Alternating Directionsmethod of Multipliers (MADMM), an extension of the classical ADMM scheme for manifold-constrained non-smooth optimization problems and show its application to several challenging problems in dimensionality reduction, data analysis, and manifold learning.

[PDF] [BibTeX]
Klematis

Functional correspondence by matrix completion

A. Kovnatsky, M. M. Bronstein, X. Bresson, and P. Vandergheynst

Computer Vision & Pattern Recognition (CVPR), 2015.

In this paper, we consider the problem of finding dense intrinsic correspondence between manifolds using the recently introduced functional framework. We pose the functional correspondence problem as matrix completion with manifold geometric structure and inducing functional localization with the L1 norm. We discuss efficient numerical procedures for the solution of our problem. Our method compares favorably to the accuracy of state-of-theart correspondence algorithms on non-rigid shape matching benchmarks, and is especially advantageous in settings when only scarce data is available.

[PDF] [BibTeX]
Klematis

Gamut mapping with image Laplacian commutators

A. Kovnatsky, D. Eynard, M. M. Bronstein

Proc. Int. Conf. Image Processing (ICIP), 2014.

In this paper, we present a gamut mapping algorithm that is based on spectral properties of image Laplacians as image structure descriptors. Using the fact that structurally similar images have similar Laplacian eigenvectors and employing the relation between joint diagonalizability and commutativity of matrices, we minimize the Laplacians commutator w.r.t. the parameters of a color transformation to achieve optimal structure preservation while complying with the target gamut. Our method is computationally efficient, favorably compares to state-of-the-art approaches in terms of quality, allows mapping to devices with any number of primaries, and supports gamma correction, accounting for brightness response of computer displays.

[PDF] [BibTeX]
Klematis

Laplacian colormaps: a framework for structure-preserving color transformations

D. Eynard, A. Kovnatsky, M. M. Bronstein

Computer Graphics Forum (EUROGRAPHICS), 2014.

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 (for example, when mapping from RGB to grayscale), 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.

[PDF] [BibTeX] [Code]
Klematis

Multimodal manifold analysis using simultaneous diagonalization of Laplacians

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), 2015.

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.

[PDF] [BibTeX] [Code]
Klematis

Coupled quasi-harmonic bases

A. Kovnatsky, M. M. Bronstein, A. M. Bronstein, K. Glashoff, R. Kimmel

Computer Graphics Forum (EUROGRAPHICS), 2013.

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. Dataset consistes of non- and isometrical shapes with pointwise ground-truth correspondences (assigned manually).

[PDF] [BibTeX] [Code] [Dataset]
Klematis

Geometric and photometric data fusion in non-rigid shape analysis

A. Kovnatsky, D. Raviv, M. M. Bronstein, A. M. Bronstein, R. Kimmel

Numerical Mathematics: Theory, Methods and Applications, 2013.

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.

[PDF] [BibTeX]
Klematis

Affine-invariant photometric heat kernel signatures

A. Kovnatsky, D. Raviv, M. M. Bronstein, A. M. Bronstein, R. Kimmel

Proc. 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 of retrieval task the proposed diffusion process may be employed in other applications.

[PDF] [BibTeX]
Klematis

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.

[PDF] [BibTeX]
Klematis

Photometric heat kernel signatures

A. Kovnatsky, M. M. Bronstein, A. M. Bronstein, R. Kimmel

Proc. Conf. on Scale Space and Variational Methods in Computer Vision (SSVM), 2011.

In this paper, we explore the use of the diffusion geometry framework for the fusion of geometric and photometric information in local heat kernel signature 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.

[PDF] [BibTeX]

PhD Thesis

Klematis

Spectral Methods for Multimodal Data Analysis

A. Kovnatsky

USI - Universitá della Svizzera italiana, 2016.

Spectral methods have proven themselves as an important and versatile tool in a wide range of problems in the fields of computer graphics, machine learning, pattern recognition, and computer vision, where many important problems boil down to constructing a Laplacian operator and finding a few of its eigenvalues and eigenfunctions. Classical examples include the computation of diffusion distances on manifolds in computer graphics, Laplacian eigenmaps, and spectral clustering in machine learning. In many cases, one has to deal with multiple data spaces simultaneously. For example, clustering multimedia data in machine learning applications involves various modalities or ''views'' (e.g., text and images), and finding correspondence between shapes in computer graphics problems is an operation performed between two or more modalities. In this thesis, we develop a generalization of spectral methods to deal with multiple data spaces and apply them to problems from the domains of computer graphics, machine learning, and image processing. Our main construction is based on simultaneous diagonalization of Laplacian operators. We present an efficient numerical technique for computing joint approximate eigenvectors of two or more Laplacians in challenging noisy scenarios, which also appears to be the first general non-smooth manifold optimization method. Finally, we use the relation between joint approximate diagonalizability and approximate commutativity of operators to define a structural similarity measure for images. We use this measure to perform structure-preserving color manipulations of a given image.

[PDF] [BibTeX]

Different codes/projects

Klematis

Iterative Acceleration Methods: Vector Extrapolation

Implementation of the MPE and RRE vector extrapolation methods.

[Code]
Klematis

Feature points in image, Keypoint extraction

Implementation of the images feature extraction, description and matching. The code has detailed comments, hence it is suitable for beginners in the topic.

[Code]
Klematis

Images stitching

Panorama creation, i.e. images stitching. The code has detailed comments.

[Code]
Image courtesy: authors of the paper
Klematis

Complex variable method for gradient checking

This code checks the gradients of a given function with complex variable method . This method is more stable for small than the standard finite difference.

[Code]
Image courtesy: http://napitupulu-jon.appspot.com
Klematis

Poisson editing

Implementation of the method proposed in Poisson editing paper for seamless image manipulations.

[Code]
Klematis

Fast Marching Method

Implementation of the two-dimensional Fast Marching Method for solving Eikonal equation (weighted distance map from provided source points). Roughly speaking, the method simulates propagation of fire in a forest from given fire sources; time that takes for fire to reach a particular tree equals to distance.

[Code]
Klematis

Non-Linear diffusion filtering of images (anisotropic diffusion).

Implementation of the anisotropic diffusion for edge-preserving image filtering. In addition to straightforward explicit numerical scheme, I also implemented semi-implicit AOS and LOD numerical schemes, which do not have restrictions on the time step.

[Code]