HAL : Dernières publications

• [hal-03286340] Valoriser des corpus littéraires numériques avec Wikisource : de la recherche à la pédagogie

  Pour la correction de textes obtenus automatiquement par numérisation puis reconnaissance optique de caractères, il est possible d’utiliser la plateforme Wikisource. Cette plateforme collaborative, hébergée comme Wikipédia par une fondation américaine, la Wikimedia Foundation, permet de visualiser simultanément la page scannée et le texte extrait automatiquement, éventuellement parsemé d’erreurs, pour corriger ce dernier et le mettre en forme (italique, notes de bas de page, titres de chapitres, etc.). Nous montrons dans cet article qu’en utilisant Wikisource, l’étape de saisie et de formatage des textes peut devenir un moyen de transmettre des savoirs non seulement numériques mais aussi littéraires, en particulier quand elle prend la forme d’un projet pédagogique associé à un enseignement universitaire ou d’une activité de stage. Cette démarche permet de bénéficier des avantages de la pédagogie par projet, notamment un apprentissage plus actif et une pédagogie plus individualisée. Par ailleurs, ces projets sont particulièrement propices à tisser des liens entre enseignement et recherche, en faisant découvrir les méthodologies ou outils d’analyse qui exploitent les corpus ainsi constitués. Ils incitent à manipuler des outils de visualisation ou d’analyse statistique des textes et conduisent aussi à des développements spécifiques, notamment pour les phases de vérification. Enfin, en utilisant un outil collaboratif qui n’a pas été conçu dans un cadre académique, ces projets ouvrent des pistes de communication grand public à propos de projets de recherche et de science participative, en réutilisant et en valorisant au mieux les contributions bénévoles effectuées sur Wikisource.

• [hal-03272963] A new parametrization for independent set reconfiguration and applications to RNA kinetics

  In this paper, we study the Independent Set (IS) reconfiguration problem in graphs. An IS reconfiguration is a scenario transforming an IS L into another IS R, inserting/removing vertices one step at a time while keeping the cardinalities of intermediate sets greater than a specified threshold. We focus on the bipartite variant where only start and end vertices are allowed in intermediate ISs. Our motivation is an application to the RNA energy barrier problem from bioinformatics, for which a natural parameter would be the difference between the initial IS size and the threshold. We first show the para-NP hardness of the problem with respect to this parameter. We then investigate a new parameter, the cardinality range, denoted by ρ which captures the maximum deviation of the reconfiguration scenario from optimal sets (formally, ρ is the maximum difference between the cardinalities of an intermediate IS and an optimal IS). We give two different routes to show that this problem is in XP for ρ: The first is a direct O(n 2)-space, O(n 2ρ+2.5)-time algorithm based on a separation lemma; The second builds on a parameterized equivalence with the directed pathwidth problem, leading to a O(n ρ+1)-space, O(n ρ+2)-time algorithm for the reconfiguration problem through an adaptation of a prior result by Tamaki [20]. This equivalence is an interesting result in its own right, connecting a reconfiguration problem (which is essentially a connectivity problem within a reconfiguration network) with a structural parameter for an auxiliary graph. We demonstrate the practicality of these algorithms, and the relevance of our introduced parameter, by considering the application of our algorithms on random small-degree instances for our problem. Moreover, we reformulate the computation of the energy barrier between two RNA secondary structures, a classic hard problem in computational biology, as an instance of bipartite reconfiguration. Our results on IS reconfiguration thus yield an XP algorithm in O(n ρ+2) for the energy barrier problem, improving upon a partial O(n 2ρ+2.5) algorithm for the problem.

• [hal-03269425] Distributed coloring and the local structure of unit-disk graphs

  Coloring unit-disk graphs efficiently is an important problem in the global and distributed setting, with applications in radio channel assignment problems when the communication relies on omni-directional antennas of the same power. In this context it is important to bound not only the complexity of the coloring algorithms, but also the number of colors used. In this paper, we consider two natural distributed settings. In the location-aware setting (when nodes know their coordinates in the plane), we give a constant time distributed algorithm coloring any unit-disk graph $G$ with at most $(3+\epsilon)\omega(G)+6$ colors, for any constant $\epsilon>0$, where $\omega(G)$ is the clique number of $G$. This improves upon a classical 3-approximation algorithm for this problem, for all unit-disk graphs whose chromatic number significantly exceeds their clique number. When nodes do not know their coordinates in the plane, we give a distributed algorithm in the LOCAL model that colors every unit-disk graph $G$ with at most $5.68\omega(G)$ colors in $O(2^{\sqrt{\log \log n}})$ rounds. Moreover, when $\omega(G)=O(1)$, the algorithm runs in $O(\log^* n)$ rounds. This algorithm is based on a study of the local structure of unit-disk graphs, which is of independent interest. We conjecture that every unit-disk graph $G$ has average degree at most $4\omega(G)$, which would imply the existence of a $O(\log n)$ round algorithm coloring any unit-disk graph $G$ with (approximatively) $4\omega(G)$ colors.

• [hal-03268782] On the detection of low-rank signal in the presence of spatially uncorrelated noise: a frequency domain approach

  This paper analyzes the detection of a M-dimensional useful signal modeled as the output of a M ×K MIMO filter driven by a K-dimensional white Gaussian noise, and corrupted by a M-dimensional Gaussian noise with mutually uncorrelated components. The study is focused on frequency domain test statistics based on the eigenvalues of an estimate of the spectral coherence matrix (SCM), obtained as a renormalization of the frequency-smoothed periodogram of the observed signal. If N denotes the sample size and B the smoothing span, it is proved that in the high-dimensional regime where M, B, N converge to infinity while K remains fixed, the SCM behaves as a certain correlated Wishart matrix. Exploiting well-known results on the behaviour of the eigenvalues of such matrices, it is deduced that the standard tests based on linear spectral statistics of the SCM fail to detect the presence of the useful signal in the high-dimensional regime. A new test based on the SCM, which is proved to be consistent, is also proposed, and its statistical performance is evaluated through numerical simulations.

• [hal-03268401] On the asymptotic distribution of the maximum sample spectral coherence of Gaussian time series in the high dimensional regime

  We investigate the asymptotic distribution of the maximum of a frequency smoothed estimate of the spectral coherence of a M-variate complex Gaussian time series with mutually independent components when the dimension M and the number of samples N both converge to infinity. If B denotes the smoothing span of the underlying smoothed periodogram estimator, a type I extreme value limiting distribution is obtained under the rate assumptions M N → 0 and M B → c ∈ (0, +∞). This result is then exploited to build a statistic with controlled asymptotic level for testing independence between the M components of the observed time series. Numerical simulations support our results.

• [lirmm-03218029] Producing Genomic Sequences after Genome Scaffolding with Ambiguous Paths: Complexity, Approximation and Lower Bounds

  Scaffolding is the final step in assembling Next Generation Sequencing data, in which pre-assembled contiguous regions ("contigs") are oriented and ordered using information that links them (for example, mapping of paired-end reads). As the genome of some species is highly repetitive, we allow placing some contigs multiple times, thereby generalizing established computational models for this problem. We study the subsequent problems induced by the translation of solutions of the model back to actual sequences, proposing models and analyzing the complexity of the resulting computational problems. We find both polynomialtime and N P-hard special cases like planarity or bounded degree. Finally, we propose two polynomial-time approximation algorithms according to cut/weight score.

• [hal-03140696] Marceline Desbordes-Valmore sur Wikisource : plus accessible, donc plus enseignée ?

  De nombreux ouvrages de Marceline Desbordes-Valmore sont disponibles en version numérisée sur internet, par exemple sur Gallica, Google Books ou Numelyo. Pourtant, peu d'entre eux sont pleinement accessibles en version texte, permettant d'en copier/coller facilement des extraits. L'association Le deuxième texte y travaille actuellement, dans le cadre de ses activités pour mettre à disposition plus de textes écrits par des femmes, à destination notamment des enseignantes et enseignants de lettres, afin de diversifier les corpus littéraires enseignés du collège à l'université.

• [hal-03232982] Properties of Unique Degree Sequences of 3-Uniform Hypergraphs

  [...]

• [hal-03121428] Quasi-regularity verification for 2D polygonal objects based on medial axis analysis

  Quasi-regularity has been proved to be a sufficient condition for simple-connectedness preservation during the digitization process of 2D continuous objects. The original definition of quasi-regularity relies on set-based morphological operations of erosion and dilation. With this definition, quasi-regularity is algorithmically difficult to assess. In this paper, we propose a tractable framework for quasi-regularity verification, especially designed for polygons. Our approach mainly relies on the computation and analysis of the medial axis of these objects, and determines their potential quasi-regularity, and thus their ability to undergo a digitization without alteration of their topological properties. The framework is applied in the context of topology-preserving rigid motions of digital objects.

• [tel-03231061] Hierarchical image analysis: theory, algorithms, and applications

  [...]

• [hal-02008378] Rotation invariant CNN using scattering transform for image classification

  Deep convolutional neural networks accuracy is heavily impacted by rotations of the input data. In this paper, we propose a convolutional predictor that is invariant to rotations in the input. This architecture is capable of predicting the angular orientation without angle-annotated data. Furthermore, the predictor maps continuously the random rotation of the input to a circular space of the prediction. For this purpose, we use the roto-translation properties existing in the Scattering Transform Networks with a series of 3D Convolutions. We validate the results by training with upright and randomly rotated samples. This allows further applications of this work on fields like automatic re-orientation of randomly oriented datasets.

• [hal-03171597] Triplet-Watershed for Hyperspectral Image Classification

  Hyperspectral images (HSI) consist of rich spatial and spectral information, which can potentially be used for several applications. However, noise, band correlations and high dimensionality restrict the applicability of such data. This is recently addressed using creative deep learning network architectures such as ResNet, SSRN, and A2S2K. However, the last layer, i.e. the classification layer, remains unchanged and is taken to be the softmax classifier. In this article, we propose to use a watershed classifier. Watershed classifier extends the watershed operator from Mathematical Morphology for classification. In its vanilla form, the watershed classifier does not have any trainable parameters. In this article, we propose a novel approach to train deep learning networks to obtain representations suitable for the watershed classifier. The watershed classifier exploits the connectivity patterns, a characteristic of HSI datasets, for better inference. We show that exploiting such characteristics allows the Triplet-Watershed to achieve state-of-art results in supervised and semi-supervised contexts. These results are validated on Indianpines (IP), University of Pavia (UP), Kennedy Space Center (KSC) and University of Houston (UH) datasets, relying on simple convnet architecture using a quarter of parameters compared to previous state-of-the-art networks.

• [hal-01804545] Automata on Infinite Trees with Equality and Disequality Constraints Between Siblings

  This article is inspired by two works from the early 90s. The first one is by Bogaert and Tison who considered a model of automata on finite ranked trees where one can check equality and disequality constraints between direct subtrees: they proved that this class of automata is closed under Boolean operations and that both the emptiness and the finiteness problem of the accepted language are decidable. The second one is by Niwinski who showed that one can compute the cardinality of any ω-regular language of infinite trees. Here, we generalise the model of automata of Tison and Bogaert to the setting of infinite binary trees. Roughly speaking we consider parity tree automata where some transitions are guarded and can be used only when the two direct sub-trees of the current node are equal/disequal. We show that the resulting class of languages encompasses the one of ω-regular languages of infinite trees while sharing most of its closure properties, in particular it is a Boolean algebra. Our main technical contribution is then to prove that it also enjoys a decidable cardinality problem. In particular, this implies the decidability of the emptiness problem.

• [hal-03014435] Collapsible Pushdown Parity Games

  This paper studies a large class of two-player perfect-information turn-based parity games on infinite graphs, namely those generated by collapsible pushdown automata. The main motivation for studying these games comes from the connections from collapsible pushdown automata and higher-order recursion schemes, both models being equi-expressive for generating infinite trees. Our main result is to establish the decidability of such games and to provide an effective representation of the winning region as well as of a winning strategy. Thus, the results obtained here provide all necessary tools for an in-depth study of logical properties of trees generated by collapsible pushdown automata/recursion schemes.

• [hal-03014425] Higher-Order Recursion Schemes and Collapsible Pushdown Automata: Logical Properties

  This paper studies the logical properties of a very general class of infinite ranked trees, namely those generated by higher-order recursion schemes. We consider three main problems -- model-checking, logical refection (aka global model-checking) and selection -- for both monadic second-order logic and modal mu-calculus and prove that they can be effectively answered positively. For that, we rely on the known connexion between higher-order recursion schemes and collapsible pushdown automata and on previous work regarding parity games played on transition graphs of collapsible pushdown automata.

• [hal-03226871] On the group of a rational maximal bifix code

  Abstract We give necessary and sufficient conditions for the group of a rational maximal bifix code Z to be isomorphic with the F -group of Z ∩ F {Z ∪ F} , when F is recurrent and Z ∩ F {Z ∪ F} is rational. The case where F is uniformly recurrent, which is known to imply the finiteness of Z ∩ F {Z ∪ F} , receives special attention. The proofs are done by exploring the connections with the structure of the free profinite monoid over the alphabet of F .

• [hal-03226869] Decidable properties of extension graphs for substitutive languages

  Given a set of words S, one can associate with every word w ∈ S its extension graph which describes the possible left and right extensions of w in S. Families of sets can be defined from the properties of the extension graph of their elements: acyclic sets, tree sets, neutral sets, etc. In this paper we study the specific case of the set of factors of a substitutive language and we show that it is decidable whether these properties are verified or not.

• [hal-03225334] Further steps on the reconstruction of convex polyominoes from orthogonal projections

  Abstract A remarkable family of discrete sets which has recently attracted the attention of the discrete geometry community is the family of convex polyominoes, that are the discrete counterpart of Euclidean convex sets, and combine the constraints of convexity and connectedness. In this paper we study the problem of their reconstruction from orthogonal projections, relying on the approach defined by Barcucci et al. (Theor Comput Sci 155(2):321–347, 1996). In particular, during the reconstruction process it may be necessary to expand a convex subset of the interior part of the polyomino, say the polyomino kernel, by adding points at specific positions of its contour, without losing its convexity. To reach this goal we consider convexity in terms of certain combinatorial properties of the boundary word encoding the polyomino. So, we first show some conditions that allow us to extend the kernel maintaining the convexity. Then, we provide examples where the addition of one or two points causes a loss of convexity, which can be restored by adding other points, whose number and positions cannot be determined a priori.

• [tel-03224484] 2D and 3D Geometric Attributes Estimation in Images via deep learning

  The visual perception of 2D and 3D geometric attributes (e.g. translation, rotation, spatial size and etc.) is important in robotic applications. It helps robotic system build knowledge about its surrounding environment and can serve as the input for down-stream tasks such as motion planning and physical intersection with objects.The main goal of this thesis is to automatically detect positions and poses of interested objects for robotic manipulation tasks. In particular, we are interested in the low-level task of estimating occlusion relationship to discriminate different objects and the high-level tasks of object visual tracking and object pose estimation.The first focus is to track the object of interest with correct locations and sizes in a given video. We first study systematically the tracking framework based on discriminative correlation filter (DCF) and propose to leverage semantics information in two tracking stages: the visual feature encoding stage and the target localization stage. Our experiments demonstrate that the involvement of semantics improves the performance of both localization and size estimation in our DCF-based tracking framework. We also make an analysis for failure cases.The second focus is using object shape information to improve the performance of object 6D pose estimation and do object pose refinement. We propose to estimate the 2D projections of object 3D surface points with deep models to recover object 6D poses. Our results show that the proposed method benefits from the large number of 3D-to-2D point correspondences and achieves better performance. As a second part, we study the constraints of existing object pose refinement methods and develop a pose refinement method for objects in the wild. Our experiments demonstrate that our models trained on either real data or generated synthetic data can refine pose estimates for objects in the wild, even though these objects are not seen during training.The third focus is studying geometric occlusion in single images to better discriminate objects in the scene. We first formalize geometric occlusion definition and propose a method to automatically generate high-quality occlusion annotations. Then we propose a new occlusion relationship formulation (i.e. abbnom) and the corresponding inference method. Experiments on occlusion reasoning benchmarks demonstrate the superiority of the proposed formulation and method. To recover accurate depth discontinuities, we also propose a depth map refinement method and a single-stage monocular depth estimation method.All the methods that we propose leverage on the versatility and power of deep learning. This should facilitate their integration in the visual perception module of modern robotic systems.Besides the above methodological advances, we also made available software (for occlusion and pose estimation) and datasets (of high-quality occlusion information) as a contribution to the scientific community

• [hal-02768998] An application of the universality theorem for Tverberg partitions to data depth and hitting convex sets

  [...]

• [hal-03222093] O(1)-online approximation of the slack for periodic task sets under EDF scheduling

  Scheduling tasks is one of the most challenging problems in real-time systems. In this paper, we assume that hard deadline periodic tasks are scheduled preemptively according to the Earliest Deadline First algorithm on uniprocessor. This work presents a framework for enhancing predictability in system behavior, when periodic task execution can be postponed. Our analysis first determines a lower bound to the slack defined as the time which may be stolen from hard deadline periodic tasks, without jeopardizing their timing constraints. Second, we show how to implement an efficient method for estimating the slack at run-time. This can be adopted to overcome practical situations where the slack has to be computed dynamically with acceptable time overheads.

• [hal-03218180] Aspecto verbal nas construções com verbo-suporte

  Este artigo tem o objetivo de discutir sobre o aspecto verbal nas Construções com Verbo-Suporte (CVS) e com extensões de verbo-suporte, focalizando a função semântica que os verbos podem ter quando exprimem aspecto. Para isso, analisamos a relação entre frases formadas com vários verbos-suporte e que diferem pelo aspecto. Por exemplo, as frases "Zé (ganhou + está com + perdeu a) coragem" indicam os aspectos incoativo, durativo e terminativo, respectivamente. Muito se discute sobre as CVS, mas o aspecto nessas construções ainda é um assunto de pouco interesse entre os pesquisadores no Brasil. Essa pesquisa está embasada no modelo teórico-metodológico do Léxico-Gramática (LG), desenvolvido por Gross (1975). O LG propõe a descrição e formalização dos itens lexicais em tábuas. Dessa forma, como resultado da descrição formal, apresentamos duas tábuas, que podem ser utilizadas no Processamento de linguagem natural (PLN), por meio de programas de computador.

• [hal-03216019] Unsupervised Layered Image Decomposition into Object Prototypes

  We present an unsupervised learning framework for decomposing images into layers of automatically discovered object models. Contrary to recent approaches that model image layers with autoencoder networks, we represent them as explicit transformations of a small set of prototypical images. Our model has three main components: (i) a set of object prototypes in the form of learnable images with a transparency channel, which we refer to as sprites; (ii) differentiable parametric functions predicting occlusions and transformation parameters necessary to instantiate the sprites in a given image; (iii) a layered image formation model with occlusion for compositing these instances into complete images including background. By jointly learning the sprites and occlusion/transformation predictors to reconstruct images, our approach not only yields accurate layered image decompositions, but also identifies object categories and instance parameters. We first validate our approach by providing results on par with the state of the art on standard multi-object synthetic benchmarks (Tetrominoes, Multi-dSprites, CLEVR6). We then demonstrate the applicability of our model to real images in tasks that include clustering (SVHN, GTSRB), cosegmentation (Weizmann Horse) and object discovery from unfiltered social network images. To the best of our knowledge, our approach is the first layered image decomposition algorithm that learns an explicit and shared concept of object type, and is robust enough to be applied to real images.

• [hal-03210968] An algebraic framework for out-of-core hierarchical segmentation algorithms

  Binary partition hierarchies and minimum spanning trees are key structures for numerous hierarchical analysis methods, as those involved in computer vision and mathematical morphology. In this article, we consider the problem of their computation in an out-of-core manner, i.e., by minimizing the size of the data structures that are simultaneously needed at the different computation steps. Out-of-core algorithms are necessary when the data are too large to fit entirely in the main memory of the computer, which can be the case with very large images in 2-, 3-, or higher dimension space. We propose a new algebraic framework composed of four main operations on hierarchies: edge-addition, select, insert, and join. Based on this framework, we propose and establish the correctness of an out-of-core calculus for binary partition hierarchies and for minimum spanning trees. First applications to image processing suggest the practical efficiency of this calculus.

• [hal-03206132] 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>i.e.</I> 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.

• [hal-03205034] Fine-tuning Convolutional Neural Networks: a comprehensive guide and benchmark analysis for Glaucoma Screening

  This work aimed at giving a comprehensive, indetailed and benchmark guide on the route to fine-tuning Convolutional Neural Networks (CNNs) for glaucoma screening. Transfer learning consists in a promising alternative to train CNNs from scratch, to avoid the huge data and resources requirements. After a thorough study of five state-of-the-art CNNs architectures, a complete and well-explained strategy for fine-tuning these networks is proposed, using hyperparameter grid-searching and two-phase training approach. Excellent performance is reached on model evaluation, with a 0.9772 AUROC validation rate, giving arise to reliable glaucoma diagnosis-help systems. Also, a baseline benchmark analysis is conducted, studying the models according to performance indices such as model complexity and size, AUROC density and inference time. This in-depth analysis allows a rigorous comparison between model characteristics, and is useful for giving practioners important trademarks for prospective applications and deployments.

• [hal-03198895] Fusion entre bases de données hétérogènes concernant la pollution des sols

  [...]

• [hal-03195118] Secure and efficient Key Exchange Mechanism for Heterogeneous Connected Objects

  The fast evolution in microelectronics and the emergence of wireless communication technologies, have allowed the appearance of the promising field of Internet of Things (IoT). The latter is more and more present in the human life, that is why it becomes essential to secure the communications done with the connected objects. Almost all communicating systems attach great importance to security, consequently, on the cryptographic key management. The existing key management schemes for conventional networks are relatively resource-intensive, that is why they are not adequate for resource-constrained networks like IoT, especially since the nodes' capabilities are heterogeneous. In this paper, we focus on exchanging and updating of cryptographic keys among the IoT objects often limited in resources, where we propose a new form of key exchange based on the mechanism of concealing encryption keys, while exploiting the misused spaces in the header fields of the exchanged packets by the communication standards, such as ZigBee, BLE, WiFi.

• [hal-03190430] Selection of relays based on the classification of mobility‐type and localized network metrics in the Internet of Vehicles

  [...]

• [hal-03189452] Software‐defined networking in vehicular networks: A survey

  [...]

• [hal-03185736] Timed Systems through the Lens of Logic

  In this paper, we analyze timed systems with data structures. We start by describing behaviors of timed systems using graphs with timing constraints. Such a graph is called realizable if we can assign time-stamps to nodes or events so that they are consistent with the timing constraints. The logical definability of several graph properties [20], [10] has been a challenging problem, and we show, using a highly nontrivial argument, that the realizability property for collections of graphs with strict timing constraints is logically definable in a class of propositional dynamic logic (EQ-ICPDL), which is strictly contained in MSO. Using this result, we propose a novel, algorithmically efficient and uniform proof technique for the analysis of timed systems enriched with auxiliary data structures, like stacks and queues. Our technique unravels new results (for emptiness checking as well as model checking) for timed systems with richer features than considered so far, while also recovering existing results.

• [hal-03174934] Some properties of the parking function poset

  In 1980, Edelman defined a poset on objects called the noncrossing 2-partitions. They are closely related with noncrossing partitions and parking functions. To some extent, his definition is a precursor of the parking space theory, in the framework of finite reflection groups. We present some enumerative and topological properties of this poset. In particular, we get a formula counting certain chains, that encompasses formulas for Whitney numbers (of both kinds). We prove shellability of the poset, and compute its homology as a representation of the symmetric group. We moreover link it with two well-known polytopes : the associahedron and the permutohedron.

• [hal-03179706] Fuzzy-marker-based segmentation using hierarchies

  This article extends a classical marker-based image segmentation method proposed by Salembier and Garrido in 2000. In the original approach, the segmentation relies on two sets of pixels which play the role of object and background markers. In the proposed extension, the markers are not represented by crisp sets, but by fuzzy ones, i.e., functions of the image domain into the real interval [0, 1] indicating the degree of membership of each pixel to the markers. We show that when the fuzzy markers are indicator functions of crisp sets, the proposed method produces the same result as the original one. We present a linear-time algorithm for computing the result of the proposed method given two fuzzy markers and we establish the correctness of this algorithm. Additionally, we discuss possible applications of the proposed approach, such as adjusting marker strength in interactive image segmentation procedures and optimizing marker locations with gradient descent methods.

• [hal-03176662] Higher-order recursion schemes and their automata models

  [...]

• [hal-03171076] Graph-based Supervoxel Computation from Iterative Spanning Forest

  [...]

• [hal-03171063] An Equivalence Relation between Morphological Dynamics and Persistent Homology in n-D

  In Mathematical Morphology (MM), dynamics are used to compute markers to proceed for example to watershed-based image decomposition. At the same time, persistence is a concept coming from Persistent Homology (PH) and Morse Theory (MT) and represents the stability of the extrema of a Morse function. Since these concepts are similar on Morse functions, we studied their relationship and we found, and proved, that they are equal on 1D Morse functions. Here, we propose to extend this proof to n-D, n ≥ 2, showing that this equality can be applied to n-D images and not only to 1D functions. This is a step further to show how much MM and MT are related.

• [hal-03170604] Reliable and adaptive distributed public-key management infrastructure for the Internet of things

  The Internet of Things (IoT) is an emerging paradigm in the world of computer networks, where physical objects are connected over the Internet. Given the huge number of connected devices that are potentially vulnerable, highly significant risks emerge around the issues of communication security. Unfortunately, the conventional security methods are hard to adapt due to the heterogeneity and resource-constrained objects. In this paper, we propose a reliable and adaptive distributed public-key management infrastructure for the IoT. The main purpose of our proposal is to mitigate the resource issue for publickey certificate management to design an effective security mechanism, which offers reliable end-to-end security services. In order to evaluate the performances of our proposal, we have conducted intensive simulations with comparison to the literature, in which we have obtained promising results in terms of storage, communication, response time and resilience against malicious nodes.

• [hal-03168979] Visiting bijective digitized reflections and rotations using geometric algebra

  Geometric algebra has become popularly used in applications dealing with geometry. This framework allows us to reformulate and redefine problems involving geometric transformations in a more intuitive and general way. In this paper, we focus on 2D bijective digitized reflections and rotations. After defining the digitization through geometric algebra, we characterize the set of bijective digitized reflections in the plane. We derive new bijective digitized rotations as compositions of bijective digitized reflections since any rotation is represented as the composition of two reflections. We also compare them with those obtained through geometric transformations by computing their distributions.

• [hal-03161362] Deep learning‐enabled imaging flow cytometry for high‐speed Cryptosporidium and Giardia detection

  Imaging flow cytometry has become a popular technology for bioparticle image analysis because of its capability of capturing thousands of images per second. Nevertheless, the vast number of images generated by imaging flow cytometry imposes great challenges for data analysis especially when the species have similar morphologies. In this work, we report a deep learning-enabled high-throughput system for predicting Cryptosporidium and Giardia in drinking water. This system combines imaging flow

• [tel-03157297] Synchronizing automata and coding theory

  This thesis is devoted to studying synchronizing words for finite automata and variable-length codes. Intuitively, a synchronizing word is a word such that its application brings a system into some particular state regardless of its initial state. A code or automaton is synchronizing if it admits a synchronizing word. There is a deep connection between the concrete implementations of this notion for finite automata and variable-length codes, and the use of it is one of the leitmotifs of this thesis.One of the main tools for dealing with variable-length codes is assigning a special automaton preserving many synchronization properties to it. For finite codes, this is done using prefix automata.We investigate two fundamental problems about synchronization. The first one is measuring the length of shortest synchronizing words for synchronizing automata and codes. For the case of complete deterministic finite automata, the Černý conjecture, one of the oldest problems in combinatorial automata theory, proposes a quadratic upper bound in terms of the number of states in the automaton. We broaden this conjecture to partial deterministic finite automata and then to unambiguous non-deterministic finite automata. We show polynomial upper bounds for mentioned classes in the presence of strong connectivity, and discuss their connections with the original Černý conjecture.The relation with finite codes allows us to show similar bounds in terms of the sum of the lengths of the codewords, as well as in terms of the length of the longest codeword. The second case is related to another important conjecture stated by Restivo. It deals with mortal words instead of synchronizing ones, the case which we also investigate. For most of these settings we also examine the computational complexity of finding short synchronizing words, which is the second fundamental question investigated in this thesis. Besides that, we study various generalization of the notion of a synchronizing word, which allow to use some partial information about the current state of an automaton. For several such generalizations we show strong computational complexity lower bounds even in very restricted cases

• [hal-03157244] The Polar Epipolar Rectification

  Epipolar rectification of a stereo pair is the process of resampling a pair of stereo images so that the apparent motion of corresponding points is horizontal. This is an important preliminary step in depth estimation, substituting depth by disparity estimation. Most methods rely on a perspective transform of both images, which has the advantage to simulate a different attitude of the pinhole cameras. A limitation is that when an epipole is inside the image domain, it has to be sent to infinity by the perspective transform, producing a strong distortion. On the contrary, relying on a polar transform centered at the epipole provides a method applicable universally to a pair of pinhole camera views. We present in detail the algorithm, filling in the information important for its implementation and missing in published articles.

• [hal-03152958] An experimental study of forbidden patterns in geometric permutations by combinatorial lifting

  We study the problem of deciding if a given triple of permutations can be realized as geometric permutations of disjoint convex sets in R3. We show that this question, which is equivalent to deciding the emptiness of certain semi-algebraic sets bounded by cubic polynomials, can be ``lifted'' to a purely combinatorial problem. We propose an effective algorithm for that problem, and use it to gain new insights into the structure of geometric permutations. In particular, we prove that all triples of permutations of size 5 are realizable, and give a complete list of triples of size 6 that are not.

• [hal-03152576] Quotients of the Magmatic Operad: Lattice Structures and Convergent Rewrite Systems

  A. We study quotients of the magmatic operad, that is the free nonsymmetric operad over one binary generator. In the linear setting, we show that the set of these quotients admits a lattice structure and we show an analog of the Grassmann formula for the dimensions of these operads. In the nonlinear setting, we define comb associative operads, that are operads indexed by nonnegative integers generalizing the associative operad. We show that the set of comb associative operads admits a lattice structure, isomorphic to the lattice of nonnegative integers equipped with the division order. Driven by computer experimentations, we provide a finite convergent presentation for the comb associative operad in correspondence with 3. Finally, we study quotients of the magmatic operad by one cubic relation by expressing their Hilbert series and providing combinatorial realizations.

• [hal-03152571] Colored operads, series on colored operads, and combinatorial generating systems

  A. We introduce bud generating systems, which are used for combinatorial generation. They specify sets of various kinds of combinatorial objects, called languages. They can emulate context-free grammars, regular tree grammars, and synchronous grammars, allowing us to work with all these generating systems in a unified way. The theory of bud generating systems uses colored operads. Indeed, an object is generated by a bud generating system if it satisfies a certain equation in a colored operad. To compute the generating series of the languages of bud generating systems, we introduce formal power series on colored operads and several operations on these. Series on colored operads are crucial to express the languages specified by bud generating systems and allow us to enumerate combinatorial objects with respect to some statistics. Some examples of bud generating systems are constructed; in particular to specify some sorts of balanced trees and to obtain recursive formulas enumerating these.

• [hal-03152558] Tree series and pattern avoidance in syntax trees

  A syntax tree is a planar rooted tree where internal nodes are labeled on a graded set of generators. There is a natural notion of occurrence of contiguous pattern in such trees. We describe a way, given a set of generators G and a set of patterns , to enumerate the trees constructed on G and avoiding. The method is built around inclusion-exclusion formulas forming a system of equations on formal power series of trees, and composition operations of trees. This does not require particular conditions on the set of patterns to avoid. We connect this result to the theory of nonsymmetric operads. Syntax trees are the elements of such free structures, so that any operad can be seen as a quotient of a free operad. Moreover, in some cases, the elements of an operad can be seen as trees avoiding some patterns. Relying on this, we use operads as devices for enumeration: given a set of combinatorial objects we want enumerate, we endow it with the structure of an operad, understand it in term of trees and pattern avoidance, and use our method to count them. Several examples are provided.

• [hal-03135811] Energy-aware key management and access control for the internet of things

  The need to establish a secure communication for most applications of Internet of Things (IoT) has become increasingly crucial. Nevertheless, one of the major issues of such networks is how to establish cryptographic keys between all IoT objects to ensure secure data exchange. Several key management schemes have been suggested in the literature to achieve this goal, but they must be revised and innovated, while taking into account the limited resources of IoT objects. Likewise, the IoT presents a system where objects belonging to the physical world, are connected to the Internet, and have the capacity to measure, communicate, and act around all over the world. Nevertheless, some information available to IoT objects is private, hence the need to ensure an access control whose aim is to guarantee that the information be accessible only to those whose the access is allowed. In this paper, we propose a scheme involving two basic modules, namely key management, and access control. The key management module is designed to ensure the symmetric key generation for the IoT objects in a completely distributed manner without resorting to a central authority. In contrast, the access control module is used to impose an access control policy so as to prevent unauthorized access to services provided by a particular IoT object. The latter is ensured thanks to the existing cooperation between the TGOs servers of dierent domains in the IoT. Through assessments based on security analysis, we demonstrate that the proposed scheme is more secure than the existing ones. Simulations were also performed to validate the proposed solution by comparing it with some relevant concurrent schemes. The obtained results are not only encouraging, but also very favorable for the proposed scheme.

• [hal-03148815] Predicting Sharp and Accurate Occlusion Boundaries in Monocular Depth Estimation Using Displacement Fields

  [...]

• [hal-03148810] SharpNet: Fast and Accurate Recovery of Occluding Contours in Monocular Depth Estimation

  We introduce SharpNet, a method that predicts an accurate depth map given a single input color image, with a particular attention to the reconstruction of occluding contours: Occluding contours are an important cue for object recognition, and for realistic integration of virtual objects in Augmented Reality, but they are also notoriously difficult to reconstruct accurately. For example, they are a challenge for stereo-based reconstruction methods, as points around an occluding contour are only visible in one of the two views. Inspired by recent methods that introduce normal estimation to improve depth prediction, we introduce novel terms to constrain normals, depth and occluding contours predictions. Since ground truth depth is difficult to obtain with pixel-perfect accuracy along occluding contours, we use synthetic images for training, followed by fine-tuning on real data. We demonstrate our approach on the challenging NYUv2-Depth dataset, and show that our method outperforms the state-of-the-art along occluding contours, while performing on par with the best recent methods for the rest of the images. Its accuracy along the occluding contours is actually better than the "ground truth" acquired by a depth camera based on structured light. We show this by introducing a new benchmark based on NYUv2-Depth for evaluating occluding contours in monocular reconstruction, which is our second contribution.

• [hal-03145943] On the Degeneracy of Random Expressions Specified by Systems of Combinatorial Equations

  We consider general expressions, which are trees whose nodes are labeled with operators, that represent syntactic descriptions of formulas. We assume that there is an operator that has an absorbing pattern and prove that if we use this property to simplify a uniform random expression with n nodes, then the expected size of the result is bounded by a constant. In our framework, expressions are defined using a combinatorial system, which describes how they are built: one can ensure, for instance, that there are no two consecutive stars in regular expressions. This generalizes a former result where only one equation was allowed, confirming the lack of expressivity of uniform random expressions.

• [hal-03145930] Uniform Random Expressions Lack Expressivity

  In this article, we question the relevance of uniform random models for algorithms that use expressions as inputs. Using a general framework to describe expressions, we prove that if there is a subexpression that is absorbing for a given operator, then, after repeatedly applying the induced simplification to a uniform random expression of size n, we obtain an equivalent expression of constant expected size. This proves that uniform random expressions lack expressivity, as soon as there is an absorbing pattern. For instance, (a + b) is absorbing for the union for regular expressions on {a, b}, hence random regular expressions can be drastically reduced using the induced simplification.