Search

International audience; We propose an efficient method to model paper tearing in the context of interactive modeling. The method uses geometrical information to automatically detect potential starting points of tears. We further introduce a new hybrid geometrical and physical-based method to compute the trajectory of tears while procedurally synthesizing high resolution details of the tearing path using a texture based approach. The results obtained are compared with real paper and with previous studies on the expected geometric paths of paper that tears.

International audience; This paper analyses the security of dirty paper trellis (DPT) watermarking schemes which use both informed coding and informed em- bedding. After recalling the principles of message embedding with DPT watermarking, the secret parameters of the scheme are highlighted. The security weaknesses of DPT watermarking are then presented: in the wa- termarked contents only attack (WOA) setup, the watermarked data-set exhibits clusters corresponding to the different patterns attached to the arcs of the trellis. The K-means clustering algorithm is used to estimate these patterns and a co-occurrence analysis is performed to retrieve the connectivity of the trellis. Experimental results demonstrate that it is possible to accurately estimate the trellis configuration, which enables to perform attacks much more efficient than simple additive white Gaus- sian noise (AWGN).

International audience; The goal of this study was to evaluate the areal mass distribution (defined as the X-ray transmission image) of paper from its optical transmission image. A Bayesian inversion framework was used in the related deconvolution process so as to combine indirect optical information with a priori knowledge about the type of paper imaged. The a priori knowledge was expressed in the form of an empirical Besov space prior distribution constructed in a computationally effective way using the wavelet transform. The estimation process took the form of a large-scale optimization problem, which was in turn solved using the gradient descent method of Barzilai and Borwein. It was demonstrated that optical transmission images can indeed be transformed so as to fairly closely resemble the ones that reflect the true areal distribution of mass. Furthermore, the Besov space prior was found to give better results than the classical Gaussian smoothness prior (here equivalent to Tikhonov regularization).

We describe a new binning technic for informed data hiding problem. In information theoretical point of view, the blind watermarking problem can be seen as transmitting a secret message M through a noisy channel on top of an interfered host signal S that is available only at the encoder. We propose an embedding scheme based on Low Density Parity Check(LDPC) codes, in order to quantize the host signal in an intelligent manner so that the decoder can extract the hidden message with a high probability. A mixture of erasure and symmetric error channel is realized for the analysis of the proposed method.

Motivation One of the most widespread methods used in taxonomy studies to distinguish between strains or taxa is the calculation of average nucleotide identity. It requires a computationally expensive alignment step and is therefore not suitable for large-scale comparisons. Short oligonucleotide-based methods do offer a faster alternative but at the expense of accuracy. Here, we aim to address this shortcoming by providing a software that implements a novel method based on short-oligonucleotide frequencies to compute inter-genomic distances. Results Our tetranucleotide and hexanucleotide implementations, which were optimized based on a taxonomically well-defined set of over 200 newly sequenced bacterial genomes, are as accurate as the short oligonucleotide-based method TETRA and average nucleotide identity, for identifying bacterial species and strains, respectively. Moreover, the lightweight nature of this method makes it applicable for large-scale analyses. Availability and implementation The method introduced here was implemented, together with other existing methods, in a dependency-free software written in C, GenDisCal, available as source code from https://github.com/LM-UGent/GenDisCal. The software supports multithreading and has been tested on Windows and Linux (CentOS). In addition, a Java-based graphical user interface that acts as a wrapper for the software is also available. Supplementary information Supplementary data are available at Bioinformatics online.

SIMBAD is a sequence-independent molecular-replacement pipeline for solving difficult molecular-replacement cases where contaminants have been crystallized. It can also be used to find structurally related search models where no obvious homologue can be found through sequence-based searching., The conventional approach to finding structurally similar search models for use in molecular replacement (MR) is to use the sequence of the target to search against those of a set of known structures. Sequence similarity often correlates with structure similarity. Given sufficient similarity, a known structure correctly positioned in the target cell by the MR process can provide an approximation to the unknown phases of the target. An alternative approach to identifying homologous structures suitable for MR is to exploit the measured data directly, comparing the lattice parameters or the experimentally derived structure-factor amplitudes with those of known structures. Here, SIMBAD, a new sequence-independent MR pipeline which implements these approaches, is presented. SIMBAD can identify cases of contaminant crystallization and other mishaps such as mistaken identity (swapped crystallization trays), as well as solving unsequenced targets and providing a brute-force approach where sequence-dependent search-model identification may be nontrivial, for example because of conformational diversity among identifiable homologues. The program implements a three-step pipeline to efficiently identify a suitable search model in a database of known structures. The first step performs a lattice-parameter search against the entire Protein Data Bank (PDB), rapidly determining whether or not a homologue exists in the same crystal form. The second step is designed to screen the target data for the presence of a crystallized contaminant, a not uncommon occurrence in macromolecular crystallography. Solving structures with MR in such cases can remain problematic for many years, since the search models, which are assumed to be similar to the structure of interest, are not necessarily related to the structures that have actually crystallized. To cater for this eventuality, SIMBAD rapidly screens the data against a database of known contaminant structures. Where the first two steps fail to yield a solution, a final step in SIMBAD can be invoked to perform a brute-force search of a nonredundant PDB database provided by the MoRDa MR software. Through early-access usage of SIMBAD, this approach has solved novel cases that have otherwise proved difficult to solve.

A new algorithm automatically determines the structures of large macromolecules of unknown fold from low-resolution single-wavelength anomalous X-ray data and a partial model that failed with other methods., Determining macromolecular structures from X-ray data with resolution worse than 3 Å remains a challenge. Even if a related starting model is available, its incompleteness or its bias together with a low observation-to-parameter ratio can render the process unsuccessful or very time-consuming. Yet, many biologically important macromolecules, especially large macromolecular assemblies, membrane proteins and receptors, tend to provide crystals that diffract to low resolution. A new algorithm to tackle this problem is presented that uses a multivariate function to simultaneously exploit information from both an initial partial model and low-resolution single-wavelength anomalous diffraction data. The new approach has been used for six challenging structure determinations, including the crystal structures of membrane proteins and macromolecular complexes that have evaded experts using other methods, and large structures from a 3.0 Å resolution F1-ATPase data set and a 4.5 Å resolution SecYEG–SecA complex data set. All of the models were automatically built by the method to R free values of between 28.9 and 39.9% and were free from the initial model bias.

International audience; Pencil-and-paper ciphers are plausible solutions that could provide lightweight protection to the communication of resource-constrained devices. A good example in this category is Schneier's Solitaire cipher. In this paper, we propose a probabilistic solution that is able to estimate Solitaire's keystream cycle length. We also present a variation of Solitaire's original design, and evaluate the resulting construction in terms of predictability. We conduct statistical randomness tests on both the original design and the modified version based on the NIST randomness test suite. The results show that our approach improves the randomness of original Solitaire's output sequences.

Date du colloque: 01/2009; International audience; This paper provides an overview of the application of Bayesian inference to accelerated life testing (ALT) models for the concrete case of estimation by Maximum of Aposteriori (MAP) method in the case of constant stress levels. It studies the Bayesian inference over the accelerated life model as presented in [1]. It suites, integrates and generalizes the particular cases presented in [2] and [3]. Towards the end, weighting of the prior information according to data is integrated. The paper also illustrates an experimental example.

In this paper, we introduce two powerful graph reductions for the maximum weighted stable set (mwss) in general graphs. We show that these reductions allow to reduce the mwss in claw-free graphs to the mwss in a class of quasi-line graphs, that we call bipolar-free. For this latter class, we provide a new algorithmic decomposition theorem running in polynomial time. We then exploit this decomposition result and our reduction tools again to transform the problem to either a single matching problem or a longest path computation in an acyclic auxiliary graph (in this latter part we use some results of Pulleyblank and Shepherd [10]). Putting all the pieces together, the main contribution of this paper is a new polynomial time algorithm for the mwss in claw-free graphs. A rough analysis of the complexity of this algorithm gives a time bound of O(n6), where n is the number of vertices in the graph, and which we hope can be improved by a finer analysis. Incidentally, we prove that the mwss problem can be solved efficiently for any class of graphs that admits a "suitable" decomposition into pieces where the mwss is easy.

Motivation: PacBio single molecule real-time sequencing is a third-generation sequencing technique producing long reads, with comparatively lower throughput and higher error rate. Errors include numerous indels and complicate downstream analysis like mapping or de novo assembly. A hybrid strategy that takes advantage of the high accuracy of second-generation short reads has been proposed for correcting long reads. Mapping of short reads on long reads provides sufficient coverage to eliminate up to 99% of errors, however, at the expense of prohibitive running times and considerable amounts of disk and memory space. Results : We present LoRDEC, a hybrid error correction method that builds a succinct de Bruijn graph representing the short reads, and seeks a corrective sequence for each erroneous region in the long reads by traversing chosen paths in the graph. In comparison, LoRDEC is at least six times faster and requires at least 93% less memory or disk space than available tools, while achieving comparable accuracy. Availability and implementaion : LoRDEC is written in C++, tested on Linux platforms and freely available at http://atgc.lirmm.fr/lordec . Contact: lordec@lirmm.fr . Supplementary information: Supplementary data are available at Bioinformatics online.

A statistical method to merge SAXS profiles using Gaussian processes is presented., Small-angle X-ray scattering (SAXS) is an experimental technique that allows structural information on biomolecules in solution to be gathered. High-quality SAXS profiles have typically been obtained by manual merging of scattering profiles from different concentrations and exposure times. This procedure is very subjective and results vary from user to user. Up to now, no robust automatic procedure has been published to perform this step, preventing the application of SAXS to high-throughput projects. Here, SAXS Merge, a fully automated statistical method for merging SAXS profiles using Gaussian processes, is presented. This method requires only the buffer-subtracted SAXS profiles in a specific order. At the heart of its formulation is non-linear interpolation using Gaussian processes, which provides a statement of the problem that accounts for correlation in the data.

Motivation: Thermodynamics-based dynamic programming RNA secondary structure algorithms have been of immense importance in molecular biology, where applications range from the detection of novel selenoproteins using expressed sequence tag (EST) data, to the determination of microRNA genes and their targets. Dynamic programming algorithms have been developed to compute the minimum free energy secondary structure and partition function of a given RNA sequence, the minimum free-energy and partition function for the hybridization of two RNA molecules, etc. However, the applicability of dynamic programming methods depends on disallowing certain types of interactions (pseudoknots, zig-zags, etc.), as their inclusion renders structure prediction an nondeterministic polynomial time (NP)-complete problem. Nevertheless, such interactions have been observed in X-ray structures. Results: A non-Boltzmannian Monte Carlo algorithm was designed by Wang and Landau to estimate the density of states for complex systems, such as the Ising model, that exhibit a phase transition. In this article, we apply the Wang-Landau (WL) method to compute the density of states for secondary structures of a given RNA sequence, and for hybridizations of two RNA sequences. Our method is shown to be much faster than existent software, such as RNAsubopt. From density of states, we compute the partition function over all secondary structures and over all pseudoknot-free hybridizations. The advantage of the WL method is that by adding a function to evaluate the free energy of arbitary pseudoknotted structures and of arbitrary hybridizations, we can estimate thermodynamic parameters for situations known to be NP-complete. This extension to pseudoknots will be made in the sequel to this article; in contrast, the current article describes the WL algorithm applied to pseudoknot-free secondary structures and hybridizations. Availability: The WL RNA hybridization web server is under construction at http://bioinformatics.bc.edu/clotelab/. Contact: clote@bc.edu

Motivation: A prerequisite for any protein study by NMR is the assignment of the resonances from the 15N−1H HSQC spectrum to their corresponding atoms of the protein backbone. Usually, this assignment is obtained by analyzing triple resonance NMR experiments. An alternative assignment strategy exploits the information given by an already available 3D structure of the same or a homologous protein. Up to now, the algorithms that have been developed around the structure-based assignment strategy have the important drawbacks that they cannot guarantee a high assignment accuracy near to 100%. Results: We propose here a new program, called NOEnet, implementing an efficient complete search algorithm that ensures the correctness of the assignment results. NOEnet exploits the network character of unambiguous NOE constraints to realize an exhaustive search of all matching possibilities of the NOE network onto the structural one. NOEnet has been successfully tested on EIN, a large protein of 28 kDa, using only NOE data. The complete search of NOEnet finds all possible assignments compatible with experimental data that can be defined as an assignment ensemble. We show that multiple assignment possibilities of large NOE networks are restricted to a small spatial assignment range (SAR), so that assignment ensembles, obtained from accessible experimental data, are precise enough to be used for functional proteins studies, like protein–ligand interaction or protein dynamics studies. We believe that NOEnet can become a major tool for the structure-based backbone resonance assignment strategy in NMR. Availability: The NOEnet program will be available under: http://www.icsn.cnrs-gif.fr/download/nmr Contact: carine@icsn.cnrs-gif.fr; eric.guittet@icsn.cnrs-gif.fr Supplementary Information: Supplementary data are available at Bioinformatics online.

International audience; An experimentally recorded time series formed by the exact times of occurrence of the neuronal spikes (spike train) is likely to be affected by observational noise that provokes events mistakenly confused with neuronal discharges, as well as missed detection of genuine neuronal discharges. The points of the spike train may also suffer a slight jitter in time due to stochastic processes in synaptic transmission and to delays in the detecting devices. This study presents a procedure aimed at filtering the embedded noise (denoising the spike trains) the spike trains based on the hypothesis that recurrent temporal patterns of spikes are likely to represent the robust expression of a dynamic process associated with the information carried by the spike train. The rationale of this approach is tested on simulated spike trains generated by several nonlinear deterministic dynamical systems with embedded observational noise. The application of the pattern grouping algorithm (PGA) to the noisy time series allows us to extract a set of points that form the reconstructed time series. Three new indices are defined for assessment of the performance of the denoising procedure. The results show that this procedure may indeed retrieve the most relevant temporal features of the original dynamics. Moreover, we observe that additional spurious events affect the performance to a larger extent than the missing of original points. Thus, a strict criterion for the detection of spikes under experimental conditions, thus reducing the number of spurious spikes, may raise the possibility to apply PGA to detect endogenous deterministic dynamics in the spike train otherwise masked by the observational noise.

Motivation: Predicting how proteins interact at the molecular level is a computationally intensive task. Many protein docking algorithms begin by using fast Fourier transform (FFT) correlation techniques to find putative rigid body docking orientations. Most such approaches use 3D Cartesian grids and are therefore limited to computing three dimensional (3D) translational correlations. However, translational FFTs can speed up the calculation in only three of the six rigid body degrees of freedom, and they cannot easily incorporate prior knowledge about a complex to focus and hence further accelerate the calculation. Furthemore, several groups have developed multi-term interaction potentials and others use multi-copy approaches to simulate protein flexibility, which both add to the computational cost of FFT-based docking algorithms. Hence there is a need to develop more powerful and more versatile FFT docking techniques. Results: This article presents a closed-form 6D spherical polar Fourier correlation expression from which arbitrary multi-dimensional multi-property multi-resolution FFT correlations may be generated. The approach is demonstrated by calculating 1D, 3D and 5D rotational correlations of 3D shape and electrostatic expansions up to polynomial order L=30 on a 2 GB personal computer. As expected, 3D correlations are found to be considerably faster than 1D correlations but, surprisingly, 5D correlations are often slower than 3D correlations. Nonetheless, we show that 5D correlations will be advantageous when calculating multi-term knowledge-based interaction potentials. When docking the 84 complexes of the Protein Docking Benchmark, blind 3D shape plus electrostatic correlations take around 30 minutes on a contemporary personal computer and find acceptable solutions within the top 20 in 16 cases. Applying a simple angular constraint to focus the calculation around the receptor binding site produces acceptable solutions within the top 20 in 28 cases. Further constraining the search to the ligand binding site gives up to 48 solutions within the top 20, with calculation times of just a few minutes per complex. Hence the approach described provides a practical and fast tool for rigid body protein-protein docking, especially when prior knowledge about one or both binding sites is available. Availability: http://www.csd.abdn.ac.uk/hex/ Contact: d.w.ritchie@abdn.ac.uk

International audience; This paper deals with the frequency design of loss-less passive electronic filters under magnitude constraints. With the huge increase in design complexity for mobile applications, new systematic and efficient methods are required. This paper focuses on the direct synthesis approach, an historical design approach that has not been recently updated. It consists in directly synthesizing the LC values of a pre-specified circuit until the spectral mask is satisfied. While beneficial in practice, this approach typically leads to an important computational time and requires an initial guess to reduce it. Based on recent developments of the System and Control community, that led to efficient methods for system design, the direct synthesis approach is revisited. To achieve this, the port-Hamiltonian Differential Algebraic Equation (pHDAE) representation, that particularly fits the design problem, is introduced. A synthesis method is then developed, leading to solve an optimization problem of moderate complexity. For particular cases, this complexity happens to be remarkably low. Based on this observation, a second method reveals how to obtain such complexity for the more general case, using an original combination between the pHDAE and the LFT representations. Finally, a numerical example shows the validity and illustrates the benefits of this work.

International audience; This paper presents a new Bit Flipping (BF) decoder, called the Probabilistic Parallel Bit Flipping (PPBF) for Low-Density Parity-Check (LDPC) codes on the Binary Symmetric Channel. In the PPBF, the flipping operation is performed in a probabilistic manner which is shown to improve significantly the error correction performance. The advantage of the PPBF also comes from the fact that no global computation is required during the decoding process and that all the computations can be executed in the local computing units and in-parallel. The PPBF provides a considerable improvement of the operating frequency and complexity, compared to other known BF decoders, while obtaining a significant gain in error correction. An improved version of the PPBF, called non-syndrome PPBF (NS-PPBF) is also introduced, in which the global syndrome check is moved out of the critical path and a new terminating mechanism is proposed. In order to show the superiority of the new decoders in terms of hardware efficiency and decoding throughput, the corresponding hardware architectures are presented in the second part of the paper. The ASIC synthesis results confirm that the operating frequency of the proposed decoders is significantly improved, compared to that of the BF decoders in the literature while requiring lower complexity to be efficiently implemented.

International audience; In this paper, we propose a reduced complexity parallel least mean square structure (RC-pLMS) for adaptive beamforming and its pipelined hardware implementation. RC-pLMS is formed by two least mean square (LMS) stages operating in parallel (pLMS), where the overall error signal is derived as a combination of individual stage errors. The pLMS is further simplified to remove the second independent set of weights resulting in a reduced complexity pLMS (RC-pLMS) design. In order to obtain a pipelined hardware architecture of our proposed RC-pLMS algorithm, we applied the delay and sum relaxation technique (DRC-pLMS). Convergence, stability and quantization effect analysis are performed to determine the upper bound of the step size and assess the behavior of the system. Computer simulations demonstrate the outstanding performance of the proposed RC-pLMS in providing accelerated convergence and reduced error floor while preserving a LMS identical O(N) complexity, for an antenna array of N elements. Synthesis and implementation results show that the proposed design achieves a significant increase in the maximum operating frequency over other variants with minimal resource usage. Additionally, the resulting beam radiation pattern show that the finite precision DRC-pLMS implementation presents similar behavior of the infinite precision theoretical results.

This paper deals with decision procedures specified by using a superposition calculus which is an inference system at the core of all equational theorem provers. This calculus is refutation complete: it provides a semi-decision procedure that halts on unsatisfiable inputs but may diverge on satisfiable ones. Fortunately, it may also terminate for some theories of interest in verification, and thus it becomes a decision procedure. To reason on the superposition calculus, a schematic superposition calculus has been developed to build the schematic form of the saturations allowing to automatically prove decidability of single theories and of their combinations.This paper presents a rule-based logical framework and a tool implementing a complete many-sorted schematic superposition calculus for arbitrary theories. By providing results for unit theories, arbitrary theories, and also for theories with counting operators, we show that this tool is very useful to derive decidability and combinability of theories of practical interest in verification. We present a many-sorted schematic superposition calculus for non-unit theories.The calculus is presented as a rule-based system.The implementation automatically checks termination for some theories of interest.Combinability of signature-disjoint theories can also be checked.

A plethora of Contrast Enhancement (CE) methods has been proposed in the literature. Each of these has its own strengths and limitations. Further, the quality of the resulting enhanced images depends upon the original image and its content. Hence, a given CE method can provide good quality for a certain image but a poorer quality for another. In this paper, we propose a novel workflow to provide an automatic ranking of enhanced images which may have been obtained using different techniques. The proposed technique is based on a Convolutional Neural Network (CNN) using saliency information. The idea is to start by comparing two enhanced versions of a given image in order to select the best one automatically based on perceived quality. Here, a saliency map is used to select relevant patches which are highly correlated with the human visual system sensitivity. The well-known Structural Similarity Image Metric (SSIM) map is also employed to compare the similarity between both enhanced images. Using such information, a CNN model is trained to predict the rank in terms of the image quality as perceived by humans. The algorithm is tested over three CE benchmarking databases with the experimental results validating the superiority of the proposed system as compared to state-of-the-art CE evaluation techniques.

International audience; In addition to standard delivery costs, shippers are concerned with delivery lead times. Shorter delivery lead times provide better service to customers. This paper investigates the bid generation problem of a carrier in collaborative transportation realized via a combinatorial auction. In this paper, we propose a multi-period bid generation problem with two types of pickup and delivery requests, namely reserved and selective requests. This problem is an extension of pickup and delivery problem with time windows. This problem arises when a shipper applies an auction for the procurement of transportation services from carriers. In each period, the carrier may have reserved requests that must be served by itself. This carrier wants to determine within a time horizon of multi periods which requests to bid and serve among a set of selective requests open for bid and its multi-period routing plan to maximize its profit and minimize delivery lead times. This problem is NP-hard. We propose an Improved Tabu Search (ITS) algorithm to solve it. The algorithm is evaluated on instances with 20 to 100 requests. The computational results show that the proposed algorithm significantly outperforms CPLEX with much shorter computation times.

This paper introduces a novel surface reconstruction method based on unorganized point clouds, which focuses on offering complete and closed mesh models of partially sampled object surfaces. To accomplish this task, our approach builds upon a known a priori model that coarsely describes the scanned object to guide the modeling of the shape based on heavily occluded point clouds. In the region of space visible to the scanner, we retrieve the surface by following the resolution of a Poisson problem: the surface is modeled as the zero level-set of an implicit function whose gradient is the closest to the vector field induced by the 3D sample normals. In the occluded region of space, we consider the a priori model as a sufficiently accurate descriptor of the shape. Both models, which are expressed in the same basis of compactly supported radial functions to ensure computation and memory efficiency, are then blended to obtain a closed model of the scanned object. Our method is finally tested on traditional testing datasets to assess its accuracy and on simulated terrestrial LiDAR scanning (TLS) point clouds of trees to assess its ability to handle complex shapes with occlusions.

Low-density parity-check (LDPC) codes are adopted in many applications due to their Shannon-limit approaching error-correcting performance. Nevertheless, belief-propagation (BP) based decoding of these codes suffers from the error-floor problem, i.e., an abrupt change in the slope of the error-rate curve that occurs at very low error rates. Recently, a new type of decoders termed finite alphabet iterative decoders (FAIDs) were introduced. The FAIDs use simple Boolean maps for variable node processing, and can surpass the BP-based decoders in the error floor region with very short word length. We restrict the scope of this paper to regular dv=3 LDPC codes on the BSC channel. This paper develops a low-complexity implementation architecture for the FAIDs by making use of their properties. Particularly, an innovative bit-serial check node unit is designed for the FAIDs, and a small-area variable node unit is proposed by exploiting the symmetry in the Boolean maps. Moreover, an optimized data scheduling scheme is proposed to increase the hardware utilization efficiency. From synthesis results, the proposed FAID implementation needs only 52% area to reach the same throughput as one of the most efficient standard Min-Sum decoders for an example (7807, 7177) LDPC code, while achieving better error-correcting performance in the error-floor region. Compared to an offset Min-Sum decoder with longer word length, the proposed design can achieve higher throughput with 45% area, and still leads to possible performance improvement in the error-floor region.

This paper presents an enhancement of the well-known Louvain algorithm for community detection with modularity maximization which was introduced in [16]. The Louvain algorithm is a partial multi-level method which applies the vertex mover heuristic to a series of coarsened graphs. The Louvain+ algorithm proposed in this paper generalizes the Louvain algorithm by including a uncoarsening phase, leading to a full multi-level method. Experiments on a set of popular complex networks show the benefits induced by the proposed Louvain+ algorithm.

In this paper, we propose an image tampering localization algorithm using semi-fragile watermarking and Error-Locating codes in the DWT domain. By introducing different families of codes, we show the benefit in terms of image tampering localization and complexity of using control code error localization as an authentication function. Indeed, we first experimentally show that error localization block codes is as precise as using classical error correcting codes (Reed-Solomon and BCH codes) to locate image tampering. However, their corresponding decoding algorithms complexity is at least quadratic which make them impractical for some real time applications. To solve this problem, we introduce error-control codes called Error-Locating codes where error localization is reduced to a single syndrome computation performed with low number of binary operations (detailed later in the paper). We provide comparisons of image quality and tampering localization performances using error-detection, error-localization and error-correction approaches with different error control codes.

This work has been supported by the aVEnir project of the PIA operated by ADEME; International audience; This is a fact that the battery life is inversely related to the number of discharge cycles. However, these days, the bidirectional smart charging scenario of plug-in electric vehicles (PEVs) has become a hot trend, using them as a storage source at peak load or price. Therefore, this paper aims to present a simple and novel technique in predictive-based linear programming for limiting the number of discharge cycles of PEV. In this regard, a specified number of cycles is defined by the user such that the predictive algorithm tries to use these cycles in the most optimal way. In this paper, first, the effect of the discharging cycle on the battery life available in the literature is presented. Then, the photovoltaic-assisted charging station configuration and desired optimization algorithm are introduced. Following, the main novelty of this work, i.e. a linear technique for limiting the number of discharging cycles will be described. Finally, the simulation results are provided to validate the performance of the proposed method.

International audience; The problem of blind joint FIR-MIMO channel and data estimation is addressed in this paper. Based on a regularized DML (Deterministic Maximum Likelihood) formulation of the problem, a bilinear approach is used in order to estimate jointly the channel impulse responses and the input data. This regularization is introduced as a penalty function added to the classical DML criterion representing the a priori information about the problem in order to enhance the accuracy of the estimation. Two types of priors information are considered for the transmitted data: the finite alphabet simplicity or the sparsity. The sparsity prior was also considered for channel impulse responses. The key advantage of the proposed criteria is their convexity when optimized alternatively over the channel and the input data. The proposed approach allows to improve further the estimation accuracy of such a blind estimation problem but suffers from a relatively high computational cost. Hence, a reduced complexity implementation of the latter has been proposed at the end of the paper, in an adaptive scheme for high dimensional or streaming data situations.

Evil Waveforms (EWF) are non-nominal distortions that can be observed on satellite signals and cause additional bias on the estimated user position. A Threat Model (TM) has been proposed by ICAO for GPS L1 C/A to describe the possible distortions that can be observed on the GPS signals. This Threat model is also adopted for Galileo E1-C and E5a-Q signals. To evaluate the induced tracking bias by the EWFs of the ICAO TM, the receiver behavior after their occurrence needs to be assessed. In addition, some EWF cases induces multiple peaks on the correlation function. The main question of this study is: how the receiver deals with the multiple peaks situation and what impact it can have on the induced EWF bias. The present paper evaluates the effect of two Receiver Behavior Models (RBM) based on two possible reactions of the DLL after EWF occurrence: loss and no loss of the tracking. Those RBMs are modelled using different parameters such as the DLL pull in area and the C/N0 loss. The study shows the occurrence of multiple zero crossing situations and the EWF induced bias for both RBMs. The sensitivity of these results to the EWF Threat Space and tested User Space is then analyzed for both RBMs. This paper presents the results obtained when testing TM-A, B and C on Galileo E5a signal. Then, it discusses the observed impacts of the two tested RBMs and the situation of multiple zero crossing on the EWF induced tracking bias.

Decomposing an image through Fourier, DCT or wavelet transforms is still a common approach in digital image processing, in number of applications such as denoising. In this context, data-driven dictionaries and in particular exploiting the redundancy withing patches extracted from one or several images allowed important improvements. This paper proposes an original idea of constructing such an image-dependent basis inspired by the principles of quantum many-body physics. The similarity between two image patches is introduced in the formalism through a term akin to interaction terms in quantum mechanics. The main contribution of the paper is thus to introduce this original way of exploiting quantum many-body ideas in image processing, which opens interesting perspectives in image denoising. The potential of the proposed adaptive decomposition is illustrated through image denoising in presence of additive white Gaussian noise, but the method can be used for other types of noise such as image-dependent noise as well. Finally, the results show that our method achieves comparable or slightly better results than existing approaches., Comment: 5 pages, 4 figures

International audience; This tutorial review paper consolidates the existing applications of the power watershed (PW) optimization framework in the context of image processing. In literature, it is known that PW framework when applied to some well-known graph-based image segmentation and filtering algorithms such as random walker, isoperimetric partitioning, ratio-cut clustering, multi-cut and shortest path filters yield faster yet consistent solutions. In this paper, the intuition behind the working of PW framework i.e. exploitation of contrast invariance on image data is explained. The intuitions are illustrated with toy images and experiments on simulated astronomical images. This article is primarily aimed at researchers working on image segmentation and filtering problems in application areas such as astronomy where images typically havea huge number of pixels. Classic graph-based cost minimization methods provide good results on images with small number of pixels but do not scale well for images with large number of pixels. The ideas from the article can be adapted to a large class of graph-based cost minimization methods to obtain scalable segmentation and filtering algorithms.

International audience; Adaptive feedforward broad-band noise compensation is currently used when a correlated measurement with the disturbance (an image of the disturbance) is available. Most of the active feedforward noise control systems feature an internal "positive" acoustical feedback between the compensation system and the disturbance measurement which has to be taken into account. Adap-tive algorithms for active feedforward noise attenuation have been developed since 1985 from a local optimization point of view. This paper presents two classes of adaptive configurations for active feedforward noise compensation developed from a stability point of view. The first class uses a standard IIR(FIR) compensator structure while the second class uses the Youla-Kučera parametrization of the feedforward noise compensator. This allows to separate the problem of stabilizing the internal positive feedback loop from the minimization of the residual noise. These adaptive schemes have been developed in the context of active vibration control but, as it will be shown, they can be used also in active noise control. The paper presents in a unified manner the available algorithms and compensator structures for adaptive feedforward noise attenuation and provides a comparative experimental evaluation on a relevant experimental test-bench (a duct silencer). Index Terms-active noise control, adaptive feedfor-ward compensation, Youla-Kučera parametrization, positive feedback coupling.

International audience; This paper focuses on the algorithms and implementation details of a published segmentation method defined to identify the defects of tree log surface. Such a method overcomes the difficulty of the high variability of the tree log surface and allows to segment the defects from the tree bark. All the algorithms used in this method are described in link to their source code which guarantees a full reproducible method associated to an online demonstration.

International audience; This paper presents a different vision of the Non-Binary LDPC decoding algorithm. So far, state-of-the-art decoders are mainly focused on the reduction of the check node processing complexity, with a potential side effect on the size of the messages that are exchanged in the iterative decoder. However, it is possible to take a different approach and consider the reduction of the message size as the main objective. The paper presents "the Best, the Requested and the Default" algorithm that shrinks dramatically the communication load between the variable nodes and check nodes.

Tunnel face stability constitutes a significant challenge for shield tunneling in urban areas. The use of a slurry pressure balanced shield machine in mixed ground conditions containing mudstone is generally disturbed by clogging, which results in noises and large fluctuations in the tunnel face pressure. These fluctuations add difficulties to the prediction of the slurry pressure. This paper proposes a denoising method to overcome this difficulty. This method is combined with variational mode decomposition and detrended fluctuation analysis. The method is coupled with cross-correlation analysis (CCA) and a long short-term memory (LSTM) network to predict the tunnel face pressure using both tunneling parameters and geological data as input. The paper proposes a predictive strategy that separates the trend component and fluctuation component from the denoised tunneling data via CCA. Two LSTM-based predictors are presented and combined for the development of a new modeling strategy. The performances of the proposed strategy are illustrated through an application to the Nanning metro. The LSTM model with the proposed strategy gave excellent results in both mudstone and round gravel grounds with an overall R2 value of 0.9974. The paper also presents a comparison of the proposed model with some traditional models as well as a discussion on the importance of input features in different ground conditions.

This paper proposes a lossless point cloud (PC) geometry compression method that uses neural networks to estimate the probability distribution of voxel occupancy. First, to take into account the PC sparsity, our method adaptively partitions a point cloud into multiple voxel block sizes. This partitioning is signalled via an octree. Second, we employ a deep auto-regressive generative model to estimate the occupancy probability of each voxel given the previously encoded ones. We then employ the estimated probabilities to code efficiently a block using a context-based arithmetic coder. Our context has variable size and can expand beyond the current block to learn more accurate probabilities. We also consider using data augmentation techniques to increase the generalization capability of the learned probability models, in particular in the presence of noise and lower-density point clouds. Experimental evaluation, performed on a variety of point clouds from four different datasets and with diverse characteristics, demonstrates that our method reduces significantly (by up to 30%) the rate for lossless coding compared to the state-of-the-art MPEG codec., This paper has been submitted to the IEEE Transactions on Circuits and Systems for Video Technology (TCSVT). arXiv admin note: text overlap with arXiv:2011.14700

The joint estimation of the location vector and the shape matrix of a set of independent and identically Complex Elliptically Symmetric (CES) distributed observations is investigated from both the theoretical and computational viewpoints. This joint estimation problem is framed in the original context of semiparametric models allowing us to handle the (generally unknown) density generator as an \textit{infinite-dimensional} nuisance parameter. In the first part of the paper, a computationally efficient and memory saving implementation of the robust and semiparmaetric efficient $R$-estimator for shape matrices is derived. Building upon this result, in the second part, a joint estimator, relying on the Tyler's $M$-estimator of location and on the $R$-estimator of shape matrix, is proposed and its Mean Squared Error (MSE) performance compared with the Semiparametric Cram\'{e}r-Rao Bound (CSCRB)., Comment: This paper has been submitted to the Special Issue (related to MLSP) of the Journal of Signal Processing Systems

Given the versatility of timed automata a huge body of work has evolved that considers extensions of timed automata. One extension that has received a lot of interest is timed automata with a, possibly unbounded, stack, also called the pushdown timed automata (PDTA) model. While different algorithms have been given for reachability in different variants of this model, most of these results are purely theoretical and do not give rise to efficient implementations. One main reason for this is that none of these algorithms (and the implementations that exist) use the so-called zone-based abstraction, but rely either on the region-abstraction or other approaches, which are significantly harder to implement. In this paper, we show that a naive extension of the zone based reachability algorithm for the control state reachability problem of timed automata is not sound in the presence of a stack. To understand this better we give an inductive rule based view of the zone reachability algorithm for timed automata. This alternate view allows us to analyze and adapt the rules to also work for pushdown timed automata. We obtain the first zone-based algorithm for PDTA which is terminating, sound and complete. We implement our algorithm in the tool TChecker and perform experiments to show its efficacy, thus leading the way for more practical approaches to the verification of pushdown timed systems., Comment: Long version of conference paper accepted at CAV'2021

International audience; In this paper, we tackle the problem of off-grid radar target detection based on the Normalized Matched Filter. State-ofthe-art solutions to this problem include the use of the Generalized Likelihood Ratio test (GLRT), whose implementation can be costly, subspace detectors, or oversampling. In this paper, we introduce a new solution for improving detection of an off-grid target. It is inspired by monopulse angle estimation methods. Using simulations, we show that our solution is comparable to the GLRT under Gaussian noise hypothesis with a known covariance matrix in terms of detection probability. As such, its detection performance appears to be often better than those of detectors in the same computational cost range, and significantly better in some cases.

International audience; In this paper, we propose a new algorithm to estimate all the parameters of a Self Exited Threshold AutoRegressive (SETAR) model from an observed time series. The aim of this algorithm is to relax all the hypotheses concerning the SETAR model for instance, the knowledge (or assumption) of the number of regimes, the switching variables, as well as of the switching function. For this, we reverse the usual framework of SETAR model identification of the previous papers, by first identifying the AR models using array clustering (instead of the switching variables and function) and second the switching conditions (instead of the AR models). The proposed algorithm is a pipeline of well-known algorithms in image/data processing allowing us to deal with the statistical non-stationarity of the observed time series. We pay a special attention on the results of each step over the possible discrepancies over the following step. Since we do not assume any SETAR model property, asymptotical properties of the identification results are difficult to derive. Thus, we validate our approach on several experiment sets. In order to assess the performance of our algorithm, we introduce global metrics and ancillary metrics to validate each step of the proposed algorithm.

International audience; One of the cornerstones of the cloud provider business is to reduce hardware resources cost by maximizing their utilization. This is done through smartly sharing processor, memory, network and storage, while fully satisfying SLOs negotiated with customers. For the storage part, while SSDs are increasingly deployed in data centers mainly for their performance and energy efficiency, their internal mechanisms may cause a dramatic SLO violation. In effect, we measured that I/O interference may induce a 10x performance drop. We are building a framework based on autonomic computing which aims to achieve intelligent container placement on storage systems by preventing bad I/O interference scenarios. One prerequisite to such a framework is to design SSD performance models that take into account interactions between running processes/containers, the operating system and the SSD. These interactions are complex. In this paper, we investigate the use of machine learning for building such models in a container based Cloud environment. We have investigated five popular machine learning algorithms along with six different I/O intensive applications and benchmarks. We analyzed the prediction accuracy, the learning curve, the feature importance and the training time of the tested algorithms on four different SSD models. Beyond describing modeling component of our framework, this paper aims to provide insights for cloud providers to implement SLO compliant container placement algorithms on SSDs. Our machine learning-based framework succeeded in modeling I/O interference with a median Normalized Root-Mean-Square Error (NRMSE) of 2.5%.

Visual tracking has received much attention in recent years, especially pedestrian tracking. People tracking represents an important computer vision problem with numerous real-world applications. While significant progress has been achieved for human tracking and detection, trackers are still prone to failures and inaccuracies to master all difficult situations that may arise during the process: changes in appearance, illumination, occlusions, camera movement or cluttered background. To overcome these limitations, tracking algorithms offered by the OpenCV software library are evaluated through this paper. These trackers are fast and easy to use. However, pedestrians are particularly difficult to track with a moving camera. This paper brings a benchmark of human tracking algorithms implementations using moving camera. Here, we propose a qualitative and quantitative assessment followed by a comparison with a particle filter algorithm based on histograms of both color and texture features. Finally, in order to compare to new developed tracking algorithms in the framework of a pedestrian tracking accuracy in an unknown environment, experiments with a new available dataset validate either the reliability of OpenCV trackers or an easy-to-use particle filter.

International audience; This paper deals with supervised classification and feature selection with application in the context of high dimensional features. A classical approach leads to an optimization problem minimizing the within sum of squares in the clusters (2 norm) with an 1 penalty in order to promote sparsity. It has been known for decades that 1 norm is more robust than 2 norm to outliers. In this paper, we deal with this issue using a new proximal splitting method for the minimization of a criterion using 1 norm both for the constraint and the loss function. Since the 1 criterion is only convex and not gradient Lipschitz, we advocate the use of a Douglas-Rachford minimization solution. We take advantage of the particular form of the cost and, using a change of variable, we provide a new efficient tailored primal Douglas-Rachford splitting algorithm which is very effective on high dimensional dataset. We also provide an efficient classifier in the projected space based on medoid modeling. Experiments on two biological datasets and a computer vision dataset show that our method significantly improves the results compared to those obtained using a quadratic loss function.; Ce document traite de la classification supervisée et de la sélection des descripteurs avec application dans le contexte des descripteurs de haute dimension. Une approche classique conduit à un problème d'optimisation minimisant la norme quadratique (norme 2) avec une pénalite de norme 1 afin de promouvoir la parcimonie. Il est bien connu que la norme 1 est plus robuste que la norme 2 aux valeurs aberrantes. Dans cet article, nous abordons cette question avec une nouvelle méthode proximale pour la minimisation d'un critère utilisant la norme 1 à la fois pour la contrainte et la fonction de perte. Comme le critère 1 n'est que convexe et non gradient de Lipschitz, nous proposons l'utilisation d'une solution de minimisation de type Douglas-Rachford. Nous tirons parti de la forme du critère et, en utilisant un changement de variable, nous fournissons un nouvel algorithme de type Douglas-Rachford dans le primal qui est très efficace dans le contexte des descripteurs de haute dimension. Nous fournissons également un classifieur efficace dans l'espace projeté basé sur la modélisation de medoïds. Des expériences sur des données biologiques et de vision par ordinateur montrent que notre méthode améliore les résultats par rapport à ceux obtenus avec une fonction de perte quadratique.

A crucial step when identifying the modal signature of systems using growing order parametric methods consists in discriminating spurious modes from physical modes. In this paper, a three-stages clustering strategy is presented in a fuzzy framework for automating this selection process in the context of Input/Output and Output-Only identification. The novelty and strong point of the approach lies in the first stage where, after computation of single mode validation indicators, a modified fuzzy c-means clustering procedure is developed for performing a first partition. It is shown how the membership function obtained for the cluster of physical modes can be interpreted as a new synthetic modal indicator and helps with pole-splitting detection, outlier rejection and generally improves the final modal parameters estimation. The developed methodology does not involve any user-specified threshold and can be used for discriminating modes produced by any methodology consisting in fitting a growing order model to experimental data of any type. In this paper, accelerations measured during the SMART2013 shaking-table test campaign are processed using data-driven state-space identification algorithms. The automated selection process is used for tracking the modal signature of a trapezoidal shaped reinforced-concrete specimen using in turn stochastic and combined deterministic-stochastic algorithms, defining for the latter the movement of the shaking table as input. Variations in the modal signature are then correlated to the damage actually observed on the specimen and a comparison between Output-Only and Input/Output results is made in order to estimate the interaction between the specimen and the whole shaking table device.

International audience; Privacy has traditionally been a major motivation of distributed problem solving. One popular approach to enable privacy in distributed environments is to implement complex cryptographic protocols. In this paper, we propose a different, orthogonal approach, which is to control the quality and the quantity of publicized data. We consider the Open Constraint Programming model and focus on algorithms that solve Distributed Constraint Optimization Problems (DCOPs) using a local search approach. Two such popular algorithms exist to find good solutions to DCOP: DSA and GDBA. In this paper, we propose DSAB, a new algorithm that merges ideas from both algorithms to allow extensive handling of constraint privacy. We also study how algorithms behave when solving Utilitarian DCOPs, where utilitarian agents want to reach an agreement while reducing the privacy loss. We experimentally study how the utilitarian approach impacts the quality of the solution and of publicized data.

International audience; Dynamic system fault diagnosis is often faced with a large number of possible faults. The purpose of this paper is to propose an efficient method for such situations. To avoid intractable combinatorial problems, sparse estimation techniques appear to be a powerful tool for isolating faults, under the assumption that only a small number of possible faults can be simultaneously active. However, sparse estimation is often studied in the framework of linear algebraic equations, whereas model-based fault diagnosis is usually investigated for dynamic systems modeled with state equations involving internal states. The main contribution of this paper is a link between these two formalisms through efficient and reliable algorithms, mainly relying on advanced analyses of residuals generated with the Kalman and Kitanidis filters. Based on these results, it becomes straightforward to solve fault diagnosis problems by applying well known sparse estimation techniques, in the framework of general time varying state-space systems involving unknown inputs.

International audience; The community detection in complex networks has become a major field of research. Disjoint community detection deals often with getting a partition of nodes where every node belongs to only one community. However, in social networks, individuals may belong to more than one community such as in co-purchasing field, a co-authorship of scientist papers or anthropological networks. We propose in this paper a method to find overlapping communities from pre-computed disjoint communities obtained by using the core detection label propagation. The algorithm selects candidates nodes for overlapping and uses belonging functions to decide the assignment or not of a candidate node to each of its neighbours communities. we propose and experiment in this paper several belonging functions, all based on the topology of the communities. These belonging functions are either based on global measures which are the density and the clustering coefficient or on average node measures which are the betweenness and the closeness centralities. We expose then a new similarity measure between two covers regarding the overlapping nodes. The goal is to assess the similarity between two covers that overlap several communities. We finally propose a comparative analysis with the literature algorithms.

This paper deals with the problem of building fast and reliable 3D reconstruction methods for blood flows for which partial information is given by Doppler ultrasound measurements. This task is of interest in medicine since it could enrich the available information used in the diagnosis of certain diseases which is currently based essentially on the measurements coming from ultrasound devices. The fast reconstruction of the full flow can be performed with state estimation methods that have been introduced in recent years and that involve reduced order models. One simple and efficient strategy is the so-called Parametrized Background Data-Weak approach (PBDW, see Maday et al. (2015)). It is a linear mapping that consists in a least squares fit between the measurement data and a linear reduced model to which a certain correction term is added. However, in the original approach, the reduced model is built a priori and independently of the reconstruction task (typically with a proper orthogonal decomposition or a greedy algorithm). In this paper, we investigate the construction of other reduced spaces which are built to be better adapted to the reconstruction task and which result in mappings that are sometimes nonlinear. We compare the performance of the different algorithms on numerical experiments involving synthetic Doppler measurements. The results illustrate the superiority of the proposed alternatives to the classical linear PBDW approach.

Graph structure is a powerful framework for the characterization of interaction between entities. In the context of graph signal processing, interpolation methods are based on the smoothness assumption that assumes that neighboring nodes present similar values. However, in several contexts, the strong relationship between two connected nodes may express different behaviour. In this paper, we propose a graph signal interpolation algorithm that uses a graph localization penalization on the reconstruction weights. These weights are learned from the data, thus allowing the use of signal anti-correlation on connected nodes in order to perform a more robust interpolation. The results displayed in the paper show that our approach is relevant when dealing with real data, for both smooth and non-smooth signals.

Domain Adaptation aims at benefiting from a labeled dataset drawn from a source distribution to learn a model from examples generated from a different but related target distribution. Creating a domain-invariant representation between the two source and target domains is the most widely technique used. A simple and robust way to perform this task consists in (i) representing the two domains by subspaces described by their respective eigenvectors and (ii) seeking a mapping function which aligns them. In this paper, we propose to use Optimal Transport (OT) and its associated Wassertein distance to perform this alignment. While the idea of using OT in domain adaptation is not new, the original contribution of this paper is two-fold: (i) we derive a generalization bound on the target error involving several Wassertein distances. This prompts us to optimize the ground metric of OT to reduce the target risk; (ii) from this theoretical analysis, we design an algorithm (MLOT) which optimizes a Mahalanobis distance leading to a transportation plan that adapts better. Extensive experiments demonstrate the effectiveness of this original approach.