Linear Sum Assignment Problem (LSAP) consists in mapping two sets of points of equal sizes according to a matrix encoding the cost of mapping each pair of points. The Linear Sum Assignment Problem with Edition (LSAPE) extends this problem by allowing the mapping of sets of different sizes and adding the possibility to reject some matchings. This problem is set up by a rectangular cost matrix whose last column and last line encode the costs of rejecting the match of an element of respectively the first and the second sets. LSAPE has been the workhorse of many fundamental graph problems such as graph edit distance, median graph computation or sub graph matching. LSAP may be solved using the Hungarian algorithm while an equivalent efficient discrete algorithm has been designed for LSAPE. However, while the Sinkhorn algorithm constitutes a continuous solver for LSAP, no such algorithm yet exists for LSAPE. This lack of solvers forbids the integration of LSAPE in Neural networks requiring continuous operations from the input to the final loss. This paper aims at providing such a solver, hence paving the way to an integration of LSAPE solvers in Neural Networks.

This paper proposes a new neural network based on Symmetric Positive Definite (SPD) manifold learning for real-time skeleton-based hand gesture recognition. The transformation of the input skeletal data into SPD matrices allows to encode efficiently high-order statistics such as covariances or correlations between the joints' features. These matrices are combined and transformed by our deep neural network which is thus constrained to work on the manifold of such matrices. The online recognition is performed using two sliding windows moving along the gesture's stream in order to simultaneously detect and classify the occurrence of a new gesture within the stream. The proposed network is validated on a challenging dataset and shows state-of-the-art performances both in terms of accuracy and inference time.

The graph edit distance (GED) is a flexible distance measure which is widely used for inexact graph matching. Since its exact computation is [Formula: see text]-hard, heuristics are used in practice. A popular approach is to obtain upper bounds for GED via transformations to the linear sum assignment problem with error-correction (LSAPE). Typically, local structures and distances between them are employed for carrying out this transformation, but recently also machine learning techniques have been used. In this paper, we formally define a unifying framework LSAPE-GED for transformations from GED to LSAPE. We also introduce rings, a new kind of local structures designed for graphs where most information resides in the topology rather than in the node labels. Furthermore, we propose two new ring-based heuristics RING and RING-ML, which instantiate LSAPE-GED using the traditional and the machine learning-based approach for transforming GED to LSAPE, respectively. Extensive experiments show that using rings for upper bounding GED significantly improves the state of the art on datasets where most information resides in the graphs’ topologies. This closes the gap between fast but rather inaccurate LSAPE-based heuristics and more accurate but significantly slower GED algorithms based on local search.

In this paper, we present GMG-BCU — a local search algorithm based on block coordinate update for estimating a generalized median graph for a given collection of labeled or unlabeled input graphs. Unlike all competitors, GMG-BCU is designed for both discrete and continuous label spaces and can be configured to run in linear time w. r. t. the size of the graph collection whenever median node and edge labels are computable in linear time. These properties make GMG-BCU usable for applications such as differential microbiome data analysis, graph classification, clustering, and indexing. We also prove theoretical properties of generalized median graphs, namely, that they exist under reasonable assumptions which are met in almost all application scenarios, that they are in general non-unique, that they are NP-hard to compute and APX-hard to approximate, and that no polynomial α-approximation exists for any α unless the graph isomorphism problem is in P. Extensive experiments on six different datasets show that our heuristic GMG-BCU always outperforms the state of the art in terms of runtime or quality (on most datasets, both w. r. t. runtime and quality), that it is the only available heuristic which can cope with collections containing several thousands of graphs, and that it shows very promising potential when used for the aforementioned applications. GMG-BCU is freely available on GitHub: https://github.com/dbblumenthal/gedlib/.

Deep learning has recently improved the performance of Speaker Identification (SI) systems. Promising results have been obtained with Convolutional Neural Networks (CNNs). This success is mostly driven by the advent of large datasets. However in the context of decentralized commercial applications, collection of large amount of training data is not always possible. In addition, robustness of a SI system is adversely effected by short utterances. Therefore, in this paper, we propose a novel text-independent speaker identification system able to identify speakers by learning from only few training short utterances examples. To achieve this, we combine a two-layer wavelet scattering network coupled with a CNN. The proposed architecture takes variable length speech segments. To evaluate the effectiveness of the proposed approach, Timit and Librispeech datasets are used in the experiments. Our experiments shows that our hybrid architecture provides satisfactory results under the constraints of short and limited number of utterances. These experiments also show that our hybrid architecture are competitive with the state of the art.

High-order statistics have been proven useful in the framework of Convolutional Neural Networks (CNN) for a variety of computer vision tasks. In this paper, we propose to exploit high-order statistics in the framework of Recurrent Neural Networks (RNN) for skeleton-based hand gesture recognition. Our method is based on the Statistical Recurrent Units (SRU), an un-gated architecture that has been introduced as an alternative model for Long-Short Term Memory (LSTM) and Gate Recurrent Unit (GRU). The SRU captures sequential information by generating recurrent statistics that depend on a context of previously seen data and by computing moving averages at different scales. The integration of high-order statistics in the SRU significantly improves the performance of the original one, resulting in a model that is competitive to state-of-the-art methods on the Dynamic Hand Gesture (DHG) dataset, and outperforms them on the First-Person Hand Action (FPHA) dataset.

In real world applications, the performances of speaker identification systems degrade due to the reduction of both the amount and the quality of speech utterance. For that particular purpose, we propose a speaker identification system where short utterances with few training examples are used for person identification. Therefore, only a very small amount of data involving a sentence of 2-4 seconds is used. To achieve this, we propose a novel raw waveform end-to-end convolutional neural network (CNN) for text-independent speaker identification. We use wavelet scattering transform as a fixed initialization of the first layers of a CNN network, and learn the remaining layers in a supervised manner. The conducted experiments show that our hybrid architecture combining wavelet scattering transform and CNN can successfully perform efficient feature extraction for a speaker identification, even with a small number of short duration training samples.

This paper proposes a new neural network based on SPD manifold learning for skeleton-based hand gesture recognition. Given the stream of hand’s joint positions, our approach combines two aggregation processes on respectively spatial and temporal domains. The pipeline of our network architecture consists in three main stages. The first stage is based on a convolutional layer to increase the discriminative power of learned features. The second stage relies on different architectures for spatial and temporal Gaussian aggregation of joint features. The third stage learns a final SPD matrix from skeletal data. A new type of layer is proposed for the third stage, based on a variant of stochastic gradient descent on Stiefel manifolds. The proposed network is validated on two challenging datasets and shows state-of-the-art accuracies on both datasets.

In this paper, we propose a new hand gesture recognition method based on skeletal data by learning SPD matrices with neural networks. We model the hand skeleton as a graph and introduce a neural network for SPD matrix learning, taking as input the 3D coordinates of hand joints. The proposed network is based on two newly designed layers that transform a set of SPD matrices into a SPD matrix. For gesture recognition, we train a linear SVM classifier using features extracted from our network. Experimental results on a challenging dataset (Dynamic Hand Gesture dataset from the SHREC 2017 3D Shape Retrieval Contest) show that the proposed method outperforms state-of-the-art methods.

The graph edit distance (GED) is a widely used distance measure for attributed graphs. It has recently been shown that the problem of computing GED, which is a NP-hard optimization problem, can be formulated as a quadratic assignment problem (QAP). This formulation is useful, since it allows to derive well performing approximative heuristics for GED from existing techniques for QAP. In this paper, we focus on the case where the edit costs that underlie GED are quasimetric. This is the case in many applications of GED. We show that, for quasimetric edit costs, it is possible to reduce the size of the corresponding QAP formulation. An empirical evaluation shows that this reduction significantly speeds up the QAP-based approximative heuristics for GED.

Although it has been studied extensively during past decades, object tracking is still a difficult problem due to many challenges. Several improvements have been done, but more and more complex scenes (dense crowd, complex interactions) need more sophisticated approaches. Particularly long-term tracking is an interesting problem that allow to track objects even after it may become longtime occluded or it leave/re-enter the field-of-view. In this case the major challenges are significantly changes in appearance, scale and so on. At the heart of the solution of long-term tracking is the re-identification technique, that allows to identify an object coming back visible after an occlusion or re-entering on the scene. This paper proposes an approach for pedestrian re-identification based on structural representation of people. The experimental evaluation is carried out on two public data sets (ETHZ and CAVIAR4REID datasets) and they show promising results compared to others state-of-the-art approaches.

Solving or approximating the linear sum assignment problem (LSAP) is an important step of several constructive and local search strategies developed to approximate the graph edit distance (GED) of two attributed graphs, or more generally the solution to quadratic assignment problems. Constructive strategies find a first estimation of the GED by solving an LSAP. This estimation is then refined by a local search strategy. While these search strategies depend strongly on the initial assignment, several solutions to the linear problem usually exist. They are not taken into account to get better estimations. All the estimations of the GED based on an LSAP select randomly one solution. This paper explores the insights provided by the use of several solutions to an LSAP, refined in parallel by a local search strategy based on the relaxation of the search space, and conditional gradient descent. Other generators of initial assignments are also considered, approximate solutions to an LSAP and random assignments. Experimental evaluations on several datasets show that the proposed estimation is comparable to more global search strategies in a reduced computational time.

The graph edit distance (GED) measures the amount of distortion needed to transform a graph into another graph. Such a distance, developed in the context of error-tolerant graph matching, is one of the most flexible tool used in structural pattern recognition. However, the computation of the exact GED is NP-complete. Hence several suboptimal solutions, such as the ones based on bipartite assignments with edition, have been proposed. In this paper we propose a binary quadratic programming problem whose global minimum corresponds to the exact GED. This problem is interpreted as a quadratic assignment problem (QAP) where some constraints have been relaxed. This allows to adapt the integer projected fixed point algorithm, initially designed for the QAP, to efficiently compute an approximate GED by finding an interesting local minimum. Experiments show that our method remains quite close to the exact GED for datasets composed of small graphs, while keeping low execution times on datasets composed of larger graphs.

The prediction of molecule's properties through Quantitative Structure Activity (resp. Property) Relationships are two active research fields named QSAR and QSPR. Within these frameworks Graph kernels allow to combine a natural encoding of a molecule by a graph with classical statistical tools such as SVM or kernel ridge regression. Unfortunately some molecules encoded by a same graph and differing only by the three dimensional orientation of their atoms in space have different properties. Such molecules are called stereoisomers. These latter properties can not be predicted by usual graph methods which do not encode stereoisomerism. In a previous paper, we proposed to encode the stereoisomerism property of each atom by a local subgraph, called minimal stereo subgraph, and we designed a kernel based on the comparison of bags of such subgraphs. However, the encoding of a molecule by a bag of subgraphs induces an important loss of information. In this paper, we propose a new kernel based both on the spatial relationships between minimal stereo subgraphs and the local neighbourhood of each minimal stereo subgraph within its supergraph. Our experiments show the benefits of taking into account such information.

In this paper we propose a graph based approach for detecting abnormal behaviors starting from the analysis of vehicles' trajectories. The scene is partitioned into zones and is dynamically represented as a graph by evaluating the distribution of trajectories belonging to the training set. Furthermore, four different strategies are proposed in order to verify if a test trajectory belongs to the scene and then can be considered normal by evaluating the probability that this trajectory belongs to the graph. Our algorithms have been tested on the standard MIT Trajectories dataset and the obtained results confirm the effectiveness of the proposed approach.

In this paper we propose HAcK, a novel method for recognizing Human Actions by string Kernel; the main idea is to represent each action through a sequence of visual characters, namely a string, able to model the temporal evolution of the events. Visual characters are extracted by analyzing global descriptors of the scene and by taking advantage on the depth information provided by a Kinect sensor. The similarity between actions is evaluated with a fast global alignment kernel, which allows to deal with actions of different length as well as with the noise introduced during the features extraction step. HAcK has been evaluated over two standard datasets and the obtained results, compared with state of the art approaches, confirm its effectiveness and its applicability in real environments.

In this paper we propose a novel and efficient method for solving queries by sketch in traffic scenarios, aiming to find the k nearest neighbor trajectories to the one hand drawn by the human operator. Each trajectory is represented as a sequence of symbols, namely a string, and it is stored into a k-d tree by taking into account the similarity between trajectories, evaluated by a global fast alignment kernel. The experimentation has been conducted over the standard MIT trajectories dataset and results confirm the effectiveness and the robustness of the proposed approach.

Chemo informatics aims to predict molecular properties using informational methods. Computer science's research fields concerned by this domain are machine learning and graph theory. An interesting approach consists in using graph kernels which allow to combine graph theory and machine learning frameworks. Graph kernels allow to define a similarity measure between molecular graphs corresponding to a scalar product in some Hilbert space. Most of existing graph kernels proposed in chemo informatics do not allow to explicitly encode cyclic information, hence limiting the efficiency of these approaches. In this paper, we propose to define a cyclic representation encoding the relative positioning of substituents around a cycle. We also propose a graph kernel taking into account this information. This contribution has been tested on three classification problems proposed in chemo informatics.

The prediction of molecule's properties through Quantitative Structure Activity (resp. Property) Relationships are two active research fields named QSAR and QSPR. Within these frameworks Graph kernels allow to combine a natural encoding of a molecule by a graph with classical statistical tools such as SVM or kernel ridge regression. Unfortunately some molecules encoded by a same graph and differing only by the three dimensional orientations of their atoms in space have different properties. Such molecules are called stereoisomer's. These latter properties can not be predicted by usual graph methods which do not encode stereoisomerism. In this paper we propose a new graph encoding of molecules taking explicitly into account stereoisomerism and propose a new kernel between these structures in order to predict properties related to stereoisomerism.

This paper aims at dynamically understanding the properties of a scene from the analysis of moving object trajectories. Two different applications are proposed: the former is devoted to identify abnormal behaviors, while the latter allows to extract the k, most of the similar trajectories to the one hand-drawn by an human operator. A set of normal trajectories' models is extracted using a novel unsupervised learning technique: the scene is adaptively partitioned into zones using the distribution of the training set and each trajectory is represented as a sequence of symbols by considering positional information (the zones crossed in the scene), speed, and shape. The main novelty is the use of a kernel-based approach for evaluating the similarity between the trajectories. Furthermore, we define a novel and efficient kernel-based clustering algorithm, aimed at obtaining groups of normal trajectories. Experimentations, conducted over three standard data sets, confirm the effectiveness of the proposed approach.

Weighted Graph regularization provides a rich framework that allows to regularize functions defined over the vertices of a weighted graph. Until now, such a framework has been only defined for real or multivalued functions hereby restricting the regularization framework to numerical data. On the other hand, several kernels have been defined on structured objects such as strings or graphs. Using definite positive kernels, each original object is associated by the ``kernel trick'' to one element of an Hilbert space. As a consequence, this paper proposes to extend the weighted graph regularization framework to objects implicitly defined by their kernel hereby performing the regularization within the Hilbert space associated to the kernel. This work opens the door to the regularization of structured objects.

Combinatorial maps define a general framework which allows to encode any subdivision of an n-D orientable quasi-manifold with or without boundaries. Combinatorial pyramids are defined as stacks of successively reduced combinatorial maps. Such pyramids provide a rich framework which allows to encode fine properties of objects (either shapes or partitions). Combinatorial pyramids have first been defined in 2D, then extended using n-D generalized combinatorial maps. We motivate and present here an implicit and efficient way to encode pyramids of n-D combinatorial maps.

We design a family of non-local image smoothing algorithms which approximate the application of diffusion PDE's on a specific Euclidean space of image patches. We first map a noisy image onto this high-dimensional space and estimate its geometric structure thanks to a straightforward extension of the structure tensor field. The tensors spectral elements allows us to design an oriented high-dimensional smoothing process by the means of anisotropic regularization PDE's which have both local and non-local properties and whose solutions are estimated by locally oriented high-dimensional convolutions. We show that the Bilateral Filtering and Non-Local Means methods are the isotropic cases of our denoising framework.

We propose in this paper a face authentication method based on a similarity measure. The SIFT descriptor is used to define some interest keypoints characterized by an invariant parameter. A graph is then built where nodes correspond to these keypoints. We model the authentication problem as a graph matching process. Experimental results on the AR database show an EER equals to 12% with only one image used for the enrollment and with images simulating real conditions.

We present a robust method to retrieve neuronal fibers in human brain white matter from high-angular resolution MRI (HARDI datasets). Contrary to classical fiber-tracking techniques done on the traditional 2nd-order tensor model (DTI) which may lead to truncated or biased estimated diffusion directions in case of fiber crossing configurations, we propose here a more complex approach based on a variational estimation of orientation diffusion functions (ODF) modeled with spherical harmonics. This kind of model can correctly retrieve multiple fiber directions corresponding to underlying intra-voxel fibers populations. Our technique is able to consider the Rician noise model of the MRI acquisition in order to better estimate the white matter fiber tracks. Results on both synthetic and real human brain white matter HARDI datasets illustrate the effectiveness of the proposed approach.

An irregular pyramid consists of a stack of successively reduced graphs. Each smaller graph is deduced from the preceding one by the contraction or the removal of a set of edges. Using a fixed decimation ratio we need approximately O(log(image size)) graphs to encode the whole pyramid. A combinatorial map encodes a planar graph thanks to two permutations encoding the edges and their orientation around the vertices. We present in this article an encoding of a combinatorial pyramid which allows to fold the whole pyramid in the base level layer and provides at the same time a measure of the relevance of every pixel. This encoding is used to retrieve any reduced combinatorial map of the pyramid from its base and to compute the borders of the partition encoded by the combinatorial maps.

The inverse colormap operation is the process which allows an image to be displayed with a limited set of colors. In order to obtain a minimal visual distortion between the input image annd the one displayed, inverse colormap algorithms associate each color with its nearest representative. The method presented in this paper is carried out in two steps. First, the 3D Voronoi diagram implicitly used by inverse colormap algorithms is approximated using a Karhunen‐Loève transformation. Then, a correcting step is carried out in order to reduce the in uence of the first approximation. The complexity of our algorithm is independent of the size of the colormap. Moreover, its results are equal or quite close to the optimal solution.

Color image quantization, the process of reducing the number of colors in a digital color image, has been widely studied for the last fifteen years. The different steps of clustering methods are studied. The methods are compared step by step and some optimizations of the algorithms and data structures are given. A new color space called H1H2H3 is introduced, which improves the quantization heuristics. A low-cost quantization scheme is proposed.