沈智勇 蘇 翀* 沈智威 孫厚權(quán) 周 揚

1(江蘇科技大學(xué) 江蘇 張家港 215600)2(蘇州大學(xué) 江蘇 蘇州 215000)

0 引 言

隨著時代的發(fā)展，交通情況越發(fā)不確定，出行的安全度和舒適度逐漸受到重視。隨著私家車日益增加，人們出行更為便捷的同時，所造成的交通擁堵往往帶來諸多不便。用戶往往只想知道自己出行中起點到終點之間的道路情況，而對其他路上的道路情況不感興趣。

已有的交通路況檢測大多基于圖像處理與識別，這種方法不但耗資巨大，對于圖片信息的儲存數(shù)據(jù)量也是一個問題，若只在少數(shù)路口安置攝像頭進行分析車流量，圖像分析大多適應(yīng)于相對靜態(tài)的情況或者車速較慢的情況，對于整條道路的動態(tài)車流量精度不能有明確保證。對于動態(tài)車流量的檢測，本文提出了一種基于亞線性MG算法的替換策略。

本文的主要貢獻如下：

(1) 提出一種基于亞線性的替換策略；

(2) 提出的亞線性算法能較好地應(yīng)用于路況檢測；

(3) 選擇出一種高效的能與替換策略相結(jié)合的基數(shù)桶數(shù)據(jù)結(jié)構(gòu)，保證了空間的亞線性。

實驗結(jié)果表明，該算法對于車流量的檢測與計算具有一定的可行性，相對于基于圖像處理的檢測方式降低了數(shù)據(jù)的緯度，提高了計算的速度，同時保護了個人的隱私。對于基于紅外方式的檢測方式本文提出的算法能大大提高數(shù)據(jù)的可信度，提高結(jié)果的正確性。

1 相關(guān)工作

1.1 ViBe算法檢測路況

ViBe算法利用視覺背景提取改進車流量估計，對靜止目標有非常良好的計算效果。ViBe算法能很好地抑制假影現(xiàn)象，將檢測器安裝至道路交通口，利用紅燈效應(yīng)可對車流量進行準確檢測，提高了車形清晰度，提高了檢測的正確性[4,8]。但ViBe算法本身仍存在運動目標不完整等問題。

1.2 紅外檢測路況

當前普通的基于紅外的道路檢測系統(tǒng)，利用脈沖進行簡單計數(shù)，由采集模塊、交通燈控制模塊和模擬控制中心?；旧贤瓿闪塑嚵髁繖z測的功能，但并未對其中收獲的數(shù)據(jù)進行簡化和計算，難以保證數(shù)據(jù)的準確性，失去了數(shù)據(jù)的意義。

2 亞線性MG替換策略-網(wǎng)絡(luò)流檢測方式

基于亞線性MG替換策略-網(wǎng)絡(luò)流的動態(tài)車流量檢測方式通過利用自制道路檢測器安置紅外對管，利用每個數(shù)據(jù)收集器收集的車輛通行數(shù)目。對道路情況進行算法分析與研究[2-4,6,10-11]。

本算法先求解出單條路徑的動態(tài)車流量，將此條路徑的車流量抽象成圖中的一條邊，根據(jù)大數(shù)定理構(gòu)建圖，根據(jù)段流量求解出最大流，根據(jù)相關(guān)知識得出交通狀況。

算法總體設(shè)計流程如圖1所示。

圖1 算法總體設(shè)計流程

3 亞線性替換算法

3.1 基數(shù)桶

道路上存放N個檢測器，分別檢測到的數(shù)據(jù)將依次存放至基數(shù)桶中。根據(jù)Zipf定理，可以確定基數(shù)桶結(jié)構(gòu)[1]是有效的。本文根據(jù)Zipf定理確定基數(shù)桶中的容量是全部數(shù)據(jù)值的10%。

基數(shù)是集合論中的一個概念，將相似的數(shù)據(jù)放入一個基數(shù)桶，并保證基數(shù)桶中各集合各自保證非遞減有序。

建立9個的基數(shù)桶，桶狀結(jié)構(gòu)樣例如圖2所示。

圖2 基數(shù)桶數(shù)據(jù)結(jié)構(gòu)圖

數(shù)據(jù)i進入基數(shù)桶中只需進入該對應(yīng)集合，數(shù)據(jù)i進入基數(shù)桶時對數(shù)據(jù)的最高位進行劃分，如：12最高位是1，則進入1號基數(shù)桶，29的最高位是2，則進入2號基數(shù)桶，其優(yōu)勢在于與其他數(shù)據(jù)保持獨立性。當有新的數(shù)據(jù)進入基數(shù)桶，如41進入基數(shù)桶，只需考慮基數(shù)4中集合所存在的元素，由于非遞減有序特性，利用插入排序?qū)?shù)據(jù)進行增加或者更新。

同時設(shè)置隊頭游標和隊尾游標分別指向各個集合的隊頭和隊尾。隨機算法替換數(shù)據(jù)時只需比較每個基數(shù)集合中的隊頭游標與隊尾游標中所指向的數(shù)據(jù)。

同時基數(shù)桶中的元素可利用塊狀鏈表[13]的形式對數(shù)據(jù)進行初始化、更新和插入，此時數(shù)據(jù)運算時的時間復(fù)雜度可大大降低。

當進行數(shù)據(jù)處理是空間復(fù)雜度顯然只與基數(shù)桶容量有關(guān)，是空間亞線性的。

3.2 隨機化與改進MG替換算法

本文利用紅外檢測器檢測道路流動車流量，并做出如下假設(shè)：

(1) 道路是單向的。

(2) 道路沒有交叉口。

根據(jù)上述假設(shè)可以得出：在單向無交叉口的一段連續(xù)道路上的檢測器在單位時間內(nèi)測定的數(shù)據(jù)值大部分是相同的或是相似連續(xù)的(車流量并不能突變)。圖3表示在以上假設(shè)下檢測器檢測結(jié)果模型圖。

圖3 檢測器檢測結(jié)果模型圖

當a測出值為5，那么b測出的值應(yīng)與a的檢測值相同或相差車道數(shù)m的倍數(shù)，且a、b檢測值差值不大。

根據(jù)以上假設(shè)推論：如果道路擁有交叉口，那在兩條交叉口之間的檢測器中的數(shù)據(jù)大部分是相同的。

利用Zipf定律可以得到一個大致的模型，90%的道路情況數(shù)據(jù)占所有道路情況數(shù)據(jù)值的10%(10%的數(shù)據(jù)值分布在不同的路口，有岔路等地)，我們可以稱這90%的數(shù)據(jù)是有效數(shù)據(jù)，剩下10%的數(shù)據(jù)是無效數(shù)據(jù)。但這90%的數(shù)據(jù)中不同的數(shù)字只占全部數(shù)據(jù)的10%，根據(jù)以上論述可以得出隨機化的合理性和有效性，亞線性替換算法描述如下：

Input：檢測器檢測到各個數(shù)值in[]；

Output：替換算法返回結(jié)果，基數(shù)桶中的有效數(shù)據(jù)out[][]；

1 While in[]!=empty:

2 i=0;

3 s←取[0,9]之間的任意一個隨機數(shù)；

4 i++;

5 cardinal←in[i*9+s]所對應(yīng)的基數(shù)

6 Size←基數(shù)桶容量

7 If Size !=full:

8 If s?out[][];

9 s放入基數(shù)桶;

10 Out[ cardinal][].count++;

11 End If

12 End If

13 If Size==full:

14 If s∈out[][]:

15 s.Count++;

16 Else

17 For each out[ cardinal][]:

18 Out[ cardinal][].count--;

19 If out[ cardinal][].count==0

20 Flag=1;

21 移出基數(shù)桶;

22 End If

23 If flag==1

24 s放入基數(shù)桶

25 End If

26 End If

27 End While

算法有效性分析如下:

(1) 對于上述算法，由于關(guān)鍵在于隨機選取的間隔d應(yīng)對于具體問題具體分析，由于隨機化，算法的時間復(fù)雜度嚴格小于數(shù)據(jù)量n，計算復(fù)雜度只與基數(shù)桶中的數(shù)量有關(guān)，故替換算法是時間亞線性的。

(2) Misra Gries算法步驟表明：在數(shù)據(jù)流中到達的項i進行如下的步驟：如果項i在數(shù)組T中，則其對應(yīng)的計數(shù)器++c；如果項i不在數(shù)組T中，且數(shù)組T中的元素個數(shù)小于k-1，將項i加入數(shù)組T，并為其分配計數(shù)器ci=1；其他情況，將數(shù)組T中所有元素的計數(shù)器減1，此時如果數(shù)組T中存在元素的計數(shù)器值為0，則從數(shù)組T移除這個元素。MG算法保證了亞線性，本文將計數(shù)器的計算由全部數(shù)據(jù)縮小至基數(shù)桶的各個基數(shù)所對應(yīng)的基數(shù)項的計數(shù)器計算此數(shù)，基數(shù)桶結(jié)構(gòu)也將計算復(fù)雜度大大降低，滿足亞線性。

(3) 替換算法替換出的是最不頻繁出現(xiàn)的數(shù)字，也就是說當替換次數(shù)越多，出現(xiàn)無效數(shù)據(jù)的概率就越低。因為根據(jù)Zipf定律，有效的數(shù)據(jù)占了90%，無效的數(shù)字只有10%，這些數(shù)據(jù)肯定是最不頻繁的數(shù)字，那優(yōu)先替換的是這些數(shù)字，故替換算法具有有效性。

(4) 關(guān)于隨機間隔d的選?。焊鶕?jù)zipf定理，最少有90%的數(shù)據(jù)是有效數(shù)據(jù)，這些數(shù)據(jù)的數(shù)據(jù)值占所有數(shù)據(jù)值的10%(數(shù)據(jù)與數(shù)據(jù)值的概念如圖3所示，其他情況的比例可由實驗大致得出)，那么剩下10%的數(shù)據(jù)是無效數(shù)據(jù)，這些數(shù)據(jù)的數(shù)據(jù)值占所有數(shù)據(jù)值的90%，這90%的數(shù)據(jù)值基本上是與10%的無效數(shù)據(jù)一一對應(yīng)。即若某數(shù)據(jù)值只出現(xiàn)一到兩次，那么這個數(shù)據(jù)值很有可能是無效數(shù)據(jù)，否則多次出現(xiàn)的數(shù)據(jù)值便不能稱之為無效數(shù)據(jù)。而對于有效數(shù)據(jù)，多個有效數(shù)據(jù)對應(yīng)一個數(shù)據(jù)值，難以定量計算，故假設(shè)數(shù)據(jù)量為n，數(shù)據(jù)值為m，有如下等式：

0.1n=0.9m

(1)

則：

n=9m

(2)

推論：每9個數(shù)據(jù)中擁有1個數(shù)據(jù)值，根據(jù)上述證明，數(shù)據(jù)值一般為集中存在于交叉口與交叉口之間，故可確定連續(xù)的間隔，并確定隨機間隔為9。

對于上述選擇的間隔d=9,選取有效數(shù)據(jù)的概率為：

即當你用隨機選取數(shù)據(jù)時，選擇有效數(shù)據(jù)的概率有90%。當數(shù)據(jù)進行替換時有效性將大大高于90%。

4 多路徑問題

4.1 圓形限定數(shù)據(jù)點

上文介紹了對于單路徑數(shù)據(jù)的數(shù)據(jù)，以下給出多路徑的數(shù)據(jù)處理，根據(jù)起點至終點選擇哪部分數(shù)據(jù)進行計算。本文利用余弦定理篩選數(shù)據(jù)，具體篩選過程如下：只選取在源點與終點間圓形區(qū)域內(nèi)的數(shù)據(jù)，將源點與終點連線構(gòu)成直徑，當輸入數(shù)據(jù)時只需判斷三條邊長度平方之間的關(guān)系，當a2+b2-c2<0，那么該點在圓形內(nèi)，當a2+b2-c2>0，那么該點不在圓形內(nèi)，如圖4所示。之所以利用圓進行數(shù)據(jù)選擇，是根據(jù)等周不等式在相同周長情況下，圓形面積最大，選擇數(shù)據(jù)更多，效果更好。

圖4 圓角度圖

4.2 大數(shù)定理與最大流

圖5 岔路模型圖

其公式為：

(3)

又可根據(jù)總流量與出入流量xi、yi的關(guān)系得出：

(4)

證得：

故有：

(5)

圖6 多道路徑模擬圖

輸入起點與終點，利用余弦定理選擇數(shù)據(jù)，分別求出各個節(jié)點之間的段流量，求出該圖的最大流[5]。

5 實驗與討論

5.1 實驗設(shè)置

實驗將所提出的的MG算法與純紅外檢測算法分別在計算復(fù)雜度、空間復(fù)雜度兩個方面做比較。數(shù)據(jù)量分別選擇容易計算的100的倍數(shù)進行計算，分別為100、500、1 000、5 000、10 000。

實驗平臺是64位Windows10操作系統(tǒng)筆記本計算機，內(nèi)存4 GB，CPU 2.5 GHz，實驗語言C++。

本文使用http://www.cs.unibo.it/projects/bolognaringway/所提供的數(shù)據(jù)，對數(shù)據(jù)進行整理，所需數(shù)據(jù)樣表如表1所示。

表1 實驗數(shù)據(jù)樣表

5.2 實驗結(jié)果

對于空間復(fù)雜度，純紅外復(fù)雜度為數(shù)據(jù)集數(shù)據(jù)個數(shù)N，對于本文空間復(fù)雜度為基數(shù)桶容量V。

表2 計算量對比

根據(jù)表2可知，未優(yōu)化的檢測方式與本文方式從計算復(fù)雜度上有較大差距。

5.3 實驗結(jié)果與分析

當數(shù)據(jù)流中的數(shù)據(jù)進行判斷的時候可以說它們服從二項分布(有效數(shù)據(jù)和遠離數(shù)據(jù))。隨機變量x～B(n,p)，對于任意的實數(shù)x，當數(shù)據(jù)量很大時[10]，有：

(6)

即，在大數(shù)情況下二項分布近似服從泊松分布，分布樣圖如圖7所示。

圖7 分布樣圖

在泊松分布的最左端是基數(shù)桶中基數(shù)為[1,2,3,…,9]中的head中最小游標指向的數(shù)，最右端是基數(shù)桶中基數(shù)為[1,2,3,…,9]中的rear中最大游標指向的數(shù)。

本文利用基數(shù)桶中的數(shù)據(jù)計算泊松分布的估計值，利用這個估計值代表這條路徑的動態(tài)流量，X(1),X(2),…,X(N)為服從泊松分布P(λ)的獨立樣本。則：

Ex(k)=λ,k=1,2,3,…,N

(7)

(8)

道路擁堵參數(shù)JAM，即能導(dǎo)致道路擁擠的最大的動態(tài)流量，由城市道路情況設(shè)定。顯然，在一定程度內(nèi)最大流動車流量max_flow越大，道路情況越好，但當max_flow達到某個限制，道路車輛陡增會導(dǎo)致道路擁擠。當max_flow

圖8 變化循環(huán)圖

由此可得出以下實驗結(jié)論：只需比較上一時間段的數(shù)據(jù)即可判斷道路情況，若流量陡降則發(fā)生擁堵；若與上文流量保持均衡，流量平穩(wěn)則不擁堵；若流量均勻下降或者均勻上升道路,情況穩(wěn)定不發(fā)生擁堵；若流量陡增則道路動態(tài)車流量大，則也沒有發(fā)生擁堵。

本文利用基數(shù)桶中所得的期望作為數(shù)據(jù)點計算標準差，利用標準差表示車流量突變情況。

(9)

根據(jù)數(shù)據(jù)的處理，可得如下結(jié)論：

(1) 在數(shù)據(jù)范圍很小的情況下，亦或是在極端情況下，即當線路是一條直線時，最大流接近于紅外接收信息的計數(shù)均值，計算速率快。

(2) 當數(shù)據(jù)范圍很大的情況下，本文數(shù)據(jù)結(jié)構(gòu)保證了數(shù)據(jù)的可靠性，使用的算法在時間亞線性計算速率相比于普通的替換策略算法有明顯優(yōu)勢。

6 結(jié) 語

本文提出的基于亞線性MG-網(wǎng)絡(luò)流算法應(yīng)用于檢測道路路況，對檢測高速動態(tài)車輛有比較好的效果。實驗證明，該算法能夠很好地達到檢測目的，并且對于數(shù)據(jù)，選擇了計算度最低的點數(shù)據(jù)，能夠很好地降低數(shù)據(jù)處理的難度和復(fù)雜度。但不足之處在于：當交通路線過于復(fù)雜，其桶容量不足會導(dǎo)致系統(tǒng)誤差，因此算法在道路錯綜復(fù)雜度過高的情況下，精度不高。