匹配算法論文精選(九篇)

前言：一篇好文章的誕生，需要你不斷地搜集資料、整理思路，本站小編為你收集了豐富的匹配算法論文主題范文，僅供參考，歡迎閱讀并收藏。

第1篇：匹配算法論文范文

關(guān)鍵詞：入侵檢測；模式匹配；算法。

中圖分類號：TP309.08 文獻標識碼：A 文章編號：1007-9416（2013）06-0135-02

1 引言

在基于主機入侵檢測技術(shù)中，應(yīng)用比較多的是誤用檢測技術(shù)，其核心多采用字符串搜索算法模式匹配技術(shù)。通過對目前廣泛應(yīng)用的BM算法[1]和AC_ BM算法[2]的分析，提出基于AC_ BM算法的改進的多模式匹配算法NAC_ BM算法。該算法綜合了BM算法和AC_ BM算法的優(yōu)點，改進了BM算法跳躍步長，使得每次匹配獲得最大的步長，同時應(yīng)用AC算法有限狀態(tài)機模式匹配自動機構(gòu)造模式樹，匹配過程中移動模式樹，減少了規(guī)則匹配次數(shù)，為基于主機的入侵檢測模式匹配技術(shù)提供了一種優(yōu)化方法。

2 多模式字符串匹配算法

由于BM算法是一種單模式字符串匹配算法，它每次只能完成對一個模式的匹配工作，效率較低。雖然研究者對BM改進算法很多，但是這些算法都沒有改變BM算法的基本思想，因此不能解決效率問題。

為了提高效率，研究者提出了多模式匹配問題[3]，多模式匹配問題可以抽象描述為：設(shè)是一個模式集合，模式串Pi 中的字母來自于一個固定的字母表。多模式匹配問題是發(fā)現(xiàn)P中所有模式在文本T中的所有出現(xiàn)，。

3 AC_BM算法的改進—NAC_BM算法

4 仿真實驗分析

為了對各個算法的性能、效率做具體的評測，在同一臺計算機上分別對單模式匹配算法和多模式匹配算法進行了仿真測試。

在本測試中采用的搜索文件是來自麻省理工學院林肯實驗室提供的“1999DARPA入侵檢測測試數(shù)據(jù)集”[4]，長度為10000000Bytes的文本，而匹配的模式串是隨機抽取的。

由于對于單模式和多模式而言，各有其不同的特點，比如對于單模式匹配算法，它的時

間開銷與模式串的個數(shù)成正比，不能用它們解決多模式匹配的性能問題。而對于絕大多數(shù)多模式匹配算法都要在執(zhí)行搜索操作前，對模式串集合進行預處理，構(gòu)造某種數(shù)據(jù)結(jié)構(gòu)，以便為搜索過程提供支持；相對于單模式匹配算法對空間需求可以根據(jù)模式串的長度而估算出來。本實驗對匹配的模式個數(shù)對各種匹配算法性能的影響進行了仿真并給出對比分析。

圖5中“*”號表示該項未測試。對于模式串為1（即單模式串）時，AC算法、AC_BM算法和NAC_BM算法沒有必要測試它們對單模式匹配的性能。當模式個數(shù)大于1時，多模式匹配算法掃描對象文本一遍，而單模式匹配算法則要掃描對象文本多遍，即對每一個模式串掃描一遍對象文本。對于模式串個數(shù)為1000時，對單模式匹配算法是十分費時，且其耗費時間也可估算出來。

從圖5的結(jié)果來看，多模式匹配算法比單模式匹配算法的匹配速度快得多。三種多模式匹配算法仍然比其他單模式匹配算法速度快，而且AC_ BM算法和NAC_ BM算法比AC算法快，這兩個算法隨著模式串數(shù)目的增加，所耗費的時間僅有很小的增加，而不是成比例地增長。從表中可以看出，NAC_ BM算法比AC_BM算法在效率上有一定程度的提高。

5 結(jié)語

本文提出了一種改進的AC_BM算法：NAC_BM算法。該算法一是在BM算法的基礎(chǔ)上，改進了跳躍步長，使得每次匹配獲得最大的步長，二是應(yīng)用AC算法有限狀態(tài)機模式匹配自動機構(gòu)造模式樹，匹配過程中移動模式樹，減少了規(guī)則匹配次數(shù)。最后通過仿真實驗對比得知：NAC_BM算法效率優(yōu)于BM和AC_BM算法。

參考文獻

[1]A Pattern Matching Model for Misuse Intrusion Detection[A]. Sandeep Kumar， Eugene Spafford. In Proceedings of the 17th National Computer Security Conference[C]，1995， 11-21.

[2]楊武，方濱興，云曉春等.入侵檢測系統(tǒng)中高效模式匹配算法的研究.計算機工程，2004，30（13）.92-94.

第2篇：匹配算法論文范文

【關(guān)鍵詞】嵌入式；Linux；指紋識別；MiniGUI

0.引言

計算機的發(fā)展使指紋識別技術(shù)得到高速發(fā)展。目前指紋識別系統(tǒng)的發(fā)展以嵌入式系統(tǒng)為主，嵌入式指紋識別系統(tǒng)需要構(gòu)建可靠的嵌入式平臺，而且由于資源有限，對指紋識別算法要求較高。嵌入式指紋識別系統(tǒng)體積小、靈活性高、操作簡單，能夠很好的滿足實際需要。與其它生物識別技術(shù)相比，指紋具有較高的穩(wěn)定性、獨特性。指紋絕對可以通過每個指紋的細節(jié)特征進行區(qū)分。

1.指紋識別系統(tǒng)設(shè)計方案

本系統(tǒng)以S3C2410微處理器為核心，擴展了SDRAM、RAM芯片、FLASH芯片、RTL8019AS網(wǎng)卡芯片。S3C2410的通用IO口與液晶顯示屏、鍵盤相連，完成與用戶的交互操作，構(gòu)成了了本系統(tǒng)的硬件開發(fā)板。指紋采集模塊采用的是Veridicom公司的FPS200指紋傳感器模塊，并通過USB接口與開發(fā)板相連，實現(xiàn)數(shù)據(jù)指令的傳送，從而在開發(fā)板上完成指紋的獲取、預處理、提取特征值、特征值對比等功能。系統(tǒng)機構(gòu)框架見圖1。

操作系統(tǒng)啟動后對FPS200指紋模塊進行初始化，然后通過USB將采集到的指紋圖像傳送到ARM開發(fā)板上，應(yīng)用程序?qū)ψx入的指紋圖像進行處理并，最后進行指紋的匹配。

2.嵌入式linux開發(fā)平臺搭建與實現(xiàn)

2.1嵌入式系統(tǒng)概述

嵌入式操作系統(tǒng)（Embedded Operating System，簡稱EOS）負責嵌入式系統(tǒng)的全部資源的分配和調(diào)度工作，管理任務(wù)和并發(fā)操作，為開發(fā)人員提供統(tǒng)一的接口和硬件抽象。嵌入式操作系統(tǒng)除具備任務(wù)調(diào)度、中斷處理、文件操作等一般操作系統(tǒng)所具有的最基本功能外，還具有小巧、穩(wěn)定可靠、可移植性好、可擴展性好、具有強大的網(wǎng)絡(luò)功能及硬件支持等優(yōu)點。

2.2嵌入式Linux交叉編譯環(huán)境的搭建

交叉編譯需要一個高性能的宿主機，用來編譯應(yīng)用開發(fā)的源程序，然后可以生成目標平臺的可執(zhí)行程序。建立交叉編譯環(huán)境需要完成兩件事：宿主機的選擇和交叉編譯環(huán)境的建立。

2.2.1宿主機的選擇

嵌入式Linux開發(fā)的宿主機可以選擇安裝Linux操作系統(tǒng)的主機或是裝有Linux虛擬機的主機。本文選擇Fedora12作為宿主機的操作系統(tǒng)，Linux宿主機與目標機通過兩種方式進行連接：（1）網(wǎng)絡(luò)方式，通過TFTP和NFS服務(wù)；（2）串口方式minicom。

2.2.2交叉編譯環(huán)境的建立

交叉編譯就是在一個平臺上編譯生成可在另一個平臺上執(zhí)行的程序。平臺是指體系結(jié)構(gòu)（Architecture）和操作系統(tǒng)（Operating System）。為了Linux的應(yīng)用程序的開發(fā)，構(gòu)建一個多體系結(jié)構(gòu)的交叉編譯環(huán)境是非常必要的。

2.5設(shè)備驅(qū)動程序移植

在Linux系統(tǒng)下將設(shè)備分為三類：字符設(shè)備，塊設(shè)備和網(wǎng)絡(luò)設(shè)備。字符設(shè)備驅(qū)動程序與訪問普通文件一樣，需要至少實現(xiàn)open、close、read和write等方法，但是普通文件可以前后移動的訪問，字符設(shè)備通常只能順序訪問。塊設(shè)備與字符設(shè)備類似，塊設(shè)備上可以容納文件系統(tǒng)。但是塊設(shè)備和字符設(shè)備在內(nèi)核中數(shù)據(jù)的管理方式不同，內(nèi)核與驅(qū)動程序之間的軟件接口也不同。

Linux設(shè)備驅(qū)動的移植分為兩種，一種是內(nèi)核已經(jīng)支持的硬件，這些設(shè)備驅(qū)動移植比較簡單，只需在內(nèi)核配置時加入該設(shè)備，并添加相應(yīng)的初始化代碼即可。另一種是內(nèi)核不支持的硬件，首先要編寫相應(yīng)的驅(qū)動程序，然后通過交叉編譯生成驅(qū)動模塊文件，在應(yīng)用程序使用該驅(qū)動時加載驅(qū)動模塊。與U-Boot的移植一樣，Linux內(nèi)核也需要對K9F1208U0B NAND Flash、RTL8019AS網(wǎng)卡進行驅(qū)動的移植，而且內(nèi)核中還要加入LCD、觸摸屏和USB驅(qū)動的移植。

2.6根文件系統(tǒng)的設(shè)計

嵌入式Linux可以支持的多種文件系統(tǒng)，最常用的是Cramfs、YAFFS、JFFS等。

3.指紋識別算法研究

指紋識別算法是將采集到的指紋與指紋模板進行對比，判斷它們是否為同一枚手指。目前的指紋識別過程如圖3所示。系統(tǒng)從指紋傳感器獲得原始指紋圖像，首先要對采集的圖像進行預處理，將噪聲等無用信息去除，并且將有用信息加強。其次對處理后的圖像提取特征，獲得能夠區(qū)分指紋的唯一性特征。注冊指紋是把得到的指紋加入到指紋庫中。最后對指紋匹配，通常為了節(jié)省查找時間，會將指紋數(shù)據(jù)庫分類。

3.1指紋圖像預處理

指紋模塊采集到的指紋圖像是灰度圖像，這些灰度圖像中通常包含有噪聲等無用信息，而這些無用信息嚴重影響到指紋識別系統(tǒng)的準確性，為了提高系統(tǒng)的性能需要對指紋圖像進行預處理。指紋圖像預處理包括提取指紋圖像中指紋的有效區(qū)域，去除有效區(qū)域中的噪聲，加強指紋有效信息，為指紋特征提取和最終的識別提供好的條件。

3.1.1歸一化

歸一化的算法描述如下：假設(shè)指紋圖像大小為N×N，G（i，j）為像素點（i，j）的灰度值，N（i，j）為歸一化后像素點（i，j）的灰度值，對指紋圖像中的像素點依次應(yīng)用公式（1）實現(xiàn)歸一化。歸一化處理調(diào)整圖像灰度值的均值和方差到一個希望的范圍內(nèi)，保證采集到的指紋圖像的灰度值能夠在同一個級別上，為以后的處理算法提供一個好的條件。

3.1.2分割

指紋模塊采集到的指紋圖像包括指紋和背景兩部分，所以在預處理時需要將背景分割出去，只留下指紋部分。分割操作就是將指紋圖像的有效指紋區(qū)域保留下來進行后續(xù)的預處理操作。

3.1.3基于點方向的二值化

通常在對指紋圖像進行二值化之前要先完成濾波去噪，如卷積法、Gabor等，但是這些算法運算量較大，不適宜在嵌入式應(yīng)用系統(tǒng)中使用，所以本文中采用將濾波和二值化合并的算法，即基于點方向的二值化，能夠在較小的運算代價下去除一定的粘連和連接斷文等。二值化操作就是將255級灰度圖像轉(zhuǎn)化為只顯示黑和白兩種顏色的指紋圖像。

3.1.4去噪

雖然二值化能夠消除一些噪聲干擾，但是可能會引入新的噪聲，而且指紋紋線上可能會存在少數(shù)氣泡噪聲，指紋圖像邊緣上也會有部分毛刺存在。這些噪聲會對后面的指紋特征提取造成影響，所以在完成二值化操作后需要進行一步去噪的操作，刪除指紋圖像邊緣的毛刺和對指紋紋線上的氣泡進行填充。

3.1.5細化

經(jīng)過上面幾步的處理，基本得到了指紋紋線，但是紋線的寬度卻是不均勻的，原因可能是采集指紋圖像時手指壓力大小不同或是手指不干凈等噪聲影響，紋線不均勻會給指紋特征提取帶來比較大的誤差。對圖像進行細化的算法有很多，常用算法有：Hitditcb算法、E.S.Deutsch算法和OPTA算法。

3.2指紋特征提取

在進行指紋特征提取前會利用紋線跟蹤算法對指紋圖像中紋線進行修復，修復后的指紋圖像會提高指紋特征提取的效果和效率，但是如果指紋圖像噪聲干擾嚴重時，指紋修復就是一件非常困難的任務(wù)，對于不同的指紋圖像，指紋修復算法效果差別會很大，從而影響到指紋識別算法。還有一種處理方法是，對細化后的指紋圖像直接進行指紋特征提取，當然提取的特征中會包含大量的偽特征，但是這樣的提取過程簡單，簡化了算法的復雜度；然后再根據(jù)實際中真實特征點和偽特征點的特點，對提取的特征進行篩選，刪除偽特征，最終得到真實有用的特征點集。

3.3指紋特征匹配

指紋匹配是指紋識別系統(tǒng)非常關(guān)鍵的一步，目前已經(jīng)做了大量的研究，常見的匹配算法有基于點模式的指紋匹配算法，基于紋理結(jié)構(gòu)的匹配算法，基于紋線的匹配算法等。點模式匹配算法因其不高的時間和空間復雜度，非常適合在嵌入式環(huán)境下使用。本文就采用基于二維群集的點模式匹配算法進行指紋匹配。

4.結(jié)束語

本設(shè)計在S3C2410實驗箱平臺上實現(xiàn)基于Linux操作系統(tǒng)的指紋識別系統(tǒng)的設(shè)計與實現(xiàn)，采用先進的FPS200指紋采集模塊，設(shè)計了良好的圖形交互界面。本文對基于嵌入式linux的指紋識別系統(tǒng)進行了深入研究，硬件平臺采用基于ARM9架構(gòu)的S3C2410嵌入式平臺。對指紋識別算法進行了深入的研究，選擇和改進后的算法更適用于嵌入式平臺，算法主要分為三個部分：指紋圖像預處理、特征值提取和指紋匹配。 [科]

【參考文獻】

[1]顏永龍.嵌入式自動指紋識別系統(tǒng)若干問題的研究[D].重慶：重慶大學碩士學位論文，2008.

[2]陳梁.嵌入式指紋識別系統(tǒng)研究與實現(xiàn)[D].南京：南京航空航天大學碩士學位論文，2007.

第3篇：匹配算法論文范文

【關(guān)鍵詞】出租車；移動智能終端；匹配算法

1.系統(tǒng)設(shè)計

1.1 系統(tǒng)總體結(jié)構(gòu)

本系統(tǒng)有三個部分組成，分別為乘客客戶端，司機客戶端和服務(wù)器端，其中乘客客戶端和司機客戶端為移動智能終端的應(yīng)用。

乘客客戶端主要負責收集乘客地理位置及相關(guān)信息、向服務(wù)器發(fā)送數(shù)據(jù)以及與司機客戶端的連接。

司機客戶端主要負責收集出租車司機地理位置信息和空車信息、向服務(wù)器發(fā)送數(shù)據(jù)以及與乘客客戶端的連接。

服務(wù)器端主要負責記錄和分析兩個客戶端發(fā)送來的數(shù)據(jù)，通過相關(guān)算法計算出最佳配對組合，并將結(jié)果傳送到相應(yīng)客戶端。

1.2 客戶端

1.2.1 移動智能終端

移動智能終端是本系統(tǒng)的軟件部分，成熟的移動智能終端應(yīng)用開發(fā)技術(shù)為本系統(tǒng)的穩(wěn)定性提供了一定的保證。

乘客客戶端，通過移動智能終端的GPS模塊或點擊地圖上的地點來獲取乘客的地理位置信息。乘客點擊打車后，通過英特網(wǎng)向服務(wù)器發(fā)送信息，同時接受服務(wù)器反饋的信息，其中包括司機的地理位置（實時更新）、計算出來的等待時間和與司機的通訊等相關(guān)信息。

司機客戶端，通過移動智能終端的GPS模塊來獲取司機的實時地理位置信息，客戶端得到來自空車牌傳感器（具體見下節(jié)）的空車信息后，通過英特網(wǎng)向服務(wù)器發(fā)送信息，同時接受服務(wù)器的反饋信息，其中包括打車人的位置，與乘客的通訊等相關(guān)信息。同時，為了保證司機的行車安全，利用移動智能終端的語音交互，避免了司機在處理相關(guān)信息時，注視智能終端屏幕忽略了交通狀況而產(chǎn)生的不安全因素。乘客的信息采用語音播報的方式，告知司機，司機可以選擇性地通過屏幕查看更具體的信息。司機在操作上也可以通過語音告知智能終端，智能終端通過相關(guān)分析得到指令，進行操作。

1.2.2 空車牌傳感器

空車牌傳感器是系統(tǒng)的硬件部分，安裝在空車牌上，方便司機更好地利用本系統(tǒng)。在不改變出租車空車牌原有結(jié)構(gòu)的前提下在其外部增加一個小型藍牙無線傳感裝置，與出租車司機客戶端建立聯(lián)系，借助司機對空車牌的放倒和立起來這兩個必要的動作自動完成司機客戶端向服務(wù)器發(fā)出空車或已載客的信息。

1.3 服務(wù)器模塊

服務(wù)器是信息處理和交換的樞紐。它把從移動智能終端接收的地理信息及相關(guān)數(shù)據(jù)存儲在數(shù)據(jù)庫中，并通過相關(guān)算法計算出最佳匹配，將相關(guān)信息分別發(fā)送到匹配的乘客客戶端和司機客戶端進行處理和顯示。

2.服務(wù)流程

服務(wù)流程如圖2所示：

3.距離計算

在很多關(guān)于出租車管理調(diào)度系統(tǒng)中，采用直接利用經(jīng)緯度信息，進行數(shù)學計算，這樣固然方便、快捷，但是忽略了實際的交通狀況，尤其是在如北京、上海等立交橋林立、交通狀況復雜的大城市，僅利用經(jīng)緯度進行計算距離就會造成一定程度上的偏差，無法達到最優(yōu)的效果。除此之外，通過GIS軟件也可以取得兩點之間的距離。這樣的方式的優(yōu)點是獲取的距離準確，缺點是會消耗一定的網(wǎng)絡(luò)資源，需要一定的等待時間。

因此綜合以上兩點因素，和實際服務(wù)器關(guān)聯(lián)匹配算法的設(shè)計，本系統(tǒng)根據(jù)不同場合，利用兩種計算方法得出兩個距離。

3.1 經(jīng)緯度信息計算兩點之間距離

利用數(shù)學知識結(jié)合半正矢理論，可以計算出兩點之間的距離。公式如下：

R=地球半徑（平均半徑=6371公里）；

3.2 利用GIS軟件獲取距離

利用GIS軟件的相關(guān)接口，即可得到兩點之間的實際路程，將這個實際路程作為精確距離。

4.匹配算法

4.1 相關(guān)領(lǐng)域的研究背景

對于出租車調(diào)度問題相關(guān)算法的研究，大都是從數(shù)學理論出發(fā)，研究限制圖上局內(nèi)出租車的調(diào)度方案，而對于實際應(yīng)用中復雜的交通狀況和眾多不可預測因素，這類研究僅具有指示意義。因此本文參考了上述研究的成果，提出一種基于實際交通狀況的，在現(xiàn)有技術(shù)和數(shù)據(jù)下可行的、相對快速的算法。

4.2 算法設(shè)計

本算法首先假設(shè)打車的請求足夠多，即在較短的時間內(nèi)，可看作一個靜態(tài)的最佳匹配問題。

將所有已知空車的地理位置集合記為，將所有已知需要打車乘客的地理位置集合記為。將上文中利用經(jīng)緯度信息計算兩點之間的距離，即粗略距離，記為，利用GIS軟件接口計算的距離，即精確距離記為。將乘客的等待時間記為。將乘客對于空車的匹配權(quán)記為。

為需要通過實際檢驗而確定的參數(shù)。

（1）乘客在地點發(fā)出打車請求。

（2）以為中心，建立邊長為的正方形區(qū)域。

（3）若在集合中，存在多個，滿足，且未曾與關(guān)聯(lián)過，轉(zhuǎn)入第（4）步；若在集合中，存在唯一，滿足，且未曾與關(guān)聯(lián)過，關(guān)聯(lián)、，轉(zhuǎn)入第（7）步；若不滿足上面兩個條件，則增加的邊長，使得，若，則告知乘客目前沒有適合車輛，否則，返回第（2）步。

（4）對于每個，計算，比較各個，得到，則為距離最近的空車。關(guān)聯(lián)、。轉(zhuǎn)入第（5）步。。

（5）對于已得到的，若存在除以外的關(guān)聯(lián)，轉(zhuǎn)入第（6）步；若不存在除以外的關(guān)聯(lián)，等待時間后（為隨著精確距離的增大而增大的函數(shù)），若仍無除以外的關(guān)聯(lián)，則在集合、中，刪除、，匹配、，匹配成功，算法結(jié)束；若在時間內(nèi)建立了其他關(guān)聯(lián)，則轉(zhuǎn)入第（6）步。

（6）比較各關(guān)聯(lián)的的權(quán)重，得：

，則為最佳乘客，其他乘客在除去返回第（3）步。

（7）在集合、中，刪除、，匹配、，匹配成功，算法結(jié)束。

4.3 算法說明

在許多關(guān)于出租車智能公共服務(wù)系統(tǒng)的論文中，對于匹配算法部分，只提出通過經(jīng)緯度信息計算最短距離的出租車，從而得到匹配。而本文引入等待時間以及匹配權(quán)是為了形成一個總體的最佳匹配，從而節(jié)約了出租車的總體空跑時間，同時也使得乘客的等待時間不會過長。

當然，本文提出的算法，是在打車的請求足夠多的情況下，才能顯示其優(yōu)越性，而若打車請求較稀少，且請求地域較分散，則該算法則會降低整體的效率。所以，整個系統(tǒng)采用何種算法進行匹配，還需要得到實際的檢驗才能得到最后的結(jié)論。

同時，在本文提出的算法中的參數(shù)，也是需要通過實際檢驗，從而得出最優(yōu)的結(jié)果。

4.4 算法用例

下面的例子，簡單地說明了利用本算法進行匹配的效果。

①在北京郵電大學西門，有一位乘客發(fā)出了打車的請求，如圖3中A點所示，稱該乘客為乘客A，其他兩個出租車圖標表示該位置存在空車。（如圖3所示）

②以A點為中心建立邊長為a的正方形區(qū)域，此處a=1000M，發(fā)現(xiàn)沒有空車處于該正方形區(qū)域內(nèi)，因此擴大正方形區(qū)域的邊長。（如圖4所示）

③擴大正方形邊長得到新的邊長a，此處a=2000m，發(fā)現(xiàn)存在兩輛空車都在正方形區(qū)域內(nèi)。調(diào)用GIS軟件的相關(guān)接口，得右側(cè)出租車距離A的路程短，關(guān)聯(lián)右側(cè)出租車和A。（如圖5所示）

④在A的乘客等待t時間中，右側(cè)出租車出現(xiàn)另一關(guān)聯(lián)乘客B，經(jīng)比較得乘客A、B的權(quán)重得，B的權(quán)重較大，則取消A和右側(cè)出租車的關(guān)聯(lián)，乘客B進入乘客等待時間。（如圖6所示）

⑤乘客A重新回到第③步，此時只存在右側(cè)一個合適的出租車，匹配A與右側(cè)出租車。算法結(jié)束。

5.結(jié)束語

本系統(tǒng)在現(xiàn)有的技術(shù)框架下，可以很好地解決乘客不易打車，出租車空跑時間長的問題，更好地分配出租車資源，提高整個出租車服務(wù)系統(tǒng)的效率，也一定程度地緩解了城市交通的壓力。用移動智能終端作為整個系統(tǒng)的基礎(chǔ)，符合當下的流行趨勢，即集成化。同時，利用空車牌傳感器感知空車牌倒立，在此處還可以添加人文關(guān)懷類的功能如，測量車內(nèi)濕度、車內(nèi)溫度等，并通過移動智能終端提醒司機。該系統(tǒng)不僅為乘客出行提供方便，減少了出租車空跑的時間，也為城市交通的順暢出了一份力量。

參考文獻

[1]Karimi Hassan A，Tom Lockhart J.GPS-based tracking systems for taxi cab fleet operations[C].IEEE.VehicleNavigation&InformationSystemConference，Ottawa，1993：679-682.

[2]徐寅峰，王刊良，丁建華.限制圖上的局內(nèi)出租車調(diào)度與競爭算法[J].系統(tǒng)工程學報，1999，14（4）：361-365.

第4篇：匹配算法論文范文

【關(guān)鍵詞】車載導航系統(tǒng)；全球定位系統(tǒng)；地圖匹配

Introduction to map matching technology in the application of vehicle navigation system

Chen Chong

（Nonferrous geological survey in liaoning province101 teamLiaoningFushun113015）

【Abstract】Briefly expounds the composition of vehicle navigation system， the basic principle of map matching technology，as a software error correction technolog has the characteristics of the real-time correction，with the global positioning system （GPS）、geographic information system and computer for the mobile vehicle to provide comprehensive services，map matching technology as an auxiliary means of improving the precision of vehicle navigation system is particularly important and meaningful。

【Key words】Vehicle navigation system；Global positioning system （GPS）；Map matching

1. 引言

（1）隨著國民經(jīng)濟的快速發(fā)展和人民生活水平的顯著提升，汽車幾乎成為人們在日常工作生活當中不可缺少的交通工具。由于機動車數(shù)量的迅猛增長，使得交通流量與現(xiàn)有道路基礎(chǔ)設(shè)施之間的矛盾日益突出，擁堵現(xiàn)象日益嚴重。如何有效地進行交通管理和疏導，減少擁堵與事故的發(fā)生，合理控制交通流量分布，提高道路利用率己成為我國主要城市面臨的嚴峻問題，必須給予充分的重視。因此，車載導航定位系統(tǒng)越來越受到人們的關(guān)注。

（2）在車載導航系統(tǒng)的應(yīng)用方面，美、歐、日等國家走在前列，其導航技術(shù)的現(xiàn)狀代表了本領(lǐng)域研究和應(yīng)用的方向。相對而言，我國對車載導航系統(tǒng)的研究處于剛剛起步的階段，但是，采用進行車輛導航的定位系統(tǒng)在最近幾年己經(jīng)有了很大的發(fā)展。目前，在我國政府及有關(guān)部門的重視下，有些企業(yè)和公司己經(jīng)開發(fā)、研制出了一些車輛導航和監(jiān)控系統(tǒng)，并投入了使用。但是，所有這些系統(tǒng)都不是很完善，有待進一步的研究和改進。隨著汽車持有量的不斷增加，各種技術(shù)的不斷成熟，以及用戶更高的服務(wù)要求，車載定位導航系統(tǒng)有了較大發(fā)展，應(yīng)用前景廣闊。

2. 車載導航系統(tǒng)的作用

車載導航系統(tǒng)是將全球定位系統(tǒng)、地理信息系統(tǒng)和計算機技術(shù)結(jié)合在一起的智能交通系統(tǒng)。車輛通過車載導航設(shè)備接收GPS數(shù)據(jù)，在電子地圖上顯示汽車行駛的位置、目的地的方向和距離等信息，并在公路網(wǎng)范圍內(nèi)定向選擇最佳行駛路線，為移動的車輛提供全面的服務(wù)，從而達到減少道路阻塞，提高交通安全的目的。

2.1車載導航系統(tǒng)的組成。

（1）現(xiàn)在的車載導航系統(tǒng)按照功能劃分為多個模塊，即：電子地圖數(shù)據(jù)庫模塊、地理信息引擎模塊、定位模塊、地圖匹配模塊、路徑規(guī)劃模塊、路徑引導模塊、人機交互界面模塊和無線通信模塊。如圖1所示。

（2）在上述模塊中，定位系統(tǒng)的準確性是非常關(guān)鍵的，只有準確地知道車輛位置，才能在地圖上正確地顯示車輛位置，并向司機提供準確的行駛指令。因此，如何向用戶提供實時、準確的車輛位置就成了車載導航系統(tǒng)的重點和難點。然而，無論是哪種定位技術(shù)都有其無法克服的局限性，得到的實時定位數(shù)據(jù)依然存在一定的誤差，往往使得車輛的定位信息與電子地圖中的道路信息不一致，車輛位置偏離了當前所行駛的道路，這些都難以滿足用戶對車輛導航系統(tǒng)的要求。

2.2地圖匹配技術(shù)的意義。

為了解決這個問題，可以采取提高GPS定位精度以及電子地圖精度的方法，但是這種方法成本較高，也不可能完全消除定位點與電子地圖之間的這種顯示誤差。地圖匹配這一基于軟件的定位修正方法，在接收到車輛當前時刻有關(guān)的信息后，從電子地圖數(shù)據(jù)庫中獲取相關(guān)信息，然后通過匹配算法得到車輛位置的偏差信息，并對其進行實時修正，從而準確顯示車輛的位置。它一方面減少了系統(tǒng)在硬件上的投入，節(jié)省資源和成本，另一方面又避免了其它定位技術(shù)無法克服的局限性。

2.3地圖匹配技術(shù)的原理。

（1）地圖匹配技術(shù)是一種利用數(shù)字地圖信息融合傳感器定位數(shù)據(jù)以產(chǎn)生最佳位置估計的技術(shù)。簡單地說，就是把車輛的行駛軌跡和電子地圖數(shù)據(jù)庫中的道路網(wǎng)進行比較，在地圖上找出與行使軌跡最相近的路線，并將實際定位數(shù)據(jù)映射到直觀的數(shù)字地圖上。

（2）電子地圖以地圖數(shù)據(jù)庫為基礎(chǔ)，通過一定得軟件和硬件在電子屏幕上顯示可視地圖。有了電子地圖，車輛的位置可以顯示在電子地圖上，同時電子地圖數(shù)據(jù)庫中的精確地理信息還可以對GPS定位結(jié)果進行必要的修正，輔助GPS進行準確定位，使車輛的位置能夠準確地顯示在電子地圖上。

（3）作為一種軟件糾錯技術(shù)，地圖匹配最終輸出的結(jié)果包括車輛的當前位置、運行方向、行駛速度和經(jīng)過的路段等信息。

恰恰避免了其它定位技術(shù)無法克服的局限性。它將車載GPS接收機測量到的當前車輛的有關(guān)位置信息，與電子地圖數(shù)據(jù)庫中獲取的相關(guān)信息聯(lián)系起來，然后通過匹配算法得到車輛的位置偏差信息，并利用結(jié)果對GPS定位數(shù)據(jù)進行實時修正，從而準確顯示車輛在道路網(wǎng)中的位置。在某中程度上，地圖匹配算法的效果直接關(guān)系到車輛定位的精度，地圖匹配技術(shù)是決定導航產(chǎn)品最終性能的關(guān)鍵技術(shù)。

（4）地圖匹配技術(shù)協(xié)調(diào)定位信息和電子地圖的道路信息之間的顯示誤差，把定位點依照某種規(guī)則強制與實際道路進行配準，從而保證車輛總在行駛的道路上。因此，地圖匹配在車輛導航系統(tǒng)中起著重要的作用，使得定位系統(tǒng)更加可靠和準確。

3. 結(jié)語

地圖匹配技術(shù)借助電子地圖數(shù)據(jù)庫中的高精度道路信息作為分類模板，進行模式識別，根據(jù)結(jié)果來修正GPS接收數(shù)據(jù)的定位數(shù)據(jù)。通過進行地圖匹配，能夠較為連續(xù)和準確地得到車輛的位置信息，大大改善了車輛導航系統(tǒng)的定位精度。這樣不僅減少了導航系統(tǒng)在硬件上的投入，而且提高了車輛匹配到路段上的正確率。同時，提高地圖匹配定位精度也可以提高交通設(shè)施和道路的利用率，減少阻塞，增加交通的機動性，降低交通工具對環(huán)境的污染，改善道路安全，減少交通事故的發(fā)生。因此，地圖匹配作為提高車輛導航系統(tǒng)精度的輔助手段就顯得更為重要和有意義了。

參考文獻

[1]張其善、吳今培、楊東凱著。智能車輛定位導航系統(tǒng)及應(yīng)用。[M]科學出版社，2002.

第5篇：匹配算法論文范文

關(guān)鍵詞：語音識別 端點檢測 特征參數(shù) DTW算法

中圖分類號：TN912 文獻標識碼：A 文章編號：1007-9416(2011)12-0184-02

1、語音識別系統(tǒng)概述

語音信號是一種典型的非平穩(wěn)信號，并且在錄音過程中不免受到電噪音，呼吸產(chǎn)生的氣流噪音以及錄音環(huán)境下的突發(fā)噪音的影響，所以語音信號要經(jīng)過預濾波、采樣量化、分幀、加窗、預加重、端點檢測等預處理過程后才可以進行下一步的特征征參數(shù)提取等工作。在接下來的語音訓練階段，我們將那些信號狀態(tài)良好，攜帶噪聲小且特征參數(shù)穩(wěn)定的語音信號作為指定詞條的模板，進而為每個詞條創(chuàng)建一個模板并保存為模板庫。在識別階段，語音信號經(jīng)過相同的通道生成測試模板，用相同的方法計算測試模板的特征參數(shù)后，將其與模板庫模板的特征參數(shù)進行匹配，配分數(shù)最高的參考模板作為識別結(jié)果。

2、語音信號的錄入

語音信號的采集方法有很多，鑒于該系統(tǒng)是在MATLAB上實現(xiàn)，且MATLAB本身提供了一定的音頻處理函數(shù)，因此我們完全可以采用在MATLAB中先完成錄音函數(shù)的編寫，然后再結(jié)合windows自帶的錄音設(shè)備進行錄音。錄音得到的wav文件即是經(jīng)過預濾波采樣和量化的語音。利用soundview讀所錄入的文件時，會彈出一個GUI界面，并可以通過輸出設(shè)備對所錄語音進行回訪，該GUI界面如圖1所示。單擊Play Again按鈕可可回放，單擊Done按鈕可關(guān)閉界面。

3、語音信號的預加重

我們知道，對語音識別更有用的是語音的高頻部分，而對于語音信號的頻譜，通常是頻率越高幅值越低。因此我們必須對語音的高頻進行加重處理。處理方法是將語音信號通過一個一階高通濾波器，即預加重濾波器，它不僅能濾除低頻提升高頻，還能很好的抑制50Hz到60Hz的工頻干擾。尤其在短點檢測之前進行預加重還可起到消除直流漂移、抑制隨機噪聲和提升清音部分能量的效果。預加重在Matlab中可由語句x=filter([1-0.9375],1,x)實現(xiàn)。

4、語音信號的分幀和加窗

經(jīng)過數(shù)字化的語音信號實際上是一個時變信號，為了能用傳統(tǒng)的方法對語音信號進行分析，應(yīng)假設(shè)語音信號在10ms-30ms內(nèi)是短時平穩(wěn)的。為了得到短時的語音信號，要對語音信號進行加窗操作。窗函數(shù)平滑地在語音信號上滑動，將語音信號進行分幀，幀與幀的交疊為幀移，一般為窗長的一半。

語音信號的分幀采用enframe函數(shù)，其語法為f=enframe(x,len,inc);其中X為輸入的語音信號，len為制定的幀長，inc為指定幀移。函數(shù)將返回一個n×len的一個矩陣，每行都是一幀數(shù)據(jù)。在本系統(tǒng)中幀長取240，幀移取80。在Matlab中要實現(xiàn)加窗即將分幀后的語音信號乘上窗函數(shù)，本文加漢明窗，即為x=x.*hamming(N)。

5、端點檢測

在語音識別系統(tǒng)中，訓練階段和建模階段都比較重要的環(huán)節(jié)都是要先通過端點檢測找到語音的起點和終點，這樣，我們就可以只對有效語音進行處理，這對于識別的準確率和識別效率至關(guān)重要。本論文在短點檢測環(huán)節(jié)采用雙門限端點檢測法，即采用短時能量檢測和短時過零率檢測雙重指標約束。結(jié)合實際，我們將整個語音端點檢測分為四個段落，即：無聲段、等待段、語音段、結(jié)束段，再為短時能量和短時過零率各設(shè)置一個高門限和一個低門限：EHigh、ELow和ZHigh、ZLow。結(jié)合MATLAB中所編程序，可以較準確的確定語音的各個部分。圖2所示為語音“1”的處理結(jié)果。

6、特征參數(shù)的提取

經(jīng)過預處理的語音數(shù)據(jù)就可以進行特征參數(shù)提取，特征參數(shù)的好壞將直接影響系統(tǒng)的性能和效率。本文將梅爾倒譜系數(shù)（MFCC）和一階MFCC系數(shù)的差分結(jié)合起來，將其合并為一個矢量作為一幀語音信號的參數(shù)，這樣，不僅描述了語音的靜態(tài)特性，由于加入了差分倒譜參數(shù)，語音的動態(tài)特性得到了更好的體現(xiàn)。梅爾倒譜參數(shù)的計算流程為：先將預處理過的語音信號進行快速傅立葉變換，將時域信號變換成為信號的功率譜。 再用一組Mel頻標上線性分布的三角窗濾波器（本文采用24個三角窗濾波器）對信號的功率譜濾波，每一個三角窗濾波器覆蓋的范圍都近似于人耳的一個臨界帶寬，以此來模擬人耳的掩蔽效應(yīng)。然后對三角窗濾波器組的輸出求取對數(shù)，可以得到近似于同態(tài)變換的結(jié)果。最后去除各維信號之間的相關(guān)性，將信號映射到低維空間。 梅爾倒譜系數(shù)的計算差分參數(shù)的計算采用下面的公式：

7、模式匹配

本語音識別系統(tǒng)的模式匹配算法采用動態(tài)時間彎折（Dynamic Time Warping，DTW）算法，該算法基于動態(tài)規(guī)劃的思想，解決了發(fā)音長短不一的模板匹配問題。DTW是語音識別中出現(xiàn)較早，較為經(jīng)典的一種算法。與HMM算法相比而言，DTW算法具有計算量小，識別效率高的特點。模式匹配的過程其實就是根據(jù)一定的規(guī)則,計算輸入矢量特征與庫存模式之間的相似度,判斷出輸入語音的語意信息。本文中,失真測度采用下式所示的歐式距離:

其中,l=1,2,…M；i=1,2,…I;k=1,2,…K.是待測矢量之間的距離，是第i個碼本的第l個碼字矢量的第k個分量。I為說話者的數(shù)量，M為碼本的大小，K為參數(shù)矢量的總維數(shù)。由上式得出該語音相對于該命令詞的最短距離,然后取最短距離最小的命令詞作為該段語音的首先識別結(jié)果。結(jié)合MATLAB程序，得到數(shù)字1-10的匹配距離矩陣：

圖3即為針對數(shù)字1-10的待測模板和模板庫模板匹配距離的現(xiàn)實，由該距離矩陣，我們可以很清楚的看到，左上角到右下角的對角線上的距離匹配值在該值所在的行和列都是最小的。即距離最短的命令詞為識別結(jié)果。

8、結(jié)語

該論文闡述了基于DTW的語音識別系統(tǒng)在MATLAB上實現(xiàn)的基本過程,在實驗室錄音情況下，該識別系統(tǒng)的識別率可以達到百分之九十以上，效果良好。

參考文獻

[1]趙力.語音信號處理[M].北京:機械工業(yè)出版社,2003.

[2]何強,何英. MATLAB擴展編程[M].清華大學出版社,2002-06.

[3]李景川,董慧穎.一種改進的基于短時能量的端點檢測算法[J].沈陽理工大學學報,2008.

[4]沈宏余,李英.語音端點檢測方法的研究[J].科學技術(shù)與工程,2008,(08).

[5]吳曉平,崔光照,路康.基于DTW算法的語音識別系統(tǒng)實現(xiàn)[J].電子工程師,2004,(07).

第6篇：匹配算法論文范文

關(guān)鍵詞： IP地址搜索；高效路由；多處理器結(jié)構(gòu)

中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2007)03-10709-03

1 引言

網(wǎng)絡(luò)的普遍使用，使得網(wǎng)絡(luò)流量劇增。同時多媒體網(wǎng)絡(luò)應(yīng)用程序和設(shè)備的使用又對網(wǎng)絡(luò)流速提出了更高的要求。高速鏈路和高速路由器則是因特網(wǎng)速度提高的關(guān)鍵。

作為網(wǎng)絡(luò)的靈魂，路由器將數(shù)據(jù)包從輸入接口傳遞到輸出接口，數(shù)據(jù)包的目的地址稱為IP地址。一個選路表包含許多（N，R）序偶，其中N是目的網(wǎng)絡(luò)的IP地址，R是到網(wǎng)絡(luò)N的路徑上的“下一跳”路由器的IP地址[1]。路由查找是對每個到達的IP報文根據(jù)其目的IP地址確定其應(yīng)轉(zhuǎn)發(fā)的輸出端口號和下一跳地址。變長地址前綴的采用提高了IP地址的利用率，但在路由查找時就有可能找到多個匹配的表項，因此需要進行最長前綴匹配。

路由器一收到數(shù)據(jù)包，就將選路表中的下一跳地址與數(shù)據(jù)包中的目標地址相比較，取前綴匹配最長的那個，然后將數(shù)據(jù)包轉(zhuǎn)發(fā)給前綴最長匹配輸出端它的輸出端口。在數(shù)據(jù)包轉(zhuǎn)發(fā)過程中，IPV6地址的增加使得最長匹配前綴問題日益成為轉(zhuǎn)發(fā)的瓶頸?？梢韵胂?，當選路表包含幾百萬IP地址時，不可能存儲所有已存在的IP地址，因此IP地址搜索問題是一個復雜的選路表查詢問題。提高數(shù)據(jù)包轉(zhuǎn)發(fā)速度的方法之一是同時對目標地址提供多重搜索，這可通過使用多個處理器并行搜索得到。本文描述提出一個新的對128位IPV6地址使用SROW（Simultaneous Read and Only Write）的多處理器搜索技術(shù)。每一個處理器存儲n/N個前綴，提出了一并使用（N+1-ary）搜索技術(shù)的高效算法。

2 已存在的一些IP查找算法

搜索操作需要找到一個逐字匹配的前綴。使用基于hash表或二叉樹搜索的傳統(tǒng)算法只可進行精確匹配的搜索。在無類域間路由（Classless Inter-Domain Routing，CIDR）[2]技術(shù)中，地址前綴長度可為不超過IPV4地址寬度的任意長度。變長地址前綴的使用使得IP地址的層次性分配成為可能。

2.1基于Trie的層次方法

這種方法最先在BSD內(nèi)核中實現(xiàn)，最壞的情況下，該算法需要O（W）次查找，其中W為地址長度，所以，對于IPV4來說完成一次查詢最多訪問存儲器32次，對于IPV6最多需要是128次查詢存儲訪問。效率不夠高。

2.2分布式存儲結(jié)構(gòu)

在選路表中，這種方式依賴前綴中的特定位以平均幾組的形式進行存儲[2]。例如，選路表中的位63，64，65，66（稱ID位）用來將前綴分成16種類。不同類以不同的存儲模式存儲，因此，可最多讓16類IPV6地址同時進行查詢。通過4位ID組將IP地址進行分類，對每類IP地址進行的最長匹配前綴的搜索是從包含同類地址的存儲模式中開始的。

3 對（N+1-ary）算法的改進

3.1多處理器結(jié)構(gòu)

本文提出一個基于多處理器的路由器結(jié)構(gòu)。將所有前綴集劃分成平均長度的子序列，每個子序列對應(yīng)一個處理器。這樣，將目的IP地址廣播至N個處理器，同一子序列中的每一個處理器同時搜索前綴。由于它是并行進行的，所以它減少了查詢時間。

圖1 基于多處理器的路由器的結(jié)構(gòu)

3.2前綴的排序

在下列算法中，以并行的方式對處理器前綴進行排序。設(shè)S=，表示未排序的輸入序列，其中Si為元素的位置，由比它小的數(shù)決定ri。當算法中止時，ri將包括輸入序列中比Si小的元素的數(shù)目，把Si放在第（ri+1）的位置上，這樣就生成了一個以升序排序的序列。

排序算法的偽代碼為：

for i=1 to n do //可同時進行

for j=1 to n do

if (Sij )

then ri=ri+1

end if

end for

把Si放在第（ri+1）的位置上

end for

該算法的時間復雜度為O（n）。

3.3前綴的發(fā)送

已排好序的前綴以n/N的大小分成子序列，每個子序列發(fā)送給一個處理器。這樣，每個處理器在子序列中比較其輸入地址。（Pi代表第i個處理器）

發(fā)送前綴的偽代碼為：

for 每一個處理器 do

send ( 子序列i, Pi )

end for

for 每一個處理器 do

send (目的地址, Pi)

end for

例如，假定有30（n=30）個前綴和6(N=6)個處理器，這30個前綴被分列成長度為5(n/N)的子序列，即每個處理器包含一個有5個前綴的子序列。

發(fā)送數(shù)據(jù)包的IP地址給所有的處理器，使用有共享存儲器的PRAM模式， 那么，所有的處理器就會在一固定的時間內(nèi)同時讀取目標地址。因此地址可被N個處理器同時讀取而僅寫一次（SROW）。廣播的過程僅需O（1）的時間。

3.4前綴的查詢

借助于（N+1-ary）搜索的思想，每一步序列以相同的長度分成（N+1）個子序列。N個處理器在序列的兩端同時搜索，Si表示在子序列兩端的元素。處理器Pi將x與Si相比（x為要查詢的IP地址）。

(1)如果Si>x，那么，若x在序列中，它必須在Si的前面，因此Si和所有它右邊的元素不予考慮。

(2)如果Si

每一個子序列的長度以（N+1）的因素在減少，所以需要logN+1(n+1)個子序列。因此，最壞情況下算法的復雜度為O（logN+1(n+1)）。當N=1時，算法運行的時間是固定的。

由上可得到匹配算法的偽代碼：

4 最優(yōu)使用前綴擴展

控制前綴擴展將前綴集轉(zhuǎn)換成前綴長度較少的相等的前綴集。在[3]中0或1填充前綴以增加前綴的長度，如果要增加的字符串已經(jīng)在數(shù)據(jù)庫中，就不增加，字符串仍在原來的位置。例如，如果擴前綴到足夠長，那整個前綴搜索問題可轉(zhuǎn)換為一般的隊列搜索。對臨界點的搜索將更容易，但這種解決方法是不理想的，對IPV6，隊列將需要2128的空間。要使所需的總的存儲空間最小，且減少查詢時間，就需限制IP地址前綴長度，而這可用控制前綴擴展來將前綴集由任意長度減至預定的長度。

5多處理器結(jié)構(gòu)的實現(xiàn)

假設(shè)有N個處理器，每個處理器的主頻為700MHz。每一處理器存在一個通用的L1緩存，所有的處理器都同時共享它，客戶端同時收到服務(wù)器創(chuàng)建的共用的套接字，套接字將所有的處理器都連接起來；客戶機使用它的端口號和主機名綁定到服務(wù)器上，服務(wù)器將收到的數(shù)據(jù)包轉(zhuǎn)發(fā)給客戶機，服務(wù)器和客戶機使用TCP套接字相互通信。隨著處理器數(shù)目的增加，前綴比較的時間明顯減少。

6 性能分析

6.1隊列系統(tǒng)分析

第7篇：匹配算法論文范文

關(guān)鍵詞：合成孔徑雷達；圖像匹配；智能導航

中圖分類號：TP391.41 文獻標識碼：A 文章編號：1007-9599 （2012） 20-0000-02

合成孔徑雷達（SAR）與慣導（INS）結(jié)合的圖像匹配智能導航系統(tǒng)在航空科學和軍事中都有廣泛的應(yīng)用，特別是在精確打擊武器的末段制導方面，是其必須解決的一個基本問題，其匹配性能直接決定了攻擊的準確性。目前，由于圖像邊緣特征的相對穩(wěn)定性，基于邊緣特征的匹配方法成為研究熱點，但大多數(shù)匹配方法不能處理圖像的仿射變形，沒有考慮特征之間的空間結(jié)構(gòu)信息，難以滿足構(gòu)像方程解算對多個對應(yīng)點在空間上要盡量均勻分布的要求。本項目旨在利用圖像邊緣的B樣條模型，在仿射形狀空間中進行匹配，并且將結(jié)構(gòu)信息融入其中，提高匹配性能。

1 SAR圖像無抽樣小波域貝葉斯軟閾值噪聲抑制

合成孔徑雷達的成像原理決定了圖像中必然存在相干斑噪聲，為了正確地對圖像進行邊緣提取，必須在有效去除噪聲的同時，盡可能保留邊緣信息。SAR圖像上的斑點為乘性形式，當服從Gamma分布的乘性噪聲模型取對數(shù)后為加性噪聲，噪聲分布近似為高斯分布。我們首先進行SAR圖像的對數(shù)變換，并對對數(shù)SAR圖像的均值進行歸一化，使其滿足均值為零的高斯分布。由于圖像的斑點噪聲主要集中在圖像的高頻部分，我們考慮在多尺度小波域抑制噪聲。對于加性噪聲模型，小波變換后的輸入圖像的小波系數(shù)為真實圖像的小波系數(shù)與噪聲的小波系數(shù)之和。在Mallat算法中，每次濾波后都要經(jīng)過亞采樣，對應(yīng)于圖像邊緣或不連續(xù)點的小波系數(shù)可能被抽樣掉。為克服這種缺陷，我們采用atrous算法的無抽樣小波變換，這種算法在每一次濾波后不進行抽樣，是通過有限濾波器的內(nèi)插近似，從而達到無抽樣離散小波變換，其圖像大小與原始圖像尺寸相同。根據(jù)小波系數(shù)的廣義高斯分布模型，利用貝葉斯框架得到自適應(yīng)閾值。去噪過程如下：估計SAR圖像的二次中心矩；對含噪的實時SAR圖像作非抽樣小波變換，分解成幾層，得到相應(yīng)的小波系數(shù)；通過二次中心矩求出各層小波系數(shù)的局部噪聲方差；然后調(diào)整各層窗口大小，估計小波系數(shù)的噪聲方差；在子帶非抽樣小波系數(shù)上估計含噪信號的方差；進一步求解出子帶上的反射率方差，利用貝葉斯軟閾值，估計反射率相應(yīng)子帶的小波系數(shù)；對濾波后反射率的小波系數(shù)估計值進行非抽樣反變換重構(gòu)圖像。

2 邊緣特征在仿射變形空間的B樣條建模

在SAR圖像去噪后，我們用形態(tài)學處理獲取目標成像區(qū)域，并根據(jù)區(qū)域內(nèi)部點與外部點的區(qū)別提取目標邊緣輪廓。目標成像區(qū)域體現(xiàn)了目標散射中心的分布，而目標自身結(jié)構(gòu)決定其散射中心分布可能并不集中，導致目標邊緣輪廓可能由多個部分組成。我們用邊緣跟蹤獲得邊緣序列點，并以此為控制點建模該邊緣的二次B樣條曲線，所有邊緣序列點坐標構(gòu)成一個控制點向量

其中， ， ， 是所有控制點 坐標組成的列向量， 是所有控制點 坐標組成的列向量。

為提高基于邊緣特征匹配方法的性能，要考慮目標可能存在的多個邊緣輪廓及相互的局部空間結(jié)構(gòu)，分別用二次B樣條曲線擬合每一邊緣輪廓，這樣目標每個邊緣都對應(yīng)一個控制點向量。在 時刻，目標成像區(qū)域的某個邊緣可以用B樣條曲線表達：

其中， 為B樣條基函數(shù)。

為了處理SAR圖像可能存在仿射變形情況，我們將控制點向量 線性映射為形狀空間中的形狀向量 ：

式中， 是 維的形狀矩陣， 是參考圖像邊緣對應(yīng)的控制點向量。形狀空間的維數(shù) 一般要遠小于控制點向量空間的維數(shù) ，這樣，形狀空間可以使邊緣輪廓匹配的性能更穩(wěn)定，而且使匹配算法的計算量減小。我們采用的形狀空間是平面仿射形狀空間，這時，

其中， 和 都是 向量， 和 分別是 的坐標分量，例如：可用 代表參考圖像邊緣旋轉(zhuǎn)了 角度，它描述平面或可以合理地近似成平面的目標進行三維運動在圖像平面內(nèi)的投影形成的變換群，該平面仿射變換可以理解為作用于參考圖像邊緣的一類線性變換。形狀矩陣 的前兩列表示目標的水平位移和垂直位移，后四列表示運動目標的旋轉(zhuǎn)，尺度變化和剪切變形。通過B樣條建模，既可以考慮邊緣上每個控制點與參考圖像邊緣控制點的局部對應(yīng)關(guān)系，又可以考慮邊緣之間的結(jié)構(gòu)信息。

3 基于粒子濾波的仿射變形邊緣匹配

粒子濾波又稱蒙特卡羅仿真，是一種以貝葉斯推理為核心的濾波技術(shù)。它用一組加權(quán)的隨機采樣來近似表示所求的后驗概率密度函數(shù)?；诹Ｗ訛V波的邊緣匹配的思路是將匹配問題轉(zhuǎn)換為貝葉斯估計問題，已知目標邊緣狀態(tài)的先驗概率，在獲得新的SAR圖像邊緣觀測數(shù)據(jù)后不斷求解目標邊緣狀態(tài)的最大后驗概率的過程。匹配過程如下：

3.1 時刻，在仿射形狀空間中產(chǎn)生初始粒子集，其中每個粒子狀態(tài)為形狀向量，用六個仿射變形參數(shù)表達，六個參數(shù)的初始化服從均勻分布。

3.2 得到 時刻SAR圖像中的邊緣。

3.3 計算粒子集中各個粒子的權(quán)值：

（1）用公式 計算每個粒子狀態(tài)所對應(yīng)的控制向量，進而得到每個控制點。（2）通過邊緣跟蹤獲得序列點作為曲線參數(shù)向量，在每個控制點計算B樣條基函數(shù)，并獲得每個控制點的坐標。（3）通過在每個控制點的坐標計算B樣條基函數(shù)的一階偏導數(shù)獲得該控制點處曲線的切向量，進而得到該點處曲線的法向量。（4）歸一化法向量。（5）沿著每個點的曲線法向搜索得到觀測。（6）根據(jù)觀測似然公式計算每個粒子的權(quán)值。

3.4 歸一化粒子集中所有粒子的權(quán)值，并計算每個粒子的累積權(quán)值。

3.5 把權(quán)值最大的粒子狀態(tài)輸出，得到六個仿射變形參數(shù)。

3.6 在 時刻，根據(jù)累積權(quán)值從初始粒子集中重采樣獲得新的粒子集。

3.7 從 以后，執(zhí)行匹配濾波過程，用系統(tǒng)狀態(tài)方程對每個粒子狀態(tài)進行預測，通過觀測似然計算每個粒子的權(quán)值。

4 結(jié)束語

實驗結(jié)果表明，本項目利用圖像邊緣的B樣條模型，在仿射形狀空間中進行匹配，并且將結(jié)構(gòu)信息融入其中，有效地提高了匹配性能。另外，在匹配過程中，同時提供兩幅圖像之間相對平移與旋轉(zhuǎn)的相似變換參數(shù)，這勢必為后續(xù)的處理提供便利。該項目成果有望直接應(yīng)用到SAR與INS結(jié)合的圖像匹配智能導航系統(tǒng)中，也可以應(yīng)用到SAR圖像解譯中，應(yīng)用前景十分明朗。

參考文獻：

[1]王其聰.復雜觀測條件下的基于粒子濾波的視覺跟蹤[D].浙江大學博士論文，2007，10.

[2]李軍俠.小波域局部貝葉斯閾值的SAR圖像斑點抑制算法[J].系統(tǒng)工程與電子技術(shù)，2006，6.

[3]徐牧.基于目標輪廓特征的SAR圖像目標識別[J].系統(tǒng)工程與電子技術(shù)，2006，12.

[4]田金文.基于圖像分割的SAR圖像匹配方法[J].華中科技大學學報（自然科學版），2006，10.

第8篇：匹配算法論文范文

一、研究目標

（1）為各學校提供一套機制合理、符合學生需求、具備學術(shù)跟蹤研究價值的基于體能測試結(jié)果分析的體育選課指導系統(tǒng)。

（2）根據(jù)不同的體育項目特征建立體能測試指標體系，將運動項目與體能測試結(jié)合，推進我國體能測試數(shù)據(jù)的合理分析利用和研究，同時加快各校的體育教改步伐。

（3）本系統(tǒng)具備長期跟蹤研究的價值，通過體育項目與體能測試的匹配結(jié)果的長期跟蹤，可以不斷調(diào)整匹配算法的精度，從而使得體育項目的指標體系模型更加合理、準確，為后續(xù)研究者提供寶貴的資料；對學生偏愛的體育項目以及學生的成績可以跟蹤研究，為我國學生體質(zhì)健康狀況的預測提供依據(jù)。

（4）具備數(shù)理統(tǒng)計功能以及反饋評價、調(diào)節(jié)功能。

二、研究內(nèi)容

對設(shè)計和開發(fā)基于體能測試結(jié)果分析的選課系統(tǒng)的相關(guān)模型研究、設(shè)計思想、實現(xiàn)技術(shù)的描述主要通過5個部分進行描述。

（1）介紹了課題的背景和研發(fā)的必要性及重要性，簡單介紹了將要研究的內(nèi)容、課題要實現(xiàn)的目標、選課制的教育思想來源、網(wǎng)絡(luò)選課系統(tǒng)的現(xiàn)狀分析以及本研究采用的技術(shù)路線。

目前學生的自主選課方式存在很大的盲目性，一方面學生不知道自己的體質(zhì)狀況，另一方面學生沒有正確認識各個課程教學大綱的主旨。同時學生每年參加體能測試，這些能全面反映學生體質(zhì)狀況的數(shù)據(jù)卻沒有得到合理利用。這使得教學大綱、學生的體質(zhì)素質(zhì)、教學管理三者之間的矛盾不斷凸顯。

（2）首先通過介紹學生體質(zhì)測試指標體系模型的構(gòu)成以及數(shù)據(jù)來源的處理，建立學生體質(zhì)指標體系的主要指標；然后介紹了運動項目的指標體系，運動項目指標體系是通過體能測試的大類指標體系來劃分的（見表1），同時關(guān)聯(lián)學生的運動項目成績作為另外一個調(diào)節(jié)指標建立的指標體系；最后介紹二者之間匹配體系的建立機制，它主要是對學生體質(zhì)指標的每個子項與運動項目子項匹配、學生體質(zhì)測試指標整體與運動項目整體匹配，并比較各個匹配結(jié)果，找到匹配中最大可能性的結(jié)果。建立了上述指標體系后需要將其應(yīng)用到體育教學實踐中，才能檢驗建立指標體系的價值以及指標體系的合理性。

（3）介紹了基于學生體質(zhì)測試的體育選課指導系統(tǒng)的實際需求。通過系統(tǒng)要實現(xiàn)的總體目標、系統(tǒng)功能需求、系統(tǒng)性能需求等幾個方面，闡述符合多生源、專業(yè)特色明顯、體育選課落后特點的體育選課系統(tǒng)的實際需求。

（4）介紹了基于學生體質(zhì)測試的體育選課指導系統(tǒng)的具體設(shè)計與實現(xiàn)。包括系統(tǒng)設(shè)計的原則、系統(tǒng)總體設(shè)計、系統(tǒng)功能設(shè)計、數(shù)據(jù)庫的設(shè)計。

學生登錄選課系統(tǒng)后進入選課子系統(tǒng)（如圖1所示），此子系統(tǒng)提供的功能包括選課系統(tǒng)、成績查詢、教學質(zhì)量測評、選課歷史分析、信息維護、新聞公告等幾個模塊。

點擊選課系統(tǒng)后進入選課界面（如圖2所示），學生可以根據(jù)運動類別選擇課程，此處運動類別是根據(jù)運動項目指標體系建立的，主要考慮到學生可以針對體能測試結(jié)果有針對性地選擇運動項目類別，以提高體質(zhì)中較差的部分，同時也可以通過智能提示功能匹配出最符合學生體質(zhì)素質(zhì)的運動項目，讓學生在不斷發(fā)揮自身優(yōu)勢的同時提高體質(zhì)。

學生可以點擊課程匹配則僅匹配當前的課程，如果點擊智能匹配則會匹配運動項目指標體系中的所有運動項目，并推薦出三種最佳的選課方案?？紤]體育課一學期只能學一門，此處一次選課只能選擇一門課。例如學生選擇編號為22的籃球課程時，可以點擊課程匹配功能，則系統(tǒng)會通過單項匹配與綜合指標匹配，并將匹配結(jié)果通過曲線圖的方式展示給學生，同時顯示當前課程與最佳課程之間的匹配相似度，其界面如圖3所示。

（5）介紹基于學生體質(zhì)測試的體育選課指導系統(tǒng)的具體實現(xiàn)。包括體質(zhì)測試成績與運動項目匹配實現(xiàn)、選課系統(tǒng)整體實現(xiàn)、應(yīng)用部署實現(xiàn)等。其中主要介紹了通過體質(zhì)測試指標體系與運動項目體系關(guān)聯(lián)分析的模式匹配方式，以及選課系統(tǒng)的熱區(qū)計算算法、匹配距離算法。

四、結(jié)論與建議

本研究利用體能測試結(jié)果指導學生選課與教師教學，并且通過數(shù)字化方式予以實現(xiàn)，這將為后續(xù)研究者提供很好的參考價值。然而由于筆者主要從事體育教育行業(yè)，接觸軟件工程行業(yè)時間短，因此本文重在通過體育專業(yè)知識建立指標體系，然后通過計算機實現(xiàn)研究理論，以下方面是以后值得研究的方向：

（1）系統(tǒng)建立體質(zhì)測試分析工具，可以根據(jù)地區(qū)、年段等統(tǒng)計學生的體質(zhì)測試走向，并能通過學生歷史體質(zhì)測試曲線，預測未來的體質(zhì)測試曲線。

（2）建立該系統(tǒng)并應(yīng)用到體育選課中后，系統(tǒng)能夠通過長期跟蹤研究使得運動項目標準曲線更加精確，同時能夠做到長期預測匹配。系統(tǒng)目前只能匹配出當年的選課計劃，未來可以考慮實現(xiàn)通過學生的體質(zhì)測試提出選課計劃或者運動計劃，例如學生在選籃球課時，如果學生的耐力與速度不夠，提示學生首先選擇提升耐力的運動項目，然后選擇提升速度的運動項目，最后才選擇籃球。通過這樣的長期規(guī)劃指導學生選課，可能會使指導更加精確。

參考文獻

[1] 孫偉偉，龔喜娟. 2005年我國青年男子籃球運動員冬訓體能測試成績分析[J].山西師大體育學院學報：研究生論文?？?006（S1）：108-109.

[2] 孫慶偉，陳歐，馬宏敏.當前我國高校體育教學面臨的新問題及其發(fā)展對策[J].實踐與探索，2010（2）：259-260.

[3] 李俠功，王海飛.對我國高校體育教學現(xiàn)狀的思考[J].內(nèi)江科技，2010（1）：66.

[4] 曲科宇.高校體育教學對學生心理健康的關(guān)注[J].民營科技，2010（1）：61.

第9篇：匹配算法論文范文

關(guān)鍵詞：凌陽單片機，電視機，語音識別，聲控選臺

 

1 、引言

隨著科技的發(fā)展和社會文化事業(yè)的進步，電視機可供觀眾選擇的頻道數(shù)目日益增多。但是傳統(tǒng)的電視遙控方法需要觀眾記憶每個電視臺對應(yīng)的頻道序號，否則就無法快捷地將頻道切換到所需位置。這顯然給用戶帶來了很大的不方便。本文利用凌陽科技有限公司專門為語音處理而設(shè)計研制出的16位單片機SPCE061A設(shè)計了一個彩電智能聲控選臺系統(tǒng)。該系統(tǒng)無需對電視機做任何改動。在保留原有遙控功能的基礎(chǔ)上，實現(xiàn)語音控制選臺，較好地解決了記憶頻道這個難題。

2 、系統(tǒng)總體方案設(shè)計

系統(tǒng)總體方案如圖1所示。

圖1　系統(tǒng)總體方案

3、各功能模塊設(shè)計

3.1 語音命令提取單元

語音命令提取單元（如圖2所示）在電視話音和其它噪音背景下，完成提取出操作者語音命令功能，其示意圖如圖3所示。

圖2　語音命令提取單元

MIC選用駐極體送話器， 它具有結(jié)構(gòu)簡單、重量、體積小、頻率響應(yīng)寬、保真度好等優(yōu)點，但靈敏度低， 必須再加放大器才行。由于輸出阻抗可高達 10

數(shù)量級，所以必須進行阻抗變換后才能與放大配合使用。放大器采用差分放大電路，一個駐極體話器面對送話者， 其輸出接放大器正向輸入端；另個駐極體送話器背對送話者，其輸出接放大器負向入端。由于兩個送話器相對于電視機和其它噪聲源位置基本一樣遠，可以近似認為通過二者輸入的干是一樣的。但考慮到送話器具有方向性，前者送入的操作者語音命令遠遠大于后者，適當選擇各電阻值可以抵消掉各種干擾。論文參考網(wǎng)。

3.2 語音命令識別單元

語音命令識別單元采用凌陽公司的SPCE061A單片機，這是一種語音識別系統(tǒng)級芯片，實際上是一個DSP+MCU，并將A/D、D/A、RAM、ROM以及預放、功放等電路集成在一個芯片上的系統(tǒng)，擁有強大的語音數(shù)據(jù)處理能力并具有良好的接口功能。

語音識別控制系統(tǒng)結(jié)構(gòu)圖3所示

圖3　語音識別控制系統(tǒng)結(jié)構(gòu)圖

3.3 語音識別算法

消費類電子產(chǎn)品中的語音識別主要為孤立詞識別，它有兩種實現(xiàn)方案：一種是基于隱含馬爾科夫統(tǒng)計模型（HMM）框架的非特定人識別；另一種是基于動態(tài)規(guī)劃（DP）原理的特定人識別。它們在應(yīng)用上各有優(yōu)缺點。DP特定人識別的優(yōu)點是方法簡單，對硬件資源要求較低；此外，這一方法中的訓練過程也很簡單，不需預先采集過多的樣本，不僅降低了前期成本，而且可以根據(jù)用戶習慣，由用戶任意定義控制項目的具體命令語句，因而適合大多數(shù)家電遙控器的應(yīng)用。

3.3.1 端點檢測方法

影響孤立詞識別性能的一個重要因素是端點檢測準確性。在10個英語數(shù)字的識別測試中，60毫秒的端點誤差就使識別率下降2%。對于面向消費類應(yīng)用的語音識別芯片系統(tǒng)，各種干擾因素更加復雜，使精確檢測端點問題更加困難。為此，李虎生等在參考文獻5中提出了稱為FRED(Frame-based Real-time EndpointDetection)算法的兩級端點檢測方案，提高端點檢測的精度。第一級對輸入語音信號，根據(jù)其能量和過零率的變化，進行一次簡單的實時端點檢測，以便去掉靜音得到輸入語音的時域范圍，并且在此基礎(chǔ)上進行頻譜特征提取工作。第二級根據(jù)輸入語音頻譜的FFT分析結(jié)果，分別計算出高頻、中頻和低頻段的能量分布特性，用來判別輕輔音、濁輔音和元音；在確定了元音、濁音段后，再向前后兩端擴展搜索包含語音端點的幀。FRED端點檢測算法根據(jù)語音的本質(zhì)特征進行端點檢測，可以更好地適應(yīng)環(huán)境的干擾和變化，提高端點檢測的精度。

3.3.2 模板匹配算法

DTW是典型的DP特定人算法， 為了克服自然語速的差異，用動態(tài)時間規(guī)整方法將模板特征序列和語音特征序列進行匹配，比較兩者之間的失真，得出識別判決的依據(jù)。

為了提高DTW識別算法的識別性能和模板的穩(wěn)健性，采用了雙模板策略，第一次輸入的訓練詞條存儲為第一個模板，第二次輸入的相同訓練詞條存儲為第二個模板，希望每個詞條通過兩個較穩(wěn)健的模板來保持較高的識別性能。

綜上所述，本語音識別系統(tǒng)采用了改進端點檢測性能的FRED算法，12階Mel頻標倒譜參數(shù)（MFCC）作為特征參數(shù)，使用雙模板訓練識別策略。通過一系列測試，證明該系統(tǒng)對特定人的識別達到了很好的識別效果。

3.4 控制面板

為了能輸入字段號， 以便建立語音樣本，SPCE061A單片機擴展了一個行列矩陣式非編碼鍵盤。鍵盤共有12個按鍵， 其中十個定義為：0～9 數(shù)字鍵，一個定義為：語音樣本建立鍵（TRN），一個定義為：語音樣本清除鍵（CLR ）。由于控制面板只在建立語音樣本時使用，為防止誤操作，應(yīng)將這12個按鍵用塑料外殼封閉起來。論文參考網(wǎng)。

3.5 操作指示電路

采用兩片數(shù)碼管和譯碼驅(qū)動電路CC4558組成操作指示電路。在本系統(tǒng)中，操作指示電路的作用是：建立語音命令樣本時，用于顯示存入的字段號；語音命令識別時用于顯示識別結(jié)果及芯片識別結(jié)果的處理報告。

3.6 邏輯控制電路

整個邏輯控制電路如圖4 所示。SPCE061A單片機通過并行接口輸出識別結(jié)果，經(jīng)過邏輯控制電路進行必要的譯碼后，用來控制后面的紅外發(fā)射裝置。

圖4　邏輯控制電路如圖4

3.7 遙控發(fā)射電路

紅外遙控發(fā)射器主要由三大部分組成：一是鍵盤矩陣，二是發(fā)射專用集成電路，三是放大驅(qū)動和紅外線發(fā)射部分。該電路與電視機的特定型號有關(guān)，可以根據(jù)電視機品牌選用適當?shù)膶Ｓ眉t外發(fā)射電路。論文參考網(wǎng)。需要說明的是：由于不同品牌電視機的紅外發(fā)射、接收電路各不相同，因此它只對兼容電視有效。

4、結(jié)束語

該系統(tǒng)不對彩電做任何改動。在保留原有遙控功能的基礎(chǔ)上，實現(xiàn)語音控制選臺，主要功能有：

開關(guān)電視：電視接通電源處于待命狀態(tài)，操作者發(fā)出“開機”命令，則打開電視機；操作者發(fā)出“關(guān)機”命令，則關(guān)掉電視機。

選臺功能：操作者想看某某電視臺的節(jié)目，只要發(fā)出“某某臺”的命令，電視機就自動跳轉(zhuǎn)到該臺。

識別主人功能：為防止誤操作，該系統(tǒng)只對事先錄入命令樣本的操作者語音敏感，其他人發(fā)出的命令包括電視伴音均無效。

其它功能：具有電視音量、畫面亮度調(diào)節(jié)等適合語音控制的功能。

由于采用了高性價比的SPCE061A這種語音識別系統(tǒng)級芯片，并設(shè)計了科學的算法，本系統(tǒng)可靠性高，價格低廉，使用方便，具有較好的市場前景。

參考文獻

[1] 趙力．語音信號處理[M] ．北京: 機械工業(yè)出版社，2003

[2] 李晶皎．嵌入式語音技術(shù)及凌陽l6位單片機應(yīng)用[M]．北京：北京航空航天大學出版社，2003

[3] 李虎生等. 高性能漢語數(shù)碼語音識別算法[J] ．北京：清華大學學報（ 自然科學版），2000；40：( 1)

[4] 孫景琪. 遙控彩色電視機集成電路及應(yīng)用[M]．北京：人民郵電出版社，1995

[5] 胡延平等. 電視機智能聲控選臺系統(tǒng)設(shè)計與實現(xiàn)[J] ．通訊與電視，2001( 1)

[6] 周季華等. 語音識別在家電遙控器中的應(yīng)用 [J] ．計算機應(yīng)用，2002( 8)