# Vision-Based Guidance for Tracking Dynamic Objects

Pritam Karmokar1∗, Kashish Dhal2∗, William J. Beksi1, and Animesh
Chakravarthy2 *Indicates equal contribution1 P. Karmokar and W.J. Beksi are
with the Department of Computer Science and Engineering, University of Texas
at Arlington, Arlington, TX, USA. Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>2 K. Dhal and A. Chakravarthy are with the Department of
Mechanical and Aerospace Engineering, University of Texas at Arlington,
Arlington, TX, USA. Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this paper, we present a novel vision-based framework for tracking dynamic
objects using guidance laws based on a rendezvous cone approach. These
guidance laws enable an unmanned aircraft system equipped with a monocular
camera to continuously follow a moving object within the sensor’s field of
view. We identify and classify feature point estimators for managing the
occurrence of occlusions during the tracking process in an exclusive manner.
Furthermore, we develop an open-source simulation environment and perform a
series of simulations to show the efficacy of our methods.

©2021 IEEE. Personal use of this material is permitted. Permission from IEEE
must be obtained for all other uses, in any current or future media, including
reprinting/republishing this material for advertising or promotional purposes,
creating new collective works, for resale or redistribution to servers or
lists, or reuse of any copyrighted component of this work in other works. DOI:
10.1109/ICUAS51884.2021.9476712

##  I Introduction

In recent years there has been an increase in the number of applications using
unmanned aircraft systems (UASs). At the same time, researchers have
progressively inclined towards using vision as a primary source of perception
[1]. This is mainly due to cameras becoming cheaper in cost, smaller in size,
lighter in weight, and higher in image resolution. Likewise, as computing
resources evolve to be more economical and powerful, there has been growing
interest in research and development for UASs. On account of their agility,
mobility, and form factor, various diverse problems have found UASs with on-
board vision-based sensors to be an ideal solution [2]. Not only can UASs
reach places that are intractable for humans to access, but they are also
excellent platforms for monotonous and dangerous jobs. This includes traffic
monitoring [3, 4], search and rescue [5, 6], reconnaissance for military
operations [7, 8], and much more.

Figure 1: Our proposed framework allows an unmanned aircraft system to
visually track a ground vehicle under the existence of partial and total
occlusions using unique guidance laws based on a rendezvous cone approach.

In this work, we construct a system that permits a UAS to pursue a dynamic
ground vehicle using only visual information. To do this we employ the concept
of a rendezvous cone. Concretely, we analytically show how a rendezvous cone
can be used to develop guidance laws for a UAS to track a moving vehicle.
These guidance laws are supported by a comprehensive set of computer vision
algorithms that perform feature detection, track and make adjustments to the
centroid of the vehicle, and filter for robustness and recovery through
partial and full occlusions. In summary, our key contributions are the
following.

  * •

We introduce a set of systematic guidance laws which allow a UAS to visually
track a moving object.

  * •

We provide an identification and taxonomy of occlusion handling for feature
point estimators under various occlusion cases.

  * •

We implement an extensive open-source simulator [9] that supplies visual
measurements while performing object tracking.

Moreover, our proposed system can be applied to applications such as tracking,
monitoring, and surveillance via UASs.

The remainder of this paper is organized as follows. We discuss related work
in Section II. Section III provides a concise statement of the problem to be
solved. Our vision-based guidance scheme is presented in Section IV. In
Section V, we report our simulation results. We conclude in Section VI and
mention future work.

##  II Related Work

###  II-A Cones in Relative Velocity Space

There has been related work on the development of guidance laws using cones
constructed in the relative velocity space. The concept of collision cones was
proposed in [10] to represent a collection of velocity vectors of an object
which leads to a collision with another moving object. Guidance laws to avoid
collision were then designed to steer the current velocity vector of the
object outside the collision cone. This idea was later employed by many
researchers for various applications ranging from aircraft conflict detection
and resolution [11], vision-based obstacle avoidance [12, 13], automobile
collision avoidance [14], robotic collision avoidance [15], and to study
collision avoidance behavior in biological organisms [16].

In subsequent work, collision cones have been extended to higher-dimensional
spaces and general obstacle shapes [17]. They’ve also been used to design safe
passage trajectories through narrow orifices for aerial as well as underwater
vehicles [18]. In contrast to these prior research problems, the guidance laws
presented in our work specify accelerations which when applied by a UAS
enables it to steer its velocity vector towards the moving object and
subsequently match its velocity to that of the object. The term rendezvous
cone is more representative for this class of applications and we shall adopt
this term in our presentation. In addition, our rendezvous cone approach
employs vision-based information in order to perform its computations.

###  II-B Vision-Based Tracking

The first comprehensive survey on visual tracking and categorization of state-
of-the-art algorithms was presented in [19]. Further research was provided by
[20] and [21] where the main trends and taxonomy in object detection and
tracking are introduced. Various vision-based tracking techniques exist
ranging from low-level HSV threshold color-based detection [22, 23] through
high-level tracking-by-detection learning-based methods [24, 25, 26]. To
overcome known challenges in visual tracking, many ideas such as template
matching [27], feature matching [28], and optical flow [29, 30, 31] have been
adopted by researchers.

Our work focuses on visual object tracking [32, 33, 34, 35] utilizing a point
estimator for target localization. In addition, we perform occlusion handling
[36] and identify occlusion states [37, 38] along with case transitions for
tracking point estimators. Tools and methods such as part-based templates
[39], RGB color distributions [40], segmentation [41], deformable models [42],
background/foreground [43] detection, etc., have been employed to carry out
occlusion management. In comparison, our approach makes use of classical
computer vision techniques [44]. Specifically, we implement a resilient
feature detection strategy for tracking and adjusting the centroid of an
object in the presence of extreme occlusions.

##  III Problem Statement

Consider a scenario in which a UAS, equipped with a downward-facing camera, is
flying at a known altitude. In addition, the UAS only perceives visual
information as it tracks a ground-based vehicle. It is assumed the vehicle has
been detected and is initially within the UAS’s field of view. Moreover, the
motion of the vehicle is along a plane orthogonal to the principal axis of the
camera and thus the image projection is orthographic. The problem is to
develop vision-based guidance laws that facilitate the UAS in consistently
tracking the vehicle even as it performs evasive maneuvers and encounters
occlusions.

##  IV Vision-Based Guidance

###  IV-A Engagement Geometry and Guidance Laws

Figure 2: An engagement between a UAS ($A$) and a ground vehicle ($B$).

We model the engagement geometry between a UAS ($A$) and vehicle ($B$) as an
orthogonal projection onto a horizontal plane, Fig. 2. The UAS and vehicle are
moving with speeds $V_{A}$ and $V_{B}$, and heading angles $\alpha$ and
$\beta$, respectively. The distance between $A$ and $B$ is represented by $r$
while $\theta$ denotes the angle made by the line of sight (LOS) $AB$. The UAS
has two control inputs: lateral acceleration $a_{lat}$ and longitudinal
acceleration $a_{long}$. Thus, $A$ can rotate its velocity vector as well as
change its speed. The vehicle can apply an acceleration of magnitude $a_{B}$
which acts at an angle $\delta_{B}$, and $R$ denotes the radius of $B$. $X$
portrays the rendezvous cone from $A$ to $B$. If $A$ can steer its velocity
vector into $X$, then $A$ is on a trajectory that will cause it to rendezvous
with $B$. The kinematics governing the engagement geometry are characterized
by the equations governing $AB$,

$\displaystyle\begin{bmatrix}\dot{{r}}\\\ \dot{{\theta}}\\\
\dot{{V_{\theta}}}\\\ \dot{{V_{r}}}\\\ \dot{\alpha}\\\ \dot{V_{A}}\\\
\dot{\beta}\\\ \dot{{V_{B}}}\end{bmatrix}$ $\displaystyle=$
$\displaystyle\begin{bmatrix}{V_{r}}\\\ {{V_{\theta}/r}}\\\
-{V_{\theta}}{V_{r}}/{r}\\\ V_{\theta}^{2}/{r}\\\ 0\\\ 0\\\ 0\\\
0\end{bmatrix}+\begin{bmatrix}0\\\ 0\\\ -\cos(\alpha-{\theta})\\\
\sin(\alpha-{\theta})\\\ 1/V_{A}\\\ 0\\\ 0\\\ 0\end{bmatrix}a_{lat}$
$\displaystyle+$ $\displaystyle\begin{bmatrix}0\\\ 0\\\
-\sin(\alpha-{\theta})\\\ -\cos(\alpha-{\theta})\\\ 0\\\ 1\\\ 0\\\
0\end{bmatrix}a_{long}+\begin{bmatrix}0\\\ 0\\\ \sin(\delta_{B}-{\theta})\\\
\cos(\delta_{B}-{\theta})\\\ 0\\\ 0\\\ \sin(\delta_{B}-{\beta})/V_{B}\\\
\cos(\delta_{B}-{\beta})\end{bmatrix}a_{B},$

where $V_{r}$ and $V_{\theta}$ are the components of the relative velocity
vector.

We define the rendezvous cone [10] as

$y_{1}=r^{2}V_{\theta}^{2}-R^{2}(V_{\theta}^{2}+V_{r}^{2}),$ (2)

i.e., it is the cone of relative velocity vectors that will cause $A$ to
rendezvous with $B$. This is established by two conditions: (i)
$y_{1}<0,V_{r}<0$ and (ii) $y_{1}=0,V_{r}<0$. Condition (i) corresponds to the
case of the relative velocity vector being inside the rendezvous cone while
condition (ii) corresponds to the scenario of the relative velocity vector
being aligned with the boundary of the rendezvous cone. When (ii) occurs $A$
will graze $B$ at the instant of closest approach. We define the velocity
matching error as

${y}_{2}=V_{r}^{2}+V_{\theta}^{2}.$ (3)

Dynamic inversion is employed to drive the output functions to the desired
values. By differentiating (2) and (3) we obtain the dynamic evolution of
$y_{1}$ and $y_{2}$ as

$\begin{bmatrix}\dot{y}_{1}\\\
\dot{y}_{2}\end{bmatrix}=\begin{bmatrix}\frac{\partial y_{1}}{\partial
r}&\frac{\partial y_{1}}{\partial\theta}&\frac{\partial y_{1}}{\partial
V_{\theta}}&\frac{\partial y_{1}}{\partial V_{r}}\\\ \frac{\partial
y_{2}}{\partial r}&\frac{\partial y_{2}}{\partial\theta}&\frac{\partial
y_{2}}{\partial V_{\theta}}&\frac{\partial y_{2}}{\partial
V_{r}}\end{bmatrix}\times\left[\begin{array}[]{c}{\dot{r}}\\\
{\dot{\theta}}\\\ {\dot{V}_{\theta}}\\\ {\dot{V}_{r}}\\\ \end{array}\right].$
(4)

The partial derivatives of (4) are expressed as

$\begin{bmatrix}2rV_{\theta}^{2}&0&2V_{\theta}(r^{2}-R^{2})&-2r^{2}V_{r}\\\
0&0&2V_{\theta}&2V_{r}\end{bmatrix}.$ (5)

To calculate the required control input, we define two error quantities with
respect to $y_{1}$ and $y_{2}$. The error in $y_{1}$ is specified as
$e_{1}(t)=y_{1d}(t)-y_{1}(t)$, where $y_{1d}(t)<0$ is a reference input while
the error in $y_{2}$ is described as $e_{2}(t)=0-y_{2}(t)$. Taking $y_{1d}(t)$
as a constant $\forall t$, we seek to determine $a_{lat}$ and $a_{long}$ which
will ensure the error dynamics follow the equations $\dot{e}_{1}=-k_{1}e_{1}$
and $\dot{e}_{2}=-k_{2}e_{2}$ where $k_{1},k_{2}>0$ are constants. This in
turn allows the quantities $y_{1}$ and $y_{2}$ to follow the dynamics, i.e.,

$\displaystyle\begin{bmatrix}\dot{y}_{1}\\\ \dot{y}_{2}\end{bmatrix}$
$\displaystyle=$ $\displaystyle\begin{bmatrix}k_{1}(y_{1d}-y_{1})\\\
-k_{2}y_{2}\end{bmatrix}.$ (6)

After substituting (IV-A), (5), and (6) into (4) we obtain

$\displaystyle\begin{bmatrix}a_{11}&a_{12}\\\
a_{21}&a_{22}\end{bmatrix}\begin{bmatrix}a_{lat}\\\
a_{long}\end{bmatrix}=\begin{bmatrix}-k_{1}(y_{1d}-y_{1})/2\\\
k_{2}y_{2}/2\end{bmatrix}-\begin{bmatrix}b_{1}\\\ b_{2}\end{bmatrix}a_{B},$
(7)

where

$\displaystyle a_{11}$ $\displaystyle=$ $\displaystyle
V_{\theta}(r^{2}-R^{2})\cos(\alpha-\theta)+R^{2}V_{r}\sin(\alpha-\theta),$
$\displaystyle a_{12}$ $\displaystyle=$ $\displaystyle
V_{\theta}(r^{2}-R^{2})\sin(\alpha-\theta)+R^{2}V_{r}\cos(\alpha-\theta),$
$\displaystyle a_{21}$ $\displaystyle=$ $\displaystyle
V_{\theta}\cos(\alpha-\theta)+V_{r}\sin(\alpha-\theta),$ $\displaystyle
a_{22}$ $\displaystyle=$ $\displaystyle
V_{\theta}\sin(\alpha-\theta)+V_{r}\cos(\alpha-\theta),$ $\displaystyle b_{1}$
$\displaystyle=$ $\displaystyle
V_{r}R^{2}\cos(\delta_{B}-\theta)-V_{\theta}(r^{2}-R^{2})\sin(\delta_{B}-\theta),$
$\displaystyle b_{2}$ $\displaystyle=$ $\displaystyle-
V_{r}\cos(\delta_{B}-\theta)-V_{\theta}\sin(\delta_{B}-\theta).$

By solving (7) we obtain

$\displaystyle a_{lat}$
$\displaystyle=\Big{[}k_{1}(y_{1}-y_{1d})\Big{(}V_{r}\cos(\alpha-\theta)+V_{\theta}\sin(\alpha-\theta)\Big{)}$
$\displaystyle+k_{2}y_{2}\Big{(}V_{r}R^{2}\cos(\alpha-\theta)-V_{\theta}(r^{2}-R^{2})\sin(\alpha-\theta)\Big{)}$
$\displaystyle-2V_{r}V_{\theta}r^{2}\sin(\alpha-\delta_{B})a_{B}\Big{]}/(2V_{r}V_{\theta}r^{2})$
(8) $\displaystyle a_{long}$
$\displaystyle=\Big{[}k_{1}(y_{1}-y_{1d})\Big{(}V_{r}\sin(\alpha-\theta)-V_{\theta}\cos(\alpha-\theta)\Big{)}$
$\displaystyle+k_{2}y_{2}\Big{(}V_{r}R^{2}\sin(\alpha-\theta)+V_{\theta}(r^{2}-R^{2})\cos(\alpha-\theta)\Big{)}$
$\displaystyle+2V_{r}V_{\theta}r^{2}\cos(\alpha-\delta_{B})a_{B}\Big{]}/(2V_{r}V_{\theta}r^{2}).$
(9)

(8) and (9) serve as the acceleration commands to the UAS and are supplied to
our simulator. We note the acceleration commands $a_{lat}(t)$ and
$a_{long}(t)$ depend on continuous feedback from the quantities $y_{1}$ and
$y_{2}$, states $r,\theta,V_{r},V_{\theta}$, and the acceleration vector of
the vehicle. The quantities $r$ and $\theta$ are obtained by direct
measurements from the vision system while the remaining quantities are
estimated using an acceleration model (Section IV-B).

###  IV-B Vehicle Acceleration Model

The positional measurements of the vehicle in the image frame are obtained
using feature point tracking (Section IV-E). In addition, since it’s assumed
the UAS knows its own states, we can transform the image measurements to an
inertial frame. These inertial measurements are then fed into a linear
acceleration model [45, 46]. The model filters the position data and provides
estimates of the velocity and acceleration of the vehicle. Given that the
position of the vehicle in the inertial frame is represented as
$(x_{B},y_{B})$, we obtain the discrete form of the motion model as

$\displaystyle\bm{\chi}_{B}(k)$ $\displaystyle=$
$\displaystyle\bm{F}_{B}\bm{\chi}_{B}(k-1)+\bm{w}_{B}(k),$
$\displaystyle\bm{z}_{B}(k)$ $\displaystyle=$
$\displaystyle\bm{H}_{B}\bm{\chi}_{B}(k)+\bm{v}_{B}(k).$ (10)

where the state vector of the vehicle is represented by
$\bm{\chi}_{B}=[x_{B},\dot{x}_{B},\ddot{x}_{B},y_{B},\dot{y}_{B},\ddot{y}_{B}]^{\top}$
and $\bm{z}_{B}$ is the measurement vector. The state transition matrix
corresponding to the acceleration model is defined as

$\bm{F}_{B}=\begin{bmatrix}\bm{T}&\bm{0}\\\ \bm{0}&\bm{T}\end{bmatrix},$

where $\bm{0}$ is a $3\times 3$ matrix of zeros and

$\bm{T}=\begin{bmatrix}1&\Delta t&[e^{-\alpha_{B}\Delta t}+\alpha_{B}\Delta
t-1]/\alpha_{B}^{2}\\\ 0&1&[1-e^{-\alpha_{B}\Delta t}]/\alpha_{B}\\\
0&0&e^{-\alpha_{B}\Delta t}\end{bmatrix}.$

The process noise is defined as
$\bm{w}_{B}\sim{\mathcal{N}}{\bigl{(}}{0},\bm{Q}_{B}{\bigr{)}}$ and the noise
covariance matrix is given by

$\bm{Q}_{B}=2\alpha_{B}\sigma_{B}^{2}\begin{bmatrix}\bm{Q}&\bm{0}\\\
\bm{0}&\bm{Q}\end{bmatrix},$

where $\alpha_{B}$, $\sigma_{B}$, and $\bm{Q}$ are described in [45]. The size
of $\bm{Q}$ and $\bm{0}$ is $3\times 3$. The measurement matrix takes the form

$\bm{H}_{B}=\begin{bmatrix}1&0&0&0&0&0\\\ 0&0&0&1&0&0\end{bmatrix}.$

$\bm{v}_{B}\sim{\mathcal{N}}{\bigl{(}}{0},\bm{R}_{B}{\bigr{)}}$ is the
measurement noise and $\bm{R}_{B}$ is the measurement noise covariance matrix.
The velocity estimates $(\dot{x}_{B},\dot{y}_{B})$ of the vehicle are
transformed back into the UAS-centered relative frame to obtain the relative
velocity components $\hat{V}_{r}$ and $\hat{V}_{\theta}$. Similarly, the
vehicle acceleration estimates $(\ddot{x}_{B},\ddot{y}_{B})$ are translated
into $\hat{a}_{B}$ and $\hat{\delta}_{B}$.

###  IV-C System Architecture

Figure 3: The overall architecture of the vision-based guidance system.

Our system architecture is shown in Fig 3. First, images captured by the UAS
are used to estimate the relative and absolute position of the vehicle. Next,
the measured velocity and acceleration states are processed to determine the
quantities
$[\hat{r},\hat{\theta},\hat{V_{\theta}},\hat{V_{r}},\hat{a}_{B},\hat{\delta}_{B}]^{\top}$.
The filtered estimates of the noisy $r_{m}$ and $\theta_{m}$ measurements are
represented by $\hat{r}$ and $\hat{\theta}$, $\hat{V}_{\theta}$ and
$\hat{V}_{r}$ express approximations of the relative velocity components, and
$\hat{a}_{B}$ and $\hat{\delta}_{B}$ represent estimates of the absolute
acceleration magnitude and direction of the vehicle. Finally, these values are
used to compute an assessment of the current rendezvous cone. An estimate of
the UAS velocity vector with respect to the rendezvous cone is denoted by
$\hat{y}_{1}$, while $\hat{y}_{2}$ measures the magnitude of the relative
velocity vector. The guidance algorithm generates suitable accelerations
$a_{lat}$ and $a_{long}$ which drive $\hat{y}_{1}$ and $\hat{y}_{2}$ to the
desired reference values. These accelerations move the UAS to a new position
whereby an updated image of the scene is generated by the simulator.

###  IV-D Simulator

We have developed a Python Pygame [47] simulator that constructs orthographic
projections from simulated kinematic states of a UAS and a vehicle. The
simulator generates RGB images at the appropriate frame rates or time
instances. Additionally, it can accept acceleration commands as input, update
the kinematic states of the simulated entities governed by the laws of rigid
body motion, and generate accurate renders. The simulator maps 3D scene points
onto a 2D image plane of RGB triplets. More formally, we describe this as the
composition of two mappings
$\mathcal{M}_{1}:\mathbb{R}^{3}\rightarrow\mathbb{P}^{2}$ and
$\mathcal{M}_{2}:\mathbb{P}^{2}\rightarrow\mathbb{R}^{3}$ which yields
$\mathcal{M}_{2}\circ\mathcal{M}_{1}:\mathbb{R}^{3}\rightarrow\mathbb{R}^{3}$.
The mapping $\mathcal{M}_{1}$ transforms kinematic states
${}^{W}\bm{x}(t)=\left[{}^{W}x(t),{}^{W}y(t),{}^{W}z(t)\right]^{\top}$ onto an
orthographic projective space. It generates the homogeneous vector
$\bm{\tilde{x}}(t)=\left[\tilde{x}(t),\tilde{y}(t),\tilde{w}(t)\right]^{\top}=\tilde{w}\left[x(t),y(t),1\right]^{\top}$
where
$\bm{x}(t)=[x(t),y(t)]^{\top}=\left[\frac{\tilde{x}(t)}{\tilde{w}(t)},\frac{\tilde{y}(t)}{\tilde{w}(t)}\right]^{\top}$.
Conversely, the mapping $\mathcal{M}_{2}$ discretizes and maps
$\bm{\tilde{x}}(t)$ to image intensities
$I_{color}(x,y,t)=\left[r(t),g(t),b(t)\right]^{\top}$. The colored image is
converted to grayscale, $I(x,y,t)$, which is then consumed by the feature
tracker. It’s worth mentioning that the simulator renders are non-anti-aliased
which introduces a discretization noise in the measurements since subpixel
motions are not simulated.

###  IV-E Feature Tracker

####  IV-E1 Optical Flow

We obtain sparse optical flow at good and desirable feature points [48].
Feature points are good if the eigenvalues of the gradient matrix at that
point are large and they are desirable if they correspond to the object to be
tracked through a sequence of images. A Kanade-Lucas-Tomasi (KLT) tracker [49,
50] is used for the task of tracking feature point sets,
$\mathcal{F}^{k}=\left\\{\bm{f}_{i}^{k}\right\\}_{i=1}^{n}$, where $n$ is the
number of points and $\bm{f}_{i}^{k}=(x_{i},y_{i})^{k}$ is the $i^{th}$ point
in the $k^{th}$ frame.

Optical flow displacements $\bm{u}|_{\bm{f}_{i}\in\mathcal{F}}$, where
$\bm{u}=\left[u_{x},u_{y},1\right]^{\top}$, are obtained under the assumption
of a linearized brightness constancy [51],

$I(x,y,t)=I(x+u_{x},y+u_{y},t+1).$ (11)

The displacements are computed over a small neighborhood
$\mathbf{\mathcal{N}}_{\bm{f}_{i}}$ of each $\bm{f}_{i}$. This is done by
solving a system of linear equations,

$\left(\nabla
I\left(\bm{x}\right)\right)^{\top}\cdot\bm{u}=\mathbf{0},\quad\forall\bm{x}\in\mathcal{N}_{\bm{f}},$
(12)

where $\nabla=\left[\frac{\partial}{\partial x},\frac{\partial}{\partial
y},\frac{\partial}{\partial t}\right]^{\top}$ is the gradient operator. Using
the computed displacement vectors, updated locations
$\bm{f}_{i}^{k+1}=(x_{i},y_{i})^{k+1}$ are obtained. Furthermore, a multiscale
pyramidal [52, 53, 54] approach enables tracking of an object through larger
displacements across frames.

####  IV-E2 Centroid Adjustment

(a)

(b)

Figure 4: Feature tracking for no occlusion to partial occlusion state
transitions: (a) without centroid adjustment, (b) with centroid adjustment.
-no occlusion, -partial occlusion, -good points (flow success), -bad points
(flow failure), -visible points, -occluded points, -not adjusted centroid,
-adjusted centroid, -optical flow across old and new frames.

Reliable optical flow computations require brightness constancy and temporal
regularity at feature points across frames. What’s more, spatial consistency
such that pixels in the neighborhood of feature points have a motion similar
to the point, is needed as well. In practice, flow computations can be brittle
when factors such as nonlinear image distortions, noise, and occlusions occur.
Moreover, we may experience $m\leq n$ missing points caused by high flow
optimization errors. This may result in unpredictable shifts in centroid
location despite the tracked object being relatively stationary.

To mitigate these effects we implement centroid adjustment, i.e., the centroid
of $n$ feature points belonging to the object is localized for consistent
measurements. Formally, we define a centroid as

$\bar{\mathcal{F}}=\frac{1}{n}\sum\limits_{i=1}^{n}\bm{f}_{i}.$ (13)

Adjustment of a centroid is then defined as

$\displaystyle\Delta\bar{\mathcal{F}}$
$\displaystyle={}^{\ast}\bar{\mathcal{F}}^{old}-{}^{good}\bar{\mathcal{F}}^{old},$
(14) $\displaystyle{}^{\ast}\bar{\mathcal{F}}^{new}$
$\displaystyle={}^{good}\bar{\mathcal{F}}^{new}+\Delta\bar{\mathcal{F}},$ (15)

where $\Delta\bar{\mathcal{F}}$ is the centroid adjustment and
${}^{\ast}\bar{\mathcal{F}}^{new}$ denotes the adjusted centroid. Pre-
superscripts are used to indicate good, bad, or all ($\ast$) points and post-
superscripts mean an old or new frame. This process is depicted in Fig. 4.

Using centroid adjustment with the assumption of rigid shape constraints, if
we compute good flow for at least one keypoint ($m<n$), then we can obtain
stable centroid measurements. Furthermore, for resilience purposes, feature
and template matching are used as fallback techniques while handling
occlusions. Even though the object of interest is primarily represented using
Shi-Tomasi keypoints, we also have access to full and partial templates of the
object. This includes SIFT [55] descriptors for redetection and recovery
purposes.

###  IV-F Occlusion Handling

In presence of occlusions, $|\mathcal{F}|=n$ cannot be assured. Besides, $m>0$
for at least $n$ time instances guarantees measurements will vanish. In the
context of tracking $n$ feature points
$\left\\{\bm{f}_{i}\right\\}_{i=1}^{n}$, we identify the following three
occlusion states ($\mathcal{O}$) with nine transitions among them: (i) no
occlusion ($\mathcal{N}$), (ii) partial occlusion ($\mathcal{P}$), and (iii)
total occlusion ($\mathcal{T}$). The occlusion states can be detected and
identified by drawing inference from the cardinality
$\left|{}^{good}\mathcal{F}\right|$, i.e.,

$\begin{split}|{}^{good}\mathcal{F}|=n\quad&\implies\mathcal{N}\\\
0<|{}^{good}\mathcal{F}|\leq n\quad&\implies\mathcal{P}\\\
|{}^{good}\mathcal{F}|=0\quad&\implies\mathcal{T}.\end{split}$ (16)

Although detecting states of occlusion is elementary, treating different
occlusion states in order to perform long-term point tracking via optical flow
is challenging. This is due to the fact that optical flow depends on the
health of the keypoints not only in the current frame, but also from the
previous frame. Consequently, to handle occlusions we enumerate nine
transition instances as shown in Fig. 5c. Observe in Fig. 5b that the no
occlusion state set $\mathcal{N}$ and the total occlusion state set
$\mathcal{T}$ are singletons. Yet, the partial occlusion state is a finite set
$\mathcal{P}=\left\\{\mathcal{F}\mid\ 0<|\mathcal{F}|\leq n\right\\}$ with
multiple elements. Accordingly, cases 1, 3, 7, 9 are the easiest to handle,
cases 2, 4, 6, 8 are moderate in complexity, and case 5 is the most complex. A
further breakdown of case 5 is discussed in Section IV-F2.

(a)

(b)

(c)

Figure 5: (a) Occlusion state transitions. (b) Occlusion state sets: No
Occlusion (top), Partial Occlusion (middle), Total Occlusion (bottom). (c)
Enumerated occlusion state transition case instances are depicted with a
vehicle and occlusion bars as follows: cases (1-3) enumerate transitions from
no occlusion to no, partial, total occlusion; cases (4-6) enumerate
transitions from partial occlusion to no, partial, total occlusion; and cases
(7-9) enumerate transitions from total occlusion to no, partial, total
occlusion. -good points (flow success), -bad points (flow failure), -visible
points, -occluded points.

(a)

(b)

Figure 6: Three consecutive frames with partial occlusions in the middle
frame. (a) Keypoints lost without missing point reconstruction, and (b)
keypoints recovered with missing point reconstruction. -good points (flow
success/recovered), -bad points (flow failure), -lost points, -visible points,
-occluded points.

####  IV-F1 From No Occlusion ($\mathcal{O}^{old}=\mathcal{N}$)

In this situation we have $|{}^{good}\mathcal{F}^{old}|=n$ and optical flow
can be computed for feature points ${}^{good}\mathcal{F}^{old}$ to obtain
${}^{good}\mathcal{F}^{new}$. The occlusion state identification in the new
frame ($\mathcal{O}^{new}$) can be carried out reliably as per (16).
Furthermore, by using the adjusted centroid, missing keypoints
${}^{bad}\mathcal{F}^{new}$ can be back projected and reconstructed as
displayed in Fig. 6. Occlusions cause these points to be lost (Fig. 6a),
however (for cases $1,2,3,5,6$) with reconstruction the missing points can be
fully recovered (Fig. 6b).

Figure 7: Partial-partial occlusion state transition subcase instances.
Subcases ($5a$-$5f$) represent equal, proper superset, proper subset, equal to
complement, proper subset of complement, and non-empty intersection,
respectively. -good points (flow success), -bad points (flow failure),
-visible points, -occluded points.

####  IV-F2 From Partial Occlusion ($\mathcal{O}^{old}=\mathcal{P}$)

Here we have $0<|{}^{good}\mathcal{F}^{old}|\leq n$ and optical flow can be
calculated at feature points ${}^{good}\mathcal{F}^{old}$. However, the
identification of occlusion state ($\mathcal{O}^{new}$) is not trivial and
(16) cannot be reliably used. Therefore, we identify the following six
subcases (Fig. 7): (a)
${}^{good}\mathcal{F}^{new}={}^{good}\mathcal{F}^{old}$, (b)
${}^{good}\mathcal{F}^{new}\supset{}^{good}\mathcal{F}^{old}$, (c)
${}^{good}\mathcal{F}^{new}\subset{}^{good}\mathcal{F}^{old}$, (d)
${}^{good}\mathcal{F}^{new}\cap{}^{good}\mathcal{F}^{old}=\varnothing$, (e)
${}^{good}\mathcal{F}^{new}\subset{}^{bad}\mathcal{F}^{old}$, and (f)
${}^{good}\mathcal{F}^{new}\cap{}^{good}\mathcal{F}^{old}\neq\varnothing$
(exclusive of other subcases). Optical flow can be successfully determined in
subcases $5a,5b,5c,5f$, or case $4$, while subcases $5d,5e$, or case $6$
indicates failure. To perform robust tracking with occlusions we need to
accurately identify the occlusion states. In the partial-partial case, SIFT
feature matching or part-based template matching can be used. The subcase
treatments can be summarized as follows: $5a$ requires no further processing,
$5b$ necessitates redetection of the points, $5c$ involves missing point
reconstruction, $5f$ needs both redetection and missing point reconstruction,
$5d$ and $5e$ call for redetection using matching techniques.

####  IV-F3 From Total Occlusion ($\mathcal{O}^{old}=\mathcal{T}$)

In this circumstance we have $|{}^{good}\mathcal{F}^{old}|=0$, hence optical
flow computations cannot be made. To continue tracking for cases $7,8,9$ we
can use techniques, such template or feature matching, and redetect
initial/updated feature points ${}^{good}\mathcal{F}^{0}$ in the new frame to
obtain ${}^{good}\mathcal{F}^{new}$. Occlusion state identification
($\mathcal{O}^{new}$) can then be decisively carried out as per (16).

###  IV-G Image Formation

Using optical flow, centroid adjustment, and occlusion handling mechanisms, we
can obtain noisy but accurate localization measurements of the vehicle
$\bm{x}_{B}$ from the image plane to the world inertial frame as follows. The
altitude ${}^{W}z_{A}(t)$ and camera calibration information such as field of
view ($\vartheta=47^{\circ}$) and image sensor width ($\mathcal{W}=5\,mm$) are
all known. Therefore, with a pixel size of $6.25\,\mu m$ we can calculate the
camera focal length as

$\varphi=\frac{\mathcal{W}}{2}\left[\tan\left(\frac{\vartheta}{2}\right)\right]^{-1}.$
(17)

Under orthographic projection of objects moving on a plane, (17) can be used
to obtain a mapping from image coordinates $\bm{x}_{B}$ to world coordinates
${}^{W}\bm{x}_{B}$ by the geometric relation

${}^{W}\bm{x}_{B}=\frac{{}^{W}z_{A}(t)}{\varphi}\bm{x}_{B}.$ (18)

Thus, (18) allows us to compute the measured kinematics state vector
$\left[{}^{W}\bm{x}_{B}^{\top},{}^{W}\dot{\bm{x}}_{B}^{\top}\right]^{\top}$ of
the vehicle in planar world coordinates. Finally,
$\left[{}^{W}{x}_{B},{}^{W}{y}_{B}\right]^{\top}$ is converted to polar form
($r,\theta$).

##  V Simulations

In this section, we demonstrate the behavior of our vision-based guidance
framework using the following (unknown to the UAS) vehicle trajectory
variants: lane changing and squircle following. All simulations were performed
on a Windows 10 machine with an Intel Core i7-8700 CPU and 32 GB RAM. For
every simulation, we make use of the true values of each quantity alongside
their measured and/or estimated values to generate the data plots.

####  V-1 Lane Changing Trajectory

(a)

(b)

(c)

(d)

(e)

Figure 8: Lane changing trajectory: (a)-(d) true, estimated, and measured
states $r$, $\theta$, $V_{r}$, and $V_{\theta}$; (e) acceleration commands
$a_{lat}$ and $a_{long}$. No ( ), partial ( ), and total ( ) occlusion states
are indicated along the zero line.

(a)

(b)

(c)

(d)

(e)

(f)

Figure 9: Lane changing trajectory: (a) speed of the UAS and vehicle and (b)
their differences; (c) heading of the UAS and vehicle and (b) their
differences; (e)-(f) true and estimated objective functions $y_{1}$ and
$y_{2}$.

(a)

(b)

Figure 10: Lane changing trajectory: UAS and vehicle trajectories in world (a)
and camera (b) reference frames.

We simulate the vehicle to move in the east direction while performing lane
changing maneuvers of approximately $4\,m$ at arbitrary time instances with
occlusions. The UAS starts at position
${}^{W}{\bm{x}_{A}}_{0}=[0.0,0.0,150.0]^{\top}(m)$ while the vehicle begins at
${}^{W}{\bm{x}_{B}}_{0}=[50.0,-30.0,0.0]^{\top}(m)$ with speeds
${}^{W}{V_{A}}_{0}=31.31\ (\nicefrac{{m}}{{s}})$ ($70\,mph$) and
${}^{W}{V_{B}}_{0}=22.22\ (\nicefrac{{m}}{{s}})$ ($50\,mph$), and headings
${}^{W}{\alpha}_{0}=0.0^{\circ}$ and ${}^{W}{\beta}_{0}=0.0^{\circ}$,
respectively. The simulation was run for approximately $149\,secs$. Fig. 8
depicts the kinematic state information collected over time. Under total
occlusions, measurements disappear and state estimations are utilized to
perform guidance. It can be observed in the data plots that estimations may
veer away from the true values if an occlusion persists for a long time. In
the simulations, the occurrence of occlusions is accompanied by an increasing
covariance ($\bm{R}_{B}$) in the measurement noise ($\bm{v}_{B}$) in (IV-B)
and by employing previous estimates as current measurements in the
acceleration model. In Fig. 9, the speed and heading profiles of the UAS and
vehicle along with their deltas are provided. The trajectories of the UAS and
vehicle in world and camera reference frames are shown in Fig. 10. Visual
tracking was successfully performed using our occlusion handling and
rendezvous cone-based guidance scheme.

####  V-2 Squircle Following Trajectory

(a)

(b)

(c)

(d)

(e)

Figure 11: Squircle following trajectory: (a)-(d) true, estimated, and
measured states $r$, $\theta$, $V_{r}$, and $V_{\theta}$; (e) acceleration
commands $a_{lat}$ and $a_{long}$.

(a)

(b)

(c)

(d)

(e)

(f)

Figure 12: Squircle following trajectory: (a) speed of the UAS and vehicle and
(b) their differences; (c) heading of the UAS and vehicle and (d) their
differences; (e)-(f) true and estimated objective functions $y_{1}$ and
$y_{2}$.

(a)

(b)

Figure 13: Squircle following trajectory: UAS and vehicle trajectories in
world (a) and camera (b) frames of reference.

We simulate the vehicle to proceed along a parameterized squircular trajectory
such that it traverses the closed curve with a period of $360\,secs$. The UAS
begins at position ${}^{W}{\bm{x}_{A}}_{0}=[0.0,0.0,350.0]^{\top}(m)$ with
speed ${}^{W}{V_{A}}_{0}=31.31\ (\nicefrac{{m}}{{s}})$ ($70\,mph$) while the
vehicle starts at ${}^{W}{\bm{x}_{B}}_{0}=[0.0,-20.0,0.0]^{\top}(m)$. Both the
UAS and vehicle have an initial heading of ${}^{W}{\alpha}_{0}=0.0^{\circ}$
and ${}^{W}{\beta}_{0}=0.0^{\circ}$. The vehicle speed ${}^{W}{V_{B}}$
decreases around the corners to approximately $14.79\ (\nicefrac{{m}}{{s}})$
($33.08\,mph$) while it reaches nearly $22.63\ (\nicefrac{{m}}{{s}})$
($50.62\,mph$) along the straight ways. The simulation was run for about
$671\,secs$. In Fig. 11, the true, estimated, and measured kinematics states
along with the lateral and longitudinal accelerations are shown. The speed,
heading, and deltas are visualized in Fig. 12 along with the true and
estimated objective functions $y_{1}$ and $y_{2}$. Fig. 13 depicts the
trajectories of the UAS and vehicle in world and camera frames of reference.
Our vision-based guidance system was able to successfully allow the UAS to
chase the vehicle while matching its speed and heading at non-constant
velocities.

##  VI Conclusion and Future Work

In conclusion, we have presented our solution to a problem wherein a UAS must
track a ground-based vehicle moving at erratic velocities through occlusions
using only visual information from a single camera. A rendezvous cone guidance
scheme drives our objective functions to the desired values resulting in the
generation of acceleration commands that lead the UAS into the cone and
towards the vehicle. We perform visual tracking of the vehicle’s centroid
using feature detection and optical flow along with a diagnosis and analysis
of occlusion events. A publicly available simulator that provides an
environment to perform these vision-based guidance simulations has been
developed. In the future, we plan to extend the guidance strategy to 3D,
incorporate multi-vehicle tracking, and improve the fidelity of the simulator.

## Acknowledgments

This material is based in part upon work supported by the National Science
Foundation through grant #IIS-1851817 and a University of Texas at Arlington
Research Enhancement Program grant #270079.

## References

  * [1] C. Kanellakis and G. Nikolakopoulos, “Survey on computer vision for uavs: Current developments and trends,” _Journal of Intelligent & Robotic Systems_, vol. 87, no. 1, pp. 141–168, 2017.
  * [2] A. Al-Kaff, D. Martin, F. Garcia, A. de la Escalera, and J. M. Armingol, “Survey of computer vision algorithms and applications for unmanned aerial vehicles,” _Expert Systems with Applications_ , vol. 92, pp. 447–463, 2018\.
  * [3] K. Kanistras, G. Martins, M. J. Rutherford, and K. P. Valavanis, “A survey of unmanned aerial vehicles (uavs) for traffic monitoring,” in _Proceedings of the International Conference on Unmanned Aircraft Systems (ICUAS)_ , 2013, pp. 221–234.
  * [4] H. Zhou, H. Kong, L. Wei, D. Creighton, and S. Nahavandi, “Efficient road detection and tracking for unmanned aerial vehicle,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 16, no. 1, pp. 297–309, 2014.
  * [5] S. Yeong, L. King, and S. Dol, “A review on marine search and rescue operations using unmanned aerial vehicles,” _International Journal of Marine and Environmental Sciences_ , vol. 9, no. 2, pp. 396–399, 2015.
  * [6] C. Van Tilburg, “First report of using portable unmanned aircraft systems (drones) for search and rescue,” _Wilderness & Environmental Medicine_, vol. 28, no. 2, pp. 116–118, 2017.
  * [7] T. Samad, J. S. Bay, and D. Godbole, “Network-centric systems for military operations in urban terrain: The role of uavs,” _Proceedings of the IEEE_ , vol. 95, no. 1, pp. 92–107, 2007.
  * [8] S. G. Manyam, S. Rasmussen, D. W. Casbeer, K. Kalyanam, and S. Manickam, “Multi-uav routing for persistent intelligence surveillance & reconnaissance missions,” in _Proceedings of the International Conference on Unmanned Aircraft Systems (ICUAS)_. IEEE, 2017, pp. 573–580.
  * [9] https://github.com/robotic-vision-lab/Vision-Based-Object-Tracking.
  * [10] A. Chakravarthy and D. Ghose, “Obstacle avoidance in a dynamic environment: A collision cone approach,” _IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans_ , vol. 28, no. 5, pp. 562–574, 1998.
  * [11] J. Goss, R. Rajvanshi, and K. Subbarao, “Aircraft conflict detection and resolution using mixed geometric and collision cone approaches,” in _AIAA Guidance, Navigation, and Control Conference and Exhibit_ , 2004, p. 4879.
  * [12] Y. Watanabe, A. Calise, E. Johnson, and J. Evers, “Minimum-effort guidance for vision-based collision avoidance,” in _AIAA Atmospheric Flight Mechanics Conference and Exhibit_ , 2006, p. 6641.
  * [13] Y. Watanabe, A. Calise, and E. Johnson, “Vision-based obstacle avoidance for uavs,” in _AIAA Guidance, Navigation and Control Conference and Exhibit_ , 2007, p. 6829.
  * [14] A. Ferrara and C. Vecchio, “Second order sliding mode control of vehicles with distributed collision avoidance capabilities,” _Mechatronics_ , vol. 19, no. 4, pp. 471–477, 2009.
  * [15] B. Gopalakrishnan, A. K. Singh, and K. M. Krishna, “Time scaled collision cone based trajectory optimization approach for reactive planning in dynamic environments,” in _Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2014, pp. 4169–4176.
  * [16] N. L. Brace, T. L. Hedrick, D. H. Theriault, N. W. Fuller, Z. Wu, M. Betke, J. K. Parrish, D. Grünbaum, and K. A. Morgansen, “Using collision cones to assess biological deconfliction methods,” _Journal of the Royal Society Interface_ , vol. 13, no. 122, p. 20160502, 2016.
  * [17] A. Chakravarthy and D. Ghose, “Collision cones for quadric surfaces in $n$-dimensions,” _IEEE Robotics and Automation Letters_ , vol. 3, no. 1, pp. 604–611, 2017.
  * [18] W. Zuo, K. Dhal, A. Keow, A. Chakravarthy, and Z. Chen, “Model-based control of a robotic fish to enable 3d maneuvering through a moving orifice,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 3, pp. 4719–4726, 2020\.
  * [19] A. Yilmaz, “Object tracking and activity recognition in video acquired using mobile cameras,” Ph.D. dissertation, University of Central Florida, 2004.
  * [20] A. Yilmaz, O. Javed, and M. Shah, “Object tracking: A survey,” _ACM Computing Surveys (CSUR)_ , vol. 38, no. 4, pp. 13–es, 2006.
  * [21] F. Porikli and A. Yilmaz, “Object detection and tracking,” in _Video Analytics for Business Intelligence_. Springer, 2012, pp. 3–41.
  * [22] R. Carelli, C. M. Soria, and B. Morales, “Vision-based tracking control for mobile robots,” in _Proceedings of the International Conference on Advanced Robotics (ICAR)_. IEEE, 2005, pp. 148–152.
  * [23] H. Lee, S. Jung, and D. H. Shim, “Vision-based uav landing on the moving vehicle,” in _Proceedings of the International Conference on Unmanned Aircraft Systems (ICUAS)_. IEEE, 2016, pp. 1–7.
  * [24] J. F. Henriques, R. Caseiro, P. Martins, and J. Batista, “High-speed tracking with kernelized correlation filters,” _IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI)_ , vol. 37, no. 3, pp. 583–596, 2014\.
  * [25] P. Bergmann, T. Meinhardt, and L. Leal-Taixe, “Tracking without bells and whistles,” in _Proceedings of the International Conference on Computer Vision (ICCV)_. IEEE, 2019, pp. 941–951.
  * [26] X. Zhou, V. Koltun, and P. Krähenbühl, “Tracking objects as points,” in _Proceedings of the European Conference on Computer Vision (ECCV)_. Springer, 2020, pp. 474–490.
  * [27] J. Pan and B. Hu, “Robust occlusion handling in object tracking,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_. IEEE, 2007, pp. 1–8.
  * [28] S. Shen, Y. Mulgaonkar, N. Michael, and V. Kumar, “Vision-based state estimation and trajectory control towards high-speed flight with a quadrotor.” in _Robotics: Science and Systems_ , vol. 1. Citeseer, 2013, p. 32.
  * [29] V. K. Madasu and M. Hanmandlu, “Estimation of vehicle speed by motion tracking on image sequences,” in _IEEE Intelligent Vehicles Symposium_ , 2010, pp. 185–190.
  * [30] B. Li, W. Wu, Q. Wang, F. Zhang, J. Xing, and J. Yan, “Siamrpn++: Evolution of siamese visual tracking with very deep networks,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019, pp. 4282–4291.
  * [31] Q. Wang, L. Zhang, L. Bertinetto, W. Hu, and P. H. Torr, “Fast online object tracking and segmentation: A unifying approach,” in _Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019, pp. 1328–1338.
  * [32] V. N. Dobrokhodov, I. I. Kaminer, K. D. Jones, and R. Ghabcheloo, “Vision-based tracking and motion estimation for moving targets using small uavs,” in _Proceedings of the American Control Conference (ACC)_. IEEE, 2006, pp. 6–pp.
  * [33] B. Jeon, K. Baek, C. Kim, and H. Bang, “Mode changing tracker for ground target tracking on aerial images from unmanned aerial vehicles,” in _Proceedings of the (ICCAS)_. IEEE, 2013, pp. 1849–1853.
  * [34] Y. Kim, W. Jung, and H. Bang, “Visual target tracking and relative navigation for unmanned aerial vehicles in a gps-denied environment,” _International Journal of Aeronautical and Space Sciences_ , vol. 15, no. 3, pp. 258–266, 2014.
  * [35] S. Liu, S. Wang, W. Shi, H. Liu, Z. Li, and T. Mao, “Vehicle tracking by detection in uav aerial video,” _Science China Information Sciences_ , vol. 62, no. 2, p. 24101, 2019.
  * [36] B. Y. Lee, L. H. Liew, W. S. Cheah, and Y. C. Wang, “Occlusion handling in videos object tracking: A survey,” in _IOP Conference Series: Earth and Environmental Science_ , vol. 18, no. 1. IOP Publishing, 2014, p. 012020.
  * [37] A. Galton, “Lines of sight,” in _AISB Workshop on Spatial and Spatio-Temporal Reasoning_ , vol. 35, 1994, pp. 37–39.
  * [38] C. Köhler, “The occlusion calculus,” in _Cognitive Vision Workshop_. Citeseer, 2002, pp. 420–450.
  * [39] T. Zhang, K. Jia, C. Xu, Y. Ma, and N. Ahuja, “Partial occlusion handling for visual tracking via robust part matching,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2014, pp. 1258–1265.
  * [40] W. Bouachir and G.-A. Bilodeau, “Structure-aware keypoint tracking for partial occlusion handling,” in _Winter Conference on Applications of Computer Vision (WACV)_. IEEE, 2014, pp. 877–884.
  * [41] B. Han, C. Paulson, T. Lu, D. Wu, and J. Li, “Tracking of multiple objects under partial occlusion,” in _Automatic Target Recognition XIX_ , vol. 7335\. International Society for Optics and Photonics, 2009, p. 733515.
  * [42] C. C. C. Pang, W. W. L. Lam, and N. H. C. Yung, “A novel method for resolving vehicle occlusion in a monocular traffic-image sequence,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 5, no. 3, pp. 129–141, 2004.
  * [43] P. Guha, A. Mukerjee, and V. K. Subramanian, “Formulation, detection and application of occlusion states (oc-7) in the context of multiple object tracking,” in _Proceedings of the International Conference on Advanced Video and Signal Based Surveillance (AVSS)_. IEEE, 2011, pp. 191–196.
  * [44] B. Zhou, P. Krähenbühl, and V. Koltun, “Does computer vision matter for action?” _arXiv preprint arXiv:1905.12887_ , 2019.
  * [45] R. A. Singer, “Estimating optimal tracking filter performance for manned maneuvering targets,” _IEEE Transactions on Aerospace and Electronic Systems_ , no. 4, pp. 473–483, 1970.
  * [46] P. R. Mahapatra and K. Mehrotra, “Mixed coordinate tracking of generalized maneuvering targets using acceleration and jerk models,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 36, no. 3, pp. 992–1000, 2000.
  * [47] Open-Source Community, _Pygame 2_ , 2021, https://www.pygame.org.
  * [48] J. Shi and C. Tomasi, “Good features to track,” in _Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 1994, pp. 593–600.
  * [49] B. D. Lucas and T. Kanade, “An iterative image registration technique with an application to stereo vision,” in _Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)_. Vancouver, British Columbia, 1981.
  * [50] C. Tomasi and T. Kanade, “Detection and tracking of point features,” CMU-CS-91-132, Carnegie Mellon University, Tech. Rep., 1991.
  * [51] B. K. Horn and B. G. Schunck, “Determining optical flow,” in _Techniques and Applications of Image Understanding_ , vol. 281. International Society for Optics and Photonics, 1981, pp. 319–331.
  * [52] E. Memin and P. Perez, “A multigrid approach for hierarchical motion estimation,” in _Proceedings of the International Conference on Computer Vision (ICCV)_. IEEE, 1998, pp. 933–938.
  * [53] T. Brox, A. Bruhn, N. Papenberg, and J. Weickert, “High accuracy optical flow estimation based on a theory for warping,” in _Proceedings of the European Conference on Computer Vision (ECCV)_. Springer, 2004, pp. 25–36.
  * [54] A. Bruhn and J. Weickert, “Towards ultimate motion estimation: Combining highest accuracy with real-time performance,” in _Proceedings of the International Conference on Computer Vision (ICCV)_ , vol. 1. IEEE, 2005, pp. 749–755.
  * [55] D. G. Lowe, “Distinctive image features from scale-invariant keypoints,” _International Journal of Computer Vision_ , vol. 60, no. 2, pp. 91–110, 2004\.


# An outline of multi objective optimization in databases with focus on
flexible skyline queries

Matteo Savino  Politecnico di Milano
Milan, Italy
<EMAIL_ADDRESS>
(January 13, 2022)

###### Abstract

The problem of optimizing across different, conceivably conflicting, criteria
is called multi-objective optimization and it is widely spread across many
fields. This is a recurring problem in database queries when there is the need
of obtaining the best objects from a very large data set. In this article, I
included a complete review of the main approaches typically used to achieve
multi-criteria optimization. Starting from ranking queries and skylines and
then proceeding to more advanced methods, this paper aims to define a clear
outline of multi-objective optimization in databases. In particular, the
flexible skyline paradigm is considered and thoroughly discussed as it
overcomes many of the critical issues that arise with other methods.

Keywords: Multi-objective optimization, Skyline queries, Top-k queries,
Ranking queries, Flexible skyline, Restricted skyline

##  1 Introduction

The problem of optimizing across different, conceivably conflicting, criteria
is called multi-objective optimization. As reported in [10] the need to find
the optimal solution to many desired goals is found across many research
fields such as mathematics, economics, engineering and many others. Several
reviews on this topic have been conducted since it is widespread across
multiple fields and many techniques have been designed to solve this problem.
Some of these methods do not require complex mathematical equations, therefore
they can be easily applied. These simpler approaches fall under two main
categories: pareto and scalarization [10].

One of the fields in which multi-objective optimization appears very
frequently is database queries. [8] highlights how the modern web
infrastructure, together with social networks, produces an unprecedented mass
of data. Therefore, data is usually available in very large quantities and
hence determining the most relevant items in data sets is fundamental. A
slightly more formal definition of the problem has been reported below.

###### Problem 1

Given N objects described by d (dimensions) attributes in a data set and given
some notion of quality, possibly conflicting, for each attribute, find the
best objects.

Problem 1 will be dealt with in this survey by showing some of the most widely
recognized or innovative techniques. Multi-objective optimization in data sets
is commonly obtained with three main approaches [4, 7, 9]:

  1. 1.

The ranking or top-k (or scalarization as previously mentioned) approach: it
reduces the multi-objective problem to a single objective one by using a
weighted formula. The weights express the relative importance of each
attribute.

  2. 2.

The lexicographic approach: It enforces a strict priority among attributes.

  3. 3.

The skyline (or Pareto as previously mentioned) approach: It is based on the
concept of dominance and it returns all objects that are not dominated by
other objects.

The lexicographic method is not covered by this document in detail. However,
its disadvantages are clear, a tuple may be better than another across all
attributes but the one with the highest priority and be discarded.

In this paper, an overview of the ranking and skyline methods is provided
along with a description of their pros and cons. Then, to overcome some of the
critical issues, a brief explanation of some evolved versions is given.
Finally, the main and final goal is to go into details of one of the
previously mentioned evolutions which is the flexible skylines paradigm. In
short, it consists of a mix between the top-ks and skylines which aims to get
the best of the two worlds.

The structure of the paper is organized as follows. Section 2 discusses
ranking queries while section 3 focuses on skylines. Section 4 contains the
list of some newer approaches and finally section 5 presents an entire module
devoted to flexible skylines. The aim of all sections before the fifth one is
to provide the reasons that made this approach necessary. F-skylines are
discussed in detail since they are the core topic of the document. Finally,
section 6 concludes the paper.

##  2 Ranking queries

Ranking queries, also called top-k queries, have been studied extensively and
are by far the most used approach for multi-criteria decision making. The
definition of Problem 1 has to be adapted to properly reflect what top-k
queries try to achieve.

###### Problem 2

Given N objects described by d (dimension) attributes in a data set and given
some notion of quality, possibly conflicting, for each attribute, find the
best k objects ordered according with their relevance.

In Problem 2, the notion of ranking is implicitly introduced and it represents
the arranging of objects accordingly with their significance. The importance
of a tuple with respect to another one, concept that defines the ranking, is
obtained by applying a so called scoring function.

The basic idea behind ranking queries is solving the multi-optimization
problem by transforming it into a single optimization one through a weighted
formula [9], called scoring function [7]. The most common and widespread cases
involve linear scoring functions, hence they will be the focus of the
discussion. The definition of the formula is as follow:

$F=w_{1}f_{1}+w_{2}f_{2}+..+w_{n}f_{n}$ (1)

where $F$ is the candidate’ score, $w_{i}$ is the weight assigned to the
$i$-th criteria $f$ and $n$ is the number of evaluation criteria [9]. It’s
clear that weights are an input that need to be either explicitly specified or
computed somehow. There are different know methods to obtain weights as shown
in [6]:

  1. 1.

The user is asked to insert directly the parameters or more conceivably some
preferences from which weights can be easily obtained.

  2. 2.

User’s activities are monitored and weights are learned from their habits.

  3. 3.

The preferences of multiple users are aggregated to obtain the needed
parameters (e.g. using crowdsourcing [8]).

An intuitive example of the top-k approach is provided without using a
specific algorithm; it will be useful also for pointing out some details
further in this paper.

Student | Math grade | Eng grade
---|---|---
Alex | 9 | 5
James | 10 | 1
Emma | 6 | 6
Robert | 6 | 4
John | 4 | 9
Table 1: Simple data set for examples.

###### Example 1

Consider the data set of Table 1 and the scoring function
$StudentScore=0.5*MathGrade+0.5*EngGrade$. We want to compute the top-2 query.
The computation procedure is shown only for one of the students, the rest can
be easily obtained in the same way: $AlexScore=0.5*9+0.5*5=7$. The ranking for
$k=2$ clearly is: Alex in first place and John in second place.

###  2.1 Pros and cons

Top-k queries are clearly a very simple, efficient and easy-to-use approach
and this probably explains why it is widespread. In addition, the ability to
control the size of the output and the trade-offs among attributes should not
be underestimated [4, 5, 7, 16]. However, this method is not free of drawbacks
and can have substantial disadvantages. First, ranking queries are essentially
aggregating different criteria and thus they are possibly mixing up different
units of measurements or, which is worse, non-commensurable criteria [9]. Data
normalization is certainly a possible solution but it requires specific
background knowledge and hence an ad-hoc solution for every domain. This
inconvenience may prevent its adoption in many areas that require general
solutions.

Last but not least, the elephant in the room is the setting of weights. First
of all, it is proven that it’s difficult to obtain the right values for
multiple reasons such as the fact that the user who inputs the data may not
themselves know their preferences. Moreover, it is really hard to estimate
what change could cause the modification of the weight’s vector [7]. The only
way to do it is to experiment by running it several times with different
values for the parameters, which evidently is not convenient and once again
would end up in an ad-hoc approach. Due to these facts, both making the user
inputs the parameters directly and computing them from user preferences does
not lead to a perfect solution. As shown in [8], some crowdsourcing techniques
proved helpful for overcoming this weakness at least to some extent.
Unfortunately, this is not enough to consider the problem solved because once
a combination of weights is found, then it’s hard to explore different
solutions to find a better setting, since it would require experiments
involving multiple runs to observe the impact on changes.

###### Example 2

Consider once more the data set of Table 1. A user may conceivably think that
the $StudentScore$ scoring function that gives to $MathGrade$ and to
$EngGrade$ the same weights is a good way of determining the best top $k=2$
students. But carefully looking at data, it is easy to notice that Emma may
never appear in the result even if she is the only student to have both grades
greater than six.

##  3 Skylines

Skyline queries are not based on an aggregate scoring function with weights,
but instead find their roots in the concept of pareto dominance. Again, as for
top-k queries, the definition of Problem 1 has to be adapted [15].

###### Problem 3

Given N objects described by d (dimension) attributes in a data set and given
some convention for assessing the attributes (e.g. usually lower values are
considered better): retrieve all objects which are not dominated by any other
object.

As seen, the notion of pareto dominance, or simply dominance, is key to
understanding skyline queries. [7, 9, 15, 12, 16, 11, 3]

###### Definition 1

Consider the tuples $t$ and $s$ belonging to a data set with schema $R$ over
$d$ dimensions and consider lower values as better. Then we can say that $t$
dominates $s$ if for each attribute, $t$ is never worse (greater or equal)
than $s$ and if for at least one attribute, $t$ is strictly better (less) than
$s$.

As a result of Definition 1, skylines can now be properly defined as well [5,
2]:

###### Definition 2

A skyline is the set of all non-dominated tuples or, alternatively and
equivalently, the set of potentially optimal tuples.

An example is included to show how skyline works. It will be used further to
discuss some characteristics of this technique.

$0$$2$$4$$6$$8$$10$$0$$2$$4$$6$$8$$10$dominatedskylineJohnEmmaAlexJamesRobertMath
gradeEng grade Figure 1:  Skyline for tuples from Table 1. Higher values are
better. The black dots are part of the skyline.

###### Example 3

We take as landmark the data set in Table 1 and then apply the skyline
operator. The results are shown graphically in Figure 1. The skyline is
composed of all students that are not dominated (e.g. no other student has a
greater or equal grade in both Math and Eng with at least one of the two
strictly greater). Reading the plot from left to right, we can find this set
of tuples in the skyline: John, Emma, Alex, James. The white dot, representing
Robert, is dominated by both Emma and Alex, thus it’s excluded.

Before moving on to the next section, it is worth noting that the concept of
skyline can be further generalized by introducing the concept of k-skybands
[7, 13]:

###### Definition 3

A k-skyband is the set of all tuples dominated by less than k other tuples.

It’s easy to note that a skyline is nothing else than a k-skyband with a
particular value of $k=1$. Another interesting aspect to consider consists in
the fact that the result of every top-k query is contained in the k-skyband
query executed on the same data set. Many k-skyband based approaches exist for
solving different problems (e.g. the one in [1]).

###  3.1 Pros and cons

Skylines completely solve the weights problem and this approach does not
require them to work properly [4, 5, 7, 9]. Actually, this approach is more
intuitive since it adapts itself to the multi-criteria optimization problem
while ranking queries transform the problem in a single-objective optimization
one [9].

Another advantage consists in the greater informative quality of the result.
Considering Example 3, it’s clear that all possible interesting tuples are
included in the result. Regrettably, there is another side of the coin. The
size of the result may increase too much especially when dealing with many
attributes $d$ and in the worst case it may reach the size of the entire data
set [15, 12, 16, 3]. The average user may be overwhelmed by the task of
choosing between many tuples [9, 16, 3]

Skylines are said to be more complex than ranking queries and usually a little
more expensive to compute but that doesn’t seem enough to overshadow the
previously mentioned advantages [4, 9]. Furthermore, the authors of [3]
provide an algorithm to parallelize the computation of skylines making this
technique suitable also in distributed scenarios.

Another drawback of this technique consists in the fact that it lacks a
feature for adjusting the relative importance of each attribute [12, 11].

###### Example 4

Consider the results obtained in Example 3. The skyline operator gave us all
the possible interesting results. We have Emma with a balance between grades,
James is the best in Math, Alex is good in Math and not so bad in Eng and
finally John has opposite grades to Alex. A user dealing with these tuples may
have a hard time choosing the best student. In a simple data set as the one
shown in Table 1, the skyline approach gave us almost the entire data set,
hence it’s evident that the situation could have been a lot worse in a real
world scenario.

##  4 Related work

In the previous sections disadvantages exhibited by ranking and skyline
queries have been deeply described. The scientific community has designed
multiple solutions to solve those problems. Usually, each of the solutions
start from one of the two classic methods and then either tries to mix them up
or consider adding new strategies.

In [6], the authors introduced an instance optimal algorithm called FSA to
compute top-k queries that do not require precise values of weights but just a
rough estimate. Their work is based on the concept of F-dominance that in this
document will be dealt with in greater depth in the next section where
F-skylines are analyzed.

Another possibility is shown in [16], where top-k dominating queries have been
studied. This technique consists in ranking queries with a particular scoring
function which, considering a tuple $t$ consists in the count of tuples
dominated by $t$. An optimized algorithm has been provided too.

A further study [13] has presented uncertain top-k queries (UTK) in which,
instead of avoiding the weighted approach, the provided algorithm takes into
account the weight uncertainties. The resulting query works using the concept
of dominance and tries to include in the result set also interesting results
within a certain range from the combination of weights.

Next, moving into more skyline based methods, there is [12] that adds
attribute importance (preferences) to skylines creating the p-skyline
framework. Incorporating preferences also reduces considerably the result
size. Unfortunately, this approach somehow requires user preferences and
limits the flexibility between dimensions.

An additional extension is the trade-off skyline paradigm [11]. As the name
suggests, they aim to introduce the concept of trade-off between attributes in
skylines. Despite this, the proposed algorithm is not so efficient and the
trade-off preferences require to be somehow elicited.

All presented solutions solve either some or even a great part of the common
problems that are usually encountered in multi-objective optimization, but
they all have some drawbacks.

##  5 Flexible skylines

Every approach is imperfect, but flexible skylines appear to solve most of the
issues with fewer problems compared to other methods. Their focus is to
enhance basic skylines by giving control of the result size [4]. Originally,
they were called restricted skylines (or r-skylines) [4, 5, 15] but newer
literature refers to them as flexible skylines [7]. Their foundation consists
in the decision of weakening the notion of pareto dominance [15]. This process
is accomplished by imposing a set of constraints on the scoring functions [4,
5, 7]. As a result, the notion of F-dominance has been obtained:

###### Definition 4

Consider the tuples $t$ and $s$ belonging to a data set with schema $R$ over
$d$ dimensions. Then we can say that $t$ $F$-dominates $s$ if for each
considered scoring function, $t$ is never worse than $s$ and if for at least
one scoring function, $t$ is strictly better than $s$.

The concept of F-dominance helps to greatly reduce the result set with respect
to the classic dominance. As a consequence of including the set of
constraints, F-skylines can adapt to user preference and hence they are more
flexible.

The definition of F-dominance leads to the definition of two different
F-skylines operators. They are respectively called ND and PO operators.

###### Definition 5

An ND F-skyline is the set of all non F-dominated tuples.

###### Definition 6

A PO F-skyline is the set of all potentially optimal tuples (i.e. top 1
according to some scoring function).

It is worth noting an interesting property of the F-skylines operators [4, 7]:

$PO\subseteq ND\subseteq SKY$ (2)

This shows clearly that the size of PO and ND result sets has to be smaller
than the size of the classic skyline (equal in the worst case). Additionally,
as said before, F-skylines offer the necessary flexibility that was missing in
the basic skylines and do not require precise weights (only constraints). It
is clear that F-skylines solve a great portion of the problems described in
previous sections.

###### Example 5

Consider the data set of Table 1 again and $F$ as the set of linear scoring
functions of the form $StudentScore=w_{1}*MathGrade+w_{2}*EngGrade$ such that
$w_{1}>w_{2}$. The PO result set is composed by the students Alex and James.
As expected, the result size is smaller than the one of the basic skyline.

Before moving on, there is another thing to take into account that our example
highlights. F-skylines successfully manage to reduce the size of the result
set, though they can’t estimate the exact size of the result before computing
it. This issue has been addressed in [14] where the two operators ORD and ORU
have been designed. Last but not least, the assessment of performances can be
found in the next subsection.

###  5.1 Algorithms

In [7] several algorithms to compute F-skylines have been introduced. The most
efficient between them are reported here along with a brief description.

Computing ND highly depends on how challenging the data set is. In case of a
challenging scenario, it is advised to use the SVE1F algorithm while in the
opposite case it is more suitable the SVE2 algorithm. The names of the
algorithms contain information to understand their behaviour.

  1. 1.

The S means that the algorithm Sorts the input data set, which is always
beneficial in ND computation.

  2. 2.

The VE part means that the algorithm works with the Vertex Enumeration
strategy which is usually faster than applying linear programming.

  3. 3.

The digit points out the number of phases required. Number 2 means that ND is
computed from the classic skyline.

  4. 4.

The F means that the algorithm interleaves dominance and F-dominance during
its execution.

The best method to compute PO is always starting from ND and then applying the
PODI2 algorithm, which behaves well in all scenarios.

  1. 1.

The PO part means that the algorithm computes the PO operator.

  2. 2.

The D part means that F-dominance is checked through a dual PO test which
usually leads to better performances than the primal test.

  3. 3.

The I means that an incremental approach is being used.

  4. 4.

The digit points out the number of phases required. Number 2 means that PO is
computed from the ND F-skyline.

In the cited article it is proven that the performances of F-skylines are
usually better than normal skylines (computed with the famous SFS [7, 3]) when
computing ND and in line with them for what concerns PO. This confirms the
fact that F-skylines can be used in place of normal skylines without worrying.
Unfortunately, they lose in the comparison of computational time with ranking
queries. The increased capability of exploring interesting results comes with
a price. However, as for basic skylines, F-skylines can be extended to work in
a parallel or distributed environment.

##  6 Conclusion

This paper has presented a list of approaches for dealing with multi-objective
optimization in data sets from classic methods to newly designed ones. This
review has shown how top-k queries and skylines work along with their
advantages and disadvantages, highlighting their weaknesses. Next, a list of
methods aiming to overcome the previously mentioned difficulties has been
presented, up to the flexible skyline paradigm, which solves most of
(unfortunately not all) the problems that arise with others solutions.
F-skylines have been deeply analyzed and some of the most efficient algorithms
to compute them have been presented. Another interesting approach that has
been mentioned but not investigated in detail is the ORD and ORU operators
that managed to solve one of the few F-skylines drawbacks.

In conclusion, even if flexible skylines are not a panacea for multi-objective
optimization, it sure is one of the most valid approaches and it is worth
keeping an eye on their possible evolution and applicability. In the future,
investigating further optimizations of this method may be interesting and the
remaining drawbacks of this approach may be solved.

## References

  * [1] Marcos Bedo, Paolo Ciaccia, Davide Martinenghi, and Daniel de Oliveira.  A k–skyband approach for feature selection.  In 12th International Conference, SISAP 2019, Newark, NJ, USA, October 2–4, 2019, pages 160–168. Springer Link, 2019.
  * [2] S. Borzsony, D. Kossmann, and K. Stocker.  The skyline operator.  In Proceedings 17th International Conference on Data Engineering, ICDE 2001, Heidelberg, Germany, 2-6 April 2001. IEEE, 2001.
  * [3] Jan Chomicki, Paolo Ciaccia, and Niccolo’ Meneghetti.  Skyline queries, front and back.  ACM SIGMOD Record, 42(3):6–18, 2013.
  * [4] Paolo Ciaccia and Davide Martinenghi.  Reconciling skyline and ranking queries.  Proceedings of the VLDB Endowment, 10(11):1454–1465, 2017.
  * [5] Paolo Ciaccia and Davide Martinenghi.  Beyond skyline and ranking queries: Restricted skylines.  In Proceedings of the 26th Italian Symposium on Advanced Database Systems, SEBD, Castellaneta Marina (Taranto), Italy , July 24 - 27, 2018, pages 1–8. CEUR Workshop Proceedings, 2018.
  * [6] Paolo Ciaccia and Davide Martinenghi.  ${FA}+{TA}<{FSA}$: Flexible score aggregation.  In Proceedings of the 27th ACM International Conference on Information and Knowledge Management, CIKM 2018, Torino, Italy, October 22 \- 26, 2018, pages 57–66. ACM, 2018.
  * [7] Paolo Ciaccia and Davide Martinenghi.  Flexible skylines: Dominance for arbitrary sets of monotone functions.  ACM Transactions on Database Systems (TODS), 45(4):1–45, 2020.
  * [8] Eleonora Ciceri, Piero Fraternali, Davide Martinenghi, and Marco Tagliasacchi.  Crowdsourcing for top-k query processing over uncertain data.  IEEE Transactions on Knowledge and Data Engineering, 28(1):41–53, 2016.
  * [9] Alex A. Freitas.  A critical review of multi-objective optimization in data mining: a position paper.  SIGKDD Explorations, 6(2):77–86, 2004.
  * [10] Nyoman Gunantara.  A review of multi-objective optimization: Methods and its applications.  Cogent Engineering, 5(1):1–16, 2018.
  * [11] Christoph Lofi, Ulrich Güntzer, and Wolf-Tilo Balke.  Efficient computation of trade-off skylines.  In Proceedings of the 13th International Conference on Extending Database Technology, EDBT 2010, Lausanne, Switzerland, September March 22 - 26, 2010, pages 597–608. ACM, 2010.
  * [12] D Mindolin and J Chomicki.  Discovering relative importance of skyline attributes.  In Proceedings of the VLDB Endowment, VLDB 2009, Lyon, France, August 24-28, 2005, pages 610–621. ACM, 2005.
  * [13] Kyriakos Mouratidis and Bo Tang.  Exact processing of uncertain top-k queries in multi-criteria settings.  Proceedings of the VLDB Endowment, 11(8):866–879, 2018.
  * [14] Kyriakos Mouratidis and Bo Tang.  Marrying top-k with skyline queries: Relaxing the preference input while producing output of controllable size.  In Proceedings of the 2021 International Conference on Management of Data, SIGMOD 2021, Virtual event, China, June 20 - 25, 2021, pages 1317–1330. ACM, 2021.
  * [15] Balke W. T. and U. Güntzer.  Efficient skyline queries under weak pareto dominance.  In IJCAI-05 Multidisciplinary Workshop on Advances in Preference Handling, PREFERENCE 2005, Edinburgh, UK, 2005, 2005.
  * [16] ML Yiu and N Mamoulis.  Efficient processing of top-k dominating queries on multi-dimensional data.  In Proceedings of the VLDB Endowment, VLDB 2007, Vienna, Austria, September 23-28, 2007, pages 483–494. ACM, 2007.