# ALINA: Advanced Line Identification and Notation Algorithm

Mohammed Abdul Hafeez Khan
Florida Institute of Technology
Melbourne, Florida
<EMAIL_ADDRESS>Parth Ganeriwala
Florida Institute of Technology
Melbourne, Florida
<EMAIL_ADDRESS>Siddhartha Bhattacharyya
Florida Institute of Technology
Melbourne, Florida
<EMAIL_ADDRESS>Natasha Neogi
NASA Langley Research Center
Hampton, Virginia
<EMAIL_ADDRESS>Raja Muthalagu
BITS Pilani Dubai Campus
Dubai, UAE
<EMAIL_ADDRESS>
###### Abstract

Labels are the cornerstone of supervised machine learning algorithms. Most
visual recognition methods are fully supervised, using bounding boxes or
pixel-wise segmentations for object localization. Traditional labeling
methods, such as crowd-sourcing, are prohibitive due to cost, data privacy,
amount of time, and potential errors on large datasets. To address these
issues, we propose a novel annotation framework, Advanced Line Identification
and Notation Algorithm (ALINA), which can be used for labeling taxiway
datasets that consist of different camera perspectives and variable weather
attributes (sunny and cloudy). Additionally, the CIRCular threshoLd pixEl
Discovery And Traversal (CIRCLEDAT) algorithm has been proposed, which is an
integral step in determining the pixels corresponding to taxiway line
markings. Once the pixels are identified, ALINA generates corresponding pixel
coordinate annotations on the frame. Using this approach, 60,249 frames from
the taxiway dataset, AssistTaxi have been labeled. To evaluate the
performance, a context-based edge map (CBEM) set was generated manually based
on edge features and connectivity. The detection rate after testing the
annotated labels with the CBEM set was recorded as 98.45%, attesting its
dependability and effectiveness.

Figure 1: (a) Illustrates the aircraft used for this research, (b) and (c)
displays the setup of cameras at different perspectives inside the aircraft,
(d) shows the manually defined region of interest on a frame, (e) showcases
the annotation label created by ALINA on a frame.

##  1 Introduction

With the advancement of sensors, hardware and intelligent software, autonomous
vehicles have become the center of attention for computer vision and robotics
research. Among the several components of autonomous vehicles, the camera-
based lane detection plays a crucial role in perceiving the lines and then
assisting autonomous vehicular systems in making decisions to follow the
correct path/lanes [11].

It is envisioned, as we gain confidence in the correctness of the design of
autonomous systems, it will pave the way for the integration of learning based
technologies in assisting safety critical systems such as, autonomous aircraft
for urban air mobility or aerial delivery [6, 28]. As a result, this has
increased the need for an advanced perception system, equipped with precise
line identification capability. In future, it can assist pilots in the
aircraft, especially when navigating the airport taxiway. As stated by the
Aviation Safety Network [16], approximately, 33.33% of the aircraft accidents,
between the years 2015 and 2022, happened during the taxiing phase. The common
causes of taxiway accidents include poor weather conditions and high traffic
on the taxiway. In order to address these issues, some researchers have
formulated solutions for assisting pilots during the taxiing phase, including:
light-based guidance systems, which have been designed by the Federal Aviation
Administration and Honeywell [4, 36], computer vision based taxiway guidance
techniques [5], Airport Moving Maps [22], and sensors, such as LIDAR and
cameras mounted on an aircraft [26, 38]. This research builds on the work of
Ganeriwala et. al [18], particularly with the contour-based detection and line
extraction method (CDLEM). They introduced AssistTaxi dataset, which
incorporates more than 300,000 frames of taxiway and runway instances. The
data was collected from Melbourne (MLB) and Grant-Valkaria (X59) general
aviation airports.

In this research, we introduce an Advanced Line Identification and Notation
Algorithm (ALINA), which is an annotation framework developed to detect and
label taxiway line markings from video frames (Fig. 1). ALINA establishes a
uniform trapezoidal region of interest (ROI) by utilizing the initial frame,
that is consistently applied across all subsequent frames of the video. The
ROI is then geometrically modified and the color space is transformed to
produce a binary pixel map. ALINA pinpoints pixels representing taxiway
markings through the novel CIRCular threshoLd pixEl Discovery And Traversal
(CIRCLEDAT) algorithm, leading to frame annotations and coordinate data files.
A context-based edge map (CBEM) set was generated for comparison to ensure
accuracy in marking detection. ALINA was tested on a subset of AssistTaxi
dataset - 60,249 frames extracted from three distinct videos with unique
camera angles. The focus of this research had been on 60,249 frames out of a
vast 300,000-frames AssistTaxi dataset, as the motivation was to lay down a
rigorous yet tractable foundation for the empirical validation of ALINA’s
efficacy, paving the way for its scalability to larger datasets in future.
Through this research, we primarily aim to reduce the intensive, expensive and
error-prone manual labeling [17], and provide labeled data to enhance taxiway
navigation safety.

Our contribution include the following four main aspects:

  * •

To reduce the intensive, expensive, and error-prone manual labeling process,
thus contributing to the efficient combination of automated and manual
creation of labelled datasets.

  * •

Development of the Advanced Line Identification and Notation Algorithm (ALINA)
providing a robust framework for precise detection and labelling of continuous
video datasets, particularly focusing on taxiway line markings.

  * •

Introduction of a novel algorithm, CIRCLEDAT, tailored to pinpoint pixels
representing taxiway/road markings with high accuracy, ensuring precise
labeling across continuous video frames.

  * •

Establishing a systematic approach based on change in perspective of scenario
to justify the sample size of ground truth which is a subset from the
AssistTaxi dataset [18].

The remainder of the paper is organized as follows: In Sec. 2, related
research works have been discussed. Sec. 3 entails the detailed methodology of
ALINA, Sec. 4 presents the experimental results. Finally, Sec. 5 provides the
conclusion and outlines the directions for future work.

##  2 Literature Review

While the research in classification of taxiway line markings is still in its
preliminary stages, the domain of car lane detection has seen substantial
advancements in road labeling techniques. The knowledge derived from detecting
car lanes not only provides fundamental perspectives that guide our
comprehension of detecting taxiway markings but also highlights research gaps
in car lane labeling methods which can be avoided and guide innovative
approaches for taxiway marking detection. Therefore, this section begins by
presenting notable works from the car lane detection domain and highlights
their research gaps.

Some researchers have used classification techniques for lane detection, where
images are segmented into grids for row-based lane location identification
[32, 42, 10]. However, these methods lack precision and might miss some lanes.
To ensure consistent lane detection, techniques such as parametric curve
modeling [31, 39, 37, 25, 15] and keypoint association [33, 40, 41] have been
used. Even though these methods acquire high results, they can struggle in
adverse weather conditions. Andrei _et al_. [3] have utilized probabilistic
Hough transform and dynamic parallelogram region of interest (ROI) to develop
a lane detection system. It was implemented on video sequences with manual ROI
definition but encountered challenges with capturing curved line endpoints,
which are crucial for complete lane boundary delineation in real-world
scenarios. Chen _et al_. [8] detected road markings using machine learning
with binarized normed gradient detection and principal component analysis
(PCA) classification, achieving an accuracy of 96.8%. However, the dependency
on PCA limited the adaptability for dynamic scenarios and challenging
environments. Similarly, the method proposed by Ding _et al_. [13], which
combined PCA and support vector machine (SVM), achieved a detection accuracy
of 94.77%. However, it struggled to detect road markings due to the failure of
the ROI extraction, in the case of reflection, occlusion and shadow.

Gupta _et al_. [20] introduced a real-time framework for camera-based road and
lane markings, using techniques such as spatio-temporal incremental
clustering, curve fitting, and Grassmann manifold learning. The real-time
nature of this approach brings challenges in processing efficiency and speed,
especially with increasing dataset complexities. Jiao _et al_. [23] proposed
an adaptive lane identification system using the scan line method, lane-voted
vanishing point, and multi-lane tracking Kalman filtering, achieving a 93.4%
F1-Score. This approach lacked the adaptability to diverse conditions across
different datasets and real-world scenarios.

Kiske [24] developed an autonomous labeling system for identifying highway
lane markings using Velodyne lidar, HDR video streams, and high-precision GPS.
However, the reliance on multiple data sources makes it less cost-effective
and more complex for wide-scale implementations. Muthalagu _et al_. [27]
proposed a vision-based algorithm for lane detection in self-driving cars,
which used polynomial regression, histogram analysis, and a sliding window
mechanism for detecting both straight and curved lines. The algorithm achieved
notable accuracy, but its high computational demand poses scalability issues,
and its limitation in detecting steep foreground curves presents challenges in
dynamic terrains.

Figure 2: Framework of ALINA

Contour-based detection and line extraction method (CDLEM) was initially used
for labeling the taxiway line markings from AssistTaxi dataset [18]. The Canny
edge detection identified the line marking’s edges. Subsequently, the Hough
transform, Ramer-Douglas-Peucker, and Bresenham’s algorithms were utilized to
identify and label both straight and curved taxiway line markings. The
limitation this approach posed was the requirement to outline an ROI around
taxiway line marking for every scenario shift.

While labeling car lanes has provided a guiding example for an end to end lane
detection system [43, 2, 29], a direct comparison of lane detection to
labeling taxiway line markings is not being made in this research. The
distinct semantics and attributes associated with the car lane datasets and
airport taxiways dataset pose different set of challenges. For example, the
airport taxiway dataset has different layouts, diverse markings, and presence
of aircraft on airport taxiways. Transfer learning can be one of the
approaches to address the differences and identify the commonalities within
the two datasets [19], however it requires the taxiways to be extensively
labeled. Therefore, our research emphasizes creating and evaluating algorithms
for labeling specific to airport taxiways, rather than contrasting them with
car lane datasets.

##  3 Methodology

In this section, we provide a detailed overview of the ALINA framework using
Fig. 2 (each subsection elaborates elements from the figure), and we discuss
its steps referencing image instances from Fig. 3 and Fig. 4.

###  3.1 Frame Representation

While reading a frame, ALINA stores each x, y coordinate and its red, green,
blue (RGB) channel values from the frame into a multi-dimensional array, as
represented in Eq. 1.

$A[i,j,k]=I[i,j,k]$ (1)

where, i, j, and k denote the row, column, and channel indices of the frame,
respectively. This formula copies the pixel values of the frame at location
(i, j) in the $k^{\text{th}}$ color channel into the corresponding location in
the array.

###  3.2 Interactive ROI Definition on the Initial Frame

The user provides source points to ALINA for creating a trapezoidal region of
interest (ROI) on the initial frame of the video, as shown in Fig. 3 (a), (e),
(f). It is drawn in the vicinity of where the camera expects to see the
taxiway’s line markings. ALINA treats the ROI as a constraint to limit the
search area for taxiway’s line markings, resulting in reduced computational
complexity and improved detection accuracy [21]. The source points, which
correspond to the vertices of ROI, are denoted as follows: $[x_{1},y_{1}],\
[x_{2},y_{2}],\ [x_{3},y_{3}],\ [x_{4},y_{4}]$.

###  3.3 Perspective Transformation of the ROI

The next step in ALINA is warping the perspective. The trapezoidal ROI is
warped into a bird’s eye view. Fig. 3 (b), (f), (j) illustrates this
transformation. The destination points, which correspond to the vertices of a
rectangle defining the bird’s eye view, are represented as:
$[x_{1}^{\prime},y_{1}^{\prime}],\ [x_{2}^{\prime},y_{2}^{\prime}],\
[x_{3}^{\prime},y_{3}^{\prime}],\ [x_{4}^{\prime},y_{4}^{\prime}]$.

It enables a more comprehensive and consistent view of the taxiway and its
features, allowing for improved detection of line markings irrespective of
their orientation or curvature [1].

Given the pairs of source and destination points, a matrix M is derived by
solving a system of linear equations formed from the pixel correspondences.
The matrix essentially maps any pixel in the trapezoidal ROI to its
corresponding pixel position in the bird’s eye view.

The matrix M is represented in Eq. 2:

$M=\begin{bmatrix}m_{11}&m_{12}&m_{13}\\\ m_{21}&m_{22}&m_{23}\\\
m_{31}&m_{32}&1\end{bmatrix}$ (2)

with each $m_{ij}$ computed based on the defined system of equations.

Once M is computed, it’s applied to each pixel in the trapezoidal ROI to
achieve its position in the bird’s eye view. This transformation is attained
using Eq. 3:

$\text{t}(x,y)=s\left(\frac{M_{11}x+M_{12}y+M_{13}}{M_{31}x+M_{32}y+M_{33}},\frac{M_{21}x+M_{22}y+M_{23}}{M_{31}x+M_{32}y+M_{33}}\right)$
(3)

Where $t(x,y)$ and $s(x,y)$ denote pixel coordinates in the bird’s eye view
and trapezoidal ROI respectively.

###  3.4 Color Feature Normalization

To accurately distinguish line markings within the ROI, ALINA performs
normalization of color characteristics. The normalization phase consists of
the following key steps:

  1. 1.

$RGB$ to $HSV$ Conversion: The $RGB$ color space of ROI is transformed to the
hue, saturation, and value $(HSV)$ color space. Given a pixel’s $RGB$ values,
denoted by $(R,G,B)$, the transformation into the $HSV$ space is depicted as
$(R,G,B)\rightarrow(H,S,V)$. This transformation is performed because $HSV$
factors in variations induced by lighting conditions and intrinsic color
properties, providing a robust representation of color in an image [35].

  2. 2.

Component Decomposition: The $HSV$ is decomposed into its individual channels:
$H,S,V$.

  3. 3.

Normalization: Every component $X$, where $X\in\\{H,S,V\\}$, undergoes 8-bit
min-max normalization as shown in Eq. 4:

$X_{\text{norm}}=\frac{X-\min(X)}{\max(X)-\min(X)}\times 255$ (4)

where $\min(X)$ and $\max(X)$ denote the minimum and maximum values of the
component $X$, respectively. This ensures the values are scaled to fit within
the $[0,255]$ range.

  4. 4.

Component Recombination: The normalized components, denoted as
$H_{\text{norm}},S_{\text{norm}},V_{\text{norm}}$, are recombined to form the
normalized $HSV$ ROI, represented as $HSV_{\text{norm}}$.

Following this normalization process, the color features of the frame are
standardized, as illustrated in Fig. 3 (c), (g), (k). This ensures uniform
contribution from each feature to the final representation, facilitating
precise color thresholding for taxiway line marking detection in the
subsequent step.

###  3.5 HSV-based Color Thresholding

Color thresholding is an essential technique in image segmentation, leveraging
color information to partition image pixels into meaningful regions [9]. In
the context of ALINA, this technique finds its application in isolating the
taxiway line markings from the rest of the regions within the ROI, using the
$HSV$ color space. Hue captures the wavelength of color, while saturation
measures the intensity, and value quantifies the brightness.

Determining the precise range for $HSV$ that corresponds to the taxiway line
markings necessitated a series of empirical tests. Multiple frame samples were
analyzed and a frequency distribution of $HSV$ values for taxiway line marking
regions were plotted. Peaks in this distribution, indicative of dominant $HSV$
values for taxiway line markings, helped in ascertaining the lower and upper
bounds of $H,S,V$, i.e. (0, 70, 170) and (255, 255, 255), respectively.

For a pixel p with $HSV$ values denoted by $H(p)$, $S(p)$, $V(p)$, the color
thresholding function $\Theta(p)$is defined in Eq. 5:

$\Theta(p)=\begin{cases}255&\text{if }0\leq H(p)\leq 255\\\ &\text{and }70\leq
S(p)\leq 255\\\ &\text{and }170\leq V(p)\leq 255\\\
0&\text{otherwise}\end{cases}$ (5)

Here, $\Theta(p)$ produces a binary outcome for each pixel in the ROI: a value
of 255 (white) indicates a pixel belonging to the taxiway line marking, while
0 (black) denotes a pixel that does not. However, after applying HSV-based
color thresholding, some non-taxiway line marking pixels within the ROI still
matched the specified range, as shown in Fig. 3 (d), (h), (l). ALINA addresses
this in the subsequent step.

Figure 3: (a),(e),(i): ROI Definition, (b),(f),(j): Perspective
Transformation, (c),(g),(k): Color Feature Normalization, (d),(h),(l): HSV-
based Color Thresholding

###  3.6 Histogram-based Analysis of the Thresholded ROI

The histogram analysis focuses on the vertical projection of white pixels in
the thresholded ROI, analyzing the spatial distribution and density of the
taxiway line markings.

For a thresholded ROI with dimensions $W\times H$, where $W$ represents the
width (number of columns) and $H$ represents the height (number of rows), the
binary representation of a pixel at position $i,j$ is defined in the Eq. 6,
where $i$ is the column index and $j$ is the row index:

$B(i,j)=\begin{cases}1&\text{if pixel at }(i,j)\text{ is white}\\\
0&\text{otherwise}\end{cases}$ (6)

The vertical histogram, denoted as $H_{\text{vert}}(i)$, quantifies the
column-wise distribution of white pixels and is calculated using Eq. 7:

$H_{\text{vert}}(i)=\sum_{j=0}^{H}B(i,j)$ (7)

For each column $i$, this equation aggregates the presence of white pixels
across all rows $j$, offering a count of white pixels for that column. When
plotted against the column index $i$, the histogram produced accentuates the
density of white pixels along the y-axis. Peaks in this histogram, denote the
presence and spatial positioning of taxiway line markings within the ROI.

###  3.7 Identifying Line Markings and Mitigating False Detections

The histogram peak value, represented by $H_{p}$, indicates the highest
density of white pixels in a particular column of the histogram. It was
important to identify whether a peak in the histogram truly represents a
taxiway line marking or in contrast, is a result of noise or other
disturbances. We identified the presence of a taxiway line marking in the ROI
using a threshold value.

Figure 4: (a),(d),(g): CIRCLEDAT, (b),(e),(h): Frame Unwarping, (c),(f),(i):
Taxiway Line Marking Annotation

###  3.8 CIRCLEDAT: Circular Threshold Pixel Discovery and Traversal Algorithm

The CIRCLEDAT algorithm assists in isolating the pixels that correspond to the
taxiway line markings, irrespective of their dimension or curvature, and
eliminate all other pixels from the ROI. For an ROI $\mathcal{I}$ with
dimensions $W\times H$, an initial coordinate pair $(x,y)$, a radius $\theta$,
a set $\mathcal{V}$ for recording visited pixels, and an array $\mathcal{L}$
for collecting taxiway line marking pixels, the algorithm executes as follows:

  1. 1.

Initialization: The starting point $(x,y)$ is pushed onto a stack $S$ and
recorded in $\mathcal{V}$. A set $\mathcal{R}$ is created containing all pixel
coordinates within the circular distance.

  2. 2.

Exploration: While $S$ is not empty, the top coordinate $(x,y)$ is popped. If
$\mathcal{I}[y][x]=255$, which indicates a white pixel, $(x,y)$ is added to
$\mathcal{L}$. For each offset $(i,j)$ in $\mathcal{R}$:

     * •

Calculate new coordinates $(x_{\text{new}},y_{\text{new}})=(x+i,y+j)$.

     * •

If $(x_{\text{new}},y_{\text{new}})\in\mathcal{V}$ or
$(x_{\text{new}},y_{\text{new}})$ is outside $0\leq x_{\text{new}}<W$ and
$0\leq y_{\text{new}}<H$, continue to the next offset.

     * •

Otherwise, push $(x_{\text{new}},y_{\text{new}})$ onto $S$ and record in
$\mathcal{V}$.

  3. 3.

Result: Once $S$ is exhausted, the algorithm returns $\mathcal{L}$,
representing all the white pixels, which correspond to the taxiway line
markings.

The Fig. 4 (a), (d), (g) represent the output generated after applying the
CIRCLEDAT algorithm (1) within the ROI. Through a depth-first search approach,
CIRCLEDAT ensures a comprehensive exploration of pixels pertaining to the
taxiway line markings. The $\mathcal{V}$ set aids in efficient traversal by
preventing revisits, and the use of $\mathcal{R}$ ensures a circular-based
neighborhood exploration.

Algorithm 1 Circular Threshold Pixel Discovery and Traversal

1:function CIRCLEDAT($image$)

2: $stack\leftarrow[(x,y)]$

3: $visited.add((x,y))$

4: $circular\\_range\leftarrow
list(product(range(-\theta,\theta+1),repeat\leftarrow 2))$

5: $circular\\_range.remove((0,0))$

6: while $stack$ is not empty do

7: $x,y\leftarrow stack.pop()$

8: if $image[y][x]=255$ then

9: $add\ (x,y)\ to\ line\\_marking\\_pixels$

10: for $i,j\leftarrow circular\\_range$ do

11: $x\\_new\leftarrow x+i$

12: $y\\_new\leftarrow y+j$

13: if $(x\\_new,y\\_new)=visited$ then

14: continue

15: end if

16: if $x\\_new,y\\_new<0\ or\ x\\_new,y\\_new\geq image.width,image.height$
then

17: continue

18: end if

19: $add\ (x\\_new,y\\_new)\ to\ stack$

20: $visited.add((x\\_new,y\\_new))$

21: end for

22: end if

23: end while

24: $return\ line\\_marking\\_pixels$

25:end function

###  3.9 Frame Unwarping and Annotating the Taxiway Line Marking Pixels

The final stage of labeling the frame involves an inverse perspective
transformation that returns the warped ROI to its original view, as shown in
Fig. 4 (b) ,(e), (h). After obtaining the unwarped ROI, white pixels are
located and mapped onto the original frame using color red to clearly identify
the taxiway line markings, as illustrated in Fig. 4 (c), (f), (i). This
representation provides a precise and clear depiction of the taxiway line
markings in the original frame. In addition, a text file is generated
containing the x, y coordinates of all pixels corresponding to the taxiway
line markings.

Having completed the labeling of the video’s initial frame, ALINA proceeds to
label the subsequent frames using the same process and the ROI established for
the first frame, as illustrated in Fig. 2.

##  4 Experimental Results

###  4.1 ALINA Performance: Specifications and Scenarios

The detailed processing time breakdown for ALINA when labeling a frame is
presented in Tab. 1. On average, ALINA requires 50.9 milliseconds (ms) to
label a single frame, yielding a rate of approximately 19.65 frames per second
(fps). In the course of our systematic labeling process, ALINA effectively
labeled 60,249 frames on a Linux system equipped with an Intel Core i7-9700K
CPU clocked at 3.60GHz and 15GB RAM, operating on Ubuntu 22.04.1 LTS. The
algorithm was developed in the PyCharm IDE with Python 3.8.15, harnessing
essential libraries such as OpenCV, NumPy, MatPlotLib, and statistics.

Table 1: Processing time analysis of ALINA (in Milliseconds). Process | Time (ms)
---|---
Perspective Transformation | 4.41
Color Feature Normalization | 5.91
HSV-based Color Thresholding | 1.05
Histogram Analysis | 28.71
CIRCLEDAT | 3.33
Projection Remapping | 6.68
Total | 50.09

As mentioned earlier, we applied ALINA on a subset of the AssistTaxi dataset,
consisting of 60,249 frames extracted from three distinct videos, each with
unique camera angles. Fig. 3 and Fig. 4 demonstrates ALINA’s consistent
labeling performance across these frames, unaffected by differing camera
angles or weather conditions. Specifically, in Fig. 3 (a) from the first
video, ALINA labeled the taxiway line marking between two aircrafts. In Fig. 3
(e) from the second video, it labeled three directional taxiway line markings:
left, straight, and right. Lastly, in Fig. 3 (i) from the third video, ALINA
labeled the taxiway line marking in front of the aircraft, which is situated
between stationary aircraft on the left and grassy area on the right.

###  4.2 Ablation Study on Threshold Value

Initially, the decision was kept binary, in which there was no set threshold,
as shown in Eq. 8. This approach considered even a slight peak in the
histogram as a taxiway line marking, leading to a high percentage of false
positives, as shown in Tab. 2.

$\Delta(p)=\begin{cases}1&\text{if }H_{p}>0\\\ 0&\text{otherwise}\end{cases}$
(8)

Here $\Delta(p)$ indicates the presence (1) or absence (0) of the taxiway line
marking.

Through empirical testing and histogram analyses, we identified that true
taxiway line markings consistently yielded peak values significantly above
sporadic noise. As shown in Tab. 2, setting a threshold at 75 led to a
substantial fall in the percentage of false positives, but by raising the
threshold to 150, the false positives were dropped to 0. Hence, the
$T_{optimal}$ was established at 150, using the equations 9 and 10. This was
primarily because true taxiway line markings consistently resulted in columns
extending well over 150 white pixels, while disturbances never reached this
level.

Table 2: Threshold Value Comparison Threshold Value | False Positives (%)
---|---
0 | 83.33
75 | 22.22
150 | 0

$T_{\text{optimal}}=\underset{T}{\mathrm{argmin}}\left(F_{\text{false
positive}}(T)-F_{\text{true positive}}(T)\right)$ (9)
$\Delta(p)=\begin{cases}1&\text{if }H_{p}>=T_{optimal}\\\
0&\text{otherwise}\end{cases}$ (10)

Once the taxiway line marking is detected using $\Delta_{150}(p)$, ALINA
extracts its centroid coordinate, initializing the subsequent CIRCLEDAT
algorithm. In contrast, if there is no taxiway line marking in the ROI, ALINA
simply stores the frame along with an empty text file, signifying that there
is no taxiway line marking present in the frame, as shown in Fig. 2.

###  4.3 Generating a Context-based Edge Map Set

To assess ALINA and CDLEM’s effectiveness, we manually created a set of
context-based edge maps (CBEM), which emphasize the edge pixel presence, edge
corner localization, thick edge occurrence, and edge connectivity [7]. We
prioritized the detection of the edges of a taxiway line marking as our
primary validation metric, because this alone provides precise information
into the line marking’s position within the frame. Our approach for developing
the CBEM was as follows:

  1. 1.

Outlining the Contour Region: The taxiway line markings in the frames were
outlined manually to create an accurate reference without including any other
edge details from the frame.

  2. 2.

Pre-processing: The contour region was transformed to grayscale and then
subjected to Gaussian blur, which helped in reducing the visual noise and
improved the clarity of edges. Consequently, the gradient amplitude and
direction were calculated and non-maximum suppression was applied to eliminate
the non-edge pixels.

  3. 3.

Edge Detection with the Canny Algorithm: We used the Canny algorithm for
precise edge extraction of taxiway line markings. We also employed an
automated method for selecting the upper and lower thresholds [34]. This
method computes the median pixel intensity $v$ of an image and subsequently
determines the thresholds using equations 11 and 12:

$\text{lower}=\max(0,(1.0-\sigma)\times v)$ (11)
$\text{upper}=\min(255,(1.0+\sigma)\times v)$ (12)

where $\sigma$ is a coefficient, defaulting to 0.33, for refining the
thresholds.

The process of manually outlining the contour region around the taxiway line
marking and generating CBEM for a frame is illustrated in Fig. 5 (a) and (b)
respectively. The Fig. 1 (e) shows the output of ALINA on the same frame.

Figure 5: (a) Manually Outlined Contour Region (b) CBEM

From the 60,249 frames, we selected a set of 120 frames to construct the
CBEM’s. The 60,249 frames spanned from three videos with durations of 11.47,
1.34, and 3.23 minutes. Our objective was to identify the frames representing
scenario shifts. Instead of conducting a granular frame-by-frame analysis, we
reviewed the videos comprehensively and marked the specific frames that
captured the scenario shifts, amounting to a total of 120 images.

Our selection is underpinned by the Law of Large Numbers (LLN), as illustrated
in Eq. 13:

$\bar{X}_{n}\rightarrow\mu\quad\text{as}\quad n\rightarrow\infty$ (13)

where $\bar{X}_{n}$ represents the sample mean and $\mu$ is the expected
population mean [14]. This indicates that our subset, if representatively
selected, provides a reliable approximation of the comprehensive dataset’s
attributes.

Furthermore, the Central Limit Theorem (CLT) [14] also reinfornces our
approach, as expressed in Eq. 14:

$\frac{S_{n}-n\mu}{\sigma\sqrt{n}}\rightarrow N(0,1)$ (14)

where $S_{n}=X_{1}+X_{2}+\ldots+X_{n}$ and $X_{i}$ are independent,
identically distributed random variables, $n$ is the sample size, $\mu$ is the
population mean, and $\sigma$ is the standard deviation. The CLT’s cornerstone
assertion, relevant in our context, is that with a sufficiently extensive
sample size, the sample mean’s distribution gravitates towards a normal
distribution. This holds irrespective of the originating population’s
distribution. Therefore, the mean distribution extrapolated from all possible
120-frame subsets is poised to achieve normality. Leveraging the Central Limit
Theorem, our diverse 120-frame sample is statistically representative of the
entire 60,249-frame dataset. With the backing of both LLN and CLT, our method
ensures a robust evaluation of ALINA and CDLEM using CBEM set.

###  4.4 Sliding Window Vs CIRCLEDAT

In the study by Muthalagu et al. [27], a sliding window (SW) search algorithm
detected lane line marking pixels with a time complexity of $O(m\times n)$,
where $m$ and $n$ represent the height and width of the frame, respectively.
In contrast, our work introduces the innovative CIRCLEDAT algorithm, which
pinpoints line marking pixels with a significantly reduced time complexity of
$O(k)$, where k is number of pixels corresponding to the line marking in a
given frame. Prior to introducing CIRCLEDAT, we used the SW search algorithm
to detect taxiway line marking pixels. Tab. 3 compares the performance of both
algorithms when tested on the taxiway dataset frames.

Table 3: Comparative Analysis of Pixel Detection Algorithms Algorithm | Time Complexity | Processing Time (ms)
---|---|---
SW Search | $O(m\times n)$ | 10.90
CIRCLEDAT | $O(k)$ | 3.33

###  4.5 Performance Evaluations

We evaluated ALINA’s performance against CDLEM using CBEM set. By comparing x
and y coordinates from both the CBEM and ALINA or CDLEM, we calculated true
positives (TP) and false negatives (FN). TP indicates accurate identification
of taxiway line marking pixels, while FN denotes missed pixels that should
have been identified as part of the taxiway line marking.

The recall or detection rate, essential for evaluating object detection
algorithms, gauges an algorithm’s accuracy in identifying the particular
objects in a frame [30] [12]. In airport taxiway line marking detection,
missing a marking can pose safety risks, underscoring the importance of
comprehensive identification. The detection rate is calculated as the ratio of
TP values to the sum of TP and FN values, as shown in Eq. 15.

$Detection\ Rate\ (Recall)=\ \frac{TP}{TP+FN}$ (15)

ALINA and CDLEM achieved detection rates of 98.45% and 91.14%, respectively,
as shown in Tab. 4. Additionally, in terms of processing time, ALINA processed
a frame in 50.09 ms, corresponding to approximately 19.65 fps, whereas CDLEM
took 120.35 ms per frame, translating to roughly 8.30 fps.

ALINA’s superior performance is attributed to several key features. Its
perspective transformation provides a bird’s-eye view of taxiway, eliminating
distortions and offering clarity in distinguishing line markings from
anomalies—a challenge for CDLEM due to varying distances and angles. Unlike
CDLEM, which may miss essential pixels using the Hough Transform and curve
fitting, ALINA’s shift to the $HSV$ color space, prioritizing H, S, and V
components, enhances taxiway line marking detection even under varying
weather. The CIRCLEDAT algorithm within ALINA swiftly captures all crucial
pixels of taxiway markings, regardless of their shape or fragmentation. A
notable limitation of CDLEM is its need to define a new ROI for each scenario
shift, resulting in 120 scenarios for 60,249 frames, demanding extensive video
pre-viewing. In contrast, ALINA only requires an ROI for the initial frame of
a video, applied consistently to all following frames, leading to just 3 ROIs
for the same number of frames.

Table 4: Comparing ALINA Vs CDLEM Algorithm | Detection Rate (%) | Processing Time (ms)
---|---|---
ALINA | 98.45 | 50.09
CDLEM | 91.14 | 120.35

##  5 Conclusion

In this work, we propose ALINA, a novel annotation framework, primarily
designed for labeling pixel coordinates in taxiway datasets. This approach
streamlines the annotation process, significantly reducing cost and manual
labor needed for precise labeling in these contexts. We also propose a
traversal algorithm CIRCLEDAT, which determines the pixels corresponding to
the taxiway line markings. We provide a comparative analysis with the sliding
window search algorithm and evaluate the performance of the framework on a
subset of the AssistTaxi dataset. We have tested ALINA with labels generated
for 60,249 frames, and evaluated it with a context-based edge map (CBEM) set
which was generated manually. We also provide theoretical analysis and a
comparative study for ALINA to Contour-Based Detection and Line Extraction
Method (CDLEM). In the future, we aim to evaluate ALINA for annotating car
lane datasets, with the CIRCLEDAT algorithm being utilized to identify pixel
coordinates of road lane markings.

## References

  * Al Noman et al. [2023] Md Abdullah Al Noman, Li Zhai, Firas Husham Almukhtar, Md Faishal Rahaman, Batyrkhan Omarov, Samrat Ray, Shahajan Miah, and Chengping Wang.  A computer vision-based lane detection technique using gradient threshold and hue-lightness-saturation value for an autonomous vehicle.  _International Journal of Electrical and Computer Engineering_ , 13(1):347, 2023.
  * Aly et al. [2015] Heba Aly, Anas Basalamah, and Moustafa Youssef.  Lanequest: An accurate and energy-efficient lane detection system.  In _2015 IEEE International Conference on Pervasive Computing and Communications (PerCom)_ , pages 163–171, 2015.
  * Andrei et al. [2022] Mihail-Alexandru Andrei, Costin-Anton Boiangiu, Nicolae Tarbă, and Mihai-Lucian Voncilă.  Robust lane detection and tracking algorithm for steering assist systems.  _Machines_ , 10(1):10, 2022.
  * Anonym [2017] Anonym.  Evaluation of a prototype advanced taxiway guidance system (atgs), 2017.
  * Batra and Gauci [2020] Aman Batra and Jason Gauci.  Aerodrome taxiway line detection and cross-track error estimation using computer vision techniques.  In _2020 IEEE Aerospace Conference_ , pages 1–9, 2020.
  * Bhattacharyya et al. [2021] Siddhartha Bhattacharyya, Jennifer Davis, Anubhav Gupta, Nandith Narayan, and Michael Matessa.  Assuring increasingly autonomous systems in human-machine teams: An urban air mobility case study.  _Electronic Proceedings in Theoretical Computer Science_ , 348:150–166, 2021.
  * Canny [1986] John Canny.  A computational approach to edge detection.  _IEEE Transactions on pattern analysis and machine intelligence_ , (6):679–698, 1986.
  * Chen et al. [2015] Tairui Chen, Zhilu Chen, Quan Shi, and Xinming Huang.  Road marking detection and classification using machine learning algorithms.  In _2015 IEEE Intelligent Vehicles Symposium (IV)_ , pages 617–621, 2015.
  * Cheng et al. [2001] Heng-Da Cheng, X_ H_ Jiang, Ying Sun, and Jingli Wang.  Color image segmentation: advances and prospects.  _Pattern recognition_ , 34(12):2259–2281, 2001.
  * Chougule et al. [2018] Shriyash Chougule, Nora Koznek, Asad Ismail, Ganesh Adam, Vikram Narayan, and Matthias Schulze.  Reliable multilane detection and classification by utilizing cnn as a regression network.  In _Proceedings of the European conference on computer vision (ECCV) workshops_ , pages 0–0, 2018.
  * Cultrera et al. [2020] Luca Cultrera, Lorenzo Seidenari, Federico Becattini, Pietro Pala, and Alberto Del Bimbo.  Explaining autonomous driving by learning end-to-end visual attention.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) Workshops_ , 2020.
  * Diebold and Mariano [2002] Francis X Diebold and Robert S Mariano.  Comparing predictive accuracy.  _Journal of Business & economic statistics_, 20(1):134–144, 2002.
  * Ding et al. [2020] Ling Ding, Huyin Zhang, Jinsheng Xiao, Bijun Li, Shejie Lu, Reinhard Klette, Mohammad Norouzifard, and Fang Xu.  A comprehensive approach for road marking detection and recognition.  _Multimedia Tools and Applications_ , 79(23-24):17193–17210, 2020.
  * Feller [1991] William Feller.  _An introduction to probability theory and its applications, Volume 2_.  John Wiley & Sons, 1991.
  * Feng et al. [2022] Zhengyang Feng, Shaohua Guo, Xin Tan, Ke Xu, Min Wang, and Lizhuang Ma.  Rethinking efficient lane detection via curve modeling.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 17062–17070, 2022.
  * Foundation [2023] Flight Safety Foundation.  Asn aviation safety database: https://aviation-safety.net/database/, 2023.
  * Fredriksson et al. [2020] Teodor Fredriksson, David Issa Mattos, Jan Bosch, and Helena Holmström Olsson.  Data labeling: An empirical investigation into industrial challenges and mitigation strategies.  In _International Conference on Product-Focused Software Process Improvement_ , pages 202–216. Springer, 2020.
  * Ganeriwala et al. [2023a] Parth Ganeriwala, Siddhartha Bhattacharyya, Sean Gunther, Brian Kish, Mohammed Abdul Hafeez Khan, Ankur Dhadoti, and Natasha Neogi.  Assisttaxi: A comprehensive dataset for taxiway analysis and autonomous operations.  In _2023 International Conference on Machine Learning and Applications (ICMLA)_ , pages 1094–1099, 2023a.
  * Ganeriwala et al. [2023b] Parth Ganeriwala, Siddhartha Bhattacharyya, and Raja Muthalagu.  Cross dataset analysis and network architecture repair for autonomous car lane detection*.  In _2023 IEEE Intelligent Vehicles Symposium (IV)_ , pages 1–6, 2023b.
  * Gupta and Choudhary [2018] Any Gupta and Ayesha Choudhary.  A framework for camera-based real-time lane and road surface marking detection and recognition.  _IEEE Transactions on Intelligent Vehicles_ , 3(4):476–485, 2018.
  * Hoang et al. [2019] Toan Minh Hoang, Se Hyun Nam, and Kang Ryoung Park.  Enhanced detection and recognition of road markings based on adaptive region of interest and deep learning.  _IEEE Access_ , 7:109817–109832, 2019.
  * JEPPESEN [2021] JEPPESEN.  Jeppesen airport moving maps: ww2.jeppesen.com/navigation-solutions/airport-moving-maps/, 2021.
  * Jiao et al. [2019] Xinyu Jiao, Diange Yang, Kun Jiang, Chunlei Yu, Tuopu Wen, and Ruidong Yan.  Real-time lane detection and tracking for autonomous vehicle applications.  _Proceedings of the Institution of Mechanical Engineers, Part D: Journal of Automobile Engineering_ , 233(9):2301–2311, 2019.
  * [24] Jeffrey Kiske.  Automatic labeling of lane markings for autonomous vehicles.
  * Liu et al. [2021] Ruijin Liu, Zejian Yuan, Tie Liu, and Zhiliang Xiong.  End-to-end lane shape prediction with transformers.  In _Proceedings of the IEEE/CVF winter conference on applications of computer vision_ , pages 3694–3702, 2021.
  * Meymandi-Nejad et al. [2021] Claire Meymandi-Nejad, Esteban Perrotin, Ariane Herbulot, and Michel Devy.  Aircraft navigation on taxiways: Evaluation of line detection algorithms proposed for automotive applications.  In _Proceedings of the 2020 4th International Symposium on Computer Science and Intelligent Control_ , New York, NY, USA, 2021. Association for Computing Machinery.
  * Muthalagu et al. [2020] Raja Muthalagu, Anudeepsekhar Bolimera, and V Kalaichelvi.  Lane detection technique based on perspective transformation and histogram analysis for self-driving cars.  _Computers & Electrical Engineering_, 85:106653, 2020.
  * Narayan et al. [2023] Nandith Narayan, Parth Ganeriwala, Randolph M. Jones, Michael Matessa, Siddhartha Bhattacharyya, Jennifer Davis, Hemant Purohit, and Simone Fulvio Rollini.  Assuring learning-enabled increasingly autonomous systems*.  In _2023 IEEE International Systems Conference (SysCon)_ , pages 1–7, 2023.
  * Neven et al. [2018] Davy Neven, Bert De Brabandere, Stamatios Georgoulis, Marc Proesmans, and Luc Van Gool.  Towards end-to-end lane detection: an instance segmentation approach.  In _2018 IEEE Intelligent Vehicles Symposium (IV)_ , pages 286–291, 2018.
  * Padilla et al. [2021] Rafael Padilla, Wesley L Passos, Thadeu LB Dias, Sergio L Netto, and Eduardo AB Da Silva.  A comparative analysis of object detection metrics with a companion open-source toolkit.  _Electronics_ , 10(3):279, 2021.
  * Proesmans et al. [2018] Marc Proesmans Proesmans, Bert De Brabandere Brabandere, Davy Neven Neven, Luc Van Gool Gool, and Stamatios Georgoulis Georgoulis.  Towards end-to-end lane detection: an instance segmentation approach.  2018\.
  * Qin et al. [2020] Zequn Qin, Huanyu Wang, and Xi Li.  Ultra fast structure-aware deep lane detection.  In _Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part XXIV 16_ , pages 276–291. Springer, 2020.
  * Qu et al. [2021] Zhan Qu, Huan Jin, Yang Zhou, Zhen Yang, and Wei Zhang.  Focus on local: Detecting lane marker from bottom up via key point.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 14122–14130, 2021.
  * Rosebrock [2015] Adrian Rosebrock.  Zero-parameter, automatic canny edge detection with python and opencv.  2015\.
  * Shuhua and Gaizhi [2010] Li Shuhua and Guo Gaizhi.  The application of improved hsv color space model in image processing.  In _2010 2nd International Conference on Future Computer and Communication_ , pages V2–10. IEEE, 2010.
  * Stern [2001] P Stern.  Advanced surface movement guidance system: Installing honeywell’s a- smgcs system has helped reduce ground delays at incheon international airport (iia), 2001.
  * Tabelini et al. [2021] Lucas Tabelini, Rodrigo Berriel, Thiago M Paixao, Claudine Badue, Alberto F De Souza, and Thiago Oliveira-Santos.  Polylanenet: Lane estimation via deep polynomial regression.  In _2020 25th International Conference on Pattern Recognition (ICPR)_ , pages 6150–6156. IEEE, 2021.
  * Theuma et al. [2019] Kevin Theuma, David Zammit-Mangion, Jason Gauci, Kenneth Chircop, and Nicolas Riviere.  A particle filter for ground obstacle tracking in the airfield.  In _AIAA Scitech 2019 Forum_ , page 1265, 2019.
  * Wang et al. [2020] Bingke Wang, Zilei Wang, and Yixin Zhang.  Polynomial regression network for variable-number lane detection.  In _Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part XVIII 16_ , pages 719–734. Springer, 2020.
  * Wang et al. [2022] Jinsheng Wang, Yinchao Ma, Shaofei Huang, Tianrui Hui, Fei Wang, Chen Qian, and Tianzhu Zhang.  A keypoint-based global association network for lane detection.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 1392–1401, 2022.
  * Xu et al. [2022] Shenghua Xu, Xinyue Cai, Bin Zhao, Li Zhang, Hang Xu, Yanwei Fu, and Xiangyang Xue.  Rclane: Relay chain prediction for lane detection.  In _European Conference on Computer Vision_ , pages 461–477. Springer, 2022.
  * Yoo et al. [2020] Seungwoo Yoo, Hee Seok Lee, Heesoo Myeong, Sungrack Yun, Hyoungwoo Park, Janghoon Cho, and Duck Hoon Kim.  End-to-end lane marker detection via row-wise classification.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition workshops_ , pages 1006–1007, 2020.
  * Zhang and Mahale [2018] Wenhui Zhang and Tejas Mahale.  End to end video segmentation for driving : Lane detection for autonomous car.  _CoRR_ , abs/1812.05914, 2018.


# An Improved Dilated Convolutional Network for Herd Counting in Crowded
Scenes

Soufien Hamrouni1, Hakim Ghazzai1, Hamid Menouar2, and Yehia Massoud1

This work was made possible, in part, by grant NPRP #NPRP12S-0313-190348 from
the Qatar National Research Fund (a member of The Qatar Foundation). The
statements made herein are solely the responsibility of the authors.  1School
of Systems & Enterprises, Stevens Institute of Technology, Hoboken, NJ, USA
2Qatar Mobility Innovations Center (QMIC), Qatar University, Doha, Qatar

###### Abstract

Crowd management technologies that leverage computer vision are widespread in
contemporary times. There exists many security-related applications of these
methods, including, but not limited to: following the flow of an array of
people and monitoring large gatherings. In this paper, we propose an accurate
monitoring system composed of two concatenated convolutional deep learning
architectures. The first part called Front-end, is responsible for converting
bi-dimensional signals and delivering high-level features. The second part,
called the Back-end, is a dilated Convolutional Neural Network (CNN) used to
replace pooling layers. It is responsible for enlarging the receptive field of
the whole network and converting the descriptors provided by the first network
to a saliency map that will be utilized to estimate the number of people in
highly congested images. We also propose to utilize a genetic algorithm in
order to find an optimized dilation rate configuration in the back-end. The
proposed model is shown to converge 30% faster than state-of-the-art
approaches. It is also shown that it achieves 20% lower Mean Absolute Error
(MAE) when applied to the Shanghai data set.

###### Index Terms:

Crowd management, Convolutional neural networks, Deep learning, Image
processing.

##  I Introduction

The study of the collective behavior of mass gatherings has attracted much
research interest and governmental investment in order to efficiently monitor
a crowd to reduce the risk of crowd-related disasters [1]. With the
improvement of video surveillance infrastructure, video-based human-behavior
motion analysis has become the new state-of-the-art. Various techniques have
been developed to deal with highly congested images and accurately estimate
the number of objects in these scenes. These heuristics vary from directly
counting the number of people present in the target images to providing
density maps that reflect the distribution of the targets in given images. The
reason behind choosing a density map as an output is that dealing with these
feature maps is more accurate as they provide more insights on how the models
perceive different clusters in the frame.

The majority of the work in congested scenes can be divided into four groups:
The first is a detection-based approach. It relies on a moving window over the
image that uses a trained algorithm to extract low level features from the
object in question, e.g. the case of human detection using Haar features and
Histogram Oriented Gradient (HOG). However, these types of straightforward
models perform poorly when it comes to highly dense images where the targets
are compact and most of times are partly visible. The second method is a
regression-based approach. In order to remedy the errors of the previous
method while dealing with dense scenes, researchers developed regression-based
techniques to utilize the relations among descriptive features extracted from
different regions and then aggregate them to estimate the total count in these
images. Low level features can be fed to regression models such as Scale
Environment Feature Transform (SIFT) and use interest points to estimate the
count [2]. The third technique is a density-based method. As a matter of fact,
one critical aspect of images that is left unattended by regression-based
methods is called saliency. It describes the conspicuity at every position in
the visual field by a finite number and guides the selection of important
patches, based on the spatial distribution of saliency. To remedy this
weakness, this method proposes a linear mapping between local features and the
density map [3] and a nonlinear mapping using a random forest regressor to
vote for densities of multiple target objects[4]. This mapping exists between
the patch features and the relative locations of all objects inside the patch.

The final method employs Convolutional Neural Networks (CNN); this CNN based
methods have been widely used to deal with congested scenes [5], due to their
ability to learn the semantic information of the image. Currently, there are
two major strategies to deploy CNNs in such problem-sets. The first is to
directly learn mapping between images and the count by directly training the
network on the images and their respective counts.

Figure 1: The components of our proposed architecture and the types of output
at each phase.

The second aims at predicting density maps and then sum all the pixels to
obtain the count. These models are trained to optimize their density maps
instead of directly optimizing the predicted number of people since the former
preserves more information than the latter. One of the previously used
architectures are called Multi-column CNNs (MCNNs) [6], which stack multiple
columns of CNNs and utilize different kernels in order to extract deep
descriptors from the frame. Another architecture used in [7] is called Crowd-
Net. It uses two parallel networks: one is a shallow network and the other is
deep and combines both outputs to construct a feature map and sum its pixels
to generate the total count.

The main focus in this paper is to provide a more accurate solution by using
high-level features and deep neural networks without losing too much
information. We propose an architecture that can be decomposed into two
concatenated convolutional neural networks as shown in Fig. 1, the first part
is called Front-end and the second part is named Back-end. The former is
responsible for extracting high-level features from the input images while the
latter is used to concatenate and aggregate the deep descriptors feature
extractor in order to provide deep information about the saliency to estimate
the number of people in these highly dense images.

In this paper, we propose an end-to-end architecture that not only estimates
accurately the number condensed objects/persons in given frames, but also
provides a precise density map that shows the location of the clusters and
that can be used for crowd behaviour studies as demonstrated in Fig. 2. Our
proposed model not only outperforms the state-of-the-art in terms of speed of
convergence by taking less than 30% number of epochs to reach stagnation, it
also scores an MAE lower by 20% than the state-of-the-art’s on Shanghai
dataset and that is due our method of optimizing the choice of the hyper-
parameters by using a genetic algorithm as our search technique.

Figure 2: Example: Pictures in the first row are the real images, pictures in
the second row are the predicted density maps, and the pictures in the third
row are the true density maps.

##  II Methodology and Architecture

Our proposed solution relies on density estimation instead of directly
predicting the count, therefore our first step is to generate each image’s
true density map.

###  II-A Ground Truth Generation

We first have to generate the ground truth values from the original images. A
feature map is generated with 1/8 the size of the initial image while
considering the spatial distribution of the pixels in the image. This can be
achieved by blurring each head using a normalized Gaussian kernel (normalized
to 1). The geometry-adaptive filter is denoted by $F(t)$ and expressed as
follows:

$F(t)={\sum_{n=1}^{N}\delta(t-t_{n})\cdot G_{\sigma_{n}}},\text{
where}\indent{\sigma_{n}}=\beta_{n}\cdot\bar{d_{n}.}$ (1)

Given $N$ targets in the image, for each targeted object $t_{n}$ in the ground
truth $\delta$, we denote by $\bar{d_{n}}$ the average distance of $k$ nearest
neighbors in each of the $N$ target images. To generate the density map, we
convolve $\delta(t-t_{n})$ with a Gaussian kernel $G_{\sigma_{n}}$, with a
standard variation $\sigma_{n}$, where $t$ is the position of pixel in each
image. In our experiment, we follow the configuration in [6] where $\beta_{n}$
= 0.3 and $k$ =3. After generating the true feature maps for each image in our
dataset, the next step is finding the best feature extractor we can use from
the numerous architectures whilst fixing the same back layers and with the
same hyper-parameters’ configuration.

Figure 3: Resulting convolutions with a kernel the size $3\times 3$ after
using a dilation rate of 1, 2, and 3, in the far left, in the middle, and in
the far right, respectively.

###  II-B Front-End Development

In this case, we adopt the Visual Group Geometry 19 (VGG-19) pretrained on
ImagNet [8], We select this model due to its light architecture, flexibility,
and ease of use for transfer learning. We use multiple layers of this
architecture except the output layers in order to preserve pretrained model
weights.. Although this model contains 19 layers, we select only the first 12
layers since it gave the best results based on a complexity/perfomance
tradeoff.

###  II-C Back-End Development

We propose to make few adjustments to the Back-end in order to make it
compatible with the pre-trained VGG-19 architecture. We add two more layers on
top of the Back-end used in [9] with 1024 channels in order to better use the
highly granular input coming from the Front-end.

####  II-C1 Dilated Convolutions

Although pooling layers are widely used for maintaining invariance and
controlling over-fitting, they also dramatically decrease the spatial
resolution. In other words, pooling layers lead to losses of spatial
information. A spatial dilated convolution can be defined as follows:

$z(m,n)=\sum_{i=1}^{M}\sum_{j=1}^{N}{x(m+r\cdot{i},n+r\cdot{j})\cdot{w(i,j)}},$
(2)

where $z(m,n)$ is the output of a dilated convolution from input x(m, n) and a
kernel $w(i,j)$ with the length and the width of $M$ and $N$ respectively. The
parameter $r$ is the dilation rate. If $r=1$, a dilated convolution turns into
a normal convolution and if the value of $r$ is greater than 1 then, our image
will be convoluted to a kernel with a stride equal to $r-1$ as shown in Fig.
3.

####  II-C2 Genetic Algorithm for Dilation Rates Optimization

The objective is to find the best set of dilation rates for the new Back-end.
Therefore instead of using the classic Grid Search method, we propose the use
of a genetic algorithm search, due to its speed and efficiency when it comes
to finding the best candidates in a given environment. Genetic algorithms are
a search technique that simulate the process of natural selection, fittest
candidates reproduce and pass their offspring to the next generation,
replacing the unfit candidates. The process starts with an initial set of
candidate solutions, called the Population. Each candidate solution (member)
is comprised of a vector encoding refered to as chromosomes. Each chromosome
is formed by a number of genes. In our case, a gene is a dilation rate in each
convolution layer and a chromosome is the set of dilation rates for each Back-
end in each network. This algorithm is characterized by repeating the
following five instructions: (a) population generation, (b) fitting each
member of the population, (c) selection of fittest individuals, (d) cross-over
and breeding of the survivals, and (e) randomly mutating newly bred networks.
The genetic algorithm for dilation rate optimization is detailed in Algorithm
1.

Algorithm 1 Genetic Alg. for Dilation Rate Optimization

1:Choose the number of generations and the number of populations in each
generation;

2:Choose mutation_rate, retain_rate, learning_rate;

3:Define $L$ as the list of possible dilation rates;

4:Networks$\leftarrow${};

5:for $i_{gen}$ in range(1,Generation) do

6: if Networks $==\\{\\}$ then

7: for $j$ in range(1,Population) do

8: Param_dict$\leftarrow$Random_choice($L$, for $i$ in range(1,8));

9: Networks($j$)$\leftarrow$Create_network(Param_dict, learning_rate, Batch-
size);

10: end for

11: end if

12: for $i_{pop}$ in range(1,Population) do

13: Train_Network(Networks($i_{pop}$));

14: MAE($i_{pop}$)$\leftarrow$Evaluate_MAE(Networks$(i_{pop})$);

15: end for

16: Parents=Select best retain_rate performing networks in
Networks;$\triangleright$ minimizing MAE

17: Children$\leftarrow$CrossOver_Breed(Parents’ Param_dict);

18: if rand() $<$ Mutation Rate then

19: Children$\leftarrow$Randomly_Mutate(Children’s Param_dict);

20: end if

21: Networks$\leftarrow${Parents,Children};

22:end for

23:Select the best performing network in Networks in the final
generation;$\triangleright$ Minimizing MAE

##  III Experimental Approach and Results

In this section, we present the experimental approach, evaluate the proposed
deep learning architecture, and compare its performance with the state-of-the-
art.

###  III-A Shanghai Dataset and Data Augmentation

The Shanghai Dataset is comprised of nearly 1,200 images with 330,000 labeled
heads. It is the largest crowd counting dataset in terms of the number
annotated heads. This dataset consists of two parts: Part A and B. Images in
Part A are randomly collected from the Internet; most of them have a large
number of people. Part B are captured from crowded streets of metropolitan
areas in Shanghai. We crop nine patches from each frame at different positions
with 1/4 size of the original image. The first four patches contain four
quarters of the image without overlapping while the other five patches are
randomly cropped from the input image. Afterwards, we mirror the patches so
that we double the training set.

###  III-B Evaluation Metrics

In this paper, we utilize both Mean Absolute Error (MAE) and Mean Squared
Error (MSE) as performance metrics to evaluate our proposed approach. The MAE
and MSE are defined as follows:

$\displaystyle\text{MAE}=\frac{1}{S}{\sum_{k=1}^{S}|{C_{k}-C_{k}^{GT}}|},\text{MSE}=\sqrt{\frac{1}{S}\sum_{k=1}^{S}|{C_{k}-C_{k}^{GT}}|^{2}},$
$\displaystyle\text{where }C_{k}=\sum_{i=1}^{W}\sum_{j=1}^{H}{Z_{i,j}},$ (3)

and $W$ and $H$ are the width and height of a predicted feature map. The
parameter $Z_{i,j}$ denotes the value of the pixel at the position $(i,j)$.

Figure 4: Layers loaded from pre-trained VGG-19 on ImageNet.

###  III-C Training Pipeline

In all the experiments, we use transfer learning i.e., we initialize the
Front-end with pre-trained layers from VGG-19, truncate the first twelve
layers and link them with a fixed Back-end with the same architecture and
hyper-parameter configuration. Next we initialize the backend weights with
gaussian noise that has a standard deviation of 0.01, and utilize a Stochastic
Gradient Descent (SGD) optimizer with a learning rate of $=10^{-7}$, 400
epochs and the Euclidean distance as the objective function, which is given as
follows:

$\text{L(T)}=\frac{1}{2D}\sum_{i=1}^{D}{||{Y(X_{i};T)-Y^{GT}_{i}}||^{2}_{2}}.$
(4)

In (4), $D$ is the size of training batch and $Y(X_{i};T)$ is the output
generated by models with parameters $T$. The notation $X_{i}$ represents the
input image while $Y^{GT}_{i}$ is the ground truth result of the input image
$X_{i}$. The notation $\|.\|_{2}$ denotes the L2 norm. For the genetic
algorithm search, we utilize a population size of 7 and we evolve the
population over 7 generations. The survival rate is set to 0.4 (i.e. the
fittest 40% of the population reproduces to round out the population in each
successive generation), and we set the mutation rate to 0.2 (i.e. each member
of the population can mutate up to 20% of its genes). As mentioned earlier,
the aim is to improve the performance of the whole model by finding the best
feature extractor and the best Back-end for this use-case. Due to the hardware
limitation, we choose the Shanghai dataset as the reference data and we choose
VGG-19 pre-trained on Image-net dataset shown in Fig. 4 as the feature
extractor. Despite the connection of the VGG-19 layers with the same back-end
as CSRNet in [9], it outperforms the front-end in the state-of-the art.
Moreover, when used with the proper Back-end, it gives better results on the
Shanghai dataset.

Figure 5: Validation MAE from training on the Shanghai dataset.

We train three networks. The first is the afromentionned CSRNet, the second is
a network constructed by using the same layers used in CSRNet’s front-end but
from VGG-19 instead of VGG-16 with the same back-end as the first network. The
third is a combination between the front-end from the second architecture
concatenated by our own back-end. The results from the second network show
that replacing pretrained layers from VGG-16 with those in VGG-19 results in
enhancing the model, thus we chose to use transfer learning with VGG-19. We
kept on adding layers from that pretrained network untill we reached the
configuration shown in Fig. 1.

TABLE I: Validation MAE each 100 epoch Epoch | VGG-16 | VGG-19 | Our model
---|---|---|---
100 | 57.290 | 44.988 | 42.187
200 | 38.084 | 32.038 | 28.553
300 | 29.763 | 26.114 | 21.652
400 | 24.924 | 24.470 | 19.144

This model outperforms CSRNet in terms of both MAE and in convergence speed,
as less epochs are required to reach stagnation. Fig. 5 illustrates the mean
value of MAE on the validation data after each epoch; it shows that our
network reached its stagnation around 270 epochs, which is 30% faster than
that of the state-of-the-art which was around 390 epochs. Our proposed
solution converges at around 200 epochs.

Moreover, in Table I, we summarize the performance of each network after 100
iterations by measuring the MAE of training at the mentioned epochs. The mean
of the validation MAE during the last 40 epochs of our proposed network was
equal to 6.458, and the MAE of the state-of-the-art was equal to 7.7496 which
is 20% higher than our MAE. Our aim is to find the best set of dilation rates
by using the Genetic Algorithm. We choose to limit the space of these
parameters from 2 to 5, we elevate the batch size from 1 to 8. We use bi-
linear interpolation in order to stack the tensors and their respective
targets in the same batch, and we reduce the number of epochs in each training
routine from 400 to 20. All of these measures linearly affected the
performance all the models, however, it is necessary to use them since we
intended to train 7 candidates per generation as shown by Fig. 6(b), where we
trained the best networks in each generation on 300 epochs and with batch-size
equal to one in order to compare the networks’ performance in optimal
conditions.

(a) MAE of the best performing networks in each generation (trained on 20
epochs).

(b) MAE rolling mean with a window size of 10 epochs of the best networks
trained on 300 epochs.

Figure 6: Genetic search output metrics.

From Fig. 6(a), we see that in the third generation, the algorithm converges
to a new candidate, and in the fourth generation it converges to the network
with the best performance. This is either because the mutations in later
generations are less effective, or that the network constructed in the fourth
generation is the best possible network based on the initial conditions.

##  IV Conclusion

In this paper, we proposed an-easier-to-train deep learning architecture that
achieves 20% lower MAE and 30 % convergence speed gain compared to state-of-
the-art techniques for mass gathering detection. We proved as well that the
use of the genetic algorithm was an efficient method to tune the hyper-
parameter configuration via evolutionary search methods in order to find more
effective networks. Moving forward, we will consider the applications of
genetic algorithms to tune the learning rate, along with the remaining hyper-
parameters.

## References

  * [1] P. Dollar, C. Wojek, B. Schiele, and P. Perona, “Pedestrian detection: An evaluation of the state of the art,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 34, no. 4, pp. 743–761, 2011.
  * [2] H. Idrees, I. Saleemi, C. Seibert, and M. Shah, “Multi-source multi-scale counting in extremely dense crowd images,” in IEEE conference on computer vision and pattern recognition, pp. 2547–2554, 2013.
  * [3] V. Lempitsky and A. Zisserman, “Learning to count objects in images,” in Advances in neural information processing systems, pp. 1324–1332, 2010.
  * [4] V.-Q. Pham, T. Kozakaya, O. Yamaguchi, and R. Okada, “Count forest: Co-voting uncertain number of targets using random forest for crowd density estimation,” in IEEE International Conference on Computer Vision, 2015\.
  * [5] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” arXiv preprint arXiv:1409.1556, 2014.
  * [6] Y. Zhang, D. Zhou, S. Chen, S. Gao, and Y. Ma, “Single-image crowd counting via multi-column convolutional neural network,” in IEEE conference on computer vision and pattern recognition, 2016.
  * [7] L. Boominathan, S. S. Kruthiventi, and R. V. Babu, “Crowdnet: A deep convolutional network for dense crowd counting,” in ACM international conference on Multimedia, pp. 640–644, 2016.
  * [8] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in IEEE conference on computer vision and pattern recognition, pp. 248–255, 2009.
  * [9] Y. Li, X. Zhang, and D. Chen, “Csrnet: Dilated convolutional neural networks for understanding the highly congested scenes,” in IEEE conference on computer vision and pattern recognition, 2018.