解開車輛檢測(cè)算法之謎

車輛檢測(cè)看似神秘，其實(shí)本質(zhì)上是通過數(shù)學(xué)公式計(jì)算出圖像指定區(qū)域的像素特征，然后根據(jù)相應(yīng)的特征判斷物體所屬的類別。目標(biāo)檢測(cè)方法一般可分為特征提取和類別確定兩個(gè)步驟，常用的支持向量機(jī)（SVM）和方向梯度直方圖（HOG）方法相互配合使用。

本文將介紹常用的車輛檢測(cè)算法，重點(diǎn)從以下幾個(gè)方面來(lái)揭開這些算法背后的奧秘，讓讀者對(duì)機(jī)器學(xué)習(xí)的過程有一個(gè)清晰的認(rèn)識(shí)。

應(yīng)用場(chǎng)景概覽

HOG特征計(jì)算詳解

SVM 工作流程概述

比較與總結(jié)

應(yīng)用場(chǎng)景概覽

車輛檢測(cè)技術(shù)在現(xiàn)實(shí)世界中得到廣泛應(yīng)用，如下例所示。我們定期駕駛的私家車有時(shí)會(huì)配備一個(gè)或多個(gè)車載后視攝像頭。當(dāng)另一輛車即將從后方一定距離內(nèi)通過時(shí)，該系統(tǒng)將被激活。一旦檢測(cè)到車輛后方有車輛，就會(huì)發(fā)出警報(bào)并提示駕駛員減速（圖 1）。另一個(gè)例子可以在與自動(dòng)駕駛領(lǐng)域相關(guān)的應(yīng)用中找到，在該應(yīng)用中，周圍汽車的位置被用來(lái)分析它們的速度、距離和其他因素，然后自動(dòng)調(diào)整汽車的路徑作為響應(yīng)。

車輛檢測(cè)系統(tǒng)還廣泛用于交通控制和道路狀況監(jiān)測(cè)（圖 2）。例如，圖中的系統(tǒng)被放置在隧道口，統(tǒng)計(jì)特定時(shí)間段內(nèi)每天的車流量，并適當(dāng)執(zhí)行相應(yīng)的限制政策，從而減少交通事故的發(fā)生，并為司機(jī)提供交通擁堵或暢通的信息。這允許司機(jī)選擇避免交通的最佳路線。此外，交通流量統(tǒng)計(jì)也可以用于機(jī)場(chǎng)或火車站的停車場(chǎng)，通過大數(shù)據(jù)分析來(lái)判斷車位是否供不應(yīng)求，以便工作人員做出相應(yīng)的響應(yīng)和分配資源。

車輛檢測(cè)系統(tǒng)產(chǎn)生的信號(hào)可以與其他技術(shù)相結(jié)合來(lái)檢測(cè)給定交通信號(hào)周圍的交通流量，工作人員可以利用大數(shù)據(jù)和人工智能來(lái)計(jì)算和確定交通信號(hào)燈的合理時(shí)間間隔。

聯(lián)合 HOG 和 SVM 算法

(40 ? 16) / 8 + 1 = 4

一種使用HOG結(jié)合SVM的行人檢測(cè)方法最初是由法國(guó)研究員Dalal于2005年在美國(guó)加州圣地亞哥舉行的計(jì)算機(jī)視覺與模式識(shí)別會(huì)議上提出的?，F(xiàn)在HOG+SVM的方法已經(jīng)發(fā)展到可以檢測(cè)各種行人。對(duì)象，包括車輛和車道的位置。

HOG 特征計(jì)算

1. HOG是一種局部特征提取算法，因此即使提取更多的特征，該算法也達(dá)不到在包含復(fù)雜背景的大圖像中檢測(cè)目標(biāo)的目的。需要對(duì)圖像進(jìn)行裁剪才能獲取目標(biāo)對(duì)象。實(shí)驗(yàn)證明，作為目標(biāo)物體的車輛必須占圖像的80%以上才能獲得良好的效果。裁剪后的局部圖像被分成塊，每個(gè)塊都被提取出由單個(gè)細(xì)胞組成的特征。

（在每個(gè)圖像中，多個(gè)像素形成一個(gè)單元格，多個(gè)單元格組成一個(gè)塊。）

下面以圖3為例說明HOG特征計(jì)算過程。

首先對(duì)整張圖片進(jìn)行裁剪，得到一張40px x 40px的圖片，之后我們必須定義如下變量：

圖 3：為了說明塊在裁剪圖像中的移動(dòng)，此圖顯示 4 個(gè)單元格形成一個(gè)邊長(zhǎng)為 16px 的塊，然后圖像被裁剪以獲得 40px x 40px 的長(zhǎng)和寬。相應(yīng)的步長(zhǎng)為 1，表示一次移動(dòng)一個(gè)像素。（來(lái)源：為貿(mào)澤創(chuàng)作的原創(chuàng)藝術(shù)作品）

我們定義運(yùn)動(dòng)步長(zhǎng)s，如：s =1。

我們進(jìn)一步以像素為單位定義單元格大小，例如：8 x 8。

我們進(jìn)一步定義塊大小，例如：每個(gè)塊由 2 x 2 = 4 個(gè)單元格組成。

最后，我們定義bin的個(gè)數(shù)，根據(jù)需要設(shè)置值，比如：bin = 9。每個(gè)bin用來(lái)存儲(chǔ)計(jì)算出的直方圖梯度方向的累加值，下面會(huì)進(jìn)一步說明。

2. 對(duì)輸入圖像和顏色進(jìn)行標(biāo)準(zhǔn)化處理，以減少光影對(duì)圖像中物體檢測(cè)精度的干擾，通過伽瑪校正，將圖像轉(zhuǎn)為灰度（伽瑪校正原理為出于本文的目的而忽略）。

3.計(jì)算梯度的大小。

以屬于cell的部分塊為例說明計(jì)算方法（圖4），像素值為25時(shí)計(jì)算中點(diǎn)的公式如下所示。

圖 4：?jiǎn)蝹€(gè)單元格的部分塊大小和像素值。（來(lái)源：為貿(mào)澤創(chuàng)作的原創(chuàng)藝術(shù)作品）

使用基于卷積核方法的合理定義，我們可以通過實(shí)驗(yàn)證明 [-1, 0, 1] 效果最好。卷積核[-1,0,1]可以理解為一個(gè)矩陣，用于計(jì)算每個(gè)像素的梯度幅度方向。因此，我們可以對(duì)水平（x軸正向，向右）使用[-1,0,1]，對(duì)垂直（y軸正向，向上）使用[-1,0,1]T來(lái)進(jìn)行水平以及圖像區(qū)域中每個(gè)像素的垂直梯度分量計(jì)算。兩者的平方和和根號(hào)給出了該點(diǎn)梯度的方向，因此使用的公式如下：

因此像素值為25的點(diǎn)的水平方向計(jì)算如下圖5所示：

圖 5：計(jì)算像素值為 25 的中點(diǎn)水平方向的像素值。（來(lái)源：為貿(mào)澤創(chuàng)作的原創(chuàng)作品）

公式：

因此，像素值為25的點(diǎn)的垂直方向計(jì)算如圖6所示：

圖 6：計(jì)算像素值為 25 的中點(diǎn)水平方向的像素值。（來(lái)源：為貿(mào)澤創(chuàng)作的原創(chuàng)作品）

公式：

??

4. 相應(yīng)的梯度方向使用以下公式計(jì)算：

5. 通過對(duì)每個(gè)單元格中的所有像素重復(fù)計(jì)算過程中的步驟3至4并求和，我們得到每個(gè)單元格在九個(gè)梯度方向上的梯度積分圖（圖7）。

6. 我們求解圖像塊的 HOG 特征，這意味著我們將包含的單元格特征連接在一起。

7. 然后我們求解整個(gè)圖像的 HOG 特征，這意味著我們連接包含的圖像塊特征。

8.特征維度的計(jì)算方法：

上例中的塊在 x 和 y 方向上各移動(dòng)了四步：

(40-16)/8+1=4

每個(gè)塊包括四個(gè)單元格：

2*2=4

特征維度計(jì)算公式：

因此，為當(dāng)前圖像示例計(jì)算的特征維度對(duì)應(yīng)于 576。

9. 然后我們對(duì)獲得的梯度向量進(jìn)行歸一化。歸一化的關(guān)鍵目標(biāo)是防止過度擬合，這會(huì)導(dǎo)致訓(xùn)練集分類良好但測(cè)試集檢測(cè)率極低，這種情況對(duì)于我們的目的來(lái)說顯然是不可接受的。使用我們用于機(jī)器學(xué)習(xí)特征歸一化的相同方法，如果我們獲得分布在 (0, 200) 之間的特征值，例如，我們需要防止 200 以下的數(shù)字影響特征的整體分布（模型會(huì)偏離從整體趨勢(shì)去擬合200，導(dǎo)致過擬合），所以我們需要將特征分布?xì)w一化到一定區(qū)間。Dalal 在他的論文中提到，使用 L2-norm 獲得的結(jié)果非常令人滿意。

（這里，0、200代表特征值的取值范圍）

10. 特征連同相應(yīng)的標(biāo)簽被發(fā)送到 SVM 以訓(xùn)練分類器。

直方圖梯度方向和 Bin 值

Dalal 在他的論文中提到，“這一步的目的是為局部圖像區(qū)域提供函數(shù)量化梯度方向的指示，同時(shí)保持對(duì)圖像中檢測(cè)到的對(duì)象的外觀保持較弱的靈敏度。 “

根據(jù)梯度的方向?qū)⑻荻却笮〔迦氲较鄳?yīng)的bin中，定義方向有兩種可能的方法。

無(wú)符號(hào)方法適用于車輛或其他物體檢測(cè)，而有符號(hào)方法已被實(shí)驗(yàn)證明不適用于車輛或其他物體檢測(cè)。然而，當(dāng)圖像被放大、縮小或旋轉(zhuǎn)時(shí)，這種方法會(huì)很有用，之后像素會(huì)返回到它們的原始位置。請(qǐng)參閱參考資料中包含的第五個(gè)鏈接以獲得更深入的了解。

1. 無(wú)符號(hào)：(0, π)

下面我們仔細(xì)看看無(wú)符號(hào)插值。

在這篇文章中，我們將使用三個(gè)表格來(lái)解釋插值是如何進(jìn)行的。在每個(gè)表中，第一行顯示計(jì)算的振幅，第二行指定 bin 的方向值，該值是通過將 180 度除以定義的 bin 數(shù)獲得的。第三行顯示 bin 序號(hào)，從 0 開始。

圖像可以根據(jù)需要分成盡可能多的箱子。例如，當(dāng)分為九個(gè)bins時(shí)，即使用每個(gè)cell有九個(gè)方向的梯度直方圖時(shí)，每個(gè)bins覆蓋20度的區(qū)域。振幅（上面計(jì)算的）被插入到每個(gè) bin 中，每個(gè) bin 中振幅的最終總和對(duì)應(yīng)于直方圖的垂直軸，而水平軸對(duì)應(yīng)于 bin 值的范圍，在本例中為 (0, 8) .

插值法：

如果像素的振幅為 80 度，方向?yàn)?20 度，則將這些值插入到表 1藍(lán)色區(qū)域中的相應(yīng)位置。

表 1：如果像素的振幅為 80，方向?yàn)?20 度，則插入相應(yīng)位置的值。

如果振幅為80度，方向?yàn)?0度，則將這些值分別插入表2中藍(lán)色區(qū)域的兩個(gè)位置。

表 2：如果像素的振幅為 80，方向?yàn)?10 度，則插入相應(yīng)位置的值。

如果振幅為60度，方向?yàn)?65度，則將這些值分別插入表3中藍(lán)色區(qū)域的兩個(gè)位置。

（180 度和 0 度在方向上是等效的，所以振幅以每個(gè) 1:3 的比例插入兩個(gè) bin 中）

表3：振幅為60，方向?yàn)?65度時(shí)對(duì)應(yīng)位置插入的值。

上表1為方向值與bin對(duì)應(yīng)值完全相同時(shí)采用的插值方法，表2為方向值落在兩個(gè)bin值之間時(shí)采用的插值方法，表3顯示方向值大于最大 bin 值時(shí)使用的插值方法。根據(jù)三種方法在以單元格為度量單位進(jìn)行計(jì)算時(shí)的原理，遍歷后累加一個(gè)單元格中所有像素點(diǎn)的幅值。例如，在上面的示例中，我們?cè)?bin 0 處獲得了 40 和 15 的兩個(gè)振幅值，因此我們的 bin 0 直方圖到目前為止已經(jīng)累積到 55。從 bin 1 到 8 的每個(gè)單元格的振幅在同樣的方式。我們最終得到了類似于下圖的直方圖（圖 7），橫坐標(biāo) X 表示梯度方向，縱坐標(biāo) Y 表示梯度幅度。

圖 7：梯度直方圖示例：橫軸對(duì)應(yīng) bin 數(shù)，縱軸對(duì)應(yīng)計(jì)算出的振幅。對(duì)應(yīng)于圖的縱軸的數(shù)字僅用于說明目的。例如，將上面三個(gè)表中的bin 1幅度值相加得到80 + 40 + 0 = 120作為最終結(jié)果，我們得到直方圖縱坐標(biāo)為120。隨著我們繼續(xù)計(jì)算 bin 1 的值，該值將不斷累加。（來(lái)源：為貿(mào)澤創(chuàng)作的原創(chuàng)藝術(shù)作品）

實(shí)驗(yàn)結(jié)果表明，當(dāng)使用九個(gè)箱子進(jìn)行目標(biāo)檢測(cè)和單向插值時(shí)，可以獲得最好的結(jié)果。

2. 有符號(hào)：(0, 2π)

當(dāng)在方向值前加上正負(fù)號(hào)時(shí)，如果同時(shí)定義了九個(gè)bin，則分配給每個(gè)bin的角度范圍為：(0, π/9°)。例如，對(duì)于第二個(gè) bin，它有一個(gè)正值插值到 20-40 范圍內(nèi)（藍(lán)色區(qū)域），負(fù)值應(yīng)該插值到 200-220 范圍內(nèi)（藍(lán)色區(qū)域）。(圖8)

圖 8：在有符號(hào)插值中，每個(gè)扇區(qū)代表一個(gè) bin 覆蓋角范圍值。紅色對(duì)應(yīng)一號(hào) bin，涵蓋 0 到 20 度。按順時(shí)針方向移動(dòng)，綠色標(biāo)記 340–360 度的終點(diǎn)。藍(lán)色區(qū)域表示兩個(gè)方向上對(duì)應(yīng)的 bin。（來(lái)源：為貿(mào)澤創(chuàng)作的原創(chuàng)藝術(shù)作品）

SVM 工作流程概述

SVM（支持向量機(jī)）通過一個(gè)超平面將空間中的兩個(gè)類分開，二維空間可以簡(jiǎn)單理解為求y且y滿足的空間：

y 值決定樣本是分類為陽(yáng)性還是陰性。然而，為了確定最優(yōu)超平面，這里我們引入支持向量和最大間隔。我們的目標(biāo)是找到一個(gè)超平面，使最靠近超平面的點(diǎn)之間的距離最大（圖 9）。

圖9：紅線對(duì)應(yīng)超平面，虛線兩邊的點(diǎn)為支持向量，計(jì)算值為1（正類）或-1（負(fù)類）。藍(lán)色點(diǎn)對(duì)應(yīng)正樣本，綠色點(diǎn)對(duì)應(yīng)負(fù)樣本。目標(biāo)是找到顯示虛線之間最大距離的值，因?yàn)檩^大的距離表示更好的二元分類模型。（來(lái)源：維基百科）

由于真實(shí)情況下呈現(xiàn)的數(shù)據(jù)非常復(fù)雜，有時(shí)會(huì)根據(jù)需要引入核函數(shù)，以便將低維映射到高維，并通過找到最優(yōu)超平面使線性不可分的數(shù)據(jù)（圖 10 ）線性可分。

圖10：紅圈中的點(diǎn)在二維空間中與藍(lán)圈中的點(diǎn)線性不可分，因此需要一個(gè)核函數(shù)將這些點(diǎn)映射到更高維的坐標(biāo)系中。（來(lái)源：為貿(mào)澤創(chuàng)作的原創(chuàng)藝術(shù)作品）

SVM 計(jì)算量大且訓(xùn)練耗時(shí)，因?yàn)橐獮槊總€(gè)點(diǎn)計(jì)算與其他所有點(diǎn)的相似性。因此，支持向量機(jī)適合訓(xùn)練數(shù)據(jù)量較小的二元分類模型，如果涉及多個(gè)類別，通常會(huì)單獨(dú)訓(xùn)練多個(gè)模型。此外，由臺(tái)灣大學(xué)教授開發(fā)的兩個(gè)開源工具現(xiàn)在非常受科學(xué)家歡迎。第一個(gè)是 LibSVM，另一個(gè)是 Liblinear，它是基于 SVM 技術(shù)針對(duì)大量數(shù)據(jù)開發(fā)的。

SVM 對(duì)參數(shù)極其敏感。在 LibSVM 或 LibLinear 的訓(xùn)練過程中，密切關(guān)注懲罰項(xiàng) C 和權(quán)重因子 w 非常重要。C為懲罰項(xiàng)，越大表示訓(xùn)練過程中的分類效果越好。但是，當(dāng)C過大時(shí)，會(huì)出現(xiàn)過擬合，即訓(xùn)練樣本分類準(zhǔn)確率極高，而測(cè)試準(zhǔn)確率極低。不可避免地會(huì)存在遠(yuǎn)離集合中心集群的數(shù)據(jù)點(diǎn)，C 的大小表明我們?cè)敢鈦G棄這些異常值。較大的 C 值表示我們不愿意丟棄這些異常值，因此該模型特別適合訓(xùn)練集而不是測(cè)試集。W，即權(quán)重，代表正負(fù)樣本的系數(shù)，如果我們想要檢測(cè)更多的目標(biāo)，我們可以增加正樣本權(quán)重。但是，這樣做會(huì)導(dǎo)致誤檢率（FP）特別高。反之，增加負(fù)樣本權(quán)重會(huì)降低誤檢率（FP），但目標(biāo)檢出率（TP）自然也會(huì)降低。

筆者做了一個(gè)簡(jiǎn)單的實(shí)驗(yàn)發(fā)現(xiàn)，使用百萬(wàn)數(shù)據(jù)點(diǎn)和1152維特征，在運(yùn)行Windows 10的情況下，使用兩個(gè)CPU和60G RAM，開啟18個(gè)線程進(jìn)行訓(xùn)練需要20分鐘。因此，建議要么使用 Liblinear 庫(kù)在非常大的語(yǔ)料庫(kù)上進(jìn)行訓(xùn)練或增加可用的計(jì)算機(jī)內(nèi)存。

比較與總結(jié)

在本文中，我們重點(diǎn)了解車輛檢測(cè)背景下的特征計(jì)算，并簡(jiǎn)要探討了 SVM 分類策略。當(dāng)HOG特征用于車輛檢測(cè)時(shí)，建議使用9個(gè)bin中1000維以上特征的無(wú)符號(hào)插值，并且必須對(duì)不均勻的特征分布進(jìn)行歸一化。對(duì)于SVM，可以根據(jù)需要選擇核函數(shù)，必要時(shí)可以使用LibSVM庫(kù)基于非常大量的數(shù)據(jù)訓(xùn)練模型。SVM 將低維空間映射到高維空間的核函數(shù)機(jī)制有效地解決了線性不可分性問題。SVM 的計(jì)算復(fù)雜度由支持向量的數(shù)量決定，最終的決策函數(shù)幸運(yùn)地由少量的支持向量決定。SVM 也有其局限性。如果不使用 LiBSVM/Liblinear 開源庫(kù)，單獨(dú)使用 SVM 時(shí)處理大量數(shù)據(jù)會(huì)非常困難。這是因?yàn)镾VM計(jì)算過程涉及矩陣計(jì)算，行數(shù)和列數(shù)由樣本數(shù)決定。因此，大樣本在計(jì)算過程中會(huì)消耗大量的時(shí)間和空間。同樣，在實(shí)踐中，選擇是否利用 HOG 應(yīng)該基于對(duì)技術(shù)優(yōu)缺點(diǎn)的雙向考慮。這些優(yōu)點(diǎn)和缺點(diǎn)總結(jié)在這里供讀者參考。SVM 也有其局限性。如果不使用 LiBSVM/Liblinear 開源庫(kù)，單獨(dú)使用 SVM 時(shí)處理大量數(shù)據(jù)會(huì)非常困難。這是因?yàn)镾VM計(jì)算過程涉及矩陣計(jì)算，行數(shù)和列數(shù)由樣本數(shù)決定。因此，大樣本在計(jì)算過程中會(huì)消耗大量的時(shí)間和空間。同樣，在實(shí)踐中，選擇是否利用 HOG 應(yīng)該基于對(duì)技術(shù)優(yōu)缺點(diǎn)的雙向考慮。這些優(yōu)點(diǎn)和缺點(diǎn)總結(jié)在這里供讀者參考。SVM 也有其局限性。如果不使用 LiBSVM/Liblinear 開源庫(kù)，單獨(dú)使用 SVM 時(shí)處理大量數(shù)據(jù)會(huì)非常困難。這是因?yàn)镾VM計(jì)算過程涉及矩陣計(jì)算，行數(shù)和列數(shù)由樣本數(shù)決定。因此，大樣本在計(jì)算過程中會(huì)消耗大量的時(shí)間和空間。同樣，在實(shí)踐中，選擇是否利用 HOG 應(yīng)該基于對(duì)技術(shù)優(yōu)缺點(diǎn)的雙向考慮。這些優(yōu)點(diǎn)和缺點(diǎn)總結(jié)在這里供讀者參考。這是因?yàn)镾VM計(jì)算過程涉及矩陣計(jì)算，行數(shù)和列數(shù)由樣本數(shù)決定。因此，大樣本在計(jì)算過程中會(huì)消耗大量的時(shí)間和空間。同樣，在實(shí)踐中，選擇是否利用 HOG 應(yīng)該基于對(duì)技術(shù)優(yōu)缺點(diǎn)的雙向考慮。這些優(yōu)點(diǎn)和缺點(diǎn)總結(jié)在這里供讀者參考。這是因?yàn)镾VM計(jì)算過程涉及矩陣計(jì)算，行數(shù)和列數(shù)由樣本數(shù)決定。因此，大樣本在計(jì)算過程中會(huì)消耗大量的時(shí)間和空間。同樣，在實(shí)踐中，選擇是否利用 HOG 應(yīng)該基于對(duì)技術(shù)優(yōu)缺點(diǎn)的雙向考慮。這些優(yōu)點(diǎn)和缺點(diǎn)總結(jié)在這里供讀者參考。的優(yōu)點(diǎn)和缺點(diǎn)。這些優(yōu)點(diǎn)和缺點(diǎn)總結(jié)在這里供讀者參考。的優(yōu)點(diǎn)和缺點(diǎn)。這些優(yōu)點(diǎn)和缺點(diǎn)總結(jié)在這里供讀者參考。

優(yōu)點(diǎn)：HOG是以局部為單位進(jìn)行的，可以更好的捕捉局部的形狀信息，同時(shí)忽略光照、顏色等因素。例如，在車輛檢測(cè)過程中可以忽略汽車的顏色，從而減少所需的特征維度數(shù)量，并且由于該技術(shù)對(duì)光的敏感度較弱，即使在視線被部分遮擋的情況下仍然可以檢測(cè)到車輛。

缺點(diǎn)：HOG不太擅長(zhǎng)處理遮擋，車輛方向的變化不易察覺。由于梯度的性質(zhì)，HOG對(duì)噪聲相當(dāng)敏感，所以在block和cells被分割成局部區(qū)域單元后，在實(shí)踐中往往需要進(jìn)行高斯平滑來(lái)去除噪聲。特征維度（cell、block、step size）的確定要求很高，在實(shí)踐中需要多次嘗試才能獲得最優(yōu)解。

我希望本文能讓您更清楚地了解車輛檢測(cè)的最新技術(shù)水平。結(jié)合SVM和HOG雖然計(jì)算量大，但相應(yīng)的成本低，模型的訓(xùn)練可以在標(biāo)準(zhǔn)CPU上完成，這使得這種方法在中小型產(chǎn)品開發(fā)公司中非常流行。例如，車載攝像頭等小部件的開發(fā)和輸出可能會(huì)繼續(xù)產(chǎn)生更好的性價(jià)比，同時(shí)還能確保可接受的可用性水平。

審核編輯hhy