11institutetext: LIGM, Ecole des Ponts, Univ Gustave Eiffel, CNRS, Marne-la-
Vallée, France 22institutetext: SYRTE, Observatoire de Paris-PSL, CNRS, Paris,
France
22email<EMAIL_ADDRESS>

# Historical Astronomical Diagrams
Decomposition in Geometric Primitives

Syrine Kalleli 11 Scott Trigg 22 Ségolène Albouy 22 Mathieu Husson 22 Mathieu
Aubry 11

###### Abstract

Automatically extracting the geometric content from the hundreds of thousands
of diagrams drawn in historical manuscripts would enable historians to study
the diffusion of astronomical knowledge on a global scale. However, state-of-
the-art vectorization methods, often designed to tackle modern data, are not
adapted to the complexity and diversity of historical astronomical diagrams.
Our contribution is thus twofold. First, we introduce a unique dataset of 303
astronomical diagrams from diverse traditions, ranging from the XIIth to the
XVIIIth century, annotated with more than 3000 line segments, circles and
arcs. Second, we develop a model that builds on DINO-DETR to enable the
prediction of multiple geometric primitives. We show that it can be trained
solely on synthetic data and accurately predict primitives on our challenging
dataset. Our approach widely improves over the LETR baseline, which is
restricted to lines, by introducing a meaningful parametrization for multiple
primitives, jointly training for detection and parameter refinement, using
deformable attention and training on rich synthetic data. Our dataset and code
are available at our project webpage:
http://imagine.enpc.fr/~kallelis/icdar2024/.

###### Keywords:

Vectorization Historical diagrams Transformers

Figure 1: Goal.  We perform historical astronomical diagram vectorization by
predicting simple geometric primitives, such as lines, circles, and arcs,
through a transformer encoder-decoder model. Our modified decoder queries,
which we refer to as a primitive queries, are associated to different
geometric primitives.

##  1 Introduction

Astronomical diagrams offer a unique perspective to understand the diffusion
of astronomical knowledge over centuries of Afro-Eurasian history. Thousands
of digitized manuscripts with hundreds of thousands of diagrams are available.
We aim to provide automatic tools to analyze their content. More precisely, we
want to vectorize historical diagram images into a set of parameterized
geometric primitives, namely line segments, circles, and arcs, as shown in
Figure 1. Such a representation of diagrams would enable effective semantic
similarity search and would serve as an important tool for historians to
create critical editions of astronomical treatises.

Inferring vector primitives from raster drawings is a long-standing problem in
computer vision. Early works address this raster-to-vector task for
architectural plans [10] and for clean technical drawings [17] through a
multi-step process for line and arc detection. Several optimization approaches
[2, 12, 3] have been developed and deep learning methods [21, 11, 26] have
shown impressive results on rougher drawings. Recently, models based on the
DEtection TRansformer (DETR) [5] have demonstrated superior performances for
line detection [39], floor plan reconstruction [40], dashed curve recognition
[23], image vectorization [6], and primitive parameter inference [37].
However, these methods are constrained to clean input images typically
rendered from vector format such as technical diagrams [33, 37] or icons and
emojis [30, 6].

In this work, we introduce a challenging dataset of 303 historical
astronomical diagrams extracted from manuscripts and Chinese woodblock prints
of the Middle Ages and modern period annotated by historian experts. Even
state-of-the-art deep models such as LETR [39] struggle with such data and
most approaches only detect a single kind of primitive. We thus present a
transformer-based vectorization method which, opposite to prior work [37, 23,
33], (i) jointly predicts line segments, circles, and arcs and (ii) adopts
deformable attention [42] in an iterative primitive-refinement scheme, that
significantly speeds up training convergence and enables fine-grained
primitives localization. Note that our parameter refinement scheme can be
seamlessly extended to support other geometric primitives which could be
beneficial for other vectorization applications. Our model is trained solely
on rich synthetic data and we demonstrate that it generalizes to our
challenging dataset. Our dataset and code are available at our project
webpage: http://imagine.enpc.fr/~kallelis/icdar2024/.

In summary, our two main contributions are:

  * •

A diverse dataset of 303 astronomical diagrams from Arabic, Latin, Greek,
Hebrew, and Chinese manuscripts, ranging from the XIIth to the XVIIIth
century, annotated by historians with more than 3000 line segments, circles,
and arcs.

  * •

A transformer-based model for diagram vectorization that iteratively refines
query primitive parameters using deformable attention and can jointly detect
lines, circles, and arcs.

##  2 Related work

In this section, we start by reviewing general works on drawing vectorization.
As the basis of our approach, we then discuss transformer-based detection,
which is the foundation for many recent vectorization techniques [6, 37, 23,
22], including our method. Finally, we briefly present works related to
historical diagrams.

####  2.0.1 Drawing vectorization.

While our primary focus is the vectorization of line-drawings and sketches, we
occasionally refer to works for image vectorization that are particularly
relevant [6, 39, 30].

Approaches to vectorize line-drawings can be roughly categorized in two
categories: optimization-based and learning-based.

##### Optimization-based approaches.

Initial efforts in diagram vectorization [17] target technical diagrams
composed of straight lines and circular arcs. The approach of [17] extracts a
1-pixel wide skeleton and junctions from a clean black-and-white image, fits
primitives through local optimization, and refines the output by merging
predictions using heuristics. The methods in [12, 9] extend this pipeline to
extract Bézier curves from input sketches and introduce a global optimization
scheme. Many follow-up works [2, 35, 29, 15] shift to frame fields to favor
robustness, assigning two directions to each pixel in the image, to guide
curve extraction. A fundamental issue of these multi-step processes is that
they are prone to error accumulation, which is especially likely with rough
sketches. They also often require hyperparameter adjustments, and since
optimization happens for each image, they can be time-consuming. Thus, most
recent approaches for vectorization rely instead on machine learning, and in
particular deep learning.

##### Learning-based approaches.

A first set of methods use deep learning to replace parts of a multi-step
pipeline. For example, [21] outputs vectorized, semantically annotated floor
plans from raster images by using a CNN for junction detection and generating
primitive proposals which are then post-processed into vector objects.
Similarly, [18] learns a pixel-level segmentation of line-art strokes and then
uses Potrace [34], a third-party tracing tool, and [26] learns junctions, then
reconstructs the topology and vectorizes using least-squares fitting.

A second set of methods directly predicts primitive parameters from the input
image. Some works predict Bézier or spline-based curves using either RNNs[14,
30] or Transformers [22, 23, 11], which enables modeling complex shapes. More
closely related to our goal are works that aim at predicting a fixed set of
simple geometric primitives. Several methods [33, 37, 28, 13] target CAD
designs [32], and PMN [1] predicts sketch strokes. LETR [39] focuses on line
segment detection in natural scenes but was particularly influential for
recent vectorization works. It introduces a transformer encoder-decoder model
built upon the DEtection TRansformer [5] (DETR), which we discuss in the next
paragraph. The method in [6] adopts DETR to reconstruct images from basic
geometric primitives such as rectangles and circles in a self-supervised
manner. Very recently, PPI-Net [37] proposed a DETR-like model with denoising
groups [19] for vectorizing simple CAD designs into lines, circles, arcs, and
points. However, these models based on DETR are very slow to train and are
typically constrained to specific primitive types [39, 37] or very simplistic
image domains [6, 37, 33, 28, 13]. In contrast, we adopt several improvements
to the DETR model which speed up training. Aditionally, we propose a method
that jointly handles lines, circles, and arcs, but can be easily extended to
support more primitive types.

####  2.0.2 Transformer-based detectors

DETR [5] casts object detection as an image-to-set problem and employs a
transformer encoder-decoder architecture to produce a set of box predictions.
The DETR framework is general and has proven to adapt to several tasks but it
suffers from slow convergence and poor performance on small objects.
Deformable-DETR [42] uses multi-scale features and introduces deformable
attention to significantly speed up convergence. Most follow-up works adopt
deformable attention and further speed up training by incorporating spatial
priors in the queries [24, 25, 38] or stabilizing Hungarian matching [19, 41].
The most relevant to our work are (i) Dab-DETR [24], which dynamically refines
anchor boxes instead of object queries, further improving training speed; (ii)
DN-DETR [19], which adds a denoising branch to the decoder; (iii) DINO-DETR
[41], which achieves state-of-the-art results through several innovations,
including contrastive denoising. Our method can be seen as formulating
primitive detection in such a way that it can be performed with an approach in
the spirit of DINO-DETR.

####  2.0.3 Historical diagrams.

Historical document datasets typically favor textual, tabular, and image
content, often overlooking diagrams. A recent exception is the S-VED dataset
[4], a large heterogeneous collection of illustrations featuring many printed
astronomical diagrams. Unfortunately, this dataset is not labeled with
geometric primitives. There are however works addressing other challenges
related to deteriorated historical drawings, including sketches and
architectural plans. Many works focus on restoration, for example the method
in [31] focuses on line drawings, while a VQ VAE proposed in [8] restores aged
hand-drawn architectural plans. Closer to our task, [36] presents a CNN-based
wall detection method on ancient floor plans and [7] designed a three-step
optimization process to convert a raster image of a historical map into a set
of polygons.

##  3 Approach

Figure 2:  Model architecture. Given an input image, the backbone extracts
multi-scale features which are fed to the Transformer encoder along with a
positional encoding. The primitive queries, composed of content (filled) and
modified positional (empty) queries, go through the Transformer decoder where
they probe the enhanced encoder features through deformable cross-attention.
Queries are refined layer-by-layer in the decoder, to finally predict the
primitive class, bounding box and parameters.

###  3.1 Model overview and notations

Given an input image of a diagram, our goal is to output the set of primitives
shapes present in the input together with their parameters. We focus on three
primitive classes, Line, Circle, and Arc, but our model could be extended to
more classes. We write $\mathcal{C}$ the set of primitive classes, including a
specific “no primitive” class we write $\emptyset$. Each primitive class
$c\in\mathcal{C}$ is associated to a vector of geometric parameters $g[{c}]$,
where the length of the vector $m[c]$ can be different for each class and is
by convention $0$ for the “no primitive” class.

####  3.1.1 Architecture

To address our image-to-set problem, we use the transformer encoder-decoder
architecture outlined in Figure 2. This is similar to LETR [39], but instead
of using a two-stage coarse-to-fine strategy to perform fine-grained
detection, we demonstrate how to leverage Multi-Scale Deformable (MSD)
attention [42] for geometric primitive prediction. In general, we follow the
standard end-to-end DETR-like architecture but we adapt several improvements
from DETR-variants, notably DINO-DETR [41] to boost speed and performance.

A CNN backbone first extracts multi-scale features from the input image which
are subsequently concatenated with a positional embedding. A standard
transformer encoder then processes these features using 6 encoder blocks based
on MSD self-attention. It outputs both an initial set of $N$ modified
positional queries that will be used as initialization by the decoder and
enhanced multi-scale image features which are then used by the transformer
decoder as keys and values in cross attention. Our modified transformer
decoder concatenates learned content queries to the positional queries
provided by the encoder (mixed query selection [41]) and processes them
successively in 6 modified decoder blocks using MSD self-attention and MSD
cross-attention with the encoder image features. These modified decoder blocks
can be seen as iteratively refining the predictions, until the final
predictions are made by a last feed-forward network, and are detailed in
Section 3.2.

####  3.1.2 Primitive queries

We index the $N$ modified decoder queries, which we refer to as primitive
queries, by $n\in{1,...,N}$ and for each query, we will predict:

  * •

probabilities $p_{n}$ of the prediction to be associated to each primitive
class, including the “no primitive” class $\emptyset$.

  * •

a bounding box $b_{n}\in[0,1]^{4}$ relative to the image size.

  * •

parameters $g_{n}[{c}]\in[0,1]^{m[c]}$ relative to the image size for all
classes $c$, which are concatenated into $g_{n}\in[0,1]^{d}$, with
$d=\sum_{c\in\mathcal{C}}m[c]$.

Note that the bounding box could be predicted from the parameters
$g_{n}[{c_{n}}]$, but having a class-independent bounding box is necessary to
correctly define MSD attention. This novel positional query parametrization is
critical to our primitive refinement detailed in Section 3.2 and our losses
discussed in Section 3.3.

Figure 3: Modified Positional Queries. All coordinates are normalized with
respect to the image size. The bounding box is defined by its center and size.
Lines are defined by endpoints, circles by center and radius (normalized by
image width, $r_{x}$, and by image height, $r_{y}$), and arcs by endpoints and
midpoint.

###  3.2 Primitive Refinement

Our transformer decoder’s core mechanism revolves around refining primitives
iteratively, and is inspired by successful object detectors like Deformable-
DETR [42] and DAB-DETR [24]. These detectors have shown the effectiveness of
updating box parameters layer-by-layer. Motivated by this paradigm, our
approach refines at each decoder layer $l$ both the primitive bounding box $b$
and primitive parameters $g$ for all queries. Each layer receives an initial
estimate of $b^{l}$ and $g^{l}$, and predicts updates $\Delta b^{l}$ and
$\Delta g^{l}$, which are used to refine the estimates. In the following, we
first detail the parameterization of the primitive bounding box $b$ and
parameters $g$, then explain how we perform the parameter update in each
decoder layer as illustrated in Figure 4.

####  3.2.1 Modified content queries parametrization

Our parameterization of the decoder positional queries is depicted in Figure
3. All values are normalized by the width and height of the image. We use the
standard parametrization of the bounding box using its center, width and
height. We concatenate these bounding box parameters $b$ to the
parameterizations $g{}$ corresponding to the different primitive types. For
line segments, we use the coordinates of the extremities in arbitrary order.
For circles, we use the center as well as the radius normalized by the image
width and by the image height. For arcs, we use the coordinates of both
extremities in arbitrary order and the coordinates of the arc middle point.
Using the primitive bounding box alongside the primitive parameters offers two
key advantages. Firstly, it enables deformable attention, guiding sampling
locations for queries using the bounding box in a way agnostic to the
primitive class. Secondly, this approach does not constrain the model to a
specific set of primitives or a specific parameterization, making it readily
extendable to other geometric primitives, opposite to the joint
parameterization used in PPI-Net [37] which shares the parameterization for
several primitives.

####  3.2.2 Modified transformer decoder block

A decoder block along with an example of primitive refinement can be seen in
Figure 4. At each decoder layer $l$, the input is a set of primitive queries
composed of a content query and a modified positional query $(b^{l},g^{l})$.
At the beginning of the block, they are combined by summing the content query
with an encoded positional query, obtained by first concatenating the 2D
sinusoidal embedding of all the parameters of the positional query then
processing this concatenated vector with a Multi-Layer Perceptron (MLP). Note
that this can be done for any number of primitive classes and any length of
parametrization for the different classes.

Figure 4:  Primitive refinement. Each modified decoder block (left) updates
the positional query $(b^{l},g^{l})$, which progressively refines predictions
(right).

The queries interact in the self attention module then probe the image
features where the predicted box is used as a reference box for deformable
attention, making each query focus exclusively on relevant regions of the
image. The output of the decoder layer passes through a MLP to generate an
update $(\Delta b^{l},\Delta g^{l})$ relative to the previous estimate
$(b^{l},g^{l})$. Similarly to [42, 41], the refined box and parameters are
defined as:

$b^{l+1}=\sigma(\Delta b^{l}+\sigma^{-1}(b^{l})),\quad g^{l+1}=\sigma(\Delta
g^{l}+\sigma^{-1}(g^{l})),$ (1)

where $\sigma$ is a sigmoid. We find this refinement strategy particularly
suitable for our vectorization task, where precise parameter predictions are
crucial and we validate the importance this approach in Section 5.

###  3.3 Losses

Our model outputs a fixed number of predictions $N$ typically much larger than
the number of ground-truth primitives. To simplify the notations, we add “no
primitive” elements to the ground truth so that we also have $N$ ground truth
for each image. Given $n\in\\{1,...,N\\}$, we have $(p_{n},b_{n},g_{n})$ the
predictions associated to query $n$ and we call
$(c_{n}^{gt},b_{n}^{gt},g_{n}^{gt})$ the $n$-th ground truth, with
$c_{n}^{gt}$ its class, $b_{n}^{gt}$ its bounding box and $g_{n}^{gt}$ its
parameters, defined only for class $c_{n}^{gt}$.

##### Bipartite Matching

To define our training loss, we establish a one-to-one correspondence between
predictions and ground-truth, similar to the approach of DETR [5] but
considering the predicted primitive parameters. We use the Hungarian algorithm
to find the permutation ${\pi}$ which minimize the matching cost:

$\leavevmode\resizebox{433.62pt}{}{
$\displaystyle\sum_{n=1}^{N}\left(-\lambda_{\text{cls}}p_{n}[c_{\pi[n]}^{gt}]+\mathbf{1}_{\\{c_{\pi[n]}^{gt}\neq\emptyset\\}}\left(\lambda_{\text{box}}d_{\text{box}}(b_{n},{b}_{\pi[n]}^{gt})+\lambda_{\text{param}}d_{c_{\pi[n]}^{gt}}(g_{n}[c_{\pi[n]}^{gt}],g_{\pi[n]}^{gt})\right)\right)$},$
(2)

where $\lambda_{\text{cls}}$, $\lambda_{\text{box}}$, and
$\lambda_{\text{param}}$ are scalar hyperparameters, $d_{\text{box}}$ is
defined by

$d_{\text{box}}(b_{n},b_{\pi[n]}^{gt})=\left\lVert
b_{n}-b_{\pi[n]}^{gt}\right\rVert_{1},$ (3)

and $d_{c}$ is a distance function tailored to each primitive class. For each
primitive class $c$, we define $d_{c}$ as the minimum, over all equivalent
parametrizations, of the $L_{1}$ distance between the parameters normalized by
the number of parameters. For instance, in the case of lines, the distance
function $d_{\text{line}}$ is computed as the minimum over both permutations
of the endpoints of the $L_{1}$ distance between the predicted and ground-
truth endpoints, divided by 4. Unlike traditional object detectors, we do not
consider an intersection over union for $d_{\text{box}}$ to avoid instability
for vertical and horizontal primitives.

##### Loss

Once the permutation $\pi$ between predictions and ground truth is defined, we
compute the loss function for each query as a weighted sum of a classification
loss $\mathcal{L}_{\text{cls}}$, a box loss $\mathcal{L}_{\text{box}}$ and a
parameters loss $\mathcal{L}_{\text{param}}$:

$\mathcal{L}(p_{n},b_{n},g_{n})=\lambda_{c}\cdot\mathcal{L}_{\text{cls}}+\lambda_{\text{box}}\cdot\mathcal{L}_{\text{box}}+\lambda_{\text{param}}\cdot\mathcal{L}_{\text{param}},$
(4)

where where $\lambda_{\text{cls}}$, $\lambda_{\text{box}}$, and
$\lambda_{\text{param}}$ are scalar hyperparameters as in equation 2, we use
the focal loss [20] as classification loss $\mathcal{L}_{\text{cls}}$,

$\displaystyle\mathcal{L}_{\text{box}}$
$\displaystyle=\mathbf{1}_{\\{c_{\pi[n]}^{gt}\neq\emptyset\\}}d_{\text{box}}(b_{n},\hat{b}_{\sigma(n)}),\
\text{and}$ (5) $\displaystyle\mathcal{L}_{\text{param}}$
$\displaystyle=d_{c_{\pi[n]}^{gt}}(g_{n}[c_{\pi[n]}^{gt}],g_{\pi[n]}^{gt}),$
(6)

where $d_{\text{box}}$ and $d_{c}$ are the box and parameter distances defined
in the previous paragraph.

##### Contrastive denoising

Similarly to DINO-DETR [41], we also adapt contrastive denoising to speed up
convergence and improve performance by training a denoising decoder branch.
The architecture of this branch is the same as our decoder but content queries
are replaced by class labels, and it is trained in parallel without
information sharing. From ground truth primitive parameters and labels, we
create positive and negative noisy primitive queries, associated to two hyper
parameters $\lambda_{pos}$ and $\lambda_{neg}$ controlling the strength of the
added noise, more noise being added to the negative group. The primitive class
can also be noised through label flipping, the class of the primitive being
switched to another with probability $p_{\text{flip}}$, which we found to have
little impact on our results. The denoising branch is trained with the same
loss as the rest of the network.

((a)) Example diagrams

((b)) Diagrams’ origins

| #Primitives | #Images
---|---|---
Line | 1794 | 261
Circle | 955 | 263
Arc | 327 | 84
((c)) Primitive statistics

((d)) Number of primitives per image

Figure 5:  Dataset characteristics. Our diagrams have varying complexity and
several challenges are introduced by document deterioration, heavy presence of
text, and overlapping primitives.

###  3.4 Implementation and training details

Our feature maps are extracted from stages $C_{3}$ through $C_{5}$ of a
ResNet50 [16] pretrained on ImageNet-1k. A fourth feature map is extracted by
down-sampling the last stages features as done in [41]. A $1\times 1$
convolution reduces the channel dimensions to the hidden dimension of the
transformer $256$. We keep the standard $H=8$ heads and $k=4$ neighbors for
deformable attention [42]. We use a $6$-layer encoder and $6$-layer decoder.
Each decoder layer is followed by a shared $3$-layer FFN and each decoder
layer outputs its own loss similarly to the training scheme in DETR [5]. We
use $N=900$. The matching cost and loss hyperparameters are set to
$\lambda_{\text{cls}}=2.0$ and
$\lambda_{\text{box}}=\lambda_{\text{param}}=5.0$. We apply scale augmentation
by resizing the input images such that the shortest side is at least 480 and
at most 800 pixels while the longest is at most 1333. Additionally, we apply
instance-aware random crops that do not cut the diagrams, random flips, and
random 90 degree rotations. We train for $12$ epochs, defined as 2000 gradient
steps, with batches of size 4, generating synthetic data on the fly, and using
an initial learning rate of $10^{-5}$ for the backbone and $10^{-4}$ for the
rest of the network, where both learning rates are divided by 10 at epoch
$11$. Our training lasts approximately $12$ hours on an A6000 GPU. Our code
will be made available after publication.

##  4 Dataset

##### Diagrams selection and annotation

Our team of historians has curated a dataset of 303 diagrams so that it
spanned diverse relevant traditions for the history of astronomy, namely
Arabic, Latin, Hebrew, Byzantine, Sanskrit, Chinese, and Greek sources.
Examples of diagrams from different traditions are presented in Figure 5(a)
and the proportion of diagrams from each tradition is shown in Figure 5(b).
This dataset includes diagrams from 27 distinct documents from the 12th to the
18th century, most of them manuscripts as well as a few Chinese woodblock
prints (which were common in ancient China). This ensures a broad diversity of
content, representations, scripts, styles, materials, digitization quality,
and conservation state. These diagrams were annotated by the historians with
circles, arcs and line segments relevant for their analysis, which resulted in
a total of 3076 annotated primitives, summarized in Figure 5(c). There is a
high variation in the number of primitive per diagram, which can be seen in
Figure 5(d), where we show the number of each type of primitive for the
different images. This dataset was used solely to evaluate our algorithms, not
for training.

|  |  |  |
---|---|---|---|---
|  |  |  |
Figure 6: Primitive distance examples. We display for each prediction (green)
the closest ground-truth (red) and the distance $\delta$ between them. By
default, we set the threshold to define valid predictions to
$\delta_{\text{max}}=4$, for which examples on the top row are considered true
positives, and all examples on the bottom row are false positives.

##### Evaluation metrics

Given a set of primitives, we first match predicted primitives to the closest
ground truth. Then, for each ground-truth, we consider the closest predicted
primitive a True Positive if its distance $\delta$ is less than a predefined
threshold $\delta_{\text{max}}$. All other predictions are considered False
Positives. We define the evaluation distance $\delta$ between primitives as
the average of the point-wise $L_{2}$ distance between a set of predefined
point depending on the primitive type in the image resized to $128\times 128$
pixels: the endpoints for lines, the four cardinal points for circles, and the
endpoints and middle point for arcs. Unless stated otherwise, we use
$\delta_{\text{max}}=4$ as our threshold. Examples illustrating this
evaluation distance and true and false positives for each primitive type are
visualized in Figure 6, giving a sense of the prediction accuracy necessary to
be considered a true positive.

##### Synthetic training data

Because annotating geometric primitives in complex examples is very time
consuming, we train our models relying solely on dynamically generated
synthetic examples. Here, we outline the key elements of this generation
process, and we show a sample of generated synthetic data in Figure 7. Our
data generation code is available on our project webpage. We leverage the
resources of backgrounds, text, and glyph fonts proposed in [27]. To generate
an example, we first randomly sample a background randomly and add floating
words, random numbers and glyphs in different fonts. We then generate a
diagram by generating line segments, circles and arcs. Because there is very
little chance that randomly generated primitives would generate challenging
configurations often present in diagrams, we sample with higher probability
specific configurations such as co-centric and tangent circles, parallel
lines, and connected arcs which share one or two endpoints. These primitives
are drawn with random opacity variation, random width and colors on the
backgrounds. Circles can be filled or hollow. Finally, we add Gaussian blur,
structured noise though randomly generated shapes, random resizing, and we
chip small regions of the final diagram in order to simulate historical
document degradation.

Figure 7: Synthetic dataset examples. While our synthetic samples are not
realistic, they are challenging enough for the network to generalize to real
diagrams.

##  5 Experiments

Table 1: Model comparison and ablation. The terms DA, QS and CDN denote Deformable Attention, Query Selection and Contrastive DeNoising. Model | Scales | DA | QS | CDN | $\text{AP}_{\text{line}}$ | $\text{AP}_{\text{circle}}$ | $\text{AP}_{\text{arc}}$ |  mAP
---|---|---|---|---|---|---|---|---
LETR [39] | 2 |  |  |  | $0.263$ | - | - | -
LETR-line (our data) | 2 |  |  |  | 0.371 | - | - | -
LETR-circle (our data) | 2 |  |  |  | - | 0.754 | - | -
Ours | 4 | ✓ | ✓ | ✓ | 0.764 | 0.917 | 0.483 | 0.722
w/o primitive refinement | 1 | $\checkmark$ |  |  | 0.490 | 0.841 | 0.262 | 0.531
w/o multi-scale features | 1 | ✓ |  | ✓ | 0.599 | 0.887 | 0.216 | 0.567
w/o denoising | 4 | ✓ | ✓ |  | 0.739 | 0.904 | 0.452 | 0.698
w/o label flipping | 4 | ✓ | ✓ | ✓ | 0.759 | 0.903 | 0.494 | 0.719
w/ pure query selection | 4 | ✓ | ✓ | ✓ | 0.756 | 0.917 | 0.476 | 0.717
w/o query selection | 4 | ✓ |  | ✓ | 0.729 | 0.904 | 0.390 | 0.674

We report our main quantitative results in Table 1, using AP with threshold
$\delta_{\text{max}}=4$ as explained in Section 4. We compare models for
varying $\delta_{\text{max}}$ thresholds in Figure 9, which enables a finer
analysis of the precision of each model. Figure 8 illustrates qualitative
comparisons on $7$ randomly selected diagrams.

##### Baselines

We compare our model to the LETR [39] model, the closest model to our work,
which expands DETR to perform line detection through a fine-to-coarse training
strategy. We report both the performance of the model released by the authors,
and the performance a LETR model re-trained with our dataset. We used
pretrained DETR weights which, as emphasized in the original paper, we found
necessary, and we train for 500 epochs in the coarse stage and for 200 epochs
in the fine stage, which made training last approximately $150$ hours,
significantly longer than our model’s training time. We also adapt LETR to
perform circle detection by modifying the prediction head to output circle
parameters, while keeping the same coarse-to-fine training strategy.
Interestingly, we failed to adapt the LETR architecture for arcs in a similar
way. Note that we could not compare to PPI-net [37], which can predict
circles, line segments and arcs, because the code is not available, but this
architecture is based on DETR, required 72h training on 4 GPUs, and was only
demonstrated on small black and white images of CAD designs [32].

Unsurprisingly, Table 1 shows that our synthetic dataset is more adapted for
astronomical diagrams than the original LETR data. More interestingly, the
boost in performance when using our network compared to the LETR approach is
very significant, increasing the line AP from 0.371 to 0.764 and the circle AP
from 0.754 to 0.917.

|  |  |  |  |
---|---|---|---|---|---
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |
(a) Input | (b) GT | (c) Ours | (d) w/o QS | (e) w/o PR | (f) LETR
Figure 8: Qualitative results on a random sample of $7$ diagrams from our
dataset. The term PR denotes Primitive Refinement, while QS denotes Query
Selection.

Figure 9: Average Precision for different distance thresholds.

##### Ablation study

In our ablation study, we investigate the importance of several key components
of our model: (i) primitive refinement, which we ablate by directly predicting
parameters with an encoder-only model; (ii) multi-scale feature maps, which we
ablate by only using the last feature map of the backbone; (iii) contrastive
denoising, which we ablate both completely (w/o denoising) or by only removing
the label-flipping noise (w/o label flipping); (iv) our primitive query
initialization (mixed query selection [41]), which we also ablate in two ways,
by either initializing both content and positional queries with the encoder
(w/ pure query selection [42]), or removing completely the query selection and
directly learning the queries as parameters (w/o query selection).

Table 1 shows that using multi-scale features is critical to the success of
our approach. This is clearly shown in the qualitative results in Figure 8,
with clearly inaccurate or some missing predictions. Contrastive denoising and
query selection also both have significant impacts on our result, which Figure
9 enables to better analyze: they improve the precision of the predictions,
which can be seen by looking at the AP using low thresholds $\delta$. Figure 8
shows that in addition to lower accuracy, not using query selection also
translates in the qualitative results by the presence of duplicate or missing
primitives. On the contrary, using label flipping or initializing the complete
queries from the encoder does not impact the results significantly.

##### Limitations

Figure 10 shows typical failure cases of our approach. We identified three
main failure modes. First, our model is prone to detecting long curves or
lines in some letters as primitives as arcs or line (Figure 10(a)). Second, in
freehand or less accurate drawings, our model fails to detect irregular lines
or predicts low curvature arcs instead (Figure 10(b)). Third, our model
achieves lower performance on arcs than on other primitives, which is often
showcased by the fact that it splits a single ground truth arc into several
arcs or both a line and an arc, or overlays arcs with parts of irregular
circles (Figure 10(c)). While we believe that these failure cases could be
mitigated by additional engineering efforts in the design of synthetic
training data, or by fine-tuning our method on some real data, for example in
an active learning setup, they are also related to the intrinsic difficulty of
the data.

((a)) Letter detection

((b)) Curved lines

((c)) Duplicate arcs

Figure 10: Failure cases of our model.

##### Qualitative results on S-VED

To evaluate the generality of our model, we test it on samples from the S-VED
dataset [4] shown in Figure 11. While results are generally satisfactory, our
synthetic data could be better adapted to paper prints, where shapes can be
well seen in transparency, leading to false positives.

|  |  |
---|---|---|---
|  |  |
Figure 11: Qualitative results on printed S-VED [4] diagrams.

##  6 Conclusion

We presented a diverse and challenging dataset of 303 historical diagrams
annotated with geometric primitives and a novel transformer-based approach to
diagram vectorization. Our model refines the primitive parameters by relying
on a novel parametrization of decoder queries. It is faster to train and more
accurate than baselines, and it can naturally be extended to support other
types of primitives. We show that this model can be trained solely on
synthetic data, and generalize to real diagrams. We believe that our method
significantly improves over existing vectorization approaches, and our dataset
opens up a novel and exciting application for History of Science.

##  7 Acknowledgments

This work was funded by ANR (project EIDA ANR-22-CE38-0014). The work of S.
Trigg is supported by the European Research Council (ERC project NORIA, grant
724175). M. Aubry and S. Kalleli are supported by ERC project DISCOVER funded
by the European Union’s Horizon Europe Research and Innovation program under
grant agreement No. 101076028. We thank Ji Chen, Samuel Guessner, Divna
Manolova, and Jade Norindr for their help in collecting and annotating the
dataset, and Sonat Baltaçi, Raphaël Benna, Yannis Siglidis, Elliot Vincent,
and Malamatenia Vlachou for feedback and fruitful discussions.

## References

  * [1] Alaniz, S., Mancini, M., Dutta, A., Marcos, D., Akata, Z.: Abstracting sketches through simple primitives. In: European Conference on Computer Vision. pp. 396–412. Springer (2022)
  * [2] Bessmeltsev, M., Solomon, J.: Vectorization of line drawings via polyvector fields. ACM Transactions on Graphics (TOG) 38(1), 1–12 (2019)
  * [3] Bo, P., Luo, G., Wang, K.: A graph-based method for fitting planar b-spline curves with intersections. Journal of Computational Design and Engineering 3(1), 14–23 (2016). https://doi.org/https://doi.org/10.1016/j.jcde.2015.05.001, https://www.sciencedirect.com/science/article/pii/S2288430015000408
  * [4] Büttner, J., Martinetz, J., El-Hajj, H., Valleriani, M.: Cor deep and the sacrobosco dataset: Detection of visual elements in historical documents. Journal of Imaging 8(10), 285 (2022)
  * [5] Carion, N., Massa, F., Synnaeve, G., Usunier, N., Kirillov, A., Zagoruyko, S.: End-to-end object detection with transformers. In: European conference on computer vision. pp. 213–229. Springer (2020)
  * [6] Chen, Y., Ni, B., Chen, X., Hu, Z.: Editable image geometric abstraction via neural primitive assembly. In: Proceedings of the IEEE/CVF International Conference on Computer Vision. pp. 23514–23523 (2023)
  * [7] Chen, Y., Carlinet, E., Chazalon, J., Mallet, C., Dumenieu, B., Perret, J.: Vectorization of historical maps using deep edge filtering and closed shape extraction. In: International conference on document analysis and recognition. pp. 510–525. Springer (2021)
  * [8] Choi, N., Lee, S., Lee, Y., Yang, S.: Restoration of hand-drawn architectural drawings using latent space mapping with degradation generator. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 14164–14172 (2023)
  * [9] Donati, L., Cesano, S., Prati, A.: An accurate system for fashion hand-drawn sketches vectorization. In: Proceedings of the IEEE International Conference on Computer Vision Workshops. pp. 2280–2286 (2017)
  * [10] Dosch, P., Tombre, K., Ah-Soon, C., Masini, G.: A complete system for the analysis of architectural drawings. International Journal on Document Analysis and Recognition 3, 102–116 (2000), https://api.semanticscholar.org/CorpusID:5948819
  * [11] Egiazarian, V., Voynov, O., Artemov, A., Volkhonskiy, D., Safin, A., Taktasheva, M., Zorin, D., Burnaev, E.: Deep vectorization of technical drawings. In: European conference on computer vision. pp. 582–598. Springer (2020)
  * [12] Favreau, J.D., Lafarge, F., Bousseau, A.: Fidelity vs. simplicity: a global approach to line drawing vectorization. ACM Transactions on Graphics (TOG) 35(4), 1–10 (2016)
  * [13] Ganin, Y., Bartunov, S., Li, Y., Keller, E., Saliceti, S.: Computer-aided design as language. Advances in Neural Information Processing Systems 34, 5885–5897 (2021)
  * [14] Gao, J., Tang, C., Ganapathi-Subramanian, V., Huang, J., Su, H., Guibas, L.J.: Deepspline: Data-driven reconstruction of parametric curves and surfaces. arXiv preprint arXiv:1901.03781 (2019)
  * [15] Gut, O., Hegde, S., Berumen, E.J., Bessmeltsev, M., Chien, E.: Singularity‐free frame fields for line drawing vectorization. Computer Graphics Forum 42 (2023), https://api.semanticscholar.org/CorpusID:259854435
  * [16] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 770–778 (2016)
  * [17] Hilaire, X., Tombre, K.: Robust and accurate vectorization of line drawings. IEEE Transactions on Pattern Analysis and Machine Intelligence 28(6), 890–904 (2006)
  * [18] Kim, B., Wang, O., Öztireli, A.C., Gross, M.: Semantic segmentation for line drawing vectorization using neural networks. In: Computer Graphics Forum. vol. 37, pp. 329–338. Wiley Online Library (2018)
  * [19] Li, F., Zhang, H., Liu, S., Guo, J., Ni, L.M., Zhang, L.: Dn-detr: Accelerate detr training by introducing query denoising. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 13619–13627 (2022)
  * [20] Lin, T.Y., Goyal, P., Girshick, R., He, K., Dollár, P.: Focal loss for dense object detection. In: Proceedings of the IEEE international conference on computer vision. pp. 2980–2988 (2017)
  * [21] Liu, C., Wu, J., Kohli, P., Furukawa, Y.: Raster-to-vector: Revisiting floorplan transformation. In: Proceedings of the IEEE International Conference on Computer Vision. pp. 2195–2203 (2017)
  * [22] Liu, H., Li, C., Liu, X., Wong, T.T.: End-to-end line drawing vectorization. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 36, pp. 4559–4566 (2022)
  * [23] Liu, H., Li, C., Liu, X., Wong, T.T.: Neural recognition of dashed curves with gestalt law of continuity. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 1373–1382 (2022)
  * [24] Liu, S., Li, F., Zhang, H., Yang, X., Qi, X., Su, H., Zhu, J., Zhang, L.: Dab-detr: Dynamic anchor boxes are better queries for detr. arXiv preprint arXiv:2201.12329 (2022)
  * [25] Meng, D., Chen, X., Fan, Z., Zeng, G., Li, H., Yuan, Y., Sun, L., Wang, J.: Conditional detr for fast training convergence. In: Proceedings of the IEEE/CVF International Conference on Computer Vision. pp. 3651–3660 (2021)
  * [26] Mo, H., Simo-Serra, E., Gao, C., Zou, C., Wang, R.: General virtual sketching framework for vector line art. ACM Transactions on Graphics (TOG) 40, 1 – 14 (2021), https://api.semanticscholar.org/CorpusID:233993908
  * [27] Monnier, T., Aubry, M.: docExtractor: An off-the-shelf historical document element extraction. In: ICFHR (2020)
  * [28] Para, W., Bhat, S., Guerrero, P., Kelly, T., Mitra, N., Guibas, L.J., Wonka, P.: Sketchgen: Generating constrained cad sketches. Advances in Neural Information Processing Systems 34, 5077–5088 (2021)
  * [29] Puhachov, I., Chien, E., Bessmeltsev, M.: Keypoint-driven line drawing vectorization via polyvector flow. ACM Transactions on Graphics (TOG) 40, 1 – 17 (2021), https://api.semanticscholar.org/CorpusID:239013957
  * [30] Reddy, P., Gharbi, M., Lukac, M., Mitra, N.J.: Im2vec: Synthesizing vector graphics without vector supervision. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 7342–7351 (2021)
  * [31] Sasaki, K., Iizuka, S., Simo-Serra, E., Ishikawa, H.: Learning to restore deteriorated line drawing. The visual computer 34, 1077–1085 (2018)
  * [32] Seff, A., Ovadia, Y., Zhou, W., Adams, R.P.: Sketchgraphs: A large-scale dataset for modeling relational geometry in computer-aided design. arXiv preprint arXiv:2007.08506 (2020)
  * [33] Seff, A., Zhou, W., Richardson, N., Adams, R.P.: Vitruvion: A generative model of parametric cad sketches. arXiv preprint arXiv:2109.14124 (2021)
  * [34] Selinger, P.: Potrace : a polygon-based tracing algorithm (2003), https://api.semanticscholar.org/CorpusID:1419652
  * [35] Stanko, T., Bessmeltsev, M., Bommes, D., Bousseau, A.: Integer-grid sketch simplification and vectorization. In: Computer graphics forum. vol. 39, pp. 149–161. Wiley Online Library (2020)
  * [36] Swaileh, W., Kotzinos, D., Ghosh, S., Jordan, M., Vu, N.S., Qian, Y.: Versailles-fp dataset: wall detection in ancient floor plans. In: Document Analysis and Recognition–ICDAR 2021: 16th International Conference, Lausanne, Switzerland, September 5–10, 2021, Proceedings, Part I 16. pp. 34–49. Springer (2021)
  * [37] Wang, L., Wang, X.: Ppi-net: End-to-end parametric primitive inference. In: Computer Graphics International Conference. pp. 67–78. Springer (2023)
  * [38] Wang, Y., Zhang, X., Yang, T., Sun, J.: Anchor detr: Query design for transformer-based object detection. arXiv preprint arXiv:2109.07107 3(6) (2021)
  * [39] Xu, Y., Xu, W., Cheung, D., Tu, Z.: Line segment detection using transformers without edges. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 4257–4266 (2021)
  * [40] Yue, Y., Kontogianni, T., Schindler, K., Engelmann, F.: Connecting the dots: Floorplan reconstruction using two-level queries. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pp. 845–854 (2023)
  * [41] Zhang, H., Li, F., Liu, S., Zhang, L., Su, H., Zhu, J., Ni, L.M., Shum, H.Y.: Dino: Detr with improved denoising anchor boxes for end-to-end object detection. arXiv preprint arXiv:2203.03605 (2022)
  * [42] Zhu, X., Su, W., Lu, L., Li, B., Wang, X., Dai, J.: Deformable detr: Deformable transformers for end-to-end object detection. arXiv preprint arXiv:2010.04159 (2020)


# Providing Wireless Coverage to High-rise Buildings Using UAVs

Hazim Shakhatreh  Department of Electrical and Computer Engineering, New
Jersey Institute of Technology  Abdallah Khreishah  Department of Electrical
and Computer Engineering, New Jersey Institute of Technology  Bo Ji
Department of Computer and Information Sciences, Temple University

###### Abstract

Unmanned aerial vehicles (UAVs) can be used as aerial wireless base stations
when cellular networks go down. Prior studies on UAV-based wireless coverage
typically consider an Air-to-Ground path loss model, which assumes that the
users are outdoor and they are located on a 2D plane. In this paper, we
propose using a single UAV to provide wireless coverage for indoor users
inside a high-rise building under disaster situations (such as earthquakes or
floods), when cellular networks are down. First, we present a realistic
Outdoor-Indoor path loss model and describe the tradeoff introduced by this
model. Then, we study the problem of efficient UAV placement, where the
objective is to minimize the total transmit power required to cover the entire
high-rise building. The formulated problem is non-convex and is generally
difficult to solve. To that end, we consider two cases of practical interest
and provide the efficient solutions to the formulated problem under these
cases. In the first case, we aim to find the minimum transmit power such that
an indoor user with the maximum path loss can be covered. In the second case,
we assume that the locations of indoor users are symmetric across the
dimensions of each floor.

###### Index Terms:

Unmanned aerial vehicles, Outdoor-to-Indoor path loss model.

##  I Introduction

UAVs can be used to provide wireless coverage during emergency cases where
each UAV serves as an aerial wireless base station when the cellular network
goes down [1]. They can also be used to supplement the ground base station in
order to provide better coverage and higher data rates for the users [2].

In order to use a UAV as an aerial wireless base station, the authors in [3]
presented an Air-to-Ground path loss model that helped the academic
researchers to formulate many important problems. The authors of [4, 5, 6, 7,
8] utilized this model to study the problem of UAV placement, where the
objective is to minimize the number of UAVs for covering a given area. The
authors of [4] described the tradeoff in this model. At a low altitude, the
path loss between the UAV and the ground user decreases, while the probability
of line of sight links also decreases. On the other hand, at a high altitude
line of sight connections exist with a high probability, while the path loss
increases. However, it is assumed that all users are outdoor and the location
of each user can be represented by an outdoor 2D point. These assumptions
limit the applicability of this model when one needs to consider indoor users.

Providing good wireless coverage for indoor users is very important. According
to Ericsson report [9], 90% of the time people are indoor and 80% of the
mobile Internet access traffic also happens indoors [10, 11]. To guarantee the
wireless coverage, the service providers are faced with several key
challenges, including providing service to a large number of indoor users and
the ping pong effect due to interference from near-by macro cells [12, 13,
14]. In this paper, we propose using a single UAV to provide wireless coverage
for users inside a high-rise building during emergency cases, when the
cellular network service is not available.

To the best of our knowledge, this is the first work that proposes using a UAV
to provide wireless coverage for indoor users. We summarize our main
contributions as follows. First, we assume an Outdoor-Indoor path loss model
[15], certified by ITU, and show the tradeoff introduced by this model.
Second, we formulate the problem of efficient UAV placement, where the
objective is to minimize the total transmit power required to cover the entire
high-rise building. Third, since the formulated problem is non-convex and is
generally difficult to solve, we consider two cases of practical interest and
provide the efficient solutions to the formulated problem under these cases.
In the first case, we aim to find the minimum transmit power such that an
indoor user with the maximum path loss can be covered. In the second case, we
assume that the locations of indoor users are symmetric across the dimensions
of each floor, and propose a gradient descent algorithm for finding the
efficient location of the UAV.

The rest of this paper is organized as follows. In Section II, we describe the
system model and a path loss model suitable for studying indoor wireless
coverage. In Section III, we formulate the problem of UAV placement with an
objective of minimizing the transmit power for covering the entire building.
In Section IV, we describe the tradeoff introduced by the path loss model and
show how to find the efficient location of the UAV such that the total
transmit power is minimized in two scenarios of practical interest. Finally,
we present our numerical results in Section V and make concluding remarks in
Section VI.

Figure 1: Parameters of the path loss model

Figure 2: Transmit power required to cover the building

Figure 3: Transmit power required to cover the building

##  II System Model

###  II-A System Settings

Let ($x_{UAV}$,$y_{UAV}$,$z_{UAV}$) denote the 3D location of the UAV. We
assume that all users are located inside a high-rise building as shown in
Figure 3, and use ($x_{i}$,$y_{i}$,$z_{i}$) to denote the location of user
$i$. The dimensions of the high-rise building are $[0,x_{b}]$ $\times$
$[0,y_{b}]$ $\times$ $[0,z_{b}]$. Also, let $d_{3D,i}$ be the 3D distance
between the UAV and indoor user $i$, let $\theta_{i}$ be the incident angle ,
and let $d_{2D,i}$ be the 2D indoor distance of user $i$ inside the building.

###  II-B Outdoor-Indoor Path Loss Model

The Air-to-Ground path loss model presented in [3] is not appropriate when we
consider wireless coverage for indoor users, because this model assumes that
all users are outdoor and located at 2D points. In this paper, we adopt the
Outdoor-Indoor path loss model, certified by the ITU [15]. The path loss is
given as follows:

$\begin{split}L_{i}=L_{F}+L_{B}+L_{I}=~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\\
(w\log_{10}d_{3D,i}+w\log_{10}f_{Ghz}+g_{1})+\\\
(g_{2}+g_{3}(1-\cos\theta_{i})^{2})+(g_{4}d_{2D,i})~{}~{}~{}~{}\end{split}$
(1)

where $L_{F}$ is the free space path loss, $L_{B}$ is the building penetration
loss, and $L_{I}$ is the indoor loss. In this model, we also have $w$=20,
$g_{1}$=32.4, $g_{2}$=14, $g_{3}$=15, $g_{4}$=0.5 [15] and $f_{Ghz}$ is the
carrier frequency (2Ghz). Note that there is a key tradeoff in the above model
when the horizontal distance between the UAV and a user changes. When this
horizontal distance increases, the free space path loss (i.e., $L_{F}$)
increases as $d_{3D,i}$ increases, while the building penetration loss (i.e.,
$L_{B}$) decreases as the incident angle (i.e., $\theta_{i}$) decreases.
Similarly, when this horizontal distance decreases, the free space path loss
(i.e., $L_{F}$) decreases as $d_{3D,i}$ decreases, while the building
penetration loss (i.e., $L_{B}$) increases as the incident angle (i.e.,
$\theta_{i}$) increases.

##  III Problem Formulation

Consider a transmission between a UAV located at
($x_{UAV}$,$y_{UAV}$,$z_{UAV}$) and an indoor user $i$ located at
($x_{i}$,$y_{i}$,$z_{i}$). The rate for user $i$ is given by:

$\begin{split}C_{i}=Blog_{2}(1+\dfrac{P_{t,i}/L_{i}}{N})\end{split}$ (2)

where $B$ is the transmission bandwidth of the UAV, $P_{t,i}$ is the UAV
transmit power to indoor user $i$, $L_{i}$ is the path loss between the UAV
and indoor user $i$ and $N$ is the noise power. In this paper, we do not
explicitly model interference, and instead, implicitly model it as noise.

Let us assume that each indoor user has a channel with bandwidth equals $B/M$,
where $M$ is the number of users inside the building and the rate requirement
for each user is $v$. Then the minimum power required to satisfy this rate for
each user is given by:

$\begin{split}P_{t,i,min}=(2^{\frac{v.M}{B}}-1)\star N\star L_{i}\end{split}$
(3)

Our goal is to find the efficient location of the UAV such that the total
transmit power required to satisfy the rate requirement of each indoor user is
minimized. The objective function can be represented as:

$\begin{split}P=\sum_{i=1}^{M}(2^{\frac{v.M}{B}}-1)\star N\star L_{i},\\\
\end{split}$ (4)

where $P$ is the UAV total transmit power. Since $(2^{\frac{v.M}{B}}-1)\star
N$ is constant, our problem can be formulated as:

$\begin{split}\min_{x_{UAV},y_{UAV},z_{UAV}}L_{Total}=\sum_{i=1}^{M}L_{i}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\\
subject~{}to~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\\
x_{min}\leq x_{UAV}\leq
x_{max},~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\\
y_{min}\leq y_{UAV}\leq
y_{max},~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\\
z_{min}\leq z_{UAV}\leq
z_{max},~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\\
L_{Total}\leq
L_{max}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\end{split}$
(5)

Here, the first three constraints represent the minimum and maximum allowed
values for $x_{UAV}$, $y_{UAV}$ and $z_{UAV}$. In the fourth constraint,
$L_{max}$ is the maximum allowable path loss and equals
$P_{t,max}$$/$$((2^{\frac{v.M}{B}}-1)\star N)$, where $P_{t,max}$ is the
maximum transmit power of UAV.

Finding the optimal placement of UAV is generally difficult because the
problem is non-convex. Therefore, in the next section, we consider two special
cases of practical interest and derive efficient solutions for the formulated
problems under these cases.

##  IV Efficient Placement of UAV

Due to the intractability of the problem, we study the efficient placement of
the UAV under two cases. In the first case, we find the minimum transmit power
required to cover the building based on the location that has the maximum path
loss inside the building. In the second case, we assume that the locations of
indoor users are symmetric across the dimensions of each floor, and propose a
gradient descent algorithm for finding the efficient location of the UAV.

###  IV-A Case One: The worst location in building

In this case, we find the minimum transmit power required to cover the
building based on the location that has the maximum path loss inside the
building. The location that has the maximum path loss in the building is the
location that has maximum $d_{3D,i}$, maximum $\theta_{i}$, and maximum
$d_{2D,i}$. The locations that have the maximum path loss are located at the
corners of the highest and lowest floors at points $(x_{b},0,0)$,
$(x_{b},y_{b},0)$, $(x_{b},0,z_{b})$ and $(x_{b},y_{b},z_{b})$ (see Figure 1).
Since the locations that have the maximum path loss inside the building are
the corners of the highest and lowest floors, we place the UAV at the middle
of the building ($y_{UAV}$= 0.5$y_{b}$ and $z_{UAV}$=0.5$z_{b}$). Then, given
the Outdoor-to-Indoor path loss model, we need to find the optimal horizontal
point $x_{UAV}$ for the UAV such that the total transmit power required to
cover the building is minimized.

Now, when the horizontal distance between the UAV and this location increases,
the free space path loss also increases as $d_{3D,i}$ increases, while the
building penetration loss decreases because we decrease the incident angle
$\theta_{i}$. Similarly, when the horizontal distance decreases, the free
space path loss decreases as $d_{3D,i}$ decreases, while the building
penetration loss increases as the incident angle increases. In Figure 3, we
demonstrate the minimum transmit power required to cover a building of
different heights, where the minimum transmit power required to cover the
building is given by:

$\begin{split}P_{t,min}(dB)=P_{r,th}+L_{i}\end{split}$ (6)
$\begin{split}P_{r,th}(dB)=N+\gamma_{th}\end{split}$ (7)

Here, $P_{r,th}$ is the minimum received power, $N$ is the noise power (equals
-120dBm), $\gamma_{th}$ is the threshold SNR (equals 10dB), $y_{b}$=50 meters
, and $x_{b}$=20 meters. The numerical results show that there is an optimal
horizontal point that minimizes the total transmit power required to cover a
building. Also, we can notice that when the height of the building increases,
the optimal horizontal distance also increases. This is to compensate the
increased building penetration loss due to an increased incident angle.

In Theorem 1, we characterize the optimal incident angle $\theta$ that
minimizes the transmit power required to cover the building. This helps us
finding the optimal horizontal distance between the UAV and the building.

######  Theorem 1.

When we place the UAV at the middle of building , the optimal incident angle
$\theta$ that minimizes the transmit power required to cover the building will
be equal to $48.654^{o}$ and the optimal horizontal distance between the UAV
and the building will be equal to
$((\dfrac{0.5z_{b}}{tan(48.654^{o})})^{2}-(0.5y_{b})^{2})^{0.5}-x_{b}$.

###### Proof.

In order to find the optimal horizontal point, we rewrite the equation that
represents the path loss in terms of the incident angle ($\theta_{i}$) and the
altitude difference between the UAV and the user $i$ ($\Delta h_{i}$):

$\begin{split}L_{i}(\Delta h_{i},\theta_{i})=w\log_{10}\dfrac{\Delta
h_{i}}{\sin\theta_{i}}+w\log_{10}f_{Ghz}+g_{1}\\\
+g_{2}+g_{3}(1-\cos\theta_{i})^{2}+g_{4}d_{2D,i}\end{split}$ (8)

We know that the altitude difference between the UAV and the location that has
the maximum path loss is constant for a given building. Now, when we take the
first derivative with respect to $\theta$ and assign it to zero, we get:

$\begin{split}\dfrac{dL(\theta)}{d\theta}=\dfrac{w}{ln10}\dfrac{\dfrac{-\Delta
h.\cos\theta}{\sin^{2}\theta}}{\dfrac{\Delta
h}{\sin\theta}}+2g_{3}\sin\theta(1-\cos\theta)=0~{}~{}~{}~{}~{}~{}~{}~{}\\\
\dfrac{dL(\theta)}{d\theta}=\dfrac{-w}{ln10}\dfrac{\cos\theta}{\sin\theta}+2g_{3}\sin\theta(1-\cos\theta)=0~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\\
\dfrac{w}{ln10}\cos\theta=2g_{3}sin^{2}\theta(1-\cos\theta)~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\\
\dfrac{w}{ln10}\cos\theta=2g_{3}(1-\cos^{2}\theta)(1-\cos\theta)~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\\
2g_{3}\cos^{3}\theta-2g_{3}\cos^{2}\theta-(\dfrac{w}{ln10}+2g_{3})\cos\theta+2g_{3}=0~{}~{}~{}~{}~{}~{}\end{split}$
(9)

To prove that the function is convex, we take the second derivative and we
get:

$\begin{split}\dfrac{d^{2}L}{d\theta^{2}}=\dfrac{w}{ln10}\dfrac{1}{\sin^{2}\theta}+2g_{3}\cos\theta(1-\cos\theta)+2g_{3}\sin^{2}\theta>0\\\
for~{}0<\theta\leq 90\end{split}$ (10)

Equation (9) has only one valid solution which is $\cos\theta$$=$0.6606, where
the non valid solutions are $\cos\theta$$=$1.4117 and $\cos\theta$$=$–1.0723.
Therefore, the optimal incident angle between the UAV and the location that
has the maximum path loss inside the building will be $48.654^{o}$.

In order to find the optimal horizontal distance between the UAV and the
building, we apply the pythagorean’s theorem. The optimal horizontal distance
between the UAV and the location that has maximum path loss inside the
building can be represented as:

$\begin{split}d_{H}=((\dfrac{0.5z_{b}}{tan(48.654^{o})})^{2}-(0.5y_{b})^{2})^{0.5}\end{split}$
(11)

In order to find the optimal horizontal distance between the UAV and the
building, we subtract $x_{b}$ from $d_{H}$ and we get:

$\begin{split}d_{opt}=((\dfrac{0.5z_{b}}{tan(48.654^{o})})^{2}-(0.5y_{b})^{2})^{0.5}-x_{b}\end{split}$
(12)

∎

In Figure 3, we demonstrate the transmit power required to cover the building
as a function of incident angle, we can notice that the optimal angle that we
characterize in Theorem 1 gives us the minimum transmit power required to
cover the building.

###  IV-B Case Two: The locations of indoor users are symmetric across the
$xy$ and $xz$ planes

In this case, we assume that the locations of indoor users are symmetric
across the $xy$-plane ((0,0,0.5$z_{b}$),($x_{b}$,0,0.5$z_{b}$)
,($x_{b}$,$y_{b}$,0.5$z_{b}$),(0,$y_{b}$,0.5$z_{b}$))) and the $xz$-plane
((0,0.5$y_{b}$,0), ($x_{b}$,0.5$y_{b}$,0),
($x_{b}$,0.5$y_{b}$,$z_{b}$),(0,0.5$y_{b}$,$z_{b}$)). First, we prove that
$z_{UAV}$=$0.5z_{b}$ and $y_{UAV}$=$0.5y_{b}$ when the locations of indoor
users are symmetric across the $xy$ and $xz$ planes, then we will use the
gradient descent algorithm to find the efficient $x_{UAV}$ that minimizes the
transmit power required to cover the building. Our simulation results show
that there is only one local minimum point and the gradient descent algorithm
will successfully converge to this point.

######  Theorem 2.

When the locations of indoor users are symmetric across the $xy$ and $xz$
planes, the efficient $z_{UAV}$ that minimizes the power required to cover the
indoor users will be equal $0.5z_{b}$.

###### Proof.

Consider that $m_{1}$ represents the users that have altitude lower than the
UAV altitude and $m_{2}$ represents the users that have altitude higher than
the UAV altitude, then:

$\begin{split}d_{3D,i}=((x_{UAV}-x_{i})^{2}+(y_{UAV}-y_{i})^{2}+(z_{UAV}-z_{i})^{2})^{0.5}\\\
~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\forall
z_{UAV}>z_{i}\\\
d_{3D,i}=((x_{UAV}-x_{i})^{2}+(y_{UAV}-y_{i})^{2}+(z_{i}-z_{UAV})^{2})^{0.5}\\\
~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\forall
z_{UAV}<z_{i}\\\ \end{split}$

Also,

$\begin{split}cos_{\theta_{i}}=\dfrac{((x_{UAV}-x_{i})^{2}+(y_{UAV}-y_{i})^{2})^{0.5}}{((x_{UAV}-x_{i})^{2}+(y_{UAV}-y_{i})^{2}+(z_{UAV}-z_{i})^{2})^{0.5}}\\\
~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\forall
z_{UAV}>z_{i}\\\
cos_{\theta_{i}}=\dfrac{((x_{UAV}-x_{i})^{2}+(y_{UAV}-y_{i})^{2})^{0.5}}{((x_{UAV}-x_{i})^{2}+(y_{UAV}-y_{i})^{2}+(z_{i}-z_{UAV})^{2})^{0.5}}\\\
~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\forall
z_{UAV}<z_{i}\\\ \end{split}$

Rewrite the total path loss:

$\begin{split}L_{Total}=~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\\
\sum_{i=1}^{m_{1}}(wlog_{10}(d_{3D,i})+g_{3}(1-\cos\theta_{i})^{2})+~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\\
\sum_{i=1}^{m_{2}}(wlog_{10}(d_{3D,i})+g_{3}(1-\cos\theta_{i})^{2})+K~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\\
\end{split}$

Where:

$\begin{split}K=\sum_{i=1}^{M}(wlog_{10}f_{Ghz}+g_{1}+g_{2}+g_{4}d_{2D,i})~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\\
\end{split}$

Now, take the derivative with respect to $z_{UAV}$, we get:

$\begin{split}\dfrac{dL_{Total}}{dz_{UAV}}=~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\\
\sum_{i=1}^{m_{1}}\dfrac{w}{ln10}\frac{(z_{UAV}-z_{i})}{((x_{UAV}-x_{i})^{2}+(y_{UAV}-y_{i})^{2}+(z_{UAV}-z_{i})^{2})}~{}~{}~{}\\\
+2g_{3}.~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\\
(1-\dfrac{((x_{UAV}-x_{i})^{2}+(y_{UAV}-y_{i})^{2})^{0.5}}{((x_{UAV}-x_{i})^{2}+(y_{UAV}-y_{i})^{2}+(z_{UAV}-z_{i})^{2})^{0.5}}).~{}~{}~{}~{}~{}\\\
(\dfrac{((x_{UAV}-x_{i})^{2}+(y_{UAV}-y_{i})^{2})^{0.5}(z_{UAV}-z_{i})}{((x_{UAV}-x_{i})^{2}+(y_{UAV}-y_{i})^{2}+(z_{UAV}-z_{i})^{2})^{\frac{3}{2}}})+~{}~{}~{}~{}\\\
\sum_{i=1}^{m_{2}}\dfrac{w}{ln10}\frac{-(z_{i}-z_{UAV})}{((x_{UAV}-x_{i})^{2}+(y_{UAV}-y_{i})^{2}+(z_{i}-z_{UAV})^{2})}~{}~{}~{}\\\
+2g_{3}.~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\\
(1-\dfrac{((x_{UAV}-x_{i})^{2}+(y_{UAV}-y_{i})^{2})^{0.5}}{((x_{UAV}-x_{i})^{2}+(y_{UAV}-y_{i})^{2}+(z_{i}-z_{UAV})^{2})^{0.5}}).~{}~{}~{}~{}~{}\\\
(\dfrac{-((x_{UAV}-x_{i})^{2}+(y_{UAV}-y_{i})^{2})^{0.5}(z_{i}-z_{UAV})}{((x_{UAV}-x_{i})^{2}+(y_{UAV}-y_{i})^{2}+(z_{i}-z_{UAV})^{2})^{\frac{3}{2}}})~{}~{}~{}~{}\end{split}$

Rewrite the $\dfrac{dL_{Total}}{dz_{UAV}}$ again, we have:

$\begin{split}\dfrac{dL_{Total}}{dz_{UAV}}=\sum_{i=1}^{m_{1}}\dfrac{w}{ln10}\frac{(z_{UAV}-z_{i})}{d_{3D,i}^{2}}+~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\\
2g_{3}.(1-\dfrac{((x_{UAV}-x_{i})^{2}+(y_{UAV}-y_{i})^{2})^{0.5}}{d_{3D,i}}).~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\\
(\dfrac{((x_{UAV}-x_{i})^{2}+(y_{UAV}-y_{i})^{2})^{0.5}(z_{UAV}-z_{i})}{d_{3D,i}^{3}})+~{}~{}~{}\\\
\sum_{i=1}^{m_{2}}\dfrac{w}{ln10}\frac{-(z_{i}-z_{UAV})}{d_{3D,i}^{2}}+~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\\
2g_{3}.(1-\dfrac{((x_{UAV}-x_{i})^{2}+(y_{UAV}-y_{i})^{2})^{0.5}}{d_{3D,i}}).~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\\
(\dfrac{-((x_{UAV}-x_{i})^{2}+(y_{UAV}-y_{i})^{2})^{0.5}(z{i}-z_{UAV})}{d_{3D,i}^{3}})~{}~{}~{}\\\
\end{split}$

The equation above equals zero when the UAV altitude equals the half of the
building height, where the locations of indoor users are symmetric across the
$xy$ and $xz$ planes. ∎

######  Theorem 3.

When the locations of indoor users are symmetric across the $xy$ and $xz$
planes, the efficient $y_{UAV}$ that minimizes the power required to cover the
indoor users will be equal $0.5y_{b}$.

The proof of Theorem 3 is similar to that of Theorem 2.

Figure 4: Total path loss for different building heights

The question now is how to find the efficient horizontal point $x_{UAV}$ that
minimizes the total transmit power. In order to find this point, we use the
gradient descent algorithm [16]:

$\begin{split}x_{UAV,n+1}=x_{UAV,n}-a\dfrac{dL_{Total}}{dx_{UAV,n}}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\\
\end{split}$ (13)

Where:

$\begin{split}\dfrac{dL_{Total}}{dx_{UAV}}=\sum_{i=1}^{M}\dfrac{w}{ln10}\dfrac{-(x_{i}-x_{UAV})}{d_{3D,i}^{2}}+~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\\
2g_{3}.(1-\dfrac{((x_{i}-x_{UAV})^{2}+(y_{i}-y_{UAV})^{2})^{0.5}}{d_{3D,i}}).~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\\\
(\dfrac{(x_{i}-x_{UAV})d_{3D,i}((x_{i}-x_{UAV})^{2}+(y_{i}-y_{UAV})^{2})^{-0.5}}{{d_{3D,i}^{2}}}-~{}~{}\\\
\dfrac{((x_{i}-x_{UAV})^{2}+(y_{i}-y_{UAV})^{2})^{0.5}(x_{i}-x_{UAV})d_{3D,i}^{-1}}{d_{3D,i}^{2}})~{}~{}~{}~{}~{}~{}~{}\end{split}$

$a$: the step size.
$d_{3D,i}$=$((x_{i}-x_{UAV})^{2}+(y_{i}-y_{UAV})^{2}+(z_{i}-z_{UAV})^{2})^{0.5}$

The pseudo code of this algorithm is shown in Algorithm 1.

Input:

The 3D locations of the users inside the building.

The step size $a$, the step tolerance $\epsilon$.

The dimensions of the building $[0,x_{b}]$ $\times$ $[0,y_{b}]$ $\times$
$[0,z_{b}]$.

The maximum number of iterations $N_{max}$.

Initialize $x_{UAV}$

For $n$=1,2,…, $N_{max}$

$x_{UAV,n+1}$ $\leftarrow$ $x_{UAV,n}$$-$ $a\dfrac{dL_{Total}}{dx_{UAV,n}}$

If $\lVert$ $x_{UAV,n}$ $-$ $x_{UAV,n+1}$ $\rVert$ $<$ $\epsilon$

Return: $x_{UAV,opt}$ $=$ $x_{UAV,n+1}$

End for

Algorithm 1 Efficient $x_{UAV}$ using gradient descent algorithm Figure 5:
Total path loss for different building widths

##  V Numerical Results

In this section, we verify our results for the second case. We assume that
each floor contains 20 users. Then, we apply the gradient descent algorithm to
find the efficient horizontal point $x_{UAV}$ that minimizes the transmit
power required to cover the indoor users. Table I lists the parameters used in
the numerical analysis.

TABLE I: Parameters in numerical analysis Height of building $z_{b}$ | 200 meters, 250 meters and 300 meters
---|---
Horizontal width of building $x_{b}$ | 10 meters, 20 meters and 50 meters
Vertical width of building $y_{b}$ | 50 meters
Hight of each floor | 5 meters
Step size $a$ | 0.01
Maximum number of iterations $N_{max}$ | 500
The carrier frequency $f_{Ghz}$ | 2Ghz
Number of users in each floor | 20 users

In Figure 4, we find the efficient horizontal points for a building of
different heights. In the upper part of the figures, we find the total path
loss at different locations ($x_{UAV}$,0.5$y_{b}$,$z_{UAV}$) and in the lower
part of the figures, we find the efficient horizontal point $x_{UAV}$ that
results in the minimum total path loss using the gradient descent algorithm.
As can be seen from the figures, when the height of the building increases,
the efficient horizontal point $x_{UAV}$ increases. This is to compensate the
increased building penetration loss due to an increased incident angle.

In Figure 5, we investigate the impact of different building widths (i.e.,
$x_{b}$). We fix the building height to be 250 meters and vary the building
width. As can be seen from the figures, when the building width increases, the
efficient horizontal distance decreases. This is to compensate the increased
indoor path loss due to an increased building width.

In [17], we validate the simulation results by using the particle swarm
optimization algorithm and study the problem when the locations of indoor
users are uniformly distributed in each floor.

##  VI Conclusion

In this paper, we study the problem of providing wireless coverage for users
inside a high-rise building using a single UAV. First, we demonstrate why the
Air-to-Ground path loss model is not appropriate for considering indoor users
with 3D locations. Then, we present the Outdoor-to-Indoor path loss model,
show the tradeoff in this model, and study the problem of minimizing the
transmit power required to cover the building. Due to the intractability of
the problem, we study the efficient placement of the UAV under two cases. In
the first case, we find the minimum transmit power required to cover the
building based on the location that has the maximum path loss inside the
building. In the second case, we assume that the locations of indoor users are
symmetric across the $xy$ and $xz$ planes and we use the gradient descent
algorithm to find the efficient placement of the UAV. In order to model more
realistic scenarios, we will consider different types of user distribution in
our future work. We will also study the problem of providing wireless coverage
using multiple UAVs.

## Acknowledgment

This work was supported in part by the NSF under Grants CNS-1647170 and
CNS-1651947.

## References

  * [1] P. Bupe, R. Haddad, and F. Rios-Gutierrez, “Relief and emergency communication network based on an autonomous decentralized uav clustering network,” in _SoutheastCon 2015_. IEEE, 2015, pp. 1–8.
  * [2] R. I. Bor-Yaliniz, A. El-Keyi, and H. Yanikomeroglu, “Efficient 3-d placement of an aerial base station in next generation cellular networks,” in _Communications (ICC), 2016 IEEE International Conference on_. IEEE, 2016, pp. 1–5.
  * [3] A. Al-Hourani, S. Kandeepan, and A. Jamalipour, “Modeling air-to-ground path loss for low altitude platforms in urban environments,” in _2014 IEEE Global Communications Conference_. IEEE, 2014, pp. 2898–2904.
  * [4] M. Mozaffari, W. Saad, M. Bennis, and M. Debbah, “Drone small cells in the clouds: Design, deployment and performance analysis,” in _IEEE Global Communications Conference (GLOBECOM)_ , 2015, pp. 1–6.
  * [5] M. Mozaffari, W. Saad, M. Bennis, and M. Debbah, “Optimal transport theory for power-efficient deployment of unmanned aerial vehicles,” _IEEE International Conference on Communications (ICC), Kuala Lumpur, Malaysia,_ , 2016.
  * [6] M. Mozaffari, W. Saad, M. Bennis, and M. Debbah, “Efficient deployment of multiple unmanned aerial vehicles for optimal wireless coverage,” _arXiv preprint arXiv:1606.01962_ , 2016.
  * [7] E. Kalantari, H. Yanikomeroglu, and A. Yongacoglu, “On the number and 3d placement of drone base stations in wireless cellular networks,” in _IEEE Vehicular Technology Conference_ , 2016, pp. 18–21.
  * [8] H. Shakhatreh, A. Khreishah, J. Chakareski, H. B. Salameh, and I. Khalil, “On the continuous coverage problem for a swarm of uavs,” in _Sarnoff Symposium, 2016 IEEE 37th_. IEEE, 2016, pp. 130–135.
  * [9] “Ericsson report optimizing the indoor experience, http://www.ericsson.com/res/docs/2013/real-performance-indoors.pdf,” 2013.
  * [10] “In-building wireless: One size does not fit all, http://www.alcatel-lucent.com/solutions/in-building/in-building-infographic.”
  * [11] “Cisco service provider wi-fi: A platform for business innovation and revenue generation, http://www.cisco.com/c/en/us/solutions/collateral/service-provider/service-provider-wi-fi/solution_overview_c22_642482.html.”
  * [12] “Using high-power das in high-rise buildings, http://www.commscope.com/docs/using-high-power-das-in-high-rise-buildings-an-318376-ae.pdf.”
  * [13] “Coverage solution for high-rise building, http://www.amplitec.net/products-2-coverage-solution-for-high-rise-building.html.”
  * [14] S. Zhang, Z. Zhao, H. Guan, and H. Yang, “Study on mobile data offloading in high rise building scenario,” in _Vehicular Technology Conference (VTC Spring), 2016 IEEE 83rd_. IEEE, 2016, pp. 1–5.
  * [15] M. Series, “Guidelines for evaluation of radio interface technologies for imt-advanced,” _Report ITU_ , no. 2135-1, 2009.
  * [16] R. S. Sutton and A. G. Barto, _Reinforcement learning: An introduction_. MIT press Cambridge, 1998, vol. 1, no. 1.
  * [17] H. Shakhatreh, A. Khreishah, A. Alsarhan, I. Khalil, A. Sawalmeh, and O. Noor Shamsiah, “Efficient 3d placement of a uav using particle swarm optimization,” in _The International Conference on Information and Communication Systems (ICICS 2017) (accepted)_.