HAL : Dernières publications

• [hal-03540226] Automatic Normalisation of Early Modern French

  Spelling normalisation is a useful step in the study and analysis of historical language texts, whether it is manual analysis by experts or automatic analysis using downstream natural language processing (NLP) tools. Not only does it help to homogenise the variable spelling that often exists in historical texts, but it also facilitates the use of off-the-shelf contemporary NLP tools, if contemporary spelling conventions are used for normalisation. We present FREEMnorm, a new benchmark for the normalisation of Early Modern French (from the 17th century) into contemporary French and provide a thorough comparison of three different normalisation methods: ABA, an alignment-based approach and MT-approaches, (both statistical and neural), including extensive parameter searching, which is often missing in the normalisation literature.

• [hal-03608412] Tree Diet: Reducing the Treewidth to Unlock FPT Algorithms in RNA Bioinformatics

  Hard graph problems are ubiquitous in Bioinformatics, inspiring the design of specialized Fixed-Parameter Tractable algorithms, many of which rely on a combination of tree-decomposition and dynamic programming. The time/space complexities of such approaches hinge critically on low values for the treewidth tw of the input graph. In order to extend their scope of applicability, we introduce the Tree-Diet problem, i.e. the removal of a minimal set of edges such that a given tree-decomposition can be slimmed down to a prescribed treewidth tw ′. Our rationale is that the time gained thanks to a smaller treewidth in a parameterized algorithm compensates the extra post-processing needed to take deleted edges into account. Our core result is an FPT dynamic programming algorithm for Tree-Diet, using 2 O(tw) n time and space. We complement this result with parameterized complexity lower-bounds for stronger variants (e.g., NP-hardness when tw ′ or tw−tw ′ is constant). We propose a prototype implementation for our approach which we apply on difficult instances of selected RNA-based problems: RNA design, sequence-structure alignment, and search of pseudoknotted RNAs in genomes, revealing very encouraging results. This work paves the way for a wider adoption of tree-decomposition-based algorithms in Bioinformatics.

• [tel-03583653] Deep Learning for Near-duplicated Patterns Discovery and Alignment in Artworks

  The goal of this thesis is to develop self-supervised learning approaches to artwork analysis. Precisely, we focus on two particular tasks: object discovery and fine alignment in a collection of artworks. Both tasks are extremely challenging in computer vision, the main difficulties include: i) no annotations are available for both tasks; ii) there are differences in the artistic media (oil, pastel, drawing, etc), and imperfections inherent in the copying process.Object discovery aims at identifying repeated visual patterns across a collection of artworks. This is an important application for art historians, as visual links built via the repeated details may indicate authorship and provenance. Apart from artwork analysis, the task is also interesting for applications on natural images, one typical example is that it enable automatically collect training data.Fine alignment takes a pair of images as inputs and predicts pixel-level alignment. Our goal is to design a generic image alignment approach, which allows aligning images with different appearances, viewpoints and styles, such as two frames in a video, two Internet images on the same landmark or even two paintings depicting the same content but with different styles. The precise flow leads to many interesting applications on artworks, such as texture transfer, aligning a group of images/patterns and analysis of copy process, etc. Moreover, the precise optical flow is also beneficial to several important 3D tasks including two-view geometry estimation and 3D reconstruction.The first technical contribution of this thesis is that we introduce a self-supervised approach to adapt a standard deep feature by fine-tuning it on the specific art collection. More specifically, spatial consistency between neighboring feature matches is used as supervision. The adapted feature leads to more accurate style-invariant matching, and we further propose a discovery pipeline, based on multi-resolution feature matching and geometric verification, to identify duplicate patterns in the dataset. Along with the approach, we also propose a dataset Brueghel which allows evaluating one-shot cross-domain art detail detection.Our second contribution is that we show that it is possible to learn co-segmentation for a pair of images on a synthetic dataset. We generate the training pairs by blending objects into a background image such that we have access into ground-truth masks and correspondences. We empirically study two architectures: Sparse Nc-Net and a transformer-based architecture, and show that employing Poisson Blending and style transfer is crucial for generalization. In terms of results, the trained transformer on the proposed dataset achieves surprisingly good performance on various tasks including one-shot cross-domain art detail detection, place recognition and object discovery.The last contribution is a two-stage method for generic image alignment. In the coarse stage, we estimate a homography transformation between a pair of images with standard feature matches and RANSAC; In the fine stage, we design and learn a small Convolutional Neural Network (CNN) to predict pixel-level alignment relying on the reconstruction loss SSIM. Yet simple, the proposed show competitive and better performance across different tasks: optical flow estimation, sparse correspondences evaluation, two-view geometry estimation, and 3D reconstruction, etc. We also show it is possible to align discovered duplicated patterns and images from Internet search.

• [hal-03651336] Bilateral K-Means for Superpixel Computation (the SLIC Method)

  As a substitute to a full segmentation of a digital image, or as preprocessing to a segmentation algorithm, superpixels provide an over-segmentation that offers several benefits: good adherence to edges, uniformity of color inside superpixels, a richer adjacency structure than the regular grid of pixels, and the fact that each node of the graph of superpixels has a shape, which can be used in subsequent processing. Moreover, their evaluation is less subjective than a full segmentation, which somehow always involves a semantic interpretation of the scene. The SLIC method (Simple Linear Iterative Clustering) has been a very popular algorithm to compute superpixels since its introduction. Its advantage is due to its simplicity and to its computing time performance. In essence, it consists in a K-means clustering in bilateral domain, involving both position and color. We study in detail this algorithm and propose a fast, simple postprocessing that ensures that superpixels are connected, a property not ensured by the original method. Source Code The commented C++ source code for SLIC and its documentation are available on the web page of this article 1. Usage instructions are detailed in the README.md file of the archive.

• [hal-03136103] Visualizing hierarchies in scRNA-seq data using a density tree-biased autoencoder

  Motivation: Single cell RNA sequencing (scRNA-seq) data makes studying the development of cells possible at unparalleled resolution. Given that many cellular differentiation processes are hierarchical, their scRNA-seq data is expected to be approximately tree-shaped in gene expression space. Inference and representation of this tree-structure in two dimensions is highly desirable for biological interpretation and exploratory analysis. Results: Our two contributions are an approach for identifying a meaningful tree structure from high-dimensional scRNA-seq data, and a visualization method respecting the tree-structure. We extract the tree structure by means of a density based minimum spanning tree on a vector quantization of the data and show that it captures biological information well. We then introduce DTAE, a tree-biased autoencoder that emphasizes the tree structure of the data in low dimensional space. We compare to other dimension reduction methods and demonstrate the success of our method both qualitatively and quantitatively on real and toy data. Availability: Our implementation relying on PyTorch and Higra is available at https://github.com/hci-unihd/DTAE.

• [hal-03643580] Towards Efficient Indoor/Outdoor Registration Using Planar Polygons

  The registration of indoor and outdoor scans with a precision reaching the level of geometric noise represents a major challenge for Indoor/Outdoor building modeling. The basic idea of the contribution presented in this paper consists in extracting planar polygons from indoor and outdoor LiDAR scans, and then matching them. In order to cope with the very small overlap between indoor and outdoor scans of the same building, we propose to start by extracting points lying in the buildings’ interior from the outdoor scans as points where the laser ray crosses detected façades. Since, within a building environment, most of the objects are bounded by a planar surface, we propose a new registration algorithm that matches planar polygons by clustering polygons according to their normal direction, then by their offset in the normal direction. We use this clustering to find possible polygon correspondences (hypotheses) and estimate the optimal transformation for each hypothesis. Finally, a quality criteria is computed for each hypothesis in order to select the best one. To demonstrate the accuracy of our algorithm, we tested it on real data with a static indoor acquisition and a dynamic (Mobile Laser Scanning) outdoor acquisition.

• [hal-03413413] Reordering a tree according to an order on its leaves

  In this article, we study two problems consisting in reordering a tree to fit with an order on its leaves provided as input, which were earlier introduced in the context of phylogenetic tree comparison for bioinformatics, OTCM and OTDE. The first problem consists in finding an order which minimizes the number of inversions with an input order on the leaves, while the second one consists in removing the minimum number of leaves from the tree to make it consistent with the input order on the remaining leaves. We show that both problems are NP-complete when the maximum degree is not bounded, as well as a problem on tree alignment, answering two questions opened in 2010 by Henning Fernau, Michael Kaufmann and Mathias Poths. We provide a polynomial-time algorithm for OTDE in the case where the maximum degree is bounded by a constant and an FPT algorithm in a parameter lower than the number of leaves to delete. Our results have practical interest not only for bioinformatics but also for digital humanities to evaluate, for example, the consistency of the dendrogram obtained from a hierarchical clustering algorithm with a chronological ordering of its leaves. We explore the possibilities of practical use of our results both on trees obtained by clustering the literary works of French authors and on simulated data, using implementations of our algorithms in Python.

• [hal-03641627] An Efficient HW/SW Design for Text Extraction from Complex Color Image

  In the context of constructing an embedded system to help visually impaired people to interpret text, in this paper, an efficient High-level synthesis (HLS) Hardware/Software (HW/SW) design for text extraction using the Gamma Correction Method (GCM) is proposed. Indeed, the GCM is a common method used to extract text from a complex color image and video. The purpose of this work is to study the complexity of the GCM method on Xilinx ZCU102 FPGA board and to propose a HW implementation as Intellectual Property (IP) block of the critical blocks in this method using HLS flow with taking account the quality of the text extraction. This IP is integrated and connected to the ARM Cortex-A53 as coprocessor in HW/SW codesign context. The experimental results show that the HLS HW/SW implementation of the GCM method on ZCU102 FPGA board allows a reduction in processing time by about 89% compared to the SW implementation. This result is given for the same potency and strength of SW implementation for the text extraction.

• [tel-03637158] Geometric and semantic joint approach for the reconstruction of digital models of buildings

  The advent of Building Information Models (BIM) in the field of construction and city management revolutionizes the way we design, build, operate and maintain our buildings. BIM models not only include the geometric aspect of the buildings but also semantic information which identifies its logical components (walls, slabs, windows, doors, etc..). While this information is fairly reasonable to create during the building design, only 1% of the building stock is renewed each year. There is therefore an increasing need for automated methods to generate BIM models on existing buildings from sensors such as simple RGB cameras or more advanced Lidar sensors which directly provide a point cloud.In this context, the goal of this thesis is to develop approaches for BIM reconstruction, including both geometric reconstruction and semantic analysis.These tasks have been explored, but an important research effort is conducted to make them more robust to the variety of use cases found in practice.3D reconstruction is usually operated based on direct 3D acquisitions such as Lidars or using photogrammetry, i.e., using pictures to triangulate key point locations and reconstruct the surface afterward. In the context of buildings, the later case is usually limited by the presence of textureless areas which make it hard for the algorithms to find key points and to triangulate them. Moreover, some parts of the buildings might be missing from the input data because of occlusions or omission from the acquisition operator.Regarding semantics in point clouds, important ambiguities exist between semantic classes: the discontinuity between a wall and a door can be hard to distinguish; a slab, a roof and a ceiling sometimes need additional context to be disentangled.In this thesis, we present three technical contributions to address these issues.First, for 3D reconstruction of building scenes, we propose the first method to reconstruct piecewise-planar scenes from images using line segments as primitives. While wide textureless areas exist in indoor scenes (e.g., walls), making it particularly difficult to detect key points, lines are often more visible and easier to detect (e.g., change of illumination at the intersection of two walls) and therefore should be used to ensure robustness of image-based reconstruction approaches. We leverage the presence of these line segments and the possibility to detect and triangulate them. This makes the method robust to textureless surfaces, and we show that we can reconstruct scenes on which point-based methods fail.The second contribution is more theoretical and addresses the problem of mesh reconstruction from multiple calibrated images of low resolution. In this context, traditional methods completely fail and directly learning priors on a large scale dataset of 3D shapes allows us to still perform reconstruction. More specifically, our method uses the learned priors to provide an initial rough shape which is further refined by incorporating geometric constraints. Our method directly outputs a mesh and competes with state of the art methods which can only output a noisy point cloud.Finally, the third technical contribution is VASAD, a dataset for volumetric and semantic reconstruction, which we created from raw BIM models available online. It is the first large scale dataset (62000m²) to offer both geometric and semantic annotation at point and mesh level. With this dataset, we propose two methods to jointly reconstruct both geometry and semantics from a point cloud and we show that the proposed dataset is challenging enough to stimulate research.

• [hal-02564349] Convergence of constant step stochastic gradient descent for non-smooth non-convex functions

  This paper studies the asymptotic behavior of the constant step Stochastic Gradient Descent for the minimization of an unknown function F , defined as the expectation of a non convex, non smooth, locally Lipschitz random function. As the gradient may not exist, it is replaced by a certain operator: a reasonable choice is to use an element of the Clarke subdifferential of the random function; an other choice is the output of the celebrated backpropagation algorithm, which is popular amongst practionners, and whose properties have recently been studied by Bolte and Pauwels [7]. Since the expectation of the chosen operator is not in general an element of the Clarke subdifferential BF of the mean function, it has been assumed in the literature that an oracle of BF is available. As a first result, it is shown in this paper that such an oracle is not needed for almost all initialization points of the algorithm. Next, in the small step size regime, it is shown that the interpolated trajectory of the algorithm converges in probability (in the compact convergence sense) towards the set of solutions of the differential inclusion. Finally, viewing the iterates as a Markov chain whose transition kernel is indexed by the step size, it is shown that the invariant distribution of the kernel converge weakly to the set of invariant distribution of this differential inclusion as the step size tends to zero. These results show that when the step size is small, with large probability, the iterates eventually lie in a neighborhood of the critical points of the mean function F .

• [hal-03633805] Assessing hierarchies by their consistent segmentations

  Recent segmentation approaches start by creating a hierarchy of nested image partitions, and then specify a segmentation from it, usually, by choosing one horizontal cut. Our first contribution is to describe several different ways, some of them new, for specifying segmentations using the hierarchy regions. Then we consider the best hierarchy-induced segmentation, in which the segments are specified by a limited number, k, of hierarchy nodes/regions. The number of hierarchy-induced segmentations grows exponentially with the hierarchy size, implying that exhaustive search is unfeasible. We focus on a common quality measure, the Jaccard index (known also as IoU). Optimizing the Jaccard index is highly nontrivial. Yet, we propose an efficient optimization * This work was done when the first author was with the Math dept. Technion, Israel.

• [tel-03629586] Systèmes de fonctions holonomes : application à la théorie des automates

  Cette thèse s'articule autour de deux parties indépendantes, qui s'intéressent à des objets différents, mais qui se rassemblent dans la méthodologie appliquée pour les étudier : nous nous appuyons essentiellement dans les deux parties sur des outils mathématiques spécialisés dans l'étude des systèmes de séries génératrices. Dans la première partie, nous étudions des arbres dont les nœuds sont étiquetés par des opérateurs, qui représentent des expressions avec une sémantique, comme les expressions régulières qui représentent des langages, ou les expressions logiques qui représentent des fonctions booléennes. Nous supposons que pour ces arbres il existe un opérateur (*) qui possède un élément absorbant P, dans le sens où tout arbre de racine (*) et dont l'un des fils est P est équivalent sémantiquement à P (par exemple, 0 est absorbant pour x, (a+b)* est absorbant pour + sur les langages à deux lettres, etc). Nous définissons à partir de cet élément absorbant une fonction de réduction σ qui réduit une expression en simplifiant de bas en haut toutes les occurrences de l'élément P sous l'opérateur (*). Cette réduction préserve la sémantique de l'arbre, par définition d'un élément absorbant. La première partie de cette thèse étudie la taille moyenne après réduction d'un arbre aléatoire de taille n, lorsque n→∞. Dans les deux premiers chapitres, nous nous sommes intéressés à des arbres d'expressions uniformes décrits respectivement par un système combinatoire et une équation récursive unidimensionnelle. Nous avons montré que la distribution uniforme était dégénérée pour ces arbres d'expression en présence d'un élément absorbant : la taille moyenne après réduction tend vers une constante lorsque n→∞. Ce résultat remet en cause l'utilité des expressions aléatoires uniformes pour l'étude de la complexité en moyenne des algorithmes, ainsi que leur pertinence pour les tests de performance automatisés (benchmarks). Nous avons ensuite affiné le résultat précédent dans le cas des expressions régulières, en utilisant plus de règles de simplifications sémantiques propres aux langages. Enfin, nous nous sommes penchés sur le comportement en moyenne de la réduction pour une autre distribution, la distribution ABR. Nous montrons que la taille moyenne après réduction dépend de la probabilité d'apparition de l'opérateur absorbant, avec des changements de phase lorsque ce paramètre varie de 0 à 1.La deuxième partie étudie le lien entre les langages formels et les propriétés de leurs séries génératrices. Nous nous intéressons en particulier à notion de non-ambiguïté de certaines classes d'automates à compteurs. Intuitivement, un automate est non ambigu si tout mot qu'il accepte est accepté par un unique calcul acceptant dans l'automate. La non-ambiguïté permet de relier par une bijection les calculs de l'automate, qui suivent un description combinatoire dictée par les transitions de l'automate, aux mots du langage accepté par l'automate. Cette bijection permet alors de traduire la structure particulière de l'automate en équation sur les séries génératrices associées à l'automate. Dans la deuxième partie, nous étudions le lien entre des classes d'automates à compteur non ambigus, dont font partie les automates de Parikh faiblement non ambigus, et la classe des séries génératrices holonomes. Nous commençons par définir de façon robuste la notion de non-ambiguïté pour ces classes d'automates, en les reliant à plusieurs classes de langages standard de la littérature. Nous utilisons ensuite le lien avec les séries génératrices holonomes pour développer des techniques de preuves d'intrinsèque ambiguïté. Nous proposons par ailleurs une preuve d'intrinsèque ambiguïté à la main d'un langage pour lequel les techniques précédentes ne s'appliquent pas. Enfin en exploitant les récurrences satisfaites par les coefficients des séries holonomes, nous produisons des bornes de complexité pour le problème de l'inclusion des automates de Parikh faiblement non ambigus

• [hal-03620996] Spatially-consistent Feature Matching and Learning for Heritage Image Analysis

  Progress in the digitization of cultural assets leads to online databases that become too large for a human to analyze. Moreover, some analyses might be challenging, even for experts. In this paper, we explore two applications of computer vision to analyze historical data: watermark recognition and one-shot repeated pattern detection in artwork collections. Both problems present computer vision challenges which we believe to be representative of the ones encountered in cultural heritage applications: limited supervision is available, the tasks are fine-grained recognition, and the data comes in several different modalities. Both applications are also highly practical, as recognizing watermarks makes it possible to date and locate documents, while detecting repeated patterns allows exploring visual links between artworks. We demonstrate on both tasks the benefits of relying on deep mid-level features. More precisely, we define an image similarity score based on geometric verification of mid-level features and show how spatial consistency can be used to fine-tune out-of-the-box features for the target dataset with weak or no supervision. This paper relates and extends our previous works. Our code and data are available at \url{http://imagine.enpc.fr/~shenx/HisImgAnalysis/}.

• [hal-03624700] Algebra and Applications 2

  [...]

• [hal-03624474] Automatic RANSAC by Likelihood Maximization

  In computer vision, and particularly in 3D reconstruction from images, it is customary to be faced with regression problems contaminated by outlying data. The standard and efficient method to deal with them is the Random Sample Consensus (RANSAC) algorithm. The procedure is simple and versatile, drawing random minimal samples from the data to estimate parameterized candidate models and ranking them based on the amount of compatible data. Such evaluation involves some threshold that separates inliers from outliers. In presence of unknown level of noise, as is usual in practice, it is desirable to remove the dependency on this fixed threshold and to estimate it as an additional unknown. Among the numerous variants of RANSAC, few, that we call "automatic", propose this approach, which involves changing the maximization criterion of consensus, as it is naturally increasing with the varying threshold. An algorithm of Zach and Cohen (ICCV 2015) uses the likelihood statistics. We present the details and the implementation of their method along with quantitative and qualitative tests on standard stereovision tasks: estimation of homography, fundamental and essential matrix. Source Code The ANSI C++ 03 implementation of the code that we provide is the one which has been peer reviewed and accepted by IPOL. The source code, the code documentation, and the online demo are accessible at the IPOL web part of this article 1. Compilation and usage instructions are included in the README.txt file of the archive.

• [hal-03624311] Permutation Pattern Matching for Doubly Partially Ordered Patterns

  We study in this paper the Doubly Partially Ordered Pattern Matching (or DPOP Matching) problem, a natural extension of the Permutation Pattern Matching problem. Permutation Pattern Matching takes as input two permutations σ and π, and asks whether there exists an occurrence of σ in π; whereas DPOP Matching takes two partial orders Pv and Pp defined on the same set X and a permutation π, and asks whether there exist |X| elements in π whose values (resp., positions) are in accordance with Pv (resp., Pp). Posets Pv and Pp aim at relaxing the conditions formerly imposed by the permutation σ, since σ yields a total order on both positions and values. Our problem being NP-hard in general (as Permutation Pattern Matching is), we consider restrictions on several parameters/properties of the input, e.g., bounding the size of the pattern, assuming symmetry of the posets (i.e., Pv and Pp are identical), assuming that one partial order is a total (resp., weak) order, bounding the length of the longest chain/anti-chain in the posets, or forbidding specific patterns in π. For each such restriction, we provide results which together give a(n almost) complete landscape for the algorithmic complexity of the problem.

• [tel-03622555] Object Detection using Component-Graphs and ConvNets with Application to Astronomical Images

  This work investigates object detection algorithms with application to astronomical images. We specifically target to detect faint astronomical sources which value near the image background level. Our main directions include Mathematical Morphology (MM) and Convolutional Neural Network (ConvNet). The contributions of this study are presented in two parts:The first part proposes a novel morphological-based approach based on component-graphs and statistical hypothesis tests. The component-graphs can efficiently handle multi-band images while the statistical hypothesis tests can identify components that are significantly different from the background level. Beyond the classical component-trees and their multivariate extensions, the component-graph holds the complete structural information of multi-band images as directed acyclic graphs (DAGs). Such DAGs are more general and more powerful at the cost of non-trivial object filtering algorithms. Then, we introduce two algorithms to filter duplicated and partial components in the component-graphs. Experiments demonstrate that our proposed approach significantly improves object detection on both multi-band simulated and real astronomical images.The second part turns our attention to ConvNet direction.We introduce a real dataset of annotated astronomical objects.Based on this dataset, we propose two models: a ConvNet-based model and a hybrid model. The ConvNet-based model tailors astronomical contexts with three novel components, including a normalization layer, an object differentiation module, and a smoothness regularizer. Besides, the hybrid model uses both Morphology and ConvNet. In the hybrid method, morphological modules select region proposals while ConvNet extracts relevant information from the selected proposals. Ablation studies show that the two proposed models outperform the state of the art on both synthetic and real datasets

• [hal-03622470] Weak quasi-symmetric functions, Rota–Baxter algebras and Hopf algebras

  [...]

• [hal-03622468] The Hopf algebras of signed permutations, of weak quasi-symmetric functions and of Malvenuto-Reutenauer

  [...]

• [hal-03621710] Automated method for real-time AMD screening of fundus images dedicated for mobile devices

  Aged macular degeneration (AMD) leads to a progressive decline in visual acuity until reaching blindness. It is considered as an irreversible pathology where an early diagnosis remains crucial. However, the lack of ophthalmologists, the permanent increase in elderly people, and their limited mobility involves a delay in AMD diagnosis. In this paper, we propose an automated method for AMD screening. The proposed processing pipeline consists in applying the well-known Radon transform to the macula region in order to model the AMD lesions even with a moderate quality of smartphone-captured fundus images. Thereby, the relevant features are carefully selected, related to the main proprieties of drusens, and then provided to an SVM classifer. The implementation of the method into a smartphone associated to a fundus image capturing device leads to a mobile CAD system that performs higher performance AMD screening. Within this framework and to achieve a real-time implementation, an optimization approach is suggested in order to reduce the processing workload. The evaluation of our method is carried out through the three public STARE, REFUGE, and RFMiD databases. A 4-fold cross-validation approach is used to evaluate the method performance where accuracies of 100%, 95.2%, and 94.3% are respectively obtained with STARE, REFUGE, and RFMiD databases. Comparisons with the state-of-the-art methods in the literature are done. Thereafter, the robustness of the proposed method was evaluated and proved. We note that 100% accuracy was preserved despite the use of degraded quality fundus images as noisy and blurred. Moreover, the propounded method was implemented in S7-Edge and S9 Smartphone devices, where the execution times of 19 and 15 milliseconds were respectively achieved, which proves the AMD real-time detection. Taking advantage of its mobility, cost-efective, detection performance, and reduced execution time, our proposed method seems a good solution for real-time AMD screening on mobile devices.

• [hal-03621303] Noncommutative Bell polynomials and the dual immaculate basis

  [...]

• [hal-03621285] A Noncommutative Cycle Index and New Bases of Quasi-symmetric Functions and Noncommutative Symmetric Functions

  [...]

• [hal-03621275] Quadri-algebras, preLie algebras, and the Catalan family of Lie idempotents

  We compute the expansion of the Catalan family of Lie idempotents introduced in [Menous et al., Adv. Applied Math. 51 (2013), 177-22] on the PBW basis of the Lie module. It is found that the coefficient of a tree depends only on its number of left and right internal edges. In particular, the Catalan idempotents belong to a preLie algebra based on naked binary trees, of which we identify several Lie and preLie subalgebras.

• [hal-03621252] Pinnacle sets revisited

  In 2017, Davis, Nelson, Petersen, and Tenner [Discrete Math. 341 (2018),3249--3270] initiated the combinatorics of pinnacles in permutations. We provide a simple and efficient recursion to compute $p_n(S)$, the number of permutations of $S_n$ with pinnacle set $S$, and a conjectural closed formula for the related numbers $q_n(S)$. We determine the lexicographically minimal elements of the orbits of the modified Foata-Strehl action, prove that these elements form a lower ideal of the left weak order and characterize and count the maximal elements of this ideal.

• [hal-03621249] Noncommutative Symmetric Functions and Lagrange Inversion II: Noncrossing partititions and the Farahat-Higman algebra

  We introduce a new pair of mutually dual bases of noncommutative symmetric functions and quasi-symmetric functions, and use it to derive generalizations of several results on the reduced incidence algebra of the lattice of noncrossing partitions. As a consequence, we obtain a quasi-symmetric version of the Farahat-Higman algebra.

• [hal-03585410] Self-Supervised Transformers for Unsupervised Object Discovery using Normalized Cut

  Transformers trained with self-supervised learning using self-distillation loss (DINO) have been shown to produce attention maps that highlight salient foreground objects. In this paper, we demonstrate a graph-based approach that uses the self-supervised transformer features to discover an object from an image. Visual tokens are viewed as nodes in a weighted graph with edges representing a connectivity score based on the similarity of tokens. Foreground objects can then be segmented using a normalized graph-cut to group self-similar regions. We solve the graph-cut problem using spectral clustering with generalized eigen-decomposition and show that the second smallest eigenvector provides a cutting solution since its absolute value indicates the likelihood that a token belongs to a foreground object. Despite its simplicity, this approach significantly boosts the performance of unsupervised object discovery: we improve over the recent state of the art LOST by a margin of 6.9%, 8.1%, and 8.1% respectively on the VOC07, VOC12, and COCO20K. The performance can be further improved by adding a second stage class-agnostic detector (CAD). Our proposed method can be easily extended to unsupervised saliency detection and weakly supervised object detection. For unsupervised saliency detection, we improve IoU for 4.9%, 5.2%, 12.9% on ECSSD, DUTS, DUT-OMRON respectively compared to previous state of the art. For weakly supervised object detection, we achieve competitive performance on CUB and ImageNet.

• [tel-03615171] Operads in algebraic combinatorics

  This habilitation thesis fits in the fields of algebraic and enumerative combinatorics, with connections with computer science. The main ideas developed in this work consist in endowing combinatorial objects (words, permutations, trees, integer partitions, Young tableaux, etc.) with operations in order to construct algebraic structures. This process allows, by studying algebraically the structures thus obtained (changes of bases, generating sets, presentations by generators and relations, morphisms, representations), to collect combinatorial information about the underlying objects. The algebraic structures the most encountered here are magmas, posets, associative algebras, dendriform algebras, Hopf bialgebras, operads, and pros. This work explores the aforementioned research direction and provides many (functorial or not) constructions having the particularity to build algebraic structures on combinatorial objects. We develop for instance a functor from nonsymmetric colored operads to nonsymmetric operads, from monoids to operads, from unitary magmas to nonsymmetric operads, from finite posets to nonsymmetric operads, from stiff pros to Hopf bialgebras, and from precompositions to nonsymmetric operads. These constructions bring alternative ways to describe already known structures and provide new ones, as for instance, some of the deformations of the noncommutative Faà di Bruno Hopf bialgebra of Foissy and a generalization of the dendriform operad of Loday. We also use algebraic structures to obtain enumerative results. In particular, nonsymmetric colored operads are promising devices to define formal series generalizing the usual ones. These series come with several products (for instance a pre-Lie product, an associative product, and their Kleene stars) enriching the usual ones on classical power series. This provides a framework and a toolbox to strike combinatorial questions in an original way. The text is organized as follows. The first two chapters pose the elementary notions of combinatorics and algebraic combinatorics used in the whole work. The last ten chapters contain our original research results fitting the context presented above.

• [hal-03614850] Gradient Vector Fields of Discrete Morse Functions are Minimum Spanning Forests

  In this paper, we prove that discrete Morse functions are equivalent to simplicial stacks under reasonable constraints. We also show that, as in Discrete Morse Theory, we can see the GVF of a simplicial stack (seen as a discrete Morse function) as the only relevant information we should consider. Last, but not least, we prove that the Minimum Spanning Forest on the dual graph of a simplicial stack (or a discrete Morse function) is equal to the GVF of the initial function. In other words, the GVF of a discrete Morse function is related to a classic combinatorial minimization problem. This paper is the sequel of a sequence of papers showing that strong relations exist between different domains: Topology, Discrete Morse Theory, Topological Data Analysis and Mathematical Morphology.

• [hal-03609629] Stability and upper bounds for statistical estimation of unbalanced transport potentials

  In this note, we derive upper-bounds on the statistical estimation rates of unbalanced optimal transport (UOT) maps for the quadratic cost. Our work relies on the stability of the semi-dual formulation of optimal transport (OT) extended to the unbalanced case. Depending on the considered variant of UOT, our stability result interpolates between the OT (balanced) case where the semi-dual is only locally strongly convex with respect the Sobolev semi-norm H1 dot and the case where it is locally strongly convex with respect to the H 1 norm. When the optimal potential belongs to a certain class C with sufficiently low metric-entropy, local strong convexity enables us to recover super-parametric rates, faster than 1 / root n.

• [hal-03602228] Classification Performance of RanSaC Algorithms with Automatic Threshold Estimation

  The RANdom SAmpling Consensus method (RanSaC) is a staple of computer vision systems and offers a simple way of fitting parameterized models to data corrupted by outliers. It builds many models from small sets of randomly selected data points, and then scores them to keep the best. The original scoring function is the number of inliers, points that fit the model up to some tolerance. The threshold that separates inliers from outliers is data-and model-dependent, and estimating the quality of a RanSaC method is difficult as ground truth data is scarce or not quite reliable. To remedy that, we propose a data generation method to create at will ground truths both realistic and perfectly reliable. We then compare the RanSaC methods that simultaneously fit a model and estimate an appropriate threshold. We measure their classification performance on those semisynthetic feature correspondence pairs for homography, fundamental, and essential matrices. Whereas the reviewed methods perform on par with the RanSaC baseline for standard cases, they do better in difficult cases, maintaining over 80 % precision and recall. The performance increase comes at the cost of running time and analytical complexity, and unexpected failures for some algorithms.

• [hal-02438493] A partial order on Motzkin paths

  [...]

• [hal-03592937] Software Defined Radio Platforms for Wireless Technologies

  Wireless connectivity standards have been developed to meet the requirements of various applications. To support a wireless standard, a wireless transceiver should be equipped with a Radio Frequency (RF) transceiver. Traditional RF transceivers are designed and implemented on a radio chip or an embedded module in a System-on-a-Chip (SoC), ensuring small size, high performance, low power consumption, and cost. However, this traditional implementation design limits directly or indirectly the programmability and flexibility of the RF transceivers. An alternative solution is to implement RF transceivers using Software Defined Radio (SDR) platforms. In the market, SDR platform hardware exists with different configurations, performance, cost, size, etc., making it hard to select the minimum SDR platform necessary to satisfy the wireless standard requirements. This paper aims to provide a list of well-known General Purpose Processor (GPP) based SDR platforms satisfying the minimum specifications of selected wireless standards. To this end, we first review the characteristics of selected wireless technologies. Then, we investigate existing SDR platform architecture and their maximal performance in terms of the frequency range, bandwidth, symbol rate, bitrate, and latency support. Finally, we intersect the wireless standard requirements with the corresponding SDR platform parameters and provide a list of GPP-based SDR platforms for some existing wireless technology implementations. While investigations related to frequency, bandwidth, symbol rate and bitrate are supported by theoretical results, latency is obtained from experiments by benchmarking existing implementations.

• [hal-03589598] UNITEX 3.3 Manuel d'utilisation

  Unitex est un ensemble de logiciels permettant de traiter des textes en langues naturelles en utilisant des ressources linguistiques. Ces ressources se présentent sous la forme de dictionnaires électroniques, de grammaires et de tables de lexique-grammaire. Elles sont issues de travaux initiés sur le français par Maurice Gross au Laboratoire d’Automatique Documentaire et Linguistique (LADL) . Ces travaux ont été étendus à d’autres langues au travers du réseau de laboratoires RELEX. Unitex est un moteur permettant d’exploiter ces ressources linguistiques. Ses caractéristiques techniques sont la portabilité, la modularité, la possibilité de gérer des langues possédant leur propre système d’écriture comme certaines langues asiatiques, et l’ouverture, grâce à une distribution en logiciel libre. Ses caractéristiques linguistiques sont celles qui ont motivé l’élaboration des ressources : la précision, l’exhaustivité et la prise en compte des phénomènes de figement, notamment en ce qui concerne le recensement des mots composés.

• [hal-03589580] UNITEX 3.3 User Manual

  Unitex is a collection of programs developed for the analysis of texts in natural language by using linguistic resources and tools. These resources consist of electronic dictionaries, grammars and lexicon-grammar tables, initially developed for French by Maurice Gross and his students at the Laboratoire d’Automatique Documentaire et Linguistique (LADL). Similar resources have been developed for other languages in the context of the RELEX laboratory network. Unitex can be viewed as a tool in which you can put linguistic resources and use them. Its technical characteristics are its portability, modularity, the possibility of dealing with languages that use specific writing systems (e.g. many Asian languages), and its openness, thanks to its open source distribution. Its linguistic characteristics are the ones that have motivated the elaboration of these resources: precision, completeness, and the taking into account of multiword expressions, most notably compound words.

• [tel-03582537] Topological embeddings of graphs onsimplicial complexes

  The study of topological embeddings of graphs, that is to say the ways of drawing without crossing a graph in a topological space, constitutes a classic field at the interface of mathematics and computer science in communities of topology, topological graph theory, computational topology and graph drawing. It is natural to be interested in the embeddability of graphs on general topological spaces such as the plane, surfaces or larger spaces. However, as all graphs can be embedded into a three-dimensional space, the topological spaces for which the question is non-trivial are of dimension at most two. It is thus logical to consider the class of simplicial complexes of dimension at most two, the spaces obtained by gluing together vertices, edges and triangles. In particular, these topological spaces include the class of all surfaces and the problem is already NP-hard even if we restrict ourselves to surfaces.This thesis presents two algorithms deciding the problem of the embeddability of a graph on a 2-complex. Both algorithms operate in polynomial time in the size of the graph when the complex is fixed, but only the second is fixed parameter tractable when parameterized by the size of the 2-complex given as input. The first algorithm is based on topological arguments. Its strategy consists in reducing the problem of the embeddability of a graph on a 2-complex to an embedding extension problem of a graph on a surface for which there already existed an algorithm due to B.Mohar. Moreover, at the same time, this approach also shows that the problem is in NP.The second algorithm is based on graph algorithmic arguments. It begins by iteratively removing unnecessary vertices from the graph until the graph has a bounded branch width. Then, it uses a dynamic programming strategy which decides whether a graph of bounded branch width is embeddable on a 2-complex

• [hal-03581837] Peer-to-peer overlay techniques for vehicular ad hoc networks: Survey and challenges

  Vehicular ad hoc networks (VANETs) provide an effective technology for vehicles communicating while on the road. Vehicles are organized in an ad hoc networks offering support for both safety-critical messaging, multi-hop entertainment applications, and connection to internet services through Road Side Units (RSUs). Sharing data between connected vehicles can help commuting people exchange travel information, and allows content delivery and entertainment applications using Peer-to-Peer (P2P) techniques. Despite the widely documented benefits of P2P techniques, there are a number of challenges faced when deployed in such a highly dynamic environments as VANETs. Such difficulties include the broadcast storm problem, network partition, and the temporal network fragmentation to name few. These issues are principally due to the high mobility of vehicles and thus to the constantly changing topology of the network. In this paper, we present a survey of the existing P2P approaches in the context of VANETs including a comprehensive survey of the various problems related to data sharing in VANET using P2P techniques, along with their proposed solutions from the perspective of data access, information lookup, routing, and message management. In this study, we provide a classification of the studied approaches in terms of network overlays, information structures, and network coding. To differentiate between the discussed approaches, we include a comparative study based on the crucial parameters and identify and discuss the open research challenges in P2P techniques. To the best of our knowledge, this survey constitutes the first attempt at a comprehensive analysis of P2P approaches in VANETs, which describes more appropriately the state-of-art of this specific topic of research.

• [hal-03578489] An hypervisor approach for mixed critical real-time UAV applications

  In the context of smart cities, with important population density, Unmanned Aerial Vehicles (UAV) should be certified for flying. Virtualization techniques allow us to run several applications of different criticalities on the same hardware architecture in a spatially and temporally isolated manner. This makes it possible to adapt the certification cost of an application to its criticality level. We consider the case where each application is composed of a set of sporadic tasks that are executed into a dedicated Virtual Machine (VM). The set of VMs is monitored by a hypervisor that provides them an abstraction of the underlying hardware resources. The use of an hypervisor to isolate the applications hosted into their VMs results in a two-level hierarchical system. The VMs are scheduled at the first level then the tasks of each application are scheduled at the second level. The parameters of the tasks composing the different applications are known a priori and the main contribution of this paper is to provide a sizing method for the VMs. It consists in computing both period and slot duration for each VM such that its assigned tasks are schedulable (satisfy all the deadlines of the tasks).

• [hal-03412799] An Interval Constraint Programming Approach for Quasi Capture Tube Validation

  Proving that the state of a controlled nonlinear system always stays inside a time moving bubble (or capture tube) amounts to proving the inconsistency of a set of nonlinear inequalities in the time-state space. In practice however, even with a good intuition, it is difficult for a human to find such a capture tube except for simple examples. In 2014, Jaulin et al. established properties that support a new interval approach for validating a quasi capture tube, i.e. a candidate tube (with a simple form) from which the mobile system can escape, but into which it enters again before a given time. A quasi capture tube is easy to find in practice for a controlled system. Merging the trajectories originated from the candidate tube yields the smallest capture tube enclosing it. This paper proposes an interval constraint programming solver dedicated to the quasi capture tube validation. The problem is viewed as a differential CSP where the functional variables correspond to the state variables of the system and the constraints define system trajectories that escape from the candidate tube "for ever". The solver performs a branch and contract procedure for computing the trajectories that escape from the candidate tube. If no solution is found, the quasi capture tube is validated and, as a side effect, a corrected smallest capture tube enclosing the quasi one is computed. The approach is experimentally validated on several examples having 2 to 5 degrees of freedom. 2012 ACM Subject Classification Applied computing → Operations research; Mathematics of computing → Ordinary differential equations; Mathematics of computing → Differential algebraic equations; Mathematics of computing → Interval arithmetic; Theory of computation → Constraint and logic programming

• [hal-03577464] MOD SLAM: Mixed Method for a More Robust SLAM without Loop Closing

  [...]

• [hal-03576442] Cognitive CQI/5QI Based Scheme for Software Defined 5G Hybrid Satellite-Terrestrial Network: Slicing for Ultra Reliability and Video Congestion Offloading

  [...]

• [hal-03576434] Leveraging multiuser diversity for adaptive hybrid satellite-LTE downlink scheduler (H-MUDoS) in emerging 5G-satellite network

  [...]

• [hal-03576426] High Altitude Platform Network for Disaster and Crises Application

  [...]

• [hal-03576417] Distance aware radio planning for sdn based 5G-satellite network 2020

  [...]

• [hal-03576411] Reconfiguration of LoRa Networks Parameters using Fuzzy C-Means Clustering

  [...]

• [hal-03575517] Deep Surface Reconstruction from Point Clouds with Visibility Information

  Most current neural networks for reconstructing surfaces from point clouds ignore sensor poses and only operate on raw point locations. Sensor visibility, however, holds meaningful information regarding space occupancy and surface orientation. In this paper, we present two simple ways to augment raw point clouds with visibility information, so it can directly be leveraged by surface reconstruction networks with minimal adaptation. Our proposed modifications consistently improve the accuracy of generated surfaces as well as the generalization ability of the networks to unseen shape domains. Our code and data is available at https://github.com/raphaelsulzer/dsrv-data.

• [hal-03575134] Do IoT LoRa Networks Support Emergency Evacuation Systems ?

  The number of building sites increased considerably these few last years. Emerging countries invest more and more in building and construction sites to overcome the need of citizens like education, residential and administration buildings. Such sites should be equipped with evacuation systems to allow bricklayers and other persons to be evacuated quickly. The lack of such mechanisms makes the life of billion of citizens in a danger. This problem could be addressed by building a novel evacuation emergency application in Internet of Things (IoT) devices with Low Power Wide Area Networks (LP W AN). One of the known LP W AN networks is Long Range (LoRa) network. To overcome the need of peer to peer communication between devices, IEEE.802.15.4 technology and particulary 6LowPAN could be used to allow devices to communicate in a mesh network. Our work is motivated by the deployment of an Emergency Evacuation Systems (EES) in building sites.

• [hal-03575086] Leveraging SDN slicing isolation for improved adaptive satellite-5G downlink scheduler

  Software-Defined Network (SDN) and network function virtualization (NFV) technologies are emerging paradigms and enablers for the progress towards service delivery in satelliteterrestrial networks. In This Paper, we propose a significant improvement of our previous proposal, which consists of a downlink scheduling strategy in heterogeneous satellite-LTE-A network, while leveraging SDN and NFV and their role in network slicing. Thus, the main goal of this improved scheduler is to profit from slice isolation to boost the effectiveness of radio resources management. So, as slices are fully independent, we propose adaptive scheduling metric strategies specified according to the network conditions and traffic types. Performance evaluation shows that reliability can be enhanced by reducing the packet of loss ratio achieved via isolation between slices. Results show that the QoS degradation may decrease the metrics of traffic however, this cannot influence the quality of experience in the other slices.

• [hal-03572205] Single-view robot pose and joint angle estimation via render & compare

  We introduce RoboPose, a method to estimate the joint angles and the 6D camera-to-robot pose of a known articulated robot from a single RGB image. This is an important problem to grant mobile and itinerant autonomous systems the ability to interact with other robots using only visual information in non-instrumented environments, especially in the context of collaborative robotics. It is also challenging because robots have many degrees of freedom and an infinite space of possible configurations that often result in self-occlusions and depth ambiguities when imaged by a single camera. The contributions of this work are three-fold. First, we introduce a new render & compare approach for estimating the 6D pose and joint angles of an articulated robot that can be trained from synthetic data, generalizes to new unseen robot configurations at test time, and can be applied to a variety of robots. Second, we experimentally demonstrate the importance of the robot parametrization for the iterative pose updates and design a parametrization strategy that is independent of the robot structure. Finally, we show experimental results on existing benchmark datasets for four different robots and demonstrate that our method significantly outperforms the state of the art. Code and pre-trained models are available on the project webpage https://www.di.ens.fr/willow/research/robopose/.

• [hal-03570688] Efficient and lightweight protocol for anti-jamming communications in wireless body area networks

  [...]

• [hal-03570684] Ultra-safe and reliable enhanced train-centric communication-based train control system

  [...]