Search

International audience; In this note, we point out two major errors in the paper "Minimizing total tardiness on parallel machines with preemptions" by Kravchenko and Werner (2012). More precisely, they claimed to have proved that both problems P|pmtn|∑T j and P|r j ,p j =p,pmtn|∑T j are NP -Hard. We give a counter-example to their proofs, letting the complexity of these two problems open.

Smoothly bent paper-like surfaces are developable. They are however difficult to minimally parameterize since the number of meaningful parameters is intrinsically dependent on the actual deformation. Previous generative models are either incomplete, i.e. limited to subsets of developable surfaces, or depend on huge parameter sets. We propose a generative model governed by a quasi-minimal set of intuitive parameters, namely rules and angles. More precisely, a flat mesh is bent along guiding rules, while a number of extra rules controls the level of smoothness. The generated surface is guaranteed to be developable. A fully automatic multi-camera three dimensional reconstruction algorithm, including model-based bundle-adjustment, demonstrates our model on real images.

In this paper, we address the problem of robustly recovering several instances of a curve model from a single noisy data set with outliers. Using M-estimators revisited in a Lagrangian formalism, we derive an algorithm that we call Simultaneous Multiple Robust Fitting (SMRF), which extends the classical Iterative Reweighted Least Squares algorithm (IRLS). Compared to the IRLS, it features an extra probability ratio, which is classical in clustering algorithms, in the expression of the weights. Potential numerical issues are tackled by banning zero probabilities in the computation of the weights and by introducing a Gaussian prior on curves coefficients. Applications to camera calibration and lane-markings tracking show the effectiveness of the SMRF algorithm, which outperforms classical Gaussian mixture model algorithms in the presence of outliers.

This paper treats the estimation of a flat fading Rayleigh channel with Jakes' Doppler spectrum model and slow fading variations. A common method is to use a Kalman filter (KF) based on an auto-regressive model of order p (AR(p)). The parameters of the AR model can be simply tuned by using the correlation matching (CM) criterion. However, the major drawback of this method is that high orders are required to approach the Bayesian Cramer–Rao lower bound. The choice of p together with the tuning of the model parameters is thus critical, and a tradeoff must be found between the numerical complexity and the performance. The reasonable tradeoff arising from setting p = 2 has received much attention in the literature. However, the methods proposed for tuning the model parameters are either based on an extensive grid-search analysis or experimental results, which limits their applicability. A general solution for any scenario is simply missing for p = 2 and this paper aims at filling this gap. We propose using a Minimization of Asymptotic Variance (MAV) criterion, for which a general closed-form formula has been derived for the optimal tuning of the model and the mean square error. This provides deeper insight into the behavior of the KF with respect to the channel state (Doppler frequency and signal to noise ratio). Moreover, the paper interprets the proposed solution, especially the dependence of the shape of the optimal AR(2) spectrum on the channel state. Analytic and numerical comparisons with first- and second-order algorithms in the literature are also performed. Simulation results show that the proposed AR(2)-MAV model performs better than the literature and similarly to AR(p)-CM models with p ≥ 15 .

International audience; This paper addresses the problem of under-determined audio source separation in multichannel reverberant mixtures. We target a semi- blind scenario assuming that the mixing filters are known. Source separation is performed from the time-domain mixture signals in order to accurately model the convolutive mixing process. The source signals are however modeled as latent variables in a time-frequency domain. In a previous paper we proposed to use the modified discrete cosine transform. The present paper generalizes the method to the use of the odd-frequency short-time Fourier transform. In this domain, the source coefficients are modeled as centered complex Gaussian random variables whose variances are structured by means of a non-negative matrix factorization model. The inference procedure relies on a variational expectation-maximization algorithm. In the experiments we discuss the choice of the source representation and we show that the proposed approach outperforms two methods from the literature.

International audience; Regularized Tyler Estimator's (RTE) have raised attention over the past years due to their attractive performance over a wide range of noise distributions and their natural robustness to outliers. Developing adaptive methods for the selection of the regularisation parameter α is currently an active topic of research. Indeed, the bias-performance compromise of RTEs highly depends on the considered application. Thus, finding a generic rule that is optimal for every criterion and/or data configurations is not straightforward. This issue is addressed in this paper for undersampled configurations (number of samples lower than the dimension of the data). The paper proposes a new regularisation parameter selection based on a subspace reduction approach. The performance of this method is investigated in terms of estimation accuracy and for adaptive detection purposes, both on simulation and real data.

The paper introduces a new method for Blind Source Separation (BSS) in noisy instantaneous mixtures of both independent or dependent source component signals. This approach is based on the minimization of a regularized criterion. Precisely, it consists in combining the total variation method for denoising with the Kullback-Leibler divergence between copula densities. The latter takes advantage of the copula to model the structure of the dependence between signal components. The obtained algorithm achieves separation in a noisy context where standard BSS methods fail. The efficiency and robustness of the proposed approach are illustrated by numerical simulations. HighlightsThe paper provides a new Blind source separation for noisy mixtures of independent/dependent sources.The proposed approach combine TV-regularization for denoising and separation by minimizing TV-regularized Kullback-Leibler divergence between copulas.The efficiency and robustness properties of the proposed approach have been illustrated by simulations.

International audience; The notion of tangential cover, based on maximal segments, is a well-known tool to study the geometrical characteristics of a discrete curve. However, it is not robust to noise, while extracted contours from digital images typically contain noise and this makes the geometric analysis tasks on such contours difficult. To tackle this issue, we investigate in this paper a discrete structure, named Adaptive Tangential Cover (ATC), which is based on the notion of tangential cover and on a local noise estimator. More specifically, the ATC is composed of maximal segments with different widths deduced from the local noise values estimated at each point of the contour. Furthermore, a parameter-free algorithm is also presented to compute ATC. This study leads to the proposal of several applications of ATC on noisy digital contours: dominant point detection, contour length estimator, tangent/normal estimator, detection of convex and concave parts. An extension of ATC to 3D curves is also proposed in this paper. The experimental results demonstrate the efficiency of this new notion.

International audience; This paper addresses the problem of robust covariance matrix (CM) estimation in the context of a disturbance composed of a low rank (LR) heterogeneous clutter plus an additive white Gaussian noise. The LR clutter is modeled by a spherically invariant random vector with assumed high clutter-to-noise ratio. In such a context, adaptive process should require less training samples than classical methods to reach equivalent performance as in a “full rank” clutter configuration. The main issue is that classical robust estimators of the CM cannot be computed in the undersampled configuration. To overcome this issue, the current approach is based on regularization methods. Nevertheless, most of these solutions are enforcing the estimate to be well conditioned, while in our context, it should be LR structured. This paper, therefore, addresses this issue and derives an algorithm to compute the maximum likelihood estimator of the CM for the considered disturbance model. Several relaxations and robust generalizations of the result are discussed. Performance is finally illustrated on numerical simulations and on a space time adaptive processing for airborne radar application.

This paper aims to propose a new feature and intensity-based image registration method. The proposed approach is based on the block matching algorithm (Ourselin et al., 2000 1): a displacement field is locally computed by matching spatially invariant intensity sub-blocks of the images before performing an optimization algorithm from this vector field to estimate the transformation. Our approach proposes a new way to calculate the displacement field by matching spatially variant sub-blocks of the images, called General Adaptive Neighborhoods (GANs) (Debayle and Pinoli, 2006 2). These neighborhoods are adaptive with respect to both the intensities and the spatial structures of the image. They represent the patterns within the grayscale images. This paper also presents a consistent shape metric used to match the GANs. The performed qualitative and quantitative experiments show that the proposed GAN matching method provides accurate displacement fields enabling us to perform image rigid registration, even for data from different modalities, that outperforms the classical block matching algorithm with respect to robustness and accuracy criteria. HighlightsNovel image rigid registration method based on a block matching strategy.Displacement vectors computed with spatially variant neighborhoods.Consistent shape metric for matching neighborhoods.Qualitative and quantitative evaluation of the proposed method.

This paper concerns state estimation of stochastic discrete event systems. For that purpose, partially observed stochastic Petri nets are used to model the system and the sensors. From the proposed modelling and the collected measurements, timed sequences which are consistent with those measurements are obtained. Based on the events date, our approach consists on evaluating the probabilities of the marking trajectories using probabilistic model. Such probabilities are important since they reflect the most probable behavior of the system. State estimation is obtained as a consequence.

International audience; Particle filter (PF) is a method dedicated to posterior density estimations using weighted samples whose elements are called particles. In particular, this approach can be applied to object tracking in video sequences in complex situations and, in this paper, we focus on articulated object tracking, i.e., objects that can be decomposed as a set of subparts. One of PF’s crucial step is a resampling step in which particles are resampled to avoid degeneracy problems. In this paper, we propose to exploit mathematical properties of articulated objects to swap conditionally independent subparts of the particles in order to generate new particle sets. We then introduce a new resampling method called Combinatorial Resampling that resamples over the particle set resulting from all the “admissible” swappings, the so-called combinatorial set. In essence, combinatorial resampling (CR) is quite similar to the combination of a crossover operator and a usual resampling, but there exists a fundamental difference between CR and the use of crossover operators: we prove that CR is sound, i.e., in a Bayesian framework, it is guaranteed to represent without any bias the posterior densities of the states over time. By construction, the particle sets produced by CR better represent the density to estimate over the whole state space than the original set and, therefore, CR produces higher quality samples. Unfortunately, the combinatorial set is generally of an exponential size and, therefore, to be scalable, we show how it can be implicitly constructed and resampled from, thus resulting in both an efficient and effective resampling scheme. Finally, through experimentations both on challenging synthetic and real video sequences, we also show that our resampling method outperforms all classical resampling methods both in terms of the quality of its results and in terms of computation times.

In the framework of Compressive Sensing (CS), the inherent structures underlying sparsity patterns can be exploited to promote the reconstruction accuracy and robustness. And this consideration results in a new extension for CS, called model based CS. In this paper, we propose a general statistical framework for model based CS, where both sparsity and structure priors are considered simultaneously. By exploiting the Latent Variable Analysis (LVA), a sparse signal is split into weight variables representing values of elements and latent variables indicating labels of elements. Then the Gamma-Gaussian model is exploited to describe weight variables to induce sparsity, while the beta process is assumed on each of the local clusters to describe inherent structures. Since the complete model is an extension of Bayesian CS and the process is for local properties, it is called Model based Bayesian CS via Local Beta Process (MBCS-LBP). Moreover, the beta process is a Bayesian conjugate prior to the Bernoulli Process, as well as the Gamma to Gaussian distribution, thus it allows for an analytical posterior inference through a variational Bayes inference algorithm and hence leads to a deterministic VB-EM iterative algorithm. HighlightsThis paper is dealing with the recovery problem for model based compressive sensing.This paper has proposed a hierarchical Bayesian model to describe the model based compressive sensing.Local Beta Process has been applied to describe the inherent structures of the sparse signals.Variational Bayesian approach has been exploited to implement the Bayesian inference.

International audience; In this paper, we address the problem of detecting and localizing closely spaced moving targets using a compressed sensing approach. In a previous work, we demonstrated the interest of a compressed sensing approach for overcoming Doppler ambiguities and proposed the N-signal Adaptive Grid Orthogonal Matching Pursuit (N-signal-AGOMP) [1] for the detection and estimation of moving targets in a continuous and ambiguous Doppler domain. Such an approach has to face grid refinement problems that may lead to reduced estimation performance when targets are closely spaced. In this paper, we propose a high resolution Orthogonal Matching Pursuit (OMP) based algorithm that sequentially refines target parameters based on a Non-linear Least Squares (NLS) estimator. We also propose to combine this algorithm with a hypothesis test process to enhance the probability to distinguish nearby targets. Simulation results show that the proposed method allows to detect and accurately estimate target parameters even when they are separated by less than half the Doppler Matched Filter (MF) resolution.

International audience; In this paper we focus on problems that deal with comparison of shapes of trajectories. One motivation comes from action recognition where features extracted from video (or RGB Depth video) frames are naturally represented by elements of nonlinear manifolds, and where temporal evolutions of an action can be modeled by trajectories on those manifolds. How- ever, as mentionned by [11], [14] and [7], the execution rate (velocity) of activities may often vary. It follows that, without the execution invariance, two identical actions can be viewed as very different trajectories. Typical approaches for accounting for variations in execution rate are either directly based on the dynamic time warping (DTW) algorithm or some variation of this algorithm.One promising idea is to formulate the features motion as trajectories. Matikainen et al. [4] present a method for using the trajectories of tracked feature points in a bag of words paradigm for video action recognition. Despite of the promising results obtained, the authors do not take into account the geometric information of the trajectories.More recently, in the case of human skeleton in RGB-Depth images, Devianne et al. [2] propose to formulate the actions recognition as the problem of computing a distance between trajectories generated by the joints moving during the action. An action is a parameterized path on the shape space of the human skeleton. Similar to the ideas of Devianne et al., Su et al. [8] propose a metric which takes into account time-warping on a Riemannian manifold. They propose a metric, which allows the regitration of trajectories and compute statistics of the trajectories. Su et al. [9] apply this framework to the problem of visual speech recognition. All these approachs require a registration of trajectories. In the present paper, we propose a new theoretical framework which uses the shape information of trajectories. The main contributions of this paper are:• The proposed framework is independent of time-re-parameterization of trajectories in $R3$.• A new rate-invariant metric on the shape space of trajectories is proposed. No trajec- tories registration is required.• We demonstrate the use of this framework theory in two computer vision applications.The rest of this paper is organized as follows. Section 2 presents the gauge invariant framework for comparing shapes. Section 3 presents applications of the proposed approach to action recognition.

Top 10% paper; International audience; This paper addresses the problem of two-region noisy image segmentation in the presence of intensity inhomogeneity and of unknown noise fluctuations. For that purpose, the inhomogeneity is modeled as spatial variations of the mean intensity (which are different inside and outside the object) and are estimated using Local Binary Fitting (LBF) approach. In order to be robust to non standard noise phenomena, the intensity fluctuations are then modeled with nonparametric probability density functions (pdf) leading to a new polygonal active contour segmentation technique based on a Minimum Description Length (MDL) criterion which does not require a priori knowledge on the intensity fluctuations and on the inhomogeneity present in the image. Furthermore, it will be shown that in the case of highly inhomogeneous images, the standard LBF approach used to estimate the intensity inhomogeneity can be generalized to Quadratic Local Binary Fitting (QLBF) in order to improve the performance of the proposed segmentation technique.

International audience; The paper addresses the problem of target detection embedded in a disturbance composed of a low rank Gaussian clutter and a white Gaussian noise. In this context, it is interesting to use an adaptive version of the Low Rank Normalized Matched Filter detector, denoted LR-ANMF, which is a function of the estimation of the projector onto the clutter subspace. In this paper, we show that the LR-ANMF detector based on the sample covariance matrix is consistent when the number of secondary data K tends to infinity for a fixed data dimension m but not consistent when m and K both tend to infinity at the same rate, i.e. m/K → c ∈ (0, 1]. Using the results of random matrix theory, we then propose a new version of the LR-ANMF which is consistent in both cases and compare it to a previous version, the LR-GSCM detector. The application of the detectors from random matrix theory on STAP (Space Time Adaptive Processing) data shows the interest of our approach.

This paper deals with lossy compression of images corrupted by additive white Gaussian noise. For such images, compression can be characterized by existence of optimal operation point (OOP). In OOP, MSE or other metric derived between compressed and noise-free image might have optimum, i.e., maximal noise removal effect takes place. If OOP exists, then it is reasonable to compress an image in its neighbourhood. If no, more “careful” compression is reasonable. In this paper, we demonstrate that existence of OOP can be predicted based on very simple and fast analysis of discrete cosine transform (DCT) statistics in 8x8 blocks. Moreover, OOP can be predicted not only for conventional metrics as MSE or PSNR but also for visual quality metrics. Such prediction can be useful in automatic compression of multi- and hyperspectral remote sensing images.

978-0-7354-1280-4; International audience; In order to improve quality of 3D X-ray tomography reconstruction for Non Destructive Testing (NDT), we investigate in this paper hierarchical Bayesian methods. In NDT, useful prior information on the volume like the limited number of materials or the presence of homogeneous area can be included in the iterative reconstruction algorithms. In hierarchical Bayesian methods, not only the volume is estimated thanks to the prior model of the volume but also the hyper parameters of this prior. This additional complexity in the reconstruction methods when applied to large volumes (from 5123 to 81923 voxels) results in an increasing computational cost. To reduce it, the hierarchical Bayesian methods investigated in this paper lead to an algorithm acceleration by Variational Bayesian Approximation (VBA) [1] and hardware acceleration thanks to projection and back-projection operators paralleled on many core processors like GPU [2].In this paper, we will consider a Student-t prior on the gradient of the image implemented in a hierarchical way [3, 4, 1]. Operators H (forward or projection) and Ht (adjoint or back-projection) implanted in multi-GPU [2] have been used in this study. Different methods will be evalued on synthetic volume "Shepp and Logan" in terms of quality and time of reconstruction. We used several simple regularizations of order 1 and order 2. Other prior models also exists [5]. Sometimes for a discrete image, we can do the segmentation and reconstruction at the same time, then the reconstruction can be done with less projections.

International audience; The paper addresses the selection of the best representations for distributed and/or dependent signals. Given an indexed tree structured library of bases and a semi-collaborative distribution scheme associated with minimum information exchange (emission and reception of one single index corresponding to a marginal best basis), the paper proposes the median basis computed on a set of best marginal bases for joint representation or fusion of distributed/dependent signals. The paper provides algorithms for computing this median basis with respect to standard tree structured libraries of bases such as wavelet packet bases or cosine trees. These algorithms are effective when an additive information cost is under consideration. Experimental results performed on distributed signal compression confirms worthwhile properties for the median of marginal best bases with respect to the ideal best joint basis, the latter being underdetermined in practice, except when a full collaboration scheme is under consideration.

International audience; In this paper we propose two iterative algorithms for the blind separation of convolutive mixtures of sparse signals. The first one, called Iterative Sparse Blind Separation (ISBS), minimizes a sparsity cost function using an approximate Newton technique. The second algorithm, referred to as Givens-based Sparse Blind Separation (GSBS) computes the separation matrix as a product of a whitening matrix and a unitary matrix estimated, via a Jacobi-like process, as the product of Givens rotations which minimize the sparsity cost function. The two sparsity based algorithms show significantly improved performance with respect to the time coherence based SOBI algorithm as illustrated by the simulation results and comparative study provided at the end of the paper.

This paper presents a symbolic and recursive calculation of the elastodynamic model of flexible parallel robots. In order to reduce the computational time required for simulating the elastodynamic behavior of robots, it is necessary to minimize the number of operators in the symbolic expression of the model. Some algorithms have been proposed for the rigid case, for parallel robots with lumped springs or for serial robots with distributed flexibilities. In this paper, we extend the previous works to parallel robots with distributed flexibilities. The generalized Newton–Euler model is used and combined with the principle of virtual powers to minimize the number of operators and intermediate variables. Recursive calculations are proposed for the computation of the Jacobian matrices defining the kinematic constraints in order to decrease the number of operators. The proposed algorithm is used to compute the elastodynamic model of a prototype of a planar parallel robot developed at IRCCyN: the DualEMPS. The computed model is compared both with simulations computed with Adams and with experiments. The validity of the approach in terms of result accuracy and computational time is demonstrated.

A collection of sets on a ground set Un (Un = {1,2,...,n}) closed under intersection and containing Un is known as a Moore family. The set of Moore families for a fixed n is in bijection with the set of Moore co-families (union-closed families containing the empty set) denoted \({\mathbb{M}}_n\). This paper follows the work initiated in Colomb et al. (Ann Math Artif Intell 67(2):109–122, 2013) in which we have given an inductive definition of the lattice of Moore co-families. In the present paper we use this definition to define a recursive decomposition tree of any Moore co-family and we design an original algorithm to compute the closure under union of any family. Then we compare performance of this algorithm to performance of Ganter’s algorithm and Norris’ algorithm.

The purpose of this paper is to develop new efficient approaches based on DC (Difference of Convex functions) programming and DCA (DC Algorithm) to perform clustering via minimum sum-of-squares Euclidean distance. We consider the two most widely used models for the so-called Minimum Sum-of-Squares Clustering (MSSC in short) that are a bilevel programming problem and a mixed integer program. Firstly, the mixed integer formulation of MSSC is carefully studied and is reformulated as a continuous optimization problem via a new result on exact penalty technique in DC programming. DCA is then investigated to the resulting problem. Secondly, we introduce a Gaussian kernel version of the bilevel programming formulation of MSSC, named GKMSSC. The GKMSSC problem is formulated as a DC program for which a simple and efficient DCA scheme is developed. A regularization technique is investigated for exploiting the nice effect of DC decomposition and a simple procedure for finding good starting points of DCA is developed. The proposed DCA schemes are original and very inexpensive because they amount to computing, at each iteration, the projection of points onto a simplex and/or onto a ball, and/or onto a box, which are all determined in the explicit form. Numerical results on real word datasets show the efficiency, the scalability of DCA and its great superiority with respect to k-means and kernel k-means, standard methods for clustering. HighlightsThe purpose of this paper is to develop new efficient approaches based on DC programming and DCA for clustering.We consider the two models for the Minimum Sum-of-Squares Clustering (MSSC): a mixed integer program and a bilevel programming formulation.The mixed integer program is reformulated as a DC program via an exact penalty technique for which DCA is investigated.A Gaussian kernel version of the bilevel programming formulation is introduced and a simple and efficient DCA scheme is developed.The two main features of DCA, say the effect of DC decomposition and of starting points, are carefully studied.

In this paper, an original observation model for multiresolution optical flow estimation is introduced. Multiresolution frameworks, often based on coarse-to-fine warping strategies, are widely used by state-of-the-art optical flow methods. They allow the recovery of large motions by successive estimations of the flow field at several resolution levels. Although such approaches perform very efficiently and usually lead to faster minimizations, they generally consider independent problems at each resolution levels and do not exploit the existing interactions between scales (especially the influences of fine scales on larger ones). In this paper, we tackle this issue by proposing a flexible framework, inspired from fluid mechanics, able to partly counter these limitations. For each resolution level, our process filters the equations of interest and decomposes the key variables into resolved (i.e., at a given resolution) and unresolved (i.e., at finer resolutions) components. This enables to derive a new data term that takes into account, at coarse resolutions, the influence of their unresolved parts. From this new term, we propose two different estimation strategies, depending on whether we explicitly know the type of relations between the different scales (as for physical processes) or not. In order to test the efficiency of this new observation model, we have embedded it in a simple multiresolution Lucas-Kanade estimator. Comparing the usual optical flow constraint equation with this new term in the same motion estimation procedure, it clearly appears that the proposed term leads to more consistent estimates and prevents from errors propagation apparition during the estimation. In all situations (synthetic, real, physical images or not), our new term is able to greatly improve the results compared with usual conservation constraints.

International audience; The problem of minimising the number of distinct values among a set of variables subject to difference constraints occurs in many real-life contexts. This is the case of the shift minimisation personnel task scheduling problem, introduced by Krishnamoorthy et. al., which is used as a case study all along this paper. Constraint-Programming enables to formulate this problem easily, through several AllDifferent constraints and a single AtMostNValue constraint. However, the independence of these constraints results in a poor lower bounding, hence a difficulty to prove optimality. This paper introduces a formalism to describe a family of propagators for AtMostNValue . In particular, we provide simple but significant improvement of the state-of-the-art AtMostNValue propagator of Bessière et. al., to filter the conjunction of an AtMostNValue constraint and disequalities. In addition, we provide an original search strategy which relies on constraint reification. Extensive experiments show that our contribution significantly improves a straightforward model, so that it competes with the best known approaches from Operational Research.

International audience; The goal of the paper is to propose an optimal statistical test for the steganalysis of Jsteg algorithm. The test is based on a state-of-the-art statistical model of quantized Discrete Cosine Transform (DCT) coefficients that allows us to reliably detect any small change in a cover image due to hidden information. By formulating the hidden information detection as a hypothesis testing problem, the paper designs the most powerful Likelihood Ratio Test (LRT) assuming that all model parameters are perfectly known. The statistical performance of the LRT is analytically provided. Numerical results and comparison with other detectors highlight the relevance of the proposed approach.

International audience; In this paper, two simple-structure neural networks based on the error back-propagation (BP) algorithm (i.e., BP-type neural networks, BPNNs) are proposed, developed, and investigated for online generalized matrix inversion. Specifically, the BPNN-L and BPNN-R models are proposed and investigated for the left and right generalized matrix inversion, respectively. In addition, for the same problem-solving task, two discrete-time Hopfield-type neural networks (HNNs) are developed and investigated in this paper. Similar to the classification of the presented BPNN-L and BPNN-R models, the presented HNN-L and HNN-R models correspond to the left and right generalized matrix inversion, respectively. Comparing the BPNN weight-updating formula with the HNN state-transition equation for the specific (i.e., left or right) generalized matrix inversion, we show that such two derived learning-expressions turn out to be the same (in mathematics), although the BP and Hopfield-type neural networks are evidently different from each other a great deal, in terms of network architecture, physical meaning, and training patterns. Numerical results with different illustrative examples further demonstrate the efficacy of the presented BPNNs and HNNs for online generalized matrix inversion and, more importantly, their common natures of learning.

International audience; A current challenging topic in mathematical morphology is the construction of locally adaptive operators; i.e., structuring functions that are dependent on the input image itself at each position. Development of spatially-variant filtering is well established in the theory and practice of Gaussian filtering. The aim of the first part of the paper is to study how to generalize these convolution-based approaches in order to introduce adaptive nonlinear filters that asymptotically correspond to spatially-variant morphological dilation and erosion. In particular, starting from the bilateral filtering framework and using the notion of counter-harmonic mean, our goal is to propose a new low complexity approach to define spatially-variant bilateral structuring functions. Then, in the second part of the paper, an original formulation of spatially-variant flat morphological filters is proposed, where the adaptive structuring elements are obtained by thresholding the bilateral structuring functions. The methodological results of the paper are illustrated with various comparative examples.

This paper concerns project scheduling under uncertainty. The project is modeled as an activity-on-node network, each activity having an uncertain duration represented by an interval. The problem of computing the minimum float of each activity over all duration scenarios is addressed. For solving this NP-hard problem, Dubois et al. (in J. Intell. Manuf. 16, 407---422, 2005) and Fortin et al. (in J. Sched. doi: 10.1007/s10951-010-0163-3 , 2010) have proposed an algorithm based on path enumeration. In this paper, new structural properties of optimal solutions are established and used for deriving a lower bound and designing an efficient branch-and-bound procedure. Two mixed-integer programming formulations are also proposed. Computational experimentations have been conducted on a large variety of randomly generated problem instances. The results show that the proposed branch-and-bound procedure is very fast and consistently outperforms the MIP formulations and the path enumeration algorithm.

International audience; In this paper we propose to investigate the use of a vectorial total variation model with spatially varying regularization and data terms for color image denoising and restoration. We pay attention to two main minimization problems: the minimization of a weighted vectorial total variation term TVg , which acts as a regularization term, using the L2 norm as data term or the minimization of the vectorial total variation with a spatially varying L1g norm. The optimization process takes benefit of convex optimization tools by introducing an augmented Lagrangian formulation. This formulation leads us to simple and efficient algorithms based on Uzawa block relaxation schemes that are also robust towards the choice of the penalty parameter. In this paper, We propose to study more particularly the impact of spatially varying terms (total variation term or data terms) for color image restoration. A new weighted total variation term is proposed for old parchments restoration and we also compare the use of a weighted total variation term with a spatially varying data term for impulse noise removal in color images.

Highlights? The greedy acceptance criterion for the glowworms updating positions is proposed. ? The new formulas for the glowworms movement are proposed. ? Uniform design experiments were investigated the effect of parameters. ? The proposed improvement algorithms were effective than the classical algorithm. Dislocation is defined as the change between discrete sequential locations of critical items in field environments such as large construction projects. Dislocations on large sites of materials and critical items for which discrete time position estimates are available represent critical state changes. The ability to detect dislocations automatically for tens of thousands of items can ultimately improve project performance significantly. Detecting these dislocations in a noisy information environment where low cost radio frequency identification tags are attached to each piece of material, and the material is moved sometimes only a few meters, is the main focus of this study. We propose in this paper a method developed in the frame of belief functions to detect dislocations. The belief function framework is well-suited for such a problem where both uncertainty and imprecision are inherent to the problem. We also show how to deal with the calculations. This method has been implemented in a controlled experimental setting. The results of these experiments show the ability of the proposed method to detect materials dislocation over the site reliably. Broader application of this approach to both animate and inanimate objects is possible.

International audience; Deblurring noisy Poisson images has recently been subject of an increasingly amount of works in many areas such as astronomy or biological imaging. In this paper, we focus on confocal microscopy which is a very popular technique for 3D imaging of biological living specimens which gives images with a very good resolution (several hundreds of nanometers), even though degraded by both blur and Poisson noise. Deconvolution methods have been proposed to reduce these degradations and we focus in this paper on techniques which promote the introduction of explicit prior on the solution. One difficulty of these techniques is to set the value of the parameter which weights the trade-off between the data term and the regularizing term. Actually, only few works have been devoted to the research of an automatic selection of this regularizing parameter when considering Poisson noise so it is often set manually such that it gives the best visual results. We present here two recent methods to estimate this regularizing parameter and we first propose an improvement of these estimators which takes advantage of confocal images. Following these estimators, we secondly propose to express the problem of Poisson noisy images deconvolution as the minimization of a new constrained problem. The proposed constrained formulation is well suited to this application domain since it is directly expressed using the anti log-likelihood of the Poisson distribution and therefore does not require any approximation. We show how to solve the unconstrained and constrained problem using the recent Alternating Direction technique and we present results on synthetic and real data using well-known priors such as Total Variation and wavelet transforms. Among these wavelet transforms, we specially focus on the Dual-Tree Complex Wavelet transform and on the dictionary composed of Curvelets and undecimated wavelet transform.

International audience; An image segmentation process often results in a special spatial set, called a mosaic, as the subdivision of a domain S within the n-dimensional Euclidean space. In this paper, S will be a compact domain and the study will be focused on finite Jordan mosaics, that is to say mosaics with a finite number of regions and where the boundary of each region is a Jordan hypersurface. The first part of this paper addresses the problem of comparing a Jordan mosaic to a given reference Jordan mosaic and introduces the (Epsilon) dissimilarity criterion. The second part will show that the (Epsilon) dissimilarity criterion can be used to perform the evaluation of image segmentation processes. It will be compared to classical criterions in regard to several geometric transformations. The pros and cons of these criterions are presented and discussed, showing that the dissimilarity criterion outperforms the other ones.

The geometric interpretation of Nonnegative Matrix Factorisation (NMF) as the problem of determining a convex cone that “well describes” the data under analysis has been key for addressing a major shortcoming of the “mainstream” NMF algorithms, that is the non-identifiability of the factorisation. On the basis of such geometric motivations, this paper proposes a novel algorithm that makes use of single-class support vector machines to recover the targeted NMF components. Not only does this new approach alleviate the NMF illposedness issue, but also it allows for automatically estimating the number of relevant NMF components, as demonstrated through experiments described in the paper. Moreover, it is readily kernelised thus opening the way for non-linear factorisations of the data.

International audience; The Sample Covariance Matrix (SCM) is widely used in signal processing applications which require the estimation of the data covariance matrix. Indeed it exhibits good statistical properties and tractability. However its performance can become very bad in context of non-Gaussian signals, contaminated or missing data. In that case M-estimators provide a good alternative. They have been introduced within the framework of elliptical distributions which encompass a large number of well-known distributions as for instance the Gaussian, the K-distribution or the multivariate Student (or t) distribution. In this paper, we show that with an appropriate normalization, the SCM and M-estimators have the same asymptotic behavior. More precisely, they share the same asymptotic covariance up to a scale factor. Tyler (1983) obtains similar results but we propose here a simpler proof for the case of M-estimators. The important consequence is that the SCM can easily be replaced by M-estimators with minor changes in performance analysis of signal processing algorithms. This result is highlighted by simulations in Direction-Of-Arrival (DOA) estimation using a MUltiple SIgnal Classification (MUSIC) approach. In this paper, we address the case of real data. These results have also been extended to the complex case but, due to the lack of space and for clarity of the presentation, this generalization will be omitted and will be addressed later.

International audience; In this paper, we propose a novel method to introduce spatial information in particle filters. This information may be expressed as spatial relations (orientation, distance, etc.), velocity, scaling, or shape information. Spatial information is modeled in a generic fuzzy-set framework. The fuzzy models are then introduced in the particle filter and automatically define transition and prior spatial distributions. We also propose an efficient importance distribution to produce relevant particles, which is dedicated to the proposed fuzzy framework. The fuzzy modeling provides flexibility both in the semantics of information and in the transitions from one instant to another one. This allows one to take into account situations where a tracked object changes its direction in a quite abrupt way and where poor prior information on dynamics is available, as demonstrated on synthetic data. As an illustration, two tests on real video sequences are performed in this paper. The first one concerns a classical tracking problem and shows that our approach efficiently tracks objects with complex and unknown dynamics, outperforming classical filtering techniques while using only a small number of particles. In the second experiment, we show the flexibility of our approach for modeling: Fuzzy shapes are modeled in a generic way and allow the tracking of objects with changing shape.

International audience; This paper is devoted to automated sequential decision in AI. More precisely, we focus here on the Rank Dependent Utility (RDU) model. This model is able to encompass rational decision behaviors that the Expected Utility model cannot accommodate. However, the non-linearity of RDU makes it difficult to compute an RDU-optimal strategy in sequential decision problems. This has considerably slowed the use of RDU in operational contexts. In this paper, we are interested in providing new algorithmic solutions to compute an RDU-optimal strategy in graphical models. Specifically, we present algorithms for solving decision tree models and influence diagram models of sequential decision problems. For decision tree models, we propose a mixed integer programming formulation that is valid for a subclass of RDU models (corresponding to risk seeking behaviors). This formulation reduces to a linear program when mixed strategies are considered. In the general case (i.e., when there is no particular assumption on the parameters of RDU), we propose a branch and bound procedure to compute an RDU-optimal strategy among the pure ones. After highlighting the difficulties induced by the use of RDU in influence diagram models, we show how this latter procedure can be extended to optimize RDU in an influence diagram. Finally, we provide empirical evaluations of all the presented algorithms.

Special issue on Advances in Angle-of-Arrival and Multidimensional Signal Processing for Localization and Communications; International audience; The Statistical Resolution Limit (SRL), which is defined as the minimal separation between parameters to allow a correct resolvability, is an important statistical tool to quantify the ultimate performance for parametric estimation problems. In this paper we generalize the concept of the SRL to the Multidimensional SRL (MSRL) applied to the multidimensional harmonic retrieval model. In this paper, we derive the SRL for the so-called multidimensional harmonic retrieval model by using a generalization of the previously introduced SRL concepts that we call Multidimensional SRL (MSRL). We first derive the MSRL using an hypothesis test approach. This statistical test is shown to be asymptotically an uniformly most powerful test which is the strongest optimality statement that one could expect to obtain. Second, we link the proposed asymptotic MSRL based on the hypothesis test approach to a new extension of the SRL based on the Cramér-Rao Bound approach. Thus, a closed-form expression of the asymptotic MSRL is given and analyzed in the framework of the multidimensional harmonic retrieval model. Particularly, it is proved that the optimal MSRL is obtained for equi-powered sources and/or an equi-distributed number of sensors on each multi-way array.

International audience; We first introduce in this paper a new wavelet based segmentation algorithm for three-dimensional (3-D) Semi-Regular (SR) meshes. This method is then considered as a pre-processing step in a view-dependent progressive coding of 3-D meshes. Our segmentation process aims at producing homogeneous regions which have similar frequency amplitudes on the mesh surface, in other words: patches with different degrees of roughness. As a preliminary step of the development of a locally-based Rate-Distortion (R-D) optimized coding scheme, we propose to study the behaviour of the wavelet decomposition in the created patches, during the coding and the view-dependent reconstruction processes. To our knowledge, no previous work has ever considered the influence of the nonrefined parts of a mesh on the more detailed ones, in a view dependent context. The main contribution of this paper consists in considering three different possible wavelet decompositions, close to the patch borders, and to study their influence during the coding and the view-dependent reconstruction stages. Among these three decompositions, we define a new scheme and finally propose various experimentations to demonstrate that it behaves better than the other classical considerations, for view-dependent reconstruction purposes.

Multiplicative update algorithms have proved to be a great success in solving optimization problems with nonnegativity constraints, such as the famous nonnegative matrix factorization (NMF) and its many variants. However, despite several years of research on the topic, the understanding of their convergence properties is still to be improved. In this paper, we show that Lyapunov's stability theory provides a very enlightening viewpoint on the problem. We prove the exponential or asymptotic stability of the solutions to general optimization problems with nonnegative constraints, including the particular case of supervised NMF, and finally study the more difficult case of unsupervised NMF. The theoretical results presented in this paper are confirmed by numerical simulations involving both supervised and unsupervised NMF, and the convergence speed of NMF multiplicative updates is investigated.

International audience; In this paper, we propose a high-order graph matching formulation to address non-rigid surface matching. The singleton terms capture the geometric and appearance similarities (e.g., curvature and texture) while the high-order terms model the intrinsic embedding energy. The novelty of this paper includes: 1. casting 3D surface registration into a graph matching problem that combines both geometric and appearance similarities and intrinsic embedding information, 2. the first implementation of high-order graph matching algorithm that solves a non-convex optimization problem, and 3. an efficient two-stage optimization approach to constrain the search space for dense surface registration. Our method is validated through a series of experiments demonstrating its accuracy and efficiency, notably in challenging cases of large and/or non-isometric deformations, or meshes that are partially occluded.

International audience; The construction of hole filling (or hole segmentation) method for 3D volumetric images is a new challenging issue in computer science. It needs a geometrical approach since from a topological point of view 3D holes (tunnels) are not well-delimited subsets of three dimensional space. In this paper, the authors propose an original, efficient, flexible algorithm of hole filling for volumetric objects. The algorithm has been tested on artificial objects and very complicated crack propagation tomography images. The qualitative results, quantitative results and features of proposed approach are presented in the paper. According to our knowledge it is the first algorithm of hole filling for volumetric objects.

The coding resources used for motion vectors (MVs) can attain quite high ratios even in the case of efficient video coders like H.264, and this can easily lead to suboptimal rate-distortion performance. In a previous paper, we proposed a new coding mode for H.264 based on the quantization of motion vectors (QMV). We only considered the case of 16x16 partitions for motion estimation and compensation. That method allowed us to obtain an improved trade-off in the resource allocation between vectors and coefficients, and to achieve better rate-distortion performances with respect to H.264. In this paper, we build on the proposed QMV coding mode, extending it to the case of macroblock partition into smaller blocks. This issue requires solving some problems mainly related to the motion vector coding. We show how this task can be performed efficiently in our framework, obtaining further improvements over the standard coding technique.

International audience; In this paper, we consider sparse decomposition (SD) of twodimensional (2D) signals on overcomplete dictionaries with separable atoms. Although, this problem can be solved by converting it to the SD of one-dimensional (1D) signals, this approach requires a tremendous amount of memory and computational cost. Moreover, the uniqueness constraint obtained by this approach is too restricted. Then in the paper, we present an algorithm to be used directly for sparse decomposition of 2D signals on dictionaries with separable atoms. Moreover, we will state another uniqueness constraint for this class of decomposition. Our algorithm is obtained by modifying the Smoothed L0 (SL0) algorithm, and hence we call it two-dimensional SL0 (2D-SL0).

best paper award -; International audience; In this paper, we consider the pre-image problem in kernel machines, such as denoising with kernel-PCA. For a given reproducing kernel Hilbert space (RKHS), by solving the pre-image problem one seeks a pattern whose image in the RKHS is approximately a given feature. Traditional techniques include an iterative technique (Mika et al.) and a multidimensional scaling (MDS) approach (Kwok et al.). In this paper, we propose a new technique to learn the pre-image. In the RKHS, we construct a basis having an isometry with the input space, with respect to a training data. Then representing any feature in this basis gives us information regarding its pre-image in the input space. We show that doing a pre-image can be done directly using the kernel values, without having to compute distances in any of the spaces as with the MDS approach. Simulation results illustrates the relevance of the proposed method, as we compare it to these techniques.

In this paper, we present a new thresholding technique based on two-dimensional fractional differentiation, that was obtained through the extension of the one-dimensional fractional differentiation. A new geometric interpretation of the two-dimensional fractional differentiation is also presented in the paper. The proposed method exploits the properties and the interpretations of the two-dimensional fractional differentiation. It is based on the assumption that there is a dependency between the pixels' gray-levels, that is translated into a correlation between pixels describing the same object. The effectiveness of the proposed method is demonstrated by using examples from real-world and synthetic images.

International audience; In this paper we are interested in non-negative matrix factorization (NMF) with the Itakura-Saito (IS) divergence. Previous work has demonstrated the relevance of this cost function for the decomposition of audio power spectrograms. This is in particular due to its scale invariance, which makes it more robust to the wide dynamics of audio, a property which is not shared by other popular costs such as the Euclidean distance or the generalized Kulback-Leibler (KL) divergence. However, while the latter two cost functions are convex, the IS divergence is not, which makes it more prone to convergence to irrelevant local minima, as observed empirically. Thus, the aim of this paper is to propose a tempering scheme that favors convergence of IS-NMF to global minima. Our algorithm is based on NMF with the beta-divergence, where the shape parameter beta acts as a temperature parameter. Results on both synthetical and music data (in a transcription context) show the relevance of our approach.

The recognition of digital shapes is a deeply studied problem. The arithmetical framework, initiated by Reveilles [Geometrie discrete, calcul en nombres entiers et algorithmique, These d'Etat, 1991], provides a powerful theoretical basis, as well as many algorithms to deal with digital objects. The tangential cover, first presented in Feschet and Tougne [Optimal time computation of the tangent of a discrete curve: application to the curvature, in: G. Bertrand, M. Couprie, L. Perroton (Eds.), 8th Discrete Geometry for Computer Imagery, Lecture Notes in Computer Science, vol. 1568, Springer, Berlin, 1999, pp. 31-40] and Feschet [Canonical representations of discrete curves, Pattern Anal. Appl. 8(1-2) (2005) 84-94] is a useful tool for representing geometric digital primitives. It computes the set of all maximal segments of a digital curve and permits either to obtain minimal length polygonalization or asymptotic convergence of tangents estimations. Nevertheless, the arithmetical approach does not tolerate the introduction of irregularities, which are however inherent to the acquisition of digital shapes. The present paper is an extension of Faure and Feschet [Tangential cover for thick digital curves, in: D. Coeurjolly, I. Sivignon, L. Tougne, F. Dupont (Eds.), DGCI 2008, Lecture Notes in Computer Science, vol. 4992, Springer, Berlin, 2008, pp. 358-369], in which we propose a new definition for a class of the so-called ''thick digital curves'' that applies well to a large class of digital object boundaries. We then propose an extension of the tangential cover to thick digital curves and provide an algorithm with an O(nlogn) time complexity, where n denotes the number of points of specific subparts of the thick digital curve. In order to keep up with this low complexity, some critical points must be taken into account. We describe all required implementation details in this paper.

There exist many simple tools for jointly capturing variability and incomplete information by means of uncertainty representations. Among them are random sets, possibility distributions, probability intervals, and the more recent Ferson's p-boxes and Neumaier's clouds, both defined by pairs of possibility distributions. In the companion paper, we have extensively studied a generalized form of p-box and situated it with respect to other models . This paper focuses on the links between clouds and other representations. Generalized p-boxes are shown to be clouds with comonotonic distributions. In general, clouds cannot always be represented by random sets, in fact not even by 2-monotone (convex) capacities., Comment: 30 pages, 7 figures, Pre-print of journal paper to be published in International Journal of Approximate Reasoning (with expanded section concerning clouds and probability intervals)