Francisco Sanchez-Fernandez
email: francisco.sanchez-fernandez@u-bourgogne.fr

Philippe Brunet
email: philippe.brunet@u-bourgogne.fr

Sidi-Mohammed Senouci
email: sidi-mohammed.senouci@u-bourgogne.fr

Background subtraction for aerial surveillance conditions

Keywords: Image processing, unmanned aerial vehicle, background modelling, background subtraction, mobile observer, moving objects

diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

I. INTRODUCTION

Visual surveillance has become an important task in the last years. Its main objective is to find changes over time in a sequence of images. Motion-related changes are most important but this task is linked with other higher-level tasks such as localization, identification and tracking of moving objects. Therefore, detecting changes is considered as a key-preprocessing step of videos. Activities in which visual surveillance is used includes protection of strategic facilities, pedestrian detection, analysis of suspicious behavior, etc.

When we analyze a sequence of images used in surveillance, we can always observe two main features. The first feature refers to a part of the image that remains temporarily constant, i.e. does not suffer any change unless sensor by which image is acquired, it is moved intentionally or not. The second feature is about absolute majority formed by intensity of certain pixels, above characteristics describe an important part in image processing called background of an image.

Background modelling or subtraction (BS) is an important component in a video surveillance system because it helps to distinguish moving or incoming objects in a sequence of images. The main objective of BS algorithms is to classify all moving objects as foreground and then identify interesting areas of an image for further analysis. The simplest case for BS is assuming a fixed camera [START_REF] Elgammal | Background and foreground modeling using nonparametric kernel density estimation for visual surveillance[END_REF][2][3] [START_REF] Neri | Automatic moving object and background separation[END_REF], however, this assumption rigorously limits the implementation of other computer vision algorithms. Nowadays, a lot of imagery sequences are done by platforms incorporating a mobile camera, like cellular phones, robots and unmanned aerial vehicles (UAVs). Therefore, it exists an increasingly need to develop algorithms to separate foreground objects from background using moving cameras for different tasks.

In any kind of images, there are many changes that happen over time and affect the performance of background modelling. It is vital for background model to be capable to efficiently handle changes. Above can be achieved by being invariant or by adapting to changes. These can be local, small persisting moving objects belonging to images like waving trees [START_REF] Bhutta | Selective subtraction when the scene cannot be learned[END_REF] [START_REF] Zhong | Multl-resolution background subtraction for dynamic scenes[END_REF], or global, like illumination changes or camera motion [START_REF] Yang | An Effective Background Subtraction under a Continuosly and Rapidly Varying Illumination[END_REF] [START_REF] Cheng | Illumination-Sensitive Background Modeling Approach for Accurate Moving Object Detection[END_REF]. Spatial and temporal information of pixels are two fundamental elements to understand background structure and these should complement each other to obtain a robust background model [START_REF] Zhao | Background modeling by subspace learning on spatio-temporal patches[END_REF].

In this paper, we propose a new background subtraction method designed to deal with particular conditions of aerial images. Our method is capable to deal with motion of UAV to extract background information. We use spatial and temporal information to classify pixels between foreground and background. We used an adaptive method focused to weight spatial or temporal information depending if motion of UAV is smooth or not. Experimental results of sequences under different conditions demonstrate robustness of the proposed method. Evaluation and comparison with existing methods show that our proposed method provides same results in motionless sequences and improved performance when sequences are unstable (camera motion).

The rest of this work is organized as follows: Section 2 presents a review of several methods for background modelling. Formulation and description of the proposed approach is presented in Section 3. Section 4 describes evaluation method and features of each dataset. The discussion of results and conclusions are made in Section 5.

II. RELATED WORK

A big number of BS methods have been proposed in recent years, trying to retrieve a background model using different approaches. Basically, classification is divided into two types of algorithms [START_REF] Hedayati | Real-time background subtraction for video surveillance: From research to reality[END_REF] parametric and non-parametric models. Parametric models represent a probability density function (pdf) parametrically. It uses a specific statistical distribution and its associated parameters, based on previous known distributions [START_REF] Ngo | Realtime video surveillance on an embedded, programmable platform[END_REF]. In a different way, a non-parametric model does not need to fit data to a specific distribution, the pdf is directly estimated and thus avoids calculating all parameters related to a specific distribution. Sections below provide some works for each class.

A. Parametric background models

Many BS algorithms for fixed cameras work by comparing color or intensities of pixels amongst an incoming image and a reference. The first approaches of BS used frame difference [12][13] between two consecutives images, where major differences in intensity from the reference image were related to moving objects. Thresholding is applied to obtain background model. However, the background obtained through this approach is not suitable in some sequences with abrupt changes of illumination or motion related.

The basic statistical method for background modelling consists in representing the color intensity at each pixel by a single Gaussian distribution. The Gaussian mixture model (GMM) [START_REF] Hedayati | Real-time background subtraction for video surveillance: From research to reality[END_REF] is probably the most popular statistical technique for background modelling. Stauffer and Grimson [START_REF] Stauffer | Adaptive background mixture models for real-time tracking[END_REF] proposed a broad view to the single Gaussian approach, by using an adaptive multiple Gaussians method that model the pixel color as a mixture of Gaussians [START_REF] Hayman | Statistical background subtraction for a mobile observer[END_REF][16] [START_REF] Shimada | Dynamic Control of Adaptive Mixture-of-Gaussians Background Model[END_REF]. The model is constructed as follows:

( 1 )

The intensity of a pixel is modeled by a mixture of K Gaussian distributions (Typically, K is around 3 to 5). Every new pixel is checked against existing K Gaussians (η), if difference between pixel and Gaussian is less than 2.5σ, the weight for that distribution is updated. Several modifications to original model has been proposed to GMM model, e.g. [18][19][20] etc.

B. Non parametric background models

The main reference for non-parametric models is kernel density estimation (KDE) and proposed by [START_REF] Elgammal | Background and foreground modeling using nonparametric kernel density estimation for visual surveillance[END_REF] [START_REF] Elgammal | Non-parametric model for background subtraction[END_REF]. Given a data sample with a specific pdf , an approximation is found with (2).

(

)

Where is a kernel function, centered at data points in sample space and uniformly weighted. Kernel density estimators have main property of asymptotically converge to any probability density function, this property is used to model background.

The kernel can be chosen from a wide range but typically a Gaussian kernel [START_REF] Parag | A Framework for Feature Selection for Background Subtraction[END_REF][23] is used for its continuity, differentiability, and locale properties. Differentiate between choosing the Gaussian as a kernel function and fitting the distribution to a Gaussian model is a critical part to understand non parametric models [START_REF] Elgammal | Non-parametric model for background subtraction[END_REF], KDE uses Gaussian only as a function to weight the data points and does not makes assumptions about shape of density function. In conclusion, a pixel is considered a background pixel if

, where ε is a global threshold that is equal to whole image and can be adjusted to obtain a desired proportion of false positives [START_REF] Mubarak | Bayesian modeling of dynamic scenes for object detection[END_REF] [START_REF] Sheikh | Background Subtraction for Freely Moving Cameras[END_REF].

The key motivation for using non parametric density estimation for background modeling lies on robustness presented at outdoor scenarios. This kind of scenarios always contains various disturbances [START_REF] Mittal | Motion-based background subtraction using adaptive kernel density estimation[END_REF] such as ocean waves, waving trees, rain, moving clouds, etc. Modeling such persistent motion requires a more flexible representation of the background probability distribution at each pixel. Since non parametric models are not based on a specific distribution, these can be updated according to characteristics of each image.

III. ADAPTIVE BACKGROUND SUBTRACTION SOLUTION DESCRIPTION

Typical background subtraction techniques are inefficient on images taken from a mobile observer due to low temporal consistency of most pixels. We propose a combination of temporal and spatial information. The workflow of the proposed method is depicted in Fig. 1. The first part of our algorithm consists to do a basic approximation of background model using an adaptive method proposed by [START_REF] Zhang | Moving vehicles detection based on adaptive motion histogram[END_REF]. However, this model still includes outliers, which will be eliminated with further processing.

In a motionless sequence, the frame difference represents the easiest way to find all objects that move and are not part of the background model. So, we first identify all pixels that are not the same between two consecutive images, i.e. estimate the absolute difference between a past frame and an nth frame and then threshold to obtain a frame difference mask as follows:

( 3 )

Frame difference mask is a binary image, where pixels that correspond to moving objects have the value 1, and remaining pixels are set to 0.

To prevent temporal variation on pixels generated by camera motion, the age of each pixel is used. Age refers to how many frames a pixel remains constant, we can infer that a pixel with a greater age has high probability to belong to the background model. Proposed method establish an upper limit of pixel age to eliminate excessive data storage. When a pixel reaches this limit, its age remains constant. Matrix containing the age of pixels is calculated according to (4) for each pair of consecutive images.

( 4 )

Then, we estimate the gradient direction of as follows:

( 5 )

The gradient direction provides reliable information about moving objects. First, the areas of image with the maximum possible age have same direction because each point in this area represents a local maximum (its direction is equal to zero). The gradient directions of moving pixels due camera motion, also have same direction because all pixels move in the same way and represent a significant quantity of the distribution of directions. Therefore, gradient directions of moving objects are minority because each one has its own direction. Thresholding sorted histogram of gradient directions, we can separate pixels with predominant gradient directions, which belong to the background. Gradient direction mask is computed as follows:

( 6 )
The background image is subtracted from the current image to obtain another representation of moving objects in the sequence. Background subtraction mask is formed as shown in [START_REF] Yang | An Effective Background Subtraction under a Continuosly and Rapidly Varying Illumination[END_REF]. [START_REF] Yang | An Effective Background Subtraction under a Continuosly and Rapidly Varying Illumination[END_REF] Finally, a function to decide which image to sample is required to update background model. Frame difference mask and background subtraction mask can perfectly describe background model when camera is static, otherwise, model still has outliers. Hence we add gradient direction mask to strengthen our sampling function shown in [START_REF] Cheng | Illumination-Sensitive Background Modeling Approach for Accurate Moving Object Detection[END_REF]. We apply OR function because gradient direction mask also contains common areas with the other masks, especially those motionless.

( 8 )

The thresholds used in ( 3), ( 6) and ( 7) are calculated according to thresholding method in [START_REF] Otsu | A Threshold Selection Method from Gray-Level Histograms[END_REF], it is used to split a histogram into two classes and minimize variance of data at each class.

To update the background model, we need to calculate an instantaneous background using the motion mask. A position where motion mask is 1, indicates that this pixel is part of a moving object then we sample last version of background model. Conversely, when motion mask is 0, current frame is sampled to keep model correctly updated. Updating rules above mentioned are shown in [START_REF] Zhao | Background modeling by subspace learning on spatio-temporal patches[END_REF].

( 9 )

The background model is a weighted average between instantaneous background and previous version of background model as follows: [START_REF] Hedayati | Real-time background subtraction for video surveillance: From research to reality[END_REF] Weight used in [START_REF] Hedayati | Real-time background subtraction for video surveillance: From research to reality[END_REF] is estimated using an adaptive approach.

If an image has high rate of static pixels, it means that we can prioritize instantaneous background and build model from it. Otherwise, the priority is the model that was built with previous versions. We should find the number of static pixels using the gradient direction mask, this is illustrated in [START_REF] Ngo | Realtime video surveillance on an embedded, programmable platform[END_REF] and [START_REF] Jain | Separating non-stationary from stationary scene components in a sequence of real world TV-images[END_REF].

( 11 ) [START_REF] Jain | Separating non-stationary from stationary scene components in a sequence of real world TV-images[END_REF] The parameter α is set in a smooth manner to mitigate e.g. influence of an abrupt camera motion or light changes. Weight update is done as follows:

( 13 )

IV. EXPERIMENTAL RESULTS

We have tested the proposed method on several scenarios involving similar conditions in aerial images acquisition, including unintentional and intentional motion of camera. The proposed method is implemented using MATLAB software on an Intel Core i5 PC with 8 GB RAM.

The evaluation is done using dataset provided by [START_REF] Goyette | Changedetection.net: A new change detection benchmark dataset[END_REF], this dataset provides a realistic and diverse set of videos, including a wide range of detection challenges. We chose three categories to evaluate our algorithm since these categories represent various conditions that affect performance of the background subtraction algorithms in the aerial images. Baseline category has videos with subtle background motion, which can represent when a static UAV is acquiring images. In this category, background subtraction is easy to apply but not trivial, its main purpose is to serve as a reference. Camera jitter category is formed by sequences taken from a sensor affected by unintentional motion like climatological conditions and vibrations of vehicle. Motionless images are important in BS algorithms to avoid detection of fixed objects caused by unintentional motion of the camera. Lastly, PTZ category contains videos captured by pan-tiltzoom cameras, which are commonly used for surveillance tasks. Images acquired from a PTZ camera can be represented as intentional motion of UAV, these sequences are challenging because motion must be removed to reduce misclassification of pixels. We compare our method against two commonly used methods, the Gaussian mixture model (GMM) [START_REF] Stauffer | Adaptive background mixture models for real-time tracking[END_REF] and kernel density estimation(KDE) [START_REF] Elgammal | Background and foreground modeling using nonparametric kernel density estimation for visual surveillance[END_REF]. To evaluate performance of methods, we compute precision of each method as follows: [START_REF] Stauffer | Adaptive background mixture models for real-time tracking[END_REF] Where:

True positives: number of pixels that are correctly detected as background;

False positives: number of pixels that are wrongly detected as background.

To obtain true and false positives, results of each method are compared to ground truth, i.e. correct classification result. The ground truth is also provided with each sequence in the dataset. We test all methods in 6 different sequences, 2 sequences for each category aforementioned. The precision of each sequence are showed in Fig. 2. The sequences "office" and "highway" are part of baseline category, which represent the simplest case for BS. In these sequences we obtained highest results. All methods show similar performances due to their constant background with subtle motion; results of this category are shown in Fig. 3. The sequences "zoomInZoomOut" and "intermittentPan" show low temporal consistency between consecutives images because the pictures are taken by a PTZ camera, which is constantly panning and zooming. However, proposed method outperforms the GMM and KDE significantly in all two sequences, BS results are given in Fig. 4. Finally, in Fig. 5, sequences "boulevard" and "traffic" affected with camera jitter, show similar precision than previous sequences.

V. CONCLUSIONS

This work presents a novel method for background modelling with an adaptive update algorithm. Three types of information are fused to obtain a robust background model. The proposed method models variations according to age of pixels, i.e. we used those pixels with low variability over time. We tested our proposed method in different sequences simulating aerial imagery conditions and from experimental results better performance than GMM and KDE algorithms in changing images is observed. Shadow removal can be considered as future work to increase performance of proposed algorithm, since in current evaluation, pixels that are part of shadows are considered false positives and this affects performance evaluation.

Figure 1 .

 1 Figure 1. Framework of the proposed method.

Figure 2 .

 2 Figure 2. Precision of our proposed method, GMM and KDE for all sequences.

Figure 3 .

 3 Figure 3. Results of baseline sequences "office" and "highway ": (a) original image, (b) ground truth, (c) proposed method, (d) GMM, (e) KDE.

Figure 4 .

 4 Figure 4. Results of moving sequences "zoomInZoomOut" and "intermittentPan" (a) original image, (b) ground truth, (c) proposed method, (d) GMM, (e) KDE.

Figure 5 .

 5 Figure 5. Results of unstable sequences "Boulevard" and "traffic": (a) original image, (b) ground truth, (c) proposed method, (d) GMM, (e) KDE.

ACKNOWLEDGMENT

The authors would like to thank University of Burgundy for support this research. We also are very grateful to chagedetection.net [29] for providing dataset used to evaluate this work.


Mohamed Ayoub Messous

Hermann Hellwagner
email: hermann.hellwagner@aau.at

Sidi-Mohammed Senouci
email: sidi-mohammed.senouci@u-bourgogne.fr

Driton Emini

Dominik Schnieders
email: dominik.schnieders@telekom.de

Edge Computing for Visual Navigation and Mapping in a UAV Network

Keywords: UAV Network, Edge Computing, Computation Offloading, Visual Navigation and Mapping

This research work presents conceptual considerations and quantitative evaluations into how integrating computation offloading to edge computing servers would offer a paradigm shift for an effective deployment of autonomous drones. The specific mission that has been considered is collaborative autonomous navigation and mapping in a 3D environment of a small drone network. Specifically, in order to achieve this mission, each drone is required to compute a low latency, highly compute intensive task in a timely manner. The proposed model decides for each task, while considering the impact on performance and mission requirements, whether to (i) compute locally, (ii) offload to the edge server, or (iii) to the ground station. Extensive simulation work was performed to assess the effectiveness of the proposed scheme compared to other models.

I. INTRODUCTION

Unmanned aerial vehicles (UAVs), also commonly named drones, have proliferated extremely fast and continue to have far-reaching effects on today's society, transforming our lives and the way we do business. While big UAV platforms have been initially introduced for strategic and defense applications, relatively small and very flexible new UAV platforms are proving to be very useful for a wide variety of applications such as disaster damage assessment, law enforcement surveillance, and earth science data collection [START_REF] Ma | Using unmanned aerial vehicle for remote sensing application[END_REF][START_REF] Messous | Implementing an emerging mobility model for a fleet of UAVs based on a fuzzy logic inference system[END_REF][START_REF] Messous | Network connectivity and area coverage for UAV fleet mobility model with energy constraint[END_REF][START_REF] Hossein Motlagh | Low-Altitude Unmanned Aerial Vehicles-Based Internet of Things Services: Comprehensive Survey and Future Perspectives[END_REF]. In order to accomplish their missions, UAVs are required to (i) collect data about their environment, (ii) compute and process the collected data for decision making, and (iii) relay specific information to their appropriate users [START_REF] Pajares | Overview and Current Status of Remote Sensing Applications Based on Unmanned Aerial Vehicles (UAVs)[END_REF][START_REF] Oubbati | A survey on position-based routing protocols for Flying Ad hoc Networks (FANETs)[END_REF]. To achieve these three basic requirements, depending of their mission, UAV platforms are equipped with different types of sensors, onboard computing capabilities and dedicated wireless communication interfaces. This would be essential for effective special awareness, realization of locally distributed processing along the communication path where applicable, and finally, for the dissemination of relevant information from producers to consumers while maintaining reliable and efficient air-to-air (UAV-to-UAV) and air-toground (UAV-to-ground station) communications [START_REF] Liu | Space-Air-Ground Integrated Network: A Survey[END_REF].

In this research work, we choose to focus on a specific mission where a small fleet of drones is deployed in order to achieve a collaborative autonomous 3D navigation and reconstruction task [START_REF] Ravankar | Autonomous Mapping and Exploration with Unmanned Aerial Vehicles Using Low Cost Sensors[END_REF][START_REF] Wang | Towards Real-time 3D Reconstruction using Consumer UAVs[END_REF]. More precisely, using only inertial information, taken from IMU readings, and visual information, through captured imagery, the drones will be required to collectively map and efficiently navigate in an unknown 3D environment [START_REF] Lu | A survey on vision-based UAV navigation[END_REF]. Technically, a process called visual inertial odometry is used [START_REF] Zhu | Event-Based Visual Inertial Odometry[END_REF]. Similar to other visionbased localization and navigation methods, this process is prone to drift errors while estimating positions and attitudes of drones due to non-perfect sensory reading [START_REF] Suleiman | Navion: A Fully Integrated Energy-Efficient Visual-Inertial Odometry Accelerator for Autonomous Navigation of Nano Drones[END_REF][START_REF] Suleiman | Navion: A 2-mW Fully Integrated Real-Time Visual-Inertial Odometry Accelerator for Autonomous Navigation of Nano Drones[END_REF]. These drift errors would eventually build up, resulting in degrading flight and mapping accuracy. IMU data readings at a 1 kHz rate and image capturing at 30 images per seconds (30 Hz) would be ideal to keep drift errors as small as possible. However, the constrained computation and limited communication capabilities of drones would not allow such high sampling rates since the preprocessing and fusion of the sensor data in general and the image processing tasks in particular are computationally intensive.

To address issues related to highly intensive computation tasks with low latency requirements, many previous research studies have resorted to computation offloading to powerful surrogate devices such as mobile edge computing (MEC). This newly emerging computation paradigm extends the capabilities of cloud servers to the edge of an access network. It provides computational power and data storage closer to the end users. Therefore, it can reduce traffic loads for central cloud servers, decrease latency, and improve QoS. Moreover, it supports users' mobility and heterogeneity, provides location awareness, and permits high deployment scalability. MEC is perceived as one of the central building blocks for 5G networks [START_REF] Parvez | A Survey on Low Latency Towards 5G: RAN, Core Network and Caching Solutions[END_REF][START_REF] Zheng | Stochastic Computation Offloading and Scheduling Based on Mobile Edge Computing[END_REF]. For drone networks, the effective deployment of MEC, on the one hand, holds the promise of a high-throughput communication fabric, and on the other hand, is expected to enable low-latency capabilities and to perform specific computational services for the client devices [START_REF] Messous | A Game Theory Based Efficient Computation Offloading in an UAV Network[END_REF][START_REF] Zhang | Stochastic Computation Offloading and Trajectory Scheduling for UAV-Assisted Mobile Edge Computing[END_REF][START_REF] Bai | Energy-Efficient Computation Offloading for Secure UAV-Edge-Computing Systems[END_REF][START_REF] Messous | A Sequential Game Approach for Computation-Offloading in an UAV Network[END_REF][START_REF] Messous | Computation Offloading Game for an UAV Network in Mobile Edge Computing[END_REF]. In our case, drones would consider the offloading of some or all of the computational tasks involved in visual inertial odometry to an edge server. Indeed, MEC can not only bring performance benefits for heavy computational tasks, it can also act as a centralized entity for the nearby deployed swarm of drones. Moreover, the MEC servers deployed at the edge of the access network would help control the drones more accurately compared to decentralized control. They would even be expected to play an important role in synchronizing and ensuring the consistency of the mapping tasks.

The main focus of the current study is to investigate how MEC can conceptually be integrated into a specific mission using a drone network, while evaluating the impact of computation offloading on the flight accuracy and the possible performance benefits of deploying an MEC-based scheme. The specific mission considered is the visual-inertial navigation and 3D mapping in an unknown remote environment. In order to tackle these challenges, the proposed solution aims to decide whether a computational task needs to be offloaded to be executed remotely or not.

The remainder of this paper is organized as follows. In Section II, we present the system model and the mathematical formulation of our problem. Section III gives the details about the main computation offloading schemes. The simulation work and the results obtained are presented and discussed in Section IV. Finally, Section V concludes the paper and gives some future directions.

II. SYSTEM MODEL AND PROBLEM FORMULATION

The system model, shown in Fig. 1, is composed of three main entities: (i) drones, (ii) edge server, and (iii) ground station. In the following subsections, we first present the mission requirements and justify our hypothesis. Then, we provide the problem formulation while explaining in detail the different possible computational use case scenarios.

A. Mission Requirements and Scenario Definition

We consider a set of small UAVs deployed in an unknown environment in order to execute a 3D mapping of their environment. Specifically, we consider as a main mission the collaborative autonomous 3D navigation and reconstruction application through a small network of drones, using inertial information (IMU data) and visual information (captured images) only (no GNSS information). The drones will reconstruct (map) an unknown 3D environment and navigate in that space. In order to perform such kind of mission, the UAVs are equipped with an onboard camera for visual imagery and also an inertial measurement unit (IMU) that provides basic information about their spatial orientation. We also consider for our use case scenario that the drones in this mission do not have access to GNSS positioning data. The lack of such information can be explained by the poor quality of GNSS signal or its absence altogether (in indoor environment) or due to problems related to precision (in a city district with a very dense building constellation).

In such a context, the drones are required to perform a process named visual inertial odometry (VIO) in order to achieve their mission. Similar to other vision-based localization and navigation methods, this process is prone to drift errors in estimating positions and attitudes of drones in case of non-perfect sensor data; these drift errors will result in degrading flight and mapping accuracy. IMU data readings at a 1 kHz rate and image capturing at 30 images per seconds (30 Hz) would be ideal to keep drift errors as small as possible. However, the constrained computation and communication capabilities of small drones would not be able to handle such high sampling rates since the processing and fusion of the sensor data in general and the image processing tasks in particular are highly compute intensive. Due to these limitations, computation offloading from the drones to an edge server would offer a viable solution.

Computational tasks involved in VIO can be fully or partially offloaded from the drones to an edge server. On the one hand, MEC would achieve better performance compared to local computing. On the other hand, an edge server would eventually act as a nearby deployed central entity for its associated drones, which would allow for an even more accurate control compared to a fully decentralized scheme, and would also ultimately perform the synchronization and mapping tasks more consistently.

B. Computational Models

As previously shown, the kind of missions considered involves performing highly intensive computation tasks. Each task Ti is defined through three basic parameters {Ci, Di, Fi} representing computational complexity, size of data and execution frequency, respectively. The first value Ci corresponds to the number of CPU cycles required to perform the task Ti. Di specifies the amount of data needed for the computation. Finally, Fi denotes the execution rate, i.e., how many times the task Ti is called upon per time unit.

Furthermore, the defined tasks can be either executed locally in the drone itself or can be eventually fully or partially offloaded to a surrogate, more powerful device if required. In the present study two offloading choices are possible: (i) through a cellular network towards an edge server, or (ii) through a WLAN access towards a nearby ground station. Therefore, three possible choices can be enumerated, namely: (i) local computing, (ii) offloading to edge, and (iii) offloading to ground station. Details for each use case are provided in the following paragraphs.

1) Local Computing

Since computation tasks in this case are executed locally, no actual data ought to be sent via wireless interfaces. Therefore, the overhead of the task is equal to local computation overhead. The latter would only be impacted by the onboard computation power available in the device, i.e., the CPU frequency of the drones which is the number of computation cycles per time unit. So, the execution time for a task Ti if the local CPU frequency is F Local CPU is given as:

TLocal =Ci/F Local CPU ( 1 )

2) Offloading to Edge

In this second case, the drone would send its computation task via its cellular interface towards the edge server. Compared to the previous option, the delay required to obtain results for the task being executed, in addition to the computation time, will incur an extra overhead. This is due to the additional time necessary to transmit data up to the edge server. Therefore, the equation for the execution time is:

TServer=Ci/F Server CPU+Di/RCellular ( 2 ) where F Server CPU represents the frequency of the server CPU, which in practice is very big compared to the frequency of the mobile devices' CPUs, and RCellular is the effective data rate achieved through the cellular link between the drone and the edge server.

3) Offloading to Ground Station

This second offloading choice, and third possible case, considers sending the computational data through a wireless access point to a neighboring ground station. The latter would compute the received task and send back results to the originating drone. In this case, the equation for the execution time is given as:

TGS=Ci/F GS CPU+Di/RWLAN ( 3 )
where F GS CPU denotes the CPU's frequency of the ground station and RWLAN is the effective data rate achieved through the wireless local network.

C. Overhead Function

Since computationally intensive tasks are known to necessitate a considerable amount of time to complete their execution, we define the overhead function as the combination of time delays required for data transfer and for data processing. Both, the communication links' effective data rates and the available processors' frequencies will play a significant role in choosing the more suitable computation choice as shown previously. Therefore, it is important to define and implement an appropriate utility function that considers the best possible tradeoff between these two competing parameters. The following equation shows the different parameters required to calculate the overall values for the overhead function for each task.

ൌࢻσ ୀ ࢼσ ୀ (4)
where N is the number of computation sub-tasks required to compute the global task;

represents the execution time (computational overhead) required for processing each sub-task i; M characterizes the number of communication exchanges required; and stands for time delay (communication overhead) to transfer/receive each message j. Additionally, Į and ȕ represent weight parameters of computational and communication delays, respectively, and Į+ȕ =1.

Moreover, no normalization method was required in order to add these two different values since both represent time measurements. Furthermore, using a weighted function provides a much higher flexibility and answers a wide range of applications with specific requirements. Specifically, depending on the envisioned application or even the current system status, different tasks might use different weight parameters. For instance, if the system administrator wishes to put more emphasis on the computational delay part, he or she would give higher values for the weight Į, whereas ȕ would be increased in order to highlight the importance of communication delay.

III. OFFLOADING COMPUTATION FOR VISUAL NAVIGATION

We provide herewith details regarding our implementation for possible choices of computation offloading in a visual navigation mission. Besides the classical approach, where all the computation is executed locally, we consider different task splitting possibilities. Furthermore, each global task can be divided into several elementary sub-tasks. There is always some computation that needs to be treated locally using the embedded processors. Typically, this process might involve the following operation: (i) collecting raw data from different onboard sensors, (ii) compression of raw data into a standard data format, (iii) aggregation of similar data within the same vector, and (iv) multi-sensor fusion. Parts of these low-level operations need to be executed locally and would not be suitable for offloading. However, other high-level operations can be offloaded, especially those including intensive computation routines. Figure 2 provides two examples for a partial-offloading and a full-offloading scenario. Details for each model are given in the following subsections.

A. Partial Offloading

In this first case, a first part of the collected data is computed locally before sending the results of execution along with specific information for further treatment in the edge server. As shown in Fig. 2(a), the partial offloading scheme starts with a locally executed task T1, then data are sent from the drone to the edge server through the communication link, denoted as communication step C1. Then, when all the required data are received, the edge server executes task T2 which ends with communicating results back to the drone (C2). Meanwhile, other local treatment would continue to be executed on the drone, which is denoted in Fig. 2(a) as task T3. Finally, when C2 is completed, local processing can be resumed in T4 taking into account the newly received data.

For the requirements of our use case scenario, the detailed execution routines for the different tasks are given in the following. First, task T1 involves (i) IMU data reading, (ii) attitude and acceleration deduction, and (iii) IMU data preintegration. T3 repeats the same instructions as in T1 but adds at the end of each cycle a "new pose estimation" routine. Data transferred in C1 encompasses: (i) the latest key frame image and (ii) up-to-date IMU data. The data sent in C1 will serve as input for T3, where the following operations are executed: (i) feature detection, (ii) feature tracking, and (iii) pose estimation and optimization. C2 will incorporate data about the newly estimated pose. Finally, the drone would

B. Full Offloading

This second case considers that only essential computation, which cannot be offloaded to edge, would be treated locally onboard the drone. All the other actions would be executed remotely on the edge server, then results are sent back to the drone as shown in Fig. 2(b). The details for each elementary action are provided as follows. T1' includes sensor data reading and compression. Only basic computation is achieved before sending gathered data in C1'. This step encompasses offloading a continuous flow of images taken by the onboard camera and inertial readings from the IMU. The edge server will do all the computations required for the mission in T2' before sending back the new commands and instructions for the drone to follow in C2'. Finally, T3' represents the control commands and updating the local pose estimate graph for the drone.

IV. PERFORMANCE EVALUATION

Extensive simulation work has been done to evaluate the effectiveness of the proposed computation offloading scheme. In this section, the detailed assumptions regarding simulation work and scenario definition are first introduced. Then, numerical results are presented followed by thorough discussions to validate the feasibility and effectiveness of an edge-based solution for visual navigation missioned by a small set of drones.

A. Simulation Setup

In the simulation scenarios, we consider a single cell consisting of a base station (plus edge server) and a small number of drones (between 1 and 10) which also have access to a ground station (GS) via WLAN. The computation tasks considered for visual navigation differ in their computation complexity and also in their size of data required for effective computation. On the one hand, computation complexity is mainly affected by the number of features considered and the type of algorithm used for feature extraction. Since the main focus of the current study is the computation offloading problem and optimized decision making, only the number of features has been considered in representing computational complexity for different tasks. On the other hand, data that would need to be offloaded comes from imagery sensors and the IMU. However, practical estimation shows that data size required for IMU readings are negligible compared to image resolution, even with very high IMU reading rates. For simplicity, as shown in Table 1, three complexity levels are tested (between 50 and 200 features to extract from an image) with three different image resolutions (360p, 480p and 720p). Finally, in order to assess the possible offloading choices explained in Sect. III, different offloading rates have been implemented: ranging from local computing (0%) to full offloading (100%), along with three intermediary offloading rates (25%, 50% and 75%). Furthermore, beside the edge server a second surrogate device, namely the ground station, is considered as a second possible destination choice for offloading computation through a WLAN link (Fig. 1). To evaluate each model, we consider the global utility function presented in Sect. II.C. Furthermore, we give an equal importance to computation and communication delays, i.e., we choose Į = ȕ = ½. For a detailed study of the impact that number of UAVs, number of features and image resolution might have on the overall utility, all the different possible combinations have been considered and tested. Other parameters used in our simulation setup are summarized in Table II. For the sake of simplicity, we consider the processing power of the ground station (F GS CPU)

and the edge server (F Edge CPU) to be respectively five and ten times the frequency of CPU available onboard the drone (F Local CPU). As for achievable data rates, the average data rates for wireless links with the ground station and with the edge server (R WLAN and R Cellular) are 50 and 20 Mbps, respectively.

B. Results and Discussion

In this subsection, we first evaluate the global average overhead achieved by the proposed approach compared to the three other models. The diagram shown in Fig. 3 represents the average system-wide overhead achieved through: (i) locally executed tasks, (ii) fully offloaded tasks to the edge, (iii) fully offloaded tasks to the ground station, and (iv) the optimal choice, which uses equation (4) as a premise for Fig. 3. Evaluation of global average overhead decision-making. It reveals that the optimal selection approach clearly outperforms the three other models in terms of global overhead. This is due to the fact that the proposed model always chooses the most efficient offloading choice in terms of computational and communication delays.

Moreover, the impact that different simulation parameters might have on the performances was thoroughly investigated. First, results shown in Fig. 4(a) represent the average overhead achieved in scenarios with different number of UAVs. We can notice that the growth in UAV swarm size does not impact the performance of locally executed tasks and has a slight impact on offloading tasks to the edge. However, it mostly affects the overhead values when offloading to the ground station. Next, the impact of computation complexity, expressed as the number of image features to be extracted, was tested. Fig. 4(b) shows that adaptive optimal selection outperforms the three other models in terms of average system overhead. The obtained results also show that overhead values increase with higher computation complexity. However, they increase much slower for full offloading approaches compared to locally executed tasks. Even though local computing achieves better performance for tasks with lower numbers of features, edge offloading was better for tasks with a higher number of features. This means that local computing is most suitable for less intensive computation tasks (less than 100 features), whereas offloading to the edge is more appropriate for highly compute intensive tasks (more than 200 features). Finally, Fig. 4(c) shows that the average overhead increases as the data size, expressing the different frame sizes in our case, increases in the two offloading approaches, due to the fact that big data induce high transmission overhead. While for high resolution (720p) local computing achieves comparable results to edge offloading, for lower resolutions (360p and 480p) it is always more interesting to offload. However, adaptive optimal selection, on average, still outperforms all the other models for the three different frame sizes.

The previous results shown in Fig. 3 and Fig. 4 only consider binary offloading choice; either all the task is computed locally or fully offloaded. For in-depth analysis, Fig. 5 shows the different possible intermediate offloading rates. As explained in Sect. III, a global task would be divided into several elementary sub-tasks that can be executed on different devices. Three intermediate offloading possibilities have been considered, namely 25%, 50% and 75%. As shown in Fig. 5, on average, higher offloading rates towards the edge server always achieve better performances compared to lower offloading rates in terms of average overhead. This is mostly true for very compute intensive tasks, since performing even a small part of the computation on the drone would penalize the overall performance. However, this statement is not true for the ground station, where offloading 50% and 75% of the computational task is better than full offloading. This later case (100% offload rate to the ground station) produced a similar average overhead compared to 25% offload rate. This observation proves that computation offloading is not always better compared to local execution. It also shows that parallel execution, even on slightly powerful devices, can really achieve better performance. It should be finally noted that sending more data would require also more time, which would eventually have more effect on average overhead in the 100% offload to ground station case compared to the 75% and 50% cases.

V. CONCLUSION

The rapid emergence of UAV-related technologies attracted the focus of many research groups, which paved the way for new possible use case applications. Throughout this study, we consider the deployment of a small fleet of UAVs in a navigation and 3D mapping mission based on visual and inertial data, which is time sensitive, requires high refresh rates, especially for IMU readings, yet entails highly intensive computations (image preprocessing, feature extraction, etc.). Therefore, a new framework based on the Fig. 4. Detailed evaluation of average overhead MEC paradigm was introduced to better address these requirements. One of the main challenges we addressed is to conceptualize the effective integration of MEC into a specific flight mission. Then, we characterized different types of computational tasks to be offloaded from the drones to the edge servers. Moreover, we evaluated the impact of the proposed scheme on performance in different simulation settings and showed the possible benefits of the deployment of a drone network in a MEC environment for this specific mission. Simulation results show the effectiveness of the proposed model compared to other models.

As future work, we plan to further evaluate the impact that our computation offloading solution might have on the flight accuracy. We also plan to integrate in our model environment reconstruction and 3D mapping as a second use case.

Fig. 1 .

 1 Fig. 1. Overall view of the system model

  (a) Partial offloading (b) Full offloading Fig. 2. Possible offloading scenarios focus in T4 on updating and optimizing the new pose graph based on inputs from C1 and T3.

Fig. 5 .

 5 Fig. 5. Impact of different offloading rates on average overhead

TABLE I .

 I TEST SCENARIOS

	Test Scenarios
	# of UAVs	[1, 5, 10]
	# of Features	[50, 100, 200]
	Image Resolution	[360p, 480p, 720p]
	Edge Offload Rate (%) [0, 25, 50, 75, 100]
	GS Offload Rate (%)	[0, 25, 50, 75, 100]

TABLE II

 II

			.	SIMULATION PARAMETERS
	Simulation Parameters	Values
	F Local	CPU	1 GHz
	F Edge	CPU	10 GHz
	F GS	CPU	5 GHz
	R Cellular	20 Mbps
	R WLAN	50 Mbps

ACKNOWLEDGMENTS

This work was partially supported by Magenta Telekom (T-Mobile Austria GmbH) and Deutsche Telekom AG as well as by Alpen-Adria-Universität Klagenfurt (scholarship for visiting researcher M.A. Messous).