# Pantomorphic Perspective for Immersive Imagery

Jakub Maksymilian Fober  0000-0003-0414-4223<EMAIL_ADDRESS>
(February 2021; July 2021)

###### Abstract.

A wide choice of cinematic lenses enables motion-picture creators to adapt
image visual-appearance to their creative vision. Such choice does not exist
in the realm of real-time computer graphics, where only one type of
perspective projection is widely used. This work provides a perspective
imaging model that in an artistically convincing manner resembles anamorphic
photography lens variety and more. It presents an asymmetrical-anamorphic
azimuthal projection map with natural vignetting and realistic chromatic
aberration. The mathematical model for this projection has been chosen such
that its parameters reflect the psycho-physiological aspects of visual
perception. That enables its use in artistic and professional environments,
where specific aspects of the photographed space are to be presented.

Curvilinear Perspective, Panini, Pantomorphic, Cylindrical, Fisheye,
Perspective Map

††ccs: Computing methodologies Perception††ccs: Computing methodologies Ray
tracing††ccs: Human-centered computing††ccs: Applied computing Media arts

© 2024 Jakub Maksymilian Fober

This work is licensed under Creative Commons BY-NC-ND 3.0 license.
https://creativecommons.org/licenses/by-nc-nd/3.0/
For all other uses including commercial, contact the owner/author(s).

##  1\. Introduction

The perspective in computer real-time graphics hasn’t changed since the dawn
of CGI. It is based on a concept as old as the fifteenth century Renaissance,
a linear projection (Alberti, 1435; Argan and Robb, 1946; McArdle, 2013). This
situation is similar to the beginnings of photography, where only one type of
lens was widely used, an A.D. 1866 _Rapid Rectilinear_ (Kingslake, 1989) lens.
Linear perspective even at the time of its advent, 500 years ago, has been
criticized for distorting proportions (Da Vinci, 1632). In a phenomenon known
today as _Leonardo’s paradox_ (Dixon, 1987), in which figures further away but
at the periphery appear larger, than those located near the optical center.
Computer graphics really skipped the artistic achievements of the last five
centuries in regard to perspective. This includes the cylindrical perspective
of Pannini (Sharpless et al., 2010), Barker (Wikipedia, contributors, 2019)
and anamorphic lenses used in cinematography (Sasaki, 2017b, a; Giardina,
2016; Neil, 2004). The situation is even more critical, as there is no
mathematical model for generating anamorphic projection in an artistically-
convincing manner (Yuan and Sasian, 2009). Some attempts were made at
alternative projections for computer graphics, with fixed cylindrical or
spherical geometry (Sharpless et al., 2010; Baldwin et al., 2014). A
parametrized perspective model was also proposed as a new standard (Correia
and Romão, 2007), but wasn’t adopted. It included interpolation states in
between rectilinear/equidistant and spherical/cylindrical projection. The
cylindrical parametrization of this solution was merely an interpolation
factor, where intermediate values did not correspond to any common projection
type. Therefore it was not suited for artistic or professional use. The notion
of sphere as a projective surface, which incorporates cartographic mapping to
produce a perspective picture became popularized (Peñaranda et al., 2015;
German et al., 2007; Williams, 2015). Also, perspective parametrization that
transitions according to the content (by the view-tilt angle) has been
developed, as a modification to the computer game Minecraft (Williams, 2017).
But the results of these solutions were more a gimmick and have not found
practical use. The linear perspective projection is still the way-to-go for
most digital content. One of the reasons is the GPU fixed-function
architecture in regard to rasterization. With the advent of real-time ray-
tracing, more exotic projections could become widely adopted.

This paper aims to provide a perspective model with mathematical
parametrization that gives artistic-style interaction with image-geometry. It
is a parametrization that works similarly to the way film directors choose
lenses for each scene by their aesthetics (Giardina, 2016; Sasaki, 2017a;
Neil, 2004), but with a greater degree of control. It also provides a psycho-
physiological correlation between perspective model parameters and the
perception of depicted space attributes, like distance, size, proportions,
shape or speed. That mapping enables the use of the presented model in a
professional environment, where image geometry is specifically suited for a
task (Whittaker, 1984).

The presented perspective model is named _pantomorphic_ (G. _panto-_ , all
_+morphē_ , shape; assuming all shapes).

###  1.1. Document naming convention

This document uses the following naming convention:

  * •

Left-handed coordinate system.

  * •

Vectors presented natively in column.

  * •

Matrix vectors arranged in rows (row-major order)
$M_{\text{row}\,\text{col}}$.

  * •

Matrix-matrix multiplication by
$[\text{column}]_{a}\cdot[\text{row}]_{b}=M_{a\,b}$.

  * •

A single bar enclosure “$|u|$” represents vector length or scalar absolute.

  * •

Vectors with an arithmetic sign, or without, are calculated component-wise and
form another vector.

  * •

Centered dot “$\cdot$” represents the vector dot product.

  * •

Square brackets with a comma “$[f,c]$” denote interval.

  * •

Square brackets with blanks “$[x\ y]$” denote vector and matrix.

  * •

The power of “-1” signifies the reciprocal of the value.

  * •

QED symbol “$\square$” marks the final result or output.

This naming convention simplifies the transformation process of formulas into
code.

##  2\. Anamorphic primary-ray map

(a) Graph mapping angle $\varphi$, to anamorphic interpolation weights
$\vec{\varphi}_{x}$ and $\vec{\varphi}_{y}$. Illustrates circular distribution
of $\vec{\varphi}$, in a periodic function.

(b) Radial graph, mapping anamorphic interpolation weights $\vec{\varphi}_{x}$
and $\vec{\varphi}_{y}$ (as radius $r$), to angle $\varphi$ in radians. Such
that $\vec{\varphi}_{x}+\vec{\varphi}_{y}=1$.

(c) Radial graph illustrating anamorphic interpolation vector
$\vec{\varphi}\in[0,1]^{2}$. Here colors _red_ , _green_ , _blue_ represent
contribution of $\vec{k}_{x}$, $\vec{k}_{y}$ and $\vec{k}_{z}$ respectively.

Figure 1. Illustrating correlation between the anamorphic interpolation
weights $\vec{\varphi}_{x}$, $\vec{\varphi}_{y}$ and the spherical angle
$\varphi$.

If we assume that projective visual space is spherical (McArdle, 2013; Fleck,
1994), one can define perspective picture as an array of rays pointing to the
visual sphere surface. This is how _the algorithm_ described below will output
_a projection-map_ (aka _perspective-map_). Perspective map is an array of
three-dimensional rays, which are assigned to each screen-pixel. Visual sphere
as the image model enables a wider angle of view, beyond 180°-limit of planar
projection. Ray-map can be easily converted to cube-$UV$-map, $ST$-map and
other screen distortion formats.

Here, the procedural algorithm for primary-ray map (aka perspective map) uses
two input values from the user: distortion parameter for two power axes and
_focal-length_ or _angle-of-view_ (aka FOV). Two distinct power axes define
the anamorphic projection type. Each axis is expressed by the azimuthal
projection factor $k$ (Krause, 2019; Bettonvil, 2005; Fleck, 1994). Both power
axes share the same focal-length $f$. Evaluation of each power-axis produces
spherical angles $\vec{\theta}_{x}$ and $\vec{\theta}_{y}$, which are then
combined to anamorphic azimuthal-projection angle $\theta^{\prime}$.
Interpolation of $\theta$ is done through anamorphic weights
$\vec{\varphi}_{x}$ and $\vec{\varphi}_{y}$. Weights are derived from
spherical angle $\varphi$, of the azimuthal projection. To note, calculation
of $\varphi$ is omitted here, by using view-coordinates
$\vec{v}$-optimization.

(1a) $\displaystyle r$
$\displaystyle=|\vec{v}|=\sqrt{\vec{v}^{2}_{x}+\vec{v}^{2}_{y}}$ (1b)
$\displaystyle\vec{\theta}_{x}$
$\displaystyle=\begin{cases}\frac{\operatorname{arctan}\big{(}\frac{r}{f}\vec{k}_{x}\big{)}}{k_{x}},&\text{if
}\vec{k}_{x}>0\\\ \frac{r}{f},&\text{if }\vec{k}_{x}=0\\\
\frac{\operatorname{arcsin}\big{(}\frac{r}{f}\vec{k}_{x}\big{)}}{k_{x}},&\text{if
}\vec{k}_{x}<0\\\ \end{cases}$ (1c) $\displaystyle\vec{\theta}_{y}$
$\displaystyle=\begin{cases}\frac{\operatorname{arctan}\big{(}\frac{r}{f}\vec{k}_{y}\big{)}}{k_{y}},&\text{if
}\vec{k}_{y}>0\\\ \frac{r}{f},&\text{if }\vec{k}_{y}=0\\\
\frac{\operatorname{arcsin}\big{(}\frac{r}{f}\vec{k}_{y}\big{)}}{k_{y}},&\text{if
}\vec{k}_{y}<0\\\ \end{cases}$ (1d)
$\displaystyle\begin{bmatrix}\vec{\varphi}_{x}\\\
\vec{\varphi}_{y}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\frac{\vec{v}^{2}_{x}}{\vec{v}^{2}_{x}+\vec{v}^{2}_{y}}\vskip
3.0pt plus 1.0pt minus 1.0pt\\\
\frac{\vec{v}^{2}_{y}}{\vec{v}^{2}_{x}+\vec{v}^{2}_{y}}\end{bmatrix}=\begin{bmatrix}\cos^{2}\varphi\\\
\sin^{2}\varphi\end{bmatrix}=\begin{bmatrix}\frac{1}{2}+\frac{\cos(2\varphi)}{2}\vskip
3.0pt plus 1.0pt minus 1.0pt\\\
\frac{1}{2}-\frac{\cos(2\varphi)}{2}\end{bmatrix},$

where $r\in\mathbb{R}_{>0}$ is the view-coordinate radius (magnitude). Vector
$\vec{\theta}\in[0,\pi]^{2}$ contains incident angles (measured from the
optical axis) of two azimuthal projections. Vector $\vec{\varphi}\in[0,1]^{2}$
is the anamorphic interpolation weight, which is linear
$\vec{\varphi}_{x}+\vec{\varphi}_{y}=1$, but has spherical distribution (see
Figure 1). Vector $\vec{k}\in[-1,1]^{2}$ (also $[-1,1]^{3}$ in subsection 2.2
variant) describes two power axes of anamorphic projection. The algorithm is
evaluated per-pixel of position $\vec{v}\in\mathbb{R}^{2}$ in view-space
coordinates, centered at the optical axis and normalized at the chosen angle-
of-view (horizontal or vertical). The final anamorphic incident angle
$\theta^{\prime}$ is obtained by interpolation, using $\vec{\varphi}$ weights.

(2a) $\displaystyle\theta^{\prime}$
$\displaystyle=\begin{bmatrix}\vec{\theta}_{x}\\\
\vec{\theta}_{y}\end{bmatrix}\cdot\begin{bmatrix}\vec{\varphi}_{x}\\\
\vec{\varphi}_{y}\end{bmatrix}$ (2b)
$\displaystyle\begin{bmatrix}\hat{G}_{x}\\\ \hat{G}_{y}\\\
\hat{G}_{z}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\frac{\sin\theta^{\prime}}{r}\begin{bmatrix}\vec{v}_{x}\\\
\vec{v}_{y}\end{bmatrix}\\\
\cos\theta^{\prime}\end{bmatrix}=\begin{bmatrix}\sin\theta^{\prime}\begin{bmatrix}\cos\varphi\\\
\sin\varphi\end{bmatrix}\\\ \cos\theta^{\prime}\end{bmatrix},\qed$

here $\theta^{\prime}\in(0,\pi]$ is the anamorphic incident angle, measured
from the optical axis. This measurement resembles azimuthal projection of the
globe (here a visual sphere) (McArdle, 2013). The final incident vector
$\hat{G}\in[-1,1]^{3}$ (aka primary-ray) is obtained from the anamorphic angle
$\theta^{\prime}$. Parameters $r,\vec{v},\vec{\varphi}$ are in view-space,
while $\vec{\theta},\theta^{\prime},\varphi,\hat{G}$ are in visual-sphere
space. Essentially the anamorphic primary-ray map preserves the azimuthal
angle $\varphi$, while modulating only the picture’s radius.

###  2.1. Focal length and angle-of-view

To give more control over the picture, a mapping between angle-of-view
$\Omega$ and focal-length $f$ can be established. Here, focal-length is
derived in a reciprocal from, to optimize usage in Equation (1).

(3)
$f^{-1}\big{(}\Omega_{h}\big{)}=\begin{cases}\frac{\tan\big{(}\frac{\Omega_{h}}{2}\vec{k}_{x}\big{)}}{\vec{k}_{x}},&\text{if
}\vec{k}_{x}>0\\\ \frac{\Omega_{h}}{2},&\text{if }\vec{k}_{x}=0\\\
\frac{\sin\big{(}\frac{\Omega_{h}}{2}\vec{k}_{x}\big{)}}{\vec{k}_{x}},&\text{if
}\vec{k}_{x}<0\end{cases},$

where $\Omega_{h}\in(0,\tau]$ denotes a horizontal angle of view. Similarly,
vertical $\Omega_{v}$ can be obtained using $\vec{k}_{y}$ parameter instead.
The resultant value $\nicefrac{{1}}{{f}}\in\mathbb{R}_{>0}$ is the reciprocal
focal-length.

######  Remark.

Focal-length $f$ value must be same for $\vec{\theta}_{x}$ and
$\vec{\theta}_{y}$. Therefore, only one reference angle $\Omega$ can be
chosen, either horizontal or vertical.

Inverse function to Equation (3), for angle-of-view $\Omega$ from focal-length
$f$, is obtained as follows

(4)
$\Omega_{v}\big{(}f\big{)}=\begin{cases}\frac{2\operatorname{arctan}\big{(}\frac{\vec{k}_{y}}{f}\big{)}}{\vec{k}_{y}},&\text{if
}\vec{k}_{y}>0\\\ \frac{2}{f},&\text{if }\vec{k}_{y}=0\\\
\frac{2\operatorname{arcsin}\big{(}\frac{\vec{k}_{y}}{f}\big{)}}{\vec{k}_{y}},&\text{if
}\vec{k}_{y}<0\end{cases}$

This formula can be used to obtain the actual vertical angle-of-view from a
horizontally established focal length. Similarly horizontal angle $\Omega_{h}$
can be obtained using the $\vec{k}_{x}$ parameter. Diagonal angle $\Omega_{d}$
can be obtained using interpolation by $\vec{\varphi}$.

Value of $k$ | Azimuthal projection type
---|---
$k_{i}=$ | $1$ | Rectilinear (aka Gnomonic)
$k_{i}=$ | $\nicefrac{{1}}{{2}}$ | Stereographic
$k_{i}=$ | $0$ | Equidistant
$k_{i}=$ | $-\nicefrac{{1}}{{2}}$ | Equisolid
$k_{i}=$ | $-1$ | Orthographic (azimuthal)

_Source:_ PTGui 11 fisheye factor (Krause, 2019).

(a) Azimuthal projection type and corresponding $k$ value.

Azimuthal projection type | Perception of space
---|---
Rectilinear | straightness
Stereographic | shape, angle
Equidistant | speed, aim
Equisolid | distance, size
Orthographic (azimuthal) | —

_Source:_ Empirical study using various competitive video games.

(b) Correct perception of space attributes and corresponding azimuthal
projection type.

Table 1. Tables presenting perspective parameters, corresponding projection
type and associated perception attitude.

###  2.2. Asymmetrical anamorphism

Parameter $\vec{k}_{y}$ can be further argumented to produce asymmetrical
anamorphic projection through the incorporation of a third parameter
$\vec{k}_{z}$. In such a case, the bottom and top half of the image can
present different azimuthal projection.

(5) $\vec{k}_{y}^{\prime}=\begin{cases}\vec{k}_{z},&\text{if }\vec{v}_{y}<0\\\
\vec{k}_{y},&\text{otherwise}\end{cases}$

therefore $\vec{k}_{y}^{\prime}$ replaces $\vec{k}_{y}$ in equations (1), (4)
and (6).

Asymmetrical anamorphism can be applied to any power axis. The use case for
such a perspective would be racing, where the bottom-half of the screen
contains an image of the road. Choosing equidistant projection (which
preserves angular speed), would provide an accurate perception of velocity.
The top-half of the screen contains the image of opponent vehicles. Choosing
equisolid projection (which preserves area) would provide an enhanced
perception of distance. For the horizontal power axis, choosing stereographic
projection (which preserves angles and proportions), would enhance cornering.

###  2.3. Vignetting mask

Vignetting is an important visual symbol indicating stretching of the visual
sphere by the projection. Incorporating the vignetting effect enhances space
perception.

Here, anamorphic vignetting mask $\Lambda^{\prime}$ is obtained similarly to
anamorphic angle $\theta^{\prime}$. Two separate vignetting masks,
$\vec{\Lambda}_{x}$ and $\vec{\Lambda}_{y}$ are generated for each power axis
and combined to a single anamorphic vignette $\Lambda^{\prime}$ by
interpolation through $\vec{\varphi}$-weights.

(6a) $\displaystyle\begin{bmatrix}\vec{\Lambda}_{x}\\\
\vec{\Lambda}_{y}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\big{|}\cos\big{(}\max\big{\\{}|\vec{k}_{x}|,\frac{1}{2}\big{\\}}\vec{\theta}_{x}\big{)}\big{|}^{\frac{k_{x}+3}{2}}\\\
\vskip 3.0pt plus 1.0pt minus
1.0pt\big{|}\cos\big{(}\max\big{\\{}|\vec{k}_{y}|,\frac{1}{2}\big{\\}}\vec{\theta}_{y}\big{)}\big{|}^{\frac{k_{y}+3}{2}}\end{bmatrix}$
(6b) $\displaystyle\Lambda^{\prime}$
$\displaystyle=\begin{bmatrix}\vec{\Lambda}_{x}\\\
\vec{\Lambda}_{y}\end{bmatrix}\cdot\begin{bmatrix}\vec{\varphi}_{x}\\\
\vec{\varphi}_{y}\end{bmatrix},\qed$

where $\Lambda^{\prime}\in[0,1]$ is the anamorphic vignetting mask value,
interpolated using circular-function-vector $\vec{\varphi}$.

The vignette mask of each axis is obtained using two laws of illumination
falloff. Inverse-square law (for $k=1$) and the cosine law of illumination
(for $k=-1$). The vignette value for _cosine law_ is simply expressed as
$\cos\theta$. _Inverse-square law_ value can be expressed as $\cos^{2}\theta$.
Therefore the value for projections other than $k\in\\{-1,1\\}$ must have a
vignetting value in-between $\cos^{1}\theta\leftrightarrow\cos^{2}\theta$.
This has been empirically evaluated to a power value linearly-mapped from
$k\in[-1,1]\mapsto[1,2]$.

Figure 2. Graph illustrating interpolation parameters for anamorphic
vignetting (represented by vertical axis), driven by parameter $k\in[-1,1]$
(represented by horizontal axis). _The power_ -graph
$\big{(}\frac{k+3}{2}\big{)}$ interpolates between _the cosine law of
illumination_ and _inverse-square law_ vignetting. _$\theta$ -scale _ graph
scales the vignetting boundary to maximum $\Omega$ for given $k$.

Picture content type | Anamorphic $\vec{k}$ values
---|---
Racing simulation | $\vec{k}=[$ | $\nicefrac{{1}}{{2}}$ | $-\nicefrac{{1}}{{2}}$ | $0$ | $]$
Flying simulation | $\vec{k}=[$ | $-\nicefrac{{1}}{{2}}$ | $0$ | $]$ |
Stereopsis (cyclopean) | $\vec{k}=[$ | $0$ | $-\nicefrac{{1}}{{2}}$ | $]$ |
First-person aiming | $\vec{k}=[$ | $0$ | $\nicefrac{{3}}{{4}}$ | $-\nicefrac{{1}}{{2}}$ | $]$
Pan motion | $\vec{k}_{x}\neq\vec{k}_{y}$
Roll motion | $\vec{k}_{y}=\vec{k}_{x}$
Tilt motion _a_ | $\vec{k}_{y}\rightarrow\vec{k}_{x}$

_Source:_ Determined empirically using various competitive video games, in
accordance to data in Table 1(b).

_a_ Mapping of vertical distortion by a tilt motion introduced first in a
Minecraft mod (Williams, 2017).

Table 2. Recommended values of $\vec{k}$, for various types of content.

(a)
$\vec{k}=\big{[}0\quad\nicefrac{{3}}{{4}}\quad-\nicefrac{{1}}{{2}}\big{]}$,
(asymmetrical) first-person.

(b) $\vec{k}=\big{[}\nicefrac{{1}}{{2}}\quad-\nicefrac{{1}}{{2}}\quad
0\big{]}$, (asymmetrical) racing.

(c) $\vec{k}=\big{[}-\nicefrac{{1}}{{2}}\quad 0\big{]}$, flying.

(d) $\vec{k}=\big{[}\nicefrac{{1}}{{2}}\quad 1\big{]}$, panini.

Figure 3. Example of various wide-angle ($\Omega_{v}=100\text{\textdegree}$)
anamorphic-azimuthal projections with vignetting in 16:9 aspect-ratio. The
checkerboard depicts a cube centered at the view-position, with each face
colored according to axis direction. Here, primary colors represent the
positive axis and complementary colors its opposite equivalent (same as in the
color-wheel), $\\{Cy,Mg,Yl\\}\mapsfrom-\ \\{X,Y,Z\\}\ +\mapsto\\{R,G,B\\}$.

##  3\. Converting ray-map to ST-map

Ray/perspective-map can be easily converted to _ST_ -map format, given that
the maximum view angle $\Omega$ does not exceed or isn’t equal to 180°.

(7a) $\displaystyle\begin{bmatrix}\vec{a}_{x}&\vec{a}_{y}\end{bmatrix}$
$\displaystyle=\begin{cases}\begin{bmatrix}1&\frac{w}{h}\end{bmatrix},&\text{if
}\Omega_{h}\vskip 3.0pt plus 1.0pt minus 1.0pt\\\
\begin{bmatrix}\frac{h}{w}&1\end{bmatrix},&\text{if }\Omega_{v}\end{cases}$
(7b) $\displaystyle\begin{bmatrix}\vec{f}_{s}\\\ \vec{f}_{t}\end{bmatrix}$
$\displaystyle=\frac{\cot\frac{\Omega}{2}}{2\hat{G}_{z}}\begin{bmatrix}\hat{G}_{x}\\\
\hat{G}_{y}\end{bmatrix}\begin{bmatrix}\vec{a}_{x}\\\
\vec{a}_{y}\end{bmatrix}+\frac{1}{2},\qed$

where $\vec{a}\in\mathbb{R}^{2}$ is the square-mapping vector for both the
horizontal and vertical angle of view. Values $w$ and $h$ represent picture
width and height, respectively. $\Omega<\pi$ is the angle of view.
$\vec{f}\in[0,1]^{2}$ represent the final _ST_ -map vector.
$\hat{G}\in[0,1]^{3}$ is the input primary-ray map vector.

##  4\. Anamorphic lens distortion

The presented perspective model can be used to mimic the real-world anamorphic
lens and its effects. Effects such as _disproportionate lens breathing_ using
focal length-based parametrization, which are unique to anamorphic photography
(Sasaki, 2017b; Neil, 2004). Some additional lens-corrections may be added to
the initial ray-map, to simulate more complex lens distortion and lens
imperfections.

Below an algorithm for anamorphic distortion of view coordinates is presented,
which can be used as an input for primary-ray map algorithm (Equation 1). It
is based on the _Brown-Conrady_ lens-distortion model (Wang et al., 2008) in a
division variant (Fitzgibbon, 2001). It is executed on view-coordinates
$\vec{v}$, forming alternative vector $\vec{v}^{\prime}$.

(8a) $\displaystyle\begin{bmatrix}\vec{f}_{x}\\\ \vec{f}_{y}\end{bmatrix}$
$\displaystyle=\underbrace{\begin{bmatrix}\vec{v}_{x}-\vec{c}_{1}\\\
\vec{v}_{y}-\vec{c}_{2}\end{bmatrix}}_{\text{cardinal offset \emph{a}}}$ (8b)
$\displaystyle\begin{bmatrix}\vec{\varphi}_{x}\\\
\vec{\varphi}_{y}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\frac{\vec{f}^{2}_{x}}{\vec{f}^{2}_{x}+\vec{f}^{2}_{y}}&\frac{\vec{f}^{2}_{y}}{\vec{f}^{2}_{x}+\vec{f}^{2}_{y}}\end{bmatrix}^{\mathsf{T}}$
(8c) $\displaystyle r^{2}$ $\displaystyle=\vec{f}^{2}_{x}+\vec{f}^{2}_{y}$
(8d) $\displaystyle\begin{split}\begin{bmatrix}\vec{v}^{\prime}_{x}\\\
\vec{v}^{\prime}_{y}\end{bmatrix}&=\begin{bmatrix}\vec{f}_{x}\\\
\vec{f}_{y}\end{bmatrix}\underbrace{\Bigg{(}\begin{bmatrix}1+\vec{k}_{x1}r^{2}+\vec{k}_{x2}r^{4}\cdots\\\
1+\vec{k}_{y1}r^{2}+\vec{k}_{y2}r^{4}\cdots\end{bmatrix}\cdot\begin{bmatrix}\vec{\varphi}_{x}\\\
\vec{\varphi}_{y}\end{bmatrix}\Bigg{)}^{-1}}_{\text{radial anamorphic}}\qed\\\
&\quad+\underbrace{\begin{bmatrix}\vec{f}_{x}\\\
\vec{f}_{y}\end{bmatrix}\left(\begin{bmatrix}\vec{f}_{x}\\\
\vec{f}_{y}\end{bmatrix}\cdot\begin{bmatrix}\vec{p}_{1}\\\
\vec{p}_{2}\end{bmatrix}\right)}_{\text{decentering}}+\underbrace{r^{2}\begin{bmatrix}\vec{q}_{1}\\\
\vec{q}_{2}\end{bmatrix}}_{\text{thin
prism}}+\underbrace{\begin{bmatrix}\vec{c}_{1}\\\
\vec{c}_{2}\end{bmatrix}}_{\text{cardinal \emph{b}}}\square\end{split}$ (8e)
$\displaystyle\begin{bmatrix}\vec{v}^{\prime}_{x}\\\
\vec{v}^{\prime}_{y}\end{bmatrix}$
$\displaystyle\mapsto\begin{bmatrix}\hat{G}_{x}\\\ \hat{G}_{y}\\\
\hat{G}_{z}\end{bmatrix},\qed$

where $\vec{c}_{1},\vec{c}_{2}$ are the cardinal-offset parameters,
$\vec{q}_{1},\vec{q}_{2}$ are the thin-prism distortion parameters and
$\vec{p}_{1},\vec{p}_{2}$ are the decentering parameters. A set of $\vec{k}$
parameters define radial distortion for each anamorphic power axis. $\vec{v}$
is the input view-coordinate, and $\vec{v}^{\prime}$ is the view coordinate
with applied lens-transformation. $\vec{\varphi}\in[0,1]^{2}$ is the
anamorphic interpolation weight, defined in Section 2.

##  5\. Anamorphic chromatic aberration

Figure 4. Graph mapping of $t\in[0,1]$ to spectral color
$\vec{\chi}\in[0,1]^{3}$, for simulation of chromatic aberration. This is an
output of periodic function found in Equation (9). The distribution of values
ensures proper color order and sum-of-samples with a neutral-white tint.

A chromatic aberration effect can be achieved with multi-sample blur, where
each sample layer is colored with the corresponding spectral-value (Gilcher,
2015). Presented periodic function for spectral color $\vec{\chi}$ produces
samples that always add up to 1 (neutral white) when their number is even. It
also presents the correct order of spectrum colors.

(9) $\begin{bmatrix}\vec{\chi}_{r}\\\ \vec{\chi}_{g}\\\
\vec{\chi}_{b}\end{bmatrix}=\operatorname*{clamp}_{0}^{1}\bigg{(}\frac{3}{2}-\big{|}4\bmod\Bigg{(}t+\begin{bmatrix}\nicefrac{{1}}{{4}}\\\
0\\\ \nicefrac{{3}}{{4}}\end{bmatrix},1\Bigg{)}-2\big{|}\bigg{)},$

where $\vec{\chi}\in[0,1]^{3}$ is the spectral-color value for position
$t\in[0,1]$. See Figure 4 for more information.

Performing a spectral blur on an image involves the multi-sample sum of
spectrum-colored layers. Here $t$ (replaced by sample progress) never reaches
1, which preserves picture white-balance. The number of samples $n$ must be an
even number, no less than 2 for a correct result.

(10) $\begin{bmatrix}\vec{f}^{\prime}_{r}\vskip 3.0pt plus 1.0pt minus
1.0pt\\\ \vec{f}^{\prime}_{g}\vskip 3.0pt plus 1.0pt minus 1.0pt\\\
\vec{f}^{\prime}_{b}\end{bmatrix}=\frac{2}{n}\sum_{i=0}^{n-1}\begin{bmatrix}\vec{f}_{r}\vskip
3.0pt plus 1.0pt minus 1.0pt\\\ \vec{f}_{g}\vskip 3.0pt plus 1.0pt minus
1.0pt\\\
\vec{f}_{b}\end{bmatrix}\underbrace{\operatorname*{clamp}_{0}^{1}\bigg{(}\frac{3}{2}-\big{|}4\bmod\Bigg{(}\frac{i}{n}+\begin{bmatrix}\nicefrac{{1}}{{4}}\\\
0\\\
\nicefrac{{3}}{{4}}\end{bmatrix},1\Bigg{)}-2\big{|}\bigg{)}}_{\vec{\chi}\text{
periodic function}},$

where $n\in 2\mathbb{N}_{1}$ is the even number of samples for the chromatic
aberration color-split. $\vec{f}\in[0,1]^{3}$ is the current-sample position
color-value. $\vec{f}^{\prime}\in[0,1]^{3}$ is the final spectral-blurred
color value.

The equation for spectral color $\vec{\chi}$ can be rewritten to a more
computationally optimized form.

(11) $\begin{bmatrix}\vec{\chi}_{r}\\\ \vec{\chi}_{g}\\\
\vec{\chi}_{b}\end{bmatrix}=\begin{bmatrix}\hfill\operatorname*{clamp}_{0}^{1}\big{(}\nicefrac{{3}}{{2}}-|4t-1|\big{)}\vskip
3.0pt plus 1.0pt minus 1.0pt\\\
\hfill\operatorname*{clamp}_{0}^{1}\big{(}\nicefrac{{3}}{{2}}-|4t-2|\big{)}\vskip
3.0pt plus 1.0pt minus 1.0pt\\\
-\operatorname*{clamp}_{0}^{1}\big{(}\nicefrac{{3}}{{2}}-|4t-1|\big{)}\\\
\end{bmatrix}+\begin{bmatrix}\hfill\operatorname*{clamp}_{0}^{1}\big{(}4t-\nicefrac{{7}}{{2}}\big{)}\vskip
3.0pt plus 1.0pt minus 1.0pt\\\ 0\vskip 3.0pt plus 1.0pt minus 1.0pt\\\
1-\operatorname*{clamp}_{0}^{1}\big{(}4t-\nicefrac{{7}}{{2}}\big{)}\end{bmatrix},$

where $\vec{\chi}\in[0,1]^{3}$ is the spectral color at position $t\in[0,1]$.
See Figure 4 for visualization.

###  5.1. Chromatic aberration through lens distortion

Figure 5. Example of anamorphic lens distortion with chromatic aberration,
where $\vec{k}_{x1}=-0.25$, $\vec{k}_{y1}=0.04$, $d=0.5$, with 64–spectral
levels.

Chromatic aberration can be integrated into lens distortion, with spectral
blurring, through lens-transformation vector $\Delta\vec{v}$. Below, the
equation for spectral-blur displacement vector $\vec{s}$ is presented,
calculated per the sample at position $t$.

(12a) $\displaystyle\begin{bmatrix}\Delta\vec{v}_{x}\\\
\Delta\vec{v}_{y}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\vec{v}^{\prime}_{x}-\vec{v}_{x}\\\
\vec{v}^{\prime}_{y}-\vec{v}_{y}\end{bmatrix}$ (12b)
$\displaystyle\begin{bmatrix}\vec{s}_{x}\\\ \vec{s}_{y}\end{bmatrix}$
$\displaystyle=\Big{(}1+\bigg{(}t-\frac{1}{2}\bigg{)}d\Big{)}\begin{bmatrix}\Delta\vec{v}_{x}\\\
\Delta\vec{v}_{y}\end{bmatrix},$

where $\vec{s}\in\mathbb{R}^{2}$ is the spectral blur sample-offset vector at
position $t\in[0,1)$. Value $d\in\mathbb{R}$ denotes the lens dispersion-
scale. For a visually pleasing result, additional blur pass can be performed,
in which the direction is perpendicular to $\vec{s}$ vector, and with smaller
magnitude, as below.

(13) $\begin{bmatrix}\vec{s}^{\prime}_{x}\\\
\vec{s}^{\prime}_{y}\end{bmatrix}=\frac{1}{4}\begin{bmatrix}-\vec{s}_{y}\\\
\vec{s}_{x}\end{bmatrix},$

where $\vec{s}^{\prime}$ is the second-pass blur direction vector.

Figure 5 presents the final effect of two-pass blur, where the first pass is
spectral, along lens-distortion $\Delta\vec{v}$, and the second-pass of
quarter-magnitude is perpendicular $\bot\Delta\vec{v}$. A combination of both
adds a defocussing effect to the distortion.

##  6\. Final thoughts

In this article, a mathematical model for asymmetrical anamorphic-perspective
geometry (pantomorphic) has been presented, along with perception-driven
distortion design recommendations. Each power axis of the pantomorphic model
resembles parametric azimuthal projection. Such parametrization enables a
picture’s geometry to be adaptive, which can dynamically adjust to the visible
content in an artistically convincing manner. Along with anamorphic
perspective, vignetting and lens-distortion with integrated chromatic-
aberration has been provided. Selection of these features enables holistic
digital-lens simulation for immersive-imagery production.

_Panorama source:_ captured from Conan Exiles through Nvidia Ansel.

(a) $\vec{k}=[\nicefrac{{1}}{{2}}\quad-\nicefrac{{1}}{{2}}\quad 0]$,
$f=0.618$, $\Omega_{h}\approx 156\text{\textdegree}$, (asymmetrical) racing.

_Panorama source:_ Grzegorz Wronkowski, under CC-BY license.

(b) $\vec{k}=[-\nicefrac{{1}}{{2}}\quad 0]$, $f=1$,
$\Omega_{h}=120\text{\textdegree}$, flying.

_Panorama source:_ captured from Obduction through Nvidia Ansel.

(c) $\vec{k}=[0\quad\nicefrac{{3}}{{4}}\quad-\nicefrac{{1}}{{2}}]$, $f=0.82$,
$\Omega_{h}\approx 140\text{\textdegree}$, (asymmetrical) first-person aim.

_Panorama source:_ captured from For Honor through Nvidia Ansel.

(d) $\vec{k}=[0\quad-\nicefrac{{1}}{{2}}]$, $f=0.63$, $\Omega_{h}\approx
182\text{\textdegree}$, stereopsis (cyclopean).

Figure 6. Examples of super wide-angle views in anamorphic projection with
natural vignetting. Mapped from 360° panorama in equirectangular projection.

## References

  * (1)
  * Alberti (1435) Leon B. Alberti. 1435\.  _On Painting_ (1970 ed.).  New Haven: Yale University Press.  http://www.noteaccess.com/Texts/Alberti/index.htm
  * Argan and Robb (1946) Giulio C. Argan and Nesca A. Robb. 1946.  The Architecture of Brunelleschi and the Origins of Perspective Theory in the Fifteenth Century.  _Journal of the Warburg and Courtauld Institutes_ 9 (1946), 96\.  https://doi.org/10.2307/750311
  * Baldwin et al. (2014) Joseph Baldwin, Alistair Burleigh, and Robert Pepperell. 2014\.  Comparing Artistic and Geometrical Perspective Depictions of Space in the Visual Field.  _i-Perception_ 5, 6 (jan 2014), 536–547.  https://doi.org/10.1068/i0668
  * Bettonvil (2005) Felix Bettonvil. 2005\.  Fisheye lenses.  _WGN, Journal of the International Meteor Organization_ 33, 1 (2005), 11–12.  https://ui.adsabs.harvard.edu/link_gateway/2005JIMO...33....9B/ADS_PDF
  * Correia and Romão (2007) José Correia and Luís Romão. 2007.  Extended perspective system. In _Proceedings of the 25th eCAADe International Conference_. 185–192.
  * Da Vinci (1632) Leonardo Da Vinci. 1632\.  _A treatise on painting_ (2014 ed.).  Project Gutenberg, Chapter Linear Perspective, 49–59.  http://gutenberg.org/ebooks/46915
  * Dixon (1987) Robert A. Dixon. 1987\.  _Mathographics_.  Basil Blackell Limited, Chapter Perspective Drawings, 82–83.
  * Fitzgibbon (2001) Andrew W. Fitzgibbon. 2001\.  Simultaneous linear estimation of multiple view geometry and lens distortion. In _Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR 2001_ , Vol. 1. IEEE Comput. Soc, Kauai, HI, USA.  https://doi.org/10.1109/cvpr.2001.990465
  * Fleck (1994) Margaret M. Fleck. 1994\.  _Perspective Projection: the Wrong Imaging Model_.  techreport 95-01. Computer Science, University of Iowa.  https://mfleck.cs.illinois.edu/my-papers/stereographic-TR.pdf
  * German et al. (2007) Daniel M. German, Pablo D’Angelo, Michael Gross, and Bruno Postle. 2007.  New Methods to Project Panoramas for Practical and Aesthetic Purposes. In _Computational Aesthetics in Graphics, Visualization, and Imaging_. The Eurographics Association.  https://doi.org/10.2312/COMPAESTH/COMPAESTH07/015-022
  * Giardina (2016) Carolyn Giardina. 2016\.  How ’The Hateful Eight’ Cinematographer Revived Lenses From the 1960s.  _The Hollywood Reporter_ (Jan. 2016).  https://hollywoodreporter.com/news/how-hateful-eight-cinematographer-revived-852586 Online.
  * Gilcher (2015) Pascal Gilcher. 2015\.  YACA (Yet Another Chromatic Aberration).  ReShade forum.  https://reshade.me/forum/shader-presentation/1133-yaca-yet-another-chromatic-aberration#8861 Forum post.
  * Kingslake (1989) Rudolf Kingslake. 1989\.  _A History of the Photographic Lens_.  Academic Press, Chapter IV, 59–62.
  * Krause (2019) Erik Krause. 2019\.  _Fisheye Projection_.  PanoTools wiki.  https://wiki.panotools.org/index.php?title=Fisheye_Projection&oldid=16077 Online.
  * McArdle (2013) James M. McArdle. 2013\.  From the corner of your eye?…  Personal blog.  https://drjamesmcardle.com/2013/04/07/from-the-corner-of-your-eye/ Online.
  * Neil (2004) Iain A. Neil. 2004\.  Lenses in Cinematography.  _Optics and Photonics News_ 15, 1 (2004), 26\.  https://doi.org/10.1364/opn.15.1.000026
  * Peñaranda et al. (2015) Luis Peñaranda, Luiz Velho, and Leonardo Sacht. 2015\.  Real-time correction of panoramic images using hyperbolic Möbius transformations.  _Journal of Real-Time Image Processing_ 15, 4 (may 2015), 725–738.  https://doi.org/10.1007/s11554-015-0502-x
  * Sasaki (2017a) Dan Sasaki. 2017a.  The Aesthetics of Anamorphic in Film and Digital.  Panavision Inc.  https://vimeo.com/167052303 Video.
  * Sasaki (2017b) Dan Sasaki. 2017b.  The Five Pillars of Anamorphic - Disproportionate Breathing.  Panavision Inc.  https://vimeo.com/167045643 Video.
  * Sharpless et al. (2010) Thomas K. Sharpless, Bruno Postle, and Daniel M. German. 2010\.  Pannini: A New Projection for Rendering Wide Angle Perspective Images.  _Computational Aesthetics in Graphics_ Visualization, and Imaging (2010).  https://doi.org/10.2312/COMPAESTH/COMPAESTH10/009-016
  * Wang et al. (2008) Jianhua Wang, Fanhuai Shi, Jing Zhang, and Yuncai Liu. 2008\.  A new calibration model of camera lens distortion.  _Pattern Recognition_ 41, 2 (2008), 607–615.  https://doi.org/10.1016/j.patcog.2007.06.012
  * Whittaker (1984) Eric J. W. Whittaker. 1984\.  _The Stereographic Projection_ (2001 ed.).  University College Cardiff Press.  http://oldwww.iucr.org/iucr-top/comm/cteach/pamphlets/11/11.pdf
  * Wikipedia, contributors (2019) Wikipedia, contributors. 2019\.  Robert Barker (painter).  _Wikipedia, The Free Encyclopedia_ (2019).  http://en.wikipedia.org/w/index.php?title=Robert_Barker_(painter)&oldid=907715733#Biography
  * Williams (2015) Shaun E. Williams. 2015\.  Blinky.  GitHub, Inc.  https://github.com/shaunlebron/blinky Modification, Quake.
  * Williams (2017) Shaun E. Williams. 2017\.  Flex FOV.  GitHub, Inc.  https://github.com/shaunlebron/flex-fov Modification, Minecraft.
  * Yuan and Sasian (2009) Sheng Yuan and Jose Sasian. 2009.  Aberrations of anamorphic optical systems I: the first-order foundation and method for deriving the anamorphic primary aberration coefficients.  _Applied Optics_ 48, 13 (2009), 2574.  https://doi.org/10.1364/ao.48.002574


# Effective Management of Airport Security Queues with Passenger Reassignment

Shangqing Cao  Aparimit Kasliwal  Department of Civil and Environmental
Engineering, University of California, Berkeley, USA Masoud Reihanifar
Francesc Robusté  Barcelona Innovative Transportation (BIT), Technical
University of Catalonia BarcelonaTech (UPC), Barcelona, Spain  Mark Hansen
Department of Civil and Environmental Engineering, University of California,
Berkeley, USA

###### Abstract

Airport security queues often suffer from inefficiencies that result in long
wait times and decreased throughput, especially at peak departure time,
affecting both passengers and airlines. This work addresses the problem of
reassigning passengers to specific time slots for crossing security, aiming to
mitigate these inefficiencies. We frame this problem as a Minimum Cost Network
Flow (MCNF) problem, enabling us to solve it exactly in polynomial time due to
its linear programming structure. Our approach redistributes passenger demand
across different time intervals. By optimizing the reassignment of passengers
to $\delta$-minute time slots, we achieve significant improvements in
throughput and reductions in waiting time. Preliminary results demonstrate the
effectiveness of our method in enhancing operational efficiency and passenger
satisfaction. The MCNF formulation offers a scalable and adaptable solution,
providing long-term benefits for airport security management.

##  1\. Introduction

Airports worldwide face significant challenges in managing security queues
efficiently, leading to prolonged wait times for passengers and decreased
throughput for airlines. These inefficiencies create a ripple effect, causing
time-related costs and frustration for both passengers and airlines.
Passengers experience delays, missed flights, and increased stress, while
airlines face scheduling disruptions and potential financial losses [1]. The
costs associated with these inefficiencies are multifaceted. From the
passengers’ perspective, extended wait times translate to lost productivity,
missed flights, and heightened travel anxiety. For airlines, the costs
manifest as increased operational expenses, potential loss of customer
loyalty, and decreased revenue from delayed or missed flights [2].

Just before the COVID-19 pandemic, long airport security queues caused one in
every seven travelers to miss a flight in the past 12 months [3]. Nearly half
of respondents in an AirHelp survey lost money due to non-refundable costs
caused by airport disruptions, including long delays and missed flights [4].
In the meantime, the airline industry aims to set a new passenger record in
2024, connecting nearly five billion people over 22,000 routes with 39 million
flights [5]. Thus, addressing the long waiting time in queues at airport
security control is crucial to ensuring smooth operations at airports
worldwide in the face of the continuing growth in passenger demand.

One issue associated with airport security management is that passengers have
varying preference in the time of arrival at airports prior to a flight.
Passengers who arrive hours prior to the departure of their flights place
additional stress on the security system in serving those who need more
immediate security checks [6]. Studies have examined the benefits of security
lane reassignment but such mitigation does not address the temporal variation
in passengers’ arrivals [7]. Therefore, in this paper, we seek to address the
issue of long wait time at security control by reassigning passengers to
specific time slots to reach system optimum.

##  2\. Literature Review

Interestingly, this problem shares similarities with the morning commute
problem, where commuters are incentivized to travel early to avoid peak
congestion periods. [8] [9] In both scenarios, the goal is to redistribute
demand to flatten congestion peaks, thereby enhancing overall system
efficiency. For instance, just as commuters are encouraged to start their
journeys earlier to reduce travel time in some cases, passengers can be
incentivized to pass through airport security during less busy periods.
However, in the morning commute problem, the cost can be broken down into two
types: travel time penalty and congestion cost [10]. It is assumed that at
equilibrium, the first and the last user going through the same bottleneck
would incur the same cost. However, in the airport security setting, there
exists an abrupt increase in cost when a user’s time of arrival is past the
flight departure time. It is difficult to reach the system equilibrium because
passengers in the air transportation system do not usually have the
opportunity to repeatedly assess the cost associated with different time of
arrival prior to a flight as most people travel by air only a few times a
year.

This problem can also be likened to the Single-Sourced Capacitated Facility
Location Problem (SSCFLP) [11] or a Capacitated Facility Location Problem
(CFLP) both of which involve allocating limited resources (in this case,
security slots) to meet varying demand levels. The idea of optimizing the
reassignment of demand to proper supply providers is used extensively in the
design of control policies for operating air transportation systems. [12]
[13].

Our approach models the problem as a Minimum Cost Network Flow (MCNF) problem,
which allows for an exact polynomial-time solution. This distinction
highlights the flexibility and efficiency of the MCNF approach in addressing
the dynamic and time-sensitive nature of airport security queue management. We
minimize the total cost associated with security queue congestion, balancing
demand across different time intervals. Preliminary results from our study
indicate significant improvements in throughput and reduced wait times for
passengers. Our approach not only addresses the immediate inefficiencies in
security line management but also offers a scalable solution that can adapt to
varying demand patterns, providing long-term benefits for airports, airlines,
and passengers alike.

The rest of the paper is organized as follows. Section 3. details the
mathematical formulation of the MCNF problem within the context of security
reassignment. In section 4., we establish a queuing system for the airport
security screening process and define the metrics on which we are evaluating
our control policy. Section 5. showcases the results under both a
deterministic, nominal condition, and under variation in passenger compliance
with the assignment.

##  3\. Methodology

We consider the problem of reassigning passengers to $\delta$-minute time
slots and $\delta$ denotes the interval length of each time slot. These time
slots represent the assigned time at which passengers cross security at the
airport. We use the phrase ”reassigning” to differentiate from the current
first-come first-served basis. We frame this problem as a Minimum Cost Network
Flow (MCNF) problem, which is well-studied in the optimization and operations
research literature. While this problem can be formulated in multiple ways,
including as a Single-Sourced Capacitated Facility Location Problem (SSCFLP),
the MCNF formulation can be solved exactly in polynomial time using network
Simplex with integral solutions.

$\vdots$$\vdots$P1P2P3PPT1T2T3TTSink NodePassengersTime SlotsSink Node Fig. 1.
: Flow network representation of passengers and time slots with a sink node.
Arrows denote feasible flows from passengers to time slots and from time slots
to the sink node.

###  3.1. MCNF Formulation

We construct a directed graph $G(V,E)$ where $V$ is the set of nodes and $E$
is the set of edges in the network. Our goal is to find the cheapest
assignment of the flow in this network $G$ while satisfying the flow balance
constraints and the capacity constraints. We define the network as the
following:

Let $p\in P$ be a passenger to be reassigned, where $P$ is the set of
passenger nodes. Let $t\in T$ be a time slot to which the passenger can be
reassigned, where $T$ is the set of time slots. Let $C_{t}$ denote the
capacity of the system in time slot $t$. We define $V=P\cup T\cup\\{s\\}$,
where $s$ denotes the sink node and we define $E=\\{e_{pt}|p\in P,t\in
T\\}\cup\\{e_{ts}|t\in T\\}$. Figure 1 visualizes the network we construct.

The decision variables in our formulation are the $x_{ij}$s, which are the
flow on the directed edges connecting node $i$ to node $j$, and $(i,j)\in E$.
The respective unit cost of flow on each edge is $c_{ij}$. We use $l_{ij}$ and
$u_{ij}$ to denote the lower and upper bounds of flow on edge $(i,j)\in E$. We
use $b_{v}$ to denote the net flow of each node $v\in V$.

We adopt a standard MCNF formulation where we seek to minimize the weighted
sum of flow on all edges while ensuring that the net flow requirement with
respect to each node is satisfied (Eq.2), and that the flow on each edge is
within the range we define (Eq.3).

$\displaystyle\text{min}\sum_{i}\sum_{j}c_{ij}x_{ij}$ (1)

$\displaystyle\sum_{k\in V\setminus\\{v\\}}x_{ik}-\sum_{k\in
V\setminus\\{v\\}}x_{ki}=b_{i}\quad\forall v\in V$ (2) $\displaystyle
l_{ij}\leq x_{ij}\leq u_{ij}\quad\forall(i,j)\in E$ (3)

We now define the parameters $b_{i}$, $l_{ij}$, and $u_{ij}$.

$\displaystyle b_{i}=\begin{cases}1&\text{if }i\in P\\\ 0&\text{if }i\in T\\\
-|P|&\text{if }i=s\end{cases}$ (4)

$\displaystyle l_{ij}=0\quad\forall(ij)\in E$ (5)

$\displaystyle u_{ij}=\begin{cases}1&\text{if }i\in P,j\in T\\\ C_{i}&\text{if
}i\in T,j=s\end{cases}$ (6)

Eq. (4) ensures that each passenger is served and Eq. (6) ensures that the
number of passengers we reassign to each time slot is within the capacity of
the particular time slot.

###  3.2. Cost Function

We assume that passengers arrive at the security queue an hour before their
flight departure time. We establish this assumption so that we can compare the
solution output from the optimization problem to the queuing system under the
first-come first-served basis outlined in 4.. The arrival process of
passengers can be substituted by different assumptions and that the
computational complexity of the model does not depend on the assumption we
establish.

Assigning a passenger to a time slot one hour prior to the flight departure
time incurs a cost of 0. We assume a quadratic cost structure for reassigning
passengers to time slots more than 1 hour before the flight departure time,
and a linear cost structure for reassigning passengers to time slot less than
1 hour before the flight departure time but before the flight departure time.
The difference in the order of the cost function assumes that it is more
feasible to delay a passenger’s entrance to the security queue compared to
asking the passenger to arrive early. If the decision is to assign a passenger
to a time slot after the flight departs, we then set the cost to a
sufficiently large number to penalize missing the flight. Let $t_{i}$ be the
flight departure time of passenger $i$ and then the cost function is defined
as a piece-wise function:

$\displaystyle c_{ij}=\begin{cases}0&\text{if }j=t_{i}\\\
\alpha\cdot(j-t_{i})&\text{if }j\in(t_{i},t_{i}+1]\\\
\beta\cdot(t_{i}-j)^{2}&\text{if }j<t_{i}\\\ \gamma&\text{if
}j>t_{i}+1\end{cases}$ (7)

where $\alpha$, $\beta$, and $\gamma$ are the coefficients. Figure 2
visualizes the cost structure with respect to each individual passenger.

Fig. 2. : The cost of reassigning passengers to different time slots with
respect to the passenger’s flight departure time.

##  4\. Security Queuing System

The processing times at the security queue at the airport are quintessentially
determined by the staffing capacity. Understandably, the key trade-off that we
are trying to address by solving this problem is to achieve the maximal gain
in passenger experience, by reducing the processing times at the security
queue, while ensuring a reasonable distribution of the capacities of the
security queues. Note that given a certain time at which a passenger arrives
at the airport security queue, the time at which they depart from the security
queue is directly dependent on the capacity of the security system at that
point of time.

We establish a first-come first-served queuing system as the baseline to which
our model is compared. We can view the queuing system as a passive control
policy, where the act of waiting in queue is the assignment. We introduce the
following notations:

  * •

$v(t)$: cumulative number of passengers who have arrived at the security queue
by time $t$.

  * •

$d(t)$: cumulative number of passengers who have departed from the security by
time $t$.

  * •

$q(t)$: cumulative number of passengers who have departed from the airport by
time $t$.

We then use $\hat{v}(t)$, and $\hat{d}(t)$, to represent queuing system under
the control policy output from the optimization problem. However, $q(t)$
remains unchanged as it is dependent on the flight schedules. Note that the
function $v(t)$ is essentially the control policy represented by the decision
variables in the optimization problem and $d(t)$ is a function dependent on
$v(t)$ and the assumed capacity of the security system.

We use two metrics to evaluate the efficiency of the control policy derived
from the optimization problem. The first metric is the total waiting $(TW)$
time in the system, as defined by:

$\displaystyle TW=\int_{0}^{T}v(t)-d(t)dt\approx\sum_{t=1}^{T}(v(t)-d(t))$ (8)

The second metric is the total cost ($TC$) of the system as defined by the
cost function explained in section 3.2.. For a system with no optimized
passenger reassignment, $TC=\alpha\cdot TW$, where $\alpha$ is the time
coefficient of assigning passengers to a time slot within the 1 hour period
before flight departure, as shown in fig 2. The $TC$ of the optimized control
is simply the optimized objective function value of the optimization problem.
$TC$ captures the relative difference in unit cost and the added benefits of
asking passengers to arrive early while taking the quadratic nature of the
cost of assigning passengers to an earlier time slot into account.

##  5\. Numeric Study

We obtained the May 9th, 2023 departure flight schedules of terminal 1 at
Josep Tarradellas Barcelona-El Prat Airport (BCN) in the city of Barcelona,
Spain. In our data sample, there are 260 departing flights out of BCN, with
49,034 seats. We set the length of the time interval $\delta$ to 15 minutes,
which results in partitioning the day into 96 time slots. For simplicity, we
assume a load factor of 100$\%$, which gives a total demand of 49,034
passengers for security processing. We assume $\alpha=4$, $\beta=1$, and
$\gamma=200$ for the cost function.

###  5.1. Time-Invariant Capacity

For the simplest case, we assume that the capacity of the security system
stays constant throughout the day. As Eq. (2) ensures that each passenger
receives an assignment, the optimization problem becomes infeasible if we set
the constant value of the capacity below a certain critical threshold. The
critical capacity, $c_{c}$, is thus:

$\displaystyle c_{c}=\frac{N}{T},$ (9)

where $N$ is the total number of passengers and $T$ is the total number of
time slots. Plugging in the values of the total number of passengers
($N=49,034$) and the total number of time slots ($T=96$), we get the critical
value of the capacity to be 511.

For a nominal case, we assume a security capacity of 900 passengers per
15-minute time slot. Figure 3 shows the queuing system before and after the
reassignment of passengers. We can see that with no reassignment, a queue
builds up at around 6 am and 9 am due to the early morning peak in the number
of departing flights. Passengers spend up to 1 hour waiting to go through
security which results in many of them barely being on time for departures.
With the reassignment, which is shown on the right side in Fig. 3, the waiting
time of passengers goes to 0. The respective $TC$ for the two systems are
132,628 and 39,622, showing a reduction of roughly 70%.

Fig. 3. : N-T diagram of the system under first-come first-served control
(left) and under the optimal control policy (right) derived from the
optimization where the capacity is not allowed to vary with time.

Additionally, we examine how different capacity levels of the security affects
the distribution of the reassignment across all passengers. Figure 4 shows the
change in arrival time of passengers under this optimized system. We observe
that as the capacity of the system increases, the optimization problem prefers
being more equitable to all passengers as far as the reassigned arrival time
is concerned. On the other hand, when the system has a lower fixed capacity,
the algorithm has no choice but to ask some passengers to arrive way later in
the day, whereas a few passengers are advised to arrive way too early -
resulting in a more inequitable distribution of recommended arrival times.

Fig. 4. : Variation in the deviation of the arrival-times of passengers for 3
different values of the constant capacities. Note that lesser values for the
capacity constrains the system and promotes inequality, whereas the optimal
solution is more equitable for all passengers for a higher value of the
capacity.

Furthermore, Fig. 5 shows the monotonous decrease in the objective value as
the capacity is increased. This is because the objective function essentially
contains the cost associated with assigning a given passenger to each possible
time-slot, summed up over all passengers. When the capacity of the system is
higher, the cost associated with assigning a given passenger to the same time-
slot decreases substantially (because of how the cost function is defined in
the first place), and hence we observe a decrease in the objective value with
increasing capacity.

Fig. 5. : Increase in the capacity yields a monotonous decrease in the
objective value, mainly because of the structure of the cost function.

###  5.2. Time-Varying Capacity

Previously, we considered the capacity of the security system to be constant
over time, and our algorithm presented the optimal reassignment for the
arrival times of the passengers. Here, we propose a methodology to optimize
the supply side of the system, which is the capacity at different times of the
day, in order to best match the temporal demand observed at the airport
security queue.

We revise the optimization problem to allow time-varying capacities at
security:

$\displaystyle\text{min}\sum_{i}\sum_{j}c_{ij}x_{ij}+\lambda_{1}\sum_{j}y_{j}+\lambda_{2}\sum_{j}^{T-1}\tau_{j}$
(10) $\displaystyle\sum_{k\in V\setminus\\{v\\}}x_{ik}-\sum_{k\in
V\setminus\\{v\\}}x_{ki}=b_{i}\quad\forall v\in V$ (11) $\displaystyle
l_{ij}\leq x_{ij}\leq u_{ij}\quad\forall(i,j)\in E$ (12)
$\displaystyle\tau_{j}\geq C_{j+1}-C_{j}\quad\forall j\in T$ (13)
$\displaystyle\tau_{j}\geq C_{j}-C_{j+1}\quad\forall j\in T$ (14)

We retain the definition of parameters in Eq. (4), Eq. (5), and Eq. (6).
Instead of having the security capacity as an input to the model, the time-
varying capacity are now decision variables as represented by $C_{j}$. The
objective function, Eq. (10), is a linear combination of three terms. The
first term is the reassignment cost that we defined in the original problem.
The second term is the weighted cost of operating security at the determined
capacity. The third term represents the sum of the absolute differences in
capacities at consecutive time steps.

While minimizing $\sum_{i}\sum_{j}c_{ij}x_{ij}$ is the primary objective,
ensuring efficient passenger service with minimal staffing is achieved by
minimizing the sum of individual capacities at different times. Furthermore,
minimizing the absolute sum of differences between capacities at consecutive
time steps ensures that capacity does not vary drastically over time. This
smooth variation in staffing capacity is crucial for the staffing agency to
manage the proposed distribution of capacity efficiently.

Fig. 6. : N-T diagram of the system under first-come first-served control
(left) and under the optimal control policy (right) derived from the
optimization where the capacity at different time slots can vary. The two
systems yield comparable results in $TW$. In the constant capacity
optimization, $C_{j}=900$. In the time-varying capacity optimization,
$\lambda_{1}=0$, and $\lambda_{2}=10$. Fig. 7. : The capacity and the service
rate in terms of the number of passengers under time-invariant and time-
varying capacities. $C_{i}=f(t)$ denotes the time varying capacity determined
by the optimization problem in 5.2.. $d^{\prime}(t,C_{i}=f(t))$ is the number
of passengers completed security screening at time $t$ under the time-varying
capacity. $C_{i}=900$ is the constant capacity scenario outlined in 5.1. and
$d^{\prime}(t,C_{i}=900)$ is the number of passengers completed security
screening at time $t$ under the constant capacity. In the time-varying
capacity optimization, $\lambda_{1}=0$, and $\lambda_{2}=10$.

Figure 6 shows the state of the first-come first-served queuing system under
the constant capacity of 900 alongside the state of the system controlled with
the proposed capacity as seen in Fig. 7. While the two systems are comparable
in reducing the total waiting time of passengers in the system, optimizing for
the capacity yields higher efficiency with respect to the security system. As
seen in Fig. 7, under the constant capacity assumption, the utilization of the
security system is extremely low in the early morning between 1am and 3am and
after 11pm. However, with the formulation in section 5.2., we lower the
capacity of the security system during the low-demand period and increase the
capacity when the demand is high. Note that we only have a limited number of
changes in capacity, due to the regularizing term in the objective function
that penalizes differences in capacity between consecutive time slots.

###  5.3. Uncertainty in Compliance

Unlike the airport slot assignment problem where the decisions are implemented
collectively among a limited number of parties, such as airlines and airports,
the security time slot assignment is subject to great uncertainty as it is
nearly impossible to forcibly align each individual passenger’s behavior to
reach system optimal. Therefore, one question of interest is how would the
system behave if the passengers were non-compliant with the reassignment of
time slots.

We identify two sources of variation in which a passenger is ”non-compliant”
with the reassignment. The first source of variation is by assuming all
passengers accept the assigned time slot, the actual time of arrival, however,
is a random process. We can model the deviation from the assigned time of
arrival of these passengers as $x\sim\mathcal{N}(0,\sigma^{2})$. Let $a_{i}$
be the assigned time slot of passenger $i$. The actual time of arrival of the
passenger $i$ at security is then $a_{i}+x$. By assuming a 15-minute security
capacity of 900 and setting the time interval $\delta=15$ minutes, Fig. 8
shows that the variance in passenger arrival times has minimal impact on $TW$
of the system. As $\sigma$ increases, the normal distribution behaves more
similar to a uniform distribution, meaning that the probability of having a
certain deviation from the assignment is similar across different levels of
deviation. By essentially spreading the passengers uniformly across the time
horizon, we experience little to no increase in the $TW$ of the system.
However, as $\sigma$ increases, passengers begin to miss flights as that their
arrival time at the security is now pass the flight departure time.

Fig. 8. : The relationship between total waiting time (TW), percentage of
passenger missing flights, and level of deviation from assigned time slot of
arrival.

The second source of non-compliance is that some passengers will reject the
assigned time slot. To model this, we assume each passenger is a Bernoulli
random variable with the probability of accepting a reassignment at
probability $p$. If the passenger does not accept the assignment, he then
arrive at the security 1 hour before the flight departure time, which is what
we assumed in solving the optimization problem. Figure 9 shows that there is
an exponential decrease in $TW$ as the percentage of people accepting the
assignment increases. At 50% compliance rate, we reduce the $TW$ of the system
by 63%. The marginal gain in $TW$ reduction suggests that the slot
reassignment mechanism can tolerate certain level of randomness in passenger
compliance while providing improvement to the existing system.

Fig. 9. : The relationship between total waiting time (TW) and the probability
$p$ of complying with a time slot reassignment.

##  6\. Conclusion

In this work, we demonstrated that both the variation in actual passenger
arrival times and the probability of compliance significantly impact the
operational efficiency of the system. Our algorithm effectively redistributed
demand based on the distribution of capacity and proposed an optimal capacity
distribution to cater to the demand most efficiently. These approaches
highlight the importance of considering compliance rates in optimizing system
performance.

One future research direction is incorporating stochasticity to the model. The
compliance rate of the passengers cannot be assumed to be 100%. Thus, the next
step in our approach is to solve a Distributed Robust Optimization (DRO)
problem. The key benefit of tackling this problem using a DRO-based
formulation is that the optimal solution allows for variations within a
certain standard deviation, which can be fine-tuned.

We propose the following formulation for our problem as a Distributed Robust
Optimization:

$\displaystyle\min_{\textbf{c}}\;$
$\displaystyle\mathbb{E}_{\xi\sim\mathcal{P}}\left[f(\textbf{c},\xi)\right]+\lambda\text{Var}_{\xi\sim\mathcal{P}}\left[f(\textbf{c},\xi)\right]$
(15) subject to $\displaystyle\textbf{c}\in\mathcal{C}$ (16)
$\displaystyle\xi\in\mathcal{U}$ (17)

where c represents the capacity distribution, $\xi$ denotes the uncertainty in
the passenger compliance rates, $\mathcal{P}$ is the probability distribution
of the uncertainty, and $\lambda$ is a regularization parameter that controls
the trade-off between the expected value and the variance of the objective
function. The feasible set $\mathcal{C}$ represents the constraints on the
capacity, and $\mathcal{U}$ is the uncertainty set.

This approach would enhance the robustness and reliability of the system under
uncertain conditions, leading to improved operational efficiency. We plan to
compare the results obtained from solving this DRO problem to the solutions we
already have from the MCNF based approach. This comparison will enable our
objective function for the optimization problem to prioritize different terms
while also allowing for a window of variance in passenger compliance.

## References

  * 1) BBC: Dublin Airport apologises after passengers miss flights due to queues, BBC News, 2022.
  * 2) Rosenow, J., Michling, P., Schultz, M., and Schönberger, J.: Evaluation of Strategies to Reduce the Cost Impacts of Flight Delays on Total Network Costs, Aerospace, 2020, 7(11):165.
  * 3) Stoller, G.: One of Every Seven Travelers Miss Their Flights Because of Long Airport Security Lines, Forbes News, 2018.
  * 4) Bhateja, A.: Expect to Lose This Much Money Every Time There’s a Major Flight Delay, Fodors Travel Guide, 2023.
  * 5) Walsh, W.: Willie Walsh’s Report on the Air Transport Industry at the 80th IATA AGM, IATA, 2024.
  * 6) Calder, S.: Why are airport queues so long and what are passengers’ rights if they miss a flight, The Independent, 2022.
  * 7) Marshall, Z. A., Mott, J. H., Gottwald, A. J., Patrick, C. A., Dy, L.R.: Expediting airport security queues through advanced lane assignment, Journal of Transportation Security, 2022, Vol. 15, pp. 245-262.
  * 8) Small, K. A.: Urban Transportation Economics, Regional and Urban Economics Parts 1 & 2, 2013, pp. 251-439.
  * 9) Vickrey, W. S.: Congestion Theory and Transport Investment, The American Economic Review, 1969, Vol. 59, No. 2, pp. 251-260.
  * 10) Lamottea, R., Palma, A., Geroliminis, N.: On the user of reservation-based autonomous vehicles for demand management, Transportation Research Part B, 2017, pp. 205-227.
  * 11) Odoni, A.: A REVIEW OF CERTAIN ASPECTS OF THE SLOT ALLOCATION PROCESS AT LEVEL 3 AIRPORTS UNDER REGULATION 95/93, Massachusetts Institute of Technology, No.ICAT-2020-09, Cambridge, MA, 2020.
  * 12) Li, A., Hansen, M.: Scenario-based Strategic Flight Reassignment in Multiple Airport Regions, International Conference on Research in Air Transportation, 2022.
  * 13) Zhou, L., Liang, Z., Chou, C.A., Chaovalitwongse, W.A.: Airline planning and scheduling: Models and solution methodologies, Frontiers of Engineering Management, 2020, Vol. 7, No. 1, pp. 1-26.