# The space of immersed polygons

Maxime Fortier Bourque  Département de mathématiques et de statistique,
Université de Montréal, 2920, chemin de la Tour, Montréal (QC), H3T 1J4,
Canada<EMAIL_ADDRESS>
###### Abstract.

We use the Schwarz–Christoffel formula to show that for every $n\geq 3$, the
space of labelled immersed $n$-gons in the plane up to similarity is
homeomorphic to ${\mathbb{R}}^{2n-4}$. We then prove that all immersed
triangles, quadrilaterals, and pentagons are embedded, from which it follows
that the space of labelled simple $n$-gons up to similarity is homeomorphic to
${\mathbb{R}}^{2n-4}$ if $n\in\\{3,4,5\\}$. This was first shown by Gonzáles
and López-López for $n=4$ and conjectured to be true for every $n\geq 5$ by
González and Sedano-Mendoza.

##  1\. Introduction

An _immersed polygon_ in the plane is a closed polygonal curve
$\phi:S^{1}\to{\mathbb{C}}$ (considered up to orientation-preserving
reparametrization) which extends to an orientation-preserving local
homeomorphism $f:\overline{{\mathbb{D}}}\to{\mathbb{C}}$. An immersed polygon
$\phi$ is _labelled_ if we choose distinct points $z_{1},\ldots,z_{n}\in
S^{1}$ in counter-clockwise order such that $\phi$ maps each component of
$S^{1}\setminus\\{z_{1},\ldots,z_{n}\\}$ to the interior of a straight line
segment. The images $w_{j}=\phi(z_{j})$ (some of which may coincide) are the
_vertices_ of the immersed polygon. At each vertex $w_{j}$, the _interior
angle_ is the clockwise angle $\angle w_{j-1}w_{j}w_{j+1}\in(0,2\pi)$, where
indices are taken modulo $n$.

Figure 1. An immersed hexagon.

Since the vertices of a labelled immersed polygon determine the map $\phi$ up
to reparametrization, the set $\operatorname{LIP}(n)$ of labelled immersed
$n$-gons can be identified with a subset of ${\mathbb{C}}^{n}$, which induces
a topology on $\operatorname{LIP}(n)$. With this topology, the group

$\operatorname{Aff}({\mathbb{C}})=\\{z\mapsto
az+b:a\in{\mathbb{C}}\setminus\\{0\\},b\in{\mathbb{C}}\\}$

of complex affine transformations (or, equivalently, of orientation-preserving
similarities of ${\mathbb{C}}$) acts on $\operatorname{LIP}(n)$ by
homeomorphisms.

The goal of this note is to show that the quotient space
$\operatorname{LIP}(n)/\operatorname{Aff}({\mathbb{C}})$ is homeomorphic to
${\mathbb{R}}^{2n-4}$.

######  Theorem 1.1.

For every $n\geq 3$, the quotient of the space $\operatorname{LIP}(n)$ of
labelled immersed $n$-gons in the plane by the action of the group
$\operatorname{Aff}({\mathbb{C}})$ is homeomorphic to ${\mathbb{R}}^{2n-4}$.

The proof is based on the Schwarz–Christoffel formula in complex analysis. It
shows that $\operatorname{LIP}(n)/\operatorname{Aff}({\mathbb{C}})$ is a
trivial ${\mathbb{R}}^{n-1}$-bundle (with fibers parametrized by the interior
angles) over the Teichmüller space of closed disks with $n$ marked points on
the boundary, itself homeomorphic to ${\mathbb{R}}^{n-3}$.

We then prove that for $n\in\\{3,4,5\\}$, all immersed $n$-gons are simple
(i.e., embedded), which has the following consequence.

######  Corollary 1.2.

For every $n\in\\{3,4,5\\}$, the quotient of the space $\operatorname{LSP}(n)$
of simple $n$-gons in the plane (with vertices labelled in counter-clockwise
order) by the action of the group $\operatorname{Aff}({\mathbb{C}})$ is
homeomorphic to ${\mathbb{R}}^{2n-4}$.

For $n=3$, this result is well-known (see e.g. [Bae24]) and elementary. Here
is a proof: the map that sends a triangle with counter-clockwise vertices
$w_{1}$, $w_{2}$, $w_{3}$ to

$\frac{w_{3}-w_{1}}{w_{2}-w_{1}}$

induces a homeomorphism from
$\operatorname{LSP}(3)/\operatorname{Aff}({\mathbb{C}})$ to the upper half-
plane ${\mathbb{H}}$, which is homeomorphic to ${\mathbb{R}}^{2}$ via the map
$x+iy\mapsto(x,\log y)$. For $n=4$, the result was first proved in [GLL16] and
then again in [GSM23] with different methods. In [GSM23], González and Sedano-
Mendoza conjectured that the result holds for every $n\geq 5$ as well. The
above corollary settles the case $n=5$ and reproves the previous cases in a
unified way. For general $n\geq 3$, it is known that
$\operatorname{LSP}(n)/\operatorname{Aff}({\mathbb{C}})$ is simply-connected
[Gon18, Theorem 3.2].

### Relation to other work

Various other moduli spaces of planar polygons have been studied in the
literature before, such as those of polygons with fixed side lengths (known as
_polygonal linkages_) [Hau91, KM95, KT99, CDR03, SW14] or with fixed interior
angles [BG92, KY93]. The former moduli spaces can be quite complicated
topologically, while the latter can be parametrized by interiors of convex
hyperbolic polyhedra (hence are cells) if all interior angles are in
$(0,\pi)$.

The works [CDR03] and [SW14] in particular study simple polygons with fixed
side lengths. Some of their results can be restated as follows. Given positive
real numbers $\ell_{1},\ldots,\ell_{n}$ such that $\ell_{j}<\sum_{k\neq
j}\ell_{k}$ for every $j$, the subset $X(\ell)$ of polygons in
$\operatorname{LSP}(n)/\operatorname{Aff}({\mathbb{C}})$ whose vector of side
lengths is a constant multiple of $\ell=(\ell_{1},\ldots,\ell_{n})$ is
contractible [CDR03, Corollary 3]. If furthermore the $\ell_{j}$ cannot
partitioned into two sets with the same sum, then $X(\ell)$ is homeomorphic to
${\mathbb{R}}^{n-3}$ [SW14, Theorem 7]. If the additionnal hypothesis on
subsets with equal sums could be removed in this result of Shimamoto–Wooters,
then the conjecture of González and Sedano-Mendoza would follow, since the set
of realizable vectors of side lengths up to scaling is homeomorphic to
${\mathbb{R}}^{n-1}$, and a fiber bundle over a contractible base is always
trivial.

This is all to say that the statement of Corollary 1.2 is likely to be true
for every $n\geq 3$ even though that cannot be deduced from Theorem 1.1.

##  2\. Schwarz–Christoffel tranformations

We will work with the closed upper half-plane

$\overline{{\mathbb{H}}}={\mathbb{H}}\cup{\mathbb{R}}\cup\\{\infty\\}$

instead of the closed unit disk.

Let $n\geq 3$. Given prevertices $z_{1}<z_{2}<\cdots<z_{n-1}$ in
${\mathbb{R}}$ and $z_{n}=\infty$, parameters
$\alpha_{1},\ldots,\alpha_{n}\in(0,2)$ such that

(2.1) $\sum_{j=1}^{n}\alpha_{j}=n-2,$

and constants $A\in{\mathbb{C}}\setminus\\{0\\}$, $B\in{\mathbb{C}}$, the
corresponding _Schwarz–Christoffel transformation_
$F:\overline{{\mathbb{H}}}\to{\mathbb{C}}$ is defined by the formula

(2.2) $F(z):=A\int_{[i,z]}\prod_{j=1}^{n-1}(\zeta-
z_{j})^{\alpha_{j}-1}\,d\zeta+B,$

where $[i,z]$ denotes the straight line segment from the imaginary unit $i$ to
$z$, and the powers $(\zeta-z_{j})^{\alpha_{j}-1}:=\exp((\alpha_{j}-1)L(\zeta-
z_{j}))$ are defined using the branch $L$ of the logarithm in
$\overline{{\mathbb{H}}}\setminus\\{0\\}$ that coincides with the usual
logarithm on $(0,\infty)$. The main result concerning these maps can be
summarized as follows [Chr67, Sch69].

######  Theorem 2.1 (Schwarz, Christoffel).

For any choice of parameters as above, the Schwarz–Christoffel transformation
$F$ is a local homeomorphism, holomorphic in ${\mathbb{H}}$, whose restriction
to ${\mathbb{R}}\cup\\{\infty\\}$ is an immersed $n$-gon in ${\mathbb{C}}$
with interior angle $\alpha_{j}\pi$ at vertex $F(z_{j})$ for every
$j\in\\{1,\ldots,n\\}$. The resulting polygon is simple if and only if $F$ is
injective. Conversely, any immersed $n$-gon in ${\mathbb{C}}$ arises as the
restriction to ${\mathbb{R}}\cup\\{\infty\\}$ of a Schwarz–Christoffel
transformation, unique up to pre-composition by an affine map $z\mapsto az+b$
with $a>0$ and $b\in{\mathbb{R}}$.

While the last part of the theorem is usually stated for simple polygons,
essentially the same proof works in the immersed case. The only minor
difference is that one needs to use the uniformization theorem instead of the
Riemann mapping theorem (the extension $f$ of an immersed polygon $\phi$ can
be made holomorphic by pulling back the complex structure from the complex
plane). Christoffel [Chr70] even proved a version of the theorem for branched
covers, in which case there are more terms in the integrand to account for the
branch points. See [DT02] and the references therein for various
generalizations of the Schwarz–Christoffel formula.

We will need another well-known fact, namely, that the map $F$ and the
resulting immersed polygon depend continuously on the parameters
$z_{1},\ldots,z_{n-1}$, $\alpha_{1},\ldots,\alpha_{n}$, and $A$,$B$. This is
because away from the prevertices, the integrand depends uniformly
continuously on the parameters, and the contribution near the prevertices can
be controlled locally uniformly.

We will say that a Schwarz–Christoffel transformation $F$ is _normalized_ if
its prevertices satisfy $z_{1}=-1$ and $z_{2}=0$ in addition to
$z_{n}=\infty$, which determines $F$ uniquely for a given immersed polygon. It
is known that the normalized Schwarz–Christoffel transformation $F$ and its
remaining parameters depend continuously on the immersed polygon, just like
normalized Riemann maps depend continuously on the domain. This can be shown
using a normal families argument and the uniqueness of the normalized map.

Given an immersed polygon $\phi$, finding the correct parameters for the
corresponding normalized Schwarz–Christoffel transformation is known as the
_parameter problem_ , which has been studied extensively (see e.g. [DT02]).

##  3\. The homeomorphism

We now use the above properties of Schwarz–Christoffel transformations to
prove Theorem 1.1. Let

${\mathcal{Z}}:=\left\\{(z_{3},\ldots,z_{n-1})\in{\mathbb{R}}^{n-3}:0<z_{3}<\cdots<z_{n-1}\right\\}$

and

${\mathcal{A}}:=\left\\{(\alpha_{1},\ldots,\alpha_{n})\in(0,2)^{n}:\sum_{j=1}^{n}\alpha_{j}=n-2\right\\}.$

We define a map

$\Phi:{\mathcal{Z}}\times{\mathcal{A}}\to\operatorname{LIP}(n)$

as follows. Given $(z_{3},\ldots,z_{n-1})\in{\mathcal{Z}}$ and
$(\alpha_{1},\ldots,\alpha_{n})\in{\mathcal{A}}$, we add the prevertices
$z_{1}=-1$, $z_{2}=0$, $z_{n}=\infty$, and let $F$ be the corresponding
Schwarz–Christoffel transformation with remaining parameters $A=1$ and $B=0$.
We then set

$\Phi((z_{3},\ldots,z_{n-1}),(\alpha_{1},\ldots,\alpha_{n})):=F|_{{\mathbb{R}}\cup\\{\infty\\}}.$

By the continuous dependence of Schwarz–Christoffel transformations upon
parameters, the map $\Phi$ is continuous.

We can also define a map

$\Psi:\operatorname{LIP}(n)\to{\mathcal{Z}}\times{\mathcal{A}}$

in the other direction as follows. For an immersed $n$-gon
$\phi\in\operatorname{LIP}(n)$, let

$z_{1}=-1<z_{2}=0<z_{3}<\cdots<z_{n-1}<z_{n}=\infty,$

$\alpha_{1},\ldots,\alpha_{n}\in(0,2)$, and
$A\in{\mathbb{C}}\setminus\\{0\\}$, $B\in{\mathbb{C}}$ be the unique
parameters such that the boundary values of the corresponding
Schwarz–Christoffel transformation coincide with $\phi$ up to
reparametrization. We then set

$\Psi(\phi)=((z_{3},\ldots,z_{n-1}),(\alpha_{1},\ldots,\alpha_{n})),$

which is continuous.

By definition, it is clear that $\Psi\circ\Phi=\mathrm{id}$. However,
$\Phi\circ\Psi$ might not give back the original immersed polygon because of
our specific choice of $A$ and $B$. On the other hand, this problem goes away
if we quotient out by $\operatorname{Aff}({\mathbb{C}})$.

Indeed, observe that if we post-compose an immersed polygon $\phi$ with an
orientation-preserving similarity $h$, then the normalized Schwarz-Christoffel
transformation for $h\circ\phi$ is $h\circ F$, which has the same parameters
as $F$ except for the constants $A$ and $B$. In other words,
$\Psi(h\circ\phi)=\Psi(\phi)$, so $\Psi$ descends to a function (which we
denote by $\widetilde{\Psi}$) on the quotient space
$\operatorname{LIP}(n)/\operatorname{Aff}({\mathbb{C}})$. Let us also denote
by $\widetilde{\Phi}$ the map $\Phi$ post-composed with the quotient map
$\operatorname{LIP}(n)\to\operatorname{LIP}(n)/\operatorname{Aff}({\mathbb{C}})$.

We evidently still have $\widetilde{\Psi}\circ\widetilde{\Phi}=\mathrm{id}$
and we now have $\widetilde{\Phi}\circ\widetilde{\Psi}=\mathrm{id}$ as well.
Indeed, if $\phi\in\operatorname{LIP}(n)$ is the restriction of a normalized
Schwarz–Christoffel transformation $F$ with constants $A$ and $B$ to
${\mathbb{R}}\cup\\{\infty\\}$, then by definition

$\Phi(\Psi(\phi))=(A^{-1}(F-B))|_{{\mathbb{R}}\cup\\{\infty\\}}=A^{-1}(\phi-B)\in\operatorname{Aff}({\mathbb{C}})\circ\phi$

and hence
$\widetilde{\Phi}(\widetilde{\Psi}([\phi]))=\widetilde{\Phi}(\Psi(\phi))=[\phi]$
in $\operatorname{LIP}(n)/\operatorname{Aff}({\mathbb{C}})$.

We have established that
$\widetilde{\Psi}:\operatorname{LIP}(n)/\operatorname{Aff}({\mathbb{C}})\to{\mathcal{Z}}\times{\mathcal{A}}$
is a continuous bijection with continuous inverse. It only remains to show
that ${\mathcal{Z}}\times{\mathcal{A}}$ is homeomorphic to
${\mathbb{R}}^{2n-4}$, which is elementary.

Firstly, the map

$\begin{array}[]{rcl}{\mathcal{Z}}&\to&{\mathbb{R}}^{n-3}\\\
(z_{3},z_{4},\ldots,z_{n-1})&\mapsto&\left(\log(z_{3}),\log(z_{4}-z_{3}),\ldots,\log(z_{n-1}-z_{n-2})\right)\end{array}$

is clearly a homeomorphism.

Secondly, observe that ${\mathcal{A}}$ is a convex relatively open set in the
hyperplane ${\mathcal{H}}\subset{\mathbb{R}}^{n}$ defined by the equation
$\sum_{j=1}^{n}\alpha_{j}=n-2$. We have that
${\mathcal{H}}\cong{\mathbb{R}}^{n-1}$ and it is well-known that any convex
open set $U$ in ${\mathbb{R}}^{m}$ is homeomorphic to ${\mathbb{R}}^{m}$
itself. Indeed, one may define a form of polar coordinates with respect to any
point in $U$. It follows that ${\mathcal{A}}$ is homeomorphic to
${\mathbb{R}}^{n-1}$, and hence

${\mathcal{Z}}\times{\mathcal{A}}\cong{\mathbb{R}}^{n-3}\times{\mathbb{R}}^{n-1}={\mathbb{R}}^{2n-4}.$

This completes the proof of Theorem 1.1.

##  4\. Embedded polygons

In this section, we show that when $n$ is at most $5$, an immersed $n$-gon is
automatically embedded.

######  Lemma 4.1.

If $3\leq n\leq 5$, then any immersed $n$-gon in the plane is simple.

###### Proof.

Let $\phi$ be an immersed $n$-gon which is not simple. We can perturb $\phi$
to a nearby non-simple immersed polygon $\psi$ where all self-intersections
happen away from the vertices and are transverse. Since $\psi$ is not simple,
there is some point $p$ in the complement of its image such that the winding
number of $\psi$ around $p$ is at least $2$. Indeed, winding numbers are non-
negative for immersed polygons and the winding number always takes 3 distinct
values around a transverse intersection point. We can further assume that $p$
does not lie on any of the lines that contain the sides of $\psi$.

Observe that each side of $\psi$ contributes strictly less than $1/2$ to the
winding number around $p$ because it spans an angle strictly less than $\pi$
as seen from $p$. It follows that $n>4$.

Suppose that $n=5$. Then each side of $\psi$ must be oriented to the left with
respect to $p$, otherwise the winding number would be strictly less than
$2=4\cdot\frac{1}{2}$ due to the negative contributions. Let us form triangles
with $p$ and each side of $\psi$. Then the sum of the angles $\gamma_{k}$ of
these triangles at the point $p$ is equal to $2\pi k$ where $k\geq 2$ is the
winding number of $\psi$ around $p$. On the other hand, by adding all the
interior angles of these triangles, we find that

$\sum_{k=1}^{n}\gamma_{k}=\sum_{j=1}^{n}\pi-\theta_{j}$

where the $\theta_{j}$ are the interior angles of the polygon $\psi$. This
last sum is the sum of the counter-clockwise turning angles of $\psi$ at the
vertices, which always equals $2\pi$ for an immersed polygon. Indeed, the sum
of the interior angles of an immersed polygon is $(n-2)\pi$ by Equation (2.1)
and Theorem 2.1. This is a contradiction, from which we conclude that $n\geq
6$. ∎

Observe that the statement of the lemma is false for $n=6$, as illustrated in
Figure 1. Also note that the Schwarz–Christoffel formula makes sense if some
of the “interior angles” $\theta_{j}=\alpha_{j}\pi$ are allowed to be larger
than or equal to $2\pi$, but in that case the resulting map is no longer
locally injective at the corresponding prevertices. Figure 2 shows that the
analogue of Lemma 4.1 for such maps fails for $n=5$, so the restriction
$\alpha_{j}\in(0,2)$ is crucial for our purposes. The part of the proof that
breaks down without this restriction is that at a vertex $w_{j}$ with
“interior angle” $\theta_{j}>2\pi$, the turning angle is $3\pi-\theta_{j}$
rather than $\pi-\theta_{j}$.

Figure 2. A pentagon which fails to be immersed at one vertex.

We conclude by observing that Corollary 1.2 follows immediately from Theorem
1.1 and Lemma 4.1.

## References

  * [Bae24] J. C. Baez, _The moduli space of acute triangles_ , Notices Amer. Math. Soc. 71 (2024), no. 5, 664–665.
  * [BG92] C. Bavard and É. Ghys, _Polygones du plan et polyèdres hyperboliques_ , Geom. Dedicata 43 (1992), no. 2, 207–224.
  * [CDR03] R. Connelly, E. D. Demaine, and G. Rote, _Straightening polygonal arcs and convexifying polygonal cycles_ , Discrete Comput. Geom. 30 (2003), no. 2, 205–239.
  * [Chr67] E. B. Christoffel, _Sul problema delle temperature stazionarie e la rappresentazione di una data superficie_ , Ann. Mat. Pura Appl. Serie II 1 (1867), 89–103.
  * [Chr70] by same author, _Ueber die Abbildung einer n-blattrigen einfach zusammenhängender ebenen Fläche auf einen Kreise_ , Göttingen Nachrichten, (1870), 359–369.
  * [DT02] T. A. Driscoll and L. N. Trefethen, _Schwarz-Christoffel mapping_ , Cambridge Monographs on Applied and Computational Mathematics, vol. 8, Cambridge University Press, Cambridge, 2002.
  * [GLL16] A. González and J. L. López-López, _Compactness of spaces of convex and simple quadrilaterals_ , Bull. Aust. Math. Soc. 94 (2016), no. 3, 507–521.
  * [Gon18] A. González, _Fundamental group of spaces of simple polygons_ , Rocky Mountain J. Math. 48 (2018), no. 6, 1871–1886.
  * [GSM23] A. González and M. Sedano-Mendoza, _Moduli space of simple polygons_ , preprint, arXiv:2303.15406, 2023.
  * [Hau91] J.-C. Hausmann, _Sur la topologie des bras articulés_ , Algebraic topology Poznań 1989, Lecture Notes in Math., vol. 1474, Springer, Berlin, 1991, pp. 146–159.
  * [KM95] M. Kapovich and J. Millson, _On the moduli space of polygons in the Euclidean plane_ , J. Differential Geom. 42 (1995), no. 2, 430–464.
  * [KT99] Y. Kamiyama and M. Tezuka, _Topology and geometry of equilateral polygon linkages in the Euclidean plane_ , Quart. J. Math. Oxford Ser. (2) 50 (1999), no. 200, 463–470.
  * [KY93] S. Kojima and Y. Yamashita, _Shapes of stars_ , Proc. Amer. Math. Soc. 117 (1993), no. 3, 845–851.
  * [Sch69] H. A. Schwarz, _Ueber einige Abbildungsaufgaben_ , J. Reine Angew. Math. 70 (1869), 105–120.
  * [SW14] D. Shimamoto and M. Wootters, _Configuration spaces of convex and embedded polygons in the plane_ , Geom. Dedicata 172 (2014), 121–134.


# A Perception Centred Self-driving System without HD Maps

Alan Sun
<EMAIL_ADDRESS>
Abstract

Building a fully autonomous self-driving system has been discussed for more
than 20 years yet remains unsolved. Previous systems have limited ability to
scale. Their localization subsystem needs labor-intensive map recording for
running in a new area, and the accuracy decreases after the changes occur in
the environment. In this paper, a new localization method is proposed to solve
the scalability problems, with a new method for detecting and making sense of
diverse traffic lines. Like the way human drives, a self-driving system should
not rely on an exact position to travel in most scenarios. As a result,
without HD Maps, GPS or IMU, the proposed localization subsystem relies only
on detecting driving-related features around (like lane lines, stop lines, and
merging lane lines). For spotting and reasoning all these features, a new line
detector is proposed and tested against multiple datasets.

##  1 Introduction

Ziegler’s system [1] can drive full-autonomously over 100 kilometers without
any interruptions in 2014. Despite these early achievements, the industry
leaders are still struggling to pass the necessary tests according to [2].
Obviously, we need to inspect why the current self-driving system is hard to
implement and widely used. Current systems rely on HD Maps to produce
centimeter-level accuracy of position. Readers are referred to [3] for more
about typical system architecture. The big question is that do we really need
accurate positions?

Human drivers make driving decisions based on what they see. They make sense
of the environment around and decide when to turn or keep the current driving
direction. They cannot mark the exact position of themselves on a map, but
they know how to travel through a complicated intersection based on the
knowledge of which way they should take. Likewise, can we build a self-driving
system without accurate locations?

In this paper, a new perception centered self-driving system is proposed and
discussed in two driving scenarios: the cruising scenario and the turning
scenario. The cruising scenario is when the vehicle cruises on parallel lanes.
The turning scenario is when the vehicle drives through free spaces (defined
as the drivable area outside of lanes, like intersections or parking area).

The proposed system comes with several advantages in these two scenarios.
Firstly, it does not rely on HD Maps. So it is easy to scale without recording
new HD Maps. Secondly, the proposed feature detection method is not based on
any specialized end-to-end deep learning solutions. Hence it is easy to debug
and visualize. Also, it does not need additional time-consuming training
process for scaling. Lastly, it performs more robustly with a severely changed
environment (like seasons, weather or lighting condition).

Just like the human drivers, the system only involves with related visual
features (defined as traffic features, including traffic lines, traffic lights
and traffic signs). The workflow of the detection and localization subsystem
is shown in Figure 1. In the cruising scenario, we only need to finish the
first step, including 1.1 and 1.2. In the turning scenario, we need to finish
all four steps. Note that the vehicle position from the localization subsystem
is based on the rebuilt scene rather than a global map. The localization
subsystem also projects the rebuilt scene onto a digital map (like Google Map)
to provide navigation instructions while crossing free spaces. The navigation
instruction leads the car to travel from one exit to the target entrance of
the free space. The path planning system and control system also works on the
rebuilt scene. Hence they are map unrelated.

Figure 1: The workflow of the proposed perception centered system

The proposed system relies on traffic lines (including curbs) for tracking the
vehicle’s position. Hence, the lines detector is the priority. We need a
general lines detector for understanding complicated traffic lines on the
road. The experiment covers several types of lines, including lane lines, stop
lines, curbs, merging and splitting lines and intersections in a roundabout.
For the popular lane lines detection problem, the proposed new traffic lines
detector performs as good as other deep neural network supported approaches
leveraging the prior knowledge of lines position and angles with easy erosion
and clustering. This robust and straightforward method is then generalized and
successfully detected other kinds of lines as well. After that, the process of
localizing the position in the rebuilt scene will be discussed with examples
and limitations. In that example, the system requires neither GPS signals nor
IMU signals nor 3D HD Maps to locate the vehicle.

##  2 Related Work

What is a perception centred self-driving system? Most self-driving systems
are relying on a map-based localization subsystem. They are categorized as
localization centred systems because all other subsystems are working under
the map space from the localization subsystem. The perception centred system
uses a local scene, instead of a global map, as the working space for all
other subsystems. Limited research have been done on this direction. One of
the exceptions is [4] by Bojarski from Nvidia. In this work, they tried to
build an end-to-end system from camera images to control signals with the help
of augmented learning. It is also map-unrelated. However, this system only
works for minimal lane-keeping tasks in the cruising scenario. It is not
compatible to work with other subsystems, and the scalability is not tested
for more sophisticated roads or sensor settings.

###  2.1 Localization

For most localization centred systems, all decision making and path planning
are based on a centimetre level localization accuracy from their localization
subsystem. Using GPS, with the aid of IMU, is a popular solution and provides
accuracy better than 20 centimetres with SLAM over an HD Map [5]. The problem
of GPS is that the signals are not always available, and the result tends to
drift accidentally. For quite a long time, SLAM is considered as the key to
solving the localization problem for self-driving cars. The SLAM algorithm
uses visual features stored in the HD Map to match features extracted from the
live camera on the self-driving cars. Visual features are usually organized as
bags of features (BoF) in the descriptor space. Without HD Maps or IMU,
researchers can hardly reach the centimetres level accuracy like [6] and [7].

However, two problems of the SLAM based localization approach are tricky to
solve. Firstly, the performance decreases once the environment changes. Light
angle changes might cause different shadow shapes and season changes cause
massive appearance changes on the trees and grass. These changes yield new
visual features which cannot be matched with the recorded ones on the HD Map.
This problem requires routine labour-intensive map recording once after the
changes occur. Secondly, the localization result tends to drift after a long-
range driving, and the error will accumulate with growing driven distance, as
discussed in [5]. The intrinsic reason of these problems is that the original
SLAM algorithm is designed for indoor localization problems where dramatic
environment changes or long-distance moving is not considered. Hence these
problems are hard to eliminate.

Recent researchers, like Ma [8], started to use as less visual features as
possible for localization. Besides saving the storage for the BoF of these
features, using fewer features decrease the risk of being affected by the
environment changes [9].

This trend brings the idea of using minimal features for localization. The
LaneLoc system proposed by Schreiber [10] tried to use the exact appearance of
lane markings for matching from pre-recorded maps. This approach could be seen
as counting the number of dashed fragments the vehicle travelled to localize
the car itself. This approach still has several limitations. Firstly, it will
not work on a solid line situation and ends up with only relying on IMU
without any visual aids. Secondly, the exact appearance will eventually change
one day in the future. Think about the time when those dashed lines were
repainted or worn out, which are both prevalent cases. Thirdly, the
performance is very fragile. Slight turbulence, like occlusions or heavy
shadows, will make the system omit one or more fragments and yield a steady
error as a result. Lastly, the labelling process is both complicated and hard
to finish accurately, as discussed by Schreiber in their paper. Our proposed
system solved these limitations by abstracting line features further to types
and directions by the proposed lines detector.

###  2.2 Traffic Line Detection

The traffic line detection, or the lane detection which is a narrower problem,
was the essence of many early driving assistant systems [11] like Lane
Departure Warning System (LDWS) and Lane Keeping Assist System (LKAS). Many
researchers, like Kim [12], used Convolutional Neural Network (CNN) to reduce
noise and get the segmentation of the markings of those lines. Wang [13] used
shape extracted from OpenStreetMap (OSM) as prior knowledge to help detect the
lanes. Some problems remain for the CNN supported approaches.

Firstly, they still can not solve the long-tail challenging situations because
CNNs heavily relies on the distribution of the training dataset. As a result,
CNN generally works terribly in rare situations. Secondly, the segmentation
result of the CNN approaches often cause blurry edges when it is not confident
about the prediction. These blurry edges come with difficulty for the
following algorithms when they try to form a line from these ambiguous pixels.
Lastly, CNNs are significantly dataset related. They tend to work well only on
the dataset they have been trained on [14]. This limitation is because that
different datasets and sensor settings tend to create distinctive patterns of
noise in the images. For example, in the KITTI dataset [15], the same line
marks show different appearances in different locations under the BEV space.
Lines far from the camera shows clear artifacts caused by the BEV
transformation. The self-driving related datasets are often covering just one
type of the available camera settings. A vast and comprehensive dataset like
MS-COCO [16] for the object detection task does not exist for now.

As a result, CNN was not used for lines detection in this paper. The proposed
lines detector leverages the lines information from a topology map, similar to
what Wang did in [13] from the OSM, as prior knowledge to help. The proposed
lines detector separates different line types to boost the performance even
more by using different lines detector for each type of lines (solid or dashed
lines, straight or curved lines). It also used a sliding window to detect and
connect traffic lines, similar to what Tsai did in [17]. The sliding window
approach is proved to be both robust and easy to visualize for debugging.

##  3 System Design

The overall workflow is shown in Figure 1. In the cruising scenario, the
detection subsystem will finish the part 1.1 and 1.2 to give the current lane
number of the vehicle, and that is enough for generating a driving path and
control signal without involving the localization system at all. However, the
detection system needs to continuously detect the traffic features for the
next traffic part (could be another lane ahead or a free space connected with
an exit). The order of the series of traffic features are based on the
topology map.

The topological map, being used as the descriptor space for matching with the
digital map and the rebuilt scene, is the centre and the relationship is shown
in Figure 2. The topology map should be drawn before the system can run on a
new area. The topology map also provides lane information helping lines
detection as prior knowledge and helps the vehicle to change to a preferred
lane in advance. The topology map contains the following information:

  * •

Lanes information: (1) the lines information on both sides (like straight
yellow lines on the left and straight curb on the right), (2) ending
information (like ends with a stop line or merges with other lanes on the
left), (3) direction information (like starting direction, turning angle
limitation for each window), (4) neighbour lanes used for lane changing while
cruising, (5) connected entrance and exit numbers, (6) traffic rules metadata
(like speed limits), (7) status (like normal, under maintenance or closed
under specific time windows)

  * •

Entrance and exit: (1) position, (2) direction, (3) the relationship (an N to
N relationship) with each other.

  * •

Free spaces: (1) detectable traffic features used for localization (including
stop lines, crosswalk lines, traffic lights, traffic signs, lines of adjacent
lanes) and their relative position in a real-world scale, (2) adjacent
entrance and exit numbers, (3) traffic rules (like speed limits), (4) status

Figure 2: The left is a digital map used for navigation, the middle is the
topology map, the right is the rebuilt scene

###  3.1 Matching digital map with topology map for navigation

Each turning point on the digital map is used for finding a nearest entrance-
exit pair which have the correlated directions. Define
$\boldsymbol{T}=\left\\{(\lambda_{t},\phi_{t}),\alpha_{t},\beta_{t}\right\\}$
as the set of all turning points on the digital map, where $\lambda_{t}$ and
$\varphi_{t}$ is the latitude and longitude of turning point $t$, $\alpha_{t}$
is the direction before the turning and $\beta_{t}$ is the direction after the
turning.
$\boldsymbol{D}_{in}=\left\\{(\lambda_{d},\phi_{d}),\beta_{d}\right\\}$ and
$\boldsymbol{D}_{out}=\left\\{(\lambda_{d},\phi_{d}),\alpha_{d}\right\\}$ are
the set of all entry points and all exit points. The score function f is the
multiplication of g and h, as equation 1, where g is the Euclidean distance
between two points and h is the difference of two angles, defined as
$g=\left\|d_{in},t\right\|+\left\|d_{out},t\right\|$ and
$h=\left|\alpha_{t},\alpha_{in}\right|+\left|\beta_{t},\beta_{out}\right|$.
The $\boldsymbol{P}=\left\\{(d_{in},d_{out})\right\\}$ is the set of all legal
pairs of entrance and exits. All legal pairs should connect with a same free
space and follow the traffic law. For example, the exit on the end of a right
turning lane cannot pair with the entrance ahead with the same direction. The
optimal pair for a minimal f score is the matched result with the condition of
$(d_{in}^{*},d_{out}^{*})\in\boldsymbol{P}$. This method assumes the turning
point on the digital map is the center point of the target exit and the target
entrance.

$\displaystyle f(d_{in},d_{out},t)=g(d_{in},d_{out},t)*h(d_{in},d_{out},t)$
(1)

The data of $\boldsymbol{P}$ and $\boldsymbol{D}$ are manually initialized as
part of the topology map. These data usually do not need to be changed unless
the traffic features are changed. For example, an intersection was updated
with an additional right changing lane or new construction on the road updated
the lane changing rules temporarily. The maintenance of the topology map is
easy, fast since we only need to change the lane data in the sets of
$\boldsymbol{P}$ and $\boldsymbol{D}$.

###  3.2 Matching topology map with perception scene for localization

Lanes form two kinds of lane sets: driving lane sets and detectable lane sets.
The driving lane sets provide information about lane changing behaviour and
traffic laws, like speed limits. Two examples of driving lane sets are
illustrated in Figure 3. The vehicle can change to other lanes within the same
driving lane set. The target lane and original lane information will be passed
towards other following subsystems to act and finish the changing maneuver
while lane changing.

Figure 3: An illustration of lane sets under two different situations
overlapping on a satellite map, the left is on highway exit, the right is a
complicated lane topology near a roundabout, the red and green arrows
represent entrances and exits of those lanes

The detectable lane sets provide information about how to detect these lanes.
Lanes with either the same travelling direction or opposite ones can be
grouped into the same set. Each detectable lane sets has left and right line
types, lane width (used as detection aid, but restrictions), dashed line
intervals, suggested detection window size and other metadata which can be
added at one’s convenience. A detectable lane set must have at least two sides
of lines information used for tracking lanes. The lane width follows the
priority of (1) the width between two detected lines, (2) the width of other
detected lanes within the same detectable lane sets, (3) equally divided width
if two lines (probably are curbs) of the whole set are detected, (4) the
default lane width of the detectable lane sets. For example:

  * •

When there are two lanes travelling in opposite directions, and there is no
middle line to separate these two lanes, if both sides are detected, the space
in between will be divided by two for the width of each lane. If the vehicle
only detected the right side (assume under right-hand driving condition), the
lane width for the current lane is the default lane width of the lane set.

  * •

When there are four lanes travelling in opposite directions by two groups of
two lanes, the middle line is a solid line, and the line between two same
direction lanes is a dashed line. The number one lane (counting from the
right) is the space between the curb and the dashed line, and the number two
lane is the space between the middle solid line and the dashed line. If the
vehicle cannot detect the curb to get the lane width of lane number one, the
width of number two will be used for the width of lane number one.

For the cruising driving scenario, we care about two questions: (1) which lane
set we are in (to prepare for the next exit) and (2) which is the ego lane
from the lane set. For these two questions, the system relies on either
initializing the lane number at the beginning of the currently running period
or initializing the lane number after driving through a free space through a
specific entrance. The detection system verifies and corrects the current lane
set and lane number by matching detected types of lane lines with the ones
from the topology map. The detection system provides four line detectors for
each type of lines: (1) solid straight line, (2) solid curve, (3) dashed
straight line, (4) dashed curve. In the remainder of this paper, curbs are
considered as the same as traffic lines without further clearance.

The changes of the types of lane lines usually represent an end of the current
lane. If is possible that there will be multiple types of lines in one side of
a lane, the system uses the detector for the highest level type, because they
are more complicated and can handle the task of detecting low-level types.
These levels (one is the highest level and four is the lowest) are: (1) Dashed
curves, (2) Solid curves, (3) Dashed straight lines, (4) Solid straight lines.

For the turning scenario, the detection subsystem only needs to detect one
pair of non-parallel lines to form an anchor to rebuild the scene. For
example, under the intersection scenario shown in Figure 4, the middle lane
line and the stop line are enough for a strong anchor to rebuild the scene
based on the given relative position from the topology map. The target
entrance on the right side can be predicted and used for path planning. Once
the vehicle has driven into the free space passing the stop line which will no
longer be detected, the stop line of the target lane will be detected and
provide a strong anchor to follow up. The starting point of the target lane
will form a weak anchor as additional clues for localization.

The detection of anchors might be effected by occlusions caused by other
objects on the road. In other situations, there is a chance when the vehicle
is crossing a large intersection, the vehicle will have no available anchor in
sight in some area. The target lane direction and the current drivable area,
as a backup, will aid the vehicle to finish the turning. The free space
situation ends with positive detection of the next detectable lane set. If
there are multiple lines parallel with each other nearby, the system assumes
the detected one is the nearest one based on the current lane level position.

The system needs to be initialized at the beginning of each run based on GPS
signals and the current driving direction from the gyroscope to tell the
system which lane the vehicle is on. The GPS signal does not need to be
centimetre-level accurate, and the detection subsystem will update the lane
number, relying on counting the line numbers between the vehicle and the
detected curbs.

Figure 4: How the vehicle locate itself using lines detection results. The
yellow triangle is a weak anchor and the red triangle is a strong anchor.

This paper does not cover behaviour decision among crossing lanes because this
can be considered as a separated and solved problem thanks to previous
research like [1]. This behaviour decision includes behaviours, like yielding
to vehicles coming out from other merging lanes. These rules are universal and
consistent.

###  3.3 General lines detector

The proposed lines detector in the detection subsystem can detect diverse
types of lines. The code for lane lines detection for the KITTI dataset can be
found on this repository. These types of lines were tested: (1) lane lines,
(2) curbs, (3) stop lines, (4) merging or splitting points of two lines (pair
of lines), (5) special lane lines or curbs (which are not parallel to the
current ego lane). The lines detection problem was dissected by tracing back
to the most significant visual feature of the lines, which is their long and
narrow appearance. A sliding window was used to follow possible lines. All
noise without this narrow feature was eliminated by applying these methods:

  * •

Region Restriction: The detection subsystem leverage a given prior knowledge
about the starting points to eliminate noise in unrelated regions. This
knowledge comes from either previous lines detection results or predicted by
the positive detection results of neighbour lines with given lane width from
the topology map. For dashed lines, the sliding window moves at a step size of
dash segment intervals given from the topology map to make sure optimal
detecting position for each segment. The system tolerates minor errors for
this interval distance. The more knowledge we know about the lines, the
smaller window for detection we can use. A smaller region of interest gives
better resilience for challenges, helps the segment normalize better and
speeds up the lines detection process.

  * •

Special Convolution Kernel: The system uses a special kernel, as shown in
Figure 5. This proposed kernel helps to produce a cleaner result in the Hough
space for the next steps with less noise. Also, this kernel is more friendly
for detecting curves, merging lines and splitting lines than the simple
vertical kernel.

  * •

Directional Erosion: The system uses a special directional erosion structuring
element to erode noise which is not spanning through a specific direction
($A\ominus B$, $A$ is the pixels in the window and $B$ is a 5 by 1 narrow
structuring element), as illustrated in Figure 6. The direction of the target
lines is given from the topology map. In a sliding window, the line segment
can be considered as a straight line. Sharp turning lines or circles will also
be eroded into small segments which will be filtered out. Though there are
some other more complicated ways to leverage the information of direction for
lines detection [18], the directional erosion is the simplest and it works.

  * •

Types of Lines: The system leverages prior knowledge of the types of the lines
to get a better performance. For curves in each detection window, the turning
angles are restricted to the thresholds, which is usually very small given
from the topology map. For straight lines, we can use a much narrower window
for detection. For dashed lines, the marks which are too long or too short
will be filtered out, as shown in Figure 7. The topology map gives the length
of segments of the dashed lines.

Figure 5: Four results for different convolution kernels. The first one is the
proposed one and the last one is a typical square edge detection kernel. The
result on the left is more smooth and cleaner than the ones on the right in
the noisy area. Figure 6: Directional erosion eliminates strong noise in the
red circles while detecting stop lines.

The proposed lines detector uses the Y channel from the YUV color channels
since it was proved to perform better by Lin in [19]. The system works on the
Bird-Eye-View (BEV) space since we can leverage the prior knowledge of those
lines without predicting the camera pose or estimating the vanishing point
(VP) [20]. More about the homography transformation from the camera image to a
BEV space with a given camera pose can be found in [21].

For the feature detection on the Hough space, a low-high-low kernel was widely
used by [22], [23] and [24]. I changed it to a low-middle-high kernel and then
mirror it to make the detection on the left and right side separately. So we
can detect merging and splitting points and their directions (merging from /
splitting to the left or the right) by comparing the lengths of these two
lines detection results. For example, at the place a line is splitting to the
right, the line detection from the right side will break coming with a shorter
length of the line than the left side, as shown in Figure 8. To separate
splitting and merging, two additional windows will be created facing upwards
and downwards. Positive result of lines in the upwards window means splitting
and positive result in the downwards window means merging.

Lastly, the procedure for stop lines detection is as follows. After the
detection of a window, if the line is broken in the upper end, two side
windows will be created. A horizontal line detection, using horizontal
convolution kernel and erosion structure, will be applied to detect the stop
lines. If the result is positive, then this lane line is marked as finished,
and no window will be created above.

Figure 7: An example of how length information helps to filter noise within a
single window. Figure 8: Illustrate when lines splits, left side and right
side line detection result will not agree with each other

The overall process of lines detector is shown as pseudo code in algorithm 1.
For special lines which are not parallel to the current ego lines, the problem
is we do not have an initial position for the sliding window to start.
However, we can still use the direction information from the topology map.
Spotting the anchors from the target entrance while turning in free spaces is
one of the situations which requires detecting special lines, as shown as in
Figure 4. The algorithm is a little different, shown as pseudo code in
algorithm 2. The image after erosion is cut into several blocks. The blocks
containing valid pixels are used for forming windows.

Data: Input Image to detect and topology map information

Result: Detected lines

Initialize the first window;

while  _sliding window does not go out of the image_ do

Cut pixels in the window;

Rotate the window;

Commit Convolution;

Commit Directional Erosion;

Cluster pixels;

Form lines for all candidates;

Filter and get the result for current window;

end while

Connect results and form a line;

Algorithm 1 The lines detector

Data: Input Image to detect and topology map information

Result: Detected lines

Rotate the image;

Commit Convolution;

Commit Directional Erosion;

Get valid pixel blocks;

Form valid blocks into windows;

Cut pixels for each window;

for  _each window_ do

Cluster pixels;

Form lines for all candidates;

Filter and get the result for current window;

Connect and merge similar lines;

if  _Any positive result in any window_ then

Return the longest detection result;

else

Return negative as a result;

Algorithm 2 The special lines detector

##  4 Results

The earlier part of this chapter shows the proposed general lines detector is
robust to typical noise on the road, works well under different lighting
conditions and detect multiple types of lines. The later part of this chapter
shows how the localization method helps the vehicle travels through an
intersection in the turning scenario.

For lane lines detection, the method was tested on KITTI [15] and Cityscapes
[25]. For general traffic lines detection, The proposed method was tested on
the Berkeley deep drive (BDD 100k) [26], KITTI and a self-recorded video.
These results of general lines detection cannot be compared to other methods
due to lacking metrics. At last, the BDD 100k dataset and images from a self-
recorded video are used for testing the localization method while passing free
spaces.

###  4.1 Lane lines detection

Figure 9: The first row is some of the detection results of KITTI-UM. The
second row is some of the detection results of Cityscapes. The red is the
converted ego lane based on lines detection.

The proposed lines detector, ECPrior (Erosion and Cluster with prior
knowledge), perform as good as other deep neural network supporting approaches
[27] [28] [29] [30] based on the KITTI behaviour evaluation [31] metric. The
result is shown in table 1. Some of the detection results are shown in the
first row of Figure 9. The proposed detector does not include object
detection; hence it will be affected by other cars close to the lines. A
typical object detector can be added before to get a better result, like
Satzoda did in [32]. The object detection is usually a separate module, and
the same feature should not be implemented again in the lines detection
module. The proposed lines detector works equally fine on Cityscape showing
its scalability, as shown in the second row of Figure 9, despite they have
very different object aspect ratio from the aspect ratio of images from KITTI.

Method | HR-30 | PRE-40 | F1-40
---|---|---|---
CyberMELD | 97.55 % | 94.57 % | 89.66 %
RBNet | 95.92 % | 95.56 % | 87.21 %
RoadNet3 | 95.57 % | 94.57 % | 83.72 %
ECPrior (Mine) | 93.96 % | 96.70 % | 91.86 %
Up-Conv-Poly | 93.14 % | 90.11 % | 83.72 %
Table 1: KITTI (UM Lane) lane lines detection result

The limitations of ECPrior are:

  * •

Like all other methods, ECPrior relies on a stable and accurate BEV
transformation. The transformation is hard to be accurate when the ground is
not flat. Although the deep neural networks can learn to avoid this for a
specific dataset, it is still hard to scale over different datasets. When it
comes to non-flat surfaces, the width of a lane might shrink, as shown in the
first fail case in Figure 10. Dynamic adjustment of the window width can avoid
windows from merging. ECPrior can tolerate minor distortion of the BEV
transformation.

  * •

Because ECPrior is for general cases, the input images should not have special
manifests which would disturb the detector, as shown in the second fail case
in Figure 10. For KITTI, these manifests are mainly caused by the BEV
transformation over low quality areas.

Figure 10: Two fail cases in each row: (1) the first image is the ego lane
result and the second is the lines detection result of the right side curb;
(2) the middle image is the gradience showing clear manifests and the lines
detection results shown in the right image.

###  4.2 General lines detection

ECPrior can solve the problem caused by shadows or short breaks for general
lines detection. ECPrior is also proved to be robust with different lighting
conditions. For stop lines, images from the BDD 100k was used for testing. The
result is shown in 11. The upper case in that image is under a lightly snowing
daylight environment, and the lower case in that image is in a night lighting
environment. In both cases, ECPrior successfully detects the stop lines ahead.

ECPrior also detects special lines well. A self-recorded video was used for
testing. An example in Figure 12 shows the ability to detect special lines
under a turning scenario travelling into a roundabout. In this situation,
ECPrior needs to detect the rear inner side of the roundabout. The left side
curb of the current lane and the inner side curb of the roundabout can then
form a strong anchor used to rebuild the scene of the free space for
localization.

ECPrior uses intense erosion and threshold so that only a small portion of
target lines will be detected at the pixel level. Hence the ECPrior detector
is not a pixel-level detector. ECPrior, as an intact line detection module,
provides lines detection result using regression for dash line segments and
straight lines and using Spline for the others. ECPrior inevitably relies on
an accurate BEV transformation to leverage the prior knowledge of the lines.
Distortion due to camera behind the windshield or problematic camera settings
also cause a narrower efficient area for general lines detection, at that
situation only lines lie in the middle of the front can be detected. As an
example, the detector failed to detect the left side of the inner curb due to
distortion in Figure 12.

Figure 11: Stop lines detected results on BDD 100K dataset. Blue pixels are
the detected stop line and green pixels are the guiding lane line of that stop
line. Figure 12: Detecting the inner side of the roundabout is an example of
detecting a special line with only its direction given. The top 2 results are
shown as red and blue in the last image in the red box.

###  4.3 Localization

Based on these results from previous examples, strong and weak anchors can be
established to locate the vehicle in the turning scenario. The proposed
localization approach relies on neither GPS nor IMU for vehicles to travel
through urban areas. The system provides a stable and accurate position based
on the rebuilt scene for path planning and control subsystems in the turning
scenario. For the cruising scenario, the detection system gives a lane level
localization result (which lane the vehicle is on) which is enough for the
following subsystems.

There are several limitations for using the naive approach of my proposed
system for localization. Firstly, the proposed localization method relies on
visual clues of specific traffic features. Heavy occlusion blocking most of
the target traffic lines will affect the location result in some degree. In
one situation, the vehicle was approaching the intersection with heavy traffic
ahead, blocking most of the coming stop lines. The localization system did not
spot anchors until when the vehicle was very close to the stop lines,
producing a short reaction time to stop for the following subsystems. In
another situation, the vehicle was about to turn right into a small allay
based on the navigation. Several parking vehicles blocked the view of the
right side curb. Hence the detection subsystem did not detect the right
turning feature for the allay and make the vehicle miss the target turning.

In the first situation, we can involve the behaviours of other vehicles as an
input for the localization subsystem, like the way Gao leveraged the position
of other vehicles in [33]. For example, when we detect a line of stopping
vehicles, we can assume the position of the first stopping car is indicating
the position of the stop line to form a prediction to extend the reaction time
for the following subsystems. In the second situation, a more comprehensive
drivable area analysis will show a right side road extension indicating the
allay. Additionally, the localization subsystem is compatible with traffic
lights, traffic signs and GPS as pieces of additional information to help.

##  5 Conclusions

This paper proposes a new perception centered self-driving system and focuses
on testing the proposed general lines detector, ECPrior, and the localization
method on several urban cases. The proposed system design is a skeleton and a
starting point with all potentials to work with additional modules to get
better performance. For example, users can try to apply the method by Hillel
in [34] to get rid of the lens flare to make the detection of ECPrior more
robust when driving towards the sunshine. The potential is much more promising
than other deep neural networks based detection methods. And diverse types of
scenes rebuilding can be discussed in future works. Places like indoor parking
area without GPS signals will heavily rely on the rebuilt scene to localize
the vehicle. Hence they should be prioritized.

In the end, I appeal to the community to reconsider the necessity of using
SIFT like visual features for localization, as well as the need for relying on
deep neural networks for traffic lines detection in the context of self-
driving.

## References

  * [1] J. Ziegler, P. Bender, M. Schreiber, H. Lategahn, T. Strauss, C. Stiller, T. Dang, U. Franke, N. Appenrodt, C. G. Keller, E. Kaus, R. G. Herrtwich, C. Rabe, D. Pfeiffer, F. Lindner, F. Stein, F. Erbs, M. Enzweiler, C. Knöppel, J. Hipp, M. Haueis, M. Trepte, C. Brenk, A. Tamke, M. Ghanaat, M. Braun, A. Joos, H. Fritz, H. Mock, M. Hein, and E. Zeeb.  Making bertha drive—an autonomous journey on a historic route.  IEEE Intelligent Transportation Systems Magazine, 6(2):8–20, 2014\.
  * [2] DMV.  Autonomous vehicle disengagement reports, 2019.  Last accessed 15 August 2020.
  * [3] S. Kuutti, S. Fallah, K. Katsaros, M. Dianati, F. Mccullough, and A. Mouzakitis.  A survey of the state-of-the-art localization techniques and their potentials for autonomous vehicle applications.  IEEE Internet of Things Journal, 5(2):829–846, 2018.
  * [4] Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp, Prasoon Goyal, Lawrence D. Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, Xin Zhang, Jake Zhao, and Karol Zieba.  End to end learning for self-driving cars.  CoRR, abs/1604.07316, 2016.
  * [5] G. Bresson, Z. Alsayed, L. Yu, and S. Glaser.  Simultaneous localization and mapping: A survey of current trends in autonomous driving.  IEEE Transactions on Intelligent Vehicles, 2(3):194–220, 2017.
  * [6] Yan Jiang, Feng Gao, and Guoyan Xu.  Computer vision-based multiple-lane detection on straight road and in a curve.  In 2010 International Conference on Image Analysis and Signal Processing, pages 114–117, 2010.
  * [7] T. Heidenreich, J. Spehr, and C. Stiller.  Laneslam – simultaneous pose and lane estimation using maps with lane-level accuracy.  In 2015 IEEE 18th International Conference on Intelligent Transportation Systems, pages 2512–2517, 2015.
  * [8] Wei-Chiu Ma, Raquel Urtasun, Ignacio Tartavull, Ioan Andrei Barsan, Shenlong Wang, Min Bai, Gellert Mattyus, Namdar Homayounfar, Shrinidhi Kowshika Lakshmikanth, and Andrei Pokrovsky.  Exploiting sparse semantic hd maps for self-driving vehicle localization.  2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Nov 2019.
  * [9] Carl Toft, Erik Stenborg, Lars Hammarstrand, Lucas Brynte, Marc Pollefeys, Torsten Sattler, and Fredrik Kahl.  Semantic match consistency for long-term visual localization.  In Proceedings of the European Conference on Computer Vision (ECCV), September 2018.
  * [10] M. Schreiber, C. Knöppel, and U. Franke.  Laneloc: Lane marking based localization using highly accurate maps.  In 2013 IEEE Intelligent Vehicles Symposium (IV), pages 449–454, 2013.
  * [11] Yeongho Son, Elijah S. Lee, and Dongsuk Kum.  Robust multi-lane detection and tracking using adaptive threshold and lane classification.  Mach. Vision Appl., 30(1):111–124, February 2019.
  * [12] Jihun Kim and Minho Lee.  Robust lane detection based on convolutional neural network and random sample consensus.  pages 454–461, 11 2014.
  * [13] Xiaoliang Wang, Yeqiang Qian, Chunxiang Wang, and Ming Yang.  Map-enhanced ego-lane detection in the missing feature scenarios.  IEEE Access, 8:107958–107968, 2020.
  * [14] A. Borkar, M. Hayes, M. T. Smith, and S. Pankanti.  A layered approach to robust lane detection at night.  In 2009 IEEE Workshop on Computational Intelligence in Vehicles and Vehicular Systems, pages 51–57, 2009.
  * [15] A. Geiger, P. Lenz, and R. Urtasun.  Are we ready for autonomous driving? the kitti vision benchmark suite.  In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 3354–3361, 2012.
  * [16] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zitnick.  Microsoft coco: Common objects in context.  Lecture Notes in Computer Science, page 740–755, 2014.
  * [17] Luo-Wei Tsai, Jun-Wei Hsieh, Chi-Hung Chuang, and Kuo-Chin Fan.  Lane detection using directional random walks.  In 2008 IEEE Intelligent Vehicles Symposium, pages 303–306, 2008\.
  * [18] Albert S. Huang, David Moore, Matthew Antone, Edwin Olson, and Seth Teller.  Finding multiple lanes in urban road networks with vision and lidar.  Autonomous Robots, 26(2):103–122, 2009.
  * [19] Q. Lin, Y. Han, and H. Hahn.  Real-time lane departure detection based on extended edge-linking algorithm.  In 2010 Second International Conference on Computer Research and Development, pages 725–730, 2010.
  * [20] C. Lee and J. Moon.  Robust lane detection and tracking for real-time applications.  IEEE Transactions on Intelligent Transportation Systems, 19(12):4043–4048, 2018.
  * [21] Z. Kim.  Robust lane detection and tracking in challenging scenarios.  IEEE Transactions on Intelligent Transportation Systems, 9(1):16–26, 2008.
  * [22] M. Bertozzi and A. Broggi.  Gold: a parallel real-time stereo vision system for generic obstacle and lane detection.  IEEE Transactions on Image Processing, 7(1):62–81, 1998.
  * [23] Raphaël Labayrade, Jerome Douret, Jean Laneurit, and Roland Chapuis.  A reliable and robust lane detection system based on the parallel use of three algorithms for driving safety assistance.  IEICE - Trans. Inf. Syst., E89-D(7):2092–2100, July 2006.
  * [24] S. Wu, H. Chiang, J. Perng, C. Chen, B. Wu, and T. Lee.  The heterogeneous systems integration design and implementation for lane keeping on a vehicle.  IEEE Transactions on Intelligent Transportation Systems, 9(2):246–263, 2008.
  * [25] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bernt Schiele.  The cityscapes dataset for semantic urban scene understanding.  CoRR, abs/1604.01685, 2016.
  * [26] Fisher Yu, Wenqi Xian, Yingying Chen, Fangchen Liu, Mike Liao, Vashisht Madhavan, and Trevor Darrell.  BDD100K: A diverse driving video database with scalable annotation tooling.  CoRR, abs/1805.04687, 2018.
  * [27] GL Oliveira, Wolfram Burgard, and Thomas Brox.  Eifficient deep methods for monocular road segmentation.  In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2016), 2016.
  * [28] Xiaoliang Wang, Yeqiang Qian, Chunxiang Wang, and Ming Yang.  Map-enhanced ego-lane detection in the missing feature scenarios.  arXiv preprint arXiv:2004.01101, 2020.
  * [29] Zhe Chen and Zijing Chen.  Rbnet: A deep neural network for unified road and road boundary detection.  In International Conference on Neural Information Processing, pages 677–687. Springer, 2017.
  * [30] Yecheng Lyu, Lin Bai, and Xinming Huang.  Road segmentation using cnn and distributed lstm.  In 2019 IEEE International Symposium on Circuits and Systems (ISCAS), pages 1–5. IEEE, 2019.
  * [31] J. Fritsch, T. Kühnl, and A. Geiger.  A new performance measure and evaluation benchmark for road detection algorithms.  In 16th International IEEE Conference on Intelligent Transportation Systems (ITSC 2013), pages 1693–1700, 2013.
  * [32] R. K. Satzoda and M. M. Trivedi.  Efficient lane and vehicle detection with integrated synergies (elvis).  In 2014 IEEE Conference on Computer Vision and Pattern Recognition Workshops, pages 708–713, 2014.
  * [33] Tianshi Gao and H. Aghajan.  Self lane assignment using egocentric smart mobile camera for intelligent gps navigation.  In 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, pages 57–62, 2009.
  * [34] Aharon Bar Hillel, Ronen Lerner, Dan Levi, and Guy Raz.  Recent progress in road and lane detection: a survey.  Machine vision and applications, 25(3):727–745, 2014.