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

篇(1)

【關鍵詞】藏文分詞 匹配算法 哈希表 詞典機制

1 引言

藏文信息處理存在著分詞的問題，而藏文分詞是對藏文詞性標注、藏語音合成、機器翻譯、大型語料庫建設和信息檢索等藏文信息處理的基礎。藏文分詞的效果會對進一步研究的藏文詞性標注、藏語音合成、機器翻譯、大型語料庫建設和信息檢索等藏文信息處理軟件的性能和效果產生影響。

為了提高分詞的準確率，需要有一個足夠大的詞庫，面對足夠大的詞庫，對詞庫中的詞語的搜索技術就顯得十分重要，對詞庫中詞語的搜索速度直接關系到分詞系統的性能。詞庫目前主要是采用索引的機制來實現的，一般用到的索引結構的包括線性索引、倒排表、Trie樹、二叉樹等。線性索引、倒排表都是靜態的索引結構，不利于插入、刪除等操作。

2 分詞

2.1 詞典機制算法

本系統采用的是基于Hash索引的分詞詞典。分詞詞典機制可以看作包含三個部分：首字Hash表、詞索引表、詞典正文。詞典正文是以詞為單位txt文件，匹配過程是一個全詞匹配的過程。首先，通過首字Hash表確定該詞在詞典中的大概位置，然后根據詞索引表進行定位，進而找到在詞典正文中的具置。該系統是采用Myeclipse10平臺，使用Java語言進行實現的，直接調用Java里的hashmap創建函數，找到該詞之后，然后進行字符串匹配。

2.2 基于匹配算法分詞

主流的分詞方法有三種：分別為基于語言學規則的方法、基于大規模語料庫的機器學習方法、基于規則與統計相結合的方法，鑒于目前藏文方面還沒有超大型的句子語料庫。該系統便采用了基于語言學規則的根據詞典進行匹配的方法對藏文進行分詞。

根據匹配的方向不同，分為正向和逆向兩種匹配算法。本系統采用的是正逆向匹配算法相結合的減字匹配法對藏文進行分詞的，因為藏文在每個字的結束時，都會以“”作為分界；每個句子會以“”或者“” 作為分界。因此，對藏文進行分詞的減字算法首先以藏文的字符“”或者“”切分出句子，如此一來，原文就被分為相應的若干個句子了。接下來，再對每一個句子進行詞典的匹配，如果沒有匹配成功就根據藏文字符中“”從句末尾減去一個字符，然后再次進行匹配，直到匹配成功為止。對每個句子重復這些流程，直到每個句子全部分解為詞為止。逆向最大匹配是從句子的末尾選擇計算最大詞的長度，從后往前匹配、切分，其基本原理是和正向最大匹配的原理是相同的。

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

本系統的逆向最大匹配和正向最大匹配均是采用減字匹配算法，減字算法實現簡單，切分效果也比較理想，流程如圖1所示。

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

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

3 結果和分析

結合26個大小不同的實驗文本，對基于哈希表索引和匹配算法的分詞系統的準確率進行了分析，準確率如圖3所示。結果顯示，該分詞系統的準確率在92%以上。由此可得基于哈希表索引和匹配算法的分詞系統在準確率上有不錯的效果。

參考文獻

[1]華卻才讓.基于樹到串藏語機器翻譯若干關鍵技術研究[D].陜西師范大學，2014.

[2]石方夏，邱瑞，張|，任帥.藏文信息隱藏技術綜述[J].物聯網技術，2014，12：28-32.

[3]王思力，張華平，王斌.雙數組Trie樹算法優化及其應用研究[J].中文信息學報，2006，05：24-30.

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

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

[6]奉國和，鄭偉.國內中文自動分詞技術研究綜述[J].圖書情報工作，2011，02：41-45.

[7]賀艷艷.基于詞表結構的中文分詞算法研究[D].中國地質大學（北京），2007.

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

[9]劉遙峰，王志良，王傳經.中文分詞和詞性標注模型[J].計算機工程，2010，04：17-19.

作者簡介

陳碩（1995-），男，自治區拉薩市人。本科在讀，主研領域為自然語言處理，數學建模及其應用。

周歡歡（1994-），女，湖南省衡陽市人。本科在讀，研究方向為數學建模及其應用、交通運輸規劃與管理。

通訊作者簡介

趙棟材（1976-），男，現為大學藏文信息技術研究中心副教授。主要研究方向為藏文信息處理。

作者單位

篇(2)

關鍵詞：入侵檢測；KMP算法；BM算法；RK算法；AC算法；AC－BM算法

中圖分類號：TP301文獻標識碼：B

文章編號：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 引 言

隨著網絡技術的發展，各種基于網絡的應用層出不窮。面對日益突出的網絡安全問題，僅靠傳統的被動防御已經不能滿足要求，能夠主動檢測并預防的入侵檢測系統應運而生。

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

由此可見，模式匹配算法性能的好壞直接影響到入侵檢測系統的效率。隨著網絡傳輸速度的大幅度提高，入侵檢測系統需要處理的數據量越來越大，如果模式匹配算法來不及處理這些實時的大量的數據包，必然會丟棄部分數據包，而這些被丟棄的數據包中很可能就包含有入侵信息，從而造成漏報。在此介紹幾種著名的用于入侵檢測的模式匹配算法，包括單模式匹配算法和多模式匹配算法，通過對它們進行剖析和實際測試，提出入侵檢測系統中模式匹配算法的選擇策略和未來的研究方向。

1 單模式匹配算法

1.1 相關定義

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

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

單模式匹配算法：在目標串中1次只能對1個模式串進行匹配的算法。

多模式匹配算法：在目標串中可同時對多個模式串進行匹配的算法。

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

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

1.2 KMP算法

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

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

定義next［j］函數為：

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

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

0，其他情況

-1(標記)，j=0時

1.3 BM算法

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

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

(3) g是轉移函數，該函數定義如下：g(s,a)：從當前狀態s開始，沿著邊上標簽為a的路徑所到的狀態。假如(u,v )邊上的標簽為a，那么g ( u,a ) =v；如果根節點上出來的邊上的標簽沒有a，則g(0,a) =0，即如果沒有匹配的字符出現，自動機停留在初態；

(4) f(不匹配時自動機的狀態轉移)也是轉移函數，該函數定義如下：

f(s)：當w是L(s)最長真后綴并且w是某個模式的前綴，那么f(s)就是以w為標簽的那個節點；

(5) q0∈Q是初態(根節點，標識符為0)；

(6) FQ，是終態集(以模式為標簽的節點集)。

這樣，在目標串中查找模式的過程轉化成在模式樹中的查找過程。查找一個串T時從模式樹的根節點開始，沿著以T中字符為標簽的路徑往下走：若自動機能夠抵達終態v，則說明T中存在模式L (v)；否則不存在模式。

AC算法模式匹配的時間復雜度是O(n)，并且與模式集中模式串的個數和每個模式串的長度無關。無論模式串P是否出現在目標串T中，T中的每個字符都必須輸入狀態機中，所以無論是最好情況還是最壞情況，AC算法模式匹配的時間復雜度都是O(n)，包括預處理時間在內，AC算法總時間復雜度是O(M+n)，其中M為所有模式串的長度總和。

2.3 AC－BM算法

對多模式串的匹配而言，雖然AC算法比BM算法高效得多，但AC算法必須逐一查看目標串的每個字符，即必須按順序輸入，不能實現跳躍，而BM算法則能夠利用“右滑”跳過目標串中的大段字符，從而提高搜索速度。如果將BM算法的這種啟發式搜索技術應用到AC算法中，則可大大提高多模式匹配算法的效率。許多人據此給出了各種改進的算法。Commentz－Walter最先將BM算法和AC算法結合在一起給出了Commentz－Walter算法；Baeza－Yates結合BMP算法和AC算法也給出了多模式匹配改進算法。

AC－BM算法［5］是Jang－Jong在1993年結合AC算法的有限自動機和BM算法的連續跳躍思想提出來的新算法，利用劣勢移動表和優勢跳轉表來實現跳躍式地并行搜索，算法的時間復雜度為O(mn)。

該算法的思想是：首先把要查找的多個模式構成一個關鍵字樹，把相同的前綴作為樹的根節點。模式樹從目標串的右端向左移動，一旦模式樹確定在適當的位置，字符比較從左向右開始進行。模式樹移動時同時使用壞字符移動和好前綴移動。壞字符移動的策略為:如果出現不匹配的情況，移動模式樹，使得樹中其他模式的能與當前目標串正在比較的字符相匹配的那個字符移動到與當前目標串正在比較的字符的相同位置上，如果在當前的深度上，目標字符沒有出現在任何模式中，則模式樹的偏移量為樹中最短模式的長度。好前綴移動的移動策略為：將模式樹移動到一個已被發現是另一個模式子串完全前綴的下一個位置，或者移動到作為樹中另一個模式后綴能夠正確匹配目標串的某個前綴的下一個位置。在模式樹的移動過程中，必須確保模式樹的偏移量不能大于樹中最短的模式長度。

2.4 AC，AC－BM算法改進情況簡介

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

3 算法的實際執行效率

上述這些算法究竟哪種算法具有最好的執行效率呢?能不能僅通過時間復雜度來進行衡量呢？時間復雜度僅是一個度量的范圍，表示受幾個參數的影響，并不代表一個具體的值，還需要在具體的環境中進行測試。

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

單模式匹配算法主要測試模式長度與匹配時間、占用空間及預處理時間的變化關系。測試結果表明：各算法的測試指標在規則長度增長的情況下均呈遞增趨勢，但BM算法的增長速度最為緩慢，在不太在意存儲空間的情況下，BM可以作為優先考慮的算法，同時對IPV6地址也更為合適。

多模式匹配算法的測試項目為規則數與單位匹配時間、占用儲存單元、單位預處理時間的變化關系。測試結果表明AC－BM算法在上述3項測試中取得了很好的性能平衡。這也是新

版的Snort系統中選用AC－BM算法的重要原因。

4 入侵檢測系統中模式匹配算法的研究方向

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

5 結 語

網絡帶寬的不斷增加、日益嚴重的網絡安全狀況要求必須盡快提高網絡入侵檢測系統的性能。雖然入侵檢測系統可以采用很多技術，并且這些技術也在不斷的研究和發展中，但是目前主流的實用的入侵檢測技術仍然是基于模式匹配的。因此如何提高模式匹配的效率成為研究入侵檢測系統的一個關鍵所在。在此對已有的經典模式匹配算法進行了系統綜述，并對入侵檢測系統中模式匹配算法的未來研究方向給出了觀點。

參考文獻

［1］龐善臣,王淑棟,蔣昌俊.BM串匹配的一個改進算法［J］.計算機應用,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］張立航,潘正運,劉海峰.基于改進的KR算法在網閘中的實現［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］黃占友,劉悅.對KMP串匹配算法的改進［A］.第四次全國便攜計算機學術交流會論文集［C］.北京:科學出版社,1997.

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

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

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

［10］盧汪節,鞠時光.入侵檢測系統中一種改進的AC算法［J］.計算機工程與應用,2006(15):146－148.

［11］萬國根,秦志光.改進的AC－BM字符串匹配算法［J］.電子科技大學學報,2006,35(4):531－533.

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

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

作者簡介

冉占軍 男，1977年出生，陜西西安人，講師，碩士研究生。主要研究方向為算法、網絡安全。

姚全珠 男，1960年出生，博士，教授。主要研究方向為算法、數據庫、網絡安全。

篇(3)

關鍵詞:點云數據;配準;ICP算法

中圖分類號:TP391.7 文獻標識碼: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

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

由于每次測量得到的點云數據往往只覆蓋物體部分表面,并且可能出現平移錯位和旋轉錯位,為了得到物體完整表面的點云數據,需要對這些局部點云數據進行整合和配準。因此,在得到點云數據之后,為了得到三維模型的原始曲面,必須要將不同角度,不同位置掃描得到的大容量三維空間數據點集轉換到一個統一的坐標系中,該技術稱之為數據縫合,即三維點云數據的配準。點云配準是點云數據獲取后的第一步處理,也是所有后續處理的基礎。因此,配準的精度將直接關系到建模精度。

1 點云數據配準算法的研究進展

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

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

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

2 ICP點云數據配準算法及其改進算法

ICP算法最初由Besl和McKay,提出來的時候,其原意是迭代最近點(IterativeClosestpoint)匹配算法,后來被廣泛理解為迭代對應點(IterativeCorrespondingpoint)匹配算法。ICP法實質上是基于最小二乘法的最優匹配方法,它重復進行“確定對應關系點集并計算最優剛體變換”的過程,直到某個表示正確匹配的收斂準則得到了滿足。目前,ICP算法在點云數據配準中應用相當廣泛,并且得到了許多學者的進一步研究和擴充。基于ICP算法點云數據配準過程如圖1所示:

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

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

整個ICP算法描述如下:

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

第二步:迭代步驟:

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

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

(3)根據變換矩陣Pk=( PR k | PT k )T變換當前掃描模型Sr中的所有掃描點位置。

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

ICP算法是一種迭代算法,具有很高的匹配精度。但由算法描述可知,它存在計算量較大且迭代過程可能無法收斂到全局最優解的缺陷。ICP算法最耗費時間的步驟是求解鄰近點對的過程,因為它采用的是全局搜索。為適應不同的環境并克服ICP算法自身的部分缺陷,許多研究人員對其進行了改進。

2.2ICP的改進算法

為了提高基本ICP方法的可靠性和魯棒性,從匹配點的選擇到最小二乘度量目標函數的選取等ICP匹配算法中的各個階段,許多研究者都提出了各種的優化方法,形成了相應的ICP變型算法。ICP算法的各個階段劃分如下[3]:

(1)匹配模型中進行匹配的數據點的選取采樣;

(2)兩模型中有對應關系的匹配點對的選擇;

(3)匹配點對的適當權值賦予;

(4)過濾某些錯誤的匹配點對;

(5)度量準則的選取;

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

對ICP算法的改進主要集中在如下四點[4]:

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

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

(3)點對的拒絕。點對拒絕的實現主要有以下三種情況:對于邊緣點的拒絕;對于對應點對中距離過大的點對的拒絕;考慮法向量的點對的拒絕。

(4)加速迭代。主要采用減少迭代次數或使用非迭代的方法來實現,作用是減少運算量,提高計算速度。

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

3 結束語

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

參考文獻:

[1]張舜德,朱東波,盧秉恒.反求工程中三維幾何形狀測量及數據預處理[J].機電工程技術,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]潘小林.三維曲面匹配技術研究[D].南京航空航天大學碩士論文,2004.

篇(4)

關鍵詞：SIFT；相似性度量；圖像匹配

引言

在計算機視覺領域，圖像匹配仍然是當前研究的熱點問題。基于特征的匹配方法[1]，因為根據圖像中趨于穩定的少量特征進行匹配，使得運算速度快、匹配效果好，所以成為目前研究最多、應用最廣泛的一種方法。但是，這種方法需要在圖像間進行遍歷性的匹配運算，存在計算量大，且精度不高的問題。

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

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

1 特征提取

1.1 SIFT特征提取

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

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

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

1.2 顏色特征提取

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

HSI顏色模型中，H表示色調，指的是人的感官對不同顏色的感受，描述純色的屬性；S表示飽和度，描述的是顏色的純度；I表示強度，描述的是顏色的明亮程度。

常用的最近鄰方法原理是，對于基準圖像中的每個特征點，在待匹配圖像中尋找距離最近的特征點，然后形成一組匹配對。因為最近鄰獲得的匹配對中存在大量的誤匹配，所以Lowe在論文[8]中對于基準圖像中的每個特征點，在待匹配圖像中尋找距離最近和次近的兩個特征點，當這兩個距離的比值小于預設的閾值時，才認為找到了一組正確的匹配對，這樣消除了大量的誤匹配，取得了不錯的匹配效果。文章設閾值為thr，且0

3 實驗結果及分析

為了觀察算法性能，我們從互聯網上尋找了兩張有重疊部分的壁畫圖片進行了實驗。圖像如圖1所示。采用Matlab7.7.0編程，運行在AMD A6-3400M CPU 1.4GHZ和4G內存的PC機上，Windows 7.0操作系統。

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

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

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

4 結束語

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

參考文獻

[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]張書真，宋海龍，向曉燕，等.采用快速SIFT算法實現目標識別[J].計算機系統應用，2010，19（6）：82-85.

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

[5]鐘金琴，檀結慶，李瑩瑩，等.基于二階矩的SIFT特征匹配算法[J].計算機應用，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]何川.高壓輸電線路視頻監控技術研究[D].北京：北京交通大學，2012.

篇(5)

[關鍵詞]模糊匹配 模糊查找 位置匹配 C語言算法

[中圖分類號]TP391.41 [文獻標識碼]A [文章編號]1009-5349（2013）02-0061-01

引言

為了提升用戶撥號的快捷性，要求用戶在輸入號碼的時候，對用戶已輸入號碼進行模糊匹配，并以列表的形式呈現給用戶，供用戶選擇。用戶使用手機鍵盤撥號速度最快不超過100毫秒，這就要求手機必須在100毫秒以內查找結束并把結果呈現給用戶。而手機號碼、SIM卡號碼、最近通訊錄號碼總和在3000個左右。利用傳統的字符串查找已不能滿足要求。

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

一、算法實現

本算法使用以空間換取時間的辦法，通過記錄不同數字所在的位置，并通過移位操作來實現模糊查找。此算法復雜度僅僅和用戶輸入的字符串長度有關，而和實際的字符串長度無關。因此，不同于常規的字符串查找算法。

（一）字符映射

首先，把手機號碼中存在的字符映射成16個字符，方法為：把字符“0”-“9”轉換成數字0～9；把“*”“#”“+”“p”“w”分別轉換成數字10、11、12、13、14；把可能存在的字符“-”或其他字符轉換成數字15。

（二）數據結構定義

用元素來定義電話號碼的存儲結構，一個元素存儲一個號碼。格式可以如下：

typedef struct

{tCellType nData[16]；

}tElement；

其中tCellType可以為unsigned short或unsigned long。前者代表可容納電話號碼的最大長度為16，后者代表可容納的最大長度為32（32位機器下）。

（三）數據結構建立

把一個電話號碼放到一個元素中去，保證：元素中nData[0]記錄數字0所在的位置，nData[1]記錄數字1所在的位置，依次類推，nData[15]記錄數字15所在的位置。

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

舉例：假如電話號碼為“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。

（四）查詢方法

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

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

算法示例：取臨時變量tm，list為用戶輸入的待查找字符串通過字符映射得到的數組，n為字符串長度。

tCellType tm = nData[list[0]]；

for（i = 1； tm&&i

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

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

舉例：假如電話號碼為“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。

其他說明：實際應用中可以通過一定的方法記錄結果，新的查找基于上一次的查找結果進行查找，而沒有必要對所有記錄重新查找。

篇(6)

關鍵詞：被動定位，匹配場，水下GPS，動目標分析

 

1.引言

聲納按照工作方式一般分為主動聲納和被動聲納。對于被動聲納，由于它不發射聲波，它具有很好的隱蔽性，且具有作用距離遠、不容易被發現等優點，在軍事領域中有著很好的應用前景。近年來，世界各國都加緊了對被動定位技術的研究和開發，被動定位技術受到廣泛的重視。隨著水中兵器作用距離和打擊精度的提高，對被動聲納的定位性能提出了更高的要求，遠程定位問題引起人們的廣泛關注，出現了多種新型的定位方法。

2.傳統被動聲納定位技術及面臨的問題

2.1 傳統的被動定位技術

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

2.2 傳統被動聲納定位技術面臨的問題

傳統被動定位方法在理論和實際應用中都存在很大的缺陷，主要表現在以下兩個方面。

2.2.1 遠程定位精度不高

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

2.2.2 定位效果受聲場環境影響大

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

3. 匹配場被動定位技術

匹配場聲源定位是國際上新興的水聲定位方法，它根據海洋聲信道性，在聲場建模的基礎上，運用一定的匹配場處理算法反演聲源位置。匹配場定位技術充分利用了海洋信道特點來反演聲源位置，因此它可以有效消除信道對定位的影響，它的定位精度比傳統的被動定位精度高。

3.1 匹配場被動定位原理[1]

匹配場定位的被動原理圖如圖1所示。匹配場定位首先將水聽器陣列接收到的數據經過傅立葉變換后計算頻域協防方差矩陣。假設聲場中某一位置有目標，已知海洋聲場環境參數時，利用現有的聲場模型可以計算出該目標聲源產生聲信號在接收水聽器陣列處的聲場值，通常稱之為拷貝場向量。最后將拷貝場向量和測量信號的協方差矩陣進行匹配運算從而輸出定位模糊表面，如果實際目標位置與假設聲源位置一致，則匹配處理器有最大值輸出，這樣從定位模糊表面上可以讀出目標的位置。

圖1 匹配場定位原理圖。

3.2 匹配場被動定位關鍵技術及發展趨勢

匹配場定位有兩個重要環節，一是拷貝聲場的計算，二是匹配處理器的設計。拷貝聲場可利用現有的聲場模型計算得到。，動目標分析。現有的聲場模型主要有簡正波模型、聲線模型、拋物方程模型等。其中，最常用的2種傳播模型是射線模型和簡正波模型。射線模型具有簡捷、直觀的特點，適用于描述深海聲場。在淺海存在嚴重的多途和較強的海底散射，射線模型不再適用。簡正波模型考慮了各種海底邊界的影響，適用于研究淺海、低頻的聲傳播問題。目前聲傳播模型的研究主要集中在快速、高精度的聲場模型的研究上。

匹配處理器就是將拷貝場與實測聲場進行匹配運算的算法，從理論上來說，匹配場處理器是傳統的陣列信號處理的波束形成概念的推廣，因此，很多傳統的陣列處理方法都可以用于匹配場處理，而且人們已經證明其中的很多方法是很有效的。按照匹配場處理器的權向量是否與測量數據有關，將其分為線性匹配處理器（CMFP）和自適應匹配處理器(AMFP)。常用的MFP處理器有線性處理器(Bartlett)、最小方差估計器(MV)和匹配模處理器(MMP)。隨著人們對傳播理論研究的深入以及陣處理技術的飛速發展，匹配場處理技術的研究取得了一些突破性的進展。近年來，匹配場處理技術逐漸走向實用階段，寬帶、穩健自適應[1]、高分辨率[2]的匹配場處理技術成為研究熱點，以試驗研究帶動理論研究成為主要的研究方法。，動目標分析。

4.水下GPS定位

水下GPS技術的設計靈感來自于GPS,該技術可以用于潛艇定位，進行爆炸軍火處理，還能用于水雷對抗許多領域。水下GPS利用空間GPS系統在海洋中布放一系列聲納浮標，形成網格，在水面用空間GPS，在水下用水聲通信。法國的ASCA公司已經開發了用水下全球定位系統進行搜索與救援的系統，它可以利用水下的GPS信號確目標的三維坐標。，動目標分析。該系統可以用于跟蹤水下的飛機或潛艇中黑匣子的聲波發器，從而找到目標。系統包括GPS浮標，控制站及聲波發送器。浮標下有水聽器，浮標通過水面上的三個天線與指揮、控制、通信等系統聯系。利用目標發射的信號與浮標接收信號的時間延遲得到浮標和目標的相對位置，同時，利用分GPS接收機能精確測量出浮標的精確位置。空間GPS技術已相當成熟。，動目標分析。

5.結束語

由于傳統的被動定位方法在理論和實際應用中都存在一些問題，研究人員致力于研究新的被動定位方法，其中匹配場被動定位技術充分利用了海洋信道，在遠距離復雜水文條件下，其定位精度較高，有著誘人的應用前景，隨著研究的不斷深入，這項技術正逐步走向實用階段，但匹配場的模型精確性，匹配算法的計算速度以及匹配場的定位的穩健性問題還急需解決。水下GPS技術系統使用條件相對苛刻，不適用于非合作被動目標的探測，工程應用受到了一定的限制。

參考文獻：

[1]楊坤德,等.水聲信號的匹配場處理技術研究[D].西北工業大學,2003,06.

[2]周俊山，陶進緒等.一種基于MUSIC算法的匹配場定位方法[J].電子技術，2010，01：21～23.

篇(7)

本文基于對大規模出租車GPS數據進行分析，結合交通量OD分布概率模型計算熱點小區的交通量，給出擁堵預測模型，幫助城市管理者更好地管理城市交通管理問題。

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

1 研究背景

出租車是城市客運交通的重要組成部分，是常規公共交通的重要補充。隨著出租車數量的不斷增長，出租車交通量已成為城市道路交通總量中的重要組成部分，成為影響城市道路交通分布及分配預測準確性的重要因素之一。由于出租車運行的隨機性，沒有固定的起訖點和運行線路，給定量分析帶來一定的困難。

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

2 傳統交通分析模型存在的問題

現階段在交通擁堵方面主要集中在研究某個路口的情況，并且用緩沖區方法，而沒有對整個區域有個整體的描述，而對于整個區域的研究則是基于交通需求建立模型，數據采集的精度不高。

目前公共交通設施是最常見的移動軌跡數據采集途徑。從已有的研究工作看，針對移動軌跡數據的分析碰到的問題可能有：

2.1 數據存儲

大規模軌跡數據的存儲一般都采用基于R-tree索引（或在R-tree基礎上改良的索引，如Quad-tree）的數據庫，這類索引的好處是給定查詢點以后，可以從查詢點所在索引結點出發，沿著樹型索引依次訪問到離查詢點距離越來越遠的被索引的點；最近，有很多研究者提出了針對路網距離的索引，使得路網距離下也可以類似的由近及遠的訪問被索引的點。基于以上這類索引結構，kNNT問題可以轉化為信息檢索領域中的聚合Top-k查詢問題。

2.2 地圖匹配問題

地圖匹配算法可以按照其考慮的軌跡范圍分成全局算法和局部算法。局部算法又稱遞增式算法，該類方法采用貪心的策略依次將每個軌跡點匹配到相應的路段上。這類算法通常基于距離和角度的相似性，對于每個軌跡點找到局部最優的路段進行匹配。

2.3 移動數據的收集與處理問題

現階段針對交通擁堵的研究主要集中在交通路口，對數據的收集主要為車輛的行駛速度與方向信息，其中不包含車輛的具體信息如車牌、車輛具置等，這樣不能夠做到對行駛車輛的實時監測和數據的精確處理。

2.4 缺少居民出行信息

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

3 基于移動數據的擁堵預測算法

3.1 算法的詳細過程

本算法主要通過大規模出租車GPS數據進行分析，結合路網信息，首先獲取熱點區域和熱點小區；其次結合交通量OD分布概率模型計算熱點小區的交通量，然后計算各個小區的總體出行情況，從而獲取各小區的交通出行量，同時結合時間信息查找各時段擁堵路段和擁堵路口，最后依據上述信息得到具體的算法過程：

（1）首先，由安裝在各個出租車上的GPS裝置得到實時的出租車載客信息，包含著各個時刻出租車的位置信息。我們可以利用馬克威分析系統中關于快速聚類的方法來對各小區進行劃分，得到每個小區的具體坐標和熱點小區的具置信息。

（2）其次，通過建立的交通量OD分布概率模型，利用Bayes方法對該模型進行參數估計與效果檢驗，由馬克威分析系統得到各小區的交通量信息，求解出交通量的OD分布。

（3）再次，通過得到的小區交通量的OD分布，來繪制各熱點小區交通量的分布模型。

（4）然后，通過采集周邊各小區的居民出行數據，得到各小區居民出行的高峰時段與出行的熱點小區區域，并且將得到的熱點出行區域信息與上面步驟中得到的出租車出行的熱點小區區域進行匹配，得到交叉地帶。

（5）最后，通過收集出租車的GPS數據，篩選出有用的數據，由上述算法，便可以查找到車輛比較擁堵的路段與時段信息。將該信息與上面采集到的居民出行的高峰時段與熱點小區區域進行比較匹配，即可得到居民出行的擁堵路段與時段信息。

3.2 算法的創新之處

針對大規模軌跡數據的分析問題，現有的解決思路往往都是通過構造地圖來進行熱點掃描和偏好軌跡掃描。針對大規模軌跡數據，之前已經完成了離線預處理、頻繁軌跡圖模型、以及在線打車推薦部分算法。本算法的關鍵特色是從大規模GPS數據快速抽取熱點和熱點小區，然后繪制頻繁小區地圖，結合交通量分析計算熱點小區出行量，再根據各個小區的總體出行情況，獲取各個小區的交通出行量，從而查找各時段擁堵路段和擁堵路口，根據上述參數獲取擁堵預測模型。具體說來，本算法的創新之處有：

（1）由安裝在出租車上的GPS得到出租車每個時段的行駛信息，可以得到實時的運行信息。

（2）設計與實現了熱點和熱點小區的識別算法。

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

（4）由采集到的GPS數據動態構造各個時段擁堵路段和路口的計算模型。得到擁堵路段與時段模型。

（5）增加了居民的出行信息，通過采集到的小區居民出行高峰時段與路段信息與出租車擁堵路線進行匹配，可以得出居民出行的擁堵區域與時段信息，更加方便小區居民進行出行選擇，同時提高了該算法的應用性。

4 結論

當前是一個信息爆炸的年代，由于物聯網技術的發展，我們已經進入了大數據時代。

本文基于GPS終端的海量數據，計算隨時間變化的車流狀態，結合交通量分布OD分布概率模型來計算熱點小區的交通量，最終得到擁堵的預測模型，可有效地幫助城市管理者管理城市交通和小區居民選擇更加合適的出行方式與時間，在北京、上海等大中城市具有很高的應用前景。

參考文獻

[1]黃鳳忖.電信運營業發展的影響因素分析[D].首都經貿大學碩士學位論文，2005（03）.

[2]李勇平.遺傳神經網絡在電信業務收入預測中的應用研究[J].商場現代化，2008（11）.

[3]胡德敏，曹桓.四網協同無線網絡規劃策略與綜合評價研究[J].通信管理與技術，2012（12）.