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

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

0 引 言

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

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

本文的主要貢獻(xiàn)如下：

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

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

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

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

1 相關(guān)工作

1.1 ViBe算法檢測(cè)路況

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

1.2 紅外檢測(cè)路況

當(dāng)前普通的基于紅外的道路檢測(cè)系統(tǒng)，利用脈沖進(jìn)行簡(jiǎn)單計(jì)數(shù)，由采集模塊、交通燈控制模塊和模擬控制中心。基本上完成了車流量檢測(cè)的功能，但并未對(duì)其中收獲的數(shù)據(jù)進(jìn)行簡(jiǎn)化和計(jì)算，難以保證數(shù)據(jù)的準(zhǔn)確性，失去了數(shù)據(jù)的意義。

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

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

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

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

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

3 亞線性替換算法

3.1 基數(shù)桶

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

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

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

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

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

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

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

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

3.2 隨機(jī)化與改進(jìn)MG替換算法

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

(1) 道路是單向的。

(2) 道路沒有交叉口。

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

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

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

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

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

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

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

1 While in[]!=empty:

2 i=0;

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

4 i++;

5 cardinal←in[i*9+s]所對(duì)應(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) 對(duì)于上述算法，由于關(guān)鍵在于隨機(jī)選取的間隔d應(yīng)對(duì)于具體問題具體分析，由于隨機(jī)化，算法的時(shí)間復(fù)雜度嚴(yán)格小于數(shù)據(jù)量n，計(jì)算復(fù)雜度只與基數(shù)桶中的數(shù)量有關(guān)，故替換算法是時(shí)間亞線性的。

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

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

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

0.1n=0.9m

(1)

則：

n=9m

(2)

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

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

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

4 多路徑問題

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

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

圖4 圓角度圖

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

圖5 岔路模型圖

其公式為：

(3)

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

(4)

證得：

故有：

(5)

圖6 多道路徑模擬圖

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

5 實(shí)驗(yàn)與討論

5.1 實(shí)驗(yàn)設(shè)置

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

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

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

表1 實(shí)驗(yàn)數(shù)據(jù)樣表

5.2 實(shí)驗(yàn)結(jié)果

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

表2 計(jì)算量對(duì)比

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

5.3 實(shí)驗(yàn)結(jié)果與分析

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

(6)

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

圖7 分布樣圖

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

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

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

(7)

(8)

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

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

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

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

(9)

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

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

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

6 結(jié) 語(yǔ)

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