# Semantic Segmentation for Free Space and Lane Based on Grid-based Interest Point Detection
###### tags: `CV論文`

# I. Introduction

使用Encoder-Decoder可以有效解決Segmentation Problem，不過他卻需要耗費大量的運算，非常沒有效率。因此本篇論文中使用物件偵測的方式來偵測可行駛區域邊緣、道路線中的關鍵點，之後再使用CV-based的方法來做後處理，透過這樣的方式可以大大減少運算時間。

論文中採用YOLO架構來做物件偵測，原因是作者希望採用YOLO的以下兩種特性：
1. Multi-label classification：因為一個點在不同情況下可能會是不同類別。
2. 跨Scale的特徵抽取：雖然論文中善用了不同Scales的特徵，不過實際上在之後只會用到第3層的輸出。

# III. Proposed Methodology

## A. Point Detection Network

### 架構說明

點偵測架構主要是基於SAMT架構組成的，包含一個用來做特徵抽取的深度捲積神經網路，接著後面連接多個不同的網路來處理不同任務。整個模型主要由以下部分組成：
- 深度神經網路
- 金字塔架構的特徵捲積神經網路
- 適合用來做影像相關任務的Backbone架構

在SAMT的論文中，他們使用的是YOLOv3中的DarkNet53作為特徵抽取的Backbone，而這篇論文中則是使用YOLOv4中的CSPDarknet53作為Backbone。這篇論文中，作者採用Confidence Map於後處理中，可能可以藉此找出邊界點。

> CSPDarknet53由53個捲積層、一些用來預測BBox相關資訊的Layers組成；YOLOv4中使用三種不同大小的Scales來預測BBox，之後再用類似FPN的方式來對這些Scales做特徵抽取。

YOLOv4有三個不同層級的輸出，不過在<font color="blue">這篇論文中作者只使用第三層的輸出</font>，因為這層的輸出包含了較豐富的特徵。

### 定義損失涵數

#### 1. Total Loss:

前面提到點偵測的架構與YOLO差不多，只是Grid Cell不再預測BBox的大小。因此他計算Loss的方式其實也跟YOLO差不多，下圖公式為Total Loss的計算方式，各個符號代表的意義分別為：
- $mf$：代表Batch Size。
- $f$：論文中說是影像的編號，我認為是影像在一個Batch中的編號。
- $xy_{loss}^{Point}(f)$：編號$f$影像預測出的<font color="blue">座標誤差</font>。
- $p_{loss}^{Point}(f)$：標號$f$影像的<font color="blue">類別預測誤差</font>。
- $C_{loss}^{Point}(f)$：編號$f$影像的<font color="blue">Confidence Loss</font>。


#### 2. 座標誤差：

他會去看所有預測出「點」的Grid Cell，並把他們的座標誤差累加起來，最後再乘上一個倍數讓不同Loss可以有差不多的Scale。
- $\mathbb{I}_{i}^{pt}$：說明了第$i$個Grid Cell裡面存在點，我猜這個符號在式子中可以解釋為：如果對應編號的Grid Cell中存在點，那麼他就會是$1$，反之則為$0$。如此一來，就可以規定哪些Grid Cell需要計算Loss。
- $\lambda_{pt}$：Normalization Weight。


#### 3. 類別預測誤差：

累加所有類別的誤差。


#### 4. Confidence Loss：

除了看有預測出「點」的Grid Cell以外，還要去看「Ground Truth有點，但卻沒預測出的那些Grid Cell」。
- $\mathbb{I}_{i}^{nopt}$：代表第$i$個Grid Cell應該要預測出「點」，但卻沒有被模型預測出來。
- $\lambda_{nopt}$：原文寫"The normalization weight for any negative xy-prediction"。大概就是說給Negative Grid Cell的Normalization Weight。


## B. CV-based Pre-processing

這部分是為了提供訓練時會用到的Ground-truth，我們必須將輸入的Ground-truth轉成符合模型輸出Grid的大小。

現有的語意分割公開資料集通常都只會提供稀疏的Ground-truth，不過在這篇論文中，應該告訴每個Grid Cell他是否包含有效的點。假如我們使用現有的資料集，那麼會發生某些Grid Cell明明包含邊緣點，但我們卻說他不包含的情形。為了解決這個問題，作者在所有相鄰的點之間插入額外的邊緣點，讓Grid Cell有辦法形成一個封閉的形狀。

:::info
下圖中，綠色的點代表原本資料集就存在的邊緣點，而黃色的點則是插值後得到的額外邊緣點，至於藍色的Grid Cell代表Positive Cell，也就是裡面包含有效的點。
:::


## C. Image Pre-processing

訓練資料集的影像形狀可能都不太一樣，這部分就是用來調整輸入影像的形狀，將原本大小為$(W_I, H_I, 3)$的形狀變成$(W_M, H_M, 3)$。過程中他先透過Interpolation演算法將影像做縮放，之後再做Padding，這是為了不影響輸入影像的比例。

## D. CV-based Post-processing

### 1) Free Space

這部分主要就是要將模型輸出的那些點連接起來，變成一個封閉的可行駛範圍。執行時需要輸入以下4個元件：
1. 模型預測出來的點：$R(x, y, p(c), C)$。
2. 第三層輸出的Confidence Map：$F_3(u, v)$。
3. 已標記出Positive Prediction的Grid Map：$Q(u, v)$。
4. 未縮放之輸入影像：$I(x, y)$。

:::info
由於$F_3(u, v)$、$Q(u, v)$的解析度都跟Grid Map相同，因此他的座標使用$(u, v)$表示。而模型會預測出各個點的詳細座標，因此他的座標使用$(x, y)$表示。

※ $u<\gamma W_M$, $v<\gamma H_M$; $x<W_I$, $y<H_I$。
:::


#### 步驟1：找出起點、終點

可行駛區域通常會與影像的最下面連接，因此所有Positive Points中最左下的點會是起點，最右下的點會是終點。

※ 論文中其實有一個奇怪的式子(如下圖)，不過我覺得講得不太清楚，直接忽略掉就好。

#### 步驟2：決定各個點的連線順序

在$Q(u, v)$中使用如下圖的Kernel來決定下一個點，每次將Kernel以中心對齊並覆蓋在目前的Cell上，選擇得分最高的Cell作為下一個點。不過由於Kernel中具有相同的數字，因此可能會遇到某兩個Cell同時為最高分的情況。這種時候就會使用到$I(x, y)$細看點在Cell中的確切位置，並選擇最短歐式距離的點作為下一個點。到下一個點之後，先將$Q(u, v)$中<font color="blue">上一個點的數值歸零</font>，再重複以上動作，直到找到終點為止。
:::info
Kernel中的權重之所以會設成這樣是因為：由於起點在左，終點在右，在找的過程中一定是不斷往右跑。不過作者希望盡量將所有點都偵測進去，因此如果左右兩邊同時都有邊界點的時候，會希望先去看左邊的點。
:::

##### 處理例外狀況：

使用Kernel的方式來尋找鄰近的下一個點會在點不連續的情況下產生例外狀況，程式會找不到下一個點，這時論文中依序使用以下方式來處理例外狀況：
1. 在$Q(u, v)$中使用額外的$5\times 5$ Kernel來尋找Positive Cell，假如找到多個Cells的話，則搭配$I(x, y)$找出最短歐式距離的點：假如找不到任何一個Positive Cell的話，則跳到第2種方法。
2. 在$F_3(u, v)$中使用額外的$5\times 5$ Kernel來尋找Positive Cell，選擇Confidence Score高的作為下一個點。

#### 步驟3：決定各個點的連線順序（畫出可行駛區域）

前面決定各點的連線順序是使用Grid Cell Level，不過這步驟是要在與輸入影像相同解析度的影像上畫出可行駛區域。由於各個點之間的距離很近，為了節省運算量，因此論文中直接使用直線來將連接各個點。

### 2) Lane

#### 步驟1：將Grid Cell做初步的分群

將有相鄰的Grid Cells分到同一組，這邊的相鄰是去看各個Cell的8個方向，在這些方向相鄰就算同一群。

#### 步驟2：進一步細分

經過步驟1分出來的群其實有個問題：不同線段在距離相機較遠的時候，可能會分到相鄰的Grid中，使得不同Grid被分到同一群，因此論文中提到還需要再進一步細分。

##### 將Cell分類：

細分的過程中，作者透過掃描$v$軸的方式，將各個群中的Grid分成三種不同類型：
1. <font color="blue">Individual Cell</font>: 相同的$v$軸中，只存在同一組的Cell。如下圖$(a)$中的藍色Grid Cells。
2. <font color="orange">Consecutive Cell</font>: 相同的$v$軸中，存在超過一組的Cell。如下圖$(a)$中的黃色Grid Cells。
3. <font color="red">Combined Cell</font>: 跟Individual Cell一樣，在相同的$v$軸中，指存在同一組的Cell，**不過他與多個組相鄰**。如下圖$(a)$中的紅色Grid Cells。
> 我認為他判斷是否與多個組相鄰是去掃描上下兩列，如果有一列存在Consecutive Cell，那就可以知道他是Combined Cell。

:::info
所謂的同組是指：在相同的$v$軸中，如果兩個Cell之間沒有空格，那就說他們在同組。例如下圖$(a)$中的黃色Grid Cell就會被分成兩組。
:::


##### 細分各群Grid Cells：

細分的過程中，我們會先從Consecutive Cells開始。他主要的概念就是去看Consecutive Cells的上下兩列，之後將相鄰較少Individual Cell的那邊更新為新的Index (如上圖$(b)$所示)。

接著他會去看Combined Cells，他會在這當中選擇一個Cell作為分隔點，之後再透過某種方法決定要把這個Cell分到哪一邊：
1. 決定分界的Cell：將Combined Set中相鄰的點連線，接著去量測這之間的夾角變化，將產生大夾角的點作為分界點。如下圖$(a)$所示。
2. 決定要把分界點分到哪一邊：作者希望將分界點分到可以讓線段比較直的那邊，因此從分界點往兩邊看取夾角較小的點。如下圖$(b)$所示。


#### 步驟3：將不同群的Cells組合到同一群：

論文中之所以會需要做這個步驟是因為：使用前面的方法在將Grid Cells分群時，如果兩個Cells之間存在空隙，那麼他們就會被分到不同群。然而我們的點其實是由神經網路預測出來的，如果產生False Negative，就會使得原本應該屬於同一條道路線的Grid Cells被分到不同群。因此我們會需要加入這個步驟，將那些因為False Negative而被拆散的Groups合併回來。為了達成這個目的，論文中主要使用以下兩個步驟：
1. 在$I(x, y)$中使用最小平方法將線性函數($m_kx+c_k$) fit到各個Group中的點 (如下圖)。
2. 使用於步驟一得到的線性函數來比較各個群，將符合條件的群合併。以一段將詳細介紹如何比較各個群。


##### 如何比較兩個群呢？

論文中使用以下三個步驟來比較各個群，這三個步驟是有先後順序的，第$n+1$個步驟只比較第$n$個步驟中符合條件的：
1. **比較各條線的傾斜度**：線性函數中的$m_k$代表斜率，論文中透過$\theta=tan^{-1}m_k$的方式得到各調線傾斜的角度。接著比較各條線的$\theta$，如果兩條線的$\Delta\theta$小於某個閾值，那麼就符合第一個條件，因此可以繼續比較第二個條件。
2. **比較兩組線的相對位置**：如果有兩群Grid Cells原本屬於同一條線，但因為False Negative導致他們被分到不同群，那麼其中一群的最小$y$值應該會大於另一群任一點的$y$值。因此這次的比較是取出這兩群的端點，如果有其中一個端點的$y$值比另一群兩個端點的$y$值都還大，那就符合這個條件。
3. **比較兩群的距離**：因False Negative而被分開的兩個群之間的距離應該會非常近，因此這次的條件是：這兩群的歐式距離是否小於一個**自適應閾值**$d_{th}=\lambda\min(p_y, q_y)$。
:::info
論文中說$p_y$、$q_y$分別代表兩個群的端點，我猜他指的是下面那個群的上端點、下面那個群的下端點。我認為他拿這兩個數值比較作為閾值的原因是：影像中同樣都是一個Cell，但上半部會對應到比較長的距離，下半部會對應到比較短的距離。因此如果線斷在下半部，那就可以允許他有比較大的斷層。
:::

:::success
由於下圖$(a)$中的綠色、橘色兩個群依序滿足以上三個條件，因此最後可以將它們合併在一起，變成圖$(c)$那樣。
:::


#### 步驟4：將各群的點連起來

論文中使用最小平方法來將二次函數 $f_k(y)=\alpha_ky^2+\beta_ky+\gamma_k$ fit到各群的點中，而各群的兩個端點也會變成對應二次曲線的兩個端點 (也就是道路線的兩個端點)。

由於各群的兩端點不一定會剛好出現在二次曲線上，因此論文中使用下列公式來找出端點的位置 (其實就是把$y$帶到函數中，得到對應的$x$，之後再將本來的$x$更新為新的$x$)：

:::info
**為甚麼要使用二次曲線，道路線不是直線嗎？**
現實中的道路線在轉彎的時候也有可能出現不是直線的狀況。另外，我個人認影像中存在的失真也可能讓本來的直線變成曲線，原本的直線如果出現在影像的邊緣，那他可能會產生一些弧度。這個現象可以在論文中實驗部分的圖片看出來：
:::
<!--
:::info
**為甚麼要使用$y$函數而不使用$x$函數呢？**
::: -->