序論：寫(xiě)作是一種深度的自我表達(dá)。它要求我們深入探索自己的思想和情感，挖掘那些隱藏在內(nèi)心深處的真相，好投稿為您帶來(lái)了七篇匹配算法論文范文，愿它們成為您寫(xiě)作過(guò)程中的靈感催化劑，助力您的創(chuàng)作。

篇(1)

【關(guān)鍵詞】藏文分詞 匹配算法 哈希表 詞典機(jī)制

1 引言

藏文信息處理存在著分詞的問(wèn)題，而藏文分詞是對(duì)藏文詞性標(biāo)注、藏語(yǔ)音合成、機(jī)器翻譯、大型語(yǔ)料庫(kù)建設(shè)和信息檢索等藏文信息處理的基礎(chǔ)。藏文分詞的效果會(huì)對(duì)進(jìn)一步研究的藏文詞性標(biāo)注、藏語(yǔ)音合成、機(jī)器翻譯、大型語(yǔ)料庫(kù)建設(shè)和信息檢索等藏文信息處理軟件的性能和效果產(chǎn)生影響。

為了提高分詞的準(zhǔn)確率，需要有一個(gè)足夠大的詞庫(kù)，面對(duì)足夠大的詞庫(kù)，對(duì)詞庫(kù)中的詞語(yǔ)的搜索技術(shù)就顯得十分重要，對(duì)詞庫(kù)中詞語(yǔ)的搜索速度直接關(guān)系到分詞系統(tǒng)的性能。詞庫(kù)目前主要是采用索引的機(jī)制來(lái)實(shí)現(xiàn)的，一般用到的索引結(jié)構(gòu)的包括線性索引、倒排表、Trie樹(shù)、二叉樹(shù)等。線性索引、倒排表都是靜態(tài)的索引結(jié)構(gòu)，不利于插入、刪除等操作。

2 分詞

2.1 詞典機(jī)制算法

本系統(tǒng)采用的是基于Hash索引的分詞詞典。分詞詞典機(jī)制可以看作包含三個(gè)部分：首字Hash表、詞索引表、詞典正文。詞典正文是以詞為單位txt文件，匹配過(guò)程是一個(gè)全詞匹配的過(guò)程。首先，通過(guò)首字Hash表確定該詞在詞典中的大概位置，然后根據(jù)詞索引表進(jìn)行定位，進(jìn)而找到在詞典正文中的具置。該系統(tǒng)是采用Myeclipse10平臺(tái)，使用Java語(yǔ)言進(jìn)行實(shí)現(xiàn)的，直接調(diào)用Java里的hashmap創(chuàng)建函數(shù)，找到該詞之后，然后進(jìn)行字符串匹配。

2.2 基于匹配算法分詞

主流的分詞方法有三種：分別為基于語(yǔ)言學(xué)規(guī)則的方法、基于大規(guī)模語(yǔ)料庫(kù)的機(jī)器學(xué)習(xí)方法、基于規(guī)則與統(tǒng)計(jì)相結(jié)合的方法，鑒于目前藏文方面還沒(méi)有超大型的句子語(yǔ)料庫(kù)。該系統(tǒng)便采用了基于語(yǔ)言學(xué)規(guī)則的根據(jù)詞典進(jìn)行匹配的方法對(duì)藏文進(jìn)行分詞。

根據(jù)匹配的方向不同，分為正向和逆向兩種匹配算法。本系統(tǒng)采用的是正逆向匹配算法相結(jié)合的減字匹配法對(duì)藏文進(jìn)行分詞的，因?yàn)椴匚脑诿總€(gè)字的結(jié)束時(shí)，都會(huì)以“”作為分界；每個(gè)句子會(huì)以“”或者“” 作為分界。因此，對(duì)藏文進(jìn)行分詞的減字算法首先以藏文的字符“”或者“”切分出句子，如此一來(lái)，原文就被分為相應(yīng)的若干個(gè)句子了。接下來(lái)，再對(duì)每一個(gè)句子進(jìn)行詞典的匹配，如果沒(méi)有匹配成功就根據(jù)藏文字符中“”從句末尾減去一個(gè)字符，然后再次進(jìn)行匹配，直到匹配成功為止。對(duì)每個(gè)句子重復(fù)這些流程，直到每個(gè)句子全部分解為詞為止。逆向最大匹配是從句子的末尾選擇計(jì)算最大詞的長(zhǎng)度，從后往前匹配、切分，其基本原理是和正向最大匹配的原理是相同的。

為了提高切分的精度，該系統(tǒng)使用的是正向最大匹配和逆向最大匹配相結(jié)合的方法進(jìn)行分詞，先分別采用兩種方法分詞，然后根據(jù)概率比較兩種分詞結(jié)果，選擇概率較大的那種匹配算法作為分詞結(jié)果。

本系統(tǒng)的逆向最大匹配和正向最大匹配均是采用減字匹配算法，減字算法實(shí)現(xiàn)簡(jiǎn)單，切分效果也比較理想，流程如圖1所示。

正向最大匹配（MM） 對(duì)于文本中的字串 ABCD，ABCD？W，若ABC∈W，并且AB∈W，然后再判別CD是否屬于W，若是，則就切分為AB/CD，如果不是，則切分為AB/C/D。其中W 為分詞的詞典。逆向最大匹配對(duì)于文本中的字串 ABCD，ABCD？W，BCD？W，CD∈W，并且AB∈W，其中W為分詞的詞典，那么就取切分 AB/CD，根據(jù)藏文詞組最長(zhǎng)的為6個(gè)字符組成的，所以進(jìn)行匹配算法的時(shí)候，初始化藏文最大字符串長(zhǎng)度為6，流程圖如圖2所示。而逆向最大匹配算法是從句子的末尾開(kāi)始進(jìn)行匹配，其核心算法與正向最大匹配算法相同，只不過(guò)開(kāi)始匹配的方向不同而已。

無(wú)論是正向匹配（MM）算法還是逆向匹配（RMM）算法都會(huì)產(chǎn)生大量的歧義字段。我們很容易舉出這樣的例子，如：（五十六個(gè)民族心連心）這一句藏語(yǔ)，采用正向匹配算法分詞的結(jié)果為：，采用逆向匹配算法的分詞結(jié)果為：，在采用逆向匹配的時(shí)候，將會(huì)被劃分為，而（五十六）實(shí)際是一個(gè)詞，不該劃分，諸如此類(lèi)的藏文句子還有很多，例如 等，無(wú)論使用正向最大匹配算法或者使用逆向最大匹配算法都會(huì)產(chǎn)生歧義，這種歧義稱(chēng)為組合歧義。為了減少這種歧義的影響，本系統(tǒng)使用兩種分詞方法相結(jié)合的方式。首先分別使用兩種算法進(jìn)行分詞，然后通過(guò)統(tǒng)計(jì)的方法消除部分歧義。具體實(shí)現(xiàn)為：設(shè)正向最大匹配算法所切分的n個(gè)詞分別為，則這個(gè)句子切分的頻率則為；設(shè)逆向最大匹配算法所切分的n個(gè)詞分別為，則這個(gè)句子切分的頻率則為。如果，則選擇正向最大匹配算法所切分的結(jié)果，反之，則選擇逆向最大匹配算法所切分的結(jié)果。

3 結(jié)果和分析

結(jié)合26個(gè)大小不同的實(shí)驗(yàn)文本，對(duì)基于哈希表索引和匹配算法的分詞系統(tǒng)的準(zhǔn)確率進(jìn)行了分析，準(zhǔn)確率如圖3所示。結(jié)果顯示，該分詞系統(tǒng)的準(zhǔn)確率在92%以上。由此可得基于哈希表索引和匹配算法的分詞系統(tǒng)在準(zhǔn)確率上有不錯(cuò)的效果。

參考文獻(xiàn)

[1]華卻才讓.基于樹(shù)到串藏語(yǔ)機(jī)器翻譯若干關(guān)鍵技術(shù)研究[D].陜西師范大學(xué)，2014.

[2]石方夏，邱瑞，張|，任帥.藏文信息隱藏技術(shù)綜述[J].物聯(lián)網(wǎng)技術(shù)，2014，12：28-32.

[3]王思力，張華平，王斌.雙數(shù)組Trie樹(shù)算法優(yōu)化及其應(yīng)用研究[J].中文信息學(xué)報(bào)，2006，05：24-30.

[4]陳碩，桂騰葉，周張穎等.信息檢索在論文寫(xiě)作和項(xiàng)目申報(bào)中的應(yīng)用[J].科技展望，2015，13：274-275.

[5]黃昌寧，趙海.中文分詞十年回顧[J]. 中文信息學(xué)報(bào)，2007，03：8-19.

[6]奉國(guó)和，鄭偉.國(guó)內(nèi)中文自動(dòng)分詞技術(shù)研究綜述[J].圖書(shū)情報(bào)工作，2011，02：41-45.

[7]賀艷艷.基于詞表結(jié)構(gòu)的中文分詞算法研究[D].中國(guó)地質(zhì)大學(xué)（北京），2007.

[8]戴上靜，石春，吳剛.中文分詞中的正向增字最大匹配算法研究[J].微型機(jī)與應(yīng)用，2014，17：15-18.

[9]劉遙峰，王志良，王傳經(jīng).中文分詞和詞性標(biāo)注模型[J].計(jì)算機(jī)工程，2010，04：17-19.

作者簡(jiǎn)介

陳碩（1995-），男，自治區(qū)拉薩市人。本科在讀，主研領(lǐng)域?yàn)樽匀徽Z(yǔ)言處理，數(shù)學(xué)建模及其應(yīng)用。

周歡歡（1994-），女，湖南省衡陽(yáng)市人。本科在讀，研究方向?yàn)閿?shù)學(xué)建模及其應(yīng)用、交通運(yùn)輸規(guī)劃與管理。

通訊作者簡(jiǎn)介

趙棟材（1976-），男，現(xiàn)為大學(xué)藏文信息技術(shù)研究中心副教授。主要研究方向?yàn)椴匚男畔⑻幚怼?/p>

作者單位

篇(2)

關(guān)鍵詞：入侵檢測(cè)；KMP算法；BM算法；RK算法；AC算法；AC－BM算法

中圖分類(lèi)號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：1004 373X(2009)02 063 05

Application of Pattern Matching Algorithm in Intrusion Detection Technique

RAN Zhanjun1,YAO Quanzhu2,WANG Xiaofeng1,ZOU Youjiao1

(1.Xi′an University of Technology,Xi′an,710054,China;2.College of Computer Science and Engineering,Xi′an Unversity of Technology,Xi′an,710048,China)

Abstract：Relying solely on traditional passive defense technology has been unable to meet today′s network security needs,IDS based on pattern－matching is becoming a hotspot of research and application,the efficiency of pattern matching determines the performance of this kind of IDS.A survey of the intrusion detection system classic pattern matching algorithm is given in this paper,including single pattern matching algorithm:KMP algorithm,BM algorithm,RK algorithm and multi－pattern matching algorithm －AC algorithm,AC－BM algorithm.Meanwhile,the efficiency of various algorithms is summarized.Through analysis of algorithms,future research directions of this kind of algorithm are advanced.

Keywords：intrusion detection;KMP algorithm;BM algorithm;RK algorithm;AC algorithm;AC－BM algorithm

0 引 言

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，各種基于網(wǎng)絡(luò)的應(yīng)用層出不窮。面對(duì)日益突出的網(wǎng)絡(luò)安全問(wèn)題，僅靠傳統(tǒng)的被動(dòng)防御已經(jīng)不能滿足要求，能夠主動(dòng)檢測(cè)并預(yù)防的入侵檢測(cè)系統(tǒng)應(yīng)運(yùn)而生。

根據(jù)采用的分析方法，入侵檢測(cè)分為誤用檢測(cè)和異常檢測(cè)。誤用檢測(cè)是指：根據(jù)己知的攻擊方法，預(yù)先定義入侵特征，通過(guò)判斷這此特征是否出現(xiàn)來(lái)完成檢測(cè)任務(wù)。異常檢測(cè)是指：根據(jù)用戶的行為或資源的使用狀況的正常程度來(lái)判斷是否屬于入侵。由于異常檢測(cè)的誤檢率和漏檢率高，因此目前大多數(shù)入侵檢測(cè)系統(tǒng)產(chǎn)品均主要采用誤用檢測(cè)的方法。誤用檢測(cè)中使用的檢測(cè)技術(shù)主要有: 模式匹配、專(zhuān)家系統(tǒng)、狀態(tài)轉(zhuǎn)移等，其中模式匹配原理簡(jiǎn)單，可擴(kuò)展性好，而且最為常用。據(jù)統(tǒng)計(jì)，現(xiàn)在大約95%的入侵檢測(cè)都是特征匹配的入侵檢測(cè)。

由此可見(jiàn)，模式匹配算法性能的好壞直接影響到入侵檢測(cè)系統(tǒng)的效率。隨著網(wǎng)絡(luò)傳輸速度的大幅度提高，入侵檢測(cè)系統(tǒng)需要處理的數(shù)據(jù)量越來(lái)越大，如果模式匹配算法來(lái)不及處理這些實(shí)時(shí)的大量的數(shù)據(jù)包，必然會(huì)丟棄部分?jǐn)?shù)據(jù)包，而這些被丟棄的數(shù)據(jù)包中很可能就包含有入侵信息，從而造成漏報(bào)。在此介紹幾種著名的用于入侵檢測(cè)的模式匹配算法，包括單模式匹配算法和多模式匹配算法，通過(guò)對(duì)它們進(jìn)行剖析和實(shí)際測(cè)試，提出入侵檢測(cè)系統(tǒng)中模式匹配算法的選擇策略和未來(lái)的研究方向。

1 單模式匹配算法

1.1 相關(guān)定義

模式匹配：是指在給定長(zhǎng)度為n的目標(biāo)串T=T1T2…Tn中查找長(zhǎng)度為m的模式串P=P1P2…Pm的首次出現(xiàn)或多次出現(xiàn)的過(guò)程。這里Ti(1≤i≤n)，

Pj(1≤j≤m)∈∑(字符集)，若P在T中出現(xiàn)1次或多次，則稱(chēng)匹配成功，否則稱(chēng)匹配失敗。

單模式匹配算法：在目標(biāo)串中1次只能對(duì)1個(gè)模式串進(jìn)行匹配的算法。

多模式匹配算法：在目標(biāo)串中可同時(shí)對(duì)多個(gè)模式串進(jìn)行匹配的算法。

最簡(jiǎn)單的模式匹配算法是Brute－Force算法(BF算法)。在BF算法的目標(biāo)串和模式串的字符比較中，只要有1個(gè)字符不相等，而不管前面已有多少個(gè)字符相等，就需要把目標(biāo)串T回退，下次比較時(shí)目標(biāo)串T只后移1個(gè)字符。雖然算法簡(jiǎn)單，但效率低下，不適合用于入侵檢測(cè)系統(tǒng)中，不做重點(diǎn)介紹。

高效的模式匹配算法都是設(shè)法增大不匹配時(shí)目標(biāo)串T或模式串P之間的偏移量，以減少總的比較次數(shù)。下面介紹3種經(jīng)典的快速單模式匹配算法。

1.2 KMP算法

1970年，S.A.Cook從理論上證明了一維模式匹配問(wèn)題可以在O(m+n)時(shí)間內(nèi)解決［1］。D.E.Knuth，V.R.Pratt和T.H.Morris 在BF算法的基礎(chǔ)上提出了一種快速模式匹配算法，稱(chēng)為KMP算法［1］，該算法消除了BF算法的目標(biāo)串指針在相當(dāng)多個(gè)字符比較相等后，只要有1個(gè)字符比較不等便需要回溯的缺點(diǎn)，使算法的效率得到了大幅度提高，時(shí)間復(fù)雜度達(dá)到最理想的O(m+n)，空間復(fù)雜度是O(m)。

KMP算法的基本思想是：若某趟匹配過(guò)程中Ti和Pj不匹配，而前j-1個(gè)字符已經(jīng)匹配。此時(shí)只需右移模式串P，目標(biāo)串T不動(dòng)，即指針i不回溯，讓Pk與Ti繼續(xù)比較。移動(dòng)后重新開(kāi)始比較的位置k僅與模式串P有關(guān)，而與目標(biāo)串T無(wú)關(guān)，因此k可以通過(guò)下面的next函數(shù)事先確定。

定義next［j］函數(shù)為：

next［j］=max{k|1＜k＜j且 P1P2…Pk=

Pj-kPj-k+2…Pj-1} ，集合非空

0，其他情況

-1(標(biāo)記)，j=0時(shí)

1.3 BM算法

相對(duì)于BF算法，KMP算法雖然消除了主串指針的回溯，在不匹配時(shí)能使模式串右滑若干位，但由上述next函數(shù)可知：右滑的最大距離不會(huì)超過(guò)1趟匹配操作所進(jìn)了的比較次數(shù)j，原因在于KMP算法的匹配操作是從左到右進(jìn)行的。受到KMP算法的啟發(fā)，R.S.Boyer和J.S.Moore提出一種新的快速字符串匹配算法－BM算法［1－3］。

BM算法基本思想是：開(kāi)始時(shí)將目標(biāo)串T與模式串P左對(duì)齊，自右至左逐個(gè)字符進(jìn)行比較(即首先比較Pm與Tm)；當(dāng)某趟比較時(shí)Ti與模式串的對(duì)應(yīng)字符不匹配，則把模式串右滑d(x)一段距離，執(zhí)行由Pm與Ti+d(x)起始的自右至左的匹配檢查。BM算法采用以下兩條規(guī)則計(jì)算模式串右移的距離：

(3) g是轉(zhuǎn)移函數(shù)，該函數(shù)定義如下：g(s,a)：從當(dāng)前狀態(tài)s開(kāi)始，沿著邊上標(biāo)簽為a的路徑所到的狀態(tài)。假如(u,v )邊上的標(biāo)簽為a，那么g ( u,a ) =v；如果根節(jié)點(diǎn)上出來(lái)的邊上的標(biāo)簽沒(méi)有a，則g(0,a) =0，即如果沒(méi)有匹配的字符出現(xiàn)，自動(dòng)機(jī)停留在初態(tài)；

(4) f(不匹配時(shí)自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)移)也是轉(zhuǎn)移函數(shù)，該函數(shù)定義如下：

f(s)：當(dāng)w是L(s)最長(zhǎng)真后綴并且w是某個(gè)模式的前綴，那么f(s)就是以w為標(biāo)簽的那個(gè)節(jié)點(diǎn)；

(5) q0∈Q是初態(tài)(根節(jié)點(diǎn)，標(biāo)識(shí)符為0)；

(6) FQ，是終態(tài)集(以模式為標(biāo)簽的節(jié)點(diǎn)集)。

這樣，在目標(biāo)串中查找模式的過(guò)程轉(zhuǎn)化成在模式樹(shù)中的查找過(guò)程。查找一個(gè)串T時(shí)從模式樹(shù)的根節(jié)點(diǎn)開(kāi)始，沿著以T中字符為標(biāo)簽的路徑往下走：若自動(dòng)機(jī)能夠抵達(dá)終態(tài)v，則說(shuō)明T中存在模式L (v)；否則不存在模式。

AC算法模式匹配的時(shí)間復(fù)雜度是O(n)，并且與模式集中模式串的個(gè)數(shù)和每個(gè)模式串的長(zhǎng)度無(wú)關(guān)。無(wú)論模式串P是否出現(xiàn)在目標(biāo)串T中，T中的每個(gè)字符都必須輸入狀態(tài)機(jī)中，所以無(wú)論是最好情況還是最壞情況，AC算法模式匹配的時(shí)間復(fù)雜度都是O(n)，包括預(yù)處理時(shí)間在內(nèi)，AC算法總時(shí)間復(fù)雜度是O(M+n)，其中M為所有模式串的長(zhǎng)度總和。

2.3 AC－BM算法

對(duì)多模式串的匹配而言，雖然AC算法比BM算法高效得多，但AC算法必須逐一查看目標(biāo)串的每個(gè)字符，即必須按順序輸入，不能實(shí)現(xiàn)跳躍，而B(niǎo)M算法則能夠利用“右滑”跳過(guò)目標(biāo)串中的大段字符，從而提高搜索速度。如果將BM算法的這種啟發(fā)式搜索技術(shù)應(yīng)用到AC算法中，則可大大提高多模式匹配算法的效率。許多人據(jù)此給出了各種改進(jìn)的算法。Commentz－Walter最先將BM算法和AC算法結(jié)合在一起給出了Commentz－Walter算法；Baeza－Yates結(jié)合BMP算法和AC算法也給出了多模式匹配改進(jìn)算法。

AC－BM算法［5］是Jang－Jong在1993年結(jié)合AC算法的有限自動(dòng)機(jī)和BM算法的連續(xù)跳躍思想提出來(lái)的新算法，利用劣勢(shì)移動(dòng)表和優(yōu)勢(shì)跳轉(zhuǎn)表來(lái)實(shí)現(xiàn)跳躍式地并行搜索，算法的時(shí)間復(fù)雜度為O(mn)。

該算法的思想是：首先把要查找的多個(gè)模式構(gòu)成一個(gè)關(guān)鍵字樹(shù)，把相同的前綴作為樹(shù)的根節(jié)點(diǎn)。模式樹(shù)從目標(biāo)串的右端向左移動(dòng)，一旦模式樹(shù)確定在適當(dāng)?shù)奈恢茫址容^從左向右開(kāi)始進(jìn)行。模式樹(shù)移動(dòng)時(shí)同時(shí)使用壞字符移動(dòng)和好前綴移動(dòng)。壞字符移動(dòng)的策略為:如果出現(xiàn)不匹配的情況，移動(dòng)模式樹(shù)，使得樹(shù)中其他模式的能與當(dāng)前目標(biāo)串正在比較的字符相匹配的那個(gè)字符移動(dòng)到與當(dāng)前目標(biāo)串正在比較的字符的相同位置上，如果在當(dāng)前的深度上，目標(biāo)字符沒(méi)有出現(xiàn)在任何模式中，則模式樹(shù)的偏移量為樹(shù)中最短模式的長(zhǎng)度。好前綴移動(dòng)的移動(dòng)策略為：將模式樹(shù)移動(dòng)到一個(gè)已被發(fā)現(xiàn)是另一個(gè)模式子串完全前綴的下一個(gè)位置，或者移動(dòng)到作為樹(shù)中另一個(gè)模式后綴能夠正確匹配目標(biāo)串的某個(gè)前綴的下一個(gè)位置。在模式樹(shù)的移動(dòng)過(guò)程中，必須確保模式樹(shù)的偏移量不能大于樹(shù)中最短的模式長(zhǎng)度。

2.4 AC，AC－BM算法改進(jìn)情況簡(jiǎn)介

文獻(xiàn)［10］中盧汪節(jié)等人針對(duì)AC算法在構(gòu)造狀態(tài)機(jī)時(shí)空間冗余較大的情況，對(duì)狀態(tài)機(jī)各結(jié)點(diǎn)進(jìn)行壓縮存儲(chǔ)，使空間性能和時(shí)間性能都有提高；文獻(xiàn)［11］中萬(wàn)國(guó)根等人對(duì)AC－BM算法的改進(jìn)借鑒了BMH算法的思想，取消了原算法的好前綴跳轉(zhuǎn)，優(yōu)化了壞字符跳轉(zhuǎn)，并修改了skip的計(jì)算方法，對(duì)大字符集的情況在平均情況下具有更優(yōu)的性能；文獻(xiàn)［12］對(duì)AC－BM的改進(jìn)則是通過(guò)預(yù)處理思想實(shí)現(xiàn)的，在進(jìn)行AC-BM匹配之前首先掃描首和(或)尾字符，確定其位置，再到相應(yīng)位置進(jìn)行匹配，相當(dāng)于把目標(biāo)串按模式串首、尾字符分成數(shù)段，每段進(jìn)行比較，段間不含首字符的就直接跳過(guò)，不用比較，從而提高效率。

3 算法的實(shí)際執(zhí)行效率

上述這些算法究竟哪種算法具有最好的執(zhí)行效率呢?能不能僅通過(guò)時(shí)間復(fù)雜度來(lái)進(jìn)行衡量呢？時(shí)間復(fù)雜度僅是一個(gè)度量的范圍，表示受幾個(gè)參數(shù)的影響，并不代表一個(gè)具體的值，還需要在具體的環(huán)境中進(jìn)行測(cè)試。

文獻(xiàn)［13］測(cè)試了包括上述算法在內(nèi)的多種單模式和多模式匹配算法的性能。測(cè)試平臺(tái)為：硬件：CPU Intel Xeon 3.46 GHz X 2，內(nèi)存2 GB DDR，硬盤(pán)200 GB SCSI；軟件：Windows 2003 Server,Intel IXA SDK4.1。單模式匹配測(cè)試的規(guī)則集，使用隨機(jī)生成的8，16，32，48，128位具有代表意義的規(guī)則，可以對(duì)應(yīng)端口、IP地址，MAC地址、IPv6地址等，對(duì)多模式匹配測(cè)試采用Snort系統(tǒng)2.4.3規(guī)則集。

單模式匹配算法主要測(cè)試模式長(zhǎng)度與匹配時(shí)間、占用空間及預(yù)處理時(shí)間的變化關(guān)系。測(cè)試結(jié)果表明：各算法的測(cè)試指標(biāo)在規(guī)則長(zhǎng)度增長(zhǎng)的情況下均呈遞增趨勢(shì)，但BM算法的增長(zhǎng)速度最為緩慢，在不太在意存儲(chǔ)空間的情況下，BM可以作為優(yōu)先考慮的算法，同時(shí)對(duì)IPV6地址也更為合適。

多模式匹配算法的測(cè)試項(xiàng)目為規(guī)則數(shù)與單位匹配時(shí)間、占用儲(chǔ)存單元、單位預(yù)處理時(shí)間的變化關(guān)系。測(cè)試結(jié)果表明AC－BM算法在上述3項(xiàng)測(cè)試中取得了很好的性能平衡。這也是新

版的Snort系統(tǒng)中選用AC－BM算法的重要原因。

4 入侵檢測(cè)系統(tǒng)中模式匹配算法的研究方向

常用的模式匹配算法所采用的思想主要有基于字符比較、基于自動(dòng)機(jī)、基于hash查找、基于位邏輯運(yùn)算和基于Tries樹(shù)型機(jī)構(gòu)搜索。鑒于目前網(wǎng)絡(luò)的實(shí)際狀況，多模式匹配算法更加適合于基于模式匹配的入侵檢測(cè)系統(tǒng)。這里認(rèn)為應(yīng)該從下面3個(gè)方面著手：一是繼續(xù)研究和改進(jìn)精確的模式匹配，將快速的單模式匹配算法和多模式匹配算法相結(jié)合，充分借鑒同類(lèi)算法的先進(jìn)思想，如：引入Hash函數(shù)、引入自動(dòng)機(jī)、對(duì)字符串分塊等來(lái)不斷提高多模式匹配算法的性能；二是嘗試采用模糊匹配的策略，國(guó)外對(duì)此已經(jīng)開(kāi)始進(jìn)行相應(yīng)的研究；三是對(duì)網(wǎng)絡(luò)數(shù)據(jù)包和入侵特征進(jìn)行研究，總結(jié)出這兩類(lèi)字符串特點(diǎn)，有針對(duì)性地對(duì)這兩類(lèi)字符串的匹配問(wèn)題進(jìn)行研究。

5 結(jié) 語(yǔ)

網(wǎng)絡(luò)帶寬的不斷增加、日益嚴(yán)重的網(wǎng)絡(luò)安全狀況要求必須盡快提高網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的性能。雖然入侵檢測(cè)系統(tǒng)可以采用很多技術(shù)，并且這些技術(shù)也在不斷的研究和發(fā)展中，但是目前主流的實(shí)用的入侵檢測(cè)技術(shù)仍然是基于模式匹配的。因此如何提高模式匹配的效率成為研究入侵檢測(cè)系統(tǒng)的一個(gè)關(guān)鍵所在。在此對(duì)已有的經(jīng)典模式匹配算法進(jìn)行了系統(tǒng)綜述，并對(duì)入侵檢測(cè)系統(tǒng)中模式匹配算法的未來(lái)研究方向給出了觀點(diǎn)。

參考文獻(xiàn)

［1］龐善臣,王淑棟,蔣昌俊.BM串匹配的一個(gè)改進(jìn)算法［J］.計(jì)算機(jī)應(yīng)用,2004,12(12):11－13.

［2］Boyer R S,Moore J S.A Fast String Searching Algorithm ［J］.Communications of ACM,1977,20(10):762－772.

［3］張立航,潘正運(yùn),劉海峰.基于改進(jìn)的KR算法在網(wǎng)閘中的實(shí)現(xiàn)［J］.微計(jì)算機(jī)信息(管控一體化),2008(24):137－138.

［4］Johnson T,Newman－Wolfe R E.A Comparison of Fast and Low Overhead Distributed Priority Locks ［J］.Journal of Parallel and Distributed Computing,1996,32(1):74－89.

［5］Jason C C,Staniford S,McAlemey J.Towards Faster String for Intrusion Detection or Exceeding the Speed of Snort ［EB/OL］./sotfware/acbm/speed－of－snort－03－16－2001.padf,2003.

［6］黃占友,劉悅.對(duì)KMP串匹配算法的改進(jìn)［A］.第四次全國(guó)便攜計(jì)算機(jī)學(xué)術(shù)交流會(huì)論文集［C］.北京:科學(xué)出版社,1997.

［7］濤,方濱興,胡銘曾.對(duì)BM串匹配算法的一個(gè)改進(jìn)［J］.計(jì)算機(jī)應(yīng)用,2003,23(3):6－8.

［8］張國(guó)平,徐汶東.字符串模式匹配算法的改進(jìn)［J］.計(jì)算機(jī)工程與設(shè)計(jì),2007,28(20):4 881－4 884.

［9］蔡曉妍,戴冠中,楊黎斌.一種快速的單模式匹配算法［J］.計(jì)算機(jī)應(yīng)用研究,2008,25(1):45－46,81.

［10］盧汪節(jié),鞠時(shí)光.入侵檢測(cè)系統(tǒng)中一種改進(jìn)的AC算法［J］.計(jì)算機(jī)工程與應(yīng)用,2006(15):146－148.

［11］萬(wàn)國(guó)根,秦志光.改進(jìn)的AC－BM字符串匹配算法［J］.電子科技大學(xué)學(xué)報(bào),2006,35(4):531－533.

［12］周四偉,蔡勇.AC－BM算法的改進(jìn)及其在入侵檢測(cè)中的應(yīng)用［J］.微計(jì)算機(jī)應(yīng)用,2007,28(1):27－31.

［13］王琢,趙永哲,姜占華.網(wǎng)絡(luò)處理模式匹配算法研究［J］.計(jì)算機(jī)應(yīng)用研究,2007,24(12):310－312.

作者簡(jiǎn)介

冉占軍 男，1977年出生，陜西西安人，講師，碩士研究生。主要研究方向?yàn)樗惴?、網(wǎng)絡(luò)安全。

姚全珠 男，1960年出生，博士，教授。主要研究方向?yàn)樗惴?、?shù)據(jù)庫(kù)、網(wǎng)絡(luò)安全。

篇(3)

關(guān)鍵詞:點(diǎn)云數(shù)據(jù);配準(zhǔn);ICP算法

中圖分類(lèi)號(hào):TP391.7 文獻(xiàn)標(biāo)識(shí)碼:A

The Research of Cloud Data Alignment

CHEN San-qing

(School of Computer, Panzhihua University, Sichuan Panzhihua 617000)

Key words: cloud data; alignment;ICP algorithm

為了得到物體真實(shí)的三維模型,人們需要獲得三維物體表面的真實(shí)數(shù)據(jù)。但是,由于受到測(cè)量設(shè)備和環(huán)境的限制,物體表面完整測(cè)量數(shù)據(jù)的獲得往往需要通過(guò)多次測(cè)量完成。點(diǎn)云(三維數(shù)據(jù))就是使用各種三維數(shù)據(jù)采集儀采集得到的密集數(shù)據(jù),它記錄了有限體表面在離散點(diǎn)上的各種物理參量。三維曲面的重建就是依據(jù)這種密集的點(diǎn)云數(shù)據(jù)來(lái)恢復(fù)原始曲面,進(jìn)而實(shí)現(xiàn)三維模型的真實(shí)重現(xiàn)的目的。

由于每次測(cè)量得到的點(diǎn)云數(shù)據(jù)往往只覆蓋物體部分表面,并且可能出現(xiàn)平移錯(cuò)位和旋轉(zhuǎn)錯(cuò)位,為了得到物體完整表面的點(diǎn)云數(shù)據(jù),需要對(duì)這些局部點(diǎn)云數(shù)據(jù)進(jìn)行整合和配準(zhǔn)。因此,在得到點(diǎn)云數(shù)據(jù)之后,為了得到三維模型的原始曲面,必須要將不同角度,不同位置掃描得到的大容量三維空間數(shù)據(jù)點(diǎn)集轉(zhuǎn)換到一個(gè)統(tǒng)一的坐標(biāo)系中,該技術(shù)稱(chēng)之為數(shù)據(jù)縫合,即三維點(diǎn)云數(shù)據(jù)的配準(zhǔn)。點(diǎn)云配準(zhǔn)是點(diǎn)云數(shù)據(jù)獲取后的第一步處理,也是所有后續(xù)處理的基礎(chǔ)。因此,配準(zhǔn)的精度將直接關(guān)系到建模精度。

1 點(diǎn)云數(shù)據(jù)配準(zhǔn)算法的研究進(jìn)展

一般情況下點(diǎn)云都是以高密度形態(tài)存在,為了有效處理各種形式的點(diǎn)云,根據(jù)點(diǎn)云的分布特征(如排列方式、密度等)可以把點(diǎn)云分為[1]:散亂點(diǎn)云,即測(cè)量點(diǎn)沒(méi)有明顯的幾何分布特征,呈散亂無(wú)序狀態(tài);掃描線點(diǎn)云,即點(diǎn)云由一組掃描線組成,掃描線上的所有點(diǎn)位于掃描平面內(nèi);網(wǎng)格化點(diǎn)云,即點(diǎn)云中所有點(diǎn)都與參數(shù)域中一個(gè)均勻網(wǎng)格的頂點(diǎn)對(duì)應(yīng);多邊形點(diǎn)云,即測(cè)量點(diǎn)分布在一系列平行平面內(nèi),用小線段將同一平面內(nèi)距離最小的若干相鄰點(diǎn)依次連接可形成一組有嵌套的平面多邊形。

針對(duì)上述各種形式的點(diǎn)云數(shù)據(jù),在20世紀(jì)80年代中期,很多學(xué)者對(duì)其配準(zhǔn)進(jìn)行了大量研究。1987年,Horn、Arun等人用四元數(shù)法提出點(diǎn)集對(duì)點(diǎn)集配準(zhǔn)方法。這種點(diǎn)集與點(diǎn)集坐標(biāo)系匹配算法通過(guò)實(shí)踐證明是一個(gè)解決復(fù)雜配準(zhǔn)問(wèn)題的關(guān)鍵方法。1992年,計(jì)算計(jì)視覺(jué)研究者Besl和Mckay[2]介紹了一種高層次的基于自由形態(tài)曲面的配準(zhǔn)方法,也稱(chēng)為迭代最近點(diǎn)法ICP(Iterative Closest Point),并在此基礎(chǔ)上產(chǎn)生了許多的變種算法。ICP主要用于解決基于自由形態(tài)曲面的配準(zhǔn)問(wèn)題。但I(xiàn)CP算法對(duì)兩個(gè)點(diǎn)云相對(duì)的初始位置要求比較高,點(diǎn)云之間初始位置不能相差太大,并且要求兩個(gè)匹配點(diǎn)集中的一個(gè)點(diǎn)集是另外一個(gè)點(diǎn)集的子集。當(dāng)條件不滿足,或相差太大時(shí),會(huì)影響ICP算法的收斂結(jié)果,使得配準(zhǔn)變的不可靠。

Chen等運(yùn)用兩個(gè)曲面在法矢方向的距離來(lái)代替某一點(diǎn)到其最近點(diǎn)的距離,并將其作為匹配的目標(biāo)評(píng)價(jià)函數(shù)。這一設(shè)想最初是由Potmesil于1983年提出的,它被推廣為最優(yōu)加權(quán)的最小二乘方法。Masuda等對(duì)點(diǎn)集進(jìn)行隨機(jī)采樣,用最小中值平方誤差作為度量準(zhǔn)則,該方法在每次迭代后都需要進(jìn)行重新采樣。Johnson等使用特征提取策略去除沒(méi)有啟發(fā)信息的平面點(diǎn)來(lái)提高配準(zhǔn)速度,在點(diǎn)云數(shù)據(jù)法矢連續(xù)、突變比較少的情況下,其速度沒(méi)有明顯的提高。也有一些學(xué)者通過(guò)引入?yún)⒖键c(diǎn)的方法來(lái)實(shí)現(xiàn)三維點(diǎn)云數(shù)據(jù)的配準(zhǔn),這些參考點(diǎn)實(shí)際也是一種標(biāo)簽,需要在測(cè)量前粘貼在被測(cè)物體上。此外,G.Barequet等人在幾何哈希技術(shù)基礎(chǔ)上采用投票機(jī)制實(shí)現(xiàn)了部分曲面匹配算法。還有使用卡爾曼估計(jì)子的三角片曲面匹配方法等。

2 ICP點(diǎn)云數(shù)據(jù)配準(zhǔn)算法及其改進(jìn)算法

ICP算法最初由Besl和McKay,提出來(lái)的時(shí)候,其原意是迭代最近點(diǎn)(IterativeClosestpoint)匹配算法,后來(lái)被廣泛理解為迭代對(duì)應(yīng)點(diǎn)(IterativeCorrespondingpoint)匹配算法。ICP法實(shí)質(zhì)上是基于最小二乘法的最優(yōu)匹配方法,它重復(fù)進(jìn)行“確定對(duì)應(yīng)關(guān)系點(diǎn)集并計(jì)算最優(yōu)剛體變換”的過(guò)程,直到某個(gè)表示正確匹配的收斂準(zhǔn)則得到了滿足。目前,ICP算法在點(diǎn)云數(shù)據(jù)配準(zhǔn)中應(yīng)用相當(dāng)廣泛,并且得到了許多學(xué)者的進(jìn)一步研究和擴(kuò)充?；贗CP算法點(diǎn)云數(shù)據(jù)配準(zhǔn)過(guò)程如圖1所示:

2.1Beslhe和Mckay提出的原始ICP算法[2]

設(shè)掃描匹配過(guò)程中的參考掃描模型為Sr,待匹配的當(dāng)前掃描模型為Sc,模型中的數(shù)據(jù)點(diǎn)個(gè)數(shù)為N。參考掃描模型和當(dāng)前掃描模型間的變換矩陣為P=(p0,pl,p2,p3,p4,p5,p6)T 其中,PR=(p0,p1,p2,p3)T四元組表示旋轉(zhuǎn)偏移量,可轉(zhuǎn)化為3×3的旋轉(zhuǎn)矩陣R(PR),PT =(p4,p5,p6)T表示平移偏移量。這樣,模型間的變換矩陣可以表示為P=( PR | PT )T 。ICP算法在進(jìn)行點(diǎn)對(duì)匹配時(shí)采用的是比較點(diǎn)間歐式距離的方法,而掃描模型間的變換矩陣是通過(guò)最小化歐式距離平方函數(shù)得到。

整個(gè)ICP算法描述如下:

第一步:初始化迭代,P0=( l,0,0,0,0,0,0 )T,迭代次數(shù)k,設(shè)置歐式距離均方差閥值r以及最大迭代次數(shù)Kmax 。

第二步:迭代步驟:

(1)對(duì)待匹配掃描模型中的每個(gè)點(diǎn)搜索其在參考掃描模型中歐式距離最近的點(diǎn),生成整個(gè)掃描模型的鄰近點(diǎn)對(duì)集合Yk。

(2)由參考模型中的掃描點(diǎn)和匹配點(diǎn)對(duì)集合計(jì)算掃描模型間的變換矩陣Pk=(PR k | PT k )T和匹配點(diǎn)對(duì)間的歐式距離誤差dk。

(3)根據(jù)變換矩陣Pk=( PR k | PT k )T變換當(dāng)前掃描模型Sr中的所有掃描點(diǎn)位置。

(4)計(jì)算變換后,參考掃描模型與當(dāng)前掃描模型間的對(duì)應(yīng)點(diǎn)對(duì)間的歐式距離誤差dk+1,并計(jì)算第k和k+1次迭代中誤差變化量。當(dāng)該變化量小于歐式距離均方差閥值r或迭代次數(shù)k大于k max時(shí),停止迭代。

ICP算法是一種迭代算法,具有很高的匹配精度。但由算法描述可知,它存在計(jì)算量較大且迭代過(guò)程可能無(wú)法收斂到全局最優(yōu)解的缺陷。ICP算法最耗費(fèi)時(shí)間的步驟是求解鄰近點(diǎn)對(duì)的過(guò)程,因?yàn)樗捎玫氖侨炙阉鳌檫m應(yīng)不同的環(huán)境并克服ICP算法自身的部分缺陷,許多研究人員對(duì)其進(jìn)行了改進(jìn)。

2.2ICP的改進(jìn)算法

為了提高基本ICP方法的可靠性和魯棒性,從匹配點(diǎn)的選擇到最小二乘度量目標(biāo)函數(shù)的選取等ICP匹配算法中的各個(gè)階段,許多研究者都提出了各種的優(yōu)化方法,形成了相應(yīng)的ICP變型算法。ICP算法的各個(gè)階段劃分如下[3]:

(1)匹配模型中進(jìn)行匹配的數(shù)據(jù)點(diǎn)的選取采樣;

(2)兩模型中有對(duì)應(yīng)關(guān)系的匹配點(diǎn)對(duì)的選擇;

(3)匹配點(diǎn)對(duì)的適當(dāng)權(quán)值賦予;

(4)過(guò)濾某些錯(cuò)誤的匹配點(diǎn)對(duì);

(5)度量準(zhǔn)則的選取;

(6)最優(yōu)化方法的確定。

對(duì)ICP算法的改進(jìn)主要集中在如下四點(diǎn)[4]:

(1)點(diǎn)集的不同選取方法。一般情況下點(diǎn)集的選取方法包含如下五種情況,分別是選取所有可用點(diǎn)作為點(diǎn)集;隨機(jī)選取抽樣點(diǎn)作為點(diǎn)集;采用平均抽樣方法進(jìn)行點(diǎn)集選取;根據(jù)點(diǎn)的特征信息(如梯度信息等)進(jìn)行點(diǎn)集選取;選取邊緣點(diǎn)作為點(diǎn)集。

(2)點(diǎn)的對(duì)應(yīng)方法。點(diǎn)的對(duì)應(yīng)方法主要有二種,一種是搜索最近點(diǎn)作為對(duì)應(yīng)點(diǎn);另一種是采用投影求交的方法確定對(duì)應(yīng)點(diǎn)。

(3)點(diǎn)對(duì)的拒絕。點(diǎn)對(duì)拒絕的實(shí)現(xiàn)主要有以下三種情況:對(duì)于邊緣點(diǎn)的拒絕;對(duì)于對(duì)應(yīng)點(diǎn)對(duì)中距離過(guò)大的點(diǎn)對(duì)的拒絕;考慮法向量的點(diǎn)對(duì)的拒絕。

(4)加速迭代。主要采用減少迭代次數(shù)或使用非迭代的方法來(lái)實(shí)現(xiàn),作用是減少運(yùn)算量,提高計(jì)算速度。

Chen和Medioni兩位學(xué)者在Besl和Mckay的經(jīng)典ICP算法的基礎(chǔ)上進(jìn)行了改進(jìn),該算法的不同之處在于改進(jìn)后算法的目標(biāo)函數(shù)中的距離是點(diǎn)到對(duì)應(yīng)點(diǎn)出的切平面的距離。事實(shí)上,因?yàn)橐婚_(kāi)始的匹配點(diǎn)對(duì)通常都是不精確的,這種方法認(rèn)為在這種不精確的意義下,嚴(yán)格地極小化匹配點(diǎn)對(duì)之間的距離平方和不能達(dá)到快速的收斂,因此它選取了到匹配點(diǎn)處的切平面的距離來(lái)代替點(diǎn)到點(diǎn)的距離。這種方法的好處是一開(kāi)始就可以使迭代誤差很快地減小,也就是快速的收斂,但是因?yàn)樗们衅矫鎭?lái)代替真正的曲面,也就是忽略了目標(biāo)函數(shù)的Hessian中的二次項(xiàng)信息,所以這種方法有時(shí)候會(huì)不收斂,尤其當(dāng)目標(biāo)物體表面曲率變化明顯時(shí),這時(shí),二次項(xiàng)信息在目標(biāo)函數(shù)種占有更多的比重。事實(shí)上,這種方法是一種Gauss-Newton法,它不保證收斂,但是如果收斂,速度會(huì)比較快,是二次收斂。后來(lái)有研究者對(duì)這種方法提出了改進(jìn),加上了步長(zhǎng)控制[5](Levenberg-Marquart方法),這樣可以保證該方法收斂,而且如果步長(zhǎng)選取地合適,并不影響收斂速度,仍然二次收斂。此外,Mitra等引入平方距離(Squared Distance)的概念。把Chen和Medioni的改進(jìn)中所忽略的二階信息做了一個(gè)理想的近似加入了迭代中,因此能保證更好的收斂性。這種方法在滿足標(biāo)準(zhǔn)假設(shè)的情況下,是一種準(zhǔn)牛頓方法。準(zhǔn)牛頓方法是收斂的,而且是二次收斂的。

3 結(jié)束語(yǔ)

近年來(lái)隨著三維掃描技術(shù)的發(fā)展,特別是三維激光掃描技術(shù)的出現(xiàn),高效、快速、準(zhǔn)確的獲取真實(shí)場(chǎng)景的高精度三維點(diǎn)云數(shù)據(jù)變得較為容易。利用這些點(diǎn)云數(shù)據(jù)可以恢復(fù)重建具有準(zhǔn)確幾何信息和真實(shí)感的原始物體。本文對(duì)點(diǎn)云數(shù)據(jù)處理中的配準(zhǔn)方法進(jìn)行了論述。本文首先總結(jié)分析了點(diǎn)云數(shù)據(jù)配準(zhǔn)算法的研究現(xiàn)狀,然后對(duì)其中比較具有代表性的ICP算法及其改進(jìn)算法進(jìn)行了具體的探討。目前,對(duì)ICP算法研究的主要集中在如何提高ICP算法的穩(wěn)定性、收斂性和可靠性等方面上,通過(guò)改進(jìn)搜索最近點(diǎn)以及計(jì)算的收斂性,來(lái)提高ICP算法的配準(zhǔn)精度和配準(zhǔn)速度。

參考文獻(xiàn):

[1]張舜德,朱東波,盧秉恒.反求工程中三維幾何形狀測(cè)量及數(shù)據(jù)預(yù)處理[J].機(jī)電工程技術(shù),2001,30(l):7-10.

[2]Besl P J, MeKay N D. A method for registration of3-D shapes.IEEE Trans onPattern Analysis and Maehine Intelligenee ,1992 ,14(2): 239-256.

[3]潘小林.三維曲面匹配技術(shù)研究[D].南京航空航天大學(xué)碩士論文,2004.

篇(4)

關(guān)鍵詞：SIFT；相似性度量；圖像匹配

引言

在計(jì)算機(jī)視覺(jué)領(lǐng)域，圖像匹配仍然是當(dāng)前研究的熱點(diǎn)問(wèn)題。基于特征的匹配方法[1]，因?yàn)楦鶕?jù)圖像中趨于穩(wěn)定的少量特征進(jìn)行匹配，使得運(yùn)算速度快、匹配效果好，所以成為目前研究最多、應(yīng)用最廣泛的一種方法。但是，這種方法需要在圖像間進(jìn)行遍歷性的匹配運(yùn)算，存在計(jì)算量大，且精度不高的問(wèn)題。

1999年，Lowe提出了SIFT（Scale Invariant Feature Transform）算法[2]，該算法利用高斯差分在圖像的多尺度空間中快速求解高斯拉普拉斯空間中的極值點(diǎn)，加快了特征提取的速度，提取的SIFT特征對(duì)于圖像平移、縮放、旋轉(zhuǎn)具有不變性，并且對(duì)于仿射變換、視覺(jué)變化、光照變化有較強(qiáng)的穩(wěn)定性和很好的匹配魯棒性，所以被廣泛應(yīng)用于計(jì)算機(jī)視覺(jué)的圖像匹配、圖像檢索和模式識(shí)別等方面[3，5]。雖然SIFT 算法具有上述的優(yōu)點(diǎn)，但該算法首先要將彩色圖像灰度化，僅利用圖像的灰度信息和特征點(diǎn)的局部鄰域信息，忽略了圖像的顏色信息，導(dǎo)致不能識(shí)別圖像內(nèi)具有相似結(jié)構(gòu)的特征點(diǎn)。

文章提出基于SIFT的多特征相似性度量算法，首先對(duì)彩色壁畫(huà)圖像提取SIFT特征點(diǎn)與特征向量，然后對(duì)每個(gè)特征點(diǎn)提取HSI彩色特征，最后按定義的相似性度量公式計(jì)算兩個(gè)特征點(diǎn)之間的距離，確定二者是否匹配。

1 特征提取

1.1 SIFT特征提取

尺度空間極值點(diǎn)的檢測(cè)采用DOG方法，將一個(gè)像素點(diǎn)與它相鄰的26個(gè)點(diǎn)相比較，如果是最大值或最小值，就作為圖像中的一個(gè)特征點(diǎn)。以特征點(diǎn)為中心，在16×16的鄰域內(nèi)，將采樣點(diǎn)與特征點(diǎn)的相對(duì)方向通過(guò)高斯加權(quán)后，分別歸入8個(gè)方向的梯度方向直方圖，最后獲得4×4×8的128維特征向量來(lái)描述一個(gè)SIFT特征點(diǎn)。

SIFT算法的兩個(gè)關(guān)鍵步驟是關(guān)鍵點(diǎn)檢測(cè)和關(guān)鍵點(diǎn)描述。在關(guān)鍵點(diǎn)檢測(cè)階段，大多是利用兩種不同的方法，即尺度不變檢測(cè)和致密采樣。文章采用致密采樣進(jìn)行特征檢測(cè)，理由如下。一方面，尺度不變檢測(cè)器在描繪均勻信息時(shí)是低效的，而壁畫(huà)圖像中包含著這樣的信息。另一方面，在特征匹配時(shí)，通過(guò)致密采樣得到的關(guān)鍵點(diǎn)優(yōu)于隨機(jī)抽樣和尺度不變的探測(cè)器[6]。

SIFT算法首先將彩色圖像灰度化，提取的特征關(guān)注圖像的梯度信息，忽視了圖像的彩色信息。文章對(duì)彩色圖像提取特征，實(shí)驗(yàn)發(fā)現(xiàn)圖像的誤匹配點(diǎn)中，存在著彩色信息不一致的問(wèn)題。因此，文章對(duì)圖像既提取SIFT特征，又提取顏色特征，對(duì)多特征融合設(shè)計(jì)相似性度量方案，可以減少誤匹配率，提高匹配效果。

1.2 顏色特征提取

為了解決誤匹配中存在的SIFT梯度信息一致，彩色信息不一致的問(wèn)題，我們?cè)趯?duì)特征點(diǎn)提取SIFT特征后，再次提取其顏色特征。由于RGB顏色模型只考慮圖像的亮度信息，而HSI顏色模型全面考慮圖像的亮度和顏色信息，因而在開(kāi)發(fā)基于彩色描述的圖像處理算法中，HSI模型更為有用[7]，文章提取HSI彩色特征。

HSI顏色模型中，H表示色調(diào)，指的是人的感官對(duì)不同顏色的感受，描述純色的屬性；S表示飽和度，描述的是顏色的純度；I表示強(qiáng)度，描述的是顏色的明亮程度。

常用的最近鄰方法原理是，對(duì)于基準(zhǔn)圖像中的每個(gè)特征點(diǎn)，在待匹配圖像中尋找距離最近的特征點(diǎn)，然后形成一組匹配對(duì)。因?yàn)樽罱彨@得的匹配對(duì)中存在大量的誤匹配，所以Lowe在論文[8]中對(duì)于基準(zhǔn)圖像中的每個(gè)特征點(diǎn)，在待匹配圖像中尋找距離最近和次近的兩個(gè)特征點(diǎn)，當(dāng)這兩個(gè)距離的比值小于預(yù)設(shè)的閾值時(shí)，才認(rèn)為找到了一組正確的匹配對(duì)，這樣消除了大量的誤匹配，取得了不錯(cuò)的匹配效果。文章設(shè)閾值為thr，且0

3 實(shí)驗(yàn)結(jié)果及分析

為了觀察算法性能，我們從互聯(lián)網(wǎng)上尋找了兩張有重疊部分的壁畫(huà)圖片進(jìn)行了實(shí)驗(yàn)。圖像如圖1所示。采用Matlab7.7.0編程，運(yùn)行在AMD A6-3400M CPU 1.4GHZ和4G內(nèi)存的PC機(jī)上，Windows 7.0操作系統(tǒng)。

實(shí)驗(yàn)首先尋找圖像的SIFT特征點(diǎn)，然后提取特征點(diǎn)的SIFT特征和HSI特征，再對(duì)圖1a和圖1b按公式（9）進(jìn)行相似性度量，再分別用歐式距離和卡方距離作為相似性度量，并且thr分別選用0.5，0.6，0.7，0.8進(jìn)行特征對(duì)提純。結(jié)果表明，匹配過(guò)程在使用同樣的閾值時(shí)，三種相似性度量方法中，所得到的匹配正確率相同，而匹配時(shí)間不同，按公式（9）計(jì)算的距離稍快一些。隨著thr值的增大，所得匹配對(duì)數(shù)減少，當(dāng)thr取值為0.6時(shí)，具有較好的匹配結(jié)果。圖2為thr取值為0.6時(shí)的匹配結(jié)果。

另外，實(shí)驗(yàn)同時(shí)表明，對(duì)于圖像分別提取SIFT特征和HSI特征，如果僅按SIFT特征或HSI特征計(jì)算相似性，所得到的匹配正確率都低于兩個(gè)特征按公式（9）計(jì)算相似性的情況。

因此，對(duì)圖像提取SIFT特征和HSI特征，按我們定義的相似性度量計(jì)算方法，確實(shí)提高了圖像匹配的效率。

4 結(jié)束語(yǔ)

文章采用的算法對(duì)彩色壁畫(huà)圖像同時(shí)提取SIFT特征和HIS彩色特征，有效地去除了梯度信息一致而彩色信息不一致產(chǎn)生的誤匹配。通過(guò)定義的相似性度量公式，在計(jì)算兩個(gè)特征點(diǎn)之間是否匹配時(shí)，速度更快一些。由于SIFT 算法計(jì)算量大，算法復(fù)雜，提高圖像匹配的實(shí)時(shí)性，將是下一步的研究工作。

參考文獻(xiàn)

[1]ZHU Q，WU B，XU Z.Seed point selection method for triangle constrained image matching propagation[J].IEEE Geoscience and Remote Sensing Letters，2006，3（2）：207-211.

[2]LOWE D G.Object recognition from local scale-invariant feature[C]// Proc.the Seventh IEEE International Conference on Computer Vision.Corfu，Greece： IEEE Press，1999：1150-1157.

[3]張書(shū)真，宋海龍，向曉燕，等.采用快速SIFT算法實(shí)現(xiàn)目標(biāo)識(shí)別[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2010，19（6）：82-85.

[4]王瑞瑞，馬建文，陳雪.多傳感器影像配準(zhǔn)中基于虛擬匹配窗口的SIFT算法[J].武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），2011，36（2）：163-166.

[5]鐘金琴，檀結(jié)慶，李瑩瑩，等.基于二階矩的SIFT特征匹配算法[J].計(jì)算機(jī)應(yīng)用，2011，31（1）：29-32.

[6]K.Mikolajczyk，C.Schmid. A performance evaluation of local descriptors [J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（10）：1615-1630.

[7]何川.高壓輸電線路視頻監(jiān)控技術(shù)研究[D].北京：北京交通大學(xué)，2012.

篇(5)

[關(guān)鍵詞]模糊匹配 模糊查找 位置匹配 C語(yǔ)言算法

[中圖分類(lèi)號(hào)]TP391.41 [文獻(xiàn)標(biāo)識(shí)碼]A [文章編號(hào)]1009-5349（2013）02-0061-01

引言

為了提升用戶撥號(hào)的快捷性，要求用戶在輸入號(hào)碼的時(shí)候，對(duì)用戶已輸入號(hào)碼進(jìn)行模糊匹配，并以列表的形式呈現(xiàn)給用戶，供用戶選擇。用戶使用手機(jī)鍵盤(pán)撥號(hào)速度最快不超過(guò)100毫秒，這就要求手機(jī)必須在100毫秒以內(nèi)查找結(jié)束并把結(jié)果呈現(xiàn)給用戶。而手機(jī)號(hào)碼、SIM卡號(hào)碼、最近通訊錄號(hào)碼總和在3000個(gè)左右。利用傳統(tǒng)的字符串查找已不能滿足要求。

本論文僅闡述核心算法部分。

一、算法實(shí)現(xiàn)

本算法使用以空間換取時(shí)間的辦法，通過(guò)記錄不同數(shù)字所在的位置，并通過(guò)移位操作來(lái)實(shí)現(xiàn)模糊查找。此算法復(fù)雜度僅僅和用戶輸入的字符串長(zhǎng)度有關(guān)，而和實(shí)際的字符串長(zhǎng)度無(wú)關(guān)。因此，不同于常規(guī)的字符串查找算法。

（一）字符映射

首先，把手機(jī)號(hào)碼中存在的字符映射成16個(gè)字符，方法為：把字符“0”-“9”轉(zhuǎn)換成數(shù)字0～9；把“*”“#”“+”“p”“w”分別轉(zhuǎn)換成數(shù)字10、11、12、13、14；把可能存在的字符“-”或其他字符轉(zhuǎn)換成數(shù)字15。

（二）數(shù)據(jù)結(jié)構(gòu)定義

用元素來(lái)定義電話號(hào)碼的存儲(chǔ)結(jié)構(gòu)，一個(gè)元素存儲(chǔ)一個(gè)號(hào)碼。格式可以如下：

typedef struct

{tCellType nData[16]；

}tElement；

其中tCellType可以為unsigned short或unsigned long。前者代表可容納電話號(hào)碼的最大長(zhǎng)度為16，后者代表可容納的最大長(zhǎng)度為32（32位機(jī)器下）。

（三）數(shù)據(jù)結(jié)構(gòu)建立

把一個(gè)電話號(hào)碼放到一個(gè)元素中去，保證：元素中nData[0]記錄數(shù)字0所在的位置，nData[1]記錄數(shù)字1所在的位置，依次類(lèi)推，nData[15]記錄數(shù)字15所在的位置。

添加一個(gè)電話號(hào)碼到號(hào)碼映射中。方法如下：（1）從字符串中取第一個(gè)字符，并根據(jù)字符映射規(guī)則映射為數(shù)字。（2）以映射成的數(shù)字為索引（index），并記錄字符所在的位置為（i），位置從0開(kāi)始計(jì)數(shù)。（3）取元素中索引為index的變量，并把位置為i的位設(shè)為1。即：nData[index] |=0x01

舉例：假如電話號(hào)碼為“13511051123”，則在nData[1]的0、3、4、7、8的位置1，nData[2]的9的位置1，nData[3]的1、10的位置1，nData[5]的2、6的位置1， nData[0]的5的位置1。

（四）查詢方法

假如用戶僅僅輸入一個(gè)字符則只需要一次判斷即可。算法復(fù)雜度為O（1）。假如用戶輸入n個(gè)字符，則需要：首先判斷第0個(gè)字符對(duì)應(yīng)元素中的值是否為真，如果是則繼續(xù)。接著取第1個(gè)字符對(duì)應(yīng)的元素值并右移1次，和第0個(gè)元素相與得結(jié)果tm，如果tm為真則繼續(xù)。然后取第2個(gè)字符對(duì)應(yīng)的元素值并右移2次，和上一次得到的結(jié)果相與得到新的tm，如果tm為真則繼續(xù)。依次執(zhí)行直到字符串結(jié)束。

算法復(fù)雜度分析：最好情況下一次判斷即可獲取結(jié)果，即用戶輸入的第一個(gè)字符對(duì)應(yīng)的元素值為0；最壞情況下需要：n-1次移位操作，n-1次與運(yùn)算，及n次判斷操作。但一般用戶輸入的待查找字符串長(zhǎng)度n遠(yuǎn)遠(yuǎn)小于原始字符串的長(zhǎng)度。

算法示例：取臨時(shí)變量tm，list為用戶輸入的待查找字符串通過(guò)字符映射得到的數(shù)組，n為字符串長(zhǎng)度。

tCellType tm = nData[list[0]]；

for（i = 1； tm&&i

{tm&=nData[list[i]] >>（i）；}

if（tm） {//處理找到的記錄}

舉例：假如電話號(hào)碼為“13511051123”，如果用戶輸入的待查找字符串為“105”，則需要判斷nData[1]| （nData[0]>>1）|（nData[5]>>2）顯然nData[1]在第4位上為1；nData[0]在第5位上為1，右移一位變成第四位；nData[5]在第6位上為1，右移二位變成第四位；相與后仍然為真。

假如用戶輸入的為“15”，而nData[5]僅僅在2、6的位置上為1，右移一位變成第1、5位，顯然nData[1]在1、5位上均為0，相與后仍然為0。

其他說(shuō)明：實(shí)際應(yīng)用中可以通過(guò)一定的方法記錄結(jié)果，新的查找基于上一次的查找結(jié)果進(jìn)行查找，而沒(méi)有必要對(duì)所有記錄重新查找。

篇(6)

關(guān)鍵詞：被動(dòng)定位，匹配場(chǎng)，水下GPS，動(dòng)目標(biāo)分析

 

1.引言

聲納按照工作方式一般分為主動(dòng)聲納和被動(dòng)聲納。對(duì)于被動(dòng)聲納，由于它不發(fā)射聲波，它具有很好的隱蔽性，且具有作用距離遠(yuǎn)、不容易被發(fā)現(xiàn)等優(yōu)點(diǎn)，在軍事領(lǐng)域中有著很好的應(yīng)用前景。近年來(lái)，世界各國(guó)都加緊了對(duì)被動(dòng)定位技術(shù)的研究和開(kāi)發(fā)，被動(dòng)定位技術(shù)受到廣泛的重視。隨著水中兵器作用距離和打擊精度的提高，對(duì)被動(dòng)聲納的定位性能提出了更高的要求，遠(yuǎn)程定位問(wèn)題引起人們的廣泛關(guān)注，出現(xiàn)了多種新型的定位方法。

2.傳統(tǒng)被動(dòng)聲納定位技術(shù)及面臨的問(wèn)題

2.1 傳統(tǒng)的被動(dòng)定位技術(shù)

傳統(tǒng)的水聲被動(dòng)定位技術(shù)是六十年代研究開(kāi)發(fā)出來(lái)的,這類(lèi)定位技術(shù)利用沿不同距離路徑傳播的水下聲脈沖間的時(shí)間差或相位差對(duì)水面、水中目標(biāo)進(jìn)行定位，其典型代表就是三子陣法和球面內(nèi)插法。三子陣被動(dòng)測(cè)距方法是己經(jīng)實(shí)用化了的被動(dòng)定位技術(shù)，它是六十年代后期出現(xiàn)的噪聲測(cè)距方法。它利用時(shí)延估計(jì)技術(shù)求出到達(dá)三個(gè)基陣的相對(duì)時(shí)延，然后得到目標(biāo)的方位和距離。但是，三子陣定位方法對(duì)水聲信道進(jìn)行了簡(jiǎn)化，三子陣系統(tǒng)是在同一平面內(nèi)進(jìn)行定位的，它不考慮信道聲速的垂直分布，也不考慮信道的多途效應(yīng)。，動(dòng)目標(biāo)分析。，動(dòng)目標(biāo)分析。不過(guò)這種定位方法算法簡(jiǎn)單，而且對(duì)近距離聲源定位能達(dá)到較高的精度，目前在工程上已經(jīng)得到廣泛應(yīng)用。

2.2 傳統(tǒng)被動(dòng)聲納定位技術(shù)面臨的問(wèn)題

傳統(tǒng)被動(dòng)定位方法在理論和實(shí)際應(yīng)用中都存在很大的缺陷，主要表現(xiàn)在以下兩個(gè)方面。

2.2.1 遠(yuǎn)程定位精度不高

傳統(tǒng)的被動(dòng)定位方法，利用球面波或柱面波波前曲率的變化，通過(guò)測(cè)量各基元的相對(duì)時(shí)延，估計(jì)目標(biāo)的距離和方位。測(cè)距精度與時(shí)延估計(jì)精度、目標(biāo)距離、方位、基陣孔徑、基陣安裝精度等因素有關(guān)，其中時(shí)延測(cè)量精度是關(guān)鍵，然而對(duì)于有限的基陣孔徑，隨著聲納探測(cè)距離的增加，波前曲率的變化越來(lái)越小，加上信道傳播起伏的影響，時(shí)延的精確測(cè)量以及距離信息的提取變得越來(lái)越困難，因此傳統(tǒng)的定位方法難以實(shí)現(xiàn)遠(yuǎn)程定位。此外，由于海洋中的聲速分布是不均勻的，特別在遠(yuǎn)距離定位時(shí)，聲速的不均勻分布使傳統(tǒng)的定位算法存在較大的誤差。為此，研究人員必須尋求新的被動(dòng)定位方法。

2.2.2 定位效果受聲場(chǎng)環(huán)境影響大

由于海水介質(zhì)的不均勻性，在海水信道中由于溫度、鹽度、壓力的不同，導(dǎo)致了海水介質(zhì)中各點(diǎn)的聲學(xué)特性差異很大，特別是不同深度層的聲學(xué)特性差異很大，導(dǎo)致了聲波在海洋中的傳播非常復(fù)雜，聲傳播受海洋信道的影響比人們想象的要大得多。要提高聲納的探測(cè)效果，必須要充分研究海洋信道特點(diǎn)。

3. 匹配場(chǎng)被動(dòng)定位技術(shù)

匹配場(chǎng)聲源定位是國(guó)際上新興的水聲定位方法，它根據(jù)海洋聲信道性，在聲場(chǎng)建模的基礎(chǔ)上，運(yùn)用一定的匹配場(chǎng)處理算法反演聲源位置。匹配場(chǎng)定位技術(shù)充分利用了海洋信道特點(diǎn)來(lái)反演聲源位置，因此它可以有效消除信道對(duì)定位的影響，它的定位精度比傳統(tǒng)的被動(dòng)定位精度高。

3.1 匹配場(chǎng)被動(dòng)定位原理[1]

匹配場(chǎng)定位的被動(dòng)原理圖如圖1所示。匹配場(chǎng)定位首先將水聽(tīng)器陣列接收到的數(shù)據(jù)經(jīng)過(guò)傅立葉變換后計(jì)算頻域協(xié)防方差矩陣。假設(shè)聲場(chǎng)中某一位置有目標(biāo)，已知海洋聲場(chǎng)環(huán)境參數(shù)時(shí)，利用現(xiàn)有的聲場(chǎng)模型可以計(jì)算出該目標(biāo)聲源產(chǎn)生聲信號(hào)在接收水聽(tīng)器陣列處的聲場(chǎng)值，通常稱(chēng)之為拷貝場(chǎng)向量。最后將拷貝場(chǎng)向量和測(cè)量信號(hào)的協(xié)方差矩陣進(jìn)行匹配運(yùn)算從而輸出定位模糊表面，如果實(shí)際目標(biāo)位置與假設(shè)聲源位置一致，則匹配處理器有最大值輸出，這樣從定位模糊表面上可以讀出目標(biāo)的位置。

圖1 匹配場(chǎng)定位原理圖。

3.2 匹配場(chǎng)被動(dòng)定位關(guān)鍵技術(shù)及發(fā)展趨勢(shì)

匹配場(chǎng)定位有兩個(gè)重要環(huán)節(jié)，一是拷貝聲場(chǎng)的計(jì)算，二是匹配處理器的設(shè)計(jì)?？截惵晥?chǎng)可利用現(xiàn)有的聲場(chǎng)模型計(jì)算得到。，動(dòng)目標(biāo)分析?，F(xiàn)有的聲場(chǎng)模型主要有簡(jiǎn)正波模型、聲線模型、拋物方程模型等。其中，最常用的2種傳播模型是射線模型和簡(jiǎn)正波模型。射線模型具有簡(jiǎn)捷、直觀的特點(diǎn)，適用于描述深海聲場(chǎng)。在淺海存在嚴(yán)重的多途和較強(qiáng)的海底散射，射線模型不再適用。簡(jiǎn)正波模型考慮了各種海底邊界的影響，適用于研究淺海、低頻的聲傳播問(wèn)題。目前聲傳播模型的研究主要集中在快速、高精度的聲場(chǎng)模型的研究上。

匹配處理器就是將拷貝場(chǎng)與實(shí)測(cè)聲場(chǎng)進(jìn)行匹配運(yùn)算的算法，從理論上來(lái)說(shuō)，匹配場(chǎng)處理器是傳統(tǒng)的陣列信號(hào)處理的波束形成概念的推廣，因此，很多傳統(tǒng)的陣列處理方法都可以用于匹配場(chǎng)處理，而且人們已經(jīng)證明其中的很多方法是很有效的。按照匹配場(chǎng)處理器的權(quán)向量是否與測(cè)量數(shù)據(jù)有關(guān)，將其分為線性匹配處理器（CMFP）和自適應(yīng)匹配處理器(AMFP)。常用的MFP處理器有線性處理器(Bartlett)、最小方差估計(jì)器(MV)和匹配模處理器(MMP)。隨著人們對(duì)傳播理論研究的深入以及陣處理技術(shù)的飛速發(fā)展，匹配場(chǎng)處理技術(shù)的研究取得了一些突破性的進(jìn)展。近年來(lái)，匹配場(chǎng)處理技術(shù)逐漸走向?qū)嵱秒A段，寬帶、穩(wěn)健自適應(yīng)[1]、高分辨率[2]的匹配場(chǎng)處理技術(shù)成為研究熱點(diǎn)，以試驗(yàn)研究帶動(dòng)理論研究成為主要的研究方法。，動(dòng)目標(biāo)分析。

4.水下GPS定位

水下GPS技術(shù)的設(shè)計(jì)靈感來(lái)自于GPS,該技術(shù)可以用于潛艇定位，進(jìn)行爆炸軍火處理，還能用于水雷對(duì)抗許多領(lǐng)域。水下GPS利用空間GPS系統(tǒng)在海洋中布放一系列聲納浮標(biāo)，形成網(wǎng)格，在水面用空間GPS，在水下用水聲通信。法國(guó)的ASCA公司已經(jīng)開(kāi)發(fā)了用水下全球定位系統(tǒng)進(jìn)行搜索與救援的系統(tǒng)，它可以利用水下的GPS信號(hào)確目標(biāo)的三維坐標(biāo)。，動(dòng)目標(biāo)分析。該系統(tǒng)可以用于跟蹤水下的飛機(jī)或潛艇中黑匣子的聲波發(fā)器，從而找到目標(biāo)。系統(tǒng)包括GPS浮標(biāo)，控制站及聲波發(fā)送器。浮標(biāo)下有水聽(tīng)器，浮標(biāo)通過(guò)水面上的三個(gè)天線與指揮、控制、通信等系統(tǒng)聯(lián)系。利用目標(biāo)發(fā)射的信號(hào)與浮標(biāo)接收信號(hào)的時(shí)間延遲得到浮標(biāo)和目標(biāo)的相對(duì)位置，同時(shí)，利用分GPS接收機(jī)能精確測(cè)量出浮標(biāo)的精確位置?？臻gGPS技術(shù)已相當(dāng)成熟。，動(dòng)目標(biāo)分析。

5.結(jié)束語(yǔ)

由于傳統(tǒng)的被動(dòng)定位方法在理論和實(shí)際應(yīng)用中都存在一些問(wèn)題，研究人員致力于研究新的被動(dòng)定位方法，其中匹配場(chǎng)被動(dòng)定位技術(shù)充分利用了海洋信道，在遠(yuǎn)距離復(fù)雜水文條件下，其定位精度較高，有著誘人的應(yīng)用前景，隨著研究的不斷深入，這項(xiàng)技術(shù)正逐步走向?qū)嵱秒A段，但匹配場(chǎng)的模型精確性，匹配算法的計(jì)算速度以及匹配場(chǎng)的定位的穩(wěn)健性問(wèn)題還急需解決。水下GPS技術(shù)系統(tǒng)使用條件相對(duì)苛刻，不適用于非合作被動(dòng)目標(biāo)的探測(cè)，工程應(yīng)用受到了一定的限制。

參考文獻(xiàn)：

[1]楊坤德,等.水聲信號(hào)的匹配場(chǎng)處理技術(shù)研究[D].西北工業(yè)大學(xué),2003,06.

[2]周俊山，陶進(jìn)緒等.一種基于MUSIC算法的匹配場(chǎng)定位方法[J].電子技術(shù)，2010，01：21～23.

篇(7)

本文基于對(duì)大規(guī)模出租車(chē)GPS數(shù)據(jù)進(jìn)行分析，結(jié)合交通量OD分布概率模型計(jì)算熱點(diǎn)小區(qū)的交通量，給出擁堵預(yù)測(cè)模型，幫助城市管理者更好地管理城市交通管理問(wèn)題。

【關(guān)鍵詞】城市交通擁堵 GPS終端定位 OD分布概率

1 研究背景

出租車(chē)是城市客運(yùn)交通的重要組成部分，是常規(guī)公共交通的重要補(bǔ)充。隨著出租車(chē)數(shù)量的不斷增長(zhǎng)，出租車(chē)交通量已成為城市道路交通總量中的重要組成部分，成為影響城市道路交通分布及分配預(yù)測(cè)準(zhǔn)確性的重要因素之一。由于出租車(chē)運(yùn)行的隨機(jī)性，沒(méi)有固定的起訖點(diǎn)和運(yùn)行線路，給定量分析帶來(lái)一定的困難。

各大城市越來(lái)越多的出租車(chē)的安裝了GPS終端，這些終端能夠每隔1分鐘向出租車(chē)管理中心發(fā)送本車(chē)的位置、速度和方向等信息，是車(chē)輛GPS實(shí)時(shí)數(shù)據(jù)。原始數(shù)據(jù)主要保存出租車(chē)上裝配的GPS終端所采集的數(shù)據(jù)，這些數(shù)據(jù)包括序號(hào)，車(chē)牌號(hào)碼，GPS時(shí)間，經(jīng)度，緯度，車(chē)輛狀態(tài)（空車(chē)、重車(chē)），車(chē)輛速度，車(chē)輛方向（8個(gè)方向）等信息。這些GPS數(shù)據(jù)為我們研究出租車(chē)交通情況題共了參考和依據(jù)。

2 傳統(tǒng)交通分析模型存在的問(wèn)題

現(xiàn)階段在交通擁堵方面主要集中在研究某個(gè)路口的情況，并且用緩沖區(qū)方法，而沒(méi)有對(duì)整個(gè)區(qū)域有個(gè)整體的描述，而對(duì)于整個(gè)區(qū)域的研究則是基于交通需求建立模型，數(shù)據(jù)采集的精度不高。

目前公共交通設(shè)施是最常見(jiàn)的移動(dòng)軌跡數(shù)據(jù)采集途徑。從已有的研究工作看，針對(duì)移動(dòng)軌跡數(shù)據(jù)的分析碰到的問(wèn)題可能有：

2.1 數(shù)據(jù)存儲(chǔ)

大規(guī)模軌跡數(shù)據(jù)的存儲(chǔ)一般都采用基于R-tree索引（或在R-tree基礎(chǔ)上改良的索引，如Quad-tree）的數(shù)據(jù)庫(kù)，這類(lèi)索引的好處是給定查詢點(diǎn)以后，可以從查詢點(diǎn)所在索引結(jié)點(diǎn)出發(fā)，沿著樹(shù)型索引依次訪問(wèn)到離查詢點(diǎn)距離越來(lái)越遠(yuǎn)的被索引的點(diǎn)；最近，有很多研究者提出了針對(duì)路網(wǎng)距離的索引，使得路網(wǎng)距離下也可以類(lèi)似的由近及遠(yuǎn)的訪問(wèn)被索引的點(diǎn)?；谝陨线@類(lèi)索引結(jié)構(gòu)，kNNT問(wèn)題可以轉(zhuǎn)化為信息檢索領(lǐng)域中的聚合Top-k查詢問(wèn)題。

2.2 地圖匹配問(wèn)題

地圖匹配算法可以按照其考慮的軌跡范圍分成全局算法和局部算法。局部算法又稱(chēng)遞增式算法，該類(lèi)方法采用貪心的策略依次將每個(gè)軌跡點(diǎn)匹配到相應(yīng)的路段上。這類(lèi)算法通?；诰嚯x和角度的相似性，對(duì)于每個(gè)軌跡點(diǎn)找到局部最優(yōu)的路段進(jìn)行匹配。

2.3 移動(dòng)數(shù)據(jù)的收集與處理問(wèn)題

現(xiàn)階段針對(duì)交通擁堵的研究主要集中在交通路口，對(duì)數(shù)據(jù)的收集主要為車(chē)輛的行駛速度與方向信息，其中不包含車(chē)輛的具體信息如車(chē)牌、車(chē)輛具置等，這樣不能夠做到對(duì)行駛車(chē)輛的實(shí)時(shí)監(jiān)測(cè)和數(shù)據(jù)的精確處理。

2.4 缺少居民出行信息

在研究擁堵問(wèn)題時(shí)必須要考慮到對(duì)周邊居民的影響，之前的算法中不包含此類(lèi)信息，諸如周邊小區(qū)居民出行的高峰時(shí)段與高峰時(shí)間，不能做到將這些信息及時(shí)的反饋。

3 基于移動(dòng)數(shù)據(jù)的擁堵預(yù)測(cè)算法

3.1 算法的詳細(xì)過(guò)程

本算法主要通過(guò)大規(guī)模出租車(chē)GPS數(shù)據(jù)進(jìn)行分析，結(jié)合路網(wǎng)信息，首先獲取熱點(diǎn)區(qū)域和熱點(diǎn)小區(qū)；其次結(jié)合交通量OD分布概率模型計(jì)算熱點(diǎn)小區(qū)的交通量，然后計(jì)算各個(gè)小區(qū)的總體出行情況，從而獲取各小區(qū)的交通出行量，同時(shí)結(jié)合時(shí)間信息查找各時(shí)段擁堵路段和擁堵路口，最后依據(jù)上述信息得到具體的算法過(guò)程：

（1）首先，由安裝在各個(gè)出租車(chē)上的GPS裝置得到實(shí)時(shí)的出租車(chē)載客信息，包含著各個(gè)時(shí)刻出租車(chē)的位置信息。我們可以利用馬克威分析系統(tǒng)中關(guān)于快速聚類(lèi)的方法來(lái)對(duì)各小區(qū)進(jìn)行劃分，得到每個(gè)小區(qū)的具體坐標(biāo)和熱點(diǎn)小區(qū)的具置信息。

（2）其次，通過(guò)建立的交通量OD分布概率模型，利用Bayes方法對(duì)該模型進(jìn)行參數(shù)估計(jì)與效果檢驗(yàn)，由馬克威分析系統(tǒng)得到各小區(qū)的交通量信息，求解出交通量的OD分布。

（3）再次，通過(guò)得到的小區(qū)交通量的OD分布，來(lái)繪制各熱點(diǎn)小區(qū)交通量的分布模型。

（4）然后，通過(guò)采集周邊各小區(qū)的居民出行數(shù)據(jù)，得到各小區(qū)居民出行的高峰時(shí)段與出行的熱點(diǎn)小區(qū)區(qū)域，并且將得到的熱點(diǎn)出行區(qū)域信息與上面步驟中得到的出租車(chē)出行的熱點(diǎn)小區(qū)區(qū)域進(jìn)行匹配，得到交叉地帶。

（5）最后，通過(guò)收集出租車(chē)的GPS數(shù)據(jù)，篩選出有用的數(shù)據(jù)，由上述算法，便可以查找到車(chē)輛比較擁堵的路段與時(shí)段信息。將該信息與上面采集到的居民出行的高峰時(shí)段與熱點(diǎn)小區(qū)區(qū)域進(jìn)行比較匹配，即可得到居民出行的擁堵路段與時(shí)段信息。

3.2 算法的創(chuàng)新之處

針對(duì)大規(guī)模軌跡數(shù)據(jù)的分析問(wèn)題，現(xiàn)有的解決思路往往都是通過(guò)構(gòu)造地圖來(lái)進(jìn)行熱點(diǎn)掃描和偏好軌跡掃描。針對(duì)大規(guī)模軌跡數(shù)據(jù)，之前已經(jīng)完成了離線預(yù)處理、頻繁軌跡圖模型、以及在線打車(chē)推薦部分算法。本算法的關(guān)鍵特色是從大規(guī)模GPS數(shù)據(jù)快速抽取熱點(diǎn)和熱點(diǎn)小區(qū)，然后繪制頻繁小區(qū)地圖，結(jié)合交通量分析計(jì)算熱點(diǎn)小區(qū)出行量，再根據(jù)各個(gè)小區(qū)的總體出行情況，獲取各個(gè)小區(qū)的交通出行量，從而查找各時(shí)段擁堵路段和擁堵路口，根據(jù)上述參數(shù)獲取擁堵預(yù)測(cè)模型。具體說(shuō)來(lái)，本算法的創(chuàng)新之處有：

（1）由安裝在出租車(chē)上的GPS得到出租車(chē)每個(gè)時(shí)段的行駛信息，可以得到實(shí)時(shí)的運(yùn)行信息。

（2）設(shè)計(jì)與實(shí)現(xiàn)了熱點(diǎn)和熱點(diǎn)小區(qū)的識(shí)別算法。

（3）建立交通量OD分布概率模型，求解出交通量的OD分布。

（4）由采集到的GPS數(shù)據(jù)動(dòng)態(tài)構(gòu)造各個(gè)時(shí)段擁堵路段和路口的計(jì)算模型。得到擁堵路段與時(shí)段模型。

（5）增加了居民的出行信息，通過(guò)采集到的小區(qū)居民出行高峰時(shí)段與路段信息與出租車(chē)擁堵路線進(jìn)行匹配，可以得出居民出行的擁堵區(qū)域與時(shí)段信息，更加方便小區(qū)居民進(jìn)行出行選擇，同時(shí)提高了該算法的應(yīng)用性。

4 結(jié)論

當(dāng)前是一個(gè)信息爆炸的年代，由于物聯(lián)網(wǎng)技術(shù)的發(fā)展，我們已經(jīng)進(jìn)入了大數(shù)據(jù)時(shí)代。

本文基于GPS終端的海量數(shù)據(jù)，計(jì)算隨時(shí)間變化的車(chē)流狀態(tài)，結(jié)合交通量分布OD分布概率模型來(lái)計(jì)算熱點(diǎn)小區(qū)的交通量，最終得到擁堵的預(yù)測(cè)模型，可有效地幫助城市管理者管理城市交通和小區(qū)居民選擇更加合適的出行方式與時(shí)間，在北京、上海等大中城市具有很高的應(yīng)用前景。

參考文獻(xiàn)

[1]黃鳳忖.電信運(yùn)營(yíng)業(yè)發(fā)展的影響因素分析[D].首都經(jīng)貿(mào)大學(xué)碩士學(xué)位論文，2005（03）.

[2]李勇平.遺傳神經(jīng)網(wǎng)絡(luò)在電信業(yè)務(wù)收入預(yù)測(cè)中的應(yīng)用研究[J].商場(chǎng)現(xiàn)代化，2008（11）.

[3]胡德敏，曹桓.四網(wǎng)協(xié)同無(wú)線網(wǎng)絡(luò)規(guī)劃策略與綜合評(píng)價(jià)研究[J].通信管理與技術(shù)，2012（12）.