基于車牌識(shí)別系統(tǒng)的卡口可達(dá)性網(wǎng)絡(luò)構(gòu)建

張 杰，王山東，徐志遠(yuǎn)，劉恒瑞

（1.河海大學(xué)地球科學(xué)與工程學(xué)院，江蘇 南京211100）

項(xiàng)目來源：國(guó)家自然科學(xué)基金資助項(xiàng)目（41271538）。

目前,對(duì)交通可達(dá)性的研究日益成熟，但現(xiàn)有的交通可達(dá)性研究中車牌識(shí)別卡口之間的可達(dá)性研究較少。本文從交通可達(dá)性概念出發(fā)，研究車牌識(shí)別卡口之間的可達(dá)性關(guān)系，構(gòu)建車牌識(shí)別卡口可達(dá)性網(wǎng)絡(luò)［1］。

A*算法作為一種啟發(fā)式算法［2］，在最短路徑搜索中有著重要的應(yīng)用［3］。本文以雙向搜索的A*算法為基礎(chǔ)［4］，針對(duì)在卡口可達(dá)性網(wǎng)絡(luò)構(gòu)建中遇到的問題對(duì)A*算法進(jìn)行改進(jìn)，用于計(jì)算卡口間的可達(dá)關(guān)系，構(gòu)建可達(dá)性網(wǎng)絡(luò)。

1 卡口可達(dá)性網(wǎng)絡(luò)與改進(jìn)的A*算法

1.1 車牌識(shí)別系統(tǒng)

車牌識(shí)別系統(tǒng)在城市安全管理中有著重要的作用［5］，為了城市的安全管理，需要在城市重要的卡口裝有車牌識(shí)別系統(tǒng)。同時(shí)，為了節(jié)約車牌識(shí)別系統(tǒng)的布設(shè)成本、避免數(shù)據(jù)冗余，不可能對(duì)所有的流向?qū)嵤┎荚O(shè)監(jiān)控，實(shí)際布設(shè)方案的目標(biāo)是用最少的車牌識(shí)別系統(tǒng)獲取路網(wǎng)中盡可能完備的交通信息。

對(duì)于每一條路段，車牌識(shí)別系統(tǒng)可以布設(shè)為監(jiān)控所有駛?cè)牖蝰偝鲈撀范蔚能囕v信息，同時(shí)，車牌識(shí)別系統(tǒng)可以對(duì)道路卡口進(jìn)行多流向監(jiān)控，每一個(gè)交通治安卡口的多個(gè)流向，如十字路口的八個(gè)流向均可布設(shè)車牌識(shí)別系統(tǒng)，如圖1所示。因此，車牌識(shí)別系統(tǒng)的監(jiān)控是一種基于流向的監(jiān)控, 可達(dá)性網(wǎng)絡(luò)為有向圖。因此，在進(jìn)行可達(dá)性網(wǎng)絡(luò)構(gòu)建之前，需要先確認(rèn)城市車牌識(shí)別系統(tǒng)的布設(shè)方案。

1.2 卡口可達(dá)性網(wǎng)絡(luò)

本文將卡口之間的可達(dá)關(guān)系分為直接可達(dá)關(guān)系、唯一直接可達(dá)關(guān)系和非直接可達(dá)關(guān)系，將可達(dá)性網(wǎng)絡(luò)分為直接可達(dá)網(wǎng)絡(luò)和唯一直接可達(dá)網(wǎng)絡(luò)。

圖1 基于流向布設(shè)的車牌識(shí)別系統(tǒng)

設(shè)兩個(gè)車牌識(shí)別卡口為C1、C2，若其間存在一條路徑P，使得C1從任意方向能夠不通過其他任何卡口到C2，則P稱為直接可達(dá)路徑，稱C1、C2存在直接可達(dá)關(guān)系；若其間有且僅有一條路徑P，使得C1從任意方向能夠不通過其他任何卡口到C2，則P稱為唯一直接可達(dá)路徑，稱C1、C2存在唯一直接可達(dá)關(guān)系；若其間不存在任何一條路徑，使得C1能夠不通過其他任何卡口到達(dá)C2，則稱C1、C2之間為非直接可達(dá)關(guān)系。

一個(gè)有序的二元組

1.3 問題提出

卡口可達(dá)性網(wǎng)絡(luò)構(gòu)建的核心在于判斷兩個(gè)車牌識(shí)別卡口之間的直接可達(dá)關(guān)系和唯一直接可達(dá)關(guān)系，即直接可達(dá)路徑的存在性及唯一性。從本質(zhì)上看，直接可達(dá)路徑的求解相當(dāng)于最短路徑問題，在道路網(wǎng)絡(luò)中確定起點(diǎn)、終點(diǎn)、道路及約束條件，尋找起訖點(diǎn)間符合約束條件的路徑，因此兩個(gè)車牌識(shí)別卡口間的直接可達(dá)路徑可以借助最短路徑算法求解。

由于直接可達(dá)路徑搜索是在兩個(gè)車牌識(shí)別卡口之間進(jìn)行的，基本元素為卡口邊，并非單一的道路結(jié)點(diǎn)，所以考慮將最短路徑算法中輸入和搜索過程中的結(jié)點(diǎn)均轉(zhuǎn)換為邊的形式。同時(shí)，起訖卡口均為具有方向的邊，起始卡口監(jiān)控多個(gè)駛出方向，任何一個(gè)方向均可能與目標(biāo)卡口存在直接可達(dá)路徑，因此計(jì)算之前需要根據(jù)車道明確起始卡口的駛出方向，而目標(biāo)卡口的監(jiān)控方向即為車輛的駛?cè)敕较?。圖2為車牌識(shí)別卡口C1分別作為起始卡口和目標(biāo)卡口時(shí)車輛的駛出方向與駛?cè)敕较颉?/p>

圖2 起始卡口和目標(biāo)卡口方向示意圖

這樣，直接可達(dá)路徑的求解問題就轉(zhuǎn)變成了以起始卡口及駛出方向?yàn)槠瘘c(diǎn)、目標(biāo)卡口為終點(diǎn)，城市道路網(wǎng)絡(luò)為載體，除起訖卡口外其余所有卡口作為障礙物約束條件下，起始卡口與目標(biāo)卡口之間的路徑規(guī)劃問題。

1.4 改進(jìn)的A*算法

由于卡口可達(dá)性網(wǎng)絡(luò)構(gòu)建的核心是車牌識(shí)別卡口之間直接可達(dá)路徑的存在性，并非嚴(yán)格的最短路徑，即計(jì)算精度要求不高；但針對(duì)所有車牌識(shí)別卡口各個(gè)可能的駛出方向，均要對(duì)其余所有卡口進(jìn)行直接可達(dá)路徑的計(jì)算，對(duì)于復(fù)雜的道路網(wǎng)絡(luò)以及密集布設(shè)的車牌識(shí)別卡口，計(jì)算量仍舊龐大，需要對(duì)問題求解的效率進(jìn)行考慮。

本文采用改進(jìn)的A*算法為基礎(chǔ)，應(yīng)用到直接可達(dá)路徑的求解問題中。針對(duì)卡口可達(dá)性網(wǎng)絡(luò)構(gòu)建中遇到的問題對(duì)基礎(chǔ)算法進(jìn)行改進(jìn)，用于計(jì)算卡口間的可達(dá)關(guān)系。算法的改進(jìn)思想如下：①以圖數(shù)據(jù)結(jié)構(gòu)中的有向邊而非結(jié)點(diǎn)作為輸入元素，采用兩條有向邊末端端點(diǎn)計(jì)算啟發(fā)式距離；若結(jié)點(diǎn)搜索過程中遇到車牌識(shí)別卡口邊形成的障礙邊，則跳過繼續(xù)運(yùn)行，即直接可達(dá)路徑不能經(jīng)過其他卡口；②由于判斷直接可達(dá)路徑存在性的同時(shí)，需要判斷路徑的數(shù)量，即直接可達(dá)關(guān)系是否為唯一直接可達(dá)關(guān)系，所以在尋找到目標(biāo)卡口后將路徑存儲(chǔ)至路徑庫(kù)，算法繼續(xù)運(yùn)行，以開放列表是否為空作為算法的終止條件；③算法結(jié)束時(shí)若路徑庫(kù)為空，則尋徑失敗，起訖卡口間為非直接可達(dá)關(guān)系；若路徑庫(kù)中存在唯一路徑，則起訖卡口間為唯一直接可達(dá)關(guān)系；若路徑庫(kù)中存在多條路徑，則起訖卡口間為直接可達(dá)但非唯一直接可達(dá)關(guān)系。

改進(jìn)的A*算法執(zhí)行步驟如下：

1）初始化，確定起始卡口S=(i, j)和駛出方向，終點(diǎn)卡口T=(u,v)，將起始卡口加入開放列表并計(jì)算代價(jià)估值F(S)=G(j)+H(j)，設(shè)置父邊p(S)為空。

2）邊選擇，尋找開放列表中代價(jià)估計(jì)值F最小的有向邊C，彈出作為當(dāng)前邊。

3）判斷C=T是否成立，若成立，則將尋找到的路徑、距離、到達(dá)時(shí)間等存入路徑庫(kù)，轉(zhuǎn)到步驟7），否則轉(zhuǎn)到步驟4）。

4）將C加入關(guān)閉列表，檢查C的每條相鄰邊N，若N在關(guān)閉列表中為障礙物邊，則跳過；若N不在開放列表中，則轉(zhuǎn)向步驟5）；若N已在開放列表中，則轉(zhuǎn)向步驟6）。

5）將N加入開放列表，并設(shè)置父邊p(N)=C，計(jì)算代價(jià)估值F(N)。

6）邊松弛，對(duì)有向邊N進(jìn)行松弛，即判斷G(C)+w(N)

7）若開放列表為空，輸出路徑庫(kù)并判斷起訖卡口間的可達(dá)關(guān)系，算法結(jié)束，否則轉(zhuǎn)向步驟2）。

2 可達(dá)性網(wǎng)絡(luò)構(gòu)建實(shí)例分析

以馬鞍山市道路網(wǎng)絡(luò)為例，針對(duì)每一個(gè)車牌識(shí)別卡口及可能的行駛方向，分別以其作為起始卡口，將其余卡口分別作為目標(biāo)卡口，采用改進(jìn)的A*算法計(jì)算兩個(gè)卡口之間的可達(dá)關(guān)系；將所有存在直接可達(dá)關(guān)系和唯一直接可達(dá)關(guān)系的車牌識(shí)別卡口組合，以道路網(wǎng)絡(luò)中所有車牌識(shí)別卡口為結(jié)點(diǎn)，以卡口間的可達(dá)關(guān)系為邊，構(gòu)建卡口的直接可達(dá)網(wǎng)絡(luò)和唯一直接可達(dá)網(wǎng)絡(luò)。圖3為馬鞍山市道路網(wǎng)絡(luò)模型及車牌識(shí)別系統(tǒng)布設(shè)方案，結(jié)點(diǎn)代表道路交叉口結(jié)點(diǎn)，結(jié)點(diǎn)間的連線代表有向路段，箭頭代表該流向路段為布設(shè)有車牌識(shí)別系統(tǒng)的卡口，示例路網(wǎng)中共布設(shè)有17個(gè)流向的車牌識(shí)別系統(tǒng)。

圖3 道路網(wǎng)絡(luò)模型及車牌識(shí)別系統(tǒng)布設(shè)方案

從圖4中可以看出，39號(hào)卡口與35號(hào)卡口為直接可達(dá)關(guān)系，且存在多條路徑使兩個(gè)卡口直接可達(dá)；39號(hào)卡口與25號(hào)卡口為唯一直接可達(dá)關(guān)系，只存在一條路徑{23,24,11,6｝使得兩個(gè)卡口直接可達(dá)，如圖5所示。

圖4 直接可達(dá)關(guān)系

圖5 唯一直接可達(dá)關(guān)系

車牌識(shí)別卡口直接可達(dá)網(wǎng)絡(luò)如圖6所示，唯一直接可達(dá)網(wǎng)絡(luò)如圖7所示，從中可以看出任意卡口之間的可達(dá)關(guān)系，如39號(hào)卡口是路網(wǎng)的入口點(diǎn)，只能作為可達(dá)關(guān)系中的起始卡口而無法作為目標(biāo)卡口。唯一直接可達(dá)網(wǎng)絡(luò)是直接可達(dá)網(wǎng)絡(luò)的子圖，存在唯一直接可達(dá)關(guān)系的卡口之間能夠用于重建確定性的車輛軌跡。從圖中可以看出，唯一直接可達(dá)關(guān)系的數(shù)量要遠(yuǎn)小于直接可達(dá)關(guān)系。

圖6 直接可達(dá)網(wǎng)絡(luò)

圖7 唯一直接可達(dá)網(wǎng)絡(luò)

3 結(jié) 語(yǔ)

本文從交通可達(dá)性概念出發(fā)研究卡口可達(dá)性，將卡口可達(dá)性網(wǎng)絡(luò)分為直接可達(dá)性網(wǎng)絡(luò)和唯一直接可達(dá)性網(wǎng)絡(luò)。對(duì)計(jì)算最短路徑的A*算法進(jìn)行改進(jìn)，在城市道路網(wǎng)絡(luò)和車牌識(shí)別系統(tǒng)布設(shè)方案的基礎(chǔ)上，用于計(jì)算卡口間的可達(dá)關(guān)系，構(gòu)建城市車牌識(shí)別卡口可達(dá)性網(wǎng)絡(luò)，對(duì)卡口車輛數(shù)據(jù)的深度挖掘有一定的意義。

[1] 約翰斯頓 R J． 人文地理學(xué)詞典[M]．北京: 商務(wù)印書館, 2004

[2] 張海濤, 程蔭杭． 基于A*算法的全局路徑搜索[J]．微計(jì)算機(jī)信息,2007,23(17):238-239

[3] 劉浩,鮑遠(yuǎn)律． A*算法在矢量地圖最優(yōu)路徑搜索中的應(yīng)用[J]．計(jì)算機(jī)仿真,2008(4):253-257

[4] 孟慶浩,劉大維． 基于雙向A*算法的自主車全局路徑規(guī)劃[J]．天津大學(xué)學(xué)報(bào):自然科學(xué)與工程技術(shù)版, 1998(6):747-751

[5] 黃健敏．淺談我國(guó)目前車牌識(shí)別系統(tǒng)的應(yīng)用研究[J]．山東工業(yè)技術(shù), 2016(1):214-214