In this paper, we consider multiple Unmanned Aerial Vehicles (UAV) serving as flying Base Stations (BS) of a wireless network and the problem of jointly optimizing their trajectory with respect to a running cost. This cost accounts for the consumed energy related to the vehicle velocity and for the amount of data traffic collected or served by the UAVs. The data traffic is supposed to be spatially distributed around a hotspot and is equivalent to a potential in Physics. Using the principles of Lagrangian Mechanics, we derive a scalable algorithm able to optimize the trajectory of thousands of drones in milliseconds on a off-the-shelf laptop. Our model allows to control the distance between the UAVs to avoid collisions by using a coupling between the drone trajectories.

We consider the problem of optimizing the trajectory of an Unmanned Aerial Vehicle (UAV). Assuming a traffic intensity map of users to be served, the UAV must travel from a given initial location to a final position within a given duration and serves the traffic on its way. The problem consists in finding the optimal trajectory that minimizes a certain cost depending on the velocity and on the amount of served traffic. We formulate the problem using the framework of Lagrangian mechanics. We derive closed-form formulas for the optimal trajectory when the traffic intensity is quadratic (single-phase) using Hamilton-Jacobi equations. When the traffic intensity is bi-phase, i.e. made of two quadratics, we provide necessary conditions of optimality that allow us to propose a gradient-based algorithm and a new algorithm based on the linear control properties of the quadratic model. These two solutions are of very low complexity because they rely on fast convergence numerical schemes and closed form formulas. These two approaches return a trajectory satisfying the necessary conditions of optimality. At last, we propose a data processing procedure based on a modified K-means algorithm to derive a bi-phase model and an optimal trajectory simulation from real traffic data.

Relay nodes-enhanced architectures are deemed a viable solution to enhance coverage and capacity of nowadays cellular networks. Besides a number of desirable features, these architectures reduce the average distance between users and network nodes, thus allowing for battery savings for users transmitting on the uplink. In this paper, we investigate the extent of these savings, by optimizing relay nodes deployment in terms of uplink energy consumption per transmitted bit, while taking into account a minimum uplink average user delay that has to be guaranteed. A novel performance evaluation framework for uplink relay networks is first proposed to study this energy-delay trade-off. A simulated annealing is then run to find an optimized relay placement solution under a delay constraint; exterior penalty functions are used in order to deal with a difficult energy landscape, in particular when the constraint is tight. Finally, results show that relay nodes deployment consistently improve users uplink energy efficiency, under a wide range of traffic conditions and that relays are particularly efficient in non-uniform traffic scenarios.

In this paper, we address the problem of optimally placing relay nodes in a cellular network with the aim of maximizing cell capacity. In order to accurately model interference, we use a dynamic framework, in which users arrive at random time instants and locations, download a file and leave the system. A fixed point equation is solved to account for the interactions between stations. We also propose an extension of a fluid model to relay based cellular networks. This allows us to obtain quick approximations of the Signal to Interference plus Noise Ratio (SINR) that are very close to 3GPP LTE-A guideline results in terms of SINR distribution. We then use these formulas to develop a dedicated Simulated Annealing (SA) algorithm, which adapts dynamically the temperature to energy variations and uses a combination of coarse and fine grids to accelerate the search for an optimized solution. Simulations results are provided for both in-band and out-of-band relays. They show how relays should be placed in a cell in order to increase the capacity in case of uniform and non-uniform traffic. The crucial impact of the backhaul link is analyzed for in-band relays. Insights are given on the influence of shadowing.

In this paper, we demonstrate how a Markov Random Field (MRF) based framework can be used for multihop networks analysis and design. In fields such as image processing it has been shown that MRFs is a powerful tool to analyse distributed systems with strong spacial interactions, which is also a defining characteristic of multihop networks. In this work we focus on using MRFs to model traffic intensity of sensor networks using shortest path routing. Later we propose a probabilistic relaying mechanism to recreate a traffic pattern similar to that observed in a network using shortest path routing. The objective is to emulate the shortest path performance without complex routing protocols and associated overheads. Using a simulation study we then show that the proposed mechanism achieves 95% of the throughput of shortest path, without using a routing protocol.

In this paper, we present a new general framework allowing sensor networks design using random Markov fields (MRF) theory. We explain how the principles underlying MRF theory naturally fit design requirements in sensor networks in particular the need to rely on decentralised and distributed methods to solve global optimisation problems. We illustrate the potential of this new general concept with the practical problems of power control and resource allocation. In addition, we present a new method to improve the convergence rate of the simulated annealing when the sensor network design problem is a constrained optimisation problem.

We describe basic properties of Markov chains on finite state spaces and their application to Green functions, partial differential equations, and their (approximate) solution using random walks on a graph. Attention is paid to the influence of boundary conditions (Dirichlet/von Neumann). We apply these ideas to the study of traffic propagation and distribution in ad hoc networks.

Interferometric synthetic aperture radar (SAR) images suffer from a strong noise, and their regularization is often a prerequisite for successful use of their information. Independently of the unwrapping problem, interferometric phase denoising is a difficult task due to shadows and discontinuities. In this paper, we propose to jointly filter phase and amplitude data in a Markovian framework. The regularization term is expressed by the minimization of the total variation and may combine different information (phase, amplitude, optical data). First, a fast and approximate optimization algorithm for vectorial data is briefly presented. Then, two applications are described. The first one is a direct application of this algorithm for 3-D reconstruction in urban areas with very high resolution images. The second one is an adaptation of this framework to the fusion of SAR and optical data. Results on aerial SAR images are presented.

Synthetic aperture radar (SAR) images, like other coherent imaging modalities, suffer from speckle noise. The presence of this noise makes the automatic interpretation of images a challenging task and noise reduction is often a prerequisite for successful use of classical image processing algorithms. Numerous approaches have been proposed to filter speckle noise. Markov random field (MRF) modelization provides a convenient way to express both data fidelity constraints and desirable properties of the filtered image. In this context, total variation minimization has been extensively used to constrain the oscillations in the regularized image while preserving its edges. Speckle noise follows heavy-tailed distributions, and the MRF formulation leads to a minimization problem involving nonconvex log-likelihood terms. Such a minimization can be performed efficiently by computing minimum cuts on weighted graphs. Due to memory constraints, exact minimization, although theoretically possible, is not achievable on large images required by remote sensing applications. The computational burden of the state-of-the-art algorithm for approximate minimization (namely the alpha -expansion) is too heavy specially when considering joint regularization of several images. We show that a satisfying solution can be reached, in few iterations, by performing a graph-cut-based combinatorial exploration of large trial moves. This algorithm is applied to joint regularization of the amplitude and interferometric phase in urban area SAR images.

This paper investigates the use of a popular regularization model, the total variation minimization (TV), to filter SAR interferometric images (amplitude and phase data). This model is extensively used for its property of preserving edges and is therefore well adapted for urban areas. Using a TV model adapted to multi-dimensional data, we propose to do a joint filtering of phase and amplitude images. Due to the many local minima, the minimization of such a model is hard to perform. A new fast approximate discrete algorithm is presented. The filtering is applied in the framework of 3D reconstruction. Results on real images are presented.

This paper investigates the joint use of interferometric SAR and optical data for 3D reconstruction. A framework for phase filtering constrained by the discontinuities of the optical image is presented. First, both the amplitude and the interferometric phase are projected in a 3D coordinate system. The problem is then expressed as the regularization of the amplitude and phase images with the introduction as prior knowledge of the edges detected on the optical image. We define the regularized elevation in the framework of Markov random fields (MRF) and derive a smoothness prior that both preserves sharp boundaries (based on total variation minimization) and is driven by the structures present in the optical image. We apply a recent graph-cut based algorithm to perform fast regularization of the elevation field. First results on a real pair of optical and InSAR images are presented.

This paper investigates the application of dynamic Bayesian networks (DBNs) to the recognition of degraded characters from historical printed books. This framework allows us to capture the 2D nature of character images by the coupling of two HMMs (Hidden Markov Models). The vertical HMM observes image columns while the horizontal HMM observes image rows respectively. Two coupled DBN architectures are proposed to model interactions between these two streams. We present experiments on real degraded characters extracted from an ancient printed book (17th century). These experiments demonstrate that coupled architectures significantly better cope with broken characters than non coupled ones and than discriminative methods such as SVMs.

This paper deals with SAR data segmentation in an unsupervised way. The model we propose is a combination of the nonstationary triplet Markov field recently introduced and the Fisher distributions. The first one allows modeling the different stationarities present in a given image. The second one has the advantage that is well adapted to this kind of data. We present an original technique based on Iterative Conditional Estimation method, to estimate the parameters of the model we propose. Application examples on simulated data and real SAR images are presented as well.

An iterative filter that can be used for speckle reduction and restoration of synthetic aperture radar (SAR) images is presented here. This method can be considered as a first step in the extraction of other important information. The second step is the detection of high-reflectance regions and continues with the segmentation of the total image. We have worked in three-look simulated and real European Remote Sensing 1 satellite amplitude images. The iterative filter is based on a membrane model Markov random field approximation optimized by a synchronous local iterative method. The final form of restoration gives a total sum-preserving regularization for the pixel values of our image. The high-reflectance regions are defined as the brightest regions of the restored image. After the separation of this extreme class, we give a fast segmentation method using the histogram of the restored image.

Due to the enormous quantity of radar images acquired by satellites and through shuttle missions, there is an evident need for efficient automatic analysis tools. This paper describes unsupervised classification of radar images in the framework of hidden Markov models and generalized mixture estimation. Hidden Markov chain models, applied to a Hilbert-Peano scan of the image, constitute a fast and robust alternative to hidden Markov random field models for spatial regularization of image analysis problems, even though the latter provide a finer and more intuitive modeling of spatial relationships. We here compare the two approaches and show that they can be combined in a way that conserves their respective advantages. We also describe how the distribution families and parameters of classes with constant or textured radar reflectivity can be determined through generalized mixture estimation. Sample results obtained on real and simulated radar images are presented.

An extension of the multi-band model including inter-band control of time asynchrony is described. It is based on the framework of Markov random fields. The law of the speech process is given by a parametric Gibbs distribution and a maximum likelihood parameter estimation algorithm is developed. This random field model is applied to isolated word recognition. It is shown that similar performances are obtained with the new model and with standard HMM techniques in the mono-band case. In the multi-band case, it is shown that the recognition rate decreases when the number of bands is increased but that modeling inter-band synchrony limits the performance decrease.

This paper presents a new definition of a spatial entropy mainly based on the Markov random field (MRF) properties. Starting with the study of the entropy proposed by Volden, Giraudon and Berthod (1995) for the Potts model, we establish a specific property of the entropy in this special case, and derive the analytical expressions for a 4-connexity neighborhood. Inspired by the previous property, we propose a new definition mainly based on an heterogeneity measure of the neighborhood. This definition is then used to analyze a SAR (synthetic aperture radar) image and it is shown to be able to discriminate different types of textures.

Speech can be represented as a time/frequency distribution of energy using a multiband filter bank. A Markov random field model, which takes into account the possible time asynchrony across the bands, is estimated for each segmental units to be recognized. The law of the speech process is given by a parametric Gibbs distribution and a maximum likelihood parameter estimation algorithm is developed. Experiments are conducted on an isolated word recognition problem. It is shown that similar performances are obtained with the new model and with standard HMM techniques in the mono-band case. In the multiband case, it is shown that modeling interband synchrony is an interesting approach to increase the performance when the number of bands increases.

In this paper, we tackle the problem of estimating textural parameters. We do not consider the problem of texture synthesis, but the problem of extracting textural features for tasks such as image segmentation. We take into account nonstationarities occurring in the local mean. We focus on Gaussian Markov random fields for which two estimation methods are proposed, and applied in a nonstationary framework. The first one consists of extracting conditional probabilities and performing a least square approximation. This method is applied to a nonstationary framework, dealing with the piecewise constant local mean. This framework is adapted to practical tasks when discriminating several textures on a single image. The blurring effect affecting edges between two different textures is thus reduced. The second proposed method is based on renormalization theory. Statistics involved only concern variances of Gaussian laws, leading to Cramer-Rao estimators. This method is thus especially robust with respect to the size of sampling. Moreover, nonstationarities of the local mean do not affect results. We then demonstrate that the estimated parameters allow texture discrimination for remote sensing data. The first proposed estimation method is applied to extract urban areas from SPOT images. Since discontinuities of the local mean are taken into account, we obtain an accurate urban areas delineation. Finally, we apply the renormalization based on method to segment ice in polar regions from AVHRR data.

In this paper, we present a new technique for statistical modeling of speech segments based on Markov random fields. Classical and multi-stream HMMs are particular cases of this more general family of models. However, the Random Field Model (RFM) proposed here can be seen as an extension of the multiband HMM in which interactions between the frequency bands have been added. In a first experiment, samples are drawn from different models and compared to real observations. This experiment shows that the RFM is able to produce realistic samples but a single HMM still performs better. Isolated word recognition experiments stress the fact that more work must be done on the RFM in order to reach the performances of classical hidden Markov modeling techniques. For the moment, the RFM parameters are estimated using a heuristic. We believe that a real maximum likelihood parameter estimation algorithm should improve the results. The main advantage of this new model is that it can easily be extended since a model is defined by some local interactions and the Gibbs potential functions associated to those interactions. 1

A new kind of entropy is proposed, which associates spatial and radiometric properties of images. The possible use of this entropy is shown firstly to measure the effect of picture processing algorithms, then to control the evolution of iterative contextual classification algorithms like Markov random fields.>

A three-dimensional (3D) reconstruction of the vessel lumen from two angiographic views, based on the reconstruction of a series of cross-sections, is proposed. Assuming uniform mixing of contrast medium and background subtraction, the cross-section of each vessel is reconstructed through a binary representation. A priori information about both the slice to be reconstructed and the relationships between adjacent slices are incorporated to lessen ambiguities on the reconstruction. Taking into account the knowledge of normal vessel geometry, an initial solution of each slice is created using an elliptic model-based method. This initial solution is then deformed to be made consistent with projection data while being constrained into a connected realistic shape. For that purpose, properties on the expected optimal solution are described through a Markov random field. To find an optimal solution, a specific optimization algorithm based on simulated annealing is used. The method performs well both on single vessels and on branching vessels possessing an additional inherent ambiguity when viewed at oblique angles. Results on 2D slice independent reconstruction and 3D reconstruction of a stack of spatially continuous 2D slices are presented for single vessels and bifurcations.