SLFS: Semi-supervised Light-field Foreground-background Segmentation

Efficient segmentation is a fundamental problem in computer vision and image processing. Achieving accurate segmentation for 4D light field images is a challenging task due to the huge amount of data involved and the intrinsic redundancy in this type of images. While automatic image segmentation is usually challenging, and because regions of interest are different for different users or tasks, this paper proposes an improved semi-supervised segmentation approach for 4D light field images based on an efficient graph structure and user's scribbles. The recent view-consistent 4D light field superpixels algorithm proposed by Khan et al. is used as an automatic pre-processing step to ensure spatio-angular consistency and to represent the image graph efficiently. Then, segmentation is achieved via graph-cut optimization. Experimental results for synthetic and real light field images indicate that the proposed approach can extract objects consistently across views, and thus it can be used in applications such as augmented reality applications or object-based coding with few user interactions.

I. INTRODUCTION
When humans look at images, their brains can easily classify the objects in the scene by distinguishing the object's borders and understand the content. However, this task is much harder for computers which consider the scene as an array of pixels. To analyze the scene and understand its content by identifying meaningful objects, computers typically must start by applying image segmentation, which is the process of partitioning an image into smaller parts with homogenous properties. In computer vision, there are lowlevel, mid-level and high-level image segmentation techniques depending on the semantic meanings of the resulting segments. Basically, low-level image segmentation divides the image into smaller regions automatically with similar visual characteristics, such as color or depth, but not necessarily with a semantic meaning, and it can be used as a pre-processing step for object tracking or image editing [1], [2]. Mid-level image segmentation divides the image into a smaller number of larger regions (i.e., objects), it may be assisted with user interaction, however, it does not have semantic labels for the objects [3]. In addition to the mid-level segmentation output, the high-level image segmentation, can be assisted with high-level knowledge or learning process to obtain semantic meaning for the objects (e.g., a car, a flower, etc.) [4], which is out of this paper's scope. In this paper, a combination of low-level image segmentation and user scribbles are considered to obtain mid-level (e.g., foregroundbackground segmentation) without having pre-defined semantic labels for the objects.
Although image segmentation is usually considered as a challenging problem, certain conditions can make it even harder, such as overlapping between objects with poor contrast or the huge amount of data, as in the 4D Light Field (LF) images, specifically when pixels are used as graph nodes. 4D LF images can be obtained by an array of cameras or by a single camera equipped with a special microlens array in front of the sensor or a moving camera gantry to capture different viewpoint images at different times. LF images record not only the intensity of light but also the angular direction of light rays [5]. The resulting 4D LF image, which can have a very large number of pixels, can be interpreted as a 2D array of 2D views and parametrized as ( , , , ) where , are the spatial geometry of pixels in each view and , are the angular geometry of views. The 2D views are obtained from slightly different perspectives. While the 4D LF images contain a huge number of pixels, the similarity between pixels in different views can be used to reduce the computational complexity [1]. Furthermore, one of the most important advantages of 4D LF imaging is that it inherently includes depth information in its structure, which can be used in clustering and label propagation. In general, when traditional 2D segmentation is applied to 4D LF images, the information from adjacent views is not considered to resolve object occlusions, thus resulting in inconsistent segmentation across views. In order to cope with these challenges, the 4D LF image structure should be adequately considered. Various LF segmentation techniques have been proposed in the literature [3], [6]- [10]. However, most 4D LF segmentation techniques are either time-consuming, not interactive, not proposed for full consistent 4D LF segmentation or relying on accurate depth estimation.

a b
This work was funded by FCT/MCTES through national funds and when applicable co-funded by EU funds under the project UIDB/50008/2020.
To overcome the existing limitations and because the regions of interest are different for different users or tasks, an improved interactive Semi-supervised 4D LF Foregroundbackground Segmentation (SLFS) solution is proposed (see Fig. 1). This approach can be widely applied in object-based LF coding, augmented reality applications, or object extraction. Similar concepts to the segmentation algorithm proposed in [9], such as the graph-based image segmentation and the graph-cut optimization technique are used in this paper. However, different superpixel algorithm (i.e., the stateof-the-art View Consistent Light Field Superpixel (VCLFS) [10]) is exploited as graph nodes, enabling a dramatic reduction in the size of the graph and to effectively propagate the segmentation consistently across views, without the need for extra accurate depth estimation algorithm.
The remainder of the paper is organized as follows: Section II briefly reviews the related work on 4D LF image segmentation available in the literature; Section III describes the proposed approach in detail; Section IV evaluates the SLFS performance through a series of experimental results; Section V concludes the paper with some final remarks and proposes directions for future work.
II. RELATED WORK Image segmentation is a fundamental task in computer vision, and it has been attracting the attention of researchers for many years. Several image segmentation solutions for 2D images have already been proposed, however, only a few solutions have been proposed to tackle the 4D LF challenges, such as the huge amount of data and the need for ensuring the segmentation consistency across views. For low-level image segmentation, 4D LF superpixels/superrays have been proposed in [1], [8], [10] and can be used to enhance LF editing tasks (e.g., by propagating the edits into a 4D LF superpixel instead of a single pixel). For the case of mid-level image segmentation, Wanner et al. [3] proposed the first variational framework for multi-label segmentation, where the color and disparity cues of input seeds are used to train a machine learning classifier (i.e., random forest) that is used to predict the label of each pixel. However, the segmentation is not performed on the full 4D data (only the central view is segmented), the authors mentioned that the optimization step can take ~5 minutes on a modern GPU if applied for all views. Mihara et al. [6] improved Wanner's approach by building a graph in 4D space with spatial and angular neighbors and then using graph-cut for multi-label segmentation. Due to the huge number of graph nodes and the high computational time, only a fraction of the LF views (i.e., 5×5) were considered in the experiments. To reduce the graph size, Hog et al. [7] proposed a novel graph representation that utilizes the ray bundle (i.e., a set of all rays describing the same 3D scene point) as a graph node and exploited the redundancy in the LF data, decreasing the running time of the Markov Random Field (MRF) optimization and achieving entire 4D LF views segmentation. However, their approach depends on quite accurate depth estimation on all the views, thus, inaccurate individual depth maps greatly increase the running time and decrease the segmentation coherence. Additionally, the segmentation results can be very sensitive to the noise in real LF images.
It has been proven the efficiency of achieving mid-level and high-level segmentation based on low-level (e.g., superpixel) segmentation [2]. Lv et al. [9] recently proposed a novel hypergraph representation for 4D LF multi-label segmentation by exploiting the superpixels proposed in [8] as hypernodes to reduce the graph size. However, Lv et al.'s approach relies on superpixel segmentation that requires depth estimation from extra algorithm, hence, it can be timeconsuming. Additionally, it is not as accurate for real LF images as for the synthetic LF images due to the lack of accurate estimated depth map. Our approach is different from the recent work in [9], by replacing the used superpixels and simplifying the graph structure and size. Our approach is designed to interactively extract foreground from background similar to the recent work in 2D images [2], however, the segmentation is applied for all 4D LF data to achieve effective interactive segmentation of user's region of interest.

III. PROPOSED LIGHT FIELD SEGMENTATION APPROACH
In order to achieve foreground-background 4D LF image segmentation, the proposed approach consists of four major steps (see Fig. 2):

A. LF superpixel extraction
In contrast to the widely used 2D superpixel algorithms, such as Simple Linear Iterative Clustering (SLIC) in [11], which divide an image into smaller clusters with similar visual appearance and spatial geometry, 4D LF image segmentation algorithms need to consider the depth information to extract consistent 4D LF superpixels. From the few proposed 4D LF superpixel algorithms, the state-of-the-art VCLFS algorithm is used in our proposed algorithm for the following reasons. Firstly, the VCLFS algorithm does not require an external depth estimation algorithm, since it implicitly estimates the disparity by computing the slopes of Epipolar Plane Image (EPI) lines for all LF views [10]. Secondly, the occluded objects where the foreground and background lines are intersected in the EPI are considered in the VCLFS algorithm and properly detected to prevent wrong segmentation. Finally, it outperforms other LF superpixel algorithms, notably [8], that is used in the recent 4D LF multi-label segmentation algorithm [9], in terms of boundary adherence, view consistency and running time [10], which is important for later foreground and background segmentation.
The VCLFS algorithm consists of three major steps: i) line extraction from the EPIs of central horizontal and vertical views of a 4D LF image; ii) occlusion-aware EPI segmentation; and iii) spatio-angular clustering by projecting the EPI segments of the central views into the central view and firstly clustering the central view using K-means algorithm, where the CIELAB color space, position and disparity are used. Afterward, the clustering labels are propagated across all views based on the EPI segments and disparity. After superpixels are extracted, the texture is characterized by using histograms of the superpixels' intensities. To compute the histograms, the image is converted to the Hue, Saturation and Value (HSV) color space first. The HSV color space is designed to approximate the human vision perception and it is widely used for image analysis and segmentation [12]. To achieve luminance invariance, the value channel is not considered, and the histogram is computed using only the hue and saturation channels. For each superpixel, a 2D histogram of hue and saturation values is computed. Each superpixels' histogram is normalized by dividing it by its sum. The obtained superpixels and the corresponding histograms will be used in the next step to create the graph representation. Overview of the proposed SLFS algorithm: step 1) LF superpixels are extracted using the VCLFS algorithm; step 2) a graph is created using superpixels as graph nodes; step 3) scribbles are inserted by the user to initially label foreground and background superpixels; step 4) a graph-cut optimization is performed to the central view and propagated to the entire 4D LF views to iteratively achieve interactive foreground-background segmentation.

B. Graph creation
Since our goal is to improve the 4D LF segmentation, the theory of graphs can be applied similarly to what has been done for 2D image segmentation. However, in the context of the 4D LF segmentation, several algorithms used a graph representation of the 4D LF image by representing each pixel as a graph node [6]. Due to the huge size of a LF image, the number of resulting graph nodes is also massive, leading to a high computational complexity not suitable for 4D LF interactive applications. In contrast, the hypergraph concept which is conceptually defined and used in [9] is similarly used in our approach and significantly reduces the graph size by defining the extracted 4D LF superpixels as graph nodes, however, we did not consider the angular neighbors or the multiple-target nodes as in [9]. Generally, a hypergraph is one type of graph representation that uses a set of nodes as one hypernode as well as the connected edges between two hypernodes as one hyperedge (see Fig. 3). Additionally, the hypergraph is coarsened into a planar graph by considering all corresponding superpixels across views as one hypernode.
In our graph representation, a planar graph is created on the central view superpixels and conceptually represented a hypergraph, where each hypernode in the central view graph includes all corresponding superpixels across views. The central view is chosen for two reasons: i) in dense 4D LF images, there is only a slight shifting across views and according to the Lambertian assumption, the 3D point of the scene is corresponding to a straight line in the EPI [10]. Thus, most superpixels in the central view having corresponding superpixels in all LF views with small disparities; and ii) the user is usually interested in segmenting frontal objects instead of small occluded objects. The corresponding superpixels across views are computed in the VCLFS by changing the spatial position of the central view superpixels based on the angular location of the view and the superpixels' disparities, and it assigns a same numeric label to the corresponding superpixels. The final segmentation will be propagated by assigning the corresponding superpixels across views, the same foreground or background labels as central view superpixels. In Fig. 3, a simplified hypergraph illustration is shown. In the red rectangle, there is an edge between two superpixels, similarly, the red edge exists in all 4D LF views in Fig. 3. The hypernodes ! , " can be shown in the two circles below and connected with a hyperedge. In order to represent a graph, we need to define the edges between the graph nodes 1 The Delaunay algorithm finds a subdivision of a set of points into a nonoverlapping set of triangles, such that no point is inside the circumcircle of any triangle. and compute their weights. Since superpixels' shapes are irregular in most situations, the Delaunay Triangles algorithm 1 [13] is used to find the graph edges between neighboring superpixels' centroids. The Delaunay algorithm provided in the open-source Python library Sci-Py [14], [15] is used here. To create the graph and perform graph-cut optimization to achieve foreground and background segmentation, the LF superpixels are used as nodes of the graph. Furthermore, two target nodes are added to the graph, for the foreground # (source node) and the background $ (sink node), respectively (see Fig. 2). The maximum flow from the source to the sink is determined by the bottleneck (i.e., the edges minimum cut). Additionally, two different edge types are defined: i) target edges (i.e., the edges between the superpixel and the target nodes); and ii) neighboring edges (i.e., edges between spatially neighboring superpixels). After defining the types of the nodes and edge, we build a graph = ( , ) of the central view, where represents both superpixels and target nodes, and represents edges between nodes. Each edge between superpixels is weighted by comparing the adjacent histograms using average Kullback-Leibler Divergence (KLD) [16] to compute the relative difference between histograms as in (1): where ! ( ) and " ( ) are, respectively, the hue and saturation 2D histograms of spatially adjacent superpixels ! and " in the central view (as a complexity tradeoff in this Foreground

Background
Step 1: LF superpixel extraction Step 2: graph creation Step 3: user scribbles insertion Step 4: graph cut image segmentation Fig. 3. The hypergraph representation where all corresponding superpixels across views are represented as one hypernode as in ! ! #$% ! " . The red lines represent edges between two neighboring superpixels and, similarly, all corresponding edges between two hypernodes are represented as one hyperedge.
scribbles are labeled either foreground or background, according to the scribble's label, and utilized as initial seeds to label unlabeled superpixels in the graph-cut step, where the cumulative foreground and cumulative background histograms are used. When user scribbles are inserted, graph target edges between labeled superpixels and target nodes are generated. Considering a superpixel under foreground scribbles, the edge weights between superpixel node * # and the target nodes , # and , $ represent the self-penalty C + (i.e., the cost of labelling each superpixel as either foreground or background) as in (2) and (3): where C , # 1, # 2 is the edge weights between the foreground labeled superpixel and , # (labeled as zero), and C , # (, $ ) is the edge weights between the foreground labeled superpixel and , $ (labeled as one). A small value is assigned for foreground target edge if the superpixel is under foreground scribbles, while a high value is assigned for the background target edge to increase the self-penalty. In our experiments we fixed W -.) to 100 as a high value. The same approach is used for superpixels under background scribbles.

D. Graph-cut image segmentation
Generally, image segmentation can be formulated as the minimization of an energy cost function with two additive terms: i) the self-penalty (a.k.a data cost); and ii) the neighboring penalty (a.k.a smooth cost). Self-penalty represents the cost of labelling each superpixel as either foreground or background. Furthermore, the neighboring penalty ensures that neighboring superpixels are smooth and penalizes neighbors that have different labels.
To achieve the segmentation, graph-cut optimization is used, which is effective and handles image segmentation in terms of energy minimization [9].
Hypernode Hypergraph paper, summations are over 20 histogram bins), and λ is a control parameter that helps in the graph-cut optimization process (after extensive testing, in our experiments a default value of = 25 was used since it led to the best subjective results); this parameter is especially useful in case of very small or null difference between the superpixel histograms.

C. User scribbles insertion
For semi-supervised interactive segmentation, a user can insert different scribbles to indicate the region of interest on the reference view. In this paper, the central view is selected as a reference view, since almost all views contain central view content with slight shifting. All superpixels under the scribbles are labeled either foreground or background, according to the scribble's label, and utilized as initial seeds to label unlabeled superpixels in the graph-cut step, where the cumulative foreground and cumulative background histograms are used. When user scribbles are inserted, graph target edges between labeled superpixels and target nodes are generated. Considering a superpixel under foreground scribbles, the edge weights between superpixel node # and the target nodes # and $ represent the self-penalty + (i.e., the cost of labelling each superpixel as either foreground or background) as in (2) and (3): , where , # 1 # 2 is the edge weights between the foreground labeled superpixel and # (labeled as zero), and , # ( $ ) is the edge weights between the foreground labeled superpixel and $ (labeled as one). A small value is assigned for foreground target edge if the superpixel is under foreground scribbles, while a high value is assigned for the background target edge to increase the self-penalty. In our experiments we fixed W -.) to 100 as a high value. The same approach is used for superpixels under background scribbles.

D. Graph-cut image segmentation
Generally, image segmentation can be formulated as the minimization of an energy cost function with two additive terms: i) the self-penalty (a.k.a data cost); and ii) the neighboring penalty (a.k.a smooth cost). Self-penalty represents the cost of labelling each superpixel as either foreground or background. Furthermore, the neighboring penalty ensures that neighboring superpixels are smooth and penalizes neighbors that have different labels.
To achieve the segmentation, graph-cut optimization is used, which is effective and handles image segmentation in terms of energy minimization [9]. The cumulative foreground and background histograms ( /0 , /1 ) of the superpixels under the user scribbles are computed separately after the user's insertion. In order to assign a label for each unlabeled superpixel, the KLD is used to compute the relative difference between cumulative target histograms and the superpixel histogram as in (4): where , ! 1 # => $ 2 is the self-penalty, and /0 => /1 is foreground or background cumulative histogram. Suppose L is a label vector, which includes foreground (0) and background (1) labels for all the superpixels L ∈ {0,1} ? . The energy function is computed by summing the data cost and smooth costs for assigning label ! to superpixel ! considering the labels of the neighbors ! as in (5) [17]: Finally, the graph-cut algorithm is applied to minimize the energy function to obtain the segmented result as in (6): where the energy function E(L) is the cost of assigning label ! to each superpixel ! in the image by summing the data cost and the smooth cost for each superpixel ! and its spatially neighboring superpixels " , where ! is the set of neighboring superpixels of ! . In our algorithm, we take advantage of the optimized PyMaxFlow library to apply the graph-cut that implements the algorithm in [17] for central view. Since each superpixel in the central view conceptually represents a hypernode of all self-similar superpixels across views, the superpixels' labels from the central view are propagated to the entire 4D LF views by assigning each superpixel related to the hypernode to the label of the superpixel in the central view. The graph-cut optimization is interactively continued after each user's scribble insertion of both foreground and background scribbles, and the calculation of the cumulative target histograms are updated until the object segmentation is achieved according to the user's decision. Finally, the border's noise is removed from the final mask using median filtering with kernel size of (7 × 7) and simple morphological operation (i.e., opening), with kernel size of (3 × 3). The used filters may slightly affect the spatial accuracy, but visually obtain smoother boundaries and reduce the noise. IV. EXPERIMENTAL RESULTS To evaluate the proposed approach, we implemented the proposed SLFS algorithm on a macOS computer with Intel i5 2.3 GHz processor and 8GB LPDDR3 memory. We used both synthetic 4D LF images [18] and 4D LF data captured with a Lytro Illum camera [19] as shown in Table I. The algorithm is implemented using Python programming language and the open-source code for the VCLFS algorithm [20] was used to extract the 4D LF superpixels. The segmentation results are presented in Fig. 4 and Fig. 5, for synthetic and real LF images, respectively. Several parameters can affect the segmentation result, such as the superpixel size and image texture complexity. In the VCLFS algorithm, the segmentation size of will generate average superpixel size of & pixels per superpixel (assuming a square shape) [20]. In our experiments (see Fig. 4 and Fig. 5), we set the segmentation size of the VCLFS to 30, to generate an average superpixel size of 900 pixels. This size of superpixel generates consistent and accurate segmentations with a reasonable computational complexity. In Fig. 6, we changed the size of superpixels to study its effect on segmentation. Larger sizes make the segmentation faster in terms of graphcut optimization. However, it results in inaccurate segmentation due to the larger clusters that cannot be divided. On the other hand, smaller sizes result in a more accurate segmentation, but will increase the graph size and complexity. In Fig. 6, the segmentation graph-cut takes around 8 , when using VCLFS with a segmentation size of 100, but it takes around 35 and 82 for a segmentation size of 30 and 15, respectively. According to the image texture, images with complex texture require more scribbles than those with non-complex texture. In Fig. 4, the Monasroom image presents a complex texture requiring more user scribbles and interaction than in the Papillon image.
To compare our results with the other 4D LF segmentation algorithms that target multi-label segmentation, we used all the published segmentation masks in [7]. We were not able to compare with the recent work in [9] since there is no published masks or open-source code for the algorithm, additionally, there is no enough implementation details to reproduce it. Furthermore, similar work targeting foreground-background segmentation has been proposed for 2D images [2], and its comparison here would be unfair due to the 4D LF structure and propagation consistency. To enable the comparison with multi-label segmentation, we considered the targeted object (e.g., the yellow horse in Fig. 7) as a foreground and other labeled objects as background, hence, binary masks from the segmentation masks in [7] and the HCI segmentation ground truth in [18] are generated instead of multi-label masks. The comparison results are displayed in Table II, we used test images and their ground truth from the HCI dataset [18].   (larger superpixels may create inaccurate segmentation results due to the larger cluster that cannot be divided while very small superpixels improves the accuracy and increases the graph complexity).
By using the hypergraph concept with the VCLF superpixels to represent the 4D LF image, a significant reduction in graph size is achieved. For example, the Buddha image has 4.77 × 10 E pixels, the algorithm in [7] reduced the graph size to 8.19 × 10 F nodes. Additionally, the algorithm in [9] reduced the graph size to 1.46 × 10 G nodes, while our algorithm reduced the graph size to only 625 nodes with similar accuracy as in Table II. Additionally, the segmentation result is consistent across views and adhere to the object's boundaries. Fig. 8, shows the consistent segmentation results, where our results show better visual consistency in some parts (e.g., the horse's hoof) compared to [7]. The VCLFS algorithm takes ~ 250s and ~273s for HCI and EPFL datasets respectively for superpixels extraction with superpixel size of 30, the graph-cut for the central view takes ~35 and the propagation to all LF views takes ~3 .  V. FINAL REMARKS In this paper, an improved interactive 4D LF foregroundbackground segmentation solution -SLFS -is proposed and evaluated. Firstly, the 4D LF superpixels are extracted efficiently using the VCLFS algorithm. Afterward, a hypergraph based on superpixels is created. Then, the segmentation problem is treated as an energy function optimization where a graph-cut technique is applied to optimize the segmentation result. Finally, the segmentation result is propagated to all 4D LF views consistently.
Experimental results were conducted on both real and synthetic 4D LF images and show the effectiveness of the proposed approach with comparable results even after the dramatic reduction in the graph complexity. Additionally, the experimental results show that the segmentation can be affected by the superpixel size, the image complexity and the graph-cut parameters.


extfieldsofstudy:
Computer Science
Engineering
Mathematics

text:
The Covering-Assignment Problem for Swarm-powered Ad-hoc Clouds: A Distributed 3D Mapping Use-case

The popularity of drones is rapidly increasing across the different sectors of the economy. Aerial capabilities and relatively low costs make drones the perfect solution to improve the efficiency of those operations that are typically carried out by humans (e.g., building inspection, photo collection). The potential of drone applications can be pushed even further when they are operated in fleets and in a fully autonomous manner, acting de facto as a drone swarm. Besides automating field operations, a drone swarm can serve as an ad-hoc cloud infrastructure built on top of computing and storage resources available across the swarm members and other connected elements. Even in the absence of Internet connectivity, this cloud can serve the workloads generated by the swarm members themselves, as well as by the field agents operating within the area of interest. By considering the practical example of a swarm-powered 3D reconstruction application, we present a new optimization problem for the efficient generation and execution, on top of swarm-powered ad-hoc cloud infrastructure, of multi-node computing workloads subject to data geolocation and clustering constraints. The objective is the minimization of the overall computing times, including both networking delays caused by the inter-drone data transmission and computation delays. We prove that the problem is NP-hard and present two combinatorial formulations to model it. Computational results on the solution of the formulations show that one of them can be used to solve, within the configured time-limit, more than 50% of the considered real-world instances involving up to two hundred images and six drones.

Introduction
An Unmanned Aerial Vehicle (UAV) -otherwise commonly known as drone -is a flying vehicle whose weight can vary, according to the targeted applications, from a few hundreds grams to hundreds of kilos. The popularity of drones is rapidly increasing across the different sectors of the economy. Aerial capabilities and relatively low CAPEX/OPEX costs make UAVs the perfect solution to improve the efficiency of those operations that are typically carried out by humans, e.g., building inspection, photo collection, area surveillance, etc.
In normal operations, drones are remotely controlled by human pilots through wireless remote controls. However, by setting the UAV autopilot in auto off-board mode, a drone can operate in a fully autonomous manner by following the inputs generated by an on-board flight computer directly connected to the autopilot. This capability can be leveraged to create fleets of autonomous UAVs collaborating to fulfill the desired missions. This is achieved by installing a arXiv:2004.11837v1 [eess.SP] 21 Apr 2020 collaborative drone application on each on-board flight computer of the fleet and by connecting these latter on the same wireless network.
The possibility of organizing drones in fleets of autonomous and collaborating entities naturally attracted the attention of swarm robotics scientists [1]. Swarm robotics studies how to reproduce, with the help of artificial agents, those swarming behaviors typically observed in nature -in ant colonies, bee swarms, bird flocks, etc. Swarm behaviors have the potential to revolutionize the world of robotized applications -including UAV applications -because of their promise of jointly achieving maximum performance and maximum resilience through the power of distributed interactions that do not require any form of centralized supervision.
In a complex mission, the UAV swarming component is typically dedicated to data collection duties, e.g., taking pictures, producing video feeds, sniffing wireless signals. Other technologies are then involved in processing the collected data and producing the desired output. For instance, digital photogrammetry algorithms [47,48], can be leveraged to elaborate the images collected by the swarming UAVs, by extracting and displaying the relevant 2D/3D geometric information.
The data-processing phase -3D processing phase in the photogrammetry use-case [49,50,51,52,53,54] -is typically executed in the cloud and in a centralized fashion [55]. However, to mitigate Internet connectivity and network latency issues, the distributed power of the UAV swarm can be leveraged to establish an ad-hoc cloud infrastructure on top of which executing the data processing phases of the considered mission [55,56,57,58]. This approach aims to exploit the power of the many -many embedded microcomputers of limited power are installed on the swarming UAVs -to replace the computer power typically available in a powerful work station reserved in the cloud. This paper addresses the problem of optimizing the exploitation of a swarm-powered ad-hoc cloud, by jointly dealing with two interrelated aspects of the data-processing stage: • the workload generation, i.e., definition of the computing application elements and of the corresponding set of data input.
• the workload scheduling/assignment, i.e., mapping of computing application elements and physical swarm members.
In particular, we consider the generation and placement of workloads whose input data are subject to geolocation/clustering constraints. Practically speaking, the collected data are bound to a location and must be processed in batch of neighboring samples: in the 3D reconstruction use-case, this means that groups of neighboring pictures have to be processed by the same computing element. This additional constraint has a non-negligible impact when dealing with a swarm powered ad-hoc cloud: due to the distributed nature of the swarm-powered data collection stage, the whole input data-set may end up being completely scattered across the UAVs of the swarm. If not properly dealt with during the workload generation/scheduling processes, this aspect may severely deteriorate the whole process performance due to unnecessary data transmission delays (input data must be received by the corresponding computing application element).
For the purpose of illustrating the applicability of our approach to a real-life application, we adjust the proposed solution to a relevant use-case scenario from the emergency response field. Our use-case is a perfect example of a real-life application subject to geolocation constraints that highly benefits from swarm-powered ad-hoc cloud infrastructure [59]. In fact, the drone swarm is able to perform 3D reconstruction of a region of interest -comprising five hundred photos -on top of twenty Raspberry Pis [60] microcomputers [61].
In such context, the 3D map of a given region of interest is used to improve the decision making process and the operator situational awareness through the availability of a 3D digital twin of the operation area, where the elements of interest can be even selectively highlighted, e.g., building or road damages, risky areas, etc. Producing the relevant 3D maps in a timely manner (near real-time), even when the cloud connectivity is not available, is crucial to increase the chances of success of an operation. To this purpose, we introduce a new optimization problem, namely the Covering-Assignment Problem for swarm-powered ad-hoc clouds (CAPsac). Given a set of geo-positioned aerial pictures (data) that are physically distributed across a set of UAVs (stored on the embedded microcomputers on the drones), CAPsac minimizes the 3D mapping (data-processing phase) completion time by jointly computing: • the optimal workload configuration/the optimal covering of photos, i.e., splitting the overall photographed region across multiple convex sub-regions, and • the optimal workload scheduling/the optimal assignment of photographed sub-regions to UAVs, i.e., deciding which drone (its embedded microcomputer) is responsible for the 3D reconstruction of a photographed sub-region.
It is worth pointing out that, differently from the decompose-then-allocate and the allocate-then-decompose paradigms [62] broadly adopted in (both the cloud computing optimization and) the multi-robot task allocation literature, CAPsac is an integrated decision model that handles workload generation (photo covering or sub-region splitting) and workload assignment (sub-region to UAV assignment) at the same time.
The remainder of the paper is organized as follows. The next section formally introduces the CAPsac problem, by clearly highlighting how the general problem designed for swarm-powered ad-hoc clouds is naturally applied to optimize the execution of a distributed 3D mapping application. Once the relationship between the general problem and the specific 3D mapping use-case will have been clearly proved through Section 2, it will be possible to present the remainder of the paper by directly referring to the latter. We believe that this editing approach will allow the reader to better grasp the details and the added value of the proposed solution. Two mathematical programming formulations to solve the CAPsac problem are described in Section 3 while Section 4 presents the NP-hardness proof for the problem. Finally, Section 5 presents and discusses the computational results obtained by experimenting with realistic 3D reconstruction instances, while Section 6 summarizes our concluding remarks.

Covering-Assignment Problem for Swarm-powered Ad-hoc Clouds -CAPsac
A swarm-powered mission can be typically decomposed in two phases: i Data collection: the UAVs of the swarm dynamically collaborate to collect all the necessary information within the area of interest. In a swarm-powered 3D mapping mission, this phase corresponds to the photo-collection process meant to shoot the required aerial photos of the selected area. Note that the set of required pictures is typically computed by a dedicated mapping software and is merely an input of the mapping mission.
ii Data processing: the collected data are collaboratively processed by the ad-hoc cloud built on top of the microcomputers installed on the UAVs to produce the desired output. During this process, thanks to the swarm-powered ad-hoc cloud, the computing workload can be parallelized over the available computing units. Furthermore, the collected data can be transferred over the inter-drone wireless network to satisfy the input requirements of the distributed processing tasks. In a swarm-powered 3D mapping mission, this phase corresponds to the 3D-processing process meant to compute a 3D point cloud and/or a 3D mesh of the selected area.
The proposed CAPsac problem deals with the optimization of the data (3D) processing phase and has no direct control on the data (photo) collection strategy. Given the set of data (aerial pictures) just collected by the UAVs, CAPsac aims at minimizing the overall processing time required to compute the desired output (3D map).
An explanatory CAPsac problem instance involving a swarm of four drones performing a 3D mapping mission is represented in Fig. 1. The full lines delimit the area of interest represented by the set P of aerial pictures just captured by the four drones during the photo collection phase. Each photo p ∈ P was taken by a specific drone (which also stores it in memory). Furthermore, each picture must be processed during the 3D processing phase to guarantee a proper reconstruction. Figure 1: Explanatory instance of CAPsac problem accordingly to the 3D mapping use-case.
In Fig. 1, the positions of the four drones are represented by the large symbols "×", "+", " ", and "•". Not all drones may be equipped with microcomputers powerful enough to support the 3D processing workload. In the example of Fig. 1, only two drones are considered 3D-capable, those represented by the + and the × symbols.
Each photo is characterized by its shooting location, which is denoted by the small versions of the symbols previously used to represent the UAVs: the pictures represented by a small + were shooted by the drone represented by the large +, and so on. Note that, given the dynamic nature of the decentralized decision-making process employed by the swarm of drones [62], it is impossible to know a-priori which UAV will shoot which picture.
A solution of the CAPsac problem describes how to: • Split the processing workload into multiple processing (application) components, each responsible for dealing with a specific subset of the collected data, e.g., of the aerial pictures. Note that in the 3D reconstruction use-case each 3D reconstruction sub-task corresponds to a specific sub-region and requires as input all the aerial pictures that belong to that sub-region.
• Assign each processing component and all its corresponding input data to at least one of the computing elements available within the swarm-powered ad-hoc cloud, i.e., the microcomputers installed on the swarming-UAVs or on any other ground element connected to the swarm itself.
The optimal solution of CAPsac minimizes the latest processing time among all the involved computing elements, which corresponds to minimizing the makespan of the whole 3D reconstruction process. Three main issues cannot be ignored when assigning the photos (and thus the sub-regions) to the optimal 3D processing drones. Note that for sake of simplicity, we consider the case of not more than one computing device available on each drone.
i A feasible region (workload) subdivision is characterized by the creation of a spatial-convex covering: the union of the sub-regions corresponds to the whole region and the photos associated to each sub-region must be a spatial-convex set. Accordingly, a photo can be assigned to a drone if and only if it lies inside the convex hull of all the photos assigned to that drone. Fig. 2 illustrates a set of photos which is not spatial-convex. The assigned photos are represented by colored "•" symbols. The "•" symbols represent photos that do not belong to the set, which are hence assigned to other drones. Spatial-convex sets are crucial to perform the 3D mapping procedure since the presence of non-overlapping photo footprints (represented by the dashed colored rectangles in Fig. 2) makes the 3D reconstruction of the associated region impossible. Fig. 3 shows an example of a photo spatial-convex set assigned to one 3D-capable drone. It is worth pointing out that the creation of a spatial-convex covering is required by any workload operating over geo-located/clustered data to be processed in neighboring batches.  Figure 3: Spatial-convex set and the respective convex hull.
ii As the sub-regions (and their corresponding pictures) are assigned to the 3D-capable drones, a drone may need to require some input pictures (data) from the other swarm members. The CAPsac considers a pre-defined single-tree network topology built by a networking middleware running on the swarming drones [63]. Note that in Fig. 4, the network links are represented by the pointed lines. Besides, in a single-tree network topology, only one routing path exists to connect each pair of UAVs. A drone cannot start the 3D reconstruction of the assigned sub-region until all the required photos are received. The TCP communication protocol is widely applied in engineering to achieve reliable transmissions and flow control, and it is adopted to model the swarm communications in the CAPsac problem. According to [64], a good way to approximate the transmission behavior concerning the TCP protocol is to assume that the transmission rate allocation follows the Max-Min Fairness -MMF paradigm [65]. Thus, minimizing the makespan of the 3D reconstruction requires that all the transmission rates of the network follow the MMF paradigm. iii Finally, a reliability factor should be considered to immunize the CAPsac assignment with respect to drone malfunctions. The reliability factor defines the minimum number of drones (computing elements) that should process each sub-region. Fig. 4 shows a feasible solution to the CAPsac problem optimizing the makespan of a 3D mapping mission and considering a reliability factor equal to one. The dashed and the dashed-and-pointed lines define a feasible spatialconvex covering. The number of sets comprising the covering is equal to the number of 3D-capable drones. For instance, the covering in Fig. 4 has only two sets. The photos lying within the left sub-region are processed by drone +, whereas those in the right sub-region are elaborated by drone ×. Given that the relationship between the general CAPsac and the swarm-powered 3D mission use-case has been clearly established, we will present the remainder of the paper referring directly to the specific use-case. Thus, it will be possible to the reader to better grasp the details and the added value of our proposed optimization problem. Table 1: CAPsac parameters in the context of the 3D mapping use-case. Parameters Description λ p estimated processing time of a photo p µ p amount of data of a photo p in Mb θ dp equal to 1 if drone d has the photo p stored in its memory F set of traffic demands between each pair of drones reliability factor m number of drones (equiv. number of sub-regions) which can perform 3D reconstruction T maximum allowed time for exchanging photos between drones 3 Mathematical programming formulations

Common definitions
Let us consider a swarm of drones D of different types which is responsible for the 3D reconstruction of a region described by the set P of photos. LetD ⊆ D, with |D| = m, be the set of 3D-capable drones that have enough computing power to support the 3D reconstruction workloads. The location of all photos p ∈ P are also known.
Given a photo p ∈ P , let λ p and µ p be the non-negative real parameters representing, respectively, the estimated processing time of p and the storage space occupied by p (expressed in megabytes). Also, for each drone d ∈ D, let θ dp be the binary parameter equal to 1 if photo p ∈ P is stored on drone d. The subset of photos processed by a drone directly corresponds to a specific sub-region. Therefore, note that the number of sub-regions are hence equal to the number of 3D-capable drones available in the swarm.
Some pictures may have to be transferred among different drones to respect the computed sub-region assignment configuration. The picture transmission is supported by an undirected transmission tree T =(N, A), where the nodes of set N correspond to the swarming drones and the arcs of set A represent the device-to-device communication links (e.g., Wi-Fi links) between the drone themselves. Furthermore, let F be the set of traffic demands defined for each pair of drones (h, d) ∈ D ×D, where f hd denotes the demand (possibly null) between drones h and d. For all demands in F , let V hd be the set of links (i, j) ∈ A in the sole routing path between h and d in T . Also for each (i, j) ∈ A, denote c ij the transmission capacity of the link (i, j), and F ij = {F hd ∈ F |(i, j) ∈ V hd }, i.e., the set of demands that use the link (i, j) for transmission purposes. Finally, the maximum allowed time for transmitting the traffic demands through the network is denoted byT .
With the support of the notation just introduced -grouped in Table 1, we present two different Mixed-Integer Linear Programming (MILP) formulations to optimize the 3D-processing phase of 3D mapping missions with UAV swarms: • The Photo-based CAPsac (pCAPsac), where sub-regions are defined by explicitly assigning each picture p ∈ P to the corresponding sub-regions.
• The Region-based CAPsac (rCAPsac), where all the feasible rectangular sub-regions are given; the formulation is responsible for selecting the optimal set of sub-regions among those available.

Photo-based CAPsac
In the pCAPsac formulation, the decision variables will be optimized to compose R = {1, . . . , m} sub-regions (equiv. subsets of photos) to be reconstructed by the set of drones. The formulation aims to jointly perform two assignment operations: • each picture p ∈ P is assigned to one sub-region r ∈ R, • each non-empty sub-region r ∈ R is assigned to one 3D-capable drone d ∈D.
To this purpose, let y r p and x r d be the binary variables equal to 1 when, respectively, photo p ∈ P is assigned to sub-region r ∈ R, and sub-region r ∈ R is assigned to drone d ∈D. Furthermore, let g r dp be the binary variables equal to 1 if drone d ∈D is assigned to a sub-region r ∈ R that contains picture p ∈ P .

Assignment constraints
To obtain a proper 3D-reconstruction, each photo must be processed at least one time, i.e., it must belong to at least one sub-region: Similarly, each sub-region must be assigned to at least σ 3D-capable drones, with σ representing the previously introduced reliability factor meant to immunize the system toward possible drone failures: Finally, let us introduce the group of constraints necessary to correctly compute the g variables without introducing any non-linearity: That is, constraints (3)-(5) are the classical McCormick inequalities [66].

Spatial-convexity constraints
To properly work, state-of-the-art 3D reconstruction algorithms have to deal with convex regions and/or sub-regions, which is also equivalent to work with spatial-convex sets of photos. To this purpose, we approximate the convex hull of the set of photos assigned to a drone by its smallest enclosing hyperrectangle. This is not a bad approximation since 3D mapping missions often considers 50% to 80% of photo overlapping [67].
Since the GPS position of each photo shooting point is known, let C be the set of distinct picture longitudes and let L be the set of distinct photo latitudes. Note that the following relations are always respected: 1 ≤ |C| ≤ |P | and 1 ≤ |L| ≤ |P |. For each sub-region, there exists a finite set of photo latitudes and longitudes that represents the bounding rectangular box, i.e. the approximated boundaries of the sub-region.
The boundary of a sub-region r is defined by its left (α r ), right (β r ), bottom (γ r ), and top (ω r ) borders. Binary variables α r c , β r c , γ r , and ω r are used to designate the latitudes and the longitudes defining these borders: • Binary variable α r c is equal to one if longitude c ∈ C delimits the left border of sub-region r ∈ R, • Binary variable β r c is equal to one if longitude c ∈ C delimits the right border of sub-region r ∈ R, • Binary variable γ r is equal to one if latitude ∈ L delimits the bottom (inferior) border of sub-region r ∈ R, • Binary variable ω r is equal to one if latitude ∈ L delimits the top (superior) border of sub-region r ∈ R.
Each sub-region r ∈ R must be associated to a unique tuple of borders: To respect the sub-region convexity, a photo p ∈ P can be assigned to sub-region r ∈ R if and only if p is contained within the boundary defined for r. Geometrically, such constraint is fulfilled when (i) lng α r ≤ lng p ≤ lng β r and (ii) lat γ r ≤ lat p ≤ lat ω r , where the lat stands for the latitude and lng for longitude. To capture this geometrical pattern, for each photo p, the sets L p α , L p β , L p γ , L p ω are defined as: • L p α = {c ∈ C|lng c ≤ lng p }, i.e., L p α contains the longitudes on the left of lng p , • L p β = {c ∈ C|lng c ≥ lng p }, i.e., L p β contains the longitudes on the right of lng p , i.e., L p ω contains the latitudes above lat p .
Finally, the sub-region convexity is modeled by the Boundary Constraints -BC 1 , expressed as: Constraints (10)  However, a photo p is not assigned to sub-region r if and only if it lies outside the boundary of r, i.e., if lng p < lng α r , or lng p > lng β r , or lat p < lat γ r , or lat p > lat ω r , which may be expressed by either or Given constraints (6)-(9), constraints (14) guarantee that at least one of left-side summations is equal to one when p is not assigned to the sub-region r (i.e., y r p = 0). Consequently, at least one boundary of r makes the photo p to lie outside r. In a complimentary way, constraints (15) force that at most three boundaries are satisfied when the photo p is not assigned to the sub-region r.
Moreover, let us define valid inequalities (namely Ordering inequalities) to preemptively remove the infeasible boundaries in the continuous space for any possible sub-region. For instance, a boundary is infeasible if the the right border is placed on the left side of the left border. Such boundaries are removed through the following set of ordering inequalities:

Photo transmission constraints
For the purpose of minimizing the 3D processing computation time, it cannot be ignored that an additional delay is introduced any time a picture is transmitted by the drone where it is currently stored, to the drone that is responsible for reconstructing the corresponding sub-region. Given a demand f hd ∈ F , letc hd represent the minimum link capacity on routing path V hd and let z hd be the binary variable equal to 1 if traffic demand f hd > 0 is active, i.e., if at least one picture has to be transferred from drone h ∈ D to drone d ∈D. In this case, non-negative real variables φ hd are used to represent the transmission rate achieved by traffic demand f hd on its routing path.
The following two groups of constraints are introduced to, respectively, correctly activate binary variables z, and force flow variables φ to 0 when the corresponding traffic demands are idle and force the upper bound on the transmission rate, otherwise: Given a demand f hd , let w hd ij be the binary variable equal to one if link (i, j) is a bottleneck of f hd , as well as let u ij be the highest transmission rate among all the traffic demands carried by a link (i, j) ∈ A, i.e., u ij = max Thus, the following groups of constraints are used to impose the MMF paradigm for all the swarm communications (the photo transmissions) in pCAPsac [69]: Constraints (22) ensure that all the active demands have at least one bottleneck link on their routing path. The capacity of each link (i, j) ∈ A is respected through inequalities (23). The first condition required to consider a link (i, j) to be a bottleneck is jointly handled by constraints (23) and (24), which ensure that any bottleneck link (for at least one traffic demand) is saturated. The second bottleneck condition is instead fulfilled via constraints (25) and (26). Constraints (25) force u ij to to be greater or equal to the highest transmission rate among the demands that are flowing through link (i, j). Finally, constraints (26) guarantee that φ hd will not be exceeded by any other transmission rate of traffic demands routed over link (i, j) ∈ A when (i, j) is a bottleneck link of traffic demand f hd .
In pCAPsac formulation, a maximum networking/transmission latency ofT seconds is imposed for each activated traffic demand: The summation term r∈R,p∈P g r dp θ hp µ p computes the overall amount of data to be transferred from drone h ∈ D to the drone d ∈D. Limiting the transmission times means to ensure every drone receives all the photos belonging to the assigned sub-region within a maximum prefixed time set by the domain expert. This constraint can be relaxed by settingT to a suitable very high value.

Symmetry breaking constraints
Formulation pCAPsac suffers from symmetry in both photo-to-sub-region (i.e., y r p ) and sub-region-to-drone (i.e., x r d ) assignments. It is possible to partially break the symmetry of the sub-region-to-drone assignments. Each subregion can be assigned to one distinct drone in advance. That is, m variables x r d are fixed where the fixed pairs { (r 1 , d 1 ), . . . , (r m , d m )} ∈ {R ×D} have distinct indexes. Considering Fig. 1, the sub-region 1 could be assigned to the drone "+" and the sub-region 2 to the drone "×" for instance. Note that setting variables x r d does not affect the variables y r p . Consequently, just redundant integer solutions are eliminated.

Complete formulation
Let T max be the 3D mapping completion time, i.e., the makespan, calculated as the maximum processing time obtained from the swarm of drones. The variable T max is computed by the group of constraints where r∈R,p∈P (g r dp λ p ) computes the required time to process all the photos assigned to drone d ∈D. Finally, the pCAPsac formulation is expressed by the following MILP. x r d , y r p , g r dp ∈ {0, 1} ∀r ∈ R, ∀p ∈ P, ∀d ∈D The objective function (29) minimizes the makespan of the whole 3D mapping procedure. The domain constraints are given by (30)- (35). As |R| = |D|, the total number of constraints in the model is O(|P | · |D| 2 ) as well as the number of its variables.

Region-based CAPsac
The CAP sac problem can be addressed by explicitly considering the set S of all feasible rectangular subsets of photos, such that each element of S corresponds to a possible rectangular sub-region to be 3D-reconstructed. It is important to remark that the cardinality of S is polynomial and bounded by O(|C| 2 |L| 2 ), which is O(|P | 4 ) in the worst scenario: Proposition 1. Given a set S comprising all feasible rectangular sub-regions to a CAPsac instance. The |S| is bounded by O(|C| 2 |L| 2 ), which is O(|P | 4 ) in the worst case.
Proof. As in Section 3.2.2, any feasible hyperectangle S ∈ S is defined by a tuple (α S , β S , γ S , ω S ) of latitudes and longitudes corresponding to the left, right, bottom, and top borders of S, respectively, with α S , β S ∈ C and γ S , ω S ∈ L, and such that α S ≤ β S and γ S ≤ ω S . Therefore, S = C × C × L × L. Since 1 ≤ |C| ≤ |P | and 1 ≤ |L| ≤ |P |, |S| is bounded by O(|P | 4 ).
In particular, the photos are commonly spread across the target region in a grid pattern to fulfil photo footprint overlapping constraints [67]. Consequently, |C| and |L| are usually far smaller than |P |, and hence, |C| 2 · |L| 2 is in practice usually significantly smaller than |P | 4 .
Let S p be the collection of rectangular subsets S ∈ S which cover photo p ∈ P . For each set S ∈ S, denote t S the photo processing time of S, and µ hd S the amount of data to transfer from drone h ∈ D to the drone d ∈D if S is selected. Let q S d be the binary variables equal to 1 if S is allocated to drone d ∈D. Finally, let us denote o S the auxiliary binary variable which is equal to 1 if S is selected, and 0 otherwise.
The region-based formulation of the CAP sac is expressed as follows: The objective function (36) minimizes the makespan T max , which is computed by constraints (37). Constraints (38) limit the networking delay for each photo transmission traffic demand. Constraints (39) impose that the selected subsets in S are assigned to σ drones which can do the 3D reconstruction. The set of constraints (40) ensures that each photo p ∈ P is covered at least once, and constraint (41) defines the number of selected subsets to m, i.e., the number of drones which can perform the 3D reconstruction. The transmission rates are defined by (42) and (21)

NP-Hardness of the CAPsac
The proof comes from a reduction of the decision version of the unweighted Geometric Set-Covering Problem -GSCP , whose objective is to assert, for a finite set of points P = {p 1 , p 2 , ..., p n ∈ R d } and a finite collection S of subsets of P , if there exists a covering for the points P composed by at most k < |S | sets of S , i.e., if there exists a C ⊂ S such that ∪ c∈C c = P and |C| ≤ k. The collection S is induced by a fixed polytope T , that is, S is formed by the points covered by the distinct placements of T over the coordinates of the points P . The decision problem is NP-Complete even when T is a fixed square [70] or a fixed circumference [71]. Proposition 2. Given an instance I of the GSCP , there exists a polynomial-time transformation from I to an instance I of the rCAP sac.
Proof. Consider an instance of the GSCP with P points, a collection S of subsets of P induced by a fixed square of length s, and a positive integer k < |S |. The instance of the rCAP sac is created on polynomial-time as follows.
Let the set of photos P and their location be equal to the set of points P (i.e., P = P ), and consider a set of k drones which can do the 3D reconstruction, i.e., |D| = |D| = k. The communication network T = (N, A) is a random tree whose links (i, j) ∈ A have infinite capacity. Therefore, the transmission times, the transmission rates φ hd , and the photos storage location θ dp can be dismissed. Thus, the latest completion time T max is defined only by the photo processing times of the drones. Concerning the reliability factor, it is made equal to 1 (σ = 1). Indeed, the collection S does not have all possible rectangular spatial-convex sets, being the S \ S missing spatial-convex sets obtained in polynomial-time by inspecting the tuples in C × C × L × L. Finally, the photo processing times of the spatial-convex sets will be either 1 or +∞. For S ∈ S , t S = 1, while for the remaining S ∈ S \ S t S = +∞. Proof. Consider rCAP sac(P, D, T, S) a routine which solves the CAP sac by the rCAP sac formulation (Section 3.3). Let its optimal solution be comprised by the optimal set Q * of variables q S d and the optimal completion time T * max . Given a solution of an instance of the CAP sac created from an instance of the GSCP , evaluating T * max is enough to answer the GSCP . If T * max = 1, reply yes. Otherwise, reply no. For an optimal solution whose T * max = 1, the covering C of the P , with |C| ≤ k, can be extracted from Q * .
Proof. Given the propositions 2 and 3, one can state that the GSCP is no harder than the CAP sac. Since the GSCP is NP-complete, the CAP sac is NP-Hard.

Computational experiments
Our experimental analysis assessed (i) the effectiveness of the ordering inequalities and the branching strategies for the pCAPsac formulation; (ii) the performance of formulation pCAPsac; (iii) the sensitivity of the pCAPsac formulation with respect to both reliability factor σ and maximum allowed transmission timeT . We used CPLEX v12.8 as generalpurpose linear programming solver. All experiments were carried exploiting a single core on a machine powered by an Intel E5-2683 v4 Broadwell 2.1GHz with 20Gb of RAM, and running the CentOS Linux 7.5.1804 OS.
We do not present computational experiments for formulation rCAPsac. As demonstrated in Section 3.3, the number of variables of that formulation is bounded by O(|P | 4 ), which can rapidly increase. Column Generation (CG) strategy has been extensively applied to formulations with a massive number of variables [72]. The great advantage of employing CG is to solve the Linear Program (LP) continuous relaxation considering only a relevant subset of variables. Such LP with reduced number of variables is called the restricted master problem (RMP). The subset of relevant variables is iteratively created as needed by solving the so-called pricing subproblem (PS). Usually, a CG iteration comprises: i) solving the current RMP to obtain current primal optimal solution and its associated dual variables, and ii) optimizing the PS to find new variables with negative reduced costs (when considering minimization problems). The CG terminates when the PS does not find any variable with negative reduced cost, i.e., when the optimality of the current RMP has been proved. Preliminary experiments (restricted to σ = 1 andT = +∞) were performed applying a vanilla column generation on the rCAP sac. Unfortunately, rCAP sac has proved highly degenerate requiring several CG iterations to prove optimality. Therefore, its performance for solving CAPsac was largely inferior to that of using the pCAPsac formulation. Finally, note that the above degeneragy is a common CG drawback that leads the resulting algorithms (and codes) to be difficult to tune and somehow delicate, thus incompatible for the applied context we deal with.

Tested instances and computational settings
The instances, which were constructed from realistic data, comprise two scenarios: i Unweighted: all photos require the same amount of processing time λ.
ii Weighted: each photo p ∈ P requires a certain amount of processing time λ p .
The λ p are acquired from the equivalent unweighted case: |P | × 0.1 groups of nine adjacent photos are randomly selected, and then, for each of those groups, a single λ p is drawn from a normal distribution (µ = 26.72 seconds and σ = 5.0) and attributed to all photos of that group. Changing the photo-processing time in that fashion allows to represent the 3D reconstruction of distinct complex objects in the region of interest. The name of the instances follows the notation X-PYYDZ%DWW where "X" is "u" for the unweighted instances and "w" for the weighted instances, "YY" stands for the number of photos in the instance, "Z" specifies the number of drones in the swarm, and "WW" informs the percentage of drones that can do 3D reconstruction. The number of drones able to perform 3D reconstruction, called |D|, is always equal to Z × W W 100 . The characteristics of the tested instances are listed in Table 2.
The tables presented hereafter report the instance employed at each row (column "Instance"), the corresponding formulation (column "Form."), the dual gap (in percentage) wrt the optimal solution found at the root node (column "gap 0 "), the number of cuts added by CPLEX at the root node (column "cuts"), the number of nodes explored by the CPLEX's branch-and-cut method (column "Nodes"), and the dual gap (in percentage) wrt the optimal solution (best known, see below) at the end of the branch-and-cut enumeration (column "gap"). CPU times spent in the solution of the root node and by the branch and cut algorithm are also reported (column "sec.").
Note that dual gaps are computed with respect to the best upper bound solution found whenever the optimal solutions are not obtained by CPLEX within one day of execution. These situations are represented in the tables by the symbol ' * '.

pCAPsac experiments
This section evaluates the performance of the proposed pCAPsac formulation. It investigates the effectiveness of valid inequalities (16)- (19), whose aim is, for any possible sub-region, to clean the search space from all the infeasible boundary configuration. Also, the experiments analyze how different branching priorities can influence the branch-andcut method. All the experiments of this section are for σ = 1 andT =+∞.

pCAPsac performance
The pCAPsac formulation using the BC 0 constraints (14), called "P B:BC 0 ", and the pCAPsac formulation using the BC 0 constraints (15), named "P B:BC 0 ", are compared in Tables 3 and 4. Table 3: CPLEX results when solving unweighted instances for the "P B:BC 0 " and the "P B:BC 0 " formulations.

Instance
Form.
Root Node Branch-and-Cut gap 0 cuts sec. Nodes gap sec.  Table 4: CPLEX results when solving weighted instances for the "P B:BC 0 " and the "P B:BC 0 " formulations.

Instance
Form. Root Node Branch-and-Cut gap 0 cuts sec. Nodes gap sec.
We can observe that the dual gaps at the root node are equal to zero for the unweighted instances whenever the number of photos is divisible by the number of drones that can do the 3D reconstruction. Consequently, the objective function value of the optimum solution coincides with the dual bound already at the root node for instances "u-P200D5%D90", "u-P200D7%D70", "u-P400D5%D90", "u-P400D7%D70", "u-P200D10%D50" and "u-P400D10%D50".

Ordering inequalities effectiveness
The effect of adding all the ordering inequalities (16)- (19) into the "P B:BC 0 " formulation is analyzed in Tables 5 and  6. The inclusion of the ordering inequalities is identified by the "+Ord." in the formulation name. Table 5: CPLEX results when solving unweighted instances for the "P B:BC 0 " and the "P B:BC 0 +Ord." formulations.  Table 6: CPLEX results when solving weighted instances for the "P B:BC 0 " and the "P B:BC 0 +Ord." formulations.

Instance
Form.  The valid inequalities (16)- (19) eliminate infeasible boundaries in the continuous solution space whereas not necessarily excluding the continuous optimum solution. Consequently, these inequalities are not guaranteed to increase the dual bound obtained. In fact, gap 0 was never improved in our experiments after adding the ordering inequalities. Nevertheless, the insertion of (16)- (19) improved the CPU time required to reach the optimum solution of 11 out to 19 instances solved to optimality (considering 2h of execution). In fact, paired t-tests show significant improvements (T= 1.907 p-val= 0.034) by adding them into the "P B:BC 0 " formulation, except for instances "P400D7%D70". However, when limited to weighted cases, there is no significant improvement on reducing the enumeration CPU time. For these cases, 11 seconds of improvement is obtained when comparing the average computing CPU time of non-inserting against inserting constraints (16)- (19). Finally, we observed that the number of cuts added by CPLEX at the root node increased considerably when the ordering inequalities were employed.

Branching priority
Different branching priorities for the selection of the boundary assignment (i.e., α r c , β r c , γ r , and ω r ) and the photo assignment (i.e., y r p ) variables were also explored in formulation "P B:BC 0 +Ord." (simply denoted "P B:BC 0 " at this section) and the results reported in Tables 7 and 8. The distinct branching priorities are denoted as "b>y" and "y>b". The the default option of CPLEX is identified by the absence of those notations. The "b>y" is used when the boundary assignment variables are given higher priority over the photo assignment variables, which still have higher priority over the remaining variables. The "y>b" refers to the opposite case, that is, when photo assignment variables are rather branched over boundary assignment variables. Table 7: CPLEX results when solving unweighted instances for the "P B:BC 0 ", "P B:BC 0 −b>y" and "P B:BC 0 −y>b" branching priority strategies.

Instance
Form.
Branch-and-Cut Nodes gap sec.  Table 8: CPLEX results when solving weighted instances for the "P B:BC 0 ", "P B:BC 0 − b>y" and "P B:BC 0 − y>b" branching priority strategies.

Instance
Form. The adoption of different branching priorities improves the CPU times to solve some instances. In fact, the "y>b" strategy achieves better or equivalent CPU times in 10 out to 11 unweighted instances solved to optimality (within 2h of execution). Regarding weighted cases, the "b>y" strategy results in better or equivalent CPU times in 5 out to 8 instances solved to optimality (considering 2h of execution). However, paired t-tests do not show significant improvement for both "b>y" (T= 0.889 p-val= 0.191) or "y>b" (T=1.295 p-val= 0.103) strategies considering overall cases.

Sensitivity of the pCAPsac formulation
This section evaluates the sensitivity of pCAPsac formulation with respect to both reliability factor σ and to maximum transmission time allowedT .

Reliability factor sensitivity
Tables 9 and 10 report results for various values of σ, ranging from 1 to |D| − 1. The subset of instances used in this experiment consists of those for which CPLEX was able to solve within 2h of execution the associated problem with σ = 1. Besides, the communication constraints concerningT were relaxed, i.e.T =+∞.  Tables 9 and 10 show that initial dual gaps are largely affected by σ. Those large dual gaps result from the increase of the optimum solution values with σ not accompanied by the increase in the dual bounds obtained at the root node. This is illustrated in Fig. 5 and Fig. 6, where the changes in the optimal objective function value (named "T max ") given the increase of σ are presented for unweighted instances "u-P200D7%D70", "u-P200D10%D50", "u-P200D7%D90", and for weighted instances "w-P200D7%D70", "w-P200D10%D50", "w-P200D7%D90". Those instances were selected to include distinct values of |D|.

Maximum transmission time sensitivity
The sensitivity analysis of formulation "P B" to parameterT is performed by decreasing its values progressively (the value of σ is fixed to 1 in this set of experiments). The first value ofT tested corresponds to the allocated communication time between the drones when no time limit is imposed for their communication, i.e.,T =+∞. From that value,T is decreased by 0.5 seconds until formulation "P B" becomes infeasible. Fig. 7 and Fig. 8 present results for instances "u-P200D5%D70" and "w-P200D5%D70". For them, the first value ofT is 48 seconds, being decreased down to 23.5      The decreasing ofT tends to reduce the number of nodes explored in the branch-and-cut enumeration whereas the objective function value increases until the problem becomes infeasible. For example, in Fig. 7, the optimum objective function value increases from 1870.4 to 2939.2 starting atT = 33.5. The problem becomes infeasible forT smaller than 24s.

Conclusion
A swarm of drones (UAVs) can be used to automate a wide range of missions, from surveillance to search and rescue, from 3D mapping to telecommunication enhancement. While UAVs are typically responsible for the mission phases related to data collection -thanks to their flying capabilities and to the availability of embedded sensors -most of the data processing is offloaded to dedicated machines (virtual or bare-metal) placed in the cloud. However, when the communication bandwidth between the swarm and the cloud is limited, an ad-hoc cloud established on top of the UAVs' computing resources (and those of other elements available in the area) can be leveraged to replace the cloud and keep data processing local.
For the purpose of optimizing the use of such ad-hoc cloud infrastructure powered by the swarming UAVs, we introduced a new optimization problem, namely the Covering-Assignment Problem for swarm-powered ad-hoc clouds -CAPsac, based on a real-life use-case in the emergency management field: swarm-powered distributed 3D reconstruction for humanitarian emergency response. After having established the relationship between the general problem and the specific use-case, we presented the NP-Hardness proof of the CAPsac and described two MILP formulations for it.
Given a set of geo-positioned aerial pictures (data) that are subject to geolocation/clustering constraints, CAPsac minimizes the 3D mapping (data-processing phase) completion time by jointly computing: (i) the optimal covering of photos (workload configuration), and (ii) the optimal assignment of photographed sub-regions (workload assignment) to UAVs (computing elements). Besides being a way to provide optimal solutions for the problem, our integrated decision model contrasts with the decompose-then-allocate and the allocate-then-decompose paradigms usually seen in (both the cloud computing optimization and) the multi-robot task allocation literature. Finally, modeling CAPsac in this way is flexible and amendable to take into account any other additional ground computing elements connected to the swarm itself.
In order to assess the proposed formulations, a series of computational experiments was conducted with a set of unweighted and weighted realistic benchmark instances available online (https://github.com/ds4dm/CAPsac). The experiments revealed that the photo-based formulation "P B" was more efficient by using ordering inequalities that remove from the feasible continuous search space those sub-regions whose boundaries are not regular (e.g. left boundary at the right of a right boundary). However, the different branching priority strategies and row generation methods have not proven to yield a performance gain while solving "P B". Column Generation was employed in the region-based formulation "RB", but the presence of highly degenerate optimums led to long execution times.
Finally, the sensitivity analysis of the formulation "P B" showed that it becomes more difficult to solve as the reliability factor σ increases. Tests with varying values for the maximum allowed transmission timeT also presented a slight gain of performance asT approaches a limit when the problem becomes infeasible.